ゼロから学ぶAI②

※この記事は3分で読む事ができます。

どうも！シミズです。

前回の記事を見てくださった方、初めてご覧になる方、お時間頂きありがとうございます！

さっそく、学習してきた事の復習と理解もかねて、綴っていきたいと思います！

第２回は。。。「～探索と推論の時代～　第一次AIブーム」編！

第一次AIブーム到来！！

1950年末頃、アメリカのダートマスにて行われた「ダートマス会議」。

ここで初めて、人間のように知的処理を行える機械のことを人工知能（AI）と呼ぶことが決定し、この世に人工知能という概念が生まれました。

ちなみに人工知能について理解したい方はこちらを参考にしてみて下さい！

1950年末頃というと今から約60年ほど前です。日本では三種の神器が誕生した頃。「白黒テレビ」「洗濯機」「冷蔵庫」が誕生しました。

日本にとっては当時革新的な技術でしたが、海の向こうでは機械に思考を持たせようとしていたようです。。

そんなアメリカで始まった第一次AIブーム。一体、どんな研究がされていたのか！

第一次AIブームで”AI”と呼ばれたモノ

まず、どんな研究がなされていたのかを紹介する前に、どんなものが当初、”AI”と呼ばれていたのか先に紹介します。

第一次AIブームにおいて、AIと呼ばれるものは以下の3つでした。

①迷路を解く②数式の証明③簡単な会話

です。その中でも、この

①迷路を解く

は、今の強化学習の基礎になっている重要な考え方なので、「迷路」を例に出しながら、探索手法を理解していきます！

そもそも探索手法とは？

探索手法とは、多くのデータの中から条件に合致するデータを探し出すためのアルゴリズムのことを指します。数ある選択肢の中から、正解を見つけ出す手法、のようなイメージで構いません。特に、第一次AIブームでは、

・幅優先探索

・深さ優先探索

以上2つの探索手法が考案されました！これから順を追って解説していきます。

幅優先探索とは？

幅優先探索・・・1ステップずつ全ての選択肢を比較しながら探索する手法。

言葉だけではわかりにくいので、迷路を例に図示していきます！

まず、このような迷路においてスタートからゴールまでの経路を考える際、探索木と呼ばれる考え方を用いてコンピューターが処理できる形に変更します。

探索木に変更する際は、まず、経路1つ1つにラベルを振っていきます。

この単純な迷路でもA～Mの13個の分岐がある事が分かりましたね。この迷路ゴールを、幅優先探索で探索します。すると、このように分岐の度に選択肢を比較しながら探索するため、以下のような順番で経路を探します。

そして、これをコンピューターが処理できる探索木の状態に変更すると、

このようになります。コンピュータは場合分けの処理を得意としているため、この状態になって初めてゴールまでの経路を探索する事ができます。その結果、ゴールまでの経路としては、

「S（スタート）→2→3→5→6→7→9→10→11→13→G（ゴール）」が最短であることが分かりました。

以上の結果から幅優先探索では、

・正解までの最短経路を必ず見つける事ができる

という強みがある事が分かりました！その一方で、全ての選択肢を考慮するため、

・分岐の数が増えるほど計算量が膨大になる

という弱点も抱えています。以上が幅優先探索の解説でした。

深さ優先探索とは？

深さ優先探索・・・一方向に掘り下げて正解でなかった場合、前のステップに戻り、異なる方向に探索する事を繰り返しながら正解を探索する手法。

分かりにくいので、図示していきます！深さ優先探索では、例として以下のような順番で探索が行われます。

これを探索木に変換してみると。。

このようになります。幅優先探索の時と比べて、探索木の形状が単純になっています。今回の探索結果を、最初のラベルを貼ったこの迷路

に照らし合わせると、

「S（スタート）→B→C→D→E→F→G→H→I→J→K→M→G（ゴール）」の順番でゴールに辿り着いたようです。

以上の結果から深さ優先探索では、

・幅優先探索と比べて計算量が少ない

という利点があるとともに、

・この経路が最適な解であるとは限らない

という難点もあります。運が良ければ少ない計算量で最適解が見つかる可能性もありますが、運が悪ければ、そこそこの計算量で最適解が出ない、といったケースも考えられます。

復習！（忙しい人はココを見る）

今回は探索手法の中の、幅優先探索と深さ優先探索について理解を深めました。まとめるとこんな感じです！

このように第一次AIブームでは探索の基礎となる考え方ができた事から、

「探索」と「推論」の時代

と言われています！単純ですね。。

まとめ

今回は第一次AIブームで多く用いられたであろう2つの探索手法について学びました。少々長くなってしまいましたが、最後まで読んで下さり、ありがとうございました！コンピューターがゴールを目指して探索していく様子は、まるで僕ら人間が歩んでいる人生のようですね。

あなたの人生は「幅優先探索」ですか？それとも「深さ優先探索」ですか？

僕の人生は。。。。

ではまた！