# DTS の部分体系のための 定理自動証明器の実装に向けて

大洞日音
お茶の水女子大学
daido. hinari@is.ocha.ac.jp
}

戸次大介
お茶の水女子大学
bekki@is.ocha.ac.jp
}

$
\left[\begin{array}{l}
v:\left[\begin{array}{l}
u:\left[\begin{array}{l}
x: \text { entity } \\
\operatorname{man}(x)
\end{array}}] \\
\operatorname{enter}\left(\pi_{1} u})
\end{array}}] \\
\text { whistle }\left(\pi_{1} \pi_{1} v})
\end{array}}]
$

図 1 DTS の例

$\exists x(\operatorname{man}(x) \wedge \operatorname{enter}(x)) \wedge$ whistle $(x)$

図 2 一階述語論理の例

には十分である．そこで本研究では，DTS の断片の ための定理自動証明器を新規に開発し, 定理証明器 の評価用ライブラリである Thousands of Problems for Theorem Provers (TPTP) ${ }^{1}$ を用いて定量的な評価を行 い，ある程度の推論を網羅できることを示した。
## 2 依存型意味論 (DTS)

高階型理論の一種であるDTS は, 関数型と直積型の一般化として П型と $\Sigma$ 型を用いる。 П 型は $(x: A) \rightarrow B$ という形で表記し, 後件の型 $\mathrm{B}$ は前件 の型 $\mathrm{A}$ をつ項に依存する. $\Sigma$ 型は $(x: A) \times B$ と表記し， П型と同様に B が型 A もつ項に依存する. この性質から DTS は前提・照応など自然言語にお ける複雑な現象を統一的に扱うことができる。図 1 は “A man enters. He whistles. ” から合成的に計算 された DTS の意味表現である。一方，この文を語 の意味から合成的に計算して一階述語論理で表記す ると図 2 のようになるのが自然であるが，これは存在量化子のスコープが適切ではない. このように,自然言語の意味計算には一階述語論理の記述力を越 える現象が多々存在するが，高階論理を用いた DTS では自然に扱うことができる.

DTS の定理証明は型理論における項の探索に対応している. 型理論では $\Gamma \vdash a: A$ という judgment を用いて文脈 $\Gamma$ において項 $a$ の型が $A$ であること を表す。一方, 論理的観点からこの judgment をみる と, これは前提 $\Gamma$ のもとで命題 $A$ の証明が $a$ であ


る,という意味である.このことから， $a$ は証明項 とも呼ばれ，証明項を探索することは証明探索と呼 ばれる。

図 3 証明探索の例

図 3 で“?”の部分に当てはまる項を探索すると $\left(\pi_{1} \pi_{1} \pi_{1} t, \pi_{2} \pi_{1} \pi_{1} t\right)$ という証明項を得ることができ， これをデコードすることで証明探索においてどのよ うな規則をどのような順番で適用したかという情報 を得ることができる.

## 3 実装

本研究で実装した定理証明器の構造を図 6 に 示す.

図 6 定理証明器の構造

アルゴリズムは Alligator [5] において提案された ものの改良である. forward_context では前向き推論を, deduce では後ろ向き推論を行っている. 前向 き推論では, 前提と結論が与えられたとき, 前提に 規則を繰り返し適用することで上から下へと自然演繹形式の証明木を構築し, 前提から導きうる命題 を蓄積する，後万向き推論では，まず結論に規則 を適用して証明のために必要なゴールを割り出し，下から上に証明木を構築していく形で推論を行う. forward_context は引数として前提を受け取り, 前向き推論の結果として得られた judgment のリスト を返す。forward_context で使用する規則の一部を 図 4 に示す. deduce は図 5 にあるような規則を用い
て後ろ向き推論を行い, judgment のリストを返す. deduce は無限再帰に陥る可能性があるため，探索の 深さや，かかる時間に制限を置くことで，計算の制御を行っている.

## 4 評価

実装にはプログラミング言語 Haskell を用い，実験環境には産総研の $\mathrm{AI}$ 橋渡しクラウド $(\mathrm{ABCI})^{2}$ を 用いた。定理自動証明器の評価のための包括的なラ イブラリである TPTP から, Alligator でカバーされ ていない等号や四則演算の問題を除いたデータセッ トによって評価を行った。 TPTP ライブラリに収録 されている問題は図 7 のような形式である.

図 7 TPTPに収録されている二重否定律の問題

推論の結果と各評価ラベルの関係は, 図 8 のとお りである.

図 8 評価の形式

