畳庵〜tatamiya practice〜

機械学習・統計モデリング練習帳。読書・source code読みの記録や,実装など。

User, Itemメタ情報を埋め込んだレコメンドアルゴリズムLightFM詳解

本記事では,LightFM(Kula, 2015)というレコメンドアルゴリズムについて,論文とGitHubの実装を読んで筆者が得た理解に基づき解説します。

arxiv.org

github.com

前回,前々回と,行列分解ベースのレコメンド手法に関する話題で記事を書きました:

tatamiya-practice.hatenablog.com

tatamiya-practice.hatenablog.com

こちらの手法ではUserのItemに対する評価履歴を行列で表し因子分解しました。

それに対しLightFMではその枠組みを拡張し,各分解要素をUser / Itemメタ情報の線型式でモデリングします。

導入:Matrix Factorizationからの流れ

Matrix Factorizationの復習

User数が M,Item数が Nであるとします。

前回の記事で扱ったMatrix Factorizationと呼ばれる手法は,各Userの各Itemに対する評価を表す M \times NのUser-Item行列 R_{u, i}を因子分解するものでした。

いくつかバリエーションはありますが,代表的なものは以下のように表されます。*1

 \tilde{r}_{u,i}=b^{U} _{u}+b^{I} _{i} + \sum_k^{d} P_{u, k} Q_{k, i}

f:id:tatamiyatamiyatatatamiya:20200321145540p:plain

 b^{U}, b^{I}は,バイアス項といって,User, Itemごとの平均的な評価を表すベクトルです。*2

一方で, P, Qはそれぞれ (M \times d),  (d \times N)の行列で,UserとItemの評価傾向を d次元に圧縮したものです。

 dはハイパーパラメータですが,商品のカテゴリ数のような特徴を表していると解釈されることもあります。

Matrix Factorizationの限界とコールドスタート問題

Matrix Factorizationを含むUser-Item行列に基づく協調フィルタリングと呼ばれる一連の手法に共通する問題点として,コールドスタート問題が挙げられます。

過去のUser, Item評価履歴に基づきモデルが作られるため,新しいUser, Itemに対しては,データが貯まるまでうまくレコメンドが行えないのです。

これの点を克服するために,User, Itemのプロフィールやジャンルといったメタ情報をモデルに組み込む改良手法が開発されました。

その中の一つが,今回紹介するLightFMです。

LightFM

アルゴリズム

LightMFは,上掲のMatrix Factorizationにおけるbias項 b^{U}, b^{I}と行列分解項 P^{U}, Q^{I}を,User, Itemのメタ情報行列 F^{U}, F^{I}の線型関数として表現したものです。

 b _u^{U} = \sum _s^{S^{U}} F^{U}_{u, s}c^{U}_s, \quad b _i^{I} = \sum _s ^{S^{I}}c^{I}_s F^{I}_{s, i}

 P_{u, k} = \sum _s ^{S^{U}} F^{U}_{u, s}e^{U}_{s, k}, \quad Q_{k, i} = \sum _s ^{S^{I}}e^{I}_{k, s} F^{I}_{s, i}

f:id:tatamiyatamiyatatatamiya:20200321145620p:plain

User, Itemそれぞれに S^{U}, S^{I}個のメタ情報が与えられているとすると,メタ情報行列 F^{U}, F^{I}はそれぞれ (M \times S^{U}), (S^{I} \times N)の大きさを持つことになります。

メタ情報行列にかかる係数 c^{U}, c^{I}, e^{U}, e^{I}は,論文および実装中ではfeature embeddingsとして呼ばれています。特に e^{U}, e^{I}はそれぞれ (S^{U} \times d), (d\times S^{I})の大きさを持っていて,各属性を低次元空間に埋め込んだ形になっています。

モデルパラメータ推定方法

Matrix Factorizationではbiasベクトル b^{U}, b^{I}と分解した行列 P, Qの各要素の合計 M+N+M\times d + N \times d = (M + N)(d+1)個パラメータがあり,これらを確率勾配降下法(SGD)で求めていました。

一方LightFMでは,代わりに c^{U}, c^{I}, e^{U}, e^{I}の各要素がモデルパラメータとなり,合計 (S^{U}+S^{I})(d+1)個を同じくSGDにて求めます。

特に購買や閲覧の有無を二値分類で当てるシチュエーションでは, モデルの出力値 \tilde{r}_{u, i}にロジスティック関数 \sigma(x) = 1/ (1+e^{-x})をかませて確率として表現し,下記の対数尤度を最大化するように学習を行います。

 \log L(c^{U}, c^{I}, e^{U}, e^{I}) = \sum_{u=1} ^{M}\sum_{i=1} ^{N} R_{u, i} \log \sigma(\tilde{r} _{u, i})+ \sum_{u=1} ^{M}\sum_{i=1} ^{N} (1-R_{u, i}) \log \{1 -  \sigma(\tilde{r} _{u, i})\}

