【人工知能/G検定】第一次AIブームで注目された「探索・推論」について解説

スポンサーリンク

本記事では、1950年代後半ごろを境に始まり、第1次AIブームで主要な役目を果たした「探索・推論」について解説していきます。

人工知能は、現代において様々な課題を乗り越えて現在のディープラーニングなど最新の技術にたどり着いています。

また、研究としても長年受け継がれてきており、多数の論文が世に出され続けてきました。

これから先、AIの分野で機械学習、特にディープラーニングについて学ぼうとしている人には、最初に学ぶべき要素となってきますので、この機会にしっかり理解していきましょう。

スポンサーリンク

探索木の考え方

迷路の問題

探索・推論について学ぶ上で、まずは、探索木について理解していきましょう。

今回は迷路をケースに取り上げます。分岐や行き止まりの多い下図のような迷路を例にとりました。この迷路のゴールまでの最短ルートをコンピュータが解く問題があったとします。

【迷路の問題】

このままでは、コンピュータが迷路の解き方を理解できないので、分岐があるところや行き止まりに目印(アルファベット)を入れ、それぞれを線で結びます。

そうすると、理解し難い迷路の問題が「木のような構造」となり、以下の図のような構造で表すことができます。このような構造を「探索木」と呼びますが、探索木とはわかりやすく言うと「場合分け」という意味になります。

コンピュータはこうして場合分けされたものから、”最短でゴールにたどり着くルート”という前提条件を基に答えを導き出します。
※今回は、S→A→E→Gが最短ルートであり、正解のルート。

【探索木】

人間がこれを行うと頭の中で全てのパターンを想像したり、紙に書き出す必要がありますが、コンピュータはこうした単純作業が非常に得意なので、人間より早く正確に答えを導くことが可能です。

有名な探索・推論の方法として「幅優先探索」「深さ優先探索」があるので紹介していきます。

幅優先探索

幅優先探索とは、出発点に近いノード順に検索することを指します。

では、図の探索木を例にとり、SからGたどり着くためのルートを検索するとどうなるのでしょうか。

近いところからシラミつぶしに探していくため、必ず最短距離で答えにたどり着くことができる一方、全てのルートを記憶しておく必要性があるため、コンピュータのメモリ(記憶領域)不足に陥ることがあります。

深さ優先探索

深さ優先は、限界まで一つのルートでどこまでたどり着けるのか検索し、最後までたどり着いたら一つ前のノードに戻って再探索をすることです。

再探索となった場合、コンピュータのメモリを開放できますが、最短距離で辿り着けるかは運に左右されてしまいます。

どちらの方法にもメリットデメリットがあるので、ケースに従ってどちらの探索方法を取るかは選択するのが良いでしょう、この2つを組み合わせるような研究もされており、古くから脈々と受け継がれています。

ハノイの塔

問題を探索で解決することに重要なのは、「コンピュータが理解できる形に変換してあげること」です。

例えば、以下の図のように3本のポールがあり、左のポールに穴のあいた大・中・小の円盤を取り付け、同じ並びで右側のポールに移動させるとします。

この場合、小さい円盤の上に大きい円盤を重ねることはできません。

ここでは最短距離を探索するのに、ポールの位置によって円盤をP,Q,Rという形に直すことによって、探索を実現することができます。これはハノイの塔と呼ばれており、世界的に有名なパズルゲームです。

【ハノイの塔】

ロボットの行動計画(プランニング)

他にも探索には、プランニングという手法もあります。これは主にロボットの行動計画を制御するのに使われていたりします。

プランニングは前提条件と行動、結果を記述することで、任意の状態に至る行動計画を立てることができると言われており、この3つの組み合わせはSTRIPS(Stanford Research Institute Problem Solver)と呼ばれています。

【例】
前提条件:部屋1にいる状態
行動:右に移動
結果:部屋2にいる状態

スポンサーリンク

コストの概念

探索は人間ではできない膨大な計算を得意としていますが、それには限界があり、特に将棋や囲碁のようなボードゲームの打ち方を計算し、最適解を導くのは困難であると言われてきました。

しかし、この問題の解決策としてコストという概念が取り入れられることで人工知能はさらなる発展を遂げます。これは「探索に時間がかかりすぎるルートを省略することで、コンピュータの負荷を軽減することができる」という画期的な発想でした。

例えば、ボードゲームでは、盤面がどれだけ自分に有利であるかをスコア化し、自分が打つときには最大化し、相手が打つときに最小化するような使い方をします。これは、Mini-Max法とも呼ばれています。

また、Mini-Max法による探索を極力減らす手法を、αβ法と言います。

自分のターンでコストを最大化するように考えるとき、

  • 最小の手段を探索対象から外すことを「βカット」
  • スコアを最小化するように考えるときに、最大の手段を外すことをαカット

と呼びます。

しかし、単純な疑問として、「コストの評価は誰がおこなっているのか?」と考えた人もいるかと思います。

その答えとして、膨大にあるコストの評価は、全て人間がおこなう事が難しいため、モンテカルロ法という手法が用いられるようになりました。

◉モンテカルロ法とは?
途中の盤面からコンピュータがプレイし、ゲームを強制的に終わらせる手法で、それを複数回繰り返すことで最適な一手を導き出すことができる手法。

こうしたコスト評価の研究の末、2016年3月9日「AlphaGo」という人工知能の囲碁プログラムがプロの棋士に勝つという偉業を達成することになりました。

これにより多大なデータや人工知能は脚光をあび、ディープラーニングの研究がより一層推し進められることになりました。

スポンサーリンク

最後に

今回は第一次AIブームで特に研究が進められてきた探索・推論について紹介をしてきました。

今では当たり前のように使われるようになっているディープラーニングもこうした探索方法やコストという過去の研究によって支えられていることが分かります。

気になった人は探索・推論に関する論文なども調べてみることをお勧めします。決して難しい話ではないので、こうした背景をきちんと理解することで、これからの新技術への理解も深めていきましょう。

コメント