ToolViterbi

computes path through a probability matrix with Viterbi
>
> @param P_E: emmission probability matrix (S X N)
> @param P_T: transition probability matrix (S X S)
> @param p_s: start probability vector (S X 1)
> @param bUseLogLikelihood: flag (default: false)
>
> @retval p path vector with matrix row indices (N)
> @retval P_res probability matrix
 ======================================================================

0001 %computes path through a probability matrix with Viterbi
0002 %>
0003 %> @param P_E: emmission probability matrix (S X N)
0004 %> @param P_T: transition probability matrix (S X S)
0005 %> @param p_s: start probability vector (S X 1)
0006 %> @param bUseLogLikelihood: flag (default: false)
0007 %>
0008 %> @retval p path vector with matrix row indices (N)
0009 %> @retval P_res probability matrix
0010 % ======================================================================
0011 function [p, P_res] = ToolViterbi(P_E, P_T, p_s, bUseLogLikelihood)
0012  
0013     if (nargin < 4)
0014         bUseLogLikelihood = false;
0015     end
0016         
0017     if (~bUseLogLikelihood)
0018         % initialization
0019         I  = zeros(size(P_E));
0020         P_res = zeros(size(P_E));
0021         P_res(:, 1) = P_E(:, 1) .* p_s;
0022 
0023         % recursion
0024         for n = 2:size(P_E, 2)
0025             for s = 1:size(P_E, 1)
0026                 % find max of preceding times trans prob
0027                 [p_max, I(s, n)] = max(P_res(:, n-1) .* P_T(:, s));
0028                 P_res(s, n) = P_E(s, n) * p_max;
0029             end
0030         end
0031     else
0032         % initialization
0033         P_E = log(P_E); % hope for non-zero entries
0034         P_T = log(P_T); % hope for non-zero entries
0035         p_s = log(p_s); % hope for non-zero entries
0036         I = zeros(size(P_E));
0037         P_res = zeros(size(P_E));
0038 
0039         P_res(:, 1) = P_E(:, 1) + p_s; 
0040     
0041         % recursion
0042         for n = 2:size(P_E, 2)
0043             for s = 1:size(P_E, 1)
0044                 % find max of preceding times trans prob
0045                 [p_max, I(s, n)] = max(P_res(:, n-1) + P_T(:, s));
0046                 P_res(s, n) = P_E(s, n) + p_max;
0047             end
0048         end
0049     end
0050         
0051     % traceback
0052     p = zeros(1,size(P_E, 2));  
0053     % start with the last element, then count down
0054     [prob, p(end)] = max(P_res(:, end));
0055     for n = size(P_E, 2)-1:-1:1
0056         p(n) = I(p(n+1), n+1);
0057     end   
0058 end