\documentstyle[jnlpbbl,epsf]{jnlp_j}

\setcounter{page}{49}
\setcounter{巻数}{8}
\setcounter{号数}{1}
\setcounter{年}{2001}
\setcounter{月}{1}
\受付{2000}{5}{10}
\採録{2000}{10}{10}   

\setcounter{secnumdepth}{2}

\title{\bf WFSTに基づく確率文脈自由文法およびその\\
	拡張文法の高速EM学習法}
\author{亀谷 由隆\affiref{TiTech} \and 森 高志\affiref{TiTech}
	\and 佐藤 泰介\affiref{TiTech}}

\headauthor{亀谷 由隆・森 高志・佐藤 泰介}
\headtitle{WFSTに基づく確率文脈自由文法およびその拡張文法の高速EM学習法}

\affilabel{TiTech}{東京工業大学 大学院情報理工学研究科 計算工学専攻}
{Department of Computer Science, Graduate School of Information Science and
	Engineering, Tokyo Institute of Technology}

\jabstract{
現在，統計的言語モデルの一クラスとして確率文脈自由文法 (PCFG)
が広く知られている．また，括弧なしコーパスからPCFGを訓練する方法
として Inside-Outside (I-O)アルゴリズムが知られてきた．
I-O アルゴリズムは PCFG 用に効率化を施した EM
(expectation-maximization) アルゴリズムだが，
依然その計算速度に問題があることが知られている．
本論文では，文法構造があらかじめ与えられていることを前提に，
訓練過程を構文解析とEM学習に分離した高速 EM 学習法を提案する．
その中間データ構造にパーザが生成する WFST
(well-formed substring table) を用いる．
例えば，一般化LRパーザを用いると事前コンパイル・ボトムアップ
探索による効率性，および Chomsky 標準形を要求しないという一般性を
引き継ぐことができる．
一方EM学習では，WFSTのコンパクトさを利用して
効率的なパラメタ推定が行なわれる．
推定結果は I-O アルゴリズムで得られるものと一致する．
更に，文脈依存性を取り入れたPCFGの拡張モデルに対する多項式オーダの
EM学習法を示す．また，ATR対話コーパスを用いて実験を行ない，
訓練時間が大幅に短縮されていることを確認した．
}

\jkeywords{確率文脈自由文法，EMアルゴリズム，
	Inside-Outside アルゴリズム，WFST}

\etitle{Efficient EM learning of probabilistic CFGs\\
		and their extensions by using WFSTs}
\eauthor{Yoshitaka KAMEYA\affiref{TiTech} \and
		Takashi MORI\affiref{TiTech} \and
		Taisuke SATO\affiref{TiTech}}

\eabstract{
Probabilistic context-free grammars (PCFGs) are a widely-known class
of statistical language models. The Inside-Outside (I-O) algorithm
is also well-known as an efficient EM algorithm tailored for PCFGs.
Although the algorithm requires only inexpensive linguistic resources,
there remains a problem in its efficiency.
In this paper, we present a new framework for
efficient EM learning of PCFGs in which the parser is separated from
the EM algorithm, assuming the underlying CFG is given.
A new EM procedure exploits the compactness
of WFSTs (well-formed substring tables) generated by the parser.
Our framework is quite general in the sense 
that the input grammar need not to be in Chomsky normal form
(CNF) while the new EM algorithm is equivalent to the I-O algorithm
in the CNF case.
In addition, we propose a polynomial-time EM procedure for
CFGs with context-sensitive probabilities, and report
experimental results with ATR corpus
and a hand-crafted Japanese grammar.
}

\ekeywords{Probabilistic context-free grammars,
	The EM algorithm, The Inside-Outside algorithm, Well-formed
	substring table}


\begin{document}
\maketitle

