情報論的学習理論テクニカルレポート 2009
Technical Report on Information-Based Induction Sciences 2009 (IBIS2009)

Hannan-Quinn の命題は、線形回帰でも、ガウス型 Baysian ネット
ワークの構造推定でも正しい
The Hannan-Quinn proposition is true for learning linear regression
and Bayesian network structures
鈴木譲∗
Joe Suzuki
Abstract: This paper proves dn = 2 log log n is the smallest {dn }∞n=1 such that the information criterion H + (k/2)dn , where H is the empirical entropy of n examples and kis the number of parameters that express the probability distribution, satisﬁes consistency
for the problem of learning linear regression. Thus far, the problem was solved only for theproblems of learning ARMA (autoregressive moving average, Hanann-Quinn, 1979) andconditional probabilities (Suzuki, 2006). The new result is good for learning the structureof Gaussian Bayesian networks as well.
Keywords:

1

まえがき
AIC や MDL/BIC といった情報量基準は、統計科学の諸問題でよく適用されている。ここで、例の個数を nとすれば、尤度の最大値にマイナスをつけたもの (経験2. 正しくないモデルが有限回しか選択されない例の無限列の集合に対して確率測度 1 が割当てられる(強一致性)的エントロピー) にパラメータ数もしくはパラメータ数

MDL/BIC(dn = log n) では両方の性質が満足されるが、AIC(dn = 2) では両方とも満足されない。一般に、dnを加えた値を AIC、それに ×(1/2) log n を加えた値をが小さいと過学習が原因で、強一致性が満足されない。

MDL/BIC といっている。一般的に、dn /n → 0 となる正実数列を {dn }∞n=1 、モデル g の経験的エントリピーお無論、モデル選択において一致性だけが要求されるすべての性能ではないが、本論文では、強一致性を満足す

よびパラメータ数をそれぞれ H(g), k(g) とおいてる最小の {dn } とな何かについて議論する。

H(g) +k(g)dn2(情報量基準) を最小にするモデルを選択する問題として定式化できる。AIC なら dn = 2、MDL/BIC ならdn = log n というふうにである。つまり、情報量基準の{dn } の選び方は無数にある。
モデル選択で、{dn } の選び方によって、n → ∞ で正しいモデルを見出す性質 (一致性) がどのようにかわるかが、よく議論される。

1. 各 n で正しいモデルを選択する確率が 1 に収束する (弱一致性)

情報量基準は、適用する問題によって、経験的エントロピーとパラメータ数の定義が異なる。1979 年に Hannan-Quinn は、ARMA(Autoregression Moving Average, 自己回帰移動平均) の場合、「dn = 2 log log n が強一致性を満足する最小の {dn } である」(本論文では、Hannan-Quinn の命題とよぶ) ことを証明した。そして、dn =2 log log n とする情報量基準 HQ が、ARMA 以外の問題にも適用されるようになった。しかしながら、Hannan-Quinn のオリジナル論文からわかることであるが、HannanQuinn の命題の証明が、ARMA という問題の性質に強く依存しており、線形回帰をはじめとする他の問題で同じ性質が真であるか否かは、証明がされていない。ただ、そういうことに頓着せずに、ARMA 以外の問題に HQ∗ 大阪大学大学院理学研究科, 560-0043 豊中市待兼山, tel. 06-68505315, e-mail suzuki@math.sci.osaka-u.ac.jp,
Osaka University, Yoyonaka, Osaka, 560-0043, Japan.

を無造作に使う人は多い。
ただ、ごく最近になって、データマニングやパター

ン認識でよく用いられる条件付確率の学習について、Hannan-Quinn の命題が正しいことが証明された (Suzuki,2006)。このことは、有限型 Bayesian ネットワークの構造推定においても、Hannan-Quinn の命題が正しいことを意味する。

Cramer の公式を用いて、{γm }km=0 の値から、(k + 1) ×(k+1) の連立一次方程式の解として、σ 2 および {λm }km=1の値が得られる。
一般に、{γm }km=0 の値は、未知であるので、その実現値

本論文では、線形回帰においても Hannan-Quinn の命

x = (x1 , · · · , xn ) ∈ X1 (Ω) × · · · × Xn (Ω)

題が正しいことを証明する。この問題の解決は、非常に大きな意義があると思われる。そうでないと、情報量基から、x̄ :=いと、HQ を適用する意味が見出されないからである。
強一致性は例では検証できないため、線形回帰で Hannan-Quinn の命題が真であるか否か、予想することは容易ではなかった。線形回帰で、HQ 以外では、

