Разреженное SVD разложение

SVD разложение: $\forall R\in \mathbb {R} ^{M\times N}$ может быть представлена как произведение трёх матриц $P\Sigma V^{T}$, где $U\in \mathbb {R} ^{M\times P},V\in \mathbb {R} ^{P\times N},\Sigma \in \mathbb {R} ^{P\times P}U^{T}U=V^{T}V=I,\Sigma =diag\{\sigma _{1},\dots ,\sigma _{P}\},P=rankR$.

Если $\sigma _{1}\geq \sigma _{2}\geq \dots \geq \sigma _{P}$, то данное разложение определено однозначно. В таком случае, если взять первые K столбцов матриц U и V, и первые K сингулярных чисел $\sigma _{1},\dots ,\sigma _{K}$, то получится матрица R', минимизирующая норму Фробениуса, по всем матрицам ранга не больше, чем K:

$R'=argmin_{rankA\leq K}\|R-A\|_{F}$.

В таком случае строки матрицы U можно воспринимать как отношение пользователя к каждой из K скрытых тем (в оригинале стоит слово topic). Строки матрицы V как степень соответствия фильма одной из K скрытых тем. Сингулярные числа $\sigma _{1},\dots ,\sigma _{K}$: важность каждой из тем.

Теперь, если у нас появляется новый пользователь с "большим" вектором оценок $r_{u}$, то его K-мерный вектор отношений к темам будет вычисляться следующим образом:

$p_{u}=argmin_{p}\|r_{u}-Vp\|=V^{T}r_{u}$ (В справедливости данного формулы можно убедиться, подставив итоговый результат и вспомнив про ортогональность V). Обратный процесс: $r_{u}=Vp_{u}$.

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

Напомним, что в SVD разложении минимизировалась норма Фробениуса: $\|R-PQ^{T}\|_{F}\rightarrow \min _{P,Q};P=[p_{1}|p_{2}|\dots |p_{K}]^{T},Q=[q_{1}|q_{2}|\dots |q_{K}]$. Предсказание $R'=PQ.$.

Идея: минимизировать только те кусочки нормы Фробениуса , где оценка пользователя определена:$\sum _{(u,i):\exists r_{u,i}}{\underbrace {(r_{u,i}-{\bar {r_{u}}}-{\bar {r_{i}}}-p_{u}^{T}q)^{2}} _{\epsilon _{u,i}}}$.

Для решения данной проблемы воспользуемся методом SGD: будем случайно выбирать пару (u, i). $p_{u}\leftarrow p_{u}+\eta \epsilon _{u,i}q_{i},$

$q_{i}\leftarrow q_{i}+\eta \epsilon _{u,i}p_{U}$.

Преимущества данного подхода:

Нет неопределённости;

Легко добавить регуляризацию: $\epsilon _{u,i}^{2}+\lambda \|p_{u}\|^{2}+\mu \|q_{i}\|^{2}\rightarrow _{p,q}$;

Можно учесть неотрицательность компонент p и q, воспользовавшись методом проекций градиента;

Достаточно быстр.