Вычислительная сложность обучения нейронных сетей

Материал из MachineLearning.

(Различия между версиями)

Версия 14:07, 13 июля 2026

Статья написана с использованием LLM Claude Sonnet 5 и проверена участником Gadel Mahmutov 18:07, 13 июля 2026 (MSD)

Промпт приводится полностью в Обсуждение:Вычислительная сложность обучения нейронных сетей

Вычислительная сложность обучения нейронных сетей — раздел теории вычислительной сложности и теории машинного обучения, изучающий ресурсы (время, память), необходимые для настройки параметров искусственной нейронной сети по обучающей выборке. Задачу обучения можно анализировать на двух принципиально разных уровнях: практическом — сколько элементарных операций требует один шаг градиентного спуска при фиксированной архитектуре, и теоретическом — существует ли вообще алгоритм, гарантированно находящий веса сети за время, полиномиальное от размера задачи, в худшем случае. Как будет показано ниже, эти два уровня дают качественно разные ответы: с точки зрения теории сложности задача обучения сети общего вида является NP-трудной уже для крайне простых архитектур, тогда как на практике сети с миллиардами параметров успешно обучаются градиентными методами за приемлемое время. Понимание этого разрыва существенно для инженерной интуиции: отсутствие теоретических гарантий не означает невозможности практического успеха, а отсутствие видимых трудностей на практике не отменяет экспоненциальной сложности в худшем случае.

Содержание

1 Постановка задачи
2 Сложность вычисления градиента: прямой и обратный проходы
3 Теоретическая сложность задачи обучения
4 Переизбыточная параметризация и полиномиальная сходимость
5 Вычислительная сложность обучения больших моделей: законы масштабирования
6 Практические способы снижения вычислительной сложности
7 Исторический очерк
8 См. также
9 Примечания
10 Литература

Постановка задачи

Пусть архитектура сети фиксирована: задан граф вычислений с $L$ слоями, функциями активации и $W$ обучаемыми параметрами (весами и смещениями). Задача обучения формулируется как задача заполнения (англ. loading problem): по обучающей выборке $\{(x^i, y^i)\}_{i=1}^{N}$ найти вектор весов $\theta \in \mathbb{R}^W$ , минимизирующий эмпирический риск

$L(\theta) = \sum_{i=1}^{N} \ell\bigl(f_\theta(x^i), y^i\bigr),$

где $f_\theta$ — функция, реализуемая сетью с весами $\theta$ , а $\ell$ — функция потерь. Часто рассматривают её "решательный" вариант: существует ли $\theta$ , при котором $L(\theta)=0$ , то есть сеть точно воспроизводит выборку. Именно эта решательная формулировка используется в классических результатах о NP-полноте.

Важно различать три отдельных источника сложности:

сложность одного шага оптимизации — стоимость вычисления $f_\theta(x)$ и его градиента по $\theta$ ;
сложность оптимизационной задачи в целом — число шагов, необходимое итерационному методу для достижения приемлемого значения $L(\theta)$ , и вопрос о существовании глобально оптимального решения, достижимого за полиномиальное время;
сложность задачи в худшем случае — принадлежность задачи заполнения тому или иному классу сложности (P, NP, NP-трудный и т. д.).

Сложность вычисления градиента: прямой и обратный проходы

Прямое распространение

Для полносвязной сети, в которой слой $l$ содержит $n_l$ нейронов, вычисление выхода слоя сводится к умножению матрицы весов размера $n_{l-1}\times n_l$ на вектор активаций предыдущего слоя. Стоимость такого умножения — $O(n_{l-1} n_l)$ операций. Суммируя по всем слоям, получаем, что стоимость прямого прохода (forward pass) через сеть пропорциональна общему числу весов $W$ , то есть составляет $O(W)$ элементарных арифметических операций на один обучающий пример^[1].

Обратное распространение ошибки

Метод обратного распространения ошибки (англ. backpropagation) — стандартный способ вычисления градиента функции потерь по всем весам сети, независимо предложенный в разных формах П. Вербосом в 1970-е годы и популяризованный работой Д. Румельхарта, Дж. Хинтона и Р. Уильямса в 1986 году^[1]. Алгоритм представляет собой применение правила дифференцирования сложной функции (chain rule) в режиме обратного автоматического дифференцирования (reverse-mode automatic differentiation): производные распространяются от выходного слоя к входному, при этом каждая промежуточная величина вычисляется ровно один раз и переиспользуется.

