全体最適解と局所最適解

問題提起
- 局所最適解と全体最適解について確認する
- 機械学習などで最適化が行われる。この際に局所最適解を求めているのか、全体最適解を求めているのかを把握したほうがよい。
全体最適解と局所最適解
- そもそも最適化とは？
  - 目的関数を設定し、その最小値(あるいは最大値)を求めること。
  - 目的関数の値が下記のようなグラフになる場合、最も値の低いA地点の解を求めること。
  - 図1($y = x^2+10$のグラフ)
    - 横軸: $x$ 値(解の範囲)
    - 縦軸: $y$ 値(目的関数の値)
- 全体最適解とは？
  - NWなどを含め一般的な最適化問題では、目的関数のグラフは複雑になる。イメージとしては、下記のようないくつもの谷があるグラフになる。
  - その場合、最も値の低い赤い矢印で示す地点の解。(この場所は他の谷より微妙に値が低い)
  - 図2
    - 横軸: 解の範囲
    - 縦軸: 目的関数の値
- 局所最適解とは？
  - ある範囲においての最適解。
  - 下記の図では、ある範囲が黄色い丸で囲まれた範囲。その範囲での最適解は、青い矢印で示す地点。
  - 図3
- 全体最適解と局所最適解
  - 局所最適解は、いくつも存在する。
    - ※目的関数のグラフに谷がいくつもある場合。
  - 局所最適解は、全体最適解とほぼ変わらない値が得られることがあるが、それが可能であるかどうかは問題次第。
局所最適解を求めるときと、全体最適解を求めるとき
- 全体最適解を求めることが可能であれば、そのほうがよい。
- 局所最適解を求めるケース
  - 全体最適解を求めようとすると、計算時間が長くかかりすぎて不可能な場合。
  - 局所最適解を求めれば、十分な精度が得られる場合。
- 局所最適解を求めるケース
  - NWにおいて、エッジの重みやノードのバイアスといったパラメータを求めるとき。
その他
- 遺伝アルゴリズムについて
  - 全体最適解を求めることが難しい場合に、なるべくよい解を得るために行われる解法の一つ
  - 以下を繰り返す。
    - 近傍における局所最適解を求める。
      - ※ 近傍: 図3の黄色で囲まれた範囲をイメージするとよい。
    - 突然変異を行い、これまで解を探索していたのとは別の場所から解の探索を行う。