\section{はじめに}
\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節），最後に今後の展望を述べる．
\section{背景}
本節では，本論文の提案手法の基になっている種々の既存研究，すなわち仮説推論およびその実装に関して説明する．\subsection{仮説推論}\label{sec:abduction}仮説推論とは，与えられた観測に対して最良の説明を求める推論である．本論文では，仮説推論の意味表現として一階述語論理\footnote{本論文では，読者が一階述語論理の基礎知識を有することを仮定する．一階述語論理の解説書については，例えば\cite{Nienhuys97}等を参照されたい．}を用い，仮説推論の形式的な定義を次のように与える．なお，本論文では関数記号のない(function-free)一階述語論理を用いるものとし，全てのリテラルは論理変数，定数，スコーレム定数を引数に取る．\begin{description}\item[Given:]背景知識$B$，観測$O$．ただし，$B$は含意型の一階述語論理式の集合であり，各論理式の前件および後件にはリテラルの連言のみを許容する．各論理式の前件に含まれる論理変数は全称限量されており，前件に含まれない論理変数は存在限量されているものとする．形式的には，各論理式は$\forallx_1,\ldots,x_n\[\existsy_1,\ldots,y_m\[p_1(x_1)\land\ldots\landp_n(x_n)\Rightarrowq_1(y_1)\land\ldots\landq_m(y_m)]]$と表現される．ここで，$x_i,y_i$はそれぞれ任意個数の引数列を表す\footnote{ただし，前件と後件の両方に含まれている変数については全称限量される．}．また，$O$は，一階述語論理リテラルおよび論理変数間の等価関係を表す等号あるいはその否定の連言であり，全ての論理変数は存在限量されているものとする．なお以降の記述では，$B$および$O$がそれぞれ矛盾を含まないことを前提とする．\item[Find:]仮説（または説明）$H$．$H$は，一階述語論理リテラル，および論理変数間の等価関係を表す等号・不等号の連言であり，$H\cupB\modelsO$および$H\cupB\nvDash\perp$を満たす\footnote{計算論理学の分野において現在主流となっているAnswerSetProgramming~\cite{Reiter87,Moore83,Gelfond88}の考え方に従えば，仮説の探索問題は，与えられた観測と背景知識から，観測を説明するようにあらゆるリテラルに対する真偽値割り当てを求める問題と見做すことができる．そのような文脈において本研究で扱う仮説推論は，仮説$H$にリテラル$l$または$\lnotl$が含まれていることが，リテラル$l$の真偽値にtrueまたはfalseが割り当てられている事に対応する．すなわち，仮説$H$に含まれないリテラルの真偽値は全て不定であると見做す．}．ここで$\models$は論理的含意を表し，$H$が$O$を\textbf{説明する}，という．$\perp$は偽を表す．また，連言と集合は相互変換可能であるとし，連言$l_1\land\ldots\landl_n$とリテラル集合$\{l_1,\ldots,l_n\}$とも書けるものとする．\end{description}なお，本論文では背景知識，観測，仮説における限量子の記述は基本的に省略する．一般には，与えられた$B$と$O$に対して，複数の仮説$H_1$,$H_2,\ldots$が存在する．本論文では，それぞれの仮説$H_i$を{\bf候補仮説}と呼び，候補仮説$H_i$に含まれる各リテラル$h\inH_i$を$H_i$の{\bf要素仮説}と呼ぶ．また，可能な全ての候補仮説を$H\equiv\{H_1,H_2,\ldots\}$で表す．例えば図\ref{fig:ia}では，点線で囲まれたリテラルの集合($\mathit{john}(x_1)\land\mathit{go}(x_1,x_2)\land\ldots$)が観測$O$，実線で囲まれた論理式（例えば，$\mathit{issue}(x_2,u_1,x_1)\Rightarrowgo(x_1,x_2)$）が背景知識$B$の一部である．候補仮説として，例えば$H_1=\mathit{john}(x_1)\land\mathit{loan}(y_2),H_2=\mathit{john}(x_1)\land\mathit{issue}(u_2,y_2,y_1)\land\mathit{financial\_inst}(x_2)\land\mathit{loan}(y_2)$などが考えられる．仮説推論の目的は，何らかの評価指標のもとでの最良の候補仮説$\hat{H}$を見つけることである．この$\hat{H}$を{\bf解仮説}と呼び，形式的には次のように表す：\begin{equation}\hat{H}=\argmax_{H\in\mathbb{H}}\mathit{Eval}(H)\end{equation}ここで，$\mathit{Eval}$は候補仮説$H$の蓋然性を表す何らかの評価値を返す関数を表し，このような関数を{\bf仮説の評価関数}と呼ぶ．先行研究では，さまざまな評価関数が提案されている\cite{Hobbs93,Singla11,Inoue12b,Raghavan10}．例えば，代表的な評価関数の一つである重み付き仮説推論\cite{Hobbs93}は，「単純な（小さい）仮説ほど良い」という基本的な仮定に基いており，候補仮説の最小性を候補仮説の評価値として定義している．より具体的には，候補仮説の評価値$\mathit{Eval}(H)$は，$H$の要素仮説のコストの負の総和$-\sum_{h\inH}\mathit{cost}(h)$で定義される．要素仮説のコスト$\mathit{cost}(h)$の詳細な計算方法は\cite{Hobbs93}に委ねるが，基本的には，(1)要素仮説$h$が観測$O$を説明するのに要する背景知識の信頼度，(2)要素仮説$h$が他の要素仮説に説明されているか，の二つの要因を基にコストが決定される．本研究では，\ref{sec:prob}~節で示す仮説の整合性条件を保証する任意の評価関数を想定する．\subsection{潜在仮説集合に基づく候補仮説の表現}\label{sec:potential}$H\cupB\modelsO,H\cupB\nvDash\perp$を満たす全ての候補仮説を陽に列挙して最良の仮説を求めることは，時間・空間的計算量の観点で非現実的である．そのため，仮説推論エンジンの先行研究\cite{Inoue11,Inoue12,Yamamoto15}では，(1)観測からの後ろ向き推論によって各候補仮説を構成するリテラルの集合$P$を列挙するに留め，(2)$P$の要素の組み合わせ（部分集合）で暗に候補仮説を表現し，組み合わせ最適化問題を解くことで効率化を実現している．この$P$は，\textbf{潜在仮説集合}と呼ばれる．例えば，図\ref{fig:lhs}の例では，観測$O=\mathit{animal}(x)\land\mathit{bark}(e_1,x)$と背景知識より，潜在仮説集合$P=\{\mathit{cat}(x),\mathit{poodle}(x),\mathit{dog}(x),\mathit{dog}(y),x=y\}$を得る．この集合の要素の組み合わせ（例えば$\{\mathit{cat}(x),\mathit{dog}(x)\}$）が，一つの候補仮説に対応する．本研究では，この潜在仮説集合の生成方法を効率化する手法を提案するため，潜在仮説集合の生成手続きについて，より詳しく説明する．\begin{figure}[t]\begin{center}\includegraphics{23-3ia2f2.eps}\end{center}\caption{潜在仮説集合の例．背景知識は，図中の実線の四角で囲まれた4つの含意型論理式である．}\label{fig:lhs}\end{figure}まず，観測に含まれるリテラルの集合を初期状態として($P=O$)，次のように定義される\textbf{後ろ向き推論}操作および\textbf{単一化仮説生成}操作を有限回だけ逐次適用することで，潜在仮説集合$P$を生成する．図\ref{fig:lhs}では，$P=\{\mathit{animal}(x),\mathit{bark}(e_1,y)\}$が初期状態となる．\begin{description}\item[後ろ向き推論]後ろ向き推論は，背景知識に含まれる含意型の論理式$p_1(x_1)\land\ldots\landp_n(x_n)\Rightarrowq_1(y_1)\land\ldotsq_m(y_m)$と，$\bigwedge_{i=1}^my_i\theta=y_i'$を満たす変数置換$\theta$が存在するようなリテラルの連言$q_1(y_1')\land\ldots\landq_m(y_m')$を含む潜在仮説集合$P$を入力として，前件部のリテラルの連言$\bigwedge_{i=1}^{n}\{p_i(x_i\theta)\}$を$P$に追加する操作である．本論文では，$q_1(y_1'),\ldots,q_m(y_m')$をそれぞれ$p_1(x_1\theta),\ldots,p_n(x_n\theta)$の{\bf根拠}と呼ぶこととする．図\ref{fig:lhs}では，背景知識$\mathit{cat}(x)\Rightarrow\mathit{animal}(x)$と$P=\{\mathit{animal}(x),\mathit{bark}(e_1,y)\}$を入力として，$\mathit{cat}(x)$を$P$に追加している．このとき，$\mathit{cat}(x)$の根拠は$\mathit{animal}(x)$である．\item[単一化仮説生成]単一化仮説生成は，同一の述語を持つリテラルの対$p(x_1,x_2,\ldots)$,$p(y_1,y_2,\ldots)$に対して，それらのリテラルの引数間の等価関係$x_1=y_1$,$x_2=y_2,\ldots$を潜在仮説集合$P$に追加する操作である．本論文では，$x=y$のような，単一化仮説生成操作によって仮説される論理変数間の等価関係を{\bf等価仮説}と呼ぶ．図\ref{fig:lhs}では，$P=\{\ldots,\mathit{dog}(x),\mathit{dog}(y),\ldots\}$に対して，本操作を適用し，$x=y$を$P$に追加している．\end{description}操作の適用回数の決め方には様々な基準が考えられるが，先行研究\cite{Inoue11,Inoue12,Yamamoto15}では，リテラルの\textbf{深さ}という概念を用いて，適用回数を制限している．\textbf{リテラル$l$の深さ}とは，$l$を潜在仮説集合に追加するまでに実行した後ろ向き推論の回数である．例えば，図\ref{fig:lhs}では，観測に含まれる全てのリテラルは深さ0であり，$\mathit{poodle}(x)$の深さは2である．先行研究では，後ろ向き推論を適用する対象をある深さ$d_\mathit{max}$までのリテラルに制限することにより，操作の適用回数の上限を決めている．このように操作の適用範囲を定めることは，再帰的な推論規則（例えば$p(x)\Rightarrowq(y)$と$q(y)\Rightarrowp(x)$）が背景知識に含まれる場合において，特に重要である．操作の適用回数が有限回であるならば，潜在仮説集合に含まれる各リテラルもまた有限回の後ろ向き推論によって仮説されたリテラルであるので，全ての候補仮説$H\in\mathbb{H}$について$H\cupB\modelsO$の決定可能性が保証される．また，アルゴリズムの停止性，および潜在仮説集合が有限集合であることについても同様に保証される．以上の議論に基づき，本研究においても以上の手続きによって生成された潜在仮説集合の部分集合を候補仮説として扱う．\subsection{仮説推論の実装に関する先行研究}まず，仮説推論の分野における代表的な実装としてはMulkarらのMini-TACITUS\cite{Mulkar07}が挙げられるが，これは計算量の面では非常に非効率であった．そのため，大規模知識を用いた仮説推論を行うにあたっては，より効率的な推論アルゴリズムが必要とされた．これを受けてBlytheらは，仮説推論の枠組みをMarkovLogicNetwork(MLN)\cite{Richardson06}の上で定式化する手法({\bfMLN-basedAbduction})を提案した\cite{Blythe11}．彼らは，仮説推論をMLN上で実装することによって，MLNの分野における成熟した最適化手法を仮説推論にも利用することを可能にした．これによりMini-TACITUSと比べ遥かに高速な推論が実現可能になった．そしてこれよりも更に高い効果をあげたのが，井之上らが提案した整数線形計画法(IntegerLinearProgramming,ILP)に基づく仮説推論({\bfILP-basedAbduction})であった\cite{Inoue11,Inoue12b}．井之上らは，仮説推論の問題を整数線形計画問題により定式化する手法を提案した．これにより，仮説推論において解仮説を導出する処理はそのままILP問題の最適解を導く処理と対応付けられ，外部の高速なILPソルバを利用することで解仮説を効率的に導出することが可能になった．文献\cite{Inoue12b}では，ILP-basedAbductionの枠組みがMLN-basedAbductionと比べても遥かに高速であることが実験によって定量的に示されている．Yamamotoらは，ILP-basedAbduction\cite{Inoue11,Inoue12b}における計算コストが潜在仮説集合の規模に強く依存することに着目し，背景知識における述語間の関連度を事前に推定しておくことで，ILP-basedAbductionの潜在仮説集合生成の手続きにおいて解仮説に含まれる見込みの無い要素仮説を潜在仮説集合から除外し，ILP問題の最適化にかかる時間を大幅に短縮する手法({\bfA*-basedAbduction})を提案した\cite{Yamamoto15}．しかしながら，\ref{sec:prob}節で示すように，A*-basedAbductionには，機能リテラルを含む知識表現において推論時間が増大するという問題がある．本研究は，我々が知る限り最も効率的な枠組みであるA*-basedAbductionを拡張する手法を提案するものである．A*-basedAbductionの詳細については\ref{sec:yamamoto15}節で述べる．
\section{関係を表すリテラルに起因する計算非効率性}
\label{sec:prob}本節では，\ref{sec:prob:mr}~節で示される意味表現と評価関数に基づくIAを先行研究の仮説推論エンジン\cite{Inoue11,Inoue12b,Yamamoto15}で実現する場合に生じる，潜在仮説集合の計算の非効率性について論じる．本節では，まず本研究が前提とする意味表現・評価関数について述べたあと（\ref{sec:prob:mr}節），既存研究の問題点について述べる（\ref{sec:prob:main}節）．\subsection{本研究が前提とする意味表現と評価関数}\label{sec:prob:mr}仮説の評価関数は，\ref{sec:abduction}~節で述べたとおり仮説の良さを評価する関数であるが，「良さ」の因子には少なくとも，(1)仮説が表す情報の良さ，(2)仮説に含まれる意味表現の文法的正しさ(well-formedness)，の二種類が考えられる．本研究は，これらに対してある前提が成立する状況での推論の非効率性を改善するものであるから，本節では，前提とする意味表現と，仮説の評価関数の概形について述べる．\paragraph{(1)意味表現}言語表現によって表される情報を，どのような論理式として表すかは重要な問題の一つである．特に，述語と項の関係の表現形式については，これまでに様々な議論が交わされてきた~\cite[etc.]{Davidson,Hobbs85,Mccord90,neodavidson,Copestake05}．述語項関係の表現形式の基本形としては，大きくDavidsonian形式~\cite{Davidson}とNeo-Davidsonian形式~\cite{neodavidson}があり，本論文ではNeo-Davidsonian形式の意味表現の利用を想定する．Davidsonian形式では，イベントの必須格をリテラルの項の順番に対応させる．例えば，例文``{\itBrutusstabbedCaesarwithaknife.}''を$\mathit{stab}(e,\mathit{Brutus},\mathit{Caesar})\land\mathit{with}(e,\mathit{knife})$のように表現する．ここでは$\mathit{stab}(e,\mathit{Brutus},\mathit{Caesar})$の1番目の引数が$\mathit{stab}$イベントそのものを参照する変数，2番目の引数がイベントの主格，3番目の引数がイベントの目的格に対応している．一方，Neo-Davidsonian形式では，全ての格関係を個別のリテラルとして記述する．例えば，前述の例文を$\mathit{stab}(e)\land\mathit{nsubj}(e,\mathit{Brutus})\land\mathit{dobj}(e,\mathit{Caesar})\land\mathit{with}(e,\mathit{knife})$のように表現する．ここで，$\mathit{stab}(e)$は$e$が$\mathit{stab}$イベントであることを，$\mathit{nsubj}(e,x)$はイベント$e$の主格が個体$x$であることを，$\mathit{dobj}(e,x)$はイベント$e$の目的格が個体$x$であることを表すリテラルである．本論文では，$\mathit{nsubj}(e,x)$や$\mathit{dobj}(e,x)$のような単語間の統語的な依存関係を表すリテラルを\textbf{機能リテラル}と呼び，その述語を\textbf{機能述語}と呼ぶ．一方，$\mathit{stab}(e)$などの，機能リテラル以外のリテラルを\textbf{内容語リテラル}と呼ぶ．また，ある機能リテラルの第一引数を他の内容語リテラルが引数に持つとき，その内容語リテラルを機能リテラルの\textbf{親}と呼び，逆にそのような内容語リテラルが存在しない場合には，その機能リテラルは\textbf{親を持たない}と表現する．例えば上の例において，$\mathit{stab}(e)$は$\mathit{nsubj}(e,x)$の親である．Neo-Davidsonian形式は，イベントに対する部分的な説明を表現できる（例えば$\mathit{police}(x)\Rightarrow\mathit{arrest}(e)\land\mathit{nsubj}(e,x)$のようにイベントの主格だけを取り上げた推論が記述できる）ことや，個々のイベントの必須格と任意格の境界を決める必要が無いなどの利点を持つ．自然言語の動詞は，動詞ごとに必須格・任意格が異なるため，実世界の様々な文を扱う上では，Neo-Davidson形式はDavidsonian形式よりIAに適した表現形式であると考えられる．以上の理由により，本論文ではNeo-Davidsonian形式の意味表現を想定する．ところで，上で述べたように，機能リテラルは言語表現における単語間の統語的依存関係を表すので，親を持たない機能リテラルは文法的に不正である．このことから本論文では，全ての観測が以下の条件を充足することを仮定する：\begin{itemize}\item[条件1.]全ての観測は親を持たない機能リテラルを含まない．\end{itemize}すなわち，この条件を充足しない観測は，元となった文が文法的に不正であると考えられるので，本研究ではそのような観測は入力として考えないものとする．\paragraph{(2)評価関数}次に，本論文で想定する評価関数の概形について述べる．まず第一に，仮説に含まれる等価仮説の正しさを評価することを前提とし，次のような条件として定義する：\begin{itemize}\item[条件2.]評価関数は，不正な等価仮説を含む候補仮説を解仮説として選択しない．\end{itemize}ここでの不正な等価仮説とは，同一事象を表し得ない変数間の等価仮説を指し，本論文ではこのような等価仮説を$e_1=^*e_2$と書く．\ref{sec:potential}節で述べたとおり，候補仮説の生成時には，同じ述語を持つリテラル対に単一化仮説生成を適用することにより等価仮説が生成される．このとき，例えば$\mathit{smart}(e_1)\land\mathit{foolish}(e_2)\lande_1=e_2$のように，同一でない二つの事象を表す論理変数が等価であるという候補仮説が生成されてしまう場合がある．条件2が満たされる限り，このような候補仮説は解仮説として選択されない．等価仮説が不正であるか否か，すなわちある2つの論理変数が同一事象を表し得るかどうかの判断については，変数の等価性について閉世界仮説\cite{raymond78}を仮定することで対応する．すなわち，ある論理変数対$a$,$b$が潜在仮説集合$P$において同じ型\footnote{ここでの型とは，型理論などにおける厳密な意味での型ではなく，説明上のアナロジーとしての型，すなわち対象の変数を引数として持つリテラルの述語を指す．}を持つ可能性が存在しないならば（すなわち同じ述語を持ち，単一化仮説生成によって等価仮説$a=b$を導くような内容語リテラル対が潜在仮説集合$P$に存在しないならば）等価仮説$a=b$は不正である($a=^*b$)とする．第二に，仮説に含まれる論理式の文法的正しさを評価することを前提とし，以下のような条件で表す：\begin{itemize}\item[条件3.]評価関数は親を持たない機能リテラルを含む候補仮説を解仮説として選択しない．\end{itemize}前述のとおり，親を持たない機能リテラルは文法的に不正であるので，本論文ではこの文法的正しさに関して，評価関数が条件3を満たしていることを前提とする．以降では，これらの条件1,2,3をまとめて\textbf{仮説の整合性条件}と呼ぶ．\subsection{機能リテラルに係る推論による計算の非効率化}\label{sec:prob:main}\ref{sec:prob:mr}~節で述べた意味表現と評価関数のもとで，先行研究の仮説推論エンジンを用いてIAを実現する場合，機能リテラルを根拠とした単一化仮説生成操作および後ろ向き推論操作により，解仮説に含まれることのない要素仮説が潜在仮説集合に追加され，推論時間を増大させてしまうという問題がある．例えば図\ref{fig:exprob1}では，観測に含まれる$\mathit{nsubj}(e_3,j)$と$\mathit{nsubj}(e_4,t)$に対して単一化仮説生成操作を適用することで，等価仮説$e_3=e_4$（$\mathit{smart}$イベントと$\mathit{foolish}$イベントは同一事象），および$j=t$（JohnとTomは同一人物）が潜在仮説集合に追加されている．また図\ref{fig:exprob2}では，観測に含まれる$\mathit{smart}(e_1)$と$\mathit{foolish}$の主格を表すリテラル$\mathit{nsubj}(e_2,t)$を根拠として，$e_1=e_2$という仮定のもと知識適用を行い，$\{\mathit{study}(e_3),\mathit{nsubj}(e_3,t)\}$を潜在仮説集合に追加している．\begin{figure}[b]\begin{center}\includegraphics{23-3ia2f3.eps}\end{center}\caption{不適切な単一化仮説生成によって誤った解釈が導かれる例}\label{fig:exprob1}\end{figure}しかしながら，これらの推論は論理的には可能であるものの，\ref{sec:prob:mr}~節で述べた仮説の評価関数に関する前提より，これらの仮説が最良の説明として選択されることは無い．このような推論は同じ述語を持つリテラルに対して組み合わせ的に発生し（例えば，「$\textit{smart}\text{を述語に持つリテラルの数}\times\textit{nsubj}\text{を述語に持つリテラルの数}$」の分だけ発生する），かつ候補仮説の数は潜在仮説集合の規模に対して指数関数的に増大するため，計算負荷の観点において重大な問題であると考えられる．\begin{figure}[t]\begin{center}\includegraphics{23-3ia2f4.eps}\end{center}\caption{不適切な後ろ向き推論によって誤った解釈が導かれる例}\label{fig:exprob2}\end{figure}この問題の本質的な原因は，先行研究の潜在仮説集合生成手続き（\ref{sec:potential}~節）における各操作において，論理変数間の等価性の意味的な整合性を考慮できていないことにある．例えば図\ref{fig:exprob1}において，$\mathit{nsubj}(e_3,j)$と$\mathit{nsubj}(e_4,t)$に対する単一化仮説生成操作によって等価仮説$e_3=e_4$が潜在仮説集合に追加されるが，このとき，この等価仮説が不正かどうか（つまり，解釈「$\mathit{study}$であり，かつ$\mathit{mistake}$であるようなイベント$e_3(=e_4)$が存在する」が実現可能なものか）は考慮されていない．その結果，図\ref{fig:exprob1}のように，不正な等価仮説であっても，潜在仮説集合に追加されてしまう．本節で述べた問題は，意味表現としてNeo-Davidsonian形式を採用した場合に—すなわち述語と項の関係を$\mathit{nsubj}(x,y)$のように個別のリテラルとして表現した場合に起こる問題である．しかし，これに限らず，Hobbsらの研究\cite{Hobbs93}のように，名詞間の意味的関係（部分全体関係など）や統語的関係（複合名詞を構成する名詞間の関係など）を$\mathit{part\_of}(x,y)$や$\mathit{nn}(x,y)$のようなリテラルで表現する場合にも，上述のような問題が生じる．このようなリテラルは一階述語論理式で自然言語の情報を表す上で必要不可欠であり，本節で述べた問題はIAの研究において決して些末な問題ではない．このような問題に対し本論文では，\ref{sec:potential}~節で述べた潜在仮説集合生成に係る操作において等価仮説の生成を伴う場合，等価仮説が不正でない場合にのみ操作の適用を許すことで，解として選ばれない等価仮説を潜在仮説集合から除外する手法を提案する．例えば図\ref{fig:exprob1}における$\mathit{nsubj}(e_3,j)$と$\mathit{nsubj}(e_4,t)$に対する単一化仮説生成操作の適用時には，まず\ref{sec:prob:mr}~節で述べた基準により$e_3=e_4$の正しさをチェックする（つまり，$\mathit{study}$かつ$\mathit{mistake}$であるような事象が存在しうるか）．ここで仮に「$\mathit{study}$と$\mathit{mistake}$が同一事象に成り得ない」ことがわかったとすると，$e_3=e_4$は不正な等価仮説であり，$e_3=e_4$が解仮説に含まれる可能性がないため，操作の適用を行わない．4節では，これらのアイデアに基づき，2.1節で説明した潜在仮説集合生成の手続きを拡張し，より効率的に潜在仮説集合を生成する方法を提案する．また5節では，これらのアイデアに基づき，A*-basedAbduction\cite{Yamamoto15}の計算効率を改善する手法を提案する．なお，以降の記述では便宜的に，機能リテラルは全て次のような形式をとるものとする：\begin{itemize}\itemアリティは2．\itemリテラルの第一引数が依存関係のgovernor，第二引数がdependentを表す．\end{itemize}自然言語における単語間の依存関係の多くは2項間関係として表されること，多項関係は一般に2項間関係の組み合わせとして一般化できることなどから，このように定義を限定した場合においても一般性は失われない．
\section{等価仮説への制約による効率化}
本節では，\ref{sec:potential}~節で定義した後ろ向き推論操作，および単一化仮説生成操作に対して適用条件を付加することにより，不正な等価仮説を探索空間から除外する方法を提案する．\subsection{機能的述語の単一化に対する制約}\label{sec:cons-unify}2節で述べた通り，先行研究\cite{Inoue11,Inoue12,Yamamoto15}における単一化仮説生成の適用は，述語の同一性にのみ依拠している．しかしながら，\ref{sec:prob:mr}~節で述べた設定の下では，機能リテラル対に対する単一化仮説生成操作によって，不正な等価仮説が潜在仮説集合に追加されてしまう可能性がある．仮説の整合性条件が充足されているとすると，不正な等価仮説を含む仮説は解仮説として選択されないため，そのような仮説が候補仮説に含まれてしまうことは，推論効率の面で無駄が生じる．我々はこの問題に対処するために，機能リテラル対に対する単一化仮説生成を行う際に「それぞれのgovernor（第一引数）の論理変数の間の等価性を導く，不正でない等価仮説が既に仮説されていること」という条件を追加する．例えば図\ref{fig:exprob1}の観測における機能リテラル対$\mathit{nsubj}(e_3,j)$,$\mathit{nsubj}(e_4,t)$に対する単一化仮説生成の適用は，等価仮説$e_3=e_4$が潜在仮説集合に既に含まれている場合に限定する．これにより，親が互いに同一事象に成り得ない機能リテラル対は単一化仮説生成の対象とならず，不正な等価仮説が潜在仮説集合に追加されなくなるので，推論効率の向上が期待できる．より一般的には，潜在仮説集合$P$において，機能述語$d$を持つ機能リテラル対$d(x_1,y_1)$,$d(x_2,y_2)$に対して単一化可能性を認め，そこから導かれる等価仮説$x_1=x_2$,$y_1=y_2$を潜在仮説集合に追加するのは，$x_1$,$x_2$が同一の変数である場合か，等価仮説$x_1=x_2$が$P$に含まれている場合に限る．このような制約により，機能リテラル間の単一化仮説生成が適用されるのは，それぞれの機能リテラルが表す依存関係のgovernorが互いに同一である可能性がある場合に限定され，常に不正な等価仮説を導くような単一化仮説生成操作の実行を防止できる．この制約をどのようなアルゴリズムとして実装するかについては\ref{sec:cons-implement}節で述べる．\subsection{後ろ向き推論への拡張}\label{sec:cons-chain}後ろ向き推論操作についても，単一化仮説生成操作と同様の議論を行うことができる．本節ではそれを踏まえ，前節と同等の制約を後ろ向き推論操作にも課すことを考える．例えば図\ref{fig:exprob2}において，論理式$\mathit{study}(e_3)\land\mathit{nsubj}(e_3,t)\Rightarrow\mathit{smart}(e_1)\land\mathit{nsubj}(e_1,t)$による後ろ向き推論を連言$\mathit{smart}(e_1)\land\mathit{nsubj}(e_2,t)$に対して適用する場合について，この後ろ向き推論操作の適用条件として「潜在仮説集合に不正でない等価仮説$e_1=e_2$が含まれていること」を課す．これにより，不正な等価仮説を導く後ろ向き推論を潜在仮説集合の生成手続きから除外することができる．このとき，全ての後ろ向き推論に制約を課してしまうと，本来除外するべきでない推論が除外されてしまう場合があることに注意する必要がある．例えば図\ref{fig:chain}における後ろ向き推論に上の制約を課した場合，等価仮説$x_1=x_3$が潜在仮説集合に含まれていることが後ろ向き推論適用の条件となるが，等価仮説$x_1=x_3$を導くためにはその後ろ向き推論を実行する必要がある．そのため，上の制約を課した場合にはこの推論は探索空間から除外されてしまう．しかしながら，図\ref{fig:chain}の仮説は最終的には不正な等価仮説を含まないため，本来は除外するべきでない．以上の議論より本論文では，このような場合を引き起こしうる論理式を用いた後ろ向き推論については制約を課さないことによって，除外すべきでない候補仮説—すなわち不正な等価仮説を含まない候補仮説が探索空間から除外される事態を防ぐ．上のような場合を引き起こしうる論理式とは，具体的には，論理式の後件中の機能リテラルの親になっているリテラルが前件に含まれるような論理式である．そのような論理式を用いた後ろ向き推論については，制約の対象から除外する．例えば図\ref{fig:chain}の例では，後件の機能リテラル$in(x_1,x_2)$の第一引数$x_1$が前件のリテラル$\mathit{student}(x_1)$の引数に含まれており，$\mathit{student}(x_1)$は$in(x_1,x_2)$の親であると言えるので，この論理式を用いた後ろ向き推論については制約の対象としない．\begin{figure}[b]\begin{center}\includegraphics{23-3ia2f5.eps}\end{center}\hangcaption{探索空間から除外すべきではないにも関わらず，等価仮説の制約によって実行不可能になってしまう後ろ向き推論の例．}\label{fig:chain}\end{figure}以上のアイデアをより一般的に表そう．潜在仮説集合$P$において，含意型論理式$\bigwedge_{i=1}^np_i(x_i)\Rightarrow\bigwedge_{j=1}^mq_j(y_j)$を用いた後ろ向き推論を，$P$に含まれる連言$\bigwedge_{j=1}^mq_j(z_j)$に適用する場合を考える．ここで，述語$q_f$が機能述語であるようなインデックス$f$の集合を$F$とすると，この逆向き推論を適用するのは，$F$の各要素$f$が以下の条件のうち少なくとも一つを満たしている場合に限る：\begin{enumerate}\item$q_f(y_f)$の第一引数$y_f^1$を引数に持つリテラルが論理式の前件に存在する．すなわち$y_f^1\in\bigcup_{i=1}^nx_i$が成り立つ．\item論理式の後件の$c$番目にある内容語リテラル（$q_c(y_c)$とおく）の任意の（$i$番目の）引数$y_c^i$が$y_f^1$と同一であるとき，変数対$z_c^i$,$z_f^1$が同一であるか，もしくは潜在仮説集合に等価仮説$z_c^i=z_f^1$が含まれる．\end{enumerate}この条件を満たさない逆向き推論は，常に不正な等価仮説を導くので，探索空間から除外できる．この制約をどのようなアルゴリズムとして実装するかについては\ref{sec:cons-implement}節で述べる．\subsection{潜在仮説集合の生成手続きの拡張}\label{sec:cons-implement}\ref{sec:cons-unify}節および\ref{sec:cons-chain}節では，単一化仮説生成操作および後ろ向き推論操作の適用条件として，不正な等価仮説を生成しないことを条件とすることにより，不正な等価仮説が潜在仮説集合に追加されることを回避する手法を示した．本節では，これらの手法を実際にアルゴリズムとして実装する方法を議論する．まず，各操作の適用条件の充足性と，潜在仮説集合の状態は互いに依存しているため（つまり，適用条件の充足性は潜在仮説集合の状態で決まり，かつ潜在仮説集合の状態は各操作の適用条件の充足性により変化する），各操作に対する条件の充足性判定は，各操作の適用時に一度ずつ行うだけでは不十分である．なぜなら，潜在仮説集合を生成する過程において，ある時点では適用条件を充足せず適用不可能な操作であっても，その後の別の時点では，別の操作の適用により条件が充足され，適用可能となる場合があるからである．そのため，最終的に適用されなかった全ての操作が制約を充足しないことを保証できるよう，各操作に対する適用条件の充足性を漏れが無いように判定する必要がある．以上のような考えに基づき，\ref{sec:potential}~節で述べた潜在仮説集合の生成手続きを次のように変更する：\begin{enumerate}\item観測$O$を潜在仮説集合$P$に追加する．これが初期状態となる．\item潜在仮説集合$P$に対して適用可能な後ろ向き推論および単一化仮説生成操作を，A*-basedAbductionの手法に基いて網羅的に適用する．ただし，\ref{sec:cons-unify}~節および\ref{sec:cons-chain}~節で提案した適用条件を満たさない単一化仮説生成・後ろ向き推論は実行しない．制約条件を満たさずに実行されなかった単一化仮説生成・後ろ向き推論については，別の記憶領域$S$に保持しておく．\itemこの時点で$S$が空の場合は，潜在仮説集合の生成を終了する．\item$S$に含まれる単一化仮説生成操作および後ろ向き推論操作のそれぞれについて，再び制約を満たすかどうかの判定を行う．満たすのなら操作を適用し，$S$から除外する．\item手続き(4)において一つの操作も実行されなかった場合は潜在仮説集合の生成を終了し，そうでなければ手続き(2)に戻る．\end{enumerate}このような実装を採ることにより，最終的に適用されなかった操作については全て適用条件を満たさないことが保証される．\ref{sec:cons-unify}節および\ref{sec:cons-chain}節での議論より，適用条件を満たさない操作は不正な等価仮説を導くので，仮説の整合性条件より，これらの操作によって導かれる要素仮説が本来の解仮説に含まれることは無い．すなわち，等価仮説への制約を課す前後で解仮説が変化しないことが保証される．
\section{A*-basedAbductionの効率化}
\label{sec:stopword}機能リテラルを含む背景知識を用いた仮説推論をA*-basedAbduction\cite{Yamamoto15}に適用する際，探索空間の枝刈りの精度が著しく低下するという問題がある．本節ではそのような問題の解決策として，探索のガイドとして用いるヒューリスティック関数の計算方法を改良することにより，枝刈りの精度の低下を抑える手法を提案する．本節では，まずA*-basedAbductionについて説明し（\ref{sec:yamamoto15}~節），機能リテラルが引き起こす枝刈り精度低下の問題（\ref{sec:sw-prob}~節）と解決策（\ref{sec:sw-sw}~節）について述べる．\subsection{A*アルゴリズムに基づく仮説推論}\label{sec:yamamoto15}まず，A*-basedAbductionのベースとなるILP-basedAbduction\cite{Inoue11b,Inoue12b}について説明する．ILP-basedAbductionでは，まず観測と背景知識を入力として受け取り，それらに対して\ref{sec:potential}~節の潜在仮説集合生成手続きを適用し，潜在仮説集合を生成する．次に，潜在仮説集合と評価関数から，ILP問題を生成する．ここでは，仮説中での各リテラルの有無がILP変数の0-1値に，仮説に対する評価関数の値がILP問題の目的関数値に対応し，各リテラル間の論理的な依存関係はILP制約として表現される．最後に，ILPソルバ\footnote{lp\_solve(http://lpsolve.sourceforge.net)やGurobiOptimizer(http://www.gurobi.com)などがある．}を用いてILP問題を解くことにより，解仮説が得られる．A*-basedAbductionは，ILP-basedAbductionの潜在仮説集合の生成手続きをA*アルゴリズムに基づいて改良するものであり，解仮説に含まれる見込みが高い仮説を生成する操作を優先的に適用していくアルゴリズムである．より具体的には，まず事前準備として，背景知識における述語間の意味的な距離を評価しておく．ここでの述語間の意味的な距離とは，一方の述語から他方の述語に至る推論によって生じる評価関数値の増減量のヒューリスティックな見積もりである．同じ論理式に含まれる述語を互いに隣接関係にあると見なすと，図\ref{fig:heuristic1}のように節点を述語，枝を隣接関係とする無向グラフ（以後，\textbf{述語グラフ}と呼ぶ）が得られる\footnote{論理プログラミング分野の慣習に従い，アリティ（引数の数）がnであるような述語pを$p/n$と表す．}．述語間の意味的な距離は，このグラフにおける距離—即ち述語間を繋ぐ枝の長さの総和として与えられる．各枝の長さは，枝に対応する知識ごとに自由に定義できる\footnote{一般には，後ろ向き推論に用いた時に評価値が大きく減少する知識ほど，対応する枝の距離が長くなるように定義する．例えば重み付き仮説推論では，知識に割り当てられた重みを述語グラフ上での距離として用いる．}が，本論文では議論の簡単のために全ての枝の長さを1と定める．このとき述語グラフにおける述語間の距離は，一方の述語から他方の述語に至る推論の段数と一致する．例えば図\ref{fig:heuristic1}によれば，図\ref{fig:ia}の背景知識において，述語$\mathit{bank}$,$\mathit{issue}$を持つリテラル同士を推論で繋ぐには最低でも3つの論理式を経由しなければならず，また述語$\mathit{he}$,$\mathit{money}$を持つリテラル間を結びつけるような推論は存在しない事が分かる．述語グラフの構造は背景知識にのみ依存するので，あらゆる述語対に対する距離を事前に計算しておき，行列として保持しておくことが可能である．\begin{figure}[t]\begin{center}\includegraphics{23-3ia2f6.eps}\end{center}\caption{図\ref{fig:ia}の背景知識に対応した無向グラフ}\label{fig:heuristic1}\end{figure}次に，述語グラフに基づいて後ろ向き推論操作の良さを見積もりながら，潜在仮説集合の生成を行う．A*-basedAbductionの潜在仮説集合の生成手続きでは，「単一化仮説生成に寄与しないリテラルは解仮説に含まれない」という前提に基づき，解仮説に含まれる見込みがあるリテラル，すなわち単一化仮説生成に寄与しうるリテラルを仮説する後ろ向き推論操作のみを，評価関数の増減量の見込みがより高いものから優先的に実行していく．より具体的には，述語グラフにおける述語間の距離をA*アルゴリズムにおけるヒューリスティック関数として用いて，観測中の個々のリテラルから他のリテラルに至る推論を探索\footnote{この探索においては，始点と終点は観測リテラルであり，始点からあるリテラルまでの移動距離は，述語グラフと同様に，その間で用いられている知識に対応した枝の長さの総和で与えられる．}することによって，単一化仮説生成に寄与しない後ろ向き推論（すなわち他のどのリテラルとも距離が無限大になるようなリテラルを根拠とした後ろ向き推論）は適用対象から除外しつつ，評価関数値の増減量の見込みが高い後ろ向き推論（すなわち他のリテラルとの述語間距離が近いリテラルを根拠にした後ろ向き推論）から優先的に適用していく．これにより，解仮説に含まれ得ないリテラルを仮説するような後ろ向き推論操作は探索空間から除外され，結果として推論全体の計算効率が改善される．例えば図\ref{fig:lhs}の潜在仮説集合における$\mathit{cat}(x)$や$\mathit{poodle}(x)$は，それ自身が単一化仮説生成操作の対象になることも，そこから仮説されたリテラルが単一化仮説生成操作の対象になることも無いので，これらのリテラルを仮説するような後ろ向き推論操作は実行されない．また，評価関数値の増減量の見込みが高い推論が優先して実行されることにより，潜在仮説集合の生成にかけられる時間が制限された状況においても，より良い解が探索空間に含まれるように，与えられた時間内で可能な限り最善の探索を行う．これは実用においては極めて大きな利点である．さて，以降の議論のために用語を一つ定義する．単一化仮説生成の対象となったリテラル対$l_1$,$l_2$と，それらの根拠である観測リテラル対$o_1$,$o_2$について，$o_1$,$o_2$から$l_1$,$l_2$をそれぞれ仮説するために必要な後ろ向き推論と，$l_1$,$l_2$間の単一化仮説生成操作から構成される操作の系列を，$o_1$,$o_2$の間の{\bf推論パス}と呼ぶことにする．例えば図\ref{fig:ia}において，リテラル対$\mathit{go}(x_1,x_2)$,$\mathit{get}(y_1,y_2)$の間の推論パスは，(1)$\mathit{go}(x_1,x_2)$から$\mathit{issue}(x_2,u_1,x_1)$への後ろ向き推論，(2)$\mathit{go}(y_1,y_2)$から$\mathit{issue}(u_2,y_2,y_1)$への後ろ向き推論，(3)$\mathit{issue}(x_2,u_1,x_1)$と$\mathit{issue}(u_2,y_2,y_1)$の間の単一化仮説生成によって構成される．定義より，全ての推論パスは，1回の単一化仮説生成操作と0回以上の後ろ向き推論操作によって構成されることに注意されたい\footnote{この定理は，付録Aに示す解の最適性の証明において必要となる．}．また，ある推論パスについて，そこに含まれる操作の系列に関与している観測リテラルの集合，すなわち推論パスで作られる推論が説明している観測リテラル集合を，推論パスの{\bf根拠}と呼ぶ．さて，現在の仮説推論の実装としてはA*-basedAbductionが最も高速であるが，彼らの枠組みを適用する際，その評価関数は次の要件を満たしていなければならない．一つ目に，彼らの枠組みはILP-basedAbduction\cite{Inoue11,Inoue12b}に基づいた枠組みであるため，評価関数は整数線形計画問題で表現可能であるものでなければならない．二つ目に，冗長な仮説に対しては評価が低下すること，すなわち単一化仮説生成に寄与しないリテラルが解仮説に含まれ得ないことが保証されていなければならない．なお，この条件については，Hobbsらの重み付き仮説推論をはじめとして，Thagard\cite{Thagard78}の提唱する「仮説の良さは簡潔さと顕現性によって決定される」とする主張に基づいて定義された評価関数であれば一般に充足される．ここで，二つ目の条件をNeo-Davidsonian形式に合わせて拡張することを考えよう．例えば，図\ref{fig:phi}(a)のNeo-Davidsonian形式で表現された推論は，表す意味そのものは図\ref{fig:phi}(b)のDavidsonian形式で表現された推論と同等であることから，図\ref{fig:phi}(b)と同様に解仮説には含まれ得ないと考えてよい．すなわち図\ref{fig:phi}(a)のように，単一の内容語リテラルとそれを親とする機能リテラルだけを根拠とする推論パスは，Thagardの主張に従うならば，解仮説には含まれないものと考えてよい．\begin{figure}[t]\begin{center}\includegraphics{23-3ia2f7.eps}\end{center}\hangcaption{異なる意味表現形式における冗長な推論の例．推論(a)はNeo-Davidsonian形式で，推論(b)はDavidsonian形式で，それぞれ同様の冗長な推論を表している．}\label{fig:phi}\end{figure}以上の議論から，以降で扱う評価関数は，整数線形計画問題で等価に表現可能であるとともに，以下に示す条件を充足すると仮定する：\begin{itemize}\item評価関数は，単一化仮説生成に寄与しないリテラルを含む候補仮説を解仮説として選択しない．\item評価関数は，単一の内容語リテラルとそれを親とする機能リテラルのみを根拠とした推論パスを含む候補仮説を解仮説として選択しない．\end{itemize}以降ではこれらの条件をまとめて仮説の{\bf簡潔性条件}と呼ぶ．\subsection{述語間距離の推定精度の低下}\label{sec:sw-prob}\ref{sec:yamamoto15}節で述べたようにA*-basedAbductionでは，図\ref{fig:heuristic1}のような述語グラフを用いて，背景知識における述語間の意味的な距離を事前に評価しておき，仮説の探索空間の枝刈りを行う．述語グラフの上では，論理式の前件に含まれる各述語と後件に含まれる各述語のあらゆる組み合わせが接続されるため，機能リテラルのような，他のリテラルと高頻度で共起するリテラルを背景知識に含む場合には，述語グラフの中にハブとなるノードが形成される．その結果，解仮説を含まれ得るような推論が実際には存在しないリテラル対に対しても，誤って距離を近く見積もってしまう，という問題がある．例えば図\ref{fig:exprob1}で用いられている背景知識$B$を考える：\begin{align*}mistake(e_1)\landnsubj(e_1,x)&\Rightarrowfoolish(e_2)\landnsubj(e_2,x)\\study(e_1)\landnsubj(e_1,x)&\Rightarrowsmart(e_2)\landnsubj(e_2,x)\end{align*}この背景知識に対して\ref{sec:yamamoto15}節で述べた手続きによって述語グラフを生成すると，図\ref{fig:sw1}(a)のような述語グラフが作られる．前述のように，背景知識に含まれる機能述語$\mathit{nsubj}/2$がハブノードとなり，あらゆる内容語述語のペアが互いに到達可能と判定されることがわかる．しかし，これらの推論パスにより生成される仮説の中には，解仮説として選択されないことが保証されるものも含まれる．例えば，図\ref{fig:sw1}(a)より，$\mathit{foolish}$と$\mathit{smart}$を述語に持つリテラル対を結ぶような推論パスは存在すると推定されるが，3節で見てきたように，この推論パスから生成される仮説は不正な等価仮説を導くため，解仮説には成り得ない．\begin{figure}[t]\begin{center}\includegraphics{23-3ia2f8.eps}\end{center}\hangcaption{提案手法による枝刈りの適用前後における述語グラフ．(a)が従来手法による述語グラフ，(b)が\ref{sec:sw-sw}節で提案する手法による述語グラフである．}\label{fig:sw1}\end{figure}このように，従来の述語グラフでは，述語間を繋ぐ推論が不正な等価仮説を導くかどうか考慮できていないために，機能リテラルを含む背景知識の上での述語間距離の推定精度が低下し，A*-basedAbductionの利点が失われてしまっている．\subsection{述語グラフの枝刈りによる高速化}\label{sec:sw-sw}本研究では，\ref{sec:sw-prob}節で述べた問題を解消するために，述語グラフから特定の枝を除外することを提案する．つまり，図\ref{fig:exprob1}における$\mathit{foolish}(e)$と$\mathit{smart}(e)$のように，あるリテラル対を繋ぐ推論パスが常に不正な等価仮説を導く時に，それらの間の距離が無限大となるように，述語グラフの枝を除外する．これにより不正な等価仮説を導く推論は探索空間から除外され，探索を効率化できる．具体的な手法を述べる．本手法では，A*-basedAbductionについて，以下の2点の拡張を加える：\begin{itemize}\item述語グラフの構築において，機能リテラルとその親の両方が前件あるいは後件に存在する含意型論理式に対しては，親に対する枝だけを述語グラフに追加するものとする．例えば$\mathit{study}(e_1)\land\mathit{nsubj}(e_1,x)\Rightarrow\mathit{smart}(e_2)\land\mathit{nsubj}(e_2,x)$という論理式に対しては，$\mathit{study}$と$\mathit{smart}$の間の枝だけを追加し，$\mathit{nsubj}$への枝は追加しない．\item潜在仮説集合の生成において，機能リテラルと他のリテラルの間の述語間距離には，機能リテラルの親の述語間距離を代わりに用いるものとする．例えば図\ref{fig:exprob1}の観測において，$\mathit{nsubj}(e_1,j)$の親は$\mathit{smart}(e_1)$であるので，$\mathit{nsubj}(e_1,j)$と$\mathit{foolish}(e_2)$の述語間距離には，$\mathit{smart}(e_1)$と$\mathit{foolish}(e_2)$の述語間距離を用いる．なお，親が複数存在する場合には，それらの中での最低値を採用するものとする．\end{itemize}このように拡張することで，不正な等価仮説を導く推論は探索空間から除外される．例えば，図\ref{fig:exprob1}の背景知識では，図\ref{fig:sw1}(a),(b)に示されるように，機能述語$\mathit{nsubj}/2$への枝が述語グラフから取り除かれる．その結果，述語$\mathit{smart}$と$\mathit{foolish}$の間の距離が無限大となり，不正な等価仮説を導く$\mathit{smart}$,$\mathit{foolish}$を繋ぐ推論は，探索空間から除外される．なお，本手法を適用したときに得られる解は，仮説の整合性条件および簡潔性条件が充足されている限り，手法を適用しない場合の解と同様の解が得られること，すなわち元々の解が提案手法によって探索空間から枝刈りされないことが保証される．詳細な説明は付録Aに委ねるものとする．
\section{実験}
\subsection{基本設定}本節では，本論文にて行った実験における基本的な設定について述べる．本実験における観測としては，Rahmanら~\cite{Rahman12}によって構築されたWinogradSchemaChallenge~\cite{Levesque11}の訓練データの問題1,305問をそれぞれ論理表現に変換したものを用いた．具体的には，各問題文に対してStanfordCoreNLP\footnote{http://nlp.stanford.edu/software/corenlp.shtml}\cite{CoreNLP}を用いて構文解析を行い，文中の単語および単語間の依存関係をそれぞれリテラルに変換した．各観測は平均して28個のリテラルから構成される．観測の例を表1の$O$に示す．なお，全ての観測について整合性条件を充足することを確認している．以降はこの観測集合を$O_\mathit{wsc}$と表す．WinogradSchemaChallengeは，例えば``{\itTonyhelpedJeffbecausehewantedtohelp.}''のような文を入力として，指定された照応表現（ここでは``{\ithe}''）の照応先として相応しいものを2つの選択肢（ここでは``{\itTony}''と``{\itJeff}''）から選ぶタスクである．仮説推論の上では，照応先の選択は等価仮説の有無に対応する．例えば，表1の$O$に対して得られた解仮説に$E_1=e_5$が含まれるなら，``{\ithe}''の照応先として``{\itTony}''を選ぶことと等しい．なお，本実験では，各問題の照応先に対応する論理変数には定数（この例では$E_1$,$E_3$）を割り当てることで，二つの照応先候補を同時に選択することを防いでいる．\begin{table}[t]\hangcaption{実験で用いた観測および背景知識の例．なお観測の例は``\textit{TonyhelpedJeffbecausehewantedtohelp.}''という文に対応する論理表現である．}\label{tab:example}\input{02table01.txt}\end{table}また背景知識には，我々がClueWeb12\footnote{http://lemurproject.org/clueweb12/}から自動獲得した因果関係知識を用いた．具体的には，まず，ClueWeb12に含まれる各文に対してStanfordCoreNLPを適用し，共参照関係にある項を持つ動詞・形容詞とその周辺文脈のペア5億個を獲得した．例えば，``\textit{Tomhelped\underline{Mary}yesterday,so\underline{Mary}thankedtoTom.}''より，\textit{Mary}を介してペアとなっている$\langle$\textit{TomhelpMaryyesterday},\textit{MarythanktoTom}$\rangle$を獲得した．獲得したペアは，そのまま因果関係知識として用いるには特殊すぎる可能性があるため，これらを統計的な基準によって一般化し，論理表現に変換した．より具体的には，獲得したペアをさまざまな抽象度に一般化した上で（例えば，$\langle$\textit{TomhelpMaryyesterday},\textit{MarythanktoTom}$\rangle$を$\langle$\textit{TomhelpX},\textit{XthanktoTom}$\rangle$,$\langle$\textit{helpX},\textit{Xthank}$\rangle$などに変換した）頻度カウントを行い，一定以上の頻度のペアだけを残す，というフィルタリング処理を施した（以降，これらのペアを\textbf{イベントペア}と呼ぶ）．結果として，278,802個の含意型論理式の集合$B_\mathit{ep}$を得た．知識の例を表1の$B_\mathit{ep}$に示す．また，WordNetのSynsetによって定義される同義語・上位語の知識を論理表現に変換し，結果として235,706個の含意型論理式の集合$B_\mathit{wn}$を得た．WordNetから生成した論理式の例を表1の$B_\mathit{wn}$に示す．提案手法を適用するにあたっては，背景知識に出現する格関係および前置詞による修飾関係を表す全ての述語を機能述語として扱うこととした．評価関数には重み付き仮説推論\cite{Hobbs93}を基に，整合性条件および簡潔性条件を充足するような評価関数を用いた．具体的には，重み付き仮説推論の評価関数に対して「全ての候補仮説は仮説の整合性条件および簡潔性条件を満たさなければならない」という制約を加えている．比較対象としてはA*-basedAbduction\cite{Yamamoto15}を用いた．以降の記述における従来手法とはA*-basedAbductionを指す．実験は\cite{Yamamoto15}の実装であるPhillip\footnote{http://github.com/kazeto/phillip.git}の上で行い，本論文の提案手法もPhillipを拡張することによって実装した．\subsection{推論効率の比較}本節では，推論効率の比較実験について報告する．この実験では，提案手法が従来手法と比べてどの程度効率的に最適解を導くことができるかを確かめるために，従来手法でも最適解が導出できる程度に小規模な設定での比較を行った．また，従来手法のほかに，4節の制約のみを用いた設定，5節の述語グラフの枝刈りのみを用いた設定との比較も行うことで，個々の手法による効率化の度合いを検証した．具体的な設定を以下に述べる，観測には$O_\mathit{wsc}$に含まれる全ての問題（1,305問）を用いた．背景知識には，$B_\mathit{ep}$から187,732個の論理式を抽出\footnote{$B_\mathit{ep}$の論理式のうち，ClueWeb中での共起頻度がある閾値を超えるイベントペアから生成された論理式のみを抽出した．背景知識を適当な規模に縮小する以外の意図は無いので，詳細は省略する．}して用いた．また，リテラルの深さの最大値は$d_\mathit{max}=1$とした．これにより後ろ向き推論の入力は観測リテラルのみに限定される．また，推論時間が5分を超えるものについてはタイムアウトとした．この実験設定を，以降は{\bfSMALL}と呼ぶ．\begin{figure}[b]\begin{center}\includegraphics{23-3ia2f9.eps}\end{center}\caption{実験設定SMALLでの，提案手法と従来手法との速度比較．}\label{fig:result1}\end{figure}\begin{figure}[t]\begin{center}\includegraphics{23-3ia2f10.eps}\end{center}\caption{実験設定SMALLでの，等価仮説の制約の有無における速度比較．}\label{fig:result2}\end{figure}\begin{figure}[t]\begin{center}\includegraphics{23-3ia2f11.eps}\end{center}\caption{実験設定SMALLでの，述語グラフの枝刈りの有無における速度比較．}\label{fig:result3}\end{figure}実験設定SMALLにおける実験結果を図\ref{fig:result1}，図\ref{fig:result2}，図\ref{fig:result3}に示す．図中の各点は開発セット1,305問のうち，少なくとも一方の実験設定がタイムアウトせずに最適解を求められた問題1,095問\footnote{提案手法においてタイムアウトした問題はいずれも，他の実験設定においてもタイムアウトしていた．そのため1,095問というのは実質，提案手法がタイムアウトしなかった問題数に等しい．}について，それぞれの問題における推論時間を表す．各点の座標は，横軸が提案手法による推論時間に対応し，縦軸が比較対象での推論時間に対応する．図\ref{fig:result1}ではA*-basedAbductionによる推論時間，図\ref{fig:result2}では提案手法において5節で述べた述語グラフの枝刈りのみを適用した場合の推論時間，図\ref{fig:result3}では提案手法において4節で述べた等価仮説への制約のみを適用した場合の推論時間が，縦軸に対応する．なお，5分以内に解を導くことが出来ずタイムアウトした問題については300秒としてプロットしている．また直線は$y=x$を表す．よって，この直線よりも上にある点については提案手法によって推論時間が改善されていると見做すことができる．図\ref{fig:result1}からは，従来手法と比べたときの，提案手法による効率化の程度を確認できる．この結果より，どのような規模の問題においても提案手法は従来手法と比べて遥かに短い時間で，平均して数十倍から数百倍の速度で解を導けていることが確かめられた．図\ref{fig:result2}からは，4節で提案した等価仮説の制約による効率化の程度を確認することができる．この結果から，探索空間が極めて小さい一部の問題に対しては効率の低下が見受けられるものの，それ以外の問題についてはいずれもより効率的な推論が実現できていることが確かめられた．推論効率が低下している一部の問題については，この制約によって除外されるような単一化仮説生成操作が探索空間に存在しない，あるいはその数が極めて少ないために，制約の判定にかかる計算量が制約を課すことで削減される計算量を上回ってしまっていると考えられる．図\ref{fig:result3}からは，5節で提案した述語グラフの枝刈りによる効率化の程度を確認することができる．図\ref{fig:result1}での結果とほぼ同様の結果であるものの，述語グラフの枝刈りによって探索空間から除外される推論は，等価仮説の制約によって探索空間から除外される推論の大半を包含していることから，これは極めて自然な結果であるといえる．また，タイムアウトせずに最適解が得られた問題については，問題設定に関わらず最適解の評価関数値が同じ値であったことが確かめられた．このことから，提案手法が解の健全性を損なわないことが実験的にも示された．\subsection{現実的な設定での比較}前節の実験では，提案手法が従来手法と比べて遥かに効率的に解仮説を導出できていることが確かめられた．しかしながら前節の実験設定(SMALL)では，従来手法でも最適解が導けるようにするために，背景知識や解の探索範囲の縮小や，タイムアウトの時間を長めにとるなど，実際のタスク適用とはかなり乖離した設定になってしまっている．それを踏まえ本節では，参考実験として，より実際のタスク適用に即した設定において比較実験を行った．この実験では，（本論文の本来のスコープではないものの，）タスクの解析精度をみることで，我々のシステムが行っている推論が，意味的な解釈として一定の妥当性を持つ推論を実現できていることを確かめる．具体的な設定を述べる．前述したように，今回用いたデータセットには，因果関係知識のみでは解くことの出来ない種類の問題—例えば否定や逆接を含む問題，特定の固有名詞に関する知識が必要な問題，数量表現を扱う問題など—が多数含まれている．そこで本実験では，$O_\mathit{wsc}$に含まれる観測のうち無作為に選んだ100問について，個々の問題を解くのに必要な知識の種類を人手で分類した．そして，その100問のうち因果関係知識の適用のみで解けると思われる問題32問を観測として用いた．背景知識としては，$B_\mathit{ep}$と$B_\mathit{wn}$に含まれる全ての論理式（514,508個）を用いた．またリテラルの深さの最大値は$d_\mathit{max}=2$とした．これは，3個以上の因果関係を繋げて導かれる仮説は意味的に不自然な説明であることが多いという経験則に基いている．また，潜在仮説集合の生成は10秒で中断し，その時点での潜在仮説集合に対する解を解仮説として扱った．推論全体では，推論時間が1分を超えるものをタイムアウトとした．この実験設定を，以降は{\bfLARGE}と呼ぶ．実験設定LARGEにおける実験結果を表2に示す．この結果より，従来手法では殆どの問題で解が得られていない一方で，提案手法ではそれがある程度改善されていることが分かる．これは，述語グラフの枝刈りを導入したことによって，A*-basedAbductionにおける述語間の距離推定の精度が改善され，後ろ向き推論の候補をより短い時間で列挙できるようになったことが大きいと考えられる．\begin{table}[t]\hangcaption{実験設定LARGEにおける実験結果．各列は従来手法および提案手法での結果を表す．各行は上から順に，正解できた問題数(Correct)，不正解だった問題数(Wrong)，出力が得られなかった問題数(NoDecision)，それらの結果から計算した適合率(Precision)および再現率(Recall)を表す．}\label{tab:result-2}\input{02table02.txt}\end{table}また，タスクの解析精度については，表2の適合率を見る限り，ある程度意味のある推論が実現できていることが伺える．その一方で再現率は低く，今後，解析精度を向上させていくためには，背景知識の拡充・高精度化や，評価関数のモデルパラメータの調整など，様々な改善が必要である．しかしながら，少なくとも今回の提案手法の導入により，実世界の問題に即した規模の背景知識および論理表現の上での仮説推論が，初めて実現可能になった．このことは，当該分野において非常に重要な貢献である．
\section{まとめ}
仮説推論は，文章に明示されていない情報の顕在化を行うための有望な枠組みと考えられてきた一方，背景知識や観測の規模に対して指数関数的に増大する計算時間が，実問題への応用を阻んできた．このような問題に対し本論文では，格関係や前置詞による修飾関係などの依存関係を表すリテラルに関して起こる計算量の問題に着目し，そのようなリテラルに対して起こる冗長な推論を探索空間から除外することによって，仮説推論を効率化する手法を提案した．また，既存手法との比較実験から，構築したシステムが従来のシステムよりも遥かに高速であることを示した．今後の展望としては，潜在仮説集合の生成において，言語そのものに対する知識を用いて探索空間の枝刈りをすることが考えられる．その一つの例としては，それぞれの依存関係が持つ性質を利用することが挙げられる．例えば，物体の位置的な上下関係のように推移律が成り立つ場合や，述語項関係のように一つのgovernorに対して一つしかdependentが存在できない場合，物体同士の隣接関係のように対称律が成り立つ場合など，それぞれの関係は固有の性質を持つ．これらの性質を潜在仮説集合の生成の時に考慮することができれば，その性質に反するような推論を探索空間から除外できることが期待される．例えば，主格関係が一つのgovernorに対して一つしか定義できないことが分かっているなら，$\mathit{go}(e_1)\land\mathit{go}(e_2)\land\mathit{nsubj}(e_1,x_1)\land\mathit{nsubj}(e_2,x_2)$のような観測が与えられたとき，$e_1=e_2$かつ$x_1\nex_2$であるような仮説は適切な説明ではないことが分かる．よって，このような仮説を候補仮説として列挙するような手続きを探索空間から除外することが出来れば，計算負荷の軽減に繋げられる可能性がある．また，潜在仮説集合の生成の手続きと，ILP問題を最適化する手続きを，相互にやりとりしながら進めることによって，推論速度を向上させることも考えられる．現状ではこれらの手続きは完全に逐次的に行われるが，潜在仮説集合を生成する段階ではどこまで探索すれば十分なのかが全くの不明であるために，必要最低限の範囲だけを探索することが難しいという問題がある．これに対して，潜在仮説集合の生成の途中の結果に対する解仮説を随時導出しながら，その結果に応じて潜在仮説集合の生成を適切に打ち切ることができれば，全体の計算量を削減できると考えられる．他には，仮説推論を実問題へ適用していくことも進めていく．本研究によって仮説推論の計算負荷は大幅に効率化され，大規模知識を用いた仮説推論は現実的な時間で実現可能となった．これにより，大規模知識を用いた仮説推論の枠組みにおいて，実タスク上での精度評価や，他の先行研究との定量的な比較が可能になったといえる．よって今後は，仮説推論に用いるための高精度かつ大規模な背景知識の構築や，より談話理解のタスクに適した評価関数モデルの構築を進めていきたいと考えている．\acknowledgment本研究は，JST戦略的創造研究推進事業CRESTおよび文部科学省科研費(15H01702)から部分的な支援を受けて行われた．\bibliographystyle{jnlpbbl_1.5}\begin{thebibliography}{}\bibitem[\protect\BCAY{Blythe,Hobbs,Domingos,Kate,\BBA\Mooney}{Blytheet~al.}{2011}]{Blythe11}Blythe,J.,Hobbs,J.~R.,Domingos,P.,Kate,R.~J.,\BBA\Mooney,R.~J.\BBOP2011\BBCP.\newblock\BBOQImplementingWeightedAbductioninMarkovLogic.\BBCQ\\newblockIn{\BemProceedingsofthe9thInternationalConferenceonComputationalSemantics},IWCS'11,\mbox{\BPGS\55--64}.\bibitem[\protect\BCAY{Chambers\BBA\Jurafsky}{Chambers\BBA\Jurafsky}{2009}]{Chambers09}Chambers,N.\BBACOMMA\\BBA\Jurafsky,D.\BBOP2009\BBCP.\newblock\BBOQUnsupervisedLearningofNarrativeSchemasandtheirParticipants.\BBCQ\\newblockIn{\BemProceedingsofthe47thAnnualMeetingoftheAssociationforComputationalLinguisticsandthe4thInternationalJointConferenceonNaturalLanguageProcessingoftheAFNLP},ACL'09,\mbox{\BPGS\602--610}.\bibitem[\protect\BCAY{Copestake,Flickinger,Pollard,\BBA\Sag}{Copestakeet~al.}{2005}]{Copestake05}Copestake,A.,Flickinger,D.,Pollard,C.,\BBA\Sag,I.~A.\BBOP2005\BBCP.\newblock\BBOQMinimalRecursionSemantics:AnIntroduction.\BBCQ\\newblock{\BemResearchonLanguageandComputation},{\Bbf3}(2-3),\mbox{\BPGS\281--332}.\bibitem[\protect\BCAY{Davidson}{Davidson}{1980}]{Davidson}Davidson,D.\BBOP1980\BBCP.\newblock{\BemEssaysonActionsandEvents}.\newblockOxfordUniversityPress.\bibitem[\protect\BCAY{Fellbaum}{Fellbaum}{1998}]{fellbaum98}Fellbaum,C.\BED\\BBOP1998\BBCP.\newblock{\BemWordNet:AnElectronicLexicalDatabase}.\newblockMITPress.\bibitem[\protect\BCAY{Gelfond\BBA\Lifschitz}{Gelfond\BBA\Lifschitz}{1988}]{Gelfond88}Gelfond,M.\BBACOMMA\\BBA\Lifschitz,V.\BBOP1988\BBCP.\newblock{\BemTheStableModelSemanticsforLogicProgramming},\mbox{\BPGS\1070--1080}.\newblockMITPress.\bibitem[\protect\BCAY{Hobbs,Stickel,Martin,\BBA\Edwards}{Hobbset~al.}{1993}]{Hobbs93}Hobbs,J.~R.,Stickel,M.,Martin,P.,\BBA\Edwards,D.\BBOP1993\BBCP.\newblock\BBOQInterpretationasAbduction.\BBCQ\\newblock{\BemArtificialIntelligence},{\Bbf63},\mbox{\BPGS\69--142}.\bibitem[\protect\BCAY{Hobbs}{Hobbs}{1985}]{Hobbs85}Hobbs,J.~R.\BBOP1985\BBCP.\newblock\BBOQOntologicalPromiscuity.\BBCQ\\newblockIn{\BemProceedingsofthe23rdAnnualMeetingoftheAssociationforComputationalLinguistics},ACL'85,\mbox{\BPGS\61--69},Chicago,Illinois,USA.UniversityofChicago.\bibitem[\protect\BCAY{Inoue\BBA\Inui}{Inoue\BBA\Inui}{2011a}]{Inoue11}Inoue,N.\BBACOMMA\\BBA\Inui,K.\BBOP2011a\BBCP.\newblock\BBOQILP-BasedReasoningforWeightedAbduction.\BBCQ\\newblockIn{\BemPlan,Activity,andIntentRecognition,Papersfromthe2011AAAIWorkshop},AAAI'11,\mbox{\BPGS\25--32}.\bibitem[\protect\BCAY{Inoue\BBA\Inui}{Inoue\BBA\Inui}{2011b}]{Inoue11b}Inoue,N.\BBACOMMA\\BBA\Inui,K.\BBOP2011b\BBCP.\newblock\BBOQAnILPFormulationofAbductiveInferenceforDiscourseInterpretation.\BBCQ\\newblock\Jem{情報処理学会研究報告．自然言語処理研究会報告},{\Bbf2011}(3),\mbox{\BPGS\1--13}.\bibitem[\protect\BCAY{Inoue\BBA\Inui}{Inoue\BBA\Inui}{2012}]{Inoue12b}Inoue,N.\BBACOMMA\\BBA\Inui,K.\BBOP2012\BBCP.\newblock\BBOQLarge-scaleCost-basedAbductioninFull-fledgedFirst-orderPredicateLogicwithCuttingPlaneInference.\BBCQ\\newblockIn{\BemProceedingsofthe13thEuropeanConferenceonLogicsinArtificialIntelligence},\mbox{\BPGS\281--293}.\bibitem[\protect\BCAY{井之上\JBA乾\JBA{EkaterinaOvchinnikova}\JBA{JerryR.Hobbs}}{井之上\Jetal}{2012}]{Inoue12}井之上直也\JBA乾健太郎\JBA{EkaterinaOvchinnikova}\JBA{JerryR.Hobbs}\BBOP2012\BBCP.\newblock大規模世界知識を用いた仮説推論による談話解析の課題と対策.\\newblock\Jem{言語処理学会第18回年次大会論文集},\mbox{\BPGS\119--122}.\bibitem[\protect\BCAY{Levesque}{Levesque}{2011}]{Levesque11}Levesque,H.~J.\BBOP2011\BBCP.\newblock\BBOQTheWinogradSchemaChallenge.\BBCQ\\newblockIn{\BemAAAISpringSymposium:LogicalFormalizationsofCommonsenseReasoning}.AAAI.\bibitem[\protect\BCAY{Manning,Surdeanu,Bauer,Finkel,Bethard,\BBA\McClosky}{Manninget~al.}{2014}]{CoreNLP}Manning,C.~D.,Surdeanu,M.,Bauer,J.,Finkel,J.,Bethard,S.~J.,\BBA\McClosky,D.\BBOP2014\BBCP.\newblock\BBOQTheStanfordCoreNLPNaturalLanguageProcessingToolkit.\BBCQ\\newblockIn{\BemProceedingsofthe52ndAnnualMeetingoftheAssociationforComputationalLinguistics:SystemDemonstrations},\mbox{\BPGS\55--60}.\bibitem[\protect\BCAY{McCord}{McCord}{1990}]{Mccord90}McCord,M.~C.\BBOP1990\BBCP.\newblock{\BemSlotGrammar}.\newblockSpringer.\bibitem[\protect\BCAY{Moore}{Moore}{1983}]{Moore83}Moore,R.~C.\BBOP1983\BBCP.\newblock\BBOQSemanticalConsiderationsonNonmonotonicLogic.\BBCQ\\newblockInBundy,A.\BED,{\BemProceedingsofthe8thInternationalJointConferencesonArtificialIntelligence},\mbox{\BPGS\272--279}.WilliamKaufmann.\bibitem[\protect\BCAY{Mulkar,Hobbs,\BBA\Hovy}{Mulkaret~al.}{2007}]{Mulkar07}Mulkar,R.,Hobbs,J.,\BBA\Hovy,E.\BBOP2007\BBCP.\newblock\BBOQLearningfromReadingSyntacticallyComplexBiologyTexts.\BBCQ\\newblockIn{\BemProceedingsofthe8thInternationalSymposiumonLogicalFormalizationsofCommonsenseReasoning},PaloAlto.\bibitem[\protect\BCAY{Ng\BBA\Mooney}{Ng\BBA\Mooney}{1992}]{Ng92}Ng,H.~T.\BBACOMMA\\BBA\Mooney,R.~J.\BBOP1992\BBCP.\newblock\BBOQAbductivePlanRecognitionandDiagnosis:AComprehensiveEmpiricalEvaluation.\BBCQ\\newblockIn{\BemProceedingsofthe3rdInternationalConferenceonPrinciplesofKnowledgeRepresentationandReasoning},\mbox{\BPGS\499--508}.\bibitem[\protect\BCAY{Nienhuys-Cheng\BBA\De~Wolf}{Nienhuys-Cheng\BBA\De~Wolf}{1997}]{Nienhuys97}Nienhuys-Cheng,S.-H.\BBACOMMA\\BBA\De~Wolf,R.\BBOP1997\BBCP.\newblock{\BemFoundationsofInductiveLogicProgramming},\lowercase{\BVOL}\1228.\newblockSpringerScience\&BusinessMedia.\bibitem[\protect\BCAY{Ovchinnikova,Hobbs,Montazeri,McCord,Alexandrov,\BBA\Mulkar-Mehta}{Ovchinnikovaet~al.}{2011}]{Ovch11}Ovchinnikova,E.,Hobbs,J.~R.,Montazeri,N.,McCord,M.~C.,Alexandrov,T.,\BBA\Mulkar-Mehta,R.\BBOP2011\BBCP.\newblock\BBOQAbductiveReasoningwithaLargeKnowledgeBaseforDiscourseProcessing.\BBCQ\\newblockIn{\BemProceedingsofthe9thInternationalConferenceonComputationalSemantics},IWCS'11,\mbox{\BPGS\225--234}.\bibitem[\protect\BCAY{Parsons}{Parsons}{1990}]{neodavidson}Parsons,T.\BBOP1990\BBCP.\newblock{\BemEventsintheSemanticsofEnglish:AStudyinSubatomicSemantics/TerenceParsons}.\newblockMITPressCambridge,Mass.\bibitem[\protect\BCAY{Raghavan\BBA\Mooney}{Raghavan\BBA\Mooney}{2010}]{Raghavan10}Raghavan,S.\BBACOMMA\\BBA\Mooney,R.~J.\BBOP2010\BBCP.\newblock\BBOQBayesianAbductiveLogicPrograms.\BBCQ\\newblockIn{\BemProceedingsoftheAAAI-10WorkshoponStatisticalRelationalArtificialIntelligence},\lowercase{\BVOL}\WS-10-06of{\BemAAAIWorkshops},\mbox{\BPGS\82--87}.\bibitem[\protect\BCAY{Rahman\BBA\Ng}{Rahman\BBA\Ng}{2012}]{Rahman12}Rahman,A.\BBACOMMA\\BBA\Ng,V.\BBOP2012\BBCP.\newblock\BBOQResolvingComplexCasesofDefinitePronouns:TheWinogradSchemaChallenge.\BBCQ\\newblockIn{\BemProceedingsofthe2012JointConferenceonEmpiricalMethodsinNaturalLanguageProcessingandComputationalNaturalLanguageLearning},\mbox{\BPGS\777--789},JejuIsland,Korea.AssociationforComputationalLinguistics.\bibitem[\protect\BCAY{Reiter}{Reiter}{1978}]{raymond78}Reiter,R.\BBOP1978\BBCP.\newblock\BBOQOnClosedWorldDataBases.\BBCQ\\newblockInGallaire,H.\BBACOMMA\\BBA\Minker,J.\BEDS,{\BemLogicandDataBases},\mbox{\BPGS\55--76}.SpringerUS.\bibitem[\protect\BCAY{Reiter}{Reiter}{1987}]{Reiter87}Reiter,R.\BBOP1987\BBCP.\newblock\BBOQALogicforDefaultReasoning.\BBCQ\\newblockInGinsberg,M.~L.\BED,{\BemReadingsinNonmonotonicReasoning},\mbox{\BPGS\68--93}.Kaufmann,LosAltos,CA.\bibitem[\protect\BCAY{Richardson\BBA\Domingos}{Richardson\BBA\Domingos}{2006}]{Richardson06}Richardson,M.\BBACOMMA\\BBA\Domingos,P.\BBOP2006\BBCP.\newblock\BBOQMarkovLogicNetworks.\BBCQ\\newblock{\BemMachinelearning},{\Bbf62}(1-2),\mbox{\BPGS\107--136}.\bibitem[\protect\BCAY{Ruppenhofer,Ellsworth,Petruck,Johnson,\BBA\Scheffczyk}{Ruppenhoferet~al.}{2010}]{framenetII}Ruppenhofer,J.,Ellsworth,M.,Petruck,M.~R.,Johnson,C.~R.,\BBA\Scheffczyk,J.\BBOP2010\BBCP.\newblock\BBOQFrameNetII:ExtendedTheoryandPractice.\BBCQ.\bibitem[\protect\BCAY{Schoenmackers,Etzioni,Weld,\BBA\Davis}{Schoenmackerset~al.}{2010}]{Scho10}Schoenmackers,S.,Etzioni,O.,Weld,D.~S.,\BBA\Davis,J.\BBOP2010\BBCP.\newblock\BBOQLearningFirst-orderHornClausesfromWebText.\BBCQ\\newblockIn{\BemProceedingsofthe2010ConferenceonEmpiricalMethodsinNaturalLanguageProcessing},EMNLP'10,\mbox{\BPGS\1088--1098}.\bibitem[\protect\BCAY{Sch{\"{u}}ller}{Sch{\"{u}}ller}{2015}]{Schuller15}Sch{\"{u}}ller,P.\BBOP2015\BBCP.\newblock\BBOQModelingAbductionoverAcyclicFirst-OrderLogicHornTheoriesinAnswerSetProgramming:PreliminaryExperiments.\BBCQ\\newblockIn{\BemProceedingsofthe22ndRCRAInternationalWorkshoponExperimentalEvaluationofAlgorithmsforSolvingProblemswithCombinatorialExplosion2015(RCRA2015)AWorkshopoftheXIVInternationalConferenceoftheItalianAssociationforArtificialIntelligence},\mbox{\BPGS\76--90}.\bibitem[\protect\BCAY{Singla\BBA\Mooney}{Singla\BBA\Mooney}{2011}]{Singla11}Singla,P.\BBACOMMA\\BBA\Mooney,R.~J.\BBOP2011\BBCP.\newblock\BBOQAbductiveMarkovLogicforPlanRecognition.\BBCQ\\newblockIn{\BemProceedingsofthe25thAAAIConferenceonArtificialIntelligence},AAAI'11,\mbox{\BPGS\1069--1075}.\bibitem[\protect\BCAY{杉浦\JBA井之上\JBA乾}{杉浦\Jetal}{2012}]{Sugiura12}杉浦純\JBA井之上直也\JBA乾健太郎\BBOP2012\BBCP.\newblock説明生成に基づく談話構造解析の課題分析.\\newblock\Jem{言語処理学会第18回年次大会論文集},\mbox{\BPGS\115--118}.\bibitem[\protect\BCAY{Thagard}{Thagard}{1978}]{Thagard78}Thagard,P.~R.\BBOP1978\BBCP.\newblock\BBOQTheBestExplanation:CriteriaforTheoryChoice.\BBCQ\\newblock{\BemTheJournalofPhilosophy},{\Bbf1},\mbox{\BPGS\76--92}.\bibitem[\protect\BCAY{Yamamoto,Inoue,Inui,Arase,\BBA\Tsujii}{Yamamotoet~al.}{2015}]{Yamamoto15}Yamamoto,K.,Inoue,N.,Inui,K.,Arase,Y.,\BBA\Tsujii,J.\BBOP2015\BBCP.\newblock\BBOQBoostingtheEfficiencyofFirst-orderAbductiveReasoningUsingPre-estimatedRelatednessbetweenPredicates.\BBCQ\\newblock{\BemInternationalJournalofMachineLearningandComputing},{\Bbf5}(2),\mbox{\BPGS\114--120}.\end{thebibliography}\appendix\renewcommand\proofname{\bf証明}
\section{提案手法が解の最適性を保持することの証明}
本節では，仮説の整合性条件および簡潔性条件が充足されるならば，5節で提案した手法に基づく述語グラフの枝刈りを用いて得られる解が最適性を保つこと，即ち手法適用後に探索空間から除外されるような要素仮説について，それらが常に解仮説とならないことを示す．任意の述語$p$,$q$に対する，述語グラフの枝刈り適用前の述語間距離を$h_1(p,q)$，適用後の述語間距離を$h_2(p,q)$と表す．まず，述語グラフの枝刈りを適用することによって除外される推論パスの集合$\mathbb{R}$に着目する．形式的には，$\mathbb{R}$は，$h_1(o_1,o_2)<\infty$かつ$h_2(o_1,o_2)=\infty$を満たすような観測リテラル対$o_1$,$o_2$を端点とするような推論パスの集合，と定義される．本証明のゴールは，「$\mathbb{R}$に含まれるすべての推論パス$R\in\mathbb{R}$から生成される候補仮説$H_R$が，整合性条件および簡潔性条件が充足される状況下では，常に解仮説とならないことを示す」ことである．証明の戦略は次のとおりである．まず，$\mathbb{R}$の部分集合について，整合性条件と簡潔性条件より，そこに含まれる推論パスから生成される候補仮説が解仮説とならないことを示す．次に，それ以外の推論パスの集合$\mathbb{R}'$について，すべての$R'\in\mathbb{R}'$が常に機能リテラルの単一化仮説生成を含むことを証明し，かつその単一化仮説生成操作が常に不正な等価仮説を導くことを示す．まず，$\mathbb{R}$に含まれる推論パスのうち，以下に示すような推論パス$R\in\mathbb{R}$から生成される候補仮説については，整合性条件および簡潔性条件により解仮説とならないことが自明である：\begin{enumerate}\item$R$は機能リテラルの単一化仮説生成を含み，かつ単一化仮説生成の対象である機能リテラル対の少なくとも一方が親を持たない．\item$R$は不正な等価仮説を導くような後ろ向き推論を含む．\item$R$の端点$o_1$,$o_2$は同じ親を持つ機能リテラルであり，親以外の内容語リテラルが推論パスの根拠に含まれない．\item$R$の端点$o_1$,$o_2$のうち一方は機能リテラルであり，他方がその親であり，親以外の内容語リテラルが推論パスの根拠に含まれない．\end{enumerate}(1)および(2)が示す場合については整合性条件2,3より，(3)および(4)が示す場合については簡潔性条件より，明らかに解仮説とならない．したがって，以降ではこれらの場合に当てはまらない推論パスの集合$\mathbb{R}'\subseteq\mathbb{R}$についてのみ検討する．$\mathbb{R}'$の定義より，すべての$R'\in\mathbb{R}'$について，不正な等価仮説を導く後ろ向き推論が$R'$に含まれないことは自明であるから，以降は，すべての$R'\in\mathbb{R}'$について，不正な等価仮説を導く単一化仮説生成操作が$R'$に含まれることを示す．まず，すべての$R'\in\mathbb{R}'$が常に機能リテラルの単一化仮説生成を含むことを証明する．\begin{proof}背理法を用いて証明する．すなわち，「推論パス$R'$が常に機能リテラル間の単一化仮説生成操作を含まない」ことを仮定すると，矛盾が生じることを以下に示す．まず，背理法の仮定は，\ref{sec:prob:mr}~節の定義より，「推論パス$R'$が内容語リテラル間の単一化仮説生成操作を含む場合がある」と言い換えることができる．形式的には，$h_1(o_1,o_2)<\infty$かつ$h_2(o_1,o_2)=\infty$を満たすような観測リテラル対$o_1$,$o_2$がそれぞれ内容語リテラル$c_1$,$c_2$を仮説しており，$c_1$,$c_2$が互いに単一化している場合が存在する，ということである．このとき，$c_1$,$c_2$は同じ述語を持つことから，明らかに$h_1(c_1,c_2)=h_2(c_1,c_2)=0<\infty$である．$\mathbb{R}'$の定義より，$R'$には不正な等価仮説を導くような後ろ向き推論は含まれないので，$c_1$の直接的な根拠となっている任意のリテラルを$d_1$とおくと$h_2(c_1,d_1)<\infty$が成り立つ．同様に$c_2$の直接的な根拠となっている任意のリテラルを$d_2$とおくと$h_2(c_2,d_2)<\infty$が成り立つ．よって，$h_2(c_1,c_2)<\infty$であるので$h_2(d_1,d_2)<\infty$も成り立つ．このような議論は$d_1$および$d_2$の根拠についても成り立つことから，帰納的に$h_2(o_1,o_2)<\infty$も成り立つ．しかし，これは前提である$h_2(o_1,o_2)=\infty$と矛盾する．以上から，$R'$は，常に機能リテラル間の単一化を導く．\end{proof}次に，$R'$における機能リテラル$f_1$,$f_2$の単一化仮説生成操作が，常に不正な等価仮説を導くことを示す．\begin{proof}$f_1$,$f_2$の親をそれぞれ$p_1$,$p_2$とおき，$p_1$,$p_2$が同一事象を表し得ない，すなわち$h_2(p_1,p_2)=\infty$であることを，背理法により示す．背理法の仮定は，$h_2(p_1,p_2)<\infty$である．この仮定のもとでは，機能リテラルにおける述語間距離の計算手続きより，$h_2(f_1,f_2)<\infty$となるので，$f_1$,$f_2$を経由する$o_1$,$o_2$についても同様に$h_2(o_1,o_2)<\infty$となる．しかし，これは前提である$h_2(o_1,o_2)=\infty$と矛盾する．この事から，$h_2(p_1,p_2)=\infty$であり，$R'$によって単一化仮説生成の対象である機能リテラルの親は，それぞれ同一事象には成り得ないこと，すなわち不正な等価仮説を導くことが示された．\end{proof}以上から，提案手法を適用することによって除外される推論パスの集合$\mathbb{R}$は，最初に挙げた4つの場合のほかには，機能リテラルに対する単一化仮説生成操作を含み，かつそれらの親が同一事象に成り得ず，不正な等価仮説を導く場合に限定される．ゆえに，すべての$R\in\mathbb{R}$について，$R$から生成される候補仮説は解仮説とならないことが証明される．以上より，本手法によって得られる解は最適性を保つ．\begin{biography}\bioauthor{山本風人}{1987年生．2011年東北大学工学部知能情報システム総合学科卒．2013年東北大学大学院情報科学研究科博士前期課程修了．2016年東北大学大学院情報科学研究科博士後期課程修了，日本電気株式会社入社，現在に至る．自然言語処理の研究に従事．}\bioauthor{井之上直也}{1985年生．2008年武蔵大学経済学部経済学科卒業．2010年奈良先端科学技術大学院大学情報科学研究科博士前期課程修了．2013年東北大学大学院情報科学研究科博士後期課程修了．2015年より東北大学大学院情報科学研究科助教，現在に至る．自然言語処理の研究に従事．言語処理学会，情報処理学会各会員．}\bioauthor{乾健太郎}{1995年東京工業大学大学院情報理工学研究科博士課程修了．同研究科助手，九州工業大学助教授，奈良先端科学技術大学院大学助教授を経て，2010年より東北大学大学院情報科学研究科教授，現在に至る．博士（工学）．自然言語処理の研究に従事．言語処理学会，情報処理学会，人工知能学会，ACL，AAAI各会員．}\end{biography}\biodate\clearpage\clearpage\end{document}