人工知能入門

Size: px

Start display at page:

Download "人工知能入門"

とよみしげい
5 years ago
Views:

1 藤田悟黄潤和

2 宣言的知識 is-a 型 has-a 型論理式を用いた表現命題論理式述語論理式意味ネットワークフレーム手続的知識プロダクションルール ( システム ) 文脈知識スクリプト

3 推論とは 3 種類の推論知識表現との対比前向き推論後ろ向き推論

5 持っている知識から結論を導き出す持っている知識から新しいことを考えるデータベースそのものは大量の知識を保管するが推論能力を持たないデータマイニングと組み合わせると大量のデータから新しい事実を発見する知識ベースは大量の知識を持ち推論能力を合わせ持つ

6 空腹である満腹である食堂に行くのどが渇く朝起きる食事をする体が温まるお昼になる歯が汚れる夜になる友と会う腹痛になる

7 知識からの推論空腹である満腹である経験からの推論食堂に行くのどが渇く朝起きるお昼になる食事をする仮説としての推論体が温まる歯が汚れる夜になる友と会う腹痛になる

8 時間があるお金が減るお金がある夏休み旅行に行く気分が変わる楽しい GW 人と出会う年末年始週末発見がある

9 知識からの推論お金がある時間があるお金が減る気分が変わる経験からの推論夏休み GW 旅行に行く仮説としての推論楽しい人と出会う年末年始週末発見がある

10 PC が動かないから推論されることを図示せよ推論を知識からの推論経験からの推論仮説としての推論に分類せよ

11 人間は推論という言葉で様々な異なるタイプの推論を表現している人工知能を実現するにはこれらの差異を十分に理解して推論エンジンを作成する必要がある演繹推論 : 知識から論理的に導く推論帰納推論 : 経験から学習的に導く推論仮説推論 ( アブダクション ): 知識から可能性として推定を行う推論

12 論理式表現された確実な知識から確実な結論を導く推論方法第 2 回第 3 回手続表現された知識を用いて最初に保有した知識から手続を用いて決定的に結論を導く推論方式第 4 回

13 第 2 回資料 1. P: ニワトリは鳥である 2. Q: 鳥は空を飛ぶ 3. R: ニワトリは空を飛ぶ 4. P Q R: ニワトリが鳥でありかつ鳥が空を飛ぶならばニワトリは空を飛ぶここで 1 と 2 と 4 が真であることが知識として与えられているならば R は真になる P Q R P Q P Q R T T T T T T T F T F T F T F T T F F F T F T T F T F T F F T F F T F T F F F F T

14 第 3 回資料親 ( 太郎, 一郎 ) 親 ( 太郎, 桜 ) 親 ( 花子, 一郎 ) 親 ( 花子, 桜 ) 男 ( 太郎 ) 男 ( 一郎 ) 女 ( 花子 ) 女 ( 桜 ) 父 (x, y) 親 (x, y) 男 (x) 娘 (y, x) 親 (x, y) 女 (y) 一郎の父は? 父 (x, 一郎 ) 太郎の娘は? 娘 (x, 太郎 ) 太郎一郎花子桜

15 第 3 回資料父 (x, 一郎 ) 適用 : 父 (x, y) 親 (x, y) 男 (x) 父 (x, 一郎 ) 親 (x, 一郎 ) 男 (x) 親 (x, 一郎 ) 男 (x) 親 (x, 一郎 ) x { 太郎, 花子 } 男 (x) 親 ( 太郎, 一郎 ) 男 ( 太郎 ) 父 ( 太郎, 一郎 ) x = 太郎太郎花子一郎桜

16 第 3 回資料娘 (x, 太郎 ) 適用 : 娘 (y, x) 親 (x, y) 女 (y) 娘 (y, 太郎 ) 親 ( 太郎, y) 女 (y) 親 ( 太郎, x) 女 (x) 親 ( 太郎, x) x { 一郎, 桜 } 女 (x) 親 ( 太郎, 桜 ) 女 ( 桜 ) 娘 ( 桜, 太郎 ) x = 桜太郎花子一郎桜

