लोग एडवाइजर सिस्टम से मिलते हैं। गुणन

मशीन लर्निंग ने हमारे रोजमर्रा के जीवन में बहुत प्रवेश किया है। कुछ को अब आश्चर्य नहीं होता है जब उन्हें अपने स्मार्टफ़ोन में तंत्रिका नेटवर्क के बारे में बताया जाता है। इस विज्ञान में बड़े क्षेत्रों में से एक सिफारिश प्रणाली है। वे हर जगह हैं: जब आप संगीत सुनते हैं, किताबें पढ़ते हैं, टीवी शो या वीडियो देखते हैं। इस विज्ञान का विकास YouTube , Spotify और Netfilx जैसी दिग्गज कंपनियों में होता है । बेशक, इस क्षेत्र में सभी वैज्ञानिक उपलब्धियां प्रसिद्ध न्यूरिप्स या आईसीएमएल सम्मेलनों में प्रकाशित की जाती हैं , और थोड़े कम प्रसिद्ध रिकशे मेंइस विषय पर पैनापन। और इस लेख में हम इस बारे में बात करेंगे कि यह विज्ञान कैसे विकसित हुआ, तब और अब की सिफारिशों में किन विधियों का उपयोग किया जाता है, और इस सब के पीछे क्या गणित है।

मुझे यह लेख स्केलेटेक में स्टैडमटेक से संबंधित सिफारिशों वाले सिस्टम में काम करके लिखने के लिए प्रेरित किया गया था ।

क्यों और किसके लिए यह लेख

यह हम में से प्रत्येक के लिए महत्वपूर्ण क्यों हो सकता है? नीचे दी गई सूची पर एक नज़र डालें:

• वीडियो सिफारिशें: YouTube, Netlix, HBO, Amazon Prime, Disney +, Hulu, Okko
• ऑडियो सिफारिशें: Spotify, Yandex.Music, Yandex.Radio, Apple Music
• उत्पाद अनुशंसाएँ: अमेज़न, Avito, लीटर, MyBook
• खोज अनुशंसाएँ: Google, यैंडेक्स, बिंग, याहू, मेल
• : Booking, Twitter, Instagram, ., , GitHub

, . , . , , YouTube.

( ), . , , . , ( ). -, . , -, , - . , . , , , , .

, , , , - . , (, , , ..). , .

, . : $$$U$ $$$I$ — . $$$r_{ui}$ $$$u$ $$$i$. , , , , . :

$$

$$\mathcal{D} = \{ (u, i) |\text{ if } \exists r_{ui}, u \in U, i \in I\}$$

$$$f$:

$$

$$f(u, i) = \hat{r}_{ui}\approx r_{ui}$$

, $$$r_{ui}$ 1 5 ( ) : 1 -1 ( / )

3 :

• Content-based (CB)
• Collaborative filtering (CF)
• Hybrid recommendations

. — , . : — , — , . . , : , ..

, . - , .

. , , , .

, , . . , , . .

Matrix Factorization

, . : . .

• :
  
  • Singular Value Decomposition (SVD)
  • Singular Value Decomposition with implicit feedback (SVD++)
  • Collaborative Filtering with Temporal Dynamics (TimeSVD++)
  • Weighted Matrix Factorization (WMF or ALS)
  • Sparse Linear Methods (SLIM)
  • Factorization Machines (FM)
• :
  
  • Probabilistic Matrix Factorization (PMF)
  • Bayesian Probabilistic Matrix Factorization (BPMF)
  • Bayesian Factorization Machines (BFM)
  • Gaussian Process Factorization Machines (GPFM)

Singular Value Decomposition (SVD)

— SVD. $$$A$ $$$n \times m$, $$$n = |U|$, $$$m = |I|$. $$$\mathcal{D}$ $$$A_{ui} = r_{ui}$, . SVD , $$$A$ : $$$U,~\Sigma,~V$. $$$k$ , $$$A$.

$$

$$A = U \Sigma V^T, \quad\quad\quad\quad A \approx \hat{A} = \hat{U} \hat{ \Sigma } \hat{V}^T .$$

