Goldreich-Levinの定理 (アルゴリズム的側面の紹介)

Goldreich-Levinの定理はGoldreich and Levin (1989)によって証明された非常に有名な定理で, 自分のお気に入りの定理の一つです. 元々は平均計算量理論の文脈でone-way functionのhardcore predicateを与えたりYaoのXOR補題の証明に使われたりしている定理ですが, その後Hadamard codeのlocal list decoding, large Fourier coefficientの計算など様々な解釈が与えられ多くの研究に影響を及ぼす重要な定理です. しかしこの定理の主張の説明の多くは理解するためにいろんな前提知識を要するため, 多くの情報系の方にとって敷居の高いものになっているような気がします.

そこで, 本記事では定理の重要性などの背景は省き, その内容と証明のアルゴリズム的な側面を本質だけ抽出して紹介します. 前提知識は特に必要ありません.

1. 線形関数の復元

$\mathbb{F}_2^n$上の線形関数$g(x)=\langle a,x\rangle=\sum_{i=1}^n a_ix_i$がオラクルで与えられるとき, 

$a_1,\dots,a_n\in\mathbb{F}_2$を復元せよ

という問題を考えます. つまり, 任意の$x\in\mathbb{F}_2^n$をクエリしたときに$g(x)$が得られるという仮定の下で係数を復元するという問題です. このような問題設定は学習理論の文脈と少し近い雰囲気を持っています. 学習理論の文脈では「$(a,h(a))$の組が複数与えられたとき, 関数$h$ (ただし$h$は何らかの関数族$\mathcal{F}$に属する)を計算せよ」というような問題設定を考えることがあります. 上記の問題はこの設定よりも簡単で, 好きな入力に対して$h(a)$を得ることが出来るという設定になっています.

この問題は簡単で, $n$個の単位ベクトル$e_1,\dots,e_n$をクエリすれば$a_i=g(e_i)$なので$n$個の係数を復元することができます.

では, 「オラクルが1%の入力に対し間違っている」という設定で同じ問題が解けるでしょうか？与えられるオラクルを$\mathcal{O}$とします. 入力全体$\mathbb{F}_2^n$のうち, ある$|L|\leq 0.01|\mathbb{F}_2^n|$を満たす$L\subseteq \mathbb{F}_2^n$が存在して$x\in L$に対しては$\mathcal{O}(x)\neq g(x)$です. オラクル$\mathcal{O}$のみが与えられたとき (つまり, $L$は分からない), 全ての係数は復元できるでしょうか? この問題設定は学習理論の文脈ではLWE (learning with errors) に対応します.

オラクルが間違わない設定だと, 単位ベクトル$e_i$に対して$\mathcal{O}(e_i)=a_i$が成り立つので簡単に復元できましたが, この設定だと入力$e_i$においてオラクルが間違えている(つまり$e_i\in L$)の可能性があり, しかも間違えているかどうかが分からないので上手くいきません.

ですが実はこの問題設定においても乱択を許せば効率的なアルゴリズムが存在します. 第$i$番目の係数$a_i$を復元する以下の乱択アルゴリズムを考えます: 

$r\in\mathbb{F}_2^n$を一様ランダムにサンプリングし, $\mathcal{O}(e_i+r)-\mathcal{O}(r)$を出力する.

このアルゴリズムは98%の確率で$a_i$を正しく出力します. なぜならば, $r\in\mathbb{F}_2^n$が一様ランダムなので99%の確率で$O(r)=\langle a,r\rangle$であり, しかも$e_i+r$も(周辺分布を見ると)一様ランダムなので, 同様に99%の確率で$\mathcal{O}(e_i+r)=\langle a,r+e_i\rangle$です. なのでunion boundより98%の確率で両方の値は正確で, 最後に線形性より$a_i=\langle a,e_i\rangle = \langle a,r+e_i\rangle - \langle a,r\rangle$により正しく復元できています. 

