kanayamaのブログ

twitter: @tkanayama_

Matrix Factorizationを確率モデルから導出する

Probabilistic Matrix Factorization [Salakhutdinov and Mnih, NIPS 2008] を読んだので、自分の言葉で行間を補いつつモデルの導出過程をまとめてみます。古典的な論文ですが、グラフィカルモデルを用いた独立性判定やベイズ推論を使いこなすための良い訓練になると思いました。

この記事のゴール

確率モデルから出発して、Matrix Factorizationの損失関数を導く。

問題設定と表記

M個のitemをN人のuserに推薦する問題を考える。user iがitem jに対してつけたRatingを R_{i, j} とする。 R_{1, 1} \cdots R_{N, M} のうち、Ratingが付いているものをまとめて Rと表記する。user i, item jの潜在表現をそれぞれ  U_i, V_j で表す。また、 U_1, \cdots ,U_N, V_1, \cdots ,V_Mそれぞれをまとめて U, Vと表記する。

確率モデルの設計

各確率変数  R_{i, j}, U_i, V_j に関するグラフィカルモデルを図のように設計する。(論文中の図より引用)

f:id:tepppei:20191116234209p:plain:w300
グラフィカルモデル

 U_i, V_jはそれぞれパラメータ  \sigma_U, \sigma_V により条件づけられ、 R_{i, j} U_i, V_j, \sigma により条件づけられる。

独立性に関する考察

上記のグラフィカルモデルから、どの確率変数が独立になるのかを判定する。(判定方法の具体的な手続きは、例えば須山敦志さんのブログがわかりやすいです。)

UとVの独立性

f:id:tepppei:20191117011256p:plain:w300

 U_i V_j R_{ij}により繋がっているが、head-to-head型でありblockされ、各 U_i V_jは独立になる。(逆に、 R_{ij}が観測されてしまうと U_i V_jが独立ではなくなってしまうこともこの図からわかる。)

Uどうし、Vどうしの独立性

f:id:tepppei:20191117103030p:plain:w300

 U_i U_i'を繋ぐpathは2種類ある。まず、 R_{ij} R_{i'j}を経由するpathは、上記と同じ理由でblockされる。一方、 \sigma_Vを経由するpathも、 \sigma_Uが観測されているという条件のもと、blockされる。したがって U_i U_i' \sigma_Uの条件付き独立となる。同じように、 V_i V_i' \sigma_Vの条件付き独立となる。

Rどうしの条件付き独立性

f:id:tepppei:20191117011308p:plain:w300

Rどうしのpathはたくさんあるが、一般化すると図のようになる。そして、Rどうしをつなぐpathの間には必ずtail-to-tail型のVノードもしくはUノードが存在する。したがって、各U, Vが観測されているという条件のもと、各Rは独立となる。

事後確率を書き下す

さて、学習データRが与えられたとき、U, Vの事後確率を最大化したい。すなわち、

 argmax_{U, V}   p(U, V | R, \Theta )

となるU, Vを求めたい。ただし、 \sigma, \sigma_V, \sigma_U をまとめて  \Theta で表している。ここで、

 p(U, V | R, \Theta) = \frac{p(U, V, R | \Theta)}{p(R | \Theta )}

であり、分母の  p(R | \Theta) はU, Vによらないので、最大化すべき関数は

 argmax_{U, V}  p(U, V, R| \Theta)

に置き換えられる。さらに、

 p(U, V, R| \Theta) = p(U |\Theta) p(V| \Theta, U) p(R | \Theta, U, V) = p(U | \Theta) p(V | \Theta) p(R |\Theta, U, V) \tag{1}

に分解できる。ここで、2つめの等号ではUとVの独立性を用いている。

したがって、 p(U | \sigma_{U}), p(V | \sigma_{V}), p(R | \sigma, U, V) をそれぞれ求めれば良い。

U, V, Rに確率分布を仮定する

  p(U | \sigma_U) = p(U_1, \cdots ,U_N | \sigma_U) において、 U_1, \cdots ,U_N \sigma_U に関して条件付き独立なので、

  p(U | \sigma_U) = \Pi_{i} p(U_i | \sigma_U)

が成り立つ。ここで、各  p(U_i | \sigma_U) に関して、平均0, 分散  \sigma_U^2 I の多次元正規分布を仮定すると、

  p(U | \sigma_U) = \Pi_{i} N(U_i | 0, \sigma_U^2 I) \tag{2}

と表せる。itemについても同様に各  p(V_i | \sigma_V) に関して、平均0, 分散  \sigma_V^2 I の多次元正規分布を仮定し、

  p(V | \sigma_V) = \Pi_{i} N(V_i | 0, \sigma_V^2 I) \tag{3}

と表せる。最後にRに関し、各RがU, Vの条件付き独立になることから、

 p(R | \sigma, U, V) = \Pi_{i} \Pi_{j} p(R_{i, j} | \sigma, U, V)^{I_{i, j}}

に分解できる。ここで、  I_{i, j} R_{i, j} が観測されているとき1、そうでないとき0になる指示関数である。そして、 各  p(R_{i, j} | \sigma, U, V) にも正規分布を仮定して、

 p(R | \sigma, U, V) = \Pi_{i} \Pi_{j} N(R_{i, j} | U_{i}^{T}V_{j}, \sigma^2)^{I_{i, j}} \tag{4}

を得る。

事後確率を計算する

さて、ここまでで準備が全て整ったので、式2, 3, 4を式1に代入して対数を取ることにより、

f:id:tepppei:20191117001701p:plain

を得る。最後に、U, Vに関する項だけ取り出して符号を反転させることで、損失関数

f:id:tepppei:20191117001710p:plain

を得る。これで、よく見るMatrix Factorizationの一般式が導かれた。終わり。

有名な拡張例

  • 今回扱った論文では  \sigma_U, \sigma_V, \sigma は外から与えるハイパーパラメータとしているが、例えば事前分布を設定して学習データから推定する論文がある。[Salakhutdinov and Mnih]
  • 今回の論文はexplicitなデータが想定されていたためratingが存在するデータのみを用いて学習を行なっていたが、ratingがあるデータと無いデータのペアを用いて学習することでimplicitに拡張した論文がある。[Rendle et al]

参考にした文献

特にグラフィカルモデルから独立性を判断するために下記を参考にしました。