\textbf{仮説推論}(Abduction)は，与えられた観測に対する最良の説明を見つける，論理推論の枠組みのひとつである．仮説推論は，自然言語処理や故障診断システムなどを含む，人工知能分野の様々なタスクにおいて古くから用いられてきた(NgandMooney1992;Blythe,Hobbs,Domingos,Kate,andMooney2011;Ovchinnikova,Hobbs,Montazeri,McCord,Alexandrov,andMulkar-Mehta2011;井之上，乾，Ovchinnikova，Hobbs2012;杉浦，井之上，乾2012)．\nocite{Ng92,Blythe11,Ovch11,Inoue12,Sugiura12}自然言語処理への応用のうち，代表的な先行研究の一つにHobbsら\cite{Hobbs93}の\textit{InterpretationasAbduction}(IA)がある．Hobbsらは，語義曖昧性解消，比喩の意味理解，照応解析や談話関係認識などの，様々な自然言語処理のタスクを，一階述語論理に基づく仮説推論により統合的にモデル化できることを示した．詳しくは\ref{sec:abduction}節で述べるが，IAの基本的なアイデアは，\textbf{談話解析}（文章に対する自然言語処理）の問題を「観測された文章（入力文）に対し，世界知識（言語の知識や常識的知識など）を用いて，最良の説明を生成する問題」として定式化することである．最良の説明の中には，観測された情報の背後で起きていた非明示的な事象，共参照関係や単語の語義などの情報が含まれる．例文``{\itJohnwenttothebank.Hegotaloan.}''に対して，IAによる談話解析を行う様子を図\ref{fig:ia}に示す．まず，入力文の論理式表現が観測として，世界知識の論理式表現が背景知識として与えられ，背景知識に基づいて説明が生成される．例えば，$\mathit{go}(x_1,x_2)$（\textit{John}が\textit{bank}に行った）という観測に対して，$\mathit{issue}(x,l,y)\Rightarrowgo(y,x)$（$x$が$y$に対して$l$を発行するには，$y$は$x$の所に行かなければならない）という因果関係（行為の前提条件）の知識を用いて，$\mathit{issue}(x_2,u_1,x_1)$（\textit{bank}が\textit{John}に対して何か($u_1$)を発行した）という説明を生成している．これは，非明示的な情報の推定に相当する．また，この非明示的な情報を根拠の一つとして生成された説明$x_1=y_1$（\textit{John}と\textit{He}は同一人物）は，共参照関係の推定に相当する．以上のようにIAでは，談話解析の様々なタスクが，説明生成という統一的な問題に帰着される．\begin{figure}[t]\begin{center}\includegraphics{23-3ia2f1.eps}\end{center}\hangcaption{仮説推論による談話解析の例．点線の四角は観測を，実線の四角は背景知識を表す．変数対を繋ぐ点線はそれらがその仮説において同一の変数であることを表す．青い吹き出しは推論中で用いられている背景知識の元となった世界知識を表し，赤い吹き出しは得られた仮説に対する解釈を表す．}\label{fig:ia}\end{figure}仮説推論は，以下の様な点で談話解析の枠組みとして適していると考えられる：\begin{enumerate}\item入力から出力が導かれるまでの過程が，解釈可能な形で得られる．すなわち，どのような仮説を立てて，どのような知識を用いて観測を説明しているかが，図\ref{fig:ia}のような証明木という形で陽に得られる．\item様々な種類の世界知識を統一的，かつ宣言的に記述し利用することができる．すなわち，どのような種類の知識であっても，その知識を解析にどう利用するかの手続きを定義する必要がなく，論理式として宣言的に記述するだけで談話解析に利用できる．\item語義曖昧性解消や照応解析，プラン認識など，談話理解の様々なサブタスクを一つのモデルに集約して解くことにより，サブタスク間の相互依存性を自然な形で考慮できる．図\ref{fig:ia}においても，照応解析と語義曖昧性の解消が同時に起こっていることが確認できる．\end{enumerate}IAを始めとした仮説推論に基づく談話解析の研究は，1990年代が全盛期であったが，近年になって再び注目を浴びつつある\cite{Blythe11,Ovch11,Inoue12,Sugiura12}．これには，大きく2つの背景があると考えられる．ひとつめに，仮説推論を実用規模の問題に適用できる程度の，大規模な世界知識を取り揃える技術が昔に比べて大幅に成熟してきたことが挙げられる\cite{fellbaum98,framenetII,Chambers09,Scho10}．例えば文献\cite{Ovch11}では，WordNet\cite{fellbaum98}とFrameNet\cite{framenetII}を用いて約数十万の推論規則からなる背景知識を構築し，含意関係認識のタスクにIAを適用している．ふたつめの背景には，計算機性能の向上や効率的な仮説推論エンジンが提案された\cite{Mulkar07,Blythe11,Inoue11,Inoue12,Yamamoto15,Schuller15}ことにより，大規模知識を用いた論理推論が計算量の面で実現可能になってきたことが挙げられる．例えば\cite{Inoue12}では，約数十万の推論規則からなる背景知識を用いて含意関係認識のデータセットに対して推論を行い，先行研究より大幅に高速な推論を行えたことが報告されている．しかしながら，仮説推論における計算コストの問題は未だ完全に解決されたとはいえないのが実情である．詳しくは\ref{sec:prob}~節で詳述するが，とりわけ，主格関係や目的格関係などの単語間の統語的依存関係を表すためのリテラル（便宜的に「機能リテラル」と呼ぶ．形式的な定義は\ref{sec:prob:mr}節で与える）が知識表現に含まれる場合（例えば，$\mathit{john}(j)\land\mathit{get}(e)\land\mathit{dobj}(e,l)\land\mathit{loan}(l)$における\textit{get}と\textit{loan}の目的格関係を表す$\mathit{dobj}(e,l)$），推論時間が増大するという問題がある．最新の仮説推論エンジンである\cite{Yamamoto15}では，A*アルゴリズムに基づいて説明の構成要素（\textbf{潜在仮説集合}）を列挙し，仮説推論の問題を「説明の構成要素の組み合わせ最適化問題」へ変換したのち，整数線形計画ソルバにより最良の説明を求める．しかし，機能リテラルが知識表現に含まれる場合，(1)機能リテラルをもとにした推論により，潜在仮説集合の中に，最良の説明になりえない構成要素が多く入り込んでしまい（例えば，$\mathit{foolish}(e_1)\land\mathit{smart}(e_2)\land\mathit{nsubj}(e_1,x)\land\mathit{nsubj}(e_2,y)$から，$e_1=e_2$を導く），組み合わせ最適化問題のサイズが無用に肥大化し，推論時間が増大する，(2)潜在仮説集合の生成をガイドするヒューリスティック関数の精度低下が起きてしまい，潜在仮説集合の生成における計算効率が低下する，という問題が起こる．このように，実タスクへの適用は未だ困難な状況であり，前述のような利点が本当にあるかどうか，検証する環境が完全に整っていない状況である．以上のような背景を踏まえ，本論文では，知識表現に機能リテラルを含む仮説推論において，機能リテラルの性質を利用して潜在仮説集合の生成手続きを改良し，効率的に最適解を求め，かつヒューリスティック関数の精度低下を抑制する手法を提案する．より具体的には，一つ目の問題に対しては，潜在仮説集合の生成を行う際に，最良の説明になりえない説明を事前チェックするように潜在仮説集合の手続きを拡張する．例えば，矛盾する二つの事象を等価とみなす説明の構成要素を生成する推論（前述の$e_1=e_2$など）を禁止することで，潜在仮説集合の肥大化を防ぐ．また，二つ目の問題に対しては，ヒューリスティック関数の中で，より良い説明の構成要素を優先的に探索するために用いられる\textbf{述語グラフ}の生成手法を工夫することにより対処する．問題の原因は，背景知識に頻出する機能リテラルがハブとなり，あらゆる説明の構成要素の候補が最良の説明の生成に寄与すると誤って判断されてしまうことにある．これに対し，述語グラフにおいて機能リテラルに繋がる一部の枝を適切に排除することにより，解の最適性を保持しながらヒューリスティック関数の精度を上げる手法を提案する．本論文における具体的な貢献は次の3点である．一つ目に，仮説推論の最新の実装であるA*-basedAbduction\cite{Yamamoto15}の手法に前述の枝刈りを導入する方法を示し，機能リテラルを知識表現に含む場合でも推論の規模耐性を維持する方法を示す．二つ目に，機能リテラルの性質に基づく探索空間の枝刈りが，ある条件のもとでは本来の解を損なわないことを示す．三つ目に，大規模な知識ベースと実在の言語処理の問題を用いて，A*-basedAbduction\cite{Yamamoto15}のシステムとの推論時間の比較を行い，提案手法を評価する．本論文での実験においては，提案手法が\cite{Yamamoto15}のシステムと比べ数十〜数百倍ほど効率的に解仮説が得られていることが確かめられた．仮説推論に基づく談話解析の枠組みを実タスクへ適用する上で，効率的な推論アルゴリズムの確立は必須の要件である．本研究の成果により，仮説推論に基づく談話解析の研究を進めるための環境整備が大きく前進すると考えられる．以降の節では，まず仮説推論とその実装に関する先行研究について述べたあと（2節），本論文で取り組む問題について述べ（3節），提案手法について説明する（4節，5節）．次に，提案手法と既存手法の比較実験の結果について報告し（6節），最後に今後の展望を述べる．