    \documentstyle[eclepsf,jnlpbbl,theorem,amsmath,amssymb,comment]{jnlp_j_b5_2e}


\theorembodyfont{\normalfont}

\theoremstyle{break}
\newtheorem{theorem}{}[] 

\theoremstyle{plain}
\newtheorem{lemma}{}[] 

\newtheorem{syoumei}{}
\renewcommand{\thesyoumei}{}
\newcommand{\proof}[1]{}

\theoremstyle{plain} 
\newtheorem{definition}{}

\newcommand{\myfigdir}{}

\newcommand{\myfiglabelskip}{}
\newcommand{\myfigskiptop}{}
\newcommand{\myfiglabelskippre}{}
\newcommand{\myfiglabelskippost}{}
\newcommand{\myhalfskip}{}
\newcommand{\mygapskip}{}

\newcommand{\mytheoremproofgap}{}
\newcommand{\mytheoremaftergap}{}

\newcommand{\mytheorembeforegap}{}

\newcommand{\mynoindent}{}
\newcommand{\mynoindentb}{}

\newcommand{\myitemindent}{}
\newcommand{\mysmallitemindent}{}

\newif\if提出
\提出true     



\setcounter{page}{37}
\setcounter{巻数}{13}
\setcounter{号数}{3}
\setcounter{年}{2006}
\setcounter{月}{7}
\受付{2005}{10}{31}
\採録{2006}{2}{4}


\title{選好依存文法とその圧縮共有データ構造「依存森」について}
\author{平川 秀樹\affiref{TOSHIBA}}

\headauthor{平川}
\headtitle{選好依存文法とその圧縮共有データ構造「依存森」について}
\affilabel{TOSHIBA}{（株）東芝　研究開発センター}
	{Toshiba R\&D Center}
\jabstract{
選好依存文法(PDG: Preference Dependency Grammar)は，自然言語の形態素，
構文，意味解析を統合的に行う枠組みであり，各レベルの種々の曖昧性を統合
的に効率良く保持し，各レベルの知識により優先度を設定し，全体解釈として
最適な解を計算する．本稿では，PDGの基本モデルである多レベル圧縮共有デー
タ結合モデルとPDGの概要について述べるとともに，選好依存文法で用いられ
るヘッド付き統語森，依存森といった言語解釈を統合保持するデータ構造とそ
の構築手法について説明する．また，文の句構造を圧縮共有する統語森と依存
構造を圧縮共有する依存森との対応関係において完全性と健全性が成立するこ
とを示す．
}
\jkeywords{文解析，句構造, 依存構造，圧縮共有データ構造}

\etitle{Preference Dependency Grammar and its Packed\\Shared Data Structure ``Dependency Forest''}
\eauthor{Hideki Hirakawa\affiref{TOSHIBA}} 
\eabstract{ Preference Dependency Grammar(PDG) is a framework for the
morphological, syntactic and semantic analysis for natural language
sentences. PDG gives packed shared data structures to hold the various
ambiguities in each level of sentence analysis with preference
scores and a method for calculating the most plausible interpretation
for a sentence. This paper describes the sentence analysis model
named the ``Multi-level Packed Shared Data Connection Model'' adopted
in PDG and shows the outline of the PDG framework. This paper
describes the packed shared data structures, such as the Headed
Parse Forest, the Dependency Forest adopted in PDG, and shows the
completeness and the soundness of the mapping between the Parse Forest
and the Dependency Forest.}
\jkeywords{文解析，句構造, 依存構造，圧縮共有データ構造}
\ekeywords{Sentence analysis, Phrase structure, Dependency structure, Packed shared data structure}

\begin{document}
\maketitle
\thispagestyle{empty}



\section{はじめに}

自然言語は，多様性・曖昧性，規則性と例外性，広範性・大規模性，語彙・
文法の経時変化などの性質を持っている．自然言語解析システムは，これらの
性質をアプリケーションが要求するレベルで旨く扱う必要がある．なかでも多
様性・曖昧性への対応，すなわち，形態素，構文，意味，文脈などの各種レベ
ルにおける組合せ的な数の曖昧性の中からいかにして正しい解釈を認識するか
がシステム構築上，最も重要な課題である．

\begin{figure}[b]
 \begin{center}
 \epsfile{file=\myfigdir/COM自然言語解析システムのモデル.eps,scale=0.7}
 \end{center}
\myfiglabelskip
\caption{自然言語解析システムのモデル}
\label{fig:NLAnalysisModel}
\end{figure}

一般に自然言語解析システム(以下システムと省略する)は，入力文に対して可
能な解釈の仮説を生成し（{\bf 仮説生成知識}の適用），ありえない仮説を棄
却したり({\bf 制約知識}の適用)，仮説に対する順位付けを行ったり（{\bf 
選好知識}の適用）することで，入力文に対する解析結果(文解釈となる構造) 
を求める．図\ref{fig:NLAnalysisModel}がこのモデルを示している．文の解
釈は，仮説記述体系により規定される仮説空間に存在し，それぞれが実世界に
おいて，正解解釈（◎:correct），可能解釈（○:plausible），不可能解釈
（×:implausible）に分類できる．仮説生成知識が可能な仮説集合を
生成する．制約知識は仮説空間内の仮説が可能か不可能かを弁別し，選好知識
は仮説空間内の仮説の順位付けを行う\footnote{制約知識は可能性ゼロの選
好知識ともいえる．但し，制約知識の適用は解釈の枝仮りであり計算機処理の
観点からは大きな差異がある．}．仮説生成・制約知識は，システムが受理可
能な文の範囲，すなわち，システムの対象文カバレッジを規定する．仮説生成・
制約・選好知識は，形態素，構文，意味といった各レベルにおいて存在し，シ
ステムの性能はこれらの総合として決定されると考えられる．例えば，各レベ
ルの選好知識がそれぞれ異なった解釈を支持するという競合が生じるため，精
度良く文解釈を行うにはこれらを総合的に判断する必要がある
\cite{Hirakawa89a}．このように，システム設計においては，「生成
\footnote{簡略のため「仮説生成知識」を単に「生成知識」と表現する．}・制
約・選好知識をどのように扱うか」（{\bf 知識適用の課題}），「多レベルの
知識をどのように融合するか」（{\bf 多レベル知識の課題}）という２つの課
題が存在する．

生成・制約知識は，正文と非文とを弁別(あるいは，正文のみを生成)する，い
わゆる，言語学の文法知識に相当する．従来，言語学からの知見を活用しなが
ら計算機処理を前提とした各種の文法フレームワークが研究されてきている．
文法フレームワークは，文の構造解釈を記述する解釈構造記述体系を基盤とし
て構築されるが，これらには，句構造，依存構造，意味グラフ，論理式など様々
ものが提案されている．一方，選好知識については意味プリファレンスの扱い
\cite{Wilks75}を始めとして古くから多くの研究がなされているが，音声認識
処理から自然言語処理への導入が始まった統計的手法が，単語系列から文脈自
由文法，依存文法などへと適用範囲(解釈記述空間)を拡大・発展させ，広くシス
テムに利用されるようになってきている．例えば，句構造をベースの枠組みと
して，文脈自由文法，LFG\cite{Kaplan89,Riezler02}，
HPSG\cite{Pollard94,Tsuruoka04}, CCG\cite{Steedman00,Clark03}など
\footnote{解析結果として依存構造を出力したりする場合もあるが，ここでは
解析のベースとなっている解釈記述空間で分類している．}，また依存構造を
ベースとした枠組みとして，確率依存文法\cite{Lee97},係り受け解析
\cite{Shudo80,Ozeki94,Hirakawa01,Kudo05_j},制約依存文法(以降CDGと記述
する) \cite{Maruyama90,Wang04}，Link
Grammar\cite{Sleator91,Lafferty92}など文法フレームワークと統計手法の融
合が広範に行われている．このように，文法フレームワークの研究は，生成・
制約知識を対象とした研究から統計ベースの選好知識の扱いへと進展し，統計
的手法は語系列，句構造，依存構造へと適用範囲を拡大し融合され，生成・制
約・選好知識全体の統合のベースが整ってきている．


多レベルの知識の融合という観点では，基本的に単一の解釈記述空間に基づく
アプローチと複数の解釈記述空間に基づくアプローチがある．単一の文脈自由
文法，依存文法などは前者の典型である．DCG\cite{Pereira80}や
BUP\cite{Matsumoto83}などは文脈自由文法をベースにしているが，拡張条件
が記述可能であり，例えば意味的な制約といった異レベルの知識を句構造とい
う１つの解釈記述空間をベースとしながら融合することができる．CDGでは依
存構造をベースにして構文的な制約を含む任意の制約条件を単項制約，２項制
約という枠組みで記述できるようにしている\cite{Maruyama90}．LFG は，
c-structure (句構造)とf-structure (機能構造) の２種類のレイヤを有し機
能スキーマにより機能構造に関する制約条件が記述可能である
\cite{Kaplan89}．また，統計ベースのアプローチにおいては，句構造情報だ
けではなく句のヘッドやその依存関係情報の利用が有効であることが判明し，句
構造情報と依存構造情報を統合判断するモデルが利用されている
\cite{Carroll92,Eisner96b,Collins99,Charniak00,Bikel04}．PDGは，複数
の解釈記述空間に基づくアプローチを取っており，後に述べるように複数の解
釈記述空間で対応付けられた圧縮共有データ構造をベースに多レベルの知識の
融合を行っている．

本稿では，PDGのモデル・概要について述べた後，PDGで採用している句構造と
依存構造という２種類の中心的共有データ構造であるヘッド付き統語森
(HPF:Headed Parse Forest)，依存森(DF:Dependency Forest) について構
築法を示し，それらに完全性と健全性が成立することを示す．また，例文解析
実験により，PDGの振る舞いや特徴についても考察を加える．

\section{選好依存文法(PDG)の概要と圧縮共有データ構造}

\subsection{多レベル圧縮共有データ結合モデル}

\begin{figure}[b]
 \begin{center}
     \epsfile{file=13-3ia3f2.eps}
 \end{center}
\myfiglabelskip
\caption{多レベル圧縮共有データ結合モデル}
\label{fig:MultilevelPSDataConnectionModel}
\end{figure}

PDGは，自然言語の曖昧性・多義性の問題に焦点をあてて設計された形態素・
構文・意味レベルの文解析を行うフレームワークである．ターゲットとしてい
る課題は，

\mygapskip 
\begin{itemize}
\item [(a)] 組み合わせ爆発の回避
\item [(b)] 生成・制約・選好知識の適切な扱い
\item [(c)] 多レベル知識のモジュラリティと統合
\end{itemize}
\mygapskip 

{\mynoindent}である．この課題に対して，図
\ref{fig:MultilevelPSDataConnectionModel}に示す多レベルの圧縮共有デー
タを結合した方式（{\bf 多レベル圧縮共有データ結合モデル}）に基づく解析
方式を採用している．各レベルは，入力文に対するそれぞれの解釈記述空間に
おける言語解釈の全てを圧縮共有データ構造の形式で保持する．入力文に近い
側を下位，出力に近い側を上位レベルと呼ぶ．各レベルの各解釈は上位・下位
のレベルの解釈との対応が取られており(図
\ref{fig:MultilevelPSDataConnectionModel}の「対応」でマークした点線)，
本稿では，これを{\bf 解釈リンケージ}と呼ぶ．多レベル圧縮共有データ結合
モデルでは，下位レベルの解釈はより上位のレベルの解釈を内包しており，入
力文は，全ての解釈を内包している．各レベルにおいて，それぞれ生成・制約・
選好知識が存在する．生成知識は，１つ下位のレベルの解釈から現在のレベル
の解釈を生成（外延化）する(図\ref{fig:MultilevelPSDataConnectionModel}
の$\longmapsto$矢印)．制約知識は，現在のレベルの解釈を制限し，選好知識
は，現在のレベルの解釈の優先度を設定する．このモデルにより，PDGは次の
実現を狙っている．

\begin{itemize}
\item [(a)] 句構造，依存構造等の複数のデータ構造(言語知識の記述ベース)
を利用して，形態素，構文，意味の多レベルの知識をモジュール独立性良く扱
う．
\item [(b)]各レベルで圧縮共有型のデータ構造を用意し各レベルでの全曖昧
性を効率良く保持することで基本的に枝刈りをしないで組合せ爆発を抑制する．
\item [(c)]入力文から最上位レベルまでの解釈リンケージによりマルチレ
ベルの選好知識(選好スコア)を統合し，精度向上を図る．
\item [(d)] 文解釈となる依存木を圧縮共有した選好スコア付き圧縮共有デー
タ構造から制約と選好を組み合わせた最適解探索手法により最適解を探索する．
\end{itemize}

{\mynoindent}一般に各レベルの解釈の内で制約知識を満足する解釈を整合解
釈(well-formed interpretation)と呼ぶ．最適解釈の探索は各レベル毎に定義
可能であり，各レベルの選好知識を利用して，そのレベルの最適解釈を取り出
すことができる．先に述べたように文解析の深さ，出力をどうするかはアプリ
ケーションが基本的に規定する事項である．例えば，同じ機械翻訳でも文の構
造表現として同属言語の場合は句構造表現がよいが，語族が違うと依存構造表
現が適切であったりする．また，解釈リンケージを利用することにより，上位
レベルで最適な解釈を選択し，その解釈に対応する下位レベルの解釈を下位レ
ベルの最適解釈として取り出す方法も考えられる．例えば，意味解析結果とし
て最適な解釈に基づいたタガーなどが自然に実現できる．


\subsection{選好依存文法(PDG)のモデル}

\begin{figure}[b]
 \begin{center}
     \epsfile{file=13-3ia3f3.eps}
 \end{center}
\myfiglabelskip
\caption{PDGの解析モデル}
\label{fig:PDGAnalysisModel}
\end{figure}

\begin{figure}[tb]
 \begin{center}
 \epsfile{file=\myfigdir/COM_PDGの圧縮共有データ構造.eps,scale=0.8}
 \end{center}
\myfiglabelskip
\caption{PDGの圧縮共有データ構造}
\label{fig:PDGPackedSharedDataStructures}
\end{figure}

PDGの全体モデルを図\ref{fig:PDGAnalysisModel}に示す．{\bf 語品詞トレリス}
\footnote{単語と品詞の組を語品詞(WPP:Word Pos Pair)と呼ぶ．単語timeは``
time /v'',``time/n''等の語品詞を持つ．} ，{\bf ヘッド付き統語森}，{\bf 
機能依存森}，{\bf 意味依存森}の４つの圧縮共有データ構造により，それぞれ，語品詞系
列，構文木(句構造)，機能依存木，意味依存木の解釈の集合を保持する．それ
ぞれを計算する処理を形態素解析，構文解析，構造生成，意味構造化と呼ぶ．
各レベルのデータ構造の概要を図\ref{fig:PDGPackedSharedDataStructures}
に示す．PDGでは，単語に対する解釈のレベルとして単語，語品詞，{\bf 語彙
概念}の３階層を採用し，各語に語彙情報として付与されていると想定してい
る．語品詞トレリスは語品詞の隣接関係の解釈を表現する語品詞系列を保持す
る．ヘッド付き統語森は，後に述べるが，語や句のカテゴリの下位範疇化(あ
るいは系列関係)を表現する構文解析木を保持する．句構造頻度の選好知識，
数の一致などの構文的制約など記述できる\footnote{数の一致などの制約を依存木のレベルで記述することも可能であり，
両者で記述してもかまわない．それは実際の文法知識設計の課題である．一般
的には制約知識は可能な限り下位のレベルで処理することが無駄な仮説生成の
抑制に繋がるため効率的である．}．機能依存森は語品詞間の機能依存関係を
表現する機能依存木を保持し，意味依存森は語彙概念間の意味関係を表現する
意味依存木を保持する．以下では簡略のため単に依存森と表記した場合は，機
能依存森を示す．各レベルのデータ構造に対してそれぞれの選好知識により優
先度を与え，これをデータ構造間の対応関係（解釈リンケージ）を通じて統合
し，最終的には，最適解釈探索により最も確からしい解釈（意味依存木）が計
算される\cite{Hirakawa05d_j}．現在，依存森のレベルまでの処理システムが
試作されており，最適解釈探索も依存森に対して行われ依存木を出力するモデ
ルとなっている．意味依存森レベルは今後の課題とし，以下本稿では依存森ま
でのモデルを対象とする．

多レベル構成により他のレベルの知識を活用することが可能となる．例えば，
依存関係をベースとした単一レベル圧縮共有構造モデルであるCDGは，基本的
に全てのノード間に全ての依存関係(仮説)を生成してeliminative parsingを
行う．解釈の枝刈りを行わないという優れた利点があるが生成解釈数が多く効
率面で問題があり，改善手法が提案されている\cite{Harper99}．PDGでは依存
構造に対して全可能性を有する依存森を生成するが，これは下位レベルの統語
森中の解釈\footnote{文脈自由文法により生成され句構造レベルの制約知識に
より絞り込まれた構文木}のみから派生する依存木であり，句構造レベルの知
識の活用による効率化が行える．また，後述するが，句構造の記述体系を利用
することにより，non-projectiveな依存構造を導入可能となり，依存構造とし
ての記述能力の向上にもつながっている．

以上のようにPDGでは，多レベルの圧縮共有データ構造が重要な役割を果たし
ている．以下では，PDGの共有データ構造であるヘッド付き統語森，依存森に
ついて説明してゆく．


\subsection{圧縮共有データ構造の要件}\label{sec:PrerequisitesForPackedSharedDataStructure}

多レベル圧縮共有データ結合モデルにおける圧縮共有データ構造には次の性質
が必要である．
\begin{itemize}
\item[(a)] 各レベルで組合せ爆発が起こらない
\item[(b)] 各種レベルの曖昧性を過不足なく表現できる
\item[(c)] 各レベルでの知識記述のベースとして適切である
\item[(d)] 各種レベル間の解釈リンケージが取れる
\end{itemize}
(a)は，実システムを構築する際に特に重要な課題である．一般に解釈の組合
せ展開を行うと直ぐに扱いが困難になり，また，計算時間的にも不十分となる．
(b)は，多レベルの知識を扱う場合に，各レベルの曖昧性を全て過不足なく表
現できること，すなわち共有構造そのものに由来する解釈の枝刈り(あるべき
解釈の欠落)や解釈の過生成(あるべきでない解釈の生成) が起こらないという
性質である．この性質を保持した上でシステム構築上有効な枝刈りを導入でき
ることは重要な好ましい性質である．(c)は，それぞれのレベル
での知識の記述が行いやすいこと,選好知識と制約知識が適切に扱えること
であり\cite{Hirakawa02_j}，(d)は各レベルの解釈の対応関係を取ることがで
きるという性質である．

\begin{comment}
\subsection{句構造と依存構造の併用}
文解析を精度良く行なうためには様々な知識を利用する必要がある．従来，文
の構造を記述する代表的枠組みとして句構造と依存構造がある．句構造は，品
詞への抽象化により語や句の順序に関する知識の記述に優れており，依存構造
は語の間の種々の依存関係に関する知識の記述に優れている．それぞれの表現
レベルでの制約知識・選好知識の記述を自然な形で可能とするため，PDGでは，
句構造形式の共有データ構造(ヘッド付き統語森)と依存構造形式の共有データ
構造(依存森)をそれぞれ関連付けて組み込んでいる．これは句構造(C-構造)と
機能構造(F-構造)という２つの構文レベルの表現を持つLFG\cite{Kaplan89}に
おいて，SUBJECT,OBJECTなど構文的機能に関する制約がF-構造で記述され，文
法の記述性を高めているのと類似している\footnote{LFGでは，１つの文解釈
であるC-構造とそれから作られるF-構造の制約関係などを規定しているが，文
に対する可能なC-構造全体とF-構造全体の扱いについては，特に規定していな
い点がPDGとの基本的違いである．}．なお，Early法，Chart法といった文脈自
由文法の解析アルゴリズムを用いて依存文法を直接解析して依存構造を求める
手法も提案されている\cite{Mertens02} が，句構造を作らない点で本手法と
は異なっている．
\end{comment}

\subsection{圧縮共有データ構造の従来技術と問題点}

\subsubsection{語品詞トレリスと圧縮共有統語森}

語品詞トレリスは，全ての語品詞系列を圧縮共有するデータ構造であり，PDG 
でもそのまま利用する．構文レベルの解析手法としては文脈自由文法をベース
にした解析が広く用いられておりPDGもこれを利用する．文脈自由文法で入力
文を解析し文の可能な解釈全体を得る手法は広く知られており，例えば，富田
により，グラフスタックを用いた構文解析手法と共に文の句構造解釈(構文木)
全体を効率的に保持する圧縮共有統語森(Packed Shared Parse Forest) が提
案されている\cite{Tomita87}．圧縮共有統語森中の構文木は，語品詞トレリ
ス中の語品詞系列と対応関係が取れ多レベル圧縮共有データ結合モデルとして
利用可能である．

\subsubsection{意味係り受けグラフ}

文献\cite{Hirakawa02_j}は，{\bf 意味係り受けグラフ}を提案し，係り受け
の多義（構文的多義）と係り受け意味関係の多義を効率良く保持する手法を提
案した．意味係り受けグラフは，ATN文法を用いて句構造解析を行い係り受け
関係を表す依存グラフを生成し，そこから意味係り受け関係を表す意味係り受
けグラフを生成する．意味係り受けグラフは，修飾語が被修飾語の左に位置す
る，英語などに比べ品詞多義は殆どないという日本語の特徴を前提に設計され
ているため，多品詞を扱えないなど英語などに適用できないという汎用性に関
する問題を有しており，PDGの圧縮共有データ構造としては採用しない．

\subsubsection{構文グラフ/排他マトリックス}
\begin{figure}[b]
 \begin{center}
 \epsfile{file=\myfigdir/DF構文グラフ例.eps,scale=0.79}
 \end{center}
\myfiglabelskip
\caption{例文に対する構文グラフと排他マトリックス}
\label{fig:KoubunGraph}
\end{figure}

Seoは，文の句構造解釈全体と対応する依存構造全体を効率良く保持する方法
として{\bf 構文グラフ}(Syntactic Graph)を提案した\cite{Seo89,Rim90}．構
文グラフは，PDGの共有データ構造として有望であったが，大きな問題もあり
そのまま採用することはできないことが判明した．

構文グラフは，単語間の依存関係をベースに文の可能な解釈を圧縮共有する枠
組みである．構文グラフは，語品詞に対応するノードとノード間の依存関係を
表現する名前付きアークで構成される有向グラフであり，{\bf 排他マトリッ
クス} (EM:Exclusion Matrix)と呼ばれるデータと組になって，入力文に含ま
れる依存構造の集合（文の解釈の集合）を表現する．構文グラフは，３次組
(Triple)と呼ばれる，アーク名とその両端のノード(語品詞，表層位置などを
持つ)の組からなる集合で表現される．図\ref{fig:KoubunGraph} は，``Time
flies like an arrow''に対する構文グラフ/排他マトリックスである．アーク
の括弧中の番号はそのIDである．１つのノードに入る複数のアークは修飾の曖
昧性を表現している．Sは，開始記号に相当する\footnote{本稿では係り受
け解析の慣習に従ってアークの方向を記述する．構文グラフとは逆向きである
が本質的な差はない．}．

排他マトリックスは，構文グラフを構成するアークを行・列とし，アーク間の
共起制約を記述するために導入されている．排他マトリックスの$i$行$j$列が
1である場合には，$i$番目と$j$番目のアークは，いかなる解釈(依存木)にお
いても共起しない．

