推薦システム入門：行列分解の役割

2022年12月23日 18:26

こんにちは、石川竜一郎(@mxb02762)です。大学で経済学を教える傍ら、SciDe Lab 株式会社ファウンダー兼取締役を務めています。SciDe Lab.は、経済学を用いて社会問題の解決を行うために立ち上げられました。

この投稿では私たちの生活に不可欠となった「推薦システム」の入門的な解説をしながら、その中心的な手法である「行列分解(matrix factorization)」について説明します。また、推薦システムが経済学とどのように関わりがあるかについてもお話ししたいと思います。

行列分解は、かつてNetflix社が行った推薦システムの改善を競うコンペで広く用いられ、近年の研究が進むきっかけとなりました。行列分解がどのような役割を果たしているかを知ることは、推薦システムそのものの理解に不可欠ですので、ぜひここでチャレンジしてみてください。

推薦システムとは？

推薦システム（レコメンデーション・エンジン）とは、amazon、Netflix、Apple MusicやRakutenなどでみかける「多数の商品・サービスからユーザーの好みと推定されるアイテムを提示」するシステムです。特に個別ユーザーに対して異なるアイテムが提示される場合には、個人化推薦（Personalized recommendations）と呼ばれます。

個人化推薦システムを実現するにあたって重要なことは、ユーザーの好みがわからないアイテムの評価をどう推定するかです。ひとたびユーザーの評価が決まれば、それにしたがって評価の高いアイテムをユーザに推薦することができます。そのために、好みのわからないアイテムの評価推定に用いられる手法が「行列分解」です。

評価値行列の構造と行列分解

推薦システムが利用する情報として重要な役割を果たすのが、評価行列(rating matrix)です。評価行列は、行方向にユーザーを、列方向にアイテムをラベルとして、ユーザーが個々のアイテムをどのように評価したかを表します。例えば二人のユーザー（太郎、次郎）が、アイテムとして三つ異なる小説 $${(a, b, c)}$$を$${ \{ }$$面白い、ふつう、つまらない$${ \} }$$で評価している評価行列$${R}$$の例として次のようなものが考えられます。

$$
R=
\begin{pmatrix}
+1 & 0 & \mathrm{□} \\
\mathrm{□} & -1 & +1
\end{pmatrix}
$$

ここで、$${\{+1, 0, -1, \mathrm{□} \}}$$は$${ \{ }$$面白い、ふつう、つまらない、評価なし$${ \} }$$に対応し、一行目は太郎の小説$${(a, b, c)}$$の評価として$${（+1, 0, 評価なし）}$$、二行目は次郎の評価として$${（評価なし, -1, +1）}$$であることを意味します。

評価値行列では、ユーザーの評価がすべてのアイテムに行われているわけではありません。評価されていないアイテムに対する評価を推定することが推薦システムの基本的な問題であり、その手法の一つが行列分解なのです。

行列分解を行うことで、たとえば上記の評価行列$${R}$$は、ユーザー数を行数とした行列

$$
p=
\begin{pmatrix}
p_{11} \\
p_{21}
\end{pmatrix}
$$

とアイテム数を列数とした行列

$$
q=
\begin{pmatrix}
q_{11}, q_{12}, q_{13}
\end{pmatrix}
$$

に分解され、行列$${R}$$を近似的に表すことができます。すなわち

$$
R \approx P \times Q = \begin{pmatrix}
p_{11} \\
p_{21}
\end{pmatrix}
\times
\begin{pmatrix}
q_{11}, q_{12}, q_{13}
\end{pmatrix}
=
\begin{pmatrix}
p_{11}q_{11} & p_{11}q_{12} & p_{11}q_{13} \\
p_{21}q_{11} & p_{21}q_{12} & p_{21}q_{13} \\
\end{pmatrix}
$$