$$$Q$ $$$P$ . $$$A$ :

$$

$$P = (\hat{U} \hat{ \Sigma })^T, \quad\quad Q = \hat{V}^T, \quad\quad\quad\quad A \approx P^T \cdot Q .$$

:

$$

$$r_{ui} \approx \hat{r}_{ui} = p^T_u q_i .$$

, $$$p_u$ $$$q_i$ — $$$u$ $$$i$ - $$$k$. . . :

$$

$$\Theta = \{ p_u, q_i| u \in U, i \in I\} .$$

c :

$$

$$\sum_{(u, i) \in \mathcal{D}} (r_{ui} - \hat{r}_{ui})^2 + \lambda\sum_{\theta \in \Theta}\|\theta\|^2 = \sum_{(u, i) \in \mathcal{D}} (r_{ui} - p^T_u q_i)^2 + \lambda\sum_{u \in U}\|p_u\|^2 + \lambda\sum_{i \in I}\|q_i\|^2 .$$

, , , , . $$$\hat{r}_{ui}$. (GD) (ALS). Habr- , . , , .

( SVD, SVD$$$_{bias}$). , , . . SVD . (bias):

$$

$$\hat{r}_{ui} =\mu + b_u + b_i + p^T_u q_i ,$$

$$$b_u$ — , $$$b_i$ — , $$$\mu$ — . :

$$

$$\Theta = \{ \mu, b_u, b_i, p_u, q_i| u \in U, i \in I\} .$$

SVD++

Factorization Meets the Neighborhood SVD . (explicit and implicit user feedback). $$$r_{ui}$, . . : $$$R(u)$ — ( ) $$$N(u)$ — ( ).

SVD++ :

$$

$$\hat{r}_{ui} =\mu + b_u + b_i + q^T_i \left( p_u + |N(u)|^{-1/2} \sum_{j \in N(u)} y_j \right) .$$

:

$$

$$\Theta = \{ \mu, b_u, b_i, p_u, q_i, y_i| u \in U, i \in I\} .$$

, $$$N(u)$ $$$R(u)$, .. $$$R(u) \subset N(u)$. (item-item recommendation).

Asymmetric-SVD

SVD++ . . :

$$

$$\hat{r}_{ui} = b_{ui} + q^T_i \left( |R(u)|^{-1/2} \sum_{j \in R(u)} (r_{uj} - b_{uj})x_j + |N(u)|^{-1/2} \sum_{j \in N(u)} y_j \right) ,$$

$$$b_{ui} = \mu + b_u + b_i$

TimeSVD++

TimeSVD++. (MovieLens, Netflix) , . , . Collaborative Filtering with Temporal Dynamics SVD++ :

$$

$$\hat{r}_{ui}(t) =\mu + b_u(t) + b_i(t) + q^T_i \left( p_u(t) + |R(u)|^{-1/2} \sum_{j \in R(u)} y_j \right) .$$

, :
Item bias: , ( 30 ) $$$b_{i,\text{Bin}(t)}$ , , $$$t$:

$$

$$b_i(t) = b_i + b_{i, \text{Bin}(t)}$$

उपयोगकर्ता पूर्वाग्रह: नेफ्लिक्स के डेटा का विश्लेषण करते हुए, हमने देखा कि प्रत्येक उपयोगकर्ता के लिए औसतन केवल 40 दिन हैं जिसमें उसने रेटिंग डाल दी है। इसलिए, हम सामान के साथ काम करेंगे और अपने स्वयं के मापदंडों को जोड़ेंगे$$$b_{u, t}$प्रत्येक उपयोगकर्ता के लिए। हम समय पर एक रैखिक निर्भरता जोड़ते हैं - हम एक अतिरिक्त अवधि का परिचय देते हैं$$$\alpha_u$ मूल्यह्रास अनुपात के साथ:

$$

$$b_i(t) = b_i + \alpha_u \cdot \text{dev}_u(t) + b_{u, t} \quad\quad\quad\quad \text{dev}_u(t) = \text{sign}(t - t_u) \cdot |t - t_u|^{\beta}$$

