fmin.xyz

В начале октября вышел ежегодный отчет State of AI Report 2024

🔗Ссылка

Помимо обзора прогресса за последний год, в конце есть секция с предсказаниями (в прошлом репорте 5 из 10 предсказаний сбылась, 3 не сбылись). Поставлю интуитивные имхо 🟢/🔴, если согласен/не согласен - проверим через год.

1️⃣ Вложение более 10 млрд $ от государства в крупную американскую AI лабораторию вызовет проверку на уровне национальной безопасности.
🔴 Такое вообще бывало? Чтобы в критически важную технологию вкладывали так много другие государства?

2️⃣ Приложение или сайт, созданные без навыков программирования, станут вирусными и попадут в Топ-100 App Store.
🟢 Было и в докурсорную эпоху.

3️⃣ Крупные AI лаборатории внесут значимые изменения в процесс сбора данных после первых судебных разбирательств.
🔴 Нет.

4️⃣ Раннее внедрение AI акта ЕС окажется мягче, чем ожидалось, после опасений по поводу избыточных мер.
🟢 Будут смягчать, но не сильно.

5️⃣ Open-source альтернатива OpenAI o1 превзойдет её по ряду тестов на рассуждение.
🟢 Если речь идет про текущую версию модели OpenAI, то звучит допустимо.

6️⃣ Конкуренты не смогут нанести серьезный удар по позиции NVIDIA на рынке.
🟢 GPUs go brrr...

7️⃣ Инвестиции в человекоподобных роботов сократятся из-за сложностей с выводом продукта на рынок.
🔴 Наивно хочу верить, что нет.

8️⃣ Успешный запуск Apple Intelligence на устройствах усилит интерес к персональному AI на девайсах.
🟢 Да.

9️⃣ Статья, сгенерированная AI, будет принята на крупной ML конференции или воркшопе.
🔴 Ахаха, учитывая рандом при review, если достаточно много людей попробуют провернуть этот трюк, то вполне. А на воркшопы иногда берут, глядя на форму, а не на суть. Но здесь в оригинальной версии написано "generated by an AI Scientist" - т.е. я думаю, что фокус на создании нетривиальной научной идеи. Думаю, что это будет, но не в ближайшем раунде.

🔟 Игра с элементами Generative AI достигнет феноменальной популярности.
🔴 Я бы сузил этот тезис до диалоговой системы/геймплейной фишки в играх, основанной на LLM/диффузионке. Я бы очень хотел в такое поиграть, но большие проекты делаются не за год, я пока ни о чем таком не слышал. Если же понимать под элементами GenAI создание ассетов или текстов во время разработки - то это, очевидно, давно есть.

В комменты прикреплю файлы с презентацией. Что думаете?
Туда же прикреплю подкаст, сделанный с помощью NotebookLM из этих гуглслайдов в один клик (очень хорошо, жаль пока только на английском)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

https://t.me/addlist/C_RSYpbW5mIyMjVi

Сегодня я планировал быть в Барселоне, рассказывать нашу работу по квантизации LLM на конференции UAI, но т.к. мой шенген делают уже больше месяца, я был вынужден использовать последнюю диффузионную модель Stable Paint, чтобы добавить меня к постеру, который, к моей большой радости, всё же был представлен @Ivan_Oseledets.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Визуализация сжатия матрицы с помощью усечённого 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% от исходной матрицы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шары в разных нормах

Вот как выглядят единичные шарики в разных p-нормах на плоскости. Отмечу, что для p < 1 функция вида sum(|x_i|^p)^{1/p} уже не будет нормой - не будет выполняться требование неравенства треугольника. Однако, для 0 < p < 1 эта штука будет квазинормой.

😡 Где шары?
👋 Один сломал, другой потерял!

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

🏎 Адаптивные градиентные алгоритмы

Смотреть на точки, скатывающиеся с поверхности минимизируемой функции - моё guilty pleasure.
Ставь Липшица👍, если тоже любишь такие гифки.

P.S. В комментах прикреплю видео, где модный lion пытается нарисовать свастон в знак протеста против слишком высокого learning rate.

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

Идею можно расширить, взяв два случайных вектора w₁, w₂ (которые по счастливой случайности в пространствах большой размерности будут с высокой вероятностью ортогональны) и посчитать уже

L(θ + α w₁ + β w₂)

и построить такие красивые 3д картинки.
Такой способ визуализации можно использовать, когда хочется проверить влияние какого-то конкретного эффекта на получаемые веса у модели. Например, если сама функция исходно выпуклая, то все её проекции будут тоже выпуклыми, поэтому если даже на таких одномерных проекциях будет заметна невыпуклость, то мы точно убедились в невыпуклости исходной функции.
Так, в одной из самых известных статьей (ссылка) показывают, что skip connection в ResNet существенно сглаживает двумерные проекции функции потерь. Надо при этом понимать ограничения подхода. Например, в статье авторов из физтеха показано, что при правильном выборе направления проекции можно получить эмблему бэтмена или корову.

🫡 Ссылка на код. Обратите внимание, что графики выше могут быть построены за считанные секунды в jax благодаря использованию jit и vmap. Но про это ещё потом поговорим. Можно строить визуализации для своих архитектур.

🤔 Статья в которой можно без запуска кода потрогать ручками визуализации в браузере.

😮 Как заглянуть в стотыщмерное пространство

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

Представьте, что у вас есть набор весов вашей нейронной сети θ (пусть он будет стотыщмерным, как на примере ниже).
Так вот если вы сгенерируете случайный вектор такого же размера w₁ и будете считать значения функции потерь вдоль случайно выбранного направления 

    L(θ + α w₁),

то сможете построить график L(α), где α - скалярная переменная из наперед заданного отрезка. Это будет называться проекция на случайно выбранное одномерное пространство.

Ниже пример проекции функции потерь простенькой сверточной нейронной сети, обученной на датасете FashionMNIST. Здесь, например, видно, что одна и та же сеть, обученная с дропаутом в одинаковых услових даёт наглядно меньшее различие между train и test. Мы надеемся, что в исходном пространстве большей размерности дела обстоят примерно так же (гарантий нет, но есть кеки, об этом дальше)

Хочу поделиться важными новостями.

🌐 Во-первых, на моем ютуб канале недавно образовалась целая тысяча уважаемых подписчиков. Ходить по улицам становится всё тяжелее, а рука уже отсохла от раздачи автографов, но я готов нести бремя селебы ради методов оптимизации 🙄.
В этом учебном году я планирую читать семинары\лекции по оптимизации не только на физтехе. Так что если вам интересно в режиме реального времени участвовать в этих курсах, то подписывайтесь, видосы там будут.

💥 Во-вторых, летом я работал над несколькими важными сюжетами в области образования, часть из них почти доведены до ума. Так что на канале будут посты. Для начала посмотрите на красоту ниже ⬇️

Градиентный спуск для линейной регрессии

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

🫡 Ссылка на код.
🤔 Статья о постановке задачи оптимизации.