Lecture Notes > 情報基礎実験 > 対数線形モデルとHMMの半教師付学習

対数線形モデルとHMMの半教師付学習

Log Linear Model

配列データとそれに対応する隠れ状態列を明示的に\(\bar{x}=x_1,\ldots , x_T\)， \(\bar{y}=y_1,\ldots , y_T\)と書くことにする．
判別モデルとしての一般の対数線形モデルは，以下の形式に書ける．

\[ \begin{align}
p(y|x;w) = \frac{\exp{\sum_{j=1}^{J}w_jF_j(x,y)}}{Z(x,w)} \hspace{3cm} \mbox{(1)}
\end{align} \]
ここで分母は、以下のような分配関数である．
\[ \begin{align}
Z(x,w) = \sum_{y’}\exp\sum_{j=1}^{J}w_jF_j(x,y’)
\end{align} \]
与えられたデータ\(x\)に対して最尤推定\(\hat{y}^{MLE}\)を求める場合は，分母は\(x\)のみに依存して共通だから，
線形重みの部分を最大にする\(y\)を求めればよい．
\[ \begin{align}
\hat{y}^{MLE} = argmax_{y}p(y|x;w) = argmax_{y}\sum_{j=1}^{J}w_jF_j(x,y) \label{eq:mle_general_llm}
\end{align} \]

Conditional Random Field

Conditional Random Field (CRF)では， (1)式の\(F_j(,)\)を以下の形に制限する．
\[ \begin{align}
F_j(\bar{x},\bar{y}) = \sum_{t=1}^{T}f_j(y_{t-1},y_{t},\bar{x},t)
\end{align} \]
ここで、固定された\(\bar{x}， w\)に対して\(g_t(,)\)を以下のように定義する．
\[ \begin{align}
g_t(y_{t-1},y_{t})=\sum_{j=1}^{J}w_jf_j(y_{t-1},y_{t},\bar{x},t) \label{eq:def-g-crf}
\end{align} \]
すると，CRFは以下の形になる．
\[ \begin{align}
p(\bar{y}|\bar{x};w) = \frac{\exp{\sum_{t=1}^{T}g_t(y_{t-1},y_t})}{Z(\bar{x},w)} \hspace{3cm} \mbox{(2)}
\end{align} \]
式(2)における\(\bar{y}\)の最尤推定\(\hat{y}^{MLE}\)は，以下の形に書ける．
\[\begin{align}
\hat{y}^{MLE} = argmax_{\bar{y}}\sum_{j=1}^{J}w_j\sum_{t=1}^{T}f_j(y_{t-1},y_{t},\bar{x},t)
= argmax_{\bar{y}}\sum_{t=1}^{T}g_t(y_{t-1},y_{t})
\end{align} \]

このモデルの推定において最大化すべきスコア
\[ \begin{align}
\sum_{j=1}^{J}w_j F_j(\bar{x},\bar{y})
=\sum_{t=1}^{T}g_t(y_{t-1},y_t)
\end{align} \]
を最大化する\(\bar{y}\)を求めるために， Viterbi変数もどき\(V(k,v)\)を，
位置\(1\)から\(k\)までのベストスコアで位置\(k\)での状態が\(v\)である値と定義する．
以下の漸化式が得られる．
\[ \begin{eqnarray}
V(k,v) &=& \max_{y_{1}\ldots y_{k-1}}
\left[\sum_{t=1}^{k-1}g_t(y_{t-1},y_{t}) + g_k(y_{k-1},v)\right]\
&=& \max_{u}\left[V(k-1,u) + g_k(u,v)\right] \hspace{3cm} \mbox{(3)}
\end{eqnarray} \]

演習問題１

\(V(k,v)\)のViterbiアルゴリズムもどきを書き下すために、
式(3)に対応する\(V(k,v)\)の初期値を求めよ．

HMM represented as a Log Linear Model

HMMを浅井が親しみやすい記法で書くと， 以下のようになる．
\[ \begin{align}
p(\bar{x},\bar{y}|\theta)&=\prod_{t=1}^T p(y_t|y_{t-1}) p(x_t|y_t) \nonumber \\
&=\prod_{t=1}^T a_{y_t,y_{t-1}}e_{x_t,y_t} \hspace{3cm} \mbox{(4)}
\end{align} \]

