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

線形時間異種混合モデル選択のための期待情報量基準最小化法

Linear Time Model Selection for Mixture of Heterogeneous
Components via Expectation Minimization of Information Criteria
藤巻遼平∗

森永聡

門馬道也

青木健児

中田貴之

Ryohei Fujimaki

Satoshi Morinaga

Michinari Momma

Kenji Aoki

Takayuki Nakata

Abstract: Our main contribution is to propose a novel model selection methodology, expectation minimization of information criterion (EMIC). EMIC makes a signiﬁcant impact
on the combinatorial scalability issue pertaining to the model selection for mixture models
having types of components. A goal of such problems is to optimize types of components aswell as the number of components. One key idea in EMIC is to iterate calculations of theposterior of latent variables and minimization of expected value of information criterion ofboth observed data and latent variables. This enables EMIC to compute the optimal modelin linear time with respect to both the number of components and the number of available
types of components despite the fact that the number of model candidates exponentially
increases with the numbers. We prove that EMIC is compliant with some information
criteria and enjoys their statistical beneﬁts.
Keywords: Mixture of Heterogeneous Components, Expectation Minimization of Information Criteria

1

はじめに
複雑多様なデータ分析へのニーズの高まりと共に，異種多様な分布を混合したモデルクラス (我々は、このモデルを異種混合モデルと呼ぶ) の重要性が高まっている．
異種混合モデルのクラスには，正規分布と指数分布の混
合分布のような比較的単純なモデルから，異なる内部次元を持つ混合因子分析モデル [6]，異なる次数を持つ混合多項曲線モデル，異なる属性を利用する混合判別モデルといった複雑なモデルまで含まれ，このような複雑な分布は実応用の様々な場面で遭遇する．
異種混合モデル (の一部) を推定するための素朴な方法としては、混合正規分布によって近似をする事が挙げられる。これは、混合正規分布がコンポーネント数の増加と共に任意の精度で分布を近似可能であるという点で根拠を持つ [14]。一方で、異種混合モデルを精度よく近似するために多数のコンポーネントを利用した場合にはポーネント数を少なくすると近似が粗くなるという問題がある。
本稿では，異種のコンポーネントを混合させて，異種混合モデルを「真っ向から」学習するための，一般的な枠組みを確立する事を目的とする．異種のコンポーネン
トを混合させるためには，事前に適切なコンポーネント
数と各コンポーネントの種類を決める必要がある．しかしながら，実応用においてこれらを事前に知る事は不可能であり，データを人手で分析してコンポーネントを一つずつ設定する事も非現実的である．したがって，異種混合モデルに関する学習問題では，データからコンポー
ネントの数，種類およびそのパラメータを推定する事が重要となる．我々は，この問題を “異種混合モデル選択”，可能なコンポーネントの種類を “コンポーネント候補” と呼ぶ事にする．
異種混合モデル選択問題の重要な課題として，モデルの解釈が困難となり、解釈性を高めるためにコン(A) 任意のモデルをコンポーネント候補として扱う，∗ NEC 共通基盤ソフトウェア研究所, 211-8666 神奈川県川崎市中原区下沼部 1753, e-mail r-fujimaki@bx.jp.nec.com, URL
http://www.nec.co.jp/rd/datamining/
NEC Common Platform Software Research Laboratoies, 1753,
Shimonumabe, Nakahara-ku, Kawasaki-shi, Kanagawa(B) コンポーネント数およびコンポーネント候補数に対して線形の計算量を保証する，という 2 点が挙げられる．(A) は，このクラスの問題を

一般に広く解決するために必要な課題である．また，モデルの候補数はコンポーネント候補の組み合わせ数によって決まり膨大となるため，(B) は異種混合モデル選
択をコンポーネント候補の組み合わせ数に依存せずに，現実的な時間で解決するために必要となる課題である．

(A) を解決するための一般的な方法として，情報量基準 (最小記述長 (MDL) [10]，赤池情報量基準 (AIC) [1]，ベイズ情報量基準 (BIC) [13] など) を目的関数としてモデル空間を探索する方法が挙げられる．しかし，モデルの候補数は，コンポーネント候補の組み合わせの数に依存し、全探索はもちろんパタン探索 [9] などの探索アル
ゴリズムを利用したとしても (B) の問題を解決する困難である．より洗練された方法として，変分ベイズ法に基づく手法 [6] や階層的クラスタリングタイプの手法 [8]

数学的準備

2

| ◦ | は，集合 ◦ の要素数，P (•; ⋆) は ⋆ によってパラメトライズされた • の確率密度 (質量) 関数，ˆ⋆は⋆ の
最尤推定量を表すとする．
．

