4d_06.dvi

Size: px

Start display at page:

Download "4d_06.dvi"

えみこしの
5 years ago
Views:

1 Learning and Recognition of Time-Series Data Based on Self-Organizing Incremental Neural Network Shogo OKADA and Osamu HASEGAWA Self-Organizing Incremental Neural Network (SOINN) DP [12] DP SOINN HMM (Hidden Markov Model) DP DP 1. DNA HMM (Hidden Markov Model) [1] HMM [2] [3] Department of Computational Intelligence and System Science, Tokyo Institute of Technology, 4259 Nagatsuta-cho, Midori-ku, Yokohama-shi, Japan Imaging Science and Engineering Laboratory, Tokyo Institute of Technology, 4259 Nagatsuta-cho, Midori-ku, Yokohama-shi, Japan HMM HMM (Discrete HMM) [4], [5] HMM (Continuous HMM) [6], [7] Segment model [8] HMM DP DP [9] [10] [11] DP 1042 D Vol. J91 D No. 4 pp c 2008

2 HMM DP HMM DP [12] DP DP DP 1 1 HMM left to right Self-Organizing Incremental Neural Network (SOINN) Self-Organizing Incremental Neural Network (SOINN) [13] Shen Hasegawa SOINN SOINN SOINN SOINN HMM DP SOINN SOINN-DP 1. 1 HMM DP SOINN-DP SOINN-DP HMM SOINN-DP HMM DP 2 HMM DP 1. 2 [14] [16] [14] HMM MLP (Multi Layer Perceptron) [16] [14] [15] MLP w hybrid HMM/ANN system MLP w Soft-Weight-sharing ML 1043

3 2008/4 Vol. J91 D No. 4 [14] HMM hybrid HMM/ANN system MLP SOINN SOINN Parzen SOINN Parzen SOINN HMM HMM/ANN hybrid MLP SOINN Parzen HMM [16] 2. SOINN-DP DP SOINN 2. 1 DP 2. 2 SOINN 2. 3 SOINN-DP 2. 1 DP I X = {x 1,x 2,,x i,,x I} J Y = {y 1,y 2,,y j,,y J} DP i j X Y X x i i X Y D(X, Y ) (i =1 j =1) g(1, 1) = d(1, 1) (i >1 j >1) g(i, j 1) + d(i, j) g(i, j) =min g(i 1,j 1) + 2d(i, j) (1) g(i 1,j)+d(i, j) D(X, Y ) D(X, Y )= g(i,j) I + J (2) DP D(X, Y ) DP X i x i Y j y j j = w i (i =1, 2,,I) 2. 2 SOINN SOINN [13] SOINN Growing Neural Gas (GNG) [17] SOINN SOINN T 1 2 T 1044

4 1 ξ s 1 2 s 2 T s1 T s2 ξ T ξ Fig. 1 Between-class insertion process. 2 SOINN Fig. 2 Flowchart of SOINN s algorithm. 2 2 i T i T i 2.1 W i i 2.1: T 1 i + 2 i 2 T i i i T i i T i =max c Ni W i W c N i i i T i i T i =min c A\{i} W i W c A SOINN (edge aging scheme [18]) a d 0 SOINN : SOINN 1 A (A = {c 1,c 2}) C (C A A) 2 ξ R n R n SOINN 3 (winner) s 1 2 (second winner) s 2 s 1 =argmin ξ Wc (3) c A s 2 =arg min ξ W c (4) c A\{s 1 } ξ s 1 s 2 T s1 T s2 A 2 T s 1 s

i) ( i N s1 ) (6) 7 a d 8 λ [13] SOINN 9 2 2 (9) LT LT ((1) (9)) A 2.

5 2008/4 Vol. J91 D No. 4 C 0 5 s 1 6 ɛ 1 ɛ 2 ɛ 1(t) =1/t ɛ 2(t) =1/100t t ΔW s1 = ɛ 1(t)(ξ W s1 ) (5) ΔW i = ɛ 2(t)(ξ W i) ( i N s1 ) (6) 7 a d 8 λ [13] SOINN (9) LT LT ((1) (9)) A 2.2 (a d λ) λ λ λ a d a d a d (a d λ) SOINN SOINN 3 1 SOINN Sin 10% SOINN SOINN 4 4 SOINN [13] 3 Fig. 3 2D artificial data set with noize pollution. 4 SOINN Fig. 4 Result of clustering. 1046

