16 2 Learning the HMM | Machine Learning скачать в хорошем качестве

16 2 Learning the HMM | Machine Learning

LEARNING THE HMM: THE LOG LIKELIHOOD I Maximizing p(~xjπ; A; B) is hard since the objective has log-sum form ln p(~xjπ; A; B) = ln SXs=11 · · · SX sT=1 TYi=1 p(xi j si; B) p(si j si−1; π; A) I However, if we had or learned~s it would be easy (remove the sums). I In addition, we can calculate p(~s j~x; π; A; B), though it’s much more complicated than in previous models. I Therefore, we can use the EM algorithm! The following is high-level. LEARNING THE HMM: THE LOG LIKELIHOOD E-step: Using q(~s) = p(~s j~x; π; A; B), calculate L(~x; π; A; B) = Eq [ln p(~x;~s j π; A; B)] : M-Step: Maximize L with respect to π; A; B. This part is tricky since we need to take the expectation using q(~s) of ln p(~x;~s j π; A; B) = TXi=1 SXk=1 1(si = k) ln Bk;xi | {z } observations + SXk=1 1(s1 = k) ln πk | {z } initial state + TXi=2 SXj=1 SXk=1 1(si−1 = j; si = k) ln Aj;k | {z } Markov chain The following is an overview to help you better navigate the books/tutorials.1 1See the classic tutorial: Rabiner, L.R. (1989). “A tutorial on hidden Markov models and selected applications in speech recognition.” Proceedings of the IEEE 77(2), 257–285 LEARNING THE HMM: THE LOG LIKELIHOOD E-step: Using q(~s) = p(~s j~x; π; A; B), calculate L(~x; π; A; B) = Eq [ln p(~x;~s j π; A; B)] : M-Step: Maximize L with respect to π; A; B. This part is tricky since we need to take the expectation using q(~s) of ln p(~x;~s j π; A; B) = TXi=1 SXk=1 1(si = k) ln Bk;xi | {z } observations + SXk=1 1(s1 = k) ln πk | {z } initial state + TXi=2 SXj=1 SXk=1 1(si−1 = j; si = k) ln Aj;k | {z } Markov chain The following is an overview to help you better navigate the books/tutorials.1 1See the classic tutorial: Rabiner, L.R. (1989). “A tutorial on hidden Markov models and selected applications in speech recognition.” Proceedings of the IEEE 77(2), 257–285 LEARNING THE HMM WITH EM E-Step Let’s define the following conditional posterior quantities: γi(k) = the posterior probability that si = k ξi(j; k) = the posterior probability that si−1 = j and si = k Therefore, γi is a vector and ξi is a matrix, both varying over i. We can calculate both of these using the “forward-backward” algorithm. (We won’t cover it in this class, but Rabiner’s tutorial is good.) Given these values the E-step is: L = SXk=1 γ1(k) ln πk + TXi=2 SXj=1 SXk=1 ξi(j; k) ln Aj;k + TXi=1 SXk=1 γi(k) ln Bk;xi This gives us everything we need to update π; A; B.LEARNING THE HMM WITH EM E-step: Using q(~s) = p(~s j~x; π; A; B), calculate L(~x; π; A; B) = Eq [ln p(~x;~s j π; A; B)] : M-Step: Maximize L with respect to π; A; B. This part is tricky since we need to take the expectation using q(~s) of ln p(~x;~s j π; A; B) = TXi=1 SXk=1 1(si = k) ln Bk;xi | {z } observations + SXk=1 1(s1 = k) ln πk | {z } initial state + TXi=2 SXj=1 SXk=1 1(si−1 = j; si = k) ln Aj;k | {z } Markov chain The following is an overview to help you better navigate the books/tutorials.1 1See the classic tutorial: Rabiner, L.R. (1989). “A tutorial on hidden Markov models and selected applications in speech recognition.” Proceedings of the IEEE 77(2), 257–285.LEARNING THE HMM WITH EM E-Step Let’s define the following conditional posterior quantities: γi(k) = the posterior probability that si = k ξi(j; k) = the posterior probability that si−1 = j and si = k Therefore, γi is a vector and ξi is a matrix, both varying over i. We can calculate both of these using the “forward-backward” algorithm. (We won’t cover it in this class, but Rabiner’s tutorial is good.) Given these values the E-step is: L = SXk=1 γ1(k) ln πk + TXi=2 SXj=1 SXk=1 ξi(j; k) ln Aj;k + TXi=1 SXk=1 γi(k) ln Bk;xi This gives us everything we need to update π; A; B.LEARNING THE HMM WITH EMLEARNING THE HMM: THE LOG LIKELIHOOD E-step: Using q(~s) = p(~s j~x; π; A; B), calculate L(~x; π; A; B) = Eq [ln p(~x;~s j π; A; B)] : M-Step: Maximize L with respect to π; A; B. This part is tricky since we need to take the expectation using q(~s) of ln p(~x;~s j π; A; B) = TXi=1 SXk=1 1(si = k) ln Bk;xi | {z } observations + SXk=1 1(s1 = k) ln πk | {z } initial state + TXi=2 SXj=1 SXk=1 1(si−1 = j; si = k) ln Aj;k | {z } Markov chain The following is an overview to help you better navigate the books/tutorials.1 1See the classic tutorial: Rabiner, L.R. (1989). “A tutorial on hidden Markov models and selected applications in speech recognition.” Proceedings of the IEEE 77(2), 257–285.LEARNING THE HMM WITH EM E-Step Let’s define the following conditional posterior quantities: γi(k) = the posterior probability that si = k ξi(j; k) = the posterior probability that si−1 = j and si = k Therefore, γi is a vector and ξi is a matrix, both varying over i. We can calculate both of these using the “forward-backward” algorithm. (We won’t cover it in this class, but Rabiner’s tutorial is good.) Given these values the E-step is: L = SXk=1 γ1(k) ln πk + TXi=2 SXj=1 SXk=1 ξi(j; k) ln Aj;k + TXi=1 SXk=1 γi(k) ln Bk;xi This gives us everything we need to update π; A; B.LEARNING THE HMM WITH EM