Матричная факторизация в рекомендательных системах: алгоритм ALS
Одной из самых коммерчески успешных задач прикладной линейной алгебры стало создание коллаборативных рекомендательных систем. В 2006 году компания Netflix объявила конкурс с призом в миллион долларов за улучшение алгоритма предсказания оценок фильмов. Победителем стал подход, основанный на матричной факторизации (Matrix Factorization). Суть проблемы заключается в том, что имеется гигантская матрица «пользователь-фильм», где строки — это миллионы пользователей, столбцы — десятки тысяч фильмов, а на пересечениях стоят оценки. Эта матрица колоссально разрежена: 99% ячеек пусты, так как человек смотрит лишь крошечную долю фильмов. Классическое сингулярное разложение (SVD) здесь неприменимо из-за пустых ячеек, поэтому математикам пришлось разработать новый алгебраический аппарат скрытых факторов.
Скрытые факторы (Latent Features) и скалярное произведение
Вместо того чтобы работать с огромной пустой матрицей R, метод матричной факторизации предполагает, что оценки формируются на основе небольшого числа скрытых (латентных) признаков (например, жанр, режиссер, уровень экшена). Мы ищем две узкие плотные матрицы: матрицу пользователей U и матрицу фильмов V. Строка матрицы U содержит вектор предпочтений конкретного пользователя, а столбец матрицы V содержит вектор характеристик конкретного фильма в этом же самом абстрактном пространстве признаков. Предсказанная оценка пользователя фильму вычисляется как классическое скалярное произведение этих двух векторов: r_ij = u_i^T * v_j. Геометрически это означает, что если вектор предпочтений пользователя сонаправлен (параллелен) вектору характеристик фильма, скалярное произведение будет велико, и алгоритм порекомендует этот фильм.
Проблема пропущенных значений и регуляризация
Поскольку исходная матрица R содержит пропуски, мы не можем применять стандартные алгоритмы поиска собственных значений. Вместо этого формулируется задача нелинейной оптимизации: минимизировать сумму квадратов ошибок между реальными оценками и предсказанными скалярными произведениями только для тех ячеек, где оценки известны. Однако, поскольку количество параметров (элементов матриц U и V) может исчисляться десятками миллионов, модель склонна к жесточайшему переобучению (overfitting). Для борьбы с этим в функцию потерь вводится математический штраф — L2-регуляризация (регуляризация Тихонова). К функции ошибки прибавляется сумма квадратов всех элементов матриц U и V, умноженная на коэффициент регуляризации лямбда. Это заставляет векторы скрытых факторов быть максимально короткими, что повышает обобщающую способность алгоритма.
Алгоритм чередующихся наименьших квадратов (ALS)
Функция потерь в задаче матричной факторизации не является выпуклой относительно обеих матриц U и V одновременно (так как они перемножаются друг на друга). Градиентный спуск в такой ситуации работает медленно. Гениальным решением стал алгоритм Чередующихся Наименьших Квадратов (Alternating Least Squares, ALS). Если мы жестко зафиксируем матрицу V (будем считать ее константой), то функция потерь относительно матрицы U становится строго квадратичной и выпуклой! Мы можем мгновенно и аналитически точно найти идеальную матрицу U, решив классическую систему нормальных уравнений метода наименьших квадратов. Затем мы фиксируем найденную матрицу U и решаем такую же систему уравнений для нахождения новой матрицы V. Чередуя эти шаги, алгоритм ALS молниеносно сходится к глубокому локальному минимуму.
Учет неявных отзывов (Implicit Feedback)
В современных системах пользователи редко ставят явные оценки (звезды). Гораздо чаще данные представляют собой неявные отклики (клики, время просмотра, добавление в корзину). Для работы с такими данными алгоритм ALS был модифицирован. Вводится понятие бинарной матрицы предпочтений (смотрел / не смотрел) и матрицы уверенности (confidence), которая зависит от того, сколько раз пользователь кликнул на товар. Матрица уверенности играет роль диагональной весовой матрицы в алгоритме наименьших квадратов. Линейная алгебра позволяет элегантно перегруппировать члены в уравнениях ALS так, чтобы алгоритм пересчитывал веса не за кубическое, а за линейное время, позволяя стриминговым сервисам и интернет-магазинам обновлять персональные рекомендации пользователей в режиме реального времени на матрицах с миллиардами записей.
