hardcore lemmaとその証明

1. 導入

Impagliazzoのhardcore lemmaと呼ばれる非常に面白いメッセージ性を持つ平均計算量理論において有名な結果[Impagliazzo, FOCS95]を紹介し, その証明をします. 直感的に言えばこの結果は「任意の"まぁまぁ困難な"計算問題に対して"めちゃくちゃ難しい"インスタンスの集合$H$であって密なものが存在する」ということを主張します.

平均計算量理論については以前の記事で触りだけ紹介しています. 本記事では問題として判定問題$f\colon \{0,1\}^n\to\{0,1\}$を考え, 入力分布としてある有限集合$H$ (例えば$H=\{0,1\}^n$) 上の一様分布を考えます. また, 計算モデルとしては回路を考え, その効率性を回路サイズ (=ゲートの個数) で測ります. これを回路計算量と呼びます. アルゴリズムの時間計算量と回路計算量の関係性は非自明で以前の記事で触れていますが, 任意のアルゴリズムはその動作を回路で（少しのオーバーヘッドがあるものの）シミュレーションできるため, 「時間計算量が小さいならば回路計算量が小さい」は成り立ちます (逆は必ずしも成り立たちません).

2. Hardcore lemmaの主張

定義1 (関数のhardness).

関数$f\colon\{0,1\}^n\to\{0,1\}$は, 任意のサイズ$s$以下の回路$C$に対し$\Pr_{x\sim H}[C(x)=f(x)]\leq 1-\delta$を満たすとき, サイズ$s$に対し$H$上で$\delta$-hardであるという. ここで, $\Pr_{x\sim H}[...]$は$x\in\{0,1\}^n$が$H$上一様ランダムにサンプリングされた時の確率をとることを意味する.

$\delta$の値が大きいほど$f$は難しいと解釈できますが, 常に0を出力する回路と常に1を出力する回路を考えればどちらか一方は半分以上の入力$x$に対し$f(x)$を正しく計算できるので, $\delta>1/2$にはなりえません. 