2.1

パラメトリックな確率分布族 Vj = {P (X; ϕVj )|ϕVj ∈つだけでなく分布系が異なってもよい．また，コンポー
ネント候補を，S = {Vj |j = 1, . . . , |S|} と定義する．
本稿では，異種混合モデルを S に対する混合分布，
C{}∑
P (X; θ) =πc P (X; ϕSc c ) ,ラスに制限があり，線形の計算量を保証する事はできて本稿は，異種混合モデル選択に対して，期待情報量基
準最小化法 (Expectation Minimization of Information

Criterion; EMIC) を提案する．EMIC は，隠れ変数を含むモデルのパラメータ推定として一般的な EM アル
ゴリズム [5] をモデル選択へ拡張した方法で，隠れ変数の事後分布に関する完全データ1 の情報量基準の期待値を繰り返し最小化する．通常の EM アルゴリズムとの最大の相違点は，M ステップにおいて，各コンポーネントのパラメータだけでなく，各コンポーネントの種類そのVVΦj } を考える．ただし，ϕVj = (ϕ1 j , . . . , ϕJVj ) は Vjjに対応するパラメータ集合 Φj の要素とする．ここで，P (X; ϕVj ) は j に対して異なるパラメータ次元 JVj を持が提案されているが，双方ともコンポーネントの分布ク
いない．

異種混合モデル(1)

c=1と定義し2 ，H = {Hi |i = 1, . . . , |H|} と表記する3 ．また，H をモデル候補と呼ぶ．(1) では，C はコンポーネント数，Sc ∈ S (c = 1, . . . , C) はコンポーネント c の種類を表し，H の要素ごとに異なる．またパラメータを，

π = (π1 , . . . , πC )，ϕ = (ϕS1 1 , . . . , ϕSCC )，θ = {π, ϕ} と
表記する．

2.2

情報量基準

一般に，情報量基準は観測データ xN = x1 , . . . , xN

ものを更新可能な事である．これによって，コンポーネおよび H ∈ H に対して，(負の) 対数尤度4 とモデルのント数とコンポーネント候補数に対して線形時間の異種

複雑性のトレードオフとして，混合モデル選択が実現される (すなわち課題 (B) が解決される)．また，第 3.4 節で，MDL/BIC, AIC に対して，
期待情報量基準の繰り返し最小化が，元の情報量基準のIC(xN ; H) = −

N
∑

H

H

− log P (xn ; θ̂ ) + ℓ(θ̂ ),

(2)

n=1
H

値が単調に減少させることを示す．これは，EMIC によと表現される5 ．ただし，ℓ(θ̂ ) はモデルの複雑性を表る期待情報量基準の探索が，元の情報量基準に対する最す．例えば，MDL/BIC6 ，AIC は，適解を探索可能である事を意味している．MDL/BIC，

AIC などの情報量基準は，任意の分布をコンポーネン
ト候補として扱う事が可能なため，これによって EMIC
が課題 (A) を解決可能である事を示す．
本稿は次節以降，以下のように構成される．まず，第2 節で異種混合モデルの定義を与え，提案手法の土台となる情報量基準に関する説明を行なう．第 3 節で，提案手法の定式化，最適化，理論的正当性などを説明し，第 4 節で人工データおよび UCI データ [2] を利用して，提案手法が (A) および (B) を解決可能である事を実証する．

1 観測データとそれに対応する隠れ変数．

M DL/BIC(xN ; H) =

N
∑
n=1

H

− log P (xn ; θ̂ )+JH
log N,
22 階層隠れ変数モデル [3] や階層混合エキスパートモデル [7] など，

より複雑な混合分布に関しては今後の課題とする．
3 混同の恐れがない場合には，表記の簡単化のため „ H の上付き文
字 H は省略する．
4 拡張型確率的コンプレキシティ [15] のように対数損失 (尤度) 以外の適合度を利用する基準，予測的確率的コンプレキシティ [11] や交差検定のように，データとモデルの複雑性が加算的な形の分解されていな基準など，より広いクラスのモデル適合度を利用する基準に対する議論は今後の課題とする．
5 交差検定法によるモデル選択は，一般には異なる形式となるため本稿の議論は必ずしも当てはまらない．
6 このタイプの MDL は crude MDL と呼ばれ，近似精度がO(log N ) となりうる事が知られている．最尤符号化を利用して近似精度が O(1) である reﬁned MDL が Rissanen [12] によって提案されている．本稿の議論は，直接 reﬁned MDL へも適用可能である
が，簡単のため crude MDL に対して議論を行なう．

AIC(xN ; H) = 2

N∑

アルゴリズムと同様に，隠れ変数の事後分布，

