アルゴリズム Lovász 局所補題

理論計算機科学において、アルゴリズム的ロヴァース局所補題は、依存性が制限された制約システムに従うオブジェクトを構築するアルゴリズム的な方法を提供します。

確率空間において、A _i間の依存関係が限定され_、それぞれの確率に特定の上限が_与えられた場合、ロヴァースの局所補題は、これらの事象すべてが非ゼロ確率で回避可能であることを証明する。しかし、この補題は非構成的であり、悪い事象を回避する 方法について何ら示唆を与えない。

イベント{ A1 _、 ...、An }が相互に独立したランダム変数の有限集合によって決定される場合、 Robin MoserとGábor Tardos ^{[1]によって提案された}_、期待される多項式実行時間を持つ単純なラスベガスアルゴリズムは、すべてのイベントが回避されるようにランダム変数への割り当てを計算できます。

ロヴァースの局所補題の復習

ロヴァース局所補題は、確率的手法において、規定された一連の特徴を持つ特定の複雑な数学的対象の存在を証明するために一般的に用いられる強力なツールです。典型的な証明は、複雑な対象にランダムな方法で作用させ、ロヴァース局所補題を用いて、特徴のいずれかが欠落する確率を制限します。特徴の欠落は悪い事象​​とみなされ、そのような悪い事象が全て非ゼロの確率で同時に回避できることが示されれば、その対象の存在が証明されます。補題自体は以下の通りです。

確率空間Ωにおける事象の有限集合を とする。 を の部分集合とし、事象の集合とは独立とする。事象に 実数を割り当てて、${\displaystyle {\mathcal {A}}=\{A_{1},\ldots ,A_{n}\}}$ ${\displaystyle A\in {\mathcal {A}}}$ ${\displaystyle \Gamma (A)}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle A}$ ${\displaystyle {\mathcal {A}}\setminus (\{A\}\cup \Gamma (A))}$ ${\displaystyle x:{\mathcal {A}}\rightarrow (0,1)}$

${\displaystyle \forall A\in {\mathcal {A}}:\Pr[A]\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B))}$

全ての事象を回避する確率は正であり、特に ${\displaystyle {\mathcal {A}}}$

${\displaystyle \Pr \left[\,{\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\,\right]\geq \prod _{A\in {\mathcal {A}}}(1-x(A)).}$

Lovász 局所補題のアルゴリズム バージョン

ロヴァースの局所補題は非構成的である。なぜなら、構造的特性や複雑な物体の存在を結論づけることはできるが、実際にそれらを効率的に発見したり構築したりする方法を示さないからである。確率空間Ωからのランダムサンプリングは、関心のある事象の確率が

${\displaystyle \Pr \left[{\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right]}$

小さな数の積によってのみ制限される

${\displaystyle \prod _{A\in {\mathcal {A}}}(1-x(A))}$

したがって、非常に小さくなる可能性が高いです。

におけるすべてのイベントはΩ 内の相互に独立したランダム変数の有限集合によって決定されるという仮定の下で、Robin Moser とGábor Tardos は、におけるすべてのイベントが回避されるように、におけるランダム変数への割り当てを計算する効率的なランダム化アルゴリズムを提案しました。 ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {A}}}$

したがって、このアルゴリズムは、ロヴァース局所補題が適用されるほとんどの問題に対して、規定された特徴を持つ複雑なオブジェクトの証拠を効率的に構築するために使用できます。

歴史

モーザーとタルドスによる最近の研究に先立ち、ロヴァースの局所補題のアルゴリズム版の開発においても進展が見られました。 ヨージェフ・ベックは1991年に初めてアルゴリズム版が可能であることを証明しました。^[2]この画期的な結果により、問題の定式化には、元の非構成的定義よりも厳しい要件が課されました。ベックのアプローチでは、各 に対して、 Aの依存関係の数が（近似的に）以上で有界であることが要求されました。局所補題の存在版では、依存関係の上限がより大きくなります。 ${\displaystyle A\in {\mathcal {A}}}$ ${\displaystyle |\Gamma (A)|<2^{n/48}}$

${\displaystyle |\Gamma (A)|<{\frac {2^{n}}{e}},}$

この上界は厳密であることが知られています。最初のアルゴリズム以来、局所補題のアルゴリズム版をこの厳密な値に近づけるための研究が行われてきました。MoserとTardosによる最近の研究は、この一連の研究の中で最も新しいものであり、この厳密な上界を達成するアルゴリズムを提供しています。

アルゴリズム

まず、アルゴリズムで使用されるいくつかの概念を紹介します。

任意の確率変数について、 はPの現在の割り当て（評価）を表します。すべての確率変数への割り当て（評価）は で表されます。 ${\displaystyle P\in {\mathcal {P}},v_{P}}$ ${\displaystyle (v_{P})_{\mathcal {P}}}$

イベントAを決定するランダム変数の一意の最小サブセットはvbl( A )で表されます。 ${\displaystyle {\mathcal {P}}}$

イベントAが評価において真である場合、 はA を満たすと言い、そうでない場合はAを回避します。 ${\displaystyle (v_{P})_{\mathcal {P}}}$ ${\displaystyle (v_{P})_{\mathcal {P}}}$

