キカベン
機械学習でより便利な世の中へ
G検定対策
お問い合わせ
   

第1次AIブーム:探索・推論

thumb image

G検定の項目「人工知能をめぐる動向」はAIの3つのブームにおけるトレンドを解説しています。「人工知能研究の歴史」の内容を深掘りした内容です。

ブーム年代トレンド
第1次AIブーム1950年代後半〜1960年代探索・推論
第2次AIブーム1980年代知識表現
第3次AIブーム2010年〜機械学習・深層学習

たくさんのキーワードが出てくるので、時代に関連させキーワードを暗記します。例えば、オントロジーは第二次ブームの知識表現で使われた、など。

今回は第1次AIブームでトレンドだった探索・推論にフォーカスします。この時代はデータを活用するよりも、アルゴリズムにフォーカスした手法がトレンドでした。

1. 学習目標🔝

第1次ブームで中心的な役割を果たした推論・探索の研究について学ぶ。

  • 迷路(探索木)
  • ハノイの塔
  • ロボットの行動計画
  • ボードゲーム
  • モンテカルロ法

キーワード探索木幅優先探索深さ優先探索、プランニング、STRIPSSHRDLUAlphaGo(アルファ碁)ヒューリスティックな知識、Mini-Max法αβ法ブルートフォース

以下では、探索木、ロボットの行動計画、ボードゲームの3つの観点から第1次AIブームの技術をまとめます。

2. 探索木🔝

探索木を使った行動計画(プランニング)が活用されました。探索木を使うことによってコンピュータで問題を解くことができる利点があります。

2.1. 迷路🔝

例えば、A地点にいるロボットがB地点で他のロボットと合流したいといったケースは探索木で解くことができます。

探索木

探索木では状態(例:A地点に居る)と行動(例:X地点に移動する)があり、行動を選ぶことによって状態が変わります。

探索木を使って正解に辿り着く道を見つけ出す手法は大きく分けて2つあります。

探索手法説明
幅優先探索(Breadth First Search)初期状態から近いところを優先に探索する。
どこまで立ち寄ったのか全て記憶しておく必要があるので
メモリを多く必要とする可能性がある。
最短距離を必ず見つけられる
深さ優先探索(Depth First Search)初期状態から遠くに行けるところまで行く。
行き止まりになったら一つ戻ってまた行けるところまで行ので
メモリが少なくて済む
複数のルートがある場合、最初の解が最短距離とは限らない

以下は、左から右へと探索する順番を幅優先探索と深さ優先探索で表示しました。

ちなみに、幅優先探索と深さ優先探索の両方とも右側を優先して探索することも可能です。

2.2. ハノイの塔🔝

探索木で問題が解決できるのは、状態と行動を場合分けしていくことでいつかはゴールの条件を満たした状態に行き着くという考えが当てはまる場合です。もう一つの有名な例としてハノイの塔があります。

ハノイの塔も全て可能な状態を探索木に当てはめることで解決することができます。繰り返しになりますが、探索木にするとコンピュータで解を見つけられるのがポイントです。これによって人間の試行錯誤が探索木を使ったプログラムになりました。

ハノイの塔では、円盤を一度に一つしか動かせません。また、円盤はより大きい円盤の上にしか乗せられません。この制限を元に全ての状態遷移を探索木にしていきます。

初期状態からは次の二つの状態に遷移可能です。

この二つの状態からまた次の状態へと枝分かれ(場合分け)していきます。これをゴール状態が出るまで繰り返せば探索木の完成になり、幅優先探索か深さ優先探索を使えば解が見つかります。解が複数存在するので幅優先探索を使えば最短の移動手順が割り出せます。

3. ロボットの行動計画🔝

3.1. プランニング🔝

ロボットの行動計画に探索を利用する技術をプランニングと呼びます。ちなみに、公式テキストで登場するお掃除ロボットは書籍「エージェントアプローチ人工知能」(原題:Artificial Intelligence:A Modern Approach)を参考にしているようです。

ロボットは部屋Aと部屋Bを掃除する必要があります。もちろん、ゴミがなければ掃除する必要はありません。

簡単な行動計画としては、ゴミがあったら掃除してなかったら別の部屋へ行くというものです。

