知識を用いる探索 ─ ヒューリスティック探索 ─ (Heuristic Search)

Presentation on theme: "知識を用いる探索 ─ ヒューリスティック探索 ─ (Heuristic Search)"— Presentation transcript:

1 知識を用いる探索 ─ ヒューリスティック探索 ─ (Heuristic Search)
人工知能　探索（3） 先を読んで知的な行動を選択するエージェント 知識を用いる探索 ─ ヒューリスティック探索 ─ (Heuristic Search) 　最良優先探索　 　均一コスト探索 　欲張り探索 　Ａ* 探索 　ヒューリスティック関数について 最良優先探索の具体的な例 　今回は，知識を用いる探索として，最良優先探索という一般的な考え方のアルゴリズムを学び，その具体例として，均一コスト探索，欲張り探索，Ａ* 探索の３つを学ぶ．これらのアルゴリズムにおいては，特定の問題分野に関する「知識」を表現するヒューリスティック関数というものが重要な役割を果たす．

2 復習：一般的探索アルゴリズム 展開する＝子を産む A 未展開ノードは待ち行列に並べる S T Z 必ず先頭から取り除き 展開する F F A
子から親へのポインタ S T Z 必ず先頭から取り除き 展開する F F A O R 戦略に基づいて 適切な位置に挿入 これは前回までの復習． 子 B

3 経路コストの導入 初期状態 O 経路コスト 71 N 87 75 Z 151 I 140 A 92 99 S F V 118 80 最適解 211 T 142 R ゴール 111 97 L P H 　前回は，暗黙に各オペレータのコストは１としていて，あまり気にかけなかったが，今回ではこの図のようにいろいろなコストがある場合を考えよう．初期状態からゴールまでの経路コストが最小の解が最適解である． 70 85 146 U 98 86 101 B M E 75 138 120 90 D C G

4 最良優先探索(best-first search)
待ち行列 A 5 T 7 Z 10 O 15 R 16 コスト関数(cost function) の小さい順になるよう挿入 コスト＞0 B 8 コスト関数の決め方によって いろいろなバリエーションがある １．均一コスト探索 ２．　欲張り探索 ３．　Ａ* 探索 ベストに見えるものを優先的に展開 　今回の基本的な考え方は，最良優先探索(best-first search)というものである． 　事前に，状態から数値に対応させる何らかの関数をコスト関数として用意しておく．コストは正の数とする．0や負のコストは考えない．また，ノード数が無限個あるときに，n番目のノードのコストが1/n などと，限りなく０に近い正のコストは考えないことにする．したがって，簡単のため，すべてのコストは正の整数であると考えておけば間違いない． 　このアルゴリズムでは，未展開の各ノードのコストを計算し，その小さい順に待ち行列に並べる． 　これまでのアルゴリズムと同様に，その先頭ノードを優先的に選んで展開する（子を産む）．つまり，コストが小さいという意味で現時点でベストに見えるノードを優先的に展開する． 　コスト関数の決め方によって，少なくとも，図に示した３つのバリエーションがある．次のスライドから，それらを順に見ていく．

5 １．均一コスト探索(unform cost search)
初期状態からそのノードn までの経路コスト g(n) をコスト関数とする最良優先探索 a 0 初期状態 3 5 b 5 n 8 現在状態 ゴールに向かってのシャープな探索に なっていない g(n) = 5+3 = 8 　１つめのアルゴリズム「均一コスト探索」(uniform cost search)は，初期状態からそのノードn までの経路コスト g(n) をコスト関数とする最良優先探索である．特別な場合として，全オペレータのコスト＝１なら，経路コスト＝ノードの深さとなるので，それを浅い順に展開する幅優先探索と同じ動作となる． 　このアルゴリズムは，ゴールがどのあたりにあるのかということをまったく気にせず，とにかく，これまで進んできた経路のコストが最も小さいものを展開するので，「広く浅く」という感じの探索になりがちで，ゴール目指してシャープに突き進んでいくような動作は望めない． 全オペレータのコスト＝１なら，幅優先探索と同じ動作となる

