Сжатие котиков с помощью PCA

😊 Эти котики просто хотели мурчать, залезать в коробки и сталкивать всё со стола. Но сингулярность не могла обойти стороной и их тоже. Им пришлось быть пожатыми с помощью сингулярного разложения 😫.

🥹 Четыре случайно выбранных жертвы котика демонстрируют, как можно сжимать изображения с помощью truncated SVD.
Если векторизовать весь датасет, то получится матрица A размером 29843 (кол-во котиков) х 4096 (картинки 64х64 преобразуем в ч\б и вытягиваем в вектор).

😬 У этой матрицы (как и у любой другой) можно посчитать SVD и найти сингулярные векторы. Зная их и сингулярные числа - легко спроецировать котиков в пространство меньшей размерности, а так же восстановить матрицу исходного размера, но меньшего ранга, оставив ненулевыми только r первых компонент матрицы сингулярных чисел.

😐 В таком случае в качестве векторов, на которые мы проецируем, выступают собственные векторы матрицы Aᵀ A. Эта идея использовалась в качестве системы распознавания лиц. Каждый человек раскладывался в базис таких вот eigenfaces. А сами главные компоненты (они же сингулярные векторы) для датасета котиков (или eigencats) - в комментариях к посту.

💻 Ссылка на код для построения анимации.

Простой пример, когда оптимальное снижение размерности не оптимально для вас.

🤔 Пусть перед нами стоит задача классификации данных с 2 классами (крестики и кружочки). Но при этом нам нужно снизить размерность этих данных. Вот, например, здесь размерность каждой точки на плоскости 2, а нам нужнно 1.

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

😭 Однако, при проекции на оптимальную ось, задаваемую первым сингулярным вектором матрицы данных, мы не сможем различить данные этих двух классов каким-нибудь простым правилом.

😎 А вот проекция на какую нибудь другую неоптимальную ось оставляет вам возможность различить данные линейным классификатором. Существуют другие методы supervised dimension reduction, которые легко справляются с этой проблемой (например, LDA).

💻 Ссылка на код для построения анимации.

🧠 А вот обычная анимация, иллюстрирующая идею PCA. Здесь видно, что при проекции на ось, соответствующую сингулярному вектору матрицы данных дисперсия проекций наибольшая (можно проверить, покрутив эту ось здесь).

🧠 Самая наглядная демонстрация того, что AB ≠ BA

С того самого момента, как в конце школы я узнал, что матричное умножение не коммутативно, меня одолевало возмущение.

- Да как так-то? 😡

😭 Десятки игрушеных матриц 2х2, перемноженных вручную не оставляли сомнений в этом факте, но понимания не прибавлялось.

🤓 Потом выяснилось, что поворот плоскости может быть задан матрицей 2х2. И, конечно же, если вы посмотрите на любую плоскость, вам будет сразу очевидно, что если вы сначала все повернёте на 35°, а потом на 55°, то результат таких поворотов не зависит от порядка поворотов и всегда будет равен одному повороту на 90°. А значит, произведение матриц поворота плоскости не зависит от порядка произведения и AB = BA.

🏥 Однако, совершенно внезапно оказалось, что для больших размерностей это не работает. То есть уже в трёхмерном мире порядок поворотов важен. То есть если мы знаем, что любой поворот может быть задан матрицей (такие матрицы называют унитарными или ортогональными в случае действительных чисел), то если от перемены порядка поворотов трёхмерного тела финальное положение будет меняться, то это нагляднейшее физическое воплощение того, что AB ≠ BA.

🎮 Именно это мы и наблюдаем на видосе выше. В одной из лучших игр 2023 года (The Legend of Zelda: Tears of the Kingdom) мы можем взять объект и сделать повороты сначала "вверх" на 90°, потом вправо на 90° и наоборот и сравнить результаты таких поворотов. Таким образом, уважаемые геймеры ощущают нюансы линейной алгебры и основы мироздания на кончиках пальцев 🎩.

Визуализация сжатия матрицы с помощью усечённого SVD

🤓 Теорема Эккарта - Янга - Мирского говорит, что для любой матрицы A её лучшим* приближением заданного наперёд ранга r является усечённое сингулярное разложение ранга r. То есть такая аппроксимация Aᵣ , которая получена путём суммирования r матриц ранга 1.

Aᵣ = ∑ σᵢ uᵢ vᵢᵀ

