Разбираемся в ML без воды: от базы до Attention. Часть 2

Итак, в предыдущей части мы остановились на поиске решения задачи линейной регрессии. Сформулировали в общем виде задачу машинного обучения, поняли суть параметров, рассмотрели функции ошибок и начали копать в сторону линейной регрессии.
Ещё раз повторю, что этот цикл статей является лишь взглядом на ML с моей колокольни, так что он не обязательно является истиной ~~во всех редакциях~~ в последней инстанции. Так что буду рад всякому, кто исправит меня, коли сверну не туда.

Что дальше?

После постановки задачи линейной регрессии можно подумать о следующем: Ежели так сошлись звезды что мы пытаемся найти вектор методом умножения матрицына некий вектор весов $\omega$ , то раз в XIX-XX веках умные люди придумали всё нужное, почему бы и не решить задачу аналитически? На самом деле, в теории это возможно. Подход называется по-разному — и МНК и нормальное уравнение, но идея крайне проста. Итак, как говорится։

Осторожно, злая ~~собака~~ математика.

Рассмотрим уравнение $X\omega = y$ , где искомое, естественно, $\omega$ .

Казалось бы, задача для третьего класса школы [(с) В. И. Арнольд]: чтобы найти $\omega$ , нужно просто умножать обе части на матрицу $X^{-1}$ . И, просто умножив обе части уравнения на нее получим: $X^{-1}X\omega = X^{-1}y$ , откуда получаем $\omega = X^{-1}y$ .

В идеальном мире это так, но у нас есть огромная(!) проблема.
Дело в том, что обратную матрицу $X^{-1}$ можно найти только для квадратных матриц (и то, далеко не для всех, но для наглядности, пока опустим это). А у нас матрица — это таблица данных. Строк в ней — это количество объектов (например, 100 000 квартир), а столбцов — количество признаков (например, 5 штук: площадь, этаж и т.д.). Матрица прямоугольная, и взять от неё обратную напрямую физически невозможно.
И да, на практике, бывает и наоборот։ фичи могут быть больше чем данные. К примеру, это происходит в областях ближе к генетике/биоинформатике (я не спец, так что подробно, увы, не расскажу)

И как быть? А давайте сделаем её квадратной искусственно! Как утвердит любой, уважающий себе третьеклассник [(с) В. И. Арнольд] — самый простой способ превратить прямоугольную матрицу в квадратную — умножить её слева на саму себя в транспонированном виде ()

Дело за малым. Умножим обе части нашего исходного уравнения $X\omega = y$ на слева: $X^T X \omega = X^T y$ .

Смотрим на левую часть: матрица теперь имеет размер $k \times k$ , ( — условно говоря, количество признаков) она квадратная. А значит, от неё уже можно взять обратную матрицу — $(X^T X)^{-1}$ .

Теперь со спокойной душой избавляемся от этого сомножителя слева, умножив на эту самую обратную матрицу: $(X^T X)^{-1} (X^T X) \omega = (X^T X)^{-1} X^T y$ .

Слева всё сокращается в единичную матрицу, и ПРОИСХОДИТ ЧУДО — мы получаем ту самую легендарную формулу нормального уравнения: $\omega = (X^T X)^{-1} X^T y$ .

Почему этот идеальный мир катится к чертям?

Казалось бы, вот она — таблетка счастья. Закинул матрицу в формулу, процессор поработал и выдал абсолютную истину. Зачем вообще нужны эти ваши эпохи обучения, гигабайты видеокарт и танцы с ~~бубнами~~ с гиперпараметрами? И вообще, мы всё решили, верните нам дешевое ОЗУ, гады!!!

Но, как всегда, гладко только на бумаге. У нашей красивой формулы есть два фундаментальных изъяна, из-за которых дата-сайентисты до сих пор не остались без работы, а бизнес тратит миллионы на инфраструктуру.

Проблема №1: Вычислительный тупик, или Кубический ад

Самая дорогая математическая операция в нашей формуле — это взятие обратной матрицы $(X^T X)^{-1}$ . Любой, кто худо-бедно знаком с алгоритмами, знает про сложность обращения матриц: она кубическая.

Если у нас в таблице 10 или 100 фичей — компьютер посчитает всё за мгновение. А теперь давай вернемся в реальность. Мы работаем с текстами, картинками или графами. Там фичи — это, мягко говоря, огромные(!) векторы или, что еще страшнее, разреженные матрицы (sparse matrix) на сотни тысяч колонок.

