一歩Matrix Factorization、二歩Factorization Machines、三歩Field-aware Factorization Machines…『分解、三段突き！！』

　こんにちは、k_oomoriです。最近、機械学習の分野でFactorization Machines (FM)という手法があることを知りました。Matrix Factorization (MF)は知っていたのですが、共にfactorizationという単語を含んでいるため、何か関係があるのだろうか？と気になり調べてみました。
　ここではサンプルデータとしてFactorization Machinesの論文で使われていたものを使用します。

	タイタニック (TI)	ノッティングヒルの恋人 (NH)	スターウォーズ (SW)	スタートレック (ST)
Alice (A)	5	3	1
Alice (A)	2010-1	2010-2	2010-4
Bob (B)			4	5
Bob (B)			2009-5	2009-8
Charlie (C)	1		5
Charlie (C)	2009-9		2009-12

表1. 映画に対する評価
Alice, Bob, Charlieの3人が4本の映画作品に対して評価をしたものです。上段が評価値、下段が評価を行った年月を表します。また空欄は未評価であることを示しています。問題設定としては、この未評価の部分を推定し、高評価になりそうな作品を推薦(レコメンド)したいとします。

Matrix Factorization (MF)

　MFにおいては、表1の人 $\times$ 作品の評価値の情報を次のような行列に対応付けます。
$V=\left(\begin{array}{cccc} 5&3&1& \\ & &4&5\\ 1& &5& \end{array}\right) \tag{1}$
そしてこれを2つの行列の積 $V=WH$ として再現しようとします。
$\left(\begin{array}{cccc} 5&3&1& \\ & &4&5\\ 1& &5& \end{array}\right) = \overbrace{ \left(\begin{array}{cc} \ast&\ast\\ \ast&\ast\\ \ast&\ast \end{array}\right) }^{W} \overbrace{ \left(\begin{array}{cccc} \ast&\ast&\ast&\ast\\ \ast&\ast&\ast&\ast \end{array}\right) }^{H} \tag{2}$
$W$ の列数 $=H$ の行数 $\equiv r$ は与えられたデータからは決まらず、モデルの形を決めるパラメータ、即ちハイパーパラメータになります。
　ここで見方を少し変えて、 $W$ という行列を横ベクトルが人数分縦に並んだもの、 $H$ を縦ベクトルが作品数分横に並んだものと考えると
$W=\left(\begin{array}{c} \vec{v}_A^T\\ \vec{v}_B^T\\ \vec{v}_C^T \end{array}\right)=(\begin{array}{ccc}\vec{v}_A & \vec{v}_B & \vec{v}_C\end{array})^T, \quad H=\left(\begin{array}{cccc} \vec{v}_{TI} & \vec{v}_{NH} & \vec{v}_{SW} & \vec{v}_{ST} \end{array}\right) \tag{3}$
となります。ここで各 $\vec{v}_i$ は $r$ 次元の特徴空間内の特徴ベクトルとみなすことができます。つまり $\vec{v}_A$ はAliceの特徴(趣味趣向)を表すベクトルであり、 $\vec{v}_{TI}$ はタイタニックという作品の特徴を表しているというふうに考えることにします。すると $W$ と $H$ の積は
$WH=\left(\begin{array}{cccc} \vec{v}_A\cdot\vec{v}_{TI} & \vec{v}_A\cdot\vec{v}_{NH} & \vec{v}_A\cdot\vec{v}_{SW} & \vec{v}_A\cdot\vec{v}_{ST}\\ \vec{v}_B\cdot\vec{v}_{TI} & \vec{v}_B\cdot\vec{v}_{NH} & \vec{v}_B\cdot\vec{v}_{SW} & \vec{v}_B\cdot\vec{v}_{ST}\\ \vec{v}_C\cdot\vec{v}_{TI} & \vec{v}_C\cdot\vec{v}_{NH} & \vec{v}_C\cdot\vec{v}_{SW} & \vec{v}_C\cdot\vec{v}_{ST} \end{array}\right) \tag{4}$
となります。ここで $\vec{v}\cdot\vec{w}$ はベクトル $\vec{v}$ と $\vec{w}$ の内積(ドット積) $\displaystyle\sum_{f=1}^r v_fw_f$ を表し、行列記法の $\vec{v}^T\vec{w}$ と等価です。式(4)を(2)と比較し、すでに埋まっている部分を合わせるように、つまりできるだけ $\vec{v}_A\cdot\vec{v}_{TI}=5, \vec{v}_A\cdot\vec{v}_{NH}=3, \ldots, \vec{v}_C\cdot\vec{v}_{SW}=5$ を再現するように特徴ベクトルの値を決めることができれば、未評価の部分、例えばAliceがスタートレックを見たときの評価点の推定値を
$\displaystyle \hat{V}_{A-ST}=\vec{v}_A\cdot\vec{v}_{ST}=\sum_{f=1}^r v_{Af}v_{STf} \tag{5}$
として求めることができます。このように未評価部分を計算によって求め、その値が高いものを取り出すことによってレコメンデーションができるようになります。
　今回の例は3人 $\times$ 4作品=12点のうち7点がすでに埋まっているというそれなりに密(dense)なデータですが、人と作品の数が多くて実際の評価点が少ない疎(sparse)なデータに対しても特徴次元を低く抑えつつうまく学習することができれば、良い推定値を求めることができる可能性があります。
　以上がMatrix Factorizationの基本的な考え方ですが、MFにはいくつかの発展形がありますのでそれを簡単に紹介しましょう。

