3.探索

 入力された問題に対して、いくつかの解を評価し、最適な解を返すアルゴリズム

 

3.1.探索とは

探索(たんさく、英: search)とは、大まかに言えば、問題を入力として、考えられるいくつもの解を評価した後、解を返すアルゴリズムです。特定の制約条件を満たす物を見つけ出す処理を示しています。機械学習と同様の人工知能の分野のアルゴリズムで、いくつかの探索アルゴリズムが試されてきました。解くべき問題を状態(英: state)と状態変化(行動、英: action)に分け処理します。将棋ならば、盤面の駒の配置と指し手の持ち駒が状態であり、交互に駒を動かすことが状態変化に当たります。

 

リスト探索(list search)

リストから何らかのキーを持つ要素を探す処理です。ハッシュテーブルもリスト探索に使われ、実行時間は平均ケースでO(1)であるが、最悪ケースでは O(n) もかかります。

 

線形探索(linear search

単純にリスト上の各要素を調べていく。その実行時間は O(n) です。

 

※注:O記法(オーきほう、オーダーきほう)

計算量の記述には、この表記が用いられ、命令数がデーター数に比例することを意味します。例えば2*nや、3*nといった計算量で、具体的にはn回や、nに比例する回数以内のループの処理で終わる場合がこれに該当します。

 

二分探索(binary search

実行時間は O(log n) で、データーが多ければ多いほど線型探索よりも性能がよくなりますが、探索の前にソートしておく必要があり、またランダムアクセスが可能でなければなりません。

 

内挿探索(ないそう:interpolation、補間とも言う)

内挿探索は分布が偏っていないソートされた大きなリストでは二分探索よりも性能が良いが、最悪ケースでは O(n) となります。

 

  • 一週間で身につくアルゴリズムとデーター構造 O(オーダー)記法

http://sevendays-study.com/algorithm/ex-day1.html

 

3.2.深層学習での探索

今までの探索アルゴリズムでは複雑な過程となれば、時間がかかり、解凍も複数個出てきて、その評価結果に曖昧さが出てきます。これは十分な探索ができていないことになるわけで、それを補うのが、深層学習です。前述したように自然言語処理はTF-IDFやリスト探索などを用いてそれなりの結果を導いたのですが、深層学習では次のような例があります。引用が少し長いのですが、重要な記事なので紹介したいと思います。

こうなってくると深層学習では自然言語の解析処理と探索が一緒に同時にお紺われているようなKン時になり、従来の方法とはまったく違ってきます。

 

3.3.IBMワトソンが女性のがん患者を救う

2年前の出来事ですが、東京大学医科学研究所の附属病院は、アメリカの大手IT企業IBMなどと協同で、AI「ワトソン」に2,000万件に上るがん研究の論文を学習させました。

ある60代の女性患者は当初、医師から「急性骨髄性白血病」と診断されこれに効果がある2種類の抗がん剤治療を数か月間続けましたが、容体が悪化し余命宣告を受けたほどでした。

このため、女性患者の1,500に上る遺伝子の変化のデータをAIに入力し分析したところ、AIは10分ほどで女性が「二次性白血病」という別のがんと診断し、抗がん剤の種類を変え、3か月後に退院したとのことです。余命宣告から完治へ、劇的なAI活用例です。


このコンテンツは会員限定のコンテンツです。
会員登録または、ログインしてください。

あわせて読みたい