シリーズAI入門：5. 第1次AIブーム 探索

第1次AIブームにおける話題，特に探索について眺めます。

Transcript

1. 第1次AIブーム シリーズAI入門 探索 © FSCjJh3NeB 2021 (※ 但し画像を除く)
2. 最初期の人工知能研究者が考えたこと n 知能とは…おそらく “記号処理” に本質がある n コンピュータは “数” という記号を処理して計算 n コンピュータで，知能を実現できるのでは！？ 2 ※ 論理回路の塊で，論理演算できる。
3. 記号処理に知能の本質？？？ n 記号処理 ＝ 論理的な演算 u 例： ソクラテスは人，人は死ぬ，ソクラテスは死ぬ n なんで？ u なぜ，記号処理が知能の本質だと考えたのか？？ u 例えば… p 人間が高度な知能を持つとして，その他の動物との違いは？ • 言葉をもっている！！！言葉をしゃべれてエライ！ • 言葉＝記号 u いろいろな実体を記号（概念）に変換して， 操作できる能力，それこそが知能なのでは？ 3 すごーい
4. ヨハネによる福音書 n 例によって，おそらくはキリスト教文化の影響も n ヨハネによる福音（冒頭） u 日本語では ”はじめに言葉ありき” と訳される p Logos = 神の言葉，真実，真理，論理，理性，概念 神様（ヤハウェ）が そう言うんなら，間違いない！ ※ 著者は別に，キリスト（ユダヤとかイスラムなども含む）教徒 ではないです 4
5. 鳥の視点 と 虫の視点 n 前掲の宗教的・文化的背景は，問題の捉え方に影響 u 一神教的な世界観では，神はすべてを見渡せる u 東洋的な世界観では，様々な視点が混合する p 当然，どちらが優れているという話ではない。優劣は場合による。 u 人工知能についても，神の視点（鳥の視点）から見て 構築するか，虫の視点（環境内部）から見て構築するか というので，アプローチが全く異なる可能性 環境を外から眺める 神・鳥の視点 環境を内部から眺める 虫の視点 5
6. 物理記号仮説（記号主義） n すべての知的作業の本質は記号操作にある …という作業仮説，記号主義とも呼ばれる u 色や形などの物理量はうわべのものであって， それらを捨象し，カテゴリー化した後の記号が本質 u この記号操作によって，高度な知的処理が可能！ 作業仮説 ： 本当かどうかは知らんが，その検証のためにも，とりあえず仮に そうだとして・考えて，やってみよう…という，暫定的な仮説 …っていう気がする。多分そう。 6
7. コンピュータで記号処理？ n コンピュータは AND，OR，NOT を組合わせて処理 u 論理的な処理がいろいろできる装置 u 知能が記号の論理的処理だとすると， この論理的な処理ができる機械で当然，模倣できる u まぁすぐに人間同等は無理でも，チェスみたいに， 完全に論理的に話が進むところならすぐできるハズ！ 7 ここから下は，当時の研究者が考えたであろう事
8. 記号接地問題 n 体を持たないAIにリンゴは理解できるか？ u 概念（記号）としてのリンゴが理解できたとして， 目も耳もないAIは，真にリンゴを知っているといえるか • …でも，そもそも「真のリンゴ」とは…リンゴのイデアって何？ n 人間は様々な情報をうまく抽象化（記号化）して 処理をしている n 抽象化された情報と，実体を対応づけること ＝記号接地 8 将来補足
9. 推論 n 知識を元に新しい結論を得ること n 三段論法も推論 u 知識1： 人間は死ぬ u 知識2： ソクラテスは人間である u 結論 ： 知識1＆2 → ソクラテスは死ぬ n 論理学は推論のための基礎 u AならばB，AかつBならばC…のような演算規則 u これを用いて，知識を操作していくと推論できる 操作自体は，後述する探索とほぼ同じ 9
10. 推論の種類 n 推論にも種類が u 演繹（De-duction）← 記号処理系はこれ p 既存の知識・ルールを組み合わせて行って結論を得る u 帰納（In-duction） ← 機械学習系はこれ p 観測された事実や事例をまとめ上げていって結論を得る u アブダクション（Ab-duction） p 仮説形成とも。観測された事象を説明する仮の理論を考える 10 環境・外部 内部 Deduction 内から外へ Abduction 外から内へ Induction ぐるぐる かけ算・⾜し算 のイメージ 公約数・因数分解 のイメージ
11. どのようにすれば推論できるか？ n 例えば現在であれば，プログラミング言語の Prolog などを 用いて，記号処理ができるが… n 1950年代の計算機は，基本的に電卓の状態 u 単純な問題であれば，“こうなったらこう” という状態を あらかじめ書き下すことはできる p オセロであれば，そもそも石を置ける場所は限られる p この状態の時，ココに石を置くと，相手はココに置ける …も，あらかじめ分かる u であれば，推論そのものが難しくても，状態を書いておいて， その中から適切なモノを選び取らせれば，行動は模倣できる p いつか，状態そのものの演算（推論）ができるとして，結局，あり得る状態から 適切なモノを選び取る…という行動は必要になる 11 推論そのものと並んで，探索も主要なテーマとして扱われた
12. 探索 Start Goal 12
13. 探索 Start Goal A C D G B E H F 13
14. 探索 Start Goal A C D G B E H F 14
15. 木構造(Tree) : 2分木 binary-tree root A C F K B G L J M D I E H Node Edge 終端のNodeはLeafともいう root ひっくり返すと木のように見えるので， Tree（木，木構造）と言う名前 情報工学における基礎的かつ 重要なデータ構造の一つ AI分野でも多用される 線でつながっている上のNodeを親， 下のNodeを子という。 ここでは2分木のみを示したが，子が2人以上のものや， トライ木，赤黒木など，様々なタイプの木構造が存在 15
16. 探索：幅優先探索 Start Goal A C D G B E H F > 親は一人なので，Goalを見つけたら， 親をたどっていけば正解がわかる 16
17. 探索：深さ優先探索 Start Goal A C D G B E H F > 親は一人なので，Goalを見つけたら， 親をたどっていけば正解がわかる 17
18. 探索 ハノイの塔 小さな円盤の上には，大きな円盤はおけない 逆の棒にすべての円盤を移したい 18
19. 探索 19
20. 探索 20
21. 探索 21
22. 探索 22
23. 探索 23
24. 探索 24
25. 探索 25
26. （小，中，大 ） P Q R （ P，P，P ） 26
27. （小，中，大 ） P Q R （ P，Q，Q ） 27
28. 探索 P,P,P Q,P,P R,P,P Q,R,P R,Q,P R,R,P Q,Q,P R,R,Q Q,Q,R P,R,Q P,Q,Q Q,Q,Q P,Q,R P,R,R R,R,R Q,R,Q Q,P,Q R,P,Q R,Q,Q R,Q,Q P,R,P P,Q,P R,Q,R R,P,R P,P,R Q,P,R Q,R,R 循環グラフであるため， 木構造の探索はそのまま使えない 28
29. グラフ A B F C D E G Node と Edge の集合で表現できるデータ構造 無向グラフと有向グラフ，循環路の有無で扱いがことなる 要素間の関係性や，状態遷移の表現に用いる．“グラフ理論”や“ネットワーク解析”などで扱う A B F C D E G 無向グラフ 有向グラフ 最短経路の探索などにはこのグラフ表現を用いる 著名な最短経路の探索手法は ダイクストラ法 29
30. このどこが知能なのか？？ n 一つには歴史的背景 u 探索問題は AI 研究の初期課題 p ENIAC 誕生は1946年頃 p AI という言葉ができたのは1956年 • 探索がブームになったのは1950年代〜70年代 u コンピュータは，いまの電卓に当たるイメージ p 弾道計算など，四則演算を高速に行うことがメイン p そうした視点に立った場合，こうした問題を自動的に解く… ということも，十分に先進的で知的なタスクだった 30
31. このどこが知能なのか？？ n 人間も似たような行動をとる …こともある u 将棋などゲームの定石 u スポーツにおける戦略 u 格闘技（主に武道）における型 p “こう来たらこうする”という一連の遷移パタンについて， 反復練習することで無意識的に出せるようにする p その分の演算リソースを先読みを含めた対応策に割ける 31
32. このどこが知能なのか？？ n 単純なロボット的なものも作成できる u 例えばお掃除ロボットを考えると… p この位置はすでに通過したか？ p 前方に進むことができるか？ など，いくつかの条件の組み合わせで実現できる 32
33. 単純な探索の限界 n オセロや将棋も探索で解けるのではないか？ u と，考えるのは自然な流れではある u が，実際には難しかった… なぜか？ 組み合わせが爆発するから 円盤3枚のハノイの塔でも状態は27通り 64枚だと最短の遷移だけに絞っても… 264 通り = 18,446,744,073,709,551,616 通り = 1844京6744兆737億955万1616 通り ゲームでは相手の動作もあるので， 先読みしつつベストな手を探す必要…だが， 探索するのに莫大な時間が… 33
34. ボードゲームの複雑さ n オセロ ： 10^30 10^60 n チェス ： 10^50 10^120 n 将棋 ： 10^70 10^220 n 囲碁 ： 10^160 10^360 盤面の数 探索木 盤面の広さ，駒の数，動きの種類，とった駒を再投入できるか？などで変化 囲碁は石（駒）の数が多く，配置自由度も高い上，盤面も広いので難しい ※ 宇宙にある水素原子の数は 10^80 個と見積もられている 34
35. 数え上げの困難さ：組み合わせ爆発 n 単純な経路探索は なかなか大変… u どのくらい大変か， ちょっと見てみましょう u パタンの組み合わせは 容易に爆発！！！ u ただの紙も 42回 折ると 月に届く厚さになる… https://www.youtube.com/watch?v=Q4gTV4r0zRs 35
36. 数年前，囲碁とAIが話題になったような…？ n いくつかのブレイクスルーを経て，最近ようやく この問題を解決できるようになったと言うこと u 取り得る状態を列挙して，有利そうな手を取るのは同じ u すべて列挙するわけではなくて，良い感じの手… というのを学習することで，全探索を回避する ここではいったんここまで 詳細は別の回で説明 36
37. トイ・プロブレム n 初期のAI研究においては，迷路やハノイの塔など ごく単純化された条件下での問題を扱った n 単純化された問題 = トイ・プロブレム u いきなり複雑な条件は扱えないので， 簡単な例から考えていくのは，問題を解く上での定石 u しかし，初期のAIはこの段階を超えることができず， “知能”の難しさ，複雑さが明らかとなった Toy:おもちゃ 37
38. トイ・プロブレムの成功例 n トイ・プロブレム とはいえ，成果を上げたものも u STRIPS （ Stanford Research Institute Problem Solver ） p 前提，行動，結果 という3要素で 仮想ロボットの動作を実現 • ロボットが自動的に動作計画を立てることを“プランニング”という p 仮想ではあるが，いろいろな動作を実現できた u 積み木の世界 SHRDLU（シュルドゥル） p 仮想空間上に配置された 積み木 を操作させることができた • 人「ブロックの上に，四角錐はおけるか？」，AI「Yes」 • 人「四角錐の上に，四角錐はおけるか？」，AI「No」 …といった対話形式で，積み木を操作させたり説明させられた ＝ 対話的にAIにプランニングを実行させることができた 38
39. SHRDLU と Google n SHRDLE の 開発者 u SHRDLE を 開発したのは スタンフォード大学の テリー・ウィノグラード 博士 u この ウィノグラード博士 の 教え子 ラリー・ペイジ が 後に Google を創業することになる 39
40. まとめ n 初期のAI研究では推論・探索などに注目があった u 具体課題：迷路やハノイの塔，積み木など u 探索木などを用い望ましい状態への遷移を探索 p 遷移のパタンを自動で組み立てること＝プランニング u トイプロブレムは解けたが，少し複雑になると破綻 p チェスや将棋，囲碁は解けなかった… • 組み合わせ爆発に伴う計算量の増加に対応できなかった 40
41. 同時代の関連研究 n 自動翻訳も最初期に取り組まれたものの一つ n 精密な文法書と，辞書さえあれば簡単にできそう u 多義語の存在や，構文解析の複数解釈可能性… p 核： 原子核？ 細胞核？ 核心的利益？ 議論の核？ p 黒い目の大きな女の子 • 目が大きくて黒い女性 の 子供 • 目が黒くて 体が大きな 女の子 • 黒目の部分が大きい女性 の 子供 • 体の大きな女性 の 黒い目をした子供 • etc. 41
42. 明らかになった課題 n 限定された環境下では， 単純な探索でもそれなりに問題を解くことができる n 少し複雑になってくると計算量の問題から， うまくは機能しなくなってくる u そもそも複雑な問題を扱えてこその知能なのでは？ n コンピューターが極めて高価な時代， できるだけ実用上の問題を解きたい…！！！ 42
43. トイプロブレムは知能の本質を捉えられない？ n 捉えられない面も多分にありそうだが， 逆に，本質を捉えやすくする部分もありそう ドア 衝立 窓 ハエの閉じ込め ランダムに動けば出られるが 明るい窓の方へ移動するので， 閉じ込められてしまう 走光性 は 条件反射か 知能か？ ランダムよりは知的っぽい 条件反射も知能の一部？ 43
44. 探索における遠回り・外乱の必要性 n 最適な解にたどり着くためには， あえて遠回り（評価値を悪化させること）が必要なことも u どの程度まで，遠回りのコストを許容すれば良いのか？ u どういうときに，遠回りを検討するべき・するのか？ 局所解 局所解 最適解 外乱を与えないと， 最適解にはたどり着けない c.f. 焼きなまし法 網 肉 犬は肉を食べるために 遠回りすることができるか？ 44