構文グラフ/排他マトリックスは，統語森に基づいたデータ構造から生成され
る．PDGでも同じデータ構造を用いており，これをヘッド付き統語森と呼ぶ．
ヘッド付き統語森の詳細は，\ref{sec:datastructure}章で述べる．なお，以
下では，単に統語森と言った場合はヘッド付き統語森を意味し，従来の統語森
はヘッド無し統語森と記述することとする．


文献\cite{Seo89}では，統語森と構文グラフ/排他マトリックス間の完全性
(completeness),健全性(soundness) について言及している．完全性は，「統
語森中の１つの構文木が存在した時に，構文グラフ/排他マトリックス中にそ
れに対応する依存木が存在する」という性質であり，健全性は，「構文グラフ
/排他マトリックス 中の１つの依存木が存在した時に，統語森中にそれに対応
する構文木が存在する」という性質である．構文グラフ/排他マトリックスの
完全性が成立することは示されているが，健全性については保証されていない．
排他マトリックスは，３次組の間の共起関係を規定しているが，ある１つの構
文木に対応する依存木が存在した場合，その依存木に含まれる３次組の間の共
起排他制約を排他マトリックスから除外するという方法で構成される．排他マ
トリックスは，全ての依存構造の解釈を規定するため，この除外された共起排
他制約が他の全ての解釈(依存木)において制約として必要でない場合にのみ健
全性が保証されることになる．付録１に構文グラフで健全性が破綻する例を示
す．

\section{PDGにおける共有データ構造}\label{sec:datastructure}

　PDGでは，前節で述べた従来手法の問題を解決するデータ保持方式として，
文脈自由文法の構文構造の保存方式としてヘッド付き統語森を採用し，依存構
造の保存方式として依存森を提案する．

\subsection{ヘッド付き統語森}

{\bf ヘッド付き統語森}は統語森の一種であり，適用された書き換え規則に対
応する弧(edge)から構成され，次の条件を満足する構文木を圧縮共有する．
\begin{itemize}
\item[(a)]句の非終端記号(カテゴリ)が同じ
\item[(b)]句の被覆する単語範囲が同じ
\item[(c)]句ヘッドとなる主構成素(語品詞)が同じ
\end{itemize}
(a),(b)の２つがヘッド無し統語森の共有条件である\cite{Schiehlen96}．ヘッ
ド付き統語森中の構文木は，統語森中の構文木と対応が取れる．PDGにおける
弧とヘッド付き統語森の具体例は構築アルゴリズムと共に
\ref{sec:construction}章で述べる．

