\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}，LinkGrammar\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:HeadedParseForest)，依存森(DF:DependencyForest)について構築法を示し，それらに完全性と健全性が成立することを示す．また，例文解析実験により，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-formedinterpretation)と呼ぶ．最適解釈の探索は各レベル毎に定義可能であり，各レベルの選好知識を利用して，そのレベルの最適解釈を取り出すことができる．先に述べたように文解析の深さ，出力をどうするかはアプリケーションが基本的に規定する事項である．例えば，同じ機械翻訳でも文の構造表現として同属言語の場合は句構造表現がよいが，語族が違うと依存構造表現が適切であったりする．また，解釈リンケージを利用することにより，上位レベルで最適な解釈を選択し，その解釈に対応する下位レベルの解釈を下位レベルの最適解釈として取り出す方法も考えられる．例えば，意味解析結果として最適な解釈に基づいたタガーなどが自然に実現できる．\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:WordPosPair)と呼ぶ．単語timeは``time/v'',``time/n''等の語品詞を持つ．}，{\bfヘッド付き統語森}，{\bf機能依存森}，{\bf意味依存森}の４つの圧縮共有データ構造により，それぞれ，語品詞系列，構文木(句構造)，機能依存木，意味依存木の解釈の集合を保持する．それぞれを計算する処理を形態素解析，構文解析，構造生成，意味構造化と呼ぶ．各レベルのデータ構造の概要を図\ref{fig:PDGPackedSharedDataStructures}に示す．PDGでは，単語に対する解釈のレベルとして単語，語品詞，{\bf語彙概念}の３階層を採用し，各語に語彙情報として付与されていると想定している．語品詞トレリスは語品詞の隣接関係の解釈を表現する語品詞系列を保持する．ヘッド付き統語森は，後に述べるが，語や句のカテゴリの下位範疇化(あるいは系列関係)を表現する構文解析木を保持する．句構造頻度の選好知識，数の一致などの構文的制約など記述できる\footnote{数の一致などの制約を依存木のレベルで記述することも可能であり，両者で記述してもかまわない．それは実際の文法知識設計の課題である．一般的には制約知識は可能な限り下位のレベルで処理することが無駄な仮説生成の抑制に繋がるため効率的である．}．機能依存森は語品詞間の機能依存関係を表現する機能依存木を保持し，意味依存森は語彙概念間の意味関係を表現する意味依存木を保持する．以下では簡略のため単に依存森と表記した場合は，機能依存森を示す．各レベルのデータ構造に対してそれぞれの選好知識により優先度を与え，これをデータ構造間の対応関係（解釈リンケージ）を通じて統合し，最終的には，最適解釈探索により最も確からしい解釈（意味依存木）が計算される\cite{Hirakawa05d_j}．現在，依存森のレベルまでの処理システムが試作されており，最適解釈探索も依存森に対して行われ依存木を出力するモデルとなっている．意味依存森レベルは今後の課題とし，以下本稿では依存森までのモデルを対象とする．多レベル構成により他のレベルの知識を活用することが可能となる．例えば，依存関係をベースとした単一レベル圧縮共有構造モデルであるCDGは，基本的に全てのノード間に全ての依存関係(仮説)を生成してeliminativeparsingを行う．解釈の枝刈りを行わないという優れた利点があるが生成解釈数が多く効率面で問題があり，改善手法が提案されている\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もこれを利用する．文脈自由文法で入力文を解析し文の可能な解釈全体を得る手法は広く知られており，例えば，富田により，グラフスタックを用いた構文解析手法と共に文の句構造解釈(構文木)全体を効率的に保持する圧縮共有統語森(PackedSharedParseForest)が提案されている\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構文グラフ}(SyntacticGraph)を提案した\cite{Seo89,Rim90}．構文グラフは，PDGの共有データ構造として有望であったが，大きな問題もありそのまま採用することはできないことが判明した．構文グラフは，単語間の依存関係をベースに文の可能な解釈を圧縮共有する枠組みである．構文グラフは，語品詞に対応するノードとノード間の依存関係を表現する名前付きアークで構成される有向グラフであり，{\bf排他マトリックス}(EM:ExclusionMatrix)と呼ばれるデータと組になって，入力文に含まれる依存構造の集合（文の解釈の集合）を表現する．構文グラフは，３次組(Triple)と呼ばれる，アーク名とその両端のノード(語品詞，表層位置などを持つ)の組からなる集合で表現される．図\ref{fig:KoubunGraph}は，``Timeflieslikeanarrow''に対する構文グラフ/排他マトリックスである．アークの括弧中の番号はその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:DependencyGraph)と{\bf共起マトリックス}(CM:Co-occurrenceMatrix）より成る．以下，依存森の構造と依存木について説明する．\subsubsection{依存グラフと共起マトリックス}\begin{figure}[b]\begin{center}\epsfile{file=\myfigdir/DF_TimeFliesに対する初期依存森.eps,scale=0.75}\end{center}\myfiglabelskip\caption{``Timeflieslikeanarrow''に対する初期依存森}\label{fig:IDF}\end{figure}図\ref{fig:IDF}は，``Timeflieslikeanarrow''に対する依存森の例である.依存グラフは，語品詞に対応するノードと１つのルートノードrootならびに，ノード間の依存関係を表現する名前付きアークより構成される．依存グラフは，rootをルートノードとする有向グラフであり，実際には，アークとその両端のノードの組からなる{\bf依存片}(dependencypiece)\footnote{依存片とアークは1対1対応するので，特に区別の必要がない場合は依存片をアークと記述する．}の集合として表現する.アークは，アーク名とIDを有す．アークの元側を{\bf依存ノード}(dependentあるいはmodifier)，先側を{\bf支配ノード}(governorあるいはmodificand)と呼ぶ．また，ノードには，表層位置などの情報も含まれている．アークの数を{\bf依存森のサイズ}と呼ぶ．また，依存グラフの部分集合で木構造を成すアーク集合が依存木であり，文や句の解釈を表現する．依存グラフは複数の依存木を含む圧縮共有データ構造となっている．共起マトリックスは，アークIDで示されたアーク集合を行と列に取り，アーク間の共起関係を規定する．共起マトリックスCM($i$,$j$)が○の場合に限り，アーク$i$と$j$は１つの依存木（解釈）において共起可能であるという制約を表現する．共起関係は双方向関係であり，CMは対称行列となる．\subsubsection{整依存木}依存森中の依存木のうち次の整依存木条件を満たす依存木を{\bf整依存木}(Well-formedDependencyTree)と呼ぶ．\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-coveredDependencyTree)と呼ぶ.また，(c)を満たす依存木を{\bf整共起依存木}(Well-cooccurredDependencyTree)と呼ぶ．整依存木の集合が入力文に対する解釈の集合となる．図\ref{fig:IDF}の依存森では，「時は矢のように過ぎる」，「時ハエは矢を好む」，「矢のようにハエを計れ」，「矢のようなハエを計れ」に対応する4つの整依存木が存在する．なお，ノード１つからなる依存木(アークが存在しない)も，整依存木として扱う．この場合のみ依存木はノード１つからなる集合となる．\subsubsection{初期依存森と縮退依存森}複数の解釈に対するアークの共有の度合いによって，同じ依存木の集合を表すサイズの異なった複数の依存森を構成可能である．詳細は後述するが，PDGでは，{\bf初期依存森}(InitialDependencyForest)と，それから変換して得られる{\bf縮退依存森}(ReducedDependencyForest)の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において文法規則は，可能な句構造の定義と，句構造から依存構造へのマッピングとを規定する拡張文脈自由文法(extendedCFG)で記述される．文法規則は，次の形式をしている．\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句ヘッド}(phrasehead)と呼ばれ，主構成素(headconstituent)に相当し，{\bf規則ボディ}(rulebody)である``$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}例文``Timeflieslikeanarrow''を解析するための文法規則と辞書を図\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-upChartParsingのアルゴリズムをベースに，依存構造の生成が可能となるよう，弧の構成やアルゴリズムを拡張することにより実現している．\subsubsection{弧の構成と例}ChartParsingにおいて，弧は，{\bf始点}(FP)，{\bf終点}(TP)，{\bf規則ヘッド頂点}(C)，{\bf既存構成素列}(FCS)，{\bf残り構成素列}(RCS)の５次組$<$FP,TP,C,FCS,RCS$>$から構成される．文法規則のヘッドは，規則ヘッド頂点に，規則ボディは，既存構成素列と残り構成素列に対応し，ドット（・）で規則ボディ内の区切りを表現し，次の例のような形式で図式的に表現される．$<$0,1,s$\rightarrow$np・vppp$>${\mynoindent}この弧は，文法規則``s$\rightarrow$npvppp''から生成される例であり，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の構文解析では，文法規則の部分依存構造に対する処理と複数の弧の圧縮共有処理の２点で拡張を行っている．依存構造構築のため，通常のChartParsingの弧に句ヘッド(PH)と部分依存構造(DS)を追加しており，模式的に示すと次のようになる．通常の弧：$<$0,1,s$\rightarrow$np・vppp$>$PDGの弧：$<$0,1,s/PH$\rightarrow$np/NP・vp/PHpp/PP:DS$>${\mynoindent}\ref{sec:bunpoukisoku}節で述べたように，PHが句ヘッド(ノード)，DSが部分依存構造(アーク集合)を示す．また，詳細は後述するが，不活性弧については圧縮共有を行うため，複数の弧を１つに纏めた{\bf圧縮弧}というデータ構造を利用する．圧縮弧は，既存構成素列(FCS)と部分依存構造(DS)の部分を，それぞれのリストに拡張したものである．圧縮弧に対して，１つの構成素列と部分依存構造を持つ弧を{\bf単一弧}と呼ぶ．圧縮弧は，共有可能な単一弧の集合と等価である．次にこれらの対応関係を模式的表現で例示する．単一弧：$<$0,5,s/PH$\rightarrow$np/NPvp/PHpp/PP・:DS1$>$$<$0,5,s/PH$\rightarrow$np/NPvp/PH・:DS2$>$圧縮弧：$<$0,5,s/PH$\rightarrow$[[np/NPvp/PHpp/PP],[np/NPvp/PH]]・:[DS1,DS2]$>${\mynoindent}この例で，PHは句ヘッド，[np/NPvp/PHpp/PP],[np/NPvp/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$)を{\bfCSDSペア}と呼ぶ．CSDSペアは，上記の単一弧に対応している．図\ref{fig:ArcStructure}の弧E1〜*E3は，名詞句規則に対応する弧が解析が進むにつれて生成されてゆく例である．弧*E3は，``anarrow''を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語彙弧}(lexicaledge)と呼ぶ．語彙弧の部分依存構造は，ノード１つからなる集合である．語彙弧は@をつけて@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を用いた一般的なChartParsingアルゴリズム\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ルート弧}(rootedge)と呼ぶ．\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{``timeflieslikeanarrow''に対する統語森}\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)の構成素列``vpnp''の部分から生成されている．(R9),(R10)は，前置詞句の有無という差はあるが，``vpnp''の関係は２つの規則で同一であり，依存構造の解釈という観点から同値アークは等価であると言える\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付きのアークからなる依存木を明示する時は{\bfID付き依存木}と記述する．また，アーク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}にマージの例を共起マトリックスの形式で模式的に示す．以下の議論で依存木の集合やアークの集合などを定義するが，マージ操作の前後の区別を示す場合には，``wrtDG,CM''あるいは``wrtDF''(wrt:withrespectto)の表現を付けて示す．例えば，以下で定義するアーク$X$を含む整依存木の集合dts($X$)に対して，``dts($X$)wrtDG,CM''，``dts($X$)wrtDG',CM'''はそれぞれマージ前と後の依存森に対する集合を示し，``dts($X$)wrtDG,CM=dts($X$)wrtDG',CM'''は，マージの前後でdts($X$)の値が同じことを示す．簡便のため，以下では``wrtDG,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付き依存木が存在する条件を{\bfID付き依存木の増加条件}(``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)$=$○wrtDF',CM(B$_i$,U)=○wrtDF'である．今，CM(Y,U)${\neq}$○wrtDFであるアークUが存在しない,すなわちCM(Y,U)$=$○wrtDF,U${\in}$Rを仮定すると，DT$_y$=\{Y,B$_i$\}+Rは，共起条件を満足する整依存木となる．DT$_x$とDT$_y$は，同値アークX,Yが異なるだけなので，DT$_x$は新たな依存木ではない．よって，新たな依存木DT$_x$には少なくとも１つCM(Y,U$_i$)${\neq}$○wrtDFなる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[\myitemindentsame\_position($U$,$V$)]：アーク$U$,$V$の依存ノードの位置が等しい\item[\myitemindentdts($S$)wrt$DG$,$CM$]：$CM$の共起制約を満たしながら，アーク集合$S{\subset}DG$から得られるID付き整依存木の集合\item[\myitemindentco($U$)wrt$DG$,$CM$]：アーク$U$あるいは$U$と共起するアーク集合，\{$X$${\mid}$$X$=$U$またはCM($X$,$U$)=○,$X{\in}DG$\}である．\item[\myitemindentdts\_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)wrtDG',CM'$=$\{\}の判定を行えば良い．\subsubsection{汎化依存木の増加条件}既に述べたようにID付き依存木の増加条件は汎化依存木の増加条件の必要条件である．このため，ID付き依存木の増加条件を満たす場合，すなわち，dts\_with\_arcs(X,A,B)wrtDF'($=$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}最終的に縮退依存森に同値アークが残る例として付録１の``Tokyotaxidrivercallcenter''に対するアルゴリズムの動作を示す．例文に対する初期依存森を図\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)wrtDG',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)wrtDG',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)のパタンもあり，``Timeflieslikeanarrow''のような多品詞の曖昧性と組み合わさって種々の構文解釈を生成する．また，(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)曖昧性の例文``Isawagirlwithatelescopeintheforest''に対する依存森である．依存グラフのアークには，アーク名/アーク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(``sawagirl''に対応)で，句ヘッドが[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)：スコープが異なる：ノードの範囲とは無関係にマージ可能としている（できる場合とできない場合の弁別を入れることが考えられる）**newarcid:arc_share(obj-15,[girl]-n-3,[saw]-v-1)173:[1,7]vp/([saw]-v-1)-->[109163]*:[[arc(obj-15,[girl]-n-3,[saw]-v-1)]]**newarcid:arc_share(obj-5,[girl]-n-3,[saw]-v-1)135:[1,4]vp/([saw]-v-1)-->[109126]*:[[arc(obj-5,[girl]-n-3,[saw]-v-1)]]**newarcid:arc_share(obj-28,[girl]-n-3,[saw]-v-1)222:[1,10]vp/([saw]-v-1)-->[109203]*:[[arc(obj-28,[girl]-n-3,[saw]-v-1)]]163:[2,7]np/([girl]-n-3)-->[126161]*:[[arc(npp-13,[with]-pre-4,[girl]-n-3)]]126:[2,4]np/([girl]-n-3)-->[119122]*:[[arc(det-4,[a]-det-2,[girl]-n-3)]]203:[2,10]np/([girl]-n-3)-->[163199]*:[[arc(npp-25,[in]-pre-7,[girl]-n-3)]]--npp-13の同値アーク：163:[2,7]np/([girl]-n-3)-->[126161]*:[[arc(npp-13,[with]-pre-4,[girl]-n-3)]]228:[2,10]np/([girl]-n-3)-->[126213]*:[[arc(npp-32,[with]-pre-4,[girl]-n-3)]]======Numberofvarioustrees========[ParseForest](a)ParseForestSize:25(b)Numberofcollectionofparsetrees:5(c)Numberofsetofparsetrees:5[DependencyForest](I-1)InitialDFsize:18(I-2)InitialDFID-treecollectionnumber:5(I-3)InitialDFID-treesetnumber:5(I-4)InitialDFGeneralized-treenumber:5(R-1)ReducedDFsize:13(R-2)ReducedDFID-treecollectionnumber:5(R-3)ReducedDFID-treesetnumber:5(R-4)ReducedDFGeneralized-treenumber: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}は，接続詞のスコープ曖昧性を含む名詞句``EarthandMoonorJupitorandGanymede''に対する依存森である．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)======Numberofvarioustrees========[ParseForest](a)ParseForestSize:18(b)Numberofcollectionofparsetrees:5(c)Numberofsetofparsetrees:5[DependencyForest](I-1)InitialDFsize:17(I-2)InitialDFID-treecollectionnumber:5(I-3)InitialDFID-treesetnumber:5(I-4)InitialDFGeneralized-treenumber:5(R-1)ReducedDFsize:10(R-2)ReducedDFID-treecollectionnumber:5(R-3)ReducedDFID-treesetnumber:5(R-4)ReducedDFGeneralized-treenumber:5\end{comment}\subsubsection{構造解釈の曖昧性}\label{sec:AmbiguityInStructuralInterpertation}図\ref{fig:DFForMyHobbyIs}は，構造解釈上の曖昧性を含む例文``Myhobbyiswatchingbirdswithtelescope''に対する依存森である．この例も，多品詞曖昧性を持たないが，``be''動詞の解釈(コピュラか進行形か)，``watchingbirds''の解釈($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)-->[121177]*:[[arc(obj-27,[birds]-n-4,[watching]-ving-3)]]188:<3,7>np/([watching]-ving-3)-->[121177]*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)]]======Numberofvarioustrees========[ParseForest](a)ParseForestSize:23(b)Numberofcollectionofparsetrees:10(c)Numberofsetofparsetrees:8[DependencyForest](I-1)InitialDFsize:24(I-2)InitialDFID-treecollectionnumber:10(I-3)InitialDFID-treesetnumber:10(I-4)InitialDFGeneralized-treenumber:10(R-1)ReducedDFsize:16(R-2)ReducedDFID-treecollectionnumber:10(R-3)ReducedDFID-treesetnumber:10(R-4)ReducedDFGeneralized-treenumber: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)======Numberofvarioustrees========[ParseForest](a)ParseForestSize:23(b)Numberofcollectionofparsetrees:10(c)Numberofsetofparsetrees:8[DependencyForest](I-1)InitialDFsize:24(I-2)InitialDFID-treecollectionnumber:10(I-3)InitialDFID-treesetnumber:10(I-4)InitialDFGeneralized-treenumber:10(R-1)ReducedDFsize:16(R-2)ReducedDFID-treecollectionnumber:10(R-3)ReducedDFID-treesetnumber:10(R-4)ReducedDFGeneralized-treenumber: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つの構文木が複数の依存木に対応するのは，１つの構文構造に対する解釈が複数存在するような場合であり，例えば，``watchingbird''という文に対して動詞の現在分詞形が名詞を修飾しているという１つの構文構造をアサインした時，依存構造として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}#ParseTree[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####DependencyStructure[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]####DependencyStructure[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(ConbinatoryCategorialGrammar)においては，多数のspuriousambiguityが存在するという類似の問題があり，標準形の木のみをただ１つ解析結果として出力する手法が提案されている\cite{Eisner96b}．この手法では，解析木の末端のカテゴリ(CCGのカテゴリ)が同一である木は同じ意味構造を有するという定義の基で，同じ意味を表す木（同じ意味クラスの木）はただ1つだけ取り出すことができる．PDGの枠組みでは，文の解釈は(汎化)依存木で表現するため，同一の(汎化)依存木を持つ構文木を同じクラスの木とするという関係になっていると見ることができる．図\ref{fig:DFContainingNtoOneMapping}は，``Shecuriouslysawacatintheforest''を例文文法で解析して得られる依存森であり，見せかけの曖昧性を含んでいる．共起制約が掛かっているのは依存先曖昧性に対応する$npp17$,$vpp18$に対する単一役割制約のみであり，``intheforest''の依存先が異なる2つの依存木(解釈)が存在している．統語森は3つの構文木，初期依存森は3つのID付き依存木(2つの汎化依存木)，縮退依存森は2つのID付き依存木(2つの汎化依存木)を含んでいる．見せかけの曖昧性は，動詞句に対する２つの修飾句に関する規則(R17),(R18)の適用順序の違いにより生じている．図\ref{fig:SuriousNtoOneMapping}に構文木と依存木を示す．\begin{comment}======Numberofvarioustrees========[ParseForest](a)ParseForestSize:19(b)Numberofcollectionofparsetrees:3(c)Numberofsetofparsetrees:3[DependencyForest](I-1)InitialDFsize:12(I-2)InitialDFID-treecollectionnumber:3(I-3)InitialDFID-treesetnumber:3(I-4)InitialDFGeneralized-treenumber:2(R-1)ReducedDFsize:9(R-2)ReducedDFID-treecollectionnumber:2(R-3)ReducedDFID-treesetnumber:2(R-4)ReducedDFGeneralized-treenumber: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{``softlyknocktwice''の解釈候補softly(twice(knock))とtwice(softly(knock))は意味的に等しいが，``intentionallyknocktwice''の解釈候補``intentionally(twice(knock))''と``twice(intentionally(knock))''は意味が異なる．}や限量詞や数の解釈に関わる曖昧性\footnote{「3人が10本の花を買った」において，「各人が10本の花を買った」か「3人全員で10本の花を買った」のようなモデル理論的な意味解釈の曖昧性であり，句構造や依存構造では表現が困難．}なども考慮する必要があり，依存構造の同一性で意味の同一性を判定することはあくまで１つの側面に関する同一性の判定に過ぎない．\cite{Meluk88}は，依存構造での自然な構造表現が困難なケースを挙げ，それらには句構造では自然に表現できるもの，句構造でも自然に表現できないもの(句構造，依存構造の両方とも能力不足)があることを示している．PDGは，句構造と依存構造を扱うため，少なくとも前者については枠組みとしての検証が必要と考える．前者は，依存構造において句のヘッドワードに修飾語が存在する場合にそれがヘッドワードのみを修飾するのか，それともヘッドワード以下の全体を修飾するのかというスコープの曖昧性を表現できないという，標準的な依存構造一般に存在する問題（ここでは{\bf修飾スコープ問題}と呼ぶ）である．図\ref{fig:DFContainingNtoOneMappingRealAmbiguity}に``EarthandJupiterinSolarSystem''に対する依存森を示す．この文には，前置詞句が並列句のヘッド``Jupitor''のみを修飾する解釈と``EarthandJupitor''全体を修飾する解釈の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は，全てに記述されるものではなく，対象は曖昧性が生じる並列構造(conjoinedstructure)，``not'',``only''と言ったオペレータ語(operatorword)などに限定されている．依存構造をベースにした大規模文法を有する機械翻訳システム\cite{Amano89}では，Groupingに相当する仕組み\footnote{スコープノードという特殊ノードの導入により依存構造の範囲を必要に応じて記述可能としている．}を導入している．工学的観点から言うと，一般にどの程度詳細に深いレベルの解釈構造を作るかという設定は，目的とするアプリケーションにより異なる．機械翻訳アプリケーションにおいては，修飾スコープ問題については並列構造に対する対応だけで実システムが構築されており\footnote{これは英日システムの例である．より詳細には言語対によっても要求レベルは異なってくると考えられる．例えば，英語とフランス語といった同族言語の場合は構文的曖昧性を保持したまま目的言語へ変換するという戦略を取ることにより修飾スコープ問題を回避できる可能性がある．}，前記Grouping対象の限定は経験的に妥当であると考えている．また，修飾スコープ問題は，言語によって様相が異なってくる．例えば，ロシア語では形容詞の数，名詞の文法的格が一致(agreement)や支配(government)により統語的に導入され，解釈が決定されるために修飾スコープ問題が起こらないことがある\cite{Meluk88}．また，日本語では，係り受け文法(依存構造文法)に被修飾語は修飾語の左に位置するという制約が存在するため，そもそも修飾スコープ問題が発生せず，依存構造(係り受け構造)の表現力の問題として意識されることがほとんどない．PDGでは同値アークがノードのスコープの違いを表現しているので，依存構造の修飾スコープ問題は，Groupingの概念を同値アークに導入するという拡張により対応できる可能性があり，今後の検討課題である．\begin{comment}======Numberofvarioustrees========[ParseForest](a)Numberofcollectionofparsetrees:2(b)Numberofsetofparsetrees:2[DependencyForest](I-1)InitialDFsize:7(I-2)InitialDFID-treecollectionnumber:2(I-3)InitialDFID-treesetnumber:2(I-4)InitialDFGeneralized-treenumber:1(R-1)ReducedDFsize:5(R-2)ReducedDFID-treecollectionnumber:1(R-3)ReducedDFID-treesetnumber:1(R-4)ReducedDFGeneralized-treenumber:1------\end{comment}\begin{comment}依存構造での表現力の問題D-language単独で表現が困難な構造がある．節のヘッドワードを修飾している要素Ｘがある構造と，Ｘが句全体を修飾している構造との意味的な対比．hischeerfulnessandhisaccentastonishing(1a)hischeerfulnessand{hisaccentastonishing}(1b){hischeerfulnessandhisaccent}astonishingこの例は単純にスコープの問題で句構造では，表現されている．(平川)BobandDick'snovels(2a)novelswrittenbytheteam``Bob+Dick''{BobandDick}'snovels(2b)novelswrittenbyBobandnovelswrittenbyDick{Bob}and{Dick'snovels}→スコープの問題としてこの例は表現されていない要素の問題で単純にスコープの問題として扱うことは困難で，句構造なら表現できるというものでもない．3つの方法(a)ラベルに情報をつける→良くないmodif(ヘッドのみ)v.s.phrase-modif(句全体)(b)(1b)(2b)を省略の問題であるとしてとらえ全体構造で表現(1b'){hischeerfulnessastonishing}and{hisaccentastonishing}(2b'){Bob'snovels}and{Dick'snovels}(c)ノード属性の属性マーカを付けて弁別(注：次は正確でない．本と違う)ロシア語では，語のinflectionで数の情報が表現され，次の２文の構造が弁別される．NewYork(MASC.SG,NOM)andChicago(MASC.SG.NOM)University[masc](PK.NOM)(ニューヨークとシカゴの各１つの大学）NewYork(PL.NOM)andChicago(PL.NOM)University[masc](PK.NOM)(ニューヨークとシカゴの各いくつかの大学）-----・句構造でも自然に表現できないもの(両方とも能力不足)とできるものがある・表現できるものスコープの曖昧性・MelukではGroupingという概念を導入している(Groupingは論理的にフレーズと等しい)（=スコープノードと同じ)Groupingは，全てに入れているのではなく，限定されている-conjoinedstructure(曖昧性の出る場合)-``operator''word(not,onlyなど)・アプリケーションにも依存する(弁別の必要がないアプリケーションもある)大規模な英語文法では，conjoinedstructureのみにスコープノードで対応するだけで実用上ほぼ問題なく実現できている．・このヘッドワード修飾か全体修飾かというスコープの問題は対象言語によって異なる．ロシア語では形容詞の数，名詞の文法的格がsyntacticallyに導入されている(byagreementandgovernment)日本語では発生しない(係り受け文法の制約の存在）今後の課題．\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}非交差制約(Projectivityconstraint)\footnote{Projectivityの条件は，「依存関係が交差しない」ことの他に「トップノードがカバーされることはない」の２つであるが，文頭(または文末)に特殊なルートノードを想定することにより，この２番目の条件は不必要となる．日本語はトップノードが文末に位置するためProjectivityのためにはルートノードは必要としない．}は，多くの依存構造解析システムにより受け入れられている制約であり，これらシステムはProjectiveparserと呼ばれる．Projectiveparserはnon-projectiveな構造を持つ文の解析に失敗する．種々の言語の大半の文はprojectiveであるが，いくつかのタイプのnon-projectiveな文が多くの言語に存在する\cite{Meluk88}．英語では，``ShesawthecatcuriouslywhichwasPercian''，日本語では「私は本を東京に買いに昨日行きました」などがnon-projectiveな構造を持つ文である．英語に比べて自由度の高い語順を持つチェコ語の解析において，Non-projectiveparserがprojectiveparserに対して総合的な精度で上回るという報告もある\cite{McDonald05}．しかしながら，単純にNon-projectiveな解釈を許すだけでは，全体として性能の劣化に繋がる恐れもあり多くのシステムでは対象をprojectiveな依存木に限定していると思われる．PDGでは，\ref{sec:bunpoukisoku}節で述べたように，構成素列(規則ボディ)とアーク集合(部分依存構造)のマッピングが拡張CFG規則で定義される．この記述の枠組みにより，Allornothingではなく，規則により定義されたnon-projectiveな構造のみをWell-formedな構造として共起マトリックスの共起制約として表現することが可能である．これをコントロールされたnon-projectivityと呼ぶこととする．図\ref{fig:GrammarForExamples}の(R19)はNon-projectiveな構文に対する文法規則であり，関係節の前に副詞が挿入された構文に対応している．図\ref{fig:Non-projectiveDT}に``ShesawthecatcuriouslywhichwasPercian''に対して例文文法が生成する依存森を示す．依存森には，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}{Amanoet~al.}{1989}]{Amano89}Amano,S.,Hirakawa,H.,Nogami,H.,\BBA\Kumano,A.\BBOP1989\BBCP.\newblock\BBOQTheToshibaMachineTranslationSystem\BBCQ\\newblock{\BemFutureComputingSystems},{\Bbf2}(3).\bibitem[\protect\BCAY{Bikel}{Bikel}{2004}]{Bikel04}Bikel,D.~M.\BBOP2004\BBCP.\newblock\BBOQIntricaciesofCollins'ParsingModel\BBCQ\\newblock{\BemComputationalLinguistics},{\Bbf30}(4),\mbox{\BPGS\479--511}.\bibitem[\protect\BCAY{Carroll\BBA\Charniak}{Carroll\BBA\Charniak}{1992}]{Carroll92}Carroll,G.\BBACOMMA\\BBA\Charniak,E.\BBOP1992\BBCP.\newblock\BBOQTwoExperimentsonLearningProbablisticDependencyGrammarsformCorpora\BBCQ\\newblockTechnicalreport,DepartmentofComputerScience,Brownuniversity.\bibitem[\protect\BCAY{Charniak}{Charniak}{2000}]{Charniak00}Charniak,E.\BBOP2000\BBCP.\newblock\BBOQAmaximum-entropy-inspiredparser\BBCQ\\newblockIn{\BemProceedingsofthe1stConferenceoftheNorthAmericanChapteroftheAssociationforComputationalLinguistics},\mbox{\BPGS\132--139}.\bibitem[\protect\BCAY{Clark\BBA\Curran}{Clark\BBA\Curran}{2003}]{Clark03}Clark,S.\BBACOMMA\\BBA\Curran,J.~R.\BBOP2003\BBCP.\newblock\BBOQLog-LinearModelsforWide-CoverageCCGParsing\BBCQ\\newblockIn{\BemProceedingsoftheSIGDATConferenceonEmpiricalMethodsinNaturalLanguageProcessing(EMNLP'03)},\mbox{\BPGS\97--104}.\bibitem[\protect\BCAY{Collins}{Collins}{1999}]{Collins99}Collins,M.\BBOP1999\BBCP.\newblock{\BemHead-DrivenStatisticalModelsforNaturalLanguageParsing}.\newblockPh.D.\thesis,UniversityofPennsylvania.\bibitem[\protect\BCAY{Eisner}{Eisner}{1996}]{Eisner96b}Eisner,J.\BBOP1996\BBCP.\newblock\BBOQEfficientNormalFormParsingforCombinatoryCategorialGrammar\BBCQ\\newblockIn{\BemProceedingsofthe34thAnnualMeetingoftheACL},\mbox{\BPGS\79--86}.\bibitem[\protect\BCAY{Harper,Hockema,\BBA\White}{Harperet~al.}{1999}]{Harper99}Harper,M.~P.,Hockema,S.~A.,\BBA\White,C.~M.\BBOP1999\BBCP.\newblock\BBOQEnhancedconstraintdependencygrammarparsers\BBCQ\\newblockIn{\BemProceedingsoftheIASTEDInternationalConferenceonArticialIntelligenceandSoftComputing}.\bibitem[\protect\BCAY{Hirakawa}{Hirakawa}{2001}]{Hirakawa01}Hirakawa,H.\BBOP2001\BBCP.\newblock\BBOQSemanticDependencyAnalysisMethodforJapaneseBasedonOptimumTreeSearchAlgorithm\BBCQ\\newblockIn{\BemProceedingsofthePACLING2001},\mbox{\BPGS\117--126}.\bibitem[\protect\BCAY{Hirakawa}{Hirakawa}{2005}]{Hirakawa05d_j}Hirakawa,H.\BBOP2005\BBCP.\newblock\BBOQGraphBranchAlgorithm:AnOptimumTreeSearchMethodforScoredDependencyGraphwithArcCo-occurrenceConstraints\BBCQ\\newblock\Jem{情報処理学会,自然言語処理研究会NL-169-16},\mbox{\BPGS\101--108}.\bibitem[\protect\BCAY{Kaplan}{Kaplan}{1989}]{Kaplan89}Kaplan,R.\BBOP1989\BBCP.\newblock\BBOQTheFormalArchitectureofLexical-FunctionalGrammar\BBCQ\\newblock{\BemJournalofInformationScienceandEngineering},{\Bbf5},\mbox{\BPGS\305--322}.\bibitem[\protect\BCAY{Lafferty,Sleator,\BBA\Temperley}{Laffertyet~al.}{1992}]{Lafferty92}Lafferty,J.,Sleator,D.,\BBA\Temperley,D.\BBOP1992\BBCP.\newblock\BBOQGrammaticalTrigrams:aProbabilisticModelofLinkGrammar\BBCQ\\newblockIn{\BemProbabilisticApproachestoNaturalLanguage}.\bibitem[\protect\BCAY{Lee\BBA\Choi}{Lee\BBA\Choi}{1997}]{Lee97}Lee,S.\BBACOMMA\\BBA\Choi,K.~S.\BBOP1997\BBCP.\newblock\BBOQReestimationandBest-FirstParsingAlgorithmforProbablisticDependencyGrammars\BBCQ\\newblockIn{\BemProceedingsoftheFifthWorkshoponVeryLargeCorpora},\mbox{\BPGS\41--55}.\bibitem[\protect\BCAY{Maruyama}{Maruyama}{1990}]{Maruyama90}Maruyama,H.\BBOP1990\BBCP.\newblock\BBOQConstraintDependencyGrammarandItsWeakGenerativeCapacity\BBCQ\\newblock{\BemComputerSoftware}.\bibitem[\protect\BCAY{Matsumoto,Tanaka,Hirakawa,Miyoshi,\BBA\Yasukawa}{Matsumotoet~al.}{1983}]{Matsumoto83}Matsumoto,Y.,Tanaka,H.,Hirakawa,H.,Miyoshi,H.,\BBA\Yasukawa,H.\BBOP1983\BBCP.\newblock\BBOQBUP:ABottom-UpParserEmbeddedinProlog\BBCQ\\newblock{\BemNewGenerationComputing},{\Bbf1}(2),\mbox{\BPGS\145--158}.\bibitem[\protect\BCAY{McDonald,Crammer,\BBA\Pereira}{McDonaldet~al.}{2005}]{McDonald05}McDonald,R.,Crammer,K.,\BBA\Pereira,F.\BBOP2005\BBCP.\newblock\BBOQSpanningTreeMethodsforDiscriminativeTrainingofDependencyParsers\BBCQ\\newblockTechnicalreport,UPennCIS.\bibitem[\protect\BCAY{Mel'uk}{Mel'uk}{1988}]{Meluk88}Mel'uk,I.~A.\BBOP1988\BBCP.\newblock{\BemDependencySyntax:TheoryandPractice}.\newblockStateUniversityofNewYorkPress,Albany,NewYork.\bibitem[\protect\BCAY{Ozeki}{Ozeki}{1994}]{Ozeki94}Ozeki,K.\BBOP1994\BBCP.\newblock\BBOQDependencyStructureAnalysisasCombinatorialOptimization\BBCQ\\newblock{\BemInformationSciences},{\Bbf78}(1-2),\mbox{\BPGS\77--99}.\bibitem[\protect\BCAY{Pereira\BBA\Warren}{Pereira\BBA\Warren}{1980}]{Pereira80}Pereira,F.\BBACOMMA\\BBA\Warren,D.\BBOP1980\BBCP.\newblock\BBOQDefiniteclausegrammarsforlanguageanalysis-asurveyoftheformalismandacomparisonwithaugmentedtransitionnetworks\BBCQ\\newblock{\BemArtificialIntelligence},{\Bbf13}(3),\mbox{\BPGS\231--278}.\bibitem[\protect\BCAY{Pollard\BBA\Sag}{Pollard\BBA\Sag}{1994}]{Pollard94}Pollard,C.\BBACOMMA\\BBA\Sag,I.~A.\BBOP1994\BBCP.\newblock{\BemHead-DrivenPhraseStructureGrammar}.\newblockUniversityofChicagoPress,Chicago.\bibitem[\protect\BCAY{Riezler,King,Kaplan,Crouch,Maxwell~III,\BBA\Johnson}{Riezleret~al.}{2002}]{Riezler02}Riezler,S.,King,T.~H.,Kaplan,R.~M.,Crouch,R.,Maxwell~III,J.~T.,\BBA\Johnson,M.\BBOP2002\BBCP.\newblock\BBOQParsingtheWallStreetJournalusingaLexical-FunctionalGrammarandDiscriminativeEstimationTechniques\BBCQ\\newblockIn{\BemProceedingsofthe40thAnnualMeetingoftheACL(ACL-02)},\mbox{\BPGS\271--278}.\bibitem[\protect\BCAY{Rim,Seo,\BBA\Simmons}{Rimet~al.}{1990}]{Rim90}Rim,H.~C.,Seo,J.,\BBA\Simmons,R.~F.\BBOP1990\BBCP.\newblock\BBOQTransformingSyntacticGraphsintoSemanticGraphs\BBCQ\\newblockTechnicalreport,ArtificialIntelligenceLab,TexasatAustin.\bibitem[\protect\BCAY{Schiehlen}{Schiehlen}{1996}]{Schiehlen96}Schiehlen,M.\BBOP1996\BBCP.\newblock\BBOQSemanticConstructionfromParseForests\BBCQ\\newblockIn{\BemComputationalLinguistics(COLING'96)}.\bibitem[\protect\BCAY{Seo\BBA\Simmons}{Seo\BBA\Simmons}{1989}]{Seo89}Seo,J.\BBACOMMA\\BBA\Simmons,R.~F.\BBOP1989\BBCP.\newblock\BBOQASyntacticGraphs:ARepresentationfortheUnionofAllAmbiguousParseTrees\BBCQ\\newblock{\BemComputationalLinguistics},{\Bbf15}.\bibitem[\protect\BCAY{Shudo,Narahara,\BBA\Yoshida}{Shudoet~al.}{1980}]{Shudo80}Shudo,K.,Narahara,T.,\BBA\Yoshida,S.\BBOP1980\BBCP.\newblock\BBOQMorphologicalaspectsofJapaneselanguageprocessing\BBCQ\\newblockIn{\BemProceedingsofCOLING'80}.\bibitem[\protect\BCAY{Sleator\BBA\Temperley}{Sleator\BBA\Temperley}{1991}]{Sleator91}Sleator,D.\BBACOMMA\\BBA\Temperley,D.\BBOP1991\BBCP.\newblock\BBOQParsingEnglishwithaLinkGrammar\BBCQ\\newblockTechnicalreport,DepartmentofComputerScience,CarnegieMellonUniversity.\bibitem[\protect\BCAY{Steedman}{Steedman}{2000}]{Steedman00}Steedman,M.\BBOP2000\BBCP.\newblock{\BemTheSyntacticProcess}.\newblockTheMITPress,Cambridge,MA.\bibitem[\protect\BCAY{Tomita}{Tomita}{1987}]{Tomita87}Tomita,M.\BBOP1987\BBCP.\newblock\BBOQAnefficientaugmented-context-freeparsingalgorithm\BBCQ\\newblock{\BemComputationalLinguistics},{\Bbf13}(1-2),\mbox{\BPGS\31--46}.\bibitem[\protect\BCAY{Tsuruoka,Miyao,\BBA\Tsujii}{Tsuruokaet~al.}{2004}]{Tsuruoka04}Tsuruoka,Y.,Miyao,Y.,\BBA\Tsujii,J.\BBOP2004\BBCP.\newblock\BBOQTowardsefficientprobabilisticHPSGparsing:integratingsemanticandsyntacticpreferencetoguidetheparsing\BBCQ\\newblockIn{\BemIJCNLP-04Workshop:BeyondShallowAnalyses-FormalismsandStatisticalModelingforDeepAnalyses}.\bibitem[\protect\BCAY{Wang\BBA\Harper}{Wang\BBA\Harper}{2004}]{Wang04}Wang,W.\BBACOMMA\\BBA\Harper,M.~P.\BBOP2004\BBCP.\newblock\BBOQAStatisticalConstraintDependencyGrammar(CDG)Parser\BBCQ\\newblockIn{\BemWorkshoponIncrementalParsing:BringingEngineeringandCognitionTogether(ACL)},\mbox{\BPGS\42--49}.\bibitem[\protect\BCAY{Wilks}{Wilks}{1975}]{Wilks75}Wilks,Y.~A.\BBOP1975\BBCP.\newblock\BBOQAnIntelligentAnalyzerandUnder-standerofEnglish\BBCQ\\newblock{\BemCommunicationsoftheA.C.M.},{\Bbf18},\mbox{\BPGS\264--274}.\bibitem[\protect\BCAY{Winograd}{Winograd}{1983}]{Winograd83}Winograd,T.\BBOP1983\BBCP.\newblock{\BemLanguageasaCognitiveProcess:Volume1Syntax}.\newblockAddison-WesleyPublishing.\bibitem[\protect\BCAY{工藤拓\JBA松本裕治}{工藤拓\JBA松本裕治}{2005}]{Kudo05_j}工藤拓\JBA松本裕治\BBOP2005\BBCP.\newblock\JBOQ相対的な係りやすさを考慮した日本語係り受け解析モデル\JBCQ\\newblock\Jem{情報処理学会論文誌},{\Bbf46}(4),\mbox{\BPGS\1082--1092}.\bibitem[\protect\BCAY{平川秀樹}{平川秀樹}{2002}]{Hirakawa02_j}平川秀樹\BBOP2002\BBCP.\newblock\JBOQ最適解探索に基づく日本語意味係り受け解析\JBCQ\\newblock\Jem{情報処理学会論文誌},{\Bbf43}(3),\mbox{\BPGS\696--707}.\bibitem[\protect\BCAY{平川秀樹\JBA天野真家}{平川秀樹\JBA天野真家}{1989}]{Hirakawa89a}平川秀樹\JBA天野真家\BBOP1989\BBCP.\newblock\JBOQ構文／意味優先規則による日本語解析\JBCQ\\newblock\Jem{人工知能学会第３回全国大会論文集},\mbox{\BPGS\363--366}.\bibitem[\protect\BCAY{野呂智哉\JBA岡崎篤\JBA徳永健伸\JBA田中穂積}{野呂智哉\Jetal}{2002}]{Noro02}野呂智哉\JBA岡崎篤\JBA徳永健伸\JBA田中穂積\BBOP2002\BBCP.\newblock\JBOQ大規模日本語文法構築に関する一考察\JBCQ\\newblock\Jem{言語処理学会第8回年次大会},\mbox{\BPGS\387--390}.\bibitem[\protect\BCAY{野呂智哉\JBA橋本泰一\JBA徳永健伸\JBA田中穂積}{野呂智哉\Jetal}{2005}]{Noro05}野呂智哉\JBA橋本泰一\JBA徳永健伸\JBA田中穂積\BBOP2005\BBCP.\newblock\JBOQ大規模日本語文法の開発\JBCQ\\newblock\Jem{自然言語処理},{\Bbf12}(1),\mbox{\BPGS\3--32}.\end{thebibliography}\begin{biography}\biotitle{略歴}\bioauthor{平川秀樹}{昭和55年京都大学大学院工学研究科電気工学専攻修士課程修了．同年東京芝浦電気(株)入社．機械翻訳システムの研究開発に従事．昭和57-59年新世代コンピュータ開発機構(ICOT)研究員，平成6-7年MITMediaLab.派遣研究員，(株)東芝研究開発センター知識メディアラボラトリ所属，自然言語処理，知識処理，ヒューマンインタフェースに関する研究に従事．情報処理学会，人工知能学会，言語処理学会，ACL，GSK各会員．}\bioreceived{受付}\bioaccepted{採録}\end{biography}\begin{comment}\end{comment}\newpage\subsection*{付録１：構文グラフの問題}\small\def\verbatimsize{}次の文法規則を与えて``Tokyotaxidrivercallcenter''をスタートシンボルをnpとして解析する場合を考える．{\rm\begin{verbatim}[GrammarRules]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[\myitemindentcs($X$)]:単一弧$X$の構成素列CS．ex.cs(*e$_1$)=[103,169](103,169は圧縮弧のID)\item[\myitemindentds($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[\myitemindentgov($X$)]:アーク$X$の支配ノード．ex.gov(arc(obj-25,[flies]-n-1,[time]-v-0))=[time]-v-0\item[\myitemindentdep($X$)]:アーク$X$の依存ノード．ex.dep(arc(obj-25,[flies]-n-1,[time]-v-0)=[flies]-n-1\item[\myitemindenttop\_node($X$)]:依存木$X$のトップノード（どのアークの依存ノードにもなっていないノード）．\end{itemize}依存木DT中のアーク$X$,$Y$に対する関係\begin{itemize}\item[\myitemindentbro($X$,$Y$)]:gov($X$)=gov($Y$)．$X$,$Y$を兄弟アークと呼ぶ．\item[\myitemindent$X\:{\xrightarrow[{\rmDT}]{1}}\:Y$]:dep($X$)=gov($Y$)．$X$は$Y$の親，$Y$は$X$の子と呼び，この関係を親子関係と呼ぶ．\item[\myitemindent$X\:{\xrightarrow[{\rmDT}]{+}}\:Y$]:$X$から$Y$に親子関係の連鎖(１段以上)が存在．$X$を$Y$の祖先アーク，$Y$を$X$の子孫アークと呼ぶ．\item[\myitemindent$X\:{\xrightarrow[{\rmDT}]{*}}\:Y$]:$X=Y$または$X{\xrightarrow[{\rmDT}]{+}}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[{\rmPF}]{+}}\:Y$]:統語森PFにおいて単一弧または圧縮弧$X$から単一弧または圧縮弧$Y$に対して[$X,{\ldots},Y$]なるパスが存在する．$X$を$Y$の祖先とも呼ぶ．\item[\myitemindent$X\:{\xrightarrow[{\rmPF}]{*}}\:Y$]:単一弧または圧縮弧$X$,$Y$に対して，$X=Y$または$X{\xrightarrow[{\rmPF}]{{\tiny+}}}Y$が成立する．このとき，$X$から$Y$に{\bf到達可能}と呼ぶ．\item[\myitemindent$X\:{\swarrow}${\tiny[PF]}${\searrow}\:Y$]:単一弧または圧縮弧$X$,$Y$に対して，$X{\neq}Y$,$\neg$($X{\xrightarrow[{\rmPF}]{*}}Y$),$\neg$($Y{\xrightarrow[{\rmPF}]{*}}X$)であり，$Z{\xrightarrow[{\rmPF}]{*}}X$かつ$Z{\xrightarrow[{\rmPF}]{*}}Y$なる単一弧または圧縮弧$Z$が統語森PFに少なくとも１つ存在する．\item[\myitemindent弧が支配するアーク]:アーク$X$は$X{\in}$ds(*e),*E${\xrightarrow[{\rmPF}]{{\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[{\rmPF}]{{\tiny+}}}$*e$_y$又は*e$_y{\xrightarrow[{\rmPF}]{{\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{文法規則を弧の形式で表現している．実際にはこの弧は生成されないが説明上導入している．}から，弧の結合により活性弧が生成され(中間に位置)，最終的に不活性弧(リーフに位置)になる様子を示している．文法規則は次である．$${\rmy/}X_h\rightarrow{\rmx}_1{\rm/}X_1{\cdots}{\rmx}_h{\rm/}X_h{\cdots}{\rmx}_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))と弧$<$*Ex$_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[\myitemindentsrc\_Edge($a$)（{\bf生成弧}）]:確定アーク$a$を生成した弧(活性圧縮弧または不活性圧縮弧)．確定アークから弧への対応は1対1，弧から確定アークへの対応は1対0〜多．\item[\myitemindent$X{\xrightarrow[{\rmCT}]{*}}Y$（{\bfオリジン}）]:弧の結合木CTにおいて，ルートから弧$Y$に至る経路に弧$X$が存在する，又は，$X=Y$である．$X$を$Y$のオリジンと呼ぶ．\item[\myitemindent{\bfオリジンの関係}]:弧の結合木CTにおいて弧$X$,$Y$に関して$X{\xrightarrow[{\rmCT}]{*}}Y$または$Y{\xrightarrow[{\rmCT}]{*}}X$が成り立つ時，$X$と$Y$はオリジンの関係にあるという．\item[\myitemindentedge($a$,$DT$)（{\bf対応弧}）]:確定アーク$a$と整依存木$DT$に対して次の条件(補題\ref{lem:app2-2})を満たす単一弧$e$を意味し，アーク$a$の整依存木$DT$に対する「対応弧」と呼ぶ．{\myitemindent}$DT{\supseteq}{\rmds(}e{\rm)},{\rma}{\in}{\rmds(}e{\rm)}$\end{itemize}\myhalfskip\end{minipage}}\myhalfskip{\mynoindent}上記の弧の結合木の構成より，部分依存構造中に存在する２つの確定アークa$_i$,a$_j$に関して，次の補題が成立する．\begin{lemma}[同一部分依存構造中のアークの関係]\label{lem:TwoArcsInOneDS}単一弧$e$中の確定アークa$_i$,a$_j{\in}${\rmds(}$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[{\rmCT}]{*}}$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[{\rmPF}]{{\tiny+}}}$e$_j$であれば，dep(a$_i$)${\neq}$dep(a$_j$)である．また，逆にdep(a$_i$)$=$dep(a$_j$)であれば¬(e$_i{\xrightarrow[{\rmPF}]{{\tiny+}}}$e$_j$)である．\proof{部分依存構造条件(\ref{sec:bunpoukisoku}節)より，１つの単一弧の有する部分依存構造は句ヘッドをルートとした依存木となるため成立する．}\end{lemma}\begin{lemma}[対応弧の存在]\label{lem:app2-2}整依存木{\rmDT}中のアーク{\rma$_i$}({\rma$_i$}${\in}${\rmDT)}に対して次が成立する圧縮弧{\rmE}${\in}${\rmPF},単一弧{\rme}${\in}${\rmE}がただ１つ存在する．{\rmDT}⊇{\rmds(}e{\rm)},{\rma$_i$}${\in}${\rmds(}e{\rm)}\mygapskip{\mynoindent}補題\ref{lem:app2-2}は，アーク{\rma$_i$}が整依存木{\rmDT}の要素の時，{\rma$_i$}を含む部分依存構造{\rmds(}e{\rm)}の全体が{\rmDT}に含まれるところの単一弧{\rme}が統語森に存在することを意味している．\proof{DTのノード数を$n$(アーク数:$n-1$)とする．DTをアークa$_i$に関して次の２つのアーク集合IN\_ARCS,OUT\_ARCSに分ける．{\mygapskip}IN\_ARCS=\{$a_j$${\mid}$src\_Edge($a_i$)${\xrightarrow[{\rmCT}]{*}}$src\_Edge($a_j$)またはsrc\_Edge($a_j$)${\xrightarrow[{\rmCT}]{*}}$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}ここで，次が成立する．$$「{\rmSRC\_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[{\rmCT}]{*}}$E$_i$,E$_i{\xrightarrow[{\rmCT}]{*}}V$\item[\myitemindent(b)]両方がE$_i$のオリジン．$U{\xrightarrow[{\rmCT}]{*}}$E$_i$,$V{\xrightarrow[{\rmCT}]{*}}$E$_i$\item[\myitemindent(c)]E$_i$が両方のオリジン．E$_i{\xrightarrow[{\rmCT}]{*}}U$,E$_i{\xrightarrow[{\rmCT}]{*}}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[{\rmPF}]{+}}$*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}$とおく．\mygapskipE$_i{\xrightarrow[{\rmCT}]{*}}$E$_{last}$E$_{last}{\xrightarrow[{\rmCT}]{*}}$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[{\rmPF}]{{\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[{\rmPF}]{{\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[{\rmDT}]{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[{\rmPF}]{+}}$*e$_j$\item[(c)]*e$_j{\xrightarrow[{\rmPF}]{+}}$*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[{\rmPF}]{+}}$*e$_j$又は*e$_j{\xrightarrow[{\rmPF}]{+}}$*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[{\rmDT}]{+}}$a$_j$)に対して，*e$_i$=edge(a$_i$,DT)，*e$_j$=edge(a$_j$,DT)とした時に，次が成立する．\begin{itemize}\item[]*e$_i{\xrightarrow[{\rmPF}]{*}}$*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[{\rmPF}]{+}}$*e$_i$)なので(c)が成立することはない．このため，親子アークについては(a),(b)のいずれかが成立する．一般のa$_i{\xrightarrow[{\rmDT}]{*}}$a$_j$に対しては${\xrightarrow[{\rmPF}]{*}}$の推移性により補題\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[{\rmPF}]{*}}$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[{\rmPF}]{*}}$*e$_j$が成立する．\proof{a$_j$がDTのトップノードの直下のアーク，すなわちgov(a$_j$)$=$top\_node(DT)の場合は，補題\ref{lem:app2-3}とtop\_edgeの定義より，*e$_t{\xrightarrow[{\rmPF}]{*}}$*e$_j$が成立する．それ以外の場合は，a$_j$はDTのトップノード直下のアークの子孫アークとなるため，補題\ref{lem:app2-4}より*e$_t{\xrightarrow[{\rmPF}]{*}}$*e$_j$である．}\end{lemma}\subsection*{［整依存木{\rmDT}の分割］}\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[\myitemindentroot\_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[{\rmPF}]{+}}$*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[{\rmPF}]{+}}$*e$_{o}$が成立する．一方，DTがアークから成る木の場合，補題\ref{lem:app2-4}より，*e$_t{\xrightarrow[{\rmPF}]{*}}$*e$_{o}$が言える．これより，圧縮弧列cs(*e$_t$)中のいづれか１つの圧縮弧Xに対してX${\xrightarrow[{\rmPF}]{*}}$*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={\rmdep(a}_j$)なるアークa$_j$が存在する．また，a$_j{\in}$DT$_i$に対して，gov(a$_k$)$=$n$_i$,a$_k{\xrightarrow[{\rmDT}]{*}}$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[{\rmPF}]{*}}$*e$_j$である．一方，DTのトップ単一弧を*e$_t$とすると補題\ref{lem:RelBetweenTopedgeAndEdge}より*e$_t{\xrightarrow[{\rmPF}]{*}}$*e$_k$であり，cs(*e$_t$)中の圧縮弧のうちの１つから*e$_k$に到達可能である．*e$_k$の句ヘッドはn$_i$であるので，*E$_i{\xrightarrow[{\rmPF}]{*}}$*e$_k$である．以上より*E$_i{\xrightarrow[{\rmPF}]{*}}$*e$_k{\xrightarrow[{\rmPF}]{*}}$*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\mygapskipDTがアークからなる依存木の場合は，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[{\rmPF}]{+}}$*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}