    \documentclass[japanese]{jnlp_1.4}
\usepackage{jnlpbbl_1.3}
\usepackage[dvipdfm]{graphicx}
\usepackage{amsmath,amssymb}
\usepackage{amsthm}
\usepackage{hangcaption_jnlp}
\usepackage{array}

\newcommand{\argmax}{}

\Volume{23}
\Number{3}
\Month{June}
\Year{2016}

\received{2015}{10}{28}
\revised{2016}{1}{5}
\accepted{2016}{2}{16}

\setcounter{page}{267}

\jtitle{機能的なリテラルを含む公理体系における仮説推論の効率化}
\jauthor{山本　風人\affiref{tohoku} \and 井之上直也\affiref{tohoku} \and 乾　健太郎\affiref{tohoku}}
\jabstract{
仮説推論は，与えられた観測に対する最良の説明を見つける推論の枠組みである．
仮説推論は80年代頃から主に人工知能の分野で長らく研究されてきたが，近年，
知識獲得技術の成熟に伴い，大規模知識を用いた仮説推論を実世界の問題へ適用
するための土壌が徐々に整いつつある．しかしその一方で，大規模な背景知識を用いる際に生じる
仮説推論の計算負荷の増大は，重大な問題である．特に言語の意味表示上の依
存関係を表すリテラル（本論文では機能リテラルと呼ぶ）が含まれる場合に生じる
探索空間の爆発的増大は，実問題への仮説推論の適用において大きな障害となっ
ている．
これに対し本論文では，機能リテラルの性質を利用して探索空間の枝刈りを行う
ことで，効率的に仮説推論の最適解を導く手法を提案する．具体的には，意味的
な整合性を欠いた仮説を解空間から除外することで，推論全体の計算効率を向上
させる．また，このような枝刈りが，ある条件が満たされる限り本来の最適解を
損なわないことを示す．
評価実験では，実在の言語処理の問題に対して，大規模背景知識を用いた仮説
推論を適用し，その際の既存手法との計算効率の比較を行った．その結果として，
提案手法が既存のシステムと比べ，数十〜数百倍ほど効率的に最適解が得られて
いることが確かめられた．
}
\jkeywords{仮説推論，談話理解，共参照解析}

\etitle{Boosting Abductive Reasoning with Functional Literals}
\eauthor{Kazeto Yamamoto\affiref{tohoku} \and Naoya Inoue\affiref{tohoku} \and Kentaro Inui\affiref{tohoku}}
\eabstract{
Abduction is also known as Inference to the Best Explanation. It has long been
considered as a promising framework for natural language processing (NLP). While
recent advances in the techniques of automatic world knowledge
acquisition warrant developing large-scale knowledge bases,
the computational complexity of abduction hinders its application to
real-life problems. In particular, when a knowledge base contains
functional literals, which express the dependency relation between
words, the size of the search space will substantially increase.
In this study, we propose a method to enhance the efficiency of first-order
abductive reasoning. By exploiting the property of functional literals, the proposed
method prunes inferences that do not lead to reasonable
explanations. Furthermore, we prove that the proposed method is sound under a
particular condition.
In our experiment, we apply abduction having a large-scale knowledge
base to a real-life NLP task. We show that our method significantly
improves the computational efficiency of first-order abductive reasoning
when compared with a state-of-the-art system.
}
\ekeywords{Abduction, Discourse Understanding, Coreference Resolution}

\headauthor{山本，井之上，乾}
\headtitle{機能的なリテラルを含む公理体系における仮説推論の効率化}

\affilabel{tohoku}{東北大学}{Tohoku University}



\begin{document}
\maketitle


\section{はじめに}

\textbf{仮説推論} (Abduction) は，与えられた観測に対する最良の説明を見つける，論
理推論の枠組みのひとつである．仮説推論は，自然言語処理や故障診断システムなどを含む，
人工知能分野の様々なタスクにおいて古くから用いられてきた
    (Ng and Mooney 1992; Blythe, Hobbs, Domingos, Kate, and Mooney 2011; Ovchinnikova, Hobbs, Montazeri, McCord, Alexandrov, and Mulkar-Mehta 2011; 井之上，乾，Ovchinnikova，Hobbs 2012; 杉浦，井之上，乾2012)．\nocite{Ng92,Blythe11,Ovch11,Inoue12,Sugiura12}



自然言語処理への応用のうち，代表的な先行研究の一つに Hobbs ら \cite{Hobbs93} の
\textit{Interpretation as Abduction} (IA) がある．Hobbs らは，語義曖昧性解消，
比喩の意味理解，照応解析や談話関係認識などの，様々な自然言語処理のタスクを，
一階述語論理に基づく仮説推論により統合的にモデル化できることを示した．