という関係を与えることができます。行列$${P}$$と$${Q}$$はそれぞれユーザーとアイテムの数に基づいて構成されるので、ユーザー及びアイテムの潜在因子行列(Latent factor matrix)と呼ばれます。この潜在因子行列を適切に推計することで、行列$${R}$$で評価されていないアイテムの評価も可能になります。

また行列$${R}$$では構成要素は２×３＝６要素ありましたが、行列分解を行うことで２及び３要素で構成される行列$${P}$$と$${Q}$$に分かれ、推計する数値の数が２＋３＝５と一つ減らすことができます。この例では考えている次元が低いためこの恩恵が分かりにくいですが、ユーザーやアイテムの数が増えると、こうした次元の縮小により推定のための計算負担を大きく減じることができます。

潜在因子行列の推定

行列$${R}$$の空欄部分を、行列$${P}$$と$${Q}$$で評価するために、$${R}$$内で評価値が与えられている要素について、$${P\times Q}$$の構成要素との差を考えてみましょう。いま、行列$${R}$$を次のように表現します。

$$
R=
\begin{pmatrix}
r_{11} & r_{12} & r_{13} \\
r_{21} & r_{22} & r_{23}
\end{pmatrix}
$$

先の例では$${r_{13}}$$と$${r_{21}}$$の評価がわからないので、それ以外の評価が与えられている要素に対して、行列$${P\times Q}$$の対応する要素との差$${e_{ij}}$$を計算します。この例では、

$$
\begin{array}{}
e_{11} &\equiv& r_{11}-p_{11}q_{11} \\
e_{12} &\equiv& r_{12}-p_{11}q_{12} \\
e_{22} &\equiv& r_{22}-p_{21}q_{12} \\
e_{23} &\equiv& r_{23}-p_{21}q_{13}
\end{array}
$$

が計算できます。$${e_{ij}}$$は正負のどちらの値も取りうるので、和の計算で打ち消し合わないように各値を二乗して、$${e_{11}^2+e_{12}^2+e_{22}^2+e_{23}^2}$$ができるだけ0に近づく行列$${P}$$と$${Q}$$を見つけることができれば、評価のなかった$${r_{13}}$$や$${r_{21}}$$に推定値を与えることが可能になります。結果として、どのように行列$${P}$$と$${Q}$$を見つけるかという問題に帰着します。

線形代数を学んだことのある読者は、特異値分解と呼ばれる行列の分解定理についてご存知かもしれません。行列$${R}$$にその分解定理を適用して、行列$${P}$$と$${Q}$$を見つけるという手法もあります。ただその場合には、行列$${R}$$の評価のない項目に対して、何らかの値を挿入する必要があり、結果として推定値があまり良いものにならないことも知られています。

そのため近年では、交互最小二乗法（Alternating least square）や確率的勾配降下法（Stochastic gradient descent）という手法が用いられています。ここでは、確率的勾配降下法の要である勾配降下法に焦点を当てて、推定手法を理解していきましょう。

ここで考える問題は行列$${R}$$内で評価がある項目だけに注目し、行列$${P\times Q}$$との差の二乗和である$${J=\sum_{ij}(e_{ij})^2}$$を最小とする行列$${P \times Q}$$を見つけることでした。このために、初期値として適当な値を行列$${P\times Q}$$に割り当てて、それを少しずつ変化させることで、$${J}$$を０に近づけていきます。

$${P}$$や$${Q}$$の各要素を変化させることで$${J}$$がどのように変化するかを知るために、高校で学んだ微分を用いて関数の変化率を計算します。この計算は微分を行列に用いる上に変数が一つではないため、複雑なことを行うように見えますが、行列$${P}$$と$${Q}$$の個々に構成要素に対する微分を考えてみてください。例えば、$${e_{11}}$$を$${p_{11}}$$で（偏）微分を計算すると$${-q_{11}}$$が得られます。すべての$${e_{ij}}$$に対してこのような（偏）微分を行うことで、$${J}$$全体がどのように変化するかが計算できます。その変化率を用いて、最も０に近くなる$${J}$$を計算し$${P}$$と$${Q}$$が決定します。

