本記事では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$が二部グラフが同値になります.
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})$
5. ランダム彩色による上界
\begin{align*}
\Pr\left[\mathrm{disc}_\chi(H) \leq \sqrt{2n\log(3m)} \right] \geq \frac{1}{3}.
\end{align*}
\Pr\left[ |X| \geq t \right] \leq 2\exp\left(-\frac{t^2}{2\ell}\right).
\end{align*}
\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*}
6. Spencer's six standard deviation theorem
\[
\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)$が小さい
- $\chi(v)\in \{-1,1\}$を満たす頂点$v$が少なくとも$\frac{n}{10}$個ある.
- $\mathrm{disc}_\chi(H)\leq C_0\sqrt{n}$
- $H_0 = (V_0,E_0) = H$とする.
- For $t=1,2,\dots,$ do:
- 部分彩色$\chi_t$を, $H_{t-1}$に対する補題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)$で定める.
- $E_t=\emptyset$になったら終了する.
\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. 部分彩色補題の証明(スケッチ)
\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\}$で定義されます.
\mathrm{H}(X)=\int_\mathcal{\mathsf{supp}(X)} f(x) \log\frac{1}{f(x)}\mathrm{d}x
\end{align*}
で定義されます. エントロピーに関しては上記の定義と以下の性質のみを使います.
\[\mathrm{H}(X) \leq \sum_{i\in[n]}\mathrm{H}(X_i)\]を満たす.
\[
Z_S = \left\lfloor \frac{\chi(S)}{w\sqrt{|S|}}\right\rfloor
\]
のエントロピー$\mathrm{H}(Z_S)$を考えます. 実際にはもう少し複雑な式を使って評価するのですが, ここでは以下の主張を認めて証明を進めていきます.
なお, この主張は本当に成り立つかは分かりません(えっ...). 実際の証明ではもう少し複雑な式を使ってエントロピーを評価します. ここではその証明のアイデアを簡潔に説明するためにあえて「成り立つか分からない主張」を仮定します. ただ, この主張には一応の理由づけはできるので, 以下ではその妥当性を説明します (実際の研究の場面ではこのようなことは私はよくやります).
[主張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$にできる.
\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}$を意味します.
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のノートには少し弱い近似精度を持つビンパッキングの近似アルゴリズムについての解説があります.
0 件のコメント:
コメントを投稿