カンボ亭

アクセスカウンタ

zoom RSS 11月24日分のグループ課題

<<   作成日時 : 2005/11/28 21:43   >>

ブログ気持玉 0 / トラックバック 0 / コメント 0

(1)人工知能とは何か?
 人工知能を簡単に言うと「コンピュータに人間の知能を擬似的に実現するシステム」のことである。人工知能と聞くとやたらと難しく得体のわからないものを想像してしまいまうが、実際にはかなり身近なものである。例えばチェスや将棋などのゲームや翻訳ソフトなどに人工知能は利用されてる。

(2)よいアルゴリズムとは何か?
 同じ正しい結果が得られるのであれば、コストがもっともかからない方法である。また誰が見ても分かりやすく、どんな場合でも正しく処理する、プログラムの効率がよいなどもよいアルゴリズムの条件である。

(3)良性問題と非良性問題の違いは何か?
 良性問題とはソフトウェアやハードウェアを使って解決できない問題であり、非良性問題はソフトウェアやハードウェアを使っても解決できない問題のことである。

(4)遺伝的アルゴリズムとは何か?
 遺伝的アルゴリズムとは、ある問題に対する最適な解を求めるための手法といえ
る。この手法はもともと、生物の世界にある遺伝の法則をまねて作られたもので、複
数の解を、遺伝的に変化させながら、より良い解を求めていくものである。

(5)ニューラルネットワークとは何か?
ニューラルネットワークとは、人間の脳の構造をまねて作った情報処理機構です。人間の脳は、「ニューロン」と呼ばれる神経細胞の組み合わさった構造(神経回路網)で構成されています。この構造をまねることで、人間の得意とするような、パターン認識や、連想記憶などの処理を効率良く行うことができます。ニューロンは、入力の和がしきい値を越えると出力をだします(発火)。このニューロンをたくさん組み合わせて、ニューロン間の接続に重みを付加することで情報処理を行います。ニューロンの学習はこの重みを変化させることによって学習を行います。実際の脳の構造や動作原理には、まだ未知の部分が多いので様々なモデル化が提唱されています。また、実際の神経細胞とは異なる方法でモデル化されたニューラルネットワークでも、有効な情報処理手法である場合もあります。ニューラルネットワークには、階層型と相互結合型があります。階層型の代表的なものにはパーセプトロン、バックプロパゲーション(BP)学習型、ネオコグニトロンなどがあります。相互結合型には、アソシアトロン、ホップフィールドネットワーク、ボルツマンマシンなどがあります。

(6)事例ベース推論とは何か?
事例ベース推論とは、その人工知能研究の一つのアプローチ法である。コンピュータに知能を持たせるにあたっては、例えば人間が問題解決を行う手順をこと細かく規則化してコンピュータに覚えさせることや、例えば確率的なモデルを使うもの、例えば学習機能を持たせて問題解決を重ねるごとにコンピュータ内に知識を蓄えていこうとするもの(簡単に言えばコンピュータに赤ちゃんをやらせようとするもの) などがある。事例ベース推論はそういったいくつもあるアプローチのうちの一つである。その方法は、コンピュータに問題解決の事例をあらかじめたくさん入力しておく。それは成功した事例と失敗した事例が混ざっていてもよいし、成功した事例だけを入力しておくのもいいだろう(簡単に成功と失敗とを評価しにくい場合もあろうが)。そして新たな問題が現れたら、過去の類似した事例を検索し、その事例において実行した解決策を出力する。検索事例が失敗事例だったら「次に似た事例を検索する」なり「その解決策は避ける」なり、いくつか対処法は考える。そして新たに解決した問題についても「状況」「解決策」「結果」といった要素からなる事例として蓄えることで次からの推論で使える。一種の学習の機能を持たせることもできるわけである。

(7)DB利用業務システムにおける良いアルゴリズムとは何か?
業務システムはデータを加工しつつ転記する動作が極めて多い特徴があります。そのため、ディスクアクセスの時間が処理時間のボトルネックとなりやすいので、アクセス回数を減少させることが最良のアルゴリズムとなることが多いです。