詳しくは\ref{sec:abduction}節で述べるが，IA の基本的なアイデアは，
\textbf{談話解析}（文章に対する自然言語処理）の問題を「観測された文章（入
力文）に対し，世界知識（言語の知識や常識的知識など）を用いて，最良の説明
を生成する問題」として定式化することである．最良の説明の中には，観測され
た情報の背後で起きていた非明示的な事象，共参照関係や単語の語義などの情報
が含まれる．例文 ``{\it John went to the bank. He got a loan.}'' に対し
て，IA による談話解析を行う様子を図\ref{fig:ia}に示す．まず，入力文の論
理式表現が観測として，世界知識の論理式表現が背景知識として与えられ，背景
知識に基づいて説明が生成される．例えば，$\mathit{go}(x_1,x_2)$（\textit{John} が
\textit{bank} に行った）という観測に対して，$\mathit{issue}(x,l,y) \Rightarrow
go(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*-based Abduction \cite{Yamamoto15}の手法に前述
の枝刈りを導入する方法を示し，機能リテラルを知識表現に含む場合でも推論の
規模耐性を維持する方法を示す．
二つ目に，機能リテラルの性質に基づく探索空間の枝刈りが，ある条件のもとで
は本来の解を損なわないことを示す．
三つ目に，大規模な知識ベースと実在の言語処理の問題を用いて，A*-based
Abduction \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$は含意型の一階述語論理
	      式の集合であり，各論理式の前件および後
	      件にはリテラルの連言のみを許容する．各論理式の前件に含まれ
	      る論理変数は全称限量されており，前件に含まれない論理変数は
	      存在限量されているものとする．形式的には，各論理式は
	      $\forall x_1, \ldots,
	      x_n\ [\exists y_1, \ldots, y_m\
	      [p_1(x_1) \land \ldots \land p_n(x_n)
	      \Rightarrow q_1(y_1) \land \ldots \land
	      q_m(y_m)]]$ と表現される．ここで，$x_i,
	      y_i$はそれぞれ任意個数の引数列を表す
	      \footnote{ただし，前件と後件の両方に含ま
	      れている変数については全称限量される．}．また，$O$は，一
	      階述語論理リテラルおよび論理変数間の等価関係を表す等号
	      あるいはその否定の連言であり，全ての論
	      理変数は存在限量されているものとする．な
	      お以降の記述では，$B$および$O$がそれぞれ矛盾を含まないこと
	      を前提とする．
\item[Find:] 仮説（または説明）$H$．$H$は，一階述語論理リテラル，およ
	      び論理変数間の等価関係を表す等号・不等号の連言であり，$H
	      \cup B \models O$ および $H \cup B \nvDash \perp$ を満たす
	      \footnote{計算論理学の分野において現在主流となっているAnswer
	      Set Programming~\cite{Reiter87,Moore83,Gelfond88} の考え方
	      に従えば，仮説の探索問題は，与えられた観測と背景知識から，
	      観測を説明するようにあらゆるリテラルに対する真偽値割り当て
	      を求める問題と見做すことができる．そのような文脈において本
	      研究で扱う仮説推論は，仮説$H$にリテラル$l$または$\lnot l$
	      が含まれていることが，リテラル$l$の真偽値にtrueまたはfalseが割り当て
	      られている事に対応する．すなわち，仮説$H$に含まれないリテ
	      ラルの真偽値は全て不定であると見做す．}．ここで
	      $\models$は論理的含意を表し，$H$ が $O$ を\textbf{説明する}，
	      という．$\perp$は偽を表す．また，連言と集合は相互変換可能
	      であるとし，連言$l_1 \land \ldots \land l_n$とリテラル集合
	      $\{l_1, \ldots ,l_n\}$とも書けるものとする．
\end{description}
なお，本論文では背景知識，観測，仮説における限量子の記述は基本的に省略
する．

一般には，与えられた$B$と$O$に対して，複数の仮説$H_1$, $H_2,\ldots$が存在す
る．本論文では，それぞれの仮説$H_i$を{\bf 候補仮説}と呼び，候補仮説
$H_i$ に含まれる各リテラル$h \in H_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) \Rightarrow go(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 \in H}
\mathit{cost}(h)$ で定義される．要素仮説のコスト $\mathit{cost}(h)$ の詳細
な計算方法は\cite{Hobbs93}に委ねるが，基本的には，(1) 要素仮説 $h$ が
観測 $O$ を説明するのに要する背景知識の信頼度，(2) 要素仮説 $h$ が他の
要素仮説に説明されているか，の二つの要因を基にコストが決定される．

本研究では，\ref{sec:prob}~節で示す仮説の整合性条件を保証する任意の評価関数を想定する．



\subsection{潜在仮説集合に基づく候補仮説の表現}
\label{sec:potential}