Возведя 100 000 в куб, мы получаем $10^{15}$ операций. Даже если использовать хитрые оптимизированные алгоритмы вроде Штрассена или Копперсмита-Виноградова (которые дают условные $O(k^{2.37})$ ), это все еще вычислительное сеппуку. Оперативка забьется промежуточными матрицами и захлебнется быстрее, чем ты успеешь нажать Ctrl+C.

Проблема №2: Мультиколлинеарность и веса, в сравнении с которыми твой жирный кореш — дрищ

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

Если у нас есть фичи «погода в городе N в Цельсиях» и «погода в городе N в Фаренгейтах» — они, как правило, жестко связаны. Матрица становится сингулярной. Попытка скормить ее формуле — это аналог деления на ноль в обычной арифметике.

Ну и ладно, просто удалим полные дубликаты! А вот тут поджидает настоящая засада — мультиколлинеарность.

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

При попытке обращения такой матрицы арифметика float64 сходит с ума от погрешностей округления. В итоге ты получаешь не просто ошибку, а катастрофу в результатах: веса $\omega$ улетают в космос. Один коэффициент становится равен , второй — $-9\,999\,999\,999$ , а третий вообще .

Модель превращается в пороховую бочку. Чуть-чуть изменился шум на входе — итоговое предсказание улетает в бесконечность. Жить с такой моделью невозможно: она разваливается от любого чиха.

И что делать? Выкидывать аналитическое решение на помойку и сразу бежать куда-то в даль? Не обязательно. Дело еще можно попытаться спасти, принудительно приструнив веса. Называется этот инструмент регуляризацией.

Идея простая: если наши веса $\omega$ улетают в космос из-за плохой матрицы, давайте их за это штрафовать! Прямо в функцию потерь (к примеру, в MSE) допишем слагаемое, которое растет вместе с ростом модулей весов. Модели станет тупо невыгодно выкручивать коэффициенты до миллиардов, чтобы подогнаться под шум.

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

-регуляризация (Ridge)

Мы прибавляем к функции потерь сумму квадратов всех весов, помноженную на коэффициент штрафа $\lambda$ .

$L(\omega) = \frac{1}{n} \|X\omega - Y\|_2^2 + \lambda \|\omega\|_2^2$

Что в этот момент происходит с нашей формулой нормального уравнения? Линейная алгебра превращает её вот в это:

$\omega = (X^T X + \lambda I)^{-1} X^T y$

Где — единичная матрица. По сути, мы принудительно прибавляем числа на главную диагональ матрицы .

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

Кстати, в западной литературе этот трюк пафосно называют Ridge, но у нас он исторически известен как регуляризация Тихонова — советский математик Андрей Тихонов придумал этот метод для решения некорректно поставленных задач еще в 1963 году.

-регуляризация (Lasso)

$L(\omega) = \frac{1}{n} \|X\omega - Y\|_2^2 + \lambda \|\omega\|_1$

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

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

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

Финальный тупик, или Куда бежать дальше? (Заключение)

Итак, регуляризация Тихонова — это круто. Мы красиво обошли проблему мультиколлинеарности, заблокировали «деление на ноль», сдули коэффициенты и сделали модель железобетонно устойчивой в продакшене.

Аналитическое решение спасено? Для маленьких датасетов — да.

Но давайте вернемся к нашей Проблеме №1, про которую мы так удобно забыли․
Добавление штрафа, мало того, что не лечит кубическую сложность, так она, гадина, ещё и подкидывает нам вычислительных проблем…
Если у нас в таблице сотни тысяч или миллионы признаков, компьютер всё так же благополучно совершит вычислительное сеппуку, пытаясь перемножить и развернуть эти гигантские массивы данных. Какая разница, устойчивы ли наши веса, если мы физически не можем их посчитать из-за нехватки железа? Здесь аналитический подход окончательно заходит в тупик.

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

В следующей статье мы уже перейдем к градиентному спуску, завоюем крепость линейной регрессии дабы в дальнейшем, рассмотреть другие варианты выбора $\mathcal{F}$ .

Статья, к сожалению, вышла короче ожидаемой, но, с другой стороны лучше сделать так, чем добавить сюда ещё и понятие градиентного спуска. Буду рад вашим комментариям, и, если вы найдете ошибки в статье, пожалуйста, напишите об этом!

ссылка на оригинал статьи https://habr.com/ru/articles/1037110/