具体的には,下記のようなルールでパラメータを更新していきます(ハイパーパラメータ \etaは学習率):

 c^{U}_s \leftarrow c^{U}_s + \eta F^{U}_{u, s} \{ R_{u, i} - \sigma(\tilde{r} _{u, i}) \}

 c^{I}_s \leftarrow c^{I}_s + \eta  F^{I}_{s, i} \{ R_{u, i} - \sigma(\tilde{r} _{u, i}) \}

 e^{U}_{s, k} \leftarrow e^{U}_{s, k} + \eta   F^{U}_{u, s} Q_{k, i} \{ R_{u, i} - \sigma(\tilde{r} _{u, i}) \}

 e^{I}_{k, s} \leftarrow e^{I}_{k, s} + \eta F^{I}_{s, i}  P_{u, k} \{ R_{u, i} - \sigma(\tilde{r} _{u, i}) \}

導出方法の詳細は,本稿末にて補足します。

関連手法

Matrix Factorizationとの対応

メタ情報行列 F^{U}, F^{I}の代わりにそれぞれ M\times M, N\times N単位行列を代入した場合,上記アルゴリズムはMatrix Factorizationと完全に一致します。

GitHubで公開されているPythonライブラリlightfmでは,メタ情報を入力しない場合はこちらの設定が適用されます。

Factorization Machinesとの関係

メタ情報を取り入れたレコメンドアルゴリズムとしては,Factorization Machines(S. Rendle, 2010)が先にあり,派生手法含めてde facto standardとなっています。

LightFMは名前にFMとつくことからFactorization Machinesの改良版のように思えてしまいますが,実際はそういうわけではなく, 行列分解に基づく・メタ情報を予測に用いるといった類似点から"FM"とつけたとのことです。

Lightとつくと勾配ブースティング木におけるLightGBMのような,ベースとなるアルゴリズムほぼそのままの軽量実装版,というものを想像してしまいますが,そのような関係ではなさそうです。

ただ,全く関係がないわけではなく,一応Factorization Machinesのモデルパラメータを制限した特殊形と解釈することもできます。

詳細はまたの機会とさせていただきますが,LightFMよりFactorizationの方が多くの種類の交互作用をモデルに取り入れることができます。

LightFMではUserメタ情報とItemメタ情報の交互作用しか入りませんが, Factorization MachinesではUserとUser/Itemメタ情報の交互作用,異なるUserメタ情報同士の交互作用といったものも含めることができます。

例えば,映画の評価数値をもとにレコメンドを行う際,Userメタ情報として性別と居住地,Itemメタ情報としてジャンルを入れるとします。

このとき,Factorization Machinesでは

  • UserとUser/Itemメタ情報の交互作用
    • 例:ある特定のユーザーについては,コメディ映画の予測評価を高めに出す
  • 異なるUserメタ情報同士の交互作用
    • 例:都心部に住む女性には対しては予測評価を高めに出す

といった効果も含めることができると考えられます。

また,bias項についてもUser/Itemメタ情報に依存する項と依存しない項の両方が入るようになります。

おわりに

MF × LightFM = FM

LightFMは,Matrix Factorizationのパラメータをメタ情報に依存させた拡張版として理解できました。

一方で名前にFMとついてはいるものの,Factorization Machinesから見ると単純な軽量実装版というより交互作用を制限した特殊形という関係にありました。

ちなみにMatrix FactorizationもFactorization Machinesの交互作用をUser×Itemのみに制限した特殊形として見られるので,ある意味

 Matrix Factorization × LightFM = Factorization Machines

とも言えなくはなさそうです。

今回触れられなかったこと

アルゴリズム間の性能比較】

本稿ではアルゴリズムの数理的な解説をメインに行いましたが,実際の性能についても別の機会に共通のデータセットを使って比較実験を行ってみたいと思います。

正則化項の入れ方】

Matrix Factorizationでは,bias項や分解後の行列成分が大きくなりすぎないように L^{2}正則化項を加えることも一般的に行われます。

LightFMについても,Pythonライブラリ上では正則化係数(user_alpha, item_alpha)を加えるオプションが存在します。ただ,これらがどのように学習に効いているかぱっと見でよくわからなかったため,今回は解説から外しました。

こちらについても改めて記事にできたらと考えております。

補足:SGDにおけるパラメータ更新式の導出

