Мысли и теория

Трансформатор Галеркина: однократный эксперимент на NeurIPS 2021

Путешествие любителя вычислительной математики по математической теории и приложениям механизма внимания.

Пролог

Недавно я написал свою первую статью о машинном обучении¹ как забавном, но сложном побочном проекте вместе с репозиторием с открытым исходным кодом, содержащим коды: https://github.com/scaomath/fourier-transformer.

Будучи полным новичком и независимым исследователем в этой области, я достаточно сумасшедший и глупый, чтобы отправить эту статью на NeurIPS 2021… благодаря поддержке моего наставника.

Я подумал, что название было довольно броским, так как при поиске по запросу Трансформатор Галеркина наверху была бы ссылка на статью arXiv. Для математика-любителя это название будет означать, что это больше похоже на статью типа развлекайся, а не нацеливаясь на публикацию. Затем я увидел несколько других очевидных отправок NeurIPS с использованием шаблона LaTeX с такими заголовками, как Anti-Koopmanism, Max-Margin is Dead, Long Live Max-Margin!, You Never Cluster Alone ». Несомненно, эти CS люди действительно серьезно относятся к этому.

Сама статья - полутеоретическая, полуэкспериментальная. Мне кажется, что даже несмотря на то, что все используют Трансформеры, потому что Внимание - это все, что вам нужно ², даже для задач резюме, сказать, что «математика, лежащая в основе механизма внимания, не совсем понятна» даже немного преуменьшение. Едва ли существует какое-либо строгое теоретическое обоснование, чтобы математически объяснить, почему внимание будет работать таким волшебным образом.

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

Попытка впервые объяснить аппроксимационную способность механизма внимания с помощью метода Галеркина из теории приближений в гильбертовых пространствах.

[1]: Цао С. (2021 г.). Выберите Трансформатор: Фурье или Галёркин. В препринте arXiv arXiv: 2105.14995.

[2]: Васвани А., Шазир Н., Пармар Н., Ушкорейт Дж., Джонс Л., Гомес А. Н., Кайзер Л. и Полосухин И., 2017. Внимание - это все, что вам нужно. . Препринт arXiv arXiv: 1706.03762.

Задний план

Оператор самовнимания математически определяется следующим образом: 𝐲 ∈ ℝⁿ × ℝᵈ - входное скрытое представление, запрос Q, ключи K, значения V вместе с матрицами проекций W ^ Q, W ^ K, W ^ V

Масштабируемый скалярный продукт внимания:

Полное внимание: для g (⋅) поточечный универсальный аппроксиматор (в данном случае нейронная сеть прямого распространения)

Во многих статьях по интерпретации механизма самовнимания в Внимание - это все, что вам нужно, включая некоторые недавние попытки, аналогии с «интерпретацией ядра» или, скажем, связывание Softmax (QKᵀ ) V в качестве обучаемой карты ядра - обычная практика. Softmax (QKᵀ) описывается как мера сходства для вектора характеристик каждой позиции (заученные вложения токенов) с таковой для каждой другой позиции. Некоторые известные линеаризации преобразователей, нормализованных по softmax, используют эту интерпретацию.

Я подумал, что жизнь была бы бесконечно проще, если бы она была без softmax, и мы изменили интерпретацию с по строкам на по столбцам. Так позвольте нам это сделать!

Попытка улучшить механизм внимания на основе математической интуиции

Теперь предположим, что j -й столбец Q, K, V как (отдельные) функции qⱼ (⋅), kⱼ (⋅), vⱼ (⋅), выбранные на физическом местоположения xᵢ ∈ ℝᵐ для i = 1,…, n вместе с zⱼ (⋅), обозначающим результат масштабированного скалярного произведения. Затем, (QKᵀ) V вместе с некоторыми оговорками по поводу пропуска соединений, внимание без softmax превращается в уравнение Фредгольма второго рода:

с κ (x, ξ): = ζ_q (x) ⋅ϕₖ (ξ) для карт характеристик:

Интерпретация механизма внимания как интеграла не нова, например, интеграл по группе был использован в LieTransformer³.

Тем не менее, введение интеграла в рисунок предлагает более интересную интерпретацию линейного варианта без softmax: Q (KᵀV) можно рассматривать как проекцию Петрова-Галеркина (если мы рассматривать столбцы Q, K, V как независимые функции):

где 𝔟 (⋅, ⋅) - билинейная форма, определенная на бесконечномерных гильбертовых пространствах, но в действии оцениваемая для дискретных приближений. Чтобы помочь нам понять, мы можем обратиться к следующим двум рисункам, чтобы увидеть, как жизнь становится намного проще без softmax.

Теперь, чтобы связать приведенное выше выражение для линейного внимания без softmax с чем-то, с чем мы знакомы, мы можем дополнительно подумать о QR -факторизации или даже о проекции в наборе d ортогональные базисные функции {qⱼ (⋅)} ⱼ₌₁ᵈ:

Неудивительно, что решение представляет собой проекцию, аналогичную явному выражению для решения линейной регрессии: если мы предположим, что {qⱼ (⋅)} дополнительно нормализуется его индуцированной внутренним произведением нормы (подумайте о нормализации экземпляра с дополнительным весом 1 / √n).

Чтобы увидеть конкретный пример: пусть Ω = [0,2π] и qⱼ (x) = sin (jx ) и cos (jx), то приведенное выше уравнение представляет собой просто приближение частичной суммы ряда Фурье для f (x) и частный случай в (PG).

Вдохновленный этой интерпретацией, предлагается следующий простой оператор внимания типа Галеркина:

нет softmax вообще. Нормализация уровня выполняется для скрытых представлений перед выполнением скалярного произведения, точно так же, как можно рассматривать базис Фурье как имеющий нормализацию перед внутренним произведением,

[3]: Хатчинсон, М., Лан, К. Л., Заиди, С., Дюпон, Э., Тех, Ю. В., и Ким, Х. (2020). LieTransformer: Эквивариантное внимание к себе для групп Ли. Препринт arXiv arXiv: 2012.10885.

Обучение оператора

Теперь, когда задумано новое внимание, возникает вопрос:

Где мы подготовим почву для этого нового оператора внимания?

Несмотря на то, что некоторые первоначальные прототипы предлагают многообещающие результаты на оценочных тестах BLEU на IWSLT14 (En-De) с использованием fairseq (например, гораздо более быстрое обучение), для меня проблема обучения операторов, связанная с уравнениями в частных производных, была бы естественным выбором. . Цикл прототипирования-отладки-улучшения слишком длинный для меня как независимого исследователя, если я решаю большую и трудную проблему обработки естественного языка (НЛП).

В прошлом году мой наставник прислал мне сообщение в блоге (на китайском языке) о том, что группа машинного обучения Caltech достигла высочайшего уровня производительности с помощью так называемого нейронного оператора Фурье (FNO) ⁴ для изучения оператора решения PDE. Внимательно прочитав его, проанализировав коды и заново реализовав его сам, я полностью склонился к ногам этого опасного подхода, поскольку он на порядки превосходит предыдущие методы. Более того, реализация убедила меня, что общий Q/K/V подход во внимании становится FFT->conv->iFFT. Это изменение представляет собой особый и эффективный линейный вариант механизма внимания, при котором матрицы проекции не обучаются. Быстрое преобразование Фурье (БПФ) или его обратное можно рассматривать как необучаемое изменение базиса путем умножения матрицы Вандермонда. В реальном механизме внимания все веса для (нелинейного) изменения базиса можно обучить.

Самое главное, что практика в FNO показывает одно

Перспективным подходом является обработка столбцов скрытого представления для выполнения операций, а не строк (вектор признаков позиций).

До недавнего времени (по состоянию на май 2021 г.) сообщество ML начало ценить это направление, например, в [5] и [6].

