接触履歴を用いた推薦で最も一般的な手法：行列分解
推薦システムのトップ会議であるRecSysにおける2016年のチュートリアルでは、「もしたった一つの手段を選ばなければいけないのであれば、行列分解は最も良い賭けだ（If you have to pick one single approach, matrix factorization is your best bet）」と述べられています。筆者は常にこの主張が正しいわけではないと考えますが、何か新しいデータに対して推薦システムを構築する機会があれば、必ず行列分解（特に重み付き行列分解）を最初に試します。
行列分解自体は明示的／暗黙的フィードバックのどちらに対しても有用な考え方ですが、この連載では暗黙的フィードバックに対するアプローチのみを扱います。前回説明したので詳細は省きますが、暗黙的フィードバックでは、我々にはユーザーとアイテムの接触履歴を表す、以下のような\(U\times I \)の行列\(R\)が与えられています（\(U\)はユーザー数、\(I\)はアイテム数）。
暗黙的フィードバックの状況。明示的な場合と異なり、レーティング情報を無視し、未観測部分はとりあえず0と扱う。
行列の要素が1となっているユーザー／アイテムの組み合わせは、その組み合わせで接触があった場合に対応し、0となっている組み合わせでは接触がなかった場合に対応します。
行列分解のアルゴリズムには、本稿で詳細に述べるように、さまざまなバリエーションが存在しますが、全てのアルゴリズムに共通して、「各ユーザー／アイテム固有の『特徴ベクトル』を持ち、その『特徴ベクトル』がユーザーとアイテムの間で揃う場合に、接触が起きやすい」という思想がベースになっています。つまり、
- 1となっているユーザー／アイテムの組み合わせは、ユーザーの「特徴ベクトル」がアイテムの「特徴ベクトル」と揃っているため、1となった。
- 0となっている組み合わせでは、ユーザー／アイテム間で「特徴ベクトル」が揃っていないため、0となった。
という考え方です。「特徴ベクトル」という言い方はやや抽象的ですが、行列分解では
- ユーザー\(u\)ごとに、その性質を表す\(n\)次元ベクトル\(\vec{p}_u\)が対応する
- アイテム\(i\)ごとに、その性質を表す\(n\)次元ベクトル\(\vec{q}_i\)が対応する。
と考えます。ここで\(n\)は「ユーザーの性質を特徴付ける潜在的な次元数」を表すパラメータであり、交差検証（学習データと検証データの役割を互い違いに変えながらデータを分割する検証手法）によって決定されます。そして、これらのベクトルの内積
\(\vec{p}_u \cdot \vec{q}_i\)
が\(u\)と\(i\)の「相性」を決定すると考えるのです。内積なので、\(\vec{p}_u\)と\(\vec{q}_i\)の長さがどちらも一定であれば方向が揃っている方がこの値は大きくなります。
例えば暗黙的フィードバックの行列\(R\)がレストランの訪問履歴と対応するというケースを考えましょう。この時、ユーザー／アイテムは
-
ユーザー（レストランの客）
- ユーザー\(1\)：本格中華が大好きなユーザー
- ユーザー\(2\)：本格フレンチが好きなユーザー
- ユーザー\(3\)：なんでもほどほどに好きなユーザー
-
アイテム（レストラン）
- レストラン\(1\)：中華料理店
- レストラン\(2\)：フランス料理店
- レストラン\(3\)：ファミリーレストラン（なんでも出てくる）
と与えられているとします。そのような背景で、それぞれのユーザの行動は、
-
ユーザー\(1\)
- レストラン\(1\)は訪問したので\(R_{11} = 1\)
- レストラン\(2\)は訪問しなかったので\(R_{12} = 0\)
-
ユーザー\(2\)
- レストラン\(1\)は訪問しなかったので\(R_{21} = 0\)
- レストラン\(2\)は訪問したので\(R_{22} = 1\)
- ...
などとなって、ユーザーのレストラン訪問履歴\(R\)は
\(R=\left (\begin{matrix} 1 & 0 & 1\\ 0 & 1 & 1\\ 1 & 1 & 1 \end{matrix}\right)\)
となったと考えましょう。ユーザー3は、全てのレストランへ訪問しますし、レストラン3は、全てのユーザーからの訪問があります。ここでやや先の内容になりますが、本稿で紹介する行列分解のアルゴリズムの一つである特異値分解（Singular Value Decomposition、以下SVD）を適用して、ユーザー／アイテムの二次元ベクトルを求めると、次の結果を得ます。
\begin{aligned} \vec{p}_1 &= (1.35 , 0.35) \\ \vec{p}_2 &= (0.35 , 1.35) \\ \vec{p}_3 &= (1.21 , 1.21) \\ \\ \vec{q}_1 &= (0.85 , -0.14) \\ \vec{q}_2 &= (-0.14 , 0.85) \\ \vec{q}_3 &= (0.5 , 0.5) \\ \end{aligned}
これは2次元空間に描画すると、次のような位置関係となっています。
SVDで計算されたユーザー／アイテムのベクトルを2次元にプロットした結果
このプロットを見ると、ユーザー／アイテムのベクトルの第一成分（横軸）は「中華料理の方向」第二成分（縦軸）は「フレンチの方向」という解釈が可能です。ユーザー1とアイテム1、ユーザー2とアイテム2はほぼ同じ方向を向いていることがわかります。実際に、行をユーザー、列をアイテムとし、行列の要素として対応するユーザー／アイテムの組み合わせのベクトルを使った内積を持つ行列を構成すると、
\(\left(\begin{matrix}\vec{p}_1\cdot \vec{q}_1 &\vec{p}_1\cdot \vec{q}_2 &\vec{p}_1\cdot \vec{q}_3 \\\vec{p}_2\cdot \vec{q}_1 &\vec{p}_2\cdot \vec{q}_2 &\vec{p}_2\cdot \vec{q}_3 \\\vec{p}_3\cdot \vec{q}_1 &\vec{p}_3\cdot \vec{q}_2&\vec{p}_3\cdot \vec{q}_3\end{matrix} \right)\) = \(P Q^T\) = \(\left (\begin{matrix}1.10 & 0.10 &0.85 \\0.10 & 1.10&0.85 \\0.85 & 0.85 & 1.21\end{matrix} \right) \) \(\simeq R\)
という行列となり、計算された行列は\(R\)の良い近似となっていることがわかります。 ただし \(P\)、\(Q\)はそれぞれユーザー／アイテムのベクトルを行の成分として持つ以下の行列です。
\(P=\left (\begin{matrix}\vec{p}_1 \\ \vec{p}_2 \\ \vec{p}_3 \end{matrix} \right)\) , \(Q =\left (\begin{matrix}\vec{q}_1 \\ \vec{q}_2 \\ \vec{q}_3 \end{matrix}\right)\)
今回の例では、\(R\)は行数・列数（ユーザー数・アイテム数）がそれほど大きくなく、かつユーザー／アイテムの性質についても事前に知識がありました。ただ、実際の現場では、もっと行数・列数が多い\(R\)が与えられていて、かつユーザー／アイテムについての性質が詳細に分からない場合が通常です。よって実運用においては、このようにサイズの大きいデータが与えられた場合であっても、行列分解アルゴリズムが「中華方向」「フレンチ方向」のような次元を勝手に発見してくれるようになっていなくてはいけません。
このように、ユーザー／アイテムのベクトル\(\vec{p}_u\)、 \(\vec{q}_i\)を\(R\)から求めるという考え方は全ての行列分解アルゴリズムで共通していますが、どのように\(R\)からユーザー／アイテムのベクトルから求めるか、についてはさまざまなアプローチが存在します。これは「最小化したい誤差関数をどのように設計するか」にさまざまな自由度があるということです。本稿では、代表的なアプローチのうち特に重要なアルゴリズムに絞って解説します。