\subsection{依存森}
{\bf 依存森}は，{\bf 依存グラフ}(DG:Dependency Graph)と{\bf 共起マトリッ
クス} (CM:Co-occurrence Matrix）より成る．以下，依存森の構造と依存木に
ついて説明する．

\subsubsection{依存グラフと共起マトリックス}

\begin{figure}[b]
 \begin{center}
 \epsfile{file=\myfigdir/DF_TimeFliesに対する初期依存森.eps,scale=0.75}
 \end{center}
\myfiglabelskip
\caption{``Time flies like an arrow''に対する初期依存森}
\label{fig:IDF}
\end{figure}

図\ref{fig:IDF}は，``Time flies like an arrow''に対する依存森の例であ
る.依存グラフは，語品詞に対応するノードと１つのルートノードrootならび
に，ノード間の依存関係を表現する名前付きアークより構成される．依存グラ
フは，rootをルートノードとする有向グラフであり，実際には，アークとその
両端のノードの組からなる{\bf 依存片}(dependency piece)\footnote{ 依存
片とアークは1対1対応するので，特に区別の必要がない場合は依存片をアーク
と記述する．}の集合として表現する.アークは，アーク名とIDを有す．アーク
の元側を{\bf 依存ノード}(dependent あるいはmodifier) ，先側を{\bf 支配
ノード}(governor あるいはmodificand)と呼ぶ．また，ノードには，表層位置
などの情報も含まれている．アークの数を{\bf 依存森のサイズ}と呼ぶ．また，
依存グラフの部分集合で木構造を成すアーク集合が依存木であり，文や句の解
釈を表現する．依存グラフは複数の依存木を含む圧縮共有データ構造となって
いる．

共起マトリックスは，アークIDで示されたアーク集合を行と列に取り，アーク
間の共起関係を規定する．共起マトリックスCM($i$,$j$)が○の場合に限り，アー
ク$i$ と$j$は１つの依存木（解釈）において共起可能であるという制約を表
現する．共起関係は双方向関係であり，CMは対称行列となる．



\subsubsection{整依存木}

依存森中の依存木のうち次の整依存木条件を満たす依存木を{\bf 整依存木}
(Well-formed Dependency Tree)と呼ぶ．
\begin{definition} \label{def:WellFormedDepTree}
{\bf 整依存木条件}とは，次の３つの条件(a)〜(c)全体をいう．
\begin{itemize}
\item[(a)]表層位置が同じノードは存在しない({\bf 語品詞単一解釈条件}）
\item[(b)]入力文の単語と，入力文に対応する依存木のノードの間に1 対1対応が取れる({\bf 被覆条件}）
\item[(c)]共起マトリックスにおいて共起関係が成立する({\bf 整共起条件})
\end{itemize}
\end{definition}
(a)(b)の２つを纏めて{\bf 整被覆条件}と呼び，これを満たす木を{\bf 整被覆木}
(Well-covered Dependency Tree)と呼ぶ.また，(c)を満たす依存木を{\bf 整共起依
存木}(Well-cooccurred Dependency Tree)と呼ぶ．整依存木の集合が入力文に
対する解釈の集合となる．図\ref{fig:IDF}の依存森では，「時は矢のように
過ぎる」，「時ハエは矢を好む」，「矢のようにハエを計れ」，「矢のような
ハエを計れ」に対応する4つの整依存木が存在する．なお，ノード１つからな
る依存木(アークが存在しない) も，整依存木として扱う．この場合のみ依存
木はノード１つからなる集合となる．


\subsubsection{初期依存森と縮退依存森}
複数の解釈に対するアークの共有の度合いによって，同じ依存木の集合を表す
サイズの異なった複数の依存森を構成可能である．詳細は後述するが，PDGで
は，{\bf 初期依存森}(Initial Dependency Forest)と，それから変換して得
られる{\bf 縮退依存森}(Reduced Dependency Forest)の2種を扱う．それぞれ，
{\bf 初期依存グラフ}と{\bf 初期共起マトリックス}，ならびに，{\bf 縮退
依存グラフ}と{\bf 縮退共起マトリックス}よりなる．単に依存森と呼んだ場
合は，通常後者を示す．図\ref{fig:IDF}の初期依存グラフは，図
\ref{fig:KoubunGraph}の構文グラフと比較すると，``fly/n''と``time/v''の
間のアーク数が異なっている．対応する縮退依存森については後述する．

\section{統語森と依存森の生成}\label{sec:construction}

PDGでは，形態素解析，構文解析，統語森・初期依存グラフの生成，
縮退依存森導出の順で解析が進む．本稿では，形態素解析処理については省略
し，構文解析以降について述べる．

\subsection{文法規則}\label{sec:bunpoukisoku}
PDGにおいて文法規則は，可能な句構造の定義と，句構造から依存構造へのマッ
ピングとを規定する拡張文脈自由文法(extended CFG)で記述される．文法規則は，次の形式をしている．
\mygapskip 
{\mynoindent}y/$Y \rightarrow$ x$_1$/$X_1$,$\ldots$,x$_n$/$X_n$ : [arc($arcname_1$,$X_i$,$X_j$),$\ldots$,arc($arcname_{n-1}$,$X_k$,$X_l$)] (0$<i$,$j$,$k$,$l{\leq}n$)

{\mynoindent}［例］vp/$V \rightarrow$ v$/V$,np$/NP$,pp$/PP$ : [arc(obj,$NP$,$V$),arc(vpp,$PP$,$V$)]
\mygapskip 
{\mynoindent}規則は，``:''で区切られた{\bf 書き換え規則部}と{\bf 構造構築部}よりな
る．書き換え規則の左辺の``y/$Y$''及び{\bf 構成素}
(constituent)``x$_i$/$X_i$''は，``{\bf 構文カテゴリ}/{\bf 構造変数}'' 
を表す．$Y$は{\bf 句ヘッド}(phrase head)と呼ばれ，主構成素(head
constituent) に相当し，{\bf 規則ボディ}(rule body)である
``$X_1{\ldots}X_n$'' のいずれかと同一となる．構造構築部は，``arc(アー
ク名, 構造変数1,構造変数2)''という形式のアークの集合であり\footnote{部
分依存構造はアークの集合であるがプログラムの都合上リスト形式としている．
本稿ではプログラム出力等の場合は[]で集合を表現する場合もある．}，構造
変数には，書き換え規則部の構成要素の句ヘッドとなる語品詞が束縛される．
例は，$V$ をヘッドとし，obj アークで$NP$ が，vppアークで$PP$が接続する
依存構造を示している．規則中の部分依存構造は，次の部分依存構造条件を満
足する整部分依存構造である．
\begin{definition} \label{def:DSCondition}
{\bf 部分依存構造条件}とは次の２つの条件(a),(b)全体をいう．
\begin{itemize}
\item[(a)] 主構成素に対応する句ヘッド$Y$をルートとする木構造である．(非主構成素は，他の構成素と依存関係（アーク）を持つ)
\item[(b)] 規則ボディの構成素の句ヘッドは，部分依存構造をなす木構造の構造変数と１対１対応が取れる
\end{itemize}
\end{definition}

例文``Time flies like an arrow''を解析するための文法規則と辞書を図
\ref{fig:ExampleGrammar}に示す．規則(R0)は，規則ヘッドをroot，規則ボ
ディをスタートシンボル(s) とし，{\bf トップノード}[root]-xを導入する特殊な
規則であり，ルート規則と呼ぶ．ルート規則は，統語森のルートとなる弧と依存森のトップノードをそれぞれ１つ
にするために導入している\footnote{この規則は，PDGの完全性・健全性を保
証するだけであれば本質的には不要である．}．

\begin{figure}[t]
 \begin{center}
  \epsfile{file=\myfigdir/DF例文TimeFlyに対する文法規則.eps,scale=0.84}
 \end{center}
\myfiglabelskip
\caption{例文を解析する文法規則と辞書}
\label{fig:ExampleGrammar}
\end{figure}

\subsection{構文解析}\label{sec:konokousei}

PDGの構文解析は，本稿では，Bottom-up Chart Parsingのアルゴリズムをベー
スに，依存構造の生成が可能となるよう，弧の構成やアルゴリズムを拡張する
ことにより実現している．

\subsubsection{弧の構成と例}

Chart Parsingにおいて，弧は，{\bf 始点}(FP)，{\bf 終点}(TP)，{\bf 規則
ヘッド頂点}(C)，{\bf 既存構成素列}(FCS)，{\bf 残り構成素列}(RCS)の５次
組$<$FP,TP,C,FCS,RCS$>$から構成される．文法規則のヘッドは，規則ヘッド
頂点に，規則ボディは，既存構成素列と残り構成素列に対応し，ドット（・）
で規則ボディ内の区切りを表現し，次の例のような形式で図式的に表現される．

 $<$0,1, s $\rightarrow$ np ・ vp pp$>$

{\mynoindent}この弧は，文法規則``s $\rightarrow$ np vp pp''から生成さ
れる例であり，FP=0,TP=1, C=s, FCS=[np], RCS=[vp,pp]である．また，入力
単語に対する辞書の検索結果は，次の例のように，品詞をヘッドとし、単語をボディと
する不活性弧として表現される．

 $<$0,1, n $\rightarrow$ [time]・$>$

\begin{figure}[b]
 \begin{center}
  \epsfile{file=\myfigdir/DF弧の構成と例.eps,scale=0.85}
 \end{center}
\myfiglabelskip
\caption{弧の構成と例}
\label{fig:ArcStructure}
\end{figure}

PDGの構文解析では，文法規則の部分依存構造に対する処理と複数の弧の圧縮
共有処理の２点で拡張を行っている．依存構造構築のため，通常のChart
Parsing の弧に句ヘッド(PH)と部分依存構造(DS)を追加しており，模式的に示
すと次のようになる．

通常の弧：$<$0,1, s $\rightarrow$ np ・ vp pp$>$

PDGの弧 ：$<$0,1, s/PH $\rightarrow$ np/NP ・ vp/PH pp/PP : DS$>$

{\mynoindent}\ref{sec:bunpoukisoku}節で述べたように，PHが句ヘッド(ノー
ド)，DSが部分依存構造(アーク集合)を示す．また，詳細は後述するが，不活
性弧については圧縮共有を行うため，複数の弧を１つに纏めた{\bf 圧縮弧}と
いうデータ構造を利用する．圧縮弧は，既存構成素列(FCS)と部分依存構造
(DS)の部分を，それぞれのリストに拡張したものである．圧縮弧に対して，１
つの構成素列と部分依存構造を持つ弧を{\bf 単一弧}と呼ぶ．圧縮弧は，共有
可能な単一弧の集合と等価である．次にこれらの対応関係を模式的表現で例示
する．

単一弧： $<$0,5, s/PH $\rightarrow$ np/NP vp/PH pp/PP・: DS1$>$

　　　　 $<$0,5, s/PH $\rightarrow$ np/NP vp/PH ・: DS2$>$

圧縮弧： $<$0,5, s/PH $\rightarrow$ [[np/NP vp/PH pp/PP], [np/NP vp/PH]] ・: [DS1,DS2]$>$

{\mynoindent}この例で，PHは句ヘッド，[np/NP vp/PH pp/PP], [np/NP vp/PH]は構成素列，
DS1,DS2は部分依存構造を示している．以下では簡便のため，圧縮弧は``E''，``
$<$E ${\ldots}>$''，「弧E」などで，単一弧は``e''，``$<$e ${\ldots}>$''，
「弧e」などで示す．曖昧でない場合や区別が必要でない場合などは単に「弧」
とも記述する．また，不活性弧は，記号の前に*をつけて表現する．弧*Eは不
活性圧縮弧，弧*eは不活性単一弧を示す．

以下で示すPDGの構文解析は，圧縮弧のデータ形式で行われる．図
\ref{fig:ArcStructure}に圧縮弧の構成を示す．圧縮弧は8次組で構成されて
いる．FCSLとDSLは同じ長さのリストであり，i番目の要素を取り出した
(FCS$_i$,DS$_i$) を{\bf CSDSペア}と呼ぶ．CSDSペアは，上記の単一弧に対
応している．

図\ref{fig:ArcStructure}の弧E1〜*E3は，名詞句規則に対応する弧が解析が
進むにつれて生成されてゆく例である．弧*E3は，``an arrow''をnpとして解
釈し，部分依存構造として\{arc(det-14,[an]-det-3,[arrow]-n-4)\}を持つ不
活性弧(RCSが[]) である．[arrow]-n-4は，単語[arrow],品詞n,位置4のノード
である．弧*E4は，複数の解釈を持つ弧の例である．FCSL の２要素とDSLの２
要素がそれぞれ対応し，([103,169] \{obj-25\}])\footnote{obj-25 は略記で
あり，実際はarc(obj-25,[flies]-n-1,[time]-v-0)である．} と
([103,119,165] \{obj-4,vpp-20\})の２つのCSDSペアが存在している．弧@E5 
のような，辞書引きにより生成される不活性弧は{\bf 語彙弧}(lexical edge)
と呼ぶ．語彙弧の部分依存構造は，ノード１つからなる集合である．語彙弧は
@をつけて@E,@eの様に表現する．


\subsubsection{構文解析アルゴリズム}

\begin{figure*}[b]
 \begin{center}
      \epsfile{file=\myfigdir/DFパースアルゴリズム.eps,width=\textwidth}
 \end{center}
\myfiglabelskip
\caption{PDGボトムアップチャートパージングアルゴリズム}
\label{fig:ChartAlgotithm}
\end{figure*}

図\ref{fig:ChartAlgotithm} にPDGの構文解析アルゴリズムを示す．基本構成
は，Agendaを用いた一般的なChart Parsingアルゴリズム\cite{Winograd83}で
あり，先頭から順次入力単語を語彙弧化してAgendaに追加処理する処理
((a),(b)）とAgendaが空になるまでAgenda 中の不活性弧に対して文法規則な
らびにChart 中の活性弧から可能な弧を生成・展開する弧の{\bf 結合}の処理
((e),(f))より成る．Agenda中の弧は，Chart中の弧と共有可能かどうかが判定
され((c),(j))，共有可能な場合はマージされる((d))ことにより，圧縮共有が
行なわれる．基本的に一般的なアルゴリズムであり，詳細な説明は省略するが，
次にPDG特有の依存構造の構築の部分について説明する．

本アルゴリズムは，弧を生成しながら弧の部分依存構造を構築する．これは句
ヘッド(ノード)と依存構造中の構造変数を束縛することで実現される．この変
数束縛は，不活性弧と文法規則から新しい弧が生成される時点((g))，ならび
に，不活性弧とChart中の活性弧により新しい弧が生成される時点((h))，すな
わち弧の結合が生じる時点で，bind\_varにより不活性弧の句ヘッドが他方の
弧の残り構成素列の先頭の構造変数に束縛されることで行なわれる．さらに，
この変数束縛により依存ノードと支配ノードの両方が束縛されたアーク({\bf 
確定アーク}と呼ぶ)に対して，add\_arcidによりユニークなアークIDが付与さ
れる((i))．図\ref{fig:ArcStructure}の弧E2の変数\$2にノード[arrow]-n-4
が束縛されると弧*E3になる．


それぞれの弧は弧IDで関連付けられており，弧からその下位の弧(構成要素に
対応）を順次辿れる．図\ref{fig:ArcStructure}の弧*E3では，弧\#160(弧IDが
160の弧)は，``np $\rightarrow$ det,n''の規則から生成された弧であり，既
存構成素列[153,156]は，弧\#153が文法規則中の構成素detに，弧\#156が構
成素nに対応することを示している．また，弧*E4のように複数の既存構成素
列を持つ弧は，merge\_csds((d))により生成される．

構文解析に成功した場合には，Chartには句ヘッドが[root]-xで文全体を被覆
する不活性弧が１つ存在する．これを{\bf ルート弧}(root edge)と呼ぶ．


\subsection{統語森・初期依存森の生成}\label{sec:PFandDFseisei}
構文解析後のChartは，活性弧，不活性弧より成る．この集合に対して，不活
性弧*Eから辿れる弧の集合をhpf(*E)と記述する．ルート弧を*E$_{root}$とし
た時，統語森はhpf(*E$_{root}$)となる．ルート弧から到達できない不活性弧
も存在するため，hpf(*E$_{root}$) はChart中の不活性弧全体の部分集合とな
る．初期依存グラフは，統語森中のアークの集合であり，hpf(*E$_{root}$)と
同時に求められる．また，初期共起マトリックスも同時に求められる．図
\ref{fig:HPF_IDF_Algorithm} に統語森・初期依存森を求めるアルゴリズム, 
また，図\ref{fig:PDGParseForest}に，図\ref{fig:ExampleGrammar}の文法を
用いて例文を構文解析した結果得られる統語森を示す．統語森を構成する全て
の弧は不活性弧であるため，残り構成素列([])は省略している．なお，統語森
の圧縮弧の数を{\bf 統語森のサイズ}と呼ぶ．弧の同一性において句ヘッドを
考慮しているため(図\ref{fig:ChartAlgotithm}(j))ヘッド付き統語森のサイ
ズは，ヘッド無し統語森のサイズ以上となる．

\begin{figure}[t]
 \begin{center}
  \epsfile{file=\myfigdir/DF統語森依存森アルゴリズム.eps,scale=0.82}
 \end{center}
\myfiglabelskip
\caption{統語森・初期依存森を求めるアルゴリズム}
\label{fig:HPF_IDF_Algorithm}
\end{figure}

\begin{figure}[t]
 \begin{center}
  \epsfile{file=\myfigdir/DFヘッド付き統語森.eps,scale=0.95}
 \end{center}
\myfiglabelskip
\caption{``time flies like an arrow''に対する統語森}
\label{fig:PDGParseForest}
\end{figure}

図\ref{fig:HPF_IDF_Algorithm}のアルゴリズムは，
try\_edge,try\_FCSL,try\_CSの３つの関数を再帰的に呼びながら，それぞれ
の引数(圧縮弧，構成素列リスト，構成素列)の下位の要素(構成素列リスト，
構成素列，圧縮弧）を深さ優先で重複を避けてトラバースする構成となってい
る((d),(h),(j))．それぞれの関数の実行後は,その引数に対する統語森HPF，
依存グラフDG，共起マトリックスCMの要素や値が追加設定されている．
try\_edge(E),try\_FCSL(FCSL),try\_CS(CS)が返すアーク集合中のアークをそ
れぞれ弧E, 構成素列リストFCSL,構成素列CSが{\bf 支配するアーク}と呼ぶ．

全体に対する処理は,図\ref{fig:HPF_IDF_Algorithm}の(a)の``try\_edge(ルー
ト弧)''である.  try\_edgeでは，(b)で既に実行済みか否かを判定し，実行済
みの場合は，TERに記録済みのアーク集合を取り出して返す．TERへの登録を
行なうのは(g)である．HPFに弧が追加されるのは，(c)と(e)においてである．
(f)にあるように，弧Eが支配するアークは，弧EのDSL中のアークとFCSLの支配す
るアークの和集合である．

try\_FCSLは，複数のCSDSペアを処理し，try\_CSは，その中の１つのCSを処理
する．(i)にあるように，FCSLの支配するアーク集合は，その要素であるCSが
支配するアークの和集合である．また，(k)にあるように，CSの支配するアー
ク集合は，その要素である圧縮弧が支配するアークの和集合である．

\begin{figure}[tbh]
 \begin{center}
  \epsfile{file=\myfigdir/DF関数実行.eps,scale=0.9}
 \end{center}
\myfiglabelskip
\caption{アルゴリズムの実行例}
\label{fig:TryEdgeFunctionExecution}
\end{figure}

図\ref{fig:PDGParseForest}の弧\#170を例に処理の具体例を図
\ref{fig:TryEdgeFunctionExecution}に示す．(c\#)は関数の呼び出し，(r\#)
はその結果(支配するアーク集合)を示す．(c1)〜(c4)は，図
\ref{fig:HPF_IDF_Algorithm} (j),(d),(h)の再帰呼び出しである．弧\#103は
語彙弧であるため，(c4)は(r4)の\{\}を返す．(c3)の処理が終了し(r3)を得る
と，(c2)の２番目のCSDSペア([103,119,165],\{obj-4,vpp-20\})に対する処理
(c5)が行なわれる．(c6)で再度`` try\_edge (弧\#103)''が実行されるが，こ
の時は，図\ref{fig:HPF_IDF_Algorithm}(b)でTERに保存された計算結果を検
索して返す．最終的に(r1)が得られる．

ここで，共起マトリックスの生成処理について説明する．共起マトリックスは，
１つの構文木に同時に含まれるアークの間に共起可能性を設定するよう，次の
共起設定条件により設定される．
\begin{definition} \label{def:CoocCondition}
{\bf 共起設定条件}とは次の3つの条件(CM1),(CM2),(CM3)のいずれかをいう．
\begin{itemize}
\item[{\mysmallitemindent}(CM1)]\ １つの部分依存構造DS中のアークは共起する
\item[{\mysmallitemindent}(CM2)]\ CSDSペア(CS,DS)において，CSが支配するアークは，DS中のアークと共起する
\item[{\mysmallitemindent}(CM3)]\ １つの構成素列CSが支配するアーク間には共起関係がある
\end{itemize}
\end{definition}
これはそれぞれ図\ref{fig:HPF_IDF_Algorithm}のCM処理(1)〜
(3)に対応している．弧\#170の例では，try\_FCSLの処理で2番目のCSDSペア
([103,119,165],\{obj-4,vpp-20\}) に対してCM処理(1)で(CM1)すなわち
set\_CM(\{obj-4,vpp-20\},\{obj-4,vpp-20\})が実施される．また，CM処理
(2)では，A\_CSは図\ref{fig:TryEdgeFunctionExecution}(r5)となり，(CM2)
すなわちset\_CM(\{obj-4,vpp-20\},\{pre-15,det-14\})が実施される．また，
try\_CS([103,119,165])の処理において，CM処理(3)により(CM3) すなわち弧
\#103,\#119,\#165が支配するアーク間の共起関係のCMへのセットが行われる．

例題に対するアルゴリズムの出力は，図\ref{fig:PDGParseForest}の
統語森ならびに図\ref{fig:IDF}の初期依存森となる．弧\#181,\#176,\#174 
は，同じ非終端記号sと句の範囲(0 から5)を持つが，句ヘッドとなるノードが
異なるため共有されておらず，ヘッド無し統語森とは異なっている．

\subsection{縮退依存森の生成}

初期依存森には，図\ref{fig:IDF}におけるobj4とobj25のようにアークID以外
は同一のアークが存在することがあり，これを{\bf 同値アーク}と呼ぶ．同
値アークは，１つの文法規則から生成されたり，複数の文法規則から生成され
たりする．例えば，obj4とobj25は，図\ref{fig:ExampleGrammar} の
(R9),(R10)の構成素列``vp np''の部分から生成されている．(R9),(R10)は，
前置詞句の有無という差はあるが，``vp np''の関係は２つの規則で同一であ
り，依存構造の解釈という観点から同値アークは等価であると言える
\footnote{文法規則の記法に任意要素を表す記号\{\}を導入すれば(R9),(R10) 
をvp/$V$ $\rightarrow$ v/$V$,np/$NP$,\{pp/$PP$\} :
[arc(obj,$NP$,$V$),arc(vpp,$PP$,$V$)]のように１つの規則に統合できる．
この規則からは同値アークは生成されない．}．


同値性を扱うために，いくつかの定義を行う．ID付きアークのアークIDを``?''
と置換したアークを{\bf 汎化アーク}と呼ぶ．アークを全て汎化した依存木を
{\bf 汎化依存木}と呼ぶ．通常のID付きのアークからなる依存木を明示する時
は{\bf ID付き依存木}と記述する．また，アークXの汎化アークを?X，依存木
DTの汎化依存木を?DTのように記述する．汎化依存木が等しい２つのID付き依
存木は{\bf 同値である}と言う．

縮退依存森は，初期依存森を縮退することで得られる．依存森の縮退とは，依
存森の健全性を保持しながら複数の同値アークを１つにマージする操作であり，
結果として依存森のサイズは小さくなる．

\subsubsection{同値アークのマージ操作}

依存グラフDG中の同値アーク$X$,$Y$(equiv($X$,$Y$)と記述する)に対する
{\bf マージ操作}を次のように定義する．
\begin{definition}
マージ操作
\begin{itemize}
\item[(1)] 依存グラフDGより，$Y$を削除して新たな依存グラフDG'を得る．(DG'=DG$-\{Y\}$)
\item[(2)] アーク$I$($I{\in}$DG,$I{\neq}X$,$I{\neq}Y$,CM($Y$,$I$)=○)
に対して，set\_CM($X$,$I$)を行なうことにより共起マトリックスCMより新
たな共起マトリックスCM'を得る．
\end{itemize}
\end{definition}

マージ操作によりDG',CM'からなる新たな縮退依存森が得られる．図
\ref{fig:ArcMerge}にマージの例を共起マトリックスの形式で模式的に示す．
以下の議論で依存木の集合やアークの集合などを定義するが，マージ操作の前
後の区別を示す場合には，``wrt DG,CM''あるいは``wrt DF''(wrt:with
respect to)の表現を付けて示す．例えば，以下で定義するアーク$X$を含む整
依存木の集合dts($X$) に対して，``dts($X$) wrt DG,CM''，``dts($X$) wrt
DG',CM' ''はそれぞれマージ前と後の依存森に対する集合を示し，``dts($X$)
wrt DG,CM=dts($X$) wrt DG',CM' '' は，マージの前後でdts($X$)の値が同じ
ことを示す．簡便のため，以下では``wrt DG,CM''の部分は基本的に省略して
いる．

初期依存グラフの全同値アークをマージする\footnote{これは構文解析時に同
値アークを共有することと同じである．}と構文グラフと同じ構造になり，健
全性を保てなくなる．

\begin{figure}[b]
 \begin{center}
  \epsfile{file=\myfigdir/DFマージ操作.eps,scale=0.54}
 \end{center}
\myfiglabelskip

\caption{同値アークペア(X,Y)のマージ操作の例}
\label{fig:ArcMerge}
\end{figure}


\subsubsection{同値アークのマージ条件}

依存森の縮退の定義より，依存森の健全性を保持すること，すなわち，同値アー
クのマージの前後で新規の汎化依存木(新規の解釈)が生成されないことが縮退
の条件である．

\mygapskip 
\mynoindent{\bf[同値アークのマージ条件]}

{\mynoindent}「同値アークX,Yのマージ前後の依存森をそれぞれDF,DF'とした
時，縮退条件は，``DF中の汎化整依存木集合$=$DF'中の汎化整依存木集合'' 
である．」{\mygapskip}

{\mynoindent}この条件は，依存森DF'に新規の汎化依存木が存在しないことを
検証することで検証できる．今，DFに対してDF'に新規の汎化依存木が存在す
るための条件を{\bf 汎化依存木の増加条件}とすると，同値アークのマージ条
件は，「汎化依存木の増加条件が満足されないこと」と等しい．

依存森はID付きアークより構成されているため，ID付き依存木の集合と(それ
から得られる)汎化依存木の集合の２つを規定している．今，DFに対してDF'に
新規のID付き依存木が存在する条件を{\bf ID付き依存木の増加条件}( ``DF中
のID付き整依存木集合${\neq}$DF'中のID付き整依存木集合'')とする．ID 付
き依存木が増加しなければ汎化依存木の増加はなく，また，ID付き依存木が増
加してもそれがDF中のID付き依存木と同値であれば汎化依存木の増加は起こら
ない．すなわち，ID付き依存木の増加条件は汎化依存木の増加条件の必要条件
である．以下では，まず，ID付き依存木の増加条件を検証し，次に汎化依存木
の増加条件を検証するという考え方で同値アークのX,Yのマージ条件を詳細化
する．

\subsubsection{ID付き依存木の増加条件}\label{subsec:IDDTZoukaJuoken}

新たな(ID付き)整依存木の増加は，同値アークのマージにより新たにアーク間
に共起関係が許されることに起因する．アークU,Vに対してCM(U,V)${\neq}$○
がCM(U,V)$=$○に変化することを{\bf アークペア(U,V)の許諾}と呼び，次が
成立する．

\begin{lemma}[アークペアの許諾と整依存木の増加]
\label{lem:ArcPairAndNewTree}
アークペア(U,V)の許諾により新たな整依存木が増加する場合，その依存木は
U,Vを要素として含んでいる．
\end{lemma}

{\mynoindent}補題\ref{lem:ArcPairAndNewTree}は，もしU,Vの許諾によ
りUとVの両方を同時に含まない新しい依存木が生成されると仮定するとそ
の依存木は許諾の前でも存在してしまうことになることから明らかである．

\mygapskip
{\mynoindent}ここで，同値アークX,Yに対してuniq,diffを次のように定義する．\\
\hspace{8mm}uniq(X,Y)=\{$I$ ${\mid}$ CM(X,$I$)=○,CM(Y,$I$)${\neq}$○,$I{\in}$DG\}\\
\hspace{8mm}diff(X,Y)=\{($I$,$J$)${\mid}$$I{\in}$uniq(X,Y),$J{\in}$uniq(Y,X)\}\\ 
図\ref{fig:ArcMerge}の例では，
uniq(X,Y)=\{j,n\},uniq(Y,X)=\{k\},diff(X,Y)=\{(j,k),(n,k)\}
となる．一般に次が成立する．

\begin{lemma}[新規の整依存木の含むアーク]
\label{lem:ArcsInNewTree}

同値アークX,Yのマージにより新たに整依存木が生成される場合には，その依
存木は少なくとも１つの(A,B) $\in$ diff(X,Y)であるA,Bを含む．

\proof{

X,Yのマージ前後の依存森をそれぞれDF,DF'とする．X,Yのマージで生じるアー
クペア(X,B$_i$)の許諾により新たな依存木DT$_x$ が得られたとすると，補題
\ref{lem:ArcPairAndNewTree} より，X,B$_i$は，DT$_x$の要素である．ここ
で，R$=$DT$_x-$\{X,B$_i$\} とする．U${\in}$Rを考えると，DT$_x$ は整依
存木であるからCM(X,U)$=$○ wrt DF',CM(B$_i$,U)=○ wrt DF' である．

今，CM(Y,U)${\neq}$○ wrt DFであるアークUが存在しない,すなわち
CM(Y,U)$=$○ wrt DF,U${\in}$Rを仮定すると，DT$_y$=\{Y,B$_i$\}+Rは，共
起条件を満足する整依存木となる．DT$_x$とDT$_y$は，同値アークX,Yが異な
るだけなので，DT$_x$は新たな依存木ではない．よって，新たな依存木DT$_x$
には少なくとも１つCM(Y,U$_i$)${\neq}$○ wrt DFなるU$_i$が存在する必要
がある．(B$_i$,U$_i$)${\in}$diff(X,Y)であるので補題が成立する．

}
\end{lemma}

{\mynoindent}補題\ref{lem:ArcsInNewTree}より，次のID付き依存木の増加条件が
成立する．

\begin{theorem}[ID付き依存木の増加条件]
\label{the:IDedDepTreeIncreaseCond}
DG,CMにおいて同値アークX,Yに対するアークペア(A,B)${\in}$diff(X,Y)とし
た時，YをXにマージして得られるDG',CM'において,\{X,A,B\}を含むID付き整
依存木NDTが存在する時，またこの時に限り，ID付き依存木は増加する．

\proof{

新規に生成される整依存木は必ず\{X,A,B\}を含むこと，\{X,A,B\}を含む整依
存木は必ず新規解であることを示せばよい．今，DG',CM'中の新たなID付き依
存木をNDTとすると，補題\ref{lem:ArcsInNewTree}より，少なくとも１つのアー
クペア(A$_i$,B$_i$)${\in}$diff(X,Y),A$_i{\in}$NDT,B$_i{\in}$NDTが存在
する．また，補題\ref{lem:ArcPairAndNewTree}より，X${\in}$NDTである．よっ
て，新規に生成される整依存木は必ず\{X,A,B\}を含む．また，
(A,B)${\in}$diff(X,Y)より\{X,A,B\}を含むID付き整依存木はDG,CM に存在し
ない．よって，\{X,A,B\}を含むID付き整依存木は必ず新規に生成される整依
存木である．

}
\end{theorem}

{\mynoindent}以下で解の増加条件を詳細化するため，ここでいくつかの関数や記法を導入
する．

\myhalfskip
\hspace{-5mm}
\fbox
{
 \begin{minipage}{13.7cm}

\begin{itemize}
\item[\myitemindent same\_position($U$,$V$)] ： アーク$U$,$V$の依存ノードの位置が等しい
\item[\myitemindent dts($S$) wrt $DG$,$CM$] ： $CM$の共起制約を満たし
ながら，アーク集合$S{\subset}DG$から得られるID付き整依存木の集合
\item[\myitemindent co($U$) wrt $DG$,$CM$] ： アーク$U$あるいは$U$と共起するアーク集合，\{$X$ ${\mid}$ $X$=$U$ または CM($X$,$U$)=○, $X{\in}DG$\}である．
\item[\myitemindent dts\_with\_arcs($A_1$,$A_2$,${\ldots}$,$A_n$) wrt $DG$,$CM$] :
$DG$,$CM$中の整依存木でアーク$A_1$,$A_2$,${\ldots}$,$A_n$を含む整依存木の集合，すなわち，
dts(co($A_1$)${\cup}{\cdots}{\cup}$co($A_n$)) wrt $DG$,$CM$である．
\end{itemize}
\myhalfskip
\end{minipage}
}
\myhalfskip

{\mynoindent}同値アークX,Yに対するdiff(X,Y)中のアークペア(A,B)に関する
ID 付き依存木の増加条件の判定は，定理\ref{the:IDedDepTreeIncreaseCond}
よりX,A,Bを含む整依存木がDG',CM'に存在するか探索することにより基本的に
実現できる．これをできるだけ効率的に行うため，X,A,Bに関して次の３つの
場合に分けて考える．

\begin{itemize}
\item[\myitemindent(RC1)]\ same\_position(A,B)またはsame\_position(X,A)またはsame\_position(X,B)が成立．
\item[\myitemindent(RC2)]\ CM(A,B)${\neq}$○である．
\item[\myitemindent(RC3)]\ (RC1)(RC2)以外の場合．
\end{itemize}

{\mynoindent}(RC1)が成立する場合は，整依存木の整被覆条件によりアークが
排他関係となりX,A,B全てを含む整依存木は存在しないと判定できる．(RC2)の
場合は，マージ後でもCM'(A,B)${\neq}$○であるためDG',CM'において
\{X,A,B\} を含む整依存木は存在しないと判定できる．(RC3)の場合は
\{X,A,B\}を含む整依存木が存在しない，すなわち，dts\_with\_arcs(X,A,B)
wrt DG',CM'$=$\{\}の判定を行えば良い．

\subsubsection{汎化依存木の増加条件}

既に述べたようにID付き依存木の増加条件は汎化依存木の増加条件の必要条件
である．このため，ID付き依存木の増加条件を満たす場合，すなわち，
dts\_with\_arcs(X,A,B) wrt DF'($=$New\_DTsとする) ${\neq}$\{\}の
場合に，NDT${\in}$New\_DTsに対して，NDTが汎化依存木の増加となっている
場合にのみ汎化依存木の増加が生じる．逆に言えば，NDTがDF'に存在した場合
でも，汎化依存木?NDTがDFに存在していれば，汎化依存木の増加は起こらない．
これより，ID付き依存木が増加する場合における同値アークのマージ条件は次
のようになる．

\mygapskip
{\mynoindent}「同値アークX,Yのマージ前後の依存森DF,DF'に対して，新規に増
加するDF'中のID付き依存木DT$_{new}$に対して，?DT$_{new}$=?DTなるID付き
整依存木DTがDFに存在する」
\mygapskip


\subsubsection{依存森の縮退アルゴリズム}

\begin{figure}[bt]
 \begin{center}
  \epsfile{file=\myfigdir/DF依存森縮退アルゴリズム.eps,scale=0.7}
 \end{center}
\caption{依存森の縮退アルゴリズム}
\label{fig:DFReductionAlgorithm}
\end{figure}

前節の依存森の縮退条件,すなわち同値アークのマージ条件に基づき依存森の
縮退を行うアルゴリズムを図\ref{fig:DFReductionAlgorithm}に示す．アルゴ
リズムでは，共起マトリックスを集合として表現している．アークX,Yに
対して，$<$X,Y$>{\in}$CMであれば共起関係が成立している．以下，アルゴリズ
ムの動作を縮退条件に照らし合わせて図\ref{fig:DFReductionAlgorithm}を参
照しながら説明する．

図\ref{fig:DFReductionAlgorithm}(a)で依存グラフ中にある同値アークペア
X,Yを順次取り出し，diff(X,Y)中のアークペア(A,B)について，許諾を行った
場合に解(汎化依存木) の増加が起こるかを(b)-(h)でチェックする．全アーク
ペアに対して汎化依存木の増加が起こらない場合に(i)で依存森の縮退が行な
われる．

(A,B)の許諾の可否は，ID付き依存木の増加条件の確認の後に汎化依存木の増
加条件の確認を行うことで判定される．(b)では，
\ref{subsec:IDDTZoukaJuoken}節の(RC1),(RC2)の条件がチェックされ，いず
れかを満たす場合は解の増加がないため，次のアークペアの確認に進む．そう
でない場合は，ID付き依存木の増加条件の確認に進む．(c)では，Y をXにマージ
したDG',CM'を生成する．新規依存木の存在チェックは，基本的に依存森に対
する解の探索により行うため，できるだけ探索空間を少なくすることで効率化
が図れる．定理\ref{the:IDedDepTreeIncreaseCond}より新規のID 付き依存木
はX,A,Bを含むので，(d)ではco(X)${\cap}$co(A)${\cap}$co(B)によりX,A,B全
てと共起するアーク以外を除いたアーク集合DG\_XABを計算し，(e)で
search\_dtによりDG\_XABに対して依存木を探索する．依存木が得られなけれ
ば，このアークペアは同値アークのマージ条件を満たすので，次のアークペア
の処理に進む．依存木DTが得られた場合，DTはX,A,Bを含む新規のID付き依存
木である．(f)のnew\_generalized\_dt(DT,CM,DG)は，CM,DG中にDTの同値依存
木が存在するかを探索することで，DTが汎化依存木として新規かをチェックす
る．詳細な説明は省略するが，(q)においてDTの同値アークのみにアーク集合
を限定することで汎化依存木の探索を実現している．DTが汎化依存木として新
規の場合は，X,Yのマージはできないため(g),(h)で同値アークX,Yに対する処
理を終了し次の同値アークペアのマージにトライする．汎化依存木として解が
存在しない場合には，(i)においてX,Yのマージ，すなわち，依存森の縮退が行
われる．なお，(f)においてDTが汎化依存木として新規でない場合は，(e) に
おいてDG\_XABに対して別の解の探索が行われる．search\_dtは，入力位置P 
に関して深さ優先に共起条件を満足する解を探索するアルゴリズムである．
(k)においてDG中の位置Pのノードを依存ノードとして持つアーク集合
arcs\_at(DG,P)から１つアークを選択するが，(m) において，P+1以降で解が
見つからなければ(k)で別のアークを選択することで，全解を探索する．

\subsubsection{依存森縮退アルゴリズムの動作例}

\begin{figure}[b]
 \begin{center}
  \epsfile{file=\myfigdir/DF_SynGrp不具合例に対する依存森処理.eps,scale=0.7}
 \end{center}
\myfiglabelskip
\caption{例文に対する初期依存森と縮退処理}
\label{fig:IDFandRDFexample}
\end{figure}

最終的に縮退依存森に同値アークが残る例として付録１の``Tokyo taxi driver
call center''に対するアルゴリズムの動作を示す．例文に対する初期依存森
を図\ref{fig:IDFandRDFexample}(a)に示す．初期依存森には
(1,2),(5,7),(13,15),(25,26,27)の４種の同値アークが存在し，図のマトリッ
クスでは2重線で括られたまとまりとして示されている．

図\ref{fig:DFReductionAlgorithm}のアルゴリズムに従って縮退処理が行なわ
れる．最初の同値アークequiv(1,2)に対し$X$=1,$Y$=2となり，diff($X$,$Y$) 
は，uniq($X$,$Y$)=\{5,24,25\},uniq($Y$,$X$)=\{14,15,27\}の組合せ
\{(5,14),(5,15),(5,27),$\ldots$\}となる．最初のアークペア(5,14)は，
same\_position(5,14)であるため図\ref{fig:DFReductionAlgorithm}(b)にお
いて(RC1)の条件判定でスキップされ，次のアークペア(5,15)が選択される．
(5,15)の場合は，(b)の条件に確定しないため，(c)においてCM',DG'が生成さ
れる．CM'= CM + \{$<$1,14$>$,$<$1,15$>$,$<$1,27$>$\}であり，図
\ref{fig:IDFandRDFexample}(b)に示す．次に図
\ref{fig:DFReductionAlgorithm}(d)において$DG\_XAB$が計算される．
$X=$1,$A=$5,$B=$15であり，$DG\_XAB=$co(1)${\cap}$co(5)${\cap}$co(15)
wrt DG',CM'=\{1,28\}となる．(e)のsearch\_dtによる$DG\_XAB$に対する解探
索は失敗するため，(5,15)の許諾は新規の依存木を生成しない．さらにアーク
ペア(5,27)のチェックへと処理が進む．以上のようにしてdiff(1,2)の全ての
アークペアに関してチェックが行われるが，いずれもが新規解を生成すること
なく終了し，(i) において依存森の縮退が行われ，CM'DG'が新規のCM,DGに設
定される．

図\ref{fig:IDFandRDFexample}(c)は，最終的に得られる縮退依存森であり，
同値アーク25,26,27を持つ．この依存森に対する縮退アルゴリズムの動作を示
す．今,$X=$25,$Y=$26の時，uniq($X$,$Y$)$=$\{1,24\},
uniq($Y$,$X$)$=$\{6,13\},
diff($X$,$Y$)$=$\{(1,6),(1,13),(24,6),(24,23)\} である．アークペア
(1,6)は(RC1)の条件を満たす．アークペア(1,13)は，(RC1),(RC2)を満足せず，
図\ref{fig:DFReductionAlgorithm}(d)において$DG\_XAB$が計算される．
$X=25$,$A=1$,$B=13$であり，$DG\_XAB=$co(25)${\cap}$co(1)${\cap}$co(13)
wrt DG',CM'=\{25,1,13,5,28\} となる．$DG\_XAB$に対して(e)のsearch\_dt
を実行すると\{25,1,13,5,28\}が新規のID付き依存木として検索される
\footnote{実際，この木は図\ref{fig:SynGraphBadExample}(d)に相当する．}．
次に(f)においてnew\_generalized\_dtが実行され，(q)でadd\_equiv\_arcsに
よりDT中の各アークに対する同値アークが追加されたアーク集合$DG\_X$が計
算される．図\ref{fig:IDFandRDFexample}(c)では，25が同値アーク26,27を持
つので，これらが追加され，$DG\_X=$\{25,26,27,1,13,5,28\}となる．図
\ref{fig:DFReductionAlgorithm}(r)のsearch\_dtでは，解が計算されるが，
同値アーク25,26,27のそれぞれに対して$<$25,13$>$,$<$26,1$>$,$<$27,5$>$ 
がCMにおいて共起条件を満足しないためsearch\_dtはfalseとなる．この結果，
(f)のnew\_generalized\_dtがtrue,すなわち汎化依存木として解の増加となる
ため，$X$=25,$Y$=26のマージは行われない．図
\ref{fig:IDFandRDFexample}(c) の依存森は，付録１の図
\ref{fig:SynGraphBadExample}の(a)〜(c)の３つの依存構造のみを保持してお
り，健全性が保たれている．


縮退処理により生成される依存森は一意に決まるという訳ではなく，マージを試
みる同値アークの順番により異なった結果が得られたりする．例えば，上記の
例でも，同じ３つの汎化依存木を含む複数の縮退依存森が存在する．図
\ref{fig:DFReductionAlgorithm}のアルゴリズムは最小の縮退依存森を得ると
いう保証はなく，実際図\ref{fig:IDFandRDFexample}(c)よりサイズの小さい
依存森も存在する．また，縮退アルゴリズムの計算量に関しても改善の余地が
ある．最小の依存森の構成法やアルゴリズム効率化などについては今後の課題
とする\footnote{PDGでは文法規則で構成素列と依存構造のマッピングを規
定するため，任意の入力構成素列に対して任意の依存木を定義・追加すること
が可能である．このため汎用的な縮退アルゴリズムの高速化だけでなく，文法
規則の構造分析を行い新規解釈を生成しないアークを事前に計算するなどの最
適化手法が有効であると考えられる．}．

\subsection{統語森と依存森の対応関係}\label{sec:MappingBetweenPTAndDT}
依存森は，統語森との間で完全性と健全性が成立する．付録２に初期依存森の
完全性と健全性の証明を示す．縮退依存森は初期依存森と同じ(汎化)依存木の
集合を保持しているため，統語森と(縮退)依存森に完全性と健全性が成立する
と言える．統語森中の構文木（句構造）と依存森中の依存木（依存構造）の対
応関係は単純な1対1対応ではなく，1つの構文木が複数の依存木に対応したり，
複数の構文木が１つの依存木に対応したりする．言語表現の多様性（１つの意
味を複数の表現で表現可能）と曖昧性（１つの表現で複数の意味を表現可能）
を考えれば，こうした対応関係は自然な関係であると考えられる．構文木と依
存木の対応関係については，次章の評価実験において例文の解析結果とともに
述べる．

\section{例文解析評価実験}

PDGは依存森により整依存木集合を圧縮共有して表現することにより，各種の
曖昧性により生じる組合せ爆発を抑制することを狙いの１つとしており，本稿
では，PDGの構文解析から圧縮依存構造の構築までの方式を中心に述べている．
本章では，自然言語の各種の曖昧性を記述したPDG文法を用いて，典型的な曖
昧性例文の構文解析・依存森生成実験を行い，各種の曖昧性がどの様に処理さ
れるかについて述べると共に，統語森と依存森との対応関係やNon-projective 
な依存木の生成についても実例も用いながら述べる．なお，アルゴリズムの効
率も実用上重要なファクタであるが，本稿で示した構文解析アルゴリズム，統
語森・依存森構成アルゴリズム，依存森縮退アルゴリズムは，PDGの解析方式
の検証を行うことを主眼に実装をしており，実システムとしての実装では種々
の改善が考えられる．PDGの実装上の検討，テストコーパスなどを使った性能
評価などについては，今後の課題とする．なお，以下の実験では，Prolog上に
実装されたPDGの試作システムを利用している．

\begin{figure}[b]
 \begin{center}
  \epsfile{file=\myfigdir/DF例文を解析する文法規則.eps,scale=0.85}
 \end{center}
\myfiglabelskip
\caption{例文を解析する文法規則}
\label{fig:GrammarForExamples}
\end{figure}

\subsection{例文解析用文法}

図\ref{fig:GrammarForExamples}は，例文解析に使用した文法規則であり，代
表的な各種曖昧性構文を含んでいる．文法中の品詞
det,n,be,ving,v,adv,pre,relcは，それぞれ，冠詞，名詞，BE動詞，動詞の現
在分詞，動詞，副詞，前置詞，関係節を表している．また，図にはトップノードを導入するルート規則は明示されていないが，文全体(s)と名詞句(np)を解析結果として受理するルート規則を想定している．
この文法は例題分析実験用
のため，言語学的妥当性や厳密性は二義的である．文法には次のような構
文的曖昧性が記述されている．

\begin{itemize}
\item[{\myitemindent}前置詞句付加の曖昧性(PP-attachment)] ：R6(名詞
修飾)とR10,R17(動詞修飾)の2種類がある
\item[{\myitemindent}接続詞スコープ曖昧性(Coordination)] ：R11(〜 and
〜),R12(〜 or 〜)の名詞句並列を表す規則が存在する
\item[{\myitemindent}BE動詞構文解釈の曖昧性] ：be動詞に対して
R15(現在進行形の構文)とR16(copulaの構文)の構文解釈曖昧性規則が存在
する
\item[{\myitemindent}現在分詞形の曖昧性] ：動詞の現在分詞形に関しては様々な解釈
が可能であり，次のような用法が記述されている
\begin{itemize}
\item[(a)] 名詞が現在分詞の主格を占める形容詞的用法(R7)
\item[(b)] 名詞が現在分詞の目的格を占める形容詞的用法(R8)
\item[(c)] 名詞句が動詞の目的格となる動名詞句(R9,R10)
\end{itemize}
\end{itemize}

R8とR9は動詞と名詞の修飾関係としては類似しているが，どちらが主辞(句ヘッ
ド)であるかという依存構造の観点からは異なった構造である．また，平叙文
(R1)と命令文(R2)のパタンもあり，``Time flies like an arrow''のような多
品詞の曖昧性と組み合わさって種々の構文解釈を生成する．また，(R19)は，
non-projectiveな依存木，すなわち，交差する依存関係を含む依存木を生成する規則である．以下では，上記文法を用いて代表的な曖昧性例文等を解析した結果について述べる．

\subsection{典型的曖昧性例文の解析}
多品詞に起因する曖昧性の解析例については，既に例題として述べている．以
下では，自然言語の統語的な曖昧性の代表例として前置詞付加曖昧性，接
続詞スコープ曖昧性，構造解釈曖昧性の３つについて前記PDG文法での解析例
を示す．

\subsubsection{前置詞付加曖昧性(PP-attachment)}\label{sec:PP-attachment}

\begin{figure}[b]
\begin{center}
 \epsfile{file=\myfigdir/OS前置詞係り受け曖昧性例文の依存森JAPENG.eps,scale=0.6}
\end{center}
\myfiglabelskip
\caption{前置詞句付加曖昧性例文に対する依存森}
\label{fig:DFForISaw}
\end{figure}

図\ref{fig:DFForISaw}は，前置詞の付加(PP-attachment)曖昧性の例文``
I saw a girl with a telescope in the forest''に対する依存森である．依
存グラフのアークには，アーク名/アークIDと選好スコアが付与されている
\footnote{アーク選好スコアは依存関係の良さを表すスコアであり，本稿では
利用されない．}．各ノードの品詞や表層位置情報は依存グラフの下の対応表
に示している．この例では多品詞曖昧性を持つ語はないが，前置詞``with''に
2 つ($npp13$,$vpp14$)，``in''に3 つ($npp23$,$npp25$,$vpp26$)の依存先の
曖昧性が存在する．図に示すように，これらのアーク間には，共起マトリック
スで○が存在しない組合せ，すなわち共起制約がかかっているアークの組がい
くつか存在している．$npp13$ と$vpp14$，$npp23$と$npp25$と$vpp26$は，そ
れぞれ位置を同じくするアークであるため被覆制約の1種である単一役割制約
がかかっている．また，$vpp14$ と$npp25$ の間には非交差制約がかかってい
る．この共起制約がなければ，前置詞句付加曖昧性の組合せにより$2*3=6$個の解
が存在するが，CM(14,25)${\neq}$ ○によりNon-projectiveな依存木が排除さ
れ，この依存森は5つの整依存木（解釈）を含んでおり，例文に対して可能な
前置詞句付加曖昧性を適切に表現している．

例文に対して，統語森のサイズは25，初期依存森のサイズは18，縮退依存森の
サイズは13である．統語森は5つの解釈に対応する5つの構文木からなる集合
\footnote {ここでいう構文木の数は，始点，終点，規則ヘッド頂点，句ヘッ
ド，既存構成素列に関して弧の同一性を判定することで構文木の同一性を判定
した場合の数であり，部分依存構造(アーク集合)は同一性判定に含まれていな
い．}，初期依存森と縮退依存森は，5つのID付き依存木(5つの汎化依存木に対
応)の集合に対応している．初期依存森は，$obj5$,$npp13$,$vpp14$,$pre11$ 
に関してそれぞれ2本,1本,1本,1本の同値アークを有している．例えば，
$obj5$とその同値アークは，次に模式的に示す単一弧から生成されるが，これ
らは全て文法規則(R14)から生まれた弧である．

\myhalfskip

 $<$1, 4, vp/([saw]-v-1) $\rightarrow$ v(ID:109) np(ID:126) ・, \{arc(obj-5,[girl]-n-3,[saw]-v-1)\}$>$

 $<$1, 7, vp/([saw]-v-1) $\rightarrow$ v(ID:109) np(ID:163) ・, \{arc(obj-15,[girl]-n-3,[saw]-v-1)\}$>$

 $<$1,10, vp/([saw]-v-1) $\rightarrow$ v(ID:109) np(ID:203) ・, \{arc(obj-28,[girl]-n-3,[saw]-v-1)\}$>$

\myhalfskip
{\mynoindent}最初の弧は，被覆範囲が1〜4(``saw a girl''に対応)で，句ヘッ
ドが[saw]-v-1，圧縮弧v(ID:109)\footnote{規則ヘッド頂点(カテゴリ)がvで，弧
IDが109の圧縮弧である．}とnp(ID:126)を構成素としてもち，アークIDが5 で
関係名がobjのアークを有する．これら同値アークは弧の範囲がそれぞれ異なっ
た名詞句との結合により生成されている．これらは全て1つのアークにマージ
され，縮退依存森では同値アークは存在していない．

\begin{comment}
同値アーク[[(5),15,28],[(13),32],[(14),33],[(11),27]]
最終アーク 30, 4, 5,13,14,10,11,25,23,26,20,21,35

(obj-5)：
スコープが異なる：ノードの範囲とは無関係にマージ可能としている
（できる場合とできない場合の弁別を入れることが考えられる）
** new arcid: arc_share(obj-15,[girl]-n-3,[saw]-v-1)
 173:[1,7] vp/([saw]-v-1)--> [109 163]* : [[arc(obj-15,[girl]-n-3,[saw]-v-1)]]
** new arcid: arc_share(obj-5,[girl]-n-3,[saw]-v-1)
 135:[1,4] vp/([saw]-v-1)--> [109 126]* : [[arc(obj-5,[girl]-n-3,[saw]-v-1)]]
** new arcid: arc_share(obj-28,[girl]-n-3,[saw]-v-1)
 222:[1,10] vp/([saw]-v-1)--> [109 203]* : [[arc(obj-28,[girl]-n-3,[saw]-v-1)]]

163:[2,7] np/([girl]-n-3)--> [126 161]* : [[arc(npp-13,[with]-pre-4,[girl]-n-3)]]
126:[2,4] np/([girl]-n-3)--> [119 122]* : [[arc(det-4,[a]-det-2,[girl]-n-3)]]
203:[2,10] np/([girl]-n-3)--> [163 199]* : [[arc(npp-25,[in]-pre-7,[girl]-n-3)]]

--
npp-13の同値アーク：
163:[2,7] np/([girl]-n-3)--> [126 161]* : [[arc(npp-13,[with]-pre-4,[girl]-n-3)]]
228:[2,10] np/([girl]-n-3)--> [126 213]* : [[arc(npp-32,[with]-pre-4,[girl]-n-3)]]


====== Number of various trees ========
[Parse Forest]
(a) Parse Forest Size : 25
(b) Number of collection of parse trees : 5
(c) Number of set of parse trees : 5
[Dependency Forest]
(I-1) Initial DF size : 18
(I-2) Initial DF ID-tree collection number : 5
(I-3) Initial DF ID-tree set number : 5
(I-4) Initial DF Generalized-tree number : 5
(R-1) Reduced DF size : 13
(R-2) Reduced DF ID-tree collection number : 5
(R-3) Reduced DF ID-tree set number : 5
(R-4) Reduced DF Generalized-tree number : 5
\end{comment}

\begin{comment}

\end{comment}

\subsubsection{接続詞スコープの曖昧性}

\begin{figure}[tb]
\begin{center}
 \epsfile{file=\myfigdir/OS接続詞スコープ曖昧性例文の依存森JAPENG.eps,scale=0.66}
\end{center}
\caption{接続詞曖昧性例文に対する依存森}
\label{fig:DFForEarthAndMoon}
\end{figure}

図\ref{fig:DFForEarthAndMoon}は，接続詞のスコープ曖昧性を含む名詞句``
Earth and Moon or Jupitor and Ganymede''に対する依存森である．3つの接
続詞のスコープの組合せに対応して``Earth''に3つ，``Moon''に2つのアーク
の依存先の曖昧性が存在する．前節の例と同様，被覆制約だけ満足する場合には，
前置詞句スコープ曖昧性の組み合わせで6つの解釈が存在するが，$or22$と$and12$が非交
差制約に対応する共起マトリックスの制約を持っているため，1つの依存木が
排除され，この依存森は合計5つの整依存木を持っている．

例文に対して，統語森のサイズは18，初期依存森のサイズは17，縮退依存森の
サイズは10である．統語森は5つの解釈に対応する5つの構文木からなる集合，
初期依存森と縮退依存森は，5つのID付き依存木(5つの汎化依存木に対応)から
なる集合に対応している．初期依存森は，
$or22$,$or9$,$cnj6$,$and18$,$cnj14$は各々1本,1本,1本,2本,2本の同値アー
クを有している．これらは全て1つのアークにマージされ，縮退依存森では同
値アークは存在していない．接続詞スコープ曖昧性は，前置詞付加曖昧性
と類似しているが，後に述べる修飾スコープの問題を持つという点で言語現象
的には異なっている．

\begin{comment}

同値アーク [[(22),23],[(9),10],[(6),7],[(18),19,20],[(14),15,16]]
最終アーク 25,12, 4, 2,22, 9, 6,18,14,26
-----
dgarc(and-25,[earth]-n-0,[ganymede]-n-6)
dgarc(and-12,[earth]-n-0,[jupitor]-n-4)
dgarc(and-4,[earth]-n-0,[moon]-n-2)
dgarc(cnj-2,[and]-and-1,[earth]-n-0)
dgarc(or-22,[moon]-n-2,[ganymede]-n-6)
dgarc(or-9,[moon]-n-2,[jupitor]-n-4)
dgarc(cnj-6,[or]-or-3,[moon]-n-2)
dgarc(and-18,[jupitor]-n-4,[ganymede]-n-6)
dgarc(cnj-14,[and]-and-5,[jupitor]-n-4)
dgarc(root-26,[ganymede]-n-6,[root]-x-root)
×dgarc(or-23,[moon]-n-2,[ganymede]-n-6)
×dgarc(or-10,[moon]-n-2,[jupitor]-n-4)
×dgarc(cnj-7,[or]-or-3,[moon]-n-2)
×dgarc(and-19,[jupitor]-n-4,[ganymede]-n-6)
×dgarc(and-20,[jupitor]-n-4,[ganymede]-n-6)
×dgarc(cnj-15,[and]-and-5,[jupitor]-n-4)
×dgarc(cnj-16,[and]-and-5,[jupitor]-n-4)

====== Number of various trees ========
[Parse Forest]
(a) Parse Forest Size : 18
(b) Number of collection of parse trees : 5
(c) Number of set of parse trees : 5
[Dependency Forest]
(I-1) Initial DF size : 17
(I-2) Initial DF ID-tree collection number : 5
(I-3) Initial DF ID-tree set number : 5
(I-4) Initial DF Generalized-tree number : 5
(R-1) Reduced DF size : 10
(R-2) Reduced DF ID-tree collection number : 5
(R-3) Reduced DF ID-tree set number : 5
(R-4) Reduced DF Generalized-tree number : 5

\end{comment}

\subsubsection{構造解釈の曖昧性}\label{sec:AmbiguityInStructuralInterpertation}

図\ref{fig:DFForMyHobbyIs}は，構造解釈上の曖昧性を含む例文``My hobby
is watching birds with telescope''に対する依存森である．この例も，多品
詞曖昧性を持たないが，``be''動詞の解釈(コピュラか進行形か)，``watching
birds''の解釈($adjs3$,$adjo4$,$obj5$)，前置詞の付加曖昧性
($npp21$,$vpp22$,$npp24$,$vpp25$)等を持っており，「私の趣味は双眼鏡で
鳥を見ることです」，「私の趣味は，双眼鏡で鳥を見ています」，「私の趣味
は双眼鏡を持った見る鳥です」など10の解釈に対応する整依存木を含んでいる．

\begin{figure}[tb]
\begin{center}
 \epsfile{file=\myfigdir/OS構造解釈曖昧性例文の依存森JAPENG.eps,scale=0.66}
\end{center}
\myfiglabelskip
\caption{構造解釈曖昧性例文に対する依存森}
\label{fig:DFForMyHobbyIs}
\end{figure}

例文に対して，統語森のサイズは23，初期依存森のサイズは24，縮退依存森の
サイズは16である．統語森は10の解釈に対応する8つの構文木集合，初期依存
森と縮退依存森は，10のID付き依存木(10個の汎化依存木に対応)の集合に対応
している．初期依存森は，$dsc9$,$dsc8$,$obj5$,$npp21$,$vpp22$に関してそ
れぞれ2本,2本,5本,2本,2本の同値アークを有している．この例では，
\ref{sec:PP-attachment}節の例とは異なり，複数の規則から同値アークが生成さ
れている．例えば，$obj5$の同値アークは，(R9),(R10),(R15)などの文法規則
から得られる次に示すような弧に含まれている．


\myhalfskip
 (R9) ⇒ $<$3, 5, np/([watching]-ving-3) $\rightarrow$ ving(ID:121) np(ID:130)・,

{\myitemindent}\{arc(obj-5,[birds]-n-4,[watching]-ving-3)\}$>$

 (R10) ⇒ $<$3, 7, np/([watching]-ving-3) $\rightarrow$ ving(ID:121) np(ID:130) pp(ID:176)・,
 
{\myitemindent}\{arc(obj-6,[birds]-n-4,[watching]-ving-3),arc(vpp-22,[with]-pre-5,[watching]-ving-3)\} $>$

 (R15) ⇒ $<$2,5, vp/([watching]-ving-3) $\rightarrow$ be(ID:117) ving(ID:121) np(ID:130)・, 

{\myitemindent}\{arc(prg-2,[is]-be-2,[watching]-ving-3),arc(obj-7,[birds]-n-4,[watching]-ving-3)\} $>$
\myhalfskip
{\mynoindent}これら同値アークは全て1つのアークにマージされ，結果として
得られる縮退依存森では同値アークは存在していない．この例では，統語森が
8つの構文木を持つのに対して解釈(汎化依存木)の数は10となっており，1つの
構文木が複数の依存木に対応する例となっている．以下，構文木と依存木の対
応関係について述べる．

\begin{comment}
## 同じ依存片の組 [[(9),30],[(8),31],[(5),6,7,27,29],[(21),23],[(22),25]]
> CurrentSameArcIDList: [[9],[8],[5],[21],[22]]
XM, 1,35,33, 2, 4, 3, 9, 8, 5,21,24,26,22,20,41,38

同値アークで違う規則からの期待
 (R9) np/V → ving/V,np/NP : [arc(obj,NP,V)] 	
(R10) np/V → ving/V,np/NP,pp/PP : [arc(obj,NP,V),arc(vpp,PP,V)] 
--> objアーク
dgarc(obj-5,[birds]-n-4,[watching]-ving-3)
×dgarc(obj-6,[birds]-n-4,[watching]-ving-3)
×dgarc(obj-7,[birds]-n-4,[watching]-ving-3)
×dgarc(obj-27,[birds]-n-4,[watching]-ving-3)
×dgarc(obj-29,[birds]-n-4,[watching]-ving-3)

138:[3,5] np/([watching]-ving-3)--> [ving(121) np(130)]* : [[arc(obj-5,[birds]-n-4,[watching]-ving-3)]]
139:<3,5> np/([watching]-ving-3)--> [ving(121) np(130)]* pp/C/true: [[arc(obj-6,[birds]-n-4,[watching]-ving-3),arc(vpp-_89026,C,[watching]-ving-3)]]
140:[2,5] vp/([watching]-ving-3)--> [be(117) ving(121) np(130)]* : [[arc(prg-2,[is]-be-2,[watching]-ving-3),arc(obj-7,[birds]-n-4,[watching]-ving-3)]]

187:[3,7] np/([watching]-ving-3)--> [121 177]* : [[arc(obj-27,[birds]-n-4,[watching]-ving-3)]]
188:<3,7> np/([watching]-ving-3)--> [121 177]* pp/C/true: [[arc(obj-28,[birds]-n-4,[watching]-ving-3),arc(vpp-_106115,C,[watching]-ving-3)]]

--
117:[2,3] be/([is]-be-2)--> [lex([is]-be)]* : [[]]
121:[3,4] ving/([watching]-ving-3)--> [lex([watching]-ving)]* : [[]]
130:[4,5] np/([birds]-n-4)--> [n(128:birds)]* : [[]]
177:[4,7] np/([birds]-n-4)--> [np(130) pp(176)]* : [[arc(npp-21,[with]-pre-5,[birds]-n-4)]]

====== Number of various trees ========
[Parse Forest]
(a) Parse Forest Size : 23
(b) Number of collection of parse trees : 10
(c) Number of set of parse trees : 8
[Dependency Forest]
(I-1) Initial DF size : 24
(I-2) Initial DF ID-tree collection number : 10
(I-3) Initial DF ID-tree set number : 10
(I-4) Initial DF Generalized-tree number : 10
(R-1) Reduced DF size : 16
(R-2) Reduced DF ID-tree collection number : 10
(R-3) Reduced DF ID-tree set number : 10
(R-4) Reduced DF Generalized-tree number : 10

==========================
dgarc(det-1,[my]-det-0,[hobby]-n-1)
dgarc(sub-35,[hobby]-n-1,[is]-be-2)
dgarc(sub-33,[hobby]-n-1,[watching]-ving-3)
dgarc(prg-2,[is]-be-2,[watching]-ving-3)
dgarc(adjo-4,[watching]-ving-3,[birds]-n-4)
dgarc(adjs-3,[watching]-ving-3,[birds]-n-4)
dgarc(dsc-9,[watching]-ving-3,[is]-be-2)
dgarc(dsc-8,[birds]-n-4,[is]-be-2)
dgarc(obj-5,[birds]-n-4,[watching]-ving-3)
dgarc(npp-21,[with]-pre-5,[birds]-n-4)
dgarc(npp-24,[with]-pre-5,[watching]-ving-3)
dgarc(vpp-26,[with]-pre-5,[is]-be-2)
dgarc(vpp-22,[with]-pre-5,[watching]-ving-3)
dgarc(pre-20,[telescope]-n-6,[with]-pre-5)
dgarc(root-41,[is]-be-2,[root]-x-root)
dgarc(root-38,[watching]-ving-3,[root]-x-root)

====== Number of various trees ========
[Parse Forest]
(a) Parse Forest Size : 23
(b) Number of collection of parse trees : 10
(c) Number of set of parse trees : 8
[Dependency Forest]
(I-1) Initial DF size : 24
(I-2) Initial DF ID-tree collection number : 10
(I-3) Initial DF ID-tree set number : 10
(I-4) Initial DF Generalized-tree number : 10
(R-1) Reduced DF size : 16
(R-2) Reduced DF ID-tree collection number : 10
(R-3) Reduced DF ID-tree set number : 10
(R-4) Reduced DF Generalized-tree number : 10

\end{comment}

\subsection{構文木と依存木の１対多/多対１対応関係}

統語森中の構文木と依存森中の依存木の対応関係は保証されているが，1つの構
文木が複数の依存木に対応したり，複数の構文木が１つの依存木に対応したり
する．以下では実験文法を用いて具体例を示しながら，同一意味解釈に対する
構文構造と依存構造の表現力についても考察を加える．

\subsubsection{１構文木の複数依存木への対応}

\begin{figure}[b]
\begin{center}
 \epsfile{file=\myfigdir/DF_1構文木2依存木対応の例JAPENG.eps,scale=0.8}
\end{center}
\myfiglabelskip
\caption{1つの構文木が2つの依存木に対応する例}
\label{fig:MapFromOnePTToTwoDTs}
\end{figure}

1つの構文木が複数の依存木に対応するのは，１つの構文構造に対する解釈が
複数存在するような場合であり，例えば，``watching bird''という文に対し
て動詞の現在分詞形が名詞を修飾しているという１つの構文構造をアサインし
た時，依存構造としてwatching ${\xrightarrow[]{subj}}$ birdとwatching
${\xrightarrow[]{obj}}$ birdの２つを対応させるような場合である．すなわ
ち，同一の書き換え規則部を持つが異なった構造構築部を持つような規則が存
在する場合である．図\ref{fig:GrammarForExamples} の文法では，(R7),(R8)
がこれに対応する．(R7),(R8)は依存森の検証のため導入した恣意的な規則で
ある．同一の書き換え規則に対して複数の部分依存構造を与えるのは，構文
構造としては同一
\footnote{構成素列をどの文法カテゴリに分類するかという構造}であるが依
存関係としては異なっているような場合である．想定されるケースとしては，
機能的関係の多義と意味的関係の多義が存在する．機能的多義は，文法機能関
係(subject,objectなど)への曖昧性である．機能的関係は構文構造と密接な関
係にあること，また，機能的関係の違いがある場合には構文構造自体にそれを
反映する\footnote{例えば，書き換え規則の構文カテゴリを細分化し，異なっ
た書き換え規則にする．}などにより異なった構文構造とするなどの文法上の対
応も可能であることから，全く同一の書き換え規則に複数の機能的多義構造を
アサインすることは必ずしも一般的であるとは考えにくい．これに対して，意
味的関係の多義はきわめて一般的な現象であると言える．意味的な関係を構文
規則に融合すること
\footnote{これは構文解析に枝刈りのために制約知識を導入することではない．} 
は，組合せ爆発の問題やメンテナンス性の低下を招く恐れがある．このため，
構文解析と意味解析に独立性を持たせたアプローチが広く提唱・利用されてい
る．PDGでも意味的な曖昧性は語彙概念，概念間意味関係を表現する意味依存
グラフとして扱うことを想定している．但し，統語森と依存森のマッピングの
枠組み自体は，機能的・意味的多義という言語的分類の議論とは独立であり，
文法設計に応じて適宜利用すればよい．

\begin{figure}[b]
\begin{center}
 \epsfile{file=\myfigdir/DF_N構文木1依存木対応（見せかけ曖昧性）を含む依存森JAPENG.eps,scale=0.6}
\end{center}
\myfiglabelskip
\caption{N構文木1依存木対応（見せかけ曖昧性）を含む依存森}
\label{fig:DFContainingNtoOneMapping}
\end{figure}

\ref{sec:AmbiguityInStructuralInterpertation}節の例(図
\ref{fig:DFForMyHobbyIs})は，(R7),(R8)により2つの依存構造を生成する構
文木を含んでいる．このため，統語森数の構文木の数(8)は，依存森の汎化依
存木数(10)より少なくなっている．図\ref{fig:MapFromOnePTToTwoDTs}に実際
の構文木と依存木を示す．


\begin{comment}

  # Parse Tree [1] 
  s[0,7,is/be]:207
    +--np[0,2,hobby/n]:108
    |     +--det[0,1,my/det]:101
    |     +--n[1,2,hobby/n]:104
    +--vp[2,7,is/be]:182
          +--be[2,3,is/be]:117
          +--np[3,7,birds/n]:179
                +--np[3,5,birds/n]:132
                |     +----ving[3,4,watching/ving]:121
                |     +----n[4,5,birds/n]:128
                +--pp[5,7,with/pre]:176
                      +----pre[5,6,with/pre]:165
                      +----np[6,7,telescope/n]:170
                              +----n[6,7,telescope/n]:168

  #### Dependency Structure [1]
  [is/be,2]
    + <-(dsc-31)- [birds/n,4]
    |         + <-(adjs-3)- [watching/ving,3]
    |         + <-(npp-23)- [with/pre,5]
    |                   + <-(pre-20)- [telescope/n,6]
    + <-(sub-35)- [hobby/n,1]
              + <-(det-1)- [my/det,0]

  #### Dependency Structure [2]
  [is/be,2]
    + <-(dsc-31)- [birds/n,4]
    |         + <-(adjo-4)- [watching/ving,3]
    |         + <-(npp-23)- [with/pre,5]
    |                   + <-(pre-20)- [telescope/n,6]
    + <-(sub-35)- [hobby/n,1]
              + <-(det-1)- [my/det,0]

\end{comment}

\subsubsection{複数構文木の１依存木への対応}

\begin{figure}[t]
\begin{center}
 \epsfile{file=\myfigdir/DF_N構文木1依存木対応（見せかけ曖昧性）JAPENG.eps,scale=0.75}
\end{center}
\myfiglabelskip
\caption{N構文木1依存木対応（見せかけ曖昧性）の例}
\label{fig:SuriousNtoOneMapping}
\end{figure}

複数の構文構造が１つの依存構造に対応するような現象の例としては，例えば
見せかけの曖昧性が挙げられる\cite{Noro02}．構文構造とそれの表す意味と
の関係において，構文構造の違いが意味的な違いに対応する真の曖昧性と，構
文構造は異なるが意味に違いがない構造，または，文法が不十分なために言語
学的に誤った構造などの見せかけの曖昧性が存在し，特にコーパスからの文法
学習での対応が重要となっている\cite{Noro05}．また，文脈自由文法ではな
いが，CCG(Conbinatory Categorial Grammar)においては，多数のspurious
ambiguityが存在するという類似の問題があり，標準形の木のみをただ１つ解
析結果として出力する手法が提案されている\cite{Eisner96b}．この手法では，
解析木の末端のカテゴリ(CCGのカテゴリ)が同一である木は同じ意味構造を有
するという定義の基で，同じ意味を表す木（同じ意味クラスの木）はただ1つ
だけ取り出すことができる．PDGの枠組みでは，文の解釈は(汎化)依存木で表
現するため，同一の(汎化)依存木を持つ構文木を同じクラスの木とするという
関係になっていると見ることができる．

図\ref{fig:DFContainingNtoOneMapping}は，``She curiously saw a cat in
the forest''を例文文法で解析して得られる依存森であり，見せかけの曖昧性
を含んでいる．共起制約が掛かっているのは依存先曖昧性に対応する
$npp17$,$vpp18$に対する単一役割制約のみであり，``in the forest'' の依存
先が異なる2つの依存木(解釈)が存在している．統語森は3つの構文木，初期依
存森は3つのID付き依存木(2つの汎化依存木)，縮退依存森は2つのID付き依存
木(2つの汎化依存木) を含んでいる．見せかけの曖昧性は，動詞句に対する２
つの修飾句に関する規則(R17),(R18)の適用順序の違いにより生じている．図
\ref{fig:SuriousNtoOneMapping}に構文木と依存木を示す．

\begin{comment}
====== Number of various trees ========
[Parse Forest]
(a) Parse Forest Size : 19
(b) Number of collection of parse trees : 3
(c) Number of set of parse trees : 3
[Dependency Forest]
(I-1) Initial DF size : 12
(I-2) Initial DF ID-tree collection number : 3
(I-3) Initial DF ID-tree set number : 3
(I-4) Initial DF Generalized-tree number : 2
(R-1) Reduced DF size : 9
(R-2) Reduced DF ID-tree collection number : 2
(R-3) Reduced DF ID-tree set number : 2
(R-4) Reduced DF Generalized-tree number : 2
\end{comment}

\begin{figure}[b]
\begin{center}
 \epsfile{file=\myfigdir/DF_N構文木1依存木対応（真の曖昧性）を含む依存森JAPENG.eps,scale=0.5}
\end{center}
\myfiglabelskip
\caption{N構文木1依存木対応（真の曖昧性）を含む依存森}
\label{fig:DFContainingNtoOneMappingRealAmbiguity}
\end{figure}

言語解釈の意味的な違いについては，微妙な意味の違い\cite{Eisner96b}
\footnote{``softly knock twice''の解釈候補softly(twice(knock))と
twice(softly(knock))は意味的に等しいが，``intentionally knock twice'' 
の解釈候補``intentionally(twice(knock))''と
``twice(intentionally(knock))''は意味が異なる．}や限量詞や数の解釈に関
わる曖昧性\footnote{「3人が10本の花を買った」において，「各人が10本の
花を買った」か「3人全員で10本の花を買った」のようなモデル理論的な意味
解釈の曖昧性であり，句構造や依存構造では表現が困難．}なども考慮する必
要があり，依存構造の同一性で意味の同一性を判定することはあくまで１つの
側面に関する同一性の判定に過ぎない．\cite{Meluk88}は，依存構造での自然
な構造表現が困難なケースを挙げ，それらには句構造では自然に表現できるも
の，句構造でも自然に表現できないもの(句構造，依存構造の両方とも能力不
足)があることを示している．PDGは，句構造と依存構造を扱うため，少なくと
も前者については枠組みとしての検証が必要と考える．前者は，依存構造にお
いて句のヘッドワードに修飾語が存在する場合にそれがヘッドワードのみを修
飾するのか，それともヘッドワード以下の全体を修飾するのかというスコープ
の曖昧性を表現できないという，標準的な依存構造一般に存在する問題（ここ
では{\bf 修飾スコープ問題}と呼ぶ）である．

図\ref{fig:DFContainingNtoOneMappingRealAmbiguity}に``Earth and
Jupiter in Solar System''に対する依存森を示す．この文には，前置詞句が
並列句のヘッド``Jupitor''のみを修飾する解釈と``Earth and Jupitor''全体
を修飾する解釈の2つが存在する．統語森には2つの解釈に対応する2つの構文
木が存在し，初期依存森には2つのID付き依存木(1つの汎化依存木)が存在し，
縮退依存森には1つのID付き依存木(1つの汎化依存木)が存在する．2つの構文
木と1つの依存木の対応を図\ref{fig:RealNtoOneMapping}に示す．

\begin{figure}[b]
\begin{center}
 \epsfile{file=\myfigdir/DF_N構文木1依存木対応（真の曖昧性）JAPENG.eps,scale=0.7}
\end{center}
\myfiglabelskip
\caption{N構文木1依存木対応（真の曖昧性）の例}
\label{fig:RealNtoOneMapping}
\end{figure}

修飾スコープ問題への対応方法として\cite{Meluk88}は，Groupingという概念
を導入している．Groupingは論理的にフレーズと同じでカバーする単語の範囲
を示すものである．ただし，Groupingは，全てに記述されるものではなく，対
象は曖昧性が生じる並列構造(conjoined structure)，``not'',``only''と言っ
たオペレータ語(operator word)などに限定されている．依存構造をベースに
した大規模文法を有する機械翻訳システム\cite{Amano89}では，Grouping 
に相当する仕組み\footnote{スコープノードという特殊ノードの導入により依
存構造の範囲を必要に応じて記述可能としている．}を導入している．工学的観
点から言うと，一般にどの程度詳細に深いレベルの解釈構造を作るかという設
定は，目的とするアプリケーションにより異なる．機械翻訳アプリケーション
においては，修飾スコープ問題については並列構造に対する対応だけで実シス
テムが構築されており\footnote{これは英日システムの例である．より詳細に
は言語対によっても要求レベルは異なってくると考えられる．例えば，英語と
フランス語といった同族言語の場合は構文的曖昧性を保持したまま目的言語へ
変換するという戦略を取ることにより修飾スコープ問題を回避できる可能性が
ある．}，前記Grouping対象の限定は経験的に妥当であると考えている．また，
修飾スコープ問題は，言語によって様相が異なってくる．例えば，ロシア語で
は形容詞の数，名詞の文法的格が一致(agreement)や支配(government) により
統語的に導入され，解釈が決定されるために修飾スコープ問題が起こらないこ
とがある\cite{Meluk88}．また，日本語では，係り受け文法(依存構造文法)に
被修飾語は修飾語の左に位置するという制約が存在するため，そもそも修飾ス
コープ問題が発生せず，依存構造(係り受け構造)の表現力の問題として意識さ
れることがほとんどない．PDGでは同値アークがノードのスコープの違いを表
現しているので，依存構造の修飾スコープ問題は，Groupingの概念を同値アー
クに導入するという拡張により対応できる可能性があり，今後の検討課題であ
る．

\begin{comment}
====== Number of various trees ========
[Parse Forest]
(a) Number of collection of parse trees : 2
(b) Number of set of parse trees : 2
[Dependency Forest]
(I-1) Initial DF size : 7
(I-2) Initial DF ID-tree collection number : 2
(I-3) Initial DF ID-tree set number : 2
(I-4) Initial DF Generalized-tree number : 1
(R-1) Reduced DF size : 5
(R-2) Reduced DF ID-tree collection number : 1
(R-3) Reduced DF ID-tree set number : 1
(R-4) Reduced DF Generalized-tree number : 1
------
\end{comment}

\begin{comment}

依存構造での表現力の問題

D-language単独で表現が困難な構造がある．
節のヘッドワードを修飾している要素Ｘがある構造と，Ｘが句全体を修飾している
構造との意味的な対比．

his cheerfulness and his accent astonishing
 (1a) his cheerfulness and {his accent astonishing}
 (1b) {his cheerfulness and his accent} astonishing

この例は単純にスコープの問題で句構造では，表現されている．(平川)

Bob and Dick's novels
 (2a) novels written by the team ``Bob + Dick''
     {Bob and Dick}'s novels
 (2b) novels written by Bob and novels written by Dick
     {Bob} and {Dick's novels} → スコープの問題として

この例は表現されていない要素の問題で単純にスコープの問題として扱うこと
は困難で，句構造なら表現できるというものでもない．

3つの方法
(a) ラベルに情報をつける → 良くない
     modif(ヘッドのみ) v.s. phrase-modif(句全体)
(b) (1b)(2b)を省略の問題であるとしてとらえ全体構造で表現
  (1b') {his cheerfulness astonishing} and {his accent astonishing}
  (2b') {Bob's novels} and {Dick's novels}
(c) ノード属性の属性マーカを付けて弁別(注：次は正確でない．本と違う)

　　ロシア語では，語のinflectionで数の情報が表現され，次の２文の構造が
　　弁別される．
    New York(MASC.SG,NOM) and Chicago(MASC.SG.NOM) University[masc](PK.NOM)
    (ニューヨークとシカゴの各１つの大学）
    New York(PL.NOM) and Chicago (PL.NOM) University[masc](PK.NOM)
    (ニューヨークとシカゴの各いくつかの大学）

-----
・句構造でも自然に表現できないもの(両方とも能力不足)とできるものがある
・表現できるものスコープの曖昧性
・MelukではGroupingという概念を導入している(Groupingは論理的にフレーズ
　と等しい) 
 （=スコープノードと同じ)
  Groupingは，全てに入れているのではなく，限定されている
   - conjoined structure (曖昧性の出る場合)
   - ``operator'' word (not, onlyなど)

   ・アプリケーションにも依存する(弁別の必要がないアプリケーションもある)
  　 大規模な英語文法では，conjoined structureのみにスコープノードで対
　　 応するだけで実用上ほぼ問題なく実現できている．

・このヘッドワード修飾か全体修飾かというスコープの問題は対象言語によっ
　て異なる．
　ロシア語では形容詞の数，名詞の文法的格がsyntacticallyに導入されてい
  る(by agreement and government)
  日本語では発生しない(係り受け文法の制約の存在）

 今後の課題．

\end{comment}

\subsection{Non-projective依存木の生成}

\begin{figure}[b]
 \begin{center}
  \epsfile{file=\myfigdir/DF_Non-projective依存木の生成例.eps,scale=0.55}
 \end{center}
\myfiglabelskip
\caption{Non-projectiveな依存木の生成例}
\label{fig:Non-projectiveDT}
\end{figure}

非交差制約(Projectivity constraint)\footnote{Projectivityの条件は，
「依存関係が交差しない」ことの他に「トップノードがカバーされることはな
い」の２つであるが，文頭(または文末)に特殊なルートノードを想定すること
により，この２番目の条件は不必要となる．日本語はトップノードが文末に位
置するためProjectivityのためにはルートノードは必要としない．} は，多く
の依存構造解析システムにより受け入れられている制約であり，これらシステ
ムはProjective parserと呼ばれる．Projective parserはnon-projectiveな構
造を持つ文の解析に失敗する．種々の言語の大半の文はprojectiveであるが，
いくつかのタイプのnon-projectiveな文が多くの言語に存在する
\cite{Meluk88}．英語では，``She saw the cat curiously which was
Percian''，日本語では「私は本を東京に買いに昨日行きました」などが
non-projectiveな構造を持つ文である．英語に比べて自由度の高い語順を持つ
チェコ語の解析において，Non-projective parserがprojective parserに対し
て総合的な精度で上回るという報告もある\cite{McDonald05}．しかしながら，
単純にNon-projectiveな解釈を許すだけでは，全体として性能の劣化に繋がる
恐れもあり多くのシステムでは対象をprojectiveな依存木に限定していると思
われる．

PDGでは，\ref{sec:bunpoukisoku}節で述べたように，構成素列(規則ボディ) 
とアーク集合(部分依存構造)のマッピングが拡張CFG規則で定義される．この
記述の枠組みにより，All or nothingではなく，規則により定義された
non-projectiveな構造のみをWell-formedな構造として共起マトリックスの共
起制約として表現することが可能である．これをコントロールされた
non-projectivityと呼ぶこととする．図\ref{fig:GrammarForExamples}の
(R19) はNon-projectiveな構文に対する文法規則であり，関係節の前に副詞が
挿入された構文に対応している．図\ref{fig:Non-projectiveDT}に``She saw
the cat curiously which was Percian''に対して例文文法が生成する依存森
を示す．依存森には，non-projectiveな整依存木が１つ存在している．


\section{おわりに}

本稿では，PDGの基本モデルである多レベル圧縮共有データ結合モデルとPDG 
の概要について述べるとともに，特にPDGにおける圧縮共有データ構造である
統語森と依存森について述べた．また，統語森と依存森の間には，完全性と健
全性が成立することを示した．圧縮共有された句構造解釈（統語森）を圧縮共
有された依存構造（依存森）に対応関係を持って変換でき，それぞれのレベル
での言語知識の適応が可能である点が最大の特徴である．また，自然言語の曖
昧性例文に対してPDGの文法と試作システムを用いて解析実験を行い，各種曖
昧性が依存森により圧縮共有表現できることを示し，さらに，PDGでは
Non-projectiveな構造を必要に応じて規則導入できることを示した．

現状のPDGの実装は，方式のフィージビリティスタディを想定したものであり，
文法記述の拡張(属性条件記述，任意構成素指定の導入など），解析アルゴリ
ズム縮退アルゴリズムの効率化(文法解析による事前最適化，実装上の効率化）
などを進める予定である．また，PDGの最適解探索の方式(グラフ分枝アルゴリ
ズム) や評価方式については一部報告しているが，各種選好知識と組み合わせ
たPDG 全体としての評価などについて報告してゆく予定である．

\acknowledgment
本研究を進めるにあたって依存森の完全性・健全性の証明に関して有意義なコ
メントをいただいたつくば大学数学科坂井公助教授に感謝いたします．
\begin{comment}
また，様々なコメントをいただいた査読者の方々に感謝いたします．
\end{comment}

\newpage



\bibliographystyle{jnlpbbl} 
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Amano, Hirakawa, Nogami, \BBA\ Kumano}{Amano
  et~al.}{1989}]{Amano89}
Amano, S., Hirakawa, H., Nogami, H., \BBA\ Kumano, A. \BBOP 1989\BBCP.
\newblock \BBOQ The Toshiba Machine Translation System\BBCQ\
\newblock {\Bem Future Computing Systems}, {\Bbf 2}  (3).

\bibitem[\protect\BCAY{Bikel}{Bikel}{2004}]{Bikel04}
Bikel, D.~M. \BBOP 2004\BBCP.
\newblock \BBOQ Intricacies of Collins' Parsing Model\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 30}  (4), \mbox{\BPGS\
  479--511}.

\bibitem[\protect\BCAY{Carroll \BBA\ Charniak}{Carroll \BBA\
  Charniak}{1992}]{Carroll92}
Carroll, G.\BBACOMMA\ \BBA\ Charniak, E. \BBOP 1992\BBCP.
\newblock \BBOQ Two Experiments on Learning Probablistic Dependency Grammars
  form Corpora\BBCQ\
\newblock Technical report, Department of Computer Science, Brown university.

\bibitem[\protect\BCAY{Charniak}{Charniak}{2000}]{Charniak00}
Charniak, E. \BBOP 2000\BBCP.
\newblock \BBOQ A maximum-entropy-inspired parser\BBCQ\
\newblock In {\Bem Proceedings of the 1st Conference of the North American
  Chapter of the Association for Computational Linguistics}, \mbox{\BPGS\
  132--139}.

\bibitem[\protect\BCAY{Clark \BBA\ Curran}{Clark \BBA\ Curran}{2003}]{Clark03}
Clark, S.\BBACOMMA\ \BBA\ Curran, J.~R. \BBOP 2003\BBCP.
\newblock \BBOQ Log-Linear Models for Wide-Coverage CCG Parsing\BBCQ\
\newblock In {\Bem Proceedings of the SIGDAT Conference on Empirical Methods in
  Natural Language Processing (EMNLP '03)}, \mbox{\BPGS\ 97--104}.

\bibitem[\protect\BCAY{Collins}{Collins}{1999}]{Collins99}
Collins, M. \BBOP 1999\BBCP.
\newblock {\Bem Head-Driven Statistical Models for Natural Language Parsing}.
\newblock Ph.D.\ thesis, University of Pennsylvania.

\bibitem[\protect\BCAY{Eisner}{Eisner}{1996}]{Eisner96b}
Eisner, J. \BBOP 1996\BBCP.
\newblock \BBOQ Efficient Normal Form Parsing for Combinatory Categorial
  Grammar\BBCQ\
\newblock In {\Bem Proceedings of the 34th Annual Meeting of the ACL},
  \mbox{\BPGS\ 79--86}.

\bibitem[\protect\BCAY{Harper, Hockema, \BBA\ White}{Harper
  et~al.}{1999}]{Harper99}
Harper, M.~P., Hockema, S.~A., \BBA\ White, C.~M. \BBOP 1999\BBCP.
\newblock \BBOQ Enhanced constraint dependency grammar parsers\BBCQ\
\newblock In {\Bem Proceedings of the IASTED International Conference on
  Articial Intelligence and Soft Computing}.

\bibitem[\protect\BCAY{Hirakawa}{Hirakawa}{2001}]{Hirakawa01}
Hirakawa, H. \BBOP 2001\BBCP.
\newblock \BBOQ Semantic Dependency Analysis Method for Japanese Based on
  Optimum Tree Search Algorithm\BBCQ\
\newblock In {\Bem Proceedings of the PACLING2001}, \mbox{\BPGS\ 117--126}.

\bibitem[\protect\BCAY{Hirakawa}{Hirakawa}{2005}]{Hirakawa05d_j}
Hirakawa, H. \BBOP 2005\BBCP.
\newblock \BBOQ Graph Branch Algorithm: An Optimum Tree Search Method for
  Scored Dependency Graph with Arc Co-occurrence Constraints\BBCQ\
\newblock \Jem{情報処理学会,自然言語処理研究会 NL-169-16}, \mbox{\BPGS\
  101--108}.

\bibitem[\protect\BCAY{Kaplan}{Kaplan}{1989}]{Kaplan89}
Kaplan, R. \BBOP 1989\BBCP.
\newblock \BBOQ The Formal Architecture of Lexical-Functional Grammar\BBCQ\
\newblock {\Bem Journal of Information Science and Engineering}, {\Bbf 5},
  \mbox{\BPGS\ 305--322}.

\bibitem[\protect\BCAY{Lafferty, Sleator, \BBA\ Temperley}{Lafferty
  et~al.}{1992}]{Lafferty92}
Lafferty, J., Sleator, D., \BBA\ Temperley, D. \BBOP 1992\BBCP.
\newblock \BBOQ Grammatical Trigrams: a Probabilistic Model of Link
  Grammar\BBCQ\
\newblock In {\Bem Probabilistic Approaches to Natural Language}.

\bibitem[\protect\BCAY{Lee \BBA\ Choi}{Lee \BBA\ Choi}{1997}]{Lee97}
Lee, S.\BBACOMMA\ \BBA\ Choi, K.~S. \BBOP 1997\BBCP.
\newblock \BBOQ Reestimation and Best-First Parsing Algorithm for Probablistic
  Dependency Grammars\BBCQ\
\newblock In {\Bem Proceedings of the Fifth Workshop on Very Large Corpora},
  \mbox{\BPGS\ 41--55}.

\bibitem[\protect\BCAY{Maruyama}{Maruyama}{1990}]{Maruyama90}
Maruyama, H. \BBOP 1990\BBCP.
\newblock \BBOQ Constraint Dependency Grammar and Its Weak Generative
  Capacity\BBCQ\
\newblock {\Bem Computer Software}.

\bibitem[\protect\BCAY{Matsumoto, Tanaka, Hirakawa, Miyoshi, \BBA\
  Yasukawa}{Matsumoto et~al.}{1983}]{Matsumoto83}
Matsumoto, Y., Tanaka, H., Hirakawa, H., Miyoshi, H., \BBA\ Yasukawa, H. \BBOP
  1983\BBCP.
\newblock \BBOQ BUP: A Bottom-Up Parser Embedded in Prolog\BBCQ\
\newblock {\Bem New Generation Computing}, {\Bbf 1}  (2), \mbox{\BPGS\
  145--158}.

\bibitem[\protect\BCAY{McDonald, Crammer, \BBA\ Pereira}{McDonald
  et~al.}{2005}]{McDonald05}
McDonald, R., Crammer, K., \BBA\ Pereira, F. \BBOP 2005\BBCP.
\newblock \BBOQ Spanning Tree Methods for Discriminative Training of Dependency
  Parsers\BBCQ\
\newblock Technical report, UPenn CIS.

\bibitem[\protect\BCAY{Mel'uk}{Mel'uk}{1988}]{Meluk88}
Mel'uk, I.~A. \BBOP 1988\BBCP.
\newblock {\Bem Dependency Syntax: Theory and Practice}.
\newblock State University of New York Press, Albany, New York.

\bibitem[\protect\BCAY{Ozeki}{Ozeki}{1994}]{Ozeki94}
Ozeki, K. \BBOP 1994\BBCP.
\newblock \BBOQ Dependency Structure Analysis as Combinatorial
  Optimization\BBCQ\
\newblock {\Bem Information Sciences}, {\Bbf 78}  (1-2), \mbox{\BPGS\ 77--99}.

\bibitem[\protect\BCAY{Pereira \BBA\ Warren}{Pereira \BBA\
  Warren}{1980}]{Pereira80}
Pereira, F.\BBACOMMA\ \BBA\ Warren, D. \BBOP 1980\BBCP.
\newblock \BBOQ Definite clause grammars for language analysis - a survey of
  the formalism and a comparison with augmented transition networks\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bbf 13}  (3), \mbox{\BPGS\
  231--278}.

\bibitem[\protect\BCAY{Pollard \BBA\ Sag}{Pollard \BBA\ Sag}{1994}]{Pollard94}
Pollard, C.\BBACOMMA\ \BBA\ Sag, I.~A. \BBOP 1994\BBCP.
\newblock {\Bem Head-Driven Phrase Structure Grammar}.
\newblock University of Chicago Press, Chicago.

\bibitem[\protect\BCAY{Riezler, King, Kaplan, Crouch, Maxwell~III, \BBA\
  Johnson}{Riezler et~al.}{2002}]{Riezler02}
Riezler, S., King, T.~H., Kaplan, R.~M., Crouch, R., Maxwell~III, J.~T., \BBA\
  Johnson, M. \BBOP 2002\BBCP.
\newblock \BBOQ Parsing the Wall Street Journal using a Lexical-Functional
  Grammar and Discriminative Estimation Techniques\BBCQ\
\newblock In {\Bem Proceedings of the 40th Annual Meeting of the ACL (ACL-02)},
  \mbox{\BPGS\ 271--278}.

\bibitem[\protect\BCAY{Rim, Seo, \BBA\ Simmons}{Rim et~al.}{1990}]{Rim90}
Rim, H.~C., Seo, J., \BBA\ Simmons, R.~F. \BBOP 1990\BBCP.
\newblock \BBOQ Transforming Syntactic Graphs into Semantic Graphs\BBCQ\
\newblock Technical report, Artificial Intelligence Lab, Texas at Austin.

\bibitem[\protect\BCAY{Schiehlen}{Schiehlen}{1996}]{Schiehlen96}
Schiehlen, M. \BBOP 1996\BBCP.
\newblock \BBOQ Semantic Construction from Parse Forests\BBCQ\
\newblock In {\Bem Computational Linguistics (COLING'96)}.

\bibitem[\protect\BCAY{Seo \BBA\ Simmons}{Seo \BBA\ Simmons}{1989}]{Seo89}
Seo, J.\BBACOMMA\ \BBA\ Simmons, R.~F. \BBOP 1989\BBCP.
\newblock \BBOQ A Syntactic Graphs: A Representation for the Union of All
  Ambiguous Parse Trees\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 15}.

\bibitem[\protect\BCAY{Shudo, Narahara, \BBA\ Yoshida}{Shudo
  et~al.}{1980}]{Shudo80}
Shudo, K., Narahara, T., \BBA\ Yoshida, S. \BBOP 1980\BBCP.
\newblock \BBOQ Morphological aspects of Japanese language processing\BBCQ\
\newblock In {\Bem Proceedings of COLING'80}.

\bibitem[\protect\BCAY{Sleator \BBA\ Temperley}{Sleator \BBA\
  Temperley}{1991}]{Sleator91}
Sleator, D.\BBACOMMA\ \BBA\ Temperley, D. \BBOP 1991\BBCP.
\newblock \BBOQ Parsing English with a Link Grammar\BBCQ\
\newblock Technical report, Department of Computer Science, Carnegie Mellon
  University.

\bibitem[\protect\BCAY{Steedman}{Steedman}{2000}]{Steedman00}
Steedman, M. \BBOP 2000\BBCP.
\newblock {\Bem The Syntactic Process}.
\newblock The MIT Press, Cambridge, MA.

\bibitem[\protect\BCAY{Tomita}{Tomita}{1987}]{Tomita87}
Tomita, M. \BBOP 1987\BBCP.
\newblock \BBOQ An efficient augmented-context-free parsing algorithm\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 13}  (1-2), \mbox{\BPGS\
  31--46}.

\bibitem[\protect\BCAY{Tsuruoka, Miyao, \BBA\ Tsujii}{Tsuruoka
  et~al.}{2004}]{Tsuruoka04}
Tsuruoka, Y., Miyao, Y., \BBA\ Tsujii, J. \BBOP 2004\BBCP.
\newblock \BBOQ Towards efficient probabilistic HPSG parsing: integrating
  semantic and syntactic preference to guide the parsing\BBCQ\
\newblock In {\Bem IJCNLP-04 Workshop: Beyond Shallow Analyses- Formalisms and
  Statistical Modeling for Deep Analyses}.

\bibitem[\protect\BCAY{Wang \BBA\ Harper}{Wang \BBA\ Harper}{2004}]{Wang04}
Wang, W.\BBACOMMA\ \BBA\ Harper, M.~P. \BBOP 2004\BBCP.
\newblock \BBOQ A Statistical Constraint Dependency Grammar (CDG) Parser\BBCQ\
\newblock In {\Bem Workshop on Incremental Parsing: Bringing Engineering and
  Cognition Together (ACL)}, \mbox{\BPGS\ 42--49}.

\bibitem[\protect\BCAY{Wilks}{Wilks}{1975}]{Wilks75}
Wilks, Y.~A. \BBOP 1975\BBCP.
\newblock \BBOQ An Intelligent Analyzer and Under-stander of English\BBCQ\
\newblock {\Bem Communications of the A.C.M.}, {\Bbf 18}, \mbox{\BPGS\
  264--274}.

\bibitem[\protect\BCAY{Winograd}{Winograd}{1983}]{Winograd83}
Winograd, T. \BBOP 1983\BBCP.
\newblock {\Bem Language as a Cognitive Process: Volume 1 Syntax}.
\newblock Addison-Wesley Publishing.

\bibitem[\protect\BCAY{工藤拓\JBA 松本裕治}{工藤拓\JBA
  松本裕治}{2005}]{Kudo05_j}
工藤拓\JBA 松本裕治 \BBOP 2005\BBCP.
\newblock \JBOQ 相対的な係りやすさを考慮した日本語係り受け解析モデル\JBCQ\
\newblock \Jem{情報処理学会論文誌}, {\Bbf 46}  (4), \mbox{\BPGS\ 1082--1092}.

\bibitem[\protect\BCAY{平川秀樹}{平川秀樹}{2002}]{Hirakawa02_j}
平川秀樹 \BBOP 2002\BBCP.
\newblock \JBOQ 最適解探索に基づく日本語意味係り受け解析\JBCQ\
\newblock \Jem{情報処理学会論文誌}, {\Bbf 43}  (3), \mbox{\BPGS\ 696--707}.

\bibitem[\protect\BCAY{平川秀樹\JBA 天野真家}{平川秀樹\JBA
  天野真家}{1989}]{Hirakawa89a}
平川秀樹\JBA 天野真家 \BBOP 1989\BBCP.
\newblock \JBOQ 構文／意味優先規則による日本語解析\JBCQ\
\newblock \Jem{人工知能学会第３回全国大会論文集}, \mbox{\BPGS\ 363--366}.

\bibitem[\protect\BCAY{野呂智哉\JBA 岡崎篤\JBA 徳永健伸\JBA
  田中穂積}{野呂智哉\Jetal }{2002}]{Noro02}
野呂智哉\JBA 岡崎篤\JBA 徳永健伸\JBA 田中穂積 \BBOP 2002\BBCP.
\newblock \JBOQ 大規模日本語文法構築に関する一考察\JBCQ\
\newblock \Jem{言語処理学会 第8回年次大会}, \mbox{\BPGS\ 387--390}.

\bibitem[\protect\BCAY{野呂智哉\JBA 橋本泰一\JBA 徳永健伸\JBA
  田中穂積}{野呂智哉\Jetal }{2005}]{Noro05}
野呂智哉\JBA 橋本泰一\JBA 徳永健伸\JBA 田中穂積 \BBOP 2005\BBCP.
\newblock \JBOQ 大規模日本語文法の開発\JBCQ\
\newblock \Jem{自然言語処理}, {\Bbf 12}  (1), \mbox{\BPGS\ 3--32}.

\end{thebibliography}

\begin{biography}
\biotitle{略歴}
\bioauthor{平川 秀樹}{
昭和55年京都大学大学院工学研究科電気工学専攻修士課程修了．
同年東京芝浦電気(株)入社．
機械翻訳システムの研究開発に従事．
昭和57-59年新世代コンピュータ開発機構(ICOT)研究員，
平成6-7年MIT Media Lab.派遣研究員，
(株)東芝研究開発センター知識メディアラボラトリ所属，
自然言語処理，知識処理，ヒューマンインタフェースに関する研究に従事．
情報処理学会，人工知能学会，言語処理学会，ACL，GSK各会員．}


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

\end{biography}
\begin{comment}
\end{comment}

\newpage
\subsection*{付録１：構文グラフの問題}
\small
\def\verbatimsize{}

次の文法規則を与えて``Tokyo taxi driver call center''をスタートシンボ
ルをnpとして解析する場合を考える．


{\rm
\begin{verbatim}
　　　[Grammar Rules]
　　　  np/NP  --> npc/NP               : []   
　　　  npc/Nb --> np1/NP1,n/Na,n/Nb    : [arc(nj,NP1,Nb),arc(nc,Na,Nb)] 
　　　  npc/Na --> np2/NP2,n/Na         : [arc(nc,NP2,Na)] 
　　　  npc/Na --> np3/NP3,n/Na         : [arc(nc,NP3,Na)]
　　　  np1/Nc --> n/Na,n/Nb,n/Nc       : [arc(nc,Na,Nb),arc(nc,Nb,Nc)]
　　　  np2/Nd --> n/Na,n/Nb,n/Nc,n/Nd  : [arc(nj,Na,Nc),arc(nc,Nb,Nc),arc(nc,Nc,Nd)] 
　　　  np3/Nd --> n/Na,n/Nb,n/Nc,n/Nd] : [arc(nc,Na,Nb),arc(nj,Nb,Nd),arc(nc,Nc,Nd)] 
　　　
　　　[Lexicon]
　　　  word(n,[Tokyo]). word(n,[taxi]). word(n,[driver]). word(n,[call]). word(n,[center]).
\end{verbatim}
}

\begin{comment}
\begin{figure}[h]
 \begin{center}
  \epsfile{file=\myfigdir/DF付録１−１.eps,scale=0.6}
 \end{center}
\myfiglabelskip
\end{figure}
\end{comment}

この例文では，図\ref{fig:SynGraphBadExample}の(a),(b),(c)の３つの依存木が解として存在する．依
存木のnp1,np2,np3の箱は，句構造と依存構造の対応を分かりやすく示すた
めに補助的に入れている．

\begin{figure}[h]
 \begin{center}
  \epsfile{file=\myfigdir/DF付録１−２.eps,scale=0.6}
 \end{center}
\myfiglabelskip
\caption{依存木と構文グラフ/排他マトリックス}
\label{fig:SynGraphBadExample}
\end{figure}

(a)では，nc-1,nc-2，(b)では，nc-2,nc-3，(c)では，nc-3,nc-1の間で共起関
係が成立するため，図の構文グラフ/排他マトリックスにおいて，それぞれ対
応する排他マトリックスは``　''となっている．このため，(d)の依存木も依
存グラフ/排他マトリックスに存在するが，これに対応する構文木は存在せず，
健全性が損なわれている．


\normalsize
\subsection*{付録２：初期依存森の完全性と健全性の証明}
\small
以下では，統語森PFとそれから構成された依存森DF(依存グラフDG,共起マトリッ
クスCM)を想定する．依存森の完全性・健全性の証明の前に，本文で示したア
ルゴリズムで生成される統語森と依存森の要素に成立する関係を示し，依存森
の完全性・健全性を示すために必要な補題を示す．

\subsection*{［圧縮弧と単一弧］}

統語森は圧縮弧の集合として構成されている．\ref{sec:konokousei}節で説明
したように圧縮弧は単一弧の集合と等価であり,以下では，圧縮弧は単一弧の
集合として扱う．すなわち，図\ref{fig:ArcStructure}の圧縮弧

\mygapskip
圧縮弧：$<$ID,FP,TP,C,PH,FCSL,RCS,DSL$>$ ここで FCSL=[CS$_1$,${\ldots}$,CS$_n$],DSL=[DS$_1$,${\ldots}$,DS$_n$]
\mygapskip

{\mynoindent}は次の単一弧の集合\{*e$_1$,${\ldots}$,*e$_n$\}に対応する．

\mygapskip
*e$_1$ : $<$ID-1,FP,TP,C,PH,(CS$_1$ DS$_1$),RCS$>$

　　　　　　:

*e$_n$ : $<$ID-$n$,FP,TP,C,PH,(CS$_n$ DS$_n$),RCS$>$
\mygapskip

{\mynoindent}例えば，図\ref{fig:ArcStructure}の弧*E4は，次の単一弧
*e$_1$,*e$_2$からなる集合である\footnote{部分依存構造はアーク集合である
ので証明部分では\{\}で表現する．}．

\mygapskip
単一弧*e$_1$: $<$170-1,0,5,vp, [time]-v-0, [103,169], [], \{arc(obj-25,[flies]-n-1,[time]-v-0)\}$>$

単一弧*e$_2$: $<$170-2,0,5,vp, [time]-v-0, [103,119,165],[],\\
　　　　　　　　　　　\{arc(obj-4,[flies]-n-1,[time]-v-0),arc(vpp-20,[like]-pre-2,[time]-v-0)\}$>$
\mygapskip

{\mynoindent}単一弧は，圧縮弧のIDとCSDSペアのリスト中の位置番号の組合
せ(例えば*e$_1$では170-1)で統語森中で一意に特定される．また，語彙弧も同
様に１つの単一語彙弧よりなる集合として扱う．図\ref{fig:ArcStructure}の
弧@E5は，次の単一語彙弧からなる集合\{@e$_3$\}である．

\mygapskip
単一弧@e$_3$: $<$156-1,4,5, n, [arrow]-n-4, [lex([arrow]-n)],\{[[arrow]-n-4]\}$>$
\mygapskip

圧縮弧や単一弧を構成する種々の要素は対応関係を持っている．次に証明で利
用する用語や関係定義などを示す．例の*e$_1$は上記の単一弧*e$_1$である．

\myhalfskip
\hspace{-5mm}
\fbox
{
 \begin{minipage}{13.7cm}

弧とその要素の関係

\begin{itemize}
\item[\myitemindent cs($X$)] : 単一弧$X$の構成素列CS． ex. cs(*e$_1$) =[103,169] (103,169は圧縮弧のID)
\item[\myitemindent ds($X$)] : 単一弧$X$の部分依存構造DSまたは単一語彙弧のノード\\
ex. ds(*e$_1$)=\{arc(obj-25,[flies]-n-1,[time]-v-0)\}, ds(@e$_3$)=\{[arrow]-n-4\}
\item[\myitemindent 統語森・弧中のアーク] : 単一弧$X$中のアークとは
$a{\in}$ds($X$)，圧縮弧$Y$中のアークとは$a{\in}$ds($X$),$X{\in}Y$，統
語森PF中のアークとは$a{\in}$ds($X$),$X{\in}Y$,$Y{\in}$PFをいう．
\end{itemize}

アークやノードの関係
\begin{itemize}
\item[\myitemindent gov($X$)] : アーク$X$の支配ノード． ex. gov(arc(obj-25,[flies]-n-1,[time]-v-0)) = [time]-v-0
\item[\myitemindent dep($X$)] : アーク$X$の依存ノード． ex. dep(arc(obj-25,[flies]-n-1,[time]-v-0) = [flies]-n-1
\item[\myitemindent top\_node($X$)] : 依存木$X$のトップノード（どのアー
クの依存ノードにもなっていないノード）．
\end{itemize}

依存木DT中のアーク$X$,$Y$に対する関係
\begin{itemize}
\item[\myitemindent bro($X$,$Y$)] : gov($X$)=gov($Y$)．$X$,$Y$を兄弟アークと呼ぶ．
\item[\myitemindent $X \: {\xrightarrow[{\rm DT}]{1}} \: Y$] : dep($X$)=gov($Y$)．$X$は$Y$の親，$Y$は$X$の子と呼び，この関係を親子関係と呼ぶ．
\item[\myitemindent $X \: {\xrightarrow[{\rm DT}]{+}} \: Y$] : $X$から$Y$に親子関係の連鎖(１段以上)が存在．$X$を$Y$の祖先アーク，$Y$を$X$の子孫アークと呼ぶ．
\item[\myitemindent $X \: {\xrightarrow[{\rm DT}]{*}} \: Y$] : $X=Y$または$X{\xrightarrow[{\rm DT}]{+}}Y$．
\end{itemize}
\myhalfskip
\end{minipage}
}

\subsection*{［統語森・統語森中の弧・構文木］}

統語森PF は，ルート圧縮弧*E$_{root}$をルートとし語彙弧をリーフとする圧
縮弧からなる非循環有向グラフ(DAG)である．統語森の構成より，次のように
パスを定義する．

\begin{definition}
{\bf 統語森中のパス}とは，圧縮弧から１つの単一弧を選択すること，ならび
に単一弧の構成素列CS(圧縮弧の列) から１つの圧縮弧を選択することに
より，圧縮弧と単一弧を交互に辿ることにより得られる圧縮弧と単一弧からな
る列である．
\end{definition}

{\mynoindent}今，統語森中の弧*E$_0$,*E$_1$,*E$_2{\cdots}$が次のようであるとする．

\mygapskip
\hspace{15mm}*E$_0=$\{*e$_1$,*e$_2$\}, *E$_1=$\{*e$_3$\}, *E$_2=$\{*e$_4$,*e$_5$\}, *E$_3=$\{*e$_6$,*e$_7$\} ${\ldots}$

\hspace{15mm}cs(*e$_1$)=[*E$_1$,*E$_2$], cs(*e$_2$)=[*E$_3$], cs(*e$_3$)=[*E$_4$,*E$_5$] ${\ldots}$
\mygapskip


{\mynoindent}次の４つはパスの例である．

\mygapskip
\hspace{15mm}[*E$_0$,*e$_1$,*E$_2$,*e$_5$], [*E$_0$,*e$_1$,*E$_2$], [*e$_1$,*E$_1$,*e$_3$,*E$_5$], [*e$_1$,*E$_1$,*e$_3$]
\mygapskip
{\mynoindent}以下に証明で用いる用語や関係定義を示す．

\myhalfskip
\hspace{-5mm}
\fbox
{
\begin{minipage}{13.7cm}
\mygapskip

統語森に関連する用語や関係定義

\begin{itemize}
\item[\myitemindent $X \: {\xrightarrow[{\rm PF}]{+}} \: Y$] : 統語森
PFにおいて単一弧または圧縮弧$X$から単一弧または圧縮弧$Y$に対して
[$X,{\ldots},Y$]なるパスが存在する．$X$を$Y$の祖先とも呼ぶ．
\item[\myitemindent $X \: {\xrightarrow[{\rm PF}]{*}} \: Y$] : 単一弧
または圧縮弧$X$,$Y$に対して，$X=Y$または$X{\xrightarrow[{\rm
PF}]{{\tiny +}}}Y$が成立する．このとき，$X$から$Y$に{\bf 到達可能}と呼ぶ．
\item[\myitemindent $X \: {\swarrow}${\tiny [PF]}${\searrow} \: Y$] : 単一弧または圧縮
弧$X$,$Y$に対して，$X{\neq}Y$,
$\neg$($X{\xrightarrow[{\rm PF}]{*}}Y$),
$\neg$($Y{\xrightarrow[{\rm PF}]{*}}X$)であり，
$Z{\xrightarrow[{\rm PF}]{*}}X$かつ$Z{\xrightarrow[{\rm PF}]{*}}Y$なる単一弧または圧縮弧
$Z$が統語森PFに少なくとも１つ存在する．
\item[\myitemindent 弧が支配するアーク] : アーク$X$は$X{\in}$ds(*e),*E${\xrightarrow[{\rm PF}]{{\tiny *}}}$*eの時，弧*Eに支配されるという．
\end{itemize}

\myhalfskip
\end{minipage}
}
\myhalfskip
\myhalfskip

{\mynoindent}統語森の定義よりルート圧縮弧*E$_{root}$から統語森PF中の全
ての単一弧または圧縮弧へ到達するパスが存在する．以上定義した記法を用い
ると\ref{sec:PFandDFseisei}節の共起設定条件は次の様に定義できる．

\begin{definition}
共起設定条件 : アーク$X$,$Y$は次のいずれかの条件を満たす時に共起可能である．
\begin{itemize}
\item[(C1)] : アーク$X$,$Y$に対し$X$,$Y{\in}$ds(*e),*e${\in}$*E,*E${\in}$PFなる*eが存在する．
\item[(C2)] : アーク$X$,$Y$に対し$X{\in}$ds(*e$_x$),$Y{\in}$ds(*e$_y$),
*e$_x{\xrightarrow[{\rm PF}]{{\tiny +}}}$*e$_y$又は*e$_y{\xrightarrow[{\rm PF}]{{\tiny +}}}$*e$_x$
なる*e$_x$,*e$_y$が存在する．
\item[(C3)] : アーク$X$,$Y$に対して$X{\in}$ds(*e$_x$),$Y{\in}$ds(*e$_y$),*e$_x{\swarrow}${\tiny [PF]}${\searrow}$*e$_y$なる*e$_x$,*e$_y$が存在する．
\end{itemize}
\end{definition}


{\mynoindent}また，構文木を次のように定義する．
\begin{definition}
構文木は，統語森中の圧縮弧*Eに対して適用される図\ref{fig:get_parse_tree} 
の再帰的な手続きget\_tree(*E)により得られる単一弧の集合である．
\end{definition}
\clearpage

    \clearpage
\begin{figure}[t]
 \begin{center}
  \epsfile{file=\myfigdir/DF付録２圧縮弧から構文木を得るアルゴリズム.eps,scale=0.7}
 \end{center}
\myfiglabelskip
\myfiglabelskippre
\caption{圧縮弧から構文木を得るアルゴリズム}
\myfiglabelskippost
\label{fig:get_parse_tree}
\end{figure}

図のselect(RPE)では圧縮弧RPE中の任意の単一弧を１つ選択する．
lexical\_edge(SE)はSEが語彙弧のときに真となる．また，構文木は，弧*Eの
始点から終点の範囲の語を被覆する．

\begin{definition}
parse\_trees(*E)は，弧*Eに対する全構文木の集合である．
\end{definition}

\begin{figure}[b]
\myfigskiptop
 \begin{center}
  \epsfile{file=\myfigdir/DF付録２弧の結合木.eps,scale=0.81}
 \end{center}
\myfiglabelskip
\myfiglabelskippre
\caption{弧の結合木}
\label{fig:EdgeCombinationTree}
\myfiglabelskippost
\end{figure}

\subsection*{［弧とアーク・部分依存構造の関係］}

図\ref{fig:ChartAlgotithm}のアルゴリズムはデータ構造として圧縮弧を用い
て構成されている．但し，弧の圧縮共有は，不活性弧が生成された時点(図
\ref{fig:ChartAlgotithm}(c),(d))でのみ行われる．このため，活性圧縮弧は
１つの単一弧を要素として持つのみであり\footnote{活性弧も圧縮共有する解
析アルゴリズムも考えられるため圧縮弧をベースとしている．}，活性圧縮弧
と単一弧は１対１対応している．以下の議論では，簡便のため，圧縮弧を単に
弧と表現する．


構文解析は，不活性弧を活性弧に結合(combine)し新しい弧が生成されること
で進行する．模式的に言えば，弧の結合では，\ref{sec:konokousei}節で述べ
たように，活性弧の``・''を１つ右に移動し，結合する不活性弧の句ヘッド(ノー
ド)との変数束縛を行った新たな弧の生成が行われる．図
\ref{fig:EdgeCombinationTree}は，弧の結合により１つの文法規則から不活
性弧が生成される様子を示した木であり，{\bf 弧の結合木}と呼ぶ．弧の結合
木は，ルートにある文法規則\footnote{文法規則を弧の形式で表現している．
実際にはこの弧は生成されないが説明上導入している．} から，弧の結合によ
り活性弧が生成され(中間に位置)，最終的に不活性弧(リーフに位置)になる様
子を示している．文法規則は次である．
$${\rm y/}X_h \rightarrow {\rm x}_1{\rm /}X_1 {\cdots} {\rm x}_h{\rm
/}X_h {\cdots} {\rm x}_n{\rm /}X_n : \{A_1,A_2,{\ldots},A_{n-1}\}$$
$A_i$はアークで，arc($a_i$,$X_k$,$X_l$)の形式($a_i$は任意のアーク名,
1${\leq}k{\leq}n$, 1${\leq}l{\leq}n$, $k{\neq}l$)をしている．
\{$A_1$,${\ldots}$,$A_{n-1}$\}は，部分依存構造条件
(\ref{sec:bunpoukisoku}節)を満足している．

結合木中の弧は，「・」を用いた図式的表現で示しており，始点，終点は省略
している．弧を結ぶ枝が弧の結合を表しており，枝の元の弧と枝に付けた不活
性圧縮弧とが結合して枝の先の弧を新規に生成する．例えば，弧E$_{11}$(図
\ref{fig:EdgeCombinationTree}(a))と弧$<$*E x$_2$/n$_{21}$
$\rightarrow$ ${\ldots}$ $>$(図\ref{fig:EdgeCombinationTree}(b)) が結合して弧
E$_{21}$(図\ref{fig:EdgeCombinationTree}(c))が生成される．枝を下る毎に
「・」が右に移動するので，E$_0$から葉の不活性弧までの深さは文法規則の
規則ボディの要素数$n$である．

弧の結合では，結合対象の弧の句ヘッド(ノード)が結合先の変数に束縛される
が，この変数の束縛状況を結合木の弧の後に\{\}で示している．例えば，
E$_0$と(d)の弧(句ヘッドはn$_{11}$)との結合でE$_{11}$が生成され，さら
に(b)の弧(句ヘッドはn$_{21}$)が結合して弧E$_{21}$が生成される．この結
果(c)の弧E$_{21}$の変数束縛結果は\{$X_1$:=n$_{11}$,$X_2$:=n$_{21}$\}と
なっている\footnote{変数のスコープは１つの弧内であり，同じ名前の変数でも別の弧で
は異なった変数である．}．変数束縛により依存ノードと支配ノードの両者が
確定したアークは{\bf 確定アーク}と呼び，図\ref{fig:ChartAlgotithm}(i) 
のadd\_arcidにより新規のアークIDが付与される．確定アークは，図
\ref{fig:EdgeCombinationTree}では，同図(e)のa$_1$ように小文字aで表現す
る．１回の変数束縛で複数のアークが確定する場合や１つも確定しない場合も
あるが，確定されたアーク$a$に対しては，それを確定した変数束縛は一意に
決定される．さらに，その変数束縛(あるいは弧の結合)により生じる弧は１つ
に特定される．この弧を(確定された){\bf アークを生成した弧}と呼び，
src\_Edge(a)と記述する．例えば，図\ref{fig:EdgeCombinationTree} の
(e)と(f)の結合では，変数$X_i$へのノードn$_{im}$(例えば[like]-pre-3とす
る)の束縛により，アーク$A_i$(例えば, arc(pre,$X_i$,[time]-v-0)とする) 
が確定されアークa$_i$ (arc(pre-28,[like]-pre-3,[time]-v-0)(ユニークアー
クIDが28))になったとすると，アークa$_i$を生成した弧すなわち
src\_Edge(a$_i$)は弧E$_{im}$(図\ref{fig:EdgeCombinationTree}(g)) とな
る．

リーフに位置する不活性弧(例えば図\ref{fig:EdgeCombinationTree}(h))では，
部分依存構造条件より句ヘッドを含む全ての変数が束縛され，全てのアークが
確定された状態となる．不活性弧は，弧の結合木のルートからリーフにいたる
一連の弧の結合により生じる変数の束縛，アークの確定の結果を表している．
次に結合木に関連する用語や関係定義などを示す．

\myhalfskip
\hspace{-5mm}
\fbox
{
\begin{minipage}{13.7cm}
\mygapskip

弧の結合木に関連する用語や関係定義

\begin{itemize}
\item[\myitemindent {\bf 確定アーク}] : 弧の結合時の変数束縛により依存ノード
と支配ノードの両者が確定されたアーク

\item[\myitemindent src\_Edge($a$)（{\bf 生成弧}）] : 確定アーク$a$を生成した弧(活性圧
縮弧または不活性圧縮弧)．確定アークから弧への対応は1対1，弧から確定アー
クへの対応は1対0〜多．

\item[\myitemindent $X {\xrightarrow[{\rm CT}]{*}} Y$ （{\bf オリジン}）]
: 弧の結合木CT において，ルートから弧$Y$に至る経路に弧$X$が存在する，
又は，$X=Y$である．
$X$を$Y$のオリジンと呼ぶ．

\item[\myitemindent {\bf オリジンの関係}] : 弧の結合木CTにおいて弧$X$,$Y$に
関して$X {\xrightarrow[{\rm CT}]{*}} Y$または$Y {\xrightarrow[{\rm
CT}]{*}} X$が成り立つ時，$X$と$Y$はオリジンの関係にあるという．

\item[\myitemindent edge($a$,$DT$)（{\bf 対応弧}）] : 確定アーク$a$と整依存木$DT$に対
して次の条件(補題\ref{lem:app2-2})を満たす単一弧$e$を意味し，アーク$a$の整依存木$DT$に対する「対応弧」と呼ぶ．

{\myitemindent}$DT {\supseteq} {\rm ds(}e{\rm )},{\rm a}{\in}{\rm ds(}e{\rm )}$


\end{itemize}
\myhalfskip
\end{minipage}
}

\myhalfskip

{\mynoindent}上記の弧の結合木の構成より，部分依存構造中に存在する２つの確定アーク
a$_i$,a$_j$に関して，次の補題が成立する．

\begin{lemma}[同一部分依存構造中のアークの関係]
\label{lem:TwoArcsInOneDS}
単一弧$e$中の確定アークa$_i$,a$_j{\in}${\rm ds(}$e${\rm )}に対してそれら
の生成弧src\_Edge(a$_i$)とsrc\_Edge(a$_j$)はオリジンの関係にある．
\end{lemma}

{\mynoindent}また，一度確定されたアークは，結合木上で下位に位置する弧
の依存構造に含まれる．例えば，(g)で確定されたアークa$_i$は，(h)など(g)
をオリジンとする弧全てに含まれる．このため，次の補題が成立する．

\begin{lemma}[アークとアークを生成した弧の関係]
\label{lem:app2-1}
確定アークa$_i$,a$_j$に対して，src\_Edge(a$_i$)${\xrightarrow[{\rm
CT}]{*}}$src\_Edge(a$_j$)の時，PF中の任意の単一弧
*e(*e${\in}$*E,*E${\in}$PF)に対してa$_j{\in}$ds(*e)であれば
a$_i{\in}$ds(*e)である．
\end{lemma}

なお，アークが確定される毎にユニークなアークIDが生成されるため，結合木
のリーフの不活性弧(図\ref{fig:EdgeCombinationTree}の
*E$_{n1}{\cdots}$*E$_{no}{\ldots}$*E$_{nw}$)中の単一不活性弧は全て異なっ
た部分依存構造を持つ．これから，PF中の任意の
*e$_i$,*e$_j$(*e$_i{\neq}$*e$_j$)に対して，
ds(*e$_i$)${\neq}$ds(*e$_j$)であり，単一不活性弧と部分依存構造は1対1対
応すると言える．実際には，既に述べたように結合木のリーフの不活性弧は，
複数の単一弧を含む弧にマージされる場合もあり，この結果得られる圧縮弧が
統語森の要素となるが，マージ操作が単一弧の部分依存構造を更新することは
ないため，単一不活性弧と部分依存構造の1対1対応関係は保証される．また，
前記共起設定条件(C2)に関連して，統語森に関する次の補題が成立する．

\begin{lemma}[パス中の弧が含むアークに関する制約]
\label{lem:ArcConstraintOfArcsOnOnePath}
アークa$_i{\in}$ds(e$_i$),a$_j{\in}$ds(e$_j$)に関して，
e$_i{\xrightarrow[{\rm PF}]{{\tiny +}}}$e$_j$であれば，
dep(a$_i$)${\neq}$dep(a$_j$)である．また，逆にdep(a$_i$)$=$dep(a$_j$)であれば
¬(e$_i{\xrightarrow[{\rm PF}]{{\tiny +}}}$e$_j$)である．

\proof{

部分依存構造条件(\ref{sec:bunpoukisoku}節)より，１つの単一弧の有する部
分依存構造は句ヘッドをルートとした依存木となるため成立する．

}
\end{lemma}

\begin{lemma}[対応弧の存在]
\label{lem:app2-2}
整依存木{\rm DT}中のアーク{\rm a$_i$}({\rm a$_i$}${\in}${\rm DT)}に対して次が成立する
圧縮弧{\rm E}${\in}${\rm PF},単一弧{\rm e}${\in}${\rm E}がただ１つ存在する．

   {\rm DT} ⊇ {\rm ds(}e{\rm )},{\rm a$_i$}${\in}${\rm ds(}e{\rm )}

\mygapskip
{\mynoindent}補題\ref{lem:app2-2}は，アーク{\rm a$_i$}が整依存木{\rm DT}の要素の時，
{\rm a$_i$} を含む部分依存構造{\rm ds(}e{\rm )}の全体が{\rm DT}に含まれる
ところの単一弧{\rm e}が統語森に存在することを意味している．

\proof{

DTのノード数を$n$(アーク数: $n-1$)とする．DTをアークa$_i$に関し
て次の２つのアーク集合IN\_ARCS,OUT\_ARCSに分ける．

{\mygapskip}
IN\_ARCS = \{ $a_j$ ${\mid}$ src\_Edge($a_i$)${\xrightarrow[{\rm CT}]{*}}$src\_Edge($a_j$)またはsrc\_Edge($a_j$)${\xrightarrow[{\rm CT}]{*}}$src\_Edge($a_i$)\}

OUT\_ARCS = DT$-$IN\_ARCS
{\mygapskip}

{\mynoindent}また，IN\_ARCS中のアークに対する生成弧の集合をSRC\_EDGESとする．

{\mygapskip}
SRC\_EDGES = \{$E$ ${\mid}$ $E$=src\_Edge($a$), $a{\in}$IN\_ARCS\}
{\mygapskip}

{\mynoindent}ここで，次が成立する．
$$「{\rm SRC\_EDGES}中の任意の弧の間でオリジンの関係が成立する」\eqno{(A)}$$
今，$U$,$V{\in}$SRC\_EDGESを考える．これらは定義より
E$_i=$src\_Edge(a$_i$)とオリジンの関係にあり，次の３つの場合のいずれか
となる．

\begin{itemize}
\item[\myitemindent(a)] 片方がE$_i$のオリジン，E$_i$が他方のオリジン．$U{\xrightarrow[{\rm CT}]{*}}$ E$_i$,E$_i{\xrightarrow[{\rm CT}]{*}} V$ 
\item[\myitemindent(b)] 両方がE$_i$のオリジン．$U{\xrightarrow[{\rm CT}]{*}}$ E$_i$,$V{\xrightarrow[{\rm CT}]{*}}$E$_i$
\item[\myitemindent(c)] E$_i$が両方のオリジン．E$_i{\xrightarrow[{\rm CT}]{*}}U$,E$_i{\xrightarrow[{\rm CT}]{*}}V$
\end{itemize}

{\mynoindent}(a),(b)の場合は，弧の結合木の構成から明らかに(A)が成立す
る．以下で(c)の場合に$U$と$V$がオリジンの関係にないと仮定すると矛盾が
生じることを示す．

$U$と$V$がオリジンの関係にないと仮定する．前提より
$U$=src\_Edge(a$_u$),$V$=src\_Edge(a$_v$)なるa$_u$,a$_v{\in}$DTが存在
する．DT中のアークは依存森中に存在する必要があるため，$U$,$V$をオリジ
ンとする不活性弧が統語森に含まれる必要がある．この不活性弧を
*E$_u$,*E$_v$，その中の単一弧を
*e$_u$,*e$_v$(a$_u{\in}$*e$_u$,a$_v{\in}$*e$_v$)とする．補題
\ref{lem:app2-1}より，*e$_u$,*e$_v$は共にa$_i$を含む．DTが整依存木なの
でa$_u$,a$_v$の間に共起関係が成立する．すなわち，前記共起設定条件(C1)〜
(C3)のいずれかが成立する．(C1) については，a$_u$,a$_v{\in}$ds($e$)なる
$e$が存在すると補題\ref{lem:TwoArcsInOneDS} より$U$と$V$がオリジンの関
係になり仮定と矛盾する．よって(C1)は成立しない．(C2)は，*e$_u
{\xrightarrow[{\rm PF}]{+}}$*e$_v$(逆も同様に議論可能)が成立することで
ある．ds(*e$_u$)中のアークを構成するノードは，部分依存構造条件より
cs(*e$_u$) の各構成素の句ヘッドである．このため，a$_i{\in}$ds(*e$_u$)
に対してdep(a$_i$)またはgov(a$_i$)のいずれかは*e$_v$の被覆範囲の外のノー
ドである．一方，a$_i{\in}$ds(*e$_v$)からは，dep(a$_i$)，gov(a$_i$)とも
に*e$_v$の被覆する範囲に存在しなければならない．これから矛盾が生じるた
め，(C2)は成立しない．(C3)は，*e$_u{\swarrow}${\tiny
[PF]}${\searrow}$*e$_v$が成立することであるが，*e$_u$と*e$_v$が共に
a$_i$を含むことから被覆範囲がオーバラップし成立しない．以上より，上記
(c)の場合も，$U$と$V$がオリジンの関係にないと仮定するとa$_u$とa$_v$の
共起関係が成立しないため，$U$と$V$ はオリジンの関係にあるといえる．以
上より，（A)が成立する．

\begin{figure}[tb]
 \begin{center}
  \epsfile{file=\myfigdir/DF付録２依存木のアークを生成した弧.eps,scale=1.0}
 \end{center}
\myfiglabelskip
\myfiglabelskippre
\caption{依存木のアークを生成した弧}
\myfiglabelskippost
\label{fig:CorrespondenceDT2Edge}
\end{figure}

\mygapskip
{\mynoindent}今，E$_i$からつながる最後の弧，すなわち次の条件を満たす弧をE$_{last}$
とおく．
\mygapskip

E$_i{\xrightarrow[{\rm CT}]{*}}$E$_{last}$ 

E$_{last}{\xrightarrow[{\rm CT}]{*}}$E$_j$ (E$_j{\in}$SRC\_EDGES)を満
たすE$_j$はE$_{last}$のみである
\mygapskip

{\mynoindent}図\ref{fig:CorrespondenceDT2Edge} に説明のためIN\_ARCSと
SRC\_EDGESの関係を模式的に示す．E$_{start}$は文法規則に対応する弧であ
り，文法規則をy/$X_h$ $\rightarrow$ x$_1$/$X_1{\cdots}$ x$_z$/$X_z$ :
\{$A_1$,${\ldots}$,$A_{z-1}$\}とする．(A)よりSRC\_EDGES中の弧は全てオ
リジンの関係にあるため，SRC\_EDGESは，E$_{start}$をルートとし，
E$_1$,${\ldots}$,E$_{last}$からなるCT上の経路を構成する．a$_i$の生成弧
E$_i$はこのパス上のいずれかに存在する．また，E$_{last}$が生成したアー
クa$_{last}$が少なくとも１つIN\_ARCS中に存在する．

E$_{last}$は，活性弧であるか不活性弧であるかのいずれかである(図
\ref{fig:CorrespondenceDT2Edge}は，弧が活性弧の場合である) が，
E$_{last}$を活性弧と仮定すると次に示すように矛盾が生じる．

\begin{figure}[b]
 \begin{center}
  \epsfile{file=\myfigdir/DF付録２整合部分依存構造の存在証明.eps,scale=0.82}
 \end{center}
\myfiglabelskip
\caption{対応弧の存在説明図}
\label{fig:ActiveEdgeLast}
\end{figure}

E$_{last}$が活性弧であると仮定する．図\ref{fig:ActiveEdgeLast}に示すよ
うに，E$_{last}$(図\ref{fig:ActiveEdgeLast}(a))は少なくとも１つの残り
構成素x$_{u+1}$(変数は省略,図\ref{fig:ActiveEdgeLast}(b))を有する．こ
こでE$_{last}$の始点をs1，終点をt1とする．

依存グラフは統語森中のアークより構成されるため，前提a$_{last}{\in}$DT 
より，a$_{last}$を生成した弧E$_{last}$ をオリジンとする少なくとも１つ
の不活性弧*E$_{x}$(図\ref{fig:ActiveEdgeLast}(c))が統語森PFに存在する．
図に示すように*E$_{x}$は，活性弧E$_{last}$ をオリジンとするため，始点
はE$_{last}$の始点s1と等しく，終点t3は，E$_{last}$の終点
t1より大きい．

次に，位置t1+1のノードn$_{t1+1}$(図\ref{fig:ActiveEdgeLast}(d))を考
える(DTは整依存木であるため，整被覆条件より必ずn$_{t1+1}$は存在する)．
DTにはn$_{t1+1}$を依存ノードとするアークが１つ存在し，これを
a$_{next}$(dep(a$_{next}$)$=$n$_{t1+1}$,図\ref{fig:ActiveEdgeLast}(e)) 
とする．a$_{next}$は，a$_{last}$の定義からOUT\_ARCSの要素である．
a$_{next}{\in}$DTより，a$_{next}$の生成弧E$_{next}$をオリジンとす
る不活性弧*E$_{y}$が少なくとも１つ統語森PFに存在する．
E$_{next}$は，その範囲中にa$_{next}$を含むので，その始点s2はt1以下(図
\ref{fig:ActiveEdgeLast}(f)) ，その終点はt1+1以上である(図
\ref{fig:ActiveEdgeLast}(g))．よって，図に示すように*E$_{y}$の始点は
t1以下となる．以上より，E$_{last}$ をオリジンとする不活性弧
*E$_{x}$とE$_{next}$ をオリジンとする不活性弧*E$_{y}$の弧の範囲は位
置t1でオーバーラップする．

ここで，a$_{last}$とa$_{next}$に対して共起設定条件(C1)〜(C3)のいずれも
が成立しないことを示す．

上記より*E$_{x}$と*E$_{y}$は被覆する範囲がオーバーラップするため，
(C3)は成立しない．また，前提より*E$_{x}{\neq}$*E$_{y}$であり(C1)は成
立しない．共起設定条件(C2)は*E$_{x}{\xrightarrow[{\rm PF}]{{\tiny
+}}}$*E$_{y}$(またはその逆)が成立することである．今，*E$_x$中のアー
クで依存ノードをn$_{t1+1}$とするアークをa$_m$とすると，
a$_m{\neq}$a$_{next}$である(もし，a$_m=$a$_{next}$であれば，
src\_Edge(a$_{next}$)とE$_i$はオリジンの関係にあるため，前提
a$_{next}{\in}$OUT\_ARCSと矛盾する)．補題
\ref{lem:ArcConstraintOfArcsOnOnePath}より*E$_{x}{\xrightarrow[{\rm
PF}]{{\tiny +}}}$*E$_{y}$が成立することはなく，(C2)も成立しない．以上
より，DTの要素であるa$_{last}$とa$_{next}$の間に共起関係が成立すること
はなく，これはDTが整依存木であることと矛盾する．よって，E$_{last}$は活
性弧ではない．　
\mygapskip
次に，E$_{last}$が不活性弧であるとする(不活性弧であるので，*E$_{last}$
と記述する）．

\begin{itemize}
\item[(a)]a$_{last}$を生成した弧*E$_{last}$は不活性弧(結合木のリーフ)
であるのでa$_{last}$を含む圧縮弧は，*E$_{last}$のみである．また，
a$_{last}{\in}$ds(*e$_{last}$),*e$_{last}{\in}$*E$_{last}$なる
*e$_{last}$がただ１つ存在する．
\item[(b)]a$_{last}{\in}$DTより，*E$_{last}{\in}$PFである．
\item[(c)]a$_{last}{\in}$DTと補題\ref{lem:app2-1}より，DT${\supseteq}$ds(*e$_{last}$)である．
\end{itemize}

{\mynoindent}(a)〜(c)より，補題が成立する．
}

\end{lemma}


\subsection*{［接続するアークと対応する弧の関係］}

親子関係または兄弟関係にあるアークa$_i$,a$_j$(a$_i{\xrightarrow[{\rm
DT}]{1}}$a$_j$またはbro(a$_i$,a$_j$))を「{\bf 接続するアーク}」と呼び，
整依存木DT中の接続するアークに対して以下の2つの補題が成立する．

\begin{lemma}[接続するアークと対応する弧]
\label{lem:app2-3}

整依存木DT中の接続するアークa$_i$,a$_j$に対して，*e$_i$=edge(a$_i$,DT)，
*e$_j$=edge(a$_j$,DT) とした時に，次の(a),(b),(c)のいづれかが成立する．
\begin{itemize}
\item[(a)]*e$_i=$*e$_j$
\item[(b)]*e$_i{\xrightarrow[{\rm PF}]{+}}$*e$_j$
\item[(c)]*e$_j{\xrightarrow[{\rm PF}]{+}}$*e$_i$
\end{itemize}

インフォーマルな表現であるが，補題\ref{lem:app2-3}は，依存木中のアーク
が接続関係にあれば，それらの対応弧はPTにおいて到達可能であるということ
を示している．

\proof{

a$_i$,a$_j$は整共起条件を満足するので，共起設定条件より，*e$_i$,*e$_j$ 
は次の(r1)〜(r3)のいずれかの関係を満足している必要がある．
\begin{itemize}
\item[(r1)] *e$_i$=*e$_j$ 
\item[(r2)] *e$_i{\xrightarrow[{\rm PF}]{+}}$*e$_j$又は*e$_j{\xrightarrow[{\rm PF}]{+}}$*e$_i$
\item[(r3)] *e$_i {\swarrow}${\tiny [PF]}${\searrow}$ *e$_j$
\end{itemize}

今，接続するアークa$_i$,a$_j$が共有するノードを$n$とすると*e$_i$と*e$_j$は共に$n$を
被覆する．(r3)の*e$_i$と*e$_j$が共に同一のノードを被覆することはないので，
(r1)または(r2)のいずれかが成立している．よって補題\ref{lem:app2-3}が成立する．
}
\end{lemma}

\begin{lemma}[子孫アークと対応する弧]
\label{lem:app2-4}
整依存木DT中のアークa$_i$,a$_j$(a$_i{\xrightarrow[{\rm DT}]{+}}$a$_j$)
に対して，*e$_i$=edge(a$_i$,DT)，*e$_j$=edge(a$_j$,DT)とした時に，次が
成立する．
\begin{itemize}
\item[] *e$_i{\xrightarrow[{\rm PF}]{*}}$*e$_j$
\end{itemize}

\proof{

a$_i$がa$_j$の親アーク(dep(a$_i$)=gov(a$_j$))の場合，補題
\ref{lem:app2-3}(a),(b),(c)のいずれかが成立する．\ref{sec:bunpoukisoku}節
の部分依存構造条件による位置関係より，子アークa$_j$の対応弧*e$_j$と親アー
クa$_i$の対応弧*e$_i$において$\neg$(*e$_j{\xrightarrow[{\rm
PF}]{+}}$*e$_i$) なので(c)が成立することはない．このため，親子アークに
ついては(a),(b)のいずれかが成立する．一般のa$_i{\xrightarrow[{\rm DT}]{*}}$a$_j$ 
に対しては${\xrightarrow[{\rm PF}]{*}}$ の推移性により補題
\ref{lem:app2-4}が成立する．

}
\end{lemma}

\subsection*{［トップ単一弧top\_edge(DT)］}

ここでは，下記の証明で使用する依存木DTに対する{\bf トップ単一弧}top\_edgeを
定義する．

\begin{definition}
{\bf トップ単一弧}top\_edge(DT)は，DTのトップノード直下のアークに対する対応弧
の内で統語森中で最上位に位置する単一弧である．すなわち，top\_edge(DT) 
は，top\_node(DT)$=$gov(a$_i$)であり，top\_node(DT)$=$gov(a$_j$)となる
どんなa$_j$に対しても
edge(a$_i$)${\xrightarrow[{\rm PF}]{*}}$edge(a$_j$)である．DTが単一ノー
ドからなる木の場合は，その単一ノードに対する単一語彙弧とする．
\end{definition}

{\mynoindent}DT中のアークとtop\_edge(DT)の間に次が成立する．

\begin{lemma}[top\_edge(DT)とedge(a$_j$,DT)の関係]
\label{lem:RelBetweenTopedgeAndEdge}

整依存木DTのトップ単一弧*e$_t$=top\_edge(DT)とa$_j$(a$_j{\in}$DT)の対
応弧*e$_j$=edge(a$_j$,DT)との間には*e$_t{\xrightarrow[{\rm
PF}]{*}}$*e$_j$が成立する．

\proof{

a$_j$がDTのトップノードの直下のアーク，すなわち
gov(a$_j$)$=$top\_node(DT)の場合は，補題\ref{lem:app2-3}とtop\_edgeの
定義より，*e$_t{\xrightarrow[{\rm PF}]{*}}$*e$_j$が成立する．それ以外
の場合は，a$_j$はDTのトップノード直下のアークの子孫アークとなるため，
補題\ref{lem:app2-4}より*e$_t{\xrightarrow[{\rm PF}]{*}}$*e$_j$である．

}
\end{lemma}

\subsection*{［整依存木{\rm DT}の分割］}

\begin{figure}[t]
 \begin{center}
  \epsfile{file=\myfigdir/DF付録２整依存木の分割の説明図.eps,scale=0.8}
 \end{center}
\myfiglabelskip
\myfiglabelskippre
\caption{整依存木の分割}
\myfiglabelskippost
\label{fig:DTGraphDivision}
\end{figure}

{\bf 整依存木DTの分割}とは，DTからds(top\_edge(DT))のアークを除外し，
部分依存木DT$_1$,${\ldots}$,DT$_m$($m$はds(top\_edge(DT))に含まれるノー
ド数)を得ることである．アークの除外により他のノードから孤立するノード
は，アークを持たない１つの依存木とする．例えば，図
\ref{fig:DTGraphDivision} において
ds(top\_edge(DT))=\{a$_s$,a$_t$,a$_u$,a$_w$\}の時，DTからこれらを除い
た残りのアーク集合は，n$_s$,n$_t$,n$_u$,n$_v$,n$_w$をトップノードとす
る依存木群DT$_s$,DT$_t$,DT$_u$,DT$_v$,DT$_w$に分割できる．ノード
n$_s$,n$_w$は孤立したノードとなるので，DT$_s$ とDT$_w$は1つのノードか
らなる依存木\{n$_s$\},\{n$_w$\}となる．\ref{sec:bunpoukisoku}節の部分
依存構造条件より，単一弧$e$において構成素列cs($e$)中の圧縮弧の句ヘッド
と部分依存構造ds($e$)中のノードは1対1対応するので，
DT$_i$(1${\leq}i{\leq}m$)のトップノードn$_i$を句ヘッドとする圧縮弧
*E$_i$がcs(top\_edge(DT))に各１つだけ存在する．*E$_i$をDT$_i$ の{\bf ルート
圧縮弧}と呼び，root\_Edge(DT$_i$)とする．

\begin{definition}
{\bf ルート圧縮弧}root\_Edge(DT$_i$)とは，依存木DTの分割で生じた依存木
DT$_i$に対して構成素列cs(top\_edge(DT))中の圧縮弧*E$_i$のうち句ヘッド
がtop\_node(DT$_i$)であるもの．
\end{definition}

図\ref{fig:DTGraphDivision}では，top\_edge(DT)が*e$_v$であり，その構成素
列cs$_v$は，n$_s$,n$_t$,n$_u$,n$_v$,n$_w$を句ヘッドとする弧
*E$_s$,*E$_t$,*E$_u$,*E$_v$,*E$_w$より構成されている．
root\_Edge(DT$_t$)=*E$_t$である．整依存木DTの分割に関して図
\ref{fig:DTiObtainedFromDT}を参照しながら以下2つの補題を示す．

\begin{comment}
\myhalfskip
\hspace{-5mm}
\fbox
{
\begin{minipage}{13.7cm}
\mygapskip
依存木分割と圧縮弧
\begin{itemize}
\item[\myitemindent root\_Edge(DT$_i$)] : ルート圧縮弧．依存木DTの分割で生じた依存木DT$_i$に対して
構成素列cs(top\_edge(DT))中の圧縮弧*E$_i$のうち句ヘッドがtop\_node(DT$_i$)であるもの．
\end{itemize}
\myhalfskip
\end{minipage}
}
\myhalfskip
\end{comment}

\begin{lemma}[ルート圧縮弧とトップ単一弧の関係]
\label{lem:app2RootEdgeAndTopEdge}
整依存木DTの分割により得られる部分依存木DT$_i$に対して，ルート圧縮弧を
*E$_i=$root\_Edge(DT$_i$),トップ単一弧を*e$_{o}=$top\_edge(DT$_i$)とす
ると，*E$_i{\xrightarrow[{\rm PF}]{+}}$*e$_{o}$が成立する．
\mygapskip

\proof{

DTのトップ単一弧を*e$_t$=top\_edge(DT)，DT$_i$のトップノードをn$_i$と
する(図\ref{fig:DTiObtainedFromDT})．今，DTが単一ノードからなる木，す
なわち，DT$i=$\{n$_i$\}の場合，*e$_{o}$はn$_i$に対する単一語彙弧であ
る．*E$_i$ の句ヘッドはn$_i$であるので*E$_i{\xrightarrow[{\rm
PF}]{+}}$*e$_{o}$が成立する．一方，DTがアークから成る木の場合，補題
\ref{lem:app2-4}より，*e$_t{\xrightarrow[{\rm PF}]{*}}$*e$_{o}$が言え
る．これより，圧縮弧列cs(*e$_t$)中のいづれか１つの圧縮弧Xに対して
X${\xrightarrow[{\rm PF}]{*}}$*e$_{o}$が成立する．今，定義より
*E$_i$${\in}$cs(*e$_t$)であり，*E$_i$と*e$_{o}$の句ヘッドは同一である
ため，X$=$*E$_i$である．

}
\end{lemma}

\begin{figure}[b]
 \begin{center}
  \epsfile{file=\myfigdir/DF付録２分割部分依存木＝整依存木の証明図.eps,scale=0.8}
 \end{center}
\myfiglabelskip
\myfiglabelskippre
\caption{DTの分割で得られる部分整依存木DT$_i$}
\label{fig:DTiObtainedFromDT}
\end{figure}

\begin{lemma}[分割で得る部分依存木の整依存木性]
\label{lem:app2-6}
整依存木DTの分割により得られる部分依存木DT$_i$ のルート圧縮弧を
*E$_i$，その始点と終点をそれぞれsp$_i$,tp$_i$とすると，DT$_i$は，
sp$_i$からtp$_i$の範囲を被覆する整依存木である．
\mygapskip

\proof{

DT$_i$が整共起条件と整被覆条件を満足することを示す．分割の元であるDTが
整依存木であることから，DT$_i$が整共起条件を満たすことは明らかである．
以下で整被覆条件を満足することを示す．

DT$_i$が単一ノードからなる木の場合は，定義よりDT$_i$は整依存木である．
DT$_i$がアークより成る場合，そのトップノードをn$_i$とし，DT$_i$中の任
意のノードn$_j$(n$_j{\neq}$n$_i$)を考える．n$_j={\rm dep(a}_j$)なるアー
クa$_j$ が存在する．また，a$_j{\in}$DT$_i$に対して，
gov(a$_k$)$=$n$_i$,a$_k{\xrightarrow[{\rm DT}]{*}}$a$_j$なる
a$_k{\in}$DT$_i$が存在する．今，対応弧
*e$_j=$edge(a$_j$,DT),*e$_k=$edge(a$_k$,DT)とすると，a$_k$はa$_j$と等
しいか，祖先ノードであるので補題\ref{lem:app2-4}より，
*e$_k{\xrightarrow[{\rm PF}]{*}}$*e$_j$である．一方，DTのトップ単一弧
を*e$_t$とすると補題\ref{lem:RelBetweenTopedgeAndEdge}より
*e$_t{\xrightarrow[{\rm PF}]{*}}$*e$_k$であり，cs(*e$_t$)中の圧縮弧の
うちの１つから*e$_k$に到達可能である．*e$_k$の句ヘッドはn$_i$であるので，
*E$_i{\xrightarrow[{\rm PF}]{*}}$*e$_k$である．

以上より*E$_i{\xrightarrow[{\rm PF}]{*}}$*e$_k{\xrightarrow[{\rm
PF}]{*}}$*e$_j$が成立し，n$_j$は*E$_i$ の範囲に存在する，すなわち，依
存木DT$_i$中の全てのノードはsp$_i$からtp$_i$の範囲に存在するといえる．
さらに，DT$_i$以外の部分依存木DT$_k$($k{\neq}i$)のノードはsp$_i$ から
tp$_i$の範囲に存在しないことも言える．分割元である$DT$が整被覆条件を満
足することから，依存木DT$_i$中の全てのノードはsp$_i$からtp$_i$の全ての
位置を占める．

以上より，DT$_i$は，sp$_i$からtp$_i$の範囲を整被覆する整依存木である．

}
\end{lemma}

\subsection*{［依存森の完全性・健全性の証明］}

構文木PT = \{*e$_1$,${\ldots}$,*e$_m$\}が与えられた時，それに対応する
依存木dependency\_tree(PT)を次のように定義する．

\begin{definition}
  dependency\_tree(PT) = ds(*e$_1$) ${\uplus}{\cdots}{\uplus}$ ds(*e$_m$) 

\mynoindent ここで，${\uplus}$は，基本的に和集合${\cup}$と同じであるが，
部分依存構造dsがアーク集合の場合とノード１つからなる集合の場合に対応す
るために導入された関係である．${\uplus}$は，和集合(${\cup}$)を取った結
果の要素にノードとアークが存在する場合にはノードを除外したアークのみの
集合とする．例えば，n$_i$をノード，a$_i$をアークとすると次の例のように
なる．

\begin{itemize}
\item[] \{n$_1$\}${\uplus}$\{a$_1$,a$_2$\} = \{a$_1$,a$_2$\}
\item[] \{a$_1$\}${\uplus}$\{a$_2$,a$_3$\} = \{a$_1$,a$_2$,a$_3$\}
\item[] \{n$_1$\}${\uplus}$\{\} = \{n$_1$\}
\end{itemize}

\end{definition}

{\mynoindent}なお，部分依存構造ds(*e$_i$) は部分依存構造条件を満足する
ので，上記dependency\_tree(PT)は部分依存木の結合により構成されるため，
木となる．

\mytheorembeforegap
\begin{theorem}[依存森の完全性]
\label{the:CompletenessOfPF}
統語森PF中の構文木PTに対してDT=dependency\_tree(PT)は，依存森DFに存在する整
依存木である

\proof{

DTは，依存グラフの構築アルゴリズムから，DGに含まれる．また，DTとPTの含
むノードは部分依存構造条件より1対1の対応関係があり，PTが文を被覆するの
で，DTは整被覆木である．また，DT中の全アークに関し，共起マトリックスの
構築アルゴリズムより共起関係が成立しDTは整共起依存木となる．よって，統
語森中の構文木PTに対応する整被覆整共起依存木dependency\_tree(PT)は依存
森DFに存在する．

}
\end{theorem}


\begin{theorem}[依存森の健全性]
\label{the:SoundnessOfPF}
依存森DF中の整依存木DTが与えられた時，DT=dependency\_tree(PT)なる構文木PTが統語森PFに存在する

\proof{

依存森DF中の整依存木DT，統語森PFのルート圧縮弧を*E$_{root}$とすると，
PT${\in}$parse\_trees(*E$_{root}$), dependency\_tree(PT)=DTなる構文木
PTが存在することを示す．

今，入力文の単語数をnとする．次に示すアルゴリズムは，圧縮弧*E$_r$(始点
sp$_r$，終点tp$_r$，1${\leq}$sp$_r<$tp$_r{\leq}$n)と整依存木DT(sp$_r$
からtp$_r$を被覆)が与えられた時に，構文木を構成する構文木構成アルゴリ
ズムである．これが上記条件を満たす構文木PTを構成するアルゴリズムである
ことをDTが含むアークの数に関する帰納法を用いて示す．

\myhalfskip

\hspace{-5mm}
\fbox
{
 \begin{minipage}{13.7cm}

[構文木構成アルゴリズム]

DTがアークからなる依存木の場合：
\begin{itemize}
\item[{\myitemindent}A-Step1［トップ単一弧の同定］:] 整依存木DTのトップ
単一弧top\_edge(DT)を取り出し*e$_t$とする．

\item[{\myitemindent}A-Step2［パスの取り出し］:] 与えられた圧縮弧*E$_r$ 
から*e$_t$へのパスを取り出し，パス中に含まれる*e$_t$以外の単一弧の集合
をPATHとする．

\item[{\myitemindent}A-Step3［依存木DTの分割］:] 依存木DTを
ds(top\_edge(DT))を除くことで分割し，部分依存木 DT$_i$($1{\leq}i{\leq}m$) 
ならびにルート圧縮弧*E$_i$=root\_Edge(DT$_i$)を得る．

\item[{\myitemindent}A-Step4［部分構文木計算］:] 構文木構成アルゴリズ
ムをDT$_i$,*E$_i$($1{\leq}i{\leq}m$)に適用し構文木PT$_i$を得る．

\item[{\myitemindent}A-Step5［構文木構成］：] DT,*E$_r$に対する構文木と
してPT=PATH ${\cup}$ \{*e$_t$\} ${\cup}$ PT$_1$ ${\cup}{\cdots}{\cup}$
PT$_m$ を返す．

\end{itemize}

DTが単一ノードからなる木(DT=\{n\})の場合：
\begin{itemize}
\item[{\myitemindent}N-Step1［語彙弧の同定］：] ノードnを生成した語彙弧@e$_{lex}$を得る．
\item[{\myitemindent}N-Step2［パス取り出し］：] *E$_r$からe$_{lex}$への
パスを取り出し，パス中の単一弧の集合を構文木として返す．
\end{itemize}
\myhalfskip
\end{minipage}
}

\mygapskip
\mygapskip

DTがアークからなる依存木の場合は，A-Step1〜A-Step5により構文木PTが構成
される．図\ref{fig:DttoParseTreeExplain} に構文木構成アルゴリズムの
A-Step1〜A-Step5の動作を図式的に示す．A-Step1では，図
\ref{fig:DttoParseTreeExplain}(S1)のトップ単一弧
*e$_t$($=$top\_edge(DT))を計算する．A-Step2では，図
\ref{fig:DttoParseTreeExplain} (S2)に示すように*E$_r$から*e$_t$ へ至る
パスを求め，単一弧集合PATHを得る．*E$_r$から*e$_t$へ至るパスの存在
(*E$_r{\xrightarrow[{\rm PF}]{+}}$*e$_t$)は，次のように保証される．す
なわち，*E$_r$が統語森のルート圧縮弧*E$_{root}$の場合は明らかである．
また，*E$_r$が分割により得られる圧縮弧(A-Step4の*E$_i$)の場合は，補題
\ref{lem:app2RootEdgeAndTopEdge}より成立する．また，PATH中の単一弧につ
いては，その部分依存構造は全て\{\}である．これは，DT中の全て
のノードが*e$_t$の範囲内に存在するため*E$_r$ と*e$_t$の範囲が等しいこ
とから明らかである．これより次が成立する．
$$dependency\_tree(PATH) = \{\} \eqno{(A)}$$
A-Step3では，DTの分割を行い図\ref{fig:DttoParseTreeExplain}(S3)に示す
ようにDT$_i$,*E$_i$($1{\leq}i{\leq}m$) を得る．この時，補題
\ref{lem:app2-6}より，DT$_i$は*E$_i$の範囲を被覆する整依存木であるので，
A-Step4において再帰的に構文木構成アルゴリズムを適用できる．A-Step5にお
いて構文木PTを計算する（図\ref{fig:DttoParseTreeExplain}(S5))．PT$_i$
が構文木であればPTが構文木であることは，構文木の定義より明らかである．

DTが単一ノードからなる木の場合は，N-Step1,N-Step2により構文木PTを得る．
*E$_r$からe$_{lex}$へのパスの存在は，A-Step1の説明と同じ理由で保証され
る．

\mygapskip
以上のようにして構文木生成アルゴリズムにより生成される構文木PTが
DT=dependency\_tree(PT)であることは以下のように示される．

まず，１ノードからなる依存木DT=\{n$_r$\}に対しては，アルゴリズムは，
N-Step2で構文木PTを生成する．PTは，１ノードn$_r$をのみを含む構文木であ
り，前記dependency\_treeの定義よりdependency\_tree(PT)=\{n$_r$\}である．
次にDTがアークからなる木の場合を示す．構文木構成アルゴリズム，
dependency\_treeの定義，(A)より，次のようになる．

\mygapskip
\hspace{5mm}dependency\_tree(PT)

\hspace{7mm}= dependency\_tree(PATH ${\cup}$ \{*e$_t$\} ${\cup}$PT$_1$ ${\cup}{\cdots}{\cup}$ PT$_m$) 

\hspace{7mm}= dependency\_tree(PATH)${\uplus}$dependency\_tree(\{*e$_t$\}) ${\uplus}$dependency\_tree(PT$_1$)${\uplus}{\cdots}$

\hspace{11mm}${\uplus}$ dependency\_tree(PT$_m$)

\hspace{7mm}= dependency\_tree(\{*e$_t$\}) ${\uplus}$ dependency\_tree(PT$_1$) ${\uplus} {\cdots} {\uplus}$ dependency\_tree(PT$_m$) 

\mygapskip

{\mynoindent}今，A-Step4において各DT$_i$,*E$_i$に対する構文木PT$_i$が次を満たすと仮定する．

\mygapskip
\hspace{5mm}dependency\_tree(PT$_i$)=DT$_i$  (1${\leq}i{\leq}$m)
\mygapskip

{\mynoindent}するとA-Step5の構文木PTが生成する依存木は次のようにDTとなる．
\mygapskip
\hspace{5mm}dependency\_tree(PT)

\hspace{7mm}= ds$_t$ ${\uplus}$ DT$_1$ ${\uplus}{\cdots}{\uplus}$ DT$_m$

\hspace{7mm}= DT
\mygapskip


}
\end{theorem}

\begin{figure}[h]
 \begin{center}
  \epsfile{file=\myfigdir/DF付録２DTに対する構文解析木の構成説明図.eps,scale=0.8}
 \end{center}
\myfiglabelskip
\myfiglabelskippre
\caption{整依存木とルート圧縮弧からの構文木の生成}
\myfiglabelskippost
\label{fig:DttoParseTreeExplain}
\end{figure}



\end{document}