6 SOINN-DP SOINN SOINN-DP SOINN SOINN SOINN SOINN SOINN-DP SOINN-DP DP DP SOINN-DP STEP C N N STEP 1 C P m C P m P n DP C DP { N } m =argmin D(P m m, P n) ({P n, P m} C) n=1 (7) (7) arg m C m P P T STEP 2 P N 1 DP P P N SOINN P j p j P n (n C) i p n i p j p n i w n i = wj n (j =1, 2,,T ) (8) (8) i j SOINN N 1 N 1 w n (n =1,,N 1) N 1 j Z j SOINN-DP DP 1 1 SOINN DP j j + L SOINN-DP SOINN-DP SOINN Z j Z j+l 1 j (SOINN) j SOINN Z j Z j = {Z j, Z j+1,, Z j+l 1} (9) L SOINN-DP Segment 1047

7 2008/4 Vol. J91 D No. 4 5 STEP 2. 5 Criterion Data Data1 3 Data Criterion Data DP Criterion Data 1 Data1 1 2 Data2 3 1 Z 1 (Z 1) Z 2 Z 3 (9) Z 1 Z L Z 1 1 SOINN Fig. 5 Process of STEP 2. (In DTW, optimal path between criterion data and training data is determined. Corresponding data in optimal path are input to each SOINN.) Segment L T T L 1 STEP 2. 5 STEP 3 SOINN j Z j SOINN Z j Z j SOINN Z j R n SOINN SOINN A SOINN 2. 2 A W i SOINN SOINN SOINN-DP j S j SOINN SOINN (W ) P whole (x i S j) 1 P whole (x i S j)= (2π) M/2 Σ j 1/2 { exp 1 } 2 (x i µ j) t Σ 1 j (x i µ j) (10) (10) M x i µ j S j SOINN Σ j P whole (x i S j) log(p whole (x i S j)) DP Z 2. 3 STEP 2. µ j A SOINN-DP Z SOINN µ j B SOINN-DP ( ) A B µ j µ j B SOINN 6 class1 3 Parzen [19] Parzen Parzen 1048

8 ( ( C(x i,s 1 K ) j)= log ω jk P class (x i U jk ) 2 k ) +log(p whole (x i S j)) (13) 6 S j SOINN 2 SOINN SOINN class1 2 3 U jk Fig. 6 Two kinds of probability distribution formed with result of SOINN. (nodes and edges) 2 SOINN k U jk U jk P class (x i U jk ) P class (x i U jk ) 1 = (2πh 2 jk )M/2 exp { } x i x jk 2 2h 2 jk (11) (11) M x i x jk SOINN U jk h jk h jk = 1 N jk a l x jk (12) N jk l=1 a l U jk l N jk U jk P class (x i U jk ) log(p class (x i U jk )) log(p whole (x i S j)) log(p class (x i U jk )) S j x i C(x i,s j) (13) ω jk = N jk N all N j all j S j SOINN K S j SOINN SOINN-DP DP c =argmaxe(ip, TM c c) (14) (14) IP E(IP, TM c) IP c DP E(IP, TM c) SOINN-DP c TM c IP DP (1) SOINN-DP SOINN-DP Q(i, j 1) + C(x i,s j) Q(i, j) =max Q(i 1,j 1) + 2C(x i,s j) Q(i 1,j)+C(x i,s j) (15) (15) C(x i,s j) TM c j S j IP i x i SOINN-DP DP DP TM c IP E(IP, TM c) 1049

9 2008/4 Vol. J91 D No. 4 E(IP, TM c)= Q(IIP,Jc) I IP + J c (16) (16) I IP IP J c TM c 3. SOINN-DP SOINN-DP SOINN-DP HMM DP HMM (Hidden Markov Model) HMM HMM HMM HMM HMM HMM Ergodic left to right left to right left to right HMM HMM Baum-Welch Baum-Welch Segmental K-means DP DP [12] Q(i 2,j 1) + log P (a i 1 j) +logp (a i j)+logp DP1(j) Q(i 1,j 1) + log P (a i j) Q(i, j) =max +logp DP2(j) Q(i 1,j 2) + log P (a i j) +logp DP3(j) (17) (17) (17) P (a i j) P DP1,2,3(j) [12] P (a i j) [12] P (a i j) σ 1 10 σ SOINN SOINN-DP SOINN-DP SOINN SOINN (a d λ) LT Baum-Welch LT SOINN LT = λ = SOINN-DP a d a d = SOINN-DP (9) L L SOINN 1050