(8)単純文字列照合、KMP法、BM法とは何か?
・単純な文字列照合
ある文字列が、与えられた部分文字列と一致する場所を探す処理であるも のを文字列照合(string matching)と言う。エディタの検索機能なんかを思い 浮かべてもらえればいいと思います。文字列照合を行うための最も単純な方 法は、照合される文字列の頭から順に照合文字列と比較して、違っていたら1 文字ずつ後ろへずれながら処理を繰り返すことでしょう。

・KMP法
一般に,力任せに単純に文字列探索を行なうと,ある開始位置からパターン文字列のマッチングを開始し,そこで失敗したら,開始位置を1文字ずらしてさらにマッチングを行ないます.したがって,場合によってはマッチングで文字を読み進めても,さらに戻ってマッチングを開始することがあります.一般に,力任せに単純に文字列探索を行なうと,ある開始位置からパターン文字列のマッチングを開始し,そこで失敗したら,開始位置を1文字ずらしてさらにマッチングを行ないます.したがって,場合によってはマッチングで文字を読み進めても,さらに戻ってマッチングを開始することがあります.しかし,KMP法では,そのような逆行が存在しません.例えばパターン文字列がabbbであったとして,3文字目のbまではマッチして,最後の4文字目のbでマッチ失敗したとしましょう.すると,マッチ失敗したのは abb? という文字列であったわけですから,次にabbbをマッチさせるならば,先ほどマッチ失敗した4文字目の位置から試せば十分なのです.また,パターンabaaに対して,最後のaで失敗したとすれば,今度は3文字目からマッチを開始しますが,既に最初のaがマッチすることは明らかですので,3文字目からのマッチ開始で,なおかつ3文字目は既にマッチ成功とみなして4文字目からマッチ開始をすればよいのです.いずれにしても,既に読んだ文字列を逆行することはありません.一般に,パターン中でマッチ失敗したときに,次に何文字ずらせばよいかはパターンのみから決定されます.これをnext表という形でパターンのそれぞれの位置に対して保持しておきます.そして,この表を用いてマッチを進めていくのがKMP法です.

・BM法
Boyer-Moore法を使って文字列検索を行うクラス(TStringSearch)です。文字列検索で最高速といわれる Boyer-Moore法を一部アセンブリで実装したので高速です。Ansi対応や、大文字小文字を区別しないなどを指定できます。両方指定すれば、ちゃんと「a」を「A」にマッチします。この場合も Boyer-Moore法を使っています。普通の Boyer-Moore法ではないですが。まずは、文字列の検索で使用する外部変数を定義する。pattern は検索文字列を格納する。rev_pat は検索文字列を逆順にして格納する。BM法は末尾から文字列を比較するので、逆順にしておいた方が都合がよい。p
at_len は検索文字列の長さを保持する。文字列の最大長は MAX_PAT (255) とした。最後に移動量を格納する bm_table を用意する。

参考文献
http://www5.airnet.ne.jp/tomy/cpro/ms1.htm
http://bal4u.dip.jp/mt/program/archives/2004/09/bmbmmatch.html
http://hwb.ecc.u-tokyo.ac.jp/current/CDD1B8ECBDB82F4B4D50CBA1.html
http://www.atmarkit.co.jp/fwin2k/experiments/defragment/defragment_1.html
http://www.geocities.co.jp/SiliconValley-Cupertino/3384/AI.html
http://kyu.pobox.ne.jp/softcomputing/ga/ga1.html
http://www5c.biglobe.ne.jp/~ecb/algorithm/1_3.html

コメント
今回は人工知能とアルゴリズムに関連することを学びました。以前に調べたことがある単語もでてきたが、忘れてしまっていたのできちんと覚えておきたいと思います。人工知能にはもっと幅広く活躍してほしいと思います。

月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
11月24日分のグループ課題 カンボ亭/BIGLOBEウェブリブログ
文字サイズ:       閉じる