(cache)Matrix Factorizationの派生アルゴリズムまとめ

本記事は情報検索・検索エンジン Advent Calendar 2019の15日目の記事です。
他の人達の記事がすばらしくてずっと胃が痛かったです。温かい目で見てください。
本記事は、ちょっと検索から離れますが情報推薦の分野からの内容になります。

要約

本記事ではMatrix Factorizationの派生手法をいくつかとりあげて紹介します。

具体的には以下の手法を紹介します。下２つは紹介程度に留めます。

オリジナルのMatrix Factorization(ベース)
ベース+バイアス項
ベース+バイアス項+implicit feedback(SVD++)
Non-negative Matrix factorization(NMF)
regularized single-element-based NMF (RSNMF)
ベース+バイアス項+implicit feedback+時系列処理(timeSVD++)
ベース+バイアス項+implicit feedback+Confidence level

背景

Matrix Factorization(MF)はいわずとしれた推薦システムにおいて重要な手法です。
MFについての解説は他にすばらしい記事があるのでよく知らない人は一読してみてください。

Matrix Factorizationとは

推薦システムにおけるMFの概要とアルゴリズムがわかりやすくまとまっています

Matrix Factorizationとレコメンドと私

MFの概要とアルゴリズムが数式ベースでていねいに解説されています

オリジナルMF

オリジナルの手法はNetFlix Prize優勝者のブログにあります。

先ほど紹介したMatrix FactorizationとはやMatrix Factorizationとレコメンドと私でもこのオリジナルの手法が解説されています。
いま一度確認しておくと、ユーザーインデックスを $u$ , アイテムインデックスを $i$ としてユーザー $u$ のアイテム $i$ への評価 $r_{u i}$ を(1)の式で予測することを考えます(詳細は上の記事を参考にしてください)。ここでは $q_{i}, p_{u}$ はそれぞれアイテム、ユーザーを表す $k$ 次元のベクトルですう。

{\hat{r}}_{u i} = q_{i}^{T} p_{u} (1)

予測値 ${\hat{r}}_{u i}$ がよく当たるように $q_{i}, p_{u}$ を学習していくわけですが、その目的関数が下の(2)式になります。直感的には、正解値と予測値の差を小さくするような関数にノルム正則化項を加えたものになります。 $(u, i) \in K$ はユーザーとアイテムのセット(u,i)が既知として存在するもののみを用いるということを表しています。

目的関数

m i n_{P, Q} \sum_{(u, i) \in K} (r_{u i} - q_{i}^{T} p_{u})^{2} + λ (| | q_{i} | |^{2} + | | p_{u} | |^{2}) (2)

この目的関数の最適解を導くためのアルゴリズムとしてSGDやALSが用いられます。
SGDの場合、目的関数を微分して更新式を導くと(3)式のようになります

更新式

\begin{aligned} e_{u i} = r_{u i} - {\hat{r}}_{u i} \\ q_{i} = q_{i} + γ (e_{u i} p_{u} - λ q_{i}) (3) \\ p_{u} = p_{u} + γ (e_{u i} q_{i} - λ p_{u}) \end{aligned}

並列計算したい場合や行列がスパースでない場合はALSを使うこともありますが基本的にはSGDのほうが計算が早くて扱いやすいです。 $γ$ や $λ$ を $q_{i}$ と $p_{u}$ で変えることもできます。

ちなみにバイスのないこのアルゴリズムがProbabilistic Matrix Factorizationとよばれる手法と同じらしいです。詳細確認していませんが論文だけ載せておきます。
Ruslan Salakhutdinov and Andriy Mnih. Probabilistic matrix factorization. 2008.

ベース+バイアス項

次に、上のオリジナルの手法にバイアス項を加えたものを紹介します。

なぜバイアス項を加える必要があるかを簡単に説明すると、
例えば、ある商品が高評価をつけられやすかったり、あるユーザーが高評価をつけやすかったりする傾向がある時に ${\hat{r}}_{u i} = q_{i}^{T} p_{u}$ だけでは説明できない場合があります。そのために各商品とユーザーにバイアスを設定することでその部分を学習させることができるわけです。

バイアス項は全評価値の平均 $μ$ と各アイテム、各ユーザーのバイアス $b_{i}, b_{u}$ からなっており、バイアス項を加えた予測評価値は以下の(4)式で表されます。