Ну что в результате? Комбинация внимания с FNO безумно хороша, и преобразователь на основе внимания Галеркина также может решить сложную задачу идентификации обратных коэффициентов (см. Рисунки выше). При той же квоте параметров в тесте уравнения Бюргерса модель с 4 слоями внимания Галеркина + 2 слоями FNO превосходит модель с 4 слоями FNO в 4 раза при тех же лабораторных условиях (1cycle планировщик с той же скоростью обучения, 100 эпох ), и в 10 раз лучше оригинала с Batchnorm. Общий диапазон средней относительной ошибки оценки в L² -норме составляет 1e-3 с максимальным значением 1.7e-3. Тесты в потоке Дарси вместе с его обратной версией свергнули короля (FNO) также с точки зрения точности оценки. Обучение трансформатора Галеркина происходит медленнее, чем у FNO, несмотря на то, что теоретически он имеет тот же порядок сложности.

За исключением структурированных сетей нейронных операторов, предложенных группой Caltech, следующий ближайший конкурент, DeepONets, намного хуже… (см. Страница 14, рисунок 10 для этого единственного случая, имеющего 3e-2 относительную ошибку). Поскольку сеть в DeepONets напоминала аддитивное внимание в нейронной машине Тьюринга (NMT), вполне предсказуемо, что DeepOnets, несмотря на то, что структура, эвристически соответствующая математике, труднее обучать из-за композиции нескольких сложных нелинейностей, таких как как гиперболический тангенс и сигмоиды.

[4]: Ли, З., Ковачки, Н., Азиззаденешели, К., Лю, Б., Бхаттачарья, К., Стюарт, А., и Анандкумар, А. (2020). Нейронный оператор Фурье для параметрических уравнений в частных производных. Препринт arXiv arXiv: 2010.08895.

[5]: Толстихин, И., Хоулсби, Н., Колесников, А., Бейер, Л., Чжай, X., Унтертинер, Т., Юнг, Дж., Кейзерс, Д., Ушкорейт, Дж., Лучич , М. и Досовицкий, А., 2021. Mlp-микшер: архитектура all-mlp для видения. Препринт arXiv arXiv: 2105.01601.

[6]: Ли-Торп, Дж., Эйнсли, Дж., Экштейн, И., и Онтанон, С. (2021). FNet: смешивание токенов с преобразованиями Фурье. Препринт arXiv arXiv: 2105.03824.

Осторожно: в последней части ниже есть полусерьезная математика.

Что мы можем доказать? Проекция Петрова-Галеркина.

Оператор внимания или его линейный вариант является нелинейным оператором по отношению как к входным, так и к обучаемым параметрам. Как мы можем связать это с чем-то вроде проекции Галеркина или Петрова-Галеркина, которые являются линейными? Ответ прост:

Мы пытаемся доказать аппроксимирующую способность в следующем смысле в рамках гильбертовской системы.

Это означает: g_θ, аппроксиматор, построенный на внимании Галеркина, имеет свою аппроксимирующую способность наравне с проекцией Галеркина на подпространство аппроксимации 𝕍ₕ ⊂ ℋ, где ℋ - гильбертово пространство, и мы хотим, чтобы моделировать поведение оператора на его подмножестве.

Это подпространство 𝕍ₕ является текущим на основе скрытого представления и во время оптимизации динамически изменяется. Тем не менее, в статическом представлении фиксированного латентного представления механизм внимания обладает способностью предоставлять лучший аппроксиматор, проекцию типа Галеркина, в текущих пространствах аппроксимации.

Сложности: преодоление нелинейного отображения с линейной проекцией

Можно спросить: разве это не тривиально? Ну, вроде как, (F) именно тот случай, когда 𝕍ₕ: = span {vⱼ (⋅)}. Однако при более внимательном рассмотрении может оказаться не так просто математически изложить этот результат кристально ясным образом. Вот трудности:

  • В отличие от настройки пространства в проекции Галеркина, подпространства аппроксимации, представленные Q/K/V, различны.
  • Как линейно объединить столбцы Q, чтобы получить каждый столбец вывода z в (PG), зависит от каждого столбца продукта KᵀV. Однако не совсем ясно, достаточно ли определенного столбца KᵀV, чтобы дать коэффициенты для получения проекции Галеркина или Петрова-Галеркина для любой функции f ∈ ℋ. Причина в том, что ни Q/K/V не гарантируется полного ранга, ни сюръективность нелинейного внутреннего продукта.

