NTTコミュニケーション科学基礎研究所 村山 立人

Presentation on theme: "NTTコミュニケーション科学基礎研究所 村山 立人"— Presentation transcript:

1 NTTコミュニケーション科学基礎研究所 村山 立人 murayama@cslab.kecl.ntt.co.jp
データ圧縮の統計力学 NTTコミュニケーション科学基礎研究所 村山 立人

2 概要 疎行列符号化 ビリーフ プロパゲーション 符号化の統計力学 だいたいのアイデアは？ TAPの方法による直感的導出 情報理論との整合性
ベイズ統計との整合性

3 疎行列符号化

4 データ圧縮（可逆，歪なし） 冗長なNビットのデータをMビットに符号化する． Mビットの符号語からNビットのデータを正確に復号する．
圧縮率（レート）R=M/Nとデータの冗長度pにはトレードオフの関係がある． ベルヌイ系列に対するシャノン限界

5 疎行列符号化 NビットのデータをMビットに線形圧縮する． データ（情報）の系列 符号語（パリティ検査）の系列
行列AはM行N列で，各行K個，各列C個だけ1が存在する．他の要素はすべて0である．

6 トイ モデル（１） 疎行列 データ（情報）系列： 符号語（検査）系列： データの復号は？

7 トイ モデル（２） M=3はN=4より小さいので，逆算は不可能． 最初のビットが分かっていれば，逆算は可能． 「シャノン限界」

8 ビリーフ プロパゲーション

9 検査ノード（１） 局所システムの定義と記法

10 検査ノード（２） 検査ノードのフロー

11 情報ノード（１） 局所システムの定義と記法

12 情報ノード（２） 情報ノードのフロー

13 周辺化 周辺事後確率の近似式

14 局所計算モデル TAP方程式 事後確率の近似式

15 2値関数のパラメータ表示 情報ビットのパラメータ表示 検査ビットのパラメータ表示 事後確率のパラメータ表示

16 符号化条件 パリティ検査 事前確率 有効磁場：

17 検査ノードのTAP方程式（１） 検査ノードの方程式

18 検査ノードのTAP方程式（２） [Technique] 周辺化の方法

19 検査ノードのTAP方程式（３） 検査ノードの方程式（続き）

20 情報ノードのTAP方程式（１） 情報ノードの方程式

21 情報ノードのTAP方程式（２） [Technique] 線形化の方法

22 情報ノードのTAP方程式（３） 情報ノードの方程式（続き）

23 TAP方程式のパラメータ表示（１） 検査ビットのパラメータ表示 検査ノードのTAP方程式

24 TAP方程式のパラメータ表示（２） 情報ビットのパラメータ表示 情報ノードのTAP方程式

25 周辺事後確率のパラメータ表示 周辺事後確率のパラメータ表示 周辺事後確率のパラメータ方程式

26 ビリーフ プロパゲーション 初期化 逐次更新 周辺事後確率

27 MPM復号 周辺事後確率の最大化

28 符号化の統計力学

29 統計力学（１） 微視的状態の実現確率 巨視的状態の実現確率

30 統計力学（２） 分配関数 検査ビット系列のインスタンスに依存 分配関数の大きい巨視的状態が実現

31 統計力学（３） 自由エネルギー 巨視的状態にだけ依存 自由エネルギーが小さい巨視的状態が実現する

32 レプリカ解析（１） 自由エネルギー 巨視的状態は関数のペアで特徴づけられる

33 レプリカ解析（２） 鞍点方程式 強磁性解 常磁性解

34 レプリカ解析（３） 強磁性解 常磁性解

35 レプリカ解析（４） ある冗長度で突然，強磁性解と常磁性解の大小関係が交代する「相転移」が起こる． 単一情報源符号化についてのシャノン限界

36 レプリカ解析（５） MPM復号の性能は「秩序パラメータ」の共役変数で解析的に評価できる．

37 レプリカ法（６） 強磁性相でのMPM復号 情報理論のシャノン限界 常磁性相でのMPM復号 ベイズ統計の「コイン投げ」

38 データ圧縮の統計力学 TAPの方法によるビリーフ プロパゲーション レプリカ法による相転移の理論 学際的研究動向 情報理論との整合性
ベイズ統計との整合性 学際的研究動向 相関データの分散符号化（ネットワーク情報理論） 乱数系列の不可逆圧縮（レート・歪理論）