2024年3月1日金曜日

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に冬のLAに参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました.

自分の発表には全く関係ないことですが, LAに参加していてValiant--Vaziraniの定理がいまいち知名度がないということを初めて認識しました. これまでもこの定理をブログ記事にしたいと常々思っていたので重い腰をあげて解説しようと思います.

充足可能性判定問題 (SAT)とUSAT

$n$個の変数$x_1,\dots,x_n$を持つ論理関数$\phi\colon\{0,1\}^n\to\{0,1\}$が与えられたときに$\phi(x)=1$を満たす$x$が存在するかを問う問題を充足可能性判定問題(SAT)と言います (ここでは論理式は回路として与えられると思ってください. CNFでもOKです.).

一般に充足可能性判定問題は解の存在性を判定するだけです. では特殊ケースとして「充足割当が高々一つしか存在しないことが保証されている論理関数」に対するSATは効率的に解けるのでしょうか?

このような判定問題をUSAT (unique SAT)と言います. 厳密にはUSATは約束問題です. すなわち, 与えられた論理関数$\phi$が以下で定義される二つの集合$U_{\mathrm{yes}},U_{\mathrm{no}}$のどちらに属するかを判定する問題です:
\begin{align*}
&U_{\mathrm{yes}} = \{\phi\colon \phi\text{ has a unique satisfying assignment}\},\\
&U_{\mathrm{no}} = \{\phi\colon \phi\text{ has no satisfying assignments}\}.
\end{align*}
与えられた$\phi$がこの二つの集合どちらにも属していない場合はYES/NOどちらを答えても正解としてみなします. $U_{\mathrm{yes}}, U_{\mathrm{no}}$はdisjointですが$U_{\mathrm{yes}}\cup U_{\mathrm{no}}$は必ずしも入力全体の集合になるわけではありません. yesインスタンス全体とnoインスタンス全体の和集合が入力全体になる決定問題を判定問題と呼び, そうとは限らない決定問題を計算量理論では約束問題 (promise problem)といいます (約束問題は判定問題を特殊ケースとして含んでいます). 細かい注意ですが, $\mathsf{P}$とか$\mathsf{NP}$は判定問題の計算量クラスなので「$\mathrm{USAT}\in\mathsf{P}$」という主張は文法がおかしく, 正しくは 「$\mathrm{USAT}\in\mathsf{prP}$」です (promise P).

Valiant--Vaziraniの定理

Valiant--Vaziraniの定理とは乱択を許したときにUSATがSATに帰着できることを主張する定理です. 例えばその帰結として

USATが多項式時間で解ける $\Rightarrow$ SATが乱択多項式時間で解ける

が得られますので, USATはいわば"乱択NP困難" (これはofficialな用語ではない!)ということになります. ValiantはPAC学習を定義したりマッチング数え上げの#P困難性を証明した方で, Vaziraniは近似アルゴリズムの本で有名なVaziraniです. どちらも非常に偉大な方です. 原著論文はこちらです.

定理1 (Valiant--Vaziraniの定理)
論理関数を別の論理関数に変換する多項式時間乱択アルゴリズム$R$とある多項式$p$が存在し, 任意の論理関数$\phi\colon\{0,1\}^n\to\{0,1\}$に対し, 
  • $\phi\in \mathrm{SAT}$ ならば, $\Pr[R(\phi)\in U_{\mathrm{yes}}]\ge \frac{1}{p(n)}$.
  • $\phi\not\in\mathrm{SAT}$ ならば, 確率1で$R(\phi)\in U_{\mathrm{no}}$.
ただし$\mathrm{SAT}$は充足可能な論理式全体を表す.

仮にUSATが多項式時間アルゴリズム$A$で解けたとしましょう. このアルゴリズム$A$を定理1のアルゴリズム$R$と組み合わせることで以下のようにしてSATを解くことができます:

  1. 与えられた論理関数$\phi$を入力として$R$を走らせ, 別の論理関数$\phi'$を得る.
  2. $\phi'$を入力として$A$を走らせ, YESを出力したらそのままYESを出力する.
  3. そうでなければステップ1に戻る. これを$100p(n)$回繰り返しても終わらない場合はNOを出力する.
上述の乱択アルゴリズムは任意のSATインスタンス$\phi$に対し99%の確率で正解を出力します. 元の$\phi$が$\phi\in\mathrm{SAT}$ならば, $100p(n)$回の繰り返しの中で全て$R(\phi)\not\in U_{\mathrm{no}}$となってしまう確率は$(1-1/p(n))^{100p(n)}\le \exp(-100)<0.01$だからです (ここでは$\forall x\in\mathbb{R},1+x\le \exp(x)$を使っている).

証明のアイデア


証明の直感を養うために, 効率性を無視した次の帰着を考えます:
  1. $\phi\colon\{0,1\}^n\to\{0,1\}$を与えられた論理関数とする.
  2. 適切に設定されたパラメータ$m$に対し, $f\colon\{0,1\}^n\to\{0,1\}^m$を一様ランダムな関数とする (すなわち, 各$x\in\{0,1\}^n$に対して$f(x)$は独立一様ランダムな$m$ビット文字列を出力する関数.
  3. $\phi'(x) = \phi(x) \land \langle f(x)=1^m \rangle$とする. ここで$\langle E \rangle$は事象$E$の指示関数とする.
明らかに, $\phi$が充足可能でないならば$\phi'$もまた充足可能ではありません. 一方で$\phi$が充足可能であるとき, 充足割当の個数を$N$とすると, $\phi'$の充足割当の個数$N'$は$\mathbb{E}[N']=N/2^m$を満たします. ですので, $m=\log_2 N$とすれば期待値が$1$になります. $N'$の実際の分布は二項分布$\mathrm{Bin}(N,1/N)$であり, $\Pr[\mathrm{Bin}(N,1/N)=1]\ge \mathrm{const}$が成り立つ ($N\to\infty$の極限では$\mathrm{Bin}(N,1/N)\to\mathrm{Po}(1)$に収束する). なお, ステップ3の$\langle f(x)=1^m \rangle$における$1^m$は特に$1^m$である必然性はありません.

この帰着では$N$の値を知る必要があるのですが, そこもまたランダムに与えれば良いです. 一様ランダムに$m\sim[n]$をとると確率$1/n$で$2^{m-1}\le N \le 2^m$を満たします. この$m$を用いて上の帰着を実行すれば, 同じようなポアソン近似により確率$\mathrm{const}\cdot (1/n) \ge \mathrm{poly}(n)$で$\phi'\in U_{\mathrm{yes}}$を満たすことが確認できます.

しかしながら, 上述の帰着では一様ランダムな関数$f$をサンプリングするには少なくとも$m2^n$ビットのランダムビットが必要なので, 指数時間かかってしまいます. そこでこのサンプリングに必要なランダムビット数を$\mathrm{poly}(n)$ビットまで削減することを目指していくことになります. すなわち, 一様ランダムな関数と同等の性質を持つ別のランダム関数を短いランダムシード長でサンプリングすることを目標にします.

これはpairwise independent hash functionという, 脱乱択化(derandomization)の分野では標準的な関数を考えることによって解決できます. まず, 確率変数のpairwise independent性について解説します. 

ペア独立性 


この記事では確率変数といえばデフォルトで離散値をとるものを考えます (計算機では全てが離散で処理されるので).

二つの確率変数$X,Y$は, 任意の$x,y$に対して$\Pr[X=x\text{ and }Y=y]=\Pr[X=x]\Pr[Y=y]$を満たすとき独立であると言います. より一般に確率変数$X_1,\dots,X_n$が独立であると言ったとき, それは任意の$x_1,\dots,x_n$に対して
\begin{align*}
\Pr[X_i = x_i \text{ for all }i\in [n]]=\prod_{i\in [n]}\Pr[X_i=x_i]
\end{align*}
を意味します. 独立という代わりに相互に独立(mutually indepedent)であると言うこともあります.

一方で, 任意の$1\le i<j\le n$と$x_i,x_j$に対し
\begin{align*}
\Pr[X_i=x_i\text{ and }X_j=x_j]=\Pr[X_i=x_i]\Pr[X_j=x_j]
\end{align*}
が成り立つとき, $X_1,\dots,X_n$はペア独立 (pairwise independent) であると言います. pairwise independenceにはこれといったスタンダードな和訳は(私の知る限り)ないと思いますが, ここではこちらのページから拝借しております. なお, 上の定義では$i\neq j$としていることに注意してください.

ペア独立ハッシュ関数

ハッシュ関数と聞くとPythonの辞書などを想起されますが, 計算量の文脈ではハッシュ関数と言ったらある分布に従って生成されたランダムな関数を指すものと思ってください.

ランダムな関数$f\colon\{0,1\}^n\to\{0,1\}^m$に対し, $2^n$個の確率変数$f(0^n),\dots,f(1^n)$がペア独立であるとき, $f$はペア独立ハッシュ関数であると言います.

単に$f$がペア独立ハッシュ関数であると言った場合は単にペア独立性だけを指しますが, しばしば, 任意に固定した$x\in\{0,1\}^n$に対して$f(x)$の分布は一様ランダムであることが多いです.

例えば, 証明のアイデアで考えた「各$x\in\{0,1\}^n$に対し独立一様ランダムな$m$ビット文字列を$f(x)$として出力する関数」はペア独立ハッシュ関数です. この例は生成に指数長のランダムシードを要しますが, よりrandomness-efficientなものも構成できます.

ランダムな直線

有限体$\mathbb{F}=\mathbb{F}_{2^n}$上の関数を考えます. ここでは$\mathbb{F}_{2^n}$の厳密な定義を理解しておく必要はありません. 掛け算と足し算ができて, 非ゼロな元では割り算ができて, これらの演算が$n$に関する多項式時間でできて, しかも$|\mathbb{F}_{2^n}|=2^n$になっているので$\{0,1\}^n$と一対一対応がある, という事実だけを使います. 一様ランダムに$a,b\sim\mathbb{F}$をサンプリングしてランダム関数$f\colon \mathbb{F}\to\mathbb{F}$を
\[f(x) = ax+b\]
で定めます. 有限体を$\mathbb{F}_{2^n}\cong \{0,1\}^n$で同一視すると$f$は$n$ビット文字列から$n$ビット文字列への関数とみなせます.

補題2.
一様ランダムな$a,b\sim\mathbb{F}$に対し, $f\colon x\mapsto ax+b$はペア独立ハッシュ関数である. すなわち, $|\mathbb{F}|$個の確率変数$(f(x))_{x\in \mathbb{F}}$はペア独立である. さらに, 固定した$x\in \mathbb{F}$に対して$f(x)$の分布は$\mathbb{F}$上一様ランダムである.

証明. 任意の$x_1\neq x_2\in \mathbb{F}$と$y_1,y_2\in\mathbb{F}$に対して
\[
\Pr[f(x_1)=y_1 \text{ and }f(x_2)=y_2] = \Pr[f(x_1)=y_1]\Pr[f(x_2)=y_2]
\]
を示せば良いです. $f(x_i)=y_i$ ($i=1,2$)という等式を行列を用いて表すと
\[
\begin{bmatrix}
x_1 & 1 \\
x_2 & 1 \\
\end{bmatrix}
\begin{bmatrix}
a \\
b
\end{bmatrix}
=
\begin{bmatrix}
y_1 \\
y_2
\end{bmatrix}
\]
となります. ヴァンデルモンドの行列式から係数行列は正則なので, $[a\,b]^{\top}$はある特定のベクトルになっていなければならず, $a,b\sim\mathbb{F}$は一様ランダムなのでこれが起こる確率は$1/|\mathbb{F}|^2$となります.

一方で$\Pr[f(x_i)=y_i]=1/|\mathbb{F}|$なので, 確かに$(f(x))_{x\in \mathbb{F}}$はペア独立であることが確認されました. (証明終)

補題2で構成したペア独立ハッシュ関数は$n$ビット文字列から$n$ビット文字列への写像でしたが, 出力の$n$ビットのうち最初の$m$ビットだけを取り出した ($m\le n$) 文字列を出力するようにすれば, 値域を$\{0,1\}^m$にしつつペア独立になるようにできます.

補題3.
ペア独立ハッシュ関数$f\colon \{0,1\}^n\to\{0,1\}^n$と固定したパラメータ$m\le n$に対し, $f'(x)\in\{0,1\}^m$を$f(x)$の先頭$m$ビットからなる文字列と定義する. このとき, $f'\colon\{0,1\}^n\to\{0,1\}^m$はペア独立ハッシュ関数である.