バイアス項付きMatrix Factorization

　上記の例ではあらゆる特徴を行列 $W,H$ の中に押し込めましたが、人または作品片方にしか依存しない性質、つまり評価が全体的に辛口/甘口な人であるとか、誰もが高い/低い評価を与える作品といったものがあるかもしれません。それらを別パラメータとして抜き出し、そこからの逸脱を行列分解として表現したものがバイアス項付きのMatrix Factorizationです。例としてBobのタイタニックに対する評価予測値は、全体の平均を $\mu$ 、Bobの評価バイアスを $w_B$ 、タイタニックの評価バイアスを $w_{TI}$ とすると
$\hat{V}_{B-TI}=\mu + w_B + w_{TI} + \vec{v}_B\cdot\vec{v}_{TI} \tag{6}$
と表されることになります。

Non-negative Matrix Factorization (NMF)

　与えられた $V$ の要素の中に負の値が一つもない場合、分解後の $W$ と $H$ の要素も全て非負にせよという制約を置くことができます。これをNon-negative Matrix Factorization (NMF)といいます。なぜこれがより良い結果を導くかという直感的な説明としては、

特徴ベクトルの成分の中に不用意に大きな値があったとする
→全ての要素が0以上のため後からマイナスの値で打ち消すことができない
→最適化するにはどうしても慎重にならざるを得ない

ということで、罰則項による正則化に似た効果があるからではないかと、筆者個人としては解釈しています。(NMFについては過去に別の記事を書いていますので興味があればそちらもご参照ください。)

Tensor Factorization

　これまでの例は人と作品という2軸のみを考えていましたが、問題設定によってはより多くの軸があり得ます。一例としてWeb広告の配信効果測定は一般に人 $\times$ 広告枠(メディアサイト) $\times$ 配信広告という3軸で行われます。従って $i$ という人が $s$ というサイトを訪れた際に表示された広告 $a$ をクリックする確率(Click-Through Rate, CTR)は $p_{isa}$ という"3次元"行列(縦横に加え奥行がある)として表現されます。これをfactorizationのスキームに載せるには、人 $\times$ 特徴 $W=(\cdots\ \vec{v}_i\ \cdots)$ 、広告枠 $\times$ 特徴 $H=(\cdots\ \vec{v}_s\ \cdots)$ 、広告 $\times$ 特徴 $D=(\cdots\ \vec{v}_a\ \cdots)$ という3つの特徴行列を考えることで、(5)式を拡張した以下のような"内積"によって推定値を得ることができます。
$\displaystyle p_{isa}=\sum_{f=1}^r v_{if}v_{sf}v_{af} \tag{7}$
通常の行列を2階のテンソルと思うことにすれば、"高次元の行列"(あまり一般的な概念ではない)は高階のテンソル(こちらは普通の概念)に対応するので*1、このような3次元以上の高次元の行列分解はTensor Factorizationと呼ばれているようです。当然バイアス項付きのTensor Factorizationや、Non-negative Tensor Factorization (NTF)といった拡張も可能です。