{

\newcommand{\q}{}
\newcommand{\hq}{}
\newcommand{\iq}{}

\newcommand{\bvec}[1]{}
\newcommand{\sym}[1]{}
\newcommand{\tuple}[1]{}
\newcommand{\defined}{}
\newcommand{\incby}{}
\newcommand{\decby}{}
\newcommand{\mulby}{}
\newcommand{\Vn}{}
\newcommand{\Vt}{}
\newcommand{\dto}{}
\newcommand{\rderives}[1]{}
\newcommand{\derives}{}
\newcommand{\derivesstar}{}
\newcommand{\derivesplus}{}
\newcommand{\win}{}
\newcommand{\rseq}{}
\newcommand{\trees}{}
\newcommand{\treesin}{}
\newcommand{\treesout}{}
\newcommand{\subtrees}{}
\newcommand{\corpus}{}
\newcommand{\labels}{}
\newcommand{\brackets}{}
\newcommand{\Rmax}{}
\newcommand{\wfst}{}
\newcommand{\condrule}[3]{}
\newcommand{\lastrule}{}
\newcommand{\sg}{}  
\newcommand{\subsg}{}  
\newcommand{\occ}{} 
\newcommand{\Gtanaka}{}
\newcommand{\Rtanaka}{}

\newcounter{linenumber}
\newenvironment{listing}{}{}
\newcommand{\itemi}{}
\newcommand{\itemii}{}
\newcommand{\itemiii}{}
\newcommand{\itemiiii}{}
\newcommand{\itemiiiii}{}
\newcommand{\itemiiiiii}{}
\newcommand{\itemiiiiiii}{}
\newcommand{\itemiiiiiiii}{}
\newcommand{\itemiiiiiiiii}{}
\newcommand{\itemiiiiiiiiii}{}
\newcommand{\varinalg}[1]{}
\newcommand{\varP}{}
\newcommand{\varQ}{}
\newcommand{\varR}{}
\newcommand{\varON}{}
\newcommand{\varComp}{}
\newcommand{\varLast}{}
\newcommand{\rw}[1]{}
\newcommand{\proc}[1]{}
\newcommand{\progcomment}[1]{}

\newcommand{\es}[3]{}
\newcommand{\esp}[4]{}
\newcommand{\ip}[3]{}
\newcommand{\op}[3]{}

\section{はじめに}
\label{sec:intro}

現在，統計的言語モデルの一クラスとして確率文脈自由文法
（probabilistic context-free grammar; 以下PCFG）が広く知られている．
PCFG は文脈自由文法（context-free grammar; 以下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-formed substring table（以下 WFST）と呼ばれる
データ構造を利用しており，全体の訓練過程を次の2段階に
分離してPCFGを訓練する．
\begin{description}
\item\underline{\bf 構文解析}:\\
	はじめにパーザによって与えられたテキストコーパスもしくは
	タグ付きコーパス中の各文に構文解析を施し，その文の構文木
	すべてを得る．ただし，構文木は実際に構築せずに
	途中で構築される WFST のままでとどめておく．
\item\underline{\bf EM学習}:\\
	上で得られた WFST から支持グラフと呼ばれる
	データ構造を抽出し，新たに導出されたグラフィカルEM
	（graphical EM; 以下 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}\\
\hline
CYK 法&三角行列\\
Earley 法&
	アイテム集合（Earley チャート）の集まり\\
GLR法&圧縮共有構文森 (packed shared parse forest)\\
\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-free grammar
	with context-sensitive probability (CFG with CSP)'' を指す．
	具体的には 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\in Y$ と
書く．
集合 $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)\le 1,\;
	\sum_{\zeta:(A\to\zeta)\in R}\theta(A\dto\zeta)=1$
が成り立つとする ($A\in\Vn,\;r\in R$)．
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}
\textstyle
P(\rseq|\theta)=\prod_{k=1}^K\theta(r_k)
\label{eq:derivation-prob}
\end{equation}
と計算される．
また，$\occ(r,\rseq)$ を適用規則列 $\rseq$ 中に\
規則 $r$ が出現する数とすると，
\begin{equation}
\textstyle
P(\rseq|\theta)=\prod_{r\in R}\theta(r)^{\occ(r,\rseq)}
\label{eq:derivation-prob2}
\end{equation}
と書くこともできる．
$S\derivesstar\win$ を実現する適用規則列すべて
から成る集合を $\trees(\win)$ とおく．
文 $\win$ は適用規則列 $\rseq$ から一意に定まるので，
文と適用規則列の同時分布 $P(\win,\rseq|\theta)$ に関し
\begin{equation}
\textstyle
P(\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}
\textstyle
P(\win)
	=\sum_{{\rm all}\;\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\in L_G}P(\win|\theta)=1$ が成り立つ．
\item 右辺が $\varepsilon$ である規則（$\varepsilon$ 規則）や
	$A\derivesplus A$ となるような $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\cdots w_n\in L_G$ に対して