6 均一コスト探索の実行 経路コスト g(n) の低い順に展開 1 4 1 4 2 1 2 3 3 2 6 7 9 2 7 7 12 5 9 9
オペレータのコスト 経路コスト g(n) の低い順に展開 1 4 経路コスト 1+2=3 1 4 待ち行列 2 1 2 3 3 2 6 7 9 2 7 7 12 5 9 9 　このスライドは均一コスト探索の実行のようすをアニメーションで表現している．ノードを表す円の中の数値はg(n)の値である．未展開のノードのうち，その数値が最も小さいものが選ばれ，展開される． 　その途中で，待ち行列のようすも確認しておこう． IN OUT 経路コスト g(n) の昇順になるように挿入 8

7 展開のために選択したときにゴールと判定する
均一コスト探索の最適性 ただし，オペレータのコストは非負とする S A 1 10 15 1 start goal 5 A B C 5 5 1 5 15 S B G 10 5 15 5 G G 11 10 C 　均一コスト探索は最適性がある．つまり，最初に見つける解は，必ず最適解である． 　そのデモとして簡単な例を見てみよう． 　この例では，最適解は S→B→G で，そのコストは10である． 　アルゴリズムでは，途中でコスト11の解 S→A→G が生成されるが，このノードはまだ展開されないので，アルゴリズムはまだこれがゴールだとは認識しない． 　そのうち， S→B→G が生成され，これがさらに展開される段になって，これがゴールであることに気付き，それを解とする．したがって，最初に見つけた解が最適解になっている． 　一般に，このアルゴリズムに最適性があるのは自明であろう．ゴールの判定は，ノードの展開の直前に行われることがポイントである．経路コストが最小のものから展開するので，最適解のゴールノードより早くに経路コストがもっと大きな他のゴールノードが展開されることはない． 展開のために選択してゴールと判定 展開のために選択したときにゴールと判定する

8 均一コスト探索の性質 最適性(optimality) あり 最適解を最初に見つける
　完全性(completeness) あり 　　解があれば必ず見つける 　時間計算量(time complexity) 　　指数的 ｂd　（ｂ：分枝率，ｄ：解の深さ） 　空間計算量(space complexity) 　　指数的 ｂd 幅優先探索 と同じ 　均一コスト探索の理論的性質をまとめるとこのスライドのようになる．

9 ２．欲張り探索(greedy search)
そのノードnからゴールまでの予想コスト h(n) 　をコスト関数とする最良優先探索 初期状態 現在状態 a 0 b 5 n 8 5 3 h(n) ヒューリスティック関数 ノードからゴールまでの 最短経路コストの見積り これの小さい順に展開 ゴール 　２つめのアルゴリズム「欲張り探索」(greedy search)は，そのノードnからゴールまでの予想コスト h(n) をコスト関数とする最良優先探索である． h(n) は，ノードn からゴールまでの最短経路コストの見積りであり，ヒューリスティック関数と呼ばれている．これは，あくまでもこの問題分野独自に関する知識や経験からの「予想」とか「見積もり」であって，その情報が正確である保証はないことに注意しよう．しかし，まったくのでたらめではないことは期待したい． 　このアルゴリズムは， h(n) の値の小さい順に未展開ノードを展開する．したがって，待ち行列はh(n) の値の小さい順に並べておく． 　さきほどの均一コスト探索とは対照的に，このアルゴリズムはこれまでのコストがどうだったかという過去は一切問わない．とにかく，今後の予想コストh(n) のみに着目し，それが現時点で最小の未展開ノードが最も有望である（ベストに見える）として展開する． 　古い教科書などでは，この欲張り探索のことを最良優先探索と呼んでいることもあるので注意しよう． g

10 ヒューリスティック(heuristic)とは？
語源：　アルキメデスが風呂で浮力の法則を発見したときに叫んだ”Heurika !” （ユーリカ！発見した！） 経験から発見した知識のこと 最悪ケースの性能は必ずしも上げないが，平均的にはたいていの場合はうまくいく手法 　ここで出てきた「ヒューリスティック」という言葉は人工知能（AI)技術にとって，非常に重要な用語である． 　これは，アルキメデスが風呂で浮力の法則を発見したときに叫んだ”Heurika !” （ユーリカ！発見した！）という言葉が語源で，AIでは，経験から発見した知識のことを指している． 　しかし，有り得る可能性のすべてを経験したわけではないので，これは数学的に完全に正しい知識であるという保証はない．しかし，アルゴリズムの性能については，最悪ケースの性能は必ずしも上げないが，平均的にはたいていの場合はうまくいく手法であることが多い． 　AIにはこのようなアルゴリズムが多いのである．理論家が（最悪のケースで）指数関数的な計算量になるので実用的でないとする難しい問題でも，AI研究者はあきらめず，ヒューリスティクスを利用して，たいていの場合には高速に解を見つける技術の開発を目指すのである．

