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

Chow-Liu アルゴリズムの一般化と、木の複雑さを考慮した修正版
について
A generalized version of Chow-Liu algorithm for data-mining.
石田 悠∗
Yuu Ishida

1

まえがき

間の Kullback-Leibler 情報量を最小にする木が得られる

確率空間 (Ω, F, µ) を決めれば、F 上で可測な写像 X :Ω → R は確率変数とよばれる。しかしながら、工学的な応用では、X の値域が離散の値をとるとか、その分布関数 FX が絶対連続 (確率密度関数 fX が存在) といった特殊な場合を扱うことが多いようである。たとえば、確率変数 X, Y の相互情報量は、離散の場合

I(X, Y ) :=∑鈴木 譲†
Joe Suzuki∑

PXY (x, y) logx∈X(Ω) y∈Y (Ω)

PXY (x, y)
PX (x)PY (y)(Chow-Liu, 1968)。分布の近似ではなく、学習のように n(j)個の例 {(xi,1 , · · · , xi,N )}n, j = 1, · · · , N
i=1 , xi,j ∈ X

からはじまっても、相対頻度を用いて empirical に相互情報量が定義され、Chow-Liu アルゴリズムが同様に適用される。
しかし、Chow-Liu のオリジナル論文をはじめ、従来は N 個の確率変数が有限個の値をとる場合のみを扱っていた。本論文では、確率空間 (Ω, F, µ) における勝手なN 個の確率変数の場合にどのようになるかを検討する。
その際に、一般的な相互情報量の定義が必要となる。

連続の場合

学習の場合、Kullback-Leibler 情報量最小という基準∫ ∞∫ ∞fXY (x, y)
dxdyfX (x)fY (y)では、尤度 (適合度) 最大という基準で木を選択すること定義される。しかし、一般の確率変数 X, Y についてた場合でも、やはり相互情報量を修正 (2 個の確率変数は、ほとんど議論されていないようである。また、分布の取りうる値の数を考慮) することによって最適解が与間の隔たりを示す Kullback-Leibler 情報量に関しても、えられる (Suzuki, 1993)。しかし、これもやはり、N 個連続とか離散とか特殊な場合についてだけ定義されての確率変数が有限個の値をとることを仮定している。本いる。

論文では、N 個の確率変数が正規分布にしたがう場合

I(X, Y ) :=−∞−∞fXY (x, y) log

本論文では、データマイニングで計算量の低減を目的に使われる、Chow-Liu アルゴリズムの一般化、およびとになる。MDL 原理を適用して、木の複雑さを考慮しにどのように修正できるかを示す。

木の複雑さを考慮したアルゴリズムの修正版 (正規分布2準備版) を提示する。N 個の確率変数 X (1) , · · · , X (N ) の間

2.1

無向グラフの Markov ネットワークを木 (巡回経路をもたないネッU を有限集合、E を E := {{X, Y }∥X, Y ∈ U, X ̸= Y }の部分集合とする。U, E の対 (U, E) を無向グラフと呼トワーク) で近似する問題を考える。
巡回経路を生成しない限り相互情報量を最大にするI(X (i) , X (j) ) を辺として結合していくと、両者の分布の∗ 大阪大学大学院理学研究科, 〒 560-0043 大阪府豊中市待兼山町

1-1, e-mail yawn.ikaryaku@gmail.com
Graduate school of Science School of Science,Osaka University,
Machikaneyamacho1-1.Toyonakashi.Osaka.560-0043† 大阪大学大学院理学研究科, 〒 560-0043 大阪府豊中市待兼山町
1-1, e-mail suzuki@math.sci.osaka-u.ac.jp
Graduate school of Science School of Science,Osaka University,
Machikaneyamacho1-1.Toyonakashi.Osaka.560-0043

ぶ。無向グラフ G = (U, E) について、U を G の頂点集合、その要素を G の頂点と呼ぶ。また E を G の辺集合、その要素を G の辺と呼ぶ。
無向グラフ G に巡回経路が存在しないとき、G は森であるという。また G が森であって連結されているとき、G は木であるという。

2.2

Kullback-Leibler 情報量

