Prologの動作原理と自然言語処理

この記事はtraP Advent Calendar 2016の23日目の記事です。当日の朝に書くとかウッソだろお前！

Hello, Everybody. Davidです。この記事ではあまり聞きなれないPrologというプログラミング言語について書きます。PrologはいいぞHaskellはもっといいぞ

事前知識

述語論理に関して多少の知見があれば良いという程度です。

Prologはいわゆる論理型言語というプログラミング言語の一種ですが、論理のことが分かっていないと書けないわけではありません。Prologの動作原理に関するところではん？となるかもしれませんが本筋では無いのであまり気にしなくて良いでしょう。一応参考となる論理学の本を2冊ほど挙げておきます。

https://www.amazon.co.jp/情報科学における論理-情報数学セミナー-小野-寛晰/dp/4535608148

https://www.amazon.co.jp/復刊-数理論理学-松本-和夫/dp/4320016823/ref=sr_1_2?s=books&ie=UTF8&qid=1482449510&sr=1-2&keywords=数理論理学(難しいやつ)

Prologの紹介

Prologはプログラミング言語です。チューリング完全なので理論上はいかなるプログラムもその他の言語同様に書くことが出来ます。

Prologのパラダイムは論理型です。論理型と言われてピンとこない人も多いとは思いますが、動作原理として一階述語論理学のフレームワークを使っている、と思ってください。

論理型プログラミング言語はここ20年くらいあまり活発に使われていません。逆にそれ以前はすごく脚光を浴びたパラダイムでした。これには様々な事情があるのですが、気になる方は"第五世代コンピュータ"で調べると色々出ると思います。

さて、Prologのベースとなる論理式は以下の含意です。

A :- B.

これはBならばAと読みます。
他にもいくつか見てみましょう。

A :- not(B). % BでなければA
A :- B, C. % BかつCならばA
A :- B; C. % BまたはCならばA

Prologのプログラムは上記のような論理式(ホーン節)の集合で構成されています。実行の際はPrologインタプリタにプログラムを読み込ませることで、インタプリタが投げられたクエリ(論理式)がプログラム中のホーン節から導ける(真になる)かどうかを判定します。

これだけでは何がなんだか分かりづらいので、簡単な例で見てみましょう。

まずは実行環境ですが、swi-plorogを使います。無料だしISO規格だし様々なライブラリも使えてアドです。これを書いている人はOS Xを使っているので、brew経由でインストールしました。

まず以下Prologプログラムをooo.swiとして保存しましょう。

human(soba).
human(math_yakuza).
human(haskell_type_yakuza).

like_haskell(math_yakuza).
like_haskell(haskell_type_yakuza).
like_D(soba).

have_kanojo(ikemen).

join(traP, soba).
join(traP, haskell_type_yakuza).
join(measure_theorem_seminar, haskell_type_yakuza).
join(measure_theorem_seminar, math_yakuza).

free_so(X) :- like_D(X), join(traP, X), human(X).

このooo.swiをPrologインタプリタに読み込ませます。

$swipl -f ooo.swi

それではインタプリタにクエリを投げてみましょう。

?- human(soba).
true.
?- join(traP, soba).
true.
?- have_kanojo(soba).
false.
?- join(traP, soba), join(traP, haskell_type_yakuza).
true.
?- free_so(soba).
true.

クエリの述語に論理変数を入れることで, trueとなるような定数をとってくることも出来ます。

?- human(X).
X = soba;
X = math_yakuza;
X = haskell_type_yakuza.

?- join(traP, X).
X = soba;
X = haskell_type_yakuza.

?- join(X, haskell_type_yakuza).
X = traP;
X = measure_theorem_seminar.

?- free_so(X).
X = soba;
false.

ここで注意が必要なのは、クエリを投げた後に返ってくる論理変数の値が複数存在するときは、";"で次の値を得ることができるということです。取りうる値が1つしかない場合に";"を入力すると最後の例の様にfalseが返ってきます。

ここで述語"free_so"に付いて見てみましょう。

free_so(X) :- like_D(X), join(traP, X), human(X).

これは、D言語が好きで、traPのメンバーで、人間であれば、フリー素材である、という意味です。一意に定まるね

この様に、Prologは物事と物事の間に成り立つ関係に基づいてプログラムを書いていきます。

Prologの動作原理

では、Prologはどうやって動いているのでしょうか？

Prologの原理は論理学に基づいており、その動作は深さ優先探索として表現することが出来ます。

融合法(resolution)

まず理論の方を少し見てみましょう。

