レコメンドシステム—— FM（Factorization Machine）の原理（コード付き）

シーリズの目次

レコメンドシステムのシーリズをここにまとめています。
https://zenn.dev/datasciencekun/articles/dc0f61c0ca7f8d

無料相談コース(未経験OK)

• 機械学習やレコメンド分野に悩んでいる人
• 機械学習やレコメンド分野に携わりたい人

ぜひ下記の無料コースへお申し込みください！
機械学習エンジニア、レコメンドエンジニアになるためのサポート

FM（Factorization Machine）とは？

FMモデルは近年提案されたモデルで、データ量が比較的多く、特徴がまばらな状態でも優れた性能と効果が得られることから、レコメンデーションシステムの領域で広く使われています。

レコメンデーションの世界では、クリック率CTR (click-through rate)とコンバージョン率CVR (conversion rate)が効果を測る2つの重要な指標となります。CTR、CVRを正確に見積もることはトラフィックの価値を高め、レコメンデーションのマッチングを増やすために重要な指針となります。ディープラーニングに加えてCTR/CVRを予測します一般的な手法としては、人工特徴工学+ LR(Logistic Regression)、GBDT(Gradient Boosting Decision Tree) + LR、FM (Factorization Machine)などがあります。

ここでは、FMモデルの実装原理を説明するために、主に原理的に検討します。

FMの公式

FM (Factorization Machine)とは、2010年にKonstanz大学のSteffen Rendle氏(現在はGoogle)が考案した、疎なデータによる特徴の組み合わせ問題を解決するためのものです。FMモデルを一例として導入します。広告分類の質問で、ユーザーと広告スペースに関する特徴から、ユーザーが広告をクリックしたかどうかを予測するとします。ソースデータは以下の通りです。

Clickedはラベルで；Country、Day、Ad_typeが特徴です。3つの特徴はいずれもcategorical型であるため、数値型特徴への変換にはone-hot Encodingが必要である。

上の表からわかるように、ワンホット符号化されたサンプルデータの特徴のほとんどは、かなりまばらです。上の例では、各サンプルは7次元の特徴を持っていますが、平均して3次元の特徴だけがゼロではありません。

実は、これはこのケースだけのことではなく、実際の応用シーンではよくあることです。例えば、CTR/CVR予測の場合、ユーザーの性別、職業、教育レベル、カテゴリー嗜好、商品のカテゴリーなど、ワンホットコード化されたサンプルデータの間引き性が発生します。特に商品カテゴリーというタイプの特徴、例えば商品の下位カテゴリーは約550個で、ワンホットコードを用いて550個の数値特徴が生成されますが、1サンプルあたり550個の特徴のうち、有効なのは1つだけ(ゼロではない)です。このように、間引きは実際の問題では避けられない課題です。

one-hotコードのもう一つの特徴は特徴空間が大きいことです。例えば、商品群が550次元の特徴を持つ場合、一つのcategorical特徴が550次元の数値的特徴に変換され、特徴空間が急増します。

また、大量のサンプルデータを見ると、ある特徴を関連付けることでラベルとの相関性が高まることがわかります。たとえば、「USA」と「Thanksgiving」、「China」と「Chinese New Year」といった関連性は、ユーザーのクリックにプラスの影響を与えます。つまり、「China」から来たユーザーは、「Chinese New Year」では大量の閲覧・購入行動を起こし、「Thanksgiving」では特に消費行動を起こさない可能性が高いということです。この相関特性とラベルとの正の相関は、実際の問題では、「化粧品」商品と「女性」性、「スポーツアクセサリー」商品と「男性」性、「映画チケット」商品と「映画」嗜好など、一般的に見られます。そのため、2つの特徴の組み合わせを取り入れることに意味があります。

多項式モデルは特徴の組み合わせを含む最も直観的なモデルです。多項式モデルの中で，特徴 xiと xj の組み合わせは $x_ix_j$ で表示，つまり $x_i$ と $x_j$ は非ゼロ値になれば，特徴 $x_ix_j$ は有意義です。対照の角度,本文はただ二階の多項式の模型を討論します。モデルの式は次の通りです：

公式1：

その中で，n はサンプルの特徴量，$X_i$ は第 i の特徴の值，$W_0$、$W_i$、$W_{ij}$ はモデルのパラメーターです。

式（1）からわかるように、組み合わせ特徴量のパラメータは合計で $n(n-1)/2$ 個あり、それぞれのパラメータは独立しています。しかし、実際の応用シナリオではデータのスパース性が一般的であるため、2次の項のパラメータトレーニングは非常に難しいです。

その理由は、各パラメータ wij のトレーニングには $x_i$ と $x_j$ が両方非ゼロのサンプルが大量に必要であるためです。サンプルデータが元々スパースであるため、「$x_i$ と $x_j$ が両方非ゼロ」を満たすサンプルは非常に少なくなります。トレーニングサンプルの不足は、繰り返しにパラメータ $W_{ij}$ の不正確さをもたらし、最終的にはモデルの性能に深刻な影響を与える可能性があります。

