解空間の探索
ほとんどの問題が、多次元の空間で最適な解(最小値)を見つけるという問題になる。
なぜ難しいのか?
評価関数を作るのがそもそも難しい。
空間の形が事前に分からない。
解空間の形が複雑すぎる。
鞍点のような勾配がなくなるケースがある。
ある条件では正しくても、別の条件では正しくないということがある。
過学習もその一つ。
局所解から改善できない。(小さな谷に落ちてしまって、そこから這い上がることがない)
多段の評価が必要で、ある時点での評価値が後方の評価値を保証しないことがある。(例:将棋など)
最小値を求めるのは最大値を求めるのとは何が違う? (最小値、最大値は0または正の値とする。)
1/x にすれば同じ問題。
離散的
離散的な場合、連続的な計算の適用が難しくなる。
連続的
なだらか
凹凸が多い
単段
1つの評価値を試すだけでよいケース
多段
ゲームなど行動ごとに評価値が定まるケース
枝分かれしていくので指数関数的に大量の評価が必要となる。
1段のみでは高い評価値も、複数段で見ると低い評価値となることがある。(先読みが難しい)
全探索
時間が途轍もなくかかる。
十分小さな空間なら実現可能。
ランダム試行
モンテカルロ
全探索よりは時間を減らせるが、運しだいになる。
ビームサーチ
多段の場合に評価値のよいところを集中的に探索する。
勾配法
勾配がわかれば、向かうべき方向がわかる。
微分できれば勾配がわかる。
多くの場合、微分できず、勾配がわからない。
勾配が消失するような場所がある。
多次元になると勾配が小さくわからなくなっていく。
局所解に陥ると、そこから抜け出せなくなる。
焼きなまし
勾配は分からなくても、周辺の小さな評価値を探す。
温度が高い場合、ランダム試行に近づく。
局所解を組み合わせる
遺伝的アルゴリズム
大局解が局所解の組み合わせでできている場合に有効。多くのケースでそういう構造になっている。
物理的アルゴリズム
実物を模倣するモデルを物理的に作ってそのモデルを操作して答えを導く。
迷路の通路をゴムで充填して、そのゴムを取り外して、入口と出口を逆方向に引っ張ると答えの通路が一直線に現れる。