10 SOINN L L SOINN (10) Σ (10) Σ (SOINN) [12] p p 4 5 p 2 N N SOINN Z i N L N L 4p p 2 L L 4p N p2 N (18) L 6p N L DP DP DP L DP L L SOINN-DP KED TIMIT [20] 1 1 (, ) =(40, 60), (80, 20) 1 Table 1 Task of phone classification experiment. (1) KED TIMIT 39 (aa,ae,ah,ao,ax,ay,bcl,ch,dcl,dh,dx,eh,er,ey, f,gcl,h,ih,iy,jh,k,kcl,l,m,n,ng,ow,p,pcl,r,s,sh, t,tcl,uw,v,w,y,z) (2) Resource Management1 27 (aa,ae,ax,ay,b,ch,d,eh,el, ey,f,iy,jh,k,l,m,n,ow,p,r,s,sil,t,uw,v,w,y) 2 (BEF03 DTB03) 2 (CMR02 DAS12) Resource Management1 [21] 2 (BEF03 DTB03) 2 (CMR02 DAS12) (, ) =(80, 40) khz 15 ms 5ms 12 MFCC (Mel-Frequency Cepstrum Coefficient) 12 ΔMFCC Δ 12 ΔΔMFCC ΔΔ 39 SOINN-DP 1051

2008/4 Vol. J91 D No. 4 L (18) 40 L =6 80 L =3 HMM HMM HMM DP (17) SOINN-DP (15) C() P (a i j) SOINN-DP L 40 6 80 3

11 2008/4 Vol. J91 D No. 4 L (18) 40 L =6 80 L =3 HMM HMM HMM DP (17) SOINN-DP (15) C() P (a i j) SOINN-DP L KED TIMIT 40 2 KED TIMIT 80 3 Resource Management1 80 SO-DP SOINN-DP ST-DP(1) DP ST-DP(2) DP HMM () 2 [%] 10 k-timit KED TIMIT RM1 Resource Management1 TD40 40 TD80 80 Table 2 Classification rate in phone classification task [%]. SO-DP ST-DP(1) ST-DP(2) HMM k-timit TD40 [%] (5S, 2M) k-timit TD80 [%] (5S, 4M) RM TD80 [%] (3S, 3M) S M 2 SOINN-DP DP HMM HMM KED TIMIT KED TIMIT Resource Management DP [12] SOINN-DP DP HMM M1 M7 Fig. 7 Examples of moving images used for experiments. 1052

12 (M1) (M6) M2 M7 SOINN-DP [22] Step1. RGB 2 Step2. [22] SOINN-DP L (18) 10 8 L =5 HMM 3 Table 3 Condition of motion classification experiment. 7 7 (M1) (M2) 2 (M3) 2 (M4) (M5) (M6) (M7) (, ) = (15, 10), (20, 5) 8 4 [%] 100 TD15 15 TD20 20 Table 4 Correct classification rate in motion classification task [%] (SOINN-DP was compared to stochastic DP and HMM). Method SOINN-DP ST-DP(1) ST-DP(2) HMM TD15 [%] (S9) TD20 [%] (S10) DP (17) DP HMM () S 4 15 (TD15) 20 (TD20) SOINN-DP HMM

13 2008/4 Vol. J91 D No. 4 DP [12] SOINN- DP DP HMM 3. 5 DP HMM DP DP SOINN-DP SOINN-DP DP SOINN SOINN-DP DP HMM SOINN-DP SOINN HMM HMM HMM SOINN-DP SOINN-DP DP SOINN-DP L SOINN-DP SOINN-DP SOINN HMM [12] DP ST-DP(1) 4. 2 L SOINN-DP L SOINN-DP L KED TIMIT L =1 4. SOINN-DP SOINN-DP 4. 1 SOINN-DP HMM DP SOINN-DP SOINN (a d λ) L HMM 1054 Fig. 8 8 Relation between number of segments and classification rate.

14 L =5 (57.04%) 40 L =6 8 L = SOINN SOINN-DP SOINN DP SOINN-DP SOINN SOINN SOINN-DP SOINN SOINN SOINN 1 Z j SOINN Z j P (x i S j) C(x i,s j) = log(p (x i S j)) C(x i,s j) 2 Z i SOINN SOINN P whole (x i S j) SOINN P class (x i U jk ) C(x i,s j) (19) α =0 ( K ) C(x i,s j)=αlog ω jk P class (x i U jk ) k +(1 α)log(p whole (x i S j)) (19) KED TIMIT L =3 α α SOINN-DP 5 SOINN-DP 5 SOINN SOINN-DP Table 5 Comparison between classification rate obtained by SOINN-DP and classification rate obtained by method that doesn t use SOINN. SOINN SOINN Method 1 2 SOINN-DP α =0.45 [%] α α =0.0 2 α =0.45 (63.22%) Fig. 9 Changes of the classification rate when α is changed % SOINN SOINN-DP SOINN SOINN SOINN α α 9 9 x α y α 9 α =0.45 α α =1.0 α =1.0 (19) 1055