状態👀行動👉
部屋Aにいる。ゴミがある。掃除する。
部屋Aにいる。ゴミがない。部屋Bに移動する。
部屋Bにいる。ゴミがある。掃除する。
部屋Bにいる。ゴミがない。部屋Aに移動する。

上記の規則に従って行動すれば両方の部屋が常に掃除されている状態になります。このように、プランニングでは状態、行動、結果などを記述して行動計画を立てます。

3.2. STRIPS🔝

プランニングの研究で有名なものにSTRIPS(Stanford Research Institute Problem Solver)があり、以下の情報を記述して目標を達成するための行動計画を立てます。

  • 初期状態(例:部屋Aにいる。そしてゴミがある)
  • 目標状態(例:全ての部屋にゴミがない)
  • 行動(例:掃除する。部屋を移動する)

また、行動には以下が含まれる:

  • 事前条件(例:掃除する条件はゴミがあること)
  • 効果・事後条件(例:掃除をするとゴミがなくなる)

3.3. SHRDLU🔝

SHRDLUは人工知能研究初期の研究開発プロジェクト。1968年から1970年にかけて、テリー・ウィノグラード(スタンフォード大学の計算機科学者)によって実施された。コンピュータに英語で指示を出すと、物体を動かしてくれるもので質問にも答えられる。

引用元:SHRDLU

上図左の画像はオリジナルの「積み木の世界」の映像で、右は後にカラー化されたものです。

自然言語を使って「積み木の世界」にあるブロック、円錐、球体を積み上げたり下ろしたりできる。以下にSHRDLUのサイトから引用します。(日本語訳は私がつけました)

発言者発言内容日本語訳
PersonPICK UP A BIG RED BLOCK.大きな赤いブロックを持ち上げて
ComputerOK.(does it)OK(持ち上げる)
PersonGRASP THE PYRAMIDピラミッドをつかんで
ComputerI DON’T UNDERSTAND WHICH PYRAMID YOU MEANどのピラミッドのことですか?
PersonFIND A BLOCK WHICH IS TALLER THAN THE ONE YOU ARE HOLDING AND PUT IT INTO THE BOX君が持っているブロックよりも背が高いブロックを見つけて、それを箱に入れて
ComputerBY “IT”, I ASSUME YOU MEAN THE BLOCK WHICH IS TALLER THAN THE ONE I AM HOLDING
OK. (does it)
「それ」とは私が持っているブロックよりも背が高いブロックのことですね。
OK(実行する)
PersonWHAT DOES THE BOX CONTAIN?箱には何が入っている?
ComputerTHE BLUE PYRAMID AND THE BLUE BLOCK青いピラミッドと青いブロックです。
PersonWHAT IS THE PYRAMID SUPPORTED BY?ピラミッドを支えているものは何?
ComputerTHE BOX箱です。
PersonHOW MANY BLOCKS ARE NOT IN THE BOX?箱に入っていないブロックはいくつある?
ComputerFOUR OF THEM4つです。

ウィノグラードは、ラリー・ペイジを1995年より指導していました。ラリー・ペイジは当時ウェブ検索を含む研究計画に参加していたスタンフォード大学の博士課程の学生でしたが、1998年に休学し「グーグル」 (Google) の共同設立者となりました。2002年には、なんとウィノグラードもサバティカル休暇をとってグーグルで客員研究員として過ごし人間とコンピュータの相互関係の理論と実践の交わりについて研究しました。近年は、スタンフォードで人間とコンピュータの相互関係 (Human-Computer Interaction, HCI) の講義とセミナーを担当しているそうです。

ちなみに、SHRDLUという名前は組版鋳造機のキーボードの並びにある意味のないフレーズだそうです。

ここでの成果は第2次AIブームへ引き継がれ、Cyc(サイク)プロジェクトへと発展していきます。

4. ボードゲーム🔝

オセロ、チェス、将棋、囲碁などのボードゲームをコンピュータで解くのにも探索が使われます。

4.1. Mini-Max法🔝

ボードゲームでは二人のプレイヤーが交互に次の手を打つのでMini-Max法によって次の一手を決めることができます。

