Алгоритм iALS

Материал из MachineLearning.

Версия от 06:49, 23 июня 2026; Mihail Mishin (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Перейти к: навигация, поиск

Статья написана с использованием LLM DeepSeek-V3 и проверена участником М. Мишин 9:50, 23 июня 2026 (MSD)

Промпт приводится полностью в Обсуждение:Алгоритм iALS

Содержание

1 Определение и основная идея
2 Математическая постановка
3 Алгоритм
- 3.1 Попеременный метод наименьших квадратов
- 3.2 Вычислительный трюк и масштабируемость
4 Связь с WRMF/WMF и сравнение с другими методами
5 Практические аспекты
6 Актуальные направления исследований
7 См. также
8 Литература
9 Категории

Определение и основная идея

Алгоритм iALS (от англ. implicit Alternating Least Squares) — метод обучения матричных факторизаций для рекомендательных систем, предназначенный для работы с неявной обратной связью (просмотры, клики, покупки, прослушивания) в отличие от классических подходов, требующих явных рейтингов. Предложен в работе Hu, Koren и Volinsky (2008) и с тех пор остаётся одним из наиболее популярных бейзлайнов в академических исследованиях и промышленных внедрениях благодаря эффективности и масштабируемости. В литературе iALS также известен как WRMF (Weighted Regularized Matrix Factorization), WMF (Weighted Matrix Factorization) или WALS (Weighted Alternating Least Squares).

Ключевая проблема неявной обратной связи заключается в том, что отсутствие взаимодействия не эквивалентно отрицательному сигналу: пользователь мог не видеть товар, не заинтересоваться им или отложить решение. iALS решает эту проблему, вводя два понятия:

Предпочтение $p_{ui}$ — бинарный индикатор того, взаимодействовал ли пользователь $u$ с объектом $i$ : $p_{ui} = \begin{cases} 1, & r_{ui} > 0 \ 0, & r_{ui} = 0 \end{cases}$ где $r_{ui}$ — сырое значение неявного сигнала (например, количество просмотров).

Уверенность $c_{ui}$ — мера достоверности наблюдения, возрастающая с интенсивностью взаимодействия: $c_{ui} = 1 + \alpha r_{ui}$ где $\alpha$ — гиперпараметр, контролирующий скорость роста уверенности.

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

Математическая постановка

Пусть имеется $m$ пользователей и $n$ объектов. Цель iALS — найти две матрицы низкого ранга: $X \in \mathbb{R}^{m \times d}$ (факторы пользователей) и $Y \in \mathbb{R}^{d \times n}$ (факторы объектов), такие что их произведение аппроксимирует матрицу предпочтений $P$ .

Оптимизационная задача имеет вид:

$\min_{X,Y} \sum_{u=1}^{m} \sum_{i=1}^{n} c_{ui} (p_{ui} - x_u^T y_i)^2 + \lambda \left( \sum_{u=1}^{m} n_{x_u} |x_u|^2 + \sum_{i=1}^{n} m_{y_i} |y_i|^2 \right),$

где:

$x_u \in \mathbb{R}^d$ — вектор латентных факторов пользователя $u$ ;

$y_i \in \mathbb{R}^d$ — вектор латентных факторов объекта $i$ ;

$c_{ui}$ — уверенность;

$\lambda$ — коэффициент регуляризации;

$n_{x_u}$ и $m_{y_i}$ — количество взаимодействий у пользователя и объекта соответственно (вариант регуляризации с учётом частоты).

В упрощённой формулировке (без взвешивания регуляризации по частоте) целевая функция записывается как:

$\min_{X,Y} \sum_{u,i} c_{ui} (p_{ui} - x_u^T y_i)^2 + \lambda \left( \sum_u |x_u|^2 + \sum_i |y_i|^2 \right).$

Алгоритм

Попеременный метод наименьших квадратов

iALS минимизирует целевую функцию с помощью попеременного метода наименьших квадратов (ALS): алгоритм поочерёдно фиксирует одну матрицу факторов и решает задачу относительно другой.

Шаг 1: Фиксируем $Y$ , обновляем $X$ . Для каждого пользователя $u$ решается задача:

$x_u = \left( Y^T C^u Y + \lambda I \right)^{-1} Y^T C^u p_u,$

где $C^u \in \mathbb{R}^{n \times n}$ — диагональная матрица уверенностей пользователя $u$ , $p_u \in \mathbb{R}^n$ — вектор его предпочтений.

Шаг 2: Фиксируем $X$ , обновляем $Y$ . Для каждого объекта $i$ :

$y_i = \left( X^T C^i X + \lambda I \right)^{-1} X^T C^i p^i,$

где $C^i \in \mathbb{R}^{m \times m}$ — диагональная матрица уверенностей объекта $i$ , $p^i \in \mathbb{R}^m$ — вектор предпочтений объекта.

Шаги 1 и 2 повторяются до сходимости или в течение заданного числа итераций (обычно 10–20).

Вычислительный трюк и масштабируемость

Ключевая причина эффективности iALS заключается в том, что выражение $Y^T C^u Y$ можно переписать без явного построения диагональной матрицы $C^u$ :

$Y^T C^u Y = Y^T Y + Y^T (C^u - I) Y = Y^T Y + \sum_{i: p_{ui}=1} (c_{ui} - 1) y_i y_i^T.$

Это позволяет вычислить обновление для каждого пользователя за время $O(d^2 + d \cdot \text{nnz}_u)$ , где $\text{nnz}_u$ — число ненулевых взаимодействий пользователя. Полная сложность одной итерации составляет $O(d^2(m+n) + d \cdot |\Omega|)$ , где $|\Omega|$ — общее число взаимодействий. Благодаря этому алгоритм линейно масштабируется по размеру данных.

Однако iALS имеет кубическую зависимость от размерности латентных факторов $d$ из-за обращения матриц $d \times d$ . Для больших $d$ (порядка 1000 и выше) это становится узким местом. Альтернативные подходы, такие как iCD (координатный спуск), имеют квадратичную сложность по $d$ , но на практике проигрывают iALS в скорости из-за неэффективного использования векторных инструкций процессора.

Связь с WRMF/WMF и сравнение с другими методами

Отношение к WRMF

Термины iALS, WRMF и WMF часто используются как синонимы, хотя между ними есть тонкие различия:

WRMF (Weighted Regularized Matrix Factorization) — общее название семейства методов взвешенной матричной факторизации;

iALS — конкретный алгоритм оптимизации (попеременный МНК) для WRMF;

WMF — часто используется как сокращение для WRMF.

Все эти подходы используют одну и ту же целевую функцию с весами уверенности.

Сравнение с SGD

Альтернативный подход к оптимизации той же целевой функции — стохастический градиентный спуск (SGD). Основные различия между iALS и SGD:

Сходимость: iALS даёт детерминированную монотонную сходимость, тогда как SGD — стохастическую и немонотонную.

Параллелизация: iALS легко распараллеливается по пользователям и объектам, тогда как SGD требует осторожной синхронизации при параллельном обучении.

Скорость на разреженных данных: iALS очень быстр (линейная сложность по числу взаимодействий), SGD также высокоскоростен, но чувствителен к настройке темпа обучения.

Качество: iALS даёт стабильно высокое качество при правильной настройке гиперпараметров, тогда как SGD может достичь более высокой точности при тонкой настройке, но менее стабилен.

Сравнение с нейросетевыми подходами

Несмотря на почтенный возраст, iALS показывает конкурентоспособное качество по сравнению с современными методами, включая VAE, EASE, SLIM и NCF. В работе Rendle et al. (2021) показано, что при правильной настройке гиперпараметров iALS превосходит все перечисленные методы как минимум на половине рассмотренных бенчмарков.

Главное преимущество iALS перед нейросетевыми подходами — скорость обучения и простота интерпретации; главный недостаток — ограниченная выразительная способность линейной модели.

Практические аспекты

Выбор гиперпараметров

Ключевые гиперпараметры iALS:

Размерность латентных факторов $d$ — типичные значения: 32–256 для большинства задач, до 1000 для крупных датасетов. Рекомендуется начинать с $d=128$ , затем удваивать размерность до насыщения качества.

Коэффициент уверенности $\alpha$ — определяет, насколько сильно интенсивность взаимодействия влияет на вес. Обычно подбирается на валидационной выборке в диапазоне $[1, 100]$ .

Коэффициент регуляризации $\lambda$ — типичные значения: $[0.001, 1.0]$ . Зависит от масштаба данных.

Количество итераций — 10–20 обычно достаточно для сходимости.

Стратегия настройки: сначала грубый поиск по сетке при $d=128$ , затем уточнение при больших размерностях.

Современные оптимизации

iALS++ — улучшенная версия, сочетающая векторную обработку iALS с пониженной сложностью iCD. Позволяет обучать модели с $d=1000$ на датасетах типа MovieLens 20M или Million Song Dataset за считанные минуты.

Конъюгатный градиент — замена прямого обращения матриц на итерационные методы для ускорения при больших $d$ .

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

Программные реализации

Наиболее популярные реализации iALS:

implicit (Python) — библиотека с оптимизированными реализациями ALS, BPR и других алгоритмов для неявной обратной связи;

Apache Spark ALS — распределённая реализация в составе MLlib;

Intel oneDAL — оптимизированная реализация для процессоров Intel;

irspack (Python) — реализация с поддержкой различных вариантов iALS;

LensKit (Java/Kotlin) — библиотека для исследований в области рекомендательных систем.

Актуальные направления исследований

Учёт справедливости

Традиционный iALS оптимизирует среднее качество рекомендаций, что может приводить к неравномерному распределению внимания (exposure) между объектами. Современные расширения, такие как exADMM, модифицируют целевую функцию iALS, добавляя регуляризатор справедливости, который позволяет контролировать баланс между точностью и равномерностью экспозиции.

Другое направление — безопасные рекомендательные системы, которые улучшают качество для наименее удовлетворённых пользователей, а не только усреднённое качество.

Вероятностные расширения

Классический iALS интерпретирует все неизвестные взаимодействия как отрицательные примеры с пониженным весом. В работе De Pauw и Goethals (2024) предложена вероятностная интерпретация, в которой неизвестные взаимодействия моделируются как потенциально положительные или отрицательные. Это позволило улучшить качество рекомендаций без дополнительных вычислительных затрат. Авторы также предложили логистическую версию iALS, адаптирующую алгоритм для использования логистической регрессии.

Масштабирование на сверхбольшие каталоги

Несмотря на линейную сложность по числу взаимодействий, iALS остаётся вычислительно дорогим при очень больших $d$ из-за кубической зависимости. Разработка алгоритмов с пониженной сложностью при сохранении качества — активная область исследований.

См. также

Матричное разложение

Коллаборативная фильтрация

Alternating least squares

Стохастический градиентный спуск

Рекомендательная система

Неявная обратная связь

Литература

Hu, Y., Koren, Y., & Volinsky, C. (2008). Collaborative Filtering for Implicit Feedback Datasets. IEEE International Conference on Data Mining (ICDM), 263–272. PDF — основополагающая работа, вводящая iALS и концепцию взвешенной матричной факторизации для неявной обратной связи.

Rendle, S., Krichene, W., Zhang, L., & Koren, Y. (2021). Revisiting the Performance of iALS on Item Recommendation Benchmarks. arXiv:2110.14037. arXiv:2110.14037 — масштабное эмпирическое исследование, показывающее, что iALS превосходит многие современные методы при правильной настройке гиперпараметров.

Rendle, S., Krichene, W., Zhang, L., & Koren, Y. (2021). iALS++: Speeding up Matrix Factorization with Subspace Optimization. arXiv:2110.14044. arXiv:2110.14044 — предложение улучшенной версии iALS, сочетающей векторную обработку и пониженную сложность, что позволяет работать с размерностями до 1000.

De Pauw, J., & Goethals, B. (2024). The Role of Unknown Interactions in Implicit Matrix Factorization — A Probabilistic View. RecSys '24, ACM, 219–227. DOI:10.1145/3640457.3688100 — вероятностная интерпретация неизвестных взаимодействий и логистическое расширение iALS.

Fleischer, D. (2008). Implicit Alternating Least Squares (реализация в oneDAL). Intel oneDAL: Implicit Alternating Least Squares — описание эффективной реализации iALS в библиотеке Intel oneDAL

Togashi, R., & Abe, K. Fair Matrix Factorisation for Large-Scale Recommender Systems. arXiv:2209.04394. arXiv:2209.04394 — расширение iALS регуляризатором справедливости для контроля равномерности экспозиции объектов.

Категории

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_iALS»

Категории: Машинное обучение | Рекомендательные системы | Матричные разложения | Алгоритмы оптимизации