15 2008/4 Vol. J91 D No. 4 2 SOINN 5 SOINN 9 α =0.45 α SOINN-DP α 4. 4 SOINN-DP SOINN-DP HMM 1 HMM SOINN-DP DP [23] DP [24] DP SOINN-DP 4. 5 SOINN-DP SOINN-DP SOINN-DP 2 DP [25] SOINN-DP SOINN-DP HMM HMM HMM HMM HMM [1] SOINN-DP SOINN-DP SOINN-DP DP 2 DP [26] 2 DP 5. Self-Organizing Incremental Neural Network (SOINN) SOINN-DP SOINN-DP DP SOINN SOINN-DP HMM DP SOINN-DP NEDO The Centre for Speech Technology Re- 1056

search University of Edinburgh [1] L.R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, Proc. IEEE, pp.257 286, 1989. [2] D-II vol.j87-d-ii, no.2, pp.

IEEE International Conference on Computer Vision, pp.379 387, 1992. [5] A. Elgammal, V. Shet, Y. Yacoob, and L.S. Davis, Learning dynamics for exemplar-based gesture recognition, Proc.

16 search University of Edinburgh [1] L.R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, Proc. IEEE, pp , [2] D-II vol.j87-d-ii, no.2, pp , Feb [3] hmm vol.53, no.3, pp , [4] J. Yamato, J. Ohya, and K. Ishii, Recognizing human action in time-sequential images using hidden Markov models, Proc. IEEE International Conference on Computer Vision, pp , [5] A. Elgammal, V. Shet, Y. Yacoob, and L.S. Davis, Learning dynamics for exemplar-based gesture recognition, Proc. IEEE International Conference on Computer Vision and Pattern Recognition, vol.1, pp.16 22, [6] A. Wilson and A. Bobick, Learning visual behavior for gesture analysis, Proc. IEEE International Symposium on Computer Vision, vol.5a, Motion2, [7] R. Hamdan, F. Heits, and L. Thoraval, Gesture localization and recognition using probabilistic visual learning, Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp , [8] M. Ostendorf, V. Digalakis, and O. Kimball, From hmms to segment models: A unified view of stochastic modeling for speech recognition, IEEE Trans. Speech Audio Process., vol.4, no.5, pp , [9] dp SP78-20, [10] D-II vol.j80-d-ii, no.6, pp , June [11] CVIM , [12] dp D vol.j70-d, no.1, pp , Jan [13] F. Shen and O. Hasegawa, An incremental network for on-line unsupervised classification and topology learning, Neural Netw., vol.19, no.1, pp , [14] H. Bourlard and N. Morgan, Continuous speech recognition by connectionist statistical methods, IEEE Trans. Neural Netw., vol.4, no.6, pp , [15] Y. Bengio, R.D. Mori, G. Flammia, and R. Kompe, Global optimization of a neural network-hidden Markov model hybrid, IEEE Trans. Neural Netw., vol.3, no.2, pp , [16] E. Trentin and M. Gori, Robust combination of neural networks and hidden Markov models for speech recognition, IEEE Trans. Neural Netw., vol.14, no.6, pp , [17] B. Fritzke, A growing neural gas network learns topologies, Advances in Neural Information Processing Systems (NIPS), pp , [18] T. Martinetz and K. Schulten, Topology representing networks, Neural Netw., vol.7, no.3, pp , [19] R. Duda, P. Hart, and D. Stork, Pattern Classification, second ed., John Wiley & Sons, Canada, [20] University of Edinburgh, CSTR US KED TIMIT, earth/fk/ [21] P. Price, W. Fisher, J. Bernstein, and D. Pallett, Resource management complete set 2.0, Linguistic Data Consortium, Philadelphia, [22] vol.818, [23] Dp CVIM , [24] C. Raphael, Coarse-to-fine dynamic programming, IEEE Trans. Pattern Anal. Mach. Intell., vol.23, no.12, pp , [25] L. Rabiner and B. Juang, Fundamentals of Speech Recognition, PTR Prentice-Hall, [26] H. Sakoe, Two-level dp-matching A dynamic programming-based pattern matching algoritm for connected word recognition, IEEE Trans. Acoust. Speech Signal Process., vol.assp-27, no.6, pp ,

4. C i k = 2 k-means C 1 i, C 2 i 5. C i x i p [ f(θ i ; x) = (2π) p 2 Vi 1 2 exp (x µ ] i) t V 1 i (x µ i ) 2 BIC BIC = 2 log L( ˆθ i ; x i C i ) + q

4. C i k = 2 k-means C 1 i, C 2 i 5. C i x i p [ f(θ i ; x) = (2π) p 2 Vi 1 2 exp (x µ ] i) t V 1 i (x µ i ) 2 BIC BIC = 2 log L( ˆθ i ; x i C i ) + q x-means 1 2 2 x-means, x-means k-means Bayesian Information Criterion BIC Watershed x-means Moving Object Extraction Using the Number of Clusters Determined by X-means Clustering Naoki Kubo, 1 Kousuke