Baum-Welchアルゴリズムの動作と応用例

1 Baum-Welch . Step by Step the Baum-Welch Algorithm and its Application Jin'ichi murakami .. EM EM.. EM Baum-Welch . Baum-Welch . Baum-Welch . Baum-Welch , EM . Baum-Welch . 1.. EM 2. HMM. EM (Expectation- Hidden Markov Model . maximization algorithm) 1 3. HMM . EM . 4. HMM . 5. HMM . Baum-Welch . 6. Baum-Welch .. 2. HMM. EM Baum- Welch 2 2. 1 HMM. Steve Young . 3 4 . Steve Young Baum-Welch . 4 .. 3 4 1.. 1 a, b, c .. E-mail Jin'ichi murakami , Member (Department of Information and Elec- . tronics, Graduate School of Engineering Tottori University 4-101, Koyamachou Minami, Tottori, 680-8552 Japan).. Fundamentals Review 9 xxxx xx . c xxxx IEICE Fundamentals Review 1. 2. 3 HMM . Left-to-Right HMM.

2 HMM 4 .. i i i . Left-to-Right HMM . 1 i = 0 0 = . HMM . HMM Left-to- HMM Right HMM . ai,j ai,j i j .. bi,j (O). bi,j (O) i j 2. 2 Ergodic HMM Left-to-Right HMM. O . parameter tie bi (O) . HMM Left-to-Right HMM Ergodic parameter tie 2. 4 . HMM Left-to-Right HMM .. Ergoic HMM 2. 4 parameter tie 2 bi,j (O) = bi,i (O) = bi (O). Left-to-Right HMM Left-to-Right HMM 4 3 HMM . Left-to-Right HMM 3 i j O . Ergodic HMM bi,j (O) . i j . bi,j (O) i i . bi,i (O) . parameter tie bi,j (O) = bi,i (O) = bi (O).. 2 Left-to-Right HMM .. bi,i (O) .. bi,j (O) . parameter tie bi,j (O) = bi,i (O) . 3 Ergodic HMM. 2. 5 HMM . Left-to-Right HMM . ( ) Ergodic HMM . HMM . ( ) .. Left-to-Right HMM 5 6 .. Ergodic-HMM.

3 7 .. 2 IEICE Fundamentals Review 4 1 HMM .. X. i = i . i j .. X. ai,j = 4 Model A. j 2 Model B. 2 Model B . i . 2 Model B .. 0 = 1 = 2 = X. bi (O) = . O K 3.. K O a0,0 = a1,1 = a2,2 = a0,1 = a1,2 = a2,3 = 2. 6 HMM . b0 ( ) = b1 ( ) = b2 ( ) = b0 ( ) = b1 ( ) = b2 ( ) = HMM Model A . b0 ( ) = b1 ( ) = b2 ( ) = 1 Model B 2 .. 4 3 Left-to-Right HMM. (i = {0, 1, 2}, j = {0, 1, 2, 3}). , , 3 . ( K = { , , }). 0 . ( i = 0, i = 3). 1 Model A. 5 Model B. 3 HMM . 2. 5 Model A . 1 Model A Model B HMM 3 .. 0 = 1 = 2 = 3 HMM . 3 0 + 1 + 2 = a0,0 + a0,1 = a0,0 = a1,1 = a2,2 = a1,1 + a1,2 = a0,1 = a1,2 = a2,3 = a2,2 + a2,3 = b0 ( ) + b0 ( ) + b0 ( ) = b0 ( ) = b1 ( ) = b2 ( ) = b1 ( ) + b1 ( ) + b1 ( ) = b0 ( ) = b1 ( ) = b2 ( ) = b2 ( ) + b2 ( ) + b2 ( ) = b0 ( ) = b1 ( ) = b2 ( ) = IEICE Fundamentals Review 3.

4 (= + + ) . 3. 4 (O0 = , O1 =. , O2 = , O3 = ) 3 . 3. 1 .. 6 ( . Ot t O0 = , O1 = , O2 = , O3 = , O4 = , O5 = ) . O0 = , O1 = , O2 = , O3 = 10 .. 40ms N 3. 3 Forward . 256 . 3. 2 .. 3. 2 forward .. Model A . 6 . HMM grid . HMM i (j) i (j) . HMM 0 i j . Model A Ot t .. 4 . 3 . grid . 4 . forward grid . t 0 1 2 3. Ot . path1: 0 0 1 2 3 t (j) = t 1 (j) aj,j bj (Ot 1 ). path2: 0 1 1 2 3 + t 1 (j 1) aj 1,j bj 1 (Ot 1 ). path3: 0 1 2 2 3. Model A grid . 5 . 0 (0) = 1 (0) = 0 (0) a0,0 b0 (O0 ) = 0 (0) a0,0 b0 ( ). 5 . = = 1 (1) = 0 (0) a0,1 b0 (O0 ) = 0 (0) a0,1 b0 ( ). path1: a0,0 b0 (O0 ) a0,1 b0 (O1 ) a1,2 b1 (O2 ) a2,3 b2 (O3 ) = = = a0,0 b0 ( ) a0,1 b0 ( ) a1,2 b1 ( ) a2,3 b2 ( ) 2 (1) = 1 (1) a1,1 b1 (O1 ) + 1 (0) a01 b0 (O1 ).