।
उपयोगकर्ताओं के लिए समय निर्भरता को जोड़ने के अन्य विकल्प हैं: यह आलेख में अधिक विवरण में वर्णित है
उपयोगकर्ता एम्बेडिंग: हम अपने अव्यक्त प्रतिनिधित्व के प्रत्येक घटक के लिए एक समान चाल जोड़ेंगे$$$p_u(t) = (p_{u1}(t), \dots, p_{uf}(t))^T$:

$$

$$p_{uk}(t) = p_{uk} + \alpha_{uk} \cdot \text{dev}_u(t) + p_{uk, t}.$$

भारित मैट्रिक्स फैक्टराइजेशन (WMF) और अल्टरनेटिंग लिस्ट स्क्वेयर (ALS)

, SVD, . SVD++. — Weighted Matrix Factorization (WMF). ($$$\hat{r}_{ui} = p^T_u q_i$), . $$$r_{ui}$, (.. $$$(u, i) \notin \mathcal{D}$) 0. $$$(u, i)$ $$$c_{ui}$, $$$r_{ui}$. , . - . YouTube , . , , , . , , , :

$$

$$\sum_{(u, i)} c_{ui}(r_{ui} - \hat{r}_{ui})^2 + \lambda\sum_{\theta \in \Theta}\|\theta\|^2 .$$

: $$$c_{ui} = 1 + \alpha r_{ui}$. : $$$r_{ui}>0$ $$$r_{ui} = 0$. $$$\alpha$ $$$\alpha = 40$ .

, (ALS) . WMF, ALS, .

Fast Alternating Least Squares

ALS , eALS . , . , . .

, $$$c_{ui}$ ALS :

$$

$$c_{ui} = c_i + \alpha r_{ui}, \quad\quad\quad\quad c_i = c_0 \frac{f_i^{\beta}}{\sum_{j \in I} f_j^{\beta}} ,$$

$$$c_0$ $$$\beta$, .

Sparse Linear Methods (SLIM)

Sparse Linear Methods (SLIM) . , SVD . . SLIM :

$$

$$\hat{a}_{ui} = a^T_u w_i \quad\quad\quad\quad \hat{A} = AW$$

$$$W \in \mathbb{R}^{m \times m}$. : $$$W \geq 0$ $$$\text{diag}(W) = 0$. :

$$

$$\frac{1}{2}\|A - AW\|^2_F + \frac{\beta}{2}\|W\|^2_F + \lambda\|W\|_1$$

$$$W$ .

Factorization Machines (FM)

, Factorization Machines (FM). , ( 2- ). :

$$

$$\hat{r}(x) = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{i=j+1}^{n} v^T_i v_j ~ x_i x_j, \quad\quad\quad\quad w_0 \in \mathbb{R} ~~~ w \in \mathbb{R}^n ~~~ V \in \mathbb{R}^{n \times k} .$$

(SGD) ( ). , $$$x$ $$$(u, i)$. . , — . — ( ). ( ).

, SVD, SVD++ — FM. SVD , :

$$

$$n = | U \cup I |, \quad\quad\quad x_j = \delta (j = u ~\lor~ j = i) .$$

$$$\delta$ — . .. $$$x$ $$$u$ $$$i$. FM :

$$

$$\hat{r}(x) = w_0 + w_u + w_i + v^T_u v_i .$$

, $$$x$: , . , , , , , , . .

Probabilistic Matrix Factorization (PMF)

, , , .

(PMF), . , SVD: $$$p_u$ $$$q_i$ — . , :

$$

$$p(r | P, Q, \sigma) = \prod_{(u, i) \in \mathcal{D}}\mathcal{N}(r_{ui}| g(p_u^Tq_i), \sigma^2) ,$$

$$$\mathcal{N}$ — , a $$$g(x) = \frac{1}{1 + e^{-x}}$ — (). , , :

$$

$$p(P| \sigma_p) = \prod_{u \in U} p(p_u| 0, \sigma^2_p \mathbf{I}), \quad\quad\quad\quad p(Q| \sigma^2_q) = \prod_{i \in I} p(q_i| 0, \sigma_q^2 \mathbf{I}) .$$