{\hat{r}}_{u i} = μ + b_{i} + b_{u} + q_{i}^{T} p_{u} (4)

目的関数、更新式もそれに応じて以下の(5),(6)式になります。

目的関数

m i n_{P, Q} \sum_{(u, i) \in K} (r_{u i} - μ - b_{i} - b_{u} - q_{i}^{T} p_{u})^{2} + λ (| | q_{i} | |^{2} + | | p_{u} | |^{2} + b_{u}^{2} + b_{i}^{2}) (5)

更新式

\begin{aligned} e_{u i} = r_{u i} - {\hat{r}}_{u i} \\ b_{i} = b_{i} + γ (e_{u i} - λ b_{i}) \\ b_{u} = b_{u} + γ (e_{u i} - λ b_{u}) (6) \\ q_{i} = q_{i} + γ (e_{u i} p_{u} - λ q_{i}) \\ p_{u} = p_{u} + γ (e_{u i} q_{i} - λ p_{u}) \end{aligned}

ベース+バイアス項+implicit feedback(SVD++)

おそらくオリジナルの論文は下のものです。

Yehuda Koren. Factorization meets the neighborhood: a multifaceted collaborative filtering model. 2008.

SVD++は評価行列だけではなくてその他のimplicitな情報をモデルに与える手法です。

この手法は推薦システムにつきものであるコールドスタート問題を解決するというモチベーションで開発されました。MFでスパースな行列が扱えるといっても、すでにあるデータからしか学習できない以上、評価値データがあまりない最初の段階では適切な推薦が行なえません。そこでimplicitな情報、例えば過去の購買履歴であったり閲覧履歴であったりといった情報を与えることでその問題を緩和できるということです。

具体的には、あるユーザー $u$ がimplicitな評価値を与えているアイテム群を $I_{u}$ とします。そして、(k次元)×(アイテム数)のimplicitなアイテム行列 $X$ から $I_{u}$ に含まれるアイテムのベクトルだけを足し合わせたもの $\sum_{j \in I_{u}} x_{j}$ を考えます。k次元ベクトル $x_{j}$ を足し合わせているのでその和もk次元ベクトルとなります。

少しわかりにくいので補足すると $x_{j}$ 自体はアイテムの情報を表すベクトルですが、それをユーザーに関連付けた $I_{u}$ に含まれる分だけ足し合わせているので、 $\sum_{j \in I_{u}} x_{j}$ はユーザーの情報を表すベクトルになります。これを正規化して $p_{u}$ に足すことでimplicitなデータを加えられます( $\sum_{j \in I_{u}} x_{j}$ はユーザーを表すベクトルなので当然足すのは $p_{u}$ )。

よって予測評価値以下の(7)式になります。

{\hat{r}}_{u i} = μ + b_{i} + b_{u} + q_{i}^{T} (p_{u} + | I_{u} |^{- 1 / 2} \sum_{j \in I_{u}} x_{j}) (7)

また、アイテムへの評価値としてユーザー情報を加えるのではなく、ユーザーの属性情報(性別や年齢等)をそのまま加えることもできます。同様にユーザー $u$ が含まれる属性群を $A_{u}$ , その情報を $y_{a}$ とすると属性情報は $\sum_{a \in A_{u}} y_{a}$ となり、これを $p_{u}$ に足すことで予測評価値(8)式を得ます。

{\hat{r}}_{u i} = μ + b_{i} + b_{u} + q_{i}^{T} (p_{u} + | I_{u} |^{- 1 / 2} \sum_{j \in I_{u}} x_{j} + \sum_{a \in A_{u}} y_{a}) (8)

Non-negative Matrix factorization(NMF)

NMFはその名の通りすべての値が非負となるように学習・予測していくアルゴリズムです。だいたい評価値というのは非負である場合が多いため、それに準じて学習するアルゴリズムを開発するのは当然のモチベーションと言えます。

オリジナルの論文は下の論文で、最初は推薦システムの分野ではなく画像生成の分野で生まれました。そもそもこの頃は"Matrix Factorization"という単語は推薦分野では使われていなかったらしいです。最初に紹介したオリジナルのブログが出てから、呼び方が変わっていき、次第にそう呼ばれるようになっていったらしいのですが、この画像生成分野ではすでに1999年からこの単語を使っていますね。

※NMFの原型は1994年の論文にあったらしいのですが、あまり詳しく掘り下げません