17 第 4 回資料初期状態ルール検索ルール適用ルール検索ルール適用 <Working Memory> 太郎は朝食を食べていない太郎はラーメンが好きである〇 <Working Memory> 太郎は朝食を食べていない太郎はラーメンが好きである太郎は空腹である〇 <Working Memory> 太郎は朝食を食べていない太郎はラーメンが好きである太郎は空腹である太郎をラーメン屋に誘う < ルール 1> IF (X は朝食を食べていない ) THEN add (X は空腹である )) < ルール 2> IF (X は空腹である ) (X はラーメンが好きである ) THEN add (X をラーメン屋に誘う )

18 第 3 回資料を用いて次の推論過程を説明せよ一郎の母は? ( 既に第 3 回で演習済み ) 桜の兄弟は? 追加する知識母 (x, y) 親 (x, y) 女 (x) 兄弟 (x, y) 親 (z, y) 親 (z, x) (x y)

19 観測されたケースから観測されていないケースを推測するための一般化 ( 学習 ) スズメは鳥であるスズメは空を飛ぶカラスは鳥であるカラスは空を飛ぶカモメは鳥であるカモメは空を飛ぶしかし帰納推論 : 鳥は空を飛ぶダチョウは鳥であるダチョウは空を飛ばない帰納推論の一般化しすぎあるいは例外処理が必要

20 第 1 回資料魚を分類できる条件は何か? 泳ぐヒレを持つ飛ぶ肺を持つ魚であるにしん yes yes no no yes 猫 no no no yes no 鳩 no no yes yes no トビウオ yes yes yes no yes カワウソ yes no no yes no たら yes yes no no yes くじら yes yes no yes no 詳しくは学習の単元で学びます

21 知識が不完全な時に原因や結果の可能性を推論する PC が動かない時たぶん電源が入らないと仮説を立てるしかし電源ランプはついている次に HDD が壊れたと仮説を立てる HDD アクセスランプが消えているそこで仮説が正しそうだと考えるしかし実際はキーボードケーブルが抜けたいただけかもしれない

22 第 2 回資料 1. P: ニワトリは鳥である 2. Q: ニワトリは空を飛ぶ 3. P Q: ニワトリが鳥であるならばニワトリは空を論理式からは飛ぶここで 2と3 ニワトリは鳥であるが真であることが知識として与えられている時に Pは証明できないについて推論せよ P Q P Q P Q P Q P Q P Q しかし仮説推論では T T F F T T T T T F F T F T F F 仮説として取り上げる F T T F F T T T F F T T F F T T

24 現在の状態からゴール向けて様々な可能性を推論していくのがボトムアップ ( データ駆動 ) ゴール状態が成立する条件を1 歩ずつ現在の状態に向けてたどるのがトップダウン ( ゴール駆動 ) ゴール現在の状態探索範囲がどのくらい広がるかで良し悪しが決まる

25 後ろ向き推論札幌に行く羽田に行く羽田 - 千歳の飛行機千歳 - 札幌の移動羽田に行く浜松町に行くモノレールに乗る蒲田に行く京急羽田線に乗る探索範囲が絞られている前向き推論東小金井中央線新宿に行く東小金井中央線立川に行く東小金井中央線八王子に行くとてもゴールにたどり着かない

26 後向き推論将棋に勝つ盤面 G0 盤面 G1 盤面 G そもそもゴール状態が無数にあり推論が始まらない前向き推論現在歩 1を動かす盤面 A1 現在歩 2を動かす盤面 A2 現在飛車をX1に動かす盤面 Ax1 状態数は多いが有限の状態で推論できそう

27 後向き x44 x43 right x43 x42 right x42 x41 right x42 x32 up 前向き x11 right x12 x12 up x22 x12 right x13 x22 left x21 x13 right x14 スタート x41 x42 x43 x44 x31 x32 x33 x34 x21 x22 x23 x24 x11 x12 x13 x14 前向き推論も後ろ向き推論も難しさに変わりはないゴール

28 3x3 の迷路を作って前ページと同じ要領で前向き推論と後ろ向き推論の論理式を完成させよ前向き推論後ろ向き推論の推論手順を示せ

29 Seven inference rules for propositional Logic R(1) Modus Ponens α β, α β R(2) And-Elimination α 1 α 2 α n α i R(3) And-Introduction α 1, α 2,, α n α 1 α 2 α n R(4) Or-Introduction α i α 1 α 2 α n R(5) Double-Negation Elimination α α R(6) Unit Resolution R(7) Unit Resolution α β, β α α β, β γ α γ 30

