



\documentstyle[fleqn,jnlpbbl]{jnlp_j}

\setcounter{page}{125}
\setcounter{巻数}{4}
\setcounter{号数}{1}
\setcounter{年}{1997}
\setcounter{月}{1}
\受付{1996}{4}{11}
\再受付{1996}{6}{11}
\採録{1996}{7}{18}


\makeatletter
\def\figcap#1#2{}
\def\tblcap#1#2{}
\makeatother
\newcommand{\inode}[1]{}

\title{括弧付きコーパスからの日本語確率文脈自由文法の自動抽出}
\author{白井 清昭\affiref{TITECH} \and
  徳永 健伸\affiref{TITECH} \and
  田中 穂積\affiref{TITECH}}

\headauthor{白井 清昭, 徳永 健伸, 田中 穂積}
\headtitle{括弧付きコーパスからの日本語確率文脈自由文法の自動抽出}

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

\jabstract{
\quad 
本論文では，括弧付きコーパスから確率文脈自由文法を
効率良く自動的に抽出する方法を提案する．
文法規則の抽出は，
日本語の主辞が句の一番最後の要素であるという特徴を利用して，
括弧付けによる構文構造の内部ノードに適切な非終端記号を
与えることによって行う．
また，文法規則の確率は規則のコーパスにおける出現頻度から推定する．
さらに，文法サイズの縮小と解析木数の抑制という2つの観点から，
抽出した文法を改良するいくつかの方法を提案する．
文法サイズの縮小は，文法に含まれる冗長な規則を自動的に
削除することによって行う．
解析木数の抑制は，
(1)同一品詞列に対して右下がりの二分木のみを生成し，
(2)``記号''と``助詞''の2つの品詞を細分化し，
(3)法や様態を表わす助動詞に対する構造を統一する
ことにより行う．
最後に，本手法の評価実験を行った．
約180,000の日本語文から確率文脈自由文法の抽出およびその改良を
行ったところ，2,219の文法規則を抽出することができた．
抽出された文法を用いて20,000文のテスト例文を統語解析したところ，
受理率が約92\%となり，適用範囲の広い文法が得られたことを確認した．
また，生成確率の上位30位の解析木の評価を行ったところ，
括弧付けの再現率が約62\%，括弧付けの適合率が約74\%，
文の正解率が約29\%という結果が得られた．
}

\jkeywords{コーパス，日本語，確率文脈自由文法}

\etitle{Automatic Extraction of Japanese Probabilistic\\
  Context Free Grammar From a Bracketed Corpus}
\eauthor{Kiyoaki shirai\affiref{TITECH} \and
  Takenobu Tokunaga\affiref{TITECH} \and
  Hozumi Tanaka}

\eabstract{
\quad 
In this paper, we describe a method to extract
a probabilistic context free grammar of Japanese
from a bracketed corpus.
To extract grammar rules,
we assign appropriate non-terminal symbols
to the intermediate nodes of the bracketed trees
by taking account of the heads of phrases.
We estimate the probabilities of the rules
based on their frequency of occurrence.
We also propose several improvements to the extracted grammar.
The size of the grammar is reduced
by removing any redundant rules.
The number of the parse tree is reduced
(1) by allowing only a right linear binary branching tree
for a constituent that consists of items of the same POS,
(2) by subcategorizing the POSs ``symbol''(``KIGOU'')
and ``postposition''(``JOSI''),
and (3) by assigning a consistent structure
to constructs representing clausal modality.
Finally, we conducted an experiment that evaluated the proposed methods.
2,219 grammar rules were extracted from about 180,000 sentences.
When we analyzed 20,000 test sentences with the extracted grammar,
a 92 \% acceptance rate was calculated, 
showing that the grammar has a broad coverage.
For the most probable 30 parse trees,
we obtained a 62 \% brackets recall, 74 \% brackets precision
and 29\% sentence accuracy.
}

\ekeywords{Corpus, Japanese, Probabilistic Context Free Grammar}

\begin{document}
\maketitle


\section{序論}
\label{sec:序論}

近年，機械可読な言語データの整備が進んだことや，
計算機能力の向上により大規模な言語データの取り扱いが
可能になったことから，
自然言語処理に用いる様々な知識を言語データから
自動的に獲得する研究が盛んに行われている\cite{utsuro95a}．
大量の言語データから自動的に獲得した知識は，
人手によって得られる知識と比べて，
獲得した知識が人間の主観に影響されにくい，
知識作成のためのコストが低い，
知識の適用範囲が広い，
知識に何らかの統計情報を容易に組み込むことができる，
といった優れた特徴を持っている．

言語データから自動獲得される自然言語処理用知識には
様々なものがあるが，その中の1つとして文法がある．
文法には様々なクラスがあるが，
統語解析の際に最もよく用いられるのは文脈自由文法
(Context Free Grammar，以下CFGと呼ぶ)であり，
一般化LR法，チャート法などのCFGを用いた
効率の良い解析手法がいくつも提案されている．
ところが，人手によってCFGを作成する場合，
作成の際に考慮されなかった言語現象については，
それに対応する規則がCFGに含まれていないために解析することができない．
これに対して，コーパスから自動的にCFGを抽出することができれば，
コーパス内に現れる多様な言語現象を網羅できるだけでなく，
人的負担も極めて軽くなる．
また，CFGの拡張の1つとして，文法規則に確率を付与した
確率文脈自由文法(Probabilistic Context Free Grammar，以下PCFGと呼ぶ)
がある\cite{wetherell80a}．
PCFGは，生成する複数の解析結果の候補(解析木)に対して，
生成確率による順序付けを行うことができるという点で
CFGよりも優れている．
そこで本論文では，CFGをコーパスから自動抽出し，
その後各規則の確率をコーパスから学習することにより
最終的にPCFGを獲得する手法を提案する．

CFGまたはPCFGをコーパスから自動獲得する研究は過去にも
いくつか行われている．
文法獲得に利用されるコーパスとしては，
例文に対して何の情報も付加されていない平文コーパス，
各形態素に品詞が割り当てられたタグ付きコーパス，
内部ノードにラベルのない構文木が与えられた括弧付きコーパス，
内部ノードのラベルまで与えられた構文木付きコーパスなど，
様々なものがある．
以下ではまず，文法獲得に関する過去の研究が，どのような種類のコーパスから
どのような手法を用いて行われているのかについて簡単に概観する．

平文コーパスからの文法規則獲得に関する研究としては
清野と辻井によるものがある~\cite{kiyono93a,kiyono94a,kiyono94b}．
彼らの方法は，まずコーパスの文を初期のCFGを用いて統語解析し，
解析に失敗した際に生成された部分木から，
解析に失敗した文の統語解析を成功させるために
必要な規則(彼らは仮説と呼んでいる)を見つけ出す．
次に，その仮説がコーパスの文の解析を成功させるのに
どの程度必要なのかを表わす尤度(Plausibility)を計算し，
高い尤度を持つ仮説を新たな規則として文法に加える．
彼らは全ての文法規則を獲得することを目的としているわけではなく，
最初からある程度正しいCFGを用意し，それを新たな領域に
適用する際にその領域に固有の言語現象を取り扱うために
必要な規則を自動的に獲得することを目的としている．

タグ付きコーパスからCFGを獲得する研究としては
森と長尾によるものがある~\cite{mori95a}．
彼らは，前後に現われる品詞に無関係に出現する品詞列を
独立度の高い品詞列と定義し，コーパスに現われる
品詞列の独立度をn-gram統計により評価する．
次に，ある一定の閾値以上の独立度を持つ品詞列を
規則の右辺として取り出す．
また，取り出された品詞列の集合に対して，
その前後に現われる品詞の分布傾向を利用してクラスタリングを行い，
同一クラスタと判断された品詞列を右辺とする規則の左辺に
同一の非終端記号を与える．
そして，得られた規則のクラスタの中からコーパス中に
最もよく現れるものを選び，それらをCFG規則として採用すると同時に，
コーパス中に現われる規則の右辺の品詞列を左辺の非終端記号に置き換える．
このような操作を繰り返すことにより，最終的なCFGを獲得すると同時に，
コーパスの各例文に構文木を付加することができる．