здесь σᵢ - сингулярные числа (важно, чтобы они были отсортированы по убыванию), а uᵢ vᵢ - левые и правые сингулярные вектора. Для анимации выше можно один раз посчитать SVD (A = U Σ Vᵀ) и после этого дергать соответствующие значения.

🗜️Почему это сжатие?
Потому что для того, чтобы нарисовать картинку выше для каждого ранга r нужно r строчек и r столбцов матрицы + r сингулярных чисел. То есть если раньше было, допустим 1920×1080 пикселей, то вместо 2 073 600 значений для ранга 50 надо хранить 150 050 то есть около 7% от исходной матрицы.

📝Обычно в таких демо показывают всегда черно-белые картинки, потому что это матрицы. Существует несколько способов сделать это с цветными изображениями. Напишите в комментариях как вы думаете какой из них в видосе выше?
📝Обратите внимание как быстро появляются геометрически простые формы (большие надписи, например) по сравнению с другими объектами. Маленькие надписи распознаются существенно даже медленее, чем лицо даже что напоминает как нейросети пытаются рисовать надписи - в некотором смысле это информация "высокого ранга".
📝Некоторые картинки в видосе выше сгенерированы, было интересно посмотреть есть ли какая-нибудь очевидная разница в спектрах между реальными изображениями и сгенерированными.

* по норме Фробениуса, спектральной норме и произвольной унитарно-инвариантной норме.

l₁ регуляризация стимулирует разреженность решения

🤨 При обучении линейной регрессии иногда хочется найти не просто вектор весов, с которыми надо учитывать фичи, но и стимулировать этот вектор обладать некоторыми свойствами.

📝Фишки l₂ - регуляризации (Ridge-регрессия):
* Единственность решения, чего нельзя гарантировать в исходной задаче.
* Новая задача становится лучше обусловлена.
* Задача гарантированно становится сильно выпуклой.

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

🤔 На гифке показано решение эквивалентных задач оптимизации (сверху Ridge, снизу Lasso) - выбор из шара единичной нормы вектора, который обеспечивает минимальное значение квадратичной функции потерь. Тут важно отметить, что каждому коэффициенту регуляризации на самом деле соответствует некоторый радиус такого шарика и наоборот (точной формулы соответствия, к сожалению, нет, но можно записать ККТ и приближенно найти довольно легко). Сверху и снизу нарисованы шарики в 2 норме и в 1 норме и точка на границе - это оптимальное решение. Точка рисуется красной, если одна из двух координат равна нулю. Черные концентрические линии - линии уровня квадратичных функций.

🧐 Легко видеть, что в случае l₁ - регуляризации гораздо чаще оптимальное решение - разрежено, чем в случае l₂ - регуляризации. Однако, это не бесплатное удовольствие, сама по себе задача с l₁ регуляризацией становится негладкой, что влечет за собой дополнительные проблемы (например, немонотонное убывание функции потерь, в отличие от гладкого случая при градиентном спуске).

💻 Код для построения гифки. Исходный код был отсюда.

Непредсказуемая сложность MIP

💡 Есть такая особенность в задачах целочисленного линейного программирования (Mixed Integer Programming - MIP), что по её виду не совсем понятно насколько сложной она будет.

🤔 Бывает так, что задача с миллионами переменных и ограничений решается на десктопе быстрее, чем за час, а бывают задачи с тысячами переменных/ограничений, которые до сих пор вообще никак не решены любыми средствами и солверами (в т.ч. коммерческим Gurobi).

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

📦 Датасет.
💻 Код для построения картинки.
@fminxyz

Коварный метод Ньютона

🏌️ Безнапряжная эстетика направлений движения методов оптимизации для невыпуклых задач.

🚶‍♂️Метод Ньютона легко сходится не только к минимумам (светлые области), но и к максимумам (темные области).
Дело в том, что метод строит квадратичную локальную аппроксимацию функции и если вдруг она не выпукла, то он может построить параболу ветвями вниз и уверенно проследует в её максимум.

То есть вы вроде применили метод оптимизации для минимизации функции, а она возьми и увеличься 😊. Для градиентного спуска с правильным шагом такого быть не может, антиградиент всегда смотрит в сторону локального убывания функции.

🎯 Здесь в анимации все направления стрелок отнормированы, т.е. показывают лишь направление движения метода, запущенного из точки.

