ボルツマンサンプラー

ボルツマンサンプラーは、組み合わせ構造のランダムサンプリングを目的としたアルゴリズムです。オブジェクトのサイズをそのエネルギーと見なし、対応する生成関数の引数を物理システムの温度の観点から解釈すると、ボルツマンサンプラーは古典的なボルツマン分布からオブジェクトを返します。

ボルツマンサンプラーの概念は、2004年にフィリップ・デュション、フィリップ・フラジョレ、ガイ・ルシャール、ジル・シェッファーによって提案されました。 ^[1]

ボルツマンサンプリングの概念は、組合せ論における記号的方法と密接に関連しています。を、収束半径がゼロでない、つまり複素解析的な通常の生成関数を持つ組合せクラスとします。正式に言えば、各オブジェクトが 非負の整数サイズを備えている場合、生成関数は次のように定義されます。 ${\displaystyle {\mathcal {C}}}$ ${\displaystyle C(z)}$${\displaystyle \rho}$${\displaystyle c\in {\mathcal {C}}}$ ${\displaystyle \omega (c)}$${\displaystyle C(z)}$

${\displaystyle C(z)=\sum _{c\in {\mathcal {C}}}z^{\omega (c)}=\sum _{n=0}^{\infty }a_{n} z^{n},}$

ここで、 はサイズ のオブジェクトの数を表します。サイズ関数は通常、ツリーまたはグラフ内の頂点の数、単語内の文字数などを表すために使用されます。 ${\displaystyle a_{n}}$${\displaystyle c\in {\mathcal {C}}}$${\displaystyle n}$

クラスのボルツマンサンプラーは、 と表され 、 確率${\displaystyle {\mathcal {C}}}$${\displaystyle z}$${\displaystyle 0<z<\rho }$${\displaystyle \Gamma {\mathcal {C}}(z)}$${\displaystyle c\in {\mathcal {C}}}$

${\displaystyle \mathbb {P} (\Gamma {\mathcal {C}}(z)=c)={\dfrac {z^{\omega (c)}}{C(z)}}.}$

が有限である場合、要素はに比例する確率で抽出されます。 ${\displaystyle {\mathcal {C}}=\{c_{1},\ldots ,c_{r}\}}$${\displaystyle c_{j}}$${\displaystyle z^{\omega (c_{j})}}$

対象クラスが他の2つのクラスの互いに素な和集合であり、およびの生成関数とが既知である場合、に対するボルツマンサンプラーは次のように得られる。 ${\displaystyle {\mathcal {C}}={\mathcal {A}}+{\mathcal {B}}}$${\displaystyle A(z)}$${\displaystyle B(z)}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {C}}}$

${\displaystyle \left(\operatorname {Bern} \left({\frac {A(z)}{C(z)}}\right)\longrightarrow \Gamma {\mathcal {A}}(z)\mid \Gamma {\mathcal {B}}(z)\right)}$

ここで、 は「ランダム変数が 1 の場合は を実行し、それ以外の場合は を実行する」を表します。より一般的には、分離した和集合が有限集合上で取られる場合、結果として得られるボルツマン サンプラーは、生成関数の値に比例する確率を持つランダム選択を使用して表すことができます。 ${\displaystyle (X\longrightarrow f\mid g)}$${\displaystyle X}$${\displaystyle f}$${\displaystyle g}$

が、およびの順序付きペアから構成されるクラスである場合、対応するボルツマンサンプラーは次のように得られる。 ${\displaystyle {\mathcal {C}}={\mathcal {A}}\times {\mathcal {B}}}$${\displaystyle (a,b)}$${\displaystyle a\in {\mathcal {A}}}$${\displaystyle b\in {\mathcal {B}}}$${\displaystyle \Gamma {\mathcal {C}}(z)}$

${\displaystyle \Gamma {\mathcal {C}}(z)=(\Gamma {\mathcal {A}}(z),\Gamma {\mathcal {B}}(z)),}$

つまり、と を、 およびから独立して描画してペアを形成することによって。 ${\displaystyle (a,b)}$${\displaystyle a}$${\displaystyle b}$${\displaystyle \Gamma {\mathcal {A}}(z)}$${\displaystyle \Gamma {\mathcal {B}}(z)}$

