Матричная факторизация

Матричная факторизация — это простая модель встраивания. Учитывая матрицу обратной связи A \(\in R^{m \times n}\), где \(m\) — количество пользователей (или запросов), а \(n\) — количество элементов, модель учится:

• Матрица встраивания пользователя \(U \in \mathbb R^{m \times d}\), где строка i — вложение для пользователя i.
• Матрица внедрения элементов \(V \in \mathbb R^{n \times d}\), где строка j — это вложение элемента j.

Вложения изучены таким образом, что произведение \(U V^T\) является хорошей аппроксимацией матрицы обратной связи A. Обратите внимание, что запись l10n-\((i, j)\) для \(U . V^T\) является просто скалярным произведением\(\langle U_i, V_j\rangle\) вложений пользователя \(i\)и элемента \(j\), который должен быть близок к \(A_{i, j}\).

Примечание. Матричная факторизация обычно дает более компактное представление, чем изучение полной матрицы. Полная матрица имеет элементы \(O(nm)\) , в то время как матрицы вложения \(U, \ V\) имеют элементы \(O((n+m)d)\) , где размер вложения \(d\) обычно намного меньше, чем \(m\)и \(n\). В результате матричная факторизация находит в данных скрытую структуру, предполагая, что наблюдения лежат близко к низкоразмерному подпространству. В предыдущем примере значения n, m и d настолько малы, что преимуществом можно пренебречь. Однако в реальных рекомендательных системах матричная факторизация может быть значительно более компактной, чем изучение всей матрицы.

Выбор целевой функции

Одной из интуитивно понятных целевых функций является квадрат расстояния. Для этого минимизируйте сумму квадратов ошибок по всем парам наблюдаемых записей:

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \sum_{(i, j) \in \text{obs}} (A_{ij} - \langle U_{i}, V_{j} \rangle)^2.\]

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

Возможно, вы могли бы рассматривать ненаблюдаемые значения как ноль и просуммировать все записи в матрице. Это соответствует минимизации квадрата расстояния Фробениуса между \(A\) и его аппроксимацией \(U V^T\):

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \|A - U V^T\|_F^2.\]

Вы можете решить эту квадратичную задачу с помощью разложения матрицы по сингулярным значениям ( SVD ). Однако SVD тоже не лучшее решение, потому что в реальных приложениях матрица \(A\) может быть очень разреженной. Например, сравните все видео на YouTube со всеми видео, просмотренными конкретным пользователем. Решение \(UV^T\) (которое соответствует приближению модели к входной матрице), скорее всего, будет близко к нулю, что приведет к плохой производительности обобщения.

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

• Сумма по наблюдаемым записям.
• Сумма по ненаблюдаемым записям (обрабатывается как нули).

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \sum_{(i, j) \in \text{obs}} (A_{ij} - \langle U_{i}, V_{j} \rangle)^2 + w_0 \sum_{(i, j) \not \in \text{obs}} (\langle U_i, V_j\rangle)^2.\]

Здесь \(w_0\) — это гиперпараметр, который взвешивает два термина, чтобы цель не преобладала ни над одним, ни над другим. Настройка этого гиперпараметра очень важна.

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

\[\sum_{(i, j) \in \text{obs}} w_{i, j} (A_{i, j} - \langle U_i, V_j \rangle)^2 + w_0 \sum_{i, j \not \in \text{obs}} \langle U_i, V_j \rangle^2\]

где \(w_{i, j}\) — это функция частоты запроса i и элемента j.

Минимизация целевой функции

Общие алгоритмы минимизации целевой функции включают:

• Стохастический градиентный спуск (SGD) — это общий метод минимизации функций потерь.

• Метод взвешенных чередующихся наименьших квадратов ( WALS ) специально предназначен для этой конкретной цели.

Цель квадратична в каждой из двух матриц U и V. (Обратите внимание, однако, что проблема не является совместно выпуклой.) WALS работает, инициализируя вложения случайным образом, а затем чередуя между ними:

• Исправление \(U\) и решение \(V\).
• Исправление \(V\) и решение для \(U\).

Каждый этап может быть решен точно (через решение линейной системы) и распределен. Этот метод гарантированно сходится, потому что каждый шаг гарантированно уменьшает потери.

SGD против WALS

SGD и WALS имеют свои преимущества и недостатки. Просмотрите информацию ниже, чтобы увидеть, как они сравниваются:

сингапурский доллар

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

Можно распараллелить.

Медленнее — сходится не так быстро.

Сложнее обрабатывать ненаблюдаемые записи (необходимо использовать отрицательную выборку или гравитацию).

ВАЛЬС

Зависит только от площадей потерь.

Можно распараллелить.

Сходится быстрее, чем SGD.

Легче обрабатывать незамеченные записи.