Mini-Max法の基本は深さ優先探索にボードの状態を評価する関数を組み合わせた手法です。評価関数は人間が決めた何らかの方法で計算した値を出します。この値をスコアと呼び、ボードの状態が有利か不利かの指標となります。

簡単な例で説明します。

架空のゲームで自分(青)の番が来たとします。相手(赤)と交互に打つ手を決めるのですが、青は2手先まで読んで次の一手を決めようとしています。

なお、青も赤も合理的にプレイするので、青は青のスコアを最大化することを目指し、赤は赤のスコアを最大化することを目指します。言い方を変えると、青は青のスコアを最大化し、赤は青のスコアを最小化することを目指します。

上から深さ優先探索で順番に探索し、2段下の左1番目に到着します。そこでスコアを計算します。

2手先までしか読まないので、次は2段下の左2番目の一番下のスコアを計算します。

今度は1段上に戻って、赤がどの手を打つか決めます。赤は青のスコアを最小化するために、スコアが2になる手を選びます。

次に右側の探索をします。2段下の右2番目のスコアを計算します。

次に2段下の右1番目のスコアを計算します。

今度は赤がスコアを最小化するようにスコア1になる手が選びます。

よって青がスコアを最大化するためにスコアが2になる手を次の一手として選択します。

スコアの予測が正しく、自分も相手も合理的に行動すれば上記のようにゲームが展開するはずです。

これがMini-Max法で、終局まで先読むすることができれば勝敗がわかるので最適な次の一手を見つけられます。全ての状態を隈なく調べる方法をブルートフォースと呼びます。

しかし、探索する深さが増すと組み合わせが指数的に増大し天文学的な数になるので、実際には先読みする深さを制限したり(五手先までとか)、無駄な探索を減らすなどの工夫が必要になります。

4.2. αβ法🔝

αβ法はMini-Max法による探索を効率よく行う手法です。探索を続けるのが不要な状態を探索から切り捨てることで無駄を省きます。

先ほどと同じ例で説明します。ただし、2手先より下にもたくさんのレベルがあることを図では明示しておきます。Mini-Max法と同じ手順(深さ優先探索)で2段下の右2番目のスコアが1と出るところまで来ました。

先ほどは、続いて2段下の1番右のスコアを計算しましたが、実はこれは必要ありません。ここでαβが出てきます。

スコアを最大化する側(青)のもつベストの手をαと呼びます。現状、αによるスコアは2です。青はこれより低いスコアの手を選択しません。

スコアを最小化する側(赤)のもつベストの手をβと呼びます。現状、βによるスコアは1です。赤はこれより高いスコアの手を選択しません。

つまり、αのスコアが2でβのスコアが1なので青が右側の手を選ぶことは無く、これ以上探索を続ける必要がないのです。

上記のように、αβ法ではたくさんの探索の手間(コスト)を省くことが可能です。また、αβ法のように経験則からの知識やルールをヒューリスティックと呼びます。

4.3. モンテカルロ法🔝

Mini-Max法やαβ法ではスコアの正確さが重要となります。先読みのレベルが制限されているので、終盤になるまでは勝ち負けがわからず、途中の状態でのボードの評価が正確でないと最善な次の一手を選べません。終局まで遠い場合は特にスコアを正確に予測するのは困難になる傾向があります。

モンテカルロ法では、ある局面からゲームが終了するまでを完全にランダムにシミュレーション(プレイアウト)し勝敗を決めます。このプレイアウトを何度も繰り返すことで、どの次の一手を打つと勝つ割合(確率)が高いのかがわかってきます。

プレイアウトの数が増えるほど、モンテカルロ法はブルートフォースによる全ての組み合わせを隈なく調べる方法に近付くので正確さが増していきます。よって、人間の考えた評価関数より正しい可能性が高くなります。また、終盤になるほどプレイアウトを速くたくさん実行できます。

しかし、囲碁は19×19のマスがあり、プレイアウトの数を十分にするだけの時間がありません。

AlphaGo(アルファ碁)ではこの問題をディープラーニングで解決し人間のプロ棋士に勝利しました。



コメントを残す

メールアドレスは公開されません。