知識情報処理の歴史と知識を表現する言語とPrologと述語論理

ウェブ技術デジタルトランスフォーメーション技術人工知能技術機械学習自然言語処理技術推論技術セマンティックウェブ技術深層学習技術オンライン学習強化学習技術チャットボットと質疑応答技術ユーザーインターフェース技術知識情報処理技術プログラミングスパースモデリング確率的生成モデルサポートベクトルマシン Prologと知識情報処理本ブログのナビ

知識表現と推論(1) -知識情報処理の歴史と知識を表現する言語とProlog

機械学習以外の人工知能技術の中心となる知識情報処理技術の歴史と知識を表現する言語およびPrologについて述べる。

1960年代のAI研究は、探索問題に全力を注いでいた。特に、研究の多くは定理証明に関するものであった。すなわち、問題を公理の小さな集合として記述し、問題を証明するために探索するものである。従って、推論機構がその能力を持っているということが、暗黙の前提であった。正しい探索技法が発見できれば、問題は全て解かれて、定理もすべて証明できるということになる。

1970年代に入り、定理証明の考え方が、期待に応えられなかったため、このアプローチに課題があることがわかり始めた。AIの研究者たちが徐々に気づき始めたことは、どんなに賢い推論アルゴリズムが考案できたとしても、NP困難な問題は解けないだろうということになる。一般的な推論機構は、トイプロブレムには有効であったが、問題のサイズが大きくなった時に対応できなかったのである。

これに対する代替案は、エキスパートシステムの考え方となる。困難な問題を解く鍵は、問題をより簡単な問題に分けるための特例のルールを獲得することだと考えられた。Feigenbaumによれば、MYCINのようなエキスパートシステムから得られた教訓は、どのような推論機構を選択するかは、正しい知識表現を持つほど重要ではないということになる。この見方からすると、MYCINが前向き推論を使っているか、後ろ向き推論を使っているかは、あまり問題ではない。

また確信度、確率、ファジー集合理論を使用しているかどうかも問題ではない。重要なことは「緑膿菌は、免疫不全の患者に感染することがあり、グラム染色性が陰性で、形状が棹状の菌である」という知識をもっていることである。言い換えると、重要なことは知識の獲得と表現となる。

エキスパートシステムの考え方は、成功した部分もあった反面、失敗もあった。研究者たちは、新しい技法の限界を確認し、その技法がどのように機能しているかを理解することに関心を払った。研究者の多くは、システムで使用された知識が、明確に定義できていなかったことに重大な認織を持った。例えばアサーション(color apple red)は、特定のりんごが赤いことを意味するのか、すべてのりんごが赤いことを意味するのか、いくつか、または大半のりんごが赤いことを意味するのか。

知識表現の分野では、知識を操作するためのアルゴリズムの提供と同様に、知識表現のための明確なセマンティクスを提供することに注力した。表現力と効率の間で、良いトレードオフを見つけることに多くの関心が払われた。効率の良い言語とは、すべての質問(少なくとも平均的な質問)が、即座に応答される言語となる。質問が即座に応答されることを保証する必要があるならば、その言語で表現できるものを制限する必要がある。

1980年代の終わりには、一連の成果により、合理的な表現力を持つ効率の良い言語を見つけるという願望に対して疑問が生まれた。ワーストケース分析に基づく数学的な技法を使用することによって、一見したところ取るに足らないような言語でさえも解決困難であることが示された。単純な質問に応答するための計算量は、ワーストケースでは指数のオーダーになる。

1990年代の関心は、知識表現と推論へと変化した。この分野は、言語の表現力と効率の両方を顔容しているが、平均的なケースのほうが、ワーストケースよりも重要であると認織されている。

知識量は、ワーストケースにおいて、解決困難な問題を解くのには役立たないが、実際にはワーストケースは稀にしか起こらない。

AI研究者は、便利で表現力があり、効率が良い言語を見つけようとして、何百もの知識表現言語を調査した。言語は、その基本的な単位が何であるかに依存して4つのグループに分類できる。

論理式(Prolog等)
ネットワーク(意味ネットワーク、概念グラフ)
オブジェクト(スクリプト、フレーム)
手続き(Lisp、プロダクションシステム)

Prologのようなの論理ベース言語はこのブログの中でも述べている。