Простой пример, иллюстрирующий сложность

В контексте любого линейного варианта внимания:

Q обозначает значения, K - запрос, а V - ключи.

Давайте рассмотрим простой пример, где Ω = (−1,1), дискретизированный по −1 = x₁ ‹x₂‹ ⋯ ‹xₙ = 1 . Q пространство колоночного приближения состоит из первых двух многочленов Чебышева {1, x }, а у K и V - {a, bx} и {c, dx} для a, b, c, d∈ ℝ можно изучить. Фактические столбцы составляются с помощью оценки этих функций в xᵢ, с фиксированным количеством точек сетки n для выборки. Отметим, что длина последовательности n может быть изменена в конвейере обучения операторов.

Теперь для f ∈ ℋ, L² -проекция f на ℚₕ: = span { 1, x} равно:

При интерпретации столбцов K / V как функций, выбранных в сетках, скалярное произведение KᵀV / n становится приближением к интегралу и легко проверить:

В этом случае, после дополнительной простой проверки, мы можем увидеть, что KᵀV / n может воспроизвести коэффициенты проекции в (L) путем простого умножения на вектор (f₁, f₂) ᵀ.

Однако что, если столбцы K и V будут изменены на оценки {a, bx} и {cx, dx } в точках сетки?

Внезапно способность воспроизводить коэффициенты в (L) исчезает! Потому что после умножения этой матрицы на Q: подпространство, представленное столбцами Q (KᵀV ) не имеет постоянной функции! Заинтересованный читатель может это проверить.

Конечно, это чрезмерное упрощение, позволяющее:

Но ты получил идею.

Доказательство: проблема перевала в гильбертовых пространствах

Используя мою собственную методику (смешанный метод конечных элементов), мы можем показать, что Q (KᵀV) обладает способностью достигать того, что может аппроксимировать проекция Петрова-Галеркина, при условии, что что имеет место следующее:

Существует сюръективная карта ключевого пространства (V в линейном внимании) в пространство ценностей (Q в линейном внимании).

В функциональном анализе это также можно рассматривать как условие теоремы о близких пределах или условие Ладыженской – Бабушки – Брецци в контексте аппроксимации операторного уравнения. Если кого-то из наших читателей интересуют подробности, обратитесь к Приложению D к статье.

Используя язык непрофессионала, чтобы перевести математический смысл доказательства линейного внимания, это:

Для наилучшего приближения (проекция Петрова-Галеркина) в пространстве значений существует по крайней мере один ключ, соответствующий входящему запросу и доставляющий это наилучшее приближение.

Записано в виде неравенства:

где c - постоянная в условии Ладыженской-Бабушки-Брецци на дискретном пространстве аппроксимации. Если можно доказать, что c не зависит от длины последовательности, то аппроксимирующая мощность преобразователя Галеркина или любого линейного варианта преобразователя не зависит от длины последовательности. , математически доказано.

Скорее, мощность аппроксимации зависит от d_model, то есть от того, сколько базисных функций мы готовы заплатить, чтобы аппроксимировать ответы оператора на подмножестве. Идеальный мост между теорией операторов и (линейным) механизмом внимания без softmax.

Поскольку я сам выполнил этот небольшой побочный проект и в ближайшем будущем вернусь к своей собственной области (возможно, еще одна работа над многоуровневым преобразователем, использующим подпространственную природу коррекции остатка в механизме внимания), это не удивительно, если с некоторыми незначительными Если сообщество машинного обучения выяснит значение этого доказательства, используя сюръективность карты значений, через 1-2 года появятся такие вещи, как «Соболев внимание »,« Дифференциальное внимание »,« Чебышевское внимание », внимание с использованием других интегральных преобразований.