H− log P (xn ; θ̂ ) + 2JH ,n=1

P (Z|x, θ, H) ∝と表現される．一般的に，これらの情報量基準を利用してモデル選択を行なう場合，各モデル候補に対して EM
アルゴリズム [5] によって最尤推定量 θ̂Hを計算し，次に情報量基準を最小化するモデルを選択する．しかし，異種混合モデル選択では，コンポーネント数とコンポー
ネント候補数と共に，モデル候補の数 |H| が膨大となる点に問題がある．

に対する，IC(xN , z N ; H) の期待値 EZ [IC(xN , z N ; H)]
を最適化することにする．完全変数の期待情報量基準を目的関数とする事の正当性は，第 3.4 節で説明する．

EZ [•] は，• の P (Z|x, θ, H) に関する期待値を表すとすると，EZ [IC(xN , z N ; H)] は，−

まず，X に対する隠れ変数を Z = (Z1 , . . . , ZC ) を考

N ∑
C
∑

N ∑
C
∑

EZ [znc ] log π̂c + EZ

れた場合に 1 ，それ以外で 0 をとる．また，xn に対応
する隠れ変数の値を z N = z 1 , . . . , z N とする．一般に，(X, Z) の組は完全変数，(xN , z N ) は完全データと呼ばれる．
完全変数に関する同時分布 P (X, Z|ϕ) は，P (X|Z, ϕ)
および P (Z|π) に分解する事が可能である．ここで，P (X|Z, ϕ) は隠れ変数 Z が条件として与えられている
c
ため，P (X|Zc = 1, ϕ) = P (X; ϕSc ) である．したがって，完全データの情報量基準 IC(xN , z N ; H) は，IC(x , z ; H) = −
N

N ∑
C
∑

n=1 c=1N ∑C∑
n=1 c=1

znc log π̂c +

c=1

(6)
と計算される．(6) と通常の EM アルゴリズムの期待対数尤度との違いは，モデルの複雑性の隠れ変数の事後分布に対する期待値を含んでいる点で，これによって最適化の各ステップでコンポーネントの種類を最適化する事が可能となる．

3.2

最適化アルゴリズム

EMIC は，各コンポーネント数 C に対して，以下でンポーネント数 C ∗ を情報量基準によって選択する．以下では，(t) は EM ステップの t 回目の繰り返しであるScℓ(ϕ̂c ) + ℓ(π̂)

(3)

c=1

と表す事が可能である．右辺の]cの種類 Sc およびパラメータ ϕS
c を最適化し，最適なコSc
znc log P (xn ; ϕ̂c )

C
∑

Sc

ℓ(ϕ̂c ) + ℓ(π̂)

説明する EM ステップを繰り返す事でコンポーネント

n=1 c=1−

Sc

EZ [znc ] log P (xn ; ϕ̂c )C[∑

える．Zc は X が c 番目のコンポーネントから生成さN(5)n=1 c=1

完全データの期待情報量基準

3.1

)Z c
πc P (x; ϕSc c ).

n=1 c=1

EZ [IC(xN , z N ; H)] = −期待情報量基準最小化

3

