(cache)userの閲覧確率を考慮したMatrix Factorization

Modeling User Exposure in Recommendation [Liang et al., WWW2016] を読んだので、今回も行間を補いつつ、主にアルゴリズムの導出部分をブログにしました。

論文の一言要約

「itemが閲覧されたかどうか」（言い換えると、ユーザーの目に入ったかどうか）を表す確率変数をMatrix Factorizationに導入した。これによって、例えば「このユーザーに興味がありそうなのにクリックされていないアイテムは、まだユーザーの目に入っていない確率が高い」などを考慮したモデルの構築が期待できる。

この記事のゴール

この論文の提案手法である「exposure MF」の更新式を導出する。

表記

user $u = 1, \dots, U$ に item $i = 1, \dots, I$ を推薦する問題を考える。user uがitem iをクリックしたかどうかを $U \times I$ 行列 $Y = {y_{u, i}}$ で表す。

確率モデルの設計

確率モデルを下記のように設計する。（論文中の図より引用）

f:id:tepppei:20191117202921p:plain:w300

ここで、 $a_{u, i}$ はuser uがitem iを閲覧したかどうかを表現するための確率変数である。 $y_{u, i}$ の値は全て観測されている一方、 $a_{u, i}$ は対応する $y_{u, i}$ の値が1であれば $a_{u, i} = 1$ となり、 $y_{u, i}$ の値が0であれば観測されない。言い換えれば、「クリックが発生したならば閲覧したと言えるが、クリックが発生していなかったら閲覧したかどうかわからない」ことを表している。（したがって $a_{u, i}$ は一部だけ観測されていることになるので、上記のグラフィカルモデルではノードの色が若干薄くなって表現されている。）

確率分布の仮定

各確率変数に関して下記のような分布を仮定する。

f:id:tepppei:20191117203808p:plain:w300

$θ_{u}, β_{i}$ には正規分布が、 $a_{u, i}$ には二項分布が仮定されている。 $y_{u, i}$ は、閲覧されたか否かによって2種類の分布が仮定される。まず、閲覧された場合は正規分布が仮定される。一方、閲覧されなかった場合は $y_{u, i} = 0$ のときに確率1を取るようなデルタ分布が仮定されている。これは、「閲覧されなかったらクリックは絶対に発生しない」ことを表している。

対数尤度関数の導出

$y_{u, i}$ と $a_{u, i}$ （の一部）がデータとして観測された場合に、最適な $θ_{u}, β_{i}$ を求めたい。まず、尤度関数は以下のように表せる。

$p (a_{u i}, y_{u i} | μ_{u i}, θ_{u}, β_{i}, λ_{y}) = p (a_{u i} | μ_{u i}, θ_{u}, β_{i}, λ_{y}) \times p (y_{u i} | a_{u i}, μ_{u i}, θ_{u}, β_{i}, λ_{y})$

ここで、 $p (a_{u i} | μ_{u i}, θ_{u}, β_{i}, λ_{y})$ に関しては仮定した正規分布をそのまま当てはめることができる。一方 $p (y_{u i} | a_{u i}, μ_{u i}, θ_{u}, β_{i}, λ_{y})$ は $a_{u i}$ が0のときと1のときで分布が異なる。これを同時に表すと以下のようになる。

$p (y_{u i} | a_{u i}, μ_{u i}, θ_{u}, β_{i}, λ_{y}) = N (y_{u i} | θ_{u}^{T} β_{i}, λ_{y}^{- 1})^{a_{u i}} + I [y_{u i} = 0]^{1 - a_{u i}}$

以上を尤度関数の式に当てはめて対数を取ることにより、下記の対数尤度関数を得る。

f:id:tepppei:20191117205843p:plain:w400

MAP推定のための目的関数を書き下す

さて、最適な $θ_{u}, β_{i}$ をMAP推定により求めることを考える。最大化したい事後確率は、

$p (θ_{1}, \dots, θ_{U}, β_{1}, \dots, β_{I} | a_{11}, \dots, a_{U I}, y_{11}, \dots, y_{U I})$

であり、

さらにMAP推定においてよくある変形

