243. Рекомендательная система SVD

Необходимо разработать рекомендательную систему для фильмов. В этой системе каждый из $U$ пользователей может поставить оценки в диапазоне от $1$ до $k$ каждому из $M$ фильмов, которые он посмотрел. Дана обучающая выборка, в которой указаны $D$ известных оценок. Также дана тестовая выборка, в которой указаны $T$ пар пользователь-фильм. Для этих пар требуется предсказать, какую оценку пользователь поставил фильму. Настоящие оценки для этих пар скрыты.

Вам необходимо предсказать оценки по метрике $RMSE$ не хуже, чем предсказывает модель $SVD^1$.

На первой строке через пробел заданы целые числа $k ,U, M, D, T$ ($2 \leq k \leq 100, 1 \leq U, M \leq 10000, 1 \leq D, T \leq 1000000$). Затем идут $D$ строк обучающей выборки. В $i$-ой строке выборки записаны целые числа $u_i$, $m_i$ и $r_i$, где $u_i$ ($0 \leq u_i \leq U-1$) — номер пользователя, $m_i$ ($0 \leq m_i \leq M-1$) — номер фильма, $r_i$ ($1 \leq r_i \leq k$) — оценка, которую этот пользователь поставил этому фильму. Затем идут $T$ строк тестовой выборки. В $i$-ой строке выборки записаны числа $u_i$ и $m_i$, где $u_i$ ($0 \leq u_i \leq U-1$) — номер пользователя, $m_i$ ($0 \leq m_i \leq M-1$) — номер фильма. Для этих строк требуется предсказать оценки.

Для каждой из $T$ строк тестовой выборки необходимо вывести предсказанную оценку (вещественное число) на отдельной строке.

Модель $SVD$: $$ {\hat r} (u,m) = \mu + b_u + b_m + \langle \overline p_u, \overline q_m \rangle, $$ где $\hat r (u,m)$ — предсказанная оценка для пользователя $u$ и фильма $m$, $\langle \cdot, \cdot \rangle$ — скалярное произведение векторов, а $\mu$, $b_u$, $b_m$, $\overline p_u$ и $\overline q_m$ — параметры, настраиваемые по обучающей выборке, причём $\mu$, $b_u$ и $b_m$ — числовые параметры, а $\overline p_u$ и $\overline q_m$ — $d$-мерные векторы для некоторого $d$. Рекомендуется использовать $d = 10$.