ANA兄弟

アクセスカウンタ

zoom RSS 11月24日の課題

<<   作成日時 : 2005/11/28 22:09   >>

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

□意味調べ

1)人工知能とは何か

知識をもとに、さまざまな問題に対し、問題を認識し、推理や判断を行ったり、知識
を 学習したり整理する能力を持った考えるコンピュータプログラムのことである。
「学習」は何か機械が勉強をする感じがしますが,ここでは「情報から将来使えそう
な知識を見つけること」です。

2)よいアルゴリズムとは何か
同じ正しい結果が得られるのであれば、コストがもっともかからない方法である。
また、さまざまな分野において特定のアルゴリズムが絶対に良いとは言えず、状況が
異なればそれにあったアルゴリズムが存在するため、よいアルゴリズムというのは状
況に応じたくさん存在する。

3) 良性問題と非良性問題
ソフトウェアにおける良性問題の解決方法は解析的に解いて、その解析解の結果を利用したり、数値演算でループを減らしたりすることである。また、ハードウェアを活用し、パイプライン化や並列化を行って良性問題を解決したりもする。非良性問題に対する解決方法としては、数値計算では判断が困難なため実際上解が求められないものに対して遺伝的アルゴリズムを使ったり、原因と結果の関係を数式で表すことが困難なものに対してニューラルネットワークを使ったり、局所最適化してしまって、大域的には最適化しない恐れのあるものに対してシミュレーション・アニ―リングを使ったりすることである。

4)遺伝的アルゴリズムとは
生物の進化過程にヒントを得た遺伝的操作を使って、与えられた問題に対する最適解を求める手法。どれほど複雑な問題に対しても、原理的には最適あるいは最 適に近い解が得られるため、計画問題を中心に多くの応用研究が進められており、実用化されたシステムもある。アルゴリズムが並列処理に適するため、超並列 コンピュータを利用することも多い。遺伝的アルゴリズムでは、@解候補(個体と呼ぶ)の集団を生成し、Aそれぞれの個体について適応度を評価し、B消化値 の高い個体を選択して、Cそれらに対して、「交叉(crossover)」、「突然変異(mutation)」などの操作を加えて月の世代の個体集団を生 成する。A〜Cを繰り返して”世代”を重ねるにつれて、適応度の高い個体が増えていくと同時に、より最適解に近い個体が現れる確率も高くなっていく。評価 値がある値に達したときの解が求める最適解となる。
各個体は染色体(chromosome)状に一次元的に並んだ遺伝子(gene)の列として表現する。Cの交叉とは、染色体を途中で切断し、切断した部 分にほかの染色体の一部を接続する操作である。例えば、染色体「aaaaa」と「bbbbb」に対して3番目の文字以降に対して交叉を施すと 「aaabb」と「bbbaa」が得られる。一方、突然変異は「aaaaa」から「aacaa」を作る操作のように、文字列中の一部を別の文字で置き換え ることである。
新しいソフトを作るために、遺伝子に見立てたプログラムをさまざまなパターンに組み替えるGP(genetic programming:遺伝子的プログラミング)が注目されている。

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

6)事例ベース推論
事例ベース推論(Case Based Reasoning、CBRと略記)とは、
与えられた問題に類似する過去の事例(成功または失敗)を直接利用して解を導く推論の方法である。
処理サイクル
@最も類似したケースを検索(RETRIEVE)
A検索したケースを再利用(REUSE)
BAで提案された解を修正(REVISE)
:専門家のチェックにより修正
C得られた経験の一部を獲得(RETAIN)
与えられた問題は、解析され検索を容易に行えるような形式に変換する。
変換された問題や事例を蓄積してあるデータベースの事例と照らし合わせ、一致する事例を検索する。
一致した場合はその事例の解が問題の解となるが、
一致しない場合は、事例を問題と一致するように修正・修復を行う。
これを行い、一致した場合はその解が問題の解になる。
一致しない場合は修正・修復を行った事例をデータベースに格納をして、
問題と事例が一致するまでこれを繰り返す。

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

