(講義ノート)乱択アルゴリズム第4回

$S_i$ は $i$ 番目の節を充足する解の集合
推定したいのは $A = |\bigcup_{i=1}^m S_i |$ である。ORなのでいずれかの $S_i$ に入れば解である。
$|S_i| = 2^{n - l_i}$ 。 $l_i$ は $S_i$ のリテラルの個数。
- 全体で $n$ 個の変数がある中で、 $i$ 番目の節を充足するのは、節の中の $l_i$ の変数からなる1通りの配置だけ。その節の外はどうなろうが問題ないので、任意に配置していい。
$B = \sum_{i=1}^m |S_i|$ は単純に加算すればいいので簡単である。

ここで、 $A / B \in[0, 1]$ を推定することを考える。

https://users.soe.ucsc.edu/~sesh/Teaching/2020/CSE290A/Slides/Lecture4.pdf

for j in [1, t]: 
		節iを確率|Si|/Bで選ぶ。(ここで重点サンプリング)
		節iを充足する解xを選ぶ。(節に含まれない変数は一様にランダムに決める)
		あるkがあって、k < iでxが節kをみたすのならばX_j=0
		それ以外ならばX_j=1

(sum(X, [1, t]))/tがA/Bの推定値

節 $i$ 以外の $i$ 以前の節に対して、ランダムにとってきた割り当てが何かしらの節の解であるなら0になり、1は他の解ではないということ。今の節を満たす解だが、以前のどの他の節の解ではないのならば、排他的で集合として純粋に足してよいといういい性質があり、それの和をAとして近似する。

推定値に $B$ を乗じると、Aの推定値 $y$ になる。

高い確率で $y$ が $A$ の $1 \pm \epsilon$ 近似であるの証明

ここでの高い確率は $2/3$ であるとする。

集合 $P$ は $(x,i)$ を元としてとり、解 $x$ は節 $i$ を充足することが集合に入る条件。よって下式が成り立つ。

|P| = \sum_{i=1}^m |S_i|=B

お気持ちとしては、 $x$ を充足する節の中で、indexが最小のものに割り当てる(お互い排他的になれないなら一番小さいindexに割り当てる)=「良い割り当て」。 $P$ のうちの $(x,i)$ がが何個その割り当てに対応しているか？それが $A$ の割合となるといいね。

証明は以下の通り。

$x, i$ をまず固定する。この時、「 $x, i$ がサンプリングされる確率」は、ベイズの定理から「 $i$ がサンプリングされる確率」と「 $i$ がサンプリングされる条件で、 $x$ がサンプリングされる確率」の積である。これはそれぞれ $|S_i|/B$ と $1/|S_i|$ であり、それの積は $1/B$ である。

よって、「 $P$ からサンプリングした $(x,i)$ が良い割り当てである確率」は $A/B$ である。

$Pr[X_j=1] = A/B$ も成り立つし、 $\mathbb{E}[X_j] = A/B$ 。

ここで、 $X = \sum_{j=1}^t X_j$ となり、 $\mathbb{E}[X] = tA / B$ であるので、チェルノフ上界を用いると、以下の式が成り立つ。

Pr[X \not \in (1 \pm \epsilon) \mathbb{E}[X]] \leq 2 \exp(-\frac{\epsilon^2 \mathbb{E}[X]}{3}) = 2 \exp(-\frac{\epsilon^2 t A}{3B})

このように、期待値が逸れる確率が求まった。ここで、 $A/B$ は

\frac{A}{B} = \frac{|\bigcup S_i|}{\sum |S_i|} \geq \frac{\max |S_i|}{\sum |S_i|} \geq \frac{1}{m}

と下限を評価できる。したがって代入することで、 $t$ を適切に大きくすることによって確かに $1/3$ で抑えることができる。

Pr[X \not \in (1 \pm \epsilon) \mathbb{E}[X]] \leq 2 \exp(-\frac{\epsilon^2 t A}{3B}) \leq 2 \exp(- \frac{\epsilon^2 t}{3m}) \leq \frac{1}{3}

計算時間

$t=\frac{m}{\epsilon^2}$ にとって、1回当たりの走査は $(x,i)$ が良いか調べるのに $O(nm)$ かかるので普通にやると $O(\frac{nm^2}{\epsilon^2})$ である。

各 $S_i$ についての極端なケースを考える。

$S_i$ が互いに素であるならば、 $A/B=1$ である。この時下界は $1/m$ ではなく1なので、1つ $m$ を落とせる。
1. 良い $(x,i)$ かどうかを調べるのには、お互い互いに素なので重ならず、 $O(nm)$ かかる。
$S_i$ が互いにほぼ重なっているのならば、 $A/B \approx 1/m$ であるので、 $m$ は落ちない。
1. 良い $(x,i)$ 稼働かを調べるとき、お互いほぼ重複しているので、実質は $O(n)$ で済ませられる。

1と2のいいところどりをすれば、 $O(\frac{nm}{\epsilon ^2})$ である。

改良版

それを実現するには以下のようなアルゴリズムである。

for j in [1, O(m / epsilon^2)]
		(x, i)を同様にサンプルし、l = 0とする。
		while True: 
				節kを一様にサンプル。
				l++
				if xが節kを充足
						break
		l / mを記録。

記録したl / mの平均をAとして扱う。

オリジナルでは、他を充足しない解 $x$ の数を直接数え上げた。

ここでは、節 $i$ を充足するとわかっている解 $x$ について、ランダムに節を選びそれに充足するまでランダムに選ぶ。それまでの回数は、先ほどの他を充足しない解 $x$ の数から計算される割合を代替する。

何故うまく行くのかは以下の証明である。

$C(x)$ を解 $x$ が充足する節の数だとする。この時、「 $(x,i)$ でサンプリングした $x$ が節 $k$ に対して1回でbreakする確率」は $C(x) / m$ である。これを何回も試行し続けるのは幾何分布であり、結果的に期待値は $\mathbb{E}[l | x] = m / C(x)$ となる。

よって、 $\mathbb{E}[l/m | x] = 1/C(x)$ であり、ここから $\mathbb{E}[l/m]$ を計算する。これは、 $x \in \bigcup S_i$ について $Pr(x) \cdot \mathbb{E}[l/m|x] = \frac{C(x)}{B} \cdot \frac{1}{C(x)} = \frac{A}{B}$ となるので、上のアルゴリズムはちゃんと正しい。