Ключевой теоретический факт, известный как «принцип дешёвого градиента» (cheap gradient principle), состоит в том, что стоимость вычисления градиента константно-кратна стоимости вычисления самой функции: для функций, составленных из элементарных арифметических операций, эта константа не превышает 5, а для рациональных функций — 3^[1]. Отсюда следует, что обратный проход также имеет сложность $O(W)$ , а полная сложность вычисления градиента по одному примеру — $O(W)$ , то есть того же порядка, что и прямой проход. Для сети с $N$ обучающими примерами и $T$ шагами (эпохами) оптимизации итоговая вычислительная сложность обучения по методу градиентного спуска оценивается как $O(N \cdot W \cdot T)$ .

Для рекуррентных сетей применяется вариант алгоритма — метод обратного распространения ошибки во времени (BPTT), в котором сеть «разворачивается» во времени на глубину, равную длине последовательности; сложность прохода растёт линейно с длиной последовательности, а требуемая память — тоже линейно, что на практике ограничивает длину обрабатываемых последовательностей^[1].

Стоимость обучения больших моделей: эмпирическое правило

Для трансформерных архитектур принято приближённое эмпирическое правило: если сеть имеет $N$ параметров и обучается на выборке из $D$ токенов, то суммарное число операций с плавающей точкой (FLOPs) на прямой проход одного токена составляет приблизительно $2N$ , а с учётом обратного прохода (который вычислительно эквивалентен двум прямым — отдельно по входным активациям и по весам) — приблизительно $6N$ на токен. Тогда полная вычислительная стоимость обучения оценивается как

$C \approx 6ND,$

это соотношение лежит в основе современных законов масштабирования языковых моделей^[1].

Теоретическая сложность задачи обучения

Теорема Блюма — Ривеста

Основополагающий отрицательный результат о вычислительной сложности обучения был получен А. Блюмом и Р. Ривестом. Они показали, что для двухслойной сети из трёх узлов (два скрытых нейрона с пороговой функцией активации и один выходной), решение задачи заполнения — то есть проверка существования весов, при которых сеть безошибочно классифицирует заданную обучающую выборку, — является NP-полной задачей^[1]. Это крайне важный результат: аналогичная задача для одного перцептрона (порогового нейрона без скрытого слоя) решается за полиномиальное время методами линейного программирования, но добавление всего одного дополнительного скрытого узла переводит задачу в класс NP-полных.

Доказательство строится через сведение к задаче о трёхмерном паросочетании (англ. 3-dimensional matching), которая, как известно, является NP-полной. Практический смысл теоремы: любой универсальный алгоритм обучения такой сети либо будет работать сверхполиномиальное время на некоторых входах, либо не гарантирует нахождения весов, безошибочно воспроизводящих выборку, — если, разумеется, не выполняется гипотеза $P=NP$ .

Обобщения

Дж. С. Джадд в монографии 1990 года дал систематическое, более общее описание вычислительной сложности задачи обучения (loading problem) для широкого класса архитектур с фиксированной топологией, показав, что интрактабельность задачи заполнения — не артефакт конкретной конструкции Блюма и Ривеста, а типичное свойство многоузловых сетей^[1]. Впоследствии NP-полнота или NP-трудность задачи обучения была установлена и для других классов сетей, в том числе для глубоких пороговых сетей^[1].

Долгое время оставался открытым вопрос о сложности обучения сетей с активацией ReLU, которая не является пороговой и обладает нетривиальными свойствами субдифференцируемости. Д. Буб, С. Дей и Г. Лан показали, что задача обучения даже простой сети с двумя ReLU-нейронами в скрытом слое (архитектура «2-ReLU NN») NP-трудна, при этом доказательство существенно отличается от порогового случая, так как ReLU не допускает прямой комбинаторной интерпретации разделяющих гиперплоскостей^[1]. Одновременно те же авторы показали, что при фиксированной размерности входа задача решается за полиномиальное от числа примеров время, а при достаточной избыточной параметризации первого слоя (число нейронов не меньше числа обучающих примеров) существует полиномиальный алгоритм, гарантированно находящий веса с нулевой ошибкой на обучающей выборке — наблюдение, тесно связанное с эффектами переизбыточной параметризации, обсуждаемыми ниже.

