Вычислительная сложность машинного обучения. Базовые принципы

Чуть ранее, в статье временная сложность алгоритмов машинного обучения, я разбирал временную сложность некоторых алгоритмов из библиотеки scykit-learn. Настало время немного подробнее остановиться на том, как в принципе считается вычислительная сложность data science.

Вычислительная сложность (или асимптотическая сложность или производительность) — это свойство алгоритма. Она определяется функцией, которая показывает насколько ухудшается работа алгоритма с усложнением поставленной задачи.

Вот пять основных правил расчета вычислительной сложности:

если для математической функции \(f\) алгоритму необходимо выполнить действия \(f(N)\) раз, то для этого ему понадобится сделать \(O(f(N))\) шагов.
если алгоритм выполняет одну операцию, состоящую из \(O(f(N))\) шагов, а затем вторую, состоящую из \(O(g(N))\) шагов, то общая производительность f и g суммируется \(O(f(N) + g(N))\)
если алгоритму необходимо сделать \(O(f(N) + g(N))\) шагов и область значений N функции \(f(N)\) больше чем у \(g(N)\), то вычислительную сложность можно упростить до \(f(N)\)
если алгоритму внутри каждого шага \(O(f(N))\) одной операции приходится выполнять еще \(O(g(N))\) шагов другой операции, то общая производительность составляет \(O(f(N)*g(N))\)
постоянными множителями (константами) можно пренебречь: \(O(C*f(N))\) и \(O(f(C*N))\) можно записать как \(O(f(N))\)

Нотация «O» большое всего лишь указывает на то, что мы рассматриваем ситуацию, когда алгоритму для завершения необходимо потребить максимальное возможное количество (худший случай). В предыдущей статье рассматривался частный случай, входящий в обобщенное понятие вычислительной сложности — временная сложность алгоритмов МО. Грубо говоря, объем задачи алгоритма всегда связан с вычислительными ресурсами — временем (или количеством шагов) вычислений и пространством (или объемом памяти), необходимыми для завершения задачи. Поэтому в различной специальной литературе по машинному обучению, где рассматриваются частные случаи алгоритмов, можно встретить отсылки как к вычислительной сложности в целом так и к сложности по времени или по памятми.

На практике чаще всего встречаются следующие сложности:

\(O(1)\) вне зависимости от сложности задачи время выполнения алгоритма постоянно
\(O(\log(N))\) на каждом шаге алгоритма происходит деление количества рассматриваемых элементов на фиксированный коэффициент
\(O(N)\) рост числа входов вызывает линейный рост производительности
\(O(N*\log(N))\) алгоритм с логарифмической сложностью, на каждом шаге которого производится дополнительная операция с каждым элементом
\(O(N^2)\) перебор всех данных, а затем повторный их перебор. Степень может быть другой, что, очевидно, влияет на сложность вычислений.
\(O(2^N)\) экспоненциальная сложность и \(O(!N)\) факториальная сложность

Задачи со сложностью до \(O(N*\log(N))\) включительно решаемы. При грамотном управлении количеством входных данных решаемы и задачи со степенной сложностью. Экспоненциальные и факториальные сложности, в виду в целом большого входного объема данных, в МО неприменимы.

Ключевым вопросом в оценке сложности алгоритмов МО является их класс, определяющий требования ко времени и ресурсам памяти, применительно к некой абстрактной машине (часто рассматривается детерминированная машина, в частности, машина Тьюринга). Для детерминированных машин определены следующие классы:

\(DTIME(f(N))\) задачи, которые машина решает за время \(f(N)\). Временная сложность таким образом будет составлять \(O(f(N))\)
\(P\) задачи, с которыми машина справляется за полиномиальное время
\(EXPTIME(EXP)\) задачи, с которыми машина справляется за экспоненциальное время

Для недетерминированных машин:

\(NTIME(f(N))\) задачи, которые машина решает за время \(f(N)\). Временная сложность, таким образом будет, составлять \(O(f(N))\)
\(NP\) задачи, с которыми машина справляется за полиномиальное время
\(NEXPTIME(EXP)\) задачи, с которыми машина справляется за экспоненциальное время

Аналогичным образом задачи делятся в зависимости от потребляемого объема памяти.