Daniel D.Lee and H. Sebastian Seung. Learning the parts of objects by non-negative matrix factorization. 1999

それでは、どのようにしてすべての値を非負となるように学習するのかを見ていきます。

この手法のキモは学習率の調整にあります。

原理的に言って、「最初の値が全て非負」で「更新式に引き算がない」という条件を満たせばすべての値が非負になるように学習されます。そこで、そうなるように学習率 $γ$ を調整します。

更新式(3)を例にします。考え方の理解のためなので厳密な計算ではないですし、オリジナルのNMF手法とも全く異なります。

\begin{aligned} e_{u i} = r_{u i} - {\hat{r}}_{u i} \\ q_{i} = q_{i} + γ (e_{u i} p_{u} - λ q_{i}) (3) \\ p_{u} = p_{u} + γ (e_{u i} q_{i} - λ p_{u}) \end{aligned}

真ん中の式だけ考えてみます。まず代入・展開を行います。

\begin{aligned} q_{i} & = q_{i} + γ r_{u i} p_{u} - γ {\hat{r}}_{u i} p_{u} - γ λ q_{i} \\ = q_{i} + γ r_{u i} p_{u} - γ ({\hat{r}}_{u i} p_{u} + λ q_{i}) \end{aligned}

この更新式から引き算をなくしたいので、

γ = \frac{q_{i}}{{\hat{r}}_{u i} p_{u} + λ q_{i}}

とすると、以下の(9)式のようになり、更新式から引き算が消えます。 $p_{u}$ も同様です。

q_{i} = q_{i} \frac{p_{u} r_{u i}}{{\hat{r}}_{u i} p_{u} + λ q_{i}} (9)

regularized single-element-based NMF (RSNMF)

以下の論文を参考にしてみてください。特殊な権限がないと見れないかもしれませんが。

Xin Luo, Mengchu Zhou, Yunni Xia, Qingsheng Zhu. An Efficient Non-Negative Matrix-Factorization-Based Approach to Collaborative Filtering for Recommender Systems. 2014

オリジナルのNMFとの違いは以下の２点です。

single-element-based
Tikhonov(チコノフ) 正則化

single-element-based

オリジナルのNMFは画像生成分野で生まれたため、データのスパーシティを考慮されていませんでした。そのため、推薦分野でそのまま使ってもうまくいかないので改良が必要です。つまり、オリジナルでは行列のすべての要素を対象に更新式を構築していたものを、データのあるものに限定して更新式を組み直す必要があります。

Tikhonov(チコノフ) 正則化

これは今まで見てきたノルム正則化項( $| | q_{i} | |^{2}$ )のようなものです。これを入れることで、計算効率を落とすことなく精度を上げることに成功しました。

更新式

p_{u} = p_{u} \frac{\sum_{i \in I_{u}} q_{i} r_{u i}}{\sum_{i \in I_{u}} q_{i} {\hat{r}}_{u i} + λ_{u} | I_{u} | p_{u}} q_{i} = q_{i} \frac{\sum_{u \in U_{i}} p_{p} r_{u i}}{\sum_{u \in U_{i}} p_{u} {\hat{r}}_{u i} + λ_{i} | U_{i} | q_{i}}

ベンチマーク

ここまでいくつかアルゴリズムを見てきて、じゃあいったいこの中でどれが良いのと思われた方もいるかもしれません。
SurpriseというMatrix Factorization向けのライブラリにMovieLensのデータを使ってのベンチマークがあります。SVDというのがバイアス項を加えたMFで、NMFがRSNMFの結果です。SVD++が１番精度が良いのですが、計算時間が非常に長いのが分かるかと思います。

ベース+バイアス項+implicit feeadback+時系列処理(timeSVD++)

ここから２つの手法はあまり詳細に触れません。知りたい方は論文を参照してください。今後詳細に解説する記事がかけたら載せたいです。

オリジナルの論文

Yehuda Koren. Collaborative Filtering with Temporal Dynamics. 2009

この手法はユーザーの好みとかアイテムの評価とかって時間によって変わるよねという当たり前かつ重要な考えが基になっています。最近ではDeepな時系列モデルがそのへんを優秀に解いているらしいですが...。

最初に、どの変数が時間によって変化するかを考えます。

