情報理論的汎化境界

1. 相互情報量による汎化境界

1.1 基本アイデア

学習アルゴリズムAが訓練データSから仮説h = A(S)を出力するとき：

汎化誤差 ≤ √(2I(S; A(S)) / m)

I(S; A(S)): 訓練データと出力仮説の相互情報量
m: サンプル数

1.2 直感

• アルゴリズムがデータに「適応」しすぎると相互情報量が大きい
• データへの依存が弱いと汎化が良い
• 正則化は相互情報量を減らす効果

2. PAC-Bayes理論

2.1 設定

P: 事前分布（データを見る前に決定）
Q: 事後分布（学習後の仮説の分布）

PAC-Bayes境界:
E_{h~Q}[R(h)] ≤ E_{h~Q}[R̂(h)] + √(KL(Q||P) + log(m/δ)) / (2m))

2.2 意味

• KL(Q||P)が小さい → 事後分布が事前に近い → 汎化が良い
• 圧縮の観点：事前知識で予測できるほど汎化が良い

3. 圧縮境界

3.1 基本定理

訓練データのうちk個のサンプルで
同じ仮説が得られるとき：

汎化誤差 ≤ O((k log m + log(1/δ)) / m)

3.2 深層学習への応用

• 過パラメータ化でも少数のサンプルで「記述」可能なら汎化
• SGDの暗黙的圧縮効果

4. 深層学習の汎化の謎

4.1 古典理論との矛盾

• パラメータ数 >> サンプル数でも汎化
• ランダムラベルも完全に記憶可能
• VC次元的には汎化しないはず

4.2 新しい視点

5. 参考文献

• Xu & Raginsky (2017). "Information-theoretic analysis of generalization" ISIT
• McAllester (1999). "PAC-Bayesian model averaging" COLT
• Arora et al. (2018). "Stronger generalization bounds for deep nets via a compression approach" ICML