## 4.1 構文解析器 :

Haskell の Alex/Happy library $[7,8]$ を用いて TPTP フォーマットから Haskell のデータ型への変換を行 う Alex/Happy Parser を実装した。このデータ型を中間言語として, 読み込んだ TPTP 形式の問題を, 本

2) https://abci.ai/
$\Gamma r_{F} z:\left[\begin{array}{l}x: A \\ B\end{array}\right]$

$\Gamma \vdash_{F} \pi_{1}(z): A$

$(\Sigma$-elim 1-1)

$
\frac{\Gamma \vdash_{F} z:\left[\begin{array}{l}
x: A \\
B
\end{array}\right]}{\Gamma \vdash_{F} \pi_{2}(z): B\left[\pi_{1}(z) / x\right]}
$

$(\Sigma$-elim 1-2)

$
\Gamma \vdash_{F} z: \Gamma_{1} \Rightarrow\left[\begin{array}{l}
x: A \\
B
\end{array}\right]
$

$
\overline{\Gamma \vdash_{F} \lambda x_{1}: m_{1} \ldots x_{n}: m_{n} \cdot \pi_{1}(z)\left(x_{1}\right) \ldots\left(x_{n}\right): \Gamma_{1} \Rightarrow A}
$

$(\Sigma$-elim 2-1)

$
\begin{aligned}
& \Gamma \vdash_{F} z: \Gamma_{1} \Rightarrow\left[\begin{array}{l}
x: A \\
B
\end{array}\right] \\
& \begin{array}{l}
n_{1} \ldots x_{n}: m_{n} \cdot \pi_{2}(z)\left(x_{1}\right) \ldots\left(x_{n}\right. \\
\Gamma_{1}=\left[x_{1}: m_{1}, \ldots, a_{n}: x_{n}\right] \\
B^{\prime}=B\left[\pi_{1}(z) / x\right]
\end{array}
\end{aligned}
$

$
\overline{\Gamma r_{F} \lambda x_{1}: m_{1} \ldots x_{n}: m_{n} \cdot \pi_{2}(z)\left(x_{1}\right) \ldots\left(x_{n}\right): \Gamma_{1} \Rightarrow B^{\prime}}
$

$(\Sigma$-elim 2-2)

図 4 forward_context の規則 (一部)

研究の定理証明器が対応している Haskell データ形式や Alligator が対応している Prolog データ形式へ翻訳する.

## 4.2 証明探索：

本研究の定理証明器は, 与えられた文脈 $\Gamma$ と命題 $A$ について, $\Gamma \vdash ?: A$ という問題の証明項が見つ かったときは YES ラベルを, $\Gamma+?: \neg A$ という問題 の証明項が見つかったときは $\mathrm{NO}$ ラベルを返す．証明探索が停止せず，証明項が見つからなかった場合 は UNK ラベルを返すが，このとき必ずしも命題が 偽であるとは言えない点に注意する。

## 4.3 結果 :

探索の深さ制限を 8 と 9 に設定した際の結果を 表 1 に示す. この結果から, accuracy は探索の深さ 制限に依存することが考えられる ${ }^{3}$ ．表 2 で，YES


$\overline{\epsilon \vdash s: s^{\prime}}$

(axiom)

$
\begin{gathered}
\Gamma \vdash a: A \quad \Gamma \vdash b: B[x / a] \quad \Gamma \vdash(x: x) \rightarrow A B: s \\
\Gamma \vdash(a, b):\left[\begin{array}{c}
x: A \\
B
\end{array}\right] \\
(\Sigma \text {-intro) }
\end{gathered}
$

図 5 deduce の規則 (一部)

表 1 探索の深さを $9 / 8$ としたときの結果

表 2 探索の深さを 9 としたときの結果詳細

ラベルと NO ラベル両方について precision は 1 であ ることから，推論での規則の適用は適切であると考 えられる。一方, recall はどちらについても低く, 特 に NO ラベルについての recall は YES ラベルと比べ

は $0.104 ， 0.050,0.025$ であることが確認された.

図 9 問題の複雑さと証明探索の結果の関係

ても低い。これは, 評価の過程で $\mathrm{NO}$ ラベルの証明 の際, 命題に否定記号 (ᄀ) を追加しており, 命題の 構造が複雑になる分, 深さ制限を超過しやすくなる ためと考えられる. 図 9 はラベルが YES である問題について, 問題の複雑さと証明探索の結果の関係 を示すぺアプロットである. オレンジのドットは証明探索の結果出力されたラベルが YES であったこ とを，青のドットはUNKであったことを表す. アプロットの $y$ 軸は命題の深さを, $x$ 軸は述語, 変数, アトム，ファンクタの数を表しており，いずれ も高ければ高いほど問題の複雑さは増す.この結果 から, 今回実装した定理証明器は $x$ と $y$ の値が小さ い単純な問題については正確に計算を行えているこ とが示された. 深さ制限を緩めると計算量が指数関数的に増加する一方, より多くの問題を解けるよう になることが期待される.

本研究の定理証明器は, 古典論理と直観主義論理の双方に対応しており, TPTP の問題の中 でもパースの法則 $(p \Rightarrow q) \Rightarrow p) \Rightarrow p$ や対偶律 $(p \Rightarrow q) \Longleftrightarrow(\neg q \Rightarrow \neg p)$, 排中律 $p \vee \neg p$ など, 推論 において重要な役割を果たす定理についてもカバー することを確認した。

