IBIS2010

多端子情報源符号化の現状と課題

葛岡成晃（和歌山大学）お話しすること• 基本的な問題意識・数理モデル• 重要な成果と未解決問題

１ Slepian & Wolf 符号化問題

Slepian & Wolf (1973)

問題の枠組み（情報源）• 集合 X 上の確率変数 X ，集合 Y 上の確率変数 Y の組(X, Y ) およびその同時分布 PXY を考える．
それぞれ独立に PXY に従う確率変数の組の列{(X(t), Y (t))}∞t=1 を定常無記憶情報源と呼ぶ．
• {X(t)}∞t=1 を情報源 X と呼ぶ．またその先頭 n 文字
X(1)X(2) . . . X(n) を X n と表す．
情報源 Y と Y n についても同様．

問題の枠組み（符号）• ブロックサイズ n の符号は，符号器 1 φ1,n : X n → M1,n
符号器 2 φ2,n : Y n → M2,n
復号器 ψn : M1,n × M2,n → X × Y
nnの組 (φ1,n , φ2,n , ψn ) によって定まる．
• 長さ n の文字列 xn ∈ X n に対して，φ1,n (xn ) ∈ M1,n をxn の符号語という．

問題の枠組み（目的）問題は，誤り確率en ≡ Pr {(X n , Y n ) ̸= ψn (φ1,n (X n ), φ2,n (Y n ))}を十分小さくできる範囲で，符号器 φ1,n , φ2,n それぞれの符号化率

1rk,n ≡ log |Mk,n |n(k = 1, 2)をどこまで小さくできるか明らかにすること．

達成可能領域の定義(R1 , R2 ) が達成可能 ⇔ ∃{(φ1,n , φ2,n , ψn )}∞n=1 s.t.
def

lim sup r1,n ≤ R1n→∞

lim sup r2,n ≤ R2n→∞lim en = 0n→∞

基本的な問題意識
達成可能な符号化率の範囲を明らかにするには，「ここまでならできる」という順定理（内界）と「これよりよくできない」という逆定理（外界）を示さないとイケナイ．

情報理論的問題意識• 漸近的（n → ∞）な性能をエントロピーなど計算可能な量を用いて記述することが目標．
• 内界と外界が一致したとき「問題は解けた」という．



SW 符号化の達成可能領域

R1 ≥ H(X|Y )

R2 ≥ H(Y |X)

R1 + R2 ≥ H(X, Y )同時復号の効果

情報源 X と Y をそれぞれ個別に符号化・復号化した場合には達成できない領域も達成可能！

SW 達成可能領域の頂点の意味
符号器・復号器共通の補助情報が利用可能な場合の最適レートを達成可能！

２ SW 符号化の拡張

一般的な情報源ネットワーク• Xj 上の確率変数 Xj の組 XJ ≡ (X1 , X2 , . . . , XJ ) を考える．XJ の同時分布 PXJ に従う独立な確率変数の組の列{XJ (t)}∞t=1 によって情報源を定める．
∞• {XJ (t)}∞から{X(t)}
jt=1
t=1 (j = 1, . . . , J) も定まる．
• インデックス集合 S ⊆ J ≡ {1, 2, . . . , J} に対して，XS で確率変数の組 (Xj )j∈S を表す．

符号器：各符号器 φk (k = 1, 2, . . . , K) がつながっている
情報源のインデックス集合を Jk ⊆ {1, 2, . . . , J} とする．

φk,n :∏

Xkn → Mk,nj∈Jk

注意：2 つ以上の復号器とつながっている場合，どの復号器にも同じ符号語を送る．

復号器：各復号器 ψl (l = 1, 2, . . . , L) がつながっている
符号器および 復号するべき情報源のインデックス集合をそれぞれ Kl ⊆ {1, 2, . . . , K}，Dl ⊆ {1, 2, . . . , J} で表す．

ψl,n :∏k∈Kl

Mk,n →∏j∈DlXjn

