時間: 火曜4限 14:45-16:15

場所: κ23

担当: 金沢篤 (総合政策学部)

[講義概要]

シャノンの情報理論について講義する. 具体的には「情報の量」,「情報の符号化」,「情報の伝送」などに関して数学モデルを考え, その基礎理論を解説する. 伝送や記録においては, データ量をできるだけ減らしたい. 一方で, 通信においては, 伝送エラーの可能性があり, 誤りをできるだけ小さくするための符号化が必要となる. これらの課題に対する基本的な考え方と方法を考察する. 鍵となるのはエントロピーと呼ばれる数学的概念である. 情報理論は情報の表現と伝達に関する基礎理論であり, 代表的な応用例としては, データ圧縮, ビット誤り検出・訂正, 暗号などがある. また機械学習においても, 情報理論は重要な役割を果たす(例えば, 交差エントロピーは機械学習での損失関数として採用される). 計算機には「ハード」と「ソフト」の側面があるが, この講義ではその前提となる「理論」を扱う. つまり実装上の制約を考慮せず, 理論上の最適化問題を考察する. 普段何気なく使っている「情報」の定量的な扱いを学び, 情報理論を基盤とする技術の理解を深めることも講義の目標である. 

[履修条件]

確率と線形代数の基礎事項を仮定する. またこの講義は2021, 2022度に最適化の数理(金沢担当)として教えてきた科目を名称変更したものである. 最適化の数理(金沢担当)で単位を受けた学生は履修することができません.

[成績評価]

レポート4回

不正行為は厳しく処分します. 

[連絡先]

atsushikあっとまーくsfc.keio.ac.jp

気軽に質問等をメールしてくれて構いません. 

[演習問題/レポート問題]

レポートの公開と提出はSOLで行います.  

(1)ファイルのフォーマットはpdf, jpgのいずれか, 回転していないか確認.
(2)ファイル名は学籍番号, 氏名をつなげて “12345678金沢篤"といった具合. 

(3)2MB以下の1つのファイルに纏めて提出.

[講義記録/予定]

10/3 第1回: 歴史, 情報伝達の基本模型, エントロピー, 情報源/通信路符号化

10/10 第2回: 先見的/経験的確率, 確率の公理, 同時確率, 独立性, 条件付き確率, 確率変数, 確率分布, 期待値

10/17 第3回: 情報量, エントロピー, 結合エントロピー, 条件付きエントロピー, 相互情報量

10/24 第4回: 相互情報量の計算例, 情報源符号化, 符号の拡張, 一意復号可能性, 語頭符号, 符号木

10/31 第5回: クラフト・マクミランの不等式, 平均符号語長, ハフマン符号
11/7 第6回: シャノンの補題, 情報源符号化定理, 理想符号語長, シャノン・ファノ符号, コンパクト符号

11/14 第7回: ブロック符号化, 連長圧縮, LZ符号, 情報源(記憶, 定常性, エルゴード性), マルコフ情報源

11/21 休講(三田祭)

11/28 休講

12/5 第8回: (一般化)マルコフ情報源, 状態遷移図, 定常状態, 

12/12第9回: エントロピーレート, 通信路モデル, (2元)対称通信路, 2元消失通信路

12/19 第10回: 雑音, 通信路容量, 計算例

12/26 第11回: 通信路符号化, 平均誤り率, 誤り訂正・検出, 情報速度, 通信路符号化定理

1/9 第12回: 通信路符号化定理(続), (水平垂直)パリティ検査符号, ハミング符号, 線形符号, 生成行列

1/16 第13回: 検査行列, シンドローム, 誤り検出/訂正

1/23 第14回: 多項式表現, モジュラー演算, 多項式(剰余)環, 巡回符号, 生成多項式, その他の代数的符号