が、要素のサイズから加算的に継承されたシーケンスのサイズを持つの要素の有限シーケンスすべてで構成されている場合、 の生成関数は と表現されます 。ここで、は の生成関数です。 あるいは、 クラスは再帰表現を許可します。これにより、 には 2 つの可能性があります。 ${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle C(z)=\sum _{k=0}^{\infty }A(z)^{k}={\dfrac {1}{1-A(z)}}}$${\displaystyle A(z)}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {C}}=1+{\mathcal {A}}\times {\mathcal {C}}.}$${\displaystyle \Gamma {\mathcal {C}}(z)}$

1. ${\displaystyle \Gamma {\mathcal {C}}(z)=\Gamma (1+{\mathcal {A}}\times {\mathcal {C}})(z)=\left(\operatorname {Bern} \left({\frac {1}{C(z)}}\right)\longrightarrow 1\,{\Big |}\,(\Gamma {\mathcal {A}}(z),\Gamma {\mathcal {C}}(z))\right)}$
2. ${\displaystyle \Gamma {\mathcal {C}}(z)=\left(\operatorname {Geom} (A(z))\Longrightarrow \Gamma {\mathcal {C}}(z)\right)}$

ここで、は「ランダム変数を描画し、値が返された場合は独立して回実行し、得られたシーケンスを返す」を表します。ここで、は幾何分布を表します。 ${\displaystyle (X\Longrightarrow f)}$${\displaystyle X}$${\displaystyle X=x}$${\displaystyle f}$${\displaystyle x}$${\displaystyle \operatorname {Geom} (p)}$${\displaystyle \mathbb {P} (\operatorname {Geom} (p)=k)=p^{k}(1-p)}$

シーケンス演算子の最初の構成が示唆するように、ボルツマンサンプラーは再帰的に使用できます。ターゲットクラスがシステムの一部である 場合${\displaystyle {\mathcal {C}}}$

${\displaystyle {\begin{cases}{\mathcal {C}}_{1}=\Phi _{1}({\mathcal {C}}_{1},\ldots ,{\mathcal {C}}_{n},{\mathcal {Z}}),\\\qquad \vdots \\{\mathcal {C}}_{n}=\Phi _{n}({\mathcal {C}}_{1},\ldots ,{\mathcal {C}}_{n},{\mathcal {Z}}),\end{cases}}}$

ここで、各式には分離和、直積、およびシーケンス演算子のみが含まれるため、対応するボルツマンサンプラーは明確に定義されます。引数値が与えられた場合、生成関数の数値はニュートン反復によって取得できます。^[2]${\displaystyle \Phi _{k}({\mathcal {C}}_{1},\ldots ,{\mathcal {C}}_{n},{\mathcal {Z}})}$${\displaystyle z}$

ボルツマンサンプリングはラベル付き構造に適用できます。ラベル付きの組み合わせクラスの場合、代わりに指数生成関数が使用されます。 ${\displaystyle {\mathcal {C}}}$

${\displaystyle C(z)=\sum _{c\in {\mathcal {C}}}{\dfrac {z^{\omega (c)}}{\omega (c)!}}=\sum _{n=0}^{\infty }a_{n}{\dfrac {z^{n}}{n!}},}$

ここで、 はサイズ のラベル付きオブジェクトの数を表します。直積とシーケンスの演算はラベル付けを考慮して調整する必要があり、構築の原則は同じままです。 ${\displaystyle a_{n}}$${\displaystyle c\in {\mathcal {C}}}$${\displaystyle n}$

ラベル付きの場合、ラベル付きクラスのボルツマンサンプラーは、確率で オブジェクトを出力する必要がある。${\displaystyle {\mathcal {C}}}$${\displaystyle c\in {\mathcal {C}}}$

${\displaystyle \mathbb {P} (\Gamma {\mathcal {C}}(z)=c)={\frac {1}{C(z)}}{\frac {z^{\omega (c)}}{\omega (c)!}}.}$

ラベル付けされた宇宙では、クラスは、順序一貫性のある再ラベル付けを持つクラスのすべての有限要素集合から構成されます。この場合、クラスの指数生成関数は次のように記述されます。 ${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {C}}}$

${\displaystyle C(z)=\sum _{k=0}^{\infty }{\dfrac {A(z)^{k}}{k!}}=e^{A(z)}}$

ここで はクラスの指数生成関数である。 のボルツマンサンプラーは次のように記述できる。 ${\displaystyle A(z)}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {C}}}$

${\displaystyle \Gamma {\mathcal {C}}(z)=\left(\operatorname {Poisson} (A(z))\Longrightarrow \Gamma {\mathcal {C}}(z)\right)}$

