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

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

  • Матрица внедрения пользователя URm×d, где строка i — это внедрение пользователя i.
  • Матрица внедрения элемента VRn×d, где строка j — это внедрение элемента j.

Иллюстрация матричной факторизации на примере повторяющегося фильма.

Вложения изучаются таким образом, что произведение UVT является хорошим приближением матрицы обратной связи A. Обратите внимание, что запись(i,j) в U.VT представляет собой просто скалярное произведениеUi,Vj вложений пользователя iи элемента j, который должен быть близок к Ai,j.

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

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

minURm×d, VRn×d(i,j)obs(AijUi,Vj)2.

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

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

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

minURm×d, VRn×dAUVTF2.

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

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

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

minURm×d, VRn×d(i,j)obs(AijUi,Vj)2+w0(i,j)obs(Ui,Vj)2.

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

(i,j)obswi,j(Ai,jUi,Vj)2+w0i,jobsUi,Vj2

где wi,j — функция частоты запроса i и элемента j.

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

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

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

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

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

  • Исправление U и решение V.
  • Исправление V и решение U.

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

SGD против WALS

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

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

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

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

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

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

ВАЛС

Полагайтесь только на квадраты потерь.

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

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

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