منشورات fmin.xyz على Telegram

Непредсказуемая сложность 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. Но про это ещё потом поговорим. Можно строить визуализации для своих архитектур.

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