We used the Forward-Backward algorithm to perform Expectation-Maximization, which is a procedure that iteratively re-estimates the model parameters (θ, φ), converging on a local maximum of the likelihood.
if the parameter estimate at time is (θ ( ) , φ ( ) ), then the re-estimated parameters at time + 1 are: where n x,y is the number of times observation x occurs with state y, n y ,y is the number of times state y follows y and n y is the number of occurences of state y; all expectations are taken with respect to the model (θ ( ) , φ ( ) ).