こんにちは、さとうみなと です。正月早々ですが、推薦関係のコードをGithubで読み漁っていたらSGDではなくAlternating Least Squares (ALS) = 交互最小二乗法で最適化しているものがあり、あまり実装したこともなかったので勉強し直してみました（すっごい今更感）。
w u ∈ W \boldsymbol{w}_u \in W w u ∈ W u u u h i ∈ H \boldsymbol{h}_i \in H h i ∈ H i i i r u i ∈ R r_{ui} \in R r u i ∈ R u u u i i i
（あくまで行列分解の文脈で）ざっくり言うと W W W H H H H H H W W W W W W H H H
min W , H ∑ u , i ( r u i − w u T h i ) 2 + λ ( ∑ u ∥ w u ∥ 2 + ∑ i ∥ h i ∥ 2 ) \min _{W, H} \sum_{u,i}\left(r_{u i}-\boldsymbol{w}_{u}^{\mathsf{T}} \boldsymbol{h}_{i}\right)^{2}+\lambda\left(\sum_{u}\left\|\boldsymbol{w}_{u}\right\|^{2}+\sum_{i}\left\|\boldsymbol{h}_{i}\right\|^{2}\right) W , H min u , i ∑ ( r u i − w u T h i ) 2 + λ ( u ∑ ∥ w u ∥ 2 + i ∑ ∥ h i ∥ 2 ) この目的関数についてアイテムの潜在ベクトル H H H W W W = 0 =0 = 0
∂ ∂ w u ( ∑ u i ( r u i 2 − 2 r u i w u T h i + ( w u T h i ) 2 ) + λ ( ∑ u ∥ w u ∥ 2 + ∑ i ∥ h i ∥ 2 ) ) = ∑ i ( − 2 r u i h i + ( 2 h i 1 w u T h i 2 h i 2 w u T h i ⋮ 2 h i K w u T h i ) ) + 2 λ w u = 0 \begin{aligned}
\frac{\partial}{\partial \boldsymbol{w}_u} \left( \sum_{ui} \left(r_{u i}^2- 2r_{u i}\boldsymbol{w}_{u}^{\mathsf{T}} \boldsymbol{h}_{i} + \left( \boldsymbol{w}_{u}^{\mathsf{T}} \boldsymbol{h}_{i} \right) ^ 2 \right) +\lambda\left(\sum_{u}\left\|\boldsymbol{w}_{u}\right\|^{2}+\sum_{i}\left\|\boldsymbol{h}_{i}\right\|^{2}\right) \right)\\
= \sum_{i}
\left(
-2r_{ui} \boldsymbol{h}_{i} +
\left(
\begin{array}{c}
2h_{i1} \boldsymbol{w}_u^{\mathsf{T}} \boldsymbol{h}_i \\
2h_{i2} \boldsymbol{w}_u^{\mathsf{T}} \boldsymbol{h}_i \\
\vdots \\
2h_{iK} \boldsymbol{w}_u^{\mathsf{T}} \boldsymbol{h}_i
\end{array}
\right)
\right) + 2\lambda \boldsymbol{w}_u = 0
\end{aligned} ∂ w u ∂ ( u i ∑ ( r u i 2 − 2 r u i w u T h i + ( w u T h i ) 2 ) + λ ( u ∑ ∥ w u ∥ 2 + i ∑ ∥ h i ∥ 2 ) ) = i ∑ ⎝ ⎜ ⎜ ⎜ ⎜ ⎛ − 2 r u i h i + ⎝ ⎜ ⎜ ⎜ ⎜ ⎛ 2 h i 1 w u T h i 2 h i 2 w u T h i ⋮ 2 h i K w u T h i ⎠ ⎟ ⎟ ⎟ ⎟ ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎞ + 2 λ w u = 0 ∑ i ( h i 1 h i T w u h i 2 h i T w u ⋮ h i K h i T w u ) + λ w u = ∑ i r u i h i ( ∑ i h i h i T + λ I K ) w u = ∑ i r u i h i ∴ w u = ( ∑ i h i h i T + λ I K ) − 1 ( ∑ i r u i h i ) \sum_{i}
\left(
\begin{array}{c}
h_{i1} \boldsymbol{h}_i^{\mathsf{T}} \boldsymbol{w}_u \\
h_{i2} \boldsymbol{h}_i^{\mathsf{T}} \boldsymbol{w}_u \\
\vdots \\
h_{iK} \boldsymbol{h}_i^{\mathsf{T}} \boldsymbol{w}_u
\end{array}
\right) + \lambda \boldsymbol{w}_u
= \sum_{i} r_{ui} \boldsymbol{h}_{i}\\
\left(\sum_{i} \boldsymbol{h}_i \boldsymbol{h}_i^{\mathsf{T}} + \lambda I_K \right) \boldsymbol{w}_u = \sum_{i} r_{ui} \boldsymbol{h}_{i}\\
\therefore \boldsymbol{w}_u = \left(\sum_{i} \boldsymbol{h}_i \boldsymbol{h}_i^{\mathsf{T}} + \lambda I_K \right)^{-1} \left( \sum_{i} r_{ui} \boldsymbol{h}_{i} \right) i ∑ ⎝ ⎜ ⎜ ⎜ ⎜ ⎛ h i 1 h i T w u h i 2 h i T w u ⋮ h i K h i T w u ⎠ ⎟ ⎟ ⎟ ⎟ ⎞ + λ w u = i ∑ r u i h i ( i ∑ h i h i T + λ I K ) w u = i ∑ r u i h i ∴ w u = ( i ∑ h i h i T + λ I K ) − 1 ( i ∑ r u i h i ) 同様に
h i = ( ∑ u w u w u T + λ I K ) − 1 ( ∑ u r u i w u ) \boldsymbol{h}_i = \left(\sum_{u} \boldsymbol{w}_u \boldsymbol{w}_u^{\mathsf{T}} + \lambda I_K \right)^{-1} \left( \sum_{u} r_{ui} \boldsymbol{w}_{u} \right) h i = ( u ∑ w u w u T + λ I K ) − 1 ( u ∑ r u i w u ) を得る。
そういえば先日紹介したExpoMF の各潜在ベクトル更新式は
θ u ← ( λ y ∑ i p u i β i β i T + λ θ I K ) − 1 ( ∑ i λ y p u i y u i β i ) β i ← ( λ y ∑ u p u i θ u θ u T + λ β I K ) − 1 ( ∑ u λ y p u i y u i θ u ) \begin{aligned}
&\boldsymbol{\theta}_{u} \leftarrow\left(\lambda_{y} \sum_{i} p_{u i} \boldsymbol{\beta}_{i} \boldsymbol{\beta}_{i}^{\mathsf{T}}+\lambda_{\theta} I_{K}\right)^{-1}\left(\sum_{i} \lambda_{y} p_{u i} y_{u i} \boldsymbol{\beta}_{i}\right)\\
&\boldsymbol{\beta}_{i} \leftarrow\left(\lambda_{y} \sum_{u} p_{u i} \boldsymbol{\theta}_{u} \boldsymbol{\theta}_{u}^{\mathsf{T}}+\lambda_{\beta} I_{K}\right)^{-1}\left(\sum_{u} \lambda_{y} p_{u i} y_{u i} \boldsymbol{\theta}_{u}\right)
\end{aligned} θ u ← ( λ y i ∑ p u i β i β i T + λ θ I K ) − 1 ( i ∑ λ y p u i y u i β i ) β i ← ( λ y u ∑ p u i θ u θ u T + λ β I K ) − 1 ( u ∑ λ y p u i y u i θ u ) where p u i is the expectation of exposure. \text{where } p_{ui} \text{ is the expectation of exposure.} where p u i is the expectation of exposure. だったので、これからexposureの期待値を除いたものが、ナイーブなALSによる更新式となります。
01: input: rating matrix R R R w 1 : U \boldsymbol{w}_{1:U} w 1 : U h 1 : I \boldsymbol{h}_{1:I} h 1 : I loop for each iterationloop for u ∈ { 1 , ⋯ , U } u \in \{1,\cdots,U\} u ∈ { 1 , ⋯ , U } w u = ( ∑ i h i h i T + λ I K ) − 1 ( ∑ i r u i h i ) \boldsymbol{w}_u = \left(\sum_{i} \boldsymbol{h}_i \boldsymbol{h}_i^{\mathsf{T}} + \lambda I_K \right)^{-1} \left( \sum_{i} r_{ui} \boldsymbol{h}_{i} \right) w u = ( ∑ i h i h i T + λ I K ) − 1 ( ∑ i r u i h i ) loop for i ∈ { 1 , ⋯ , I } i \in \{1,\cdots,I\} i ∈ { 1 , ⋯ , I } h i = ( ∑ u w u w u T + λ I K ) − 1 ( ∑ u r u i w u ) \boldsymbol{h}_i = \left(\sum_{u} \boldsymbol{w}_u \boldsymbol{w}_u^{\mathsf{T}} + \lambda I_K \right)^{-1} \left( \sum_{u} r_{ui} \boldsymbol{w}_{u} \right) h i = ( ∑ u w u w u T + λ I K ) − 1 ( ∑ u r u i w u )
import numpy as np
from lightfm. datasets import fetch_movielens
dataset = fetch_movielens( min_rating= 4.0 )
iterations = 3
K = 20
lambda_theta = 1e-2
lambda_beta = 1e-2
U, I = dataset[ "train" ] . shape
R = dataset[ "train" ] . toarray( )
R[ R > 0 ] = 1.0
W = np. random. uniform( low= - 0.1 , high= 0.1 , size= ( U, K) ) / K
H = np. random. uniform( low= - 0.1 , high= 0.1 , size= ( I, K) ) / K
for iteration in range ( iterations) :
print ( f"CURRENT ITERATION = { iteration+ 1 } " )
for u in range ( U) :
B = np. zeros( ( K, K) )
a = np. zeros( K)
for i in range ( I) :
B += H[ i, None ] * H[ i, None ] . T
a += R[ u, i] * H[ i]
B += lambda_theta * np. eye( K)
W[ u] = np. linalg. solve( B, a)
for i in range ( I) :
B = np. zeros( ( K, K) )
a = np. zeros( K)
for u in range ( U) :
B += W[ u, None ] * W[ u, None ] . T
a += R[ u, i] * W[ u]
B += lambda_beta * np. eye( K)
H[ i] = np. linalg. solve( B, a)
R_test = dataset[ "test" ] . toarray( )
R_test[ R_test > 0 ] = 1.0
from sklearn import metrics
predicted = W. dot( H. T)
scores = np. zeros( U)
for u in range ( U) :
fpr, tpr, thresholds = metrics. roc_curve( R_test[ u] , predicted[ u] )
scores[ u] = metrics. auc( fpr, tpr) if len ( set ( R_test[ u] ) ) != 1 else 0.0
print ( f"test mean auc: { scores. mean( ) } " ) 僕の実行環境では下記の通りとなり、予想通り前回のExpoMF よりも性能が劣る結果となりました。
CURRENT ITERATION = 1
CURRENT ITERATION = 2
CURRENT ITERATION = 3
test mean auc: 0.8723854034443516今回はALSでの行列分解の学習について簡単に紹介と実装を行ってみました。数式やコード、説明に間違いございましたらTwitter かコメント欄までお願い致します。
