言語処理学会 第21回年次大会 発表論文集 (2015年3月)

FOL を表現する論理ネットワーク：依存構造からの変換の試み
鈴木 秀明
情報通信研究機構 脳情報通信融合研究センター

hsuzuki@nict.go.jp

概要

構造との関係において研究されているグラフに、DCS木（Dependency-based Compositional Semantics Tree）

一階述語論理 (FOL) のプログラム（ホーン節の集（Petri-net-baesd Knowledge Transitive Network）という[4] がある。最初これはデータベースに対する検索を行なうクエリの表現として提案されたが、田ら [17, 18]
はこれをベースに外延を抽象的に表わした関係代数を記述形式を対象とし、自然言語文（英文）から pKTN定義し、完備ではないが自然言語のある部分をカバーへの変換の定式化を試みる。pKTN によると、信念・する高速な推論機構を実現した。しかしながら、DCS時間・副詞句等を除く自然言語に含まれる FOL 知識

木やその外延の抽象表現は、データベースに有限サイが、入れ子等のグラフ構造化をすることなく表現されズのものを仮定しており、その結果、論理表現能力とることが示唆させる。

しては、FOL から全称限量される変数を除いたものを合）をひと繋がりのペトリネットによって表わす pKTN

キーワード：ペトリネット、pKTN、一階述語論理、依存表現するにとどまった。

構造、意味解析

一方鈴木らはごく最近、FOL（特に、ホーン節集合）のグラフ表現として pKTN（Petri-net-baesd Knowledge

1

Transitive Network）という記述形式を提案した [10, 11,12, 13, 14, 15]。pKTN は FOL の定数・変数・関数記

はじめに自然言語から論理を抽出して推論を行なうために、号、および述語をプレースで表わしたペトリネット

これまでいくつかのグラフを用いる手法が提案されてで、それ上の演繹（後向き推論）が、pKTN を展開しきた。初期の意味ネットワーク (SN) [5, 6] は、概念たペトリネットにおける、部分グラフの探索と制約条ノードを ‘is’,‘have’ といった関係を表わすエッジで繋件間の辻褄合わせ（単一化）として定式化できる。鈴いだ比較的単純・素朴なものであった。その記述能力

木らはこれを解くためのアルゴリズムとして、ELISEは一階述語論理 (FOL) と同等だが、場当たり的で見通（ELiminating Inconsistency by SElection）と呼ばれる、しが悪い上、推論には知識グラフとクエリ・グラフのトークンの局所伝搬を利用し、信頼度と共に単一化解間の構造マッチングという重い処理を必要とした。

を求める（ある種の曖昧推論を行なう）方法も提案し一方、Sowa によって提案された概念グラフ (CG)ている [12]。ネットワークに冗長性のない場合、ELISE[8, 1, 9] は SN をより洗練させたものであり、概念ノードと格を表わす概念関係ノードという 2 種類のノードを用意することにより、エッジラベルをなくすことには変数の個数にほぼ比例した時間で収束することが報成功した。これによりグラフの均質性が向上し、FOL

然言語文の動詞に対応する述語を中心に構築されるたとの対応もより明確化されたが、例えば含意を表わすめ、自然文の依存構造と高い親和性を持つ。本論文はためには、グラフ構造化（入れ子にすること）を行なこの点に着目し、自然言語文（英文）から抽出されるう必要がある。けれども、CG で導入された、1 引数依存構造グラフ（動詞述語を頂点、その他の単語を枝述語（概念）と 2 引数述語（概念関係）の連言によ葉とする係り受けネットワーク）を pKTN に変換す告されている。

pKTN では、述語論理の節に相当するグラフが、自り節を記述する方法は、自然言語から FOL へ変換する処方箋を定式化することを試みる。定式化に基づくる際の一つの規範となった。CG は最近の Google のと、自然言語文から抽出される全ての FOL 相当の論『Knowledge Graph』[19] のルーツにもなっている。