定理1 (Impagliazzo's hardcore lemma)

任意の$\delta,\epsilon>0$に対し以下が成り立つ: $f\colon\{0,1\}^n\to\{0,1\}$がサイズ$s$に対し$\{0,1\}^n$上で$\delta$-hardであるならば、サイズ$\delta 2^n$以上のある集合$H$が存在して$f$はサイズ$O(\delta^2\epsilon^2 s)$に対し$H$上で$(1/2-\epsilon)$-hardである.

冒頭でも述べた通り, $f$が$\{0,1\}^n$上でまぁまぁ難しい (i.e., $0.01$-hard) ならば, $f$がめちゃくちゃ難しい(i.e., $0.499$-hard)ようなサイズ$0.01\times 2^n$以上のインスタンスの集合$H$が存在することになります.

3. 証明

主に二通りの証明方法 (ブースティングアルゴリズムに基づくものとNewman's min-max theoremに基づくもの) が知られています. 後者の証明はArora-Barakの本などにも紹介されているので, 本記事では前者の証明を紹介します.

3.1. Hardcore measure

まず, setの連続緩和としてmeasureという概念を定義し, hardcore setの存在性の代わりにhardcore measureの存在性を証明します. 

定義2 (measure)

関数$M\colon\{0,1\}^n\to\{0,1\}$をmeasureと呼ぶ (測度論における測度とは区別するのを注意してください). $M$のサイズを$|M|=\sum_{x\in\{0,1\}^n}M(x)$とし, 相対サイズを$\mu(M)=|M|/2^n$とする. $\mu(M)\geq \delta$であるとき, $M$は$\delta$-denseであるという.

定義3 (measureにおけるhardness)

$M$をmeasureとする. 関数$f\colon \{0,1\}^n\to\{0,1\}$は以下を満たすとき, サイズ$s$に対し$M$上で$\delta$-hardであるという: 任意のサイズ$s$以下の回路$C$に対し$\Pr_{x\sim M}[C(x)=f(x)]\leq 1-\delta$.

ここで, $\Pr_{x\sim M}[...]$は$M(x)$に比例する確率で$x$をサンプリングした時の確率を考える.

注釈: measureは集合$H\subseteq \{0,1\}^n$を"連続化したもの"と解釈できます. 例えば$M$として$H$の指示関数 ($M(x)=1$ if $x\in H$, $M(x)=0$ if $x\not\in H$) をとれば, $M$が$\delta$-dense $\iff$ $|H|\geq \delta 2^n$ となります.

まず, 定理1の代わりにそれのmeasure版となる以下の結果を証明します:

定理2 (hardcore measure)

任意の$\delta,\epsilon>0$に対し以下が成り立つ: $f$が$\{0,1\}^n$上でサイズ$s$に対し$\delta$-hardならば, ある$\delta$-denseな measure $M$が存在し, $f$は$M$上でサイズ$O(\delta^2\epsilon^2s)$に対し$(1/2-\epsilon)$-hardである.

(証明)

待遇 (i.e., 任意の$M$上でhardでないならば$\{0,1\}^n$上でhardでない) を示します. 具体的には, 任意の$\delta$-denseなmeasure $M$に対し, $f$は$M$上でサイズ$s'$に対し$(1/2-\epsilon)$-hardでないと仮定します. すなわち, 任意の$\delta$-denseな$M$に対しあるサイズ$s'$の回路$C_M$が存在して$\Pr_{x\sim M}[C(x)=f(x)]>1/2+\epsilon$とします. これらの回路$C_M$を組み合わせることによって, $\Pr_{x\sim \{0,1\}^n}[C'(x)=f(x)]>1/2+\delta$となるようなサイズ$O(\epsilon^{-2}\delta^{-2}s')$の回路$C'$を構成します.

最終的に得られる回路$C'$は$C'=\mathsf{maj}(C_1,\dots,C_t)$の形になります ($\mathsf{maj}(x_1,\dots,x_t)$は$\sum x_i\geq t/2$以上ならば$1$, そうでなければ$0$を返す関数で, この関数はサイズ$O(t)$の回路で計算できることが知られています.) 以下では$C_1,\dots,C_t$を定義します.

$\gamma:=\delta\epsilon$とします. まず, 定数measure $M_1\equiv 1$ から始めます. measure $M_i$に対し$C_i=C_{M_i}$とします (待遇の仮定からこのような回路が存在). 事象$Z$の符号付き指示関数を$[Z]$と定義し (i.e., $Z$が真なら$[Z]=1$, そうでないなら$[Z]=-1$), $R_i(x)=\sum_{j=1}^i [C_i(x)=f(x)]$とします. 次のステップにおけるmeasure $M_{i+1}$を,

$$M_{i+1}(x) = \begin{cases} 1 & \text{if }R_i(x)\leq 0,\\1-\gamma R_i(x) & \text{if }0<R_i(x)<1/\gamma,\\0 & \text{if }R_i(x)>1/\gamma\end{cases}$$

で定義します. イメージとしては, これまで得られた回路の過半数が間違えるような入力に対しては最大の重み$M_{i+1}(x)=1$を与え, これまでの回路のうち多くが正解するような入力に対しては重みを与えない ($M_{i+1}(x)=0$) ようなものです. これを$\mu(M_{i+1})\leq \delta$になるまで繰り返し, 得られた回路を$C_1,\dots,C_t$とします.

最終的な回路$C'$の性能を評価します. 入力$x$に対して$C'(x)\neq f(x)$ならば, $C_1,\dots,C_t$のうち過半数が違う値を計算してるので, $C_1(x)+\dots+C_t(x)<t/2$となり, $R_t(x)<0$となります. このとき上記の構成より$M_{t+1}(x)=1$です. したがって

$$\Pr_{x\sim \{0,1\}^n}[C'(x)\neq f(x)] \leq \Pr_{x\sim \{0,1\}^n}[M_{t+1}(x)=1] \leq \frac{1}{2^n}\sum_{x\in\{0,1\}^n}M_{t+1}(x)\leq \delta$$

となるので, $C'$は$\{0,1\}^n$上で$f$を$1-\delta$以上の確率で計算していることになります. また, 各$C_i$のサイズ$\leq s'$であることから$C'$のサイズは$O(ts')$です.

最後に$t=O(\epsilon^{-2}\delta^{-2})$を示せば証明が完了します. ポテンシャルとして

$$A_t:=\sum_{1\leq i\leq t}\sum_{x\in\{0,1\}^n}M_i(x)[C_i(x)=f(x)]$$

を考え, その上下界を求めます:

(1): $A_t\geq t2^{n+1}\gamma$.

回路$C_i$の$M_i$上の正答率の仮定から $$\sum_{x\in\{0,1\}^n}\frac{M_i(x)}{|M_i|}[C_i(x)=f(X)]=2\Pr_{x\sim M_i}[C_i(x)=f(x)]-1\geq 2\epsilon$$ なので,

$$A_t=\sum_{1\leq i\leq t}|M_i|(2\Pr_{x\sim M_i}[C_i(x)=f(x)]-1)\geq t\delta 2^{n+1}\epsilon=t2^{n+1}\gamma.$$

(2): $A_t\leq 2^n(\gamma t/2+1/\gamma)$.

$x\in\{0,1\}^n$を固定し, $S:=\sum_{i=1}^tM_i(x)[C_i(x)=f(x)]$を上から抑えます. $a\in\mathbb{Z}$に対して

$$m(a) = \begin{cases} 1 & \text{if }a\leq 0,\\1-\gamma a & \text{if }0<a<1/\gamma,\\0 & \text{if }a>1/\gamma\end{cases}$$

と定めると, $M_i(x)=m(R_{i-1}(x))$と書けます. ここで, 次で定義される辺重み付き有向グラフ$G=(V,A)$を考えます: $V=\{R_i(x)\colon i=0,\dots,t\}$, $A=\{(R_i(x),R_{i+1}(x))\colon i=0,\dots,t-1\}$, 辺$(R_i(x),R_{i+1}(x))$の重みは$M_i(x)(R_i(x)-R_{i-1}(x))=m(R_{i-1}(x))(R_i(x)-R_{i-1}(x))$.

有向グラフ$G$

ここで, 辺のペア$(a,a+1)$と$(a+1,a)$を考えます. これらの辺は逆向きなので重みの符号は異なり, その大きさは$|M(a)-M(a+1)|\leq \gamma$を満たします. このような辺のペアは高々$t/2$本あり, 総和に対して高々$\gamma t/2$だけ寄与します. 次に, この辺のペアを$G$から除去すると残るグラフは右に行き続けるパスまたは左に行き続けるパスになります.

ペアを全て除去して残ったグラフ

上図のように左に行き続けるパス (つまり, 頂点$a\to a-1\to\dots \to a-\ell$を辿るパス) の辺重みは全て負なので, パス重みの総和には寄与しません. また, 右に行き続けるパス (頂点$a\to a+1\to \dots \to a+\ell$を辿るパス) の寄与は$m(a)+m(a+1)+\dots+m(a+\ell-1)$ですが, $b>1/\gamma$なる任意の$b$に対して$m(b)=0$なのでこの寄与は高々$1/\gamma$となります. 従って, パス重みの総和は高々$\gamma t/2 + 1/\gamma$です. 考えるべきパスは$2^n$個あるから, $A_t\leq 2^n(\gamma t/2+1/\gamma)$を得ます.

(1),(2)のバウンドより, 

$$t2^{n+1}\gamma \leq A_t \leq 2^n(\gamma t/2+1/\gamma)$$

となるので, $t\leq 2/(3\gamma^2) \leq (\delta\epsilon)^{-2}$を得ます.

3.2. Hardcore measure $\Rightarrow$ Hardcore set

3.1の議論により, hardcore measure $M$の存在性が言えました. randomized roundingとprobabilistic methodを組み合わせてhardcore set $H$の存在性を証明します. 整理すると, $M$は$\delta$-denseであり, かつ任意の小さい回路$C$に対して

$$\Pr_{x\sim M}[C(x)=f(x)]\leq \frac{1}{2}+\epsilon$$

を満たします.　この節では$|H|\geq \delta/2\cdot 2^n$であり, かつ任意の小さい回路$C$に対して

$$\Pr_{x\sim H}[C(x)=f(x)]\leq \frac{1}{2}+\epsilon$$

を満たす集合$H\subseteq\{0,1\}^n$の存在性を証明します.

Hardcore measure $M$ を考えます. 各$x\in\{0,1\}^n$に対して, 独立に確率$M(x)/|M|$で$x$を含むようなランダム集合を$H$とします. まず, $|H|$の期待値は$|M|$なので, Hoeffding boundより確率$1-2^{-\Omega(2^{n})}$で$|H|\geq 0.9|M|$を満たします (つまり$H$は高確率で密な集合). 次に$\Pr_{x\sim H}[C(x)=f(x)]=\frac{|\{x\in H\colon C(x)=f(x)\}|}{|H|}$を考えます ($H$がランダム集合なので, この値は$H$のランダムネスに起因する確率変数となる). 先ほど分母の下界を求めたので, 次は分子の上界を求めます. まず, 回路$C$を固定して$A_C=\{x\colon C(x)=f(x)\}$を回路$C$が正解する入力の集合とします. すると分子は$|H\cap A_C|=\sum_{x\in A_C}\mathbf{1}_{x\in H}$となり, これは($H$の構成法により)独立な確率変数の和となります. さらにその期待値は$\mathrm{E}[|H\cap A_C|]=|M|\sum_{x\in A_C}\frac{M(x)}{|M|}=|M|\Pr_{x\sim M}[C(x)=f(x)]\leq (1/2+\epsilon)|M|$となるので, 非常に高い確率 (確率$1-2^{-\Omega(2^n)}$) で$|H\cap A_C|\leq 1.001(1/2+\epsilon)|M|\leq (1/2+\epsilon')|M|$となります. 従って, 回路$C$に関するunion bound ($C$が小さいサイズ, 例えば多項式サイズならば, $C$の総数は$2^{\mathrm{poly}(n)}$以下になる) により, 

$$\Pr_H[\forall C,\Pr_{x\sim H}[C(x)=f(x)]\leq \frac{1}{2}+\epsilon'] \geq 1-2^{-\Omega(2^n)}\cdot 2^{\mathrm{poly(n)}}>0.$$

よって正の確率で$H$はhardcore setの条件を満たすので, 所望の$H$の存在性が証明できました (証明終).

4. 教師有り学習のブースティングとの関係

教師有り学習の文脈では, $f\colon\{0,1\}^n\to\{0,1\}$を二値分類タスクとみなし, $C_M$を$M$上で動作する弱い分類器とみなすことにより, $C'$の構成をブースティングの一種と解釈することができます (ただし上記の証明ではあくまでも$C'$の存在性にすぎず, その構成アルゴリズムを与えたものではないため, ブースティングアルゴリズムそのものは与えていません). 上記の証明は$M$を上手く更新しながら対応する分類器をとってきてそれらのmajorityをとるものになっており, 今回の証明以外にも$M$の更新方法は様々知られており, 例えばAdaBoostのようなmultiplicative updateに基づくもの (+Bregman projection)も知られており, $t=O(\epsilon^{-2}\log\delta^{-1})$まで改善されています (Barak et al. SODA09).