それわかるぅ〜

日々「それわかるぅ〜」と思ったこと、忘れたくないことを徒然なるままに。Inputした情報を定着させるためのOutputの場として使用しています。誤字脱字等はたぶん仕様です。

人工知能

講義メモ
具体的なアルゴリズムとかはここには書かない.

経路探索問題の定義

初期状態から目標状態までに至るオペレータの系列を発見する問題.

幅優先探索

探索木の接点をあるレベルの接点を全て展開してから次のレベルの節点を順次展開する. すなわち、早い時期に生成された節点を優先的に展開する探索方法. 必ず停止する.
木の分岐数をb、深さをdとすると計算量と記憶量はともに\(O(b^d)\)となる.

深さ優先探索

探索木のより深いレベルの節点を順次展開する. すなわち、最近展開された節点の子節点を順次展開していく探索方法. 停止しない可能性がある.
計算量は\(O(b^d)\)、記憶量は\(O(d)\)となる.

反復深化

動的に変数cの値を変化させながらそのcの値以下の深さの範囲内で優先探索もしくは幅優先探索などの線形記憶量探索を反復させる方法. 解があれば停止する .
計算量は\(O(b^d)\)、記憶量は\(O(d)\)である. したがって深さ優先探索に比べて必ず停止するという部分で、幅優先探索に比べて記憶量の面で優れている.

最良優先探索

探索木において次に展開する節点を評価関数fを用いて決定しながら探索を行う方法.

A*

最良優先探索の一種. 評価関数としてはf(n) = g(n) + h(n)を用いる. g(n)は初期節点から節点nに至るまでのコストのその時点での最小値. h(n)は節点nから目標節点までの最短経路のコストの推定値. なおfの値が同じ節点があれば同時に展開していく.

IDA*

反復深化をA*に適用して線形記憶量探索を行う方法.

制約充足問題

変数の集合、各変数の値域、制約の集合が与えられたときに、全ての制約を満足する値の割り当てを見つける問題. 木探索と弛緩法によって解が得られる.

同定木

一定数のデータをその属性の値と結果を基にいくつかのクラスに分類し、未知のデータに対しても正しく分類が行えるような手順を示す木のこと.

ニューラルネットワークの学習

教師つき学習と教師なし学習に分類される. 前者では回路網がその出力を教師信号に近づけるように学習を行い、後者では入力信号の統計的性質に基づいて学習を行う.

パーセプトロンの構成

2値の入力の組み合わせに応じて0もしくは1を出力する論理関数を複数用意し入力に対する論理回路の出力にそれぞれの出力に対応する重み関数を掛けあわせたものの総和をとりそれを閾値を0として出力を定める. (閾値に関しては抑制性入力を設けて0にすることができる. 通常は0を超えれば1. )

パーセプトロンの学習

  • 初期設定として全ての重みは0
  • 全てのサンプルを順にパーセプトロンに適応する
  • その結果について
  • 1を0に誤ったときは出力ベクトルを重みベクトルに加える.
  • 0を1に誤ったときは出力ベクトルを重みベクトルから引く.
  • 正しければなにもしない.
  • 以上を全てのサンプルについて正しい結果が出力できるようになるまで繰り返す.

パーセプトロンで学習できないこと

パーセプトロンは論理関数に対する入力範囲の制限から離れた部分の変化を同時に学習できる論理関数や、XORなどの非線形分離問題を学習できない.

サポートベクタマシンにおけるマージン最大化

境界の位置に微小な誤差が合っても誤識別される可能性が低く、サポートベクタ以外の点は削除されても問題がないことを理由にサポートベクタマシンでの識別にはマージン最大化の概念が用いられる.

カーネルトリック

本質的に非線形で複雑な問題に対しては必ずしも性能のよい識別器を構成できるとは限らないため、特徴ベクトルを非線形変換して変換された高次元空間で線形の識別を行うこと.

サポートベクタマシンの利点と欠点

マージンの最大化を行うことで、誤認識の可能性の低い識別器を作成でき、非線形分離問題においても高次元空間に識別対象を移し、そこで線形識別を行うというカーネルトリックに手法により識別器の作成が可能になるという利点があるが、カーネルトリックにより高次元空間での計算が膨大な量になる可能性や過学習の可能性があるという欠点がある.

論理の単調性

その論理体系で証明できる定理は新しく無矛盾な公理を付け加えてできる体系においても必ず定理となる.

論理の非単調性

新しい公理を加える事によって定理であったものが定理でなくなること.

強化学習

明確な教師がいない環境における学習アルゴリズム. 明確な教師がいないため、思考を通じて報酬を最大にするような状態から動作への写像を学習する. また動作は後続する動作の報酬にも影響する.

マルコフ過程

現在の状態が有限の過去の過程に依存するような過程.

遺伝的アルゴリズム

評価->選択->交叉->突然変異を1世代分の走査と考えてこれを何世代分も繰り返す. 例えば巡回セールスマン問題では、各都市に異なる数値をラベルとして割り当てて、それを巡回都市順に並べて遺伝子をつくる. そして予めベクトルとして入力された各都市間の移動距離から対象となる巡回都市の方法の移動距離を求めてそれをその遺伝子の評価値にする. さらにその後、トーナメント選択法によって残す遺伝子を決定し、それらの中で遺伝子の交叉を行う.(交叉の方法についてはいろいろなものが考えられるがここでは言及しない. )そしてそこに低い確率で突然変異を発生させる. (突然変異の方法としてはランダムな数値を遺伝子の中に混ぜる方法などが考えられる.)これを繰り返すことで最適解に近い解が得られる.

遺伝的アルゴリズムが発見できる解

遺伝的アルゴリズムでは最適解を発見する保証はない. なぜなら解空間において遺伝的アルゴリズムでは最適解に近いと考えられる遺伝子を次の世代に残すアルゴリズムをとっているため、低く評価される遺伝子の近辺、子孫に最適な解が存在するケースではそれが見つからない可能性が高い. 逆に遺伝的アルゴリズムの利点としては優れた遺伝子を多く次の世代に引き継ぐようにしているため、大域的に良い解が多数見つかりやすいという点があげられる.