複数の相関のある情報源に対するベイズ符号化について

Presentation on theme: "複数の相関のある情報源に対するベイズ符号化について"— Presentation transcript:

1 複数の相関のある情報源に対するベイズ符号化について
*須子 統太 堀井 俊佑 松嶋 敏泰 平澤 茂一 早稲田大学

2 背景 無歪み情報源符号化 可変長符号化 パラメトリックな情報源モデルに対するユニバーサル 符号化 ⇒符号化確率を計算して算術符号化
ベイズ符号 i.i.d.情報源[Clarke 90] 文脈木情報源[Matsushima 95][Gotoh 98] 補助情報付き情報源[Matsushima 05] etc.

3 研究目的 本研究の目的 複数の相関のある情報源（Multiple Correlated 情報源） 相関構造を考慮したベイズ符号化法
Sources encoder decoder channel … 相関構造を考慮したベイズ符号化法 符号長の漸近評価

4 従来研究：i.i.d.情報源に対するベイズ符号
：未知パラメータベクトル 事前分布　　　　　は既知と仮定 ベイズ符号化確率 [Matsushima 91] ブロック符号化 逐次符号化 ※符号化確率は一致することが知られている

5 従来研究：i.i.d.情報源に対するベイズ符号
符号化確率の計算 自然共役事前分布を仮定することで解析的に解ける 平均符号長 定理[Clarke 90] ：　　　中の記号　　の頻度 ：ハイパーパラメータ（既知） 平均冗長度 : パラメータサイズ

6 従来研究：文脈木情報源に対するベイズ符号
過去に出現した系列に依存して次のシンボルの出現確率が 変わる マルコフ情報源の一般化 確率モデル ⇒考え得る最大の木の深さ d に対して，モデルの数が指数的 に増える 未知 図．文脈木情報源モデル m の例

7 従来研究：文脈木情報源に対するベイズ符号
ベイズ符号化確率（逐次符号化確率） 計算アルゴリズム [Matsushima95]で効率的な計算アルゴリズムが提案 計算量　O(nd) 平均符号長 定理[Gotoh 98] : 真のモデルのパラメータサイズ

8 従来研究：補助情報のあるベイズ符号 補助情報のある情報源 確率モデル channel Sources encoder decoder
補助情報源系列

9 従来研究：補助情報のあるベイズ符号 ベイズ符号化確率（逐次符号化確率） 平均符号長 定理[Matsushima 05] : パラメータサイズ

10 ＭＣ（Multiple Correlated）情報源
Sources encoder decoder channel …

11 ＭＣ（Multiple Correlated）情報源
拡大情報源のi.i.d.系列と見なした場合のベイズ符号 その場合の平均符号長（[Clarke90]の結果より） 平均冗長度 相関構造を利用して冗長度を削減する方法を提案

12 提案符号化法のアイディア 例 K=3で以下の相関構造が既知だとする ⇒ 　 の出現確率は　　　　にしか依存しない パラメータ数2

13 提案符号化法のアイディア 符号化の例 Step-1: を符号化. Step-2: を補助情報と見なし を符号化．

14 提案符号化法のアイディア 平均符号長⇒[Clarke90]の結果を適用可能 Step-1: を符号化.

15 提案符号化法のアイディア 提案符号化の総平均符号長 拡大情報源のi.i.d.系列と見なした場合の平均符号長
⇒相関構造を利用することで冗長度を削減できる

16 提案符号化法（相関構造既知の場合） 任意の に対し， の相関構造が既知の場合（ は未知） [Scheme A] を順番に符号化
任意の　　　　　　　　　に対し，　　　　　　　　　　　　　　 の相関構造が既知の場合（　　　は未知） [Scheme A] 　　　　　　　　　　　を順番に符号化　 　　　を符号化する場合，　　　　　　　　　　　　を補助情 報として用い以下の符号化確率で符号化する

17 提案符号化法（相関構造既知の場合） 任意の　　　　　　　　　に対し，　　　　　　　　　　　　　　 の相関構造が既知の場合（　　　は未知） 　　　の平均符号長 パラメータサイズ 総平均符号長

18 相関構造のクラス 　　　　　　　　　　　　　　の相関構造の取り得るクラス　　 　　　　の例

19 k に対して指数的にモデルの数が増えてしまう
相関構造のクラス k に対して指数的にモデルの数が増えてしまう

20 相関構造のクラスの制約 完全木の完全部分木で表わされるモデルのクラス 文脈木情報源と本質的に等価なモデルクラスを仮定 ・・・ ・・・ ・・・

21 提案符号化法（相関構造未知の場合） 任意の に対し， の相関構造が未知の場合（ も未知） [Scheme B] を順番に符号化
任意の　　　　　　　　　に対し，　　　　　　　　　　　　　　 の相関構造が未知の場合（　　　も未知） [Scheme B] 　　　　　　　　　　　を順番に符号化　 　　　を符号化する場合，　　　　　　　　　　　　を補助情 報として用い以下の符号化確率で符号化する． （計算は[Matsushima 95]と等価なアルゴリズム※予稿参照）

22 提案符号化法（相関構造未知の場合） 任意の に対し， の相関構造が未知の場合（ も未知） の平均符号長 総平均符号長
任意の　　　　　　　　　に対し，　　　　　　　　　　　　　　 の相関構造が未知の場合（　　　も未知） 　　　の平均符号長 真の相関構造のパラメータサイズ 総平均符号長

23 まとめ 複数の相関のある情報源に対するベイズ符 号化法について示した 漸近的な平均符号長を示した [Scheme A]：相関構造が既知
[Scheme B]：相関構造が未知 漸近的な平均符号長を示した [Scheme A]と[Scheme B]が一致

24 Reference [Clarke 90]B.S. Clarke and A.R. Brron, “Information-theoretic asymptotics of Bayes methods,” IEEE Trans. Inf. Theory, vol.IT-36, no.3, pp.453–471, May 1990. [Matsushima 91] T. Matsushima, H. Inazumi and S. Hirasawa, “A Class of Distortionless Codes Designed by Bayes Decision Theory,” IEEE Trans. Inf. Theory, vol.37, No.5, pp. 1288–1293, [Matsushima 95] T. Matsushima and S. Hirasawa, “A Bayes coding algorithm for FSMX sources,” In Proc. Int. Symp. of Inf. Theory, pp.388, 1995. [Gotoh 98] M. Gotoh, T. Matsushima, S.Hirasawa, “A generalization of B.S.Clarke and A. R. Barron’s asymptotics of Bayes codes for FSMX sources,” IEICE Trans. fundamentals, vol.E81-A, no.10, pp.2123–2132, 1998. [Matsushima 05] T. Matsushima and S. Hirasawa, “Bayes Universal Coding Algorithm for Side Information Context Tree," In Proc. Int. Symp. of Inf. Theory, pp , 2005.