💻 Код для построения анимации.
@fminxyz

Почему стохастический градиентный спуск не сходится?

👍 Многие привыкли использовать SGD(stochastic gradient descent), но не все знают, что он гарантированно(!) не сходится в случае постоянного шага (learning rate) даже для самой приятной в мире функции - сильно выпуклой квадратичной (даже в среднем).😰

🧠 Почему так? Дело в том, что в SGD на каждой итерации на самом деле решается другая задача, построенная по выбранным данным. И эта задача на батче может радикально отличаться от полной задачи (однако, внимательный читатель может отметить, что это не гарантирует очень плохой шаг😬). То есть на каждой итерации мы на самом деле сходимся, но к минимуму другой задачи, и каждую итерацию мы меняем правила игры для метода, не давая ему ему пройти больше одного шага. 👊

👀 В конце прикрепленного видео видно, что по выбранным точкам из задачи линейной регрессии можно построить оптимальное решение батчевой задачи и градиент к ней - он и будет называться стохастическим градиентом для исходной задачи. Чаще всего стохастичность SGD анализируют с помощью шума в градиенте и реже рассматривают шум, обусловленный случайностью/неполнотой выбора решаемой задачи (интересно, что это не совсем одно и то же).

Это, конечно же, не повод не применять метод, потому что сходимость к примерному решению все же гарантирована. Для выпуклых задач можно бороться с несходимостью
* постепенным уменьшением шага (медленная сходимость)
* увеличением размера батча (дорого)
* применением методов редукции дисперсии (об этом потом)

👨‍💻 Код для построения видосов.

Мам, я хочу double descent - у нас есть double descent дома!

💀 Феномен двойного спуска - явление, наблюдаемое в моделях машинного обучения, при котором при увеличении сложности модели на тестовых данных сначала наблюдается улучшение качества предсказаний (первый спуск), затем идёт ожидаемый рост ошибки (переобучение), а потом, внезапно, происходит улучшение обобщающей способности модели (второй спуск). Интересно, что похожую картинку можно получить на довольно простом примере полиномиальной регрессии. На анимации выше слева 50 точек синусоиды, которые используются в качестве train set для обучения полиномиальной регрессии.

😎 Типичное поведение при увеличении степени полинома - переобучение, т.е. почти нулевая ошибка на трейне (синих точках слева) и высокая ошибка на тесте (равномерно расположенные 100 точек на черной линии). Однако при дальнейшем увеличении сложности модели мы видим, что среди бесконечного множества решений задачи как-то выбираются более гладкие. То есть мы явно наблюдаем double descent.

🤩 Это, конечно, происходит не просто так. Конкретно в этой анимации с полиномами Чебышева среди бесконечного множества подходящих полиномиальных коэффициентов я выбирал те, что обладают наименьшей нормой. В машинном обучении часто нельзя явно так сделать, поэтому используется weight decay для выбора решений с не очень большой нормой.

👨‍💻 Код для построения анимации.

🧠 Часто в рассказах про double descent упоминают другое похожее явление - grokking. Мой коллега Антон Разжигаев у себя в канале @abstractDL выложил крутейший пост со ссылкой на свое воспроизведение этого эксперимента в домашних условиях в колабе (и там получилось). Антон - молодой исследователь, который в канале выкладывает в том числе и свои серьезные оригинальные исследования, что я особенно ценю. Так же прикрепляю ссылку на папку (вы, скорее всего, её уже видели) с авторскими телеграм каналами про ИИ - на большую часть из них я подписан лично.

https://hottg.com/addlist/C_RSYpbW5mIyMjVi

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

🤩 Продемонстрирую наглядно на примере решения задачи Multidimensional Scaling (MDS). В этой задаче нам надо нарисовать на плоскости объекты, про которые мы знаем только насколько каждый из них далеко друг от друга. Т.е. на входе у нас матрица попарных расстояний, а на выходе координаты объектов на плоскости. Причем эти координаты должны быть такими, чтобы соотношения расстояний между объектами оставалось как можно более близким к исходным. В качестве функции потерь выступает сумма квадратов отклонений расстояний между городами при текущих координатах и заданным значением.

f(X) = ∑ₘ ∑ₙ (Dₘₙ − dₘₙ(X))²