Prologの紹介で見たように、Prologのプログラムはホーン節の集合です。Prologインタプリタは投げられたクエリ(論理式)が説明できるか、ということを、ホーン節の集合から証明という形で探索します。

ここで話を簡単にするために一回述語論理から命題論理に限定して、論理式と論理式から別の論理式を導く方法を見て見ましょう。

任意の命題論理式は選言標準形という、1つ以上のリテラル(原始論理式またはそれの否定)を1つ以上含む論理和の形式になっている論理式に変換出来ます。選言標準形の論理式に対し、以下のような演算$⊢$が定義出来ます。

a ∨ c, ¬a ∨ b $⊢$ b ∨ c

が成り立ちます。これは融合(resolution)と呼ばれるもので、正しさを保存する演算です。

Prologの論理式にこれを適用するためには、2つの異なる論理変数同士を同じ論理変数に書き換える単一化という演算が必要だったり、融合法は一階述語論理が満たす完全性を満たしてなく代わりに反駁完全性を満たしていたり、完全性を満たすためには融合法を包摂という演算で強化する必要があったり、というのは今回は書きません。長すぎるんじゃ

融合法が反駁完全というのは、もし一階述語論理の論理式が充足不能であれば、融合法は必ず矛盾を導くことが出来る、ということを示しています。この反駁完全性というのは背理法を想定しており、与えられた論理式の集合K、 示したい論理式の集合をQとすれば、K' = K ∪ ¬QとしてK'から矛盾を導くことが出来れば、K $⊢$ Qが背理法によって導けるということです。

しかしこれだけではPrologの動作と直感的な対応付けが出来ません。

このホーン節を見てみましょう。

free_so(X) :- like_D(X), join(traP, X), human(X).

これは論理式として書くと、以下のように書けます(もちろんPrologの文法上では間違いですが)

free_so(X) ∨ ¬like_D(X) ∨ ¬join(traP, X) ∨ ¬human(X).

ここまで来ると、融合法をどのように適用すれば良いか分かると思います。

Prologのインタプリタは、¬が付いた述語を、ホーン節の集合の中に存在する節を深さ優先探索しながら、述語名がマッチした節に対し融合と単一化を行いながら投げられたクエリ(論理式)が真であるかを探索します。

実際に上の例でどのように探索が行われているか見てみましょう。

Prologインタプリタで以下のように入力してみます。

?- trace, free_so(X).

得られるのは以下のような探索の系列です。

Call:(8) free_so(_G1235) ? creep
Call:(9) like_D(_G1235) ? creep
Exit:(9) like_D(soba) ? creep
Call:(9) join(traP, soba) ? creep
Exit:(9) join(traP, soba) ? creep
Call:(9) human(soba) ? creep
Exit:(9) human(soba) ? creep
Exit:(8) free_so(soba) ? creep
X = soba.

分かりづらい()

ですが、左のCallとExitに注目すると、Callが新たな探索に入り、Exitがその探索から抜けることが分かると思います。

?- free_so(haskell_type_yakuza).
Call:(7) free_so(haskell_type_yakuza) ? creep
Call:(8) like_D(haskell_type_yakuza) ? creep
Fail:(8) like_D(haskell_type_yakuza) ? creep
Fail:(7) free_so(haskell_type_yakuza) ? creep
false.

このように、プログラム中の論理式からクエリ(論理式)が説明出来ない場合は、探索としてこのような動作をしていることが分かります。

DCG(Difinite Clause Grammar)

さて、Prologの動作原理をゆるふわに理解したところで、Prologの強力な文法について見ていきましょう。

DCGと呼ばれる記法は、パーサを書くためのものです。

1見は114514聞に如かず。実際にどのようなものか見てみるのが早いでしょう。

s --> np, vp.
np --> det, noun.

% np --> noun, [and], noun, {write('I found two nouns.'), nl}.

vp --> verb, np.
vp --> verb, np, pp.
pp --> prep, np.

/*
det --> [the].
det --> [a].
*/

det --> [the]; [a].
noun --> [soba].
noun --> [cocoro].
verb --> [eat].
prep --> [to].
prep --> [in, front, of].

クエリ(論理式)として以下を投げてみましょう。

?- s([the, soba, eat, the, cocoro], []).
true.

?- s([the, X, eat, the, Y], []).
X = Y, Y = soba;
X = soba,
Y = cocoro;
X = cocoro,
Y = soba;
X = Y, Y = cocoro;
false.

この動作はどうやって実現しているのでしょうか？

この"-->"という演算子を用いて書かれたホーン節は、以下のように書き換えることが出来ます。

