Recommender systém pomocou SVD a bidiagonalizácie

1 Úvod a motivácia

Odporúčacie systémy zohrávajú kľúčovú úlohu v moderných digitálnych platformách – od odporúčaní filmov na Netflixe, cez produkty na Amazone, až po hudbu na Spotify. Tieto systémy sa snažia personalizovať obsah na základe preferencií a správania používateľov, čím zvyšujú spokojnosť, angažovanosť a v konečnom dôsledku aj výnosy spoločnosti.

V tejto štúdii riešim úlohu predikcie chýbajúcich hodnotení položiek jednotlivými používateľmi. Každý používateľ hodnotí len malé množstvo položiek, preto máme do činenia s veľmi riedkou maticou hodnotení.

Formálne možno problém vyjadriť nasledovne: \(R \in \mathbb{R}^{m \times n}\), kde \(m\) je počet používateľov a \(n\) počet položiek. Matica je zvyčajne veľmi riedka, keďže väčšina hodnotení chýba. Cieľom je predikovať chýbajúce hodnotenia a zlepšiť používateľskú skúsenosť.

2 Teoretické pozadi

2.1 Bidiagonalizácia

Predstavme si maticu \(A \in \mathbb{R}^{m \times n}\) ktorá reprezentuje napríklad hodnotenia používateľov (riadky) voči položkám (stĺpce). V prípade odporúčacích systémov ide často o riedku a veľkú maticu. Na jej efektívne spracovanie potrebujeme nájsť vhodnú maticovú dekompozíciu. [@sukharskyi2019bidiagonalizaciia]

2.1.1 Cieľ bidiagonalizácie

Nájsť ortonormálne matice \(U \in \mathbb{R}^{m \times m},\) a \(V \in \mathbb{R}^{n\times n},\) také, že \(U^T A V = B\) kde \(U^T\) je transpozícia ortonormálnej matice \(U\) ortonormálna matica je \(V\), \(B \in \mathbb{R}^{m\times n}\) je bidiagonálna matica, teda matica, ktorá má nenulové prvky iba na hlavnej diagonále a prvej poddiagonále (pod hlavnou).

2.2 Singulárne rozloženie po bidiagonalizácii

Po tom, ako maticu \(A \in \mathbb{R}^{m \times n},\) zredukujeme na bidiagonálny tvar pomocou Golub–Kahanovej metódy, môžeme efektívne vypočítať jej singulárne rozloženie (SVD).

Formalna definicia:
\[ A = U\Sigma V^T\]kde \(U \in \mathbb{R}^{m \times m}\) – ortogonálna matica ľavých singulárnych vektorov, ktoré tvoria bázu priestoru riadkov \(A\)

\(V \in \mathbb{R}^{n \times n}\) – ortogonálna matica pravých singulárnych vektorov, ktoré tvoria bázu priestoru stĺpcov \(A\)

\(\Sigma \in \mathbb{R}^{m \times n}\) $σ1≥σ2≥⋯≥0σ1​≥σ2​≥⋯≥0.

Vlastnosti: Singulárne hodnoty reprezentujú dôležitosť jednotlivých skrytých komponentov v údajoch.

2.3 Aproximácia nízkeho rangu

Reálny svet často produkuje dáta so skrytou štruktúrou, ktoré možno efektívne vystihnúť maticou nízkeho rangu. Pomocou singulárneho rozkladu (SVD) vieme z matice \(A \in \mathbb{R}^{m \times n},\) extrahovať najdôležitejšie informácie a zanedbať menej významné detaily.

2.3.1 Princíp zníženia dimenzie

Po výpočte úplného rozkladu: \[ A = U\Sigma V^T\]

• Singulárne hodnoty \(\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r \geq 0\) diagonálnej matici

  \(\Sigma\) vyjadrujú relatívny význam jednotlivých komponentov.

Väčšina „energie“ (t. j. informácie alebo variability v údajoch) je sústredená v niekoľkých prvých hodnotách.

