Slepian–Wolfの定理(Slepian–Wolf theorem)とは、互いに独立で同じ分布に従う組 $(S_i,T_i)$ の 2 つの列を別々の符号化器で固定長に圧縮し、1 つの復号器でまとめて復元するとき、誤りの確率を $0$ に近づけられる速さの組の閉包が $R_1\ge H(S\mid T)$、$R_2\ge H(T\mid S)$、$R_1+R_2\ge H(S,T)$ で与えられるという定理である。和の速さは 2 つの列をまとめて圧縮するときと同じ $H(S,T)$ まで下げられる。達成は情報源の列を無作為に箱へ振り分ける方法(線形写像のシンドロームでもよい)で、逆は Fano の不等式で示される。
Slepian–Wolfの定理(Slepian–Wolf theorem)は、互いに相関のある 2 つの情報源を、2 か所で 別々に 圧縮し、1 か所でまとめて復元するときに、誤りの確率を $0$ に近づけられる圧縮の速さの組をすべて決める定理である。答えは
$$
R_1\ge H(S\mid T),\qquad R_2\ge H(T\mid S),\qquad R_1+R_2\ge H(S,T)
$$
で、とくに速さの和は、2 つの列を 1 か所でまとめて圧縮するときと同じ $H(S,T)$ まで下げられる。符号化器は相手の列を見ないのに、相関を利用した分だけ短くできる。D. Slepian と J. K. Wolf が 1973 年に示した(SW73)。
この記事では、情報源と符号を定義して主定理を述べ、情報源の列を無作為に箱へ振り分ける方法(乱択ビン分け)で達成を、情報理論 の Fano の不等式で逆を、それぞれ完全に証明する。振り分けを線形写像にしてもよいこと、2 値の相関のある情報源の例、仮定を外すと何が成り立たなくなるかも述べる。以下 $\log$ は 2 を底とし、エントロピーの単位は bit とする。
$\mathcal S,\mathcal T$ を有限集合とし、$(S_1,T_1),(S_2,T_2),\dots$ は互いに独立で、どれも $\mathcal S\times\mathcal T$ 上の同じ分布 $P_{ST}$ に従うとする(各 $i$ の内部では $S_i$ と $T_i$ は相関してよい)。$S^n:=(S_1,\dots,S_n)$、$T^n:=(T_1,\dots,T_n)$ と書く。エントロピー $H(S\mid T)$、$H(S,T)$ などは、1 組 $(S,T)\sim P_{ST}$ について エントロピー の定義「同時・条件付きエントロピーと相互情報量」のとおりに(底 2 で)定める。
非負の整数 $k_1,k_2$ について、長さ $n$ の 分散符号 とは、2 つの符号化器 $f_1\colon\mathcal S^n\to\{0,1\}^{k_1}$、$f_2\colon\mathcal T^n\to\{0,1\}^{k_2}$ と復号器 $g\colon\{0,1\}^{k_1}\times\{0,1\}^{k_2}\to\mathcal S^n\times\mathcal T^n$ の組である。その誤りの確率を
$$
P_e:=P\bigl(g(f_1(S^n),f_2(T^n))\ne(S^n,T^n)\bigr)
$$
とする。実数の組 $(R_1,R_2)$ が 達成可能 であるとは、各 $n\ge1$ について長さ $n$ の分散符号で $k_1\le nR_1$、$k_2\le nR_2$ を満たすものがとれ、その誤りの確率が $n\to\infty$ で $0$ に近づくことをいう。
$f_1$ は $S^n$ だけを、$f_2$ は $T^n$ だけを見る。$\{0,1\}^0$ は 1 点とし、$k_j=0$ は何も送らないことを表す。
$$
\mathcal R_{\mathrm{SW}}:=\bigl\{(R_1,R_2)\in\mathbb R^2\bigm|R_1\ge H(S\mid T),\ R_2\ge H(T\mid S),\ R_1+R_2\ge H(S,T)\bigr\}
$$
を Slepian–Wolf の速度領域 という。
連鎖律 $H(S,T)=H(T)+H(S\mid T)=H(S)+H(T\mid S)$(エントロピー の定理「連鎖律と劣加法性」)から、和の直線 $R_1+R_2=H(S,T)$ は 2 つの角 $(H(S\mid T),H(T))$ と $(H(S),H(T\mid S))$ を結ぶ。$H(S\mid T)+H(T\mid S)\le H(S,T)$ なので $\mathcal R_{\mathrm{SW}}$ は空でない閉凸集合で、内部も空でない。
1 は下の節「達成:乱択ビン分け」で、2 は節「逆:Fano の不等式による証明」で証明する。最後の主張は 1 と 2 から従う。閉凸集合 $\mathcal R_{\mathrm{SW}}$ の内部は空でないので、$\mathcal R_{\mathrm{SW}}$ は内部の閉包に等しいからである(内部の点 $r_0$ と $r\in\mathcal R_{\mathrm{SW}}$ について、$r+\lambda(r_0-r)$ は $0<\lambda\le1$ で内部にある)。
主張は PW25 Theorem 11.16(p. 225)にあり、同書は外側では誤りの確率が $1$ に近づくこと(強い逆)まで述べている。Mac03 Exercise 15.17(pp. 236–237)も同じ領域を答えとして示している。
比べるために、2 つの列を 1 か所で見てまとめて固定長で圧縮する場合を考えると、誤りの確率を $0$ に近づけるには速さ $H(S,T)$ より大きければ足り、それ未満では足りない(PW25 Corollary 11.3、p. 214。下の prf-sw-converse の段 2 は符号化器が 1 つでも成り立つ)。各列をそれぞれ単独で圧縮するなら $R_1\ge H(S)$、$R_2\ge H(T)$ が要る。Slepian–Wolf の定理は、別々に符号化しても、復号器がまとめて復元するなら和の速さは単独の圧縮の和 $H(S)+H(T)$ でなく $H(S,T)$ でよいことをいう。差は相互情報量 $I(S;T)=H(S)+H(T)-H(S,T)$ である。
有限集合 $\mathcal X,\mathcal Y$ 上の任意の同時分布 $P_{XY}$ を考える。$P_{XY}(x,y)>0$ となる $(x,y)$ について
$$
\imath(x\mid y):=\log\frac1{P_{X|Y}(x\mid y)},\qquad\imath(y\mid x):=\log\frac1{P_{Y|X}(y\mid x)},\qquad\imath(x,y):=\log\frac1{P_{XY}(x,y)}
$$
とおく(情報密度)。$E[\imath(X\mid Y)]=H(X\mid Y)$、$E[\imath(X,Y)]=H(X,Y)$ である。
非負の整数 $k_1,k_2$ と実数 $\tau$ について、符号化器 $f_1\colon\mathcal X\to\{0,1\}^{k_1}$、$f_2\colon\mathcal Y\to\{0,1\}^{k_2}$ と復号器 $g$ で
$$
P\bigl(g(f_1(X),f_2(Y))\ne(X,Y)\bigr)\le P\bigl((X,Y)\notin A\bigr)+3\cdot2^{-\tau}
$$
を満たすものがある。ここで $A$ は、$P_{XY}(x,y)>0$ かつ
$$
\imath(x\mid y)< k_1-\tau,\qquad\imath(y\mid x)< k_2-\tau,\qquad\imath(x,y)< k_1+k_2-\tau
$$
を満たす $(x,y)$ の集合である。
1. 符号の作り方。 各 $x\in\mathcal X$ に $\{0,1\}^{k_1}$ の元 $c_x$ を、各 $y\in\mathcal Y$ に $\{0,1\}^{k_2}$ の元 $d_y$ を、すべて互いに独立に一様に選ぶ($(X,Y)$ とも独立)。$f_1(x):=c_x$、$f_2(y):=d_y$ とおき、$c_x$ を $x$ の入る 箱の番号 と考える。復号器 $g(w_1,w_2)$ は、$c_x=w_1$、$d_y=w_2$ かつ $(x,y)\in A$ となる $(x,y)$ がちょうど 1 つならそれを返し、そうでなければ固定した 1 点を返す。
2. 誤りの事象。 $(X,Y)=(x,y)$ を送って誤るなら、$(x,y)\notin A$ であるか、$(x',y')\ne(x,y)$、$(x',y')\in A$、$c_{x'}=c_x$、$d_{y'}=d_y$ となる $(x',y')$ がある。後者を、(a) $x'\ne x$、$y'=y$、(b) $x'=x$、$y'\ne y$、(c) $x'\ne x$、$y'\ne y$ の 3 つに分ける。
3. (a) の確率。 $(x,y)$ を固定する($P_{XY}(x,y)>0$ なので $P_Y(y)>0$)。$(x',y)\in A$ なら $P_{X|Y}(x'\mid y)>2^{-(k_1-\tau)}$ で、$\sum_{x'}P_{X|Y}(x'\mid y)=1$ だから、そのような $x'$ は $2^{k_1-\tau}$ 個未満である。$x'\ne x$ なら $c_{x'}$ と $c_x$ は独立で一様なので $P(c_{x'}=c_x)=2^{-k_1}$ である。和の上界から (a) の確率は $2^{k_1-\tau}\cdot2^{-k_1}=2^{-\tau}$ 以下である。
4. (b) と (c) の確率。 (b) は $x$ と $y$ の役を入れ替えて同じく $2^{-\tau}$ 以下である。(c) では、$(x',y')\in A$ なら $P_{XY}(x',y')>2^{-(k_1+k_2-\tau)}$ なので、そのような組は $2^{k_1+k_2-\tau}$ 個未満であり、$x'\ne x$、$y'\ne y$ なら $c$ と $d$ の独立性から $P(c_{x'}=c_x,\ d_{y'}=d_y)=2^{-k_1}\cdot2^{-k_2}$ である。よって (c) の確率は $2^{-\tau}$ 以下である。
5. 符号を 1 つ選ぶ。 箱の番号は $(X,Y)$ と独立なので、2〜4 を $(X,Y)$ の分布で平均すると、無作為な符号の誤りの確率の期待値は $P((X,Y)\notin A)+3\cdot2^{-\tau}$ 以下である。期待値以下の値をとる箱の番号の選び方が少なくとも 1 つあり、それを固定すればよい。$\square$
証明が使ったのは、(i) 異なる $x\ne x'$ の箱の番号が一致する確率が $2^{-k_1}$ であること($y$ も同様)、(ii) $c$ と $d$ が独立であること、の 2 つだけである。したがって $\mathcal X=\mathbb F_2^m$ のときは、一様に選んだ $k_1\times m$ 行列 $A_1$ を使って $c_x:=A_1x$ としてもよい。$x\ne x'$ なら $A_1(x-x')$ は $\{0,1\}^{k_1}$ 上一様で、$P(A_1x=A_1x')=2^{-k_1}$ となるからである(2元対称通信路 の定理「線形符号による達成」の証明の段 2 と同じ議論)。このとき $c_x$ は、検査行列 $A_1$ の線形符号の シンドローム である。
$(R_1,R_2)$ を $\mathcal R_{\mathrm{SW}}$ の内部の点とし、$\delta>0$ を
$$
R_1>H(S\mid T)+3\delta,\qquad R_2>H(T\mid S)+3\delta,\qquad R_1+R_2>H(S,T)+3\delta
$$
となるようにとる。$k_j:=\lfloor nR_j\rfloor$、$\tau:=n\delta$ とおき、lem-sw-oneshot を $(X,Y)=(S^n,T^n)$ に使う。$k_j\le nR_j$ である。
独立性から $P_{S^nT^n}(s^n,t^n)=\prod_iP_{ST}(s_i,t_i)$、$P_{S^n|T^n}(s^n\mid t^n)=\prod_iP_{S|T}(s_i\mid t_i)$ なので
$$
\imath(S^n\mid T^n)=\sum_{i=1}^n\imath(S_i\mid T_i)
$$
であり、右辺は互いに独立で同じ分布に従う有界な確率変数の和で、各項の期待値は $H(S\mid T)$ である。大数の法則 の大数の弱法則により、$P\bigl(\imath(S^n\mid T^n)\ge n(H(S\mid T)+\delta)\bigr)\to0$ である。$n(R_1-H(S\mid T)-3\delta)>1$ となる $n$ では $k_1-\tau>nR_1-1-n\delta>n(H(S\mid T)+\delta)$ なので、$P\bigl(\imath(S^n\mid T^n)\ge k_1-\tau\bigr)\to0$ である。$\imath(T^n\mid S^n)$ と $\imath(S^n,T^n)$ についても同じで、和の条件では $k_1+k_2-\tau>n(R_1+R_2)-2-n\delta$ を使う。よって $P((S^n,T^n)\notin A)\to0$、$3\cdot2^{-n\delta}\to0$ で、誤りの確率は $0$ に近づく。$\square$
角の点 $(H(S\mid T)+\varepsilon,\ H(T)+\varepsilon)$ の付近は、次のように読める。$T^n$ を単独で速さ $H(T)$ 強で圧縮して送り、$S^n$ は箱の番号だけを送る。復号器はまず $T^n$ を復元し、その箱に入る $s^n$ のうち $T^n$ のもとで条件付き確率の大きいものを探す。そのような $s^n$ は約 $2^{nH(S|T)}$ 個しかないので、箱が $2^{n(H(S\mid T)+\varepsilon)}$ 個ほどあれば正しいものがほぼ確実に 1 つに決まる。符号化器は $T^n$ を知らないが、箱への振り分けは $T^n$ に依らなくてよい。
$(R_1,R_2)$ を達成する分散符号の列をとり、長さ $n$ の符号の誤りの確率を $P_e^{(n)}$、$W_1:=f_1(S^n)$、$W_2:=f_2(T^n)$、$U:=(S^n,T^n)$ とする。$k_j\ge0$ なので $R_j\ge0$ である。
1. Fano の不等式。 $U$ のとりうる値は $M:=(\#\mathcal S\cdot\#\mathcal T)^n$ 個である($M=1$ なら $H(S,T)=0$ で $\mathcal R_{\mathrm{SW}}=\{R_1,R_2\ge0\}$ となり主張は自明なので、$M\ge2$ とする)。$\hat U:=g(W_1,W_2)$ は $U$ の推定値なので、情報理論 の定理「Fano の不等式」を底 2 で書くと $H(U\mid\hat U)\le1+P_e^{(n)}\log M$ である。$\hat U$ は $(W_1,W_2)$ の関数なので、同記事の補題「関数で条件を粗くするとエントロピーは減らない」により
$$
H(U\mid W_1,W_2)\le H(U\mid\hat U)\le n\varepsilon_n,\qquad\varepsilon_n:=\frac1n+P_e^{(n)}\log(\#\mathcal S\cdot\#\mathcal T)
$$
であり、$\varepsilon_n\to0$ である。
2. 和の速さ。 $(S_i,T_i)$ の独立性から $H(U)=nH(S,T)$ である(エントロピー の定理「連鎖律と劣加法性」)。$(W_1,W_2)$ は $U$ の関数なので $H(W_1,W_2\mid U)=0$ で、
$$
nH(S,T)=H(U)=I(U;W_1,W_2)+H(U\mid W_1,W_2)=H(W_1,W_2)+H(U\mid W_1,W_2)\le k_1+k_2+n\varepsilon_n
$$
である($(W_1,W_2)$ の値は $2^{k_1+k_2}$ 個以下)。$k_1+k_2\le n(R_1+R_2)$ で割って $n\to\infty$ とすると $R_1+R_2\ge H(S,T)$ を得る。
3. 一方の速さ。 独立性から $H(S^n\mid T^n)=H(S^n,T^n)-H(T^n)=nH(S\mid T)$ である。$W_1$ は $S^n$ の関数なので、$T^n$ を条件にした連鎖律により
$$
H(S^n\mid T^n)=H(S^n,W_1\mid T^n)=H(W_1\mid T^n)+H(S^n\mid W_1,T^n)
$$
である。第 1 項は $H(W_1)\le k_1$ 以下である。$(W_1,W_2)=(W_1,f_2(T^n))$ は $(W_1,T^n)$ の関数なので、第 2 項は $H(S^n\mid W_1,W_2)\le H(U\mid W_1,W_2)\le n\varepsilon_n$ 以下である。よって $nH(S\mid T)\le nR_1+n\varepsilon_n$ で、$R_1\ge H(S\mid T)$ を得る。$R_2\ge H(T\mid S)$ も同じである。$\square$
段 3 は、復号器が $T^n$ そのものを知っていても $S^n$ には速さ $H(S\mid T)$ が要ることを示している。段 2 の評価は、2 つの符号化器を 1 つにまとめても下がらない。
復号器が $T^n$ を知り、符号化器 $f\colon\mathcal S^n\to\{0,1\}^k$ は $S^n$ だけを見るとする(復号器は $g'\colon\{0,1\}^k\times\mathcal T^n\to\mathcal S^n$)。$R>H(S\mid T)$ なら、$k\le nR$ で誤りの確率が $0$ に近づく符号の列があり、$R< H(S\mid T)$ ならない。
$R>H(S\mid T)$ なら、$R_2>H(T)$ をとると $(R,R_2)$ は $\mathcal R_{\mathrm{SW}}$ の内部にある($R+R_2>H(S\mid T)+H(T)=H(S,T)$)。thm-sw-main の 1 の符号 $(f_1,f_2,g)$ について $g'(w,t^n):=g(w,f_2(t^n))$ の第 1 成分とおけば、誤りの確率はもとの符号のもの以下である。逆は prf-sw-converse の段 3 で $W_2$ を $T^n$ に替えれば同じである。$\square$
符号化器も $T^n$ を知っている場合の最適な速さも $H(S\mid T)$ なので、相手の列が復号器にしか届かなくても速さは損なわれない(PW25 Theorem 11.13 と Corollary 11.14、p. 223)。ただしこれは、誤りの確率が $0$ に近づけばよいという基準による。PW25 Remark 11.5(p. 224)は、正の確率をもつすべての組で誤りなく復元することを求めると相手の列が役に立たず、可変長の誤りのない圧縮でも平均の長さは $H(S)$ 以上になることを注意している(下の表の 1 行目を参照)。
歪みを許して圧縮する場合に、復号器だけが相手の列を知る問題は Wyner–Ziv の問題として知られ、相手の列そのものでなくその圧縮だけが届く問題は PW25 §11.7(Theorem 11.17、p. 227)で扱われている。
$0< p< \frac12$ とし、$S$ を $\{0,1\}$ 上の一様分布、$Z$ を $S$ と独立で $P(Z=1)=p$ とし、$T:=S+Z\bmod2$ とする。$h_2(p):=-p\log p-(1-p)\log(1-p)$ とおくと、$T$ も一様で、$S=s$ のもとで $T$ は確率 $p$ で $s$ と異なるので $H(T\mid S)=h_2(p)$、$H(S,T)=1+h_2(p)$、対称性から $H(S\mid T)=h_2(p)$ である。よって
$$
\mathcal R_{\mathrm{SW}}=\{R_1\ge h_2(p),\ R_2\ge h_2(p),\ R_1+R_2\ge1+h_2(p)\}
$$
である。$p=0.11$ では $h_2(0.11)\approx0.49992$ で、たとえば $(0.75,0.75)$ は内部の点である。単独で圧縮すればそれぞれ $1$ bit が要る。
角の点の付近では、$T^n$ をそのまま送り、$S^n$ はシンドローム $A_1S^n$ だけを送る。$A_1S^n+A_1T^n=A_1Z^n$ なので、復号器の仕事は「シンドロームから雑音の列 $Z^n$ を推定する」ことになり、これは 2元対称通信路 で検査行列 $A_1$ の線形符号を復号するのと同じ問題である。
$S$ を $\{0,1,2,3\}$ 上の一様分布とし、$T:=S\bmod2$ とする。$H(S)=2$、$H(T)=1$、$H(T\mid S)=0$、$H(S\mid T)=1$、$H(S,T)=2$ なので、$\mathcal R_{\mathrm{SW}}=\{R_1\ge1,\ R_2\ge0,\ R_1+R_2\ge2\}$ である。角の点 $(1,1)$ は誤りなしで達成できる。$S$ の側は $\lfloor S/2\rfloor$(1 bit)を、$T$ の側は $T$(1 bit)を送れば、$S=2\lfloor S/2\rfloor+T$ と $T$ が復元できる。もう一方の角 $(2,0)$ では $S$ を 2 bit で送り、$T$ は復号器が計算する。
$S$ と $T$ が独立なら $H(S\mid T)=H(S)$、$H(S,T)=H(S)+H(T)$ で、$\mathcal R_{\mathrm{SW}}=\{R_1\ge H(S),\ R_2\ge H(T)\}$ は単独の圧縮の組と同じになり、まとめて復号しても得はない。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 誤りの確率が $0$ に近づけばよい(誤りなしを求めない) | ex-sw-binary($p=0.11$)で、正の確率をもつすべての $(s^n,t^n)$ を誤りなく復元することを求める | thm-sw-main の 1 が成り立たない:$(0.6,\ 1)$ は内部の点だが、誤りなしでは $R_1\ge1$ が要る |
| $(S_i,T_i)$ が互いに独立で同じ分布 | $B$ を一様なビットとし、すべての $i$ で $S_i=T_i=B$ | thm-sw-main の 2 が成り立たない:1 回ずつの分布では $H(S,T)=1$ だが、どの $\varepsilon>0$ でも $(\varepsilon,0)$ が達成可能で、和の速さは $1$ より小さくできる |
| 復号器が 2 つの番号をまとめて使う | $S^n$ を $W_1$ だけから、$T^n$ を $W_2$ だけから復元する | thm-sw-main の 1 の範囲が狭まる:ex-sw-binary の内部の点 $(0.75,0.75)$ でも、$S^n$ を $W_1$ だけから復元するには $R_1\ge H(S)=1$ が要る |
1 行目:$p>0$ なのですべての $(s,t)$ が正の確率をもつ。$s^n\ne s'^n$ で $f_1(s^n)=f_1(s'^n)$ なら、同じ $t^n$ に対して $g$ は 2 つを区別できないので、$f_1$ は単射でなければならず、$2^{k_1}\ge2^n$、すなわち $k_1\ge n$ である。
2 行目:$n\ge1/\varepsilon$ では $k_1:=1\le n\varepsilon$、$k_2:=0$ とし、$f_1(s^n):=s_1$、$f_2$ は何も送らず、$g$ は受け取ったビット $b$ から $(S^n,T^n)=((b,\dots,b),(b,\dots,b))$ を返せば誤りはない($n< 1/\varepsilon$ の符号は何でもよい)。この情報源は列全体で 1 bit の情報しかもたず、1 回ずつのエントロピーで速さを測れない。
3 行目:$S^n$ の復元だけに prf-sw-converse の段 2 を当てはめる($U:=S^n$、$W_2$ を除く)と、$nH(S)\le k_1+1+P_e^{(n)}n\log\#\mathcal S$ となり、$R_1\ge H(S)$ を得る。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する