Матричное разложение градиентным спуском

Урок реализует матричное разложение с нуля на стандартном Python: учим скрытые факторы стохастическим градиентным спуском и восстанавливаем матрицу.

SGD-разложение — итеративный метод, который на каждом известном взаимодействии слегка двигает векторы пользователя и товара так, чтобы их произведение стало ближе к настоящей оценке.

Что именно мы оптимизируем

Для известной оценки R[u][i] прогноз — это скалярное произведение векторов P[u] и Q[i]. Ошибка err = R[u][i] - prediction. Мы хотим её уменьшить, поэтому сдвигаем каждый компонент векторов в сторону, уменьшающую ошибку, с маленьким шагом (learning rate). Чтобы факторы не «разъезжались», добавляем регуляризацию — лёгкий штраф, тянущий их к нулю.

Правила обновления (для каждого фактора k):

P[u][k] += lr * (err * Q[i][k] - reg * P[u][k])
Q[i][k] += lr * (err * P[u][k] - reg * Q[i][k])

Полная реализация

Берём крошечную матрицу 5x4 с явными пробелами (0 = неизвестно), учим два фактора и восстанавливаем пропуски. Зерно случайности фиксировано, поэтому вывод воспроизводим.

import random

R = [
    [5, 3, 0, 1],
    [4, 0, 0, 1],
    [1, 1, 0, 5],
    [1, 0, 0, 4],
    [0, 1, 5, 4],
]
n_users, n_items, K = len(R), len(R[0]), 2
random.seed(42)
P = [[random.uniform(0, 0.1) for _ in range(K)] for _ in range(n_users)]
Q = [[random.uniform(0, 0.1) for _ in range(K)] for _ in range(n_items)]
lr, reg = 0.01, 0.02

def dot(a, b):
    return sum(x * y for x, y in zip(a, b))

for epoch in range(5000):
    for u in range(n_users):
        for i in range(n_items):
            if R[u][i] > 0:
                err = R[u][i] - dot(P[u], Q[i])
                for k in range(K):
                    pu, qi = P[u][k], Q[i][k]
                    P[u][k] += lr * (err * qi - reg * pu)
                    Q[i][k] += lr * (err * pu - reg * qi)

mse = cnt = 0
for u in range(n_users):
    for i in range(n_items):
        if R[u][i] > 0:
            mse += (R[u][i] - dot(P[u], Q[i])) ** 2
            cnt += 1
print("RMSE на известных:", round((mse / cnt) ** 0.5, 3))
print("Восстановленная матрица:")
for u in range(n_users):
    print([round(dot(P[u], Q[i]), 1) for i in range(n_items)])

Вывод:

RMSE на известных: 0.028
Восстановленная матрица:
[5.0, 3.0, 3.0, 1.0]
[4.0, 2.4, 2.6, 1.0]
[1.0, 1.0, 6.0, 4.9]
[1.0, 0.9, 4.9, 4.0]
[1.2, 1.0, 5.0, 4.0]

Известные оценки восстановлены почти идеально (RMSE ≈ 0,03), а на месте бывших нулей появились осмысленные прогнозы: например, пользователю из третьей строки модель уверенно ставит высокий интерес к третьему товару.

Как работает под капотом

Мы обходим только ненулевые ячейки — это ключ к работе с разреженностью. Learning rate управляет размером шага: слишком большой — обучение «прыгает» и расходится, слишком маленький — сходится медленно. Регуляризация reg не даёт факторам раздуться и переобучиться под шум. В реальных системах добавляют ещё bias-члены (средняя оценка, поправка на пользователя и товар), мини-батчи и адаптивные шаги, но ядро остаётся ровно таким, как выше.

Частые ошибки

Обновлять P и Q по очереди после изменения друг друга. Используйте сохранённые значения pu, qi до обновления, иначе градиент будет несогласован.
Учиться на нулях. Цикл должен трогать только R[u][i] > 0 для явного фидбэка.
Слишком большой learning rate. Обучение расходится, RMSE растёт вместо падения.

Итоги

SGD двигает векторы пользователя и товара, уменьшая ошибку на известных оценках.
Регуляризация защищает от переобучения, learning rate задаёт скорость.
Обучение идёт только по известным ячейкам — так побеждается разреженность.
После обучения скалярное произведение векторов заполняет любые пропуски.