$p (θ_{1}, \dots, θ_{U}, β_{1}, \dots, β_{I} | a_{11}, \dots, a_{U I}, y_{11}, \dots, y_{U I}) \propto p (a_{11}, \dots, a_{U I}, y_{11}, \dots, y_{U I} | θ_{1}, \dots, θ_{U}, β_{1}, \dots, β_{I}) p (θ_{1}, \dots, θ_{U}, β_{1}, \dots, β_{I})$

を用いて、最大化対象の関数を次のように書き直せる。

$m a x i m i z e_{θ, β} p (a_{11}, \dots, a_{U I}, y_{11}, \dots, y_{U I} | θ_{1}, \dots, θ_{U}, β_{1}, \dots, β_{I}) p (θ_{1}, \dots, θ_{U}, β_{1}, \dots, β_{I}) = Π_{u} Π_{i} p (a_{u i}, y_{u i} | θ_{u}, β_{i}) \cdot Π_{u} p (θ_{u}) \cdot Π_{i} p (β_{i})$

ここで、

$a_{11} \dots a_{U I}$ が $θ_{1} \dots θ_{U}, β_{1}, \dots, β_{I}$ の条件付き独立であること
$y_{11} \dots y_{U I}$ が $θ_{1} \dots θ_{U}, β_{1}, \dots, β_{I}$ の条件付き独立であること
$θ_{1}, \dots, θ_{U}, β_{1}, \dots, β_{I}$ が独立であること

を用いている。独立かどうかは前回記事と同様にグラフィカルモデルから判定できる。

最後に対数を取って、目的関数は以下のようになる。

$m a x i m i z e_{θ, β} Σ_{u} Σ_{i} l o g p (a_{u i}, y_{u i} | θ_{u}, β_{i}) + Σ_{u} l o g p (θ_{u}) + Σ_{i} l o g p (β_{i})$

なお、 $μ, λ$ は今回は確率変数ではなくハイパーパラメータとして扱っているため省略している。

EMアルゴリズムによる最適化

さて、上記の目的関数を最大化したいところだが、通常のMFとは異なり $θ_{u}, β_{i}$ だけでなく $a_{u, i}$ も最適化対象となり、そのまま最大化するのは困難である。そこで、EMアルゴリズムを適用することを考える。

EMアルゴリズムでは、まず目的関数を $a | y$ の条件付き期待値で置き換え、E stepとM stepを交互に繰り返すことで最適化を行う。すなわち、目的関数は

$E_{a_{11} \dots a_{U I} | y_{11} \dots y_{U I}} [Σ_{u} Σ_{i} l o g p (a_{u i}, y_{u i} | θ_{u}, β_{i}) + Σ_{u} l o g p (θ_{u}) + Σ_{i} l o g p (β_{i})$ ]

であり、期待値の加法性を用いて $Σ_{u} Σ_{i} E_{a_{u i} | y_{u i}} [l o g p (a_{u i}, y_{u i} | θ_{u}, β_{i})] + Σ_{u} l o g p (θ_{u}) + Σ_{i} l o g p (β_{i})$

と表せる。次に $p (a_{u i}, y_{u i} | θ_{u}, β_{i})$ に上で求めた対数尤度を代入して、

$Σ_{u} Σ_{i} E_{a_{u i} | y_{u i}} [a_{u i} l o g N (y_{u i} | θ_{u}^{T} β_{i}, λ_{y})] + Σ_{u} l o g p (θ_{u}) + Σ_{i} l o g p (β_{i}) + C$

ただし、このあと $θ$ や $β$ で偏微分するので、これに関係ない項（対数尤度の1項目と3項目）は全てCに押し込めた。

さらに $E_{a_{u i} | y_{u i}} [a_{u i} l o g N (y_{u i} | θ_{u}^{T} β_{i}, λ_{y})]$ について、期待値 $a_{u i} | y_{u i}$ に無関係な部分を外に出した上で、 $y_{u i}$ の条件付きであることに注意すると、

$l o g N (y_{u i} | θ_{u}^{T} β_{i}, λ_{y}) E_{a_{u i} | y_{u i}} [a_{u i} | y_{u i}]$

が出てくる。この $E_{a_{u i} | y_{u i}} [a_{u i} | y_{u i}]$ を $p_{u i}$ とおき、最後に目的関数をまとめると下記のようになる。

