Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
6
Help us understand the problem. What is going on with this article?
@9ryuuuuu

全体最適解と局所最適解

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の黄色で囲まれた範囲をイメージするとよい。
        • 突然変異を行い、これまで解を探索していたのとは別の場所から解の探索を行う。
6
Help us understand the problem. What is going on with this article?
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
9ryuuuuu
twitter: https://twitter.com/9ryu エンジニアに役立つ統計や最適化の知識を発信していきたいです。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
6
Help us understand the problem. What is going on with this article?