IBIS2010

補助情報を用いた情報源符号化
松嶋敏泰
早稲田大学

統計的学習理論と情報理論（関係するものですぐ思いつくのは）

情報源符号化（冗長度を削減）
ユニバーサル情報源符号

予測，統計的複雑度，モデル選択，．．．

通信路符号化（冗長度を付加）
復号法（誤り訂正符号，CDMA，MIMO）

グラフィカルモデル，
事後確率計算，BP，和積アルゴリズム，平均場近似，．．．

学習理論，統計理論，情報理論（無理して特徴付けると）
評価基準
粗い
学習理論

データ数少ない

多い
統計理論

情報理論

細かい

情報理論の特徴• 評価基準が明確（復号誤り率，レート）• 評価基準の限界をまず示す• その限界を達成する符号化，復号化を求める• 実用的アルゴリズムを求める（計算量，メモリー量）

0. Slepian –Wolf Problem
SourceCodingDecoding

Destination

1.Surece coding with side information
SourceCodingDistortion less:
Mean code length:

DecodingDestination

2. Source coding
SourceCoding

Decoding

Destination

Distortion less:
Mean code length:
Ideal code length:

If the distribution of a source is known, we
can construct the optimal source code.
eg) Arithmetic codesユニバーサル情報源符号化と学習理論
最適な符号化
ブロック符号

逐次符号

ユニバーサル符号問題

損失関数：
累積損失： 符号長
累積リスク： 期待符号長が未知補助情報つき情報源符号化と学習理論
目的変数
説明変数

（補助情報）

回帰問題，分類問題

補助情報つき情報源符号化の問題
情報理論的にはほとんど解決
補助情報つき情報源符号化についてはZiv[1984],
Subarahmanya[1995], Muramatsu[1998], Yan[2001],Uematsu[2002]等の研究があり，i.i.d. や定常エルゴード情報源等について，漸近最良の符号，で平均符号長が条件付エントロピーに近づくことは示されている．
学習理論の問題を考えると，リスク関数を最小化するダイレクトで詳細な性能解析が望まれる（最速でエントロピーに近づく）．
ベイズ符号で補助情報つき情報源符号化を考える

3. Why Bayes codes?
The advantage of Bayes codes?
1) Precise evaluation of the code length:
We can evaluate the exact asymptotic code lengthof Bayes codes as far as constant terms

2) The highest convergence rate:
The convergence rate of Bayes codes achieves thehighest order for universal codes

3) Maximin codes and Minimax codes:
The class of Bayes codes includes Maximin codes(Jeffrys’ prior) and Minimax codes4-1. Bayes codes
Known ← a parametric distribution:
Unknown ← k-dimensional real parameter vector:
Under the condition that the Arithmetic Coding is used forcoding, the decision of encoding probability
is the main
problem in universal coding.
The optimal solution from the view point of Bayes strategy
Block code:

Predictive code:4-2. the code length of Bayes codes
The code length of the Bayes block code is the same as that of the Bayes
predictive code.

Fisher information
Precise evaluation [Clarck&Barron90]:

This convergence rate achieves the highest order for universal codes5. Precise evaluation of the code length of the Bayes codeswith side information

Conditional Fisher information:

6. Bayes codes (unknown model )Known ← a parametric distribution class:
Unknown ← k-dimensional real parameter vector:
Unknown ← parametric model:
The encoding probability of Bayes codes:

Expectation is taken all over the model class
Precise evaluation for the code length for unknown model problem is givenby[Gotoh & Matsushima98]

The disadvantage of Bayes codes?
The complexity of the coding calculation
Assuming the conjugate prior as the prior probability of θ,
the integral does not need for calculating the coding
probability.
Integral is taken all over the parameter space

Summation is taken all over the model class
Assuming a special prior distribution on the models, someefficient algorithms can be constructed.

7-1. Context tree models

0010 0 1 0 1 ‥

1P(1¦00)P(0¦1)P(1¦10)‥

Context
A context tree(FSMX) model m is represented by a context tree( or a setof contexts) and a set of the parameters on the leaves :8. Bayes codes for Context tree models(1)Unknown model
Unknown parameters

010000011010111For calculation of the Bayes code, the expectation is taken over all context treemodels whose number is.

1

8. Bayes codes for Context tree models(2)A special class of the prior distribution of m001

1

The CTW algorithm is regarded as the Bayes code
assuming q(s) = 1/2

8. Bayes codes for Context tree models(3)The efficient coding algorithm is given by using the tree to which all context treemodels in M are merged and the special prior.
Block codes: CTW algorithm
Predictive codes: Predictive Bayes algorithm for Context tree models[Matsushima95]
0‥ 1 0 00

Posterior probability of models

1011

By using q(s), the complexity is deduced to O(d).

9. Side information Context tree models
00110
The context of X
is 1 under thecondition that thecontext of Y is 10‥t-2 t-1 tside information‥ 1 0 1‥ 1 1 0

1

A side information context tree model is represented by9. A special prior on Side-information context tree models

A special class of the prior distribution of m[Matsushima 05]

10. Algorithm of Bayes codes for Side-information
context tree models
Posterior probabilityof states of X
00Posterior probabilityof states of Y1011

11. Precise evaluation of the code length of the Bayes codes

Conditional Fisher information:

12. Time complexity of the algorithmd(x) : The depth of the context tree for x

The time complexity of the algorithm:
O(d(x)d(y))

0010The parallel time complexity of thealgorithm: O(d(x)+d(y))
11d(y) : The depth of the context tree for yまとめSource

CodingDecoding

Destination

・補助情報付ユニバーサル符号と学習理論の関係
・補助情報付ベイズ符号の累積log損失（符号長）の漸近評価
・補助情報文脈木モデルとその上での効率的符号化アルゴリズム