N ∏
C (
∏

事を表すとし，混乱の恐れがない場合には省略する場合
がある．

∑C

Sc
c=1 ℓ(ϕ̂c ) + ℓ(π̂) は，完全変数に対する同時分布のモデル複雑性であり，MDL/BIC

3.2.1

E ステップE ステップでは，隠れ変数の事後分布 P (Z|x, θ, H) を計算する．具体的には，M ステップで必要となる EZ [znc ]∑CScおよび EZ [ c=1 ℓ(ϕ̂c ) + ℓ(π̂)] の期待値計算を行なう．
for MDL/BIC
まず，EZ [znc ] に関しては EM アルゴリズムと同様に，
for AIC
(t−1)
(t−1)
(4)
πc
)
P (xn ; ϕcSc
(t)
.
(7)
EZ [znc ] = ∑
(t−1)
(t−1)
C
と計算される．
P (xn ; ϕcSc)
c=1 πc(2) に対する (3) の重要な利点は，目的関数が各コンと計算される．z n はお互いに独立であるため，この処
ポーネントに対して分離されているため，各コンポーネ
理にかかる計算量は O(N ) である．
ントの種類やパラメータを独立に最適化可能な点にある．
∑C
Sc
次に，EZ [ c=1 ℓ(ϕ̂c )+ℓ(π̂)] に関しては，基準によっ
これによって，コンポーネント候補数およびコンポーネて具体的な計算方法が異なるため，ここでは MDL/BIC
ント数に対して線形の計算オーダーで，異種混合モデル
および AIC の場合を説明する．MDL/BIC に関しては，
選択を実行する事が可能である．
∑N(t)
EZ [log( n=1 znc )] を直接計算するためには，z1c , . . . , zN c
実際には，隠れ変数の値は観測する事ができないため，に関する 2N の組み合わせを考える必要があるため，指IC(xN , z N ; H) を計算する事ができない．そこで，EM数時間の計算量が必要となる．これでは第 1 節で述べたおよび AIC に対しては，
∑()
 C JSc log ∑N znc + C−1 log N
n=1
c=1 2
2
∑C J + (C − 1)
c=1 Sc(B) の課題を解決できたとしても，高速な異種混合モデ
ル選択が実現できない事となる．そこで，第 3.3 節で N

性 (4) が隠れ変数に依存しないため，特別な期待値の計

Algorithm 1 Expectation Minimization of Information Criterion
1: Input: xN , S and Cmax
2: Initialization : H̄ ← NULL and IC ← ∞3: for C = 1, . . . , Cmax do

算は必要ない．

4:に対する線形オーダーかつ任意精度で近似が可能なアルゴリズムを説明する．AIC に関しては，モデルの複雑

t ← 1 and initialize H (t) and θ̂
repeat5:

3.2.2

M ステップ7:8:{
argmin −c
Sc ,ϕSc},11:

Update:

(8)

12:

(t)

13:

なる最適化問題を解くことによって，各コンポーネント

15:

また，混合比に関しては，

16:

,

(t)

(t)

{C, S1 , . . . , SC } and(t)

end if
17: end for
18: Output: the optimal model H̄ and parameter θ̄

∑N

N

←

if IC(xN ; H (t) ) < IC then(t)
IC ← IC(xN ; H (t) ), H̄ ← H (t) and θ̄ ← θ̂ .

14:c
ごとに Sc および ϕS
c を最適化することが可能である．

H (t)θ̂ ← {π̂ (t) , ϕ̂ }.
Evaluate IC(xN ; H (t) ) and convergence.
until IC(xN ; H (t) ) converges

n=1

(t)
n=1 EZ [znc ]

(t)

10:

(t)
EZ [znc ] log P (xn ; ϕSc c ) + ℓ(ϕ̂Sc c )π̂c(t) =(t)(t)

Calculate Sc , ϕ̂Sc , π̂c by (8) and (9).
end for9:関数がコンポーネント毎に分解されているため，N∑.

t ← t + 1.
∑C
Sc
Evaluate EZ [znc ] and EZ [ c=1 ℓ(ϕ̂c )+ℓ(π̂)].
for c = 1, . . . , C do

6:

M ステップでは，EZ [IC(xN , z N ; H)] を最小化するコ
ンポーネントの種類およびパラメータを推定する．EMIC
では，完全変数に対する情報量基準を考える事で，目的

(t)

(9)

3.3

と推定される．

EMIC のモデル選択の鍵は，各 EM ステップにおいcて，コンポーネントごとに Sc および ϕS
c の推定が可能

MDL/BIC に関する高速近似アルゴリ
ズムな点である．これによって，コンポーネントの種類に関第 3.2.1 節で説明したように，MDL/BIC の E ステップ∑N(t)において，素朴に EZ [log( n=1 znc )] を計算しようとすする全ての組み合わせに関して情報量基準を計算する事

ると O(2N ) の計算量が必要となる．これは，場合によっを回避し，コンポーネント候補数の線形オーダーでの異てはコンポーネント候補の組み合わせを考慮する以上の

種混合モデル選択が可能となっている．
N

(t−1)

EM ステップの収束は，元の情報量基準 IC(x ; H
IC(xN ; H (t) ) に対して判定を行う．通常の EM アルゴ(t)
リズムでは，しばしばパラメータの値 θ̂ に対して収束判定が行われるが，EMIC では各ステップで θ̂が変動するため θ̂

(t)

(t)

計算量が必要となる．そこで，本節では，任意の近似精度∑N(t))− かつ N の線形オーダーの計算量で EZ [log( n=1 znc )]の次元に対して収束判定は難しい点で注を近似する方法を説明する．

∑N
まず，µnc = EZ [znc ] および µc = n=1 µnc とする．
∑N
∑N
(t)
EZ [log( n=1 znc )] を n=1 znc に関して µc の周りでテイラー展開し，M 次より大きい項を無視すると，意が必要である．

Algorithm 1 に EMIC の疑似コードを示す．各コン
ポーネント数 C に対して，コンポーネント種類とパラメータを EM ステップによって最適化する．最適なコ
ンポーネント数 IC は IC(xN ; H) の最小化によって選択される．Algorithm 1 では，コンポーネント数を無限大まで探索する事ができないため，入力として最大のコンポーネント数 Cmax が必要となる．この問題は，

Ghahramani ら [6] の手法のようにコンポーネントの分
割併合といった経験則を利用することで解決する事が可能と考えられる．

EZ [log

M
N
[( ∑
∑
)
)m ]
znc ] ≈
bm EZ
znc
,