証明. 確率変数$(f(x))_{x\in\{0,1\}^n}$がペア独立であることを利用して$(f'(x))_{x\in\{0,1\}^n}$がペア独立であることを示します. ペア独立性の定義から, 任意の$x_1\neq x_2\in\{0,1\}^n$と$y_1,y_2\in\{0,1\}^m$に対して
\[
\Pr[f'(x_1)=y_1\text{ and }f'(x_2)=y_2]=\Pr[f'(x_1)=y_1]\Pr[f'(x_2)=y_2]
\]
が成り立つことを示せばよいです.

文字列$y\in\{0,1\}^m$に対して, 先頭$m$ビットが$y$になるような$n$ビット文字列の全体を$S(y)\subseteq\{0,1\}^n$とします. $f'(x)$は$f(x)$の先頭$m$文字を取り出すことから, $f'(x)=y \iff f(x)\in S(y)$です. 従って
\begin{align*}
\Pr[f'(x_1)=y_1\text{ and }f'(x_2)=y_2] &= \sum_{z_1\in S(y_1),z_2\in S(y_2)} \Pr[f(x_1)=z_1\text{ and }f(x_2)=z_2] \\
&= \sum_{z_1\in S(y_1),z_2\in S(y_2)} \Pr[f(x_1)=z_1]\Pr[f(x_2)=z_2] & & \text{pairwise independence of $f$} \\
&= \Pr[f(x_1) \in S(y_1)]\Pr[f(x_2)\in S(y_2)] \\
&= \Pr[f'(x_1)=y_1]\Pr[f'(x_2)=y_2]
\end{align*}
より主張が得られます. (証明終)

補題2,3を組み合わせると, 以下の命題が成り立つことがわかります.

補題4.
任意の$m\le n$に対し, $\{0,1\}^n$から$\{0,1\}^m$へのペア独立ハッシュ関数$f$であって, 全ての$x\in\{0,1\}^n$に対して$f(x)$の分布が$\{0,1\}^m$上一様ランダムになるようなものが存在する. さらに$x\mapsto f(x)$の計算は$\mathrm{poly}(n)$時間で計算できる.


Valiant--Vaziraniの定理の証明

いよいよ定理1を証明します. $\phi\colon\{0,1\}^n\to\{0,1\}$を与えられた論理関数とし, 以下の帰着を考えます:

  1. $m\sim\{1,\dots,n\}$を一様ランダムに選ぶ.
  2. $f\colon\{0,1\}^n\to\{0,1\}^m$を補題4で保証されるペア独立ハッシュとする.
  3. $\phi'(x)=\phi(x)\land \langle f(x)=1^m\rangle$で定義される論理関数$\phi'$を出力する.

ステップ3では, Cook-Levinの定理の証明からコンピュータで計算できるアルゴリズムはその内部(レジスタや読み込みテープの位置など)の動きを回路で表現できることを用います. すなわち, 補題4では$x\mapsto f(x)$は多項式時間で計算できるので, この計算を回路で表現することによってBoolean関数$x\mapsto \langle f(x)=1^m\rangle$を$n$に関する多項式サイズの回路で表現することができます (SATを考えると, このようにペア独立ハッシュ関数の計算過程を表現できるというuniversalityが役にたつというわけです!). 従って$\phi\mapsto \phi'$を計算する上記の乱択アルゴリズムは多項式時間アルゴリズムです.

正当性の証明

$\phi'$の正当性を証明します. 与えられた論理関数$\phi$が充足不可能ならば$\phi'$を充足する割当も存在しません. 従って$\phi$が充足可能であるときに$\phi'$が充足可能である確率を評価すればよいです.

$\phi$が充足可能であるとし, $1\le N \le 2^n$を$\phi$の充足割当の個数とします. 充足割当が非常に多く, 例えば$N\ge 2^{n-3}$を満たすならば一様ランダムな$x\sim\{0,1\}^n$に対して$\phi(x)=1$かどうかをチェックすれば$\phi$の充足可能性が簡単に解けて, $\phi$が充足可能ならば定数$1$を$\phi'$として出力すればよいので, $N\le 2^{n-3}$を仮定します.

$m\sim[n]$が一様ランダムに選ばれているので, 確率$1/n$で
\begin{align}
2^{m-3}\le N \le 2^{m-2}
\end{align}
を満たします. 以後は$m$が(1)を満たすと仮定して議論を進めます.

$\phi$の充足割当の全体を$a_1,\dots,a_N$ ($a_i\in\{0,1\}^n$) とし, 確率変数$X_i=\langle f(a_i)=1^m \rangle$を考えると, $X=\sum_{i\in[N]} X_i$は$\phi'$の充足割当の個数に等しいです. ですので $\Pr[X=1]\ge 1/\mathrm{poly}(n)$を示すのが目標です. $N$と$m$の関係(1)より, $1/8 \le \mathbb{E}[X] \le 1/4$です.

任意の$x\in\{0,1\}^n$に対して$\Pr[f(x)=1^m]=1/2^m$なので, $\mathbb{E}[X]=N/2^m$を満たします. 従って
\begin{align*}
\Pr[X=1] &= \Pr[\exists i,X_i=1\text{ and }\forall j\neq i,X_j=0] \\
&= \sum_i \Pr[X_i=1\text{ and }\forall j\neq i,X_j=0] \\
&= \sum_i \Pr[\forall j\neq i,X_j=0\,|\,X_i=1]\Pr[X_i=1] \\
&= \sum_i (1-\Pr[\exists j\neq i,X_j=1\,|\,X_i=1])\Pr[X_i=1] \\
&\ge \sum_i \Pr[X_i=1] (1-\sum_{j\neq i} \Pr[X_j=1\,|\,X_i=1]\Pr[X_i=1]) \\
&= \sum_{i}\Pr[X_i=1]-\sum_{i\neq j} \Pr[X_i=1]\Pr[X_j=1] & & \text{pairwise independence}\\
&\ge \mathbb{E}[X] - \mathbb{E}[X]^2 \\
&\ge \frac{1}{8} - \frac{1}{16} & & \text{(1)}\\
&\ge \frac{1}{16}
\end{align*}
を得ます. $m$が一様ランダムなので, (1)が成り立つ確率は$1/n$です. 従って, $\phi$が充足可能のときに$\phi'\in U_{\mathrm{yes}}$となる確率は少なくとも$\frac{1}{16n}$となります. (証明終)

グラフ問題に対するペア独立性の応用

Valiant--Vaziraniの定理はSATに対してペア独立な関数を制約に加えることによって解の個数を減らすという帰着でしたが, 似たようなアイデアに基づいてグラフ上の部分グラフ数え上げ問題に対して解の個数を減らす帰着を与えることができます (ただし帰着後の問題は元の問題とは違う問題になってしまう).

次の二つの問題を考えます:

  1. 与えられたグラフ$G=(V,E)$が三角形を含むかどうかを判定せよ ($\mathrm{TRI}$)
  2. 有限体$\mathbb{F}_q$に対し, 各辺$e\in E$が$\mathbb{F}_q$の元を重みとして持つ辺重みグラフ$\tilde{G}$を考え, 辺重みの総和が$0$になるような三角形(以後はゼロ三角形と呼ぶ) の存在性を判定せよ ($\mathrm{ZWT}_q$)
問題1は隣接行列の三乗を計算して対角成分を見ればよいので$O(n^{\omega})$時間で計算できます. 問題2は精緻な計算量 (fine-grained complexity) の文脈で難しい問題とされていて, $q$が十分大きいときは任意の定数$\varepsilon>0$に対して$O(n^{3-\varepsilon})$時間で解けないと予想されています. ですので, 本質的には$\mathrm{TRI}$と$\mathrm{ZWT}_q$の間にはギャップがありそうだと思われており, $\mathrm{ZWT}$の方が難しいと思われています.

ここで, 問題2においてゼロ三角形が高々一つであることを保証する問題を$\mathrm{UZWT}$とします. $q\approx 3\log n$のとき, $\mathrm{TRI}$から$\mathrm{UZWT}_q$への乱択帰着が存在します.

証明のアイデア. 与えられた$\mathrm{TRI}$のインスタンス$G=(V,E)$に対し, 各辺に$\mathbb{F}_q$上一様ランダムな重みを付与したグラフ$\tilde{G}=(V,\tilde{E})$を考えます. $G$の各三角形$(u,v,w)$に対し, この三角形が$\tilde{G}$においてゼロ三角形になる確率は$1/q^2$です. なので適当な範囲から$q$をランダムに選ぶと, ある程度の確率で$q^2$が$G$の三角形の個数と大体同じくらいになります. また, $G$の三角形$T$に対して$X_T$を三角形$T$が$\tilde{G}$においてゼロ三角形になるかどうかの指示関数とすると, $(X_T)_T$はペア独立になります!

この事実を確認するために, 相異なる二つの三角形$T\neq T'$を考えます. $T$と$T'$が辺を共有しない場合は$X_T$と$X_{T'}$は独立です. 仮にこの二つの三角形が辺を共有していたとしても, $T\neq T'$より共有している辺の本数は必ず$1$本になり, これ以外の辺の重みは独立に決まるので$X_T$と$X_{T'}$は独立になります.

従って, ランダムに重みを付与したZWTのインスタンス$\tilde{G}$はある程度の確率でゼロ三角形を唯一含みます.




2024年1月7日日曜日

最近使っているツール

あけましておめでとうございます. 年明け早々に大変な災害や事故が発生して色々大変なことになってしまいましたが私の方は何事もなく平穏に過ごしております. この状況下において災難に遭われた方々の一日も早い快復をお祈りします.

さて, 昨今はchatGPTなど, 我々の取り巻く技術的進歩の状況は目まぐるしく変化しており, かなり数学に近い分野にいる私はそのようなツールに対し必要性を感じなかったために特に利用していませんでした. 使っているのはせいぜいoverleafとgoodnoteくらいでした.

一方で便利なツールがあるのに使わないのは非常にもったいない気がするので去年くらいから徐々に色々と導入しています. 中には特に合わないものもあったのですが, 色々紹介したいと思います.

1. Logseq

Logseq は勉強した内容をメモしておくツールで, 2023年の4月から使っています. iCloud上にファイルを置いておくことで複数のデバイス間で同期することができ, iPadからもアクセスできます.

例えばこちらの記事を執筆する際は次のようなメモを作成していました.


特徴としては, 文章というよりかは箇条書きを駆使した階層構造でメモしていきます. 特にブロック記法というものの中にQuoteというものがあり, 上図のDefinitionのような枠を気軽に作れるのが使っていてよかったです. 読んだ論文をまとめる際にも使っており, このようなメモを残しています. メモ間にリンクもはっています.


日誌という機能もあり, 気軽に日記を残すことができます.



2. Notion

Notionはメモ, タスク管理, ドキュメント等を行うオンラインサービスです. Legseqと比べるとカラフルで機能が豊富です. 例えば海外旅行などにいくときにこのようなページを作っていました.


オンライン上でノートが保存されているため, デバイス間の共有も非常に楽です. これまでは生活で使っていたのですが, 論文執筆をする際にTODOやメモを書いたり関連研究をまとめておくのに便利だなぁと気づいたので最近は積極的に利用しています.



それぞれの既存研究のリンクにはそれらをまとめるサブページを設けることもできます.

自分の中では
  • Logseqは勉強する際に書く気軽なメモ
  • Notionは論文を書くときのメモ
という立ち位置です. Obsidianというのもあるらしいのですが, どちらの方が良いとかはわかりません.

3. Visual Studio Code

Visual Studio Code (VS Code)は統合開発エディタです. 要するにプログラムのソースコードを書くためのエディタです. 講義の時を除いて自分は普段はプログラミングをしないので必要性を感じなかったのですが, VS Codeには様々な拡張機能を追加することができ, 実は論文執筆にも利用することができます.

特にoverleafに繋げるプラグインが存在しており, これを使ってoverleaf上のファイルの編集も行えます. ほかのプラグインと併用してスペルチェックなどができる上に, LaTeXのコンパイル時間が早くなったりして便利です.

設定が少し面倒なのですが, 導入の解説をしてくれるページが色々あるので, VS Codeをインストールした初日になんとかoverleafと繋げて文章を編集するところまでもっていけました.

個人的にはCookieでログインする, という手順で少し詰まった (公式ドキュメントではFireFoxの画面で説明されてた) のですが, google chromeでは右上の3点が縦に並んでいるボタンから「その他のツール」→「デベロッパーツール」と進んでいき, 

ApplicationというタブにあるCookieのところから値をコピーしていけば良いです.

拡張機能の中にはDeepLやGithub Copilotなどがあり, これらと連携することで英語執筆が非常に楽になるそうです (自分はまだ試していない). 

今後使おうと思っているもの

最後に, 自分が気になっているものについて列挙しておきます. 「こういうのがオススメ」というのがありましたら教えていただけると嬉しいです.
  • draw.io
    • 今まではkeynoteで図を作ってたけど, いちいち開くのは面倒だと思っていた.
    • draw.ioを使えば気軽に図を描ける. グラフとかフローチャートが描きやすそう.
    • VS Codeにプラグインがある.
    • 軽く触ってみた感触だとオブジェクトとオブジェクトの間にいい感じで曲線をひくのがむずそう (本当はもっと楽な方法がありそうではある)
  • Github Copilot
    • プログラミングの支援サービスのように書いてあるが, 論文執筆にも有用そうなことが書いてある記事を見かけたので自分も使ってみようかなと.
    • どれくらい有用なのかを見極めたい.
    • VS Codeの拡張機能で導入できる.
  • ChatGPT

2023年12月20日水曜日

ランダムウォークの混交時間の解析(スペクトルギャップと修正された対数ソボレフ不等式)

スペクトルギャップを用いたランダムウォークの混交時間の解析は前々から知ってたけど対数ソボレフ不等式を用いた解析は知りたいなぁと長年思っていてようやく理解できてきたのでまとめてみました.

連結かつ非二部なグラフ上の離散時間単純ランダムウォーク(隣接点に一様ランダムに遷移するランダムウォーク)の分布は必ず定常分布と呼ばれる分布に収束することが知られており, その収束のレートを測る指標として混交時間(mixing time)が知られています. 時刻$t$においてランダムウォークが頂点$v$にいる確率を$p_t(v)$と書き, $\pi\in[0,1]^V$を定常分布とします (基本的にベクトルは行ベクトルとして扱います). 通常のランダムウォーク(一様ランダムな隣接点に遷移するランダムウォーク)では$\pi(v) = \frac{\deg(v)}{2|E|}$となることが知られています.

より一般に, 頂点$u$から$v$への遷移確率$P(u,v)$を成分として持つ行列を遷移確率行列(transition matrix)と呼び, $\pi P = \pi$を満たす分布$\pi$を定常分布(stationary distribution)と呼び, 定常分布が存在するランダムウォークを可逆(reversible)であると言います. 時刻$t$におけるランダムウォークの分布ベクトル$p_t$は$p_t = p_{t-1}P$を満たすので, この等式の両辺を$t\to\infty$をとれば確かに$p_t$が収束するとしたらそれは定常分布になりそうな感じがします. 

可逆なランダムウォークは非常に重要なクラスであり, 定常分布が誘導するある計量を考えると遷移確率行列を対称行列として扱えるのが嬉しい性質で, 例えば$P$が実固有値を持つのでエクスパンダー性の議論などと相性が良いです (例えばこの記事参照). 基本的に無向グラフ上のランダムウォーク(辺重みがあっても良い)はこのクラスに属しますが, 有向グラフにすると可逆性が失われます. 本記事では主に可逆なランダムウォークを扱います.

$P(u,v)>0$のときに有向辺$(u,v)$を張って得られる有向グラフ$G$が強連結ならば$P$は既約(irreducible)であると言い, $G$の全ての有向閉路の長さのgcdが$1$であるならば非周期的(aperiodicity)であると言います (例えば二部グラフなら閉路長が偶数なので周期的). 既約ならば定常分布は一意に存在し, 非周期的ならばランダムウォークの分布は$\pi$に収束することが知られています (二部グラフ上のランダムウォークはステップ数の偶奇で分かれるので収束しない). ランダムウォークの文脈では確率$1/2$の自己ループによって長さ1の閉路を付与することで必ず非周期性を持たせられます. また, 連続時間ランダムウォークを考えると既約性だけで定常分布への収束性を保証できます. 自己ループ確率を$1/2$にすると遷移確率行列$P$が半正定値性を持ち, 例えば$\sqrt{P}$といった行列を考えることができるのが嬉しいポイントで, 例えば[Oliveira and Peres, 2019]ではこの分解を巧妙に使って到達時間(hitting time)のバウンドを証明しています.

混交時間の話に戻ります. 二つの分布$p_t,\pi\in[0,1]^V$の統計距離$d_{\mathrm{TV}}(p_t,\pi):=\frac{1}{2}\|p_t - \pi\|_1$を考え, 任意の初期分布$p_0$に対しこの値が$\epsilon$以下になるような最小の$t$を$\epsilon$-混交時間と呼び, $t_{\mathrm{mix}}(\epsilon)$で表します. すなわち
\begin{align*}
t_{\mathrm{mix}}(\epsilon) = \inf\{t\geq 0\colon d_{\mathrm{TV}}(p_t,\pi)\leq\epsilon\text{ for any }p_0\}.
\end{align*}
なお, 初期分布$p_0$は各頂点上のDirac測度の凸結合で表せるので, 最悪の頂点からスタートした場合の混交スピードを測るという意味で最悪時の指標になっています. 例えば初期状態が定常分布だった場合は$0$ステップで混交しているので平均時みたいなものはあまり考えません.

ランダムウォークとはグラフ上を局所的に遷移する過程ですので一般に解析が難しそうに見えますが, 時刻$1$から$T$を長さ$t_{\mathrm{mix}}(\epsilon)$の区間で区切るとそれぞれで分布が$\pi$に収束するため, それぞれの区間の最後では$\pi$からランダムに頂点を選んだものとみなすことができます. 例えば正則グラフを考えると$\pi$は一様分布となるので, $100n\log n$個の区間を考えるとそれぞれで固定した頂点$v$に行き着く確率はおおよそ$\pi(v)=1/n$なので, ランダムウォークが一度も頂点$v$を訪れない確率は$(1-1/n)^{100\log n}\leq n^{-100}$となり, $v$に関するunion boundをとれば全ての頂点を訪問することがわかります. すなわち混交時間を抑えることによって, 全訪問時間(cover time)も抑えることができます. こちらの記事で, このトピックに関する簡単なサーベイをまとめています.

このように, 混交時間を抑えることによって到達時間や全訪問時間といった他のパラメータに対する上界も得ることができるため, 混交時間の解析はランダムウォークにおいては非常に重要な研究課題となっています. 現代はマルコフ連鎖モンテカルロ法(MCMC)の解析, 特にIsing modelやPotts modelに対するGlauber dynamicsなどの混交時間の解析が大きな注目を集めています. また, Langevin dynamicsによって最適化問題を表現し, その混交時間が抑えられればその最適化問題に対するアルゴリズムを与えることができます.

混交時間を抑えるためには$d_{\mathrm{TV}}(p_t,\pi)$を上から抑える必要があります. 本記事では, 

  • Cauchy-Schwarzの不等式を使って$\chi^2$-ダイバージェンスで上から抑える (スペクトルギャップ)
  • Pinskerの不等式を使ってKL-ダイバージェンスで上から抑える (修正された対数ソボレフ不等式)
という二つのよく知られる方法について, ダイバージェンスの観点から紹介します. スペクトルバウンドのみを理解したい場合はダイバージェンスを介さずとも良いのですが, 修正された対数ソボレフ不等式に基づく解析も理解するならば両方をダイバージェンスの縮小という観点で理解した方が見通しがよくなると思ったからです.

なお, オリジナルの対数ソボレフ不等式は元々は関数解析の分野の概念ですが, 本稿では関数解析には触れず, マルコル連鎖に焦点を絞って解説していきます.

スペクトルギャップに基づくバウンド

線形代数です. アイデアとしては, $\ell^1$ノルムを$\ell^2$ノルムで抑えて$\ell^2$ノルムをバウンドするためにスペクトルを使うというものです. $p_t-\pi = (p_{t-1} - \pi)P$であり, $p_{t-1}-\pi$は$P$の第一固有ベクトル$\mathbf{1}$と直交するので, $P$の第二固有値を見ることが肝要になります.

この議論をダイバージェンスの観点からと述べるために, $\chi^2$-ダイバージェンスと呼ばれる値を定義します. 確率変数$X$の台を$\mathsf{supp}(X)=\{x\colon \Pr[X=x]>0\}$で定めます.

定義1 ($\chi^2$-ダイバージェンス)
離散値をとり, $\mathsf{supp}(X) \subseteq \mathsf{supp}(Y)$を満たす二つの確率変数$X,Y$の$\chi^2$-ダイバージェンス$\chi^2(X||Y)$を以下で定義する:
\begin{align*}
\chi^2(X||Y) &= \sum_{a\in \mathsf{supp}(Y)} \Pr[Y=a]\left(\frac{\Pr[X=a]}{\Pr[Y=a]}-1\right)^2 \\
&= \mathbb{E}_{a\sim Y}\left[ \left( \frac{\Pr[X=a]}{\Pr[Y=a]} - 1 \right)^2 \right].
\end{align*}
また, $\mathsf{supp}(X)\not\subseteq \mathsf{supp}(Y)$であった場合は$\chi^2(X||Y)=\infty$と定める.

この量は二つの分布の乖離度を測る指標として知られているのですが, 距離の公理は満たしません (そもそも$\chi^2(X||Y) = \chi^2(Y||X)$は一般に成り立たない). イメージとしては確率変数$X,Y$がどれくらい識別しにくいかを表す指標だと思ってもらえれば十分です.

今回の記事では特に扱いませんが, ダイバージェンス全般において特筆すべき性質としては

  • 非負性: $\chi^2(X||Y)\geq 0$.
  • データ処理不等式: 任意の決定的アルゴリズム(関数)$f$に対し, $\chi^2(f(X)||f(X))\leq \chi^2(X||Y)$.
  • 凸性: 確率変数をその分布ベクトルとみなし, $\chi^2$を二つの分布から実数値を返す関数とみなしたときに$\chi^2$は凸関数.

がよく知られています. 特に凸性はJensenの不等式との相性が良いので非常によく使います. また, $\chi^2$ダイバージェンスと統計距離との間には以下の関係が成り立ちます.

補題2.
離散値をとる二つの確率変数$X,Y$に対して
\begin{align*}
d_{\mathrm{TV}}(X,Y) \leq \frac{1}{2}\sqrt{\chi^2(X||Y)}.
\end{align*}

証明.
$Y$の台を$\Omega$とし, $x(a)=\Pr[X=a],y(a)=\Pr[Y=a]$とします. $\mathsf{supp}(X)\not\subseteq\mathsf{supp}(X)$の場合は右辺が$\infty$となり自明なので, $\mathsf{supp}(X)\subseteq\mathsf{supp}(Y)$を仮定すると,
\begin{align*}
d_{\mathrm{TV}}(X,Y) &= \frac{1}{2}\sum_{a\in \Omega}\left| x(a) - y(a) \right| \\
&= \frac{1}{2}\sum_{a\in\Omega} \sqrt{y(a)}\cdot \sqrt{y(a)} \left| \frac{x(a)}{y(a)} - 1 \right| \\
&\leq \frac{1}{2}\sqrt{\sum_{a\in\Omega}y(a)}\cdot \sqrt{\sum_{a\in\Omega}y(a)\left(\frac{x(a)}{y(a)} - 1 \right)^2} & & \text{the Cauchy--Schwarz inequality} \\
&= \frac{1}{2}\sqrt{\chi^2(X||Y)}.
\end{align*}
より主張を得ます. (証明終)

ランダムウォークに話を戻すと, 補題2より$\chi^2(p_t||\pi)$の上界が得られれば混交時間のバウンドを得ることができます. 以下の補題で$\chi^2(p_t||\pi)$を$\ell^2$ノルムで抑えます.

補題3.
定常分布$\pi$を持つ可逆なランダムウォークに対して, $\pi_{\min}:=\min_{v\in V}\pi(v)$とすると,
\begin{align*}
\chi^2(p_t||\pi) \leq \pi_{\min}^{-1}\cdot \|p_t - \pi\|_2^2.
\end{align*}

証明.

\begin{align*}
\chi^2(p_t||\pi) &= \sum_{v\in V}\pi(v)\cdot \left(\frac{p_t(v)}{\pi(v)}-1\right)^2 \\
&= \sum_{v\in V}\pi(v)\cdot\left(\frac{p_t(v)^2}{\pi(v)^2} - \frac{2 p_t(v)}{\pi(v)} + 1\right) \\
&= \sum_{v\in V}\pi(v)\left(\frac{p_t(v)}{\pi(v)} - 1\right)^2 \\
&= \sum_{v\in V}\frac{1}{\pi(v)}\cdot \left( p_t(v) - \pi(v) \right)^2 \\
&\leq \pi_{\min}^{-1}\cdot \|p_t - \pi\|_2^2.
\end{align*}
よって主張を得る. (証明終)

最後に行列$P$のスペクトルを用いた混交時間の上界を導出します.

定理4.
遷移確率行列$P$に従い, 定常分布$\pi$を持つ可逆なランダムウォークを考える. $\lambda(P)=\max_{\|x\|_2=1,x\bot \mathbf{1}}\|Px\|$とする. $\lambda(P)<1$ならば,
\begin{align*}
d_{\mathrm{TV}}(p_t,\pi) \leq \frac{\lambda(P)^t}{\sqrt{2\pi_{\min}}}.
\end{align*}
特に, スペクトルギャップ$\gamma:=1-\lambda(P)$に対し, $\tau_{\mathrm{mix}}(\epsilon) = O\left(\gamma^{-1}(\log(1/\epsilon) + \log(1/\pi_{\min}))\right)$.

Remark. $\lambda(P)$は$P$の非自明な第二固有値になります. すなわち, $P$の固有値を$1=\lambda_1 \geq \lambda_2\geq \dots \geq \lambda_{|V|}$としたときに$\lambda(P) = \max\{\lambda_2,|\lambda_{|V|}|\}$です. これはCourant-Fischerの定理(行列の固有値に関するmin-max定理)からわかります. エクスパンダーグラフの文脈では$\lambda(P)$が小さいグラフ (言い換えると$\gamma\approx 1$) を考えるのに対し, 例えば混交時間が多項式かどうかを気にするMCMCの文脈では$\gamma \geq 1/\mathrm{poly}(n)$かどうかを気にするので, $\gamma\to 0$の時の漸近挙動におけるオーダーを考えます.

証明. 分布$p_t$は等式$p_t = p_{t-1}P$を満たすので,
\begin{align*}
\|p_t - \pi\|_2 = \|(p_{t-1} - \pi) P\|_2 \leq \|p_{t-1} - \pi\|_2\cdot \lambda(P)
\end{align*}
を得る (最後の不等式ではベクトル$p_t-\pi$がall-one ベクトル$\mathbf{1}$に直交することを用いた).

補題2,3より,
\begin{align*}
d_{\mathrm{TV}}(p_t,\pi) &\leq \frac{1}{2\sqrt{\pi_{\min}}}\cdot \|p_t - \pi\|_2 \\
&\leq \frac{1}{2\sqrt{\pi_{\min}}} \cdot \lambda(P)^t \|p_0 - \pi\|_2 \\
&\leq \frac{\lambda(P)^t}{\sqrt{2\pi_{\min}}}
\end{align*}
特に, $\lambda(P)\leq 1-\gamma\leq\mathrm{e}^{-\gamma}$ならば$d_{\mathrm{TV}}(p_t,\pi) \leq \frac{\exp(-\gamma t)}{\sqrt{2\pi_{\min}}}\leq \epsilon$とおくと混交時間のバウンドを得る. (証明終)


修正された対数ソボレフ不等式

スペクトルギャップの章は線形代数でしたが, こちらは情報理論です. Pinskerの不等式を使って統計距離をKLダイバージェンスで抑え, KLダイバージェンス$\mathrm{KL}(p_t||\pi)$がexponentialにdecayする議論を紹介します. この時の指数のrateが修正された対数ソボレフ不等式となります. このことを述べるためにまず, Dirichlet形式と連続時間マルコフ連鎖を導入します.

KLダイバージェンスについて. 二つの分布$\mu,\nu\in[0,1]^V$に対し, それらのKLダイバージェンスを, $\mathsf{supp}(\mu)\subseteq\mathsf{supp}(\nu)$のとき
\begin{align*}
\mathrm{KL}(\mu||\nu) = \mathbb{E}_{v\sim\mu}\left[ \log \frac{\mu(v)}{\nu(v)}\right],
\end{align*}
$\mathsf{supp}(\mu)\not\subseteq\mathsf{supp}(\nu)$のとき, $\mathrm{KL}(\mu||\nu)=\infty$と定義します. すると, Pinskerの不等式より, $d_{\mathrm{TV}}(\mu,\nu)\leq \frac{1}{2}\sqrt{\mathrm{KL}(\mu||\nu)}$が成り立ちます. 混交時間の文脈では$d_{\mathrm{TV}}(p_t,\pi)\leq \frac{1}{2}\sqrt{\mathrm{KL}(p_t || \pi)}$より, $p_t$と$\pi$のKLダイバージェンスを抑えれば混交時間も抑えることができます.

Dirichlet形式について. 行列$M\in\mathbb{R}^{V\times V}$を線形作用素$M\colon\mathbb{R}^V\to\mathbb{R}^V$ととらえます. 定常分布$\pi$を持つ遷移確率行列$P$を考えます. 空間$\mathbb{R}^V$に内積$\langle \cdot,\cdot\rangle$を
\begin{align*}
\langle f,g\rangle = \sum_{v\in V}f(v)g(v)\pi(v) = \mathbb{E}_{v\sim\pi}[f(v)g(v)]
\end{align*}
を定めます.

定義5.
定常分布$\pi$を持つ$V$上の可逆なマルコフ連鎖$P$に対し, そのDirichlet形式$\mathcal{E}\colon \mathbb{R}^V\times\mathbb{R}^V\to\mathbb{R}$を
\begin{align*}
\mathcal{E}(f,g) = \langle (I-P)f,g\rangle =\sum_{v\in V}\pi(v) (I-P)f(v) g(v)
\end{align*}
で定める.

正規化されたラプラシアン$L=I-P$を用いると, $\mathcal{E}(f,g)=\langle Lf,g \rangle$と表すことができます. 特に$f=g$のとき,
\begin{align*}
\mathcal{E}(f,f) &= \langle f,f\rangle - \langle Pf,f\rangle \\
&= \frac{1}{2}\mathbb{E}_{x\sim \pi,y\sim P(x,\cdot)}[f(x)^2 - 2f(x)f(y) + f(y)^2] \\
&= \frac{1}{2}\mathbb{E}_{x\sim\pi,y\sim P(x,\cdot)}[(f(x) - f(y))^2]
\end{align*}
となり, ランダムな辺$xy$を選んだときの$f$の二乗差の平均となります. これを, $\mathcal{E}(f,f)$は関数$f$のエネルギーのようなものだと思ってください. 

連続時間マルコフ連鎖について. 可逆な遷移確率行列$P$に従う離散時間ランダムウォークを$(X_t)_{t=0,1,\dots}$とします. これを連続時間ランダムウォークに拡張します. 一般に状態空間が離散であるような連続時間のランダムウォークでは遷移時刻の間隔は平均$1$の指数分布$\mathrm{Exp}(1)$に従うものを考えます (指数分布とは$\Pr[\mathrm{Exp}(1)\geq t]=\mathrm{e}^{-t}$を満たす連続値をとる確率分布です). 以下でもう少しフォーマルに定義します. 確率変数$T_1,T_2,\dots$を$\mathrm{Exp}(1)$の独立なサンプルとし, $T_0=0$と定義します. 各$t$に対し$T_i \leq t < T_{i+1}$を満たす$i$を$i(t)$と書くことにします. 連続時間マルコフ連鎖とは, $Y_t=X_{i(t)}$で定義される連続時刻$t\in\mathbb{R}_{\geq 0}$で添字づけられた確率変数の族$(Y_t)_{t\in\mathbb{R}_{\geq 0}}$です. 連続時間ランダムウォークについても時刻$t$における分布$q_t\in[0,1]^V$を定義できます.

熱核について. $H_t = \mathrm{e}^{-t}\cdot \sum_{i=0}^\infty \frac{(tP)^i}{i!} = \mathrm{e}^{-t(I-P)}$とします. この行列はランダムウォークの分野では熱核(heat kernel)と呼ばれます (おそらく物理や微分方程式の文脈からきているのでしょうが私は専門外なので知りません). 証明は[Levin and Peres, 2017; Chapter 20]に譲りますが, $H_t(u,v)$は頂点$u$からスタートした連続時間ランダムウォークが時刻$t$において頂点$v$にいる確率を表します. 初期頂点の分布を$q_0$とすると, 時刻$t$におけるランダムウォークの分布は$q_t=q_0 H_t$と表すことができます. これを用いると連続時間ランダムウォークの$\epsilon$-混交時間$t^{\mathrm{cont}}_{\mathrm{mix}}(\epsilon)$を, 離散時間の場合と同様に
\begin{align*}
t^{\mathrm{cont}}_{\mathrm{mix}}(\epsilon) = \inf\{t\geq 0\colon d_{\mathrm{TV}}(q_t,\pi)\leq \epsilon \text{ for any $q_0$}\}
\end{align*}
で定義できます.

連続時間と離散時間の比較. 連続時間と離散時間は期待値の意味では時刻$T\in\mathbb{N}$においてどちらも$T$回の遷移を行うため, その時点でのランダムウォークの分布$p_T,q_T$はほぼ同じ性質を有します. 従って混交時間についても離散時間と連続時間でほぼ同じになります. このことは遷移回数の集中性を使って簡単に説明できます. 離散時間ランダムウォークの$(\epsilon/2)$-混交時間を$t^*$とおき, $10t^*$回目の遷移が発生した瞬間の時刻$T^*:=T_{10t^*}$を考えます. 時刻$T^*$は$10t^*$個の独立な指数分布$\mathrm{Exp}(1)$の和となり, この値は期待値$10t^*$に集中するため, 確率$1-2^{-\Theta(t^*)}$で$T^*\geq t^*$が成り立ちます. 従って
\begin{align*}
d_{\mathrm{TV}}(Y_{T^*},\pi) \leq d_{\mathrm{TV}}(X_{t^*},\pi) + \Pr[T^*<t^*] \leq \frac{\epsilon}{2} + 2^{-\Theta(t^*)}.
\end{align*}
を得ます. 適当な定数$c>0$に対して$t^*\geq c\log(1/\epsilon)$であれば$d_{\mathrm{TV}}(Y_{T^*},\pi)\leq\epsilon$が成り立つので, $t^{\mathrm{cont}}_{\mathrm{mix}}(\epsilon) = O(t_{\mathrm{mix}}(\epsilon/2) + \log(1/\epsilon))$を得ます ($\log(1/\epsilon)$の項は$t^*\ll \log(1/\epsilon)$の場合をケア). 逆方向の不等式も同様に証明できます.

修正された対数ソボレフ定数について. 上記の議論から, 連続時間における$\mathrm{KL}(q_t||\pi)$を抑えることによって元の離散時間における混交時間をバウンドできます. $\mathrm{KL}(q_t||\pi)$の減少を知りたいので, KLダイバージェンスを$t$で微分してみます. 関数$\phi_t \colon v\mapsto  \frac{q_t(v)}{\pi(v)}$とすると,

\begin{align*}
\frac{\mathrm{d}}{\mathrm{d}t} \mathrm{KL}(q_t||\pi) &= -\mathcal{E}(\phi_t,\log \phi_t)
\end{align*}
を得ます. この式の右辺の減少スピードは, 以下で定義される修正された対数ソボレフ定数によって与えられます.

定義6.
定常分布$\pi$を持つ$V$上の可逆なマルコフ連鎖$P$を考える. 関数$\phi\colon V\to\mathbb{R}_{>0}$に対し, $\mathrm{Ent}[\phi]$を
\begin{align*}
\mathrm{Ent}[\phi] = \mathbb{E}_{v\sim\pi}\left[ \phi(v) \log\frac{\phi(v)}{\mathbb{E}_{\pi}[\phi]} \right]
\end{align*}
とし, 修正された対数ソボレフ定数 (modified log-Sobolev constant) $\rho$を
\begin{align*}
\rho = \inf\left\{ \frac{\mathcal{E}(\phi, \log \phi)}{\mathrm{Ent}(\phi)} \colon \phi\geq 0,\mathrm{Ent}[\phi]\neq 0 \right\}
\end{align*}
で定める.

分布$q,\pi$のKLダイバージェンス$\mathrm{KL}(q||\pi)$は$\mathrm{KL}(q||\pi)=\mathrm{Ent}\left[\frac{q}{\pi}\right]$という関係が成り立ちます (このことからKLダイバージェンスを相対エントロピーと呼ぶのも納得ですね!). これを先ほどの微分の式に代入すると, $\rho$の定義より
\begin{align*}
\frac{\mathrm{d}}{\mathrm{d}t} \mathrm{Ent}[\phi_t] = -\mathcal{E}(\phi_t,\log \phi_t) \leq -\rho\cdot \mathrm{Ent}[\phi_t]
\end{align*}
を得ます. この微分方程式を解きます. $g(t) = \mathrm{Ent}[\phi_t]$とすると, 両辺を$g(t)$で割って
\[
\frac{\mathrm{d}}{\mathrm{d}t}\log g(t) \leq -\rho.
\]
積分定数$C_0$を使うと
\[
\log g(t) \leq -\rho t + C_0.
\]
従って$g(t) \leq \mathrm{e}^{-\rho t}\cdot g(0)$と表せます. 元々$g(t)=\mathrm{Ent}[\phi_t]=\mathrm{KL}(q_t||\pi)$だったので,
\[
\mathrm{KL}(q_t||\pi) \leq \mathrm{e}^{-\rho t}\mathrm{KL}(q_0||\pi)
\]
を得ます. 

定理7.
定常分布$\pi$を持つ$V$上の可逆なマルコフ連鎖$P$を考え, $\rho$を修正された対数ソボレフ定数とする. このとき,
\begin{align*}
t_{\mathrm{mix}}(\epsilon) = O(\rho^{-1}(\log(1/\epsilon) + \log\log(1/\pi_{\min}))).
\end{align*}
で定める.

証明.
ここでは, 離散時間と連続時間のランダムウォークの比較で主張していた関係を認め, $t_{\mathrm{mix}}(\epsilon) = O(t^{\mathrm{cont}}_\mathrm{mix}(\epsilon/2))$を認めることとします. 以後では$t^{\mathrm{cont}}_{\mathrm{mix}}(\epsilon/2)$を抑えるために, $q_t$を連続時間ランダムウォークの時刻$t$における分布とします. Pinskerの不等式および前段落の議論から
\begin{align*}
d_{\mathrm{TV}}(q_t,\pi) &\leq \frac{1}{2}\sqrt{\mathrm{KL}(q_t||\pi)} \\
 &\leq \frac{1}{2}\mathrm{e}^{-\rho t / 2}\sqrt{\mathrm{KL}(q_0||\pi)} \\
&\leq \frac{1}{2}\mathrm{e}^{-\rho t / 2}\sqrt{\log(1/\pi_{\min})}.
\end{align*}
なお, 最後の式はKLダイバージェンスの定義から任意の分布$q$に対して$\mathrm{KL}(q||\pi)\leq \log(1/\pi_{\min})$が成り立つことを用いています. 従って, 適当な$t=O(\rho^{-1}(\log(1/\epsilon) + \log\log(1/\pi_{\min})))$に対して, この値は$\epsilon/2$以下になるので主張を得ます. (証明終)

スペクトルギャップと修正された対数ソボレフ定数の関係については以下の結果が知られています

定常分布$\pi$を持つ$V$上の可逆なマルコフ連鎖$P$を考え, $\gamma$をスペクトルギャップ, $\rho$を修正された対数ソボレフ定数とする. このとき,
\begin{align*}
\rho \leq 2\gamma
\end{align*}
が成り立つ.

したがって修正された対数ソボレフ定数の下界を得るのはスペクトルギャップ以上に難しいことが分かります. しかしながら定理4と定理7を比較すると, $1/\pi_{\min}$に対する依存が大きく異なっていることが分かります. 例えば$n$頂点のグラフ上での解析を考えると$\log n$と$\log\log n$の差しかないのでそこまで大きくはなさそうなのですが, イジングモデルなど状態空間が指数的に膨大ならばその差は非常に大きくなってくるので, 修正された対数ソボレフ不等式のテクニックが有用になってきます.


参考文献


2023年12月14日木曜日

Pinskerの不等式の簡単な証明

 Pinskerの不等式とは, KLダイバージェンスと統計距離(total variation distance)の関係を表す不等式です. 本記事ではこれを紹介し, こちらの論文Yihong Wuの講義資料のTheorem 4.5に載っている非常にトリッキーな証明を紹介します.

有限集合$\Omega$を値域とする二つの確率変数$X,Y$に対して

  • 統計距離: $d_{\mathrm{TV}}(X,Y) = \frac{1}{2}\sum_{x\in \Omega}|\Pr[X=x] - \Pr[Y=y]| = \sup_{A\subseteq \Omega}|\Pr[X\in A] - \Pr[Y \in A]|$.
  • KLダイバージェンス: $\mathrm{KL}(X||Y)=\sum_{a\in\mathsf{supp}(Y)}\Pr[X=a]\ln\frac{\Pr[X=a]}{\Pr[Y=a]}$.

定理 (Pinskerの不等式)
\[
d_{\mathrm{TV}}(X,Y) \leq \sqrt{\frac{1}{2}\mathrm{KL}(X||Y)}.
\]

証明では, KLダイバージェンスに関する以下のデータ処理不等式(data processing inequality)を認めることにします.

補題 (データ処理不等式)
$\Omega,\Omega'$を有限集合とする. 任意の関数$f\colon \Omega\to\Omega'$と$\Omega$上に値をとる任意の確率変数$X,Y$に対し
\[
\mathrm{KL}(f(X),f(Y)) \leq \mathrm{KL}(X,Y).
\]

KLダイバージェンス$\mathrm{KL}(X||Y)$は直感的には二つの確率変数$X,Y$の識別しにくさを表す指標であり, データ処理不等式とは二つのデータ$X,Y$をアルゴリズム$f$で処理して得られるデータ$f(X),f(Y)$を考えたとき, データ処理不等式とはデータを処理しても識別しにくさは上がらないことを意味します.

一般にデータ処理不等式は決定的アルゴリズム$f$を乱択アルゴリズムに置き換えても成り立ちます. こちらの講義資料が参考になると思います.

Pinskerの不等式の証明.

大まかな流れとしてはデータ処理不等式を用いて$01$値確率変数の場合に帰着して, あとは積分を計算します.

統計距離の定義および$\Omega$が有限であることから, ある集合$E\subseteq \Omega$が存在して$d_{\mathrm{TV}}(X,Y)=\Pr[X\in A] - \Pr[Y \in A]$が成りたちます. この集合$A$の指示関数を$f$とします. すなわち$f\colon\Omega\to\{0,1\}$は$x\in A$ならば$f(x)=1$, そうでなければ$f(x)=0$です.

データ処理不等式から$\mathrm{KL}(f(X),f(Y))\leq \mathrm{KL}(X,Y)$なので, ベルヌーイ試行$f(X),f(Y)$に対してPinskerの不等式が証明できれば証明が完了します.

では, $X,Y$がそれぞれベルヌーイ試行で$X\sim\mathrm{Ber}(p),Y\sim\mathrm{Ber}(q)$とします (すなわち$\Pr[X=1]=p,\Pr[Y=1]=q$). このとき

  • $d_{\mathrm{TV}}(X,Y)=|p-q|$,
  • $\mathrm{KL}(X||Y)=p\ln\frac{p}{q} + (1-p)\ln\frac{1-p}{1-q}$
です. 従って, 任意の$p,q\in[0,1]$に対して不等式
\begin{align}
2(p-q)^2 \leq p\ln\frac{p}{q} + (1-p)\ln\frac{1-p}{1-q}
\end{align}
を示せば良いです. $p,q\in\{0,1\}$の場合は4通り試せば明らかに成り立つことが確認できます.

$p,q\in(0,1)$とし, $f(x) = p\log x + (1-p)\log(1-x)$とします. すると
\begin{align*}
(\mathrm{RHS}) &= f(p) - f(q) \\
&= \int_q^p f'(x)\mathrm{d}x \\
&= \int_q^p \frac{p-x}{x(1-x)}\mathrm{d}x \\
&\geq 4\int_q^p (p-x)\mathrm{d}x \\
&= 2(p-q)^2 = (\mathrm{LHS})
\end{align*}
より証明を得ます. (証明終)


2023年12月12日火曜日

確率論的手法の計算論的な複雑性 (大雑把なサーベイ)

組合せ論や計算量理論ではしばし, 良い性質を持った離散構造の存在性が議論されます. 例えば

といった離散構造はそれ自体が興味の対象となるだけではなく非常に幅広い応用をもち, 擬似ランダム生成器, 良い性質を持つ誤り訂正符号, 計算量下界の証明, 脱乱択の証明, 近似アルゴリズムの構成, アルゴリズムの近似率の限界(PCP定理)などに用いられます.

しかしながらこれらの存在性の証明の多くはしばし確率論的手法や鳩の巣原理などに基づいた非構成的な手法もしくは非効率的な構成に基づく証明になっています. 実際の応用では(特に擬似ランダムネスの文脈では)しばし効率的(計算量が小さい)かつ決定的(ランダムネスを使わない)な構成が求められます. これを確率論的手法の脱乱択化と呼ぶことにします. 

確率論的手法の脱乱択化は組合せ論と計算量理論が密接に関連しているとても面白いトピックですので, ここでは非常に大雑把にいくつかのトピックを紹介していきます. なお, この辺りの擬似ランダムネスに関するトピックはVadhanの本に詳しいです.

疎なエクスパンダーグラフ (ラマヌジャングラフ)


頂点数$n$の$d$-正則グラフ$G$を考えます (ただし$n\geq 2, d\geq 3$). 隣接行列$A$の固有値を大きい順に並べて$d=\lambda_1\geq \lambda_2 \geq \dots \geq \lambda_n$とします. すると, 
\[
\lambda_2 \geq 2\sqrt{d-1} - \frac{2\sqrt{d-1}-1}{\lfloor \mathrm{diam}(G)/2\rfloor}
\]
が成り立つことが知られています(Alon-Boppanaの定理). ここで$\mathrm{diam}(G)$はグラフ$G$の直径で, Moore bound (または幅優先探索に基づく議論)により, $\mathrm{diam}(G)=\Omega(\log_{d-1} n)$が成り立ちます. 従って上記のバウンドにより, $d\geq 3$を固定し$n\to\infty$の漸近を考えると$\lambda_2 \geq 2\sqrt{d-1} - O(1/\log n)$となります.

では, このバウンドは(漸近的に)タイトなのでしょうか? 実はこの問いはランダム正則グラフを考えることで簡単に肯定的に解けます. $n$頂点$d$正則グラフ全体の集合から一様ランダムに選んだグラフを$G_{n,d}$と書くと, Friedman(2003)によると, $n\to\infty$の漸近的を考えると, 確率$1-n^{-0.1}$で$G_{n,d}$は
\[
\lambda_2 \leq 2\sqrt{d-1} + O\left(\left(\frac{\log\log n}{\log n}\right)^2\right)
\]
を満たすことが知られています. なので, 無限に多くの$n$について上記を満たす$n$頂点$d$正則グラフがとれるため, $n\to \infty$の漸近においてAlon-Boppanaの定理のバウンドはほぼタイトであることがわかります. ちなみにFriedman(2003)の定理の別証明を与えたという論文も知られています.

しかしながらこの証明は非構成的であるという点で応用向きではありません. スペクトルグラフ理論では, $\lambda_2 \leq 2\sqrt{d-1}$を満たすグラフをラマヌジャングラフと呼びます. ある$d\geq 3$に対して$d$-正則ラマヌジャングラフの列$(G_i)_{i=1,2,\dots}$であって, $G_i$の頂点数が$i\to\infty$で発散するようなものが陽に構成できるか, という問題を考えます. この問題はLubotzky, Phillips, Sarnak (1988)によって解決され, その後も様々な進展を見ています.
  • Lubotzky, Phillips, Sarnak (1988)は$p\equiv 1 \bmod 4$を満たす全ての素数$p$に対して$(p+1)$-正則ラマヌジャングラフの列を代数的に構成する方法を与えました. この構成はいわゆるLPSラマヌジャンなどと呼ばれています.
  • Morgenstern (1994)はLPSラマヌジャンを$p$がprime powerの場合に拡張しました.
  • 全ての$d\geq 3$に対して$d$正則ラマヌジャングラフは存在するのでしょうか?Friedmanの定理によるとランダム正則グラフは$\lambda_2 \leq 2\sqrt{d-1}+o(1)$を満たすことが知られていますが, 厳密にはラマヌジャングラフであるということを意味しません. このように, $\lambda_2\leq 2\sqrt{d-1}+o(1)$を満たすグラフをnear-Ramanujan graphといいます.
  • Marcus, Spielman, Srivastava (2015)は上の問いを解決し, 任意の$d\geq 3$に対して$d$正則二部ラマヌジャン(multi)グラフの無限列の存在性を証明しました. 彼らの証明はinterlacing polynomial methodと呼ばれる手法に基づいており, LPSラマヌジャンなどの代数的なアプローチとは根本的に異なっています.
  • すぐ後にCohen(2016)はMarcus, Spielman, Srivastavaの証明を構成的に修正し, $n$頂点ラマヌジャングラフを$\mathrm{poly}(n)$時間で構成するアルゴリズムを与えました.

ランダムネス抽出器


平たく言うとランダムネス抽出器(または単に抽出器)とは, ランダムっぽい文字列を受け取ってランダムな文字列を出力する乱択アルゴリズムです. 入力で与えられる文字列の「ランダムっぽさ」はmin-entropy(以下で定義している)によって測り, 出力文字列のランダムネスは一様ランダムな文字列との統計距離(total variation distance)によって測ります. 一般にdata processing inequalityより, どのような決定的なアルゴリズムを考えても分布のエントロピーを増大させることはできないため, ランダム抽出器は乱択アルゴリズムとしています.

定義1 (min-entropy).
確率変数$X$のmin-entropy $H_\infty(X)$を以下で定める:
\begin{align*}
H_\infty (X) = \min_{x\in\mathsf{supp}(X)}\log_2\frac{1}{\Pr[X=x]}.
\end{align*}

通常のShannon entropyは情報量の期待値によって定義されますが, min-entropyでは情報量の最小値を考えます. すなわちmin-entropyの方がworst-caseの情報量を考えていることになります. 二つの確率変数$X,Y$の統計距離を$d_\mathrm{TV}(X,Y)$で表します.

定義2 (ランダムネス抽出器)
以下を満たす関数$\mathrm{Ext}\colon \{0,1\}^m\times\{0,1\}^d\to\{0,1\}^n$を$(k,\epsilon)$-抽出器と呼ぶ: 任意の$H_{\infty}(X)\geq k$を満たす$\{0,1\}^m$上の分布$X$と$\{0,1\}^d$上の一様分布$U_d$に対し, $d_{\mathrm{TV}}\left( \mathrm{Ext}(X,U_d) , U_n \right) \leq \epsilon$.

すなわち, 抽出器とは, $m$ビットのランダムっぽい文字列$X$と$d$ビットの一様ランダムな文字列$U_d$を受け取り, $n$ビットのランダムな文字列を返す関数のことです. 一般に$m,d$は小さい方がよく, $n$は大きい方が良いです. 入力$X$をしばし弱ランダムソースと呼びます.

ランダムな関数を考えると高確率でランダムネス抽出器になっていることが簡単に示せます. すなわち, 各$\mathrm{Ext}(x,r)$の値を$\{0,1\}^n$上の一様ランダムにとってきたとき, $\mathrm{Ext}(\cdot,\cdot)$が抽出器になっている確率は適切なパラメータの下で$1-o(1)$になることが示せます.

ランダムネス抽出器は以下のように二部グラフによって表現することによって組合せ論的な解釈を与えることができ, そこに組合せ論のテクニックが介入する余地があります.


左側の各頂点は弱ランダムソース$X$の入力に対応しており, 右側の各頂点は$\{0,1\}^n$の元に対応します. 頂点$X$からは$2^d$本の辺が出ており, 各辺には$\{0,1\}^d$の元でラベル付けされています. 頂点$X$からラベル$u\in\{0,1\}^d$の辺を辿った先にある右側の頂点が$\mathrm{Ext}(X,u)$になるようにグラフを構成します.

このように二部グラフを構成すると, 抽出器とは以下の性質を持つ二部グラフ$G=(L,R,E)$であると解釈できます:

左側の頂点集合$L$上のmin-entropy$\ge k$であるような任意の分布に従って頂点$X$を選び, そこから$1$ステップだけランダムウォークを行って得られる右側の頂点を$Y\in R$とする. このとき, $Y$は$R$上一様分布に(統計距離の意味で)近い.

特に, エクスパンダーグラフを考えるとある条件下では抽出器になることが知られています. 抽出器についてのサーベイは, 古い論文ですがNisan(1996)に詳しいです.

エクスパンダーグラフなどの組合わせ論的な道具を使った構成のほかにも, 平均時計算量の道具を使って抽出器を構成するという手法も知られています. Trevisan (2001)は非常に賢いアイデアによって, 多くの擬似ランダム生成器の構成が実は抽出器の構成とみなせるということが示しました. 擬似ランダム生成器(pseudorandom generator; PRG)とは短いランダム文字列を受け取って長いランダム文字列を出力するアルゴリズムです. ただし一般に任意のアルゴリズムはエントロピーを増大しないので, PRGの出力は擬似ランダムであるということが求められます. 詳細は以前の記事をご覧ください. 

例えばNisan-Wigderson generator $G^f_{\mathrm{NW}}\colon \{0,1\}^d\to\{0,1\}^n$は, 計算が非常に困難なBoolean関数$f\colon\{0,1\}^\ell\to\{0,1\}$を使って$d$ビットのランダム文字列$U$(いわゆる乱数シード)を$n$ビットのランダム文字列に変換しています. Trevisan (2001)の抽出器では, 弱ランダムシード$x\in\{0,1\}^m$をまず誤り訂正符号で$2^\ell$ビットの文字列に復号化し, この文字列を真理値表として持つ関数をNisan-Wigderson generatorの構成に用いることによって, 抽出器を構成しています.


解析の大雑把な概要:
もしもTrevisan's extractorの出力値が一様ランダム文字列$U_n$から統計的に離れているならば, Nisan-Wigderson generatorのreconstructionの議論により関数$\mathrm{ECC}(x)\colon\{0,1\}^\ell\to\{0,1\}$からハミング距離$1/2-\epsilon$以下の文字列は短い記述を持つ. さらに$\mathrm{ECC}(x)$に対するリスト復号のアルゴリズムを用いれば, 最終的に弱ランダムシード$x$は短い記述を持つ. これはmin-entropyの仮定に反する.


Rigid Matrix


グラフの剛性とは違う文脈で行列のrigidityと呼ばれる概念があります. 直感的には, $M$がrigidであるというのは, $M$の成分をたくさん書き換えなければ低ランクにできない, ということを意味します. 有限体上の行列$M \in \mathbb{F}_q^{n\times n}$のランクを$\mathrm{rank}(M)$と書き, 二つの行列のハミング距離(異なる成分の個数)を$d_{\mathrm{ham}}(\cdot,\cdot)$で定義します. 

定義3 (matrix rigidity)
行列$M\in\mathbb{F}_q^{n\times n}$と自然数$r\leq n$に対し, $R_M(r)$を
\begin{align*}
R_M(r) := \min\{|S|\colon \mathrm{rank}(A+S)\leq r\}
\end{align*}
で定める. ここで, $|S|$は行列$S\in\mathbb{F}_q^{n\times n}$の非ゼロ成分の個数である.

$(n-r)\times (n-r)$首小行列を考えれば任意の行列$M$に対し$R_M(r)\leq (n-r)^2$が簡単に分かります.


各成分を$\mathbb{F}_q$から一様ランダムに選んで得られるランダム行列$M$に対し高確率で$R_M(r)\leq (n-r)^2/\log n$であることが示せます. 実際, ランク$r$以下の行列の個数とハミング距離$\leq s$のボールのサイズを考える数え上げによる議論で示せます.

Rigid matrixの概念はValiant(1977)によって, 線形変換を計算する算術回路のサイズ下界を得るという文脈で導入されました. 大雑把にいうと, Valiant(1977)はrigidな行列に基づく線形変換は超線形サイズの算術回路を要することを証明しており, ランダム行列は高確率でrigidであることを踏まえると, ランダムな線形変換の算術回路複雑性は超線形であることを意味します. この辺りのサーベイについてはLokam(2009)をご覧ください.

線形変換の回路下界自体も重要なトピックで, 例えば高速フーリエ変換は実用的にも重要な線形変換の一つなのでその計算の下界がわかればアルゴリズムの最適性も議論できることになります.

行列のrigidityに関しては次の重要な予想が重要な未解決問題として知られています.
予想 (Valiant, 1977)
ある体$\mathbb{F}_q$, 定数$\delta,\epsilon>0$およびサイズが発散していく陽に構成できる行列の列$(M_n)_{n=1,2,\dots}$が存在して, 十分大きな任意$n\in\mathbb{N}$に対して$R_{M_n}(\epsilon n) \geq n^{1+\delta}$を満たすようにできるか?

現在は$R_M(r)=\Omega\left(\frac{n^2}{r}\log\frac{n}{r}\right)$という下界が知られています(Friedman(1993), Shokrollahi, Spielman, Stemann (1997)).

近年はrigid matrixを計算量の道具を使って(NPオラクルを使って)構成するという手法が開発されました. Alman and Chen (2019)はNPオラクルを用いてrigid matrixを決定的に構成する手法を与えました. この解析は後にrectanglar PCPというアイデアを用いてsimplifyされました (Bhangale, Harsha, Paradise, Tal (2020)). 以下ではrectanglar PCPについてものすごくざっくり説明します.

非決定性機械に対する時間階層定理より, $\mathsf{NTIME}(2^n)\setminus \mathsf{NTIME}(2^n/n)$に属する判定問題$L$が存在します. さらに$\mathsf{NTIME}(2^n)$に対してPCP定理から PCP $\pi$とPCP検証者$V^{\pi}(\cdot)$が得られます. rencangular PCPとはその名の通り, 行列として表現できるPCP $\pi$のことです. ただしPCP検証者はランダムネスを使って行$i$と列$j$を選び, $\pi[i][j]$を見ます. これを定数回繰り返し, 見た証明ビットの内容においじて受理/拒否を決定します. Bhangaleら(2020)はNTIMEで解ける問題に対してある種の性質を満たすrectangular PCPが存在するということを示しています.

PCP定理から, 入力$x$上で元の問題$L$を得くためにはPCP検証者$V^{\pi}(x)$の受理確率を十分な精度で近似できれば良いです. もしrectanglular PCP $\pi$がrigidでないならば, ある低いランク行列$L$にハミング距離の意味で非常に近いはずです. そこで, nondeterministicに$L$の分解$L=R^\top R$をguessします. 実はこの情報を使ってPCP検証者の受理確率を決定的に十分な精度で近似することができます(!!). 実際には受理確率をある行列内に含まれる$1$の個数で表現し, $\pi$の低ランク分解を用いるとその行列もまた低ランク分解できることを示し, 最後に低ランク行列内に含まれる1の個数は高速に数え上げられるという結果(Chan and Williams, 2016)を使い, 最終的に$L$を$\mathsf{NTIME}(2^n/n)$で解けることを主張します. ところがこれは時間階層定理に矛盾するので, rectangular PCP $\pi$はrigidであることが結論づけられます.


その他の話題 (クラスPPAD)


確率論的手法以外にも非構成的な存在性の証明手法はあります. 例えばゲーム理論ではナッシュ均衡の存在性はブラウアーの不動点定理でその存在性が保証されるものの実際にそれを構成しているわけではありません. このような問題を扱うため, 計算量理論ではPPADと呼ばれる計算量クラスが考えられています. ナッシュ均衡の計算やブラウアーの不動点定理における不動点の計算はPPAD完全である, というある種の困難性の結果が知られています (Daskalakis, Goldberg, Papadimitriou, 2009).


まとめ

確率論的手法は興味深い離散構造の存在性を証明できる非常に強力なツールである一方, その離散構造をどのように得るかについては明示的な情報を与えてくれません. それではそれをどのように構成するかに関しては組合せ論や計算量理論で広く研究されており, 驚くほど広い(理論的な)応用を持っています.


2023年12月7日木曜日

discrepancy: ハムサンドイッチ定理の離散化 (確率論的手法)

本記事ではdiscrepancyと呼ばれる組合せ論(特に確率論的手法の文脈)でよく知られる概念について紹介します. この概念はハムサンドイッチ定理と呼ばれる定理を離散化したような概念とみなすことができます. discrepancyはその定義自体はとても簡単である一方で奥深い結果が多く知られており, 理論計算機科学においてはビンパッキング問題に対する近似アルゴリズムの設計にも応用されています. 後の章になっていくほどテクニカルになっていきます.

1. ハムサンドイッチ定理

ハムサンドイッチ定理とは, 直感的に説明すると「3次元空間内に配置された三つの物体は、ある平面でうまくスラッシュすることによって全ての物体の体積を半分にできる」ということ主張する定理です. 私は詳しくないのですが, wikipediaによると, より一般に$d$次元空間にある$d$個の「物体」(有限測度を仮定するが必ずしも連結である必要はない)はある$d-1$次元超平面によってそれぞれの測度を半分ずつにできる、という主張をハムサンドイッチの定理と呼ぶらしいです.

名前の由来はハムとそれを挟む2枚のパンからなる三つの物体は, 一回のナイフカットによって平等に二分割できるということから来るようです. 特に二次元($d=2$)の場合はパンケーキの定理とも呼ばれるようで, 限りなく薄い2枚のパンケーキを等分割するようにカットできるということを意味します (下図)


要するにハムサンドイッチ定理とは二つの物体を組み合わせたものはうまくナイフを入れることで等分できる, ということを主張しています. この定理を数学的に厳密に述べるのは難しいのですが, ここではそれを離散化した設定を考えます.

2. discrepancy

ハイパーグラフ$H=(V,E)$を考える (各$e\in E$は$e\subseteq V$を満たす). 関数$\chi\colon V\to\{-1,1\}$と集合$S\subseteq V$に対して$\chi(S)=\sum_{i\in V}\chi(i)$とし, $\chi$のdiscrepancy
\begin{align*}
\mathrm{disc}_{\chi}(H) = \max_{e\in E}|\chi(e)|
\end{align*}
で定義します. 直感的には$\chi$は頂点集合$V$を二つに分けるナイフカットを意味しており, そのdiscrepancyは$\chi$がどれだけ二等分に近いかを表す指標とみなすことができます. この設定下ではdiscrepancyが最小となる$\chi$が最も公平な分割と思うことができます. すなわち, 以下で定義される最小discrepancyを考えてみましょう:
\[
\mathrm{disc}(H):=\min_{\chi\colon V\to\{-1,1\}}\mathrm{disc}_{\chi}(H).
\]

以後, 関数$\chi\colon V\to\{-1,1\}$を彩色と呼びます.

例えば$G=(V,E)$が通常の意味でのグラフだとすると, $\mathrm{disc}(G)=0$であることと$G$が二部グラフが同値になります.

図: グラフ$G=(V,E)$が二部グラフならば, それぞれの部集合を$\chi^{-1}(1),\chi^{-1}(-1)$とすれば, discrepancyを$0$にできる.

3. 行列を用いたdiscrepancyの表現

ハイパーグラフ$H=(V,E)$の接続行列$A_H\in\{0,1\}^{E\times V}$を,
\[
A_H(e,v) = \begin{cases}
1 & \text{ if }v\in e,\\
0 & \text{otherwise}
\end{cases}
\]
で定義します. 関数$\chi\colon V\to\{-1,1\}$をベクトル$\chi\in\{-1,1\}^V$と同一視すると, 行列$A\chi \in \mathbb{Z}^{E}$は, その第$e$成分が$\sum_{v\in V}\chi(v)$になるので,
\[
\mathrm{disc}(H) = \min_{\chi\in\{-1,1\}^V}\left\| A_H\chi \right\|_{\infty}
\]
と表せます. ここで$\|\cdot\|_{\infty}$は$\ell^{\infty}$-ノルムで, 各成分の最大絶対値を表します. いくつかの論文ではこの形でdiscrepancyを議論していくこともあります. 

より一般に$A\in\{0,1\}^{m\times n}$に対して$\mathrm{disc}(A)$を
\[
\mathrm{disc}(A) = \min_{\chi\in\{-1,1\}^V}\left\| A\chi \right\|_{\infty}
\]
と定義することができ, さらにこの定義は一般の実行列$A\in\mathbb{R}^{m\times n}$に対して考えるもできます. これを行列$A$のdiscrepancyと呼びます.

蛇足になりますが, 関連する概念としてlinear discrepancyと呼ばれるものが知られています. この値は$m\times n$実行列$A$に対して定義でき,
\[
\mathrm{lindisc}(H) = \max_{w\in[-1,1]^n}\min_{x\in \{-1,1\}^n} \left\| A(x-w) \right\|_{\infty}
\]
で定義されます. この概念は元々は連続変数$w\in[-1,1]^n$を持つ線形計画問題を整数変数$x\in\{1,1\}^n$に丸めた際のギャップを考えるという文脈で定義されています.

4. discrepancyの計算量

考えるハイパーグラフ$H=(V,E)$の頂点数を$n$, ハイパー辺の個数を$m$で表します.

[Charikar, Newman, Nikolov, SODA11]によって, $m=O(n)$を満たすとき, 以下の二つの入力を区別することがNP困難であることが示されています:

  • $\mathrm{disc}(H)=0$
  • $\mathrm{disc}(H)=\Omega(\sqrt{n})$
例えば$m=n$を満たす任意のハイパーグラフ$H$に対して$\mathrm{disc}(H)\leq 6\sqrt{n}$であることが知られている (後述するがこの結果はSpencer's six standard deviations theoremと呼ばれる重要な結果) ので, 上記の困難性は定数倍を除いてタイトです.

5. ランダム彩色による上界


彩色$\chi\colon V \to \{-1,1\}$を一様ランダムにとってきたときのdiscrepancyを考えてみましょう. すなわち, 各$v\in V$に対して$\chi(v)$を$\pm 1$から一様ランダムに選びます. このとき, Hoeffding boundとunion boundを組み合わせることによって簡単に以下を示すことができます.

命題1 (ランダム彩色のdiscrepancy)
ハイパーグラフ$H=(V,E)$に対し, $n=|V|,m=|E|$とする. 一様ランダムに選ばれた彩色$\chi\colon V \to \{-1,1\}$を考えると, 以下が成り立つ:
\begin{align*}
\Pr\left[\mathrm{disc}_\chi(H) \leq \sqrt{2n\log(3m)} \right] \geq \frac{1}{3}.
\end{align*}
特に, $\mathrm{disc}(H)\leq \sqrt{2n\log(3m)}$である.

命題1の証明のために以下のHoeffding boundを用います:

補題1 (Hoeffding bound)
$X_1,\dots,X_\ell$を$\pm 1$に値をとる独立一様ランダムな確率変数とし, $X=\sum_{i\in[\ell]} X_i$とする. このとき, 任意の$t\geq 0$に対して
\begin{align*}
\Pr\left[ |X| \geq t \right] \leq 2\exp\left(-\frac{t^2}{2\ell}\right).
\end{align*}

[命題1の証明].
固定した辺$e\in E$に対して, 補題1より
\begin{align*}
\Pr\left[\chi(e) > \sqrt{2n\log(3m)} \right] \leq \Pr\left[\chi(e) > \sqrt{2|e|\log(3m)}\right] \leq \frac{2}{3m}.
\end{align*}
従って, $e\in E$に関するunion boundにより
\begin{align*}
\Pr\left[\mathrm{disc}_{\chi}(H) > \sqrt{2n\log(3m)}\right] \leq \Pr\left[\exists e\in E,\,\chi(e)>\sqrt{2n\log(3m)}\right] \leq \frac{2}{3}.
\end{align*}
すなわち, ランダムに選ばれた$\chi$のdiscrepancyは確率$1/3$で$\mathrm{disc}_\chi(H)\leq \sqrt{2n\log(3m)}$を満たす. (証明終)

証明から分かるように, $\log(3m)$の定数$3$は任意の定数$c>1$に対し$\log(cm)$に置き換えることが可能です.

6. Spencer's six standard deviation theorem


$m=O(n)$のとき, 5章では確率論的手法を使って$\mathrm{disc}(H)=O(\sqrt{n\log n})$が得られますが, 実はさらに改善して$\mathrm{disc}(H)=O(\sqrt{n})$を示すことができます[Spencer, 1985].

定理1 [Spencer's six standard deviation theorem]
$|V|=|E|$を満たす任意のハイパーグラフ$H=(V,E)$は$\mathrm{disc}(H)\leq 6\sqrt{|V|}$を満たす.

この結果は, その係数からSpencer's six standard deviation theoremと呼ばれます. 実はこの証明は$\chi$の存在性を鳩の巣原理から導出しており構成的ではないのですが, 後に構成論的な証明が与えられ[Bansal, 2010], 現在ではより簡単な証明も知られています[Lovett, Meka, 2015]. ここではhidden constantについてはoptimizeせず, 単に存在性($\mathrm{disc}(H)=O(\sqrt{n})$)を証明します.

証明では部分彩色 (partial coloring) という概念が鍵になります. 部分彩色とは関数$\chi\colon V\to\{-1,0,1\}$です. 部分彩色に対しても$\chi(e) = \sum_{v\in e} \chi(v)$とし, $\chi$のdiscrepancyを
\[
\mathrm{disc}_{\chi}(H) = \max_{e\in E}\left| \chi(e) \right|
\]
で定義することができます.

明らかに, 全ての頂点に$0$を割り当てる部分彩色を考えるとdiscrepancyが$0$となり最小値をとります. 従って, 部分彩色$\chi$であって
  • 多くの頂点(少なくとも$0.01|V|$個以上の頂点) に$\pm 1$の値を割り当てる, かつ
  • $\mathrm{disc}_{\chi}(H)$が小さい
ような部分彩色が望ましい部分彩色であるといえます. 以下の補題はそのような部分彩色の存在性を保証します.

補題2 (部分彩色補題)
ある定数$C_0$が存在して, $m\leq \frac{n}{10}$を満たす任意のハイパーグラフ$H=(V,E)$に対し, 以下の二つを同時に満たすある部分彩色$\chi\colon V\to \{-1,0,1\}$が存在する:
  • $\chi(v)\in \{-1,1\}$を満たす頂点$v$が少なくとも$\frac{n}{10}$個ある.
  • $\mathrm{disc}_\chi(H)\leq C_0\sqrt{n}$
補題2の証明が最もテクニカルなパートになるので次の章で紹介するとして, ここでは補題2$\Rightarrow$定理1を示します.

まずは証明のアウトラインを述べます. 元々は$m=n$という仮定でしたが, ダミー頂点を追加すれば相対的に$|E|\leq \frac{|V|}{10}$になるようにできるので, 与えられたハイパーグラフは$m=\frac{n}{10}$を満たすと仮定して良いです (ダミー頂点追加後の彩色に対するdiscrepancyは$O(\sqrt{O(n)})=O(\sqrt{n})$になるのでdiscrepancyのバウンドも大丈夫). これに対して補題2を適用して得られる部分彩色に対し, $0$が割り当てられた頂点部分集合からなる誘導部分ハイパーグラフに対して再帰に彩色を得て先ほどの部分彩色とマージするという方針になります. 一回の反復で塗られていない頂点の個数は$0.9$倍になるので, 全体のdiscrepancyは高々$\sum_{t=0}^\infty C_0 \sqrt{0.9^t n}=O(\sqrt{n})$になるという議論です.

[補題2$\Rightarrow$定理1]
以下の手順に従ってハイパーグラフの列$(H_t)_{t=0,1,\dots}$と各$H_t$上の部分彩色$\chi_t$を定義します:
  1. $H_0 = (V_0,E_0) = H$とする.
  2. For $t=1,2,\dots,$ do:
    1. 部分彩色$\chi_t$を, $H_{t-1}$に対する補題2で存在性が保証される部分彩色とする.
    2. $V_t=\{v\in V_{t-1}\colon \chi_t(v)= 0\}$, $E_t = \{e\cap V_t\colon e\in E_{t-1}$とし, $H_t=(V_t,E_t)$で定める.
    3. $E_t=\emptyset$になったら終了する.
補題2の条件より, $|V_t| \leq 0.9|V_{t-1}|$ なので, 十分大きな$T=O(\log n)$に対して$E_T=\emptyset$となるため, 上の手順は有限ステップで終了します. このとき, $\chi_1,\dots,\chi_T$に対して彩色$\chi$を, $\chi(v) = \chi_i(v)$で定めます. ここで$i\in[T]$は$\chi_i(v)\neq 0$を満たす唯一の$i$とします. 

上で定義した$\chi$のdiscrepancyを評価します. 各辺$e\in E$に対して
\begin{align*}
|\chi(e)| \leq \left|\sum_{v\in e}\chi(v)\right| \leq \sum_{t=1}^T \left| \sum_{e\in E_{t-1}\setminus E_t } \chi(e) \right| \leq \sum_{t=1}^T C_0\sqrt{0.9^t n} = O(\sqrt{n})
\end{align*}
を得ます.

7. 部分彩色補題の証明(スケッチ)


6章で紹介した補題2(部分彩色補題)を証明します. この証明はその鳩の巣原理からその存在性が保証されるため構成的ではありません. 部分彩色補題 (ひいては定理1) を満たす彩色$\chi$の構成については長年未解決だったのですが, Bansal (2010) によるブレイクスルーにより解決され, 現在ではLovett and Meka (2015) による(ランダムネスを用いる)簡単な構成法も知られています. 厳密な証明をしようとすると瑣末な部分のケアで煩雑になってしまい大変なので, できる限り本質を捉えつつ厳密性を捨てて, 分かった気になれる証明のスケッチを紹介します.


定義1 (エントロピー)
離散集合上に値をとる確率変数$X$に対し, そのエントロピー$\mathrm{H}(X)$を
\begin{align*}
\mathrm{H}(X) = \mathbb{E}_{x\sim X}\left[\log\frac{1}{\Pr[X=x]}\right] = \sum_{x\in \mathsf{supp}(X)} \Pr[X=x]\log\frac{1}{\Pr[X=x]}
\end{align*}
で定義します. ここで対数の底はlogとし, $\mathsf{supp}(X)$は$X$の台(support)と呼ばれる集合で, $\mathsf{supp}(X)=\{x\colon \Pr[X=x]>0\}$で定義されます.

なお, 連続値をとり密度関数が存在するような確率変数に対しても$\Pr[X=x]$を密度関数$f(x)$に置き換えて微分エントロピーという値が定義されます. すなわち, 密度関数$f$を持つ実数値をとる確率変数$X$の微分エントロピー$\mathrm{H}(X)$は
\begin{align*}
\mathrm{H}(X)=\int_\mathcal{\mathsf{supp}(X)} f(x) \log\frac{1}{f(x)}\mathrm{d}x
\end{align*}
で定義されます. エントロピーに関しては上記の定義と以下の性質のみを使います.

補題3 (エントロピーの劣加法性).
ランダムなベクトル$X=(X_1,\dots,X_n)$に対し, そのエントロピー$\mathrm{H}(X)$は
\[\mathrm{H}(X) \leq \sum_{i\in[n]}\mathrm{H}(X_i)\]を満たす.

さて, 部分彩色補題の証明に戻ります. ランダムな彩色$\chi\colon V \to \{-1,1\}$を考え, パラメータ$w>0$と頂点部分集合$S$に対し, 確率変数
\[
Z_S = \left\lfloor \frac{\chi(S)}{w\sqrt{|S|}}\right\rfloor
\]
のエントロピー
$\mathrm{H}(Z_S)$を考えます. 実際にはもう少し複雑な式を使って評価するのですが, ここでは以下の主張を認めて証明を進めていきます.

主張1.
パラメータ$w$を適切にとり, 部分集合$S$の要素数が十分大きいとき, $\mathrm{H}(Z_S)\leq 0.9$とできる.

なお, この主張は本当に成り立つかは分かりません(えっ...). 実際の証明ではもう少し複雑な式を使ってエントロピーを評価します. ここではその証明のアイデアを簡潔に説明するためにあえて「成り立つか分からない主張」を仮定します. ただ, この主張には一応の理由づけはできるので, 以下ではその妥当性を説明します (実際の研究の場面ではこのようなことは私はよくやります).

[主張1の妥当性の説明]

  • 定義よりエントロピーはスケーリングで不変なので, $\mathrm{H}(Z_S)=\mathrm{H}(w\cdot Z_S) \approx \mathrm{H}(\chi(S)/\sqrt{|S|})$ (本当は切り下げの有無でのエントロピーの誤差の評価が必要).
  • $\chi(S)$は平均$0$, 分散$1$の独立な確率変数$(\chi(v))_{v\in S}$の和なので, $|S|$が十分大きければ中心極限定理より$\chi(S)/\sqrt{|S|}$は漸近的に標準正規分布$\mathcal{N}(0,1)$で近似できる.
  • 従って, $\mathrm{H}(\chi(S)/\sqrt{|S|}) \approx \mathrm{H}(\mathcal{N}(0,1)) = (1+\log(2\pi))/2 \approx 1.419$. なお, 正規分布の微分エントロピーについての事実を使っている(例えばこの記事参照).  本当はBerry--Esseenの不等式などを使ってエントロピーの誤差評価が必要.
  • これらをまとめると, $\mathrm{H}(Z_S)\approx 1.419$なので, パラメータ$w$を適切にとり, 集合サイズ$|S|$が十分大きいならば, 近似精度を$0.001$未満にできて$\mathrm{H}(Z_S)\leq 1.42$にできる.
ハイパーグラフ$H$に対し, ランダムベクトル$Z=Z(\chi)=(Z_e)_{e\in E}$を考えます. ここで, 全ての辺$e$の要素数は十分大きいと仮定します (そうでない場合はサイズが小さいのでdiscrepancyに寄与しないため無視できる). するとエントロピーの劣加法性(補題3)と主張1より
\begin{align*}
\mathrm{H}(Z) \leq \sum_{e\in E}\mathrm{H}(Z_e) \leq 1.42m \leq 0.2n
\end{align*}
を得ます. エントロピーの定義より, averaging argumentにより, あるベクトル$z^*\in\mathbb{Z}^E$が存在して
\begin{align*}
\log\frac{1}{\Pr[Z=z^*]} \leq 0.2n
\end{align*}
となります. これを整理すると$\Pr[Z=z^*] \geq \mathrm{e}^{0.2n} > 2^{0.2n}$を得ます. ここでの確率は一様ランダムな彩色を考えていたので, 少なくとも$2^{0.8n}$個の$\chi\in \{-1,1\}^V$が存在して$Z(\chi)=z^*$を満たすことになります. そのような$\chi$の集合を$B\subseteq\{-1,1\}^V$とします. ここで, $|B|\geq 2^{0.8n}$より, ある二つのベクトル$\chi_1,\chi_2\in B$が存在して, $\|\chi_1-\chi_2\|_1 \geq 0.1n$となります (後述). そのような$\chi_1,\chi_2$に対して$\chi = \frac{1}{2}(\chi_1 - \chi_2)$と定義します. するとこの$\chi$は部分彩色補題の要件を満たしています:
  • $\chi_1,\chi_2$の選び方より, $\chi(v)=0\iff \chi_1(v)=\chi_2(v)$となる$v\in V$は高々$0.9n$個あります.
  • $\chi_1,\chi_2\in B$より, $Z(\chi_1)=Z(\chi_2)$です. すなわち, 任意の$e\in E$に対して
    \[
    \left\lfloor\frac{\chi_1(e)}{w\sqrt{|e|}} \right\rfloor = \left\lfloor \frac{\chi_2(e)}{w\sqrt{|e|}} \right\rfloor
    \]
    が成り立つので, $|\chi(e)| = |\chi_1(e) - \chi_2(e)| \leq w\sqrt{|e|} \leq w\sqrt{n}$です. これは$\mathrm{disc}_\chi(H)\leq w\sqrt{n}$を意味します.
以上より, 部分彩色補題(補題3)の証明が完了し, 同時に定理1の証明も完了しました. (証明終)


以上の証明では次の事実を用いています:

主張2.
集合$B\subseteq \{-1,1\}^n$が$|B|\geq 2^{0.8n}$を満たすならば, ある二つのベクトル$x,y\in B$が存在して$\|x - y \|_1\geq 0.1n$となる.

証明(概要). 一般に, 任意のベクトル$x\in \{-1,1\}^n$に対し$x$からハミング距離$\alpha n$以内にある点の個数は高々$\sum_{i=0}^{\alpha n} \binom{n}{i} \leq 2^{\mathrm{H}(\alpha)n}$を満たします (ここで$\mathrm{H}(\alpha):=\alpha\log_2\frac{1}{\alpha} + (1-\alpha)\log_2\frac{1}{1-\alpha}$はbinary entropy function). $\alpha=0.1$を代入すると, この個数は$2^{\mathrm{H}(0.1)n}< 2^{0.469n}<|B|$なので, 主張を満たす2点をとることができます. (証明終)

Further Reading

  • 驚くべきことにスタンフォード大学では過去にdiscrepancyについての講義(おそらく集中講義?)があり, いくつかの講義ノートが公開されています.
  • The Probabilistic Method (Alon and Spencer)の12章ではランダムな$\chi$の解析とsix-deviation theoremとBeck-Fiala theoremとHadamard行列に基づく下界の紹介がされています.
  • ビンパッキング問題の近似アルゴリズムに対する応用については "A Logarithmic Additive Integrality Gap for Bin Packing" (Hoberg and Rothvoss, SODA2017) 参照. なお, 箇条書き一つ目のリンクにあるLecture 10のノートには少し弱い近似精度を持つビンパッキングの近似アルゴリズムについての解説があります.

2023年12月1日金曜日

hardcore補題を使ったXOR補題の証明

 平均時計算量においてはXOR補題と呼ばれる定理がよく知られています. この分野では脱乱択化や暗号プリミティブの構成への応用を念頭に, 非常に難しい関数をどのように構成するかが研究されています.

関数$f\colon\{0,1\}^n\to\{0,1\}$に対する回路$C$の成功確率$p_{C,f}$を
\begin{align*}
p_{C,f}:= \Pr_{x\sim\{0,1\}^n}[C(x)=f(x)]
\end{align*}
と定めます. ここで, 有限集合$S$に対して$x\sim S$で$x$は$S$上一様分布に選ばれたことを意味します. 任意のサイズ$s$の回路$C\colon\{0,1\}^n\to\{0,1\}$に対してその成功確率が高々$1-\delta$であるとき, 関数$f$はサイズ$s$に対して$\delta$-困難であるといいます. 定数回路(常に$0$を出力, または常に$1$を出力する回路)を使えば成功確率$\geq1/2$を達成するので, 基本的に$\delta\leq1/2$の範囲で考えます. 特に, 小さい$\epsilon>0$に対して$(1/2-\epsilon)$-困難な関数は正解できる入力の個数が下界に近いので非常に困難な関数であるとみなすことができます. XOR補題とは, XORをとることによって関数の困難性を増幅できることを主張する定理です.

定理1 (XOR補題)
関数$f$, パラメータ$k\in\mathbb{N}$に対して関数$f^{\oplus k}\colon \{0,1\}^{nk}\to\{0,1\}$を
\begin{align*}
f^{\oplus k}(x_1,\dots,x_k)=f(x_1)\oplus \dots \oplus f(x_k)
\end{align*}
で定める. $f$がサイズ$
O\left(\frac{\log(1/\delta)}{(\epsilon/k)^2}(s+kn)\right)$に対して$\delta$-困難かつ$k\geq \frac{C\log(1/\epsilon)}{\delta^2}$ならば, $f^{\oplus k}$はサイズ$s$に対して$(1/2-\epsilon)$-困難である. ここで$C$は十分大きな定数である.

一般に, 「関数$f$がサイズ$s$に対して$\delta$-困難ならば関数$g$はサイズ$s'$に対して$(1/2-\epsilon)$-困難である」という形の定理を困難性の増幅(hardness amplification)といい, XOR補題はその最も基本的な定理の一つです. 原則として$s'\approx s$であることが望まれます.

本記事ではこの定理を証明します. そのためにhardcore lemmaを使います. 回路$C$の問題$f$に対する入力集合$H\subseteq\{0,1\}^n$上での成功確率を$p_{C,f,H}:=\Pr_{x\sim H}[C(x)=f(x)]$と定義します. ここでは[Impagliazzo (1995)]のパラメータを改善した[Barak, Hardt, Kale (2009)]による以下のhardcore lemmaを用いることにします:

補題1. (hardcore lemma)
サイズ$s$に対して$\delta$-困難な関数を任意にとってきて$f$とすると, ある$|H|\geq\delta 2^n$を満たす集合$H\subseteq \{0,1\}^n$であって, 任意のサイズ$O\left(\frac{\epsilon^2}{\log(1/\delta)}s\right)$の回路$C$に対して$p_{C,f,H}\leq 1/2-\epsilon$を満たすものが存在する.

補題1によって存在性が保証されている集合$H$を$f$のハードコア集合と呼びます. hardcore lemmaの対偶をとると以下の主張を得ます:

補題1'. (hardcore lemma)
任意の$|H|\geq \delta 2^n$を満たす集合$H\subseteq \{0,1\}^n$に対してあるサイズ$s$の回路$C_H$が存在して$\Pr_{x\sim H}[C_H(x) = f(x)]\geq 1/2+\epsilon$を満たすならば, あるサイズ$O\left(\frac{\log(1/\delta)}{\epsilon^2} \cdot s\right)$の回路$C'$が存在して, $\Pr_{x\sim\{0,1\}^n}[C'(x)=f(x)]\geq 1-\delta$.

関数$f\colon \{0,1\}^n\to\{0,1\}$が$\delta$-困難であるならば, 一様ランダムな$x\sim \{0,1\}^n$に対して確率変数$f(s)$は1ビットのベルヌーイ試行$\mathrm{Ber}(\delta)$と区別がつかないということを意味します. ここでベルヌーイ試行$\mathrm{Ber}(\theta)$とは確率$\theta$で$1$, 確率$1-\theta$で$0$を出力する確率変数です. 従って, ハードコア補題は, 直感的には,

$f$が$\delta$-困難ならば, サイズ$|H|\geq \delta$を満たすある入力集合$H\subseteq \{0,1\}^n$が存在して, 一様ランダムな$x\sim H$に対して$f(x)$は1ビットの一様分布$\mathrm{Ber}(1/2)$と(計算論的に)区別がつかない

ということを主張しています. では, 定理1を証明しましょう. まずはアウトラインを述べます. 独立に$x_1,\dots,x_k\sim\{0,1\}^n$をランダムにとって$f^{\oplus k}(x_1,\dots,x_k)$を考えてみましょう. まず, $x_1,\dots,x_k$のうち少なくとも一つが$H$に入っている確率は下から$1-(1-\delta)^k\approx 1-\mathrm{e}^{-\delta k}\approx 1-\epsilon$で抑えられます. 非常に高確率で発生するこの事象で条件つけ, 例えば$x_i\in H$であるとします. このとき, $x_i$の分布は$H$上で一様ランダムです. したがって$f(x_i)$は$\mathrm{Ber}(1/2)$と区別がつきません. ここで確率変数$f(x_1),\dots,f(x_k)$は$x_1,\dots,x_k$が独立なのでこれらもまた独立であり, $f(x_i)$が$\mathrm{Ber}(1/2)$と区別できないので, XORをとった$f^{\oplus k}(x_1,\dots,x_k)$もまた$\mathrm{Ber}(1/2)$と区別できないです (一様ランダムなビットと他のビットのXORをとったらそれもまた一様ランダムなビットになる). すなわち, $f^{\oplus k}(x_1,\dots,x_k)$が$\mathrm{Ber}(1/2)$と区別できず, これは$f^{\oplus k}(x_1,\dots,x_k)$が$(1/2-\epsilon)$-困難であることを意味します (事象の発生確率が$1-\epsilon$なので$\epsilon$程度のロスが発生している).

以上の流れを対偶を使って証明します. 以下, 二つの確率変数$X,Y$に対し, $X\not\approx_c Y$で$X$と$Y$をcomputationalに識別できる (i.e., ある小さい回路$C$が存在して$|\Pr[C(X)=1]-\Pr[C(Y)=1]|$がnon-negligibleに大きい) ことを表すとします. また, $X\approx_s Y$によって, $X$と$Y$はstatisticalの意味で近い (つまりtotal variation distanceが小さい)ことを表すとします. 最後に, $U_k$によって一様ランダムな$k$ビットの文字列を表すとします. 例えば$(U_{nk},f^{\oplus k}(U_{nk}))$と書いた場合は, $x\sim U_{nk}$を一様ランダムにサンプリングして$x=(x_1,\dots,x_k)$に$k$分割して$(x,f^{\oplus k}(x_1,\dots,x_k))$の分布のことを表すものとします (なので分布のランダムネスは$x$の選び方のみです).
  1. $f^{\oplus k}(x_1,\dots,x_k)$を成功確率$(1/2+\epsilon)$で計算するサイズ$s$の回路が存在するので, $(U_{nk},f^{\oplus k}(U_{nk}))\not\approx_c (U_{nk},U_1)$.
  2. ランダム関数$f_H(x)$を, $x\in H$ならば$f_H(x)=U_1$, $x\not\in H$ならば$f_H(x)=f(x)$と定義する. 情報論的なバウンドによって, $(U_{nk},f_H^{\oplus k}(U_{nk}))\approx_s (U_{nk},U_1)$.
  3. 1と2の議論によって, $(U_{nk},f_H^{\oplus k}(U_{nk}))\approx_s U_{nk+1}\not \approx_c (U_{nk},f^{\oplus k}(U_{nk}))$が得られる. 特に, $(U_{nk},f_H^{\oplus k}(U_{nk}))\not\approx_c (U_{nk},f^{\oplus k}(U_{nk}))$.
  4. $(U_{nk},f^k(U_{nk})) \not\approx_c (U_{nk},f^k_H(U_{nk}))$を得る (k-wise XORを識別できるので). ここで, $f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$と定義していて, $(U_{nk},f^k(U_{nk}))$とは$(x_1,\dots,x_k)\sim U_{nk}$に対して$(x_1,\dots,x_k,f(x_1),\dots,f(x_k))$によって与えられるものです.
  5. ハイブリッド議論(hybrid argument)によって$(x,f(x))\not\approx_c (x,f_H(x))$となる (ただし分布のランダムネスは$x\sim U_n$).
  6. $H$が密(i.e., $|H|\geq \delta 2^n$)であることを使うと, $H$上一様ランダムな$x\sim H$に対して$(x,f(x))\not\approx_c (x,f_H(x))=(x,U_1)$が示せる.
  7. Yao's next-bit predictorより, $x\sim H$に対して$f(x)$を成功確率$1/2+\epsilon$で計算できる.
  8. ハードコア補題より$\{0,1\}^n$上で$f$を成功確率$1-\delta$で計算できる. これは元の$f$の条件に矛盾する.

それでは, 定理1の証明をします. 以下の議論では上記のステップ1〜8を補足しつつフォーマルに確認していくだけなので, 上記のアイデアで満足な人は読まなくても構いません.

関数$f$をサイズ$s$に対して$\delta$-困難な関数とし, $H\subseteq\{0,1\}^n$をハードコア集合とします. 回路$D$のサイズを$\mathrm{size}(D)$と表すことにします.

ステップ1. $f^{\oplus k}(U_{nk})$を成功確率$1/2+\epsilon$で計算する回路を$C$とします. 与えられた$(x,b)\in \{0,1\}^{nk+1}$に対して$C(x)\oplus b \oplus 1$を出力する回路を$C_1$とすると,
\begin{align*}
&\Pr_{x\sim U_{nk}}[C_1(x,f^{\oplus k}(x))=1] = \Pr_x[C(x)=f^{\oplus k}(x)] \geq \frac{1}{2}+\epsilon \\
&\Pr_{x\sim U_{nk},b\sim U_1}[C_1(x,b)=1] = \frac{1}{2}
\end{align*}
より, 二つの分布$(U_{nk},f^{\oplus k}(U_{nk}))$と$(U_{nk},U_1)$を$\epsilon$のアドバンテージで識別できます. $C_1$のサイズは, $\mathrm{size}(C_1) = \mathrm{size}(C)+O(1)$を満たします.

ステップ2. 関数$f_H\colon\{0,1\}^n\to\{0,1\}$を
\begin{align*}f_H(x) = \begin{cases}U_1 & \text{ if }x\in H,\\f(x) & \text{otherwise}\end{cases}\end{align*}
とします. ここで$U_1$は各$x\in H$ごとにランダムに生成されるランダムビットです. 厳密には$\mathcal{F}_H$を, 任意の$x\not\in H$に対して$g(x)=f(x)$を満たす関数$g$の集合, すなわち
\begin{align*}
\mathcal{F}_H = \{g\colon \forall x\not\in H, g(x)=f(x)\}
\end{align*}
と定義したときに$f_H$は$\mathcal{F}_H$から一様ランダムに選ばれたランダム関数として定義されます. 独立に$k$個の入力$x_1,\dots,x_k\sim U_n$と$k$個のランダム関数$f_H$をサンプリングして, $f_H(x_i)$のXORをとったときの値$f_H^{\oplus k}(x_1,\dots,x_k)$の分布を考えましょう (ランダムネスは$x_i$と$f_H$の選び方についてとる). どれか一つの$i$でも$f_H(x_i)=U_1$であったならば, そのXORの値もまた$U_1$となります. 従って, 統計距離は$\prod_{i=1}^k \Pr[x_i\not\in H] \leq (1-\delta)^k$となり (ここで$|H|\geq\delta\cdot 2^n$を使っている), 適当な$k=O(\log(1/\epsilon)/\delta)$に対して統計距離は高々$0.1\epsilon$となります.

ステップ3. 統計距離の性質から, ステップ1で構成された回路$C_1$は二つの分布$(U_{nk},f^{\oplus k}(U_{nk}))$と$(U_{nk},U_1)$をアドバンテージ$0.9\epsilon$で識別します.

ステップ4. 二つの分布$(U_{nk}, f^k(U_{nk}))$と$(U_{nk},f_H^k(U_{nk}))$を識別する回路$C_2$を以下のように構成します: 入力$(x_1,\dots,x_k,b_1,\dots,b_k)$に対し, $C_1(x_1,\dots,x_k,b_1\oplus\dots\oplus b_k)$を出力する. この回路$C_2$は, $C_1$の識別性により確かに二つの分布$(U_{nk}, f^k(U_{nk}))$と$(U_{nk},f_H^k(U_{nk}))$をアドバンテージ$0.9\epsilon$で識別します. 回路$C_2$のサイズは高々$\mathrm{size}(C_1)+O(k)$です.

ステップ5. ステップ4で構成された回路$C_2$は二つの分布
\begin{align*}
&D_0 := (x_1,\dots,x_k,f(x_1),\dots,f(x_k)),\\
&D_k := (x_1,\dots,x_k,f_H(x_1),\dots,f_H(x_k))
\end{align*}
をアドバンテージ$0.9\epsilon$で識別します. これら二つの分布を滑らかに補間するような分布列$D_1,\dots,D_{k-1}$を
\begin{align*}
D_i := (x_1,\dots,x_k,f(x_1),\dots,f(x_{i-1}),f_H(x_i),\dots,f_H(x_k))
\end{align*}
とします(これをハイブリッド分布とよぶ). $i=0,k$の場合でもそれぞれ$D_0,D_k$になっていることが分かります. $p_i = \Pr[C_2(D_i)=1]$とすると, $p_0 - p_k = \sum_{i\in[k]}(p_{i-1} - p_{i}) \geq 0.9\epsilon$なので, ある$i\in[k]$が存在して$p_{i-1} - p_i \geq 0.9\epsilon/k$を満たします. 
さらに, ある$z_1,\dots,z_{i-1},z_{i+1},\dots,z_k \in \{0,1\}^{n}$および$c_1,\dots,c_{i-1},c_{i+1},\dots,c_k\in \{0,1\}$が存在して,
\begin{align*}
\Pr_{x\sim U_n}[C_2(\mathbf{v}(i,x,f(x))=1] - \Pr_{x\sim U_n}[C_2(\mathbf{v}(i,x,f_H(x))]\geq \frac{0.9\epsilon}{k}
\end{align*}
が成り立ちます. ここで, $\mathbf{v}(i,x,b)$は
\begin{align*}
\mathbf{v}(i,x,b) = (z_1,\dots,z_{i-1},x,z_{i+1},\dots,z_k,c_1,\dots,c_{i-1},b,c_{i+1},\dots,c_k)
\end{align*}
で定義される文字列である (インデックス$i$と各$z_j$と$c_j$は入力$x$に依存しない値なので, これらの情報を回路にあらかじめ組み込むことによって, 与えられた$x,b$に対し$\mathbf{v}(i,x,b)$はサイズ$O(kn)$の回路で計算できる). 従って, 関数$(x,b)\mapsto C'(\mathbf{v}(i,x,b))$はサイズ$s+O(nk)$程度で計算でき, さらに上記の式より二つの分布$(x,f(x))$と$(x,f_H(x))$をアドバンテージ$0.9\epsilon/k$で識別する. この回路を$C_3$とします.

ステップ6. 全ての$x\not\in H$に対して定義より$f(x) = f_H(x)$となるので, $(U_n,f(U_n))$と$(U_n,f_H(U_n))$が区別できるということは, ステップ5の回路$C_3$を使って$x\sim H$に対して$(x,f(x))$と$(x,f_H(x))$が区別できるということになります. 実際,
\begin{align*}
\frac{0.9\epsilon}{k} &\leq \Pr[C_3(U_n,f(U_n))=1] - \Pr[C_3(U_n,f_H(U_n))=1] \\ &= 2^{-n}\sum_{x\in\{0,1\}^n} (C_3(x,f(x)) - \mathbb{E}_{f_H}[C_3(x,f_H(x))]) \\ &= 2^{-n}\sum_{x\in H}(C_3(x,f(x)) - \mathbb{E}[C_3(x,U_1)]) & & \text{since $f_H(x)=U_1$ for $x\in H$} \\ &\leq \frac{1}{|H|}\sum_{x\in H}(C_3(x,f(x)) - \mathbb{E}[C_3(x,U_1)]) & & \text{since $f_H(x)=U_1$ for $x\in H$} \\ &= \Pr_{x\sim H}[C_3(x,f(x))=1] - \Pr_{x\sim H,U_1}[C_3(x,U_1)=1]
\end{align*}
なので$C_3$は, $x\sim H$に対して$(x,f(x))$と$(x,U_1)$を識別します.

ステップ7. 以前の記事で紹介した計算量的な識別不可能性の概念を思い起こします. この概念は関数の困難性と等価であることがYao's next-bit predictorからわかります.

定義1.
$\{0,1\}^n$上の二つの確率変数$X,Y$は, あるサイズ$s$の回路$C$が存在して
\begin{align*}
\Pr[C(X)=1]-\Pr[C(Y)=1]\geq \epsilon
\end{align*}
を満たすとき, サイズ$s$で$\epsilon$-識別可能であるといい, $C$を識別回路という. 逆に, そのような回路$C$が存在しない場合はサイズ$s$で$\epsilon$-識別不可能であるという.

補題2 (Yao's next-bit predictor; 以前の記事の定理の対偶の言い換え).
関数$f\colon \{0,1\}^n\to\{0,1\}$に対し, 二つの分布$(U_n,f(U_n))$と$(U_n,U_1)$がサイズ$s$で$\epsilon$-識別可能であるならば, サイズ$s+O(1)$のある回路$C$が存在して
\begin{align*}
\Pr_{x\sim U_n}[C(x) = f(x)] \geq \frac{1}{2} + \epsilon.
\end{align*}

上記の補題において, $U_n$を$H$上の一様分布に置き換えることによって以下の補題を得ます.

補題3.
関数$f\colon \{0,1\}^n\to\{0,1\}$と任意の集合$H\subseteq\{0,1\}^n$を考える. $x\sim H$に対して二つの分布$(x,f(x))$と$(x,U_1)$がサイズ$s$で$\epsilon$-識別可能であるならば, サイズ$s+O(1)$のある回路$C$が存在して
\begin{align*}
\Pr_{x\sim H}[C(x) = f(x)] \geq \frac{1}{2} + \epsilon.
\end{align*}

補題3の証明は省略しますが, $\ell = \lceil \log_2 |H|\rceil$に対して, $H$上の一様分布を$U_\ell$とみなすことができることから分かると思います.

ステップ6までの議論より補題3の仮定を満たす回路が存在するので, あるサイズ$\mathrm{size}(C_3)+O(1) = s+O(nk)$の回路$C_4$が存在して
\begin{align*}
\Pr_{x\sim H}[C_4(x) = f(x)] \geq \frac{1}{2} + \frac{0.9\epsilon}{k}
\end{align*}
が成り立ちます.

ステップ8. ハードコア補題(補題1)の対偶を適用する. 任意の$|H|\geq \delta 2^n$を満たす$H$に対してある回路$C_4$が存在して$p_{C_4,f,H}\geq \frac{1}{2} + \frac{0.9\epsilon}{k}$となるので, 補題1'より, $f$を成功確率$1-\delta$で計算する回路$C_5$であって, サイズ
\[
\mathrm{size}(C_5) = O\left(\frac{\log(1/\delta)}{(\epsilon/k)^2}(s+kn)\right)
\]
となるものが存在する. これは定理1の$f$の困難性の仮定に矛盾します.

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...