FM的求解推导

二次項のパラメータトレーニング問題をどのように解決すればよいか？行列分解はこの問題に対するアプローチを提供します。モデルベースの協調フィルタリングでは、評価行列はユーザーマトリックスとアイテムマトリックスに分解でき、各ユーザーとアイテムは潜在的なベクトル表現を持つことができます。

たとえば、以下の図の例では、各ユーザーを2次元ベクトルで表現し、同様に各アイテムも2次元ベクトルで表現し、2つのベクトルの内積が評価行列中のユーザーによるアイテムへの評価を表します。

同様に、すべての二次項のパラメータ $W_{ij}$ は、対称行列 W を構成でき、(説明の便宜のために対角要素を正の実数に設定できます)、したがって、この行列は $W=V^TV$ に分解できます。V の第 j 列は第 j 次元の特徴の潜在ベクトルです。言い換えれば、すべてのパラメータ $W_{ij}$=⟨$V_i$,$V_j$⟩ です。これがFMモデルの中心思想です。したがって、FMのモデル方程式は次のとおりです。

公式2：

ここで、$V_i$ は i 番目の特徴の潜在ベクトルであり、⟨⋅,⋅⟩ はベクトルの内積を表します。潜在ベクトルの長さは k です（k<<n）、k 個の特徴を記述する要因を含みます。式（2）に従えば、二次項のパラメータの数は kn 個に減少し、多項式モデルのパラメータの数よりもはるかに少なくなります。さらに、パラメータのファクタリングにより、$x_hx_i$ のパラメータと $x_ix_j$ のパラメータが相互独立でなくなり、サンプルが疎な場合でも相対的に合理的にFMの二次項パラメータを推定できます。

具体的には、$x_hx_i$ および $x_ix_j$ の係数はそれぞれ ⟨$v_h$,$v_i$⟩ および ⟨$v_i$,$v_j$⟩ であり、それらに共通の要因 $v_i$ が存在します。つまり、「$x_i$ の非ゼロ組み合わせ特徴を含むすべてのサンプル」（ある j≠i が存在し、$x_ix_j$≠0 である場合）は、隠れたベクトル $v_i$ を学習するために使用できます。これにより、データの疎さによる影響が大幅に回避されます。一方、多項式モデルでは、$W_{hi}$ および $W_{ij}$ は互いに独立しています。

明らかなことですが、式（2）は一般的なフィッティング方程式であり、異なる損失関数を使用して回帰、バイナリ分類などの問題を解決するために使用できます。たとえば、回帰問題を解くためにMSE（平均二乗誤差）損失関数を使用することができますし、分類問題を解くためにHinge/Cross-Entropy損失を使用することもできます。

もちろん、バイナリ分類を行う場合、FMの出力はシグモイド変換を経る必要があり、これはロジスティック回帰と同じです。直感的には、FMの計算量は O($kn^2$) です。ただし、式（3）の等式を通じて、FMの二次項は簡略化でき、その計算量を O($kn$) に最適化できます。したがって、FMは新しいサンプルに対して予測を行うのに線形時間で対応できます。

公式3：

SGD（Stochastic Gradient Descent）を使用してモデルをトレーニングする場合、FMのトレーニングの複雑さを再評価します。モデルの各パラメータの勾配は次のようになります。

ここで、$V_{j,f}$ は隠れたベクトル $V_j$ の第 f 番目の要素です。
$Σ^n_{j=1}V_{j,f}X_j$は f に依存するだけであり、i には依存しないため、各イテレーションで
$Σ^n_{j=1}V_{j,f}X_j$の計算を一度だけ行うことで、すべての $V_{i,f}$ の勾配を簡単に取得できます。明らかに、すべての f の $Σ^n_{j=1}V_{j,f}X_j$ の計算量は O($kn$) です。

$Σ^n_{j=1}V_{j,f}X_j$ がわかっている場合、各パラメータの勾配を計算するのは O(1) の複雑さです。勾配を得た後、各パラメータを更新するのは O(1) の複雑さです。モデルのパラメータは合計で $nk+n+1$ 個あります。したがって、FMのパラメータトレーニングの複雑さも O($kn$) です。以上から、FMは線形時間でトレーニングと予測ができる非常に効率的なモデルであることがわかります。

おわりに

FMは非常に柔軟なモデルであり、適切な特徴変換方法を使用することで、二次多項式カーネルのSVMモデル、MFモデル、SVD++モデルなどをシミュレートできます。

SVMの二次多項式カーネルと比較すると、FMはサンプルが疎な場合に優れています。さらに、FMのトレーニング/予測の複雑さは線形です。

MFと比較すると、FMは実質的には特徴 u と i の2つのカテゴリの特徴を持つモデルです。FMでは、ユーザーの購買履歴の平均値、アイテムの購買履歴の平均値など、任意の数の特徴を追加できますが、MFは2つのカテゴリの特徴に制限されています。

コード実例

https://github.com/datasciencekun/starmie/blob/master/recall/factor_machine_demo.ipynb