MIT OCW, Machine Learning 12日目

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

モデル選択理論難しすぎ

• • Mixture models
    • • Example: Student exam model: 1-year
      • Example: student exam model: K-years
  • Collaborative filtering
  • Estimating mixtures: the EM-algorithm (期待値最大化法)
    • Complete data
    • Imcomplete data
      • Algorithm (EM)
      • Example

Mixture models

mixture model(混合モデル)は与えられたデータの曖昧さを捉えるモデルで，データの背後に有る，観測できない要因についての仮定を行う. 観測された一つのexampleを$\mathbf{x}$というベクトルで表すとする. exampleは$m$個の要因($1,...m$とする)のどれかによって生成されている$m$をcomponentの数という． $j \in \{1,..m\}$その要因であるとすると,$\mathbf{x}$の事後確率は$P(\mathbf{x}|j)$である. また$j$の頻度を$P(j)$とすると,$P(\mathbf{x}, j)=P(j)P(\mathbf{x}|j)$. 実際の$j$が何であるかは一般にはわからず，全ての$\{1, ..., m\}$について混合して，$\mathbf{x}$の確率

$$P(\mathbf{x}) = \sum_{j=1}^m P(\mathbf{x}|j)P(j)$$
となる.

Example: Student exam model: 1-year

例えば,学生たち$\{1,...,n\}$の試験の結果$D_1=\{\mathbf{x}_1,...\mathbf{x}_n\}, \mathbf{x_i}=(\text{問1の点数, 問2の点数},...)$をモデル化することを考える. 学生たちは，例えば学士での専攻のような，$D$では与えられていない要因によってことなった正答/誤答の傾向が存在すると仮定する. そのような要因が合計で$m$個(この$m$を選ぶのはmodel selectionの問題である)あって，さらに個々の学生がどれに該当するかわからないときのモデリングを考える.
それぞれの学生の点数が独立とするなら

$$P(\mathbf{x_1,...,x_n}|\theta)=\prod_{t=1}^n \left[\sum_{j=1}^m P(\mathbf{x}_t|j)P(j) \right]$$ である.

Example: student exam model: K-years

上の例で,過去$K$年間のデータがあるとする. $k$年での学生数$n_k$で,$\mathbf{x}_{k,t}$は学生$t$の$k$年目の試験結果とする($t$はただのインデックスで,$t$が同じだからといって同じ学生であるというわけではない). $m$と$P(\mathbf{x}|j)$は変わらないと仮定する. しかし学生の数$n_k$は各年でことなって,$j$の頻度$P(j)$も一定でなく,$P(j|k)$と条件付きにする. この場合のmixture modelは

$$P(\mathbf{x}|k, \theta) = \sum_{j=1}^m P(\mathbf{x}|\theta_j)P(j|k)$$
そして全てのデータ$D=\{D_1, ..., D_k\}$を考えたときの尤度は
$$L(D;\theta)=\prod_{k=1}^K\prod_{t=1}^{n_k} P(\mathbf{x}_{k,t}|k,\theta)=\prod_{k=1}^K\prod_{t=1}^{n_k} \left(\sum_{j=1}^m P(\mathbf{x}_{k,t}|\theta_j)P(j|k) \right)$$
となる.ここでの$\theta$は$\{\theta_j\},\{P(j|k)\}$をも決定する.

Collaborative filtering