dn→∞log log nが過去に知られた強一致性を満足する最小の {dn } の十分条件である (Rao-Wu, 1989)。

2 節で、ARMA と条件付確率で Hannan-Quinn の命
題がどのように証明されたかの概略を簡潔に述べる。3節で、まず、線形回帰で情報量基準を適用した場合のモデル選択の漸近的な誤り率の公式を導く (3.1 節)。これは副産物ではあるが、主結果の証明への重要なステップとなる。3.2 節で Hannan-Quinn の命題の証明をおこなう。さらに 4 節で、線形回帰とガウス型 Bayesian ネッ

1∑xin i=1n準を適用する際に、Hannan-Quinn の命題が証明されなおよび1 ∑(xi − x̄)(xi+m − x̄)γ̂m := γ̂−m :=n i=1n−mを計算して推定する。したがって、Yule-Walker 方程式は、以下のようにかける。
 
−1γ̂1γ̂2···γ̂kσ̂k2−γ̂0  0γ̂0γ̂1· · · γ̂k−1   λ̂1,k   −γ̂1   0 γ̂1γ̂0· · · γ̂k−2   λ̂2,k  =  −γ̂2  , .

..
..
..
..   ..   ..  .
.
.
.
.  .   .  .
0 γ̂k−1 γ̂k−2 · · ·γ̂0λk,k−γ̂k
特に、次数 k が未知であれば、各 k について上記の連立方程式を解き、トワークの構造学習の問題との関係をのべ、後者においL(xn , k) =ても Hannan-Quinn の命題が正しいことを証明する。5節で、本論文のまとめをおこなう。

knlog σ̂k2 + dn22の値を計算して、この値を最小にする k を推定値とす

22.1

Hannan-Quinn の命題が証明された例

る。この k を求める操作を ARMA の学習とよぶ。

ARMAが成立する。したがって、k = 1, 2, · · · に対して、以下では、{Wi }∞i=−∞ を平均 0 分散 1 の独立同一分布にしたがう確率変数の列、{Xi }∞i=−∞ を平均 0、

Xi =k
∑

λj Xi−j + Wi

j=1および実数 {λi }ki=1 で定義される確率変数の列とする (自己回帰移動平均, autoregressive moving average)。ここで、E[Xi ] = 0 であり、また {Xi } は定常であるので、m ≥ 0 として、γm := EXi Xi+m は i によらず、また以下の方程式 (Yule-Waker 方程式) が得られる。

γm =k∑j=1λj γm−j + δ0m σ 2

一般に、
2σ̂k2 = {1 − λ̂2k,k }σ̂k−12{L(xn , k) − L(xn , k − 1)}σ̂ 2= n log 2 k + dn
σ̂k−1
≤ −n(1 −σ̂k2) + dn
2σ̂k−1(1)= −nλ̂2k,k + dnなる変形ができる。また、n → ∞ で、k ≤ k ∗ に対して
σ̂ 2は、 2 k は 1 より小さな値に概収束する。したがって、
σ̂k−1(1) より、L(xn , 0) > L(xn , 1) > · · · > L(xn , k ∗ − 1) > L(xn , k ∗ )が確率 1 で成立する。他方、k ≥ k ∗ + 1 に対しては、
σ̂k2は 1 に概収束する。Hannan-Quinn(1979) は、重2σ̂k−1
複対数の法則から、

λ̂2k,k≤12n−1 log log nが確率 1 で成立することを証明し、dn = 2c log log n(c > 1) について

1. Ĝn = G ∗2. Ĝn ⊃ G ∗ (過学習)3. Ĝn ̸⊇ G ∗ (未学習)に大別できる。fl で自由度 l の χ2 分布の確率密度関数をあらわすものとする。
∞

L(xn , k ∗ ) < L(xn , k ∗ + 1) < · · ·が確率 1 で成立することを証明した。

条件付確率

2.2

X, Y : Ω → R を確率空間 (Ω, F, µ) における確率変数とし、Y が有限 (|Y (Ω)| < ∞) であることを仮定する。
以下では、σ-集合体 G1 , G2 が A ∈ G1 =⇒ A ∈ G2 を満足するとき、G1 ⊆ G2 とかくものとする。また、µ は確率測度であり、µ(Ω) = 1 を満足する測度である。