2.3.2 Aproximácia pomocou top-k komponentov

Vyberieme len prvých \(k\) singulárnych hodnôt a k nim prislúchajúce stĺpce matíc \(U\) a \(V\):
\[A_k = U_k \Sigma_k V_k^T,\] kde:

• \(U_k \in \mathbb{R}^{m \times k}\)

• \(\Sigma_k \in \mathbb{R}^{k \times k}\)

• \(V_k \in \mathbb{R}^{n \times k}\)

Táto aproximácia AkA_kAk​ má špeciálnu vlastnosť: \[\|A - A_k\|_F= \min_{\text{rank}(B) = k} \|A - B\|_F\]

Zo všetkých možných matíc \(B\) s hodnosťou najviac \(k\) je práve \(A_k\)​ najbližšia k pôvodnej matici \(A\)podľa Frobeniovej normy (súčet štvorcov všetkých rozdielov prvkov).

2.4 Vyhodnotenie

Predikované hodnotenia vyčítam z rekonštruovanej matice . Kvalitu odhadu meriame RMSE: \[\mathrm{RMSE} = \sqrt{\frac{1}{N} \sum_{(u,i)\in\mathcal{T}} (r_{ui} - \hat r_{ui})^2},\] kde \(\mathcal{T}\) je testovacia množina.

3 Dáta

Používam dataset MovieLens 100k, ktorý obsahuje 100 000 hodnotení od približne 943 používateľov na 1682 filmoch.

library(Matrix)
library(irlba)
library(ggplot2)
library(dplyr)

ratings <- read.table("C:/Users/vikap/OneDrive/Desktop/projekt.Plygach/u.data",
                      sep = "\t",
                      col.names = c("userId","movieId","rating","timestamp")) %>%
  select(-timestamp)

# Vytvorenie sparse matice R
R <- sparseMatrix(i = ratings$userId,
                  j = ratings$movieId,
                  x = ratings$rating,
                  dims = c(943, 1682))

# Rozdelenie na tréning a test
set.seed(123)
idx   <- sample(nrow(ratings), size = 0.8 * nrow(ratings))
train <- ratings[idx, ]
test  <- ratings[-idx, ]

R_train <- sparseMatrix(i = train$userId,
                        j = train$movieId,
                        x = train$rating,
                        dims = c(943,1682))

cat("Dáta načítané do objektu ratings:\n")

Dáta načítané do objektu ratings:

print(dim(ratings))

[1] 100000      3

cat("Prvých 6 riadkov:\n")

Prvých 6 riadkov:

print(head(ratings))

  userId movieId rating
1    196     242      3
2    186     302      3
3     22     377      1
4    244      51      2
5    166     346      1
6    298     474      4

4 Implementácia

# Počet latentných faktorov
k <- 20
set.seed(42)
svd_res <- irlba(R_train, nu = k, nv = k)

U_k <- svd_res$u
Sigma_k <- diag(svd_res$d)
V_k <- svd_res$v

# Rekonštrukcia matice
R_hat <- U_k %*% Sigma_k %*% t(V_k)

#VÝSLEDKY
cat("Počet latentných faktorov k =", k, "\n")

Počet latentných faktorov k = 20 

cat("Prvých 5 singulárnych hodnôt:\n")

Prvých 5 singulárnych hodnôt:

print(head(svd_res$d, 5))

[1] 514.5335 198.6843 177.5206 132.4337 128.5647

cat("Rozmery U_k:", paste(dim(U_k), collapse = "×"), "\n")

Rozmery U_k: 943×20 

cat("Rozmery Sigma_k:", paste(dim(Sigma_k), collapse = "×"), "\n")

Rozmery Sigma_k: 20×20 

cat("Rozmery V_k:", paste(dim(V_k), collapse = "×"), "\n")

Rozmery V_k: 1682×20 

cat("Rozmery rekonštruovanej matice R_hat:", paste(dim(R_hat), collapse = "×"), "\n")

Rozmery rekonštruovanej matice R_hat: 943×1682 