Отдельное направление составляют результаты о так называемой криптографической сложности обучения: А. Кливанс и А. Шерстов показали, что задача обучения пересечений полупространств (частный случай, к которому сводятся некоторые архитектуры пороговых сетей) трудна не только в худшем случае, но и в усреднённом смысле — при условии существования криптографически стойких генераторов псевдослучайных чисел не существует эффективного алгоритма обучения даже в модели PAC-обучения с шумом^[1]. Это усиливает вывод Блюма и Ривеста: трудность задачи не является «хрупким» артефактом конкретной конструкции наихудшего случая, а имеет более фундаментальную природу, связанную с криптографическими предположениями.

Как совместить теоретическую трудность с практическим успехом

Результаты о NP-полноте относятся к наихудшему случаю (worst case): они гарантируют существование хотя бы одной трудной выборки для данной архитектуры, но не утверждают, что все или «типичные» выборки одинаково трудны. Сами Блюм и Ривест отмечали, что доказательства «хрупки» и не переносятся автоматически на любые другие сети^[1]. На практике успех градиентных методов обучения объясняется, среди прочего, следующими факторами:

реальные данные и решаемые задачи далеки от специально сконструированных «трудных» инстансов;
современные сети сильно переизбыточны по параметрам относительно объёма обучающей выборки, что, как показано ниже, качественно меняет геометрию ландшафта функции потерь;
используются не точные, а приближённые (эвристические) методы поиска весов, для которых гарантия глобальной оптимальности не требуется — достаточно достижения приемлемого значения ошибки.

Переизбыточная параметризация и полиномиальная сходимость

С конца 2010-х годов появился ряд результатов, показывающих, что при достаточной ширине сети (числе нейронов в скрытых слоях) градиентный спуск сходится к глобальному минимуму эмпирического риска за полиномиальное время, причём с высокой вероятностью по случайной инициализации весов. Ключевым техническим инструментом стало понятие нейронного касательного ядра (Neural Tangent Kernel, NTK), введённое А. Жако, Ф. Габриэлем и К. Хонглером: при устремлении ширины сети к бесконечности динамика обучения градиентным спуском становится эквивалентна обучению линейной модели относительно фиксированного ядра^[1].

На основе этой идеи С. Ду с соавторами и, независимо, Ц. Аллен-Чжу с соавторами доказали, что для двухслойной сети с ReLU-активацией и достаточно большим числом скрытых нейронов (полиномиальным от числа обучающих примеров и обратной величины наименьшего собственного значения соответствующей ядерной матрицы Грама) случайно инициализированный градиентный спуск сходится к глобальному минимуму квадратичной функции потерь с линейной скоростью — то есть задача обучения переизбыточной сети решается за полиномиальное время, несмотря на невыпуклость и негладкость целевой функции^[1]^[1].

Эти результаты дают частичное объяснение упомянутого выше парадокса: теорема Блюма — Ривеста говорит о трудности задачи для сетей минимального размера, тогда как современная практика, наоборот, использует заведомо избыточные по числу параметров сети, для которых в определённом режиме (называемом «ленивым обучением», lazy training) существуют полиномиальные гарантии сходимости. Однако у этих гарантий есть оговорки: требуемая степень переизбыточности во многих ранних работах была очень высокой (полиномы высокой степени от числа примеров), а полученный режим не всегда точно описывает поведение сетей конечной, используемой на практике ширины.

Вычислительная сложность обучения больших моделей: законы масштабирования

Начиная с конца 2010-х годов для языковых моделей на основе архитектуры трансформер эмпирически установлены степенные зависимости («законы масштабирования») между вычислительным бюджетом обучения, числом параметров модели, объёмом обучающих данных и итоговым значением функции потерь. Дж. Каплан с соавторами (OpenAI) показали, что тестовая ошибка убывает по степенному закону от числа параметров $N$ , объёма данных $D$ и вычислительного бюджета $C$ в широком диапазоне масштабов^[1]. Позднее Дж. Хоффманн с соавторами (DeepMind), пересмотрев экспериментальный протокол (в частности, схему изменения скорости обучения), показали, что при фиксированном вычислительном бюджете параметры модели и объём обучающих данных следует масштабировать примерно в равной пропорции, а не наращивать преимущественно число параметров, как это подразумевалось в более ранней работе — так называемые Chinchilla-оптимальные законы масштабирования^[1].