30 Inferring knowledge using propositional logic Concerning with the 6 squares, [1,1], [2,1], [1,2], [3,1], [2,2], [1,3], there are 12 symbols, S 1,1, S 2,1, S 1,2, B 1,1, B 2,1, B 1,2, W 1,1, W 1,2, W 2,1, W 2,2, W 3,1, W 1,3 The process of finding a wumpus in [1,3] as follows: 1. Apply R 1 to S 1,1, we obtain W 1,1 W 1,2 W 2,1 2. Apply And-Elimination, we obtain W 1,1 W 1,2 W 2,1 3. Apply R 2 and And-Elimination to S 2,1, we obtain W 1,1 W 2,2 W 2,1 W 3,1 α 1 α 2 α n α i α β, β α R 4 : S 1,2 W 1,3 W 1,2 W 2,2 W 1,1 4. Apply R 4 and the unit resolution to S 1,2, we obtain (α is W 1,3 W 1,2 W 2,2 and β is W 1,1 ) W 1,3 W 1,2 W 2,2 5. Apply the unit resolution again, we obtain (α is W 1,3 W 1,2 and β is W 2,2 ) W 1,3 W 1,2 6. Apply the unit resolution again, we obtain (α is W 1,3 and β is W 1,2 ) W 1,3 Here is the answer: the wumpus is in [1,3]. 31

31 The three new inference rules R (8) Universal Elimination: For any sentence α, variable v, and ground term g: v α SUBST({v/g}, α) e. g., x Likes(x, IceCream), we can use the substitute {x/rose} and infer Like(Rose, IceCream). R (9) Existential Elimination: For any sentence α, variable v, and constant symbol k that does not appear elsewhere in the knowledge base: Ground term is a term that contains no variables. key x y x value rose Murderer v α SUBST({v/k}, α) e. g., x Kill(y, Victim), we can infer Kill(Murderer, Victim), as long as Murderer does not appear elsewhere in the knowledge base. R (10) Existential Introduction: For any sentence α, variable v that does not occur in α, and ground term g that does occur in α: e. g., from Likes(Rose, IceCream) we can infer x Likes(x, IceCream). α v SUBST({g/v}, α) 32

32 Example of proof ( 証明 ) Bob is a buffalo 1. Buffalo(Bob) --f1 Pat is a pig 2. Pig(Pat) --f2 Buffaloes run faster than pigs 3. x, y Buffalo(x) Pig(y) Faster(x,y) --r To proof: Bob runs faster than Pat Apply R(3) to f1 And f2 4. Buffalo(Bob) Pig(Pat) --f3 (And-Introduction) Apply R(8) to r1 {x/bob, y/pat} 5. Buffalo(Bob) Pig(Pat) Faster(Bob,Pat) --f4 (Universal-Elimination) Apply R(1) to f3 And f4 6. Faster(Bob,Pat) --f5 (Inplication-Elimination ) 33

33 x, y Buffalo(x) Pig(y) Faster(x,y) Buffalo(Bob) Pig(Pat) (Universal-Elimination) Buffalo(Bob) Pig(Pat) Faster(Bob,Pat) (And-Introduction) Buffalo(Bob) Pig(Pat) α β α Faster(Bob, Pat) 34

34 Backward chaining example Bob is a buffalo 1. Buffalo(Bob) --f1 Pat is a pig 2. Pig(Pat) --f2 Buffaloes run faster than pigs 3. x, y Buffalo(x) Pig(y) Faster(x,y) --r1 Goal: to prove Faster(Bob, Pat) Faster(x, y) r1 Buffalo(x) Pig(y) R(8) Universal Elimination R(2) And Elimination Buffalo(x) Pig(y) {x/bob} {y/pat} R(8) Universal Elimination Buffalo(Bob) {} Pig(Pat) {} 35

35 教科書 p54 演習 1 に回答せよヒント ( 必ずしも下記の例にこだわらない ) 演繹推論は祖父を推論する帰納推論は魚が泳ぐ動物であることを推論するアブダクションは電子機器は電池が切れたら立ち上がらないことを使って立ち上がらない原因を推論する

人工知能入門

人工知能入門藤田悟黄潤和宣言的知識 is-a 型 has-a 型論理式を用いた表現命題論理式述語論理式手続的知識プロダクションルール ( システム ) http://www.amzi.com/expertsystemsinprolog/xsipfrtop.htm 2.1 The Bird Identification System Prolog in JavaScript http://ioctl.org/logic/prolog-latest