N
(∑
n=1

m=0

(10)

n=1

を得る．ここで，bm は適当な係数とする．M は近似の精度を制御する定数である．
k(10) を高速に計算する鍵は，znc に関する zic= zic (k ≥1) および EZ [zn1 c zn2 c ] = µn1 c µn2 c (n1 ̸= n2 ) なる性質を利用する事である．この性質を利用すると，任意の∑Nm に対して，EZ [( n=1 znc )m ] が O(N ) で計算できる．
例として，m = 2 に関しては，

EZ [(

N
∑

n=1

と計算される．

znc )2 ] = µ2c + µc −

N
∑
i=1

µ2ic

(11)

EMIC の正当性

3.4が成立する。Jensen の不等式より、

本節では，MDL および AIC に対して，完全データに

(t+1)

EZ

(t+1)

[log P (z N |xN ; θ (t+1) ] ≤ EZ

[log P (z N |xN ; θ (t) ]対する期待情報量基準の最小化処理によって計算される(15)最適解が，元の情報量基準に関する局所最適解となる事が成立するため8 、両辺を (14) の両辺に加えて、ℓ(θ̂ ) =∑CSc
EZ [ c=1 ℓ(ϕ̂c ) + ℓ(π̂)] を考慮すると、を証明する．BIC に関しては，漸近的には MDL と同じH形式となるため，MDL に関する証明によって正当性をIC(xN ; H (t+1) ) ≤ IC(xN ; H (t) )示す．なお，各証明は紙面の都合上、骨子のみ記述する。
まず，MDL に関して以下の定理を与える．

(16)となる事がわかる．2

定理 1 EMIC において MDL を情報量基準として利用
した場合，データ数 N が大きい場合，第 3.2 節の EM

H

定理 2 によって、AIC を含む ℓ(θ̂ ) = EZ [∑CSc
c=1 ℓ(ϕ̂c )+証明 1 MDL のモデル複雑性 JH /2 log N は，パラメーℓ(π̂)] を満たす情報量基準のクラスに対して，EMIC における IC(xN ; H) の単調減少性が証明された．
定理 1 および定理 2 より，MDL/BIC，AIC に関しタ θ H を記述するために必要な符号長という意味を持つては，適当な正則条件の元で，EMIC の最適化処理にが，これはクラフトの不等式 [4] を満たし，パラメータ

よって計算されるモデルおよびパラメータ (H (t) , θ̂ステップによって，M DL(xN ; H) が単調に減少する．

(t)

)

N

θ H に関する確率分布7 (の対数尤度) と解釈する事が可能

が，IC(x ; H) の停留点へ収束する事がわかる．これである．よって，θ を確率変数とみなし M DL(xN ; H) =らの定理によって，EMIC が，対応する情報量基準に関− log P (x , θ̂)，M DL(x , z ; H) = − log P (x , z , θ̂) する最適化という意味において正当性を持つことが示された．
と解釈する事が可能である．
N

N

N

N

N

したがって，N

M DL(x ; H

(t)

(t)
) = EZ

[

)]
− log
.
(t)
P (z N |xN , θ̂ )(12)
P (xN , z N , θ̂

(t)

(t)

が成立し，EZ [M DL(xN , z N ; H (t) )] の最適性およびJensen の不等式 [4] を考慮すると，
M DL(xN ; H (t+1) ) ≤ M DL(xN ; H (t) )

(13)

実験と考察

4

本稿では，2 つの異種混合モデルに関して、EMIC の評価を実施した．1 つ目のモデルは，異なる独立性を持
つ 3 次元正規分布9 の混合モデルで GAUSS と表記する．

2 つ目のモデルは，異なる次数を持つ多項曲線の混合モ
デルで POLY と表記する．また，以下の結果は全て 10回の実験の平均 (または 10-fold 交差検定) の結果であり，全ての手法が 10 個の異なる初期値に対して最適化を実となる事がわかる．2

施し，最適解を探索した．また，各実験における真のモ定理 1 では，MDL のモデル複雑性が漸近的にパラメータに関する確率値の対数と等価となる事を利用しているため，小さい N に対しては必ずしも成立しない．しかし，デルを H ∗ ，真のコンポーネント数を C ∗ と表記する．

4.1

人工データに対する性能評価

本稿での実験では単調性が常に成立していたため，実用

まず，人工データを利用して EMIC の計算速度および上はある程度小さな N までは定理 1 が成立し，EMIC

モデル選択の性能に関して評価を行った．本実験では，によって正しく MDL/BIC の最小化が実施できる．

真のモデルに関する一致性を評価するために，MDL を基準として利用した10 ．

次に，AIC に関して以下の定理を与える．

∑C
H
Sc
定理 2 EMIC において ℓ(θ̂ ) = EZ [ c=1 ℓ(ϕ̂c ) +

4.1.1

比較手法

によって，IC(x ; H) が単調に減少する．

MDL を利用した EMIC (EMICM DL ) に関する比較手法として，全モデル候補に対して 1 回ずつ探索を行う

証明 2 まず、EMIC の最適化の性質より、

P(t)
8 E (t+1) [•] =) である点に注意。
Z •P (Z|x, „Z
9 コンポーネントの候補は独立性の違いで 8 種類。3 次元と限定しℓ(π̂)] を満たす情報量基準は，第 3.2 節の EM ステップ
N

(t+1)

EZ

(t+1)

[IC(xN , z N ; θ (t+1) ] ≤ EZ

[IC(xN , z N ; θ (t) ],(14)

7 正確には劣確率分布であるが，確率分布とみなしても議論に差はないため，簡単のため確率分布として議論をする．

た理由は、高次元とした場合に比較手法の計算量が膨大となり実験が難しいため。
10 混合モデルは，特異モデルであるため MDL/BIC、AIC の導出
における漸近展開が発散してしまい，各基準が正しく機能しない場合がある事が知られている．しかし，実用上で真のモデルへの一致性能を評価する事は意味がある．なお，AIC は真のモデルへの一致性はないため，本実験では MDL/BIC を採用している．

FULLM DL と，パタン探索 [9] によってモデル候補を探索する PATM DL を評価した．各手法ともパラメータ推定には EM アルゴリズムを用いた．なお，EM アルゴリ
ズムによるパラメータ推定は，大域的な最適解を得ることができないため，EMICM DL および PATM DL の推定精度が FULLM DL よりも良い可能性がある (EMICM DL
および PATM DL は、同じモデルを複数回探索する可能性があるため)．

4.1.2

評価基準

モデル選択の性能を評価するために，1) 情報量基準の値 M DL(xN ; H̄)，2) H̄ = H ∗ となった割合 (RH )，3) C̄ = C ∗ となった割合 (RC )，4) 最適化の CPU 時
間，を評価基準とした．定性的には，1) は目的関数に対する最適解の探索精度，2) はコンポーネント数およびコンポーネントの種類まで含めたモデル選択の精度，3)はコンポーネント数に関するモデル選択の精度を表す．