5 = = 1 (1) a1,1 b1 ( ) + 1 (0) a01 b0 ( ). = = + = path2: 2 (2) = 1 (1) a1,2 b1 (O1 ) = 1 (1) a1,2 b1 ( ). a0,1 b0 (O0 ) a1,1 b1 (O1 ) a1,2 b1 (O2 ) a2,3 b2 (O3 ). = a0,1 b0 ( ) a1,1 b1 ( ) a1,2 b1 ( ) a2,3 b2 ( ). = = = 3 (2) = 2 (2) a2,2 b2 (O2 ) + 2 (1) a1,2 b1 (O2 ). = = 2 (2) a2,2 b2 ( ) + 2 (1) a1,2 b1 ( ). path3: = + a0,1 b0 (O0 ) a1,2 b1 (O1 ) a2,2 b2 (O2 ) a2,3 b2 (O3 ). = (; ). = a0,1 b0 ( ) a1,2 b1 ( ) a2,2 b2 ( ) a2,3 b2 ( ). 4 (3) = 3 (2) a2,3 b2 (O3 ) = 3 (2) a2,3 b2 ( ). = = = = (; ). = 4 (3) = 4 IEICE Fundamentals Review 3. 2 4. 2 HMM .. HMM .. 4. 1 HMM . 6 7 . 6 forward . 3. 4 . 1 . 7 .. Ot t . 6 HMM . O0 = , O1 = , O2 = , O3 = .. 2 . 0 = 1 = 2 = Model A HMM Model B HMM . HMM 3.

6 Model A HMM . Model B HMM a0,0 = a1,1 = a2,2 = a0,1 = a1,2 = a2,3 = Model A Model B .. Model A Model A . b0 ( ) = b1 ( ) = b2 ( ) = b0 ( ) = b1 ( ) = b2 ( ) = b0 ( ) = b1 ( ) = b2 ( ) = 4. HMM . forward grid 8 . 3. HMM .. 4. 5.. HMM . 4. 1 .. Ot t . O0 = , O1 = , O2 = , O3 = . HMM . HMM 8 . 2. 5 . 3 . IEICE Fundamentals Review 5. backword grid t (i) . 5. Baum-Welch t (i) t i . forward grid t (i) . 4. 2 . Baum-Welch 2 4 (3) = 4 (2) = 4 (1) = 4 (0) = .. backward grid . Left-to-Right HMM . t (j) = t+1 (j + 1) aj,j+1 bj (Ot ). Baum-Welch t . + t+1 (j) aj,j bj (Ot ). i j t (i, j) . grid . forward backward . t (i, j) . 4 (3) = 3 (2) = 4 (3) a2,3 b2 (O3 ) = 4 (3) a2,3 b2 ( ). = = 5. 1 Forward . 2 (2) = 3 (2) a2,2 b2 (O2 ) = 3 (2) a2,2 b2 ( ).

7 = = 4. 1 . 2 (1) = 3 (2) a1,2 b1 (O2 ) = 3 (2) a1,2 b1 ( ). 1 . = = forward . 1 (1) = 2 (2) a1,2 b1 (O1 ) + 2 (1) a1,1 b1 (O1 ). 9 9 3. 3 6 . = 2 (2) a1,2 b1 ( ) + 2 (1) a1,1 b1 ( ). forward grid t (i) . = + = (; ). t (j) = t 1 (j) aj,j bj (Ot 1 ). 1 (0) = 2 (1) a0,1 b0 (O1 ) = 2 (1) a0,1 b0 ( ). + t 1 (j 1) aj 1,j bj 1 (Ot 1 ) = = (; ). 0 (0) = 1 (1) a0,1 b0 (O0 ) + 1 (0) a0,0 b0 (O0 ). 0 (0) = 1 (0) = = 1 (1) a0,1 b0 ( ) + 1 (0) a0,0 b0 ( ). 1 (1) = 2 (1) = = + 2 (2) = 3 (2) = = (; ). 4 (3) = = 4 (3) = Backword grid 0 (0) Forward . grid 4 (3) .. = 0 (0) = 4 (3) = 9 forward . 5. 2 Backword . 10 backward . Backward . forward . 10 .. 6 IEICE Fundamentals Review 5. 3 t (i, j) 5. 4 ai,j . Baum-Welch ai,j t (i, j).