8) 単純文字列照合、KMP法、BM法とは何か
@単純な文字列照合
照合される文字列(以下、テキストとします)の頭から順に照合文字列(以下、パターンとします)と比較して、違っていたら1文字ずつ後ろへずれながら処理を繰り返すアルゴリズムです。
テキストとパターンのそれぞれの文字数がn,mで、かつnがmに対して十分大きいとすると、上記のアルゴリズムの場合最悪m×n回近く文字を比較する 必要があります。例えば、単一の文字がn個並んだ文字列から、同じ文字の並びの末尾に1文字だけ違う文字コードを付加したm個の文字列を検索した場合、m -1文字まで検索して最後のm文字目で不一致を検出する処理をn回近く繰り返すことになります。
しかし、現実にはこのような「最悪の」場面というのはまずないと言えます。仮に各文字コードがテキスト中に現れる確率が全て等しいとした場合、テキストと パターンの1文字目が一致する確率は「文字コードの種類の逆数」となり、さらに2文字目、3文字目と連続して一致する確率はその2乗、3乗とさらに小さく なっていきます。実際には各文字コードの使用頻度がバラバラであるため正確さに欠けるとはいえ、現実の文字コードの種類は十分多いから、2つの文字が連続 して一致する確率より、一致しない確率の方がずっと高いということはまず間違いないと思います。
もし、常にパターンの先頭で不一致が見つかったとすれば、文字コードの比較回数は最大でも約n回となるので、パターンの先頭で不一致を検出する確率が 非常に高ければ実行速度はだいたいnに比例すると考えることができます。一般に、実行時間がデータの量に比例するアルゴリズムは「高速」、少なくとも「実 用的」な部類に属するので、上に示した「単純な」文字列比較は実用上十分「高速」であり、よって文字列照合に関しては複雑なアルゴリズムが入り込む余地が あまりないことを意味します。そのため歴史的には、より高速な文字列照合のアルゴリズムが登場するのがかなり遅かったようです。


AKMP法
単純な文字列照合アルゴリズムでは不一致が検出されたらパターンを1文字ずらして再び照合を繰り返すものでしたが、KMP法では、パターンとテキスト の間で部分的に一致した場合に、その情報を元に大きくパターンを移動することによって効率化を図っています。そのために、不一致を起こした個所それぞれに ついて何文字までずらせばいいのかを事前に調べてテーブルにしておきます。KMP法の性能については理論上、文字の比較回数が最悪でも2×n回であるそう です。よって、単純法の比較回数が最悪m×n回であることと比べると大きく性能が向上したように見えます。しかし、KMP法はパターンの末尾側で不一致が 発生したときにはじめて移動量が大きくなるため、通常の場合では前に述べたようにパターンの先頭付近で不一致が発生することを考えると、処理が複雑な上に 前処理が必要になる分、かえって単純法よりも遅くなることが考えられます。
KMP法のもう一つの特徴としては、テキストを走査するときのポインタが逆戻りしないというものがあります。この特徴により、KMP法はメモリに納まらないような長いテキストを扱うのに適しているといわれ、事実、発案者のMorrisはテキストエディタを作成中に、ポインタが逆戻しないような文字列照 合アルゴリズムを考えていてKMP法にたどり着いたという事です。
また名前の由来は、KnuthとPrattおよびこの二人の他にMorrisが同時期に考案し、Knuth-Morris-Prattの頭文字をとって、KMP法とよばれている。

