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

Матричная факторизация — это простая модель внедрения. Учитывая матрицу обратной связи 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. Обратите внимание, что запись\((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.

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