括弧付きコーパスからCFGを獲得する研究としては，
まずInside-Outsideアルゴリズムを利用したものが挙げられる．
LariとYoungは，与えられた終端記号と非終端記号の集合から
それらを組み合わせてできる全てのチョムスキー標準形の
CFG規則を作り，それらの確率をInside-Outsideアルゴリズムによって学習し，
確率の低い規則を削除することにより新たなPCFGを獲得する方法を
提案した~\cite{lari90a}．
この方法では収束性の悪さや計算量の多さが問題となっていたが，
この問題を解決するために，PereiraらやSchabesらは
Inside-Outsideアルゴリズムを部分的に括弧付けされたコーパスに対して
適用する方法を提案している~\cite{pereira92a,schabes93b}．
しかしながら，局所解は得られるが最適解が得られる保証はない，
得られる文法がチョムスキー標準形に限られるなどの問題点も残されている．
一方，括弧付きコーパスから日本語のCFGを獲得する研究としては
横田らのものがある\cite{yokota96a}．
彼らは，Shift-Reduceパーザによる訓練コーパスの例文の
統語解析が最も効率良くなるように，コーパスの内部ノードに
人工的な非終端記号を割り当てることによりCFGを獲得する
方法を提案している．
これは組み合わせ最適化問題となり，Simulated Annealing法を用いる
ことにより解決を求めている．
1000〜7500例文からCFGを獲得し，それを用いた統語解析では
15〜47\%の正解率が得られたと報告している．
この方法では，CFG獲得の際に統計情報のみを利用し，
言語的な知識は用いていない．
しかしながら，
利用できる言語学的な知識はむしろ積極的に利用した方が，
文法を効率良く獲得できると考えられる．

構文木付きコーパスから文法を獲得する研究としては
SekineとGrishmanによるものがある~\cite{sekine95a}．
彼らは，Penn Tree Bank~\cite{marcus93a} の中から
SまたはNPを根ノードとする部分木を自動的に抽出する．
解析の際には，得られた部分木をSまたはNPを左辺とし
部分木の葉の列を右辺としたCFG規則に変換し，
通常のチャート法により統語解析してから，
解析の際に使用した規則を元の部分木に復元する．
得られた解析木にはPCFGと同様の生成確率が与えられるが，
この際部分木を構成要素としているため若干の
文脈依存性を取り扱うことができる．
しかしながら，SまたはNPがある記号列に展開されるときの
構造としては1種類の部分木しか記述できず，
ここでの曖昧性を取り扱うことができないといった問題点がある．
また，構文木付きコーパスにおいては，
例文に付加された構文木の内部ノードにラベル(非終端記号)が
割り当てられているため，
通常のCFGならば構文木の枝分れをCFG規則と
みなすことにより容易に獲得することができる．

大量のコーパスからPCFGを獲得するには，
それに要する計算量が少ないことが望ましい．
ところが，統語構造情報が明示されていない平文コーパスや
タグ付きコーパスを用いる研究においては，
それらの推測に要する計算コストが大きいといった問題がある．
近年では，日本においてもEDRコーパス~\cite{edr95a} といった
大規模な括弧付きコーパスの整備が進んでおり，
効率良くCFGを獲得するためにはそのような括弧付きコーパスの
統語構造情報を利用することが考えられる．
一方，括弧付きコーパスを用いる
研究\cite{pereira92a,schabes93b,yokota96a} においては，
平文コーパスやタグ付きコーパスと比べて統語構造の情報が
利用できるとはいえ，反復アルゴリズムを用いているために
文法獲得に要する計算量は多い．
本論文では，括弧付きコーパスとしてEDRコーパスを利用し，
日本語の言語的特徴を考慮した効率の良いPCFG抽出方法を
提案する~\cite{shirai95b,shirai95a}．

本論文の構成は以下の通りである．
2節では，括弧付きコーパスからPCFGを抽出する
具体的な手法について説明する．
3節では，抽出した文法を改良する方法について説明する．
文法の改良とは，具体的には文法サイズを縮小することと，
文法が生成する解析木の数を抑制することを指す．
4節では，実際に括弧付きコーパスからPCFGを抽出し，
それを用いて統語解析を行う実験について述べる．
最後に5節では，この論文のまとめと今後の課題について述べる．
\section{括弧付きコーパスからの文法抽出}
\label{sec:文法抽出}
\subsection{EDRコーパスの概要}
\label{sec:EDRコーパスの概要}

本論文では，言語データとしてEDR日本語コーパスを使用する．
EDRコーパスに収録されている例文数は207,802である．
それぞれの文には補助情報として形態素情報，構文情報，意味情報が
付加されている．
本論文では形態素情報(特に品詞情報)と括弧付けによる構文構造を
利用する．
EDRコーパスの例文，及びそれに付加された
形態素情報・括弧付けによる構文構造の例を
図\ref{fig:構文構造の例1} に示す．

\begin{center}
  \atari(120,68)

  \figcap{EDRコーパスの構文構造}{fig:構文構造の例1}
\end{center}

EDRコーパスで使われている品詞は以下に挙げる15種類であり，
比較的粗い品詞体系になっている．
\begin{quote}
  名詞，動詞，形容詞，形容動詞，連体詞，
  副詞，接続詞，数字，感動詞，助詞，\\
  助動詞，語尾，接頭語，接尾語，記号
\end{quote}
ここで注意しなければならないのは，
``動詞''という品詞は動詞語幹に対して割り当てられ，
語尾には``語尾''という品詞が割り当てられている点である．
同様に，``形容詞''，``形容動詞''，``助動詞''という品詞は，
それぞれ形容詞語幹，形容動詞語幹，助動詞語幹に割り当てられている．
\subsection{ノードへの非終端記号の付与}
\label{sec:ノードへの非終端記号の付与}

図\ref{fig:構文構造の例1} は図\ref{fig:基本規則} のような
書き換え規則の集合とみなすことができる．
図\ref{fig:構文構造の例1} のような構文構造の各ノードに対して
適切なラベル(非終端記号)を割り当てることができれば，
図\ref{fig:基本規則} の規則はCFG規則となる．
このように，括弧付けによる構文構造の内部ノードに
適切なラベルを与えることは括弧付きコーパスからCFGを
抽出することと等価である．
そこで，\ref{sec:ラベルの決定方法} 節では構文構造の内部ノードに
与えるラベルを決定する方法について考える．

\begin{center}
  \small
  \smallskip
  \begin{tabular}[t]{ccccc}
    \inode{0} & $\rightarrow$ & \inode{1} & 記号 & \hspace{3zw} \\
    \inode{1} & $\rightarrow$ & \inode{2} & 助動詞 & \\
    \inode{2} & $\rightarrow$ & \inode{3} & \inode{4} & \\
    \inode{3} & $\rightarrow$ & 名詞 & 助詞 & \\
    \inode{4} & $\rightarrow$ & \inode{5} & \inode{14} & \\
    \inode{5} & $\rightarrow$ & \inode{6} & 助詞 & \\
    \inode{6} & $\rightarrow$ & \inode{7} & 名詞 & \\
    \inode{7} & $\rightarrow$ & \inode{8} & \inode{13} & \\
  \end{tabular}
  \hspace{5mm}
  \begin{tabular}[t]{ccccc}
    \inode{8}  & $\rightarrow$ & \inode{9}  & 助詞 & \\
    \inode{9}  & $\rightarrow$ & \inode{10} & 名詞 & \\
    \inode{10} & $\rightarrow$ & \inode{11} & 助詞 & \\
    \inode{11} & $\rightarrow$ & \inode{12} & 名詞 & \\
    \inode{12} & $\rightarrow$ & 接頭語 & 名詞 & \\
    \inode{13} & $\rightarrow$ & 動詞   & 語尾 & \\
    \inode{14} & $\rightarrow$ & 動詞   & 語尾 & 助動詞 \\
  \end{tabular}
  \bigskip

  \figcap{構文構造から得られる書き換え規則}{fig:基本規則}
\end{center}
\subsection{ラベルの決定方法}
\label{sec:ラベルの決定方法}

日本語の特徴として，前の要素が後ろの要素を修飾する，
すなわち句の主辞はその句における一番最後の要素である
ということが知られている\cite{mihara94a}．
例えば，図\ref{fig:基本規則} の中の
\begin{quote}
  \inode{12} ~~ $\rightarrow$ ~~ 接頭語 ~~ 名詞