User-Item行列が,購買や閲覧の有無を0, 1で表したものであるとします。

この時,モデルの出力値 \tilde{r}_{u, i}にロジスティック関数 1/(1+e^{-x})を噛ませることで予測購買率/閲覧率を出すとすると,その時の尤度は以下のように書けます:

尤度

 L(c^{U}, c^{I}, e^{U}, e^{I}) = \prod_{u=1} ^{M}\prod_{i=1} ^{N} \sigma(\tilde{r} _{u, i})^{R_{u, i} } \{1 -  \sigma(\tilde{r} _{u, i})\} ^{1-R_{u, i}} .

パラメータを更新する際には,これを最大化させます。

ただし,尤度そのままは扱いづらいので,対数をとります:

対数尤度

 \log L(c^{U}, c^{I}, e^{U}, e^{I}) = \sum_{u=1} ^{M}\sum_{i=1} ^{N} R_{u, i} \log \sigma(\tilde{r} _{u, i})+ \sum_{u=1} ^{M}\sum_{i=1} ^{N} (1-R_{u, i}) \log \{1 -  \sigma(\tilde{r} _{u, i})\}.

ここで仮にパラメータ xを更新する場合,

 x \leftarrow x + \eta  \frac{\partial \log L}{\partial x}

のように行います。

対数誤差の変数 xによる微分ですが,こちらは以下のように書けます:

 \frac{\partial \log L}{\partial x} = \sum_{u=1} ^{M} \sum_{i=1} ^{N} \frac{\partial \tilde{r} _{u, i}}{\partial x} \{ R_{u, i} - \sigma(\tilde{r} _{u, i}) \}.

ここで \frac{\partial \tilde{r} _{u, i}}{\partial x}の部分をどう求めるかですが,

 \tilde{r} _{u, i} = \sum _s F^{U}_{u, s}c^{U}_s +  \sum _s c^{I}_s F^{I}_{s, i} + \sum _{k=1}^{d} \left\{ \sum _s F^{U}_{u, s}e^{U}_{s, k}\right\}\left\{\sum _s e^{I}_{k, s} F^{I}_{s, i} \right\}

と書き表わせることを思い出し,

 \frac{\partial \tilde{r} _{u, i}}{\partial c^{U}_s} = F^{U}_{u, s}, \quad \frac{\partial \tilde{r} _{u, i}}{\partial c^{I}_s} = F^{I}_{s, i}

 \frac{\partial \tilde{r} _{u, i}}{\partial e^{U}_{s, k}} = F^{U}_{u, s} Q_{k, i}, \quad \frac{\partial \tilde{r} _{u, i}}{\partial e^{I}_{k, s}} = P_{u, k} F^{I}_{s, i}

となります。

以上をまとめると,以下のようにパラメータ更新をしていくことになります:

 c^{U}_s \leftarrow c^{U}_s + \eta \sum_{u=1} ^{M} F^{U}_{u, s} \sum_{i=1} ^{N} \{ R_{u, i} - \sigma(\tilde{r} _{u, i}) \}

 c^{I}_s \leftarrow c^{I}_s + \eta  \sum_{i=1} ^{N} F^{I}_{s, i} \sum_{u=1} ^{M}\{ R_{u, i} - \sigma(\tilde{r} _{u, i}) \}

 e^{U}_{s, k} \leftarrow e^{U}_{s, k} + \eta \sum_{u=1} ^{M}  F^{U}_{u, s} \sum_{i=1} ^{N} Q_{k, i} \{ R_{u, i} - \sigma(\tilde{r} _{u, i}) \}

 e^{I}_{k, s} \leftarrow e^{I}_{k, s} + \eta \sum_{i=1} ^{N}F^{I}_{s, i} \sum_{u=1} ^{M}  P_{u, k} \{ R_{u, i} - \sigma(\tilde{r} _{u, i}) \}

上記では  \sum_{i=1}  \sum_{u=1} ^{M} の範囲で和を取っていますが,メタ情報行列は大抵疎なので F^{U}, F^{I}の要素が0でない部分のみ計算すれば良いことになります。

さらに,User-Item行列 R_{u, i}についてもnon-zero要素のみを使って学習を行い,値が0の要素=未評価の部分は学習から外します。

この時,SGDでは R_{u, i}のnon-zero要素を一つ一つランダムに取り出して u, iを固定しながらパラメータ更新を行なっていきます。そして,全non-zero要素分学習を回したら1 epochとカウントします。

*1:https://datajobs.com/data-science-repo/Recommender-Systems-[Netflix].pdf

*2:この他に, \muというUser, Item合わせた全体の平均的な評価を表す項が入ることもあります。