\section{はじめに}
\label{sec:intro}現在，統計的言語モデルの一クラスとして確率文脈自由文法（probabilisticcontext-freegrammar;以下PCFG）が広く知られている．PCFGは文脈自由文法（context-freegrammar;以下CFG）の生成規則に確率パラメタが付与されたものと見ることができ，それらのパラメタによって生成される文の確率が規定される．しかし，すべてのパラメタを人手で付けるのはコストと客観性の点で問題がある．そこで，計算機によるコーパスからのPCFGのパラメタ推定，すなわちPCFGの訓練(training)が広く行なわれている．現在，構造つきコーパス中の規則出現の相対頻度に基づきPCFGを訓練する方法（以下，相対頻度法と呼ぶ）が広く行なわれているが，我々はより安価な訓練データとして，分かち書きされている（形態素解析済みの）括弧なしコーパスを用いる．括弧なしコーパスからのPCFGの訓練法としては，Inside-Outsideアルゴリズム\cite{Baker79,Lari90}が広く知られている（以下,I-Oアルゴリズムと略す）．I-OアルゴリズムはCYK(Cocke-Younger-Kasami)パーザで用いられる三角行列の上に構築された，PCFG用のEM(expectation-maximization)アルゴリズム\cite{Dempster77}と特徴づけることができる．I-Oアルゴリズムは多項式オーダのEMアルゴリズムであり，効率的とされているが，訓練コーパスの文の長さに対し3乗の計算時間を要するため，大規模な文法・コーパスからの訓練は困難であった．また，基になるCFGがChomsky標準形でなければならないという制約をもっている．一方，本論文では，PCFGの文法構造（基になるCFG）が所与であるときの効率的なEM学習法を提案する．提案手法はwell-formedsubstringtable（以下WFST）と呼ばれるデータ構造を利用しており，全体の訓練過程を次の2段階に分離してPCFGを訓練する．\begin{description}\item\underline{\bf構文解析}:\\はじめにパーザによって与えられたテキストコーパスもしくはタグ付きコーパス中の各文に構文解析を施し，その文の構文木すべてを得る．ただし，構文木は実際に構築せずに途中で構築されるWFSTのままでとどめておく．\item\underline{\bfEM学習}:\\上で得られたWFSTから支持グラフと呼ばれるデータ構造を抽出し，新たに導出されたグラフィカルEM（graphicalEM;以下gEMと略記）アルゴリズムを支持グラフ上で走らせる．\end{description}WFSTは構文解析途中の部分的な解析結果（部分構文木）を格納するデータ構造の総称であり~\cite{Tanaka88,Nagata99}，パーザはWFSTを参照することにより再計算を防いでいる．また，最終的にWFSTに格納されている部分構文木を組み合わせて構文木を出力する．表~\ref{tab:WFST}に各構文解析手法におけるWFSTを掲げる．なお，Fujisakiらも文法が所与であるとして，上の2段階でPCFGを訓練する方法を提案しているが\cite{Fujisaki89}，その方法ではWFSTは活用されていない．\begin{table}[b]\caption{各パーザにおけるWFST．}\label{tab:WFST}\begin{center}\begin{tabular}{|l||l|l|}\hlineパーザ&\multicolumn{1}{c|}{WFST}\\\hlineCYK法&三角行列\\Earley法&アイテム集合（Earleyチャート）の集まり\\GLR法&圧縮共有構文森(packedsharedparseforest)\\\hline\end{tabular}\end{center}\end{table}提案手法の特長は従来法であるI-Oアルゴリズムの一般化と高速化が同時に実現された点，すなわち\begin{description}\item{\bf特長1:}従来のPCFGのEM学習法の一般化となっている，\item{\bf特長2:}現実的な文法に対してはI-Oアルゴリズムに比べてEM学習が大幅に高速化される，\item{\bf特長3:}提案手法が，PCFGに文脈依存性を導入した確率言語モデル（PCFGの拡張文法\footnote{Magermanらが\cite{Magerman92}で述べている``Context-freegrammarwithcontext-sensitiveprobability(CFGwithCSP)''を指す．具体的にはCharniakらの疑似確率文脈依存文法\cite{Charniak94b}や北らの規則バイグラムモデル\cite{Kita94}が挙げられる．}と呼ぶ）に対する多項式オーダのEMアルゴリズムを包含する\end{description}点にある．先述したように，I-OアルゴリズムはCYK法のWFSTである三角行列を利用して効率的に訓練を行なう手法と捉えることができ，提案手法のCYK法とgEMアルゴリズムを組み合わせた場合がI-Oアルゴリズムに対応する．一方，提案手法でEarleyパーザや一般化LR（以下GLR）パーザと組み合わせる場合，文法構造にChomsky標準形を前提としないため，本手法はI-Oアルゴリズムの一般化となっている（{\bf特長1}）．加えて，本論文ではStolckeの確率的Earleyパーザ\cite{Stolcke95}や，PereiraとSchabesによって提案された括弧なしコーパスからの学習法\cite{Pereira92}も提案手法の枠組で扱うことができる\footnote{より正確には，文法構造が与えられている場合のPereiraとSchabesの学習法を扱う．}ことを示す．また，{\bf特長2}が得られるのは，提案手法ではがWFSTというコンパクトなデータ構造のみを走査するためである．そして，LR表へのコンパイル・ボトムアップ解析といった特長により実用的には最も効率的とされる一般化LR法~\cite{Tomita91}（以下GLR法）を利用できる点も訓練時間の軽減に効果があると考えられる．そして{\bf特長3}は提案手法の汎用性を示すものであり，本論文では北らの規則バイグラムモデル\cite{Kita94}の多項式オーダのEMアルゴリズムを提示する．本論文の構成は次の通りである．まず節~\ref{sec:PCFG}でPCFG，CYKパーザ，I-Oアルゴリズム，およびそれらの関連事項の導入を行なう．I-Oアルゴリズムと対比させるため，提案手法をCYKパーザと\gEMアルゴリズムの組合せを対象にした場合を節~\ref{sec:GEM}で記述した．{\bf特長2}を検証するため，GLRパーザとgEMアルゴリズムを組み合わせた場合の訓練時間をATR対話コーパス(SLDB)を用いて計測した．その結果を節~\ref{sec:experiment}に示す．また，{\bf特長3}を具体的に示すため，節~\ref{sec:extensions}ではPCFGの拡張文法に対する多項式オーダのEMアルゴリズムを提示する．最後に節~\ref{sec:related-work}で関連研究について述べ，{\bf特長1}について考察する．本論文で用いる例文法，例文，およびそれらに基づく構文解析結果の多くは\cite{Nagata99}のもの，もしくはそれに手を加えたものである．以降では$A,B,\ldots$を非終端記号を表すメタ記号，$a,b,\ldots$を終端記号を表すメタ記号，$\rho$を一つの終端または非終端記号を表すメタ記号，$\zeta$,$\xi$,$\nu$を空列もしくは終端記号または非終端記号から成る記号列を表すメタ記号とする．空列は$\varepsilon$と書く．一方，一部の図を除き，具体的な文法記号を$\sym{S},\sym{NP},\ldots$などタイプライタ書体で表す．また，$y_n$を第$n$要素とするリストを\$\tuple{y_1,y_2,\ldots}$で表現する．またリスト$Y=\tuple{\ldots,y,\ldots}$であるとき，$y\inY$と書く．集合$X$の要素数，記号列$\zeta$に含まれる記号数，リスト$Y$の要素数をそれぞれ$|X|$,$|\zeta|$,$|Y|$で表す．これらはどれも見た目は同じだが文脈で違いを判断できる．
\section{準備}
\label{sec:PCFG}\subsection{確率文脈自由文法}\label{sec:PCFG:PCFG}はじめに，文脈自由文法$G$を4つ組$\tuple{\Vn,\Vt,R,S}$で定義する．ただし，$\Vn$は非終端記号の集合，$\Vt$は終端記号の集合，$R$は規則の集合，$S$は開始記号$(S\in\Vn)$である．$R$中の各規則$r$は$A\to\zeta$の形をしており，記号列$\zeta'$中に非終端記号$A$が出現するとき，$A$を$\zeta$に置き換えることが可能であることを表す．我々は常に最左の非終端記号を置き換えるように規則を適用する（最左導出に固定する）．規則$r$の適用により記号列$\zeta$が$\xi$に置き換えられるとき$\zeta\rderives{r}\xi$と書く．このような置き換えを0回以上行なって$\zeta$から$\xi$が得られるとき，$\zeta\derivesstar\xi$と書く．特に，置換えが1回以上であることを強調する場合は\$\zeta\derivesplus\xi$と書く．$S$から導出可能な非終端記号列$\win$を文と呼ぶ．CFG$G$における文の集合を$G$の言語と呼び，$L_G$と書く．そして，$G$に基づくPCFGを$G(\theta)$で表す．逆に$G$を「PCFG$G(\theta)$の文法構造」と呼ぶ．$\theta$は$|R|$次元ベクトルであり，以降パラメタと呼ぶ．$\theta$の各要素は$\theta(r)$で参照され，$0\le\theta(r)\le1,\;\sum_{\zeta:(A\to\zeta)\inR}\theta(A\dto\zeta)=1$が成り立つとする($A\in\Vn,\;r\inR$)．PCFGでは「適用する規則は他に影響を受けずに選択される」と仮定される．従って\$\zeta_0\rderives{r_1}\zeta_1\rderives{r_2}\zeta_2\rderives{r_3}\cdots\rderives{r_{K}}\zeta_K$における規則の適用列$\rseq=\tuple{r_1,r_2,\ldots,r_K}$の出現確率$P(\rseq|\theta)$は\begin{equation}\textstyleP(\rseq|\theta)=\prod_{k=1}^K\theta(r_k)\label{eq:derivation-prob}\end{equation}と計算される．また，$\occ(r,\rseq)$を適用規則列$\rseq$中に\規則$r$が出現する数とすると，\begin{equation}\textstyleP(\rseq|\theta)=\prod_{r\inR}\theta(r)^{\occ(r,\rseq)}\label{eq:derivation-prob2}\end{equation}と書くこともできる．$S\derivesstar\win$を実現する適用規則列すべてから成る集合を$\trees(\win)$とおく．文$\win$は適用規則列$\rseq$から一意に定まるので，文と適用規則列の同時分布$P(\win,\rseq|\theta)$に関し\begin{equation}\textstyleP(\win,\rseq|\theta)=\left\{\begin{array}{ll}P(\rseq|\theta)&\mbox{if}\;\rseq\in\trees(\win)\\0&\mbox{otherwise}\end{array}\right.\label{eq:joint-prob}\end{equation}が成り立つ．式~\ref{eq:joint-prob}より開始記号$S$から$\win$が導出される確率$P(\win|\theta)$は次のように求まる：\begin{equation}\textstyleP(\win)=\sum_{{\rmall}\;\rseq}P(\win,\rseq|\theta)=\sum_{\rseq\in\trees(\win)}P(\rseq|\theta)\;.\label{eq:sentence-prob}\end{equation}パラメタ$\theta$が文脈より明らかなときは\$P(\rseq,\ldots|\theta)$,$P(\win,\ldots|\theta)$を各々$P(\rseq,\ldots)$,$P(\win,\ldots)$と書く．先述した規則適用の独立性に加え，以降で考えるPCFG$G(\theta)$は次を満たすとする．\begin{itemize}\item$G(\theta)$は整合的である．すなわち\$\sum_{\win\inL_G}P(\win|\theta)=1$が成り立つ．\item右辺が$\varepsilon$である規則（$\varepsilon$規則）や$A\derivesplusA$となるような$A\in\Vn$が存在しない．\end{itemize}ChiとZemanは，2番目の条件を満たす文法構造$G$と有限長の文から成る括弧なしコーパス$\corpus$が与えられたとき，I-Oアルゴリズムで得られる訓練パラメタ$\theta^{\ast}$の下でのPCFG$G(\theta^{\ast})$が整合的であることを示した~\cite{Chi98}．\subsection{コーパス・構文木}\label{sec:PCFG:corpus}平文$\win=w_1w_2\cdotsw_n\inL_G$に対して個々の$w_j$は単語である($n>0$,$j=1\ldotsn$)．$\win$に対して単語位置$d=0\ldotsn$を与える．$0\led\led'\len$について$d$と$d'$の間にある部分単語列$w_{d+1}\cdotsw_{d'}$を$\win_{d,d'}$と書く（$\win=\win_{0,n}$である）．また，（部分）単語列$w_d\cdotsw_{d'}$をリスト\$\tuple{w_d,\ldots,w_{d'}}$で表すことがある．$\win\inL_G$に対して，$\win$の構文木は\$S\derivesstar\win$の導出過程を木構造で表現したものである．我々は導出戦略を最左導出に固定しているので，$S\derivesstar\win$の適用規則列$\rseq$から$\win$の構文木$t$が一意に決まり，逆も真である．従って$P(t)=P(\rseq)$が成り立つ．先に我々は対象とするPCFGが$\varepsilon$規則をもたないこと，$A\derivesplusA$という導出が起こらないと仮定した．この仮定より，$\win$の構文木$t$の部分構文木（以下，部分木）$t'$はその根ノードの非終端記号$A$と葉ノードを構成する部分単語列の開始／終了位置の対$(d,d')$によって一意に定まるので，以降，我々は部分木$t'$をラベル$A(d,d')$で参照する．$\win$の構文木$t$は，葉ノードを除く$t$の部分木ラベルから成る集合$\labels(t)$（$t$のラベル集合と呼ぶ）と同一視できる．また，$(d,d')$は一つの括弧づけに相当する．$\brackets(t)\defined\{(d,d')\midA(d,d')\in\labels(t)\}$と定め，$t$の括弧集合と呼ぶ．また，$A\dto\rho_1\rho_2\cdots\rho_M$の展開によって得られた$\rho_1,\rho_2,\ldots,\rho_M$を根とする部分木$\rho_m(d_{m-1},d_m)$を考える（図~\ref{fig:parse-tree}）．このとき$A(d_0,d_M)@\rho_m(d_{m-1},d_m)$なる部分木に関する半順序関係$@$を導入する($m=1\ldotsM$)．この関係を以降では「$A(d_0,d_M)$は$\rho_m(d_{m-1},d_m)$の親である」，また逆に「$\rho_m(d_{m-1},d_m)$は$A(d_0,d_M)$の子である」などということがある．そして親$A(d_0,d_M)$とその子をすべてまとめて\begin{equation}A(d_0,d_M)@\rho_1(d_0,d_1)\rho_2(d_1,d_2)\cdots\rho_M(d_{M-1},d_M)\label{eq:parent-children}\end{equation}と表し，これを「部分木の親子対」と呼ぶことにする．構文木$t$中に出現する部分木の親子対をすべて集めた集合を$\wfst(t)$で表す．構文木$t$に対応する適用規則列$\rseq$に対して\$\labels(\rseq)$,$\brackets(\rseq)$,$\wfst(\rseq)$をそれぞれ$\labels(t)$,$\brackets(t)$,$\wfst(t)$と同一視する．\begin{figure}[t]\atari(51,32)\caption{部分木の親子対．}\label{fig:parse-tree}\end{figure}PCFGの訓練用のコーパスとして我々は(1)構造つきコーパス(labeledcorpus)，(2)完全括弧つきコーパス(fullybracketedcorpus)，(3)部分括弧つきコーパス(partiallybracketedcorpus)，(4)括弧なしコーパス(unbracketedcorpus)の4つを考える．我々は訓練法として最尤推定法(maximumlikelihoodestimation)を考えており，$N$文を含むコーパス$\corpus\defined\tuple{c_1,c_2,\ldots,c_N}$はPCFG$G(\theta)$に基づく独立な$N$回のサンプリング導出の結果であると仮定する．$\win_\ell$,$\rseq_\ell$を$\ell$回目のサンプリングで得られた平文および適用規則列とすると($\ell=1\ldotsN$)，$\corpus$が構造つきコーパスのとき$c_\ell=\tuple{\win_\ell,\labels(\rseq_\ell)}$,完全括弧つきコーパスのとき$c_\ell=\tuple{\win_\ell,\brackets(\rseq_\ell)}$,部分括弧つきコーパスのとき$c_\ell=\tuple{\win_\ell,\brackets_\ell}$,括弧なしコーパスのとき$c_\ell=\win_\ell$となる($\win_\ell\inL_G$,$\rseq\in\trees(\win_\ell)$,$\brackets_\ell\subseteq\brackets(\rseq_\ell)$)．$\win_\ell$の部分単語列を\$\win^{(\ell)}_{d,d'}$とおき$(0\led<d'\len_\ell)$，$\win_\ell$の$d$番目の単語を$w^{(\ell)}_d$とおく．ただし$n_\ell\defined|\win_\ell|$である．\subsection{CYKパーザ}\label{sec:PCFG:CYK}CYKパーザはChomsky標準形であるCFGに適用可能なパーザである．我々は括弧なしコーパス$\corpus$中の文$\win_\ell$に対して\$n_\ell\timesn_\ell$の三角行列$T^{(\ell)}$を用意する\footnote{通常，三角行列の各行と各列に振られる番号は（単語位置ではなく）単語そのものに振られた番号であるが，本論文では他の記法と整合をとるために行番号を1つずつ減らす．}($n_\ell=|\win_\ell|$)．$d$行$d'$列の要素$T_{d,d'}$には部分単語列$\win_{d,d'}$に対する解析結果が格納される．CYKパーザを実現する手続き$\proc{CYK-Parser}$を図~\ref{alg:CYK}に示す．対角要素から順に部分木を組み上げ（行~\ref{list:CYK:fill-diagonal:begin}--\ref{list:CYK:fill-non-diag:end}），$T_{0,n_\ell}$に$S(0,n_\ell)@\;\cdot$が含まれていたら解析が成功したものとし，含まれていなかったら失敗したものとする（行~\ref{list:CYK:accept}）．解析が成功したら$T_{0,n_\ell}$に含まれる$S(0,n_\ell)@\;\cdot$から順に部分木の親子対を辿って構文木が取り出される．図~\ref{gram:ichiro-CNF}に示したCFG$G1$において文$\win=\tuple{急いで,走る,一郎,を,見た}$に対する三角行列を図~\ref{fig:CYK-table}に示す．図~\ref{fig:CYK-table}の○印のついた部分木の親子から図~\ref{fig:parse-tree-ichiro-CNF}の構文木$t1$が取り出され，●印のついた部分木の親子から$t2$が取り出される．\begin{figure}[t]\begin{listing}\item\rw{procedure}$\proc{CYK-Parser}(\corpus)$\rw{begin}\itemi\rw{for}$\ell:=1$\rw{to}$N$\rw{do}\rw{begin}\itemiiPrepare$(n_\ell\timesn_\ell)$triangularmatrix$T^{(\ell)}$;\itemii\rw{for}$d:=0$\rw{to}$n_\ell-1$\rw{do}\q\q\progcomment{三角行列の対角要素から始める}\label{list:CYK:fill-diagonal:begin}\itemiii$T^{(\ell)}_{d,d+1}:=\{A(d,d+1)@w_{d+1}^{(\ell)}(d,d+1)\mid(A\dtow_{d+1})\inR\}$;\label{list:CYK:fill-diagonal:end}\itemii\rw{for}$k:=2$\rw{to}$n_\ell$\rw{do}\q\q\progcomment{三角行列の非対角要素について計算}\label{list:CYK:fill-non-diag:begin}\itemiii\rw{for}$d:=0$\rw{to}$n_\ell-k$\rw{do}\itemiiii$T_{d,d+k}^{(\ell)}:=\bigcup_{k'=1}^{k-1}\bigl\{A(d,d+k)@B(d,d\!+\!k')C(d\!+\!k',d\!+\!k)\;\big|\;(A\dtoBC)\inR,$\item\hfill$(B(d,d+k')@\;\cdot)\inT_{d,d+k'}^{(\ell)},(C(d+k',d+k)@\;\cdot)\inT_{d+k',d+k}^{(\ell)}\bigr\}$;\label{list:CYK:fill-non-diag:end}\itemii\rw{if}$(S(0,n_\ell)@\;\cdot)\inT_{0,n_\ell}^{(\ell)}$\rw{then}accept\rw{else}reject\label{list:CYK:accept}\itemi\rw{end}\item\rw{end}.\end{listing}\caption{CYKパーザ．}\label{alg:CYK}\end{figure}\begin{figure}[t]\centerline{\small\def\arraystretch{}\begin{tabular}{rlrlrl}\multicolumn{6}{l}{$G1:$}\\$(1)$&$\sym{S}\dto\sym{PP}\;\sym{V}$&$(6)$&$\sym{NP}\dto\sym{V}\;\sym{N}$&$(10)$&$\sym{N}\dto\sym{一郎}$\\$(2)$&$\sym{S}\dto\sym{ADV}\;\sym{VP}$&$(7)$&$\sym{PP}\dto\sym{NP}\;\sym{P}$&$(11)$&$\sym{P}\dto\sym{を}$\\$(3)$&$\sym{VP}\dto\sym{PP}\;\sym{V}$&$(8)$&$\sym{PP}\dto\sym{N}\;\sym{P}$&$(12)$&$\sym{V}\dto\sym{走る}$\\$(4)$&$\sym{VP}\dto\sym{ADV}\;\sym{V}$&$(9)$&$\sym{ADV}\dto\sym{急いで}$&$(13)$&$\sym{V}\dto\sym{見た}$\\$(5)$&$\sym{NP}\dto\sym{VP}\;\sym{N}$\\\end{tabular}}\caption{文脈自由文法の例$G1$．}\label{gram:ichiro-CNF}\end{figure}\begin{figure}[t]\atari(140,42)\caption{$G1$と文$\tuple{急いで,走る,一郎,を,見た}$に対する三角行列．}\label{fig:CYK-table}\end{figure}\begin{figure}[t]\atari(99,36)\caption{三角行列から取り出された2つの構文木．}\label{fig:parse-tree-ichiro-CNF}\end{figure}\subsection{Inside-Outsideアルゴリズム}\label{sec:PCFG:IO}先にも述べたように，我々はPCFGのパラメタをコーパス$\corpus=\tuple{c_1,c_2,\ldots,c_N}$から最尤推定法に基づき訓練することを考えている．$\corpus$が構造つきコーパスの場合，相対頻度法で得られる各規則$r$の相対出現頻度が最尤推定値となるので，これを$r$の訓練パラメタ$\theta^{\ast}(r)$とすればよい．しかし，構造つきコーパスの作成コストを考えると，より安価な括弧なしコーパスしか利用できない場合が十分考えられる．括弧なしコーパスでは構文構造が明らかでないため，相対頻度法が適用できず，代わりにI-OアルゴリズムというPCFGに特化された形のEMアルゴリズムが広く知られている．I-Oアルゴリズムは，括弧なしコーパス$\corpus=\tuple{\win_1,\win_2,\ldots,\win_N}$が与えられたときに尤度$\prod_{\ell=1}^NP(\win_\ell\mid\theta)$あるいはその対数$\sum_{\ell=1}^N\logP(\win_\ell\mid\theta)$（対数尤度）を局所的に最大にする$\theta^{\ast}$を見つける．つまりI-Oアルゴリズムもまた最尤推定法である．\cite{Lari90}をはじめとする多くの文献の記述では，文法構造$G$のうち規則集合$R$を明示的に与えず，終端記号集合$\Vt$と非終端記号集合$\Vn$を与えた場合を考えている．提案手法との対比のため，本節では$R$を明示的に与えた場合のI-Oアルゴリズムを記述する．$\Vt$と$\Vn$のみを与えた場合のI-Oアルゴリズムは\begin{equation}\Rmax(\Vn,\Vt)\defined\left\{A\dtoBC\;\left|\;A,B,C\in\Vn\right.\right\}\;\cup\;\left\{A\dtoa\;\left|\;A\in\Vn,a\in\Vt\right.\right\}\label{eq:Rmax}\end{equation}（以下では$\Rmax$と略すことがある）を考え，規則集合を$R=\Rmax(\Vn,\Vt)$として与えた場合と同一である．ただし，いずれの場合でも$R$はChomsky標準形でなければならない．\cite{Lari90}では規則集合$R$を含めた学習を目的にI-Oアルゴリズムを使用しているが，我々はパラメタ$\theta$の学習に焦点を絞る．I-Oアルゴリズムの中心は内側確率$P(A\derivesstar\win_{d,d'}^{(\ell)})$と外側確率$P(S\derivesstar\win_{0,d}^{(\ell)}A\win_{d',n_\ell}^{(\ell)})$という2つの確率値の計算である($\ell=1\ldotsN$,$A\in\Vn$,$0\led<d'\len_\ell$)．各確率値を配列変数$\beta_{d,d'}^{(\ell)}[A]$,$\alpha_{d,d'}^{(\ell)}[A]$に格納する．これらの配列変数はCYKアルゴリズムで用いた三角行列$T_{d,d'}$中に設けられているものとする．$\win^{(\ell)}_{0,n_\ell}=\win_\ell$より\$\beta_{0,n_\ell}^{(\ell)}[S]$に文$\win_\ell$の生起確率$P(S\derivesstar\win_\ell)$が格納される点に注意する．\begin{figure}[b]\begin{listing}\item\rw{procedure}$\proc{Get-Beta}()$\rw{begin}\itemi\rw{for}$\ell:=1$\rw{to}$N$\rw{do}\rw{begin}\itemii\rw{for}$d:=0$\rw{to}$n_\ell-1$\rw{do}\q\progcomment{三角行列の対角要素について計算}\itemiii\rw{foreach}$A$suchthat$(A\dtow_{d+1}^{(\ell)})\inR$\rw{do}\itemiiii$\beta_{d,d+1}^{(\ell)}[A]:=\theta(A\dtow_{d+1}^{(\ell)})$;\label{list:get-beta:calc-beta-diagonal}\itemii\rw{for}$k:=2$\rw{to}$n_\ell$\rw{do}\q\progcomment{三角行列の非対角要素について計算}\itemiii\rw{for}$d:=0$\rw{to}$n_\ell-k$\rw{do}\itemiiii\rw{foreach}$A\in\Vn$\rw{do}\itemiiiii$\beta_{d,d+k}^{(\ell)}[A]:=\sum_{B,C:(A\toBC)\inR}\theta(A\dtoBC)\sum_{k'=1}^{k-1}\beta_{d,d+k'}^{(\ell)}[B]\beta_{d+k',d+k}^{(\ell)}[C]$\label{list:get-beta:calc-beta}\itemi\rw{end}\item\rw{end}.\end{listing}\begin{listing}\item\rw{procedure}$\proc{Get-Alpha}()$\rw{begin}\itemi\rw{for}$\ell:=1$\rw{to}$N$\rw{do}\rw{begin}\itemii$\alpha_{0,n_\ell}^{(\ell)}[S]:=1$;\q\progcomment{右上隅の$S$については特別に1に初期化}\label{list:get-alpha:init:end}\label{list:get-alpha:init:s}\itemii\rw{for}$k:=n_\ell$\rw{downto}$2$\rw{do}\label{list:get-alpha:inverse-for}\itemiii\rw{for}$d:=0$\rw{to}$n_\ell-k$\rw{do}\itemiiii\rw{foreach}$B\in\Vn$\rw{do}\itemiiiii$\alpha_{d,d+k}^{(\ell)}[B]:=\sum_{A,X:(A\toBX)\inR}\theta(A\dtoBX)\sum_{k'=k+1}^{n_\ell-d}\alpha_{d,d+k'}^{(\ell)}[A]\beta_{d+k,d+k'}^{(\ell)}[X]$\label{list:get-alpha:calc-op:begin}\itemiiiiiiiiii$+\sum_{A',Y:(A'\toYB)\inR}\theta(A'\dtoYB)\sum_{k'=1}^d\alpha_{d-k',d+k}^{(\ell)}[A']\beta_{d-k',d}^{(\ell)}[Y]$\label{list:get-alpha:calc-op:end}\itemi\rw{end}\item\rw{end}.\end{listing}\caption{（上）内側確率の計算ルーチン$\proc{Get-Beta}$，（下）外側確率の計算ルーチン$\proc{Get-Alpha}$．}\label{alg:get-beta-alpha}\end{figure}内側確率と外側確率を計算する手続き$\proc{Get-Beta}$,$\proc{Get-Alpha}$を図~\ref{alg:get-beta-alpha}に示す．記述を簡単にするため，配列変数$\alpha_{d,d'}^{(\ell)}[\cdot]$および$\beta_{d,d'}^{(\ell)}[\cdot]$は手続きが呼び出される度に0に初期化されるものとする．$\proc{Get-Beta}$はCYKパーザにおいて部分木を組み上げるのと同じように，三角行列の対角要素から出発し，右上隅$\beta_{0,n_\ell}^{(\ell)}[\cdot]$に至るまで段階的に内側確率を計算していく．また，逆に$\proc{Get-Alpha}$では右上隅$\alpha_{0,n_\ell}^{(\ell)}[\cdot]$から対角要素に向かって外側確率を計算する．このように内側・外側確率は動的計画法(dynamicprogramming)に基づき，一方向に従って計算が進められる．内側・外側確率を計算し終ったら，コーパス$\corpus$が与えられた下での規則$A\dtoBC$,$A\dtoa$の適用回数の条件つき期待値（以下，期待適用回数という）が次のように計算される:{\small\begin{eqnarray}\eta[A\dtoBC]&:=&\sum_{\ell=1}^N\frac{1}{\beta_{0,n_\ell}^{(\ell)}[S]}\sum_{k=2}^{n_\ell}\sum_{d=0}^{n_\ell-k}\sum_{k'=1}^{k-1}\theta(A\dtoBC)\alpha_{d,d+k}^{(\ell)}[A]\beta_{d,d+k'}^{(\ell)}[B]\beta_{d+k',d+k}^{(\ell)}[C]\label{eq:eta-ABC},\\\eta[A\dtoa]&:=&\sum_{\ell=1}^N\frac{1}{\beta_{0,n_\ell}^{(\ell)}[S]}\sum_{d=0}^{n_\ell-1}\theta(A\dtoa)\alpha_{d,d+1}^{(\ell)}[A].\label{eq:eta-Aa}\end{eqnarray}}\noindent更に，上で計算された期待値からパラメタ$\theta(A\dto\zeta)$が更新（再推定）される:\begin{equation}\textstyle\theta(A\dto\zeta):=\eta[A\dto\zeta]\Big/\sum_{\zeta':(A\to\zeta')\inR}\eta[A\dto\zeta'].\label{eq:update}\end{equation}I-Oアルゴリズムでは，まず$\theta$を適当な値に初期化し，次いで手続き$\proc{Get-Beta}$,$\proc{Get-Alpha}$および式~\ref{eq:eta-ABC},~\ref{eq:eta-Aa},~\ref{eq:update}によって\$\theta$を更新する．そして，このように更新を繰り返すと対数尤度\$\sum_{\ell=1}^N\logP(\win_\ell)=\sum_{\ell=1}^N\log\beta_{0,n_\ell}^{(\ell)}[S]$が単調増加しながら最終的には収束する．収束したら，そのときのパラメタの値を最終的な推定値としてI-Oアルゴリズムは終了する．ここで，I-Oアルゴリズムの計算量を考える．収束までのパラメタ更新回数は初期値に依存するため，事前には分からない．従って1回のパラメタ更新に必要な計算量をI-Oアルゴリズムの計算量とする．非終端記号集合$\Vn$,終端記号集合$\Vt$を固定した場合の最悪計算量を測る場合には$R=\Rmax(\Vn,\Vt)$の場合を考えればよい．訓練コーパス$\corpus$に対して最長の文の長さを$L$とする．手続き$\proc{Get-Beta}$,$\proc{Get-Beta}$（図~\ref{alg:get-beta-alpha}）中の{\bffor},{\bfforeach}ループと$\sum$の引数に注目すれば，I-Oアルゴリズムの最悪計算量は$O(|\Vn|^3L^3)$であることが容易に分かる．\subsection{Inside-Outsideアルゴリズムに関する考察}\label{sec:PCFG:IO-problems}アルゴリズム中で最もコストが高いのは，$\proc{Get-Beta}$行~\ref{list:get-beta:calc-beta}における内側確率の計算，$\proc{Get-Alpha}$行~\ref{list:get-alpha:calc-op:begin}--\ref{list:get-alpha:calc-op:end}における外側確率の計算である．$\proc{Get-Beta}$行~\ref{list:get-beta:calc-beta}において図~\ref{fig:get-beta-alpha}(1)という状況すべてを考慮して内側確率が計算される．一方，$\proc{Get-Alpha}$の行~\ref{list:get-alpha:calc-op:begin}--\ref{list:get-alpha:calc-op:end}における右辺第1項，第2項ではそれぞれ図~\ref{fig:get-beta-alpha}(2),(3)という状況がすべて考慮されている．考えられるすべての状況について計算をすすめるという意味でI-Oアルゴリズムの動作は仮説駆動（トップダウン）型パーザの動作と同じである．一般に仮説駆動型は入力文$\win_\ell$の情報とは無関係に計算をすすめるために効率が悪いとされている．文法構造が与えられていてもI-Oアルゴリズムの計算速度が低いのは，仮説駆動型であることが原因であると考えられる．そもそもI-Oアルゴリズムは\begin{equation}\eta[r]=\sum_{\ell=1}^N\sum_{{\rmall}\;\rseq}P(\rseq|\win_\ell)\occ(r,\rseq)=\sum_{\ell=1}^N\frac{1}{P(\win_\ell)}\sum_{{\rmall}\;\rseq}P(\win_\ell,\rseq)\occ(r,\rseq)\label{eq:naive-eta}\end{equation}という規則$r$の期待適用回数$\eta[r]$の計算を\begin{equation}\eta[r]\;=\;\theta(r)\cdot\sum_{\ell=1}^N\frac{1}{P(\win_\ell)}\frac{\partialP(\win_\ell)}{\partial\theta(r)}\;=\;\theta(r)\cdot\sum_{\ell=1}^N\frac{1}{P(\win_\ell)}\frac{\partial}{\partial\theta(r)}\sum_{{\rmall}\;\rseq}P(\win_\ell,\rseq)\label{eq:naive-eta2}\end{equation}から得られる手続き$\proc{Get-Beta}$,$\proc{Get-Alpha}$および式~\ref{eq:eta-ABC},~\ref{eq:eta-Aa}によって効率化したものである~\cite{Lafferty93}\footnote{\cite{Lafferty93}ではコーパスサイズ$N=1$の場合が説明されている．}．ただし，節~\ref{sec:PCFG:PCFG}で定めたように\$\occ(r,\rseq)$は規則列$\rseq$に出現する規則$r$の数である．式~\ref{eq:naive-eta2}で，$r=(A\dtoBC)$とおいたとき，I-Oアルゴリズムでは\$\frac{\partial}{\partial\theta(A\toBC)}\sum_{{\rmall}\;\rseq}P(\win_\ell,\rseq)$を次のように計算する（添字の${\cdot}_{\ell}$,${\cdot}^{(\ell)}$は省略）．\begin{eqnarray}&&\frac{\partial}{\partial\theta(A\toBC)}\sum_{\mbox{\footnotesizeall$\rseq$}}P(\win,\rseq)\nonumber\\&&\q\q\q=\frac{\partial}{\partial\theta(A\toBC)}\sum_{\mbox{\footnotesizeall$\rseq$s.t.$A\toBC$appearsin$\rseq$}}\iq\iqP(\win,\rseq)\nonumber\\&&\q\q\q=\frac{\partial}{\partial\theta(A\toBC)}\sum_{d,k,k'}\sum_{\mbox{\footnotesize\begin{tabular}{l}all$\rseq$s.t.$A\toBC$appearsin$\rseq$\\\qwiththeposition$(d,d+k',d+k)$\end{tabular}}}\iq\iq\iq\iqP(\win,\rseq)\label{eq:with-position}\\&&\q\q\q=\frac{\partial}{\partial\theta(A\toBC)}\sum_{d,k,k'}P(S\derivesstar\win_{0,d}A\win_{d+k,n})\theta(A\dtoBC)\cdot\nonumber\\&&\q\q\q\q\q\q\q\q\q\q\q\q\qP(B\derivesstar\win_{d,d+k'})P(C\derivesstar\win_{d+k',d+k})\nonumber\\&&\q\q\q=\sum_{d,k,k'}P(S\derivesstar\win_{0,d}A\win_{d+k,n})P(B\derivesstar\win_{d,d+k'})P(C\derivesstar\win_{d+k',d+k})\end{eqnarray}式~\ref{eq:with-position}の変形は入力文$\win$や実際の構文木$t\in\trees(\win)$とは無関係に行なわれており，I-Oアルゴリズムが仮説駆動型であるというのはこの点に由来する．\begin{figure}[t]\atari(115,26)\caption{内側確率，外側確率の計算において想定している状況（$n=n_\ell$とおいている）．}\label{fig:get-beta-alpha}\end{figure}それに対し，式~\ref{eq:joint-prob}より式~\ref{eq:naive-eta}を下の式~\ref{eq:naive-eta3}に変形し，構文木情報$\trees$を直接利用する方法を考える．$\trees$はパーザを利用することによって事前に獲得しておく．また，式~\ref{eq:naive-eta3}はFujisakiらの計算方法\cite{Fujisaki89}に他ならない．\begin{equation}\eta[r]=\sum_{\ell=1}^N\frac{1}{P(\win_\ell)}\sum_{\rseq\in\trees(\win_\ell)}P(\rseq)\occ(r,\rseq)\label{eq:naive-eta3}\label{eq:Fujisaki-eta}\end{equation}式~\ref{eq:naive-eta3}を用いればI-Oアルゴリズムのように$\psi$と無関係な部分を計算することはなくなる．ただし，一般に$|\trees(\win)|$は文長$|\win|$に対して指数オーダになってしまうため，これをそのまま計算するのは現実的ではない．提案手法ではI-Oアルゴリズムのように再計算を防ぐ仕組みを取り入れ，パーザのもつWFSTを利用して式~\ref{eq:naive-eta3}を効率的に計算する．従って，提案手法をFujisakiらの方法とI-Oアルゴリズム双方の長所を取り入れた方法と見ることもできる．
\section{提案手法}
\label{sec:GEM}提案手法の概要を図~\ref{fig:scheme}に示す．入力として確率文脈文法$G(\theta)$の文法構造\$\tuple{\Vn,\Vt,R,S}$と括弧なしコーパス$\corpus$が与えられるものとする．そして訓練パラメタ$\theta$を出力として返す．提案手法において，我々は全体の訓練過程を構文解析とEM学習に分離する．はじめに我々はパーザで$\corpus$中の各文$\win_\ell$をすべて解析する．すると$\trees(\win_\ell)$を細切れにした，しかし$\trees(\win_\ell)$と等価な構文情報$\tuple{O_\ell,\subtrees_\ell}$がパーザのWFSTに格納されているので，これらを抽出する．$\tuple{O_\ell,\subtrees_\ell}$を表現するデータ構造を支持グラフと呼ぶ．次に，支持グラフに基づきgEMアルゴリズムを動作させ$\theta$を得る．図~\ref{gram:ichiro-CNF}のCFG$G1$と文\$\win_\ell=\tuple{急いで,走る,一郎,を,見た}$の例を考えると，支持グラフは図~\ref{fig:CYK-table}において○印と●印がついた部分木の親子から得られる．この例から分かるように，文法によっては\gEMアルゴリズムで参照する支持グラフは三角行列全体に比べて非常に小さくなる可能性があり，その場合は三角行列全体を走査しなければならない\I-Oアルゴリズムに比べ大幅な速度向上が得られる（提案手法の{\bf特長2}）．\begin{figure}[t]\atari(83,56)\caption{提案手法の概要．}\label{fig:scheme}\end{figure}\subsection{準備}\label{sec:GEM:preliminary}提案手法を記述する前に形式化を行なう．$\ell=1\ldotsN$について以下をおこなう．まず，$\wfst_\ell\defined\bigcup_{\rseq\in\trees(\win_\ell)}\wfst(\rseq)$,$V_\ell\defined\bigcup_{\rseq\in\trees(\win_\ell)}\labels(\rseq)=\{\tau\mid\tau@\;\cdot\;\in\wfst_\ell\}$と定める\footnote{$\labels(\rseq)$および$\wfst(\rseq)$については節~\ref{sec:PCFG:corpus}で定めたとおりである．}．そして，$V_\ell$の要素を\$\tau_k@\tau_{k_1}\tau_{k_2}\cdots\tau_{k_M}\in\wfst_\ell\Rightarrowk<k_1,k_2,\ldots,k_M$を満たすように並べた$\tuple{\tau_1,\tau_2,\ldots,\tau_{|V_\ell|}}$を\$O_\ell$とする．また，次を導入する．\begin{eqnarray}\subtrees_\ell(A(d,d'))&\defined&\left\{E\left|\begin{array}{l}A(d,d')@\rho_1(d_0,d_1)\rho_2(d_1,d_2)\cdots\rho_M(d_{M-1},d_M)\in\wfst_\ell,\\E=\{\rho_m(d_{m-1},d_m)\midm=1\ldotsM\}\\\q\q\q\q\cup\;\{A\dto\rho_1\rho_2\cdots\rho_M\},\qd=d_0,\;d'=d_M\end{array}\right.\right\}\end{eqnarray}$\wfst_\ell$はコーパス中の文$\win_\ell$の構文木のいずれかに現れる部分木の親子対の集合である．同様に$V_\ell$は$\win_\ell$の構文木のいずれかに現れる部分木ラベルの集合である．$O_\ell$は$V_\ell$の要素を\$\wfst_\ell$中の半順序関係（親子関係）$@$を満たすように順序づけたものである．$O_\ell$の第一要素$\tau_1$は必ず$S(0,n_\ell)$になる．$\subtrees_\ell$は部分木と規則の論理的な関係を表現する．例えば，\[\subtrees_\ell(A(d,d'))=\bigl\{\;\{A\dtoB_1C_1,\;B_1(d,d''_1),\;C_1(d''_1,d')\},\;\{A\dtoB_2C_2,\;B_2(d,d''_2),\;C_2(d''_2,d')\}\;\bigr\}\]に対しては，「$\win_\ell$に対して部分木$A(d,d')$を作るためには，規則$A\dtoB_1C_1$を適用し，部分木$B_1(d,d''_1)$と部分木\$C_1(d''_1,d')$を作る，もしくは規則$A\dtoB_2C_2$を適用し，部分木$B_2(d,d''_2)$と部分木$C_2(d''_2,d')$を作る，のいずれかである（他の場合はあり得ない）」と解釈する．$O_\ell$と$\subtrees_\ell$は次節で説明する支持グラフを構成する．例として，図~\ref{gram:ichiro-CNF}のCFG$G1$と\$\win_\ell=\tuple{急いで,走る,一郎,を,見た}$に対して図~\ref{fig:parse-tree-ichiro-CNF}の2つの構文木$t1$,$t2$を考える．各々に対応する適用規則列を$\rseq_1,\rseq_2$とおくと，$\trees(\win_\ell)=\{\rseq_1,\rseq_2\}$である．このとき$\wfst_\ell$は{\small\begin{eqnarray*}\wfst_\ell&=&\wfst(\rseq_1)\cup\wfst(\rseq_2)\\&=&\{\;\sym{S}(0,5)@\sym{PP}(0,4)\sym{V}(4,5),\;\sym{PP}(0,4)@\sym{NP}(0,3)\sym{P}(3,4),\;\sym{NP}(0,3)@\sym{VP}(0,2)\sym{N}(2,3),\\&&\q\sym{VP}(0,2)@\sym{ADV}(0,1)\sym{V}(1,2),\;\sym{V}(4,5)@\sym{見た}(4,5),\;\sym{P}(3,4)@\sym{を}(3,4),\;\sym{N}(2,3)@\sym{一郎}(2,3),\\&&\q\sym{V}(1,2)@\sym{走る}(1,2),\;\sym{ADV}(0,1)@\sym{急いで}(0,1)\;\}\\&&\cup\;\{\;\sym{S}(0,5)@\sym{ADV}(0,1)\sym{VP}(1,5),\;\sym{ADV}(0,1)@\sym{急いで}(0,1),\;\sym{VP}(1,5)@\sym{PP}(1,4)\sym{V}(4,5),\\&&\q\q\sym{PP}(1,4)@\sym{NP}(1,3)\sym{P}(3,4),\;\sym{NP}(1,3)@\sym{V}(1,2)\sym{N}(2,3),\;\sym{V}(1,2)@\sym{走る}(1,2),\\&&\q\q\sym{N}(2,3)@\sym{一郎}(2,3),\;\sym{P}(3,4)@\sym{を}(3,4),\;\sym{V}(4,5)@\sym{見た}(4,5)\;\}\end{eqnarray*}}\noindentとなる．また，$O_\ell$は一意には決まらないが，どの場合でも第一要素は必ず$\sym{S}(0,5)$になる点に注意する．例えば下のような$O_\ell$が考えられる．{\small\[\begin{array}{l}O_\ell=\langle\sym{S}(0,5),\sym{VP}(1,5),\sym{PP}(1,4),\sym{NP}(1,3),\sym{V}(4,5),\sym{PP}(0,4),\sym{P}(3,4),\\\q\q\q\sym{NP}(0,3),\sym{N}(2,3),\sym{VP}(0,2),\sym{V}(1,2),\sym{ADV}(0,1)\rangle\end{array}\]}\noindentまた$\subtrees_\ell$を$O_\ell$の順に示す．\begin{small}\[{\arraycolsep=4pt\begin{array}{lll|lll}\subtrees_\ell(\sym{S}(0,5))&=&\{\;\{\sym{S}\dto\sym{PP}\;\sym{V},\;\sym{PP}(0,4),\;\sym{V}(4,5)\},&\subtrees_\ell(\sym{NP}(0,3))&=&\{\;\{\sym{NP}\dto\sym{VP}\;\sym{N},\\&&\q\{\sym{S}\dto\sym{ADV}\;\sym{VP},\;\sym{ADV}(0,1),\;\sym{VP}(1,5)\}\;\}&&&\q\sym{VP}(0,2),\;\sym{N}(2,3)\}\;\}\\\subtrees_\ell(\sym{VP}(1,5))&=&\{\;\{\sym{VP}\dto\sym{PP}\;\sym{V},\;\sym{PP}(1,4),\;\sym{V}(4,5)\}\;\}&\subtrees_\ell(\sym{N}(2,3))&=&\{\;\{\sym{N}\dto\sym{一郎}\}\;\}\\\subtrees_\ell(\sym{PP}(1,4))&=&\{\;\{\sym{PP}\dto\sym{NP}\;\sym{P},\;\sym{NP}(1,3),\;\sym{P}(3,4)\}\;\}&\subtrees_\ell(\sym{VP}(0,2))&=&\{\;\{\sym{VP}\dto\sym{ADV}\;\sym{V},\\\subtrees_\ell(\sym{NP}(1,3))&=&\{\;\{\sym{NP}\dto\sym{V}\;\sym{N},\;\sym{NP}(1,2),\;\sym{N}(2,3)\}\;\}&&&\q\sym{ADV}(0,1),\;\sym{V}(1,2)\}\;\}\\\subtrees_\ell(\sym{V}(4,5))&=&\{\;\{\sym{V}\dto\sym{見た}\}\;\}&\subtrees_\ell(\sym{V}(1,2))&=&\{\;\{\sym{V}\dto\sym{走る}\}\;\}\\\subtrees_\ell(\sym{PP}(0,4))&=&\{\;\{\sym{PP}\dto\sym{NP}\;\sym{P},\;\sym{NP}(0,3),\;\sym{P}(3,4)\}\;\}&\subtrees_\ell(\sym{ADV}(0,1))&=&\{\;\{\sym{ADV}\dto\sym{急いで}\}\;\}\\\subtrees_\ell(\sym{P}(3,4))&=&\{\;\{\sym{P}\dto\sym{を}\}\;\}\end{array}}\]\end{small}\subsection{支持グラフ}\label{sec:GEM:support-graph}$\tuple{O_\ell,\subtrees_\ell}$という組を支持グラフ$\sg_\ell$というデータ構造で捉えるとgEMアルゴリズムが理解しやすくなる．「グラフィカルEM」の名もここに由来する．まず，前節で示した$O_\ell$,$\subtrees_\ell$の例に対応する支持グラフを図~\ref{fig:support-graph-ichiro}(a)に示す．支持グラフ$\sg_\ell$は再帰遷移ネットワーク（recursivetransitionnetwork;以下RTN）に似た構造をもつ非循環有向グラフ(DAG)であり，共通の辺をもたない部分グラフ\$\subsg_\ell(\tau)\defined\tuple{\tau,\subtrees_\ell(\tau)}$の集まりから成る（ただし$\tau\inO_\ell$）．各$\subsg_\ell(\tau)$は「$\tau$の部分支持グラフ」と呼ばれ，$\tau=A(d,d')$が付与されている．また，$\subsg_\ell(\tau)$は開始ノード，終了ノードと呼ばれる2つの特殊なノードをもち（図~\ref{fig:support-graph-ichiro}では各々{\sfstart},{\sfend}と書かれている），各$E\in\subtrees_\ell(\tau)$に対して開始ノード，$E$の各要素（規則$A\dto\zeta$または部分木ラベル$A(d,d')$）が付与されたノード，終了ノードが一列に連結されている．複数のノードに同じ規則または部分木ラベルが付与されることもある点に注意する．有向辺はすべて開始ノードから終了ノードに向かっている．開始ノードから終了ノードに至るパスを局所パスと呼び，これも$E$で参照する．局所パスにおいて，規則$A\dto\zeta$が付与されたノードを基本ノード，部分木ラベル$A(d,d')$が付与されたノードを中間ノードと呼び，各々図~\ref{fig:support-graph-ichiro}のように○と◎で表す．支持グラフは次の特徴をもつ．\begin{enumerate}\item支持グラフ$\sg_\ell$に対してRTNのように再帰的な巡回を行なうことができる．\item複数の巡回パスの一部が共有される．\item部分支持グラフ$\subsg_\ell(\tau)=\tuple{\tau,\subtrees(\tau)}$の$E\in\subtrees_\ell(\tau)$に対して，どの$\tau'=A(d,d')\inE$についても$\tau@\tau'$が成り立つ．\item一つの局所パス中に存在する基本ノードと中間ノードの数に制限がない．\end{enumerate}\begin{figure}[t]\atari(140,74)\caption{支持グラフの例．}\label{fig:support-graph-ichiro}\end{figure}1つ目の特徴である再帰的な巡回は次のようにして行なわれる．$S(0,n_\ell)$の開始ノードから出発し，辺に沿って各ノードを訪問していくが，途中に中間ノード$\tau=A(d,d')$があったら，$\tau$が付与された部分支持グラフ$\tau$の開始ノードにジャンプする．そして終了ノードに至ったらジャンプ元のノードに戻る．これを再帰的に繰り返し，$S(0,n_\ell)$の終了ノードに至ったら一回の巡回を終了する．分岐がある場合はその中のどれかを選ぶ．このような巡回の途中で中間ノードに付与される部分木ラベルを集めると$\win_\ell$の構文木いずれか一つのラベル集合が得られる．また，局所パス中のノードの順序を図~\ref{fig:support-graph-ichiro}のようにして，巡回中に基本ノードに付与されている規則を順に集めると\$\win_\ell$の最左導出における適用規則列$\rseq\in\trees(\win_\ell)$が一つ得られる．再帰的巡回を全通り行なえば$\trees(\win_\ell)$中の適用規則列をすべて見つけることができる．この考えは後に記述するgEMアルゴリズムの正当性を示すときに用いる（付録~\ref{sec:GEM-validity}）．図~\ref{fig:support-graph-ichiro}~(b)に再帰的巡回の例を示す．2つ目の特徴が得られるのは，ある再帰的巡回において，同じ部分木ラベル$\tau=A(d,d')$が付与されたノードでは同じ部分支持グラフ$\subsg_\ell(\tau)$にジャンプするためである．このような共有構造により支持グラフのサイズが圧縮され，我々はgEMアルゴリズムを支持グラフの上で動作させることによって効率的な確率計算を実現する．例えば，図~\ref{fig:support-graph-ichiro}(a)において$\sym{V}(4,5)$が付与されたノード（$\times$印）では同じ部分支持グラフ\$\subsg_\ell(\sym{V}(4,5))$にジャンプする．3つ目の特徴は，$\varepsilon$規則およびサイクル$A\derivesplusA$が存在しないという仮定と，$O_\ell$,$\subtrees_\ell$の定義から明らかであり，「$\tau@\tau'$であるとき，$\tau'$の部分支持グラフ$\subsg_\ell(\tau')$中のノードは$\tau$を参照しない」と言い替えることもできる．この事実に基づき，I-Oアルゴリズムの内側・外側確率計算における動的計画法（節~\ref{sec:PCFG:IO}）の考えを一般化したものがgEMアルゴリズムに導入されている．また，4つ目の特徴は支持グラフの構造の一般性を示しているが，gEMアルゴリズムはこの一般性を保持するように記述される．\subsection{支持グラフの獲得}\label{sec:GEM:extract-support-graph}次に，支持グラフ$\tuple{O_\ell,\subtrees_\ell}$をパーザがもつWFSTから効率的に抽出する方法を説明する．$O_\ell$は$V_\ell$の要素を$\wfst_\ell$における半順序関係$@$を満たすように全順序に並べたものである．一般に，半順序関係の全順序関係への変換はトポロジカルソーティングによって実現される．従って，我々はトポロジカルソーティングの考えに基づき$O_\ell$を獲得する．また，ソーティングの途中で$\subtrees_\ell$が計算できる．以上を実現する支持グラフ抽出ルーチン$\proc{Extract-CYK}$を図~\ref{alg:extract-sg}（上）に示す．ただし，そのサブルーチンは利用するパーザのWFSTの形式に特化したものを用意する．図~\ref{alg:extract-sg}（下）にCYK用サブルーチン\$\proc{Visit-CYK}$を示す．我々は大域的にスタック\footnote{スタック用手続きとして，スタック$U$を空にする$\proc{ClearStack}(U)$,スタック$U$にオブジェクト$x$をpushする$\proc{PushStack}(x,U)$,スタック$U$をpopして，popされたオブジェクトを返す$\proc{PopStack}(U)$の3つを用意する．}$U$とフラグ$\varComp[\cdot]$を用意し，再帰的手続き$\proc{Visit-CYK}$で三角行列（CYKのWFST）の右上隅から部分木$A(d,d')$を次々に訪問する（$\proc{Extract-CYK}$行~\ref{list:preproc-CYK:call-visit}）．そして訪問が終ったら，部分木のラベルをスタック$U$に積む（$\proc{Visit-CYK}$行~\ref{list:visit-CYK:push}）．また，訪問の途中で$\subtrees_\ell$を記録していく（$\proc{Visit-CYK}$行~\ref{list:visit-CYK:add1},~\ref{list:visit-CYK:add2}）．フラグ$\varComp[\cdot]$に訪問したことを記録し，一度訪問した部分木には行かない（$\proc{Visit-CYK}$行~\ref{list:visit-RB:mark},\ref{list:visit-CYK:recursion:begin}--\ref{list:visit-CYK:recursion:end}）．最後にスタック$U$に積んであった部分木ラベルを順に取り出せば（$\proc{Extract-CYK}$行~\ref{list:preproc-CYK:pop:begin}--\ref{list:preproc-CYK:pop:end}），それが$O_\ell$になっている．\begin{figure}[b]\begin{listing}\item\rw{procedure}$\proc{Extract-CYK}()$\rw{begin}\itemi\rw{for}$\ell:=1$\rw{to}$N$\rw{do}\rw{begin}\itemiiInitializeall$\subtrees_\ell(\cdot)$to$\emptyset$andall$\varComp[\cdot]$to$\sym{NO}$;\itemii$\proc{ClearStack}(U)$;\q\progcomment{スタックを初期化}\label{list:preproc-CYK:clear-U}\itemii$\proc{Visit-CYK}(\ell,S,0,n_\ell)$;\q\progcomment{各パーザ専用ルーチン;三角行列右上隅から巡回}\label{list:preproc-CYK:call-visit}\itemii\rw{for}$k:=1$\rw{to}$|U|$\rw{do}$\tau_k:=\proc{PopStack}(U)$;\q\progcomment{スタック中の整列結果を順に取り出す}\label{list:preproc-CYK:pop:begin}\itemii$O_\ell:=\tuple{\tau_1,\tau_2,\ldots,\tau_{|U|}}$\label{list:preproc-CYK:pop:end}\itemi\rw{end}\item\rw{end}.\end{listing}\begin{listing}\item\rw{procedure}$\proc{Visit-CYK}(\ell,A,d,d')$\rw{begin}\itemiPut$\tau=A(d,d')$andthen$\varComp[\tau]:={\ttYES}$;\q\progcomment{訪問を記録}\label{list:visit-CYK:mark}\itemi\rw{if}$d'=d+1$\rw{and}$A(d,d')@w_{d'}(d,d')\inT_{d,d'}^{(\ell)}$\rw{then}Addaset$\{A\dtow_{d'}\}$to$\subtrees_\ell(\tau)$\label{list:visit-CYK:add1}\itemi\rw{else}\itemii\rw{foreach}$A(d,d')@B(d,d'')C(d'',d')\inT_{d,d'}^{(\ell)}$\rw{do}\rw{begin}\label{list:visit-CYK:foreachABC}\itemiiiAddaset$\{A\dtoBC,\;B(d,d''),\;C(d'',d')\}$to$\subtrees_\ell(\tau)$;\label{list:visit-CYK:add2}\itemiii\rw{if}$\varComp[B(d,d'')]={\ttNO}$\rw{then}\label{list:visit-CYK:recursion:begin}$\proc{Visit-CYK}(\ell,B,d,d'')$;\q\progcomment{再帰}\itemiii\rw{if}$\varComp[C(d'',d')]={\ttNO}$\rw{then}$\proc{Visit-CYK}(\ell,C,d'',d')$\q\progcomment{再帰}\label{list:visit-CYK:recursion:end}\itemii\rw{end};\itemi$\proc{PushStack}(\tau,U)$\label{list:visit-CYK:push}\item\rw{end}.\end{listing}\caption{（上）支持グラフ抽出ルーチン$\proc{Extract-CYK}$，（下）CYKパーザ用サブルーチン$\proc{Visit-CYK}$．}\label{alg:extract-sg}\end{figure}GLRパーザのWFSTである共有圧縮統語森は$\wfst_\ell$を木（森）構造で捉えたものと見ることができる．GLRパーザは文法構造にChomsky標準形を要求しないので，$\proc{Visit-CYK}$よりも一般的な形で記述する必要があるが，スタック$U$,フラグ$\varComp[\cdot]$を用いる点や再帰手続きになる点など基本手続きは$\proc{Visit-CYK}$と変わらない．また，支持グラフ抽出ルーチンの動作はパーザ備え付けの構文木出力ルーチンや構文木数え上げルーチンによく似ている．従って，支持グラフ抽出ルーチンを実装するときにはこれらのルーチンを基にすればよい．\subsection{グラフィカルEMアルゴリズム}\label{sec:GEM:GEM}提案手法によるPCFG訓練のメインルーチン$\proc{Learn-PCFG}$は図~\ref{alg:learn-PCFG}のようになる．2つのサブルーチン$\proc{CYK-Parser}$と\$\proc{Extract-CYK}$は先に説明した．本節ではgEMアルゴリズムを実現する手続き$\proc{Graphical-EM}$を記述する．I-Oアルゴリズムと同様，gEMアルゴリズムでも内側・外側確率という2つの確率値の計算が中心になる．各$\tau\inO_\ell$の内側確率，外側確率の値は$\varP[\ell,\tau]$,$\varQ[\ell,\tau]$という配列変数に格納される．これは各部分支持グラフ\$\subsg_\ell(\tau)=\tuple{\tau,\subtrees_\ell(\tau)}$によって保持される．また，$\subsg_\ell(\tau)$は各局所パス$E\in\subtrees_\ell(\tau)$ごとに配列変数$\varR[\ell,\tau,E]$をもつ．また，配列変数$\varON[A\dto\zeta]$に規則$A\dto\zeta$の期待適用回数が格納される．$\proc{Graphical-EM}$は内側確率を計算する$\proc{Get-Inside-Probs}$,外側確率と規則の期待適用回数を同時に計算する$\proc{Get-Expectations}$という2つのサブルーチンをもつ．\begin{figure}[t]\begin{listing}\item\rw{procedure}$\proc{Learn-PCFG}(\corpus)$\rw{begin}\itemi$\proc{CYK-Parser}(\corpus)$;\q\progcomment{$\corpus$の解析結果のWFSTを生成}\itemi$\proc{Extract-CYK}()$;\q\progcomment{WFSTから支持グラフを抽出}\itemi$\proc{Graphical-EM}()$\q\progcomment{支持グラフを参照しながらパラメタ$\theta$を訓練}\item\rw{end}.\end{listing}\caption{PCFG訓練のメインルーチン$\proc{Learn-PCFG}$．}\label{alg:learn-PCFG}\end{figure}\begin{figure}[b]\begin{listing}\item\rw{procedure}$\proc{Graphical-EM}()$\rw{begin}\itemiInitializeallparameters$\theta(A\dto\zeta)$suchthat$P(\win_\ell|\theta)>0$forall$\ell=1\ldotsN$;\label{list:gEM:init}\itemi$\proc{Get-Inside-Probs}()$;\itemi$\lambda^{(0)}:=\sum_{\ell=1}^N\log\varP[\ell,S(0,n_\ell)]$;\label{list:gEM:loglike:1}\itemi\rw{repeat}\label{list:gEM:repeat:begin}\itemii$\proc{Get-Expectations}()$;\label{list:gEM:call-expect}\itemii\rw{foreach}$(A\dto\zeta)\inR$\rw{do}\label{list:gEM:update:begin}\itemiii$\theta(A\dto\zeta):=\varON[A\dto\zeta]/\sum_{\zeta':(A\to\zeta')\inR}\varON[A\dto\zeta']$;\label{list:gEM:update:end}\itemii$m\incby1$;\itemii$\proc{Get-Inside-Probs}()$;\itemii$\lambda^{(m)}:=\sum_{\ell=1}^N\log\varP[\ell,S(0,n_\ell)]$\label{list:gEM:loglike:2}\itemi\rw{until}$\lambda^{(m)}-\lambda^{(m-1)}$becomessufficientlysmall\label{list:gEM:repeat:end}\item\rw{end}.\end{listing}\caption{gEMアルゴリズムのメインルーチン$\proc{Graphical-EM}$．}\label{alg:GEM}\end{figure}$\proc{Graphical-EM}$を図~\ref{alg:GEM}に示す．$\proc{Graphical-EM}$では，はじめにすべてのパラメタを初期化する（行~\ref{list:gEM:init}）．そして，$\proc{Get-Inside-Probs}$,$\proc{Get-Expectations}$,パラメタの更新（行~\ref{list:gEM:update:begin}--\ref{list:gEM:update:end}）をこの順に繰り返す．対数尤度$\lambda$が収束したら（行~\ref{list:gEM:repeat:end}），その時点でのパラメタ値$\theta$を推定値$\theta^{\ast}$として終了する．$\varP[\ell,S(0,n_\ell)]$に文$\win_\ell$の生起確率$P(\win_\ell)$が格納されており，対数尤度の計算にはこの値を使う（行~\ref{list:gEM:loglike:1},~\ref{list:gEM:loglike:2}）．図~\ref{alg:GEM-sub}にサブルーチン$\proc{Get-Inside-Probs}$,$\proc{Get-Expectations}$を示す．また，図~\ref{fig:GEM-sub}は支持グラフ上における各々の計算イメージである．\begin{figure}[t]\begin{listing}\item\rw{procedure}$\proc{Get-Inside-Probs}()$\rw{begin}\itemi\rw{for}$\ell:=1$\rw{to}$N$\rw{do}\rw{begin}\itemiiPut$O_\ell=\tuple{\tau_1,\tau_2,\ldots,\tau_{|O_\ell|}}$;\itemii\rw{for}$k:=|O_\ell|$\rw{downto}$1$\rw{do}\rw{begin}\label{list:get-ip:for-k:begin}\itemiii\rw{foreach}$E\in\subtrees_\ell(\tau_k)$\rw{do}\rw{begin}\label{list:get-ip:foreachE:begin}\itemiiii$\varR[\ell,\tau_k,E]:=1$;\itemiiii\rw{foreach}$\tau'\inE$\rw{do}\label{list:get-ip:for-tau:begin}\itemiiiii\rw{if}$\tau'=(A\dto\zeta)$\rw{then}$\varR[\ell,\tau_k,E]\mulby\theta(A\dto\zeta)$\rw{else}$\varR[\ell,\tau_k,E]\mulby\varP[\ell,\tau']$\label{list:get-ip:for-tau:end}\itemiii\rw{end};\q\progcomment{\rw{foreach}$E$}\itemiii$\varP[\ell,\tau_k]:=\sum_{E\in\subtrees_\ell(\tau_k)}\varR[\ell,\tau_k,E]$\label{list:get-ip:calc-P}\itemii\rw{end}\q\progcomment{\rw{for}$k$}\label{list:get-ip:for-i:end}\itemi\rw{end}\q\progcomment{\rw{for}$\ell$}\item\rw{end}.\end{listing}\begin{listing}\item\rw{procedure}$\proc{Get-Expectations}()$\rw{begin}\itemi\rw{foreach}$(A\dto\zeta)\inR$\rw{do}$\varON[A\dto\zeta]:=0$;\label{list:get-exp:init:eta}\itemi\rw{for}$\ell:=1$\rw{to}$N$\rw{do}\rw{begin}\itemiiPut$O_\ell=\tuple{\tau_1,\tau_2,\ldots,\tau_{|O_\ell|}}$;\itemii\rw{for}$k:=2$\rw{to}$|O_\ell|$\rw{do}$\varQ[\ell,\tau_k]:=0$;\label{list:get-exp:init:s:1}\itemii$\varQ[\ell,\tau_1]:=1$;\q\progcomment{$\tau_1$は特別に1に初期化}\label{list:get-exp:init:s:2}\itemii\rw{for}$k:=1$\rw{to}$|O_\ell|$\rw{do}\label{list:get-exp:for-i:begin}\itemiii\rw{foreach}$E\in\subtrees_\ell(\tau_k)$\rw{do}\label{list:get-exp:foreach-E}\itemiiii\rw{foreach}$\tau'\inE$\rw{do}\itemiiiii\rw{if}$\tau'=(A\dto\zeta)$\rw{then}$\varON[A\dto\zeta]\incby\varQ[\ell,\tau_k]\cdot\varR[\ell,\tau_k,E]/\varP[\ell,S(0,n_\ell)]$\label{list:get-exp:updateON}\itemiiiii\rw{else}\rw{if}$\varP[\ell,\tau']>0$\rw{then}$\varQ[\ell,\tau']\incby\varQ[\ell,\tau_k]\cdot\varR[\ell,\tau_k,E]/\varP[\ell,\tau']$\label{list:get-exp:updateQ}\itemi\rw{end}\q\progcomment{\rw{for}$\ell$}\item\rw{end}.\end{listing}\caption{$\proc{Graphical-EM}$のサブルーチン：（上）内側確率を計算する$\proc{Get-Inside-Probs}$，\\（下）外側確率および規則の期待適用回数を計算する$\proc{Get-Expectations}$．}\label{alg:GEM-sub}\end{figure}$\proc{Get-Inside-Probs}$における内側確率$\varP[\ell,\tau]$の計算は$O_\ell$の最後尾の部分支持グラフから順に行なう．$\tau_k$の部分支持グラフ\$\subsg_\ell(\tau_k)=\tuple{\tau_k,\subtrees_\ell(\tau_k)}$($k=1\ldots|O_\ell|$)の各局所パス$E\in\subtrees_\ell(\tau_k)$ではパス中の各ノードの確率積を計算し，$\varR[\ell,\tau_k,E]$に格納する（行~\ref{list:get-ip:for-tau:begin}--\ref{list:get-ip:for-tau:end},図~\ref{fig:GEM-sub}(1)）．その際，基本ノード$A\dto\zeta$に対してパラメタ\$\theta(A\dto\zeta)$を乗じ，中間ノード$\tau'$に対して内側確率$\varP[\ell,\tau']$を乗じる\footnote{節~\ref{sec:GEM:support-graph}で述べた支持グラフの3つ目の特徴より$\tau'=\tau_{k'}$とおくと必ず$k<k'$であることと，$\varP$の計算は$O_\ell$の最後尾から順に行なわれることから，$\varP[\ell,\tau']$は参照されるとき既に計算済みになっている点に注意する．}（図~\ref{fig:GEM-sub}(2)）．最後に$\varR[\ell,\tau_k,E]$の和によって$\varP[\tau_k]$を計算する（行~\ref{list:get-ip:calc-P},図~\ref{fig:GEM-sub}(3)）．\begin{figure}[t]\atari(142,57)\caption{サブルーチン$\proc{Get-Inside-Probs}$（左）と\$\proc{Get-Expectations}$（右）の計算イメージ．}\label{fig:GEM-sub}\end{figure}一方，$\proc{Get-Expectations}$では$\proc{Get-Inside-Probs}$とは逆に$O_\ell$の先頭の部分支持グラフから順に計算を進める．はじめに配列変数$\varQ$と$\varON$を初期化する．特に外側確率$\varQ[\ell,\cdot]$について$O_\ell$の先頭要素\$\tau_1=S(0,n_\ell)$のみを1,他は0にする点に注意する（行~\ref{list:get-exp:init:s:1}--\ref{list:get-exp:init:s:2}）．次に，ある$k=1\ldots|O_\ell|$について$\tau_k$の部分支持グラフ\$\subsg_\ell(\tau_k)$の局所パス$E$を考える（行~\ref{list:get-exp:foreach-E}）．更に，行~\ref{list:get-exp:updateQ}で外側確率$\varQ$が書き換えられる$\tau'\inE$を考える．また，行~\ref{list:get-exp:updateQ}の式で$\varQ[\ell,\tau']$に加算されるのは，$E$における$\tau'$の局所的な外側確率（パス$E$に現れる$\tau'$以外のノードの確率積）と$\tau'$の親部分木$\tau_k$の外側確率$\varQ[\ell,\tau_k]$の積である\footnote{$\tau'=\tau_{k'}$とおくと，支持グラフの3つ目の特徴より必ず$k<k'$が成り立つので，$\tau'$は$O_\ell$では常に$\tau_k$より後ろに現れる．逆にいえば$k''=k\ldots|O_\ell|$なる部分支持グラフ\$\subsg_\ell(\tau_{k''})$では$\varQ[\ell,\tau_k]$の値は書き換えられることはなく，従って行~\ref{list:get-exp:updateQ}の式の右辺に現れる$\varQ[\ell,\tau_k]$は既に計算済みである．}（図~\ref{fig:GEM-sub}(4)）．また，行~\ref{list:get-exp:updateON}において，基本ノード\$A\dto\zeta$に対しては局所パスの確率$\varR[\ell,\tau_k,E]$と親部分木$\tau_k$の外側確率$\varQ[\ell,\tau_k]$の積を文$\win_\ell$の生起確率$P(\win_\ell)$で割って\footnote{$\proc{Graphical-EM}$行~\ref{list:gEM:init}のように，すべての$\ell=1\ldotsN$について$P(\win_\ell|\theta)>0$となる$\theta$に初期化しているので，以降$\theta$の更新が行なわれても$P(\win_\ell|\theta)=0$となることはない．この事実は，gEMアルゴリズムにおける$\eta[r]$の更新値とFujisakiらの方法（式~\ref{eq:Fujisaki-eta}）における$\eta[r]$の更新値が等しいと仮定したとき（これは付録~\ref{sec:GEM-validity}で直観的に証明される），以下のように帰納的に証明される:まず$m$回目の更新後のパラメタ$\theta^{(m)}$の下で\$P(\win_\ell|\theta^{(m)})>0$が成り立つとする．すると，ある$\rseq\in\subtrees(\win_\ell)$に対して\$P(\rseq|\theta^{(m)})>0$が成り立つ．そしてこの$\rseq$に出現する任意の規則$r\in\rseq$について，$\occ(r,\rseq)>0$が成り立つことと式~\ref{eq:Fujisaki-eta}より，$\theta^{(m)}$の下で$\eta[r]>0$となる．すると$\proc{Graphical-EM}$行~\ref{list:gEM:update:end}により更新後のパラメータ$\theta^{(m+1)}(r)>0$が保たれる．従って同じ$\rseq$に対して$P(\rseq|\theta^{(m+1)})>0$が成り立ち，これより$P(\win_\ell|\theta^{(m+1)})>0$もまた成り立つ．以上で\$P(\win_\ell|\theta^{(m)})>0\RightarrowP(\win_\ell|\theta^{(m+1)})>0$が言えたので，パラメタを$P(\win_\ell|\theta^{(0)})>0$なる\$\theta^{(0)}$に初期化すれば，以降の更新$m=1,2,\ldots$では必ず$P(\win_\ell|\theta^{(m)})>0$である．（証明終）また，$P(\win_\ell|\theta)>0$とするために，現実的にはすべての規則$r\inR$について$\theta(r)>0$となる$\theta$を選べば十分である．}$\varON[A\dto\zeta]$に足し込む（図~\ref{fig:GEM-sub}(5)）．こうして$\varON[A\dto\zeta]$の内容を書き換えていくと，$\proc{Get-Expectations}$の終了時には$\varON[A\dto\zeta]$に$A\dto\zeta$の期待適用回数が格納されている．gEMアルゴリズムの計算は支持グラフの1つ目の特徴である支持グラフ$\sg_\ell$の再帰的巡回（節~\ref{sec:GEM:support-graph}）に基づいて正当化される．それを付録~\ref{sec:GEM-validity}で示す．一般に，EMアルゴリズムは尤度関数の山登りを行なうため局所的な最尤推定しか保証しない．従って訓練されたパラメタの質は初期パラメタ値に依存する．LariとYoungはHMMを利用して初期パラメタ値を与える方法を提案している~\cite{Lari90}．最も簡便な解決法としては，初期パラメタをランダムに設定することとEMアルゴリズムを動作させることを$h$回繰り返し，その中で収束時の対数尤度が最も高かった回の収束パラメタ値を訓練パラメタ値とする．この方法を以降では簡単に再出発法と呼ぶ．\subsection{予測構文木の計算}\label{sec:GEM:ML-tree}いったんパラメタ$\theta^{\ast}$が訓練されたら，括弧なしであるテストコーパスの各文$\win_\ell$に対して$\rseq^{\ast}_\ell\defined\max_{{\rmall}\;\rseq}P(\rseq|\win_\ell)=\max_{{\rmall}\;\rseq}P(\rseq,\win_\ell)=\max_{\rseq\in\trees(\win_\ell)}P(\rseq)$なる$\rseq^{\ast}_\ell$を計算することができる．$\rseq^{\ast}_\ell$に対応する構文木$t^{\ast}_\ell$を予測構文木（以下，単に予測木）という．この予測木$t^{\ast}_\ell$によって入力文$\win_\ell$に対する構文的曖昧性が解消される．ただし，$|\trees(\win_\ell)|$は指数オーダなので，ここでも支持グラフに基づいて$t^{\ast}_\ell$を計算する．予測木$t^{\ast}_\ell$を計算する手続き$\proc{Predict}$およびそのサブルーチン$\proc{Construct-Tree}$を図~\ref{alg:predict}に示す．$\proc{Predict}$はテストコーパス\$\corpus=\tuple{\win_1,\win_2,\ldots,\win_N}$を受けとり，各$\win_\ell$に対する予測木中の部分木ラベルの集合$\labels(t^{\ast}_\ell)$を$\labels^{\ast}_\ell$に格納する．$\proc{Predict}$では，はじめにパーザ，支持グラフ抽出ルーチン，内側確率計算ルーチン$\proc{Get-Inside-Probs}$の3つを走らせる（行~\ref{line:predict-tree:parser}）．次に，$\proc{Get-Inside-Probs}$が計算した確率値$\varR[\ell,\tau,E]$を参照しながら，$\delta[\ell,\tau]$に最も確率の高い$\tau$の局所パスを記録する（行~\ref{line:predict-tree:record}）．再帰手続き$\proc{Construct-Tree}$では，支持グラフ$\sg_\ell$の再帰的巡回に基づき，$\delta[\ell,\tau]$中のラベル$A(d,d')$を$\labels^{\ast}_\ell$に追加する（行~\ref{line:const-pred-tree:add}）ことで予測木を構築する．$\delta[\ell,\tau]$に複数の局所パス候補を格納するように拡張すれば，生起確率上位$n$個の予測木が獲得できる．\begin{figure}[t]\begin{listing}\item\rw{procedure}$\proc{Predict}(\corpus)$\rw{begin}\itemiPut$N=|\corpus|$;\itemi$\proc{CYK-Parser}(\corpus)$;\q$\proc{Extract-CYK}()$;\q$\proc{Get-Inside-Probs}()$;\label{line:predict-tree:parser}\itemi\rw{for}$\ell:=1$\rw{to}$N$\rw{do}\rw{begin}\itemiiPut$O_\ell=\tuple{\tau_1,\tau_2,\ldots,\tau_{|O_\ell|}}$;\itemii\rw{for}$k:=1$\rw{to}$|O_\ell|$\rw{do}$\delta[\ell,\tau_k]:=\mathop{\mbox{argmax}}_{E\in\subtrees_\ell(\tau_k)}\varR[\ell,\tau_k,E]$;\label{line:predict-tree:record}\itemii$\labels^{\ast}_\ell:=\emptyset$;\itemii$\proc{Construct-Tree}(\ell,\tau_1)$\q\progcomment{必ず$\tau_1=S(0,n_\ell)$である．}\itemi\rw{end}\item\rw{end}.\end{listing}\begin{listing}\item\rw{procedure}$\proc{Construct-Tree}(\ell,\tau)$\rw{begin}\itemi\rw{foreach}$\tau'\in\delta[\ell,\tau]$suchthat$\tau'=A(d,d')$\rw{do}\rw{begin}\itemiiAdd$\tau'$to$\labels^{\ast}_\ell$;\label{line:const-pred-tree:add}\itemii$\proc{Construct-Tree}(\ell,\tau')$\itemi\rw{end}\item\rw{end}.\end{listing}\caption{予測木計算ルーチン$\proc{Predict}$とそのサブルーチン$\proc{Construct-Tree}$．}\label{alg:predict}\end{figure}\subsection{計算量}\label{sec:GEM:complexity}節~\ref{sec:PCFG:IO}のI-Oアルゴリズムの計算量評価で述べたように，収束までのパラメタ更新回数は初期値に依存するため，1回のパラメタ更新に要する計算量をgEMアルゴリズムの計算量とする．手続き$\proc{Graphical-EM}$では{\bfrepeat}ループ内の計算量をはかればよい．まず，各$\ell=1\ldotsN$について\$O_\ell=\tuple{\tau_1^{(\ell)},\tau_2^{(\ell)},\ldots,\tau^{(\ell)}_{|O_\ell|}}$とおく．$\proc{Graphical-EM}$に呼び出される\$\proc{Get-Inside-Probs}$はその内部処理において$k=1\ldots|O_\ell|$について$|\subtrees_\ell(\tau_k^{(\ell)})|$の要素を一回ずつ訪れることから，\begin{eqnarray}\mu_{\rmnum}&\defined&\max_{\ell=1\ldotsN}\sum_{k=1}^{|O_\ell|}\big|\subtrees_\ell(\tau_k^{(\ell)})\big|\label{eq:xi-num}\\\mu_{\rmmaxsize}&\defined&\max_{E:\;\ell=1\ldotsN,\;k=1\ldots|O_\ell|,\;E\in\subtrees_\ell(\tau_k^{(\ell)})}|E|\label{eq:xi-maxsize}\end{eqnarray}を導入すると，手続き$\proc{Get-Inside-Probs}$の計算量は\$O(\mu_{\rmnum}\mu_{\rmmaxsize}N)$である．同様に手続き$\proc{Get-Expectations}$においても\$O(\mu_{\rmnum}\mu_{\rmmaxsize}N)$の計算量を要する．I-Oアルゴリズムの計算量評価と同様，訓練コーパス$\corpus$に対して最長の文の長さを$L$とし，非終端記号集合$\Vn$,終端記号集合$\Vt$を固定する．我々はChomsky標準形を満たす文法に対する最悪計算量を考える．そのために，まずChomsky標準形を満たす最大のPCFGとして節~\ref{sec:PCFG:IO}式~\ref{eq:Rmax}で導入した規則集合$\Rmax$を考える．このとき，$A\in\Vn$,$0\led,d'\leL$,$d+2\led'$なる\$A$,$d$,$d'$について下が成り立つ（$d'=d+1$の場合は無視できる）：\begin{equation}\subtrees_\ell(A(d,d'))=\bigl\{\{A\dtoBC,\;B(d,d''),\;C(d'',d')\}\;\big|\;B,C\in\Vn,\;d<d''<d'\bigr\}_{\mbox{.}}\label{eq:possible-psi}\end{equation}$|O_\ell|=\bigl|\{A(d,d')\midA\in\Vn,\;0\led<d'\leL\}\bigr|=O(|\Vn|L^2)$かつ$\big|\subtrees_\ell(\tau)\big|=O(|\Vn|^2L)$が成り立ち，定義より$\mu_{\rmnum}=O(|\Vn|^3L^3)$となる．同様に定義より$\mu_{\rmmaxsize}=3=O(1)$である．また，$\theta(A\dto\beta)$の更新に要する計算量は$O(|\Rmax|)$だが，$|\Rmax|=O(|\Vn|^3)$なので無視できる．以上より手続き$\proc{Graphical-EM}$の{\bfrepeat}ループ内の計算量は$O(|\Vn|^3L^3N)$である．以上よりgEMアルゴリズムの最悪計算量はI-Oアルゴリズムと同じ$O(|\Vn|^3L^3N)$である．Chomsky標準形を仮定したとき，CYKパーザ$\proc{CYK-Parser}$と支持グラフ抽出ルーチン$\proc{Extract-CYK}$の最悪計算量はEMの一更新ステップの最悪計算量と同じ\$O(|\Vn|^3L^3N)$である．ただ，EMアルゴリズムでは更新ステップを数10から数100回繰り返すのが通常なので$\proc{Extract-CYK}$が訓練全体に占める割合は小さい．同様にChomsky標準形を仮定したとき，一つの文に対する生起確率計算，予測木の計算いずれの計算量も$O(|\Vn|^3L^3)$である($N=1$)．また，式~\ref{eq:parent-children}の形をした部分木の親子対を構成要素とするWFSTをもつパーザ（例えばCYKやGLR）では，抽出される$O_\ell$,$\subtrees_\ell$は全く同じになるので，提案手法の計算量は組み合わせたパーザによる差はない．Earleyパーザを用いた場合に関する評価は付録~\ref{sec:Stolcke}に示す．
\section{訓練時間に関する実験}
\label{sec:experiment}我々は現実的な文法に対してはI-Oアルゴリズムに比べてEM学習が大幅に高速化される（提案手法の{\bf特長2}）ことを示すため，ATR対話コーパス(SLDB)でパラメタ推定に要する計算時間（訓練時間と呼ぶ）を計測した．対象PCFGの元になるCFGは860規則から成る，田中らが開発した音声認識用日本語文法~\cite{Tanaka97}に手が加えられたものである．以降ではこのCFGを$\Gtanaka$で参照する．ATR対話コーパスもこの文法に対応して手が加えられている．$\Gtanaka$は品詞を細分化したカテゴリを終端記号としたCFGであり，非終端記号数173,終端記号数441である．ATR対話コーパス中の文では，（実際の単語ではなく）上記カテゴリの列を対象とした．文長は平均9.97,最短2,最長49である．また，$\Gtanaka$の規則集合$\Rtanaka$はChomsky標準形ではないので，GLRパーザとの組合せを採用した\footnote{具体的には，東京工業大学田中・徳永研究室で開発・公開されている\MSLR(MorphologicalandSyntacticLR)パーザに支持グラフ抽出ルーチンとgEMアルゴリズムのルーチンを連結した．MSLRパーザは\verb|http://tanaka-www.cs.titech.ac.jp/pub/mslr/|で公開されている．MSLRパーザは形態素解析と構文解析を同時に行なう機能を有するが，今回の実験では構文解析機能のみを使用した．MSLRパーザを含め，実験で用いたプログラムはすべてC言語で実装されている．Cコンパイラはgcc2.8.1を使用した．また，実験で使用した計算機のCPUとOSはそれぞれ\SunUltraSPARC-II296MHzとSolaris2.6である．}．本論文の実験では$\Gtanaka$が与えられた場合の訓練時間を提案手法とI-Oアルゴリズムの間で比較する．ただし，I-Oアルゴリズムにおいては節~\ref{sec:PCFG:IO}で記述したものを用い，そこで参照される規則集合$R$には，全ての終端・非終端記号の組合せから成るChomsky標準形の規則集合$\Rmax$ではなく，$\Gtanaka$の規則集合$\Rtanaka$を用いる点に注意する\footnote{当然，$\Rtanaka$を用いた場合のI-Oアルゴリズムは，その文法制約のため$\Rmax$を用いた場合より高速になる．}．我々は文長$L$を変化させたときにパラメタを一回更新するのに要する計算時間（更新時間と呼ぶ）が変化する様子を比較する．まず，我々はATRコーパス$\corpus$の中で文長$L-1$と$L$の文をグループ化し，各々から無作為に取り出した100文を\$\corpus_L$とする($L=2,4,\ldots26$)\footnote{長さ27以上の176文（全体の1.6\%）はデータ不足のため，実験では考慮しなかった．}．そして，各$\corpus_L$を一つの訓練コーパスとし，各々に対して更新時間を計測する．I-OアルゴリズムはChomsky標準形でしか動作しないので，あらかじめ$\Gtanaka$をChomsky標準形に変換した．その結果860規則が2,308規則（非終端記号数210,終端記号数441）の文法になった．更新時間を計測した結果を図~\ref{graph:1}左に示す．縦軸が更新時間(sec)，横軸$L$が使用した訓練コーパス$\corpus_L$を表す．``{\itInside-Outside}''はI-Oアルゴリズムの更新時間，``{\itIOwithpruning}''は\cite{Kita99}で説明されている，I-Oアルゴリズムの外側確率の計算において無駄な計算部分を枝刈りするように改良したものである．これを以下では枝刈り版I-Oアルゴリズムと呼ぶ．``{\itGraphicalEM}''はgEMアルゴリズムの更新時間を示す．また，変化の様子を見やすくするために，図~\ref{graph:1}左の縦軸を拡大，縮小したものをそれぞれ図~\ref{graph:1}中央，図~\ref{graph:1}右に示す．図~\ref{graph:1}中央においてgEMアルゴリズムの更新時間は見にくいため省略した．\begin{figure}[t]\atari(125,63)\caption{（左）Inside-Outsideアルゴリズムとその枝刈り版，および\gEMアルゴリズムにおける\\更新時間(sec)の変化，（中央）縦軸を縮小したもの，（右）縦軸を拡大したもの．}\label{graph:1}\end{figure}図~\ref{graph:1}左のグラフから分かるように，gEMアルゴリズムはI-Oアルゴリズムやその枝刈り版に比べてはるかに高速な計算が行なわれていることが分かる．また，図~\ref{graph:1}中央のグラフから分かるようにI-Oアルゴリズムは理論値どおり$L^3$の曲線を描く．枝刈り版I-Oアルゴリズムは枝刈りした分高速であるものの，仮説駆動型である（$L\timesL$の三角行列の全要素を走査する）点は変わらないので，枝刈りが最も効率良く行なわれた場合でも$L^2$を下回ることはない．収束まで数100回の更新を要すること，および再出発法を採用することを考慮すると，$L=20$を越える訓練コーパス\$\corpus_L$に対してI-Oアルゴリズムおよびその枝刈り版を収束するまで動作させるのは現実的ではない．それに対し，提案手法では$L=2,4,\ldots,26$の範囲では$L$に対してほぼ線形に計算できており（図~\ref{graph:1}右），最悪計算量$O(|\Vn|^3L^3)$とは大きな差があることが分かった．これは文法の制約により，WFSTに格納される部分木の数が抑えられたためと考えられる．ATRコーパスにおける文長平均9.97に近い$L=10$ではI-Oアルゴリズムに対しておよそ1,000倍（枝刈り版に対してはおよそ700倍）の速度向上が得られた．\begin{figure}[t]\atari(103,63)\caption{訓練時間全体に占める各過程の処理時間の内訳．（左）再出発なしの場合($h=1$)，\\（右）再出発回数$h=10$の場合．}\label{graph:2}\end{figure}良質なパラメタを得る目的で再出発法（節~\ref{sec:GEM:GEM}）を採用すると，訓練時間の内訳は\begin{eqnarray*}(\mbox{全体の訓練時間})&=&(\mbox{構文解析時間})+(\mbox{支持グラフ抽出に要する時間})\nonumber\\&&\q+\;(\mbox{gEMアルゴリズム実行時間}),\\(\mbox{gEMアルゴリズム実行時間})&=&(\mbox{更新時間})\times(\mbox{収束までの更新回数})\times(\mbox{再出発回数$h$}).\end{eqnarray*}となる．先に述べた文長毎の訓練コーパス$\corpus_L$($L=2,4,\ldots,26$)を使って，訓練時間の内訳（構文解析時間，支持グラフ抽出時間，gEM実行時間）を計測した．その結果を図~\ref{graph:2}に示す．横軸が$L$,縦軸が処理時間(sec)である．図~\ref{graph:2}（左）は再出発なし$(h=1)$の場合，図~\ref{graph:2}（右）は再出発回数$h=10$の場合である．また，収束までの更新回数はコーパス$\corpus_L$によって異なるため，ここでは100に固定した．構文解析時間(``{\itParsing}'')，支持グラフ抽出時間(``{\itSupportgraph}'')，gEM実行時間(``{\itGraphicalEM}'')はいずれも文長$L$に対してほぼ線形になっていることが分かる．更に図~\ref{graph:2}（右）より，再出発法を採用した場合は構文解析時間と支持グラフ抽出時間が訓練時間全体に占める割合は非常に小さい．構文解析と支持グラフ抽出は再出発の度に繰り返す必要がないからである．構文解析と支持グラフ抽出をgEMアルゴリズムの前処理と捉えれば，わずかな前処理（図~\ref{graph:2}）で大きな速度向上（図~\ref{graph:1}）が得られているということができ，構文解析とEM学習を分離したメリットが現れている．
\section{PCFGの拡張文法のEM学習}
\label{sec:extensions}これまでPCFGに文脈依存性を採り入れたモデル（PCFGの拡張文法と呼ぶ）が数多く提案されているが，Charniakらの疑似確率文脈依存文法(pseudoprobabilisticcontext-sensitivegrammars)\cite{Charniak94b}を除けばEMアルゴリズムを具体的に記述した文献は見当たらない．本節では，提案手法がPCFGの拡張文法に対する多項式オーダのEMアルゴリズムを包含する（提案手法の{\bf特長3}）ことを示すため，一例としてKitaらの規則バイグラムモデル\cite{Kita94}を取り上げ，その多項式オーダのEMアルゴリズムを導出する．\subsection{規則バイグラムモデルとそのEMアルゴリズム}\label{sec:extensions:RB}まず，我々はPCFGのときと同様に導出戦略は最左導出に固定する．規則バイグラムモデルでは，節~\ref{sec:PCFG:PCFG}で述べたPCFGの「規則選択は他と独立」という仮定の代わりに，「規則選択は直前の選択のみに依存する」という仮定をおく．従って，規則バイグラムモデルではPCFGでは扱えなかった文脈依存性も若干考慮できる．この仮定の下で適用規則列$\rseq$の出現確率は\begin{equation}P(\rseq)=\theta(r_1\mid\#)\prod_{k=2}^K\theta(r_k\midr_{k-1})\end{equation}と計算される．\#は境界を表すマーカ，$\theta(r\midr')$は各規則$r\inR$に付与されるパラメタである($r'\inR\cup\{\#\}$)．各$A\in\Vn$,$r\inR\cup\{\#\}$に対し$\sum_{\zeta:(A\to\zeta)\inR}\theta(A\dto\zeta\midr)=1$が成り立つ．\cite{Kita94}で示された，括弧なしコーパス\$\corpus=\tuple{\win_1,\ldots,\win_N}$に基づく$\theta(r_k|r_{k-1})$の推定式は式~\ref{eq:kita}のとおりである．適用規則列$\rseq$に対して，$\occ(r,r';\rseq)$は\$\rseq$において$r'$が$r$の直後に出現する頻度を表す．定義より明らかに$\sum_{r'\inR}\occ(r,r';\rseq)=\occ(r;\rseq)$が成り立つ．\begin{equation}\textstyle\theta(r_k|r_{k-1}):=\left({\displaystyle\sum_{\ell=1}^N\frac{\sum_{\rseq\in\trees(\win_\ell)}\occ(r_{k-1},r_k;\rseq)}{\displaystyle|\trees(\win_\ell)|}}\right)\left/\left({\displaystyle\sum_{\ell=1}^N\frac{\sum_{\rseq\in\trees(\win_\ell)}\occ(r_{k-1};\rseq)}{\displaystyle|\trees(\win_\ell)|}}\right)\right.\label{eq:kita}\end{equation}ところが式~\ref{eq:update},~\ref{eq:naive-eta3}から類推できるように，EMアルゴリズムの考えに基づく更新式は次のようになる($m=1,2,\ldots$)．つまり式~\ref{eq:kita}は相対頻度法，EMアルゴリズムのいずれにもなっていない．\begin{eqnarray}&&\textstyle\theta^{(m+1)}(r_k|r_{k-1}):=\nonumber\\&&\textstyle\q\q\left({\displaystyle\sum_{\ell=1}^N\frac{\sum_{\rseq\in\trees(\win_\ell)}P(\rseq|\theta^{(m)})\occ(r_{k-1},r_k;\rseq)}{P(\win_\ell|\theta^{(m)})}}\right)\left/\left({\displaystyle\sum_{\ell=1}^N\frac{\sum_{\rseq\in\trees(\win_\ell)}P(\rseq|\theta^{(m)})\occ(r_{k-1};\rseq)}{P(\win_\ell|\theta^{(m)})}}\right)\right.\nonumber\\\label{eq:kita:EM}\end{eqnarray}式~\ref{eq:kita:EM}の更新式により（局所）最尤推定は実現されるが，これまで述べてきたように一般に$|\trees(\win)|$は文長$|\win|$に対して指数オーダになるため，式~\ref{eq:kita:EM}は現実時間で計算できない．一方，提案手法に基づき，式~\ref{eq:kita:EM}と等価な規則バイグラムモデルの多項式オーダのEMアルゴリズムを導出することができる．次節でアルゴリズムを記述するが，その前にいくつかの記号を導入する．まず，次のような文$\win$の最左導出列$\rseq$を考える:\begin{equation}S\derivesstar\cdots\rderives{r}\win_{0,d}A\xi\rderives{r''}\win_{0,d}\zeta\xi\derivesstar\cdots\derivesstar\win_{0,d}\zeta'\xi\rderives{r'}\win_{0,d}\win_{d,d'}\xi(=\win_{0,d'}\xi)\derivesstar\win\q.\label{eq:RB-derivation}\end{equation}を考える．式~\ref{eq:RB-derivation}において$r$は$A$を展開する直前に適用された規則，$r'$は導出$A\derivesstar\win_{d,d'}$で用いられた最後の規則である．$r$と$r'$を考慮した，$\win_{d,d'}$を統治する部分木ラベルを$A(d,d'|r,r')$で表す．また，式~\ref{eq:RB-derivation}において$r'$を$\lastrule(A,d,d';\rseq)$で参照し，$r$の次に適用された規則$r''$を$\condrule{A}{\zeta}{r}$で参照する．前節で述べた$\theta(A\dto\zeta|r)$の確率で$\condrule{A}{\zeta}{r}$が適用される．また，$\win$の構文木中の部分木$A(d,d')$を導出するとき最後に使われた規則の集合を\$\lastrule(A,d,d';\win)\defined\bigcup_{\rseq\in\trees(\win)}\lastrule(A,d,d';\rseq)$と定める．\subsection{グラフィカルEMアルゴリズムの適用}\label{sec:extensions:RB-GEM}ここではCYKパーザと組み合わせた場合の規則バイグラムモデルのEM学習法を示す．規則バイグラムモデルを対象にする場合，パーザに新たな変更を加える必要はない．また，gEMアルゴリズムもその汎用性により，対象とする確率値の意味が変わるだけで制御構造に変化はない．従って，我々は支持グラフ抽出ルーチンを変更するだけである．例えば，図~\ref{fig:parse-tree-ichiro-CNF}の$t2$にでは次のような関係$\subtrees_\ell$が得られる．\[\begin{array}{l}\subtrees_\ell(\sym{VP}(1,5\mid\sym{ADV}\dto\sym{急いで},\;\sym{V}\dto\sym{見た}))=\\\q\q\Bigl\{\;\bigl\{\condrule{\sym{VP}}{\sym{PP}\;\sym{V}}{\mbox{\footnotesize\ttADV}\to急いで}\;,\;\sym{PP}(1,4\mid\sym{VP}\dto\sym{PP}\;\sym{V},\;\sym{P}\dto\sym{を}),\;\sym{V}(4,5\mid\sym{P}\dto\sym{を},\;\sym{V}\dto\sym{見た})\bigr\}\;\Bigr\}\end{array}\]節~\ref{sec:GEM:preliminary}で示したPCFGの場合に比べて，部分木ラベル$A(d,d')$が，その導出直前に適用された規則と自身の導出において最後に適用された規則の組（``$\mid$''記号の後ろ）によって細分化されており，この細分化によって文脈依存性が表現される．\begin{figure}[t]\begin{listing}\item\rw{procedure}$\proc{Extract-CYK-RB}()$\rw{begin}\itemi\rw{for}$\ell:=1$\rw{to}$N$\rw{do}\rw{begin}\itemiiInitializeall$\subtrees_\ell(\cdot)$to$\emptyset$andall$\varComp[\cdot,\cdot]$and$\varLast[\cdot]$to$\sym{NO}$;\itemii$\proc{ClearStack}(U)$;\label{list:Extract-CYK-RB:clear-U}\itemii$\proc{Visit-CYK-RB}(\ell,S,0,n_\ell,\#)$;\q\progcomment{\#は境界を表すマーカ．}\label{list:Extract-CYK-RB:call-visit}\itemii\rw{for}$k:=1$\rw{to}$|U|$\rw{do}$\tau_k:=\proc{PopStack}(U)$;\label{list:Extract-CYK-RB:pop:begin}\itemiiPreparesome$\tau_0$;\itemii$\subtrees_\ell(\tau_0):=\bigl\{\{S(0,n_\ell|\#,r)\}\big|r\in\varLast[S(0,n_\ell)]\bigr\}$;\itemii$O_\ell:=\tuple{\tau_0,\tau_1,\tau_2,\ldots,\tau_{|U|}}$\label{list:Extract-CYK-RB:pop:end}\itemi\rw{end}\item\rw{end}.\end{listing}\caption{規則バイグラム用支持グラフ抽出ルーチン$\proc{Extract-CYK-RB}$}\label{alg:extract-CYK-RB}\end{figure}規則バイグラム用の支持グラフ抽出ルーチン\$\proc{Extract-CYK-RB}$とそのサブルーチン$\proc{Visit-CYK-RB}$をそれぞれ図~\ref{alg:extract-CYK-RB},図~\ref{alg:visit-CYK-RB}に示す．$\proc{Visit-CYK-RB}(\ell,r,A,d,d')$は$\win_\ell$の構文木中の部分木$A(d,d')$を訪問し，大域的配列変数$\varLast[A(d,d')]$に\$\lastrule(A,d,d';\win_\ell)$を格納する再帰手続きである．後はgEMアルゴリズム（手続き$\proc{Graphical-EM}$,$\proc{Get-Inside-Probs}$,$\proc{Get-Expectations}$）において$A\dto\zeta$,$\theta(A\dto\zeta)$,$\varON[A\dto\zeta]$を各々$\condrule{A}{\zeta}{r}$,$\theta(A\dto\zeta|r)$,$\varON[A\dto\zeta|r]$といった規則バイグラム用の確率値，期待値に書き換え，$\proc{Graphical-EM}$行~\ref{list:gEM:update:begin}--\ref{list:gEM:update:end}と$\proc{Get-Expectations}$行~\ref{list:get-exp:init:eta}の\rw{foreach}ループに``\rw{foreach}$r\inR$''ループを重ねるだけでよい．\begin{figure}[t]\begin{listing}\item\rw{procedure}$\proc{Visit-CYK-RB}(\ell,A,d,d',r)$\rw{begin}\itemi$\varComp[A(d,d'),r]:={\ttYES}$;\label{list:visit-RB:mark}\itemi\rw{if}$d'=d+1$and$A(d,d+1)@w_{d,d+1}^{(\ell)}\inT_{d,d+1}^{(\ell)}$\rw{then}\rw{begin}\itemiiiAddaset$\{\condrule{A}{w_{d,d+1}^{(\ell)}}{r}\}$to$\subtrees_\ell(A(d,d+1|r,A\dtow_{d,d+1}^{(\ell)}))$;\label{list:visit-RB:diagonal:begin}\label{list:visit-RB:add1}\itemiii$\varLast[A(d,d')]:=\{A\dtow_{d,d+1}^{(\ell)}\}$\label{list:visit-RB:diagonal:end}\itemii\rw{end}\itemi\rw{else}\rw{begin}\itemii$\varLast[A(d,d')]:=\emptyset$;\itemii\rw{foreach}$A(d,d')@B(d,d'')C(d'',d')\inT_{d,d'}^{(\ell)}$\rw{do}\rw{begin}\label{list:visit-RB:foreachABC}\label{list:visit-RB:foreachABC:begin}\itemiii\rw{if}$\varComp[B(d,d''),A\dtoBC]={\ttNO}$\rw{then}$\proc{Visit-CYK-RB}(\ell,B,d,d'',A\dtoBC)$;\label{list:visit-RB:recursion:begin}\label{list:visit-RB:visit-B}\itemiii\rw{foreach}$r''\in\varLast[B(d,d'')]$\rw{do}\rw{begin}\label{list:visit-RB:visit-C:begin}\itemiiii\rw{if}$\varComp[C(d'',d'),r'']={\ttNO}$\rw{then}$\proc{Visit-CYK-RB}(\ell,C,d'',d',r'')$;\label{list:visit-RB:recursion:end}\label{list:visit-RB:add2}\itemiiii\rw{foreach}$r'\in\varLast[C(d'',d')]$\rw{do}\rw{begin}\itemiiiiiAddaset$\bigl\{\condrule{A}{BC}{r},\;B(d,d''|A\dtoBC,r''),\;C(d'',d'|r'',r')\bigr\}$\itemiiiiiiito$\subtrees_\ell(A(d,d'|r,r'))$;\itemiiiii$\proc{PushStack}(A(d,d'|r,r'),U)$\label{list:visit-RB:push}\itemiiii\rw{end}\itemiii\rw{end};\q\progcomment{\rw{foreach}$r''$}\label{list:visit-RB:visit-C:end}\itemiii$\varLast[A(d,d')]:=\varLast[A(d,d')]\cup\varLast[C(d'',d')]$\itemii\rw{end}\q\progcomment{\rw{foreach}$A@BC$}\label{list:visit-RB:foreachABC:end}\itemi\rw{end}\q\progcomment{\rw{else}}\item\rw{end}.\end{listing}\caption{規則バイグラム用支持グラフ抽出ルーチンのサブルーチン$\proc{Visit-CYK-RB}$．\\記述短縮のため，ここでは異なる引数$r$（直前の適用規則）の呼び出しについて$\varLast[A(d,d')]$\\の計算を重複して行なうものを示す．}\label{alg:visit-CYK-RB}\end{figure}次に，規則バイグラム用EMアルゴリズムの最悪計算量を評価する．$\Rmax$を考えたとき，最悪計算量は$O(|\Vn|^{12}L^3N)$となる\footnote{まず，$A\in\Vn$,$0\led<d'\leL$かつ$d+2\led'$なる$A$,$d$,$d'$および，$r,r'\inR$について\[\subtrees_\ell(A(d,d'|r,r'))=\left\{\bigl\{\condrule{A}{BC}{r},\;B(d,d''|A\dtoBC,r''),\;C(d'',d'|r'',r')\bigr\}\;\left|\begin{array}{l}B,C\in\Vn,\;d<d''<d',\\r''\in\lastrule(B,d,d'')\subseteqR\end{array}\right.\right\}\]となるような$A(d,d'|r,r')$が$O_\ell$中に出現する($\ell=1\ldotsN$)．$\left|\subtrees_\ell(\tau)\right|=O(|\Vn|^2L|R|)$であるのは明らかである．また，$O_\ell$は\$\big\{A(d,d'|r,r')\;\big|\;A\in\Vn,\;0\led<d'\leL,\;r,r'\inR\big\}$の部分集合を並べたものであるから，$|O_\ell|=O(|\Vn|L^2|R|^2)$となる．定義より$\mu_{\rmnum}=O(|\Vn|^3L^3|R|^3)$,$\mu_{\rmmaxsize}=O(1)$であり，さらに最悪の場合$R=\Rmax$を考えるとgEMアルゴリズムの計算量は\$O(|\Vn|^3L^3|\Rmax|^3N)=O(|\Vn|^{12}L^3N)$となる．}．これは非常に大きなオーダであるが，文長$L$に対して3乗のオーダである点はI-Oアルゴリズムと変わらない．また，節~\ref{sec:experiment}の実験結果はPCFGに対する現実の計算時間と最悪時の計算時間$O(|\Vn|^3L^3)$に大きな差があることを示しており，これは規則バイグラムモデルでも成り立つと考えられる．実際森らは，節~\ref{sec:experiment}の実験で用いたCFG$\Gtanaka$に対し本節で述べた方法を適用した結果，規則バイグラムのEM学習におけるパラメタ更新時間がPCFG（図~\ref{graph:1}右）の1.5倍程度で収まることを報告している\cite{Mori00}．
\section{関連研究}
\label{sec:related-work}まず，Magermanらの${\calP}$earl\cite{Magerman91}およびその後継である${\calP}$icky\cite{Magerman92},またStolckeの確率的Earleyパーザ\cite{Stolcke95}をはじめ，確率的パーザが多く提案されている．しかし，それらの多くは文法構造$G$とパラメタ$\theta$が与えられていることを前提としており，Stolckeを除けばPCFG（もしくはその拡張文法）のEM学習について具体的に記述しているものは少ない．Chomsky標準形でないPCFGの訓練法としては，Kupiecの方法~\cite{Kupiec92}と先述のStolckeの確率的Earleyパーザによる訓練が挙げられる．Kupiecの方法はPCFGを再帰遷移ネットワークと捉え，拡張したtrellis図に基づき訓練を行なうものである．しかし，仮説駆動型である点はI-Oアルゴリズムと変わらない．また，提案手法で用いるWFSTは，CFGに基づく構文解析にとって本質的なデータ構造であることから，本手法はtrellis図に基づく\Kupiecの方法よりも簡潔で理解しやすいものと考える．一方，$\varepsilon$規則やサイクル$A\derivesplusA$が存在しない\PCFGに対して，Stolckeの方法は我々の枠組でEarleyパーザと\gEMアルゴリズムを組み合わせた場合と等価である．すなわち，このようなPCFGに対して我々の枠組はStolckeの方法の一般化になっている．Stolckeの方法との対応づけを付録~\ref{sec:Stolcke}に示す．また，StolckeはPCFGの拡張文法については言及していない．$\varepsilon$規則やサイクル$A\derivesplusA$をもつPCFGに対する訓練法を考えるのは今後の課題であるが，提案手法は現段階においても充分実用的である．PerairaとSchabesは部分もしくは完全括弧コーパスからPCFGの文法構造を学習する方法を提案し，学習された文法構造とパラメタの質が括弧なしコーパスからの学習に比べ大きく向上することを実験的に示した~\cite{Pereira92}．我々の枠組でも，括弧づけされた文に対し，括弧の制約を満たす構文木のみを出力する機能をもつパーザを用意すれば\footnote{節~\ref{sec:experiment}で用いたMSLRパーザはそのような機能を備えている．}，支持グラフ抽出ルーチン，gEMアルゴリズムに何の変更も加えることなく括弧つきコーパスからの訓練が可能になる．変更の必要がないのは，我々が最終的な構文木情報（すなわちWFST）のみを参照するためである．また，完全に括弧づけされた訓練コーパスに対し\gEMアルゴリズムの計算量はPereiraとSchabesの方法と同じオーダ$O(|\Vn|^3LN)$であることも容易に分かる\footnote{PereiraとSchabesは$O(L)$としか明記していないが，彼らが提示したアルゴリズムより$\Rmax(\Vn,\Vt)$に対して\$O(|\Vn|^3LN)$となることは明らかである．また，gEMアルゴリズムで$O(|\Vn|^3LN)$であることは次のように示される：まず，$\win_\ell$に与えられた括弧集合$\brackets(\win_\ell)$のサイズは（PereiraとSchabesも述べているように）$O(|\win_\ell|)$である．与えられた$\brackets(\win_\ell)$と一致しない部分木は最終的な構文木にはならない（すなわち$O_\ell$の要素にはならない）ので，$\forall\ell=1\ldotsN$について$|O_\ell|=\left|\{A(d,d')\midA\in\Vn\;\mbox{かつ}\;(d,d')\in\brackets(\win_\ell)\}\right|=O(|\Vn|\cdot|\win_\ell|)=O(|\Vn|L)$である．また，式~\ref{eq:possible-psi}において，$\brackets(\win_\ell)$に一致する$d'$は高々1つであるから，すべての$\ell=1\ldotsN$について$|\subtrees_\ell(A(d,d'))|=O(|\Vn|^2)$である．従って，式~\ref{eq:xi-num}より$\mu_{\rmnum}=O(|\Vn|^3L)$である．前の議論と同様に$\mu_{\rmmaxsize}=O(1)$であるから，gEMアルゴリズムにおいて一回のパラメタ更新に要する計算量は\$O(|\Vn|^3LN)$である．}．本論文の手法は文法構造(CFG)が与えられていることを前提としているが，人間が精密な文法を記述するのに多くの手間を費やすことを考えると，文法構造の自動学習は重要な課題である．先述したように，LariとYoungは非終端記号集合$\Vn$と終端記号集合$\Vt$をあらかじめ定めた上で先述した$\Rmax(\Vn,\Vt)$を考え，I-Oアルゴリズムを走らせ，推定後にパラメタ値が小さい規則を除去する方法を提案した~\cite{Lari90}．また，先述したPereira\&Schabesの学習法~\cite{Pereira92}も括弧づけコーパスからの文法学習と捉えることができる．しかし，一般にEMアルゴリズムは局所的な最尤推定値しか保証しないため，学習される文法の質はパラメタの初期値に大きく依存し，文法学習を困難にしている．それに対し，HMMでは逐次状態分割(SSS)法~\cite{Takami93}やモデル選択規準に基づくHMMの構造探索法~\cite{Ikeda95}のように，パラメタ訓練と構造探索を分離し，これらを交互に繰り返して良質なモデル構造を得る方法が提案されている．どちらの手法もパラメタ訓練ステップではモデル（文法）構造が与えられるので，上記手法をPCFGの構造学習に一般化したとき\footnote{もちろん，そのときはパラメタ訓練ステップが更に構文解析ステップとgEMアルゴリズムステップに分離される．}，本論文で示した高速化が有効に働くものと期待する．本論文で示したgEMアルゴリズムは最小モデル意味論の確率的一般化である分布意味論~\cite{Sato95}に基づく確率的な論理プログラミング言語PRISM~\cite{Sato97}における高速EM学習のために提案されたものである~\cite{Kameya00}．そこではOLDT探索~\cite{Tamaki86}とgEMアルゴリズムを連結するが，本論文の手法はPCFGおよびその拡張文法用に\OLDTをパーザに置き換えて特殊化を図ったものである．OLDT探索を構文解析に用いることも可能だが，OLDT探索はトップダウン（仮説駆動）探索であるので，LR表へのコンパイル・ボトムアップ探索を利用するGLRパーザの方が現実文法ではより高速である．得られる支持グラフはまったく同じなのでgEMアルゴリズムの計算時間は変わらない．
\section{まとめ}
\label{sec:conclusion}文法構造が与えられていることを前提に，確率文脈自由文法(PCFG)を括弧なしコーパスから訓練するための一般的な枠組を提案し，従来法であるInside-Outsideアルゴリズムの一般化と（現実文法における）高速化を同時に実現した．提案手法ではPCFGの訓練過程を構文解析とEM学習を分離し，パーザが記録するWFSTから訓練文と関係のある部分木構造のみを抽出してからEM学習することにより，仮説駆動型であった\Inside-Outsideアルゴリズムの計算効率上の欠点を克服した．また，従来知られてきた構文解析の高速化技術がPCFGの訓練にそのまま反映される．更に，提案手法を実装し，ATR対話コーパスにおける訓練時間を計測したところ，Inside-Outsideアルゴリズムに比べコーパス平均文長においておよそ1,000倍の速度向上が得られることを確認した．また，提案手法の一般性に基づき，文脈依存性を考慮したPCFGの拡張文法（北らの規則バイグラムモデル）の多項式オーダのEMアルゴリズムを導出した．加えて，確率EarleyパーザによるStolckeのEM学習法やPereiraとSchabesらによる部分括弧つきコーパスからの学習法も提案手法の枠組で扱えることを示し，提案手法がCFGに基づく確率言語モデルの訓練手法を広くカバーしていることを明らかにした．今後の課題としては，PCFGの拡張文法を用いた実験や文法構造の学習，また支持グラフとgEMアルゴリズムの一般性を利用して，Inuiらによって再定式化された確率GLRモデル~\cite{Inui98}の効率的なEMアルゴリズムの導出を試みるのも興味深い．\subsection*{謝辞}実験に用いたATRコーパス，日本語文法の改訂版は，東京工業大学\田中・徳永研究室のご厚意により提供頂きました．記して感謝致します．また，同研究室白井清昭助手には上記コーパス・文法に関する情報やテキスト処理プログラムの提供，文献紹介など貴重なご助力を頂きました．重ねて感謝申し上げます．また，東京工業大学佐藤泰介研究室の上田展久氏には文献紹介を含め，数多くの有益なコメントを頂きました．感謝致します．なお，本研究の一部は平成11年度科学研究費補助金特定領域研究(A)「発見科学」の補助を受けています．\bibliographystyle{jnlpbbl}\bibliography{draft}\appendix
\section{グラフィカルEMアルゴリズムの正当化}
\label{sec:GEM-validity}本節ではFujisakiらの方法，I-Oアルゴリズム，gEMアルゴリズムに同じ初期パラメタを与えたとき，収束条件を同一にすればパラメタが同一の値に収束することを示す．これによりgEMアルゴリズムが正当化される．具体的にはgEMアルゴリズムが計算する$\eta[A\dto\zeta]$,すなわち規則$(A\dto\zeta)\inR$の期待適用回数がFujisakiらの方法，およびI-Oアルゴリズムで得られるものと一致することを示せばよい．また，節~\ref{sec:PCFG:IO-problems}で見たように，Fujisakiらの方法とI-Oアルゴリズムが計算する$\eta[A\dto\zeta]$は一致するので，ここではFujisakiらの方法とgEMアルゴリズムで計算される\$\eta[A\dto\zeta]$を調べれば十分である．はじめに，我々はgEMアルゴリズムの計算は支持グラフの1つ目の特徴である支持グラフ$\sg_\ell$の再帰的巡回を考える．そして，以下では$\tau$の部分支持グラフの開始（終了）ノードを「$\tau$の開始（終了）ノード」と呼ぶことにする．節~\ref{sec:GEM:support-graph}で述べたように，我々は巡回中に基本ノードに付与されている規則を集めることにする．まず，$\sg_\ell$中に出現する$A\dto\zeta$が付与された基本ノードの一つ$v$に注目する．$v$は$\tau$の部分支持グラフに含まれているとし，$v$が属する局所パスを$E$とおく．その状況を図~\ref{fig:v-in-sg}に示す．そして，$S(0,n_\ell)$の開始ノードから出発して$v$を通過するような再帰的巡回を全通り行ない，そこで集められた規則列の集合を$\trees(v,\win_\ell)$とおく\（明らかに$\trees(v,\win_\ell)\subseteq\trees(\win_\ell)$である）．\begin{figure}[b]\atari(56,48)\caption{支持グラフ$\sg_\ell$に出現する$A\dto\zeta$が付与された基本ノード$v$.}\label{fig:v-in-sg}\end{figure}$\tau$の開始ノードから$E$に沿って$\tau$の終了ノードに至る巡回によって得られる部分規則列を$\rseq_1$とおく．また$O_\ell$の先頭である$S(0,n_\ell)$の開始ノードから出発し，$\tau$が付与された中間ノード$u$（図~\ref{fig:v-in-sg}）に至る巡回，および$u$から$S(0,n_\ell)$の終了ノードに至る巡回によって得られた部分規則列をそれぞれ$\rseq_0$,$\rseq_2$とおく．そして，このような$\rseq_1$すべてから成る集合を\$\treesin(v,\win_\ell)$とおき，可能な$\rseq_0,\rseq_2$の組$\tuple{\rseq_0,\rseq_2}$から成る集合を$\treesout(v,\win_\ell)$とする．すると，先に定義した$\trees(v,\win_\ell)$は\$\treesin(v,\win_\ell)$と$\treesout(v,\win_\ell)$の直積と同一視できる．以上の定義と，PCFGにおける規則適用に関する独立性の仮定より，\begin{eqnarray*}\textstyle\sum_{\rseq'\in\trees(v,\win_\ell)}P(\rseq')&=&\textstyle\sum_{\tuple{\rseq_0,\rseq_1,\rseq_2}\in\trees(v,\win_\ell)}P(\rseq_0,\rseq_1,\rseq_2)\\&=&\textstyle\sum_{\rseq_1\in\treesin(v,\win_\ell)}\sum_{\tuple{\rseq_0,\rseq_2}\in\treesout(v,\win_\ell)}P(\rseq_1)P(\rseq_0,\rseq_2)\\&=&\textstyle\left(\sum_{\rseq_1\in\treesin(v,\win_\ell)}P(\rseq_1)\right)\left(\sum_{\tuple{\rseq_0,\rseq_2}\in\treesout(v,\win_\ell)}P(\rseq_0,\rseq_2)\right)\end{eqnarray*}が成り立つ．手続き$\proc{Get-Inside-Probs}$における$\varP$と\$\varR$の計算を再帰的に追えば，手続き終了時に\$\varR[\ell,\tau,E]=\sum_{\rseq_1\in\treesin(v,\win_\ell)}P(\rseq_1)$となることは明らか．また，手続き$\proc{Get-Expectations}$の$\varQ$の計算を追えば，$\varQ[\ell,\tau]=\sum_{\tuple{\rseq_0,\rseq_2}\in\treesout(v,\win_\ell)}P(\rseq_0,\rseq_2)$であることが分かる．よって\$\varQ[\ell,\tau]\cdot\varR[\ell,\tau,E]=\sum_{\rseq'\in\trees(v,\win_\ell)}P(\rseq')$となる．これより$\proc{Get-Expectations}$行~\ref{list:get-exp:updateON}で$\varON[A\dto\zeta]$に足し込まれる値は\$\frac{1}{P(\win_\ell)}\sum_{\rseq'\in\trees(v,\win_\ell)}P(\rseq')$に等しい．$A\dto\zeta$が付与された他の基本ノードについても同じ作業が行なわれ，さらにこれを$\ell=1\ldotsN$で繰り返すので，最終的に\$\varON[A\dto\zeta]$は次のように計算される：\begin{equation}\varON[A\dto\zeta]=\sum_{\ell=1}^N\frac{1}{P(\win_\ell)}\sum_{v:\;A\to\zeta\;{\rmis\;attached}}\;\sum_{\rseq'\in\trees(v,\win_\ell)}P(\rseq')\;.\label{eq:naive-eta4}\end{equation}ところで，$S(0,n_\ell)$の開始ノードから出発する一つの再帰的巡回を考え，そこで集められた規則列を$\rseq$とする．そのとき，この巡回において$A\dto\zeta$が付与された基本ノードを通過する回数は$\occ(A\dto\zeta,\rseq)$である．従ってこの$\rseq\in\trees(\win_\ell)$について，和\$\sum_{v:\;A\to\zeta\;{\rmis\;attached}}\;\sum_{\rseq'\in\trees(v,\win_\ell)}$では$\rseq$が$\occ(A\dto\zeta,\rseq)$回重複して数え上げられている．よって式~\ref{eq:naive-eta4}はFujisakiらの計算式（式~\ref{eq:Fujisaki-eta}）と同値になる．以上と本節冒頭に述べた注意より，Fujisakiらの方法，I-Oアルゴリズム，gEMアルゴリズムに同じ初期パラメタを与えたとき，収束条件を同一にすればパラメタは同じ値に収束する．
\section{Stolckeの方法との対応}
\label{sec:Stolcke}本節ではStolckeが提案した確率的Earleyパーザを用いるPCFGの訓練法~\cite{Stolcke95}と提案手法においてEarleyパーザとgEMアルゴリズムを組み合わせた場合を簡単に対応づける．はじめに確率的Earleyパーザを簡単に記述する\footnote{確率的Earleyパーザの記述は基本的にStolckeの記法に従うが，本論文の記法に合わせた箇所もある．また，用語は\cite{Tanaka88}のものを用いる場合がある．}．\subsection{確率的Earleyパーザ}Earleyパーザは入力文$\win_\ell$の各単語位置をアイテム集合（Earleyチャート）$I_\ell$に基づいて構文解析を行なう．各アイテムは``$\es{d'}{d}{A\dto\zeta.\xi}$''の形をしており，(i)現在のポインタの位置が$d'$（$\win_{0,d'}^{(\ell)}=w_1^{(\ell)}\cdotsw_{d'}^{(\ell)}$が解析済み）であること，(ii)非終端記号$A$が統治する部分単語列が位置$d$から始まること，(iii)$A$の展開は規則$A\dto\zeta\xi$を用いて進められ，ドットの場所まで展開されていること，を表す．確率的Earleyパーザでは，Earleyパーザに確率的な拡張が施されており，各アイテムに内側確率$\ip{d'}{d}{A\dto\zeta.\xi}$が式~\ref{eq:pitem}のように付与される（式中の$\beta$は$\ip{d'}{d}{A\dto\zeta.\xi}$の略記）\footnote{\cite{Stolcke95}では内側確率の他に前向き確率と呼ばれる確率値を各アイテムに付与するが，EM学習とは無関係なのでここでは省略する．その他にもEM学習と無関係な記述は省略されている．}．内側確率$\ip{d'}{d}{A\dto\zeta.\xi}$はアイテム$\es{d}{d}{A\dto.\zeta\xi}$から始まり，$\es{d'}{d}{A\dto\zeta.\xi}$に至る経路の確率和である．\begin{equation}\esp{d'}{d}{A\dto\zeta.\xi}{\beta}\label{eq:pitem}\end{equation}内側確率は次の3つの操作に従って計算される．\begin{description}\item{\bf$\diamond$Prediction:}アイテム$\esp{d'}{d}{A\dto\zeta.B\xi}{\beta}$が存在し，かつ$(B\dto\nu)\inR$であるとき，アイテム$\esp{d'}{d'}{B\dto.\nu}{\beta'}$が$I_\ell$中に存在しなければ，そのアイテムを$I_\ell$に追加する．ただし，$\beta'=\theta(B\dto\nu)$である．もし存在すれば何も行なわない．\item{\bf$\diamond$Scanning:}アイテム$\esp{(d'-1)}{d}{A\dto\zeta.w_{d'}^{(\ell)}\xi}{\beta}$が$I_\ell$中に存在するとき，$\esp{d'}{d}{A\dto\zetaw_{d'}^{(\ell)}.\xi}{\beta'}$が$I_\ell$に存在しなければ，これを$I_\ell$に追加する．ただし\$\beta'=\beta$である．\item{\bf$\diamond$Completion:}$d''<d'$なる\footnote{$d''\led'$と等号が入らないのは，我々が$\varepsilon$規則をもたず$A\derivesplusA$とならない文法構造(CFG)を仮定しているためである．Stolckeは両者を許しているので，彼の記述では等号が入っている．}2つのアイテム$\esp{d'}{d''}{B\dto\nu.}{\beta''}$および$\esp{d''}{d}{A\dto\zeta.B\xi}{\beta}$が$I_\ell$に存在するとき，$\esp{d'}{d}{A\dto\zetaB.\xi}{\beta'}$が$I_\ell$に存在しなければ，これを$I_\ell$に追加する．ただし，$\beta'=\beta\cdot\beta''$である．存在しているときは\$\beta'\;\incby\;\beta\cdot\beta''$とする．\end{description}EM学習においては更にアイテム$\es{d'}{d}{A\dto\zeta.\xi}$の外側確率$\op{d'}{d}{A\dto\zeta.\xi}$を考慮する．この確率は(i)初期アイテム$\es{0}{0}{\dto.S}$から出発し，(ii)$\win_{0,d}^{(\ell)}$を生成し，(iii)ある$\nu$について${}_{d}A\dto.\nu\xi$を通り，(iv)${}_{d'}A\dto\nu.\xi$から出発して\$\win_{d',n_\ell}^{(\ell)}$を生成し，(v)最終アイテム$\es{n_\ell}{0}{\toS.}$で終わるような経路の確率和である．\begin{description}\item{\bf$\diamond$Reversecompletion:}$I_\ell$中の\$\esp{d'}{d''}{B\dto\nu.}{\alpha'',\beta''}$と$\esp{d''}{d}{A\dto\zeta.B\xi}{\alpha',\alpha'}$の組すべてに対し，$\esp{d'}{d}{A\dto\zetaB.\xi}{\alpha,\beta}$を見つけ，$\alpha'\;\incby\;\beta''\cdot\alpha$と\$\alpha''\;\incby\;\beta'\cdot\alpha$を行う．\end{description}ただし，アイテム$\esp{n_\ell}{0}{S\dto\nu.}{\alpha}$のみ\$\alpha:=1$と初期化し，それ以外は$\alpha:=0$としておく．すべての内側確率と外側確率を計算し終ったら，規則$A\dto\zeta$の期待適用回数を次のように求め，後はI-Oアルゴリズムの式~\ref{eq:update}と同様にパラメタを更新する．\begin{equation}\varON[A\dto\zeta]=\sum_{\ell=1}^N\frac{1}{\ip{n_\ell}{0}{\toS.}}\sum_{(d:{}_d{A\to.\zeta})\inI_\ell}\op{d}{d}{A\dto.\zeta}\ip{d}{d}{A\dto.\zeta}\label{eq:update-Stolcke}\end{equation}\subsection{対応する支持グラフ}\label{sec:Stolcke:support-graph}図~\ref{alg:learn-PCFG}のメインルーチン$\proc{Learn-PCFG}$における支持グラフ抽出ルーチン$\proc{Extract-CYK}$をEarleyパーザ用の支持グラフ抽出ルーチン$\proc{Extract-Earley}$（図~\ref{alg:extract-Earley}）に置き換える．そのサブルーチン$\proc{Visit-Earley}$を図~\ref{alg:visit-Earley}に示す．gEMアルゴリズムは汎用であるため，手続きを特に変更する必要はない．$\proc{Extract-Earley}$はEarleyパーザの構文木出力ルーチンに基づいて記述されており，支持グラフ\$\sg_\ell=\tuple{O_\ell,\subtrees_\ell}$を生成する．$\subtrees_\ell$は次のような形をしている．\begin{eqnarray}\subtrees_\ell(\es{d}{d}{B\dto.\nu})&=&\bigl\{\{B\dto\nu\}\bigr\}\label{eq:subtrees-earley:1}\\\subtrees_\ell(\es{d'}{d}{A\dto\zetaw_{d'}^{(\ell)}.\xi})&=&\bigl\{\{\es{(d'-1)}{d}{A\dto\zeta.w_{d'}^{(\ell)}\xi}\}\bigr\}\label{eq:subtrees-earley:2}\\\subtrees_\ell(\es{d'}{d}{A\dto\zetaB.\xi})&=&\Bigl\{\bigl\{(\es{d''}{d}{A\dto\zeta.B\xi}),\;(\es{d'}{d''}{B\dto\nu.})\bigr\}\nonumber\\&&\q\q\q\q\q\Big|\;d\led''<d',(\es{d'}{d''}{B\to\nu.})\inI_\ell\Bigr\}\label{eq:subtrees-earley:3}\end{eqnarray}\begin{figure}[b]\begin{listing}\item\rw{procedure}$\proc{Extract-Earley}()$\rw{begin}\itemi\rw{for}$\ell:=1$\rw{to}$N$\rw{do}\itemiiInitializeall$\subtrees_\ell(\cdot)$to$\emptyset$andall$\varComp[\cdot]$to$\sym{NO}$;\itemii$\proc{ClearStack}(U)$;\itemii$\proc{Visit-Earley}(\ell,\es{n_\ell}{0}{\toS.})$;\itemii\rw{for}$k:=1$to$|U|$\rw{do}$\tau_k:=\proc{PopStack}(U)$;\itemii$O_\ell:=\tuple{\tau_1,\tau_2,\ldots,\tau_{|U|}}$\itemi\rw{end}\item\rw{end}.\end{listing}\caption{Earleyパーザ用の支持グラフ抽出ルーチン$\proc{Extract-Earley}()$．}\label{alg:extract-Earley}\end{figure}式~\ref{eq:subtrees-earley:1}の部分支持グラフに対するgEMアルゴリズムの内側確率の計算が確率的EarleyパーザのPrediction操作に対応する．同様に式~\ref{eq:subtrees-earley:2}に対するgEMアルゴリズムの内側確率計算がScanning操作に対応する．さらに，式~\ref{eq:subtrees-earley:3}に対するgEMアルゴリズムの内側確率計算がCompletionに，外側確率計算がReversecompletion操作に各々対応する．そして，式~\ref{eq:subtrees-earley:1}の部分支持グラフでの期待値計算が式~\ref{eq:update-Stolcke}に対応する．この場合のgEMアルゴリズムの計算量としては，式~\ref{eq:subtrees-earley:3}の形の$\subtrees_\ell$をもつ部分支持グラフに対する部分が効いてくる．Chomsky標準形を満たす文法に対しては，このような部分支持グラフのノード数は可能な規則および単語位置\$d$,$d'$,$d''$の組合せ数$O(|R|L^3)$となる（$R$は規則集合，$L$はコーパス中の最大文長）．$R=\Rmax$のときgEMアルゴリズムの最悪計算量はStolckeの確率的Earleyパーザのものと同じく$O(|\Vn|^3L^3)$となる．また，Chomsky標準形を満たさない場合を考え，規則右辺の最大記号数を\$m$とおく．提案手法において，式~\ref{eq:parent-children}のような部分木の親子対を構成要素とするWFSTをもつパーザ（GLRなど）を用いた場合の計算量は$O(L^{m+1})$となるが，Earleyパーザを用いた場合の計算量は\Stolckeの確率的Earleyパーザと同じく，$m$によらず$O(L^3)$になる．ただ，GLRはLR表への事前コンパイル・ボトムアップ計算等の好ましい性質を持っており，対象とする文法の特徴に応じてパーザを使い分けることが重要と思われる．\begin{figure}[h]\begin{listing}\item\rw{procedure}$\proc{Visit-Earley}(\ell,\es{d'}{d}{A\dto\zeta.\xi})$\rw{begin}\itemiPut$\tau=(\es{d'}{d}{A\dto\zeta.\xi})$\itemi$\varComp[\tau]:={\ttYES}$;\itemi\rw{if}$\zeta=\varepsilon$and$d'=d$\rw{then}\q\progcomment{$\es{d}{d}{A\dto.\xi}$(Prediction)}\itemii$\subtrees_\ell(\tau):=\bigl\{\{A\dto\xi\}\bigr\}$\itemi\rw{else}\rw{if}$\zeta=\zeta'w_{d'}^{(\ell)}$\rw{then}\rw{begin}\q\progcomment{$\es{d'}{d}{A\dto\zeta'w_{d'}^{(\ell)}.\xi}$(Scanning)}\itemiii$\subtrees_\ell(\tau):=\bigl\{\{\es{(d'-1)}{d}{A\dto\zeta'.w_{d'}^{(\ell)}\xi}\}\bigr\}$;\itemiii\rw{if}$\varComp[\es{(d'-1)}{d}{A\dto\zeta'.w_{d'}^{(\ell)}\xi}]={\ttNO}$\rw{then}$\proc{Visit-Earley}(\ell,\es{(d'-1)}{d}{A\dto\zeta'.w_{d'}^{(\ell)}\xi})$\itemii\rw{end}\itemi\rw{else}\rw{begin}\itemiiPut$\zeta=\zeta'B$;\q\progcomment{$B$は非終端記号;$\es{d'}{d}{A\dto\zeta'B.\xi}$(Completion)}\itemii\rw{foreach}$d''$suchthat$d\led''<d'$and$(\es{d''}{d}{A\dto\zeta'.B\xi}),(\es{d'}{d''}{B\dto\nu.})\inI_\ell$\rw{do}\rw{begin}\itemiiiAddaset$\bigl\{(\es{d''}{d}{A\dto\zeta'.B\xi}),(\es{d'}{d''}{B\dto\nu.})\bigr\}$to$\subtrees_\ell(\tau)$;\itemiii\rw{if}$\varComp[\es{d''}{d}{A\dto\zeta'.B\xi}]={\ttNO}$\rw{then}$\proc{Visit-Earley}(\ell,\es{d''}{d}{A\dto\zeta'.B\xi})$;\itemiii\rw{if}$\varComp[\es{d'}{d''}{B\dto\nu.}]={\ttNO}$\rw{then}$\proc{Visit-Earley}(\ell,\es{d'}{d''}{B\dto\nu.})$\itemii\rw{end}\itemi\rw{end};\itemi$\proc{PushStack}(\tau,U)$\item\rw{end}.\end{listing}\caption{$\proc{Extract-Earley}()$のサブルーチン$\proc{Visit-Earley}$．}\label{alg:visit-Earley}\end{figure}}\newpage\begin{biography}\biotitle{略歴}\bioauthor{亀谷由隆}{1995年東京工業大学工学部情報工学科卒業．1997年同大学大学院情報理工学研究科修士課程修了．2000年9月同研究科博士後期課程修了．博士（工学）．同研究科技術補佐員を経て，現在同研究科リサーチアソシエイト．論理プログラミングに基づく確率推論システム研究に従事．人工知能学会会員．}\bioauthor{森高志}{1999年東京工業大学工学部情報工学科卒業．1999年同大学大学院情報理工学研究科修士課程入学，現在在学中．}\bioauthor{佐藤泰介}{1973年東京工業大学工学部電子物理学科卒業．1975年同大学大学院修士課程修了．工学博士．同年，電子技術総合研究所入所．以来，人工知能の研究に従事．1995年以来，東京工業大学大学院情報理工学研究科教授．人工知能学会，情報処理学会，EATCS各会員．}\bioreceived{受付}\bioaccepted{採録}\end{biography}\end{document}