この議論はオラクルが正直である確率が$0.75+\epsilon$であれば成功確率は$0.5+2\epsilon$となるので, $\lceil\frac{\log (n/\delta)}{8\epsilon^2}\rceil$回繰り返して多数決をとることによって成功確率を$1-\delta/n$までamplifyすることができます. 実際, $i$番目の繰り返しにおいて, 上記のアルゴリズムが正しく$a_i$を計算できていれば$X_i=1$, そうでなければ$X_i=0$として確率変数$X_i$を定義(ランダムネスはベクトル$r$の選択)して$S=X_1+\dots+X_T$とおくと ($T$は繰り返しの回数), $\mathrm{E}[S]\geq (0.5+2\epsilon)T$なので, Hoeffdingの不等式より

$$\Pr[S\leq T/2]\leq \Pr[S\leq \mathrm{E}[S]-2\epsilon T] \leq \exp(-8\epsilon^2 T)$$

を得ます. $T=\lceil\frac{\log(n/\delta)}{8\epsilon^2}\rceil$とすれば, この確率は高々$\delta/n$になります.

再び$i=1,\dots,n$でunion boundをとれば, 全ての成分$a_1,\dots,a_n$を確率$1-\delta$で復元することができます.

上記のアルゴリズムはオラクルが高々$0.25-\epsilon$の割合の$x$に対して誤った値を返すという仮定が大前提でした. この割合がもっと大きくても (例えばオラクルが40%の確率で間違うという設定で)$a$を復元できるでしょうか？

定式化するために, 「オラクルが間違う入力の割合」を関数の距離として捉えます. 二つの関数$f,g\colon\mathbb{F}_2^n\to\mathbb{F}_2$に対して$d(f,g):=\Pr_x[f(x)\neq g(x)]$と定義します. これは$f$と$g$を長さ$2^n$のbinary文字列とみなしたときの(正規化した)ハミング距離と見なすことができます.

$\mathbb{F}_2^n$上の二つの相異なる線形関数$g(x)=\langle a,x\rangle$, $g'(x)=\langle a',x\rangle$に対して, $x\in\mathbb{F}_2^n$を一様ランダムにとってくると

$$\Pr[g(x)=g'(x)] = \Pr[\langle a-a',x\rangle=0] = \frac{1}{2}$$

となります. 最後の等式は$a\neq a'$であることを利用しています. 対偶をとって$\Pr[g(x)=g'(x)]<1/2$ならば$g=g'$という命題を得ます. このことから, $\mathbb{F}_2^n$を係数に持つ線形関数の世界では二つの相異なる線形関数はハミング距離の意味でかなり離れているという面白い性質を持つことがわかります.

図1. Boolean関数全体の空間において二つの異なる線形関数は離れている (0.5以上とありますが実際はぴったり0.5です).

ここで冒頭の「$0.25-\epsilon$の割合の入力に対しオラクルは間違える」という問題設定に戻りましょう. 与えられるオラクル$\mathcal{O}$は, ある線形関数$g$に対して$d(\mathcal{O},g)\leq 0.25-\epsilon$という条件を満たしています. つまりオラクル$\mathcal{O}$は$g$を中心とした半径$0.25-\epsilon$の円に属しているため, 一意に復元可能です.

ところが, 「$0.25+\epsilon$の割合の入力に対しオラクルは間違える」という問題設定だと, 図2のように二つの円が被ってしまう可能性があります.

図2. 半径が大きすぎると円が被りその共通部分にオラクルがあると一意じゃない可能性がある.

ここまでの状況を整理しましょう. 「オラクルが間違える」という表現を距離$d$の言葉で置き換えて以下のように問題を再定義します:

関数$\mathcal{O}$がある線形関数$g$に対して$d(\mathcal{O},g)\leq 0.25-\epsilon$であるとする. 

関数$\mathcal{O}$のオラクルが与えられたとき, $g$ (の係数を全て) を求めよ.

この問題は先ほどのアルゴリズムで解くことができます. 定理の形で述べておくと

定理1. 上記の問題に対し確率$1-\delta$で正しい係数を全て出力する$O(n\epsilon^{-2}\log(n/\delta))$時間乱択アルゴリズムが存在する.

一方で, 

関数$\mathcal{O}$がある線形関数$g$に対して$d(\mathcal{O},g)=0.25+\epsilon$であるとする. 

関数$\mathcal{O}$のオラクルが与えられたとき, $g$ (の係数を全て) を求めよ.

という問題を考えると, 候補となる$g$が複数存在しうることを図で紹介しました. 