\end{quote}
という規則について考えよう．[接頭語 名詞]という句の主辞は
句の一番最後にある``名詞''であると考えられる．
そこで，この主辞``名詞''に``句''をつけたラベル``名詞句''を
左辺のノード\inode{12}に与えることにする．
同様に，
\begin{quote}
  X ~~ $\rightarrow$ ~~ 形容詞句 ~~ 名詞句
\end{quote}
という規則が存在すると仮定し，
ラベルの決定されていないノードXに非終端記号を与える場合を考える．
この時，[形容詞句 名詞句]という句全体の主辞もまた
句の最後にある``名詞句''であると考えられる．
先ほどと異なるのは主辞となる記号が非終端記号であるという点である．
このような場合には，右再帰を用いて左辺ノードXにも主辞と同じ
``名詞句''というラベルを与える．

しかしながら，このようなラベルの与え方が常に適切であるわけではない．
\begin{itemize}
\item 主辞にならない品詞

  \quad 例えば，
  \begin{quote}
    X ~~ $\rightarrow$ ~~ 接続詞 ~~ 記号
  \end{quote}
  という規則について考える
  \footnote{
    この規則の右辺は「しかし，」などに対応している．
    }．[接続詞 記号]という句の1番最後にある
  品詞は``記号''であるが，
  この句の主辞は``記号''ではなく``接続詞''である．
  したがって，左辺のノードXに与えるラベルも``記号句''ではなく
  ``接続詞句''とすべきである．
  このように，``記号''は主辞にはならない品詞であるとみなし，
  句の一番最後にある要素が``記号''である場合には，
  その左隣にある要素を主辞とみなす．

\item ``語尾''と``助動詞''の取り扱い

  \quad 図\ref{fig:基本規則} の中の
  \begin{quote}
    \inode{13} ~~ $\rightarrow$ ~~ 動詞 ~~ 語尾
  \end{quote}
  という規則について考える．
  今までのやり方では，[動詞 語尾]という句の1番最後にある
  品詞は``語尾''であるので，左辺のノード\inode{13}に与える
  ラベルは``語尾句''となる．
  ところが，\ref{sec:EDRコーパスの概要} 節で述べたように，
  EDRコーパスにおいては，``語尾''という品詞は
  動詞の語尾にだけではなく形容詞・形容動詞・助動詞の
  語尾にも割り当てられている．
  したがって，このようなラベルの付け方では，
  \begin{quote}
    X ~~ $\rightarrow$ ~~ 形容詞 ~~ 語尾   \\
    X ~~ $\rightarrow$ ~~ 形容動詞 ~~ 語尾 \\
    X ~~ $\rightarrow$ ~~ 助動詞 ~~ 語尾
  \end{quote}
  といった規則の左辺にも``語尾句''というラベルを与えることになる．
  この場合，``語尾句''というラベルを割り当てられたノードが
  ``動詞''，``形容詞''，``形容動詞''，``助動詞''の
  どれを含んでいるのかを識別することができない．
  同様に，規則の右辺の一番最後にある要素が``助動詞''のときも，
  左辺に``助動詞句''というラベルを与えるのは好ましいことではない．
  このような理由から，句の一番最後にある要素が品詞``語尾''または
  ``助動詞''である場合には，その左隣にある要素から左辺に与える
  非終端記号を導出する．

\item 主辞が``助詞''の場合
  
  \quad 左辺に``助詞句''というラベルを与えることも考えられるが，
  わかりやすさのため``後置詞句''というラベルを与える．

\item 主辞が``接尾語''の場合

  \quad EDRコーパスにおいては，品詞が``接尾語''となる形態素は
  「月」，「日」，「メートル」など単位を表しているものが多く，
  他にも「区」，「氏」など全体として名詞句を形成するものが
  ほとんどである．
  そこで，主辞が``接尾語''のときには左辺ノードに``名詞句''
  というラベルを与える．
\end{itemize}

以上のようないくつかの例外処理が必要ではあるが，
基本的には句の一番最後にある要素を主辞とみなして，
それから左辺ノードに与えるラベルを決定することにする．

本節で提案した括弧付きコーパスから文法を抽出する
アルゴリズムを以下にまとめる．

\begin{flushleft}
  \vspace*{2mm}{\bf 【文法抽出アルゴリズム】}\vspace*{-3mm}
\end{flushleft}

\begin{enumerate}
\item
  構文構造の中で，まだラベルが割り当てられていなくて，
  かつその子ノードには全てラベルが割り当てられているノードを
  見つける．
  そのようなノードがなければ(3)へ．

\item
  (1)で見つけたノードが構文構造のルートである場合には，
  そのノードのラベルを開始記号Sとする．
  それ以外は【ラベル決定アルゴリズム】(後述)を用いて
  ノードに与えるラベルを決定する．
  (1)へ戻る．

\item
  構文構造の全ての内部ノードにはラベルが与えられているはずなので，それを
  \begin{center}
    ノード \quad → \quad 子ノードの列
  \end{center}
  という形に分解しCFG規則とする．
\end{enumerate}

\begin{flushleft}
  \vspace*{2mm}{\bf 【ラベル決定アルゴリズム】}\vspace*{-3mm}
\end{flushleft}

``記号'',``語尾'',``助動詞''以外の要素で子ノードの列の
最も右側にあるものを選び，それをXとする．
\begin{itemize}
\item
  Xが``助詞''の場合，左辺ノードに``後置詞句''というラベルを与える．

\item
  Xが``接尾語''の場合，左辺ノードに``名詞句''というラベルを与える．

\item
  Xが``助詞''，``接尾語''以外の品詞の場合，
  左辺ノードに``X句''というラベルを与える．
  例えば主辞が``名詞''の場合，``名詞句''というラベルを与える．

\item
  Xが非終端記号の場合，左辺ノードにも同じXという
  ラベルを与える．
  例えば主辞が``名詞句''の場合，左辺ノードにも
  同じ``名詞句''というラベルを与える．
\end{itemize}

\bigskip
上記の方法によって図\ref{fig:構文構造の例1} の内部ノードにラベルを
与えて抽出された文法規則を図\ref{fig:抽出された文法の例} に示す．
この操作をコーパスの全ての構文構造に対して行うことにより
CFGを抽出することができる．

\begin{center}
  \small
  \smallskip
  \begin{tabular}{lcll}
    S        & $\rightarrow$ & 助動詞句 & 記号 \\
    助動詞句 & $\rightarrow$ & 動詞句 & 助動詞 \\
    動詞句   & $\rightarrow$ & 後置詞句 & 動詞句 \\
    動詞句   & $\rightarrow$ & 動詞 & 語尾 \\
    動詞句   & $\rightarrow$ & 動詞 & 語尾 ~~~~ 助動詞 \\
    後置詞句 & $\rightarrow$ & 名詞 & 助詞 \\
    後置詞句 & $\rightarrow$ & 名詞句 & 助詞 \\
    名詞句   & $\rightarrow$ & 後置詞句 & 名詞 \\
    名詞句   & $\rightarrow$ & 接頭語 & 名詞 \\
    名詞句   & $\rightarrow$ & 動詞句 & 名詞 \\
    名詞句   & $\rightarrow$ & 名詞句 & 名詞 \\
  \end{tabular}

  \bigskip
  \figcap{抽出された文法規則}{fig:抽出された文法の例}
\end{center}

次に，本手法の文法抽出に要する計算量について考察する．
【文法抽出アルゴリズム】は，
「句の主辞はその句における一番最後の要素である」という
日本語の言語学的特徴を利用して括弧付けによる構文構造の
内部ノードに非終端記号を与えているため，
文法抽出に必要な計算量はコーパスの構文構造の内部ノード数に比例する．
また，長さ $n$ の文があったとき，
それに対する最も内部ノード数の多い構文構造は完全な二分木であり，
そのときの内部ノード数は $n-1$ である．
したがって，文法抽出に必要な計算量は入力文の長さ $n$ にも比例する．
このことは大規模なコーパスからの文法抽出を可能にしている．
これに対し，本研究と同じく括弧付きコーパスを用いてCFGを獲得する
Pereiraらの方法~\cite{pereira92a,schabes93b} では，
Inside-Outsideアルゴリズムによる規則の推定に
必要な計算量は$O(n)$ であり\footnote{
  厳密には，コーパスに付加された構文木が完全な二分木のときのみ
  $O(n)$ となり，それ以外の場合の計算量は$O(n)$ よりも多い．}
