fmin.xyz Telegram Gönderileri

QR алгоритм

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

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

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

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

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

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

😐 Код

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

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

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

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

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

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

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

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

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

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

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

О чем пишут на ICLR 2025

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

Всего в датасете около 9600 работ (подано вроде чуть больше), а самые популярные категории (фул картинки и полный датасет в комментариях):

1797: large language models
592: diffusion models
458: reinforcement learning
291: transformers
280: graph neural networks
247: generative models
222: deep learning
210: benchmark
210: representation learning
194: interpretability
175: ai safety
160: alignment
160: multimodal large language models
135: in-context learning
128: federated learning
119: optimization

В начале октября вышел ежегодный отчет 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