Near Rate-Distortion Bound Performance of Sparse

センサーネットワークでも
「More is different」
日本電信電話株式会社
NTTコミュニケーション科学基礎研究所
村山 立人 デイビス・ピーター
[email protected]
[email protected]
準備
誤り訂正

「システム的」解決策によって,通信路の物理的
特性を超えた信頼性を確保する.
《符号化》
《復号》
《通信》
情報に「冗長性」を追加してロバストな通信を実現
可逆データ圧縮

冗長な情報系列をより経済的に記述することで,
効率的なデータの記録を可能にする.
《符号化》
《復号》
《記録》
情報の「冗長性」を削除して経済的な記録を実現
不可逆データ圧縮

情報系列の信頼性を犠牲にすることで,効率的な
データの記録を可能にする.
《符号化》
《復号》
《記録》
情報の「信頼性」を犠牲にして経済的な記録を実現
シャノンのレート・歪み理論

全く冗長性の存在しない系列を圧縮できるか?
○
圧縮率
(レート)
×
ハミング距離
(歪み)
「レート・歪み関数」まではデータ圧縮が可能である
要約
センサーネットワークとは?
《センサー》
端末はノイズが含まれたセンサー
情報を独立に送信する
《コンピューター》
コンピューターは受信した複数
のセンサー情報を統合する
《ネットワーク》
センサー情報の通信コストは
ネットワークの容量を超えない
新しい自由度の発見

通信コストを一定にして,システムの情報損失を最
小化するセンサーの「数」を議論することを提案
《飽和戦略》
通信容量を飽和させる比較的少数のセン
サー情報を圧縮しないで伝送する
情報は高品質で少数
どちらの「戦略」が比較優位か?
情報は低品質で多数
《大システム化戦略》
通信容量を超える圧倒的多数のセンサー
情報を不可逆圧縮して伝送する
「飽和戦略」のイメージ
観測
圧縮
通信容量は
センサー2個分
復号
統合
通信コスト=センサーの数 (×観測したデータ量)
通信容量が一定だと,大規模化は不可能である
「大システム化戦略」のイメージ
観測
圧縮
復号
統合
通信コスト=センサーの数×情報の圧縮率
通信容量が一定でも,大システム化が可能となる
最適戦略の転移点が存在

最良符号のレート・歪み限界を仮定する
情報損失(dB)
飽和戦略
(少数&低圧縮)
最適戦略が
シフトする !
ノイズ(BER)
通信コスト=エージェント数×圧縮率が一定
ノイズが小さい⇒少数のエージェントで低圧縮
ノイズが大きい⇒多数のエージェントで高圧縮
システムのモデル
二極化する学術動向

センサーネットワークにおける理論と実践の乖離
《理論》 研究者は情報理論を専門とする
【利点】 システムに創発する非自明な関係性を記述
【欠点】 ユーザー側の要請を無視した「砂上の楼閣」
実用的な革新技術を先導する「標語的定理」が必要!
《実践》研究者はエンジニアリングを専門とする
【利点】ユーザー側の要請を現実的手段で解決
【欠点】えてして既存技術の「自明な集積」になりがち
「CEO問題」とは?
多数を「無限」
で近似する!
《エージェント》
無限個のエージェントがノイズが
含まれた情報を独立に送信する
《マネージャー》
マネージャーは受信した無限
個の情報を統合して予想する
《ネットワーク》
センサー情報の通信コストは
ネットワークの容量を超えない
必ずしも独立
に復号しない
「CEO問題」のイメージ
観測
圧縮
復号
統合
統合の前処理としての分散復号を強制しない
情報の復号と統合における自由度が大きい難問
もし強制的に独立復号させると
観測
圧縮
復号
統合
センサー情報を独立に復号しない自由度を消去
「大システム化戦略」+「復号・統合融合」=「CEO」
さらに圧縮自体を禁止すると
観測
圧縮
通信容量は
センサー2個分
復号
統合
センサー情報を独立に圧縮する自由度を消去
「飽和戦略」+「分散符号化」=「大システム化戦略」
システムの自由度

自由度に注目したモデルのマップ
《観測》
《圧縮》
《統合》
《復号》
非圧縮
独立復号
飽和戦略  大システム化戦略  CEO問題
「CEO問題」の結論

