情報理論におけるユニバーサルなベイズ測度の汎化誤差の理論的解析

情報理論におけるユニバーサルなベイズ測度の汎化誤差の理
論的解析と統計科学への応用
大阪大学綾野孝則
大阪大学鈴木讓
MDL 規準とはデータから各モデルについてモデルの記述とモデルを仮定したときのデータの記述の長さの
合計を最小とするモデルを選択する情報量基準である (Rissanen, 1976)。データの記述長を求める際、仮定
したモデルに対して、それから生じたデータ xn = x1 · · · xn の起こる確率 P n (xn ) を推定する必要が生じる。
離散データに対しては、P n (xn ) の精度の良い推定法として、情報理論のユニバーサル符号化に基づいた方法
(ユニバーサルなベイズ測度) が提案されている。データの取り得る値を {0, 1, . . . , m − 1}、j の起こる確率を
∏m−1 c
θj としたとき、xn の起こる確率は Pθn (xn ) = j=0 θj j となる。ここで、cj は xn における j の起こった回数
∫
である。Jeﬀreys の事前確率 w(θ) に対して、Qn (xn ) = Pθn (xn )w(θ)dθ が離散データに対するユニバーサ
ルなベイズ測度であり、これを P n (xn ) の推定値として用いる。近年、Ryabko[1] により、連続データに対し
てもユニバーサルなベイズ測度が一般化され、それを用いることで、連続データに対しても MDL 規準が適用
できるようになった。その応用として、MDL 規準を用いた独立性検定法、因果推論、ベイジアンネットワー
クの構造推定法などが提案されている ([2])。X1 , X2 , . . . を [0, 1] 上の独立同分布の確率変数列で、各 Xi は
確率密度関数 f (x) を持つとする。(X1 , . . . , Xn ) の確率密度関数を f n (xn ) とする。sk を [0, 1] を k 等分した
[sk ]
区間の集合とする。xi の含まれる sk の元を xi
[s ]
[s ]
[s ]
[s ]
[s ]
[s ]
[s ]
として、gkn (xn ) = Qn (x1 k , . . . , xn k )/λn (x1 k , . . . , xn k )
[s ]
とする。λn (x1 k , . . . , xn k ) は x1 k × · · · × xn k のルベーグ測度である。gkn (xn ) を連続データに対するユニ
バーサルなベイズ測度といい、これを f n (xn ) の推定値として用いる。本発表では f n と gkn の誤差をカル
バックライブラー情報量 KL(f n ∥gkn ) で測ったときの収束率を導出する。以下を満たす f 全体を F とする。
• c, C > 0 が存在して、c ≤ f (x) ≤ C
• 0 < p ≤ 1, L > 0 が存在して、|f (x) − f (y)| ≤ L|x − y|p (ヘルダー連続)
定理 1 k, n に依存しない C1 , C2 > 0 が存在して、
1
C1
k log n
KL(f n ∥gkn ) ≤ 2p + C2
n
k
n
特に、k = [c0 n1/(2p+1) ] と取ると、n に依存しない C3 > 0 が存在して、
1
log n
KL(f n ∥gkn ) ≤ C3 2p/(2p+1)
n
n
定理 2 n に依存しない C4 > 0 が存在して、
1
inf
sup KL(f n ∥g n ) ≥ C4 n−2p/(2p+1)
n
g f ∈F n
ここで、inf gn は全ての関数 g n : [0, 1]n → R>0 を渡る。
参考文献
[1] B. Ryabko, Compression-Based Methods for Nonparametric Prediction and Estimation of Some Characteristics of Time Series, IEEE Transactions on Information Theory, VOL. 55, NO. 9, pp. 4309-4315,
2009.
[2] J. Suzuki, The Universal Measure for General Sources and its Application to MDL/Bayesian Criteria,
Data Compression Conference 2011, Snowbird, Utah, 2011.

Download Report