Factorization Machines (FM)

　さて、次はFMです。最も基本的なFMにおいては、表1のデータは次のような持ち方をします。

$\begin{array}{crccccccc} & \mbox{A} & \mbox{B} & \mbox{C} & \mbox{TI} & \mbox{NH} & \mbox{SW} & \mbox{ST} & \quad \mbox{評価値}\\ \vec{x}^{(1)}=& (1 & 0 & 0 & 1 & 0 & 0 & 0), & \quad y^{(1)}=5\\ \vec{x}^{(2)}=& (1 & 0 & 0 & 0 & 1 & 0 & 0), & \quad y^{(2)}=3\\ \vec{x}^{(3)}=& (1 & 0 & 0 & 0 & 0 & 1 & 0), & \quad y^{(3)}=1\\ \vec{x}^{(4)}=& (0 & 1 & 0 & 0 & 0 & 1 & 0), & \quad y^{(4)}=4 \tag{8}\\ \vec{x}^{(5)}=& (0 & 1 & 0 & 0 & 0 & 0 & 1), & \quad y^{(5)}=5\\ \vec{x}^{(6)}=& (0 & 0 & 1 & 1 & 0 & 0 & 0), & \quad y^{(6)}=1\\ \vec{x}^{(7)}=& (0 & 0 & 1 & 0 & 0 & 1 & 0), & \quad y^{(7)}=5 \end{array}$