1. G ⊃ G ∗ への誤り確率は

命題 1∫ (Suzuki, 2006){k(G)−k(G∗ )}dnfk(G)−k(G∗ ) (x)dx

2. 確率 1 で、G (̸⊇ G ∗ ) への誤り確率は 0
3. dn = 2c log log n (c > 1) で、確率 1 で誤り確率は
0
X (1) , · · · , X (N ) を有限の値をとる確率変数とし、π (i) ⊆{1, · · · , i − 1}(i = 1, · · · , N ) について、
1. X (i) と {X (j) }j∈{1,··· ,i−1}\π(i) が {X (j) }j∈π(i) のもとで、条件付独立であり、以下では、事象 (X = x) のもとでの、事象 (Y = y)の条件付確率を µY |X (y|x), x ∈ X(Ω), y ∈ Y (Ω) で表記する。X(Ω) における同値関係 ∼ を、x, x′ ∈ X(Ω) について2. π (i) の真部分集合について、条件付独立でない
この条件を満足する π := (π (1) , · · · , π (N ) ) は一意にきまる (有限型 Bayesian ネットワークの構造)。|X (i) (Ω)| =µY |X (y|x) = µY |X (y|x′ ), y ∈ Y (Ω) ⇐⇒ x ∼ x′で定義する。実際、

α(i) とおくと、確率パラメータの数は、k(π (i) ) := (α(i) −∏(i)1) j∈π(i) α(j) となる。学習の誤りは、真の π (i) を π∗ 、(i)推定された π (i) を π̂n とかくと、

1. x ∼ x

1. π̂n = π∗

2. x ∼ x′ ⇐⇒ x′ ∼ x

2. π̂n ⊃ π∗ (過学習)3. x ∼ x′ , x′ ∼ x′′ =⇒ x ∼ x′′ .

3. π̂n ̸⊇ π∗ (未学習)が成立する。この同値類で生成される事象の集合を G ⊆(i)(i)(i)(i)(i)に大別できる。

F とかく。条件付確率の学習では、n 個の独立に発生した例 z n = (z1 , · · · , zn ),(i)(i)1. π (i) (⊃ π∗ ) への誤り確率は、∫ ∞fk(π(i) )−k(π(i) ) (x)dx系1zi := (xi , yi ) ∈ X(Ω) × Y (Ω) , i = 1, 2, · · · , n(i){k(π (i) )−k(π∗ )}dnから、モデル G を見出す問題として定義されるものと(i)2. 確率 1 で、π (i) (̸⊇ π∗ ) への誤り確率は 0する。
本稿では、例 z n ∈ X n (Ω) × Y n (Ω) からk(G)L(z n , G) := H(z n , G) +dn ,2(情報量基準) の値を比較して、それを最小にする G を、学習結果とよぶ。ただし、H(z n , G) を経験的エントロピー、k(G) をそのパラメータの数とした。
学習の誤りは、真の G を G ∗ 、推定された G を Ĝn と
かくと、∗3. dn = 2c log log n (c > 1) で、確率 1 で誤り確率は03

線形回帰の場合の証明

したがって、2 乗誤差の差は以下では、標本空間を Ω とし、ϵ を正規分布 N (0, σ 2 )にしたがう確率変数、Y, X1 , · · · , Xp をY =p∑

Sp −Sm = y T (I −Pp )y−y T (I −Pm )y = y T (Pm −Pp )yとなる。ここで、
TPmαj Xj + ϵT
T= Xm {(XmXm )T }−1 Xm= Pm

j=1にしたがう確率変数、Xp+1 , · · · , Xm を Y −∑p

j=1 αj Xjとは独立な確率変数とする (0 ≤ p ≤ m)。
独立に生成した n 個の例 {(yi , xi,1 , · · · , xi,m )}ni=1yi ∈ Y (Ω), (xi,1 , · · · , xi,m ) ∈ X1 (Ω) × · · · × Xm (Ω)
が得られたものとする。α = ϵi := yi −∑m

j=1 αj xi,j

x1,1 .
.
X m :=  .
xn,1...