🗣 Несмотря на увеличение размерности, вся траектория метода может быть наглядно продемонстрирована на плоскости. Количество переменных в задаче здесь - 2*(количество городов), т.к. для каждого из городов мы ищем 2 координаты на плоскости.

↗️ По очереди запускается обычный градиентный спуск, требующий знания градиента, и метод Нелдера-Мида из scipy (широко используемый безградиентный метод). Сначала задача решается для 6 самых населенных европейских городов, потом для 15 и для 34 (это все города-миллионики Европы из википедии).

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

🤔 Оказывается, у градиентных методов (при наборе разумных предположений) количество итераций, необходимое до сходимости метода, не зависит напрямую от размерности задачи. То есть если вы рассмотрите корректно настроенный градиентный спуск на десятимерной задаче, то ему нужно будет, скажем, не более 20 итераций для сходимости. А если вы возьмёте условно ту же задачу, но 100500-мерную, то ему нужны будут те же 20 итераций. Конечно, стоимость одной итераций растет с ростом размерности задачи, но хотя бы их количество явно не растет.

🤩 Ставь реакцию, если видишь свой город.
💩 Код для построения анимации

Нейронная сеть Хопфилда

🏆 На этой неделе нобелевскую премию по физике дали Джону Хопфилду и Джеффри Хинтону за 

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

😲 Я, как и многие в моем окружении, сначала недоумевал, почему так и причем здесь физика. И решил заботать, что вообще такое нейронная сеть Хопфилда, и получил дикое удовольствие. Оказывается, что сама концепция заметно отличается от тех нейронных сетей, к которым мы привыкли. В этих сетях гораздо больше связи с физикой и биологией, чем в полносвязных/сверточных слоях.

🔬 Что это такое

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

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

🧠 Нейросеть как память

Таким образом, мы зафиксируем матрицу весов, соответствующую нашей текущей памяти. То есть процесс обучения сети Хопфилда - это один шаг (никаких градиентных спусков и итерационных алгоритмов - одна формула).

А потом можно возмутить состояние нейронов как угодно (при выученных весах это гарантированно приведет к увеличению энергии системы) и посмотреть на пошаговую эволюцию состояний сети во времени - она сойдется к одному из стационарных состояний, которыми являются выученные паттерны. Но когда паттернов для запоминания становится много, то появляются новые стационарные состояния, которые мы не вкладывали в сеть (их называют химерами).

🧲 Принцип минимизации энергии и магниты

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

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

⚔️👁⚔️ Выводим ящеров на чистую воду

Например, в этой анимации я обучил сеть запомнить 2 состояния - турбославянина и ящера. А потом дал ей несколько разных картинок (чтобы посмотреть, кто есть кто на самом деле), которыми инициализировал значение нейронов (возмутил систему) и нарисовал эволюцию каждой из них. Видно, как они сходятся к стационарным состояниям. Хопфилд показал, что количество паттернов, которые может запомнить такая сеть растет примерно линейно с количеством нейронов.

📺 Крутейший видос, поясняющий базу
🖥 Статья на N+1 с объяснением
🐱 Ссылка на код для построения анимации

Как ускоряли обучение GPT-2 S в 10 раз

🤩Очень интересный репозиторий Modded-NanoGPT, и набор тредов о том, как спидранили обучение GPT-2 (самой маленькой версии на 125М параметров).

😎 Результат был достигнут на 8xH100 за 4.7 минуты на PyTorch вместо 45 минут в бейзлайне (llm.c). В денежном выражении это экономия с ~$15 до ~$1.56.

Представляете, обучение GPT-2 S с нуля теперь стоит $1.5 и занимает 5 минут. А обучение XL модели ~$200 и 10 часов.

😂 Стоит обратить внимание, что всё это произошло за счёт алгоритмических/модельных улучшений. Потенциально можно все эти трюки перенести обратно с Python на C чтобы получить ещё более быстрое обучение, ведь эффективность обучения на один токен у llm.c всё равно выше (где-то на 25% для GPT- 2 XL).

🐱 Самые большие оптимизации в абсолютном времени обучения на фоне изначальных 45 минут:
* Увеличение learning rate в 3 раза (хуже работает на больших моделях) + Rotary embeddings + lr cooldown - 13.6 минут
* Padding эмбеддингов нулями до размерности, которая делится на 64 😫 + Исправление GeLU на ReLU² + QKNorm + инициадизация нулями projection слоев. - 7.1 минута
* Muon optimizer - 6.5 минут