相互に独立したランダム変数の集合によって決定される、回避したい一連の悪いイベントが与えられた場合、アルゴリズムは次のように進行します。 ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {P}}}$

1. ${\displaystyle \forall P\in {\mathcal {P}}}$ : Pのランダム評価${\displaystyle v_{P}\leftarrow }$
2. 一方 、Aは${\displaystyle \exists A\in {\mathcal {A}}}$ ${\displaystyle (v_{P})_{\mathcal {P}}}$
   • 任意の満足イベントを選択する${\displaystyle A\in {\mathcal {A}}}$
   • ${\displaystyle \forall P\in {\text{vbl}}(A)}$ : Pの新しいランダム評価${\displaystyle v_{P}\leftarrow }$
3. 戻る ${\displaystyle (v_{P})_{\mathcal {P}}}$

最初のステップでは、アルゴリズムは各確率変数に対して現在の割り当てv _{P を}ランダムに初期化します。これは、割り当てv _{P が}確率変数Pの分布に従ってランダムかつ独立にサンプリングされることを意味します。 ${\displaystyle P\in {\mathcal {P}}}$

次にアルゴリズムはメインループに入り、すべてのイベントが回避されるまで実行され、回避された時点で現在の割り当てが返されます。メインループの各反復において、アルゴリズムは任意の満たされたイベントA を（ランダムまたは決定論的に）選択し、 A を決定するすべての確率変数を再サンプリングします。 ${\displaystyle {\mathcal {A}}}$

主定理

確率空間Ωにおける互いに独立な確率変数の有限集合をとする。これらの変数によって決定される事象の有限集合をとする。事象に 実数の割り当てが存在し、${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle x:{\mathcal {A}}\to (0,1)}$

${\displaystyle \forall A\in {\mathcal {A}}:\Pr[A]\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B))}$

内のすべてのイベントを回避する変数への値の割り当てが存在します。 ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {A}}}$

さらに、上記のランダム化アルゴリズムは、イベントを最大で期待値で 再サンプリングします。${\displaystyle A\in {\mathcal {A}}}$

${\displaystyle {\frac {x(A)}{1-x(A)}}}$

このような評価を見つけるまでに、何回も繰り返す必要がある。したがって、予想される再サンプリングステップの総数、ひいてはアルゴリズムの予想される実行時間は、最大で

${\displaystyle \sum _{A\in {\mathcal {A}}}{\frac {x(A)}{1-x(A)}}.}$

エントロピー圧縮法を用いたこの定理の証明は、モーザーとタルドスの論文^{[1]に記載されている。}

対称バージョン

上記の定理において、割当関数x が不等式の集合を満たすという 要件は複雑で直感的ではありません。しかし、この要件は3つの単純な条件に置き換えることができます。

• ${\displaystyle \forall A\in {\mathcal {A}}:|\Gamma (A)|\leq D}$ つまり、各イベントAは最大D個の他のイベントに依存し、
• ${\displaystyle \forall A\in {\mathcal {A}}:\Pr[A]\leq p}$ つまり、各イベントAの確率は最大でpであり、
• ${\displaystyle ep(D+1)\leq 1}$ ここで、eは自然対数の底です。

割り当て関数xの代わりにこれらの3つの条件を適用したロヴァース局所補題は、対称ロヴァース局所補題と呼ばれます。また、対称アルゴリズム的ロヴァース局所補題も次のように表すことができます。

を互いに独立な確率変数の有限集合とし、を前述のようにこれらの変数によって決定される事象の有限集合とします。上記の3つの条件が満たされる場合、内のすべての事象を回避するような変数への値の割り当てが存在する。 ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {A}}}$

さらに、上述のランダム化アルゴリズムは、そのような評価値を見つけるまでに、イベントを最大で期待回数だけ再サンプリングします。したがって、再サンプリングステップの期待総数、ひいてはアルゴリズムの期待実行時間は最大で となります。 ${\displaystyle A\in {\mathcal {A}}}$ ${\displaystyle {\frac {1}{D}}}$ ${\displaystyle {\frac {n}{D}}}$

例

次の例は、Lovász の局所補題のアルゴリズム バージョンを単純な問題に適用する方法を示しています。

Φ を変数X ₁ , ..., X _n上のCNF式とし、 n個の節を含み、各節には少なくともk個のリテラルがあり、各変数X _{i は}最大で個の節に出現するとする。このとき、Φ は充足可能である。 ${\displaystyle {\frac {2^{k}}{ke}}}$

この命題は、アルゴリズム的ロヴァース局所補題の対称版を用いて簡単に証明できます。X 1 _, ..., X _{n を}、一様ランダムにサンプリングされた互いに独立な確率変数の集合とします。 ${\displaystyle {\mathcal {P}}}$

まず、Φ の各節を切り捨てて、ちょうどk個のリテラルを含むようにします。各節は選言であるため、これは充足可能性を損なうものではありません。なぜなら、切り捨てられた式に対する充足割り当てが見つかれば、切り捨てられたリテラルを再挿入することで、元の式に対する充足割り当てに容易に拡張できるからです。