$H \cup B \models O, H \cup B \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 \land p_n(x_n)
	      \Rightarrow q_1(y_1) \land \ldots q_m(y_m)$
	      と，$\bigwedge_{i=1}^m y_i\theta = y_i'$
	      を満たす変数置換$\theta$が存在するようなリテラルの連言
	      $q_1(y_1') \land \ldots \land q_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)
\Rightarrow q(y)$と$q(y) \Rightarrow p(x)$）が背景知
識に含まれる場合において，特に重要である．操作の適用回数が有限回であ
るならば，潜在仮説集合に含まれる各リテラルもまた有限回の後ろ向き推論に
よって仮説されたリテラルであるので，全ての候補仮説 $H \in \mathbb{H}$
について $H \cup B \models O$ の決定可能性が保証される．また，
アルゴリズムの停止性，および潜在仮説集合が有限集合であることについても
同様に保証される．以上の議論に基づき，本研究においても以上の手続きによって生成された潜在仮説集
合の部分集合を候補仮説として扱う．



\subsection{仮説推論の実装に関する先行研究}

まず，仮説推論の分野における代表的な実装としては
MulkarらのMini-TACITUS \cite{Mulkar07} が挙げられるが，これは計算量の
面では非常に非効率であった．そのため，大規模知識を用いた仮説推論を行う
にあたっては，より効率的な推論アルゴリズムが必要とされた．

これを受けてBlytheらは，仮説推論の枠組みを Markov Logic
Network (MLN) \cite{Richardson06} の上で定式化する手法 ({\bf MLN-based
Abduction}) を提案した\cite{Blythe11}．彼らは，仮説推論をMLN上で実装する
ことによって，MLNの分野における成熟した最適化手法を仮説推論にも利用する
ことを可能にした．これによりMini-TACITUSと比べ遥かに高速な推論が実現可
能になった．

そしてこれよりも更に高い効果をあげたのが，井之上らが提案した整数線形計
画法 (Integer Linear Programming, ILP) に基づく仮説推論 ({\bf
ILP-based Abduction}) であった\cite{Inoue11,Inoue12b}．井之上らは，仮
説推論の問題を整数線形計画問題により定式化する手法を提案した．こ
れにより，仮説推論において解仮説を導出する処理はそのままILP問題の最適
解を導く処理と対応付けられ，外部の高速なILPソルバを利用することで解仮
説を効率的に導出することが可能になった．文献\cite{Inoue12b}では，
ILP-based Abductionの枠組みがMLN-based Abductionと比べても遥かに高速で
あることが実験によって定量的に示されている．

Yamamotoらは，ILP-based Abduction \cite{Inoue11,Inoue12b}における計算
コストが潜在仮説集合の規模に強く依存することに着目し，背景知識における
述語間の関連度を事前に推定しておくことで，ILP-based Abduction の潜在仮
説集合生成の手続きにおいて解仮説に含まれる見込みの無い要素仮説を潜在仮
説集合から除外し，ILP問題の最適化にかかる時間を大幅に短縮する手法
({\bf A*-based Abduction}) を提案した\cite{Yamamoto15}．

しかしながら，\ref{sec:prob}節で示すように，A*-based Abduction には，
機能リテラルを含む知識表現において推論時間が増大するという問題がある．
本研究は，我々が知る限り最も効率的な枠組みである A*-based Abduction
を拡張する手法を提案するものである．
A*-based Abduction の詳細については\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形式では，イベントの必須格をリテラルの項の順番に対応させる．
例えば，例文 ``{\it Brutus stabbed Caesar with a knife.}'' を
$\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) \land e_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*-based
Abduction \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}^n p_i(x_i) \Rightarrow \bigwedge_{j=1}^m
q_j(y_j)$を用いた後ろ向き推論を，$P$に含まれる連言
$\bigwedge_{j=1}^m q_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}^n x_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*-based Abductionの手法に基いて網羅的に適用する．
	 ただし，\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*-based Abduction の効率化}
\label{sec:stopword}

機能リテラルを含む背景知識を用いた仮説推論をA*-based Abduction
\cite{Yamamoto15} に適用する際，探索空間の枝刈りの精度が著しく低下する
という問題がある．本節ではそのような問題の解決策として，探索のガイドと
して用いるヒューリスティック関数の計算方法を改良することにより，枝刈り
の精度の低下を抑える手法を提案する．

本節では，まず A*-based Abduction について説明し
（\ref{sec:yamamoto15}~節），機能リテラルが引き起こす枝刈り精度低下の
問題（\ref{sec:sw-prob}~節）と解決策（\ref{sec:sw-sw}~節）について述べ
る．

\subsection{A*アルゴリズムに基づく仮説推論}
\label{sec:yamamoto15}