😁Работает ли это для моделей побольше?
В комментариях прикреплю результаты оптимизаций для модели GPT-2 XL 1.6 B - обучение тоже ускорилось в абсолютном значении, но не в 10, а в 2 раза. Но там и попыток спидрана меньше. Интересно это прежде всего тем, как можно решить очень конкретную задачу, если предпринять много попыток. Нет никаких гарантий, что это будет работать для моделей в сотни миллиардов параметров или других данных.

Подбор шага с помощью линейного поиска в градиентном спуске

Если нам известны характеристики сильно выпуклой функции, то мы можем выбрать оптимальный постоянный шаг 2/(μ + L),
где μ и L – наименьшее и наибольшее собственные значения гессиана функции.

Однако на практике эти параметры почти никогда не известны. Да и функции бывают невыпуклые. Приходится подбирать learning rate вручную (перебор), линейным поиком или использовать эвристики/адаптивные алгоритмы (например, AdamW, NAG-GS).

В первой части видео мы минимизируем функцию Розенброка с помощью градиентного спуска с разными постоянными шагами, отличающимися всего в 2 раза. Разница в поведении методов – колоссальная!

Во второй части видео демонстрируются работа методов линейного поиска для решения этой задачи:
📝 Метод золотого сечения - прекрасный вариант для выпуклых функций, но если функция не унимодальна, то я не знаю гарантий сходимости для него.
📝 Неточный поиск с условиями Вульфа позволяет подобрать шаг так, чтобы он гарантировал "достаточное" убывание функции, исключая при этом слишком маленькие шаги.

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

Наглядно о том, зачем нужна нормализация признаков

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

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

Явление характерно не только для квадратичных функций - это одна из главных причин наличия разных нормализаций в нейросетях.

👨‍💻 Код для построения анимации

QR алгоритм

🥸 Одна из жемчужин численных методов. Он используется для поиска собственных чисел матрицы.

🥰 Простой и стабильный, а при небольших модификациях ещё и быстрый.

Qₖ, Rₖ = qr(Aₖ) - Вычисляем QR-разложение матрицы
Aₖ₊₁ = RₖQₖ - Умножаем факторы в обратном порядке

😑 Для произвольной квадратной матрицы он сходится к верхнетреугольной матрице, на диагонали которой стоят её собственные числа (картинка слева)

👍 Если же матрица - симметричная, то он сходится вообще к диагональной матрице собственных чисел (картинка справа).

Идея анимации взята у Gabriel Peyré - один из лучших аккаунтов по красивым математическим визуализациям. По моим предварительным исследованиям, после этого поста отпишется наибольшее количество уважаемых подписчиков.👌

😐 Код

🧬 Эволюционные алгоритмы

Полтора месяца назад DeepMind выкатил AlphaEvolve, где LLM-агент генерирует, скрещивает и отбирает фрагменты кода на основе эволюционного подхода. Так появляются новые алгоритмы — от рекордов в матричном умножении до оптимальных расписаний вычислений и топологий печатных плат для TPU. Сообщество уже откликнулось опен-сорсным OpenEvolve — можно запустить тот же процесс самому и выращивать свои программы.

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

Расписание описываем вектором моментов, когда включается красный:

1-й 🚦 5 с, 35 с
2-й 🚦 7 с, 37 с
…
n-й 🚦 3 с, 17 с

Дальше классика:

🐱 Особь - вектор расписания светофоров
🏙️ Популяция - 256 случайно сгенерированных особей
🧑‍🧑‍🧒 Скрещивание - из двух особей создаём третью, унаследовавшую их черты
🐷 Мутация - случайно меняем часть особей и возвращаем их в популяцию
💎 Отбор - подсчёт функции приспособленности - количества проехавших машин за симуляцию в нашем случае. И выбор лучших 256 особей

🌀 Цикл «популяция → скрещивание → мутация → селекция» повторяем, и каждое новое поколение едет не медленнее предыдущего.

🧐 Легко увидеть, что на обоих частях видео все светофоры одинаково горят по 2 раза красным одинаковое время. То есть уважаемые пешеходы проходят одинаково.Этот подход к решению задачи очень наивен. Есть более продвинутые формулировки и результаты. Однако, его можно применять к очень широкому классу задач.

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