備忘録

主に機械学習、統計、競技プログラミングに関する備忘録

Regression-based EMの導出

はじめに

Learning to rankにおけるポジションバイアスの求め方の一種であるRegression-based EM[Wang18]の導出についてまとめる。 より具体的には論文中のEMアルゴリズムの更新式(2)のあたりを詳しく追う。

定義

基本的には論文の表記に従う。

  • $q$ : クエリ
  • $d$ : 文書
  • $C$ : ユーザが文書をクリックしたか
  • $R$ : ユーザが文書に興味があるか
  • $E$ : ユーザが文書を確認したか
  • $k$ : 文書の位置
  • $\mathcal{L} = \left\{ \left(c, q, d, k\right)\right\}$ : ユーザのログの集合

Position Bias Model

Posigion Bias Model (PBM) ではクリックしたかを表す確率変数 $C$ が潜在変数 $E, R$ を通じて以下のように生成されると仮定する: $$ P(C = 1 \mid q, d, k) = P(E = 1 \mid k) \cdot P(R = 1 \mid q, d) $$

すなわち、$C=1$ となるのは $E=R=1$ の場合に限る。

第一項及び第二項をそれぞれ以下のように定義しておく:

$$ \begin{align} \theta_k &= P(E = 1 \mid k), \\ \gamma_{q, d} &= P(R = 1 \mid q, d). \end{align} $$

$\gamma_{q, d}$ は通常適当な特徴量 $x_{q,d}$ と予測器 $f$ を用いて $\gamma_{q,d} = f(x_{q, d})$ と計算される。しかし、ここでは機械学習モデルによる予測には立ち入らず、PBMの尤度最大化による $\gamma_{q, d}$ の最適化を考えるものとする。

PBMにおけるパラメータは $\left\{ \theta_k \right\}, \left\{ \gamma_{q, d}\right\}$ であり、最適なパラメータは対数尤度

$$ \begin{align} \log P(\mathcal{L}) &= \sum_{(c, q, d, k) \in \mathcal{L}} c \log P(C = 1 \mid q, d, k) + (1 - c) \log P(C = 0 \mid q, d, k) \\ &= \sum_{(c, q, d, k) \in \mathcal{L}} c \log \theta_k \gamma_{q, d} + (1 - c) \log (1 - \theta_k \gamma_{q, d} ) \end{align} $$

を最大化するものである。この目的関数を直接最適化するのは困難なため、EMアルゴリズムを用いて最適なパラメータを反復法で求めることになる。

EMアルゴリズムによるパラメータ推定

EMアルゴリズムの概要

観測可能な確率変数 $X$ と観測不可能な潜在変数 $Z$ が確率密度関数 $p(X, Y \mid \xi)$ に従ってるとする。 $Z$ を観測出来ないという設定の下で素朴に $\xi$ を推定しようと思えば対数尤度

$$ \log p(X^n \mid \theta) = \log \sum_{Z^n} p(X^n, Z^n \mid \xi) $$

を最大化すればよいが、この操作は一般には優しくない。EMアルゴリズムでは以下の操作によって $\hat{\xi}^{(0)}, \hat{\xi}^{(1)}, \dots$ を生成する。このように生成された列 $\hat{\xi}^{(t)}$ は局所最適解に収束することが示される。

  • Eステップ : $p(Z \mid X, \hat{\xi}^{(t)})$ を計算する
  • Mステップ : $\hat{\xi}^{(t+1)} = \mathrm{arg~max}~Q(\xi \mid \hat{\xi}^{(t)})$ を計算する ただし、 $Q$ は以下のような関数である: $$ \begin{align} Q(\xi \mid \hat{\xi}^{(t)}) &= \mathbb{E}_{Z^n \mid X^n, \hat{\xi}^{(t)}} \left[ \log p(X^n, Z^n \mid \xi) \right] \\ &= \sum_{Z^n} p(Z^n \mid X^n, \hat{\xi}^{(t)}) \log p(X^n, Z^n \mid \xi) \end{align} $$

