Factorization Machines

Collaborative Filteringの概要とFactorization Machinesの説明

Transcript

1. Factorization Machines
2. Ø もともと推薦システムに使われたモデル Ø 協調フィルタリングの⼿法の⼀つ
3. 協調フィルタリング 3 複数のユーザーの嗜好に基づく推薦 ・ 推薦対象の特徴量を必要としない ・ ⼈では予測できないようなものが推薦される可能性がある(新規性）
4. 協調フィルタリングの基本モデル a b c d e A 5 1 ? 3 4 B 1 3 4 5 C 5 5 2 4 D 4 5 2 1 E 4 1 4 2 アイテム ユ ザ ユーザーAとの類似度 4 B -0.5 C 0.9 D -0.9 E 0.7
5. B -0.5 C 0.9 D -0.9 E 0.7 5 類似度の⾼いユーザーを選択する a b c d e A 5 1 ? 3 4 B 1 3 4 5 C 5 5 2 4 D 4 5 2 1 E 4 1 4 2 アイテム ユ ザ ユーザーAとの類似度 協調フィルタリングの基本モデル
6. 嗜好の似ているユーザーを基に予測する 予測値= (5*0.9＋4*0.7)/2=3.65 6 B -0.5 C 0.9 D -0.9 E 0.7 類似度の⾼いユーザーを選択する a b c d e A 5 1 ? 3 4 B 1 3 4 5 C 5 5 2 4 D 4 5 2 1 E 4 1 4 2 アイテム ユ ザ ユーザーAとの類似度 協調フィルタリングの基本モデル
7. 問題点 スパース問題 ・評価されてるアイテムは圧倒的に少ない 10,000以上のアイテム 100,000 以上のユーザー 評価⾏列 約99%評価されていない ことがほとんど 7
8. スパース問題 密度が低いほど、精度が悪い 縦軸: MAE（低いほうが精度が良い） 横軸: 密度（評価率） [Joonseok Lee+ 2012] 密度ごとの精度 8
9. Matrix Factorization r aj ∧ = f (u a ,v j ) 9 予測値 ユーザーとアイテムの嗜好ベクトルを学習し、予測を⾏う ユーザーの 嗜好ベクトル アイテムの 嗜好ベクトル l スパースに⽐較的強い l Netflix Prizeでよく使われたモデル 協調フィルタリングで有名なアルゴリズム
10. 評価⾏列 = ユーザー⾏列 アイテム⾏列 1 n 1 m user item 1 r 1 r VT :r × m 10 U : n×r U a ユーザーの 嗜好ベクトル アイテムの 嗜好ベクトル a j V j T ˆ r a, j =U a V j T a j R : n× m ユーザー嗜好ベクトルとアイテム嗜好ベクトルを 学習することによって次元の削減を⾏う パラメータ Matrix Factorization
11. min b,U,V (r a, j − ˆ r a, j )2 + λ(U a 2 + V j 2 + b2 a + b2 j ) (a, j)∈R ∑ ˆ r a, j = µ + b a + b j +U a V j T モデル ⽬的関数 [Y.Koran+ 2009] 11 バイアス ユーザー バイアス アイテム バイアス ユーザー嗜好ベクトル アイテム嗜好ベクトル 評価値のついているユーザーとアイテムのみを学習に使う Matrix Factorization
12. 問題点 l ユーザーやアイテムのコンテキスト情報（年齢、性別、ジャンルなど）を扱えない l 新しいアイテム、ユーザーに対して予測ができない（精度が低い）
13. Factorization Machines 13 ユーザー同⼠の嗜好の相関情報に加えてコンテキスト情報を加えられる ユ ザ アイテム A B C x y z 特徴量 特徴ベクトル 5 1 3 4 5 5 y(評価値） ユーザー アイテム
14. Factorization Machines 14 Χ(1) Χ(2) Χ(3) Χ(4) Χ(5) V :k ×n 1 k 1 n w 0 1 n W :1×(n+1) f j k f f i n i n i j j i n i i i v v x x x w w y , 1 , 1 1 1 0 ) ( ˆ ∑ ∑ ∑ ∑ = = + = = + + = Χ バイアス 特徴量 重み 特徴量同⼠ の相関関係 training data 各パラメータ A B C x y z 特徴量 ユーザー アイテム
15. 各特徴量の相関関係も学習できる k : 特徴ベクトルの次元 (ハイパーパラメータ) Factorization Machines 15 f j k f f i n i n i j j i n i i i v v x x x w w X y , 1 , 1 1 1 0 ) ( ˆ ∑ ∑ ∑ ∑ = = + = = + + =
16. 計算量 " = & + ( ) ) + ( ( ) + ( ),. +,. / .01 2 +0)31 2 )01 2 )01 = & + () ) + 1 2 ( (),. ) 2 )01 6 − (),. 6 2 )01 ) 6 / .01 2 )01 ()
17. 利点 l より多くのデータを活⽤することができる l スパースなものに対しても⾼い精度が出せる l 新しいユーザーやアイテムに対しても予測ができる
18. 学習⽅法 ３つの学習⽅法がある l 確率的勾配降下法（SGD） l 最⼩⾃乗法(ALS) l マルコフ連鎖モンテカルロ法(MCMC) オンライン学習で、収束も割と早い バッチ学習で、収束も早くない 試したことない よくわからない
19. 学習（SGD) ⽬的関数 ( " , + ( E 6 EGH (I,J)GK " , = " − 6 = − M ME " , + 2E 各パラメータの更新式 損失関数 正規化項 & , ) , ),. E & , O , PQ
20. 各パラメータの学習（SGD) f j k f f i n i n i j j i n i i i v v x x x w w X y , 1 , 1 1 1 0 ) ( ˆ ∑ ∑ ∑ ∑ = = + = = + + = & & =& − M MOR " , + 2& & = & − 2 " − & " + 2& U = 学習率
21. 各パラメータの学習（SGD) f j k f f i n i n i j j i n i i i v v x x x w w X y , 1 , 1 1 1 0 ) ( ˆ ∑ ∑ ∑ ∑ = = + = = + + = ) ) =) − M MOZ " , + 2O ) = ) − 2 " − ) " + 2O ) ( = 0
22. 各パラメータの学習（SGD) ),. ),. =),. − M MPZ,Q " , + 2P ),. = ),. − 2 " − ),. " + 2P ),. , ( ( ( , , 0 03 = 0 (, ` " = & + ( ) ) + ( ( ) + ( ),. +,. / .01 2 +0)31 2 )01 2 )01 = & + () ) + 2 )01 ( ) ( + ( ),. +,. / .01 2 +0)31 2 )01
23. Factorization MachinesとCTR予測 l 似た広告をクリックしたユーザー同⼠の情報を扱える l 新規のクリエイティブも予測できる l 属性情報を扱える Ø メリット Ø デメリット l 計算量が多い l ユーザーの数、クリエイティブの数の分だけ特徴量が増える（メモリ）