理が、均質で入れ子構造を持たないネットワークに変CG は格ベースのグラフであることから、自然言語の依存構造 [16, 3, 2] と親和性を持つが、もう一つ依存換されることが示唆される。

― 976 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

以下ではまず、第 2 節で pKTN とそれによる論理プログラムの表現について述べ、第 3 節では依存構造からの変換について述べる。第 4 節に結論を述べる。

2pKTN
pKTN [10, 11, 12, 13, 14, 15] とは、論理プログラムを非同期並列計算のモデルであるペトリネットで表わす表現方法である。pKTN の特徴を以下にまとめる。
▲ネットワークは FOL の定数・変数・関数記号を表わすプレースと、∈ もしくは&のラベルを持つトランジションが有向アークで繋がれた 2 部グラフ構成をとる。アークはラベル情報を持たない。
▲ FOL、特にホーン節の集合で表わされる任意の論理プログラムが、所定の規則によって pKTN へ変換できる。
▲演繹推論ではまず、pKTN がゴール節を起点として、展開 pKTN（AND/OR グラフ）へと展開される。演繹
解の有無は、あるシンボル代入（単一化）の下での展開 pKTN の真偽、即ち根を真とする部分グラフの存在の有無と等価であることが証明できる（健全性と完全性）[11, 12]。
▲前記の部分グラフ特定と単一化を行なうために、

ELISE（ELiminating Inconsistency by SElection）と呼ばれる局所並列アルゴリズムが用いられる。展開 pKTNの中で、“信頼度”（[0, 1] 間の連続実数）を付加したトー

図 1: ホーン節から pKTN への変換の例。(a),(b) はゴール節、(c)∼(f) は事実節、(g)∼(i) はルール節の変換例。丸および楕円がプレース、四角がトランジションを表わす。複数のアークにかかる太線の弧は AND 記号である。

クンが何度も往復伝搬しながら、シンボル間の矛盾に応じて選択淘汰されることにより、変数制約条件に合致した単一化解が漸近的に求められる。最終的なトーて、たとえ頭部引数と本体引数が共通項を持たなくてクンの信頼度が、解の真偽の度合いを連続的に（曖昧も、単連結となることが保証される。に）表現する。

図 2 に論理プログラム（ホーン節集合）から pKTN

図 1 にいくつかのホーン節を pKTN に変換した例への変換の例を示す。述語プレース Wife 、Child を共を示す。一般に pKTN は、項プレースから述語プレー有することにより、グラフは一繋がりに連結され、ルース（ゴール節で）、述語プレースから項プレース（事プを持つようになる。共有されたプレース（Child ）か実節で）、頭部の述語プレースから本体の述語プレーら出る複数のアークは論理 OR の関係を持つが、それス（ルール節で）へと一方向に流れる有向グラフであらの順番は問題とはならない。

る。プレース間にはトランジションが挿入されるが、引数が複数個あって ∈ トランジションが挿入される
場合、合成／分解される複数のアークには論理 AND

3依存構造からの変換の関係がマーキングされる。これらのアークのトラン
自然英語文は、依存構造（動詞述語を頂点とする木ジションにとっての順番は重要である。なおルール節（図 1(g)∼(i)）の場合には、頭部述語と本体述語の間には引数項のプレースが挿入されるが、こうして作られる pKTN は、論理的なトークンだけを保持するプレース（図 1(g)∼(i) の白丸）や AND を意味する ‘&’ トランジション（図 1(i) のオレンジの四角）の挿入によっ構造）を介して pKTN へと変換できる。図 3∼5 にいく
つかの変換例を示す。依存構造図には自然文に含まれる全ての単語または句が漏れなく含まれており、その間の文法的／意味的係り受け関係が、実線および点線で示されている。このような係り受け関係から、我々― 977 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

図 2: 論理プログラムから pKTN への変換の例。
図 4: 自然英語文（疑問文）から pKTN への変換の例。