$\theta_{k}, \gamma_{q, d}$ の推定

EMアルゴリズムの設定において $Z = (E, R), \xi = \left( \left\{ \theta_{k} \right\}, \left\{ \gamma_{q, d} \right\} \right)$ として更新式の導出を行う。

Eステップ

観測データで条件付けた下での潜在変数の条件付き確率 $P(E, R \mid C, q, d, k)$ を求める。 これは変数の定義と設定した確率モデルから直ちに求まる。

Mステップ

論文中ではMステップにおいて $E$ と $R$ それぞれの周辺確率について $Q$ 関数を計算し、$\theta_{k}$ と $\gamma_{q, d}$ の更新式を求めているが、その部分が若干天下り的だったので詳細を確認する。 まず今回の設定で $Q$ 関数を書き下すと以下のようになる:

$$ \begin{align} Q(\xi \mid \hat{\xi}^{(t)}) = \sum_{(c, q, d, k) \in \mathcal{L}} \sum_{(E, R)}P(E, R \mid c, q, d, k) \left( c \log P(C = 1, E, R \mid q, d, k) + (1 - c) \log P(C=0, E, R \mid q, d, k) \right) \end{align} $$

ここで $\log P(C,E,R \mid q, d, k)$ は

$$ \log P(C, E, R \mid q, d, k) = \log P(C \mid E, R) + \log P(E \mid k) + \log P(R \mid q, d) $$

と分解できる。パラメータ $\xi$ のうち、$\theta_{k}$ は $\log P(E \mid k)$に、$\gamma_{q, d}$ は $\log P(R \mid q, d)$ にそれぞれ依存することに着目して、$Q$ 関数も以下のように分解する:

$$ \begin{align} Q(\xi \mid \hat{\xi}^{(t)}) &= Q_{\theta}(\theta \mid \hat{\xi}^{(t)}) + Q_{\gamma}(\gamma \mid \hat{\xi}^{(t)}) + \mathrm{const.}, \\ Q_{\theta}(\theta \mid \hat{\xi}^{(t)}) &= \sum_{(c, q, d, k) \in \mathcal{L}} \sum_{E}P(E \mid c, q, d, k) \left( c \log P(E \mid k) + (1 - c) \log P (E \mid k) \right), \\ Q_{\gamma}(\gamma \mid \hat{\xi}^{(t)}) &= \sum_{(c, q, d, k) \in \mathcal{L}} \sum_{R}P(R \mid c, q, d, k) \left( c \log P(R \mid q, d) + (1 - c) \log P(R \mid q, d) \right). \end{align} $$

次に $\theta$ の第 $k$ 要素 $\theta_{k}$ の更新式を求める。$Q_{\theta}$ を $\theta_{k}$ で偏微分した式

$$ \frac{\partial}{\partial \theta_{k}} Q_{\theta}(\theta \mid \hat{\xi}^{(t)}) = 0 $$

を満たす $\theta_{k}$ を求めれば良い。