両辺の対数を取って変形すると，
\begin{eqnarray}
\log{p(\bar{x},\bar{y}|\theta)}
&=&\sum_{t=1}^T \left[ \log{p(y_t|y_{t-1})} + \log{p(x_t|y_t)} \right]\\
&=&\sum_{i=1}^m \sum_{j=1}^m N^{a}{i,j}(\bar{y}) \log{a{i,j}}
+\sum_{i=1}^m \sum_{d=1}^D N^e(\bar{x},\bar{y}) \log{e_{i,d}} \hspace{3cm} \mbox{(4)}
\end{eqnarray}
ここで，
\(a_{ij}\)は状態\(i\)から\(j\)への遷移確率，
\(e_{i,d}\)は状態$i$から記号\(d\)が出力される出力確率
\(N^a_{i,j}(\bar{y})\)は状態\(i\)から状態\(j\)への遷移した回数，
\(N^\phi_{i,d}(\bar{x},\bar{y})\)は状態\(i\)から出力記号\(d\)が出力された回数
である。

演習問題２

式(4)を用いて，
HMMを判別モデルとしての対数モデルとして表現せよ．

対数線形モデルのパラメータ学習

学習データ（\(x\)と\(y\)のセット）から， 対数条件付き尤度（LCL; Log Conditional Likelihood）を最大化する$w$を求めることが目的．
LCLの偏微分は以下のようになる．
\[ \begin{eqnarray}
\frac{\partial}{\partial w_j}\log(y|x;w)
&=& F_j(x,y) – \frac{\partial}{\partial w_j}\log{Z(x,w)}\
&=& F_j(x,y) – \frac{1}{Z(x,w)}\sum_{y’}\frac{\partial}{\partial w_j}Z(x,w)
\end{eqnarray} \]
分配関数$Z(x,w)$の部分の偏微分は以下のようになる．
\[ \begin{eqnarray}
\frac{\partial}{\partial w_j}Z(x,w)
&=& \frac{\partial}{\partial w_j}\sum_{y’}\left[\exp\sum_{j’}w_{j’}F_{j’}(x,y’)\right]\\
&=& \sum_{y’}\frac{\partial}{\partial w_j}\left[\exp\sum_{j’}w_{j’}F_{j’}(x,y’)\right]\\
&=& \sum_{y’}\left[\exp\sum_{j’}w_{j’}F_{j’}(x,y’)\right]
\frac{\partial}{\partial w_j}\left[\exp\sum_{j’}w_{j’}F_{j’}(x,y’)\right]\\
&=& \sum_{y’}\left[\exp\sum_{j’}w_{j’}F_{j’}(x,y’)\right]F_{j’}(x,y’)
\end{eqnarray} \]
したがって，結局LCLの偏微分は以下のようになる．
\begin{eqnarray}
\frac{\partial}{\partial w_j}\log(y|x;w)
&=& F_j(x,y) – \frac{1}{Z(x,w)}\sum_{y’}F_{j’}(x,y’)\left[\exp\sum_{j’}w_{j’}F_{j’}(x,y’)\right]\\
&=& F_j(x,y) – \sum_{y’}F_{j’}(x,y’)\left[\frac{\exp\sum_{j’}w_{j’}F_{j’}(x,y’)}{Z(x,w)}\right]\\
&=& F_j(x,y) – \sum_{y’} F_j(x,y’)p(y’|x;w)\\
&=& F_j(x,y) – E_{y’\sim p(y’|x;w)}\left[F_j(x,y’)\right]
\end{eqnarray}

つまり，学習データ\(<x,y>\)にに対する対数条件付き尤度の(j)番目の重み\(w_j\)による偏微分は，
特徴関数の\(x\)、\(y\)に対する値（\(F(x,y)\)）から
特徴関数の\(y’\)に関する平均値を引いたものとなる．

学習データがデータセット\(T={(x,y)}\)として与えられ，
大域的な最大値においてはGradientはゼロとなるから，
\[ \begin{align}
\sum_{<x,y> \in T}F_j(x,y)=\sum_{<x,> \in T}E_{y\sim p(y|x;w)}[F_j(x,y)]
\end{align} \]

前向き後向きアルゴリズム

以下では，\(y\)，\(y’\)はシークエンスではなく，単一の状態に対応している．
確率として正規化されていないスコアを\(\alpha(t,y)\)とする．
\[ \begin{align}
\alpha(t,y)=\sum_{y’}\alpha(t-1,y’)M_t(y’,y)
\end{align} \]
ここで，
\[ \begin{align}
M_t(y’,y)=\exp \sum_{j=1}^{J}w_{j}f_{j}(y’,y,\bar{x},t)
\end{align} \]

