\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|$で表す．これらはどれも見た目は同じだが文脈で違いを判断できる．