(V. Voráček, 2021)

V problémech s doporučovacími systémy ( Recommender system) je cílem odhadnout, co by se mohlo uživateli líbit a následně mu to doporučit. Příkladem je třeba Youtube, nebo reklamy. Známou instancí této úlohy je soutěž Netflix Prize, kde bylo známo asi $10^8$ hodnocení na stupnici $1 \dots 5$, filmů bylo asi $2\cdot10^4$ a uživatelů asi $5\cdot10^5$. Cílem bylo odhadnout hodnocení filmu uživatelem. Data k této soutěži jsou dostupná, ale jsou obrovská a těžko se s nimi pracuje, proto se jim v této úloze vyhneme. Použijeme dataset Jester, který obsahuje hodnocení vtipů. Každé hodnocení vtipu je reálné číslo z intervalu $[-10, 10]$.

Problém motivovaný výše lze zadat jako problém doplňení matice (Matrix completion). Vezměme následují matici, nazvěme ji $\_M$. Například hodnocení vtipu $a$ Alicí je $7$, zatímco hodnocení vtipu $d$ Bobem není známé. Množina $\_E = \{(i_1, j_1), (i_2, j_2), \dots\}$ je množina obsahující indexy známých polí matice $\_M$.

Naším cílem je doplnit neznámé hodnoty v matici a chceme, aby matice měla co nejmenší hodnost. Myslíme si totiž, že je několik nemnoho (skrytých) kategorií vtipů - třeba krátké, ironické, absurdní - a každý člověk preferuje nějaké kategorie. Proto se dá čekat, že by každý vtip měl jít popsat několika deskriptory, které jsou dostačující pro odhad hodnocení vtipu člověkem. Tyto deskriptory nechceme explicitně hledat, jsou zmíněny jako motivace pro požadavek co nejnižší hodnosti matice. Formálně tedy úlohu popíšeme následovně:

\begin{equation} {\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&{\text{rank}}(X)\\&{\text{subject to}}&X_{ij}=M_{ij}&\;\;\forall i,j\in E\\\end{aligned}}} \end{equation}

Hodnocení $\_M$ ale jsou zatížené šumem, proto bychom neměli trvat na rovnostech, ale relaxovat tuto podmínku. Tato úloha je ale i tak velice obtížná, protože hodnost matice je zuřivě nekonvexní a potřebujeme si ji zjednodušit. Buď přistoupíme k nejlepší konvexní aproximaci hodnosti, a tou je jádrová norma (nuclear norm), definovaná jako součet singulárních čísel: \begin{equation} {\displaystyle \|A\|_{*}=\operatorname {trace} \left({\sqrt {A^{T}A}}\right)=\sum _{i=1}^{\min\{m,n\}}\sigma _{i}(A),} \end{equation}

a v účelové funkci nahradíme hodnost matice její aproximací. Pro jednoduchost notace ještě zavedeme $P_{E}(\_A)$, což bude matice stejných rozměrů jako $\_A$ a \begin{equation} P_{E}(A)_{i,j} = \begin{cases} A_{i,j} & \text{pro } (i,j) \in E \\ 0 & \text{jinak } \end{cases} \end{equation} Ještě oznčíme práh $\delta$. Pak bude úloha ve tvaru: \begin{equation} {\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&\|X\|_{*}\\&{\text{subject to}}&\|P_{E }(X-M)\|_{F}\leq \delta \\\end{aligned}}} \end{equation}

Což je ekvivalentní úloze bez omezení:

\begin{equation} {\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&\ \lambda\|X\|_{*} + \|P_{\_E }(X-M)\|^2_{F} \\\end{aligned}}} \end{equation} Pro nějakou $\lambda$, kterou najdeme typicky krosvalidací. Tato úloha se řeší iterativně opakováním dvou kroků.

• $\_X_{ij}=\_M_{ij}\;\; \forall i,j\in \_E$
• Spočítejte SVD rozklad $\_X = \_U\_S\_V^T$, každé singulární číslo $\sigma$ nahraďte za $\sigma' = \max\{\sigma-\lambda, 0\}$ a opět roznásobte $\_X := \_U\_S'\_V^T$

Druhou možností, kterou vyzkoušíme je “uhodnout” - a krosvalidovat hodnost hledané matice $\_X$, která bude $r$. Poté budeme hledat matice $\_A$, $\_B$, že $\_A\_B^T = X$, kde $\_A$ i $\_B$ budou mít $r$ sloupečků.

\begin{equation} {\displaystyle {\begin{aligned}&{\underset {A,B}{\text{min}}}&\|P_{E }(AB^{T}-M)\|_{F}^{2}\\\end{aligned}}} \end{equation} Tato úloha je konvexní v $\_A$ i $\_B$ a můžeme ji řešit alternující minimalizací. Tedy Iterativně budeme metodou nejmenších čtverců počítat $\_A$ se zafixovaným $\_B$ a následně $\_B$ se zafixovaným $\_A$. Rozmyslete co počítáme, pokud je $\_M$ kompletně známá.