MFに比べるとちょっとわかりにくいですね。 $\vec{x}^{(i)}$ が入力の特徴ベクトルで、値の0/1はBoolean的な意味と思ってください。つまり $\vec{x}^{(1)}$ はAlice(A)とタイタニック(TI)のところにフラグが立っているだけで、1という値の大きさに意味はありません。そしてもちろん、2人以上の人(AとB)や2つ以上の作品(TIとNH)に同時に1が立つこともありません。このベクトルの次元は評価者の人数と作品数の和で、ここでは $n$ とおきます。(上記例では $n=7$ )
　これを用いて、Factorization Machineの数式モデルは以下のように与えられます。
$\displaystyle\hat{y}(\vec{x})=w_0 + \sum_{i=1}^nw_ix_i + \sum_{i=1}^n\sum_{j=i+1}^n (\vec{v}_i\cdot\vec{v}_j)x_ix_j \tag{9}$
この中で $w_0, w_i\in\mathbb{R},\ \vec{v}_i\in\mathbb{R}^r\ (1\le i\le n)$ が機械学習によって決めるべきパラメータで、ベクトル $\vec{v}_i$ の次元 $r$ は例によってハイパーパラメータです。
　モデルの学習ができたとして、再びBobのタイタニックに対する評価値を推定してみましょう。引数として $\vec{x}^{B-TI}=(0\ \ 1\ \ 0\ \ 1\ \ 0\ \ 0\ \ 0)$ を与えると、値が残るのは $x^{B-TI}_2$ と $x^{B-TI}_4$ だけなので
$\displaystyle\hat{y}(\vec{x}^{B-TI})=w_0 + w_2 + w_4 + \vec{v}_2\cdot\vec{v}_4 \tag{10}$
となります。ここで $w_0\to \mu,\ w_2\to w_B,\ w_4\to w_{TI},\ \vec{v}_2\to\vec{v}_B,\ \vec{v}_4\to\vec{v}_{TI}$ と読みかえて(6)式の右辺 $\mu + w_B + w_{TI} + \vec{v}_B\cdot\vec{v}_{TI}$ と比較すると…ぴったり一致してますね！そうです、(8)式のような"誰"と"どの作品"の箇所にのみ1を立てるような特徴ベクトルの持ち方をした場合、Factorization MachineはMatrix Factorizationに一致するのです。(9)式では2次の項までに抑えていますが、これに例えば次のような3次の項
$\displaystyle \sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=j+1}^n\left(\sum_{f=1}^r v_{if}v_{jf}v_{kf}\right)x_ix_jx_k \tag{11}$
を付け加えると3階のTensor Factorizationになります。
　ではなぜMFで満足せずわざわざFMのようなモデルを新しく考えるかというと、フラグ以外の属性を加えるという拡張性があるからです。このセクションの初めに"最も基本的なFM"と書いたのはこのためです。再度FMの論文から例を拝借すると
$\begin{array}{crcc|cccc|cccc|c|c} & \mbox{A} & \mbox{B} & \mbox{C} & \mbox{TI} & \mbox{NH} & \mbox{SW} & \mbox{ST} & \overline{\mbox{TI}} & \overline{\mbox{NH}} & \overline{\mbox{SW}} & \overline{\mbox{ST}} & \mbox{Time} & \quad \mbox{評価値}\\ \hline \vec{x}^{(1)}=& (1 & 0 & 0 & 1 & 0 & 0 & 0 & 1/3 & 1/3 & 1/3 & 0 & 13) & y^{(1)}=5\\ \vec{x}^{(2)}=& (1 & 0 & 0 & 0 & 1 & 0 & 0 & 1/3 & 1/3 & 1/3 & 0 & 14) & y^{(2)}=3\\ \vec{x}^{(3)}=& (1 & 0 & 0 & 0 & 0 & 1 & 0 & 1/3 & 1/3 & 1/3 & 0 & 16) & y^{(3)}=1\\ \hline \vec{x}^{(4)}=& (0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1/2 & 1/2 & 5) & y^{(4)}=4\\ \vec{x}^{(5)}=& (0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1/2 & 1/2 & 8) & y^{(5)}=5\\ \hline \vec{x}^{(6)}=& (0 & 0 & 1 & 1 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 & 9) & y^{(6)}=1\\ \vec{x}^{(7)}=& (0 & 0 & 1 & 0 & 0 & 1 & 0 & 1/2 & 0 & 1/2 & 0 & 12) & y^{(7)}=5 \end{array}$
$\tag{12}$
わかりやすくするために罫線を入れてあります。ここで $\overline{\mbox{TI}}$ などにはその人が評価を行った作品に対して1/評価件数が、Timeには2008年12月から数えて何ヵ月後に評価を行ったかが入っています。このような属性を追加することにより、例えば直近に行った評価の方により重みを置くとか、過去に評価したことのある作品の影響を評価推定値に反映させるといったことが可能になります。例えばBobが2010年6月にタイタニックを評価した場合の特徴ベクトルは
$\vec{\tilde{x}}^{B-TI}=(0\ \ 1\ \ 0\ \ 1\ \ 0\ \ 0\ \ 0\ \ \frac{1}{3}\ \ 0\ \ \frac{1}{3}\ \ \frac{1}{3}\ \ 18) \tag{13}$
となるので、その評価予測値は(9)式より
$\begin{eqnarray} \hat{y}(\vec{\tilde{x}}^{B-TI})&=&w_0+w_B+w_{TI}+\frac{1}{3}w_{\overline{TI}}+\frac{1}{3}w_{\overline{SW}}+\frac{1}{3}w_{\overline{ST}}+18w_{T}\\ & &+\vec{v}_B\cdot\vec{v}_{TI}+\frac{1}{3}\vec{v}_B\cdot\vec{v}_{\overline{TI}}+\frac{1}{3}\vec{v}_B\cdot\vec{v}_{\overline{SW}}+\frac{1}{3}\vec{v}_B\cdot\vec{v}_{\overline{ST}}\\ & &+18\vec{v}_B\cdot\vec{v}_{T}+\frac{1}{3}\vec{v}_{TI}\cdot\vec{v}_{\overline{TI}}+\frac{1}{3}\vec{v}_{TI}\cdot\vec{v}_{\overline{SW}}+\frac{1}{3}\vec{v}_{TI}\cdot\vec{v}_{\overline{ST}}\\ & &+18\vec{v}_{TI}\cdot\vec{v}_{T}+\frac{1}{9}\vec{v}_{\overline{TI}}\cdot\vec{v}_{\overline{SW}}+\frac{1}{9}\vec{v}_{\overline{TI}}\cdot\vec{v}_{\overline{ST}}+6\vec{v}_{\overline{TI}}\cdot\vec{v}_{T}\\ & &+\frac{1}{9}\vec{v}_{\overline{SW}}\cdot\vec{v}_{\overline{ST}}+6\vec{v}_{\overline{SW}}\cdot\vec{v}_{T}+6\vec{v}_{\overline{ST}}\cdot\vec{v}_{T} \tag{14} \end{eqnarray}$
として求められます。この例で考えた項目に限らず、自分が使いたいと思った付帯属性を好きなだけモデルに加えて拡張していけるというのがFMの強みです。

