Help us understand the problem. What is going on with this article?

全体最適解と局所最適解

More than 1 year has passed since last update.

全体最適解と局所最適解

  • 問題提起

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

    • そもそも最適化とは?
      • 目的関数を設定し、その最小値(あるいは最大値)を求めること。
      • 目的関数の値が下記のようなグラフになる場合、最も値の低いA地点の解を求めること。
      • 図1($y = x^2+10$のグラフ)
        • 横軸: $x$ 値(解の範囲)
        • 縦軸: $y$ 値(目的関数の値) 局所最適解と全体最適解_図1.png
    • 全体最適解とは?
      • NWなどを含め一般的な最適化問題では、目的関数のグラフは複雑になる。 イメージとしては、下記のようないくつもの谷があるグラフになる。
      • その場合、最も値の低い赤い矢印で示す地点の解。(この場所は他の谷より微妙に値が低い)
      • 図2
        • 横軸: 解の範囲
        • 縦軸: 目的関数の値 全体最適解と局所最適解_図2.png
    • 局所最適解とは?
      • ある範囲においての最適解。
      • 下記の図では、ある範囲が黄色い丸で囲まれた範囲。その範囲での最適解は、青い矢印で示す地点
      • 図3 全体最適解と局所最適解_図3.png
    • 全体最適解と局所最適解
      • 局所最適解は、いくつも存在する。
        • ※目的関数のグラフに谷がいくつもある場合。
      • 局所最適解は、全体最適解とほぼ変わらない値が得られることがあるが、それが可能であるかどうかは問題次第。
  • 局所最適解を求めるときと、全体最適解を求めるとき

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

    • 遺伝アルゴリズムについて
      • 全体最適解を求めることが難しい場合に、なるべくよい解を得るために行われる解法の一つ
      • 以下を繰り返す。
        • 近傍における局所最適解を求める。
        • ※ 近傍: 図3の黄色で囲まれた範囲をイメージするとよい。
        • 突然変異を行い、これまで解を探索していたのとは別の場所から解の探索を行う。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away