Эти законы важны для практика не как теоретические гарантии сложности, а как инструмент планирования: зная формулу $C \approx 6ND$ и целевое качество модели, можно заранее оценить необходимый объём вычислений и данных, а также выбрать компромисс между размером модели и продолжительностью обучения при фиксированном бюджете.

Практические способы снижения вычислительной сложности

Поскольку точные гарантии полиномиальности в худшем случае либо отсутствуют, либо требуют значительной переизбыточности, на практике вычислительную нагрузку обучения снижают за счёт инженерных приёмов, не меняющих класс сложности задачи, но существенно уменьшающих константы и эффективное время работы:

стохастическая оптимизация — использование стохастического градиентного спуска и его вариантов (мини-батчи) вместо полного градиента по всей выборке на каждом шаге, что снижает стоимость одной итерации с $O(NW)$ до $O(BW)$ , где $B \ll N$ — размер мини-батча;
распределённое и параллельное обучение — разбиение вычислений по данным (data parallelism) или по параметрам модели (model/tensor parallelism) между несколькими вычислительными устройствами;
пониженная точность вычислений (mixed precision) — использование форматов с меньшей разрядностью (например, 16-битных вместо 32-битных чисел), ускоряющее матричные операции на современных ускорителях;
разреженность и обрезка сети (pruning), а также методы дистилляции и квантования, снижающие эффективное число параметров, участвующих в вычислениях;
эффективные архитектуры внимания для трансформеров, снижающие квадратичную по длине последовательности сложность операции внимания.

Эти методы относятся к области практической, а не теоретической сложности: они не отменяют результатов о NP-трудности задачи обучения в общем случае, а обеспечивают приемлемое время работы эвристических (не гарантированно оптимальных) алгоритмов на данных, встречающихся на практике.

Исторический очерк

Идея использования правила дифференцирования сложной функции для настройки весов многослойных сетей восходит к работам П. Вербоса, который в диссертации 1974 года (Гарвардский университет) впервые описал схему, впоследствии названную обратным распространением ошибки, в контексте задач прогнозирования^[1]. Алгоритм получил широкую известность после публикации Д. Румельхарта, Дж. Хинтона и Р. Уильямса в журнале Nature в 1986 году, что дало толчок «второй волне» интереса к нейронным сетям^[1].

Практически одновременно с ростом интереса к обучаемым многослойным сетям в конце 1980-х годов появились и первые отрицательные теоретические результаты. Работа А. Блюма и Р. Ривеста 1988–1992 годов о NP-полноте обучения трёхузловой сети^[1] и последовавшая за ней монография Дж. Джадда 1990 года^[1] заложили основы теории вычислительной сложности обучения нейронных сетей как самостоятельного направления. Эти результаты, наряду с ограниченными успехами практического применения на тогдашних вычислительных мощностях, стали одним из факторов спада интереса к нейросетевым методам в 1990-е — начале 2000-х годов.

Возрождение интереса к глубоким сетям в 2010-е годы, связанное с ростом доступных вычислительных мощностей (в первую очередь, графических процессоров) и объёмов данных, сместило акцент исследований в практическую плоскость. Введение понятия нейронного касательного ядра (2018) и последующие результаты о полиномиальной сходимости градиентного спуска для переизбыточных сетей^[1]^[1]^[1] дали первое строгое теоретическое объяснение того, почему на практике простые градиентные методы столь эффективно обучают сети, для которых в общем случае задача заполнения NP-трудна. Параллельно, с ростом масштабов языковых моделей во второй половине 2010-х — начале 2020-х годов, сформировалось эмпирическое направление законов масштабирования^[1]^[1], сместившее акцент вычислительной сложности с вопроса «разрешима ли задача» на вопрос «сколько вычислений нужно потратить для достижения заданного качества».

См. также

Примечания

Литература