Field-aware Factorization Machines (FFM)

　では最後にFFMの説明をします。Factorization Machineの式(9), (14)に現れるベクトル $\vec{v}_i$ は、例えばBobを表すベクトル $\vec{v}_B$ はあくまでも一つであり、内積を取る相手が作品だろうと拡張された属性だろうと常に同一のBobベクトル $\vec{v}_B$ を使っていました。それに対してFFMでは特徴ベクトル $\vec{x}$ のカラムをfield(日本語訳不明)と呼ばれるクラスに分け、同じBobを表現するベクトルであってもfieldごとに異なるものを用意し、内積をとる相手が属するクラスに応じて使い分けるということをします。例を挙げましょう。(9)式の2次の部分のFFM版は
$\displaystyle \sum_{i=1}^n\sum_{j=i+1}^n (\vec{v}_{i, f(j)}\cdot\vec{v}_{j, f(i)})x_ix_j \tag{15}$
となります。式(12)のケースではfieldは罫線で区切られた4つ、つまりAlice,Bob,Charlieはuser field $f(A)=f(B)=f(C)=f_u$ 、TI, NH, SW, STはmovie field $f(\mathrm{TI})=f(\mathrm{NH})=f(\mathrm{SW})=f(\mathrm{ST})=f_m$ 、 $\overline{\mbox{TI}}, \overline{\mbox{NH}}, \overline{\mbox{SW}}, \overline{\mbox{ST}}$ は逆評価数field $f(\overline{\mbox{TI}})=f(\overline{\mbox{NH}})=f(\overline{\mbox{SW}})=f(\overline{\mbox{ST}})=f_n$ 、TimeはTime field $f(\mathrm{Time})=f_t$ に属するものとします。(14)式に対応するFFM版の予測式は
$\begin{eqnarray} \hat{y}(\vec{\tilde{x}}^{B-TI})&=&w_0+w_B+w_{TI}+\frac{1}{3}w_{\overline{TI}}+\frac{1}{3}w_{\overline{SW}}+\frac{1}{3}w_{\overline{ST}}+18w_{T}\\ & &+\vec{v}_{B,f_m}\cdot\vec{v}_{TI,f_u}+\frac{1}{3}\vec{v}_{B,f_n}\cdot\vec{v}_{\overline{TI},f_u}+\frac{1}{3}\vec{v}_{B,f_n}\cdot\vec{v}_{\overline{SW},f_u}\\ & &+\frac{1}{3}\vec{v}_{B,f_n}\cdot\vec{v}_{\overline{ST},f_u}+18\vec{v}_{B,f_t}\cdot\vec{v}_{T,f_u}+\frac{1}{3}\vec{v}_{TI,f_n}\cdot\vec{v}_{\overline{TI},f_m}\\ & &+\frac{1}{3}\vec{v}_{TI,f_n}\cdot\vec{v}_{\overline{SW},f_m}+\frac{1}{3}\vec{v}_{TI,f_n}\cdot\vec{v}_{\overline{ST},f_m}+18\vec{v}_{TI,f_t}\cdot\vec{v}_{T,f_m}\\ & &+\frac{1}{9}\vec{v}_{\overline{TI},f_n}\cdot\vec{v}_{\overline{SW},f_n}+\frac{1}{9}\vec{v}_{\overline{TI},f_n}\cdot\vec{v}_{\overline{ST},f_n}+6\vec{v}_{\overline{TI},f_t}\cdot\vec{v}_{T,f_n}\\ & &+\frac{1}{9}\vec{v}_{\overline{SW},f_n}\cdot\vec{v}_{\overline{ST},f_n}+6\vec{v}_{\overline{SW},f_t}\cdot\vec{v}_{T,f_n}+6\vec{v}_{\overline{ST},f_t}\cdot\vec{v}_{T,f_n} \tag{16} \end{eqnarray}$
となります。同じBobでも対movieのときは $\vec{v}_{B,f_m}\cdot\vec{v}_{TI,f_u}$ , 対評価数では $\vec{v}_{B,f_n}\cdot\vec{v}_{\overline{TI},f_u}$ , 対時間では $\vec{v}_{B,f_t}\cdot\vec{v}_{T,f_u}$ と使い分けられています。FFMは実際にCTR予測[ Click-Through Rate Prediction | Kaggle, GitHub - guestwalk/kaggle-avazu ]や商品レコメンド[ E-Commerce Item Recommendation Based on Field-aware Factorization Machine ]などに応用されています。