4.1.3

真のモデルとデータの生成

GAUSS の真のモデルの各コンポーネントは，平均ベクトルを [−5, 5] より，共分散行列の要素を [0, 1] よりランダムに生成し，各次元の独立性もランダムに決定した．
GAUSS に関しては真のコンポーネント数を C ∗ = 5 とし，探索するコンポーネントの最大数 Cmax を変化させ

図 1: POLY の真のモデルに関する 8 つコンポーネント．
1
2
3
4
5
⃝:y
= 10, ⃝:y= −10, ⃝:y= 2x, ⃝:y= −2x, ⃝:y=6
72x2 − 3, ⃝:y= −2x2 + 3, ⃝:y= 0.5x3 − 1.5x2 − 2x + 4,8⃝:y
= −0.5x3 + 1.5x2 + 2x − 4.

線形時間の計算量で異種混合モデル選択を実施できる事を裏付ける結果である．さらに，真のモデルの推定性能
では，RH および RC の両方で，EMIC は他の手法を凌駕している．これは，同一基準を利用した通常の EM ア
ルゴリズムに基づく手法と比較して，EMIC の探索が局所解に対してロバストにモデルを推定可能である事を示た場合の性能の変化を評価した．

している．EMIC はパラメータとモデルの空間を同時に

POLY の真のモデルの各コンポーネントは，図 1 に示される多項曲線からランダムに 4 つを選択した11 ．デー

探索するため，パラメータ空間で性質の悪い局所解に落タは各曲線に対して平均が 0 の正規分布にしたがうノ

索を継続可能であるため，よりよい解が得られたと考えイズを加えて生成し，分散は [1, 4] でランダムに決定しられる．

ちた場合 (あるいは落ちる前) に，モデルを変更して探た．POLY に関しては、Cmax = 5 と固定し，探索する

図 3，POLY に関する結果を示す．CPU 時間に関して次数の最大値 Dmax を変動させた場合の性能の変化を評