ネットワークの通信容量が一定なら,センサーが
無限にあっても有限の誤差が残る!
ノイズ
容量
《指数的減衰》
Berger, Zhang, & Viswanathan 1996
システム科学的な視点を持たない漸近論を完成
システム科学的な視点を持った非漸近論は?
システムの「解ける化」
《通信路モデル》
完全にランダム
な情報源を観測
《圧縮モデル》
レート・歪み限界
で不可逆圧縮
《統合モデル》
ビットごとの多数
決で最適に予想
「有効歪み」の通信路モデル

「有効歪み」を次式で定義する.
+ ノイズ
等価
有効歪み
独立復号過程は結局ひとつの
歪み
通信路モデルに帰着する!
ビット誤り率:有限系

《ニ項分布》

《累積分布》
《ビット誤り率》
ビットが反転している確率
ビット以下が反転している確率
ビット誤り率:無限系
有限系
中心極限定理
無限系
情報の伝達可能性

ビット誤り率は,レート・歪み限界の高圧縮領域の
漸近的な振る舞いによって分類できる.
情報が全く
伝わらない
情報が欠損
して伝わる
実現不可能
相対ビット誤り率

大システム戦略の飽和戦略に対する優位性を測
るため,ビット誤り率をデシベル(dB)で定義
大システム化
戦略
飽和戦略
《最適性の判定条件》
相対ビット誤り率が負⇒「大システム化戦略」
相対ビット誤り率が正⇒「飽和戦略」
シャノン限界では?
最良符号による大システム化

最良符号のレート・歪み限界を分析する.
《高圧縮領域》
テーラー展開

最良符号による大システム化戦略
有意な指数が実現可能!
情報を伝える
ことができる
飽和戦略に対しての比較優位性は?
最適戦略の転移理論

大システム化が最適戦略になる領域が存在!
ココが
すごい
優位性の存在は,コストを払ってシステムを大
規模化する理論的動機を与える!
ベクトル量子化
ベクトル量子化の定義

任意の情報ビットは唯一の「ボロノイ領域」に属し,
その「代表ゲージ」(代表点)に置き換わる.

指標の写像は「代表ゲージ」(代表点)を定義

代表ゲージ(代表点)が支配する「ボロノイ領域」
ベクトル量子化のイメージ

情報をボロノイ領域に分割して代表ゲージ(代表
点)を考える
孤立系の自由エネルギー

システムのコスト関数は「孤立系」で表現される
厳密解

コスト関数
(エネルギー)
エネルギーがハミング距離で測った「歪み」
「ランダム
ウォーク」
歪みがセンサー数の関数として厳密に求まる
ビット誤り率の厳密解

汎用公式に厳密解を代入

ベクトル量子化の性能限界
ベクトル量子化の限界

最良符号とは定性的に異なる性能限界を示す
冗長性がないので,それを搾取して圧縮できない
パリティ量子化
パリティ量子化の定義: K=2

任意の情報ビットは複数の「擬似ボロノイ領域」に
属し,代表ゲージの「パリティ」に置き換わる.

代表ゲージの集合が「パリティ」を定義

代表ゲージが支配する「擬似ボロノイ領域」
パリティ量子化のイメージ

情報を擬似ボロノイ領域に重複して分割して代表
ゲージを考え,パリティを構成する
多体系の自由エネルギー

システムのコスト関数は「多体系」で表現される
近似解
レプリカ法で計算可能

コスト関数
(エネルギー)
エネルギーがハミング距離で測った「歪み」
自由エネルギー
の鞍点解
歪みがセンサー数の関数として近似表現される
ビット誤り率の近似解

汎用公式に近似解を代入
鞍点方程式

パリティ量子化の性能限界
を漸近解析
定数

定数

鞍点方程式
秩序パラメータの分散:
 エントロピー非負条件:


積分測度:
パリティ量子化の限界: K=2

最良符号と定性的に似たような性能限界を示す
情報理論的な「トレード・オフ」をうまく搾取する
パリティ量子化の限界: K→∞

最良符号と同一の性能限界を示す
レート・歪み関数による漸近解析と一致する!
飽和戦略の実施例
5.4k bps
BER 20.0%
計測
伝送
32.4k bps
BER 20.0%
BER 9%
推定
大システム化戦略の実施例
5.4k bps
BER 20.0%
計測
圧縮
&
伝送
32.4k bps
BER 24.7%
BER 5%
推定