ネットワークベースの言語は、論理型言語の構文上の変形と見做せる。ノードAとノードこの間のリンクLは、論理関係L(A,B)を表現する別の方法となる。相違点は、ネットワークベース言語の方が、そのリンクを重要に扱う、すなわち、リンクはコンピューター内部のポインタによって直接に実装されることを意味し、推論はリンクを辿ることによって実行される。従って、AとBの間にリンクLを置くことは、L(A,B)が真であることを表明するだけでなく、知識ベースがどのように探索されるかについて、何かを表明することでもある。

オブジェクト指向言語は、述語論理の構文上の変形と見做せる。以下は典型的なスロット埋め込み型フレーム言語における文となる。

(a person
  (name = Jan)
  (age = 32))

これは以下の論理式と等価となる。

\[\exists p:\ person(p)\land name(p,Jan)\land age(p,32)\]

フレームで表記する方が読みやすいという意見もあるが、フレームの表現力は小さい、personのnameがJanまたはJohnのどちらかであることや、personのageが34でないことを述べる方法がない。もちろん、述語論理ではこのような文は容易に作れる。

手続き型言語は表現言語と対比される。すなわち、手続き型言語は知識の明示的な表現がなくても答えを計算する。

ハイブリッドの表現言語は、異なる種類の知識を表現するために異なる手法を併用する。例えば、KL-ONE familyは、論理式とネットワークに編成したオブジェクトの両方を使用する。フレーム言語の多くは、手続き付加(procedual attachment)が可能である。これは、フレーム言語自身で表現できないか、または表現が難しい表現の値を計算するために手続きを使用する技法となる。

ここまで述べてきた表現の多くは述語論理に基づいている。述語論理は、ちにの中で特別の地位にある表現方法となる。すなわち、他の表現方法の定義や評価を行う普遍性の高い標準としての価値がある。前述ではフレーム言語による表現例を示した。構文を使用する容易さやデータの内部表現の効率の観点からは、フレーム言語は多くの利点を持つ。しかし、言語で表現されたものの意味を理解するには、明確な定義が必要となる。述語論理を使用すれば、ほとんどの場合そのような定義を与えられる。

述語論理による知識表現は、関係や関数が適用された個体と、論理結合子and、or、notにより、関係を結合して形成された文を使用する。哲学者や心理学者は、人間の思考モデルとしての述語論理の適性について論じるだろう。しかし、以下の点に関しては明快となる。すなわち、述語論理は、デジタルコンピューターで表現できる任意のものを表現するには十分である。これを示すことは容易となる。コンピューターの記憶域がn bitで構成され、bi=はビットiがオンを意味するものと仮定すると、コンピューターの全状態は器用な連言により表現できる。

\[(b_0=0)\land (b_1=0)\land(b_2=1)\land\dots\land(b_n=0)\]

コンピューターのある状態を表現すれば、ある状態を別の状態にマップする公理群として、任意のコンピュータープログラムを、述語論理で表現できるようになる。このようにして、述語ロリがコンピューター内部で発生する任意の事象を表現するために十分な言語であることが示される。また、外側から任意のプログラムを分析するためのツールとして使用できる。

これは、述語論理がすべてのアプリケーションに適した言語であることを証明したわけではない。たの言語を使用する正当な理由がある場合もある。述語論理と全く異なる形式で知識を表現し、論理推論とは全く異なる形式でと式を捜査すべきこともある。しかし、述語論理の公理を使用してシステムを記述し、その定理を証明で値必要がある。手を省こうとすると粗雑になる。例えば、述語論理の公理を操作するよりも、むしろCPUに組み込まれた算術演算命令を使用してコンピューター内部の数を操作したいだろう。

しかし、平方根のルーチンを書く時には、次のような公理を満足させる方が良い。

\[\sqrt{x}=y\Rightarrow y\times y=x\]

術後論理は別の目的でも使用される。プログラムとしてというよりも、むしろプログラムによって使用できるツールとして役に立つ。すべてのプログラムはデータを操作する必要がある。また、プログラムによっては、述語論理の表現法で書かれているとみなされるデータを操作する。この使用法には関心がある。

述語論理を使用して、ある領域の事実を書き始めることは容易である。しかし、述語論理を正攻法で使用しても以下に示すような重大な制約に苦しむことになる。