## 5 おわりに

本研究では DTS の部分体系 ( $\Pi \Sigma$ 断片) について 証明探索アルゴリズムを実装し，TPTP ライブラリ を用いて評価を行った。その結果，十分な範囲の定理について適切に自動計算を行うことを確認した。今後は自然言語推論で用いられる, 等号や算術に ついても扱えるようアルゴリズムを拡張していく. また, 日本語 CCG パーザ lightblue[9] と組み合わせ ることによって, 自然言語推論のためのパイプライ ンを構築し, DTS 基づく検証可能な意味計算シス テムを実現することが今後の課題である.

## 謝辞

本研究の一部は，JSPS 科研費 JP18H03284，およ び JST CREST JPMJCR20D2 の助成を受けたもので ある.また，評価の際は産総研の AI 橋渡しクラウ ド $(\mathrm{ABCI})$ を利用した。

## 参考文献

[1] Johan Bos. Wide-coverage semantic analysis with Boxer. In Semantics in Text Processing. STEP 2008 Conference Proceedings, pp. 277-286, 2008.

[2] Lasha Abzianidze. LangPro: Natural language theorem prover. In Proceedings of EMNLP2017 System Demonstrations, pp. 115-120, Copenhagen, Denmark, September 2017.

[3] Pascual Martínez-Gómez, Koji Mineshima, Yusuke Miyao, and Daisuke Bekki. ccg2lambda: A Compositional Semantics System. In Proceedings of ACL 2016 System Demonstrations, pp. 85-90, 2016.

[4] Daisuke Bekki and Koji Mineshima. Context-passing and underspecification in Dependent Type Semantics. In Modern Perspectives in Type Theoretical Semantics, pp. 11-41. Springer, 2017.

[5] Paul Piwek. The alligator theorem prover for dependent type systems: Description and proof sample. In Proceedings of the Inference in Computational Semantics Workshop, pp. 157-163, 2006.

[6] Daisuke Bekki and Miho Satoh. Calculating projections via type checking. In TYTLES: Types Theory and Lexical Semantics, Robin Cooper, Christian Retore (eds.), pp. 6268, 2015.

[7] alex: Alex is a tool for generating lexical analysers in Haskell. https://hackage. haskell.org/package/ alex/.

[8] happy: Happy is a parser generator for Haskell. https: //hackage.haskell.org/package/happy.

[9] Daisuke Bekki and Ai Kawazoe. Implementing variable vectors in a ccg parser. In LACL2016, Nancy, France, C.Retore and S.Pogodalla (Eds), pp. 52-67, Heiderburg, 2016.
 大洞日音 お茶の水女子大学 daido. hinari@is.ocha.ac.jp }  戸次大介 お茶の水女子大学 bekki@is.ocha.ac.jp }  $ \left[\begin{array}{l} v:\left[\begin{array}{l} u:\left[\begin{array}{l} x: \text { entity } \\ \operatorname{man}(x) \end{array}}] \\ \operatorname{enter}\left(\pi_{1} u}) \end{array}}] \\ \text { whistle }\left(\pi_{1} \pi_{1} v}) \end{array}}] $  図 1 DTS の例  $\exists x(\operatorname{man}(x) \wedge \operatorname{enter}(x)) \wedge$ whistle $(x)$  図 2 一階述語論理の例  には十分である．そこで本研究では，DTS の断片の ための定理自動証明器を新規に開発し, 定理証明器 の評価用ライブラリである Thousands of Problems for Theorem Provers (TPTP) ${ }^{1}$ を用いて定量的な評価を行 い，ある程度の推論を網羅できることを示した。 