図 3: 自然英語文（平叙文）から pKTN への変換の例。この図、および続く図では、自然英語文、依存構造グラフ、pKTNが上から順番に示されている。依存構造グラフのレイアウ
トは、pKTN に習い、平叙文では動詞述語を左に、疑問文では動詞述語を右に、仮定節を含意する関係代名詞節や、仮定節を表わす部分は動詞述語を右に配置している。依存構
造グラフ中の実線は単語や句の間の直接の係り受け関係を表わし、点線は代名詞や関係代名詞によるリンクを表わす。

図 5: 自然英語文 −(a) 関係代名詞節、(b) 仮定節を含む文 −から pKTN への変換の例。となるが、論理的には等価である。
図 4(a) と (b) には同様に、同じ内容を含む異なった疑問文の例を示す。疑問文であるため、図 3 と異なり、は pKTN を次のようにして構築できる。まず、主な品動詞／述語が図の右側に配置されている。(b) には疑問詞／句の変換ルールを以下に示す：を表わす ‘does’、関係節を表わす ‘who’ が含まれるが、これらは依存構造グラフで、それぞれ動詞（‘equal’）

・不定冠詞＋名詞変数＋述語や be 動詞（‘is’）のさらに右側に配置される。なお、

述語 or 関数記号

定数(a) では be 動詞が省略されるため、補語である ‘a man’は述語へ変換されるが、(b) では ‘a man’（不定冠詞＋名詞）は ‘x’ ＋ ‘Man’（変数＋述語）へと変換されて(削除)いる。この ‘x’ は、代名詞 ‘someone’ が変換されて出・定冠詞＋名詞・代名詞⇒・固有名詞・be 動詞・動詞⇒⇒⇒変数⇒⇒

述語来る変数を兼ねている。

図 3(a) と (b) は、同じ内容を含む異なった平叙文の図 5(a) と (b) は、良く用いられる『ロバ文』[7] の例である。(a) では be 動詞 ‘is’ が省略されて定冠詞＋異なる表現である。まず (a) は、関係代名詞を使って名詞 ‘the wife’ が述語に変換されているが、(b) では動仮定を暗示的に表わした例である。依存構造グラフで

詞 ‘equal’ が省略されず、‘wife’ は関数記号へと変換さは、関係代名詞 ‘who’ に引っ張れて動詞 ‘own’ は右へれている。作られる pKTN は (a) と (b) で異なるもの配置され、それによって pKTN でも述語 ‘Own’ は右― 978 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

側へ来る。不定冠詞＋名詞（‘a farmer’ と ‘a donkey’）[5] Quillian, M.: Semantic Memory. In Minsky, M. (ed.): Semantic Information Processing. MIT Press: Cambridge,MA. (1968) 216-270

はともに変数＋述語へと変換される。一方 (b) では、仮定が if-節によってを明示的に表わされている。‘if’

例は、意味が等しいが構造が異なる自然言語文が同一[6] Randal, D.M.: Semantic Networks. In: Ringland, G.A.,
Duce, D.A. (Eds.): Knowledge Representation - An Introduction. Research Studies Press, Ltd. (1988) Chapter
3, pp.45-80の pKTN へと変換された。なお、ここで生成された変[7] 白井賢一郎：自然言語の意味論．産業図書 (1991)に引っ張れた動詞 ‘own’ はやはり右へ配置され、それによって述語 ‘Own’ も右側へと来る。このロバ文の 2

数 x,y は、形式上はともにスコーレム標準形の中の全[8] Sowa, J.F.: Conceptual Structures: Information Processing in Mind and Machine. Addison-Wesley: Reading,MA. (1984)

称限量された変数であるが、ELISE を用いた後向き推論では、クエリ起因のトークンだけが根側から流れてくるため、ロバ文が抱える限量子の問題をごく自然な[9] Sowa, J.F.: Conceptual Graphs. In: van Harmelen, F., Lifschitz, V., Porter, B. (eds.): The Handbook of Knowledge
Representation, Chapter 5. Elsevier (2008) pp. 213 − 237

形で克服することが出来る。

4

結論
一階述語論理 (FOL) のプログラム（ホーン節の集合）