BBM法(BMH法)
BM法の最大の特徴は、パターンを末尾側から逆方向に比較するということです。テキストとパターンの先頭をそろえた後、今までのアルゴリズムではパ ターン先頭とテキスト先頭を比較するのですが、BM法ではパターン末尾(先頭からm文字目)の文字と、テキストのm文字目の文字を比較します。もし一致していたら注目文字を1つ前にずらし、末尾側から逆方向に比較していきます。もし不一致が検出されたら、不一致を引き起こしたテキスト側の文字に注目して、 もしその文字がパターン中に含まれていたら、両者が重なる位置までパターンを右にずらします。そうしないと、同じ場所で再び不一致を検出してしまうからで す。また同じ理由により、不一致を引き起こしたテキスト上の文字がパターン中に含まれていない場合、パターンの先頭を不一致を起こしたテキスト上の文字より次の位置にまでずらすことができます。BM法はKMP法同様、パターンの移動量をあらかじめテーブルに登録します。KMP法のテーブルは不一致を起こしたパターン上の位置をインデックスにしていましたが、BM法では不一致を起こしたテキスト側の文字がインデックスとなります。このテーブルには、右端の文 字位置を0として、各文字がパターンの右端から何文字目に現れるかを登録します。パターン中に同じ文字が複数ある場合には、その最も右側の位置を採用します。
しかしこのように便利なBM法ですが、いくつか問題があります。一つめは、テキスト上で不一致を起こした文字が、パターンの比較位置より右側に含まれていた場合に生じるバックスライドです。このバックスライドが発生すると永久に先へ進まなくなるため、どんな場合でもパターンは必ず右に最低1文字分は移動しなければならないのですが、実はバックスライドが発生した場合はパターンを右1文字ではなく"2文字分"移動しても問題ありません。というのも、あと 1文字パターンが右へ移動すれば文字列が全て一致する場合、不一致を生じた位置より末尾側にあるパターンの文字は全て一致し、それは必ず不一致を起こした テキストの文字とは一致しないため、バックスライドが生じないからです。もう一つの問題は、BM法の場合テキストを1文字ごとに走査するわけではないの で、文字列の終端コードで末尾に到達したかをチェックすることができないことです。このため、テキストの長さをあらかじめ調べておいて、比較位置が文字列 長を越えていないかをチェックするようにする必要があります。テキストの長さは、処理前に数える方法とメインルーチン側から引数として渡す方法の2通りが 考えられますが、文献ではメインルーチン側から引数として渡す方法を取っています。テキストエディタなどからこのルーチンを使用する場合を考えると、たいていは各行のテキスト長や末尾のアドレスは保持しているのが普通ですし、エディタから再検索をする度に文字列長をサブルーチン側で数え直すのは無駄である というのが主な理由です。
また名前の由来は、BoyerとMoore、また両者とは別にGosperが考案した方法にBoyer-Mooreの頭文字をとって、BM法と呼ばれている。

□感想

調べる数と内容が多く、難しくなってきたので大変でした。人工知能がとても興味深く、これからどれだけ進化を続けていくのか楽しみです。が、誤った進化を続けていくのは危険なことなのでそこは注意してほしいと思います。

□参考文献
http://www.maebashi-it.org/~onaya/index.xml
http://www.ai-gakkai.or.jp/jsai/whatsai/
http://www2.starcat.ne.jp/~fussy/index.htm の中の各項目
http://hwb.ecc.u-tokyo.ac.jp/current/CDD1B8ECBDB82F4B4D50CBA1.html
http://hwb.ecc.u-tokyo.ac.jp/current/CDD1B8ECBDB82FA5A2A5EBA5B4A5EAA5BAA5E0.html
http://kyu.pobox.ne.jp/softcomputing/ga/ga1.html
http://kyu.pobox.ne.jp/softcomputing/neuro/words.html
◆講義録
◆情報・通信新語辞典/日経BP社
◆誰でもわかるパソコン用語辞典/新星出版社
◆エクスメディア 超図解 パソコン用語辞典 2003-04年版
◆以前調べた用語の説明から引用



月別リンク

ブログ気持玉

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

トラックバック(0件)

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

トラックバック用URL help


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

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
11月24日の課題 ANA兄弟/BIGLOBEウェブリブログ
文字サイズ:       閉じる