s --> np, vp.
s(L1, L) :- np(L1, L2), vp(L2, L).

det --> [the].

det([the | L], L).

これらは全く等価です。

DCGは応用が広く、その一つが入力された文を自然言語処理で重要な意味形式(λ計算の形)に変換するパーサです。

簡単な例で見てみます。

s(Predicate) -->
 np(Subject), vp(Subject^Predicate).

vp(Semantics) --> verb, np(Semantics).

np(soba) --> [soba].
np(naruse) --> [naruse].
np(X) --> det, noun(X).

noun(X^programmer(X)) --> [programmer].
noun(X^titech_student(X)) --> [titech_student].


det --> [a].
verb --> [is].

これに対して以下のようなクエリを投げると、

?- s(T, [soba, is, a, programmer], []).
T = programmer(soba);
false.

と返って来ます。

上のクエリのTには、β変換されたλ式が単一化されます。

X^programmer(X)

という部分は

λ x . programmer(x)

ということを意味しています。

Prologの自然言語処理への応用例

さて、今までPrologの文法等を見て来ましたが、ぶっちゃけ書かないとこのパラダイムには中々慣れないと思います。

そこで細かいことは抜きにして、いくつかプログラムを見てみることにします。時間がなくて書けない

編集距離

与えられた2つの文字列を一致させるためにはどれくらい文字列の操作コストが必要か、という問題があります。Prologだと文字列その距離を求めるだけでなく、距離を指定した時の文字列操作がどのようなものになるか、系列として得ることも、比較的簡単な記述で可能です。

% edit_distance(+Source, +Target, -Edits, +Cost).
edit_distance(Source, Target, Edits, Cost) :-
 edit_distance(Source, Target, Edits, 0, Cost).

edit_distance([], [], [], Cost, Cost).
edit_distance(Source, Target, [EditOp | Edits], Cost, FinalCost) :-
 edit_operation(Source, Target, NewSource, NewTarget, EditOp, CostOp),
 Cost1 is Cost + CostOp,
 edit_distance(NewSource, NewTarget, Edits, Cost1, FinalCost).

%edit_operation carries out one edit operaion
edit_operation([Char | Source], [Char | Target], Source, Target, ident, 0).
edit_operation([SChar | Source], [TChar | Target], Source, Target, sub(SChar, TChar), 2) :-
 SChar \= TChar.
edit_operation([SChar | Source], Target, Source, Target, del(SChar), 1).
edit_operation(Source, [TChar | Target], Source, Target, ins(TChar), 1).

クエリとしては以下のようなものを投げます。

?- edit_distance([s, o, b, a, y, a], [y, a, k, u, z, a], Edits, Cost).

Edits = [sub(s, y), sub(o, a), sub(b, k), sub(a, u), sub(y, z), ident],

Cost = 10;

Edits = [sub(s, y), sub(o, a), sub(b, k), sub(a, u), sub(y, z), del(a), ins(a)],

Cost = 12;

Edits = [sub(s, y), sub(o, a), sub(b, k), sub(a, u), sub(y, z), ins(a), del(a)],

Cost = 12;

Edits = [sub(s, y), sub(o, a), sub(b, k), sub(a, u), del(y), sub(a, z), ins(a)],

Cost = 12
...

以下取りうる編集距離とそれに対する編集を無限に返します。

意味形式パーサ(量化無し)

上で見た意味形式に変換するパーサの複雑なバージョンです。

s(Sem) --> np(Sub), vp(Sub^Sem).

np(SemNP) --> npx(SemNP).
np(SemNP) --> npx(SemVP^SemNP), vp_passive(SemVP).

vp(SemVP) --> verb_group(SemVP).
vp(SemVP) --> verb_group(Obj^SemVP), np(Obj).
% vp(SemVP) --> verb_group(Obj^SemVP), vp_inf(Obj).
vp(Sub^SemVP) -->
 verb_group(SemInf^Sub^SemVP),
 vp_inf(Sub^SemInf).

npx(SemNP) --> pro(SemNP).
npx(SemNP) --> noun(SemNP).
npx(SemNP) --> det, noun(SemNP).
% vp --> aux, vp.

verb_group(SemVG) --> aux(SemAux), verb(SemVG).
verb_group(SemVG) --> verb(SemVG).

verb(Obj^Sub^like(Sub, Obj)) --> [like].
verb(Obj^Sub^hear(Sub, Obj)) --> [hear].
verb(Obj^Sub^play(Sub, Obj)) --> [play].
verb(Obj^Sub^punch(Sub, Obj)) --> [punch].
verb(Obj^Sub^yakuzas(Sub, Obj)) --> [yakuzas].
verb(Obj^Sub^fuck(Sub, Obj)) --> [fuck].