HivemallでFactorization Machines

　実際にこれらの手法を試すにあたり、C++で書かれたMF, FM, FFM用のライブラリ

は用意されているのですが、プログラムを自前で組むのはハードルが高いので、今回はSQLでお手軽に実行できるHivemallで試してみようと思います。
　Hivemallとは、トレジャーデータ株式会社の油井誠氏によって開発されている機械学習ライブラリで、SQL-likeなクエリを使ってプログラミングレスで学習から予測までの機械学習の一連の処理を実行することができるというものです。トレジャーデータサービス(TDS)を導入してログを格納していれば、そのデータに対して手軽に分析をかけることができます。
　HivemallでMatrix Factorizationを行うやり方については、油井さんによるわかりやすい解説記事（HivemallでMatrix Factorization - Qiita）がありますのでそちらをご参照ください。Factorization Machinesについてもトレジャーデータの
公式ドキュメントがあるのですが、そちらの例には付帯属性(context information)が含まれていないようなので(2016/6/12現在)、今回は(12)のデータを使ったFMのやり方を示してみようと思います。
　以下の例では、データベースは全てfm_test_dbを使うものとします。まず、次のようなCSVファイルを作ってトレジャーデータのobserved_dataテーブルにアップロードします。これくらいの小さなデータであればブラウザからFile Uploadするのが一番楽です。

userId,movieId,n1,n2,n3,n4,months,rating,time
A,TI,0.333333,0.333333,0.333333,0.000001,13,5,0
A,NH,0.333333,0.333333,0.333333,0.000001,14,3,0
A,SW,0.333333,0.333333,0.333333,0.000001,16,1,0
B,SW,0.000001,0.000001,0.5,0.5,5,4,0
B,ST,0.000001,0.000001,0.5,0.5,8,5,0
C,TI,0.5,0.000001,0.5,0.000001,9,1,0
C,SW,0.5,0.000001,0.5,0.000001,12,5,0