B を実数全体 R の Borel 集合体として、写像 X : Ω →Rが
D ∈ B =⇒ {ω ∈ Ω|X(ω) ∈ D} ∈ F(F 上可測) を満足するとき、X は確率空間 (Ω, F, µ) の確率変数という。

2 個の F 上の測度について、ν(A) = 0 =⇒ µ(A) = 0

確率密度関数 fX , fY , fXY が存在する場合、∫ ∞∫ ∞fXY (x, y)
dxdy
I(X, Y ) =fXY (x, y) log
fX (x)fY (y)−∞ −∞となる。

2.3

Chow-Liu アルゴリズムのとき、µ は ν について絶対連続であるといい、µ << ν

n 個の例から推定される確率変数間の条件付独立性を表現する無向グラフを、特に木の範囲で推定する (推とかく。そして、任意の A ∈ F について、µ << ν の定したものを木で近似するとみなしてもよい) ことを∫考える。そのために、分布 PX (1) ,...X (n) (x(1) , ..., x(N ) ),とき、µ(A) =x(1) ∈ X (1) (Ω),...,x(N ) ∈ X (N ) (Ω) をf dν
Aとなる dµdν := f が存在する (Radon-Nikodym の定理)。

∫

このとき、D(µ||ν) :=log(:=dµ)dµdνj∈Nを測度 µ の測度 ν に対する Kullback-Leibler(K-L) 情報量とよぶ。などが容易に導かれる。この性質より K-L 情報量が小さいほど µ は ν に近いと考えられる。X が有限の値をとる (X(Ω) < ∞) とき、P (x) := µX ({x}), x ∈ X(Ω),Q(x) := νX ({x}), x ∈ X(Ω) とおくと、Q(x) = 0 =⇒P (x) = 0 であれば、

x∈X(Ω)(Dendoroid 分布) で近似する問題を考える。ここで、1 ≤λ[j] ≤ j − 1,j ̸= 1,λ[1] = 0, PX (j) |X (0) (·|x(0) ) = Px(j) (·)

補題 1 U := {X (i) |i = 1, ..., N },D(µ||ν) = 0 ⇐⇒ µ = ν

D(P ||Q) =P (x)P (x) log
Q(x)E ⊆ E := {{X (i) , X (j) }|i ̸= j} をそれぞれ頂点集合、辺集合とする無向グラフ G = (U, E) について、G が木であるならば
E = {{X (aj ) , X (aλ[j] ) }|j = 1, ..., N }、1 ≤ λ[j] ≤ j − 1,j ̸= 1,λ[1] = 0, となる (1, ..., N ) の順
列 (a1 , ..., aN ) が存在する。
命題 1 (Chow-Liu) [1]

それぞれの確率密度関数 f, g が存在する場合、g(x)dx =D0 =⇒ f (x)dx = 0 であれば、
∫ ∞
f (x)
dx
D(f ||g) =f (x) log
g(x)
−∞

:=