は，Dmax の増加とともに，PATM DL および FULLM DL

価した．

では探索に必要な時間が急速に増加するのに対して，

なお，両方のモデルで混合比はランダムに設定した．
また，各結果ともデータ数は N = 500 とした．また，最適化に関しては EMIC では情報量基準に対して，EM

EMIC では線形に増加している事が確認できる (左上図)．これは，コンポーネントの候補数12 の増加に対して，

アルゴリズムに関しては対数尤度の値に対して 10−6 のEMIC が線形時間の計算量で異種混合モデル選択を実施できる事を裏付ける結果である．また，GAUSS の場合と閾値を設けて最適化を打ち切っている．

同様に，IC(xN ; H̄)，RH ，RC に関しても，EMICM DL

4.1.4

結果と考察

図 2 に，GAUSS に関する結果を示す．Cmax の増加とともに，PATM DL および FULLM DL の CPU 時間が急速に増加するのに対して，EMIC では線形で CPU 時間が増加している事が確認できる (左上図)．これは，探索するコンポーネントの最大数 Cmax に対して EMIC が11 多項曲線の次数と係数をランダムとした実験では，複数の曲線が重なってしまいモデル選択がほぼ不可能なケースが多く発生したため，本稿の実験では評価のために図 1 に示される曲線を真のコンポーネン
トとした．

がその他の手法よりも優れた性能を発揮している事が確認できる．
次に，EMIC の EM ステップを詳しく分析するために，

POLY に関して，各ステップにおけるモデルの推定結果の例を，図 4 に示す．t は EM ステップの回数，Fi は i 番
目のコンポーネントに対応する曲線，Di は Fi の次数をそれぞれ表している．t = 1 (左上) は，隠れ変数をランダムに初期化した際に推定されたコンポーネントで，真12 0 次まで合わせて D

max + 1．

図2:GAUSS に 対 す る EMICM DL ，PATM DL ，
FULLM DL のモデル選択性能の比較．

図 4: EMIC における POLY モデル推定プロセス．
う．なお，この例では t = 20 で最適化が収束し，推定されたモデルは真のモデルと一致した．

4.2

UCI データに対する性能評価

次に，UCI データセット [2] の ecoli，housing，iris，

wine，yeast，vowel context に関して，各手法の比較実験を実施した．各データについて，真のモデルはわからないため，評価指標としては交差検定尤度13 と CPU 時間を行った．また，本評価では EMIC，パタン探索，全探索の全てに対して情報量基準として MDL および AICの両者の比較を行った．実験では，交差検定の各繰り返
しにおいて，ランダムに 3 つの属性を選択し，3 次元の

GAUSS モデルを学習させた．属性を 3 つと限定したの
図

3:

POLY に 対 す る EMICM DL ，PATM DL ，

FULLM DL のモデル選択性能の比較．

は，それ以上の場合にはモデル候補の数が増大し，比較手法の計算が終了しなかったためである．同様に，比較手法の計算コストの問題からコンポーネントの最大数は

t = 3，t = 10，t = 20 と進むとともに，推定された曲線

Cmax = 5 とした．
表 1 に，比較結果を示す．交差検定尤度に関してはが徐々にデータの適合していく様子が確認できる．ここ

各手法とも大きな差はなく，データによって最も性能がで，各コンポーネントに対する最適な次数 (D1 ∼ D4 )よかった手法が異なり、予測精度の意味でよいモデルおが最適化とともに頻繁に変動している点は注目に値す

よびパラメータの探索性能に関しては，手法による違る．変動の様子も，真のコンポーネントへ次数が単調にいを明確に観察する事はできなかった．一方で，推定に近づくもの (例えば F1 ) や，真のコンポーネントよりもかかった CPU 時間をみると，MDL および AIC 共に，

複雑なモデルを推定してから真のコンポーネントへ収束

EMIC は他の手法と比較して圧倒的に短い時間で解を探索できている事が確認できる．この結果は，真のモデルの曲線を全く再現できていない．EMIC による最適化がするもの (例えば F4 の t = 10) など，コンポーネントによってモデル空間の探索の様相が異なる点で興味深い．
∑N
これは，期待されるデータ数 n=1 EZ [znc ] が小さい場がわからない実応用においても，EMIC によって全探索

合には単純なモデルが，大きい場合には複雑なモデルが能である事を示している．

などと同程度の精度かつ高速に異種混合モデルを推定可選ばれやすいため，各ステップにおける隠れ変数の事後分布の推定 (E ステップ) とコンポーネントごとのモデ
ル選択 (M ステップ) が密接に関連しているためであろ

13 交差検定に関するテストデータに対して計算された尤度．