決定可能性(decidability):公理の集合と目標が与えられた場合に、目標とその否定のどちらも、公理から導出できないかもしれない。
扱いやすさ(tractability):目標が証明可能であったとしても、利用可能な推論機構を使用してその証明を発見するには時間がかかり過ぎるかもしれない。
不確実性(uncertainty):ある程度証明されているが、真または偽であるか確実にはわからない関係を扱うことは不都合かもしれない。
単調性(monotonicity):純粋な述語論理では、いったん定理が証明されると永久に真である。しかし、仮説に基づいて仮の定理を導出し、仮説が偽であることが証明された時に、仮説を撤回する方法を持ちたい。
無矛盾性(consistency):純粋な述語論理では矛盾が許されない。偶然に、Pと¬Pの両方が導出されるならば、任意の定理が証明できる。要するに、矛盾が少しでもあればデータベース全体が汚染される。
全知性(omniscience):証明可能なものと、証明される必要があるものを区別することが難しいかもしれない、このことは、エージェントがわかっている事実からのすべての帰結を信じるととい根拠のない仮説につながる。
表現力(expressiveness):一階述語論理は、関係や命題のようなものについて語ると、ぎこちないものになる。

今日、優位を占めている考え方からすると、述語論理の内側と外側の両方から、これらの問題に対処するのが最善の方策となる。便利さのためと、汎用の定理証明器よりも効率の良い専用の推論機構を利用するために、新しい表記法を公案することは良いアイデアとなる。

しかし、よく知られている述語論理の表記法を使用して、新しい表記法の意味を綿密に定義することも重要となる。Drew McDermott(1978)も次のように表現している。「No notation without denotation(明示的意味がなければ表記法ではない)」

次に、既存の表現と推論システムを拡張するために、新しい表記法(とそれらに対応する意味)が、どのように使用されるかを示す。拡張する言語としてPrologを選択するが、究極の知識表現言語としてPrologを推薦するというものではなく、単に明快で基礎に精通しているからである。

Prologは、論理でプログラミングする問題に対する答えとして提案された。Prologはなぜ普遍的な知識表現言語として認められないのか?それはおそらく、Prologは知識表現言語とプログラミング言語との間で妥協があったためであると考えられる。論理的に等価な2つの使用が与えられると、一方は効率の良いPrologプログラムになるだろうが、他方はそうではない。

Kowalsjiの有名な等式「アルゴリズム=論理+制御」は、論理単独での限界を表している。すなわち、「論理=アルゴリズム-制御」となる。多くの問題(とくにAIにおける問題)は、大規模または無限の探索空間を持っている。Prologは、探索方法に関する助言を受けなければ、合理的な時間で答えを見つけ出せない。

Prologの問題は3つに分類される。最初に、言語の効率を良くするために、その表現力が制限されている。Prologでは、人の名前がJanまたはJohnであることを表現できない(人の名前がJanまたはJohnのどちらかであるかどうかの質問はできる)。どうように、ある事実が偽であるということも表明できない。Prologは偽と未知を区別しない。

2番目に、Prologの推論機構は正しくもないし、完全でもない。循環ユニフィケーションの検査をしないので、間違った答えを出すかもしれない。また深さ優先探索を行うので、正しい答えを見つけられないかもしれない。

3番目に、Prologは基本となる論理に制御情報を追加する良い方法を持たない。ただし、制御情報を追加すると、特定の問題に関しては効率を悪くするかもしれない。

Prologが論理でプログラミングする言語だとしても、それは完全な述語論理ではない。重要な問題は、Prologが、ある種の不明確な事実を表現できないことである。Prologは明確な事実は表現できる。かなわち、「Rhode Island州の州都はProvidenceである」は表現できる。また事実の連言も表現できる。すなわち「Rhode Island州の州都はProvidenceであり、かつClaifornia州の州都はSacramentoである」も表現できる。

しかし、選言や否定を表現できない。すなわち「Claifornia州の州都はLos Angelsでない」や「New York州の州都はNew York CityかAlbanyのどちらかである」は表現できない。次のことを試してみる。