Blum A., Rivest R. L. Training a 3-node neural network is NP-complete // Neural Networks. — 1992. — Vol. 5, No. 1. — P. 117–127.
Judd J. S. Neural Network Design and the Complexity of Learning. — Cambridge, MA: MIT Press, 1990. — 150 p. — ISBN 978-0-262-10045-8.
Klivans A. R., Sherstov A. A. Cryptographic hardness for learning intersections of halfspaces // Journal of Computer and System Sciences. — 2009. — Vol. 75, No. 1. — P. 2–12.
Boob D., Dey S. S., Lan G. Complexity of Training ReLU Neural Network // Optimization Letters. — 2022. (препринт: arXiv:1809.10787, 2018.)
Baur W., Strassen V. The complexity of partial derivatives // Theoretical Computer Science. — 1983. — Vol. 22. — P. 317–330.
Rumelhart D. E., Hinton G. E., Williams R. J. Learning representations by back-propagating errors // Nature. — 1986. — Vol. 323. — P. 533–536.
Werbos P. J. Backpropagation through time: what it does and how to do it // Proceedings of the IEEE. — 1990. — Vol. 78, No. 10. — P. 1550–1560.
Jacot A., Gabriel F., Hongler C. Neural Tangent Kernel: Convergence and Generalization in Neural Networks // Advances in Neural Information Processing Systems 31 (NeurIPS 2018). — 2018.
Du S. S., Zhai X., Poczos B., Singh A. Gradient Descent Provably Optimizes Over-parameterized Neural Networks // International Conference on Learning Representations (ICLR), 2019.
Allen-Zhu Z., Li Y., Song Z. A Convergence Theory for Deep Learning via Over-Parameterization // Proceedings of the 36th International Conference on Machine Learning (ICML), 2019. — P. 242–252.
Kaplan J., McCandlish S., Henighan T., Brown T. B., Chess B., Child R., Gray S., Radford A., Wu J., Amodei D. Scaling Laws for Neural Language Models. — arXiv:2001.08361, 2020.
Hoffmann J., Borgeaud S., Mensch A. et al. Training Compute-Optimal Large Language Models. — arXiv:2203.15556, 2022.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BD%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D1%8B%D1%85_%D1%81%D0%B5%D1%82%D0%B5%D0%B9»

@@ Строка 1: / Строка 1: @@
+{{well|Статья написана с использованием LLM '''Claude Sonnet 5''' и проверена участником [[Участник:Gadel Mahmutov|Gadel Mahmutov]] 18:07, 13 июля 2026 (MSD)
+Промпт приводится полностью в [[Обсуждение:Вычислительная сложность обучения нейронных сетей]]}}
 '''Вычислительная сложность обучения нейронных сетей''' — раздел теории вычислительной сложности и теории машинного обучения, изучающий ресурсы (время, память), необходимые для настройки параметров [[искусственная нейронная сеть|искусственной нейронной сети]] по обучающей выборке. Задачу обучения можно анализировать на двух принципиально разных уровнях: '''практическом''' — сколько элементарных операций требует один шаг [[градиентный спуск|градиентного спуска]] при фиксированной архитектуре, и '''теоретическом''' — существует ли вообще алгоритм, гарантированно находящий веса сети за время, полиномиальное от размера задачи, в худшем случае. Как будет показано ниже, эти два уровня дают качественно разные ответы: с точки зрения теории сложности задача обучения сети общего вида является [[NP-полная задача|NP-трудной]] уже для крайне простых архитектур, тогда как на практике сети с миллиардами параметров успешно обучаются градиентными методами за приемлемое время. Понимание этого разрыва существенно для инженерной интуиции: отсутствие теоретических гарантий не означает невозможности практического успеха, а отсутствие видимых трудностей на практике не отменяет экспоненциальной сложности в худшем случае.
@@ Строка 38: / Строка 40: @@
 </tex>
-это соотношение лежит в основе современных [[законы масштабирования|законов масштабирования]] языковых моделей<ref name="kaplan">Kaplan J. et al. Scaling Laws for Neural Language Models. — arXiv:2001.08361, 2020.</ref>.
+это соотношение лежит в основе современных [[закон масштабирования нейронных сетей|законов масштабирования]] языковых моделей<ref name="kaplan">Kaplan J. et al. Scaling Laws for Neural Language Models. — arXiv:2001.08361, 2020.</ref>.
 == Теоретическая сложность задачи обучения ==