$\begin{matrix} (1) & Σ_{u} Σ_{i} p_{u i} l o g N (y_{u i} | θ_{u}^{T} β_{i}, λ_{y}) + Σ_{u} l o g p (θ_{u}) + Σ_{i} l o g p (β_{i}) + C \end{matrix}$

Eステップ

Eステップでは、式1の $p_{u i}$ を求める。これは $y_{u i}$ の値によって場合分けが必要になる。

(i) $y_{u i} = 1$ のとき

$a_{u i} = 1$ となるので、期待値を取っても当然 $p_{u i} = 1$ である。

(ii) $y_{u i} = 0$ のとき

期待値をさらに書き下すと、

$E [a_{u i} | y_{u i}] = Σ_{a_{u i} = 0, 1} a_{u i} p (a_{u i} | y_{u i}) = 0 \times p (a_{u i} = 0 | y_{u i}) + 1 \times p (a_{u i} = 1 | y_{u i}) = p (a_{u i} = 1 | y_{u i})$

さらに、

$p (a_{u i} | y_{u i}) = \frac{p (a_{u i}, y_{u i})}{p (a_{u i})} = \frac{p (a_{u i}) p (y_{u i} | a_{u i})}{Σ_{a_{u i}} p (a_{u i}) p (y_{u i} | a_{u i})} = \frac{p (a_{u i}) p (y_{u i} | a_{u i})}{p (a_{u i} = 0 p (y_{u i} | a_{u i} = 0) + p (a_{u i} = 1) p (y_{u i} | a_{u i} = 1)}$

であるので、 $a_{u i} = 1, y_{u i} = 0$ のとき、

f:id:tepppei:20191120221432p:plain:w400

が得られる。

ただし、

$p (a_{u i} = 1) = μ_{u i}$

$p (a_{u i} = 0) = 1 - μ_{u i}$

$p (y_{u i} = 0 | a_{u i} = 1) = N (0)$

$p (y_{u i} = 0 | a_{u i} = 0) = 1$

を用いた。

Mステップ

Mステップでは、 $p_{u i}$ が分かっているという前提のもと、式1を $θ$ および $β$ で偏微分し、更新式を得る。 $θ$ と $β$ は対照なので、以下では $θ$ の更新式のみ導くことにする。

まず、式1の第一項 $Σ_{u} Σ_{i} p_{u i} l o g N (y_{u i} | θ_{u}^{T} β_{i}, λ_{y})$ に正規分布を当てはめた上で $θ$ で偏微分すると、

$\frac{\partial}{\partial θ} Σ_{u} Σ_{i} p_{u i} l o g N (y_{u i} | θ_{u}^{T} β_{i}, λ_{y}) = Σ_{i} λ_{y} p_{u i} \frac{\partial}{\partial θ} (y_{u i} - θ_{u}^{T} β_{i})^{2} = \dots = Σ_{i} λ_{y} p_{u i} (- y_{u i} β_{i} + (β_{i} β_{i}^{T}) θ_{u})$

一方、式1の第二項 $Σ_{u} l o g p (θ_{u})$ も同様に偏微分すると、

$\frac{\partial}{\partial θ} Σ_{u} l o g p (θ_{u}) = λ_{θ} θ_{u}$

となる。

以上より、式1を $θ$ で偏微分すると

$\frac{\partial}{\partial θ} (式 1) = Σ_{i} λ_{y} p_{u i} (- y_{u i} β_{i} + (β_{i} β_{i}^{T}) θ_{u}) + λ_{θ} θ_{u}$

となって、これを0とおいた方程式を解くことで、以下の更新式を得る。

f:id:tepppei:20191120224724p:plain:w400

$β$ の更新式も同様に得られる。終わり。

著者による実装

こちらで公開されています。

類似の研究

この論文もそうでしたが、implicit feedbackにおいては「クリックがなかった」という事象をどのように扱うかが鍵になります。この論文よりもナイーブな方法として、「クリックがなかった」を「多分興味がない」に読み替えて、弱い重み付けをしてMFを学習する論文（Collaborative Filtering for Implicit Feedback Datasets）などがあります。

参考文献

論文中ではEMアルゴリズムによる更新式だけがいきなり出てきていたので、事後確率から出発して更新式を導くために下記の書籍・記事を参考にしました。