，しかもこの作業を反復しなければならない．
また，同じく括弧付きコーパスを利用した
横田らの方法~\cite{yokota96a} では，
内部ノードに与える非終端記号をランダムに変化させることを
繰り返すSimulated Annealing法を用いてCFG規則を獲得しているため，
内部ノードに決定的に非終端記号を与える本手法よりも
多くの計算量を必要とするのは明らかである．
\subsection{規則の確率の推定}
\label{sec:規則の確率の推定}

前節で提案した方法により括弧付きコーパスから抽出した
CFGに対して，各規則の確率を次のように推定した\cite{wetherell80a}．

\newpage
\begin{flushleft}
  \vspace*{2mm}{\bf 【規則の確率の推定】}\vspace*{-3mm}
\end{flushleft}

\begin{enumerate}
\item
  コーパスからCFG規則を抽出する際に，同じ規則を抽出した回数，
  すなわちその規則のコーパスにおける出現頻度を数える．
  規則 $r_i$ の出現頻度を $C(r_i)$ とする．

\item
  規則 $r_i \;:\; A \rightarrow \zeta_i$ の確率 $P(r_i)$ を
  次式により求める．
  \begin{equation}
    \label{eq:規則の確率}
    \hspace*{30mm}
    P(r_i) \quad = \quad 
      \frac{C(r_i)}
           {\displaystyle
            \sum_{\forall r_j \;:\; A \rightarrow \zeta_j} C(r_j)}
  \end{equation}
  すなわち $P(r_i)$ は，$r_i$ の出現頻度を，
  $A$ を左辺とする全ての規則の出現頻度の和で割った値とする．
\end{enumerate}

以上のように規則の確率を推定することにより，
括弧付きコーパスからPCFGを抽出することができる．
\section{文法の改良}
\label{sec:文法の改良}

サイズの小さなコーパスを用いて，
前節で説明した方法によりPCFGを抽出する予備実験を行ったところ，
以下のような問題点が明らかになった．

\begin{itemize}


\item 文法のサイズが大きい

  \quad EDRコーパスからランダムに選び出した3,000例文から
  PCFGを抽出したところ，文法規則の数は1,009となり，
  コーパスサイズに比べて非常に多くの文法規則が抽出されることがわかった．
  統語解析に要するコストを考えると，
  文法サイズが不必要に大きいことは望ましいことではない．

\item 生成される解析木の数が多い

  \quad 抽出したPCFGを用いて
  EDRコーパスからランダムに選び出した100例文\footnote{
    PCFGを抽出した3,000例文とは別の例文である．
    }
  を統語解析したところ，
  解析結果の候補として生成された解析木の数は
  平均 $1.5 \times 10^6$ となり，
  非常に多くの解析木を生成することがわかった．
  また，メモリ不足によって解析に失敗した文は69文あった．
  統語解析を意味解析や文脈解析などの前処理と考えるなら，
  統語解析結果の候補の数はできるだけ少ないことが望まれる．
\end{itemize}
本節ではこれらの問題への対応策について述べる．
\subsection{文法サイズの縮小}
\label{sec:文法サイズの縮小}

ここでは，コーパスから抽出した文法のサイズを縮小する方法を提案する．
文法サイズを縮小する方法としてまず考えられるのは，
出現頻度の低い規則を削除することである．
しかし，単純に出現頻度の低い規則を削除した場合，
その規則がコーパスの構文構造作成時の誤りによって生じた
不適切な規則であればよいが，
稀にしか現われない言語現象に対応した規則である場合には，
そのような規則を削除することにより文法の適用範囲(coverage)が狭くなる．
両者を出現頻度のみで区別することは難しく，出現頻度が低いからといって
その規則を削除することは必ずしも適切ではない．


予備実験で抽出した文法を調べたところ，
右辺長の長い規則が多く含まれていることがわかった．
予備実験で抽出した文法規則の右辺長の分布を
表\ref{tab:規則の右辺長の分布} に示す．
\begin{center}

  \tblcap{文法規則の右辺長の分布}{tab:規則の右辺長の分布}

  \small
  \begin{tabular}{|c||r|r|r|r|r|r|r|r|r|r|r|r|r|r|} \hline
    右辺長 &
    \makebox[4mm]{2}  & \makebox[4mm]{3}  & \makebox[4mm]{4} &
    \makebox[4mm]{5}  & \makebox[4mm]{6}  & \makebox[4mm]{7} &
    \makebox[4mm]{8}  & \makebox[4mm]{9}  & \makebox[4mm]{10} &
    \makebox[4mm]{11} & \makebox[4mm]{12} & \makebox[4mm]{13} &
    \makebox[4mm]{14} & \makebox[4mm]{16} \\ \hline
    規則数 &
    235 & 205 & 155 & 161 & 111 & 69 & 31 & 25 & 7 & 6 &
    1 & 1 & 1  & 1 \\ \hline
  \end{tabular}
  \bigskip
\end{center}
右辺長の長い規則が多く含まれていることがわかる．
そのような規則の一例を次に挙げる．
\begin{center}
  \begin{tabular}{ccl}
    動詞句 & $\rightarrow$ &
      動詞 ~ 語尾 ~ 名詞 ~ 助詞 ~ 形容動詞 ~ 語尾 ~ 動詞 ~ 語尾 \\
  \end{tabular}
\end{center}
これは，コーパスのある例文において，
\begin{center}
  [ ~~ 動詞 ~ 語尾 ~ 名詞 ~ 助詞 ~ 形容動詞 ~ 語尾 ~ 動詞 ~ 語尾 ~~ ]
\end{center}
といった括弧付けがなされているためである．
本来，その例文の構文構造を反映させるためには
もう少し細かい括弧付けが必要である．
しかし，EDRコーパスの中には多くの要素を1つの括弧で括ってしまう
例文も存在する．
このような右辺の長い規則の存在が文法サイズを大きくしている
原因の1つと考えられる．

右辺の長い規則の場合，その規則を除去しても文法中の
他の規則によって右辺の記号列を生成できる場合がある．
例えば，文法中に次のような規則があったとする．
\begin{center}
  \begin{tabular}{llcl}
    $r_b$ :    & 動詞句   & $\rightarrow$ &
      動詞句 ~ 後置詞句 ~ 動詞句 \\[-1mm]
    $r_{c1}$ : & 動詞句   & $\rightarrow$ &
      動詞 ~ 語尾 \\[-1mm]
    $r_{c2}$ : & 後置詞句 & $\rightarrow$ &
      名詞 ~ 助詞  \\[-1mm]
    $r_{c3}$ : & 動詞句   & $\rightarrow$ &
      形容動詞 ~ 語尾 ~ 動詞 ~ 語尾 \\
  \end{tabular}
\end{center}
これら4つの規則を用いれば，非終端記号``動詞句''から
``動詞~ 語尾~ 名詞~ 助詞~ 形容動詞 語尾~ 動詞~ 語尾''
という記号列を生成することが可能である．
このことを図式化したものを図\ref{fig:冗長規則の例1} に示す．
このように，ある規則を文法から除去しても，
他の規則によって右辺の記号列を生成できるような場合は
文法の生成能力は変わらない．

\begin{center}
  \bigskip
  \atari(115,36)
  \figcap{複数の規則を用いた記号列の展開}{fig:冗長規則の例1}
\end{center}

そこで，「冗長な規則」を次のように定義する．
\begin{center}
  \begin{minipage}{0.73\textwidth}
    ある規則 $r_i : A_i \rightarrow \zeta_i$ があるとき，
    文法内の $r_i$ 以外の規則を用いて
    非終端記号 $A_i$ を記号列 $\zeta_i$ に展開できるならば，
    すなわち $A_i \stackrel{*}{\rightarrow} \zeta_i$ である
    ならば，$r_i$ は冗長な規則である．
  \end{minipage}
\end{center}

\noindent
$\stackrel{*}{\rightarrow}$ は規則を1回以上適用することを示す．
冗長な規則を削除する前の文法によって受理される文は，
冗長な規則を削除した後の文法でも必ず受理される．
したがって，冗長な規則を自動的に検出しそれを削除すれば，
文法の適用範囲を狭めることなく文法サイズを縮小することができる．

