重みつき行列分解
次に、SVDとは異なる行列分解手法である「重み付き行列分解（Weighted Matrix Factorization、以下WMF）」を紹介します。これは別名で暗黙的交互最小二乗法（Implicit Alternating Least Squares、以下iALS）とも呼ばれる手法であり、SVDと違った次のような前提があります。
- \(R_{ui}=1\)となっている組み合わせは実際に接触があった組なので、\(u\)の\(i\)に対する評価は高く、スコア値\(s_{ui}=\vec{p}_{u} \cdot \vec{q}_i\)は自信をもって\(1\)に近いと言えるだろう
- 一方、\(R_{ui}=0\)である組み合わせについては、対象のデータは「暗黙的フィードバック」に基づくものであるため、\(u\)の\(i\)に対する評価が低いのか、それとも単にまだ\(i\)について知らないのかを区別できず、接触があった場合と比較して自信をもって \(s_{ui}\) が \(0\)に近いはずである、とは言えない。
この考え方を反映する誤差関数として、論文"Collaborative Filtering for Implicit Feedback Datasets"で導入されたのが、次の誤差関数です。
\(L_{ \mathrm{WMF}}\)=\( \sum_{u=1} ^ U \sum_{i=1} ^ I c_{ui} (R_{ui} - \vec{p}_{u} \cdot \vec{q}_i) ^2\)
この誤差関数は、ユーザー／アイテムの間に接触があるかどうか（\(R_{ui}\)の値が0か1のどちらか）によって、誤差の重み付けを変えることで、接触がないケースよりも接触があるケースを重視するように考える誤差関数です。ここで新たに導入された係数 \(c_{ui}\) は「confidence scaling」と呼ばれます。通常この\(c_{ui}\)は、接触がある場合の重みを高くするために\(\alpha \ge 0\)をパラメータとして、次のように設定します。
仮に\(\alpha=0\)ならば、全ての\(c_{ui}=1\)ですので、誤差関数はSVDの場合と同じものとなり、接触の有無によって誤差関数の重み付けは変わりません。\(\alpha=0\)ではないケースとして、例えば\(\alpha=9\)の場合を考えてみましょう。ユーザー\(u=1\)がアイテム\(1\)とは接触したけれども、アイテム\(2\),\(3\),\(\cdots\)とは接触していない状況を考えましょう。すると、誤差関数のユーザー\(1\)に関する部分は
\(10 (1 - \vec{p}_1 \cdot \vec{q}_1)^2 + (0 - \vec{p}_1 \cdot \vec{q}_2) ^2 + (0 - \vec{p}_1 \cdot \vec{q}_3) ^2 + \cdots\)
となります。この状況では、接触のある組み合わせに対応するスコア\(\vec{p}_1 \cdot \vec{q}_1\)を1に近づける方が、接触のない組み合わせに対応するスコア\(\vec{p}_1 \cdot \vec{q}_2\)を0に近づける方よりも、より誤差関数を小さくすることができます。
例えば、
\(R=\left(\begin{array}{ccc}1 & 0 & 0 \\1 & 1 & 0 \\0 & 1 & 1\end{array}\right)\)
という行列を考えると、\(n=2\),\(\alpha=0\) (SVD)の場合
\(S_{\alpha=0}=\left(\begin{array}{ccc} 0.892 & 0.193 & -0.241 \\ 1.086 & 0.844 & 0.193 \\-0.047 & 1.086 & 0.892\end{array}\right)\)
になりますが、\(\alpha=9\) を用いた場合は
\(S_{\alpha=9}=\left(\begin{array}{ccc} 0.981 & 0.285 & -0.316 \\1.016 & 0.974 & 0.285 \\-0.108 & 1.016 & 0.981\end{array}\right)\)
が誤差関数を最小化する \(\vec{p}\)、\(\vec{q}\) に対応するスコア行列\(S=P Q^T\)になります。\(S_{\alpha=9} \)は、
- \(R\)が\(1\)の場所では\(S_{\alpha=0} \)より1に近く
- \(R\)が\(0\)の場所では\(S_{\alpha=0} \)より外れている
ことが分かり、狙いが達成されていることがわかります。
\(P\)、 \(Q\)の導出
大規模な問題にWMFを適用する場合は、数値的な安定性の担保と過学習の回避のために誤差関数に正則化項（パラメータが学習データに過剰に適合するのを抑制し、学習に用いなかったデータに対しても一定の性能を担保するための項）を付け加え、
\(L_{\mathrm{WMF, reg}} = \sum_{u=1}^U \sum_{i=1} ^I c_{ui}(R_{ui} - \vec{p}_{u} \cdot \vec{q}_i) ^2 + \lambda \left(\sum _{u=1} ^U | \vec{p}_u | ^2 + \sum _{i=1} ^I | \vec{q}_i | ^2\right)\)
という関数を用います。SVDはWMFで\(\alpha=\lambda=0\)という特殊な誤差関数を用いていたことになります。\(\sum_{u=1}^U \sum_{i=1}^I\)は純粋に算出するユーザーとアイテムの全組み合わせについての和になり、対象は膨大になりますが、上述の原論文ではこの和を効率的に計算する方法が述べられています。
\(\alpha\), \(\lambda >0\)の場合の\(P\)、\(Q\) の導出は容易ではありませんが、交互最小二乗法というポピュラーな方法によって近似解を得ることができます。この方法では、 \(\vec{p}_i\)、\(\vec{q}_i\)を乱数で初期化した後
- \(\vec{q}_i\)を（全ての\(i\)について）固定し、\(\vec{p}_u\)のみを動かして誤差関数を最小化する
- \(\vec{p}_u\)を（全ての\(u\)について）固定し、\(\vec{q}_i\)のみを動かして誤差関数を最小化する
という操作を 1, 2, 1, 2, ... と交互に一定回数\(N_{\mathrm{epoch}}\)繰り返すことで近似的な最適解を得ます。
この計算コストについていくつかコメントをしますと、各々の繰り返しで行われる1.の\(\vec{p}_u\)についての最適化は、異なる\(u\)に関して独立に行うことができるため、複数の\(u\)について並列に計算することが可能で、並列化によって計算スピードを高めることができます。2.の\(\vec{q}_i\)についても\(i\)について並列な最小化が可能です。
一方、1.で各々の\(u\)についての最小化は比較的高コストであり、\(n\)を次元数、\(N_u\)を\(R_{ui}=1\)となるアイテム\(i\)の数（\(u\) が接触したアイテム数）として、原論文のコレスキー分解を用いる方法では\(O(N_u n^2 + n^3)\)、共役勾配法を用いた近似的な方法では\(O(N_u n + n^2)\)のコストを要します。アイテム\(i\) についても同様に、\(i\)と接触したユーザー数\(N_i\)を用いて、コレスキー分解では\(O(N_u n^2 + n^3)\)、共役勾配法で\(O(N_u n + n^2)\)のコストが生じます。\(n\)が大きい時には共役勾配法の方が圧倒的に省コストとなります。
まとめると、WMFには\(n\), \(\alpha\), \(\lambda\)、\(N_{\mathrm{epoch}}\)というパラメータが存在することになり、これらのパラメータの最適な値は交差検証によって決める必要があります。アルゴリズムの繰り返し回数\(N_{\mathrm{epoch}}\)は、繰り返しの度にその時点での精度を計測し、もし精度が下がり始めたら見切りをつけて終了するというアプローチが精度的にも学習時間的にも大変実用的です。このアプローチは早期終了（early stopping)と呼ばれます。
ここまで紹介した一部のアルゴリズムについても、結局それらのうちのどのアルゴリズムを利用すればよいか分からないと読者の皆さんは考えるかもしれません。参考までに、紹介した行列分解の手法からどれを選べば良いか考える際の選択基準として、利用現場での適用経験を踏まえた筆者の選択基準を紹介しておきます。
- WMF（iALS）が多くのケースで最も高い精度となるため、どのようなデータであっても WMF（iALS）は試す。この時、後述するパラメータ\(n\), \(\alpha\), \(\lambda\), \(N_{\mathrm{epoch}} \)の値は必ず交差検証によって適切にチューニングする（ハイパーパラメータ最適化ツール「optuna」などを用いれば多くの場合、適切にチューニングすることができる）
- 余力があれば次回以降で紹介するBPRというアルゴリズム（接触しなかったアイテムより接触したアイテムを重視するように学習する行列分解手法）も試すべきだが、パラメータチューニングがWMFと比べて若干不安定なところがある。
- ここで紹介したもの以外にもいくつかアルゴリズムが存在し、非負値行列分解（Nonnegative matrix factorization）は特によく用いられるが、多くの場合 WMF よりも精度が劣る。
