G検定 局所最適解と大域的最適解

株式会社リュディアです。停留点と鞍点のまとめに続いて、局所最適解と大域的最適解についてまとめてみます。この2つのキーワードも G検定では頻出となっていますので丁寧にみていきましょう。

関数 f (x)  にの最小化問題を考えます。このとき「局所的な x の範囲」に存在する x = a で f (a) が最小となるとき、a を局所最適解、f (a) を局所最小値とよびます。ここで「局所的」という言葉は感覚的なのですが、まずはこのまま進めます。また「x の定義域全域」に存在する x = a で f (a) が最小となるとき、a を大域的最適解、f (a) を大域的最小値とよびます。文字で書くとわかりにくいと思いますので簡単な関数のグラフを眺めてみましょう。グラフでは縦軸が y ですが y = f (x) と理解してください。

グラフを見ると簡単にわかりますね。大域的最小値は2か所あります。また x = -2 ~ 2 の範囲でf (x) の最小値が 0 であることもわかると思います。この 最小値 f (0) = 0 は x = -2 ~ 2 の範囲で最小ですが、x の定義域全域では最小でないこともわかりますね。つまりf (0) = 0 は局所最小値です。機械学習ではさらに複雑な関数を扱うのですが、この簡単な関数ですら勾配降下法で最小値を探す際には問題が発生します。何が問題なのでしょうか？

単純な勾配降下法はある点を開始点としてより小さな値を順に探す方法です。図中の A から関数値が小さくなる方向に探し始めると局所最適解 x = 0 で動けなくなります。一方、Bから探し始めると大域的最小値にたどり着きます。初期値によって到達する最小値が異なる、という問題が最小値検索における初期値の依存性です。これらの問題点を解決するために、最近の実装では初期値の依存性を小さくする工夫、局所最適解に陥っても脱出してよりよい局所最適解、あるいは大域的最適解に到達するための工夫が施されています。

参考までにコンピューターで大域最適解にかならず到達するには、総当たりをするしかありません。通常は膨大な時間が必要となるので、よりよい解を見つけにいく、というアプローチをとります。このあたりは、計算量の理論を学ぶ必要があるので特に言及はしません。興味のある方は以下の書籍がよい思います。

NP完全問題入門

また先の停留点、鞍点と局所最小点、大域的最小点の関係を見ると、以下のように関係づけられます。

停留点は、極大点、極小点、鞍点のいずれかになりうる、また最小化問題においては極小点は局所最小点または大域的最小点のいずれかになります。同様に最大化問題においては極大点は局所最大点または大域的最大点のいずれかになります。

いろいろな用語が出てきていますが、これで言葉の間の関係は理解いただけたのではないでしょうか。数学的には厳密性を欠く記述もありますが感覚的に理解してもらうために今回のまとめを用意しました。G検定の勉強にお役立てください。

では、ごきげんよう。