ここで問題となるのは，冗長な規則のコーパスにおける出現頻度を
どのように取り扱うかということである．
本論文では，式(\ref{eq:規則の確率})に示した通り，
規則の出現頻度を規則の確率の推定に用いている．
そのため，冗長な規則を文法から削除する際に，
その出現頻度をも破棄してしまうのは望ましいことではない．
冗長な規則を削除するのは，その規則の右辺の記号列が
他の規則によって生成できることが保証されているからである．
したがって，削除された冗長な規則の出現頻度は，
その規則の右辺の記号列を生成するのに必要な
規則の出現頻度に加えるべきである．
例えば図\ref{fig:冗長規則の例1} において，
$r_a$ の右辺の記号列は$r_b$, $r_{c1}$, $r_{c2}$, $r_{c3}$ を
それぞれ1回ずつ適用することによって生成されるので，
$r_a$ を文法から除去する場合には，
$r_b$, $r_{c1}$, $r_{c2}$, $r_{c3}$ の出現頻度に
$r_a$ の出現頻度をそれぞれ加えるべきである．

さらに，冗長な規則の右辺を生成する規則の組\{$r_b$, $r_{ci}$\}
(図\ref{fig:冗長規則の例1} においては
\{$r_b$, $r_{c1}$, $r_{c2}$, $r_{c3}$\})が
複数ある場合には，冗長な規則$r_a$ の出現頻度を，
各組の$r_b$ に該当する規則の出現頻度で比例配分してから
各規則に足し合わせる．
また，ある規則$r_a$ が冗長であるかどうかを調べる際には
右辺長の長い規則から順番に行い，
\{$r_b, r_{ci}$\}が冗長であるかどうかについては考慮しない．
そして，$r_a$ が冗長であるとわかった際には，
\{$r_b, r_{ci}$\}の規則の出現回数を更新してから
次の規則が冗長であるかどうかを調べる．
したがって，例えば図\ref{fig:冗長規則の例1} の$r_{c3}$ が
冗長な規則である場合でも，$r_a$ の出現頻度は$r_{c3}$ の
出現頻度に一旦加えられた後，$r_{c3}$ の右辺の記号列を生成する
規則の出現頻度にも足し合わされる．

本節で提案した冗長な規則を検出しそれを削除するアルゴリズムを
以下にまとめる．

\begin{flushleft}
  \vspace*{2mm}{\bf 【冗長規則削除アルゴリズム】}
  \vspace*{-3mm}
\end{flushleft}

$R, ~ R_{new}, ~ C(r), ~ C_{new}(r)$ を次のように定義する．
\begin{center}
  \begin{tabular}{lcl}
    $R$          & ~$\cdots$~ &
      抽出した文法規則の集合 \\
    $C(r)$       & ~$\cdots$~ &
      $R$ 中の規則 $r$ の出現頻度 \\
    $R_{new}$    & ~$\cdots$~ &
      冗長な規則を削除して作られる新しい文法規則の集合 \\
    &&($R$ の中から冗長でない規則を取り出した集合) \\
    $C_{new}(r)$ & ~$\cdots$~ &
      $R_{new}$ の各規則の出現頻度 \\
  \end{tabular}
\end{center}

\begin{enumerate}
\item
  $R_{new}$ を空集合とする．

\item
  $R$ の中から右辺長の一番長い規則 $r_a$ を1つ抜き出す．

\item
  以下の条件を満たす規則の組
  \{$r_b^j$, $r_{c1}^j$, $\cdots$, $r_{cn}^j$\} を
  可能な限り見つける．
  \begin{quote}
    規則$r_b^j$ の右辺に含まれる非終端記号$B_i^j$ を，
    $B_i^j$ を左辺とする規則$r_{ci}^j$ の右辺の記号列$\beta_i^j$ に
    置き換えた記号列が$r_a$ の右辺の記号列と一致する．
  \end{quote}

  この条件を図示すると図\ref{fig:冗長な規則のチェック} のようになる．
  但し，図\ref{fig:冗長な規則のチェック} において，
  $A, \; B_i \in N ~，~~~ \alpha_i, \; \beta_i \in (N+T)*$である．
  ($N$ は非終端記号の集合，$T$ は終端記号の集合)

  \bigskip
  \begin{center}
    \atari(120,44)
    \figcap{冗長な規則のチェック}{fig:冗長な規則のチェック}
  \end{center}

  ※ このような規則の組が1つも見つからなかった場合($j=0$の場合)
  \begin{quote}
    $r_a$ は冗長な規則ではない．
    この規則を $R_{new}$ に加え，$C_{new}(r) = C(r)$ とする．
  \end{quote}
  ※ このような規則の組が1つ以上見つかった場合($j>=1$の場合)
  \begin{quote}
    $r_a$ は冗長な規則である．
    このときは $r_a$ を $R_{new}$ には加えず，
    出現頻度 $C(r)$ の更新のみを
    図\ref{fig:出現頻度の更新} のように行う．
    すなわち，見つけた規則の組の $r_b^j$ に該当する
    規則の出現頻度で $C(r_a)$ を比例配分し，
    それを $C(r_b^j)$, $C(r_{ci}^j)$ に加える．

    \bigskip
    \begin{center} $
      \begin{array}{c@{\hspace*{5mm}}c@{\hspace*{5mm}}ccc@{\hspace*{10mm}}l}
        C(r_b^j)    & \leftarrow & C(r_b^j)    & + &
          C(r_a) \times \frac{\displaystyle C(r_b^j)}
                             {\displaystyle \sum_j ~ C(r_b^j)} &
          for ~ all ~~~~ j \\[5mm]
        C(r_{ci}^j) & \leftarrow & C(r_{ci}^j) & + &
          C(r_a) \times \frac{\displaystyle C(r_b^j)}
                             {\displaystyle \sum_j ~ C(r_b^j)} &
          for ~ all ~~~ i, \; j \\
      \end{array} $
      \figcap{出現頻度の更新}{fig:出現頻度の更新}
      \bigskip
    \end{center}
  \end{quote}

\item
  $R$ が空なら終了．それ以外は(2)へ戻る．
\end{enumerate}

以上のように冗長な規則を削除することにより，
文法の適用範囲を狭めることなく文法サイズを縮小することができる．
この方法により文法サイズをどの程度縮小することができるのかについては
第\ref{sec:評価実験} 節の実験で評価する．
\subsection{解析木数の抑制}
\label{sec:解析木数の抑制}

ここでは，抽出した文法が生成する解析木の数を抑制するための
3つの方法を提案する．
\subsubsection{同一品詞列の取り扱い}
\label{sec:同一品詞列}

統語解析を行う文の中に同じ品詞が複数並んだ句が存在する
場合には，生成される解析木数が増大すると予想される．
例えば，``名詞''が3つ並んで構成される句の構造としては，
名詞間の修飾関係に応じて図\ref{fig:複合名詞の構造3} に
示す3つの構造が考えられる．
\begin{center}
  \atari(110,24)
  \figcap{``名詞''が3つ並んだ句の構造}{fig:複合名詞の構造3}
\end{center}

ところが，これらの構造の中から正しいものを選択するためには
何らかの意味的な情報が必要である\cite{kobayashi96a}．
したがって，意味的な情報を用いない統語解析の段階では，
これらの構造全てを解析結果の候補として生成する．
一般に，生成される解析木の数は組合せ的に増大するため，
同一品詞列に対して不必要な構造を無意味に生成することが
解析木数を増大させる原因の1つとなっている．
そこで統語解析の段階では，
図\ref{fig:複合名詞の構造3} のような構造を全て生成する代わりに，
図\ref{fig:右下がりの構造} のような右下がりの構造のみを
出力することにし，
この部分の係り受け解析については統語解析の後で
行われる意味解析に任せることにした．
また，他の非終端記号と区別するために，
図\ref{fig:右下がりの構造} の構造の内部ノードには
``X列''(例えばXが``名詞''の場合は``名詞列'')という
ラベルを与えることにした．

\begin{center}
  \atari(40,23)
  \figcap{右下がりの構造}{fig:右下がりの構造}
\end{center}

\noindent
このように同一品詞列に対する構造を一意に決めれば
解析結果として得られる解析木の数を減少させることができる．

同一品詞列に対して図\ref{fig:右下がりの構造} のような
右下がりの構造のみを生成するために，
\ref{sec:ラベルの決定方法} 節に述べた【文法抽出アルゴリズム】に，
次の手続きを最初のステップとして追加する．

\newpage
\begin{flushleft}
  {\bf 【文法抽出アルゴリズム】}
  \vspace*{-3mm}
\end{flushleft}

