ランダム探索
候補を無作為に選んで評価し、一番良かったものを採る。 最も単純な最適化で、他の手法の下限（これより悪いなら意味がない）として使われる。
純粋なランダム探索#
探索空間から一様に 点引き、最良を返す。目的関数の性質を一切仮定しないので、 どんな問題にも適用できる代わりに、次元が上がると急速に無力になる。 体積が次元に対して指数的に増えるため、良い領域に当たる確率が指数的に下がる。
意外に強い場面 — ハイパーパラメータ探索#
Bergstra と Bengio は、機械学習のハイパーパラメータ探索において ランダム探索がグリッドサーチより効率的であることを示した。
理由は、多くのハイパーパラメータのうち実際に効くのは少数だから。 グリッドサーチは全次元を等しく刻むので、効かない次元にも同じ数の点を割く。 個の値を試すグリッドでは、効くパラメータについても 通りしか試せない。 ランダム探索なら 点すべてが、効くパラメータについて異なる値を持つ。
これは「探索空間の実効次元が低い」ときに効く議論で、 ベイズ最適化が 比較対象としてまずランダム探索を置くのもこのため。
参考文献#
- James Bergstra, Yoshua Bengio. Random Search for Hyper-Parameter Optimization. JMLR 13, 2012. https://jmlr.org/papers/v13/bergstra12a.html
- Jeffrey Larson, Matt Menickelly, Stefan M. Wild. Derivative-free optimization methods. Acta Numerica 28, 2019. https://arxiv.org/abs/1904.11585