8 T (i, j) t i j . Baum-Welch . Forward Backword P. t t (i, j). t (i, j) ai,j = P P. t (i, j). j t t (i)ai,j bi (Ot ) t+1 (j). t (i, j) = ai,j . likelihood 0 (0,0). a0,0 = 0 (0,0)+ 0 (0,1)+ 1 (0,1). = likelihood = = 4 (3). 0 (0,1)+ 1 (0,1). a0,1 = 0 (0,0)+ 0 (0,1)+ 1 (0,1). = t (i, j) . 0 (0)a0,0 b0 (O0 ) 1 (0) (0)a0,0 b0 ( ) 1 (0). 0 (0, 0) = likelihood = 0 likelihood 1 (1,1). a1,1 = 1 (1,1)+ 1 (1,2)+ 2 (1,2). = = = 0 (0)a0,1 b0 (O0 ) 1 (1) 0 (0)a0,1 b0 ( ) 1 (1). 0 (0, 1) = likelihood = likelihood 1 (1,2)+ 2 (1,2). a1,2 = 1 (1,1)+ 1 (1,2)+ 2 (1,2). = = = 1 (0)a0,1 b0 (O1 ) 2 (1) (0)a0,1 b0 ( ) 2 (1). 1 (0, 1) = likelihood = 1 likelihood 2 (2,2). a2,2 = 2 (2,2)+ 3 (2,3). = = = 1 (1)a1,1 b1 (O1 ) 2 (1) 1 (1)a1,1 b1 ( ) 2 (1).

9 1 (1, 1) = likelihood = likelihood 3 (2,3). a2,3 = 2 (2,2)+ 3 (2,3). = = = 1 (1)a1,2 b1 (O1 ) 2 (2) (1)a1,2 b1 ( ) 2 (2). 1 (1, 2) = likelihood = 1 likelihood . = = 2 (1)a1,2 b1 (O2 ) 3 (2) 2 (1)a1,2 b1 ( ) 3 (2) a0,0 + a0,1 = 2 (1, 2) = likelihood = likelihood a1,1 + a1,2 = = = 2 (2)a2,2 b2 (O2 ) 3 (2) (2)a2,2 b2 ( ) 3 (2) a2,2 + a2,3 = 2 (2, 2) = likelihood = 2 likelihood = = 3 (2, 3) =. 3 (2)a2,3 b2 (O3 ) 4 (3) (2)a2,3 b2 ( ) 4 (3). = 3 likelihood 5. 5 bj (O) . likelihood = = bj (O) t (i, j) .. 0 (0, 0) + 0 (0, 1) = 1 (0, 1) + 1 (1, 1) + 1 (1, 2) = 2 (1, 2) + 2 (2, 2) = P P. t O t (j, k). bj (O) = P k 3 (2, 3) = P. t k t (j, k). t (i, j) t i j . t (i, j) t O t Ot O . Baum-Welch . 11 t (i, j) bj (O).

10 0 (0,0)+ 0 (0,1)+ 1 (0,1). b0 ( ) = 0 (0,0)+ 0 (0,1)+ 1 (0,1). = 0. b0 ( ) = 0 (0,0)+ 0 (0,1)+ 1 (0,1). = 0. b0 ( ) = 0 (0,0)+ 0 (0,1)+ 1 (0,1). = 1 (1,1)+ 1 (1,2). b1 ( ) = 1 (1,1)+ 1 (1,2)+ 2 (1,2). = 2 (1,2). b1 ( ) = 1 (1,1)+ 1 (1,2)+ 2 (1,2). = 0. b1 ( ) = 1 (1,1)+ 1 (1,2)+ 2 (1,2). = 0. b2 ( ) = 2 (2,2)+ 3 (2,3). = 2 (2,2). b2 ( ) = 2 (2,2)+ 3 (2,3). = 3 (2,3). b2 ( ) = 2 (2,2)+ 3 (2,3). = . b0 ( ) + b0 ( ) + b0 ( ) = b1 ( ) + b1 ( ) + b1 ( ) = b2 ( ) + b2 ( ) + b2 ( ) = 11 t (i, j) . IEICE Fundamentals Review 7. 5. 6 0 Baum-Welch .. forward 8 . DNA . 12 9 . Baum-Welch .. Ergodic HMM .. 12 forward .. = .. 5. 1 .. 5. 7 .. Baum-Welch 5. 1 5. 5 . 13 .. (likelihood) 4. 2 7.. Baum-Welch.