ЛР4 · Факторизация: большую таблицу сжимаем двумя маленькими

Разобраться с нуля

Факторизация: большую таблицу сжимаем двумя маленькими

Две маленькие матрицы должны при умножении восстановить исходную с малой ошибкой.

Матрица A: Исходная таблица чисел, m строк и n столбцов.
Ранг k: Число скрытых координат, размер сжатия.
U и V_T: Два множителя размера m×k и k×n.
MSE: Среднее квадратов разностей между исходной и восстановленной таблицей.
Градиент: Производная ошибки: направление её роста.
Шаг learning_rate: Насколько сильно меняем параметры за раз.
Эпоха: Один шаг вычисления градиентов и обновления множителей.

На пальцах. Запоминаем не каждую оценку человека каждому фильму, а несколько вкусов человека и несколько свойств фильма. Их сочетание приближает исходную таблицу.

Размерности без магии

A имеет размер 2×3, k=2. U это 2×2, V_T это 2×3, произведение снова 2×3. Ошибка E = U @ V_T - A такой же формы.

L = mean(E²)
grad_U = 2 E @ V_T.T / A.size
grad_V = 2 U.T @ E / A.size
U = U - learning_rate × grad_U

@ это матричное умножение. .T меняет строки и столбцы местами. A.size это m×n. Оба градиента считаются до изменения U и V_T.

Мини-версия: подобрать x так, чтобы x≈3. Ошибка L=(x-3)², градиент 2(x-3).

Шаг обучения

Ловушка. Произвольные U и V_T из градиентного спуска не обязаны быть сингулярными ортогональными векторами. Название функции svd_gradient_descent взято из шаблона, точнее говорить о низкоранговой факторизации. Для второй тестовой матрицы 1000 эпох мало, поэтому дополнительно показаны 10000.

Код и построчный разбор

Код исходной ячейки 46: def svd_gradient_descent(A, k, learning_rate=0.001, epochs=100):

def svd_gradient_descent(A, k, learning_rate=0.001, epochs=100):
    A = np.asarray(A, dtype=float)
    m, n = A.shape
    rng = np.random.RandomState(42)
    U = rng.randn(m, k)
    V_T = rng.randn(k, n)
    for epoch in range(epochs):
        error = U @ V_T - A
        grad_U = 2 * error @ V_T.T / A.size
        grad_V = 2 * U.T @ error / A.size
        U -= learning_rate * grad_U
        V_T -= learning_rate * grad_V
    return U, V_T

1: def svd_gradient_descent(A, k, learning_rate=0.001, epochs=100):
Объявляет функцию: код внутри выполняется при её вызове.
2: A = np.asarray(A, dtype=float)
Превращает результат вычисления в массив NumPy; ravel делает его одномерным.
3: m, n = A.shape
Вычисляет правую часть и сохраняет результат в m, n.
4: rng = np.random.RandomState(42)
Вычисляет правую часть и сохраняет результат в rng.
5: U = rng.randn(m, k)
Вычисляет правую часть и сохраняет результат в U.
6: V_T = rng.randn(k, n)
Вычисляет правую часть и сохраняет результат в V_T.
7: for epoch in range(epochs):
Повторяет вложенный блок для каждого элемента указанной последовательности.
8: error = U @ V_T - A
Разность восстановленной и исходной матрицы: UV_T - A.
9: grad_U = 2 * error @ V_T.T / A.size
Градиент MSE по U, форма m×k; вычисляется матричной формулой.
10: grad_V = 2 * U.T @ error / A.size
Градиент MSE по V_T, форма k×n; используется старая U.
11: U -= learning_rate * grad_U
Сдвигает U против градиента на величину learning_rate.
12: V_T -= learning_rate * grad_V
Сдвигает V_T против своего заранее вычисленного градиента.
13: return U, V_T
Возвращает результат функции вызывающему коду.

Код исходной ячейки 47: # Примеры - значения матрицы Result должны приближаться к значениям исходной матрицам

# Примеры - значения матрицы Result должны приближаться к значениям исходной матрицам

print('-' * 50)

A = np.array([[3, 1, 1],
              [-1, 3, 1]])

U, V_T = svd_gradient_descent(A, k=2, learning_rate=0.1)
print("U:\n", U)
print("V_T:\n", V_T)
print("Result:\n", U @ V_T)

print('-' * 50)

A2 = np.array([[1, 2, 3],
               [4, 5, 6],
               [7, 8, 9]])

U2, V_T2 = svd_gradient_descent(A2, k=2, learning_rate=0.02, epochs=1000)
print("U2:\n", U2)
print("V_T2:\n", V_T2)
print("Result2:\n", U2 @ V_T2)

print('-' * 50)

1: # Примеры - значения матрицы Result должны приближаться к значениям исходной матрицам
Комментарий объясняет причину следующего действия.
3: print('-' * 50)
Печатает число или пояснение, чтобы проверить результат выполнения.
5: A = np.array([[3, 1, 1],
Вычисляет правую часть и сохраняет результат в A.
6: [-1, 3, 1]])
Продолжает выражение предыдущей строки: здесь заданы данные или аргументы вызова.
8: U, V_T = svd_gradient_descent(A, k=2, learning_rate=0.1)
Вычисляет правую часть и сохраняет результат в U, V_T.
9: print("U:\n", U)
Печатает число или пояснение, чтобы проверить результат выполнения.
10: print("V_T:\n", V_T)
Печатает число или пояснение, чтобы проверить результат выполнения.
11: print("Result:\n", U @ V_T)
Печатает число или пояснение, чтобы проверить результат выполнения.
13: print('-' * 50)
Печатает число или пояснение, чтобы проверить результат выполнения.
15: A2 = np.array([[1, 2, 3],
Вычисляет правую часть и сохраняет результат в A2.
16: [4, 5, 6],
Продолжает выражение предыдущей строки: здесь заданы данные или аргументы вызова.
17: [7, 8, 9]])
Продолжает выражение предыдущей строки: здесь заданы данные или аргументы вызова.
19: U2, V_T2 = svd_gradient_descent(A2, k=2, learning_rate=0.02, epochs=1000)
Вычисляет правую часть и сохраняет результат в U2, V_T2.
20: print("U2:\n", U2)
Печатает число или пояснение, чтобы проверить результат выполнения.
21: print("V_T2:\n", V_T2)
Печатает число или пояснение, чтобы проверить результат выполнения.
22: print("Result2:\n", U2 @ V_T2)
Печатает число или пояснение, чтобы проверить результат выполнения.
24: print('-' * 50)
Печатает число или пояснение, чтобы проверить результат выполнения.

Вопросы защиты

Почему нет цикла по элементам?

Ошибка и оба градиента выражены матричными формулами NumPy. Цикл остаётся только по эпохам.

Почему минус перед градиентом?

Градиент показывает рост ошибки, а мы хотим идти в сторону уменьшения.

Можно сравнивать элементы U с чужим запуском?

Нет: разные множители могут давать одно произведение. Сравнивают реконструкцию и MSE.

Что если шаг слишком большой?

Ошибка может колебаться или расти; это видно в демо.

Одна фразаУменьшаю MSE восстановления A матричными градиентами, цикл только по эпохам.