書記の読書記録#870『情報理論 -基礎と広がり-』

Thomas M.Cover，Joy A.Thomas『情報理論 -基礎と広がり-』のレビュー

情報理論 -基礎と広がり-

レビュー

情報理論のバイブルといってもいいような網羅性の高さが特徴，情報理論そのものに加えて統計学・ネットワーク・金融工学への応用にも詳しい。情報理論を学ぶ上で本書を理解することは一つの指標になり得る。

もくじ

第1章　入門と概論
　　1.1　本書の概要

第2章　エントロピー，相対エントロピー，相互情報量
　　2.1　エントロピー
　　2.2　同時エントロピーと条件付きエントロピー
　　2.3　相対エントロピーと相互情報量
　　2.4　エントロピーと相互情報量の関係
　　2.5　エントロピー，相対エントロピーおよび相互情報量のチェイン則
　　2.6　イェンセンの不等式およびその関連結果
　　2.7　対数和不等式とその応用
　　2.8　データ処理不等式
　　2.9　十分統計量
　　2.10　ファノの不等式
　　本章の要点
　　演習問題
　　歴史メモ

第3章　AEP
　　3.1　AEP定理
　　3.2　AEPから導かれる結果：データ圧縮
　　3.3　高確率集合と典型集合
　　本章の要点
　　演習問題
　　歴史メモ

第4章　確率過程のエントロピーレート
　　4.1　マルコフ連鎖
　　4.2　エントロピーレート
　　4.3　例：重み付きグラフ上のランダムウォークに対するエントロピーレート
　　4.4　熱力学の第二法則
　　4.5　マルコフ連鎖の関数
　　本章の要点
　　演習問題
　　歴史メモ

第5章　データ圧縮
　　5.1　符号の例
　　5.2　クラフトの不等式
　　5.3　最適符号
　　5.4　最適符号語長の限界
　　5.5　一意復号可能な符号に対するクラフトの不等式
　　5.6　ハフマン符号
　　5.7　ハフマン符号に関するコメント
　　5.8　ハフマン符号の最適性
　　5.9　シャノン-ファノ-イライアス符号
　　5.10　シャノン符号の競合最適性
　　5.11　公平なコインによる離散確率分布の生成
　　本章の要点
　　演習問題
　　歴史メモ

第6章　ギャンブルとデータ圧縮
　　6.1　競馬
　　6.2　ギャンブルと補助情報
　　6.3　記憶のある競馬とエントロピーレート
　　6.4　英文のエントロピー
　　6.5　データ圧縮とギャンブル
　　6.6　ギャンブルによる英文のエントロピー推定
　　本章の要点
　　演習問題
　　歴史メモ

第7章　通信路容量
　　7.1　通信路容量の例
　　7.2　対称通信路
　　7.3　通信路容量の性質
　　7.4　通信路符号化定理のプレビュー
　　7.5　定義
　　7.6　同時典型系列
　　7.7　通信路符号化定理
　　7.8　ゼロエラー符号
　　7.9　ファノの不等式と符号化逆定理
　　7.10　通信路符号化逆定理における等号成立条件
　　7.11　ハミング符号
　　7.12　フィードバック通信路容量
　　7.13　情報源・通信路分離定理
　　本章の要点
　　演習問題
　　歴史メモ

第8章　微分エントロピー
　　8.1　定義
　　8.2　連続確率変数に対する漸近等分割性
　　8.3　微分エントロピーと離散エントロピーの関係
　　8.4　同時微分エントロピーと条件付き微分エントロピー
　　8.5　相対エントロピーと相互情報量
　　8.6　微分エントロピー，相対エントロピー，相互情報量の性質
　　本章の要点
　　演習問題
　　歴史メモ

第9章　ガウス型通信路
　　9.1　ガウス型通信路：定義
　　9.2　ガウス型通信路に対する符号化逆定理
　　9.3　帯域制限された通信路
　　9.4　並列ガウス型通信路
　　9.5　有色ガウス型雑音通信路
　　9.6　フィードバックのあるガウス型通信路
　　本章の要点
　　演習問題
　　歴史メモ