表 1: UCI データに関する交差検定尤度と CPU 時間 (尤度/CPU 時間) の比較

5

ecoli

housing

iris

wine

yeast

vowel context

EMICM DL70.6/39.8-219.6/25.6-46.5/27.8-73.3/35.5

558.6/85.5-553.8/69.4

PATM DL

72.3/723.0-239.1/346.7-47.7/408.2-70.6/691.3

556.2/1252.9-550.2/800.7

FULLM DL72.3/856.2-239.3/533.5-49.9/612.7-69.2/780.9

556.9/1630.9-555.2/1317.5

EMICAIC70.1/35.5-228.6/23.5-52.3/23.4-71.7/30.0

557.8/81.0-548.8/64.0

PATAIC67.4/607.6-250.1/342.9-51.7/429.4-74.8/526.7

558.8/1158.4-553.1/1099.4

FULLAIC

65.0/855.9-239.2/538.3-50.8/610.6-75.1/779.2

558.6/1635.8-550.6/1313.2

おわりに
本稿では，複数の異種多様なモデルが混合する，異種混合モデルに対するモデル選択問題に対する一般的な枠組みとして，期待情報量基準最小化法 (EMIC) を提案した．EMIC は，任意のコンポーネントを扱う事が可能であり，コンポーネント数とコンポーネント候補数の双方に対して線形時間でモデルを推定が可能，という二つの利点を持つ．本稿では，一部の情報量基準に対してEMIC の理論的な正当性を証明するとともに，実証実験
によってその有効性を確認した．
本稿の中心として議論した MDL/BIC や AIC を含む
漸近展開から導出される情報量基準は，混合分布のような特異モデルに対して，実用上は重要であるが基準としての理論的正当性は失ってしまう．今後，漸近展開に基
づかない基準14 など，その他のモデル選択基準に関しても EMIC を拡張し議論を発展させる必要がある．この際に，特に重要なのは，期待情報量基準の最小化プロセスが，元の情報量基準の最小化につながるかという点であろう．
また，本稿では EMIC の基礎的な性質を理解するために，比較的単純な異種混合モデルに対して実証実験を実施したが，より複雑な異種混合モデルに対する評価が今後の重要な課題として挙げられる．

参考文献

action on Pattern Analysis and Machine Intelligence,20(3):281–293, 1998.
[4] T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley-Interscience, 1991.
[5] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from imcomplete data via the em
algorithm. Journal of the Royal Statistical Society,B39(1):1–38, 1977.
[6] Z. Ghahramani and M. J. Beal. Variational inference
for bayesian mixtures of factor analysers. In In Advances in Neural Information Processing Systems 12,
pages 449–455. MIT Press, 2000.
[7] M. I. Jordan and R. A. Jacobs. Hierarchical mixturesof experts and the EM algorithm. Neural Computation, 6:181–214, 1994.
[8] Y. Ma, H. Derksen, W. Hong, and J. Wright. Segmentation of multivariate mixed data via lossy data coding and compression. IEEE Transactions on PatternAnalysis and Machine Intelligence, 29(9):1546–1562,
2007.
[9] M. Momma and K. P. Bennett. A pattern searchmethod for model selection of support vector regression. In In Proceedings of the SIAM International Conference on Data Mining. SIAM, 2002.
[10] J. Rissanen. Modeling by shortest data description.
Automatica, 14:465–471, 1978.
[11] J. Rissanen. Stochastic Complexity in Statistical Inquiry. World Scientiﬁc Pub Co Inc, 1989.
[12] J. Rissanen. Fisher information and stochastic complexity. IEEE Transaction on Information Theory,42(1):40–47, 1996.

[1] H. Akaike. Information theory and an extension of
the maximum likelihood principle. In B. N. Petrov
and F. Caski, editors, Proceedings of the 2nd International Symposium on Information Theory, pages 267–
281, 1973.

[13] G. Schwarz. Estimating the dimension of a model. The
Annals of Statistics, 6(2):461–464, 1978.

[2] A. Asuncion and D. Newman. UCI machine learning
repository, 2007.

[15] K. Yamanishi. Advances in minimum description
length: Theory and applications. In P. D. Grunwald,
editor, Extended Stochastic Complexity and Its Applications to Learning. The MIT Press, 2005.

[3] C. Bishop and M. Tipping. A hierarchical latentvariable model for data visualization. IEEE Trans14 例えば MDL 基準における予測確率的コンプレキシティ[11] や，
交差検定によるモデル選択基準など。

[14] R. A. Tapia and J. R. Thompson. Nonparametric
Probability Density Estimation. Johns Hopkins Univ.
Press, 1978.