α̂ = [α̂1 , · · · , α̂m ]T := (X Tm X m )−1 X Tm y が得られる。
他方、Pm := X m (X Tm X m )−1 X Tm とおくと、TPp Pm = PpT Pm= (Pm Pp )T = PpT = Ppが成立する。したがって、Pp , I −Pp だけではなく、Pm −Pp についても、
2(Pm − Pp )2 = Pm− Pm Pp − Pp Pm + Pp2 = Pm − Pp:=i=1(yi −m∑

モデル選択の誤り確率

命題 2Sp − Smは、自由度 q := m − p の χ2 分布にSp /nので、I − Pp , Pm − Pp のトレースはそれぞれ n − p, q となる。また、固有値 1 の重複度もそれぞれ、n − p, q とがいえるので、このときの 2 乗誤差はn∑3.1

証明: 簡単な計算から、行列 Pp のトレースが p となる(I − Pm )2 = I − Pmなる (固有値 0 の重複度はそれぞれ、p, n − q となる)。

α̂j xi,j )2

j=1=||y − X m α̂||2=||(I − Pm )y||2=y T (I − Pm )yとかける。同様に、n 個の例 {(yi , xi,1 , · · · , xi,p )}ni=1 か
x1,p.. TT−1.  , Pp := X p (X p X p ) X pxn,pとおくと、2 乗誤差は

Sp := y T (I − Pp )yとなる。

Pm Pp = Pm Xp (XpT Xp )−1 XpT = Xp (XpT Xp )−1 XpT = Pp

従う

2= Pm
Pm

ら出発する場合、
x1,1 . . .
 .
..
X p :=  ..
.
xn,1 . . .

Xp より、 が成立する。このような性質を満足する正方行列は冪x1,my1
ϵ1 .  .  等 (Idempotent) 行列とよばれ、固有値として 0 および.. .  , y :=  ..  , ϵ :=  ..  1 しかもたないことが知られている (Chatterjee-Hadi,xn,mynϵm 1987)。

...
..
.

とおくと、y = X m α + ϵ とかける。これを解くと、Sm同様に PpT = Pp が成立する。また、Pp Xp = Xp , Pp Xp =

α1.. .  を未知として、
αmT T
TT= (Xm) {(XmXm )−1 }T Xm

まず、事象 X p のもとで、I −Pp の直交行列 U = (ui,j )を、u1 , · · · , un−p の固有値が 1、un−p+1 , · · · , un の固有∑n
値が 0 になるように選ぶと、Y の分散が σ 2 、 i=1 u2j,i =n∑1 より、zj := uTj y =uj,i yi は、i=1

1. 1 ≤ j ≤ n − p に関して、N (0, σ 2 ) にしたがう。
2. n − p + 1 ≤ j ≤ n に関して、値が 0
したがって、大数の強法則より、確率 1 でn−p11∑ 2
Sp =z → σ2nn j=1 j(2)次に、事象 X m のもとで、Pm − Pp の直交行列 V =(vi,j ) を、v 1 , · · · , v q の固有値が 1、v q+1 , · · · , v n の固有∑n2
値が 0 になるように選ぶと、Y の分散が σ 2 、 i=1 vj,i=n∑1、v Tj v k = 0(j ̸= k) より、rj := v Tj y =vj,i yi は、
i=1

1. 1 ≤ j ≤ q に関して、N (0, σ 2 ) にしたがう (相互に独立)。

Hannan-Quinn の命題の証明

3.2
命題 3

2. q + 1 ≤ j ≤ n に関して、値が 0
したがって、n → ∞ で、q∑zj2
Sp − Sm=∼ χ2q2σ2σj=1(3)

ここで、独立な標準正規分布にしたがう q 個の確率変数の 2 乗和が自由度 q の χ2 分布にしたがうことを用いた。

(証明終)
以下では、π ⊆ {1, · · · , N } について、{Xj }j∈π , Y の2 乗誤差を S(π) であらわし、k(π)
dn2および k(π) = |π| とおく。ただし、π∗ ⊆ {1, · · · , N } を真の π であるとする。また、L(z n , π) := n log S(π) +定理 1 π ⊃ π∗ について、L(z n , π) < L(z n , π∗ ) となる∫ ∞{k(π)−k(π∗ )}dni=1の比が確率 1 で 1 になる。E[Zi ] = 0, E[Zi2 ] = 1 である
ので、重複対数の法則を適用すると、√ T
nv j y/σ√≤1n log log nすなわち

v Tj y √≤ log log nσが確率 1 で成立する。これは、Sp − Sm≤ q log log nSp /nが確率 1 で成立することを意味する。

fk(π)−k(π∗ ) (x)dx(証明終)

