Random & Quasi-Monte Carlo

Tunny は、ベイズ最適化や遺伝的アルゴリズムなどの最適化アルゴリズムだけでなく、単純にランダムでサンプリングする Random Sampler と QMC Sampler も提供しています。

このセクションでは、これらが Tunny に存在する理由と、どのような場合に必要になるかを、技術的な詳細も含めて説明します。 まず両者の違いを図で確認し、次にどちらを選ぶかを整理したうえで、最後に最適化のなかでどう使うかを紹介します。

両者の違い

詳細な説明を読む前に、まずは各サンプラーでサンプリングした結果を見るのがもっとも理解しやすいでしょう。

Tunny の Quasi-Monte Carlo サンプラーは Halton と Sobol の 2 つのアルゴリズムを使用できるため、以下はこの 2 つと Random Sampler を用いて x と y を -10 から 10 の範囲でサンプリングした結果です。 以下の例では 256 個の個体をサンプリングしており、色が濃いほど後にサンプリングされたことを示します。

QMC(Halton)

QMC(Sobol')

Random

これらの図から、Random と QMC の違いがすでに見て取れます。

QMC によるサンプリングはランダムですが、点が一箇所に密集することなく、適度な間隔でサンプリングされます。 このような特徴を持つ数列は低差異列（low-discrepancy sequence）と呼ばれます。

一方、Random Sampler はその言葉が示すとおりできるだけ「ランダム」であることが求められるため、すでに観測された点のごく近くの点をサンプリングすることもあります。 QMC のようにそれまでの点との間隔を考慮しないことによる結果であり、Random Sampler が正しく動いていないわけではありません。

どちらを使うべきか

解空間全体をきれいに把握したい場合は、QMC の使用をお勧めします。 同じ試行回数であれば、点が密集しない分だけ空間を広く覆えるためです。

Halton と Sobol' の使い分けについては、sobol は一定の間隔を保ちながらより多くの変数でサンプリングできるという特徴があります。

ですが、Sobol' は 2 のべき乗までサンプリングした場合に低差異列となるアルゴリズムであるため、2 のべき乗までサンプリングできない場合は Halton を使用するとよいでしょう。 たとえば上の図では 256 個、すなわち 2 の 8 乗の点をサンプリングしているので、Sobol' がもっともきれいに散らばる条件を満たしています。

次に、Random を使うべき場面を見てみましょう。

Random は、たとえば目的関数が短い範囲内でジグザグに変化する可能性がある場合に有用です。 上で説明したように、QMC は低差異性を持つため、観測点間の間隔は常に一定です。 そのため、短い範囲内でのジグザグの変化が観測できない場合があります。

Tunny では、同じ study 内で変数の範囲を変更できます。 そのため、たとえば QMC で study 全体をまず確認し、その後 Number スライダーの範囲を変更して、より詳しく見たい領域だけを Random でサンプリングするといったことが可能です。 この機能を使うことで、単純な最適化を行うだけでなく、解空間についてより詳細な理解を得ることもできます。

いつ使うべきか

TPE と GP のセクションで述べたように、これらの SMBO（Sequential Model-Based Global Optimization、逐次モデルベース大域最適化）は、最適化対象の形状を事前にある程度把握しておく必要があるため、事前に Random を使用します。

これを知っておくべきなのは SMBO だけではありません。 最適化を実行する際には、あなた自身も、設定した Number スライダーの範囲内に求める解が存在しそうかどうかを事前に把握しておくべきです。 範囲の外に本当の最適解がある場合、最適化はその範囲のなかでの最良解を返すだけで、範囲の設定が誤っていたことは結果からはわかりません。 Random と QMC は、これを実現するために使用されます。

解空間がどの手法によってどのように把握できるかの例として、Random、QMC、TPE でそれぞれ 512 回サンプリングした結果を以下に示します。

Random

QMC(Sobol')

TPE

これらの図からは、目的関数の形状をある程度読み取ることができます。

この関数は Ackley 関数と呼ばれ、以下の式で表されます。

# Ackley function
Z = -20*exp(-0.2*sqrt(0.5*(X^2 + Y^2))) - exp(0.5*(cos(2*pi*X) + cos(2*pi*Y))) + exp(1) + 20

確かに TPE は、大域最適解である (0,0) で 0 に近い値を取ることで、この問題を適切に解いています。

ですが、目的関数の形状は他の手法ほど明確にはわかりません。 TPE は良い値が期待できる領域に点を集めていくことで、それ以外の領域には点がほとんど残らないためです。 一方 QMC の結果は、空間全体に点が散っているため、実際の形状に非常に近いことがわかります。

上の例が示すように、最適化では最良の解しかわかりません。 Random と QMC は、真の最適解を把握できない場合があります。 ですが、結果を注意深く分析することで、最適化よりも多くの情報を得られる可能性があります。

たとえば、上の例をもう一度使ってみましょう。 z の値が 2 以下の範囲が必要だとします。 最適化だけでは、(0, 0) 付近でおよそ 0 になることしかわかりません。

ですが、Random と QMC を使うことで、-0.5 から 0.5 の範囲が 2 以下であることがわかります。 つまり、-0.5 から 0.5 の範囲がこの設計に使用可能であることがわかり、(0,0) 周辺の範囲を自分で改めて探索する必要がなくなります。 最適解の一点だけを渡されるよりも、許容できる範囲がわかっているほうが、設計を進めるうえでは扱いやすい場合もあります。

Reference

• scipy.stats.qmc
  • Tunny は QMC の計算に Python ライブラリである Scipy を使用しています。
• Low-discrepancy sequence
• Bergstra, James, and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research 13.2, 2012.