ひとたび$${P}$$と$${Q}$$の推定ができれば、$${R}$$内の評価がなかった要素を推定した$${P}$$と$${Q}$$を用いて計算することができ、すべてのアイテムの評価が得られます。これが勾配降下法の基本的な考え方です。確率的勾配降下法では、勾配降下法の計算量を減らすための工夫が施されていますが、基本的な考え方は同じです。

その他の推定方法

これまでの推定方法では、ユーザーが個々のアイテムに対して与えた明示的な評価をデータとして想定しました。一方でユーザーが評価値を入力せずに、クリック数などのユーザーの行動等の暗黙的な評価から、アイテムの評価を推定する方法も議論されています。しかし暗黙的評価データより明示的評価データを用いる方が、推薦システムのパフォーマンスはよくなることも知られています。データを取得がどのようにできるかは状況にもよるので、その状況に合ったデータの取得とそれに基づく手法を選択してく必要があります。

経済学と推薦システム

これまでみたように推薦システムでは、評価行列内で得られているユーザの評価を用いて、評価されていないアイテムの評価を推定しています。この方法がうまくいくためには、ユーザーが与えている評価が、そのユーザーの真実の評価でなければありません。ユーザーが熟考せずに安易に回答した評価値をもとに他のアイテムを評価すると、そこから作られる推薦システムも精度が高くならないことは容易に想像できます。したがって、経済学やゲーム理論の観点から考えると、ユーザーが真実の評価を与えてくれるインセンティブは何かを考慮しなければなりません。

別の記事で書いたベイジアン自白剤は、ゲーム理論的に基礎付けされたユーザーが真実の評価を与えているかを評価する指標と考えることもできます。また、評価するアイテムについて情報交換するためのコミュニケーション場を適切に設計することで、アイテムの特性理解を深めることもできるでしょう。いずれにしても経済学やゲーム理論は、データとして用いる情報をできるだけ適切にユーザーから引き出すためのインセンティブの設計の際に用いられ、分析の精度をあげることに一役買うという重要な役を担っています。

重要な点は、そうした情報獲得のためのルール設計は推薦システムと独立に考えることはできません。なぜならば、ユーザーは自分の与えた評価がどのようにシステム内で用いられかを考慮して自分の評価情報を提供する可能性があるからです。たとえば極端な例として、あるアイテムに高い評価を与えたとしても、それが推薦システム上では正反対の低い評価に変換されるようであれば、ユーザーは高く評価したいアイテムを低い評価値にして提示するでしょう。ここまで極端ではなくても、高い評価がシステム上で割り引かれたり歪められて反映されると、その歪め方に対応した評価を各ユーザーが提出することになります。

ここからわかるように、推薦システムの設計とユーザが評価を正しく提示することを独立に考えることはできないのです。

まとめ

この投稿では、近年様々な場面で見かける推薦システムについて、簡単な概要とそのシステム設計のコアとなる行列分解について説明しました。実務的には、多くのアイテムに対して個々のユーザーの評価がほとんど与えられていないのが通常です。そのような疎なデータに対してどのように評価値を推計して補うのかが推薦システムの設計における問題となります。

行列分解はその問題に直接的に取り組む手法ですが、近年はそれ以外にも自然言語解析の手法を応用したトピックモデル、深層学習や強化学習を用いた推薦システム構築も研究されています。最先端の研究成果については専門論文を見ていく必要がありますが、推薦システムの基本的な数理を理解するため、以下の教科書をお勧めしたいと思います。参考になれば幸いです。

SciDe Lab.ではこのように、経済学・ゲーム理論の知見を用いて、ユーザーの評価情報収集とシステムの依存性を考慮した推薦システム構築を行なっています。このような推薦システム設計に興味がありましたらば、お気軽にご連絡ください。

この記事が気に入ったらサポートをしてみませんか？