verb_passive(Sub^Obj^compose(Sub, Obj)) --> [composed].
verb_passive(Sub^Obj^punched(Sub, Obj)) --> [punched].
verb_passive(Sub^Obj^fucked(Sub, Obj)) --> [fucked].

vp_inf(SemVP) --> [to], vp(SemVP).
vp_passive(SemVP) --> verb_passive(Sub^SemVP), [by], np(Sub).

aux(would) --> [would].

pro('I') --> ['I'].
% pro(something) --> [something].
pro(Modifier^something(Modifier)) --> [something].

noun(N) --> proper_noun(N).
noun(Modifier^waiter(Modifier)) --> [waiter].

proper_noun('Shrcyan') --> ['Shrcyan'].
proper_noun('Sobaya') --> ['Sobaya'].
proper_noun('DgenGO') --> ['DgenGO'].
proper_noun('Buri') --> ['Buri'].
proper_noun('Haskell_kata_yakuza') --> ['Haskell_kata_yakuza'].

det --> [some].
det --> [the].

conj --> [and].

クエリを投げてみます。

?- s(T, ['I', like, something, composed, by, 'Sobaya'], []).

T = like('I', something(_G1365^compose('Sobaya', _G1365)));

false.

意味形式にまだ適用されていない変数が"_G1365"という形で残っています。これは自然言語に置ける代名詞の一種である先行詞と照応詞の関係によるものになっています。

意味形式パーサ(量化有り)

英語で言うa, the, all等の量化を考慮した意味形式パーサです。

s(Sem) --> np((X^SemRest)^Sem), vp(X^SemRest).

sentence(Sem) -->
 np((X^SemRest)^Sem), vp(X^SemRest), {asserta(Sem)}.

np(Sem) --> determiner((X^SemNP)^Sem), noun(X^SemNP).

/*
np(SemNP) --> npx(SemNP).
np(SemNP) --> npx(SemVP^SemNP), vp_passive(SemVP).
*/

vp(X^SemRest) --> verb(X^SemRest).
vp(X^SemRest) -->
 verb(Y^X^SemVerb),
 np((Y^SemVerb)^SemRest).

noun(N) --> proper_noun(N).

noun(X^waiter(X)) --> [waiter].
noun(X^patron(X)) --> [patron].
noun(X^meal(X)) --> [meal].

proper_noun(X^'Shrcyan'(X)) --> ['Shrcyan'].

verb(X^rushed(X)) --> [rushed].
verb(Y^X^ordered(X, Y)) --> [ordered].
verb(Y^X^brought(X, Y)) --> [brought].

determiner((X^SemNP)^(X^SemRest)^a(X, SemNP, SemRest)) -->
 [a].
determiner((X^SemNP)^(X^SemRest)^the(X, SemNP, SemRest)) -->
 [the].

?- s(T, [a, 'Shrcyan', brought, the, meal], []).

T = a(_G1387, 'Shrcyan'(_G1387), the(_G1408, meal(_G1408), brought(_G1387, _G1408)));

false.

このように、単一化される意味形式は量化された対象を考慮するため、常に論理変数が入っています。

終わりに

最後は駆け足でしたが、Prologの力の一片が垣間見れたと思います。

これはどんなパラダイムの言語にも言えることですが、Prologのようなパラダイムの言語は、一部の問題は簡単に解けますが、別の問題は非常に複雑になってしまうという側面があります。Prologはそれが非常に顕著で、制御的に書こうとすると記述量が非常に多くなってしまいます。

今回は載せていませんが、単語のconcordanceを抜き出すコードなんかはもう手続き型で書けば簡潔に書けるのに対し、Prologで同じものを書くと頭がぽわわするくらいのめんどくさいコードになります。

しかし、Prologは一部の分野(知識表現、計算論的機械学習)、つまり人工知能の分野には非常に有効であることは間違いなく、個人的には今後は現在主流となっている統計的機械学習と組み合わさって、人工知能を発展させていくのだと思っています。

この記事でPrologに興味を持ってくれる人が出てくればと思います。皆さんもぜひ、一度はPrologを触ってみてはいかがでしょうか。私はしばらくはPrologは書きたくないですHaskell書くぞ書くぞ

Davidでした。

参考にした文献

https://www.amazon.co.jp/帰納論理プログラミング-古川-康一/dp/4320120140

https://www.amazon.co.jp/Introduction-Language-Processing-Perl-Prolog/dp/3642064051