11 ヒューリスティック関数の例：直線距離 374 253 329 h(n) = ｎからゴールまでの直線距離 初期状態 Z A S ゴール T B

12 374 253 178 366 329 193 欲張り探索は最適解を見つける保証がない h の値（直線距離） 99 80 211 97
欲張ってこっちにこだわった （欲張り探索） 374 Z 253 A 178 366 S 99 F しかし多くの場合 うまくいく 80 329 T 211 193 R 97 P 　欲張り探索は最適解を見つける保証がない．この例（アニメーション）がその証拠である．最初に最適解でない方の解を見つけてしまう． 101 最短経路はこちら！ （最適性がない） B

13 欲張り探索は解を見つける保証（完全性）がない
374 Z 253 A 366 S 150 T 不適切なヒューリスティクス 150 　欲張り探索には完全性もない．この図のように，不適切なヒューリスティック関数を与えると，その間違った情報にミスリードされて，際限なく変な方向を探してしまう． T1 B 150 T2

14 欲張り探索の性質 最適性(optimality) なし 最適解を見つける保証がない
　完全性(completeness) なし 　　解を見つけないことがある 　時間計算量(time complexity) 　　ｂｍ　（ｍ：　探索木の最大の深さ） 　空間計算量(space complexity) 　　ｂｍ 深さ優先探索 と同じ 　欲張り探索の性質をまとめるとこのようになる．

15 ３．A* 探索(A* search) g(n) h(n) n 8 ｆ(n) = g(n) + h(n) n 経由の最短経路の見積もりコスト
エイスター 経路全体の予想コスト f(n)=g(n)+h(n) （ただし，h(n)は許容的なヒューリスティック関数） をコスト関数とする最良優先探索 初期状態 n 8 現在状態 5 3 g(n) h(n) ゴール ここまでのコスト ここからの予想コスト 　３つめのアルゴリズム「A*探索」(A* search)は，今回の授業の山場で，かつ，探索アルゴリズムの最も重要なものの１つである．このアルゴリズムは， n 経由の最短経路の見積もりコストを f(n)=g(n)+h(n) で定義し，それをコスト関数とする最良優先探索である．ただし，h(n)は許容的なヒューリスティック関数（次のスライドで定義する）であるものとする． 　g(n) は「ここまでのコスト」という過去の実績を表し，h(n)は「ここからの予想コスト」という将来の見積もりを表している．その和は，初期状態から n を経由してゴールまでの最短経路のコストの見積もりになっている．この値の小さい順に未展開ノードを展開するのがこのアルゴリズムである． ｆ(n) = g(n) + h(n) n 経由の最短経路の見積もりコスト これの小さい順に展開

16 許容的ヒューリスティック(admissible heuristic)
予想最小コスト h(n) ≦ 実際の最小コスト h*(n) を満たすヒューリスティック関数のこと 楽観的(optimistic) ヒューリスティック とも言う 初期状態 A 予想最小コスト h(n) 直線距離 S 253 　A*アルゴリズムでは，ヒューリスティック関数 h(n) が許容的(admissible)であることが要求される．（ヒューリスティクスが許容的と限らないときは，このアルゴリズムはAアルゴリズムと呼ばれる．） 　 h(n) が許容的とは，すべてのノード n について， 　　　　　予想最小コスト h(n) ≦ 実際の最小コスト h*(n) が成り立つことである．つまり，実際よりも小さめにコストを予想するので，楽観的なヒューリスティック とも言う． 　ナビの例では，h(n) をゴールまでの直線距離とすれば，それは許容的なヒューリスティック関数である． ゴール R P 実際の最小コスト h*(n)＝278 B 　ヒューリスティクスが許容的と限らないときは，Aアルゴリズムと呼ぶ．

17 A* 探索の性質 最適性(optimality) あり！ 最初に見つけた解は最適解
　完全性(completeness) あり！ 　　解があれば必ず見つける 　時間計算量(time complexity) 　空間計算量(space complexity) ヒューリスティックの 精度に依存 　 A* 探索の性質はこのようになる． 　最適性と完全性があることは，このあとのスライドで直観的に（やや強引に）納得してもらう． 　計算量はヒューリスティックの精度に依存することも，後のスライドでうすうすわかる．

