В последние годы градиентный спуск стал основным инструментом для обучения нейронных сетей, который успешно применяется во множестве практических задач — от распознавания изображений до обработки естественного языка. Однако ряд исследований выявил фундаментальные ограничения методов градиентного обучения, особенно когда речь заходит о некоторых специфических функциях, таких как функция паритета. Паритет — это простая булева функция, которая возвращает значение, зависящее от чётности количества единичных бит во входном векторе. Несмотря на очевидную простоту, обучение функции паритета с помощью классических градиентных алгоритмов оказывается чрезвычайно сложной задачей. Попытаемся разобраться, почему так происходит и как это связано с теоретическими основами машинного обучения и методами оптимизации нейросетей.
Функция паритета и её особенности Функция паритета определяется на битовых строках фиксированной длины. Вход представляет собой последовательность из нулей и единиц, а выход — это либо 1, либо -1 (в математическом представлении), в зависимости от того, сколько единичных бит содержится в определённом подмножестве входа. Если количество единичных бит чётное, результат, например, равен 1, если нечётное — -1. С точки зрения теории вычислимости и логики, паритет — классический пример функции, демонстрирующей значительную сложность для различных алгоритмов обучения. Её особенность заключается в том, что для любой подвыборки битов сложно однозначно определить, как именно эта функция формирует значение, если мы имеем ограниченное число примеров.
В худшем случае для точного восстановления целевой функции паритета необходимо предоставить практически всю пространство входных данных — то есть количество примеров должно расти экспоненциально с длиной входа. Кроме того, существует множество функций паритета, которые дают одинаковый результат для заданного подмножества входов, из-за чего обучение становится неоднозначным. Сложности градиентного спуска в обучении функции паритета Градиентный спуск в контексте обучения нейросетей – это итеративный алгоритм, который на каждом шаге корректирует параметры модели, стремясь минимизировать функцию ошибки. При обучении функции паритета мы пытаемся настроить веса нейросети так, чтобы её выход точно повторял значение паритета на входных данных. Однако ключевая проблема, как показали исследования Омара Шамира и коллег, состоит в том, что градиенты функции ошибки оказываются практически неинформативными для выбора правильного направления оптимизации.
Градиенты для различных функций из семейства паритетов очень похожи, и эта их схожесть приводит к тому, что сигнал, который передаёт ошибка, сливается с шумом и не даёт возможности корректно идентифицировать нужную функцию. Другими словами, даже если нейросеть инициализирована случайным образом и подвергается достаточно большому числу шагов градиентного спуска, она в значительной степени не сможет «уловить» конкретную функцию паритета, которую нужно выучить. В рамках математических доказательств это проявляется в том, что дисперсия градиентов по всей совокупности паритетных функций убывает экспоненциально с ростом размерности входных данных. Низкая дисперсия означает, что независимо от цели обучения — конкретной функции паритета — градиент будет практически идентичен и не предоставит дифференцирующего сигнала для корректировки весов. Эта фундаментальная трудность обусловлена природой функции паритета, в которой выход зависит от четко определенного набора позиций входных битов и требует учета их взаимного влияния.
В стандартных нейросетевых архитектурах и алгоритмах оптимизации, построенных на основе дифференцируемости и локальных аппроксимаций, подобные функции становятся практически неразрешимыми для эффективного обучения. Последствия для практического машинного обучения Описанная теоретическая картина находит отражение и в практических экспериментах. Например, система SATNet, разработанная группой исследователей во главе с Ваном и коллегами, использует дифференцируемый SAT-солвер, который способен решать задачи логического вывода с помощью непрерывных оптимизационных методов. При всём своём успехе с некоторыми классами задач, SATNet также демонстрирует трудности, связанные с обучением функции паритета, предупреждая о том, что одноразрядные метки в обучающем сигнале оказываются слишком бедными для обычных градиентных методов в этой специфической задаче. Однако интересно, что SATNet и аналогичные методы в некоторых случаях успешно обучают полную функцию паритета длины четыре, что кажется контрастом с утверждениями о невозможности обучения.
Эта кажущаяся парадоксальность связана с тем, что SATNet вводит сильные индуктивные смещения в архитектуру, что ограничивает пространство изучаемых функций, тем самым облегчая обучение в малом объёме данных. Таким образом, несмотря на теоретическую сложность, на практике удаётся добиться успеха благодаря архитектурным особенностям и дополнительным предположениям о данных. Теоретическое доказательство сложности обучения функции паритета В основе теоретических доказательств лежит анализ дисперсии градиентов функции ошибки по семейству паритетов, обозначаемому как множество Н. Изучается вариация градиента функции ошибки при различных целевых функциях из этого семейства. Теорема Омара Шамира гласит, что при слишком низкой дисперсии градиентного сигнала — экспоненциально убывающей с ростом числа битов — любой алгоритм, построенный на приближённом вычислении градиента, спустя неэкспоненциальное число шагов обучения будет сходиться к параметрам, не зависящим от обучаемой функции.
В техническом аспекте доказательства используется ряд лемм и теорем из линейной алгебры и теории вероятности: свойства умножения функций, ортонормированные базисы в гильбертовых пространствах и неравенство Бесселя. Эти инструменты позволяют показать, что функция паритета формирует класс сложных векторов в пространстве функций, которые почти ортогональны друг другу, и на фоне этого ортогонального множества градиенты усредняются и теряют индивидуальные особенности. В итоге, если рассматривать алгоритм оптимизации с приближённым градиентом, существует способность возбудителя «подставлять» усреднённый по всем функциям градиент, который технически уложится в заданную погрешность, мешая процессу обучения выделить правильные параметры. Это означает, что для достоверного обучения необходима значительная вычислительная и выборочная мощь, что выходит за пределы возможностей стандартных методов для больших значений длины входа. Влияние длины входных данных и масштабируемость задачи Основным ограничивающим фактором в обучении функции паритета остаётся экспоненциальный рост сложности с увеличением длины входа.
Параметры и количество возможных функций растут экспоненциально, а информационный сигнал, необходимый для корректного неквалифицированного обучения, становится практически недостижимым. Из-за этого алгоритмы, основанные на градиентном обучении, не масштабируются и не могут эффективно работать с большими входными размерами. Таким образом, когда длина входного вектора достаточно мала (например, четыре бита), подходы с учетом индуктивного сдвига могут успешно найти решение. Но при увеличении размерности классические алгоритмы градиентного спуска задерживаются в локальных плоских участках функции ошибки — так называемых плато — и не находят корректный ответ без дополнительной информации или структурных предположений. Перспективы и альтернативные подходы Проблема обучения функции паритета с помощью градиентного спуска указывает на существование фундаментальных ограничений подходов, основанных на дифференцируемом обучении.
Это стимулирует исследователей обращать внимание на разработку индуктивных смещений в архитектурах моделей, использование гибридных методов, объединяющих логические и дифференцируемые компоненты, а также более сложные алгоритмы оптимизации, способные справляться с плоскостями низкой вариативности градиента. Кроме того, в некоторых работах предлагаются методы, опирающиеся на непрерывные релаксации дискретных процессов, как в случае SATNet, где непрерывное пространственное представление позволяет частично преодолевать дискретные ограничения логических функций. Однако эти способы пока эффективны ограниченно в зависимости от сложности задачи и размера входных данных. Заключение Функция паритета является важным эталоном в понимании границ возможностей современных методов машинного обучения. Несмотря на многочисленные успехи нейросетей, парадоксальная сложность, заложенная в простом с виду булевом операторе, показывает, что градиентные методы имеют значительные теоретические и практические ограничения.
Основной причиной является исчезновение информативного сигнала в градиентах при обучении на полноценном пространстве функций паритета. Эти результаты имеют большое значение для понимания природы обучения и подчеркивают необходимость новой теоретической и практической базы, которая сможет эффективно подходить к задачам с высокой логической сложностью и дискретной природой. В будущем развитие гибридных моделей, усиление индуктивных предположений и исследования в области сложных алгоритмов оптимизации помогут преодолеть существующие барьеры в обучении таких функций, как паритет.
