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

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

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