(PX (1) ,...,X (N ) |P̂X (1) ,...,X (N ) )∑Px(1) ...X (N ) (x(1) , ..., x(N ) )x(1) ∈X (1) (Ω),...,x(N ) ∈X (N ) (Ω)·log ∏となる。
確率空間 (Ω, F, µ) における 2 個の確率変数 X, Y にPx(1) ...X (N ) (x(1) , ..., x(N ) )(aj ) , x(aλ[j] ) )j∈N PX (aj ) |X (aλ[j] ) (xを最小にする (a1 , ..., aN ) および λ[k]、2 ≤ k ≤ N は∑

ついて、X, Y および X, Y の直積が生成する σ-集合体

FX , FY , FXY に対する測度を µX , µY , µXY とかくとき、I(i, j):=

そこで、I(X, Y ) := D(µXY ||µX µY ) を X, Y の相互情報量とよぶ。X, Y が有限の値をとる (X(Ω), Y (Ω) <∞) とき、PX (x) := µX ({x}), x ∈ X(Ω), PY (y) :=µY ({y}), y ∈ Y (Ω) PXY (x, y) := µXY ({x}, {y}), x ∈X(Ω), y ∈ Y (Ω) とおくと、∑∑x∈X(Ω) y∈Y (Ω)

PXY (x, y) log

PXY (x, y)
PX (x)PY (y)PX (i) X (j) ((x(i) , x(j) )x(i) ∈X (i) (Ω),...,x(j) ∈X (j) (Ω)

積 µX µY も FXY に対する測度になる。

I(X, Y ) =|XXとし、(a1 , ..., aN ) は (1, ..., N ) の順列であるとする。

D(µ||ν) ≥ 0∑

P̂X (1) ,...,X (N ) (x(1) , ..., x(N ) )∏(a)
P (aj ) (aλ[j] ) (x(aj ) , x λ[j] )·log

PX (i) X (j) (x(i) , x(j) )PX (i) PX (j)として、重み最大極大木アルゴリズムに

U := {X (i) |i = 1, ..., N }, w(X (i) , X (j) ) := I(X i , X j )を入力として与えることによって得られる。

入力 n 個の例 xn

証明:

D=(PX (1) ,··· ,X (N ) |P̂X (1) ,...,X (N ) )∑PX (1) ...X (N ) (x(1) , ..., x(N ) )x(1) ∈X (1) (Ω),...,x(N ) ∈X (N ) (Ω)·=log ∏PX (1) ...X (N ) (x(1) , ..., x(N ) )(a

出力 H[π](xn ) を最小とする木 T1. E ← {}2. E ̸= {} であるかぎり以下を繰り返す。

)(aj ) , x λ[j] )j∈N PX (aj ) |X (aλ[j] ) (x∑(a)
I(X (aj ) , X λ[j] ) + H(X (1) , · · · , X (N ) )−(a) In (i, j) が最大の {X (i) , X (j) } ∈ E について、
E ← E − {X (i) , X (j) }aλ[j] →aj−N∑(b) (U, E ∪ {X (i) , X (j) }) が巡回経路を持たない
とき、E ← E ∪ {X (i) , X (j) }H(X (i) )(c) T ← (U, E)

i=1

H(X (1) , · · · , X (N ) ):=∑−PX (1) ,··· ,X (N ) (x(1) , · · · , x(N ) ) 例 1 I (i, j) の各値が表１で与えられているときn

X (1) ,··· ,X (N )H(X (i) ) :=·∑

log PX (1) ,··· ,X (N ) (x(1) , · · · , x(N ) )−PX (i) (x(i) ) log PX (i) (x(i) )2. それ以外では、In (1, 3) が最大なので、X (1) , X (3)を結ぶ。

x(i)より D(P ||P̂ ) の最小化は∑aλ[j] →aj I(X(aλj ),X(aλ[j] ))の最大化に等しい。
補題 1 より、これは辺 {X (aj ) , X (aλ[j] ) } に割り当てられた重みの合計を最小にする木を見出す問題となる。

n 個の例 xn = {x1 , x2 , ...xn },∏Nxi ∈ X(Ω) = j=1 X (j) (Ω),i = 1, ..., n からその条件付独立性を表現する無向グラフを木の範囲で推定をすることを考える。そして、命題１の I(i, j) を∑In (i, j) :=ci,j [x, y] logx∈X (i) ,y∈X (j)1. In (1, 2) が最大なので、最初に X (1) , X (2) を結ぶ。

3. それ以外では、In (2, 3) が最大だが、X (2) , X (3)を結ぶと巡回経路が出来るので、X (2) , X (3) は結ばない。
4. それ以外では、In (1, 4) が最大なので、X (1) , X (4)を結ぶ。
5. 候補となる辺はあるが、これ以上辺を結ぶと巡回経路が出来るのでアルゴリズムを停止する。

ci,j [x, y]≥0
ci [x]cj [y]に置き換えればよい。ただし ci [x],ci,j [x, y] を、それぞれ

表 1: 各 (i,j) に対する相互情報量
i j In (i, j)

x1 , ..., xn における X (i) = x ∈ X (i) (Ω) の頻度、X (i) =x ∈ X (i) (Ω)、X (j) = y ∈ X (j) (Ω) の同時頻度とした。

1212

1310

したがって D(PX (1) ,...,X (n) |P̂X (1) ,...,X (n) ) の最小化は∑H[π](xn ) :=c1,...,N (x(1) , ..., x(N ) )23

8146244342x(i) ∈X (i) (Ω)∏

caλ[j] (x(aλ[j] ) )X (1)
X (3)



X (1)
X (3)


X (1) = x(1) ∈ X (1) (Ω), ..., X (N ) = x(N ) ∈ X (N ) (Ω)
が同時に成立する頻度であるとした。

X (2)
X (4)



X (2)
X (4)
アルゴリズム 1 (相対頻度を用いた Chow-Liu アルゴリズム)

X (1)
X (3)



X (1)
X (3)
@@@(2)
XX (4)
·log

caj ,aλ[j] (x,(aj ) x(aλ[j] ) )の最小化に相当する。ただし c1,...,N (x(1) , ..., x(N ) ) を
X (2)X (4)木の複雑さを考慮した Chow-Liu アルゴリズムの一般化

3. (a) Jn (i, j) が最大の {X (i) , X (j) } ∈ E について、E ← ε − {X (i) , X (j) }前節では n 個の例 xi ∈ X(Ω)、i=1,2,・・・,n から、その条件付独立性を表現する無向グラフを木の範囲で推定(b) (U, E ∪{X (i) , X (j) }) が巡回経路を持たず、かつ Jn (i, j) ≥ 0 のとき、E ← E∪{X (i) , X (j) }することを考えた。

(c) F ← (U, E)

2.4だが上記のアルゴリズムを用いてサンプルからの学習を行う場合、真のグラフが連結でない場合でも出力され

例 2 In (i, j) の各値が表１で与えられているものとし、る木は連結されたものとなる。つまり、興味のある事象

α(1) = 5,α(2) = 2,α(3) = 3, α(4) = 4 であるとする。とは本来無関係の事象までも、一つの木の要素に組み込んでしまうということが起こりうる。それを解決するた

1. 最初に Jn (1, 2) = 8 が最大なので、X (1) , X (2)を結ぶ。

め、以下では木 π の構造の簡潔さまでを考慮してモデリングを行う方法を考える。具体的には H[π](xn ) の最小化ではなくパラメータ数 K[π] を加えた

L[π](xn ) := H[π](xn ) +K[π]log n2と定義した L[π](xn ) を最小化する方法を考える。ここnで H[π](x ) は木 π の例 xnK[π]への適合性、 2 log n は木π の複雑さを表している。[3, pp.106-117]
以下
Jn (i, j) := In (i, j) −(α(i) − 1)(α(j) − 1)log n2

2. それ以外では、Jn (2, 3) = 6 が最大なので、X (2) , X (3)を結ぶ。
3. それ以外では、Jn (1, 3) = 2 が最大だが、X (1) , X (3)を結ぶと巡回経路が出来るので、 は結ばない。

4. それ以外では、In (2, 4) = 1 が最大なので、X (2) , X (4)を結ぶ。

5. Jn < 0 となる辺は連結しない。また連結することによって巡回経路が出来る辺は連結しない。
表 2: 例２
In (i, j) α(i) α(j)とおく。(α(i) := |X (i) (Ω)|) これはエントロピー H[π](xn )ijの減少分だけではなく、辺を加えることによる木の複雑

1212528さの増加分を評価している。

131053223823614654-624424134234-4

補題 2 U := {X (i) |i = 1, ..., N }E ⊆ ε := {{X (i) , X (j) }|i ̸= j} をそれぞれ頂点集合、辺集合とする無向グラフ G = (U, E) について、G が森であるならば、

E = {{X (aj ) , X (aλ[j] ) }|j = 1, ..., N }、0 ≤ λ[j] ≤ j − 1、j = 1, ..., N 、λ[1] = 0 となる (1, ..., N ) の順列 (a1 , ..., aN )が存在する。
木では 1 ≤ λ[j] ≤ j − 1 となるが、森では 0 ≤ λ[j] ≤j − 1 となる。

アルゴリズム 2 (パラメータ数を考慮した修正版)(suzuki,1993)[2]
入力: n 個の例 xn
出力: L[π](xn ) を最小とする森 F

1. E ← {}2. E ̸= {} であるかぎり以下を繰り返す。

Jn (i, j)X (1)
X (3)



X (1)
X (3)



X (2)
X (4)

X (2)
X (4)

X (3)
X (1)

X (1)
X (3)

X (4)
X (2)

X (2)
X (4)


上記のアルゴリズムは n 個の例 xn から L[π](xn ) を最小とする森 F を正しく出力する。

a

証明: 実際 X (aj ) が X λ［j ］ に依存するので、

K［π ］=N∑(aj − 1)(aλ［j］ − 1)
j=0Radon-Nikodym の定理から、
dµ1,··· ,N∏d i→j µj|iとできる。したがって、L[π](x ) の最小化は、

1∑(aj − 1)(aλ［j ］ − 1) log n2 j=0
N−In (aj , aλ［j ］) +j=0

= −∏N
dN µ1,··· ,N
k=1 dµk∏·∏Ni→j dµj|i
k=1 dµk∏ d2 µi,jdN µ1,··· ,N·[]−1∏Ndµdµijdµkk=1=nN∑dN µ∏ 1,··· ,Ni→j dµj|i==i→j,i̸=0N∑1{In (aj , aλ［j ］) − (aj − 1)(aλ［j ］ − 1) log n}2j=0の最小化と同値である。したがって補題 2 よりであるから、Kullback-Leibler 情報量はD(µ1,··· ,N ||∏µj|i )−=i→ja辺 (X (aj ) , X λ［j ］) に割り当てられた重みの合計を最小に∫する森を見出す問題となる。実際、Jn (i, j) < 0 なる i,j+

∑I(X (i) , X (j) )i→j,i̸=0

dN µ1,··· ,Ndµ1,··· ,N log{ ∏N}
k=1 dµkに関しては、X (i) , X (j) が連結されず、(X (i) , X (j) ) を辺∑nとして加えると j=1 Jn (aj , aλ［j ］) が増えないので、辺と書けて、I(X (i) , X (j) ) の大きな順に辺を結ぶことにとして加える操作は行わないことによって最大化がはか

よって Kullback-Leibler 情報量が最小の木を得ることがれる。

出来る。

このアルゴリズムによって最終的に森が木になった場合の順序と Jn (i, j) の順序は一致しないため、アルゴリズ

確率変数が正規分布にしたがう場合の修正版

ム 1 とアルゴリズム 2 では異なる木を出力する場合があ

ここまで確率変数が離散型の場合に限って考えていたでも、|X (j) (Ω)| ≥ 2 なる X (j) が含まれる場合、In (i, j)

3.2

る。（例 1、例 2）Jn (i, j) は、辺 {X (aj ) , X (aλ[j] ) } を結が、以下では前述のアルゴリズム１を正規分布に従う確ぶことによる木表現の例への適合性の増加と、パラメー率変数の条件付独立性の表現に対して実際に適用した場タ数の増加を比べる指標となっている。

合を考える。

離散分布を仮定しない、Chow-Liu

3X (i) ∼ N (0, σ 2 ) の確率密度関数をアルゴリズム
3.1(i) 2
1−xfX (i) (x(i) ) := √e 2σii
2πσii

任意の確率変数の場合への一般化

X (1) , · · · , X (N ) が一般の確率変数の場合においても、Chow-Liu アルゴリズムで Kullback-Leibler 情報量が最とおく。また X (i) , X (j) の同時確率密度を
小になる。

• 一般的な相互情報量の定義(i)

fX (i) X (j) (x , x(j)とおく。ここで Σ =µi,j : X (i) , X (j) の生成する事象の測度∫I(X(i),X(j)) :=dµi,j log

D(µ||ν) :=σji σjj
σ関関数を ρij = √σiiijσjj とすると

d2 µi,jdµi dµj

dµ log(dµ)
dνpX (i) X (j) (x(i) , x(j) )=·log

証明: 無向木の１頂点を任意に選び根とする。そして、そこから遠い頂点に向かって、辺に向きをつける。以下
では頂点 j の親が頂点 i であることを i → j と書く。
（ただし、i が根の場合 0 → i と書く）である。このとき相∫ ∫I(i, j)∫− 12 (x(i)

1 e2π|Σ| 2()σii σij) :=µj|i : X (i) を前提とした、X (j) の生成する事象の条件付測度

1= logpX (i) X (j) (x(i) , x(j) )dx(i) dx(j)pX (i) (x(i) )pX (j) (x(j) )√σii σjj
1|Σ| 2

1= − log (1 − ρij 2 ) 2(i)x x(j) )Σ−1 x(j)となり I(i, j) の値は相関関数 ρij から求めることができ最終的に森が木になった場合にアルゴリズム１とアルゴが正規分布に従うときは、|ρij |リズム２の正規分布に対する修正版は全く同じ木を出力る。したがって各 X(i)の大きい順に辺を繋いでいき Chow-Liu アルゴリズムをする。

進めることができる。

• Xi の分布が、βi 次元の正規分布に従うとき

1Jn (i, j) = In (i, j)− 21 log n = − log (1 − ρij 2 ) 2 − 12 log n
とおく

アルゴリズム 3 (正規分布に従うときの修正版)∑N
共分散行列の次数は i=1 βi であり、独立なパラメータ∑
数 i→j βi βj と書ける。
βi βjlog n木の範囲で学習するとき Jn (i, j) := In (i, j) −2とすればよい。この場合、木の複雑さを考慮しても選択する順序は異なる。

入力: n 個の例 xn
出力: L[π](xn ) を最小とする森 F

3.4

1. E ← {}【Conjecture】

2. E ̸= {} であるかぎり以下を繰り返す。
3. (a) Jn (i, j) が最大の {X (i) , X (j) } ∈ E について、E ← ε − {X (i) , X (j) }(b) (U, E ∪{X (i) , X (j) }) が巡回経路を持たず、かつ Jn (i, j) ≥ 0 のとき、E ← E∪{X (i) , X (j) }(c) F ← (U, E)

X(i)は正規分布に従い、X (j) は離散分布に従う確率変数とする。

Jn (i, j) := In (i, j) −(α(j) − 1)log n2と置く。(α(j) := |X (j) (Ω)|) このときアルゴリズム２は正規分布、離散分布が混在している場合においても以上のように確率変数が正規分布にしたがっている場
合、例に適合する木は相関関数 ρ から求められる。

3.3

正規分布、離散分布が混在している際のChow-Liu アルゴリズム

L[π](xn ) を最小とする森を出力する。

4まとめ正規分布で、木の複雑さを考慮した Chow確率変数間の条件付独立性を木で表現する手法とし
Liu アルゴリズムて、確率変数が有限離散の場合と連続の場合の Chow-• 正規分布で木の複雑さを考慮するときLiu アルゴリズムについて考えてきた。どちらの場合であっても与えられた例に適合する木が出力されることがf (x|Σ): µ = 0, 共分散行列 Σ ∈ RN ×N の正規分布の確率密度関数
Σ̂(xn ): xn = (x1 , · · · , xn ) から得られた Σ の最尤推

相互情報量 I(i, j) の関係から、考慮する確率変数の集定量ルゴリズムが適用できるであろうことが予想される。正尤度 H := − log f (x|Σ̂(xn ))dxk: Σ における独立なパラメータ数分かったが、Kullback-Leibler(K-L) 情報量 D(P ||Q) と合が離散、連続の入り混じったものであっても同様のア規分布での例から分かるように結びつける確率変数のパラメータ数が一定である場合は、Chow-Liu アルゴリズ
ムとその修正版とで確率変数を結び付けていく順序に違と置き、MDL 原理記述長 L := H +となるように

klog n → 最小2

1
Jn (i, j) := In (i, j) − log n2とすればよい。
X (i) , i = 1, ..., N が離散確率変数であったときと異なりパラメータ数がどの確率変数についても一定であるた
めに、木の複雑さを考慮しても選択の順序（In (i, j) とJn (i, j) の大小関係の順序）は変化しない。したがっていはないが、パラメータ数の異なる確率変数の集合にアルゴリズムを適用した場合、結びつける順序によって出力される木構造の簡潔さに大きな差が生まれるためパラメータ数を考慮した修正版のアルゴリズムは大きな意味を持つ。

参考文献[1] C.K.CHOW,C.N.LIU: Approximating Discrete
Probability Distributions
Trees.(1968)

withDependence[2] J.Suzuki,”A construction of bayesian networks
from databases on an MDL principle”,Proc 9thUAI,Morgan,Kaufmann,pp.266-273,1993.
[3] 鈴木譲: ベイジアンネットワーク入門［確率的知識
情報処理の基礎］(2009)