ここで、 Φ の各節に対して、悪いイベントA _{jを定義します。A j}は、 Φ の節jが現在の割り当てによって満たされないイベントです。各節にはk個のリテラル（したがってk個の変数）が含まれており、すべての変数は一様にランダムにサンプリングされるため、各悪いイベントの確率は次のように制限されます。

${\displaystyle \Pr[A_{j}]=p=2^{-k}.}$

各変数は最大で節に出現でき、各節にはk個の変数があるため、各不良イベントA _{j は}最大で ${\displaystyle {\frac {2^{k}}{ke}}}$

${\displaystyle D=k\left({\frac {2^{k}}{ke}}-1\right)\leq {\frac {2^{k}}{e}}-1}$

その他のイベント。したがって、

${\displaystyle D+1\leq {\frac {2^{k}}{e}},}$

両辺にepを掛けると次のようになります。

${\displaystyle ep(D+1)\leq e2^{-k}{\frac {2^{k}}{e}}=1}$

対称的なロヴァースの局所補題により、Φ のすべての節を満たすX ₁、...、X _nへのランダム割り当ての確率はゼロでないため、そのような割り当てが存在する必要があることがわかります。

さて、アルゴリズム的ロヴァース局所補題は、上記のアルゴリズムを適用することで、このような割り当てを効率的に計算することを可能にします。アルゴリズムは以下のように進行します。

このアルゴリズムは、一様ランダムに抽出された変数X ₁ , ..., X _nにランダムな真理値を割り当てることから始まる。Φ に満たされていない節が存在する場合、Φ から満たされていない節C をランダムに選び、 Cに現れる一様ランダムに選ばれたすべての変数に新しい真理値を割り当てる。Φ のすべての節が満たされると、アルゴリズムは現在の割り当てを返す。したがって、アルゴリズム的ロヴァース局所補題は、このアルゴリズムの期待実行時間が最大で

${\displaystyle {\frac {n}{{\frac {2^{k}}{e}}-k}}}$

上記の2つの条件を満たすCNF式に関するステップ。上記の命題のより強いバージョンはMoserによって証明されている^[3]。また、Berman、Karpinski、Scottも参照のこと^{[4] 。}

このアルゴリズムは、一般的なブール充足可能性問題を解くために使用されるWalkSATに似ています。主な違いは、WalkSATでは、充足されていない節Cが選択された後、 C内の単一の変数がランダムに選択され、その値が反転されることです（これは、 Cへのすべての値割り当てではなく、唯一の値割り当て から均一に選択すると考えることができます）。 ${\displaystyle k}$ ${\displaystyle 2^{k}}$

アプリケーション

前述のように、ロヴァース局所補題のアルゴリズム版は、一般のロヴァース局所補題が証明技法として用いられるほとんどの問題に適用されます。これらの問題のいくつかは、以下の記事で議論されています。

• 非確率定理の確率的証明
• ランダムグラフ

パラレルバージョン

上記のアルゴリズムは並列化に適しています。2つの独立したイベント、すなわち を並列にリサンプリングすることは、AとB を順にリサンプリングすることと等価だからです。したがって、メインループの各反復処理において、独立かつ条件を満たすイベントの最大集合Sを決定し、 S内のすべてのイベントを並列にリサンプリングすることができます。 ${\displaystyle A,B\in {\mathcal {A}}}$ ${\displaystyle \operatorname {vbl} (A)\cap \operatorname {vbl} (B)=\emptyset }$

割り当て関数xがやや強い条件を満たすという仮定の下では、

${\displaystyle \forall A\in {\mathcal {A}}:\Pr[A]\leq (1-\varepsilon )x(A)\prod _{B\in \Gamma (A)}(1-x(B))}$

モーザーとタルドスは、あるε > 0に対して並列アルゴリズムの方が実行時間の計算量が少ないことを証明した。この場合、アルゴリズムの並列版は期待される

${\displaystyle O\left({\frac {1}{\varepsilon }}\log \sum _{A\in {\mathcal {A}}}{\frac {x(A)}{1-x(A)}}\right)}$

終了するまでにステップ数だけ実行します。このアルゴリズムの並列版は、上記に示した逐次アルゴリズムの特殊なケースと見なすことができるため、この結果は逐次アルゴリズムの場合にも当てはまります。

参考文献

1. モーザー、ロビン A.;タルドス、ガボール (2010)。 「一般ロヴァシュ局所補題の建設的な証明」。ACM のジャーナル。57 (2): 1. arXiv : 0903.0544。土井：10.1145/1667053.1667060。S2CID  2813462。
2. Beck、József (1991)、「Lovász Local Lemma へのアルゴリズム的アプローチ。I」、Random Structures and Algorithms、2 (4): 343–366、doi :10.1002/rsa.3240020402。
3. モーザー、ロビン A. (2008)。 「ロヴァシュ局所補題の建設的な証明」。arXiv : 0810.4812 [cs.DS]。。
4. Piotr Berman、Marek Karpinski、Alexander D. Scott、「SAT の制限付き発生インスタンスの近似困難性と充足可能性」、ECCC TR 03-022 (2003)。