個々の $w_j$ は単語である ($n>0$, $j=1\ldots n$)．
$\win$ に対して単語位置 $d=0\ldots n$ を与える．
$0\le d\le d'\le n$ について $d$ と $d'$ の間にある部分単語列
$w_{d+1}\cdots w_{d'}$ を $\win_{d,d'}$ と書く
（$\win=\win_{0,n}$ である）．
また，（部分）単語列 $w_d\cdots w_{d'}$ をリスト\
$\tuple{w_d,\ldots,w_{d'}}$ で表すことがある．
$\win\in L_G$ に対して，$\win$ の構文木は\
$S\derivesstar\win$ の導出過程を木構造で表現したものである．
我々は導出戦略を最左導出に固定しているので，
$S\derivesstar\win$ の適用規則列 $\rseq$ から $\win$ の構文木 $t$ が
一意に決まり，逆も真である．従って $P(t)=P(\rseq)$ が成り立つ．
先に我々は対象とする PCFG が $\varepsilon$ 規則をもたないこと，
$A\derivesplus A$ という導出が起こらないと仮定した．
この仮定より，$\win$ の構文木 $t$ の部分構文木（以下，部分木）
$t'$ はその根ノードの非終端記号 $A$ と葉ノードを構成する
部分単語列の開始／終了位置の対 $(d,d')$ によって一意に定まるので，
以降，我々は部分木 $t'$ をラベル $A(d,d')$ で参照する．
$\win$ の構文木 $t$ は，葉ノードを除く $t$ の部分木ラベルから
成る集合 $\labels(t)$ （$t$ のラベル集合と呼ぶ） と同一視できる．
また，$(d,d')$ は一つの括弧づけに相当する．
$\brackets(t)\defined\{(d,d')\mid A(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\ldots M$)．
この関係を以降では「$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)構造つきコーパス (labeled corpus)，
(2)完全括弧つきコーパス (fully bracketed corpus)，
(3)部分括弧つきコーパス (partially bracketed corpus)，
(4)括弧なしコーパス (unbracketed corpus)
の4つを考える．
我々は訓練法として最尤推定法 (maximum likelihood estimation)
を考えており，$N$ 文を含む
コーパス $\corpus\defined\tuple{c_1,c_2,\ldots,c_N}$ は
PCFG $G(\theta)$ に基づく独立な $N$ 回のサンプリング導出の結果
であると仮定する．
$\win_\ell$, $\rseq_\ell$ を $\ell$ 回目のサンプリングで得られた
平文および適用規則列とすると ($\ell=1\ldots N$)，
$\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\in L_G$,
$\rseq\in\trees(\win_\ell)$, $\brackets_\ell\subseteq\brackets(\rseq_\ell)$)．
$\win_\ell$ の部分単語列を\
$\win^{(\ell)}_{d,d'}$ とおき $(0\le d< d'\le n_\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\times n_\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}
\itemii Prepare $(n_\ell\times n_\ell)$ triangular matrix $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\dto w_{d+1})\in R\}$;
	\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\dto BC)\in R,$
\item\hfill
	$(B(d,d+k')@\;\cdot)\in T_{d,d+k'}^{(\ell)},
		(C(d+k',d+k)@\;\cdot)\in T_{d+k',d+k}^{(\ell)}\bigr\}$;
	\label{list:CYK:fill-non-diag:end}
\itemii \rw{if} $(S(0,n_\ell)@\;\cdot)
			\in T_{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}^N P(\win_\ell\mid\theta)$
あるいはその対数 $\sum_{\ell=1}^N \log P(\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\dto BC\;\left|\; A,B,C\in \Vn\right.\right\}
	\;\cup\;
	\left\{A\dto a\;\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\ldots N$,
$A\in \Vn$, $0\le d < d'\le n_\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$ such that
	$(A\dto w_{d+1}^{(\ell)})\in R$ \rw{do}
\itemiiii
	$\beta_{d,d+1}^{(\ell)}[A]:=\theta(A\dto w_{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\to BC)\in R}\theta(A\dto BC)
		\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\to BX)\in R}
			\theta(A\dto BX)
			\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'\to YB)\in R}\theta(A'\dto YB)
		\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]$ から対角要素に向かって
外側確率を計算する．
このように内側・外側確率は動的計画法 (dynamic programming)
に基づき，一方向に従って計算が進められる．
内側・外側確率を計算し終ったら，コーパス $\corpus$ が
与えられた下での規則 $A\dto BC$, $A\dto a$
の適用回数の条件つき期待値（以下，期待適用回数という）が
次のように計算される:

{\small
\begin{eqnarray}
\eta[A\dto BC]&:=&
	\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\dto BC)
		\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\dto a]&:=&
			\sum_{\ell=1}^N
				\frac{1}{\beta_{0,n_\ell}^{(\ell)}[S]}
			\sum_{d=0}^{n_\ell-1}\theta(A\dto a)\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')\in R}\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 \log P(\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}）中の {\bf for}, {\bf foreach} ループ
と $\sum$ の引数に注目すれば，I-O アルゴリズムの最悪計算量
は $O(|\Vn|^3 L^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_{{\rm all}\;\rseq}
			P(\rseq|\win_\ell)
			\occ(r,\rseq)
	=
	\sum_{\ell=1}^N
		\frac{1}{P(\win_\ell)}
		\sum_{{\rm all}\;\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{\partial P(\win_\ell)}{\partial \theta(r)}
	\;=\;
	\theta(r)
	\cdot\sum_{\ell=1}^N
		\frac{1}{P(\win_\ell)}
		\frac{\partial}{\partial \theta(r)}
		\sum_{{\rm all}\;\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\dto BC)$ とおいたとき，
I-O アルゴリズムでは\
$\frac{\partial}{\partial\theta(A\to BC)}
	\sum_{{\rm all}\;\rseq}P(\win_\ell,\rseq)$
を次のように計算する（添字の ${\cdot}_{\ell}$, ${\cdot}^{(\ell)}$ は
省略）．
\begin{eqnarray}
&&\frac{\partial}{\partial\theta(A\to BC)}
	\sum_{\mbox{\footnotesize all $\rseq$}}
		P(\win,\rseq)\nonumber\\
	&&\q\q\q=\frac{\partial}{\partial\theta(A\to BC)}
		\sum_{\mbox{\footnotesize
					all $\rseq$ s.t. $A\to BC$ appears in $\rseq$}}
		\iq\iq
		P(\win,\rseq)\nonumber\\
	&&\q\q\q=\frac{\partial}{\partial\theta(A\to BC)}
		\sum_{d,k,k'}
		\sum_{\mbox{\footnotesize
				\begin{tabular}{l}
				all $\rseq$ s.t. $A\to BC$ appears in $\rseq$\\
				\q with the position $(d,d+k',d+k)$
				\end{tabular}}}
		\iq\iq\iq\iq
		P(\win,\rseq)
	\label{eq:with-position}\\
	&&\q\q\q=\frac{\partial}{\partial\theta(A\to BC)}
		\sum_{d,k,k'}
			P(S\derivesstar\win_{0,d}A\win_{d+k,n})
			\theta(A\dto BC)\cdot\nonumber\\
	&&\q\q\q\q\q\q\q\q\q\q\q\q\q
			P(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\ldots N$ について以下を
おこなう．
まず，
$\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
	\Rightarrow k<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)\mid m=1\ldots M\}\\
	\q\q\q\q\cup\;\{A\dto\rho_1\rho_2\cdots\rho_M\},\q d=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\dto B_1 C_1,\;B_1(d,d''_1),\;C_1(d''_1,d')\},\;
		\{A\dto B_2 C_2,\;B_2(d,d''_2),\;C_2(d''_2,d')\}
	\;\bigr\}
\]
に対しては，「$\win_\ell$ に対して部分木 $A(d,d')$ を作るためには，
規則 $A\dto B_1 C_1$ を適用し，部分木 $B_1(d,d''_1)$ と部分木\
$C_1(d''_1,d')$ を作る，もしくは 規則 $A\dto B_2 C_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$ は再帰遷移ネットワーク
（recursive transition network; 以下 RTN）
に似た構造をもつ非循環有向グラフ(DAG)であり，
共通の辺をもたない部分グラフ\
$\subsg_\ell(\tau)\defined\tuple{\tau,\subtrees_\ell(\tau)}$
の集まりから成る（ただし $\tau\in O_\ell$）．
各 $\subsg_\ell(\tau)$ は「$\tau$ の部分支持グラフ」と呼ばれ，
$\tau=A(d,d')$ が付与されている．
また，$\subsg_\ell(\tau)$ は開始ノード，終了ノード
と呼ばれる2つの特殊なノードをもち（図~\ref{fig:support-graph-ichiro}
では各々 {\sf start}, {\sf end} と書かれている），
各 $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')\in E$ に
	ついても $\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\derivesplus A$
が存在しないという仮定と，$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}
\itemii Initialize all $\subtrees_\ell(\cdot)$ to $\emptyset$
	and all $\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}
\itemi Put $\tau=A(d,d')$ and then $\varComp[\tau]:={\tt YES}$;
	\q\progcomment{訪問を記録}
	\label{list:visit-CYK:mark}
\itemi \rw{if} $d'=d+1$ \rw{and}
	$A(d,d')@w_{d'}(d,d')\in T_{d,d'}^{(\ell)}$ \rw{then}
	Add a set $\{A\dto w_{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')\in T_{d,d'}^{(\ell)}$
	\rw{do} \rw{begin}
	\label{list:visit-CYK:foreachABC}
\itemiii Add a set $\{A\dto BC,\;B(d,d''),\;C(d'',d')\}$ to
	$\subtrees_\ell(\tau)$;
	\label{list:visit-CYK:add2}
\itemiii \rw{if} $\varComp[B(d,d'')]={\tt NO}$ \rw{then}
	\label{list:visit-CYK:recursion:begin}
	$\proc{Visit-CYK}(\ell,B,d,d'')$;
	\q\progcomment{再帰}
\itemiii \rw{if} $\varComp[C(d'',d')]={\tt NO}$ \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\in O_\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}
\itemi Initialize all parameters $\theta(A\dto\zeta)$
	such that $P(\win_\ell|\theta)>0$ for all $\ell=1\ldots N$;
	\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)\in R$ \rw{do}
	\label{list:gEM:update:begin}
\itemiii
	$\theta(A\dto\zeta):=
		\varON[A\dto\zeta]/\sum_{\zeta':(A\to\zeta')\in R}\varON[A\dto\zeta']$;
	\label{list:gEM:update:end}
\itemii $m\incby 1$;
\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)}$ becomes sufficiently small
	\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}
\itemii Put $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'\in E$ \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)\in R$ \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}
\itemii Put $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'\in E$ \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'\in E$ を考える．
また，行~\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\ldots N$ について $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\Rightarrow P(\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\in R$ について $\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_{{\rm all}\;\rseq}P(\rseq|\win_\ell)=
	\max_{{\rm all}\;\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}
\itemi Put $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}
\itemii Put $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]$ such that $\tau'=A(d,d')$
	\rw{do} \rw{begin}
\itemii Add $\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}$ では {\bf repeat}
ループ内の計算量をはかればよい．まず，
各 $\ell=1\ldots N$ について\
$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_{\rm num}&\defined&
	\max_{\ell=1\ldots N}
		\sum_{k=1}^{|O_\ell|}\big|\subtrees_\ell(\tau_k^{(\ell)})\big|
	\label{eq:xi-num}\\
\mu_{\rm maxsize}&\defined&
	\max_{E:\;\ell=1\ldots N,\;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_{\rm num}\mu_{\rm maxsize}N)$ である．同様に 
手続き $\proc{Get-Expectations}$ においても\
$O(\mu_{\rm num}\mu_{\rm maxsize}N)$ の計算量を要する．

I-O アルゴリズムの計算量評価と同様，
訓練コーパス $\corpus$ に対して最長の文の長さを $L$
とし，非終端記号集合 $\Vn$, 終端記号集合 $\Vt$ を固定する．
我々は Chomsky 標準形を満たす文法に対する最悪計算量を考える．
そのために，まず Chomsky 標準形を満たす最大の PCFG として
節~\ref{sec:PCFG:IO} 式~\ref{eq:Rmax} で導入した規則集合 $\Rmax$
を考える．
このとき，$A\in\Vn$, $0\le d, d'\le L$, $d+2\le d'$ なる\
$A$, $d$, $d'$ について下が成り立つ（$d'=d+1$ の場合は無視できる）：
\begin{equation}
\subtrees_\ell(A(d,d'))=
	\bigl\{\{A\dto BC,\;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')\mid A\in\Vn,\;0\le d<d'\le L\}\bigr|
=O(|\Vn|L^2)$ かつ $\big|\subtrees_\ell(\tau)\big|=O(|\Vn|^2 L)$
が成り立ち，定義より $\mu_{\rm num}=O(|\Vn|^3 L^3)$
となる．同様に定義より $\mu_{\rm maxsize}=3=O(1)$ である．
また，$\theta(A\dto\beta)$ の更新に要する計算量は $O(|\Rmax|)$
だが，$|\Rmax|=O(|\Vn|^3)$ なので無視できる．
以上より手続き $\proc{Graphical-EM}$
の {\bf repeat} ループ内の計算量は $O(|\Vn|^3 L^3 N)$ である．
以上より gEM アルゴリズムの最悪計算量は I-O アルゴリズム
と同じ $O(|\Vn|^3 L^3 N)$ である．

Chomsky 標準形を仮定したとき，CYKパーザ $\proc{CYK-Parser}$ と
支持グラフ抽出ルーチン $\proc{Extract-CYK}$
の最悪計算量は EM の一更新ステップの最悪計算量と同じ\
$O(|\Vn|^3 L^3 N)$ である．
ただ，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 (Morphological and Syntactic LR) パーザに
支持グラフ抽出ルーチンと gEM アルゴリズムのルーチンを連結した．
MSLR パーザは \verb|http://tanaka-www.cs.titech.ac.jp/pub/mslr/|
で公開されている．
MSLR パーザは形態素解析と構文解析を同時に行なう機能を有するが，
今回の実験では構文解析機能のみを使用した．
MSLRパーザを含め，実験で用いたプログラムはすべてC言語
で実装されている．Cコンパイラは gcc 2.8.1 を使用した．
また，実験で使用した計算機の CPU と OS はそれぞれ\
Sun UltraSPARC-II 296 MHz と Solaris 2.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,\ldots 26$)\footnote{
長さ 27 以上の 176 文（全体の 1.6 \%）はデータ不足の
ため，実験では考慮しなかった．
}．
そして，各 $\corpus_L$ を一つの訓練コーパスとし，各々に対して
更新時間を計測する．
I-O アルゴリズムは Chomsky 標準形でしか
動作しないので，あらかじめ $\Gtanaka$ を Chomsky 標準形に
変換した．その結果 860 規則が 2,308 規則（非終端記号数 210,
終端記号数 441）の文法になった．

更新時間を計測した結果を図~\ref{graph:1} 左に示す．
縦軸が更新時間(sec)，
横軸 $L$ が使用した訓練コーパス $\corpus_L$ を表す．
``{\it Inside-Outside}'' は I-O アルゴリズムの
更新時間，``{\it IO with pruning}'' は \cite{Kita99} で
説明されている，I-O アルゴリズムの外側確率の計算において
無駄な計算部分を枝刈りするように改良したものである．
これを以下では枝刈り版 I-O アルゴリズムと呼ぶ．
``{\it Graphical EM}'' は 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\times L$ の三角行列の全要素を
走査する）点は変わらないので，枝刈りが最も効率良く
行なわれた場合でも $L^2$ を下回ることはない．
収束まで数100回の更新を要すること，および再出発法を
採用することを考慮すると，$L=20$ を越える訓練コーパス\
$\corpus_L$ に 対して I-O アルゴリズムおよびその枝刈り版を
収束するまで動作させるのは現実的ではない．
それに対し，提案手法では $L=2,4,\ldots, 26$ の範囲では $L$ に
対してほぼ線形に計算できており（図~\ref{graph:1} 右），
最悪計算量 $O(|\Vn|^3 L^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に固定した．
構文解析時間 (``{\it Parsing}'')，
支持グラフ抽出時間 (``{\it Support graph}'')，
gEM 実行時間 (``{\it Graphical EM}'') はいずれも文長 $L$ に
対してほぼ線形になっていることが分かる．
更に図~\ref{graph:2}（右）より，再出発法を採用した場合は
構文解析時間と支持グラフ抽出時間が訓練時間全体に占める割合は
非常に小さい．構文解析と支持グラフ抽出は再出発の度に繰り返す
必要がないからである．
構文解析と支持グラフ抽出を gEM アルゴリズムの前処理と捉えれば，
わずかな前処理（図~\ref{graph:2}）で大きな速度向上
（図~\ref{graph:1}）が得られているということができ，
構文解析とEM学習を分離したメリットが現れている．


\section{PCFGの拡張文法のEM学習}
\label{sec:extensions}

これまで PCFG に文脈依存性を採り入れたモデル（PCFGの拡張文法と呼ぶ）
が数多く提案されているが，Charniak らの
疑似確率文脈依存文法 (pseudo probabilistic context-sensitive grammars)
\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\mid r_{k-1})
\end{equation}
と計算される．\# は境界を表すマーカ，$\theta(r\mid r')$ は
各規則 $r\in R$ に付与されるパラメタである($r'\in R\cup\{\#\}$)．
各 $A\in\Vn$, $r\in R\cup\{\#\}$ に対し
$\sum_{\zeta:(A\to\zeta)\in R}\theta(A\dto\zeta\mid r)=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'\in R}\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\tt ADV}\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}
\itemii Initialize all $\subtrees_\ell(\cdot)$ to $\emptyset$
	and all $\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}
\itemii Prepare some $\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\in R$'' ループを
重ねるだけでよい．

\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]:={\tt YES}$;
	\label{list:visit-RB:mark}
\itemi \rw{if}
		$d'=d+1$ and
		$A(d,d+1)@w_{d,d+1}^{(\ell)}\in T_{d,d+1}^{(\ell)}$ \rw{then}
	\rw{begin}
\itemiii Add a set $\{\condrule{A}{w_{d,d+1}^{(\ell)}}{r}\}$
			to $\subtrees_\ell(A(d,d+1|r,A\dto w_{d,d+1}^{(\ell)}))$;
	\label{list:visit-RB:diagonal:begin}
	\label{list:visit-RB:add1}
\itemiii $\varLast[A(d,d')]:=\{A\dto w_{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')\in T_{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\dto BC]={\tt NO}$
	\rw{then} $\proc{Visit-CYK-RB}(\ell,B,d,d'',A\dto BC)$;
	\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'']={\tt NO}$
	\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}
\itemiiiii
	Add a set $\bigl\{\condrule{A}{BC}{r},
			\;B(d,d''|A\dto BC,r''),\;C(d'',d'|r'',r')\bigr\}$
\itemiiiiiii to $\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^3 N)$
となる\footnote{
まず，$A\in\Vn$, $0\le d<d'\le L$ かつ $d+2 \le d'$ なる $A$, $d$, $d'$
および，$r,r'\in R$ について
\[
\subtrees_\ell(A(d,d'|r,r'))=
	\left\{
		\bigl\{
		\condrule{A}{BC}{r},\;B(d,d''|A\dto BC, r''),\;C(d'',d'|r'',r')
		\bigr\}
	\;\left|
	\begin{array}{l}
	B,C\in \Vn,\;d<d''<d',\\
	r''\in\lastrule(B,d,d'')\subseteq R
	\end{array}
	\right.
	\right\}
\]
となるような $A(d,d'|r,r')$ が $O_\ell$ 中に出現する
($\ell=1\ldots N$)．
$\left|\subtrees_\ell(\tau)\right|=O(|\Vn|^2 L |R|)$
であるのは明らかである．また，$O_\ell$ は\
$\big\{A(d,d'|r,r')\;\big|\;
	A\in\Vn,\;0\le d < d'\le L,\;r,r'\in R\big\}$
の部分集合を並べたものであるから，$|O_\ell|=O(|\Vn| L^2 |R|^2)$
となる．
定義より $\mu_{\rm num}=O(|\Vn|^3 L^3 |R|^3)$,
$\mu_{\rm maxsize}=O(1)$ であり，さらに最悪の場合 $R=\Rmax$ を
考えると gEM アルゴリズムの計算量は\
$O(|\Vn|^3 L^3 |\Rmax|^3 N)=O(|\Vn|^{12} L^3 N)$ となる．
}．
これは非常に大きなオーダであるが，文長 $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 らの ${\cal P}$earl \cite{Magerman91}
およびその後継である ${\cal P}$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\derivesplus A$ が存在しない\
PCFGに対して，Stolcke の方法は我々の枠組で Earley パーザと\
gEMアルゴリズムを組み合わせた場合と等価である．
すなわち，このような PCFG に対して我々の枠組は Stolcke の方法の
一般化になっている．
Stolcke の方法との対応づけを付録~\ref{sec:Stolcke} に示す．
また，Stolcke はPCFGの拡張文法については言及していない．
$\varepsilon$ 規則やサイクル $A\derivesplus A$
をもつPCFG に対する訓練法を考えるのは今後の課題であるが，
提案手法は現段階においても充分実用的である．

Peraira と Schabes は部分もしくは完全括弧コーパス
から PCFG の文法構造を学習する方法を提案し，
学習された文法構造とパラメタの質が
括弧なしコーパスからの学習に比べ大きく向上することを
実験的に示した~\cite{Pereira92}．
我々の枠組でも，括弧づけされた文に対し，括弧の制約を
満たす構文木のみを出力する機能をもつパーザを用意すれば\footnote{
節~\ref{sec:experiment} で用いた MSLR パーザはそのような
機能を備えている．
}，支持グラフ抽出ルーチン，gEM アルゴリズムに何の変更も加えることなく
括弧つきコーパスからの訓練が可能になる．
変更の必要がないのは，我々が最終的な構文木情報（すなわちWFST）
のみを参照するためである．
また，完全に括弧づけされた訓練コーパスに対し\
gEM アルゴリズムの計算量は Pereira と Schabes の方法と
同じオーダ $O(|\Vn|^3 L N)$ であることも容易に分かる\footnote{
Pereira と Schabes は $O(L)$ としか明記していないが，
彼らが提示したアルゴリズムより $\Rmax(\Vn,\Vt)$ に対して\
$O(|\Vn|^3 L N)$ となることは明らかである．
また，gEM アルゴリズムで $O(|\Vn|^3 L N)$ であることは次のように
示される：
まず，$\win_\ell$ に与えられた括弧集合 $\brackets(\win_\ell)$ のサイズは
（Pereira と Schabes も述べているように）$O(|\win_\ell|)$ である．
与えられた $\brackets(\win_\ell)$ と一致しない部分木は最終的な
構文木にはならない（すなわち $O_\ell$ の要素にはならない）ので，
$\forall \ell=1\ldots N$ について
$|O_\ell|=
	\left|\{A(d,d')\mid
			A\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\ldots N$ について
$|\subtrees_\ell(A(d,d'))|=O(|\Vn|^2)$ である．
従って，式~\ref{eq:xi-num} より $\mu_{\rm num}=O(|\Vn|^3L)$ である．
前の議論と同様に $\mu_{\rm maxsize}=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)\in R$ の期待適用回数が 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\ldots N$ で繰り返すので，最終的に\
$\varON[A\dto\zeta]$ は次のように計算される：
\begin{equation}
\varON[A\dto\zeta]
=\sum_{\ell=1}^N
\frac{1}{P(\win_\ell)}
\sum_{v: \; A\to\zeta\; {\rm is\;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\; {\rm is\;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)}\cdots w_{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)\in R$
であるとき，アイテム $\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\zeta w_{d'}^{(\ell)}.\xi}{\beta'}$ が $I_\ell$
に存在しなければ，これを $I_\ell$ に追加する．ただし\
$\beta'=\beta$ である．
\item{\bf $\diamond$ Completion:}
$d''<d'$ なる\footnote{
$d''\le d'$ と等号が入らないのは，我々が $\varepsilon$ 規則をもたず
$A\derivesplus A$ とならない文法構造 (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\zeta B.\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}{\to S.}$ で終わる
ような経路の確率和である．
\begin{description}
\item{\bf $\diamond$ Reverse completion:}
$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\zeta B.\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}{\to S.}}
\sum_{(d:{}_d {A\to.\zeta})\in I_\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\zeta w_{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\zeta B.\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\le d''< d',
					(\es{d'}{d''}{B\to\nu.})\in I_\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}
\itemii Initialize all $\subtrees_\ell(\cdot)$ to $\emptyset$
			and all $\varComp[\cdot]$ to $\sym{NO}$;
\itemii $\proc{ClearStack}(U)$;
\itemii $\proc{Visit-Earley}(\ell,\es{n_\ell}{0}{\to S.})$;
\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 に，外側確率計算が Reverse completion
操作に各々対応する．そして，式~\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|^3 L^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}
\itemi Put $\tau=(\es{d'}{d}{A\dto\zeta.\xi})$
\itemi $\varComp[\tau]:={\tt YES}$;
\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}
								]={\tt NO}$
			\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}
\itemii Put $\zeta=\zeta'B$;
		\q\progcomment{$B$ は非終端記号;
		$\es{d'}{d}{A\dto\zeta'B.\xi}$ (Completion)}
\itemii \rw{foreach} $d''$ such that
			$d\le d''< d'$ and
			$(\es{d''}{d}{A\dto\zeta'.B\xi}),
			(\es{d'}{d''}{B\dto\nu.})\in I_\ell$
				\rw{do} \rw{begin}
\itemiii Add a set 
			$\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}]=
					{\tt NO}$ \rw{then}
			$\proc{Visit-Earley}(\ell,\es{d''}{d}{A\dto\zeta'.B\xi})$;
\itemiii \rw{if} $\varComp[\es{d'}{d''}{B\dto\nu.}]=
					{\tt NO}$ \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}
