センサーネットワークでも 「More is different」 日本電信電話株式会社 NTTコミュニケーション科学基礎研究所 村山 立人　デイビス・ピーター murayama@cslab.kecl.ntt.co.jp davis@cslab.kecl.ntt.co.jp

準備

誤り訂正 「システム的」解決策によって，通信路の物理的特性を超えた信頼性を確保する． 情報に「冗長性」を追加してロバストな通信を実現 《符号化》 　　　　　　　　　　　　《通信》 《復号》 情報に「冗長性」を追加してロバストな通信を実現

可逆データ圧縮 冗長な情報系列をより経済的に記述することで，効率的なデータの記録を可能にする． 情報の「冗長性」を削除して経済的な記録を実現 《符号化》 　　　　　　　　　　　　《記録》 《復号》 情報の「冗長性」を削除して経済的な記録を実現

不可逆データ圧縮 情報系列の信頼性を犠牲にすることで，効率的なデータの記録を可能にする． 情報の「信頼性」を犠牲にして経済的な記録を実現 《符号化》 　　　　　　　　　　　　《記録》 《復号》 情報の「信頼性」を犠牲にして経済的な記録を実現

× ○ シャノンのレート・歪み理論 全く冗長性の存在しない系列を圧縮できるか？ 圧縮率 （レート） ハミング距離 （歪み） 「レート・歪み関数」まではデータ圧縮が可能である

要約

センサーネットワークとは？ 《センサー》 端末はノイズが含まれたセンサー情報を独立に送信する 《コンピューター》 0100110 100110101011001010110 1100101 《コンピューター》 コンピューターは受信した複数のセンサー情報を統合する 《ネットワーク》 センサー情報の通信コストは ネットワークの容量を超えない

新しい自由度の発見 通信コストを一定にして，システムの情報損失を最小化するセンサーの「数」を議論することを提案 《飽和戦略》 通信容量を飽和させる比較的少数のセンサー情報を圧縮しないで伝送する どちらの「戦略」が比較優位か？ 情報は高品質で少数 情報は低品質で多数 《大システム化戦略》 通信容量を超える圧倒的多数のセンサー情報を不可逆圧縮して伝送する

「飽和戦略」のイメージ 通信コスト=センサーの数 (×観測したデータ量) 通信容量が一定だと，大規模化は不可能である 観測 圧縮 復号 通信容量は センサー2個分 統合 通信コスト=センサーの数　(×観測したデータ量) 通信容量が一定だと，大規模化は不可能である

「大システム化戦略」のイメージ 観測 圧縮 復号 統合 通信コスト＝センサーの数×情報の圧縮率 通信容量が一定でも，大システム化が可能となる

最適戦略の転移点が存在 最良符号のレート・歪み限界を仮定する 情報損失（dB） 最適戦略が シフトする ! 飽和戦略 （少数&低圧縮） 大システム化戦略 （多数&高圧縮） ノイズ(BER) 通信コスト=エージェント数×圧縮率が一定 ノイズが小さい⇒少数のエージェントで低圧縮 ノイズが大きい⇒多数のエージェントで高圧縮

システムのモデル

実用的な革新技術を先導する「標語的定理」が必要！ 二極化する学術動向 センサーネットワークにおける理論と実践の乖離 《理論》 研究者は情報理論を専門とする 【利点】 システムに創発する非自明な関係性を記述 【欠点】 ユーザー側の要請を無視した「砂上の楼閣」 実用的な革新技術を先導する「標語的定理」が必要！ 《実践》研究者はエンジニアリングを専門とする 【利点】ユーザー側の要請を現実的手段で解決 【欠点】えてして既存技術の「自明な集積」になりがち

「CEO問題」とは？ 多数を「無限」で近似する！ 必ずしも独立に復号しない 《エージェント》 無限個のエージェントがノイズが含まれた情報を独立に送信する 0100110 100110101011001010110 1100101 《マネージャー》 マネージャーは受信した無限個の情報を統合して予想する 《ネットワーク》 センサー情報の通信コストは ネットワークの容量を超えない 必ずしも独立に復号しない

「CEO問題」のイメージ 観測 圧縮 復号 統合 統合の前処理としての分散復号を強制しない 情報の復号と統合における自由度が大きい難問

もし強制的に独立復号させると センサー情報を独立に復号しない自由度を消去 「大システム化戦略」+「復号・統合融合」=「CEO」 観測 圧縮

さらに圧縮自体を禁止すると センサー情報を独立に圧縮する自由度を消去 「飽和戦略」+「分散符号化」=「大システム化戦略」 観測 圧縮 復号 通信容量は センサー2個分 統合 センサー情報を独立に圧縮する自由度を消去 「飽和戦略」+「分散符号化」=「大システム化戦略」

システムの自由度 自由度に注目したモデルのマップ 飽和戦略 大システム化戦略 CEO問題 非圧縮 独立復号 《観測》 《圧縮》 《統合》 《復号》 非圧縮 独立復号 飽和戦略　　大システム化戦略　　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% 　& 伝送 32.4k bps BER 24.7% BER 5% 推定