ここで は標準ポアソン分布を表します。 ${\displaystyle \operatorname {Poisson} (\lambda )}$ ${\displaystyle \mathbb {P} (\operatorname {Poisson} (\lambda )=k)=e^{-\lambda }{\dfrac {\lambda ^{k}}{k!}}}$

巡回構成では、クラスはクラスの要素の有限シーケンスすべてから構成され、2つのシーケンスは巡回シフトによって得られる場合は同等であるとみなされます。クラスの指数生成関数は次のように記述されます。 ${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {C}}}$

${\displaystyle C(z)=\sum _{k=0}^{\infty }{\frac {A(z)^{k}}{k}}=\log {\frac {1}{1-A(z)}}}$

ここで はクラスの指数生成関数である。 のボルツマンサンプラーは次のように記述できる。 ${\displaystyle A(z)}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {C}}}$

${\displaystyle \Gamma {\mathcal {C}}(z)=\left(\operatorname {Loga} (A(z))\Longrightarrow \Gamma {\mathcal {C}}(z)\right)}$

ここで、 は対数分布を表します。 ${\displaystyle \operatorname {Loga} (\lambda )}$ ${\displaystyle \mathbb {P} (\operatorname {Loga} (\lambda )=k)={\dfrac {1}{\log(1-\lambda )^{-1}}}{\dfrac {\lambda ^{k}}{k}}}$

から生成されたオブジェクトのランダムなサイズを とします。すると、サイズは第1および第2のモーメントを満たします。 ${\displaystyle N}$${\displaystyle \Gamma {\mathcal {C}}(z)}$