5 Výsledky

# Výpočet RMSE na testovacej množine
true_vals <- test$rating
pred_vals <- mapply(function(u, m) R_hat[u, m], test$userId, test$movieId)
rmse <- function(actual, pred) sqrt(mean((actual - pred)^2))
cat("RMSE =", rmse(true_vals, pred_vals), "\n")

RMSE = 2.66287 

# Spektrum singulárnych hodnôt
df_sigma <- data.frame(idx = 1:length(svd_res$d), sigma = svd_res$d)
print(
  ggplot(df_sigma, aes(x = idx, y = sigma)) +
    geom_line() +
    labs(title = "Spektrum singulárnych hodnôt", x = "Index i", y = expression(sigma[i]))
)

# RMSE vs. k
results <- data.frame(k = integer(), rmse = double())
for(k_try in seq(5, 50, by = 5)){
  r <- irlba(R_train, nu = k_try, nv = k_try)
  Rk <- r$u %*% diag(r$d) %*% t(r$v)
  preds <- mapply(function(u, m) Rk[u, m], test$userId, test$movieId)
  results <- rbind(results, data.frame(k = k_try, rmse = rmse(true_vals, preds)))
}
print(
  ggplot(results, aes(x = k, y = rmse)) +
    geom_point() + geom_line() +
    labs(title = "Závislosť RMSE na počte faktorov k", x = "k", y = "RMSE")
)

5.1 Tabuľka výsledkov RMSE

Nasledujúca tabuľka zobrazuje hodnoty RMSE pre rôzne počty latentných faktorov \(k\).

Table: (#tab:rmse) Hodnoty RMSE pri rôznych hodnotách \(k\)

library(knitr)
kable(results, caption = "RMSE pre rôzne hodnoty latentných faktorov k")

RMSE pre rôzne hodnoty latentných faktorov k

k	rmse
5	2.703444
10	2.629588
15	2.633864
20	2.662870
25	2.698867
30	2.737992
35	2.775405
40	2.813379
45	2.856580
50	2.892384

6 Diskusia

• Latentné faktory interpretujem ako skryté vlastnosti filmov a používateľov.

• Metóda funguje dobre pri menšom počte faktorov, no príliš malé \(k\) môže stratiť dôležitú informáciu.

7 Záver

V tejto práci som ukázala, že singulárne rozloženie matice (SVD), realizované prostredníctvom Golub–Kahanovej bidiagonalizácie, predstavuje efektívny nástroj na predikciu chýbajúcich hodnotení v odporúčacích systémoch. Tento prístup umožňuje aproximovať pôvodnú hodnotiacu maticu pomocou matice nízkeho rangu, čím sa efektívne zachytávajú skryté vzťahy a preferencie medzi používateľmi a položkami.

Získaná aproximácia poskytuje kompaktnejšiu reprezentáciu dát, ktorá odhaľuje latentné faktory zodpovedné za používateľské správanie. Vďaka tomu je možné vytvárať kvalitnejšie odporúčania aj v prípadoch, keď je väčšina hodnotení nedostupná (tzv. problém riedkosti matice).

7.0.1 Výhody:

• Redukcia dimenzie a šumu v dátach,

• schopnosť generalizovať na neznáme hodnotenia,

• jednoduchosť a stabilita numerického riešenia.

Teória bidiagonalizácie bola opísaná v práci [1]. Okrem toho, základné metódy sú zhrnuté v [2].

References

[1]

Сухарський, Олександр В., “Голуб–Каханова бідіагоналізація та її застосування у чисельних методах.” [Online]. Available: http://dspace.nbuv.gov.ua/bitstream/handle/123456789/191025/04-Sukharskyi.pdf?sequence=1

[2]

—, “Навчальний посібник «МАТЕМАТИЧНІ МЕТОДИ МОДЕЛЮВАННЯ».” [Online]. Available: https://www.kdu.edu.ua/new/PHD_vid/Nav_posibnuk_MMM.pdf