をひと繋がりのペトリネットによって表わす pKTN という記述形式を対象とし、自然言語文（英文）からpKTN への変換の定式化を試みた。その結果、仮定節や関係代名詞節を含む全ての平叙文と疑問文が、適切に抽出された依存構造グラフから pKTN に変換されるという見通しを得た。今後は、定式化のリファインとその計算機実装を進めるとともに、ELISE による推論と融合して、自然言語の意味解析への応用展開を目指す。
特に、今回の報告には含めなかったが、否定文をネッ
トワークを入れ子にすることなく表わすためには、新[10] 鈴木 秀明，吉田 幹，澤井 秀文：演繹推論を実現するデー
タフローネットワークの提案．人工知能学会研究会資料 人工知能基本問題研究会（第 83 回）SIG-FPAI-B102(2011) 1-7[11] Suzuki, H., Yoshida, M., Sawai, H.: A data-flow network that represents first-order logic for inference. In:Kuo, Y.H., Tseng, V.S.M., Kao, H.Y., Hong, T.P., Horng,M.F. (eds.): The 2012 Conference on Technologies andApplications of Artificial Intelligence TAAI, Proceedings(2012) 211-218 DOI: 10.1109/TAAI.2012.44[12] Suzuki, H., Yoshida, M., Sawai, H.: A network representation of first-order logic that uses token evolution for inference. Journal of Information Science and Engineering(JISE) 30(3) (2014) 669-686[13] 鈴木秀明，吉田 幹：述語を変数ノードに持つペトリ
ネット型 KTN を用いた論理表現と演繹．計測自動制御学会 (SICE) 第 41 回知能システムシンポジウム資料(2014) B22-3

たな種類のプレース／トランジションの導入が必要なことが分かっており、その扱いについての検討を行なう必要がある。また、信念文、副詞句等の FOL を越える表現について、新たなプレースの導入によってpKTN に変換できる可能性が示唆されており、それに[14] Suzuki, H., Yoshida, M.: Direct graphical representationof first-order logic for inference. In: Lambert, M.J. (ed.):
Logic Programming: Theory, Practices and Challenges.
Chap.4. Nova Science Publishers, Inc. (2014) 117-142
ISBN: 978-1-63117-853-5[15] 鈴木 秀明: 論理と言語を共通に表現するペトリネッ
ト型推論モデル．計測自動制御学会システム・情報部
門学術講演会講演論文集 (SSI-2014)．(2014) GS11-6,pp.254-260

ついても検討を行なう予定である。

参考文献[1] Amati, G., Ounis, I.: Conceptual Graphs and First Order
Logic. The Computer Journal 43(1) (2000) 1-12
[2] 麻生 英樹：句構造と依存構造について．2012 年度人工知能学会全国大会（第 26 回）論文集 (2012) 4K1-OS-2-9[3] Kubler, S., McDonald, R., Nivre, J.: Dependency Parsing(Synthesis Lectures on Human Language Technologies).
Morgan and Claypool Publishers (2009)[4] P. Liang, M. Jordan, and D. Klein. Learning dependencybased compositional semantics. Proceedings of the 49th
Annual Meeting of the Association for Computational
Linguistics: Human Language Technologies (ACL-HLT’11) - Volume 1 (2011) Pages 590-599[16] Tensniere, L.: Elements de Syntaxe Structurale, Kliensieck, 1959. （小泉（監訳）, 構造統語論要説, 研究社,2007.）[17] Tian, R., Miyao, Y., Matsuzaki, T.: Logical Inferenceon Dependency-based Compositional Semantics. In: Proceedings of the 52th Annual Meeting of the Association
for Computational Linguistics (2014)[18] 田 然，宮尾 祐介：テキスト推論でセンター試験の歴史問題を解く．2014 年度人工知能学会全国大会（第 28回）論文集 2A1-4[19] Zhang, L.: Knowledge graph theory and structural parsing. Thesis, Twente University Press (2002)― 979 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.