mixture modelは推薦システムにもよく使われる. $n$人のユーザに$m$本の映画を推薦する問題を考える. ユーザは$m$のうち極わずかだけに点数をつけているとして,つけていない映画たちをどう評価するかを推測するのが我々の課題である. このような問題をcollaborative filtering(協調フィルタリング)という.
点数は$r_{ij} \in \{1, ...,5\}$をつけられるとする. ただし$r_{ij}$はユーザ$i$の映画$j$に対する評価とする. ユーザたちが実際に与えた評価を$D$とする. $r_{ij}$が与えられているとき$r_{ij}\in I_D$と書く．
collaborative filteringでは,ユーザと映画の両方にいくつかの種類があって,それが評価に影響すると仮定する.すなわち，それぞれの映画が”movie types” $z_m \in \{1,..,K_m\}$の分布の上にあって,ユーザも”user types” $z_u\in \{1,...,K_u\}$の分布の上にあるとする. 有る映画が,すべてのユーザにとって同じタイプであるとは考えず,それぞれの映画が，その映画に対応した特徴のバッグをもっており，それぞれのユーザごとにそのバッグからタイプを取り出すと考える. この仮定はユーザにも適用される． すなわち点数を付けるたびに，そのユーザのタイプのバッグからタイプが取り出される.
$r_{ij}\notin I_D$を以下によって推測する.
$P(z_m|j)$から映画$j$のタイプをサンプルし,また$P(z_j|i)$からユーザ$i$のタイプをサンプルする. さらに$P(r_{ij}|z_u, z_m)$から$r_{ij}$をサンプルするのである. これを全ての$z_m, z_u$に足し合わせて

$$P(r_{ij}|i, j, \theta)=\sum_{z_u=1}^{K_j}\sum_{z_m=1}^{K_m}P(r_{ij}|z_u,z_m)P(z_u|i)P(z_m|j)$$
となる. $\theta$はタイプから評価への写像$\{P(r|z_u, z_m)\}$と$\{P(z_u|i)\}, \{P(z_m|j)\}$を決定する.
$D$を与えられたときの尤度は
$$L(D;\theta) = \prod_{(i,j)\in I_D} P(r_{ij}|i,j,\theta)$$
である.
さらに,ユーザの評価のスタイルもモデルに組み込める. 例えば$3,4,5$のような高評価に偏った評価をする人や,$1$と$5$のみのような極端な評価をする人を考えることが出来る.このような評価スタイルの集合を$\{1,...,K_s\}$とする.ユーザのスタイルは全ての映画に一貫しているが，個々のユーザにどうスタイルを割り当てるかは未知とする. ユーザがスタイル$s \in \{1,...,K_s\}$をもつ確率は$P(s)$と書ける. スタイルも$\{1,..,K_s\}$すべてを$PS(s)$を重みにして総和を考えて尤度を求めるとすると,尤度$L'$は,
$$L'(D;\theta) = \prod_{i=1}^n \left[\sum_{s=1}^{K_s} P(s) \underline{\prod_{j: (i,j)\in I_D} \left( \sum_{z_u=1}^{K_u} \sum_{z_m=1}^{K_m}P(r_{ij}|z_u,z_m,s)P(z_u|i)P(z_m|j) \right)}_{(1)} \right]$$
となる.(1): user $i$がスタイル$s$によって評価する尤度
このモデルは
$$\underline{ (K_s-1)}_{P(s)} + \underline{(5-1)K_uK_mK_s}_{P(r|z_u,z_m,s)}+\underline{n(K_u-1)}_{P(z_u|i)} + \underline{m(K_m-1)}_{P(z_m|j)}$$
個のパラメータを持つ.
さらに充実したモデルでは,”missing elements”のモデル，すなわちある映画の評価がなぜなされないかもモデル化するはずである.

Estimating mixtures: the EM-algorithm (期待値最大化法)

midture modelの例をいくつか見てきた. データによく合うようにパラメータを設定する方法を論じる. $\mathbf{x}$の要因$j$が不明なので，$\{1,..,m\}$で総和を取ってきたのだが,まずは要因がわかっているモデルを考える．

Complete data