\begin{itemize}
\item[0.]
  構文構造において一種類の品詞のみを支配するノードがあれば，
  そのノードの下の構造を図\ref{fig:右下がりの構造} のような
  右下がりの構造に修正する．

\item[1.] $\sim$ 3. \hspace{5mm} 変更なし．
\end{itemize}

\bigskip
\noindent
また，【ラベル決定アルゴリズム】に次の手続きを追加する．
\begin{flushleft}
  {\bf 【ラベル決定アルゴリズム】}
  \vspace*{-3mm}
\end{flushleft}

\begin{itemize}
\item
  子ノードが品詞``X''または非終端記号``X列''のみによって
  構成されている場合には，\\
  ``Ｘ列''というラベルを与える．
\end{itemize}

\subsubsection{品詞の細分化}
\label{sec:品詞の細分化}

\ref{sec:EDRコーパスの概要} 節で述べたようにEDRコーパスで
使われている品詞は15種類である．
したがって，コーパスから抽出した文法に含まれる
終端記号(品詞セット)の数も15であるが，
これは統語解析を行うのに十分であるとは言えない。
例えば，コーパスの中に
\begin{center}
  [ ~ 名詞 ~ 助詞 ~ 名詞 ~ ] \qquad (e.g. ~ 記者席 / と / 傍聴席 ~)
\end{center}
という括弧付けが存在し，名詞並列を表わすCFG規則が抽出されたとする．
ところが，この規則は``名詞 助詞 名詞''という
品詞列に常に適用され，「地上 / に / 茅 (を出す)」といった
名詞並列でない入力に対しても，それが名詞並列であるといった
解析結果を出力してしまう．
これは全ての助詞に対して``助詞''という品詞を与えているためであり，
並列助詞と他の助詞に異なる品詞を与えれば，
このような誤った解析を回避することができる．

そこで，EDRコーパスに用いられている品詞を細分化して
生成される解析木の数を抑制することを試みた．
ここでは``記号''と``助詞''の2つの品詞に着目する．
\begin{itemize}
\item 品詞``記号''の細分化

  \quad EDRコーパスにおいては，
  記号には全て``記号''という品詞が割り当てられている．
  しかし，読点は文の切れ目を，句点は文の終りを表す特別な記号であり，
  他の記号とは区別するべきである．
  そこで，形態素「、」と「，」には``読点''という品詞を
  与えることにした．
  また，EDRコーパス中の例文の文末に現れる形態素のほとんどは
  「。」,「．」,「？」,「！」のいずれかであり，
  しかもこれらは文末以外に現れることはほとんどなかった．
  そこで，形態素「。」,「．」,「？」,「！」には
  ``文末記号''という品詞を与えることにした．
  また，これらの以外の形態素が文末に現れる文，
  及びこれらの形態素が文末以外の場所に現れる文，
  合計102文を例外としてコーパスから除去した．

\item 品詞``助詞''の細分化

  \quad EDRコーパスにおいては，
  助詞には全て``助詞''という品詞が割り当てられているが，
  その助詞の持っている機能により``格助詞'', ``係助詞''などの
  品詞を割り当てるべきである．
  しかしながら，助詞の中には2つ以上の機能を持っているものもあり，
  助詞の機能をその表層だけから判断することは一般に困難である．
  そこで，EDRコーパスにおいて``助詞''という品詞を
  割り当てられた形態素「Ｍ」については，
  その形態素毎に独自の品詞``助詞Ｍ''を割り当てることにした．
  例えば，形態素「は」が``助詞''という品詞を
  割り当てられていたならば，その品詞を``助詞は''に変更する．
\end{itemize}

PCFGの抽出は，まずコーパスの品詞を上記のように細分化し，
その後で\ref{sec:ラベルの決定方法} 節で提案した
【文法抽出アルゴリズム】 に従って行う．
また，品詞の細分化に伴い\ref{sec:ラベルの決定方法} 節の
【ラベル決定アルゴリズム】 を以下のように変更する．
下線を引いた部分が変更箇所である．

\begin{flushleft}
  \vspace*{2mm}{\bf 【ラベル決定アルゴリズム】}\vspace*{-3mm}
\end{flushleft}

\underline{``記号''，``語尾''，``助動詞''，``読点''，``文末記号''}
以外の要素で子ノードの列の最も右側にあるものを選び，それをXとする．
\begin{itemize}
\item
  Xが\underline{``助詞Ｍ''}の場合，
  左辺ノードに``後置詞句''というラベルを与える．

\item[~] (以下同じ)
\end{itemize}

\subsubsection{法・様相を表わす助動詞に対する構造の統一}
\label{sec:助動詞に関する修正}

文末に現われる助動詞は文全体の法や様態を表していることが多い．
例えば，EDRコーパス中の2つの例文
\begin{quote}
  \smallskip
  \begin{tabular}{ll}
    (a) & １０月中旬には、袋から顔を出しそうだ。 \\
    (b) & そのうえソ連は対越援助を削減しそうだ。 \\
  \end{tabular}
  \smallskip
\end{quote}
には「そう」と「だ」という2つの助動詞が含まれている．
これらは文全体にそれぞれ伝聞，断定の意味合いを
持たせる働きをしている．
ところがEDRコーパスにおいては，このような助動詞は，
文全体に付加している構造(図\ref{fig:助動詞の2つの構造} の(a))と，
文末の最後の要素に付加している構造(図\ref{fig:助動詞の2つの構造} の(b))
の2通りの構造で表されている．
このような2種類の構文構造を含むコーパスから抽出された文法は，
文末に助動詞を含む文に対して少なくとも
図\ref{fig:助動詞の2つの構造} のような2つの構造を生成し，
このことが解析木の数を増加させる一因となっている．


そこで，助動詞が文全体に付加された
図\ref{fig:助動詞の2つの構造} の(a)のような構造を，
図\ref{fig:助動詞の2つの構造} の(b)のような構造に修正してから
文法を抽出することにした．
助動詞に対する構造を統一することにより，
生成される解析木数の減少が期待できる．
統一後の構造として図\ref{fig:助動詞の2つの構造} の(a)ではなく
(b)を選択したのは，(a)のような構造からは
解析木数を著しく増加させる文法規則が抽出されるからである．
例えば，図\ref{fig:助動詞の2つの構造} の(a)のノード
\inode{1},\inode{2},\inode{3},\inode{8},\inode{10},\inode{12}には，
\ref{sec:ラベルの決定方法} 節の【文法抽出アルゴリズム】に従って
``動詞句''という非終端記号が割り当てられ，
その結果次のような規則が抽出される．
\begin{quote}
  動詞句 ~ $\rightarrow$ ~ 動詞句 ~ 助動詞  \qquad
  (``\inode{1} $\rightarrow$ \inode{2} 助動詞'' という枝分かれに対応)
\end{quote}

\begin{center}
  \atari(95,100)
  \figcap{助動詞に対する2つの構造}{fig:助動詞の2つの構造}
\end{center}

\noindent
ところが，この規則により``助動詞''がノード
\inode{8},\inode{10},\inode{12}に付加される
構造も生成されることになり，生成される解析木の数を増加させる
要因の1つとなっている．
これに対して，図\ref{fig:助動詞の2つの構造} の(b)のような構造からは
上述のような文法規則は抽出されないため，
無駄な解析木を生成することはない．
\vspace{-1mm}
\section{評価実験}
\label{sec:評価実験}

本論文で提案した手法の評価実験を行った．
まず，EDRコーパスの207,802例文のうち，約10分の1に相当する
20,000例文をランダムに選んでテストデータとし，残りを訓練データとした．
そして，訓練データからPCFGを抽出し，抽出したPCFGを用いて
テストデータの例文を統語解析することにより，
抽出したPCFGの品質を評価した．
\subsection{文法抽出実験}
\label{sec:文法抽出実験}
文法抽出を以下の手順で行った．
\begin{enumerate}
\item
  訓練データの例文の品詞を細分化した．(\ref{sec:品詞の細分化} 節)

  また，文末の助動詞に対する構造を統一した．
  (\ref{sec:助動詞に関する修正} 節)

\item
  【文法抽出アルゴリズム】に従って訓練データから
  PCFGを抽出した．
  (\ref{sec:ラベルの決定方法} 節，\ref{sec:同一品詞列} 節)


\item
  【冗長規則削除アルゴリズム】に従って冗長な規則を削除した．
  (\ref{sec:文法サイズの縮小} 節)