Не вдаваясь в подроности, в общем случае \(P \subseteq NP\), экспоненциальные задачи, по сути, не считаемые, а задачей построения алгоритмов МО, в том числе, является их сведение к менее затратному классу. Задачи, которые входят в класс NP и к которым можно свести любые другие задачи этого класса за полиномиальное время называются NP-полными. NP-сложные задачи необязательно относятся к классу NP.

Время обучения для алгоритмов МО

Фактическое время работы алгоритма МО зависит от конкретной машины, на которой алгоритм реализован. В общем случае алгоритм обучения с учителем имеет доступ к множеству примеров, классу гипотез, функции потерь и обучающему набору, взятому из множества примеров. Четкого понятия размера входных данных для такого алгоритма не существует, т.к. если мы предъявляем алгоритму избыточное количество обучающих примеров, он может игнорировать лишние. Поэтому увеличение размера обучающего набора не ведет к тому, что проблема обучения становится более трудной. кроме того, алгоритм обучения может передавать часть вычислений выходной гипотезе, в случае, когда такая гипотеза определена как функция, сохраняющая обучающий набор. Для этого вводятся понятия времени обучения и времени предсказания. Будем рассматривать алгоритмы, чье время предсказания не превышает время обучения.

Вычислительная сложность алгоритма обучения определяется в два этапа:

дана функция \(f : (0, 1)^2 \rightarrow \mathbb{N}\), задача обучения \((Z, H, l)\) и алгоритм обучения \(A\). Алгоритм \(A\) решает задачу обучения за время \(O(f)\), если существует постоянное число \(c\) такое, что для любого распределения вероятности \(D\) на \(Z\) и входных параметров \(\epsilon, \delta \in (0, 1)\) справедливо следующее утверждение: если \(A\) имеет доступ к примерам, независимо выбранным из распределения \(D\), то, во-первых, \(A\) завершается, выполнив не более \(c f(\epsilon, \delta)\) операций, во-вторых, выход \(A\) обозначаемый как \(h{\scriptstyle A}\) можно применять для предсказания метки нового примера и при этом будет выполнено не более \(c f(\epsilon, \delta)\) операций и, в-третьих, выход \(A\) вероятно почти корректен, т.е. с вероятностью не ниже \(1 - \delta\) (для случайной выборки, которую получает \(A\)) \({L_{\scriptscriptstyle D}}({h_{\scriptscriptstyle A}}) \leq {\min_{\scriptscriptstyle h'\in H}} {L_{\scriptscriptstyle D}}{(h'_{\scriptscriptstyle A}}) + \epsilon\)
далее, рассматриваем последовательность проблем обучения \({({Z_{\scriptscriptstyle n}}, {H_{\scriptscriptstyle n}}, {l_{\scriptscriptstyle n}})^{\scriptscriptstyle{\infty}}_{\scriptscriptstyle n=1}}\), где проблема \(n\) описывается областью примеров \({Z_{\scriptscriptstyle n}}\), классом гипотез \({H_{\scriptscriptstyle n}}\) и функцией потерь \({l_{\scriptscriptstyle n}}\). Если \(A\) спроектирован для проблем обучения такого вида и задана функция \(g : \mathbb{N} x (0, 1)^2 \rightarrow \mathbb{N}\), то считается, что время работы \(A\) на вышеупомянутой последовательности равно \(O(g)\), если для всех \(n\) \(A\) решает проблему \(({Z_{\scriptscriptstyle n}}, {H_{\scriptscriptstyle n}}, {l_{\scriptscriptstyle n}})\) за время \(O({f_{\scriptscriptstyle n}})\), где функция \(f : (0, 1)^2 \rightarrow \mathbb{N}\) определяется выражением \({f_{\scriptscriptstyle n}}(\epsilon, \delta) = {g_{\scriptscriptstyle n}}(n, \epsilon, \delta)\)

В таком случае можно сказать, что алгоритм \(A\) эффективен на последовательности \(({Z_{\scriptscriptstyle n}}, {H_{\scriptscriptstyle n}}, {l_{\scriptscriptstyle n}})\), если его время работы равно \(O(p(n, 1/\epsilon, 1/\delta))\) для некоторого полинома p. Очевидно, что вопрос об эффективном решении проблемы обучения зависит от того, как именно задача обучения представлена в виде последовательности конкретных проблем.

Более подробную информацию на эту тему можно найти в учебнике «Understanding Machine Learning», изданном в Cambridge University Press в 2014-ом году.

Подробнее о нотации в асимптотическом анализе и про временную сложность в машинном обуче6нии