$$P(\mathbf{x}; \theta) = \sum_{j=1}^m P(j)N(\mathbf{x};\mu_j,\Sigma_j)$$
それぞれの$\mathbf{x}_t$に対応する$j_t$が既知であると仮定して議論する. $\delta(j|t) =\begin{cases} 1 \ \ (j = j_t) \\ 0 \ \ (j \neq j_t) \end{cases}$を使うと便利である． log-likelihoddは
$$\begin{aligned} l(\mathbf{x_1,...,x_n},j_1,...,j_n;\theta) &= \sum_{t=1}^n \log [P(j_t)N(\mathbf{x}; \mu_{j_t},\Sigma_{j_t})] \\ &= \sum_{t=1}^n \sum_{j=1}^m \delta(j|t) \log [P(j)N(\mathbf{x}_t; \mu_j, \Sigma_j)] \\ &= \sum_{j=1}^m (\sum_{t=1}^n \delta(j|t)) \log P(j) + \sum_{j=1}^m (\sum_{t=1}^n \delta(j|t) \log N(\mathbf{x}_t; \mu_j, \Sigma_j)) \end{aligned}$$
尤度を最大とするパラメータをハットで表すと,
$\hat{P}(j) = \frac{\hat{n}(j)}{n}, \ \ \hat{n}(j) = \sum_{t=1}^n \delta(j|t)$
$\hat{\mu}_j = \frac{1}{\hat{n}(j)} \sum_{t=1}^n \delta(j|t)\mathbf{x}_t, \ \ \hat{\Sigma}_j = \frac{1}{\hat{n}(j)} \sum_{t=1}^n \delta(j|t)(\mathbf{x}_t-\hat{\mu_j})(\mathbf{x}_t-\hat{\mu}_j)^T$
となる.このように$\{j_t\}$が既知である場合には，最尤推定は簡単に行えるとわかる.

Imcomplete data

$j_t$がわかっていない場合を考える. $\theta^{(l)}$を初期のパラメータとする. このパラメータで,ある$\mathbf{x}_t$が$j$によって生成される確率は

$$P(j|\mathbf{x}_t,\theta^{(l)})= \frac{P^{(l)}(j)N(\mathbf{x}_t; \mu^{(l)}_j, \Sigma^{(l)}_j)}{\sum_{j'=1}^m P^{(l)}(j')N(\mathbf{x_t}; \mu^{(l)}_{j'}, \Sigma^{(l)}_{j'})}=\frac{P^{(l)}(j)N(\mathbf{x}_t;\mu_j^{(l)},\Sigma_j^{(l)})}{P(\mathbf{x}_t; \theta^{(l)})}$$
$\delta(j|t)$という二値の割当の代わりに,$p^{(l)}(j|t) = P(j|\mathbf{x}_t, \theta^{(l)})$という”soft”な割当を使うのである. この割当は$\theta^{(l)}$によっており,$\theta$を更新していくたびに変化していく.
これらの結果から,Expectation Maximization algorithm (EM)が導かれる. EMは全てのmixture modelと更に広範なモデルに適用できる. Gaussian mixtureでのEM-algorithmは以下の通り.

Algorithm (EM)

(step1)
$\theta^{(0)}$を定める. 例えば$P^{(0)}(j)=1/m$とし,$\mu^{(0)}_j$をランダムに選んだ$D$の点に,$\Sigma_j^{(0)}$を$D$の分散行列としたりなどする.
(E-step)
$p^{(l)}(j|t) = P(j|\mathbf{x}_t, \theta^{(l)})$を$\theta^{(l)}$によって評価する.
(M-step)
パラメータを，

$$\begin{aligned} P^{(l+1)}(j) &= \frac{\hat{n}(j)}{n}, \ \ \hat{n}(j)=\sum_{t=1}^n p^{(l)}(j|t) \\ \mu_j^{(l+1)} &= \frac{1}{\hat{n}(j)} \sum_{t=1}^n p^{(l)} (j|t) \mathbf{x}_t \\ \Sigma_j^{(l+1)} &= \frac{1}{\hat{n}(j)}\sum_{t=1}^n p^{(l)} (j|t) (\mathbf{x}_t - \mu^{(l+1)}_j)(\mathbf{x}_t - \mu_j^{(l+1)})^T \end{aligned}$$
によって更新する.

この更新則によってlog-likelihoodは増加し,またパラメータは収束することが証明されているが, その極限では$d/d\theta l(D;\theta)=0$が成立することしか保証されていない.

Example

2つのGaussianのmixture modelを考える. fig.2 はEM-algorithmのイテレーションの様子である.