1 / 21
Kruscal V : w i,j R: w i,j = w j,i i j Kruscal (w i,j 0 ) 1 E {{i, j} i, j V, i i} 2 E {} 3 while(e = ϕ) for w i,j {i, j} E 1 E E\{i, j} 2 G = (V, E {i, j}) = E E {i, j} G {i,j} E w i,j 2 / 21
w i,j = I (i, j)( ) i 1 1 2 1 2 3 j 2 3 3 4 4 4 I (i, j) 12 10 8 6 4 2 X (1) X (3) X (2) X (4) X (1) X (3) X (2) X (4) X (1) X (3) X (2) X (4) X (1) X (3) X (2) X (4) 3 / 21
Dendroid G := (V, E) V := {1,, N} Q 1,,N (x (1),, x (N) ) = d i := {j V {i, j} E} {i,j} E P i,j(x (i), x (j) ) i V P i(x (i) ) d i 1 4 / 21
Chow-Liu : P 1,,N Dendroid Q 1,,N Chow-Liu, 1968 w i,j := I (i, j) Kruscal D(P 1,,N Q 1,,N ) P 1,,N (x (1),, x (N) ) log Q 1,,N (x (1),, x (N) ) x (1),,x (N) = H(i) I (i, j) i V {i,j} E 5 / 21
Chow-Liu : {(X (1) i,, X (N) i )} i=1 : iid P 1,,N n {(x (1) i,, x (N) i )} n i=1 I n (i, j): X (i), X (j) ˆP 1,,N : P 1,,N 1 I n (i, j) i, j V (i j) 2 Chow-Liu : D(ˆP 1,,N ˆQ 1,,N ) ˆQ 1,,N 6 / 21
{x (i) k }n k=1 (i), {(x k, x (j) k )}n k=1 R n (i), R n (i, j) A (i) : X (i) α (i) := A (i) c n [x]: {x (i) k }n k=1 x A(i) c n [x, y]: {(x (i) k, x (j) k )}n k=1 (x, y) A(i) A (j) Direchlet(a = 1/2) R n (i) := R n (i, j) := Γ(n + α (i) a)γ(a) α(i) Γ(α (i) a) x A (i) Γ(c n[x] + a) Γ(n + α (i) α (j) a)γ(a) α(i) α (j) Γ(α (i) α (j) a) x A (i) Γ(c n[x, y] + a) 7 / 21
{(x (1) k,, x (N) )} n k=1 L k log R n (i) nh n (i) + α(i) 1 log n 2 log R n (i, j) nh n (i, j) + α(i) α (j) 1 log n 2 log R n (i, j) + logr n (j) n{h n (i, j) H n (j) + α(j) (α (i) 1) 2n = n{h n (i) + α(i) 1 2n L n i V n log n} log n I n (i, j) + (α(j) 1)(α (i) 1) 2n {H n (i) + α(i) 1 2n {i,j} E log n} {I n (i, j) 1 2n (α(i) 1)(α (j) 1) log n} log n} 8 / 21
Chow-Liu : J n (i, j) := I n (i, j) 1 2n (α(i) 1)(α (j) 1) log n J n (i, j) Kruscal (V, E) 1 J n (i, j) i, j V (i j) 2 3 J n (i, j) < 0 Chow-Liu : (Suzuki, 1993) ˆQ 1,,N 9 / 21
i j I n (i, j) α (i) α (j) J n (i, j) 1 2 12 5 2 8 1 3 10 5 3 2 2 3 8 2 3 6 1 4 6 5 4-6 2 4 4 2 4 1 3 4 2 3 4-4 X (1) X (3) X (2) X (4) X (1) X (3) X (2) X (4) X (1) X (3) X (2) X (4) X (1) X (3) X (2) X (4) 10 / 21
(Ω, F): µ, ν: F B: R Borel Radon-Nikodym µ ν (µ << ν) A F ν(a) = 0 = µ(a) = 0 ν σ- Ω = i A i ν(a i ) < A i F, i = 1, 2, f : Ω R F D B {ω Ω X (ω) D} F Radon-Nikodym µ, ν σ µ ν A F µ(a) = F dµ dν := f 0 A fdν 11 / 21
(Ω, F, µ): X : Ω R X F Kullback-Leibler F X (x) = 0 x < 1 1 2 1 x < 0 1 2 + x 0 1 2 g(t)dt 0 x Kullback-Leibler µ ν D(µ ν) := log( dµ dν )dµ 12 / 21
Chow-Liu : D (1),, D (N) B µ i (D (i) ) := µ(x (i) D (i) ) µ ij (D (i), D (j) ) := µ(x (i) D (i), X (j) D (j) ) µ 1,,N (D (1),, D (N) ) := µ(x (i) D (i), i = 1,, N) N µ 1 µ N (D (1),, D (N) ) := µ i (D (i) ) i=1 13 / 21
µ ij µ i µ j I (i, j) := D(µ ij µ i µ j ) dµ i,j (x (i), x (j) ) dν 1,,N (x (1),, x (N) ) = 1 {i,j} E dµ i (x (i) ) d i 1 D(µ 1,,N ν 1,,N ) = D(µ 1,,N µ 1 µ N ) I (i, j) i V {i,j} E 14 / 21
( ) X : A c n [x]: n x n := {x k } n k=1 An x A R n (x n ) := Γ(n + A /2)Γ(1/2) A Γ( A /2) x A Γ(c n[x] + 1/2) H: X iid X P 1 n log Rn (x n ) H (n ) P n (x n ): X n = x n Shannon-McMillan-Breiman X P 1 n log Pn (x n ) H (n ) R X P 1 n log Pn (x n ) R n (x n 0 (n ) ) 15 / 21
( ) X [0, 1) A 0 := {[0, 1)} A 1 = {[0, 1/2), [1/2, 1)} A 2 = {[0, 1/4), [1/4, 1/2), [1/2, 3/4), [3/4, 1)} A k = {[0, 2 (k 1) ), [2 (k 1), 2 2 (k 1) ),, [(2 k 1 1)2 (k 1), 1)} g (Ryabko, 2009) X f 1 n log f n (x n ) g n (x n 0 (n ) ) 16 / 21
( ) η: σ, µ η Suzuki, 2011 f := dµ dµ dλ dη ( λ η ) D(µ k η) D(µ η) (k ) = 1 n (µ η ) log dµn dν n (x n ) 0 (n ) 17 / 21
Bayes (x n, y n ): (X, Y ) n µ X η X, µ Y η Y dµ n X dηx n (x n ), dµn Y dηy n (y n dµ n XY ), dηx n (x n, y n ) dηn Y dνn X dηx n (x n ), dνn Y dηy n (y n ), dν n XY 2: 1 n log dν n XY dηx n (x n, y n ) dηn Y dνx n dηx n (x n ) dνn Y dηy n (y n ) dηx n (x n, y n ) dηn Y I (X, Y ) (1) 18 / 21
1 (Ω, F) µ(ω) = 1 {µ[m]} m N 1 n log µn [m] ν n [m] (x n ) 0 {ν[m]} m N 2 m N µ[m ] n x n log dνn [m] dη n (x n ) m m log dν[m ] n dη n (x n ) log dν[m]n dη n (x n ) log dν[m ] n dν[m] n (x n ) 0 19 / 21
Chow-Liu : K n (i, j): X (i), X (j) Bayes {(x (1) k,, x (N) k )} n k=1 log dνn i dηi n ({x (i) k }n k=1 ) n K n (i, j) i V {i,j} E 1 K n (i, j) i, j V (i j) 2 3 K n (i, j) < 0 Chow-Liu : ν ν n log dνn dν n (x n ) 0 20 / 21
Bayes Bayes Chow-Liu : 21 / 21