(ML 14.8) Forward algorithm (part 2)

The Forward algorithm for hidden Markov models (HMMs).

[@jamesyeh8508]

Thank you Prof. Miller, I finally understand the B-F part of the algorithm!

[@mrbeancanman]

You have saved me.. my lecturer did not explain HMMs well. Thank you.

[@amizan8653]

Thanks for posting these videos. I finally understand the forward part of the forward-backward algorithm, and how it is used in order to figure out the probability that an observed sequence was generated by a given hidden markov model.

[@kjpr5641]

I really have enjoyed your tutorials. Just wondering though isn't the computational complexity n-2(m^2) + m as the penultimate value alpha2(z2) has only m lots of values as the alpha1(z1) feeds only 1 value into alpha2(z2) per each component of the sum. I guess if n is very large then the value is essentially nm^2 but just wanted to ask to check whether i am missing something

[@broker220981]

Nice video, although computational complexity part still isn't clear to me. You say In naive approach we have to do p(x), which is m^n steps, but don't we have to compute p(x) after Forward algorithm as well?

[@traverseapp1587]

Can you do a video on the Junction Tree Algorithm (JTA). Seems like logical inclusion given HMMs, Markov chains, and earlier graphical models sequence. Also a piece on message passing to could be a good additional video for this sequence

[@p.z.8355]

sounds like variable elimination with a perfect order

[@amirkhalili82]

In respond to broker220981's question the naive approach refers to p(zk,x) = sum over z1,z2,...zk-1,zk+1,...zn which is theta(m^(n-1)) for each instance of zk. And since Zk can take m finite values , m*m^(n-1) = m^n in total. P(x) needs to be computed in the both approaches for exact calculation but usually P(x) is assumed to be a constant to avoid the calculation

[@MrUmeshgade]

video is just awesome... could you please give me any illustration video or any link that you know, about how we apply HMM over protein sequence.

[@kiranravuri8218]

I am not clear about the O(m^n) calculation for P(X). Considering 'm' states for Z's, isn't P(X) = P(X,Z_1) + P(X,Z_2) +... + P(X,Z_m) = Sum ( P(X,Z_i) ) : i from 1 to m ?? Isn't each individual P(X,Z_i) is same as the output of Forward algorithm which is O(m) and P(X) will be O(m^2) as explained in previous video ??

[@amirkhalili82]

@broker220981 n respond to broker220981's question the naive approach refers to p(zk,x) = sum over z1,z2,...zk-1,zk+1,...zn which is theta(m^(n-1)) for each instance of zk. And since Zk can take m finite values , m*m^(n-1) = m^n in total. P(x) needs to be computed in the both approaches for exact calculation but usually P(x) is assumed to be a constant to avoid the calculation

[@rojas70]

@ min ~7 , you say we have n z-states, each processing m data points. The time complexity, I think should be n^m, where n is 10 states and and m is 100 data points, versus m^n.

[@wenkunwu3644]

+Juan Rojas He said m is 10 states and n is 100 data points at 7:22

[@ebubechukwuenwerem9145]

Just one example with real values and data would have helped alot