Expectation-Maximization is a procedure that iteratively re-estimates the model parameters (θ, φ), converging on a local maximum of the likelihood.
if the parameter estimate at iteration is (θ ( ) , φ ( ) ), then the re-estimated parameters at iteration + 1 are: (2) where n w,t is the number of times word w occurs with state t, n t ,t is the number of times state t follows t and n t is the number of occurences of state t; all expectations are taken with respect to the model The experiments below used the Forward-Backward algorithm (Jelinek, 1997), which is a dynamic programming algorithm for calculating the likelihood and the expectations in (2) in O(nm 2 ) time, where n is the number of words in the training corpus and m is the number of HMM states.