全体最適解と局所最適解

• 問題提起

  • 局所最適解と全体最適解について確認する
  • 機械学習などで最適化が行われる。この際に局所最適解を求めているのか、全体最適解を求めているのかを把握したほうがよい。

• 全体最適解と局所最適解

  • そもそも最適化とは？

    • 目的関数を設定し、その最小値(あるいは最大値)を求めること。
    • 目的関数の値が下記のようなグラフになる場合、最も値の低いA地点の解を求めること。
    • 図1($y = x^2+10$のグラフ)
      • 横軸: $x$ 値(解の範囲)
      • 縦軸: $y$ 値(目的関数の値)
        

  • 全体最適解とは？

    • NWなどを含め一般的な最適化問題では、目的関数のグラフは複雑になる。 イメージとしては、下記のようないくつもの谷があるグラフになる。
    • その場合、最も値の低い赤い矢印で示す地点の解。(この場所は他の谷より微妙に値が低い)
    • 図2
      • 横軸: 解の範囲
      • 縦軸: 目的関数の値
        

  • 局所最適解とは？

    • ある範囲においての最適解。
    • 下記の図では、ある範囲が黄色い丸で囲まれた範囲。その範囲での最適解は、青い矢印で示す地点。
    • 図3
      

  • 全体最適解と局所最適解

    • 局所最適解は、いくつも存在する。
      • ※目的関数のグラフに谷がいくつもある場合。
    • 局所最適解は、全体最適解とほぼ変わらない値が得られることがあるが、それが可能であるかどうかは問題次第。

• 局所最適解を求めるときと、全体最適解を求めるとき

  • 全体最適解を求めることが可能であれば、そのほうがよい。
  • 局所最適解を求めるケース
    • 全体最適解を求めようとすると、計算時間が長くかかりすぎて不可能な場合。
    • 局所最適解を求めれば、十分な精度が得られる場合。
  • 局所最適解を求めるケース
    • NWにおいて、エッジの重みやノードのバイアスといったパラメータを求めるとき。

• その他

  • 遺伝アルゴリズムについて
    • 全体最適解を求めることが難しい場合に、なるべくよい解を得るために行われる解法の一つ
    • 以下を繰り返す。
      • 近傍における局所最適解を求める。
        • ※ 近傍: 図3の黄色で囲まれた範囲をイメージするとよい。
      • 突然変異を行い、これまで解を探索していたのとは別の場所から解の探索を行う。