\item
  式(\ref{eq:規則の確率})より各規則の確率を推定した．
  (\ref{sec:規則の確率の推定} 節)
\end{enumerate}
コーパスから抽出したPCFGの概要を表\ref{tab:抽出したPCFG} に示す．
\begin{center}
  \tblcap{抽出したPCFG}{tab:抽出したPCFG}

  \begin{tabular}{|c||r|r|r|} \hline
    \makebox[10mm]{~} &
    \makebox[18mm]{非終端記号数} &
    \makebox[18mm]{終端記号数}   &
    \makebox[18mm]{規則数}       \\ \hline
    $G_0$ & 41~~ & 149~~ & 15206~~ \\ \hline
    $G_1$ & 41~~ & 149~~ &  2219~~ \\ \hline
  \end{tabular}
  \bigskip
\end{center}
$G_1$ は上述の手続きによって訓練データから抽出されたPCFG，
$G_0$ は冗長規則を削除する前のPCFGである．
冗長規則を削除したことにより文法サイズを約85\%縮小することができた．
\subsection{統語解析実験}
\label{sec:統語解析実験}

得られたPCFGを用いてテストデータの例文の統語解析を行った．
統語解析は一般化LR法~\cite{tomita86a} により行った．
LRパーザをSun Sparc Station 10/51(主記憶64Mbyte)上に実装した．
結果を表\ref{tab:統語解析結果(枝刈りなし)} に示す．
\begin{center}
  \tblcap{統語解析結果}{tab:統語解析結果(枝刈りなし)}
  \begin{tabular}{|r|r|r||r|} \hline
    \makebox[17mm][c]{受理} &
    \makebox[17mm][c]{不受理} &
    \makebox[17mm][c]{メモリ不足} &
    \makebox[17mm][c]{合計} \\ \hline
    12,658 文 & 23 文 & 7,319 文 & 20,000 文 \\ \hline
  \end{tabular}
  \bigskip
\end{center}
「受理」はパーザが解析に成功して1個以上の解析木を出力したことを，
「不受理」は解析に失敗したことを，
「メモリ不足」はメモリ不足のためにパーザが解析を中断したことを示す．
全体の約36\%に当たる7,319文がメモリ不足のために解析できなかった．
そこで，これらの文については，生成確率の低い部分木を解析途中で
破棄する枝刈りを行いながら再度統語解析を行った．
その結果を表\ref{tab:統語解析結果(枝刈りあり)} に示す．
\begin{center}
  \tblcap{枝刈りを行う統語解析結果}
         {tab:統語解析結果(枝刈りあり)}
  \begin{tabular}{|r|r|r||r|} \hline
    \makebox[17mm][c]{受理} &
    \makebox[17mm][c]{不受理} &
    \makebox[17mm][c]{メモリ不足} &
    \makebox[17mm][c]{合計} \\ \hline
    5,822 文 & 562 文 & 935 文 & 7,319 文 \\ \hline
  \end{tabular}
  \bigskip
\end{center}
これにより，$12,658 + 5,822 = 18,480$ 文を受理することができた．
受理した文の平均単語数は24.45単語であった．
また，生成した解析木数の1文当たりの平均は
$3.24 \times 10^9$ であった．
非常に多くの解析木が生成されているが，
PCFGにより解析木の生成確率を計算し，
その上位何位かを出力することによって
解析結果の候補数を絞り込むことが可能である．

まず，文法の適用範囲の広さを示す尺度として，受理率を次のように定義する．
\[
  受理率 ~=~ 
  \frac{\displaystyle 受理した文の数}
       {\displaystyle 統語解析した文の数}
\]
受理率は$18480/20000 ~\simeq~ 0.924$ となり，
適用範囲の広い文法が得られたことがわかる．
また，受理しなかった1520文のうち935文(約61.5\%)が
メモリ不足によるものである．
したがって，パーザの使用メモリを増やすことができれば
受理率はさらに向上することが予想される．

次に，パーザが出力した解析木の評価を行った．
出力された解析木がどれだけ正しいかを評価するための
尺度として，括弧付けの再現率，括弧付けの適合率，文の正解率を
それぞれ以下のように定義した．
\smallskip
\[
  括弧付けの再現率
  ~=~ \frac{\displaystyle 正しい括弧付けの数}
           {\displaystyle コーパスの構文構造に含まれる括弧付けの数}
\]
\smallskip
\[
  括弧付けの適合率
  ~=~ \frac{\displaystyle 矛盾しない括弧付けの数}
           {\displaystyle 解析木に含まれる全ての括弧付けの数}
\]
\smallskip
\[
  文の正解率
  ~=~ \frac{\displaystyle
            出力した解析木の中に正しい解析木が含まれる文の数}
           {\displaystyle 受理した文の数}
\]
\smallskip
ここで「正しい括弧付け」とは，コーパスに付加された構文構造の括弧付けと
完全に一致している解析木中の括弧付けを表し，
「矛盾しない括弧付け」とは，コーパスに付加された構文構造の全ての
括弧付けと交差していない括弧付けを表す~\cite{pereira92a}．
また「正しい解析木」とは，
解析木中の全ての括弧付けが矛盾していない解析木を表す．
解析木の評価方法としては，
コーパスの各例文に付加された構文構造を正解とみなし，
これと同じ構造を持つ解析木を正しい解析結果とする方法も考えられる．
しかしながら，\ref{sec:文法サイズの縮小} 節で述べたように，
EDRコーパスの括弧付けの中には
多くの要素を1つの括弧で括ってしまうものも含まれている．
これに対し，冗長な規則すなわち右辺長の比較的長い規則を削除したPCFGは，
EDRコーパスに付加された括弧付けよりも細かく括弧付けする傾向を持っている．
したがって，コーパスの構文構造と単純に比較して
正しい解析結果か否かを判断するのは適切であるとは言えない．
「括弧付けの適合率」及び「文の正解率」を計算する際に，
コーパスに付加された構文構造と完全に一致していなくても，
「矛盾しない括弧付け」及び「矛盾する括弧付けを含まない解析木」を
正解としたのはこのためである．

まず，生成確率が1位の解析木について，
括弧付けの再現率，括弧付けの適合率，文の正解率の値を計算した．
結果を表\ref{tab:解析結果の評価(1位のみ)} に示す．
\begin{center}
  \tblcap{解析結果の評価(1位のみ)}{tab:解析結果の評価(1位のみ)}

  \begin{tabular}{|r|r|r|} \hline
    \makebox[27mm][c]{括弧付けの再現率} &
    \makebox[27mm][c]{括弧付けの適合率} &
    \makebox[27mm][c]{文の正解率}     \\ \hline
    54.30\%~~ & 65.74\%~~ &  8.47\%~~ \\ \hline
  \end{tabular}
  \smallskip
\end{center}
Schabesらは，英語の括弧付きコーパス(Wall Street Journal Corpus)から
Inside-Outsideアルゴリズムにより獲得した文法を用いた統語解析実験を行い，
20〜30単語のテスト文に対して括弧付けの適合率が71.5\%，
文の正解率が6.8\%であったと報告している\footnote{
  彼らは括弧付けの再現率は示していない．
}\cite{schabes93b}．
我々の実験の結果は，括弧付けの適合率ではSchabesらの結果に劣るが
文の正解率では優っている．
しかしながら，本研究とは使用しているコーパスや対象言語が
異なるため，単純な比較はできない．

表\ref{tab:解析結果の評価(1位のみ)} では，
生成確率が1位の解析木についてのみ評価を行ったが，
生成確率は統語的にみた解析木の尤もらしさを示しており，
係り受け関係などの意味的な関係を考えた場合，生成確率の
最も高い解析木が必ずしも正しい解析結果を表わしているわけではない．
正しい解析結果を選択するのには何らかの意味解析が必要であるが，
統語解析の結果出力される全ての解析結果の候補に対して
意味解析を行うのは現実的ではない．
統語解析を，意味解析を行う解析結果の候補の数を絞り込み，
意味解析にかかる負担を軽減するための前処理と考えるなら，
正解となる解析木の生成確率が1位とならなくても，
生成確率の上位何位かに含まれていれば十分であろう．
そこで，生成確率の上位$k$ 位の解析木を出力し，
その中から矛盾する括弧付けの最も少ない解析木を選んで評価した．
結果を表\ref{tab:統語解析結果の評価(上位k位)} に示す．
\begin{center}
  \tblcap{統語解析結果の評価(上位$k$ 位)}
         {tab:統語解析結果の評価(上位k位)}

  \begin{tabular}{|c||r|r|r|} \hline
    $k$ &
    \makebox[27mm][c]{括弧付けの再現率} &
    \makebox[27mm][c]{括弧付けの適合率} &
    \makebox[27mm][c]{文の正解率}     \\ \hline\hline
     1 & 54.30\%~~ & 65.74\%~~ &  8.47\%~~ \\ \hline
     5 & 57.60\%~~ & 69.04\%~~ & 16.23\%~~ \\ \hline
    10 & 59.53\%~~ & 71.10\%~~ & 21.11\%~~ \\ \hline
    20 & 61.46\%~~ & 73.18\%~~ & 26.51\%~~ \\ \hline
    30 & 62.48\%~~ & 74.13\%~~ & 29.06\%~~ \\ \hline
  \end{tabular}
  \smallskip