(<- (not (capital LA CA)))
(<- (or (capital Albany NY) (capital NYC NY)

これら2つの事実は、関係capitalに関心があるわけではなく、関係notとorに関心がある。したがってcapitalについて質問するときには、それらは考慮されない。幸運にも、アサーション「MYCかAlbanyのどちらかがNY州の州都である」は、2つのアサーションに言い換えることができる。すなわち、「MYCがNY州の州都でなければ、AlbanyがNY州の州都である」と「AlbanyがNY州の州都でなければ、NYCがNY州の州都である」のように言い換えることができる。

(<- (capital Albany NY) (not (capital NYC NY)))
(<- (capital NYC NY) (not (capital Albany NY)))

不幸なことに、Prologのnotは論理のnotとは異なる、Prologが質問に対して、「no」と答えた時には、その質問が既知の事実からは証明できないことを意味している。あらゆることが街ならば、その質問は偽に違いない。しかし、未知事実があるとするならば、その質問は実際には真かもしれない。このことは驚くべきことではない。持っていない知識を利用して答えを見つけることを、プログラムに期待するのは正しくはない。

しかも、上記のケースでは問題を引き起こす。直前の2つの節と、質問(capital ?c NY)が与えられた時に、prologは無限ループに入る。最初の節を取り除くと、prologはAlbanyが州都であることの証明に失敗するので、結果的にNYCが州都であることが証明される。2番目の節を取り除くと、反対の結果が引き出される。

問題はPrologが、「証明されていない」ことと、「偽」を同等と見做すことである。Prologは閉世界仮説(closed world assumption)と呼ばれる状態を作り出す。それは真であるものはすべてが既知であると仮定する。閉世界仮説は、大半のプログラムにとって合理的である。なぜならば、プログラマは、関連する情報は全て知っているからである。しかし、一般的な知識表現では、閉世界仮説の状態をつくらず、質問に対する答えとして、「yes」「no」「unknown」の3つを持つシステムが必要である。

この例では、NY州の州都がNYCであるか、またはそNYCでないかは結論できないので、ALbanyについて何かを結論づけることはできない。

もう一つ例を考えてみる。

(<- (damned) (do))
(<- (damned) (not (do)))

これらのルールを使用すれば、質問(?- (damned))に対して、論理的には「yes」と答える必要がある。さらに(do)が証明されるか、または証明されないかを調べなくても、(damned)を結論づけることができるべきとなる。いずれにせよ、Prologは再度(do)を証明しようとし、証明が失敗するならば(damned)は証明される。このように、Prologは、証明が全く不必要な時に、同じ証明を2回行う。否定を導入すると、Prologの単純な評価機構では収拾がつかない。一度に、単一の節しか考慮しないのでは、もはや十分でない。正しい答えを導出したいのならば、複数の節を一緒に考慮する必要がある。

Robert Moore(1982)は、選言的推論の能力に関しての好例を提供している。彼の問題は、3つの色分けされたブロックに関するものではあるが、ここではブロックを国に変更する。ある東欧の国gが、共産主義国家を維持するか、または民主主義国家になるかどうかを決定したいけれども、その結果は未だわかっていない。gの国土は、民主主義国家Dと、社会主義国家cに囲まれている。

問題は「ある共産主義国家が、ある民主主義国家に隣接しているか?」である。Mooreは、答えは「yes」だと指摘しているが、答えを見出すにはケースごとに推論するひつようがある。Eが民主主義国家ならば、Cに隣接しているので、答えは「yes」である。Eが共産主義国家ならば、Dに隣接しているので、やはり答えは「yes」となる。可能性は2つしかないので、答えはいかなる場合でも「yes」にならなければならない。

論理推論は正しい答えを教えてくれるが、Prologはそれができない。以下の7つのアサーションと、一つの質問で問題を記述する。しかし、Prologは最後のアサーションのorを扱えない。

(<- (next-to D E))(<- (next-to E D))
(<- (next-to E C))(<- (next-to C E))
(<- (democracy D))(<- (communist C))
(<- (or (democracy E)(communist E)))

(?- (next-to ?A ?B)(democracy ?A)(communist ?B))

Prologは、選言と否定があまり得意でないことが確認できた。また、存在を表現することも難しい。英文、論理、Prologで書かれた次のような例を考えてみる。

Jan likes everyone.
∀x person(x)⇒likes(Jan,x)
(<- (likes Jan ?x)(person ?x))

この例では、prologの翻訳は忠実だが、「Jan likes someone」となると、良い翻訳が見つからない。最も忠実と思われるものは以下となる。

Jan likes someone.
∃x person(x)⇒likes(Jan,x)
(<- (likes Jan p1))
(<- (person p1))

この例では、Janが好む未知の人を表す新しいシンボルp1を導入している。p1は変数ではなく定数となる。特定されてはいるが未知の存在を表す定数は、Thoralf Skolemにちなんで、スコーレム定数(Skolem constant)と呼ばれている。目的は、p1が、その存在を知っている、あるいは他の人に等しいかもしれないということを表現することである。

Janが好む人がAdrianだということが分かれば、アサーションp1=Adrianを追加できる。しかし、これはPrologではうまく働かない。なぜならば、Prologは、異なるアトムが異なる個体を指すという名前の唯一性仮説(unique name asssumotion)を暗黙的に使用するからである。

実際には、スコーレム定数は一つ以上の変数によって決まる未知の存在を表すスコーレム関数(Skolem function)の特殊なケースとなる。例えば「誰かが誰かを好む」をあせ和すには次のように記述する。

Everyone likes someone.
∀y∃x person(x)⇒likes(y,x)
(<- (likes ?y (p2 ?y)))
(<- (person (p2 ?y)))

この例では、p2が変数?yによって決まるスコーレム関数となる。言い換えれば、「誰もが、必ずしも同じ人でないある人を好む」となる。

前述では、Prologは効率を上げるために、表現力を犠牲にしていることを述べた。今回は、述語論理における表現力の限界について述べる。

ライオン、トラ、クマが動物の一種であることを表敬する必要がある。述語論理やPrologでは、ケースごとに次のような含意をかける。

(<- (animal ?x)(lion ?x))
(<- (animal ?x)(tiger ?x))
(<- (animal ?x)(bear ?x))

これらの含意を使用すれば、任意の既知のライオン、トラ、クマが動物であることを証明できる。しかし、「そこには、どのような種類の動物がいるのか?」の質問には答えられない。以下の質問に答えられるような、Prologの拡張を考えること自体は難しくない。

(?- (<- (animal ?x) ?proposition))

しかし、この拡張はPrologにとって正当ではないし、一階述語論理(FOPC)にとってさえも正当ではない。FOPCでは、変数は、その言語の中の定数を表すものであり、関係や命題を表すものではあってはならない。高階述語論理には、この制約はないが、証明論が複雑になる。

上記の質問においても、?propositionの値が何であるべきかは明白ではない。(lion ?x)が正当な答えであることは確かだが、(animal ?x)、(or (tiger ?x)(bear ?x))などその他の命題が無限に存在する。おそらく「種類」に関する質問と、命題に関する質問の2つのタイプの質問をするべきだろう。

また、関係に関して質問する必要がある可能性がある。Lisp関数で、パラメータの型を宣言することが有益であるのと同様に、関係のパラメータの型を宣言して、後でその型を質問することは有益だろう。例えば、関係likesは、personとobjectとの関係を保持することを言及できる。

一般には、関係や文を項として使用する述語論理の文を、高階文(high-order sentence)と呼ぶ。高階表現の使用を許す場合には、ある微妙な問題が表面化する。すなわち、「「この分は偽である」という分は真か、それとも偽か?」である。

述語論理は、固体で構成されてる世界において、個体の特性や個体感の関係を利用して定義される。したがって、述語論理は、例えば、ここにいる人間、あそこの建物、それらの間にある歩道というように個体を見つけ出して、それらを分類するというモデルに適している。しかし、連続的な実態の世界は、例えば全体としては水であるけれども、いくらかは蒸発して空気に混ざり、いくらかは上昇して雲になるような、不定の成分からなる水を考えるとそれらを個体として定義する方法は明らかでない。これに対してPatrick Hayesは、適切な選択が行われると、述語論理でこの種の状況をうまく記述できることを示している。

さらにカテゴリを定義する場合、さらに困難な問題がある。述語論理は、数学的に明確なカテゴリに関してはうまく機能する。例えば「xが3辺を持つ多角形の時、かつその時に限り、xは3角形である」などとなる。残念ながら、人間が日々の生活で使用するカテゴリの大半は、それほど幻覚に定義できない。「友人」というカテゴリは、通常は、信頼できるなどの好意的な感情を持てる誰かを参照する。この「定義」は必要ではあるが十分ではない。

むしろカテゴリ「友人」と高い相関関係があるが、範囲が明確でない特性のリストである。理想的な友人のプロトタイプは記述できるが、「友人」と「知人」を区別する明確な境界は記述できない。その上、境界は、状況ごとに変わる。すなわち、職場ではよき友人だと記述できる人でも、家庭生活では、単なる知人であるかもしれない。

「すべての〜に対して(for all)」や「存在する(there exist)」に加えて、「ほとんどの(most)」のような限定詞を許す述語論理もある。また、プロトタイプを定義して、そこからの距離を測定する試みもある。