トレジャーデータに入れるときは時刻を表すカラム(time)が必要なので、UNIX epoch (0)をダミーで指定しています。またn1などの値を0にしてしまうと次のステップでfeatureに取り込まれなくなってしまうようなので、非常に小さな値( $10^{-6}$ )としています。次いでこれを形式変換してobserved_featuresテーブルに保存します。*2

$ td table:create fm_test_db observed_features
$ td query -w --type hive -d fm_test_db "
  INSERT OVERWRITE TABLE observed_features 
  select 
    rowid() as rowid, 
    concat_array(
      categorical_features(array('userid', 'movieid'), userid, movieid), 
      quantitative_features(array('n1', 'n2', 'n3', 'n4', 'months'), n1, n2, n3, n4, rescale(months, 0, 18))
    ) as features, 
    rating 
  from observed_data"

質的変数（値の大きさに意味のないもの）はcategorical_featuresに、量的変数はquantitative_featuresに渡し、concat_arrayで結合します。rescaleは変数を0-1の範囲に規格化したい場合に使用します。このコマンドを実行するとobserved_featuresテーブルには以下のようなデータが入ります。
f:id:fan_k_oomori:20160612004328p:plain
通常、機械学習ではデータセットを学習用データと検証用データに分け、学習の結果得られたモデルの精度の検証を行うのですが、今回は元データが7レコードしかないため全てを学習に使用します。検証用データを分ける方法については公式ドキュメントを参照してください。
　では学習を行います。

$ td table:create fm_test_db fm_model
$ td query -w -x --type hive -d fm_test_db "
  INSERT OVERWRITE TABLE fm_model 
  select feature, avg(Wi) as Wi, array_avg(Vif) as Vif 
  from (
    select train_fm(features, rating, '-f 2 -iters 50 -min 1 -max 5') 
      as (feature, Wi, Vif) 
    from observed_features
  ) t 
  group by feature"

train_fmに与えたオプションパラメータは次のような意味です：itersは学習の際のイテレーションの回数を指定します。f（factorの頭文字）は特徴ベクトル空間の次元で、現在の例ではラブストーリー系とSF系という2種類のジャンルの映画を考えていることから $r=2$ としました。min, maxには目的変数（現在の場合は映画に対する5段階評価）の値の範囲を指定しますが、学習後のモデルによる予測値が厳密にmin～maxの間に収まるというものではなく、学習のヒント程度とのことです。さて、得られたfm_modelは以下のようになります。
f:id:fan_k_oomori:20160612010924p:plain
(9)式と比較すると、Wiがそれぞれのバイアス、Vifが特徴を表すベクトル（ここでは2次元）に対応していることがわかります。
　モデルの学習が済んだので、予測を行いましょう。予測用データとして、すでに学習用に使ったものも含めた3人×4作品の全12通りの組み合わせを用います。monthsには、2010年6月に評価を行うという想定で18を入れます。

userId,movieId,n1,n2,n3,n4,months,time
A,TI,0.333333,0.333333,0.333333,0.000001,18,0
A,NH,0.333333,0.333333,0.333333,0.000001,18,0
A,SW,0.333333,0.333333,0.333333,0.000001,18,0
A,ST,0.25,0.25,0.25,0.25,18,0
B,TI,0.333333,0.000001,0.333333,0.333333,18,0
B,NH,0.000001,0.333333,0.333333,0.333333,18,0
B,SW,0.000001,0.000001,0.5,0.5,18,0
B,ST,0.000001,0.000001,0.5,0.5,18,0
C,TI,0.5,0.000001,0.5,0.000001,18,0
C,NH,0.333333,0.333333,0.333333,0.000001,18,0
C,SW,0.5,0.000001,0.5,0.000001,18,0
C,ST,0.333333,0.000001,0.333333,0.333333,18,0

これをto_be_predictedテーブルに格納したとして、先ほどと同じようにfeaturesに変換します。