$b_{i}$ はアイテムの評価される傾向(高評価されやすい等)を表しているので、これは時間によって変わります
$b_{u}$ はユーザーの評価する傾向(高評価しやすい等)を表しているので、これは時間によって変わります
$p_{u}$ はユーザーアイテム間の相互作用におけるユーザーの好みを表しているので、これは時間によって変わります
$q_{i}$ はアイテムの性質を表しているので、これは時間によって変わりません

よって、導かれる結論として、予測評価値は(10)式で表されます

{\hat{r}}_{u i} = μ + b_{i} (t) + b_{u} (t) + q_{i}^{T} p_{u} (t) (10)

これらを時間の関数としてどう表していくのかという問題に移ります。

アイテムバイアス $b_{i}$

まず、アイテムバイアス $b_{i}$ はそれほど短期間で変わらないと考えられるため、単純にある程度の期間で分割してその平均を考慮すればよいとします。実際の予測ケース想定すると、レコメンドするそのタイミングから過去n日の平均を取るみたいなことなのかなと思います。式にすると(11)式のようになります。

b_{i} (t) = b_{i} + b_{i, B i n (t)} (11)

ユーザーバイアス $b_{u}$ , ユーザーの好み $p_{u}$

次に、ユーザーバイアス $b_{u}$ は短期間で変化することがあるため少し工夫します。手法が3つ紹介されていて、実験的にはスプライン補間+single day effectが最も良い精度が出ています。

単純な線形補間
- $b_{u} (t) = b_{u} + | ある基準時間から今までの時間間隔 |^{β} \times α_{u}$ として $b_{u}, α_{u}$ を学習していきます
スプライン補間
- スプラインによる補間
- $b_{u} (t) = b_{U} + \frac{\sum_{l} e^{- γ | t - t_{l} |} b_{t_{l}^{u}}^{u}}{\sum_{l} e^{- γ | t - t_{l} |}}$
Single day effect
- その日限りの爆発的な傾向というのを考慮するため、上の補間に加えてあるユーザーのその日のみのバイアス $b_{u, t}$ を加えます

ユーザーの好み $p_{u}$ も $b_{u}$ と同じで補間+single day effectで時間の関数化をしています。

実験結果を見ると、従来手法と比べてかなり良い結果が出ています

ベース+バイアス項+implicit feedback+Confidence level

オリジナル論文

Yifan Hu, Yehuda Koren, Chris Volinsky, Collaborative Filtering for Implicit Feedback Datasets, 2008.

すべての評価情報が等価ではないという考えのもと開発された手法です。

ユーザーの行動傾向等からデータごとにConfidence levelを測るConfidence functionを学習します。
そのConfidence levelに合わせてデータを重み付けするような形で学習を進めていくことで、データの重要度を考慮したモデルが作成できるという発想です。

最後に

オリジナルのMatrix Factorizationを解説したものは多いのですが、その派生形をとりあげたものがあまりなかったので今回まとめてみました。

近年はDeepなモデルでの推薦がもっぱら研究対象ですが、RecSys2019のBest Paperでも取り上げられたようにDeepなモデルばかりが優れているとは限らないのでこのへんのアルゴリズムもおさえておきたいです。

このへんの実装もおいおい書きます。

Reference

https://qiita.com/michi_wkwk/items/52660778ad6a900965ee

https://qiita.com/ysekky/items/c81ff24da0390a74fc6c

https://github.com/NicolasHug/Surprise

https://sifter.org/~simon/journal/20061211.html

Ruslan Salakhutdinov and Andriy Mnih. Probabilistic matrix factorization. 2008.

Yehuda Koren. Factorization meets the neighborhood: a multifaceted collaborative filtering model. 2008.

Daniel D.Lee and H. Sebastian Seung. Learning the parts of objects by non-negative matrix factorization. 1999

Xin Luo, Mengchu Zhou, Yunni Xia, Qingsheng Zhu. An Efficient Non-Negative Matrix-Factorization-Based Approach to Collaborative Filtering for Recommender Systems. 2014

Yehuda Koren. Collaborative Filtering with Temporal Dynamics. 2009

Yifan Hu, Yehuda Koren, Chris Volinsky, Collaborative Filtering for Implicit Feedback Datasets, 2008.

SVD++, time SVD++, ConfidenceSVDを開発したYehuda Koren氏のまとめ記事↓
https://datajobs.com/data-science-repo/Recommender-Systems-[Netflix].pdf