( ) , :

$$

$$\frac{1}{2} \sum_{(u, i) \in \mathcal{D}} (r_{ui} - p_u^T q_i)^2 + \frac{\lambda_p}{2} \sum_{u \in U} \|p_u\|^2 + \frac{\lambda_q}{2} \sum_{i \in I} \|q_i\|^2 ,$$

$$$\lambda_p = \frac{\sigma_p}{\sigma}$ $$$\lambda_q = \frac{\sigma_q}{\sigma}$ — . , SVD , .

Constrained PMF

PMF Constrained PMF. , SVD SVD++. , , $$$p_u$ :

$$

$$p_u + \frac{\sum_{i \in R(u)} y_i}{|R(u)|} ,$$

$$$R(u)$ — , $$$u$.

Bayesian Probabilistic Matrix Factorization (BPMF)

PMF BPMF. PMF , , . :

$$

$$p(P| \mu_p, \Lambda_p) = \prod_{u \in U} p(p_u| \mu_p, \Lambda_p) ,\quad\quad\quad\quad p(Q| \mu_q, \Lambda_q) = \prod_{i \in I} p(q_i| \mu_q, \Lambda_q) .$$

$$$\Theta_p = \{ \mu_p, \Lambda_p \}$ $$$\Theta_q = \{ \mu_q, \Lambda_q \}$ - $$$\Theta_0 = \{ \mu_0, \nu_0, W_0 \}$. , .

Bayesian Factorization Machines (BFM)

, Bayesian, . , $$$\Theta = \{ w_0, w_i, v_i\} .$ , - . : $$$\Theta_H = \{ \lambda_{\theta}, \mu_{\theta} | \theta \in \Theta \}$. .

Gaussian Process Factorization Machines (GPFM)

GPFM . $$$f$ $$$\theta$. $$$\theta_u$ , , :

$$

$$\hat{r}_{ui} = f(q_i, \theta_u)$$

, . , $$$f$ , . , , , .

.

: Bayesian Personalized Ranking (BPR)

BPR , "". , BPR — , , Bayesian Personalized Ranking. . , , $$$i$ $$$j$ $$$u$. $$$(u, i)$ $$$r_{ui}$ $$$(u, i, j)$ $$$i$ $$$j$ ((+) $$$i$ , $$$j$ (-) ). $$$\mathcal{D}_S$. . ( personalized ):

$$

$$p(i <_u j | \Theta) = \sigma(\hat{r}_{uij}(\Theta)) ,$$

$$$\sigma$ — , a $$$\hat{r}_{uij}$ — . (MLE), , :

$$

$$\min_{\Theta} \sum_{(u, i, j) \in \mathcal{D}_S}\ln{\sigma(\hat{r}_{uij})} - \lambda \|\Theta\|^2$$

(SGD):

$$

$$\Theta \leftarrow \Theta + \alpha\left(\frac{e^{-\hat{r}_{uij}}}{1 + e^{-\hat{r}_{uij}}} \cdot \frac{\partial}{\partial \Theta}\hat{r}_{uij} + \lambda \Theta \right)$$

, . , , . SVD:

$$

$$\hat{r}_{uij} = \hat{r}_{ui} - \hat{r}_{uj} \quad\quad\quad\quad \hat{r}_{ui} = p_u^T q_i$$

:

$$

$$\frac{\partial}{\partial \Theta}\hat{r}_{uij} =\begin{cases} (q_{ik} - q_{jk})~~~\text{if } \theta = p_{uk}\\ p_{uk}~~~~~~~~~~~~~~~\text{if } \theta = q_{ik}\\ -p_{uk}~~~~~~~~~~~~\text{if } \theta = q_{jk} \end{cases}$$

BPR ( ) , . , . . , (pairwise approach) (pointwise approach). . , 5 , . , , . — BPR - , . , .

Show must go on

इस बार हमने सिफारिश प्रणालियों में कई फैक्टराइजेशन विधियों पर चर्चा की, लेकिन ग्राफ और न्यूरल नेटवर्क , जिसमें बहुत सारी दिलचस्प चीजें भी हैं , अछूती रही ।