18 A*が最初に見つける解は最適解 経路コスト h 関数の値 （直線距離） 329 253 374 366 178 193 80 97 101
80 97 101 211 99 75 118 140 A S F R P B T 98 Z O 380 151 160 146 C 138 71 O 526 380 Z 75 449 374 151 A 366 S 366 253 F 140 393 178 118 417 99 80 T 447 329 193 R 211 413 97 P B 98 415 B 450 　これは，A*が最初に見つける解が最適解であることのデモである． 　最適解でない方の経路が先に生成されるが，最終的に，先にゴールと判断されるのは最適解の経路の方であることに注意しよう． 146 101 418 138 C 526 C 615 最適解 160

19 休憩

20 しかし，すべての問題が単調性が成り立つわけではない．
A*探索の振る舞い（１）　単調性 526 探索木に沿ったすべての経路で f のコストは非減少 449 366 393 417 447 413 415 450 418 　先ほどの例題では，探索木に沿ったすべての経路で f のコストは非減少になっている．これを単調性という．すべての問題で単調性が成り立つわけではないが，そうなることが多い．単調性の正式な定義と，その意味合いはつぎのスライドで． 526 615 　しかし，すべての問題が単調性が成り立つわけではない．

21 先へ進んで，情報が得られてくるほど，楽観性が弱くなる
A*探索の振る舞い（２）　単調性の定義 三角不等式に似ている 単調性 　先へ進んで，情報が得られてくるほど，楽観性が弱くなる n h(n) c(n,n') 　任意の n, n' についてここで示した不等式が成立するとき，ヒューリスティック関数 h(n) は単調であるという． 　この不等式を２つめのように変形すればわかるように，これは，先へ進んで，情報が得られてくるほど，楽観性が弱くなるということを表している．つまり，最初は将来についてかなり楽観的だったのが，先へ進んできてみていろいろな情報が見えてくると，現実のきびしさがわかってきて，その楽観性が後退してくるというわけで，我々の人生に通ずるものがある．とほほほほ． ゴール n' h(n')

22 実際には，単調性がなくても，最適性と完全性がある．
A*探索の振る舞い（３）　等高線 A*アルゴリズムは f 値の山を ゴールに向かって，見落としなく （シャープに）単調に登っていく 449 526 f = 366 の等高線 366 393 413 415 417 418 393 417 最適解の等高線 447 413 準最適解 415 　最適性あり！ 　完全性あり！ 　単調性があるときには，A*の振る舞いは f(n) の等高線を低い方から高い方へ地道に引いていく手順として理解できる．そうすると，完全性と最適性が成り立つことが納得できる． 450 526 418 615 　実際には，単調性がなくても，最適性と完全性がある．

23 つねに h(n)=0 とすれば，A*は均一コスト探索と一致する．
最良優先探索の比較 均一コスト 欲張り Ａ* 完全 ○ × 最適 時間 △ 空間 　今回学んだ３つのアルゴリズムに対して，４つの評価尺度を検討した結果を表にまとめておく． 幅優先的 深さ優先的 ヒューリスティクス 次第 　つねに h(n)=0 とすれば，A*は均一コスト探索と一致する．

24 ヒューリスティック関数について ヒューリスティックの優位性 ８パズルのヒューリスティック ヒューリスティック関数の作り方
　ヒューリスティック関数について ヒューリスティックの優位性 ８パズルのヒューリスティック ヒューリスティック関数の作り方 　ヒューリスティック関数について，この３つの点から補足しておく．

25 すべてのノード n において h1(n) ≦ h2(n) ≦ h*(n)
ヒューリスティックの優位性 実際の値 すべてのノード n において h1(n) ≦ h2(n) ≦ h*(n) h2 は h1 より優位 h1 で展開されたノード ⊆ h2 で展開されたノード 　すべてのノード n において 　　　　h1(n) ≦ h2(n) ≦ h*(n)=実際の値 であるとき， h2 は h1 より優位であるという．より精度の良い見積もりということである． 　このとき， ヒューリスティック関数として優位な h2 を用いたA*アルゴリズムによって展開されるノードは，必ず，優位でない h1 を用いたA*アルゴリズムによっても展開される．つまり，優位なヒューリスティック関数を用いた方が，はっきり効率が良いことが理論的に言えるのである．