Непрерывный в континууме, устойчивый в дискретном

Для людей, незнакомых с аппроксимацией операторных уравнений в условиях Гильберта, самая большая путаница после изучения хода мыслей в статье, вероятно, будет:

Карта "ключ-значение" определяется с использованием билинейной формы. Эта билинейная форма определена на двух бесконечномерных гильбертовых пространствах, но почему в статье показана ее нижняя граница только для конечномерных дискретных аппроксимационных пространств?

Ответ длинный. Перед написанием статьи я прочитал обзоры на одну из первых статей пытаясь объяснить аппроксимационную способность математически строго с использованием ядра Мерсера. Их доказательство в основном переносило доказательство из ранней основополагающей работы на контекст банаховых пространств⁸. Судя по срокам их отправки в arXiv, можно с уверенностью предположить, что они также отправили свою работу на NeurIPS 2021 (несмотря на то, что не использовали шаблон LaTeX).

На странице открытого обзора своей заявки на ICLR 2021 рецензент 1 поднял ключевой проницательный вопрос:

Еще одна слабость в аргументе заключается в том, что ядро ​​изменяется с каждым шагом стохастического градиентного спуска. А именно, параметры W ^ Q и W ^ K обновляются, и это меняет функцию ядра. В результате обучение трансформеров не работает в едином банаховом пространстве воспроизводящего ядра.

Это одна из основных проблем, на которую авторы статьи о ядре Мерсера не ответили прямо и ясно аргументированно. Ответ на самом деле довольно прост в контексте обучения операторов:

Даже несмотря на то, что Transformer предлагает производительность, инвариантную к длине последовательности, например, модель, обученная на n = 512, может предложить ту же ошибку оценки на n = 512 или n = 2048; для одного образца предлагается аппроксимация через дискретное пространство с n точками сетки. Таким образом, теория может быть сформулирована с использованием динамически изменяющихся конечномерных аппроксимационных пространств , но единственного бесконечномерного основного гильбертова (или банахова) пространства.

Например, пространство непрерывных кусочно-линейных функций, отобранных в n точках сетки Ω, независимо от того, насколько велико это n, является подпространством L² ( Ω). Аппроксимация для каждого отдельного образца выполняется на дискретном уровне. Пространства аппроксимации динамически обновляются посредством оптимизации, но лежащие в основе бесконечномерные гильбертовы пространства (L², H¹ и т. Д. Или даже банаховы пространства, такие как Lᵖ ) не меняются!

Я чувствовал, что это была упущенная возможность для статьи о ядре Мерсера, поскольку теория приближения имеет бесконечномерный подход. Аппроксимационная мощность архитектуры Transformer по-прежнему ограничена конечномерным подпространством, ограниченным d_model, которое представляет собой количество базисных функций, оплачиваемых в нашей интерпретации, ориентированной на столбцы.

[7]: Райт, М.А., и Гонсалес, Дж. Э. (2021 г.). Трансформаторы - это глубокие бесконечномерные машины с двоичным ядром, не принадлежащие Mercer. Препринт arXiv arXiv: 2106.01506.

[8]: Окуно, А., Хада, Т., и Шимодаира, Х. (2018, июль). Вероятностная структура для изучения функций с несколькими представлениями с ассоциациями "многие ко многим" через нейронные сети. В Международной конференции по машинному обучению (стр. 3888–3897). PMLR.

Эпилог

Комитет NeurIPS 2021 решил поставить контрольный список ближе к концу формы подачи:

Контрольный список NeurIPS Paper разработан для поощрения передовых практик ответственных исследований в области машинного обучения, решения вопросов воспроизводимости, прозрачности, этики исследований и воздействия на общество.

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

  • Признание активов других людей (код, набор данных);
  • Представление исследования машинного обучения с воспроизводимыми / воспроизводимыми кодами и инструкциями;
  • Предоставление столбцов / полос ошибок в отношении различных семян.

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

Первоначально опубликовано на https://scaomath.github.io 6 июня 2021 г.