2. Goldreich-Levinの定理

次の列挙問題を考えてます:

関数$\mathcal{O}$のオラクルが与えられたとき, $d(\mathcal{O},h)\leq 0.5-\epsilon$を満たす線形関数$h$を列挙せよ.

そのような$h$が存在しない場合は「なし」と出力せよ.

定理1では距離の条件が$0.25-\epsilon$で考えていましたが, ここでは大きく攻めて$0.5-\epsilon$に緩和します. なお, 任意の相異なる線形関数は距離0.5だけ離れているので, "$0.5-\epsilon$"を"$0.5$"に置き換えた場合, $O=g$だとすると全ての線形関数を列挙しなければならないので列挙候補の個数は$2^n$になってしまいます. ですが$0.5-\epsilon$にすると多項式時間で列挙できるということがGoldreich and Levin (1989)によって(本質的に)示されました.

定理2.

上記の列挙問題の全ての解$h$を含むリスト$L$を確率$1-\delta$で出力する$O\left(\frac{n^3}{\delta^2\epsilon^8}\log\left(\frac{n}{\delta\epsilon^4}\right)\right)$時間アルゴリズム$A$が存在する. 

注釈: 冒頭にも述べた通り, Goldreich-Levinの定理自体は様々な解釈ができ, Goldreich and Levin (1989) の平均計算量の文脈の結果のアルゴリズム的に本質的な部分を抽出したものが定理2なので, 定理2そのものをGoldreich-Levinの定理と呼ぶべきかどうかは微妙かもしれませんので, 注意してください.

定理2を証明していきます. まず, 以下の定理を既知として認めます.

定理3. 上記の列挙問題の解は高々$1/\epsilon^2$個しか存在しない.

定理3は関数$\mathcal{O}$のフーリエ級数解析で簡単に示せますが, 後日行います.

定理2の証明). 以下が主張にあるアルゴリズム$A$になります.

1:  $t\leftarrow \lceil \log_2\left(1+\frac{n}{4\delta\epsilon^4}\right)\rceil$;

2:  $r_1,\dots,r_t\in\{0,1\}^n$を独立一様ランダムに生成;

3:  $L\leftarrow \emptyset$;

4:  for each $b=(b_1,\dots,b_t)\in\{0,1\}^t$ do:

5:     for each $i\in\{1,\dots,n\}$ do:

6:        for each $S\subseteq \{1,\dots,t\}$ of $S\neq\emptyset$ do:

7:            $b_S\leftarrow \sum_{i\in S}b_i$;

8:            $r_S\leftarrow \sum_{i\in S}r_i$;

9:            $c_S \leftarrow \mathcal{O}(r_S+e_i)-b_S$;

10:       $a_i \leftarrow \mathsf{maj}((c_S)_{S\neq\emptyset})$;

11:   $L \leftarrow L\cup \{(a_1,\dots,a_n)\}$;

12: return $L$;

ただし, $\mathsf{maj}$は多数決をとる関数 (受け取ったビット列の中で多く登場したビットを返す関数) です.

以下ではアルゴリズム$A$の解析を行います. $d(\mathcal{O},g)\leq 0.5-\epsilon$を満たす関数を一つとってきて$g$とします. アルゴリズム$A$の重要なポイントは

• 2行目で生成したランダムベクトルに対し, $g(r_1),\dots,g(r_t)$の値はオラクルに聞いていないので分からないが, 4行目で$\{0,1\}^t$を列挙しているためどれか一つの$b$に対しては$b_i=g(r_i)$ ($\forall i$) が成り立ちます. 以後この条件を満たす$b$に対して話を進めます.
• 7行目で与えた$b_S$は$g$の線形性より$b_S=g\left(\sum_{i\in S}r_i\right)=g(r_S)$が成り立ちます. ここまでの議論は任意の線形関数$g$で成り立ちます.
• 9行目では, ベクトル$r_1,\dots,r_t$の一様ランダム性により$r_S+e_i$の分布も一様ランダムです. なのでオラクル$\mathcal{O}$の性質により, $\Pr[c_S=g(e_i)]\geq 0.5+\epsilon$です ($b_S=g(r_S)$の仮定の下で).

ここまでをまとめると, 