\end{center}
上位30位までの解析木を出力した場合，その中に正解となる解析木が
含まれている文の割合は8.47\%から29.06\%に向上することがわかった．

最後に，統語解析を行う文法のサイズを変化させ，
受理率と正解率および生成される解析木数との相関を調べる実験を行った．
まず，$G_1$ の中からある一定の閾値$P$ 以下の確率を持つ
文法を除去し，サイズの小さい文法$G_2$〜$G_5$ を抽出した
\footnote{
  実際には，閾値以下の規則を削除した後，
  残された規則の出現回数をもとに各規則の確率の推定をやり直した．
}．
次に，テストデータの中から枝刈りなしで受理した12,658文
(表\ref{tab:統語解析結果(枝刈りなし)} 参照)を
$G_2$〜$G_5$ を用いて統語解析し，結果を比較した．
テスト文をこのように限定したのは，
パーザがメモリ不足によって統語解析を中断した場合には
文法が生成する解析木の数を測定することができないからである．
解析した文の平均単語数は19.01単語であった．

実験結果を表\ref{tab:文法サイズと解析結果の変化} に示す．
メモリ不足によって解析に失敗した文はなかった．
括弧付けの再現率，括弧付けの適合率，文の正解率は，
生成確率の1位の解析木のみについて評価した．
表\ref{tab:文法サイズと解析結果の変化} により，
文法サイズが小さくなるにつれて受理率が低下していることがわかる．
また，受理率の低下に伴い平均解析木数も減少する傾向が見られる．
これに対し，受理率が変化しても
括弧付けの再現率，適合率，文の正解率はほとんど変化していない．
このことから，受理率を向上させるために文法サイズを大きくして，
その結果得られる解析木の数が増大しても，
生成確率の上位の解析木のみを出力すれば
正解率はほとんど変わらないということがいえる．

\begin{center}
  \tblcap{文法サイズと解析結果の変化}{tab:文法サイズと解析結果の変化}
  \begin{tabular}{|c||r|r|r|r|r|} \hline
    \makebox[27mm]{文法} &
    \makebox[18mm]{$G_1$} &
    \makebox[18mm]{$G_2$} &
    \makebox[18mm]{$G_3$} &
    \makebox[18mm]{$G_4$} &
    \makebox[18mm]{$G_5$} \\[-1mm]
    \multicolumn{1}{|c||}{(閾値$P$)}  &
    \multicolumn{1}{|c|}{( --- )}     &
    \multicolumn{1}{|c|}{($10^{-5}$)} &
    \multicolumn{1}{|c|}{($10^{-4}$)} &
    \multicolumn{1}{|c|}{($10^{-3}$)} &
    \multicolumn{1}{|c|}{($10^{-2}$)} \\ \hline\hline
    非終端記号数 &    41 &    37 &  34 &  23 &  15 \\ \hline
    終端記号数   &   111 &    80 &  57 &  33 &  23 \\ \hline
    規則数       & 2,219 & 1,289 & 871 & 390 & 115 \\ \hline\hline
    受理率 &
      100\%   & 99.39\% & 95.57\% & 76.74\% & 34.22\% \\ \hline
    平均解析木数 & $2.730 \times 10^7$ & 
      $1.810 \times 10^7$ & $1.071 \times 10^7$ &
      $9.841 \times 10^5$ & $4.485 \times 10^4$ \\ \hline
    括弧付けの再現率 &
      62.71\% & 62.73\% & 62.66\% & 62.91\% & 60.11\% \\ \hline
    括弧付けの適合率 &
      75.59\% & 75.62\% & 75.68\% & 76.58\% & 73.64\% \\ \hline
    文の正解率 &
      12.07\% & 12.00\% & 12.25\% & 13.38\% & 11.45\% \\ \hline
  \end{tabular}
  \smallskip
\end{center}
\section{結論}
\label{sec:結論}

本論文では，括弧付きコーパスから確率文脈自由文法(PCFG)を
自動的に抽出する方法を提案した．
PCFGの抽出は，
日本語の主辞が句の一番最後の要素であるという特徴に着目し，
括弧付けによる構文構造の内部ノードに適切な非終端記号を
与えることによって行った．
また，抽出した規則の確率はその規則のコーパスにおける
出現回数から推定した．
さらに，抽出したPCFGに対して2つの面から改良を加えた．
1つは文法サイズの縮小，もう1つは生成される解析木数の抑制である．
前者は冗長な規則を削除することにより行った．
後者は同一品詞列に対する構造を右下がりの二分木のみに限定したこと，
品詞を細分化したこと，
文末の助動詞に対する構造を統一したことにより行った．
最後に，提案した方法により抽出・改良されたPCFGを用いた
統語解析実験を行ったところ受理率が約92\%となった．
また，生成確率の上位30個の解析木を出力した場合，
文の正解率が約29\%，括弧付けの再現率が約62\%，
括弧付けの適合率が約74\%という結果が得られた．

最後に本論文の今後の課題について述べる．
コーパスから抽出したPCFGの問題点の1つは，
\ref{sec:解析木数の抑制} 節で生成される解析木の数を
抑制したにも関わらず，
依然として多くの解析木を生成することである．
実験では，PCFGが出力する解析木数の1文当たりの平均は
$3.24 \times 10^9$ であった．
生成確率の高い解析木のみを出力することにより
解析結果の候補数を絞り込むことができるものの，
文法が多くの解析木を生成するのは効率の面から見ても
望ましいことではない．
また，本論文では対象言語を日本語とし，
句の主辞を特定する際に日本語の特性を考慮に入れているが，
他の言語についても句の主辞を特定することができれば
本手法をそのまま適用することができる．
今後は，日本語以外の言語の文法を獲得することについても
検討していきたい．




\bibliographystyle{jnlpbbl}
\bibliography{jpaper}

\begin{biography}
\biotitle{略歴}
\bioauthor{白井 清昭}{
  1970年生．
  1993年東京工業大学工学部情報工学科卒業．
  1995年同大学院理工学研究科修士課程修了．
  1995年同大学院情報理工学研究科博士課程入学，現在在学中．
  コーパスからの自然言語処理用知識の自動獲得に関する研究に従事．
  情報処理学会会員．}

\bioauthor{徳永 健伸}{
  1961年生．
  1983年東京工業大学工学部情報工学科卒業．
  1985年同大学院理工学研究科修士課程修了．
  同年(株)三菱総合研究所入社．
  1986年東京工業大学大学院博士課程入学．
  現在, 同大学大学院情報理工学研究科計算工学専攻助教授．
  博士 (工学)．
  自然言語処理, 計算言語学に関する研究に従事．
  情報処理学会, 認知科学会, 人工知能学会, 計量国語学会, 
  Association for Computational Linguistics, 各会員．}

\bioauthor{田中 穂積}{
  1941年生．
  1964年東京工業大学工学部情報工学科卒業．
  1966年同大学院理工学研究科修士課程修了．
  同年電気試験所(現電子技術総合研究所)入所．
  1980年東京工業大学助教授．
  1983年東京工業大学教授．
  現在, 同大学大学院情報理工学研究科計算工学専攻教授．
  博士(工学)．
  人工知能，自然言語処理に関する研究に従事．
  情報処理学会, 電子情報通信学会，認知科学会, 人工知能学会,
  計量国語学会, Association for Computational Linguistics, 各会員．}

\bioreceived{受付}
\biorevised{再受付}
\bioaccepted{採録}

\end{biography}

\end{document}
