Tunny Icon
TunnyDocs

The next-gen Grasshopper optimization tool.

Random & QMC

Random & Quasi-Monte Carlo

Tunny は、ベイズ最適化や遺伝的アルゴリズムなどの最適化アルゴリズムだけでなく、単純にランダムを使ってサンプリングする Random Sampler と QMC Sampler も提供しています。
このセクションでは、これらが Tunny に存在する理由と、どのような場合に必要になるかを、技術的な詳細も含めて説明します。

両者の違い

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

Tunny の Quasi-MonteCarlo サンプラーは 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 の使用をお勧めします。
Halton と Sobol' の使い分けについては、sobol は一定の間隔を保ちながらより多くの変数でサンプリングできるという特徴があります。ただし、Sobol' は 2 のべき乗までサンプリングした場合に低差異列となるアルゴリズムであるため、2 のべき乗までサンプリングできない場合は Halton を使用するとよいでしょう。

次に、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 に近い値を取ることで、この問題を適切に解いています。しかし、目的関数の形状は他の手法ほど明確には分かりません。
QMC の結果は実際の形状に非常に近いことが分かります。

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

例えば、上の例をもう一度使ってみましょう。z の値が 2 以下の範囲が必要だとします。最適化だけでは、(0, 0) 付近でおよそ 0 になることしか分かりません。しかし、Random と QMC を使うことで、-0.5 から 0.5 の範囲が 2 以下であることが分かります。つまり、-0.5 から 0.5 の範囲がこの設計に使用可能であることが分かり、(0,0) 周辺の範囲を自分で改めて探索する必要がなくなります。

Reference

← 前へ技術情報: CMA-ES