ある$b\in\{0,1\}^t$が存在して$\forall S\neq\emptyset$, $\Pr[c_S=g(e_i)]\geq 1/2+\epsilon$

が成り立ちます. 10行目では多数決をとってこの確率をamplifyしています. この部分を解析します. 確率変数$X_S$を, $c_S=g(e_i)$ならば$X_S=1$, そうでなければ$X_S=0$と定義して$X=\sum_{S\neq\emptyset} X_S$とします. $r_1,\dots,r_t$は全て独立ですが, $(r_S)_{S\neq\emptyset}$はそうではないので, Hoeffdingの不等式を適用して$X$の集中性を示すことはできません. 代わりにChebyshevの不等式 (以前の記事参照) を利用して$X$の集中性を示します. Chebyshevの不等式は分散が小さければ集中することを主張する不等式なので, $X=\sum X_S$の分散を抑えれば良いことになります. これは$(r_S)$のpairwise independentという性質を用いると可能です.

定義. 確率変数の族$(R_i)$が任意の$i\neq j$に対し

$$\Pr[R_i=a\land R_j=b] = \Pr[R_i=a]\Pr[R_j=b]$$

を満たすとき, $(R_i)$はpairwise independentであるという.

例えば$(R_i)$が全て独立ならば自動的にpairwise independentになります. ところでアルゴリズム$A$で考えた確率変数の族$(r_S)$も実はpairwise independentです (簡単な計算で確認できます). 従って$X_S$もpairwise independentです. 次に分散$\mathrm{Var}[X]=\mathrm{E}[X^2]-\mathrm{E}[X]^2$を計算しましょう.

$$\mathrm{E}[X^2]=\mathrm{E}\left[\sum_{S,S'\neq\emptyset}X_S X_{S'}\right] =\left(\sum_{S}\mathrm{E}[X_S]\right)^2 + \sum_{S}\mathrm{E}[X_S](1-\mathrm{E}[X_S]^2) \leq \mathrm{E}[X]^2 + \frac{2^t-1}{4}$$

より$\mathrm{Var}[X]\leq (2^t-1)/4$です. ここの式変形ではpairwise independentであることから$\mathrm{E}[X_SX_{S'}]=\mathrm{E}[X_S]\mathrm{E}[X_{S'}]$が成り立つことを利用しています (2番目の等式). 最後の不等式では任意の$x\in[0,1]$に対して$x(1-x)\leq 1/4$であることを用いました.

よってChebyshevの不等式および$t$の条件より

$$\Pr[X\leq (2^t-1)/2] \leq \Pr[X\leq\mathrm{E}[X]-(2^t-1)\epsilon] \leq \frac{\mathrm{Var}[X]}{(2^t-1)^2\epsilon^2} \leq \frac{1}{4(2^t-1)\epsilon^2}\leq \frac{\delta\epsilon^2}{n}.$$

を得ます. つまり確率$1-\epsilon^2\delta/n$で$a_i=g(e_i)$が成り立つので, $i=1,\dots,n$と条件を満たす線形関数$g$ (定理3より高々$\epsilon^{-2}$個) に関するunion boundにより, アルゴリズム$A$の出力リストの中に$g$の第$i$番目の係数が入っていない確率は高々$\delta$となる, すなわち$A$は確率$1-\delta$で答えが含まれるリストを出力することができました.

なお, $A$の計算時間は$O(nt 2^{2t})=O\left(\frac{n^3}{\delta^2\epsilon^8}\log\left(\frac{n}{\delta\epsilon^4}\right)\right)$です.

(証明終)

なお, アルゴリズム$A$の出力されたリスト$L$の中から$d(h,\mathcal{O})\leq 0.5-\epsilon$を満たす関数$h$を抽出するのは(乱択を許せば)ある程度までは簡単で, 「ランダムな入力$x\in\{0,1\}^n$に対して$\mathcal{O}(x)=h(x)$かどうかをチェックする」という操作を何度も行って正答数が$0.5+\epsilon$くらいになるような$h$のみを抽出すればOKです (ただし, $d(h,\mathcal{O})\leq 0.5-(1-o(1))\epsilon$を満たす$h$も抽出される可能性もあるので完璧ではありません).