(R1 , . . . , RK ) が達成可能⇔∃{(φ1,n , . . . , φK,n , ψ1,n , . . . , ψL,n )}∞n=1 s.t.
1lim sup log |Mk,n | ≤ Rk (k = 1, . . . , K)n→∞ n}{nn≠X̂lim Pr XD
Dl = 0 (l = 1, . . . , L)ldefn→∞nただし X̂Dは ψl,n の出力．
l

解けている問題

以下の条件を満たす場合を考える：

1. 情報源 Xk と符号器 φk (k = 1, . . . , K) は一対一に対応
2. l ̸= ˆl ⇒ Kl ̸= Kl̂
3. Kl ⊂ Kl̂ ⇒ Dl ⊂ Dl̂
4. k ∈ Dl ⇒ k ∈ Kl
5. k ∈ Kl ⇒ k ∈ Dl
← 4, 5 から Kl = Dl

解けている問題

定理 [Csiszár & Körner (1980)](R1 , . . . , RK ) が達成可能⇕

すべての l = 1, 2, . . . , L と S ⊆ Dl に対して∑k∈SRk ≥ H(XS |XKl \S )

補足説明

• 実際には，定理は冗長な制約式を除いた形で示されている．

• Csiszár & Körner の論文では，一般的なネットワークから，達成可能領域を変えることなく条件 1 から 3 を満足するようにネットワークを変換する手法も示されている．
• Csiszár & Körner は符号化の誤り指数まで導出している．

4 番目，5 番目の条件について• 4 番目の条件 k ∈ Dl ⇒ k ∈ Kl が満たされていないと，一見どうしようもない（例：Z が X, Y と独立）．
• しかし，Z = f (X, Y ) の場合は，計算機科学分野の分散計算とも関係がある重要な問題．一般的に未解決．
• 難しさは，X, Y は復号器側で復元しなくてよい点にある（X, Y も復元するならその後で Z = f (X, Y ) を計算すればよい）．

ヘルパーありの符号化問題/ Dl となる l が存在する φk をヘルパーと• k ∈ Kl かつ k ∈呼ぶ．
• つまり，5 番目の条件 k ∈ Kl ⇒ k ∈ Dl は「ヘルパーが存在しない」という制約になっている．
• ヘルパーがある場合の符号化問題では，一般的に，達成可能領域を記述するためには補助確率変数を導入する必要がある．
• 補助確率変数の導入に対応して，符号も子持ち符号(piggyback code) と呼ばれる符号化手法が導入された．

Wyner (1975), Ahlswede & Körner (1975)

R1 ≥ H(X|U )R2 ≥ I(Y ; U )ただし U ↔ Y ↔ X
かつ |U| ≤ |Y| + 2．

Wyner (1975)

R1 ≥ H(X|U )R2 ≥ H(Y |U )R3 ≥ I(Z; U )ただし U ↔ Z ↔ XY かつ |U| ≤ |Z| + 2．

Sgarro (1977)

R1 ≥ max{H(X|U ), H(Y |V )}R2 ≥ I(Y ; U )R3 ≥ I(Z; V )ただし U ↔ Y ↔ X ，V ↔ Z ↔ X ，|U| ≤ |Y| + 2，|V| ≤ |Z| + 2．

Körner & Marton (1977)

R1 ≥ H(X)R2 ≥ H(Y |X) + I(X; U ) − r
R3 ≥ H(Z|U ) + r
ただし 0 ≤ r ≤ I(X; U )，U ↔ Y ↔ XZ ，|U| ≤ |Y| + 2．

一般的なヘルパーありの符号化問題• Han & Kobayashi (1980) は子持ち符号の理論の拡張（Markov Lemma の一般化）により，かなり一般的な問題に対して内界（順定理）を示している．
• Han & Kobayashi の順定理で示された内界は，上述のWyner-Ahlswede-Körner, Wyner, Sgarro, Körner-Martonの各問題の場合にはタイトであることも示されている．
• しかしながら，ヘルパーを含む符号化問題も一般的には未解決．

３ 歪みを許容する多端子情報源符号化

2 対 1 有歪み符号化問題（歪み測度・符号）

歪み測度（X̂ , Ŷ を復元アルファベットと呼ぶ）：

d1 : X × X̂ → [0, ∞)d2 : Y × Ŷ → [0, ∞)
符号器・復号器：

φ1,n : X n → M1,nφ2,n : Y n → M2,n
ψn : M1,n × M2,n → X̂ n × Ŷ n

2 対 1 有歪み符号化問題（歪みの評価）

情報源からの出力 (X n , Y n ) と復号結果(X̂ n , Ŷ n ) ≡ ψn (φ1,n (X n ), φ2,n (Y n )) との歪みを考える：
n∑1∆1,n ≡
d1 (X(t), X̂(t))
n t=1∆2,n ≡n∑1n t=1d2 (Y (t), Ŷ (t))

2 対 1 有歪み符号化問題（達成可能領域）(R1 , R2 ) が (D1 , D2 )-許容⇔∃{(φ1,n , φ2,n , ψn )}∞n=1 s.t.
1
lim sup log |Mk,n | ≤ Rk (k = 1, 2)n→∞ n
lim sup ∆k,n ≤ Dk (k = 1, 2)
defn→∞

一般的には未解決！

Wyner & Ziv (1976)

復号器が Y を観測できる（R2 ≥ H(Y )）とき：E[d(X, X̂)] ≤ D となるように復元できる符号化率の下限はRW Z (D) = min I(X; U |Y )U,f

ただし min は U ↔ X ↔ Y , |U| ≤ |Y| + 1 およびE [d(X, f (Y, U ))] ≤ D を満たす補助確率変数 U と関数
f : Y × U → X̂ とについてとられる．

片方の許容歪みが 0 の場合

情報源 Y に対する許容歪みを D2 = 0 とした場合の達成可能領域は，Kaspi & Berger (1982) や Berger & Yeung (1989)
によって与えられた．

ガウス形情報源・平均二乗誤差歪みの場合

Berger (1977) と Tung (1978) が領域の内界を与えた．
Oohama (1997) が曲線部分は最適であることを証明．
最近 Wagner ら (2008) が直線部分も最適であることを証明．
情報源が 3 つ以上の場合への拡張はまだ．

応用側からの関心• 動画の符号化では，符号器と復号器が前のフレームを共通の補助情報として利用できる（上左図の問題）• 最近，符号器の計算量を削減するために，前のフレームを復号器のみで利用する手法が注目されている（上右図）⇒ WZ 問題！
• ただし，SW 符号化とは違い，歪み有りの場合は符号器が補助情報を利用する／しないで最適符号化率に差が出る．

• 動画配信などの応用上で重要な問題として MultipleDescription (MD) がある（上左図）．一般的には未解決．
• Successive Refinement も MD 問題の特別な場合として考えられる（上右図）．
Successive Refinable である（すなわち 1 段目・2 段目ともに最適なレート・歪みのトレードオフを達成できる）ための必要十分条件などが明らかにされている．

最後に• 基本的な問題の枠組みを説明し，重要な成果と未解決問題を駆け足で紹介した．
• 一見すると「解けそうな問題は解けていて，未解決問題には手が出せない」という閉塞状態にある．
• それでも地道な研究が続いており，境界を記述する制約式をよりタイトにするための証明手法も発展中．

• 語り残したことの方が多いが，最新の面白いトピックはこの後の３人の講演をお楽しみに！