隐马尔科夫介绍.ppt

* Solution to Problem 2 Forward-Backward Procedure First run forward and backward separately Keep track of the scores at every point Coin toss α: pb of this coin for seeing all the flips now and before β: pb of this coin for seeing all the flips after H T T H H H T α1(F) α2(F) α3(F) α4(F) α5(F) α6(F) α7(F) α1(B) α2(B) α3(B) α4(B) α5(B) α6(B) α7(B) β1(F) β2(F) β3(F) β4(F) β5(F) β6(F) β7(F) β1(B) β2(B) β3(B) β4(B) β5(B) β6(B) β7(B) * Solution to Problem 2 Forward-Backward Procedure Coin toss Gives probabilistic prediction at every time point Forward-backward maximizes the expected number of correctly predicted states (coins) * Solution to Problem 2Viterbi Algorithm Report the path that is most likely to give the observations Initiation Recursion Termination Path (state sequence) backtracking * Viterbi Algorithm Observe: HTTHHHT Initiation * Viterbi Algorithm H T T H F B * Viterbi Algorithm Observe: HTTHHHT Initiation Recursion Max instead of +, keep track path * Viterbi Algorithm Max instead of +, keep track of path Best path (instead of all path) up to here H T T H F F B B * Viterbi Algorithm Observe: HTTHHHT Initiation Recursion Max instead of +, keep track path * Viterbi Algorithm Max instead of +, keep track of path Best path (instead of all path) up to here H T T H F F B B F B F B * Viterbi Algorithm Terminate, pick state that gives final best δ score, and backtrack to get path H T T H BFBB most likely to give HTTH F F B B F B F B B B F B * Solution to Problem 3 No optimal way to do this, so find local maximum Baum-Welch algorithm (equivalent to expectation-maximization) Random initialize ? =(A,B,?) Run Viterbi based on ? and O Update ? =(A,B,?) ?: % of F vs B on Viterbi path A: frequency of F/B transition on Viterbi path B: frequency of H/T emitted by F/B STAT115 02/24/2009 * GenScan HMM model for gene structure Hexamer coding