まず，A*-based Abduction のベースとなる ILP-based Abduction
\cite{Inoue11b,Inoue12b} について説明する．
ILP-based Abductionでは，まず観測と背景知識を入力
として受け取り，それらに対して\ref{sec:potential}~節の潜在仮説集合
生成手続きを適用し，潜在仮説集合を生成する．次に，潜在仮説集合と評価関数から，
ILP問題を生成する．ここでは，仮説中での各リテラルの有無がILP変数の0-1値に，
仮説に対する評価関数の値がILP問題の目的関数値に対応し，各リテラ
ル間の論理的な依存関係はILP制約として表現される．
最後に，ILPソル
バ\footnote{lp\_solve (http://lpsolve.sourceforge.net)やGurobi
Optimizer (http://www.gurobi.com) などがある．}を用いてILP問題を
解くことにより，解仮説が得られる．

A*-based Abduction は，ILP-based Abduction の潜在仮説集合の生成手続き
を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*-based Abduction の潜在仮説集合の生成手続きで
は，「単一化仮説生成に寄与しないリテラルは解仮説に含まれない」という前
提に基づき，解仮説に含まれる見込みがあるリテラル，すなわち単一化仮説生
成に寄与しうるリテラルを仮説する後ろ向き推論操作のみを，評価関数の増減
量の見込みがより高いものから優先的に実行していく．より具体的には，述語
グラフにおける述語間の距離を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*-based Abduction が最も高速である
が，彼らの枠組みを適用する際，その評価関数は次の要件を満たしていなけれ
ばならない．一つ目に，彼らの枠組みはILP-based Abduction
\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*-based Abductionでは，図
\ref{fig:heuristic1}のような述語グラフを用いて，背景知識における述語間
の意味的な距離を事前に評価しておき，仮説の探索空間の枝刈りを行う．述語
グラフの上では，論理式の前件に含まれる各述語と後件に含まれる各述語のあ
らゆる組み合わせが接続されるため，機能リテラルのような，他のリテラル
と高頻度で共起するリテラルを背景知識に含む場合には，述語グラフの中にハ
ブとなるノードが形成される．その結果，解仮説を含まれ得るような推論が実
際には存在しないリテラル対に対しても，誤って距離を近く見積もってしまう，
という問題がある．

例えば図\ref{fig:exprob1}で用いられている背景知識$B$を考える：
\begin{align*}
mistake(e_1) \land nsubj(e_1,x) & \Rightarrow foolish(e_2) \land
nsubj(e_2,x) \\
study(e_1) \land nsubj(e_1,x) & \Rightarrow smart(e_2) \land
nsubj(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*-based Abductionの利点が失われてしまっ
ている．


\subsection{述語グラフの枝刈りによる高速化}
\label{sec:sw-sw}

本研究では，\ref{sec:sw-prob}節で述べた問題を解消するために，述語グラ
フから特定の枝を除外することを提案する．つまり，図\ref{fig:exprob1}に
おける$\mathit{foolish}(e)$と$\mathit{smart}(e)$のように，あるリテラル対を繋ぐ推論パスが
常に不正な等価仮説を導く時に，それらの間の距離が無限大となるように，述
語グラフの枝を除外する．これにより不正な等価仮説を導く推論は探索空間か
ら除外され，探索を効率化できる．

具体的な手法を述べる．本手法では，A*-based Abductionについて，以下の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}によって構築された
Winograd Schema Challenge~\cite{Levesque11} の
訓練データの問題1,305問をそれぞれ論理表現に変換した
ものを用いた．具体的には，各問題文に対してStanford Core
NLP\footnote{http://nlp.stanford.edu/software/corenlp.shtml}
\cite{CoreNLP} を用いて構文解析を行い，文中の単語および単語間の依存関
係をそれぞれリテラルに変換した．各観測は平均して28個のリテラルから構成
される．観測の例を表1の$O$に示す．なお，全ての観測について整合性
条件を充足することを確認している．以降はこの観測集合を$O_\mathit{wsc}$と表す．

Winograd Schema Challenge は，例えば``{\it Tony helped Jeff because he
wanted to help.}''のような文を入力として，指定された照応表現（ここでは
``{\it he}''）の照応先として相応しいものを2つの選択肢（ここでは ``{\it
Tony}'' と ``{\it Jeff}''）から選ぶタスクである．仮説推論の上では，照応
先の選択は等価仮説の有無に対応する．例えば，表1の$O$に対して得ら
れた解仮説に$E_1=e_5$が含まれるなら，``{\it he}'' の照応先として
``{\it Tony}'' を選ぶことと等しい．なお，本実験では，各問題の照応先に対
応する論理変数には定数（この例では$E_1$, $E_3$）を割り当てることで，二つ
の照応先候補を同時に選択することを防いでいる．

\begin{table}[t]
\hangcaption{実験で用いた観測および背景知識の例．なお観測の例は``\textit{Tony helped Jeff because he wanted to help.}''という文に対応する論理表現である．}
\label{tab:example}
\input{02table01.txt}
\end{table}

また背景知識には，我々が
ClueWeb12\footnote{http://lemurproject.org/clueweb12/}から自動獲得した
因果関係知識を用いた．具体的には，まず，ClueWeb12に含まれる各文に対
して Stanford Core NLP を適用し，
	共参照関係にある項を持つ動詞・形容詞とその周辺文脈のペア
	5億個を獲得した．
	例えば，
	``\textit{Tom helped \underline{Mary} yesterday,
	so \underline{Mary} thanked to Tom.}''
	より，\textit{Mary} を介してペアとなっている $\langle$\textit{Tom help Mary yesterday}, \textit{Mary thank to Tom}$\rangle$
	を獲得した．
	獲得したペアは，そのまま因果関係知識として用いるには特殊すぎる可能性があるため，
	これらを統計的な基準によって一般化し，
	論理表現に変換した．
	より具体的には，獲得したペアをさまざまな抽象度に一般化した上で（例えば，$\langle$\textit{Tom help Mary yesterday}, \textit{Mary thank to Tom}$\rangle$ を $\langle$\textit{Tom help X}, \textit{X thank to Tom}$\rangle$, $\langle$\textit{help X}, \textit{X thank}$\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*-based Abduction \cite{Yamamoto15}を用いた．以降の記述における従来手
法とは A*-based Abduction を指す．

実験は\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分を超えるものについては
タイムアウトとした．この実験設定を，以降は{\bf SMALL}と呼ぶ．

\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*-based Abduction による推論時間，図\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分を超えるものをタイムアウ
トとした．この実験設定を，以降は{\bf LARGE}と呼ぶ．

実験設定LARGEにおける実験結果を表2に示す．この結果より，従来手法では殆
どの問題で解が得られていない一方で，提案手法ではそれがある程度改善され
ていることが分かる．これは，述語グラフの枝刈りを導入したことによって，
A*-based Abductionにおける述語間の距離推定の精度が改善され，後ろ向き推
論の候補をより短い時間で列挙できるようになったことが大きいと考えられる．

\begin{table}[t]
\hangcaption{実験設定LARGEにおける実験結果．各列は従来手法および提案手法での結果を表す．各行は上から順に，正解できた問題数(Correct)，不正解だった問題数(Wrong)，出力が得られなかった問題数(No Decision)，それらの結果から計算した適合率(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 \ne x_2$であるような仮説は適切
な説明ではないことが分かる．よって，このような仮説を候補仮説として列挙す
るような手続きを探索空間から除外することが出来れば，計算負荷の軽減に繋げ
られる可能性がある．

また，潜在仮説集合の生成の手続きと，ILP問題を最適化する手続きを，相互にや
りとりしながら進めることによって，推論速度を向上させることも考えられる．
現状ではこれらの手続きは完全に逐次的に行われるが，潜在仮説集合を生成する
段階ではどこまで探索すれば十分なのかが全くの不明であるために，必要最低限
の範囲だけを探索することが難しいという問題がある．これに対して，潜在仮説
集合の生成の途中の結果に対する解仮説を随時導出しながら，その結果に応じて
潜在仮説集合の生成を適切に打ち切ることができれば，全体の計算量を削減でき
ると考えられる．

他には，仮説推論を実問題へ適用していくことも進めていく．本研究によって仮
説推論の計算負荷は大幅に効率化され，大規模知識を用いた仮説推論は現実的な
時間で実現可能となった．これにより，大規模知識を用いた仮説推論の枠組みに
おいて，実タスク上での精度評価や，他の先行研究との定量的な比較が可能になっ
たといえる．よって今後は，仮説推論に用いるための高精度かつ大規模な背景知
識の構築や，より談話理解のタスクに適した評価関数モデルの構築を進めていき
たいと考えている．



\acknowledgment

本研究は，JST 戦略的創造研究推進事業CRESTおよび文部科学省科研費
(15H01702)から部分的な支援を受けて行われた．


\bibliographystyle{jnlpbbl_1.5}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Blythe, Hobbs, Domingos, Kate, \BBA\ Mooney}{Blythe
  et~al.}{2011}]{Blythe11}
Blythe, J., Hobbs, J.~R., Domingos, P., Kate, R.~J., \BBA\ Mooney, R.~J. \BBOP
  2011\BBCP.
\newblock \BBOQ Implementing Weighted Abduction in Markov Logic.\BBCQ\
\newblock In {\Bem Proceedings of the 9th International Conference on
  Computational Semantics}, IWCS '11, \mbox{\BPGS\ 55--64}.

\bibitem[\protect\BCAY{Chambers \BBA\ Jurafsky}{Chambers \BBA\
  Jurafsky}{2009}]{Chambers09}
Chambers, N.\BBACOMMA\ \BBA\ Jurafsky, D. \BBOP 2009\BBCP.
\newblock \BBOQ Unsupervised Learning of Narrative Schemas and their
  Participants.\BBCQ\
\newblock In {\Bem Proceedings of the 47th Annual Meeting of the Association
  for Computational Linguistics and the 4th International Joint Conference on
  Natural Language Processing of the AFNLP}, ACL '09, \mbox{\BPGS\ 602--610}.

\bibitem[\protect\BCAY{Copestake, Flickinger, Pollard, \BBA\ Sag}{Copestake
  et~al.}{2005}]{Copestake05}
Copestake, A., Flickinger, D., Pollard, C., \BBA\ Sag, I.~A. \BBOP 2005\BBCP.
\newblock \BBOQ Minimal Recursion Semantics: An Introduction.\BBCQ\
\newblock {\Bem Research on Language and Computation}, {\Bbf 3}  (2-3),
  \mbox{\BPGS\ 281--332}.

\bibitem[\protect\BCAY{Davidson}{Davidson}{1980}]{Davidson}
Davidson, D. \BBOP 1980\BBCP.
\newblock {\Bem Essays on Actions and Events}.
\newblock Oxford University Press.

\bibitem[\protect\BCAY{Fellbaum}{Fellbaum}{1998}]{fellbaum98}
Fellbaum, C.\BED\ \BBOP 1998\BBCP.
\newblock {\Bem WordNet: An Electronic Lexical Database}.
\newblock MIT Press.

\bibitem[\protect\BCAY{Gelfond \BBA\ Lifschitz}{Gelfond \BBA\
  Lifschitz}{1988}]{Gelfond88}
Gelfond, M.\BBACOMMA\ \BBA\ Lifschitz, V. \BBOP 1988\BBCP.
\newblock {\Bem The Stable Model Semantics for Logic Programming}, \mbox{\BPGS\
  1070--1080}.
\newblock MIT Press.

\bibitem[\protect\BCAY{Hobbs, Stickel, Martin, \BBA\ Edwards}{Hobbs
  et~al.}{1993}]{Hobbs93}
Hobbs, J.~R., Stickel, M., Martin, P., \BBA\ Edwards, D. \BBOP 1993\BBCP.
\newblock \BBOQ Interpretation as Abduction.\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bbf 63}, \mbox{\BPGS\ 69--142}.

\bibitem[\protect\BCAY{Hobbs}{Hobbs}{1985}]{Hobbs85}
Hobbs, J.~R. \BBOP 1985\BBCP.
\newblock \BBOQ Ontological Promiscuity.\BBCQ\
\newblock In {\Bem Proceedings of the 23rd Annual Meeting of the Association
  for Computational Linguistics}, ACL '85, \mbox{\BPGS\ 61--69}, Chicago,
  Illinois, USA. University of Chicago.

\bibitem[\protect\BCAY{Inoue \BBA\ Inui}{Inoue \BBA\ Inui}{2011a}]{Inoue11}
Inoue, N.\BBACOMMA\ \BBA\ Inui, K. \BBOP 2011a\BBCP.
\newblock \BBOQ ILP-Based Reasoning for Weighted Abduction.\BBCQ\
\newblock In {\Bem Plan, Activity, and Intent Recognition, Papers from the 2011
  AAAI Workshop}, AAAI '11, \mbox{\BPGS\ 25--32}.

\bibitem[\protect\BCAY{Inoue \BBA\ Inui}{Inoue \BBA\ Inui}{2011b}]{Inoue11b}
Inoue, N.\BBACOMMA\ \BBA\ Inui, K. \BBOP 2011b\BBCP.
\newblock \BBOQ An ILP Formulation of Abductive Inference for Discourse
  Interpretation.\BBCQ\
\newblock \Jem{情報処理学会研究報告．自然言語処理研究会報告}, {\Bbf 2011}  (3),
  \mbox{\BPGS\ 1--13}.

\bibitem[\protect\BCAY{Inoue \BBA\ Inui}{Inoue \BBA\ Inui}{2012}]{Inoue12b}
Inoue, N.\BBACOMMA\ \BBA\ Inui, K. \BBOP 2012\BBCP.
\newblock \BBOQ Large-scale Cost-based Abduction in Full-fledged First-order
  Predicate Logic with Cutting Plane Inference.\BBCQ\
\newblock In {\Bem Proceedings of the 13th European Conference on Logics in
  Artificial Intelligence}, \mbox{\BPGS\ 281--293}.

\bibitem[\protect\BCAY{井之上\JBA 乾\JBA {Ekaterina Ovchinnikova}\JBA {Jerry R.
  Hobbs}}{井之上 \Jetal }{2012}]{Inoue12}
井之上直也\JBA 乾健太郎\JBA {Ekaterina Ovchinnikova}\JBA {Jerry R. Hobbs} \BBOP
  2012\BBCP.
\newblock 大規模世界知識を用いた仮説推論による談話解析の課題と対策.\
\newblock \Jem{言語処理学会第 18 回年次大会論文集}, \mbox{\BPGS\ 119--122}.

\bibitem[\protect\BCAY{Levesque}{Levesque}{2011}]{Levesque11}
Levesque, H.~J. \BBOP 2011\BBCP.
\newblock \BBOQ The Winograd Schema Challenge.\BBCQ\
\newblock In {\Bem AAAI Spring Symposium: Logical Formalizations of Commonsense
  Reasoning}. AAAI.

\bibitem[\protect\BCAY{Manning, Surdeanu, Bauer, Finkel, Bethard, \BBA\
  McClosky}{Manning et~al.}{2014}]{CoreNLP}
Manning, C.~D., Surdeanu, M., Bauer, J., Finkel, J., Bethard, S.~J., \BBA\
  McClosky, D. \BBOP 2014\BBCP.
\newblock \BBOQ The Stanford CoreNLP Natural Language Processing Toolkit.\BBCQ\
\newblock In {\Bem Proceedings of the 52nd Annual Meeting of the Association
  for Computational Linguistics: System Demonstrations}, \mbox{\BPGS\ 55--60}.

\bibitem[\protect\BCAY{McCord}{McCord}{1990}]{Mccord90}
McCord, M.~C. \BBOP 1990\BBCP.
\newblock {\Bem Slot Grammar}.
\newblock Springer.

\bibitem[\protect\BCAY{Moore}{Moore}{1983}]{Moore83}
Moore, R.~C. \BBOP 1983\BBCP.
\newblock \BBOQ Semantical Considerations on Nonmonotonic Logic.\BBCQ\
\newblock In Bundy, A.\BED, {\Bem Proceedings of the 8th International Joint
  Conferences on Artificial Intelligence}, \mbox{\BPGS\ 272--279}. William
  Kaufmann.

\bibitem[\protect\BCAY{Mulkar, Hobbs, \BBA\ Hovy}{Mulkar
  et~al.}{2007}]{Mulkar07}
Mulkar, R., Hobbs, J., \BBA\ Hovy, E. \BBOP 2007\BBCP.
\newblock \BBOQ Learning from Reading Syntactically Complex Biology
  Texts.\BBCQ\
\newblock In {\Bem Proceedings of the 8th International Symposium on Logical
  Formalizations of Commonsense Reasoning}, Palo Alto.

\bibitem[\protect\BCAY{Ng \BBA\ Mooney}{Ng \BBA\ Mooney}{1992}]{Ng92}
Ng, H.~T.\BBACOMMA\ \BBA\ Mooney, R.~J. \BBOP 1992\BBCP.
\newblock \BBOQ Abductive Plan Recognition and Diagnosis: A Comprehensive
  Empirical Evaluation.\BBCQ\
\newblock In {\Bem Proceedings of the 3rd International Conference on
  Principles of Knowledge Representation and Reasoning}, \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. \BBOP 1997\BBCP.
\newblock {\Bem Foundations of Inductive Logic Programming}, \lowercase{\BVOL}\
  1228.
\newblock Springer Science \& Business Media.

\bibitem[\protect\BCAY{Ovchinnikova, Hobbs, Montazeri, McCord, Alexandrov,
  \BBA\ Mulkar-Mehta}{Ovchinnikova et~al.}{2011}]{Ovch11}
Ovchinnikova, E., Hobbs, J.~R., Montazeri, N., McCord, M.~C., Alexandrov, T.,
  \BBA\ Mulkar-Mehta, R. \BBOP 2011\BBCP.
\newblock \BBOQ Abductive Reasoning with a Large Knowledge Base for Discourse
  Processing.\BBCQ\
\newblock In {\Bem Proceedings of the 9th International Conference on
  Computational Semantics}, IWCS '11, \mbox{\BPGS\ 225--234}.

\bibitem[\protect\BCAY{Parsons}{Parsons}{1990}]{neodavidson}
Parsons, T. \BBOP 1990\BBCP.
\newblock {\Bem Events in the Semantics of English: A Study in Subatomic
  Semantics / Terence Parsons}.
\newblock MIT Press Cambridge, Mass.

\bibitem[\protect\BCAY{Raghavan \BBA\ Mooney}{Raghavan \BBA\
  Mooney}{2010}]{Raghavan10}
Raghavan, S.\BBACOMMA\ \BBA\ Mooney, R.~J. \BBOP 2010\BBCP.
\newblock \BBOQ Bayesian Abductive Logic Programs.\BBCQ\
\newblock In {\Bem Proceedings of the AAAI-10 Workshop on Statistical
  Relational Artificial Intelligence}, \lowercase{\BVOL}\ WS-10-06 of {\Bem
  AAAI Workshops}, \mbox{\BPGS\ 82--87}.

\bibitem[\protect\BCAY{Rahman \BBA\ Ng}{Rahman \BBA\ Ng}{2012}]{Rahman12}
Rahman, A.\BBACOMMA\ \BBA\ Ng, V. \BBOP 2012\BBCP.
\newblock \BBOQ Resolving Complex Cases of Definite Pronouns: The Winograd
  Schema Challenge.\BBCQ\
\newblock In {\Bem Proceedings of the 2012 Joint Conference on Empirical
  Methods in Natural Language Processing and Computational Natural Language
  Learning}, \mbox{\BPGS\ 777--789}, Jeju Island, Korea. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Reiter}{Reiter}{1978}]{raymond78}
Reiter, R. \BBOP 1978\BBCP.
\newblock \BBOQ On Closed World Data Bases.\BBCQ\
\newblock In Gallaire, H.\BBACOMMA\ \BBA\ Minker, J.\BEDS, {\Bem Logic and Data
  Bases}, \mbox{\BPGS\ 55--76}. Springer US.

\bibitem[\protect\BCAY{Reiter}{Reiter}{1987}]{Reiter87}
Reiter, R. \BBOP 1987\BBCP.
\newblock \BBOQ A Logic for Default Reasoning.\BBCQ\
\newblock In Ginsberg, M.~L.\BED, {\Bem Readings in Nonmonotonic Reasoning},
  \mbox{\BPGS\ 68--93}. Kaufmann, Los Altos, CA.

\bibitem[\protect\BCAY{Richardson \BBA\ Domingos}{Richardson \BBA\
  Domingos}{2006}]{Richardson06}
Richardson, M.\BBACOMMA\ \BBA\ Domingos, P. \BBOP 2006\BBCP.
\newblock \BBOQ Markov Logic Networks.\BBCQ\
\newblock {\Bem Machine learning}, {\Bbf 62}  (1-2), \mbox{\BPGS\ 107--136}.

\bibitem[\protect\BCAY{Ruppenhofer, Ellsworth, Petruck, Johnson, \BBA\
  Scheffczyk}{Ruppenhofer et~al.}{2010}]{framenetII}
Ruppenhofer, J., Ellsworth, M., Petruck, M.~R., Johnson, C.~R., \BBA\
  Scheffczyk, J. \BBOP 2010\BBCP.
\newblock \BBOQ FrameNet II: Extended Theory and Practice.\BBCQ.

\bibitem[\protect\BCAY{Schoenmackers, Etzioni, Weld, \BBA\ Davis}{Schoenmackers
  et~al.}{2010}]{Scho10}
Schoenmackers, S., Etzioni, O., Weld, D.~S., \BBA\ Davis, J. \BBOP 2010\BBCP.
\newblock \BBOQ Learning First-order Horn Clauses from Web Text.\BBCQ\
\newblock In {\Bem Proceedings of the 2010 Conference on Empirical Methods in
  Natural Language Processing}, EMNLP '10, \mbox{\BPGS\ 1088--1098}.

\bibitem[\protect\BCAY{Sch{\"{u}}ller}{Sch{\"{u}}ller}{2015}]{Schuller15}
Sch{\"{u}}ller, P. \BBOP 2015\BBCP.
\newblock \BBOQ Modeling Abduction over Acyclic First-Order Logic Horn Theories
  in Answer Set Programming: Preliminary Experiments.\BBCQ\
\newblock In {\Bem Proceedings of the 22nd RCRA International Workshop on
  Experimental Evaluation of Algorithms for Solving Problems with Combinatorial
  Explosion 2015 (RCRA 2015) A Workshop of the XIV International Conference of
  the Italian Association for Artificial Intelligence}, \mbox{\BPGS\ 76--90}.

\bibitem[\protect\BCAY{Singla \BBA\ Mooney}{Singla \BBA\
  Mooney}{2011}]{Singla11}
Singla, P.\BBACOMMA\ \BBA\ Mooney, R.~J. \BBOP 2011\BBCP.
\newblock \BBOQ Abductive Markov Logic for Plan Recognition.\BBCQ\
\newblock In {\Bem Proceedings of the 25th AAAI Conference on Artificial
  Intelligence}, AAAI '11, \mbox{\BPGS\ 1069--1075}.

\bibitem[\protect\BCAY{杉浦\JBA 井之上\JBA 乾}{杉浦 \Jetal }{2012}]{Sugiura12}
杉浦純\JBA 井之上直也\JBA 乾健太郎 \BBOP 2012\BBCP.
\newblock 説明生成に基づく談話構造解析の課題分析.\
\newblock \Jem{言語処理学会第 18 回年次大会論文集}, \mbox{\BPGS\ 115--118}.

\bibitem[\protect\BCAY{Thagard}{Thagard}{1978}]{Thagard78}
Thagard, P.~R. \BBOP 1978\BBCP.
\newblock \BBOQ The Best Explanation: Criteria for Theory Choice.\BBCQ\
\newblock {\Bem The Journal of Philosophy}, {\Bbf 1}, \mbox{\BPGS\ 76--92}.

\bibitem[\protect\BCAY{Yamamoto, Inoue, Inui, Arase, \BBA\ Tsujii}{Yamamoto
  et~al.}{2015}]{Yamamoto15}
Yamamoto, K., Inoue, N., Inui, K., Arase, Y., \BBA\ Tsujii, J. \BBOP 2015\BBCP.
\newblock \BBOQ Boosting the Efficiency of First-order Abductive Reasoning
  Using Pre-estimated Relatedness between Predicates.\BBCQ\
\newblock {\Bem International Journal of Machine Learning and Computing}, {\Bbf
  5}  (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}