先に定義した\(g()\)とは，
\(M_i(y’,y)= \exp g_i(y’,y)\)
という関係になっている．
\(t\)を固定して考えると，\(\alpha(t,y)\)は長さ$m$のベクトル（前向きベクトル）となっている．
初期値は
\(\alpha(0,\mbox{START})=1, \alpha(0,y)=0 \mbox{for } y\ne \mbox{START}\)
分配関数は前向きベクトルから計算出来て，
\[ \begin{align}
Z(x,w) = \sum_{y}\alpha(n,y) = \alpha(n+1,\mbox{STOP})
\end{align} \]
後向きベクトルは以下のように定義できる．
\[ \begin{align}
\beta(y,t) = \sum_{y’} \beta(y’,t+1)M_{t+1}(y,y’)
\end{align} \]
初期値は，
\(\beta(\mbox{STOP},T+1)=1\)，
\(\beta(y,T+1)=0\)， \(\mbox{for}\) \(y\ne \mbox{STOP}\)
周辺確率は，こんな感じ．
\[ \begin{eqnarray}
p(Y_t=y|x;w) &=& \frac{\alpha(t,y)\beta(y,t)}{Z(x,w)}\
p(Y_t=y, Y_{t+1}=y’|x;w) &=& \frac{\alpha(t,y)M_{t+1}(y,y’)\beta(y’,t+1)}{Z(x,w)}
\end{eqnarray} \]
学習では，
\[ \begin{eqnarray}
E_{\bar{y} \sim p(\bar{y}|x,w)}[F_j(x,\bar{y})]
&=& \sum_{t=1}^{T}E_{y_{t-1},y_t}[f_j(y_{t-1},y_t,x,t)]\\
&=& \sum_{t=1}^{T}\sum_{y_{t-1}}\sum_{y_t}p(y_{t-1},y|x;w)f_j(y_{t-1},y_t,x,t)\\
&=& \sum_{t=1}^{T}\sum_{y_{t-1}}\sum_{y_t}f_j(y_{t-1},y_t,x,t)
\frac{\alpha(t-1,y_{t-1})M_t(y_{t-1},y_t)\beta(y_t,t)}{Z(x,w)}
\end{eqnarray} \]

行列\(Q_t\),を以下のように定義し，
\[ \begin{align}
Q_t(y,y’)=f_j(y,y’,x,t)M_t(y,y’)=f_t(y,y’,x,t)\exp\sum_{j=1}^{J}w_jf_f(y,y’,\bar{x},t)
\end{align} \]
\(\alpha_t=\alpha(t,y_t)\), \(\beta_t=\beta(y_t,t)\)とおくと，
以下のように書き表せる．
\[ \begin{align}
E_{y’\sim p(y’|x;w)}[F_j(x,y’)]=\sum_{i=t}^{T}\alpha_{t-1}^{T}Q_t\beta_t
\end{align} \]

Stochastic Gradient Ascent

\[ \begin{align}
w_j := w_j + \alpha(F_j(x,y) – E_{y’\sim p(y’|x;w)}[F_j(x,y’)]
\end{align} \]
\(\alpha\) は，学習率のパラメータである．

Hybrid model for semi-supervised learning

半教師付学習を行うためのハイブリッド確率モデルを，以下のように定義する．
\[ \begin{eqnarray}
R(y|x;\Lambda, \Theta, \Gamma)
&=&\frac{\prod_{i} p_i^{D}(x,y;\lambda_i)^{\gamma_i}
\prod_{j} p_j^{G}(x,y;\theta_j)^{\gamma_j}}
{\sum_{y}\prod_i p_i^{D}(x,y;\lambda_i)^{\gamma_i}
\prod_{j}p_j^{G}(x,y;\theta_j)^{\gamma_j}}\\
&=&=\frac{\prod_{i} p_i^{D}(y|x;\lambda_i)^{\gamma_i}
\prod_{j} p_j^{G}(x,y;\theta_j)^{\gamma_j}}
{\sum_{y}\prod_i p_i^{D}(y|x;\lambda_i)^{\gamma_i}
\prod_j p_j^{G}(x,y;\theta_j)^{\gamma_j}} \hspace{3cm} \mbox{(5)}
\end{eqnarray} \]

ここで，判別モデル$p_i^{D}(y|x;\lambda_i)$が以下のように書かれることを用いた．
\[ \begin{align}
p_i^{D}(y|x;\Lambda)
= \frac{p_i^{D}(x,y;\Lambda)}
{\sum_{y}p_i^{D}(y|x;\Lambda)}
\end{align} \]

演習問題３

HMMの対数線形モデルをうまく用いて，　式(5)をHMMの場合に書き下せ．

発展課題

参考文献(3)を参考に，演習問題４のモデルの半教師付学習のアルゴリズムをスケッチせよ．

(1) Charles Elkan: Log-linear models and condiional random fields,
http://cseweb.ucsd.edu/~elkan/250B/loglinearCRFs.pdf

(2) J.Lafferty et al., Conditioal Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data,
http://www.cis.upenn.edu/~pereira/papers/crf.pdf

(3) Jun Suzuki et al.,Semi-Supervised Structured Output Learning
based on a Hybrid Generative and Discriminative Approach,
http://acl.ldc.upenn.edu/D/D07/D07-1083.pdf