第10章　レート歪み理論
　　10.1　量子化
　　10.2　定義
　　10.3　レート歪み関数の計算
　　10.4　レート歪み逆定理
　　10.5　レート歪み関数の達成可能性
　　10.6　強典型系列とレート歪み
　　10.7　レート歪み関数の特徴付け
　　10.8　通信路容量とレート歪み関数の計算
　　本章の要点
　　演習問題
　　歴史メモ

第11章　情報理論と統計学
　　11.1　タイプの手法
　　11.2　大数の法則
　　11.3　ユニバーサル情報源符号化
　　11.4　大偏差理論
　　11.5　Sanovの定理の例
　　11.6　条件付き極限定理
　　11.7　仮説検定
　　11.8　Chernoff-Steinの補題
　　11.9　Chernoff情報量
　　11.10　フィッシャー情報量とクラメール-ラオの不等式
　　本章の要点
　　演習問題
　　歴史メモ

第12章　最大エントロピー
　　12.1　最大エントロピー分布
　　12.2　例
　　12.3　変則的な最大エントロピー問題
　　12.4　スペクトル推定
　　12.5　ガウス型確率過程のエントロピーレート
　　12.6　Burgの最大エントロピー定理
　　本章の要点
　　演習問題
　　歴史メモ

第13章　ユニバーサル情報源符号化
　　13.1　ユニバーサル符号と通信路容量
　　13.2　2元系列に対するユニバーサル符号
　　13.3　算術符号
　　13.4　Lempel-Ziv符号
　　13.5　Lempel-Ziv符号の最適性
　　本章の要点
　　演習問題
　　歴史メモ

第14章　コルモゴロフ複雑度
　　14.1　計算モデル
　　14.2　コルモゴロフ複雑度：定義と例
　　14.3　コルモゴロフ複雑度とエントロピー
　　14.4　整数のコルモゴロフ複雑度
　　14.5　アルゴリズム的にランダムな系列と圧縮不可能な系列
　　14.6　ユニバーサル確率
　　14.7　コルモゴロフ複雑度
　　14.8　Ω
　　14.9　ユニバーサルギャンブリング
　　14.10　オッカムのかみそり
　　14.11　コルモゴロフ複雑度とユニバーサル確率
　　14.12　コルモゴロフ十分統計量
　　14.13　最小記述長原理
　　本章の要点
　　演習問題
　　歴史メモ

第15章　ネットワーク情報理論
　　15.1　ガウス型多ユーザ通信路
　　15.2　同時典型系列
　　15.3　多重アクセス通信路
　　15.4　相関のある情報源の符号化
　　15.5　Slepian-Wolf符号化と多重アクセス通信路の双対性
　　15.6　放送通信路
　　15.7　中継通信路
　　15.8　補助情報を伴う情報源符号化
　　15.9　補助情報源を伴うレート歪み問題
　　15.10　一般的多端子ネットワーク
　　本章の要点
　　演習問題
　　歴史メモ

第16章　情報理論とポートフォリオ理論
　　16.1　株式市場：いくつかの定義
　　16.2　対数最適ポートフォリオに関するKuhn-Tucker的特徴付け
　　16.3　対数最適ポートフォリオの漸近最適性
　　16.4　補助情報と成長率
　　16.5　定常な株式市場における投資
　　16.6　対数最適ポートフォリオの競合最適性
　　16.7　ユニバーサルポートフォリオ
　　16.8　Shannon-McMillan-Breimanの定理（一般のAEP）
　　本章の要点
　　演習問題
　　歴史メモ

第17章　情報理論における不等式
　　17.1　情報理論における基本的不等式
　　17.2　微分エントロピー
　　17.3　エントロピーと相対エントロピーの上界と下界
　　17.4　タイプに関する不等式
　　17.5　エントロピーに関する組合せ論的上界と下界
　　17.6　部分集合に対するエントロピーレート
　　17.7　エントロピーとフィッシャー情報量
　　17.8　エントロピー電力不等式とBrunn-Minkowskiの不等式
　　17.9　行列式に関する不等式
　　17.10　行列式の比に関する不等式
　　全体のまとめ
　　演習問題
　　歴史メモ

参考文献

本記事のもくじはこちら：

書記の読書記録まとめ｜Writer_Rinka｜note