証明: まず、定理 3 dn := 2c log log n (c > 1) のとき、確率 1 で2{L(z n , π) − L(z n , π∗ )}S(π)= n log+ {k(π) − k(π∗ )}dn(4)S(π∗ )S(π∗ ) − S(π)= n log(1 −) + {k(π) − k(π∗ )}dnS(π∗ )S(π∗ ) − S(π)− Rn + {k(π) − k(π∗ )}dn
= −S(π∗ )/n(5)L(z n , π) > L(z n , π∗ )
証明: (6) と命題 3 は、定理 3 の成立を意味する。

(証明終)

4

ガウス型 Bayesian ネットワークの構造学習の場合の証明
条件付確率の学習を、有限型 Bayesian ネットワークのの第 2 項

Rn :=

(7)

証明: 記法は命題 2 と同様とし、p + 1 ≤ j ≤ m とする。
√大数の強法則より、 nvi,j は確率 1 で n によらない一√δi,j yi
定値 δi,j に収束する。Zi :=とおくと、 nv Tj y と
σnn∑∑δi,j yiσ=σZi
σi=1(2)(3) は、命題 2 を意味する。

確率は、

Sp − Sm≤ q log log nSp

1 (nh)2S(π∗ ) − S(π), h :=,0 < θ < 12n (θh − 1)2S(π∗ )は、n → ∞ で 0 に概収束する。したがって、L(z n , π) < L(z n , π∗ )S(π∗ ) − S(π)> {k(π) − k(π∗ )}dn⇐⇒S(π∗ )/n構造学習に適用したのと同様に、線形回帰の学習を、ガウス型 Bayesian ネットワークの構造学習に適用することができる。X (1) , · · · , X (N ) を確率変数、ϵ(i) ∼ N (0, σi2 )として、X (i) =を満足する π (i) を見出す問題となる。

命題 2 より、これは定理 1 を意味する。

定理 2 π ̸⊇ π∗ について、確率 1 で L(z n , π) > L(z n , π∗ )S(π)> 0 となり、また dn /n → 0 が成S(π∗ )立する。(4) より、これは定理 2 を意味する。
証明: 確率 1 で(証明終)α(j) X (j) + ϵ(i)j∈π (i)(6)

(証明終)

∑

定理 4(i)1. π (i) (⊃ π∗ ) への誤り率は、∫ ∞fk(π(i) )−k(π(i) ) (x)dx(i){k(π (i) )−k(π∗ )}dn∗(i)2. 確率 1 で、π (i) (̸⊇ π∗ ) への誤り確率は 0
3. dn = 2c log log n (c > 1) で、確率 1 で誤り確率は0

5

まとめ
線形回帰の学習、およびその帰結として、ガウス型

Bayesian ネットワークの学習に関して、Hannan-Quinnの命題が真であることを証明した。そもそも、ARMA でしか成立していなかったが、条件付確率 (Suzuki, 2006)の場合に引き続いて、本論文によって、線形回帰の場合でも解決された。長年未解決であり、喜んでいただけるものと思われる。
過学習の誤り確率の計算で、条件付確率および線形回帰のいずれにおいても、経験的エントロピーの差がパラメータ数の差を自由度にもつ χ2 分布にしたがうことがわかった。そして、ともにその性質を利用して、Hannan-Quinn の命題が真となることが証明された。では、条件付確率、線形回帰を含むどのような一般的な条件でHannan-Quinn の命題が真となるのであろうか。大変興味深い。

参考文献[1] Akaike, H. (1974): ”A New Look at the Statistical Model Identiﬁcation,” I.E.E.E. Transactions on
Automatic Control, AC 19, 716-723[2] Schwarz, G. (1978): ”Estimating the Dimension ofa Model,” Annals of Statistics, 6, 461-464.
[3] Hannan, E. J., and B. G. Quinn (1979): ”The Determination of the Order of an Autoregression,”
Journal of the Royal Statistical Society, B, 41, 190195.
[4] J. Suzuki (2006): On Strong Consistency of Model
Selection in Classiﬁcation. IEEE Transactions on
Information Theory 52(11): 4767-4774[5] Rao, C.R., Wu, Y., (1989): A strongly consistentprocedure for model selection in a regression problem. Biometrika 76, 369-374[6] Chatterjee, S. and Hadi, A. S. (1988), Sensitivity
Analysis In Linear Regression, New York: John
Wiley & Sons.
[7] 鈴木譲 (2009): ベイジアンネットワーク入門 (培風館)