エージェントシステム：第 ¿ 回講義参考資料稲邑哲也 ¾¼¼ 年 ½¼ 月 ½ 日 ½ 一階述語論理による推論 ½º½ 述語論理形式論理を基本的な知識表現として利用することは，人工知能研究の初期にまでさかのぼって行われてきた．論理に基づいた数学的演繹は，既存の知識かｒああ田らしい知識を生成する方法として良く用いられている．初期のＡＩ研究者は自分達の知識を利用していた．形式論理は文の作られ方を定義する構文規則（×ÝÒØ Ü）と，その意味を表す意味論 ´× Ñ ÒØ ×µ を独自に持つ言語である．最も基本的な論理表現はブール論理あるいは，命題論理と呼ばれる．それぞれの命題あるいはファクトは記号で表現され，真（ØÙÖ ），または偽 ´ Ð× µ で評価される．文は命題シンボル ´È¸É¸Ê などµ や，ブール型接続詞，つまり連限 ´ ÓÒ ÙÒ Ø ÓÒµ Ò ，選言 ´ × ÙÒ Ø ÓÒµÓÖ，含意，等価などを用いて構築される．こうした簡素な構文規則を用いることで，含意やルールを書くことが可能となり，プログラムすることも可能となる． ½º¾ 限量子を含む推論規則命題論理での推論規則は，三段論法に必要なモーダスポーネンス， Ò 除去， Ò 導入，ÇÖ 導入と融合法であった． ¯ モーダスポーネンス（含意除去）：含意とその前提が真ならば結論は真 «µ¬ « ¬ ¯ Ò 除去：連言が真ならばそれぞれの連言子は真 «½ «¾ ¯ Ò « ÇÖ ¡¡¡ «Ò ´¾µ 導入：真となる文のリストが与えられたときその連言は真 «½ «¾ «½ «¾ ¯ ´½µ ¡ ¡ ¡ «Ò ¡ ¡ ¡ «Ò ´¿µ 導入：有る文が真ならばそれと他の任意の文を含む選言は真 «½ «¾ ¯ 融合 « ¡¡¡ ´ µ «Ò « ¬ ¬ « 一階述語論理ではこれに加え，以下の三つの規則が追加される．ここで ËÍ た結果を表す． ½ ´ µ ËÌ ´ «µ は，文 « にを適用し ¯ 全称除去：任意の文 «¸ 変数 Ú と基礎項に対して， Ú« ËÍ ËÌ ´ Ú ¯ 存在除去：任意の文 «¸ 変数 Ú と知識ベースのどこにも背湯津源していない定数記号 Ú« ËÍ ËÌ ´ Ú ´ µ «µ に対して ´ µ «µ ¯ 存在導入：任意の文 « と¸« に出現しない変数 Ú および « に出現する基礎項に対して， « ÚËÍ ËÌ ´ ½º¿ ´ µ Ú «µ 証明の手続き初期状態を記述する一階述語論理の文 Ã からスタートし，適用可能な推論規則をオペーレータとして考え，証明したい文をゴールであると考えると，一階述語論理の推論は一種の探索問題になる．しかしながら，全称除去は，変数を任意の基礎項で置換できるため，それ自体に関して膨大な分岐度をもつ．また，モーダスポーネンスの適用に多くの時間を費やすため，探索問題の計算量は爆発する傾向にある．そのため，単一化やホーン節が扱える標準形への変換などを行う工夫をする． ½º 前向きアルゴリズム，後ろ向きアルゴリズムここで一階述語論理における探索は一般的な探索問題と同等に扱える．ゴールを求めるように前提から推論を進めるのが前向きアルゴリズム．逆に求めたいゴールの文からスタートして前提を導けるかどうかをチェックするのが後ろ向きアルゴリズムである． ½º 完全性ここで， ÜÈ ´Üµ µ É´Üµ Ü È ´Üµ µ Ê´Üµ ÜÉ´Üµ µ Ë ´Üµ ÜÊ´Üµ µ Ë ´Üµ ´ µ ´½¼µ ´½½µ ´½¾µ とう規則から Ë ´ µ を結論づけることを考える．直感的には簡単に推論できるが，モーダスポーネンスを用いた場合，Ë ´ µ を導出することはできない．問題は， Ü È ´Üµ µ Ê´Üµ をホーン節に変換できず，モーダスポーネンスを適用できないからである．これをモーダスポーネンスを用いる証明手続きが不完全であるという．実際には融合アルゴリズムと呼ばれる方法で証明可能であるが，その証明可能／不可能を議論するために，ÃÙÖØ Ó Ð は完全性定理を発表した．これは，一階述語論理の場合，ある文の集合から含意される任意の文をその文集号から証明できることを証明するものである．これは干し草の中の針を探し当てるような手続きが存在すると言っているだけであり，実際にどのような手続きが良いのか，という事に言及しているわけではないことに注意が必要である．また，有名は不完全性定理とは全く関係が無いのでこれも注意． ¾ P(w) => Q(w) Q(y) => S(y) {y/w} True => P(x) R(x) > P(w) => S(w) {w/x} R(z) => S(z) R(x) > True => S(x) {x/A, z/A} True => S(A) 図 ½ 融合法を利用した Ë ´ µ の成立の証明手順．Ｖ形の枝は融合ステップを表す．上の二つの文は前提であり，下は融合節である． ¾ 推論システム ¾º½ 論理プログラミングシステム ÈÖÓÐÓ ÈÖÓÐÓ プログラミング言語は非手続き型プログラミング言語の一つで，論理型言語に分類される．名前の由来は ÈÖÓ Ö ÑÑ Ò Ò ÄÓ の略である．½ ¾ 年ごろにイギリス・エジンバラ大学の ÊÓ Ð Ò 論体系が作られ，フランス・マルセイユ大学 Àº ÖØ ÃÓÛ Ð× によって理 ÓÐÑ Ö Ù Ö によって確立された言語である．½ 年に Ú º Ï ÖÖ Ò らによって計算機上に実装された．一階述語論理に基づいてデータ間の関係を示す命題としてプログラムが記述されるのが特徴である．解釈処理系は単一化（ユニフィケーション）を施しながら，与えられた命題が成立するか否かを再帰的手続きによって探索する．トップ・ダウン式の問題解決方法と相性が良いために，人工知能研究，特にエキスパートシステムの実現のための主要言語として広く採用された． ½ ¼ 年代，日本の国家プロジェクトである「第世代コンピュータ技術開発機構（Á ÇÌ）」が，知識情報処理システム開発の核言語として ÈÖÓÐÓ を採用し，注目を浴びることとなった．ここでの「世代」とは，コンピュータの素子技術による時系列的な分類である．第１世代：真空管，第２世代：トランジスタ，第三世代：Á ∼ÄËÁ，第４世代：超 ÄËÁ，となり，最終的に第５世代はそれまでとはまったく異なるシステム，と定義されている．実際には明確な定義があるわけではなく，ニューロコンピューティングや人工知能のことなどを指していることが多い．プロジェクトは ÈÖÓÐÓ を一つの成果として公表した． ÈÖÓÐÓ プログラムは規則 ´ÖÙÐ µ・事実 ´ Øµ・目標 ´ Ó Ðµ を示すホーン節の集合によって成り立ち¸ 前提条件とそれに対応する帰結条件という統一した形で記述されるº 一般的な ÈÖÓÐÓ プログラムは複数の規則と複数の事実¸ そして ½ つの目標によって構成され¸ 与えられた規則と事実から目標が導けるかという後ろ向き推論の原理で動作するº 次のような特徴を持つ．記号処理言語，リスト処理言語データとして，記号 ´シンボルµ を取り扱うことができる．また，リストと呼ばれる可変長のデータの列を取り扱うことができる．論理型言語 ÈÖÓÐÓ ÈÖÓÐÓ では新たな述語を論理式で定義することによってプログラムを作り上げていく．すなわち，のプログラムは論理式の集まりである． ÈÖÓÐÓ や ÄÁËÈ は， ÇÊÌÊ Æ や ËÁ などの手続き型言語とは異なり，非手続き型言語と呼ばれる．対話的使用，会話的使用 ÈÖÓÐÓ システムの使用形態は対話的である．すなわち，ユーザは ÈÖÓÐÓ システムを ¿ 立ち上げたあと，システムと会話するような形で命令を与え，述語を定義したり実行したりできる．また，論理の側面から見ると以下のような性質を持っている． ¯ プログラムは文の列からなるが，これらは暗黙の内に連言的に結合されている．全ての変数は，暗黙の内に全称束縛されており，別の文の変数は互いに異なるものとされる． ¯ ホーン節のみを受け付ける．つまり，文は原子文から，もしくは前件に否定が無く後件後見が原子分であるような含意文のいずれかとする． ¯ 項は定数記号か変数か関数項である． ¯ 質問は連言，選言，変数，関数項を含んでよい ¯ 含意文の前件での否定の代わりに，ÈÖÓÐÓ では失敗による否定演算子が用いられる．つまり，システムが È の証明に失敗したとき ÒÓØ È が証明されたとする． ¯ すべての統語的に異なる項は異なるオブジェクトを指示している物とする．つまりとか ´Üµ などを表明することはできない．Ü が変数のとき，Ü とか Ü ことができる．を定数とするとき， Ý ´ µ なら表明する ¯ 算術，入出力，システムや知識ベースのいろいろな昨日のための組み込み述語がたくさん用意されている．これらの述語を使ったリテラルは，推論ではなく機械命令の実行により証明される． ¾º¾ 単一化単一化は，述語論理の二つの文を同一のものにするような置換方法をお見つける技術である．これは上で議論したような融合を用いる定理証明の用件である．もし二つの述語が同一であるなら，それらは定義によりマッチしているという．一つか双方が変数を含むのなら，以下のような単一化を用いて定説な置き換えが見つけられなければならない． ¯ 変数を定数によって置き換える ¯ 変数を別の変数によって置き換える ¯ 変数を述語で置き換える．ただしその述語がその変数を含まない限り以下のような述語の組み合わせを使ってそれらがどのように単一化されるかの例を示す． ½º Ø ×´ ¸ µ ¾º Ø ×´ ¿º Ø ×´ Ð Ü¸ ×Ô Ò ÓÖ ÓÖ ¸ ÓÐ µ µ に束縛し， ÖÓ ÓÐ ´ブロッコリーµ を変数を変数できる．同様に ÖÓ Ð Ü と，×Ô Ò ´ほうれん草µ とに束縛すれば，２番目の文は１番目の文と単一化を束縛することができる．述語名が異なれば，これらの述語を単一化することはできない．いくつか述語を追加することでもっと複雑な単一化を調べることができる． º Ø ×´ ¸Ú Ø º Ø ×´ ¸ Ú º Ø ×´ ¸ ÓÖ ÖÓ Ð ´ µµ ÓÐ µ Ø Ð ´ ÖÓ ÓÐ µµ 変数を変数，変数を定数 ÖÓ ÓÐ と置き換えることで，６番目の文を１番目の文と単一化できる．に， ÖÓ ÓÐ を変数をに結びつけることで，４番目の文と５番目の文は単一化される．Ñ Ø ÓÖ と呼ばれる単一化アルゴリズムの一般化された版が ÈÖÓÐÓ で用いられている．ÈÖÓÐÓ では，ファクトは節で表現される．節は標準の述語のように見え，無条件で真であるとそのものごとについて宣言している．結論が正しいところでは， ÖÙÐ はすべての条件部の節が真であれば，結論は真になるような節である．ルールの処理やゴール節として提示される質問への回答のため，ÈÖÓÐÓ は融合に基づいた組み込みの推論手続きを提供する．述語はルールを表現し，推論するのに使うことができるが，全てのルールシステムが知識を表現する言語として述語論理を用いるわけではない．初期のルールベースシステムは ÈÖÓÐÓ や Ä ×Ô を使って開発されてきたが，多くの商用系処理系は現在のところ， ··や Â Ú を用いて書かれている．この ÈÖÓÐÓ はデータベース，再帰的プログラミング，記号処理，リスト処理，探索問題，言語処理などに強く，定理証明器などにも使われ，第５世代コンピュータプロジェクト ´Á ÇÌµ の中心的なプログラミング言語 ´ÃÄ½µ として採用された． ¾º¿ プロダクションシステム特に，ÈÖÓÐÓ などの論理プログラミングはプロダクションシステムを構築するのに適している．プロダクションシステムは前向き推論に基づく推論エンジンで，知識ベースを格納する作業用記憶域，推論規則を格納する記憶域，を持ち，複雑な問題を対話的に解くシステムに応用された．エキスパートシステムなどはプロダクションシステムを利用した応用例の一つである． ¿ 知識工学とオントロジエージェントシステムにとって，推論やプラニング，意志決定を効果的に行うには知識のデータベースが必要である．論理は背景となる知識を記述する手法としての役割であったが，記述された知識を取り扱う枠組みや理論も必要である． ¿º½ オントロジオントロジとは，かなり抽象的な概念で，文脈によってはかなり広範囲の意味を包含する言葉である ½ ．例えば ¯ 対象とする世界に存在する事象を体系的に分類し，その関係を記述するもの． ¯ 階層関係，部分全体関係，クラスとインスタンス，デフォルト知識等を表現可能．などの定義，性質がある．近年は，Ë Ñ ÒØ のÏ Ï というキーワードとともに注目されている ¾ ．Ë Ñ ÒØ Ï とは，テキストベースの情報源を活かし，その中に含まれている意味の構造を抽出して，膨大な量の意味情報のオントロジを自動生成するというプロジェクトである． ¿º¾ ニュース記事より抜粋「特殊な符号によって、どれが気温かをコンピュータに教える。さらに、そこで使われている『気温』という言葉のニュアンスまで、わかるようにする」。かつて ÏÏÏ（ÏÓÖÐ Ï ズリー氏は、¾¼¼¼ 年 ½¾ 月 ½¿ 日号の Æ Û×Û Ë Ñ ÒØ Ï Ï ）の生みの親ティム・バーナー」をこのように表現した。では現在、の研究はどこまで進んでいるのだろうか。 ÅÄ コンソーシアムは ¿ 月として Ë Ñ ÒØ 日本版で「Ë Ñ ÒØ Ï Ï 日、「第回 ÅÄ コンソーシアムを取り上げ「セマンティック Ï Ý×」を開催、最新動向のトピックの ½ つの動向とメタデータ」とする発表を行った。発表を行っ Anything AbstractObjects Sets Numbers Categories Events RepresentationalObjects Sentences Measurements Times Intervals Places Moments Weights PhysicalObjects Processes Things Stuff Animals Agents Solid Liquid Gas Humans 図 ¾ 一般世界のトップレベルのオントロジ．枝は部分集合の関係を示している．たジャストシステムの野村直之氏は、Ë Ñ ÒØ Ï の活用のためのステップとして「メタデータ、オントロジ、知的エージェントという ¿ つの“ 技術 ”を順番に実用化し、アプリケーションに組み込みながら活用していく」道を示した。そもそも、メタデータとは何か。バーナーズリー氏の言葉と合わせて考えれば、記述される情報の意味（Ë ¹ Ñ ÒØ ×）を指し示す。つまり、ÏÏÏ 上に散在するさまざまな個々の情報に意味を付与し、その情報が“ なにもの ”かを明確にするデータこそがメタデータである。そして、従来（今でも）情報の意味を人間が判断していた状況を、メタデータの存在によってコンピュータが理解できるようにする仕組みが Ë Ñ ÒØ ティム・バーナーズリー氏が描く Ë Ñ ÒØ り巻く世界から巻き起こっている。Ë Ñ ÒØ しており、Ï¿ が策定する Ê ×ÓÙÖ ÅÄ る × Ö ÔØ ÓÒ である。の構造（クリックすると拡大）実際的な動きは、 ÅÄ を取では個々のメタデータではなく、メタデータの記述形式を規定 ÓÖÑ Ø（Ê ）が、¾ つのリソース（情報）間の関係を定義す言語として標準的な位置を占めている。ただし、「かなりローレベルの規定言語であるため、情報流通の現場で活用するには ÊËË（Ê Ë Ð Ï Ï Ï Ë Ø ËÙÑÑ ÖÝ ÓÖ Ê Ø ÓÒ）、È¿È（ÈÐ Ø ÓÖÑ ÓÖ ÈÖ Ú Ý ÈÖ Ö Ò 用化を図ろうとする。ここで言うローレベルとは、Ê り、例えば Ê Ë Ø ËÙÑÑ ÖÝ）や ÈÁ Ë（ÈÐ Ø ÓÖÑ ÓÖ ÁÒØ ÖÒ Ø × ÈÖÓ ÓÒØ ÒØ Ø）などの応用言語を上位レイヤに組み込むことで、実があくまでリソース間の関係を定義するだけの言語であの記述そのものを完全に信頼できるかどうかは別の問題なのである。そのために、上位レイヤとして個人のプライバシー情報伝達のための枠組みである È¿È や有害コンテンツのフィルタリングを行うメタデータをページに付与する ÈÁ Ë を介することで、セキュリティを高め実用に耐える仕組みを構築しようとする。さらに、メタデータの構造自体を定義するレイヤとしてのオントロジを記述する言語として、最近は「Ï ÇÒØÓÐÓ Ý Ä Ò Ù （ÇÏÄ）」が注目されている。ÇÏÄ は、Ê 付けの仕組みを用いて Ï やÊ ¹Ë（Ê ¹Ë Ñ ）のリソースの位置上の分類体系（クラス）やその間の関係、さらにそれらの推論ルール群（定理や公理）を記述する言語である。オントロジ定義による知識の相互運用が可能になって初めて、その次のレイヤであるエージェント（人やデータベース）が「動き回って仕事ができるようになる」（野村氏）という。 ØØÔ »»ÛÛÛº ØÑ Ö ¿º¿ Øº Óº Ô»Ò Û×»¾¼¼¿¼¿»¼ »ÜÑÐ ÓÒ×º ØÑÐ よりプロジェクトこのようなオントロジの生成の有名な例として，Ä Ò Ø らによるプロジェクト ¿ がある．プロジェクトは数年に渡る新聞記事をシステムに入力し，その中に存在する単語の意味関係を記述するというプロジェクトで，½ 年からスタートし，力ずくながら成果を出している．たとえば幸せそうな絵が欲しいと質問すると，女の子と遊ぶお父さんの写真が出力されたりする．しかしながら数人のスタッフが，概念間の関係を議論しながら付け加えるという戦略はあまり効率の良いものではなく，ボトムアップに自動的にオントロジを生成できた方が良いという近年の流れに飲み込まれつつある． Ý ÈÖÓ 部分）は Ø は元々は大規模知識ベースを構築することが目的であったが，その成果のうち，上位部分（抽象的オントロジーとしてフリーではないが，プロジェクトのページから ÏÏÏ で入手可能である．現在約 ¿¼¼¼ 個の用語が含まれている． ¿º 意味ネットワーク冒頭で解説したオントロジと似た概念で，概念の意味を他の概念との関連によって定義する際に使われる．概念を含むノード，関係を示す自然言語ラベルのリンクからなるグラフデータ構造が使われている．関係は一般的には一階述語論理で記述され，親子関係などの述語関係で結ばれる．特に，で結ばれたものを，「 ×¹ 」「という階層関係や， t se Birds Animals Mammals Animals bs et Su b Rel(Alive,Animals,T) Rel(Flies,Animals,F) T F Su Birds Mammals Legs: 2 Flies: T Legs: Rel(Flies,Birds,T) Rel(Legs,Birds,2) Rel(Legs,Mammals,4) 4 Su Subset Penguins Penguins Birds Cats Mammals Bats Mammals Rel(Flies,Penguins,F) Rel(Legs,Bats,2) Rel(Flies,Bats,T) bs et Cats Bats Legs: Flies: F 2 T Opus Penguins Bill Cats Pat Bats Member Member Flies: Opus Bill Name: Opus Friend: Name: Bill Friend: (a) A frame−based knowledge base Name(Opus,"Opus") Name(Bill,"Bill") Friend(Opus,Bill) Friend(Bill,Opus) Name(Pat,"Pat") Pat Name: Pat (b) Translation into first−order logic 図 ¿ フレームに基づくネットワークと，一階述語による翻訳 Link Type Semantics Example A Subset ;! B A Member B ;! R B A ;! A B A2B R(A, B) Cats Mammals Bill 2 Cats Age Bill ;! 12 R B A ;! A ;! B R 図 × ×¹Ô ÖØ」などと呼び，意味ネットワークの基本的な関係記述となっている． Animals Alive: Flies: Subset Ô ÖØ Member × × 8 x x 2 A ) R(x, B) 8 x 9 y x 2 A ) y 2 B ^ R(x, y) Legs 2 ;! Birds Parent ;! Birds Birds 意味ネットワークにおけるリンクの型とその意味レポート課題以下の設問の中から２問を選択し，電子メールで回答せよ．レポートは Ô は Ò ÑÙÖ × ºØºÙ¹ØÓ ÝÓº º Ô で，電子メールの題名を「 ÒØËÝ×Ø Ñ ファイルにて提出すること．宛先 ½ ÜÜÜÜÜ」とすること．ÜÜÜÜÜ の部分は自分の学籍番号を記入すること．〆切は１１月１１日． ½º 宣教師と人食い人種問題を実装して，最短の解を見つけるために幅優先探索を用いよ．繰り返し現れる状態をチェックすることは良い考えであるか？決定の助けとするために完全な状態空間の図を描け．宣教師と人食い人種問題：宣教師３人と人食い人種３人が川を渡ろうとしている．船の最大定員は２名であり，何度か船を往復をして全員が渡る必要がある．ただし一方の岸で人食い人種の人数が宣教師の人数よりも多くなると宣教師は食べられてしまう．全員が無事に渡河する方法を考える問題． ¾º ÆÈ 完全問題，ÆÈ 困難問題は具体的にはどのような問題が例として挙げられるか？また，どのくらいの種類の存在が知られているのかを調べよ．また，それらの問題の複雑さを計算量の観点から検討し，説明せよ． ¿º クロスワードパズルを作ることを考える．長方形の格子に単語を埋めていくものである．格子は問題の一部として与えられ，どのますが黒でどのますが白かは特定されている．単語（例えば Ø ÓÒ ÖÝ）のリストが与えられ，このリストの何らかの部分集合を用いて白いますを埋めることが仕事だと仮定しよう．この領域における完全なゴールと問題の定式化を与え，それを解くための探索戦略を選べ．必要ならばヒューリスティック関数も決めよ． º ある駅から目的の駅までの経路を探索するシステムを作成したい．経費を最小にしたいという顧客，最短の時間で到達したいという顧客．乗り換えのために歩く距離を最小限にしたいという顧客．乗り換えの回数を最小限にしたいと顧客．これらの全てに対応するためのデータ構造または状態空間は，どのように構成するのが適切か．また探索戦略はどのようなものを採用するべきか．検討せよ． º ÁÅ のウェブページ ØØÔ »» Ñ º ×º Ö Ð Ýº Ù»から，サンプルのソフトウェア群をダウンロードし，実行環境を構築せよ．サンプルプログラムを参考にして，ハノイの塔の問題を解くプログラムを構築せよ．プログラムを実行した際には，探索に必要となった空間計算量やコストなどを表示するようにして，問題の複雑さ Ò が増加するとともに計算量がどのように増加するかを調べよ． º 「私には，兄弟，姉妹はいませんが，あの男の父は私の父の息子です．」という有名な謎解きクイズがある．「あの男」が誰なのかを，一階述語論理と推論規則を用いて解け．参考文献 ½ 武田英明º 私のブックマーク：オントロジーº ØØÔ »»ÛÛÛº ¹ ¾ セマンチック Û ¿ ÓÙ Ð × ガイドº º Ä Ò Øº Ý ØØÔ »»ÛÛÛº Ð Ö ¹× ÎÓÐº ¿ ¸ ÆÓº ½½¸ ÔÔº ¿¿ß¿ ¸ ÆÓÚ ½ Ý ÔÖÓ Ø Û Ô º Ð Ô º Ô»¼ » ÒÚ ×ØÑ ÒØ Ò ºÓÖº Ô» × » ÓÙÖÒ Ð»ÑÝ ÓÓ Ñ Ö »½ ¹ º ØÑÐº «Ù× Ò Û» Ù ÒÓÛÐ Ò Ö ×ØÖÙ ØÙÖ º º ØØÔ »»ÛÛÛº Ý º ÓÑ» Ý ¹¾¹½» Ò »× Ñ ÒØ ¹Û Üº ØÑÐº º ØÑÐº ÓÑÑÙÒ Ø ÓÒ× Ó Ø Å¸