$$ \begin{align} \frac{\partial}{\partial \theta_{k}} Q_{\theta}(\theta \mid \hat{\xi}^{(t)}) &= \frac{\partial}{\partial \theta_{k}} \sum_{(c, q, d, k') \in \mathcal{L}} \mathbb{1}(k = k') \sum_{E}P(E \mid c, q, d, k) \left( c \log P(E \mid k) + (1 - c) \log P (E \mid k) \right) \\ &= \frac{\partial}{\partial \theta_{k}} \sum_{(c, q, d, k') \in \mathcal{L}} \mathbb{1}(k = k') \left\{P(E=1 \mid c, q, d, k) \left( c \log P(E=1 \mid k) + (1 - c) \log P (E=1 \mid k) \right) + P(E=0 \mid c, q, d, k) \left( c \log P(E=0 \mid k) + (1 - c) \log P (E = 0 \mid k) \right) \right\} \\ &= \frac{\partial}{\partial \theta_{k}} \sum_{(c, q, d, k') \in \mathcal{L}} \mathbb{1}(k = k') \left\{ P(E=1 \mid c, q, d, k) \left(c \log \theta_{k} + (1-c)\log \theta_{k}\right) + P(E=0 \mid c, q, d, k) \left( c \log (1 - \theta_{k} )+ (1-c) \log (1 - \theta_{k}) \right)\right\} \\ &= \frac{\partial}{\partial \theta_{k}} \sum_{(c, q, d, k') \in \mathcal{L}} \mathbb{1}(k = k') \left\{ P(E=1 \mid c, q, d, k) \left(c \log \theta_{k} + (1-c)\log \theta_{k}\right) + P(E=0 \mid c, q, d, k) (1-c) \log (1 - \theta_{k})\right\} (\because~ c=0~\mathrm{when}~E = 0)\\ &= 0 \cdots(1) \end{align} $$

以下簡単のため $ p = P(E=1 \mid c, q, d, k)$ とおいて変形を進める。

$$ \begin{align} (1) &\iff \sum_{(c, q, d, k') \in \mathcal{L}} \mathbb{1}(k = k') \frac{\partial}{\partial \theta_{k}} \left\{ p\left(c \log \theta_{k} + (1-c)\log \theta_{k}\right) + (1-p)(1-c)\log (1 - \theta_{k}) \right\} = 0 \\ &\iff \sum_{(c, q, d, k') \in \mathcal{L}} \mathbb{1}(k = k') \left\{ p\left(\frac{c}{\theta_{k}} + \frac{1-c}{\theta_{k}}\right) - \frac{(1-p)(1-c)}{1 - \theta_{k}} \right\} = 0 \\ &\iff \sum_{(c, q, d, k') \in \mathcal{L}} \mathbb{1}(k = k') \left\{ c\frac{p}{\theta_{k}} + (1-c) \left( \frac{p}{\theta_{k}} - \frac{1-p}{1-\theta_{k}} \right) \right\} = 0\\ &\iff \sum_{(c, q, d, k') \in \mathcal{L}} \mathbb{1}(k = k') \left\{ cp(1 - \theta_{k}) + (1-c) \left( p(1 - \theta_{k}) - (1-p) \theta_{k} \right)\right\} = 0 \\ &\iff \theta_{k} \sum_{(c, q, d, k') \in \mathcal{L}} \mathbb{1}(k = k') \left(cp + (1-c)\right) = \sum_{(c, q, d, k') \in \mathcal{L}} \mathbb{1}(k = k') \left(cp + (1-c)p\right) \end{align} $$

ここで、$c=1$ のとき $p = P(E=1 \mid c, q, d, k) = 1$より $cp + 1 - c = 1\cdot 1 + 1 - 1 = 1$, $c=0$ のとき $cp + 1 - c = 1$ より、左辺は $\theta_{k} \sum_{(c, q, d, k') \in \mathcal{L}} \mathbb{1}(k = k')$ となる。右辺に関しても $cp = c$ となることから $\sum_{(c, q, d, k') \in \mathcal{L}} \mathbb{1}(k = k') \left(c + (1-c)p\right)$ と整理出来る。以上より、$\theta_{k}$ に関する更新式

$$ \theta_{k}^{(t+1)} = \frac{\sum_{(c, q, d, k') \in \mathcal{L}} \mathbb{1}(k = k') \left(c + (1-c)P(E=1 \mid c, q, d, k)\right)}{\sum_{(c, q, d, k') \in \mathcal{L}} \mathbb{1}(k = k')} $$

が得られた。$\gamma_{q, d}$ の更新式も同様に求めることが出来る。

参考

[Wang18] Wang, X., Golbandi, N., Bendersky, M., Metzler, D., & Najork, M. (2018, February). Position bias estimation for unbiased learning to rank in personal search. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining (pp. 610-618).