$ td table:create fm_test_db features_to_be_predicted
$ td query -w --type hive -d fm_test_db "
  INSERT OVERWRITE TABLE features_to_be_predicted 
  select 
    rowid() as rowid, 
    concat_array(
      categorical_features(array('userid', 'movieid'), userid, movieid), 
      quantitative_features(array('n1', 'n2', 'n3', 'n4', 'months'), n1, n2, n3, n4, rescale(months, 0, 18))
    ) as features 
  from to_be_predicted"

f:id:fan_k_oomori:20160612165220p:plain
さらにこれをexplodeします。

$ td table:create fm_test_db features_to_be_predicted_exploded
$ td query -x -w --type hive -d fm_test_db "
  INSERT OVERWRITE TABLE features_to_be_predicted_exploded 
  select rowid, extract_feature(fv) as feature, extract_weight(fv) as Xi 
  from features_to_be_predicted t1 
  LATERAL VIEW explode(add_bias(features)) t2 as fv"

features_to_be_predicted_explodedに格納されるデータのうちAlice×タイタニックのものを抜き出すと以下のようになります。
f:id:fan_k_oomori:20160612175129p:plain
これで準備が整いました。いよいよ予測です。

$ td table:create fm_test_db fm_predict_result
$ td query -w -x --type hive -d fm_test_db "
  INSERT OVERWRITE TABLE fm_predict_result 
  select t1.rowid, fm_predict(p1.Wi, p1.Vif, t1.Xi) as predicted 
  from features_to_be_predicted_exploded t1 
  LEFT OUTER JOIN fm_model p1 ON (t1.feature = p1.feature) 
  group by t1.rowid"

f:id:fan_k_oomori:20160612191907p:plain
これを(1)式のような行列で表現すると
$\left(\begin{array}{cccc} 5.261762887 & 3.184835209 & 1.084852807 & 2.699171219\\ 3.262923061 & 3.617618868 & 4.402889457 & 5.405837467\\ 1.354865797 & 2.605049221 & 5.090644018 & 5.181248237 \end{array}\right) \tag{17}$
(1)式を再掲します。
$\left(\begin{array}{cccc} 5\quad\quad\quad\quad\ \ &3\quad\quad\quad\quad\ \ &1\quad\quad\quad\quad\ \ \ & \quad\quad\quad\quad\ \ \\ \quad\quad\quad\quad\ \ & \quad\quad\quad\quad\ \ &4\quad\quad\quad\quad\ \ \ &5\quad\quad\quad\quad\ \ \\ 1\quad\quad\quad\quad\ \ & \quad\quad\quad\quad\ \ &5\quad\quad\quad\quad\ \ \ & \quad\quad\quad\quad\ \ \end{array}\right) \tag{1}$
これらを比較すると、評価値があるところについてはその値がある程度再現されており、未評価部分も埋まっていることが見て取れます。これにより、例えばCharlieに対してレコメンドを行う際には、ノッティングヒルの恋人(約2.60)よりもスタートレック(約5.18)の方が高評価になりそうということがわかります。
　HivemallにはFFMも近いうちに実装予定(2016/6/12現在)とのことですので、利用可能になったら試してみたいと思います。

References

[1] S. Rendle, "Factorization Machines," http://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf

[2] http://www.csie.ntu.edu.tw/~r01922136/slides/ffm.pdf

[3] HivemallでMatrix Factorization - Qiita

[4] MovieLens 20m Rating Prediction using Factorization Machine – Arm Treasure Data

[5] Factorization Machinesについて調べてみた - Qiita

[6] Factorization Machinesのおはなし。 | 分析のおはなし。

[7] Factorization Machines (ICDM 2010) 読んだ - 糞糞糞ネット弁慶

*1:物理屋、特に相対論屋さんとしては行列とテンソルを同一視することに違和感があるかもしれません（例：クリストッフェル記号 $\Gamma^i{}_{jk}$ は3つ足を持つので成分表記としては"3次元行列"として書けるが一般座標変換の下でテンソルとしての変換性を有しない）が、細かいことを気にしたら負けです。