エントロピー
概要
エントロピーは情報理論における基本的な概念で、確率変数の不確実性や情報量を測る指標である。理論計算機科学においても、ランダムネス抽出器、プライバシー保護、通信理論など様々な場面で重要な役割を果たす。
また、チェインルールや劣モジュラ性に基づいて様々な定理の証明の道具としても有用で、エントロピーを考えることによって一気に証明の見通しが良くなる、といったことが多々ある。
エントロピーの種類
エントロピーには様々な種類があり、それぞれ異なる用途で使用される：
シャノンエントロピー
- 定義: $\entropy(X) = \sum_{x\in\calX} \Pr[X=x] \ln\frac{1}{\Pr[X=x]}$
- 特徴: 最も基本的なエントロピー、平均的な不確実性を測る
- 詳細: シャノンエントロピー
最小エントロピー
- 定義: $\minentropy(X) = \min_{x\in\calX} \ln\frac{1}{\Pr[X=x]}$
- 特徴: 最悪の場合の不確実性を測る、保守的な測度
- 詳細: 最小エントロピー
関連概念
KLダイバージェンス
- 定義: $\KL{X}{Y} = \sum_{x} \Pr[X=x] \ln \frac{\Pr[X=x]}{\Pr[Y=x]}$
- 特徴: 二つの確率変数の分布間の「距離」を測る
- 詳細: KLダイバージェンス
応用例
エントロピーは理論計算機科学の様々な分野で応用されています:
- ランダムネス抽出器: 低エントロピーな乱数源から高品質な乱数を生成
- 通信理論: 通信路の容量や符号化の限界の解析
- 暗号学: 暗号学的に安全な乱数生成のための条件