26 ８パズルのヒューリスティック関数 初期状態 5 4 1 2 3 ゴール 6 1 8 8 4 7 3 2 7 6 5 ２ ＋３ ＋３ ＋２
候補１　h1=ゴールの位置にないタイルの数．上の例では７． 候補２　h2=各タイルのゴール状態までのマンハッタン距離 の和．上の例では１８． 　 ８パズルのヒューリスティック関数として，このスライドで示す２つが良く知られている．明らかに，双方とも許容的（楽観的）で，さらに，h2 は h1 より優位である． ２ ＋３ ＋３ ＋２ ＋４ ＋２ ＋０ ＋２ ＝１８ ■どちらも許容的（楽観的）　　■h2はh1より優位．

27 ８パズルの実験結果 解の長さ 展開した平均ノード数 反復深化 A*(h1) A*(h2) 2 10 6 4 112 13 12 680 20 18 8 6384 39 25 47127 93 364404 227 73 14 539 113 16 1301 211 3056 363 7276 676 22 18094 1219 24 39135 1641 　 ８パズルの実験結果である．初期状態によって最適解の長さが違うので別々にデータを整理してある． 　前回学んだ反復深化探索（知識を用いない探索で，前回学んだ範囲ではベストだったもの）よりも，知識 h1 を用いたA*探索が効率が良い．さらに，h1よりも優位なヒューリステッィク h2 を用いるとさらに効率が改善されることがわかる．

28 弱条件問題 緩和問題 (relaxed problem)
ヒューリスティック関数の作り方（１） 弱条件問題 緩和問題 (relaxed problem) ＝ オペレータに対する制限を減らして 　　解きやすくした問題 ８パズルの場合： となりにタイルが置いてあってもそこに動かせる 　ヒューリスティック関数は，経験あるいは「発見」によって見つけるものなのだが，それを見つけるおよそのガイドラインはある． 　それは，弱条件問題あるいは緩和問題と呼ばれるものを利用することである．弱条件問題とは，オペレータに対する制限を減らして解きやすくした問題のことである．この問題の正確な解のコストが元の問題の良いヒューリスティクスになっていることが多い．弱条件問題はもとの問題より解を得やすいのだから，「楽観的」な解が得られるからである． 　弱条件問題の正確な解のコストが元の問題の 良いヒューリスティクスになっていることが多い

29 ヒューリスティック関数の作り方（２） → h2 → h1 → 弱条件問題の自動生成 relax AからBへタイル を動かせる AがBのとなり
＆ Bが空 relax h2 AからBへタイル を動かせる → AがBのとなり h1 　これは，８パズルのヒューリスティック関数を，弱条件問題を利用して自動生成する考え方を示している． 　いずれも，重要な制限のうちの１つをはずして弱条件問題を生成し，その解をヒューリスティック関数の値としている． AからBへタイル を動かせる → Bが空

30 h1,h2,…,hm という許容的ヒューリスティクスがあり， どれも他の優位にないとき，どれを選ぶか？
ヒューリスティック関数の作り方（３） h1,h2,…,hm という許容的ヒューリスティクスがあり， どれも他の優位にないとき，どれを選ぶか？ h(n) = max (h1(n), h2(n), …, hm(n) ) 　互いに他よりも優位でないヒューリスティック関数が複数あれば，それらの最大値を求める関数をヒューリスティック関数とすれば，これは一つひとつのどのヒューリスティック関数よりも優位である． ■ ｈは一つひとつの関数より優位

31 許容性の保証はなくなるが 平均的に効率が向上する
ヒューリスティック関数の作り方（４） 統計情報の利用 h2(n)=14 → 90%の確率で実際の距離＝18 許容性の保証はなくなるが 平均的に効率が向上する h(n)=18 　統計情報を利用して，経験を補強して，より精度の高いヒューリスティック関数を作れば，平均的に効率が向上する．しかし，許容的でなくなるので，完全性と最適性は保証されない．

32 ヒューリスティック関数の作り方（５） 状態の「特徴」の利用 将棋の例 h(n)=α×駒の得点の差 ＋β×駒の働きの差 ＋γ×玉の囲いの差
　この将棋の例のように，その問題特有の状態の特徴からヒューリスティック関数をモデル化することも多い． 　未知パラメータを含むモデルを作っておき，AIならではの「学習」という機能で，パラメータの値を動的に改善していく方法もある． α β γ：学習アルゴリズムで値を調整する