1. ${\displaystyle \mathbb {E} _{z}(N)=z{\dfrac {C'(z)}{C(z)}};}$
2. ${\displaystyle \mathbb {E} _{z}(N^{2})={\dfrac {z^{2}C''(z)+zC'(z)}{C(z)}};}$
3. ${\displaystyle z{\dfrac {d}{dz}}\mathbb {E} _{z}(N)=\operatorname {Var} _{z}(N)}$。

二分木のクラスは再帰的な仕様によって定義できる。 ${\displaystyle {\mathcal {B}}}$

${\displaystyle {\mathcal {B}}={\mathcal {Z}}+{\mathcal {Z}}\times {\mathcal {B}}\times {\mathcal {B}}}$

そしてその生成関数は方程式を満たし 、二次方程式の解として評価できる。 ${\displaystyle B(z)}$${\displaystyle B(z)=z+zB(z)^{2}}$

${\displaystyle B(z)={\dfrac {1-{\sqrt {1-4z^{2}}}}{2z}}}$

結果として得られるボルツマンサンプラーは、次のように再帰的に記述できる。

${\displaystyle \Gamma {\mathcal {B}}(z)=\left(\operatorname {Bern} \left({\frac {z}{B(z)}}\right)\longrightarrow {\mathcal {Z}}\mid \left({\mathcal {Z}},\,\Gamma {\mathcal {B}}(z),\,\Gamma {\mathcal {B}}(z)\right)\right)}$

集合をいくつかの空でないクラスに分割し、それらのクラス同士が無秩序になるようにする。記号的方法を用いると、集合分割のクラスは次のように表現できる。 ${\displaystyle \{1,2,\ldots ,n\}}$${\displaystyle {\mathcal {C}}}$

${\displaystyle {\mathcal {C}}=\operatorname {Set} (\operatorname {Set} _{>0}({\mathcal {Z}})).}$

対応する生成関数は に等しい。したがって、ボルツマンサンプラーは次のように記述できる。 ${\displaystyle C(z)=e^{e^{z}-1}}$

${\displaystyle \Gamma {\mathcal {C}}=\left(\operatorname {Poisson} (e^{z}-1)\Longrightarrow \left(\operatorname {Poisson} _{>0}(z)\Longrightarrow {\mathcal {Z}}\right)\right),}$

ここで、正のポアソン分布は、正の値のみを取るように条件付けられたパラメータを持つポアソン分布です。 ${\displaystyle \operatorname {Poisson} _{>0}(\lambda )}$${\displaystyle \lambda }$

Philippe Duchon、 Philippe Flajolet、Guy Louchard、Gilles Schaeffer ^[1]によって記述されたオリジナルのボルツマンサンプラーは、分離和、直積、シーケンスという基本的なラベルなし演算と、ラベル付きクラスに対するセットとサイクルの構築という 2 つの追加演算のみをサポートしています。それ以来、ボルツマンサンプラーを構築できる組み合わせクラスの範囲は拡大しました。

ラベルなしクラスに対して許容される演算には、 Multiset、Cycle、Powersetなどの追加の演算が含まれます。これらの演算のためのボルツマンサンプラーは、 Philippe Flajolet 、Éric Fusy、Carine Pivoteauによって説明されています。^[3]

をラベル付きの組み合わせクラスとします。微分演算は次のように定義されます。ラベル付きオブジェクトを取り、最大のラベルを持つ原子をラベルのない区別された原子に置き換えます。これにより、結果のオブジェクトのサイズが1だけ小さくなります。がクラス の指数生成関数である場合、微分クラスの指数生成関数は次のように与えられます。微分仕様は、タイプの再帰仕様です。 ${\displaystyle {\mathcal {C}}}$${\displaystyle c\in {\mathcal {C}}}$${\displaystyle C(z)=\sum _{n=0}^{\infty }a_{n}{\dfrac {z^{n}}{n!}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {C}}'}$$${\displaystyle C'(z)={\dfrac {d}{dz}}C(z)=\sum _{n=0}^{\infty }na_{n}{\frac {z^{n-1}}{n!}}}$$

${\displaystyle {\mathcal {T}}'=\Phi ({\mathcal {T}},{\mathcal {Z}})}$

ここで、式には、和、積、数列、循環、集合の標準的な演算のみが含まれ、微分は含まれません。 ${\displaystyle \Phi ({\mathcal {T}},{\mathcal {Z}})}$

微分仕様のためのボルツマンサンプラーは、オリヴィエ・ボディニ、オリヴィエ・ルーセル、ミシェル・ソリアによって構築されました。^[4]

マルチパラメトリックな組み合わせクラスのマルチパラメトリックなボルツマン分布は、古典的な場合と同様に定義されます。各オブジェクトには、負でない整数のベクトルである合成サイズが備わっているものとします。各サイズ関数は、ツリー内の特定の色の葉の数、ツリーの高さなど、データ構造のパラメータの1つを反映できます。対応する多変量生成関数は、マルチパラメトリッククラスに関連付けられ、次のように定義されます。 の解析ドメイン内のベクトルパラメータを持つマルチパラメトリッククラスのボルツマンサンプラーは、次のように表されます。${\displaystyle c\in {\mathcal {C}}}$${\displaystyle \omega (c)=(\omega _{1}(c),\ldots ,\omega _{d}(c))}$${\displaystyle \omega _{j}(c)}$ ${\displaystyle C(z_{1},\ldots ,z_{d})}$$${\displaystyle C(z_{1},\ldots ,z_{d})=\sum _{c\in {\mathcal {C}}}z_{1}^{\omega _{1}(c)}\cdots z_{d}^{\omega _{d}(c)}.}$$${\displaystyle {\mathcal {C}}}$${\displaystyle {\boldsymbol {z}}=(z_{1},\ldots ,z_{d})}$${\displaystyle C(z_{1},\ldots ,z_{d})}$

${\displaystyle \Gamma {\mathcal {C}}(z_{1},\ldots ,z_{d})}$確率で オブジェクトを返す${\displaystyle c\in {\mathcal {C}}}$

${\displaystyle \mathbb {P} (\Gamma {\mathcal {C}}(z_{1},\ldots ,z_{d})=c)={\frac {z_{1}^{\omega _{1}(c)}\cdots z_{d}^{\omega _{d}(c)}}{C(z_{1},\ldots ,z_{d})}}.}$

マルチパラメトリックボルツマンサンプラーは、オリヴィエ・ボディーニとヤン・ポンティによって構築されました。^[5]目標パラメータの期待値が与えられた場合にパラメータの数値を見つける多項式時間アルゴリズムは、補助凸最適化問題を定式化することによって得られます^[6]${\displaystyle z_{1},\ldots ,z_{d}}$

ボルツマンサンプリングは、プロパティベースのテストのために代数データ型を生成するために使用できます。^[7]

• ランダム離散オブジェクト スイート (RDOS) : http://lipn.fr/rdos/
• Maple のCombstructパッケージ: https://www.maplesoft.com/support/help/Maple/view.aspx?path=combstruct
• Haskell パッケージBoltzmann Brain : https://github.com/maciej-bendkowski/boltzmann-brain