\hypertarget{group__gHMM}{
\subsection{Generic hidden Markov model solver.}
\label{group__gHMM}\index{Generic hidden Markov model solver.@{Generic hidden Markov model solver.}}
}


The notation follows `A tutorial on hidden Markov models and selected applications in speech recognition', Rabiner, 1989.  


\subsubsection*{Functions}
\begin{DoxyCompactItemize}
\item 
{\footnotesize template$<$int States, class Btype , class Otype $>$ }\\std::tr1::tuple$<$ double, TooN::Vector$<$ Btype::NumParameters $>$, TooN::Matrix$<$ Btype::NumParameters $>$ $>$ \hyperlink{group__gHMM_gad8e396017fa83143c23cef23eb7aa52a}{forward\_\-algorithm\_\-hessian} (TooN::Matrix$<$ States $>$ A, TooN::Vector$<$ States $>$ pi, const Btype \&B, const std::vector$<$ Otype $>$ \&O, bool compute\_\-deriv=1, bool compute\_\-hessian=1)
\item 
{\footnotesize template$<$int States, class Btype , class Otype $>$ }\\double \hyperlink{group__gHMM_ga15931236a398994295355281ab9d3aad}{forward\_\-algorithm} (TooN::Matrix$<$ States $>$ A, TooN::Vector$<$ States $>$ pi, const Btype \&B, const std::vector$<$ Otype $>$ \&O)
\item 
{\footnotesize template$<$int States, class Btype , class Otype $>$ }\\std::pair$<$ double, TooN::Vector$<$ Btype::NumParameters $>$ $>$ \hyperlink{group__gHMM_ga930d55cd3b8449c37365608136c01f6b}{forward\_\-algorithm\_\-deriv} (TooN::Matrix$<$ States $>$ A, TooN::Vector$<$ States $>$ pi, const Btype \&B, const std::vector$<$ Otype $>$ \&O)
\item 
{\footnotesize template$<$int States, class Btype , class Otype $>$ }\\std::vector$<$ std::tr1::array$<$ double, States $>$ $>$ \hyperlink{group__gHMM_ga7ad792b5840a0d87cf09b3ca1f965b25}{forward\_\-algorithm\_\-delta} (TooN::Matrix$<$ States $>$ A, TooN::Vector$<$ States $>$ pi, const Btype \&B, const std::vector$<$ Otype $>$ \&O)
\item 
{\footnotesize template$<$int States, class Btype , class Otype $>$ }\\void \hyperlink{group__gHMM_ga4b8c925bc5dce88e8360e7fb6d3eeba3}{forward\_\-algorithm\_\-delta2} (TooN::Matrix$<$ States $>$ A, TooN::Vector$<$ States $>$ pi, const Btype \&B, const std::vector$<$ Otype $>$ \&O, std::vector$<$ std::tr1::array$<$ double, States $>$ $>$ \&delta)
\item 
{\footnotesize template$<$int States, class Btype , class Otype $>$ }\\std::pair$<$ std::vector$<$ std::tr1::array$<$ double, States $>$ $>$, std::vector$<$ std::tr1::array$<$ double, States $>$ $>$ $>$ \hyperlink{group__gHMM_gae3026a883d9181ca6d0a45f2b90907cb}{forward\_\-backward\_\-algorithm} (TooN::Matrix$<$ States $>$ A, TooN::Vector$<$ States $>$ pi, const Btype \&B, const std::vector$<$ Otype $>$ \&O)
\item 
{\footnotesize template$<$class A , class Rng $>$ }\\int \hyperlink{group__gHMM_ga9e09dfeb90185e6608812cfa02685649}{select\_\-random\_\-element} (const A \&v, const double scale, Rng \&rng)
\item 
{\footnotesize template$<$int N, class Rng $>$ }\\int \hyperlink{group__gHMM_ga48e8bcf73f2d3d195aa2bd00dc341680}{sample\_\-unscaled\_\-log} (std::tr1::array$<$ double, N $>$ a, Rng \&rng)
\item 
{\footnotesize template$<$int States, class StateType , class Rng $>$ }\\std::vector$<$ StateType $>$ \hyperlink{group__gHMM_ga225966a4ff18994642fb6fc0a88fca1f}{backward\_\-sampling} (TooN::Matrix$<$ States $>$ A, const std::vector$<$ std::tr1::array$<$ double, States $>$ $>$ \&delta, Rng \&rng)
\end{DoxyCompactItemize}


\subsubsection{Detailed Description}
The notation follows `A tutorial on hidden Markov models and selected applications in speech recognition', Rabiner, 1989. 

\subsubsection{Function Documentation}
\hypertarget{group__gHMM_gad8e396017fa83143c23cef23eb7aa52a}{
\index{Generic hidden Markov model solver.@{Generic hidden Markov model solver.}!forward\_\-algorithm\_\-hessian@{forward\_\-algorithm\_\-hessian}}
\index{forward\_\-algorithm\_\-hessian@{forward\_\-algorithm\_\-hessian}!Generic hidden Markov model solver.@{Generic hidden Markov model solver.}}
\paragraph[{forward\_\-algorithm\_\-hessian}]{\setlength{\rightskip}{0pt plus 5cm}template$<$int States, class Btype , class Otype $>$ std::tr1::tuple$<$double, TooN::Vector$<$Btype::NumParameters$>$, TooN::Matrix$<$Btype::NumParameters$>$ $>$ forward\_\-algorithm\_\-hessian (
\begin{DoxyParamCaption}
\item[{TooN::Matrix$<$ States $>$}]{A, }
\item[{TooN::Vector$<$ States $>$}]{pi, }
\item[{const Btype \&}]{B, }
\item[{const std::vector$<$ Otype $>$ \&}]{O, }
\item[{bool}]{compute\_\-deriv = {\ttfamily 1}, }
\item[{bool}]{compute\_\-hessian = {\ttfamily 1}}
\end{DoxyParamCaption}
)}}
\label{group__gHMM_gad8e396017fa83143c23cef23eb7aa52a}


The forward algorithm is defined as: \begin{align} \alpha_1(i) &= \pi_i b_i(O_1) \\ \alpha_t(j) &= b_j(O(t)) \sum_i \alpha_{t-1}(i) a_{ij} \end{align} And the probability of observing the data is just: \begin{equation} P(O_1 \cdots O_T|\lambda) = P(O|\lambda) \sum_i \alpha_T(i), \end{equation} where the state, $\lambda = \{ A, \pi, B \}$. 

All multipliers are much less than 1, to $\alpha$ rapidly ends up as zero. Instead, store the logarithm: \begin{align} \delta_t(i) &= \ln \alpha_t(i) \\ \delta_1(i) &= \ln \pi_i + \ln b_j(O_t) \end{align} and the recursion is: \begin{align} \delta_t(j) &= \ln b_j(O_t) + \ln \sum_i \alpha_{t-1}(i) a_{ij} \\ &= \ln b_j(O_t) + \ln \sum_i e^{\delta_{t-1}(i) + \ln a_{ij}} \\ \end{align} including an arbitrary constant, $Z_t(j)$ gives: \begin{align} \delta_t(j) &= \ln b_j(O_t) + \ln \sum_i e^{Z_t(j)} e^{\delta_{t-1}(i) + \ln a_{ij} - Z_t(j)} \\ &= \ln b_j(O_t) + Z_t(j) + \ln \sum_i e^{\delta_{t-1}(i) + \ln a_{ij} - Z_t(j)}. \end{align} In order to prevent a loss of scale on the addition: \begin{equation} Z_t(j) \overset{\text{def}}{=} \operatorname*{max}_i \delta_{t-1}(i) + \ln a_{ij}, \end{equation} so the largest exponent will be exactly 0. The final log probability is, similarly: \begin{equation} \ln P(O|\lambda) = Z + \ln \sum_i e^{\delta_T(i) - Z}, \end{equation} {\itshape Z\/} can take any value, but to keep the numbers within a convenient range: \begin{equation} Z \overset{\text{def}}{=} \operatorname*{max}_i \delta_T(i). \end{equation}

For computing derivatives, two useful results are: \begin{align} \PD{}{x} \ln f(x) &= \frac{f'(x)}{f(x)}\\ \PD{}{x} e^{f(x)} &= f'(x) e^{f(x)} \end{align} There are {\itshape M\/} parameters of {\itshape B\/}, denoted $\phi_1 \ldots \phi_M$. The derivatives of {\itshape P\/} are: \begin{align} \DD P(O|\lambda) &= \SSum \DD e^{\delta_T(i)} \\ &= \SSum e^{\delta_T(i)} \DD \delta_T(i)\\ \end{align} Taking derivatives of $ \ln P$ and rearranging to get numerically more convenient results gives: \begin{align} \DD \ln P(O|\lambda) & = \frac{\DD P(O|\lambda)}{P(O|\lambda)} \\ & = \frac{\SSum e^{\delta_T(i)} \DD \delta_T(i)}{P(O|\lambda)}\\ & = \SSum e^{\delta_T(i) - \ln P(O|\lambda)} \DD \delta_T(i) \end{align} The derivarives of $\delta$ are: \begin{align} \gdef\dtj{\delta_T(j)} \PD{\dtj}{\en} &= \DD \ln \left[ b_j(O_t) \SSum e^{\delta_{t-1}(i) + \ln a_{ij}} \right] \\ &= \DD \left[ \ln b_j(O_t) \right] + \frac{\SSum \DD e^{\delta_{t-1}(i) + \ln a_{ij}}}{\SSum e^{\delta_{t-1}(i) + \ln a_{ij}}}\\ \underset{\text{\tt diff\_delta[t][j]}}{\underbrace{\PD{\dtj}{\en}}} &= \underset{\text{\tt B.diff\_log(j, O[t])}}{\underbrace{\DD \left[ \ln b_j(O_t) \right]}} + \frac{\overset{\text{\tt sum\_top}}{\overbrace{\SSum e^{\delta_{t-1}(i) + \ln a_{ij} - Z_t(j)} \DD \delta_{t-1}(i)}} }{\underset{\text{\tt sum}}{\underbrace{\SSum e^{\delta_{t-1}(i) + \ln a_{ij} -Z_t(j)}}}}, \end{align} with $Z_t(j)$ as defined in \hyperlink{group__gHMM_ga15931236a398994295355281ab9d3aad}{forward\_\-algorithm}.

For computing second derivatives, with $\Grad$ yielding column vectors, two useful results are: \begin{align} \Hess \ln f(\Vec{x}) & = \frac{\Hess f(\Vec{x})}{f(\Vec{x})} - \Grad f(\Vec{x}) \Grad f(\Vec{x})\Trn \\ \Hess e^f(\Vec{x}) & = e^{f(\Vec{x})}(\Grad f(\Vec{x}) \Grad f(\Vec{x})\Trn + \Hess f(\Vec{x})), \end{align} therefore: \begin{equation} \Hess \ln P(O|\lambda) = \frac{\Hess f(\Vec{x})}{P(O|\lambda)} - \Grad P(O|\lambda) \Grad P(O|\lambda)\Trn, \end{equation} and: \begin{equation} \Hess P(O|\lambda) = \sum_i e^{\delta_t(i) - \ln P(O|\lambda)}\left[ \Grad\delta_t \Grad\delta_t\Trn + \Hess \delta_t\right]. \end{equation} Define $s_t(j)$ as: \begin{equation} s_t(j) = \sum_i e^{\delta_{t-1}(j) + \ln a_{ij}} \end{equation} so that: \begin{equation} \delta_t(j) = \ln b_j(O_t) + \ln s_t(j). \end{equation} The derivatives and Hessian recursion are therefore: \begin{align} \Grad \delta_t(j) &= \Grad\ln b_j(O_t) + \frac{\Grad s_t(j)}{s_t(j)} \\ \Hess \delta_t(j) &= \Hess\ln b_j(O_t) + \frac{\Hess s_t(j)}{s_t(j)} - \frac{\Grad s_t(j)}{s_t(j)}\frac{\Grad s_t(j)}{s_t(j)}\Trn.\\ &= \underset{\text{\tt B.hess\_log(j, O[t])}}{\underbrace{\Hess\ln b_j(O_t)}} + \frac{ \overset{\text{\tt sum\_top2}}{ \overbrace{ \sum_i e^{\delta_{t-1}(j) + \ln a_{ij} - Z_t(j)}\left[\Hess\delta_{t-1}(i) + \Grad\delta_{t-1}(i)\Grad\delta_{t-1}(i)\Trn\right]}} }{\text{\tt sum}} - \frac{\text{\tt sum\_top sum\_top}\Trn}{\text{\tt sum}^2} \end{align}


\begin{DoxyParams}{Parameters}
{\em A} & {\itshape A:\/} State transition probabilities. \\
\hline
{\em pi} & {\itshape $\pi$\/}: initial state probabilities. \\
\hline
{\em O} & {\itshape O\/} or {\itshape I:\/} the observed data (ie the images). \\
\hline
{\em B} & $B$: A function object giving the (log) probability of an observation given a state, and derivatives with respect to the parameters. \\
\hline
{\em compute\_\-deriv} & Whether to compute the derivative, or return zero. \\
\hline
{\em compute\_\-hessian} & Whether to compute the Hessian, or return zero. This implies {\ttfamily compute\_\-deriv}. \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
the log probability of observing all the data, and the derivatives of the log probability with respect to the parameters, and the Hessian. 
\end{DoxyReturn}


Definition at line 153 of file forward\_\-algorithm.h.



References ln().



Referenced by forward\_\-algorithm\_\-deriv(), sampled\_\-background\_\-spot\_\-hessian2(), and sampled\_\-background\_\-spot\_\-hessian\_\-FAKE().


\begin{DoxyCode}
{
    using namespace TooN;
    using namespace std;
    using namespace std::tr1;

    if(compute_hessian == 1)
        compute_deriv=1;

    static const int M = Btype::NumParameters;
    int states = pi.size();
    
    //delta[j][i] = delta_t(i)
    vector<array<double, States> > delta(O.size());

    //diff_delta[t][j][n] = d/de_n delta_t(j)
    vector<array<Vector<M>,States > > diff_delta(O.size());
    
    
    //hess_delta[t][j][m][n] = d2/de_n de_m delta_t(j)
    vector<array<Matrix<M>,States > > hess_delta(O.size());
    
    //Initialization: Eqn 19, P 262
    //Set initial partial log probabilities:
    for(int i=0; i < states; i++)
    {
        delta[0][i] = ln(pi[i]) + B.log(i, O[0]);
        
        if(compute_deriv)
            diff_delta[0][i] = B.diff_log(i, O[0]);

        if(compute_hessian)
            hess_delta[0][i] = B.hess_log(i, O[0]);
    }

    //Perform the recursion: Eqn 20, P262
    //Note, use T and T-1. Rather than  T+1 and T.
    for(unsigned int t=1; t < O.size(); t++)
    {   
        for(int j=0; j < states; j++)
        {
            double Ztj = -HUGE_VAL; //This is Z_t(j)
            for(int i=0; i < states; i++)
                Ztj = max(Ztj, delta[t-1][i] + ln(A[i][j]));

            double sum=0;
            for(int i=0; i < states; i++)
                sum += exp(delta[t-1][i] + ln(A[i][j]) - Ztj);

            delta[t][j] = B.log(j, O[t]) + Ztj + ln(sum);

            if(compute_deriv)
            {
                Vector<M> sum_top = Zeros;
                for(int i=0; i < states; i++)
                    sum_top += diff_delta[t-1][i] * exp(delta[t-1][i] + ln(A[i][j
      ]) - Ztj);

                diff_delta[t][j] = B.diff_log(j, O[t]) +  (sum_top) / sum;
                
                if(compute_hessian)
                {
                    Matrix<M> sum_top2 = Zeros;
                    for(int i=0; i < states; i++)
                        sum_top2 += exp(delta[t-1][i] + ln(A[i][j]) - Ztj) * ( he
      ss_delta[t-1][i] + diff_delta[t-1][i].as_col() * diff_delta[t-1][i].as_row());
                    
                    hess_delta[t][j] = B.hess_log(j, O[t]) + sum_top2 / sum - sum
      _top.as_col() * sum_top.as_row() / (sum*sum);
                }
            }
        }
    }

    //Compute the log prob using normalization
    double Z = -HUGE_VAL;
    for(int i=0; i < states; i++)
        Z = max(Z, delta.back()[i]);

    double sum =0;
    for(int i=0; i < states; i++)
        sum += exp(delta.back()[i] - Z);

    double log_prob = Z  + ln(sum);

    //Compute the differential of the log
    Vector<M> diff_log = Zeros;
    //Compute the differential of the log using normalization
    //The convenient normalizer is ln P(O|lambda) which makes the bottom 1.
    for(int i=0; compute_deriv && i < states; i++)
        diff_log += exp(delta.back()[i] - log_prob)*diff_delta.back()[i];

    Matrix<M> hess_log = Zeros;
    //Compute the hessian of the log using normalization
    //The convenient normalizer is ln P(O|lambda) which makes the bottom 1.
    for(int i=0; compute_hessian && i < states; i++)
        hess_log += exp(delta.back()[i] - log_prob) * (hess_delta.back()[i] + dif
      f_delta.back()[i].as_col() * diff_delta.back()[i].as_row());

    hess_log -= diff_log.as_col() * diff_log.as_row();

    //Compute the differential of the Hessian
    return  make_tuple(log_prob, diff_log, hess_log);
}
\end{DoxyCode}
\hypertarget{group__gHMM_ga15931236a398994295355281ab9d3aad}{
\index{Generic hidden Markov model solver.@{Generic hidden Markov model solver.}!forward\_\-algorithm@{forward\_\-algorithm}}
\index{forward\_\-algorithm@{forward\_\-algorithm}!Generic hidden Markov model solver.@{Generic hidden Markov model solver.}}
\paragraph[{forward\_\-algorithm}]{\setlength{\rightskip}{0pt plus 5cm}template$<$int States, class Btype , class Otype $>$ double forward\_\-algorithm (
\begin{DoxyParamCaption}
\item[{TooN::Matrix$<$ States $>$}]{A, }
\item[{TooN::Vector$<$ States $>$}]{pi, }
\item[{const Btype \&}]{B, }
\item[{const std::vector$<$ Otype $>$ \&}]{O}
\end{DoxyParamCaption}
)}}
\label{group__gHMM_ga15931236a398994295355281ab9d3aad}


Run the forward algorithm and return the log probability. 


\begin{DoxyParams}{Parameters}
{\em A} & {\itshape A:\/} State transition probabilities. \\
\hline
{\em pi} & {\itshape $\pi$\/}: initial state probabilities. \\
\hline
{\em O} & {\itshape O\/} or {\itshape I:\/} the observed data (ie the images). \\
\hline
{\em B} & $B$: A function object giving the (log) probability of an observation given a state. \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
the log probability of observing all the data. 
\end{DoxyReturn}


Definition at line 263 of file forward\_\-algorithm.h.



References ln().


\begin{DoxyCode}
{
    using namespace TooN;
    using namespace std;
    using namespace std::tr1;

    int states = pi.size();
    
    //delta[j][i] = delta_t(i)
    vector<array<double, States> > delta(O.size());

    //Initialization: Eqn 19, P 262
    //Set initial partial log probabilities:
    for(int i=0; i < states; i++)
        delta[0][i] = ln(pi[i]) + B.log(i, O[0]);

    //Perform the recursion: Eqn 20, P262
    //Note, use T and T-1. Rather than  T+1 and T.
    for(unsigned int t=1; t < O.size(); t++)
    {   
        for(int j=0; j < states; j++)
        {
            double Ztj = -HUGE_VAL; //This is Z_t(j)
            for(int i=0; i < states; i++)
                Ztj = max(Ztj, delta[t-1][i] + ln(A[i][j]));

            double sum=0;
            for(int i=0; i < states; i++)
                sum += exp(delta[t-1][i] + ln(A[i][j]) - Ztj);

            delta[t][j] = B.log(j, O[t]) + Ztj + ln(sum);
        }
    }

    //Compute the log prob using normalization
    double Z = -HUGE_VAL;
    for(int i=0; i < states; i++)
        Z = max(Z, delta.back()[i]);

    double sum =0;
    for(int i=0; i < states; i++)
        sum += exp(delta.back()[i] - Z);

    double log_prob = Z  + ln(sum);

    return  log_prob;
}
\end{DoxyCode}
\hypertarget{group__gHMM_ga930d55cd3b8449c37365608136c01f6b}{
\index{Generic hidden Markov model solver.@{Generic hidden Markov model solver.}!forward\_\-algorithm\_\-deriv@{forward\_\-algorithm\_\-deriv}}
\index{forward\_\-algorithm\_\-deriv@{forward\_\-algorithm\_\-deriv}!Generic hidden Markov model solver.@{Generic hidden Markov model solver.}}
\paragraph[{forward\_\-algorithm\_\-deriv}]{\setlength{\rightskip}{0pt plus 5cm}template$<$int States, class Btype , class Otype $>$ std::pair$<$double, TooN::Vector$<$Btype::NumParameters$>$ $>$ forward\_\-algorithm\_\-deriv (
\begin{DoxyParamCaption}
\item[{TooN::Matrix$<$ States $>$}]{A, }
\item[{TooN::Vector$<$ States $>$}]{pi, }
\item[{const Btype \&}]{B, }
\item[{const std::vector$<$ Otype $>$ \&}]{O}
\end{DoxyParamCaption}
)}}
\label{group__gHMM_ga930d55cd3b8449c37365608136c01f6b}


Run the forward algorithm and return the log probability and its derivatives. 


\begin{DoxyParams}{Parameters}
{\em A} & {\itshape A:\/} State transition probabilities. \\
\hline
{\em pi} & {\itshape $\pi$\/}: initial state probabilities. \\
\hline
{\em O} & {\itshape O\/} or {\itshape I:\/} the observed data (ie the images). \\
\hline
{\em B} & $B$: A function object giving the (log) probability of an observation given a state, and derivatives with respect to the parameters. \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
the log probability of observing all the data. 
\end{DoxyReturn}


Definition at line 321 of file forward\_\-algorithm.h.



References forward\_\-algorithm\_\-hessian().



Referenced by SpotNegProbabilityDiffWithSampledBackground::operator()().


\begin{DoxyCode}
{
    using namespace std::tr1;
    double p;
    TooN::Vector<Btype::NumParameters> v;
    tie(p,v, ignore) = forward_algorithm_hessian(A, pi, B, O, 1, 0);
    return make_pair(p,v);
}
\end{DoxyCode}
\hypertarget{group__gHMM_ga7ad792b5840a0d87cf09b3ca1f965b25}{
\index{Generic hidden Markov model solver.@{Generic hidden Markov model solver.}!forward\_\-algorithm\_\-delta@{forward\_\-algorithm\_\-delta}}
\index{forward\_\-algorithm\_\-delta@{forward\_\-algorithm\_\-delta}!Generic hidden Markov model solver.@{Generic hidden Markov model solver.}}
\paragraph[{forward\_\-algorithm\_\-delta}]{\setlength{\rightskip}{0pt plus 5cm}template$<$int States, class Btype , class Otype $>$ std::vector$<$std::tr1::array$<$double, States$>$ $>$ forward\_\-algorithm\_\-delta (
\begin{DoxyParamCaption}
\item[{TooN::Matrix$<$ States $>$}]{A, }
\item[{TooN::Vector$<$ States $>$}]{pi, }
\item[{const Btype \&}]{B, }
\item[{const std::vector$<$ Otype $>$ \&}]{O}
\end{DoxyParamCaption}
)}}
\label{group__gHMM_ga7ad792b5840a0d87cf09b3ca1f965b25}


Run the forward algorithm and return the log partials (delta) 


\begin{DoxyParams}{Parameters}
{\em A} & {\itshape A:\/} State transition probabilities. \\
\hline
{\em pi} & {\itshape $\pi$\/}: initial state probabilities. \\
\hline
{\em O} & {\itshape O\/} or {\itshape I:\/} the observed data (ie the images). \\
\hline
{\em B} & $B$: A function object giving the (log) probability of an observation given a state, and derivatives with respect to the parameters. \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
the log probability of observing all the data. 
\end{DoxyReturn}


Definition at line 342 of file forward\_\-algorithm.h.



References ln().



Referenced by forward\_\-backward\_\-algorithm(), SampledMultispot::GibbsSampler::next(), and sampled\_\-background\_\-spot\_\-hessian\_\-ffbs().


\begin{DoxyCode}
{
    using namespace TooN;
    using namespace std;
    using namespace std::tr1;

    int states = pi.size();
    
    //delta[j][i] = delta_t(i)
    vector<array<double, States> > delta(O.size());

    //Initialization: Eqn 19, P 262
    //Set initial partial log probabilities:
    for(int i=0; i < states; i++)
        delta[0][i] = ln(pi[i]) + B.log(i, O[0]);

    //Forward pass...
    //Perform the recursion: Eqn 20, P262
    //Note, use T and T-1. Rather than  T+1 and T.
    for(unsigned int t=1; t < O.size(); t++)
    {   
        for(int j=0; j < states; j++)
        {
            double Ztj = -HUGE_VAL; //This is Z_t(j)
            for(int i=0; i < states; i++)
                Ztj = max(Ztj, delta[t-1][i] + ln(A[i][j]));

            double sum=0;
            for(int i=0; i < states; i++)
                sum += exp(delta[t-1][i] + ln(A[i][j]) - Ztj);

            delta[t][j] = B.log(j, O[t]) + Ztj + ln(sum);
        }
    }

    return delta;
}
\end{DoxyCode}
\hypertarget{group__gHMM_ga4b8c925bc5dce88e8360e7fb6d3eeba3}{
\index{Generic hidden Markov model solver.@{Generic hidden Markov model solver.}!forward\_\-algorithm\_\-delta2@{forward\_\-algorithm\_\-delta2}}
\index{forward\_\-algorithm\_\-delta2@{forward\_\-algorithm\_\-delta2}!Generic hidden Markov model solver.@{Generic hidden Markov model solver.}}
\paragraph[{forward\_\-algorithm\_\-delta2}]{\setlength{\rightskip}{0pt plus 5cm}template$<$int States, class Btype , class Otype $>$ void forward\_\-algorithm\_\-delta2 (
\begin{DoxyParamCaption}
\item[{TooN::Matrix$<$ States $>$}]{A, }
\item[{TooN::Vector$<$ States $>$}]{pi, }
\item[{const Btype \&}]{B, }
\item[{const std::vector$<$ Otype $>$ \&}]{O, }
\item[{std::vector$<$ std::tr1::array$<$ double, States $>$ $>$ \&}]{delta}
\end{DoxyParamCaption}
)}}
\label{group__gHMM_ga4b8c925bc5dce88e8360e7fb6d3eeba3}


Run the forward algorithm and return the log partials (delta) 


\begin{DoxyParams}{Parameters}
{\em A} & {\itshape A:\/} State transition probabilities. \\
\hline
{\em pi} & {\itshape $\pi$\/}: initial state probabilities. \\
\hline
{\em O} & {\itshape O\/} or {\itshape I:\/} the observed data (ie the images). \\
\hline
{\em B} & $B$: A function object giving the (log) probability of an observation given a state, and derivatives with respect to the parameters. \\
\hline
{\em delta} & the $\delta$ values \\
\hline
\end{DoxyParams}


Definition at line 390 of file forward\_\-algorithm.h.



References ln().


\begin{DoxyCode}
{
    using namespace TooN;
    using namespace std;
    using namespace std::tr1;

    int states = pi.size();
    
    //delta[j][i] = delta_t(i)
    delta.resize(O.size());

    //Initialization: Eqn 19, P 262
    //Set initial partial log probabilities:
    for(int i=0; i < states; i++)
        delta[0][i] = ln(pi[i]) + B.log(i, O[0]);

    Matrix<States> lA;
    for(int r=0; r < States; r++)
        for(int c=0; c < States; c++)
            lA[r][c] = ln(A[r][c]);

    //Forward pass...
    //Perform the recursion: Eqn 20, P262
    //Note, use T and T-1. Rather than  T+1 and T.
    for(unsigned int t=1; t < O.size(); t++)
    {   
        for(int j=0; j < states; j++)
        {
            double Ztj = -HUGE_VAL; //This is Z_t(j)
            for(int i=0; i < states; i++)
                Ztj = max(Ztj, delta[t-1][i] + lA[i][j]);

            double sum=0;
            for(int i=0; i < states; i++)
                sum += exp(delta[t-1][i] + lA[i][j] - Ztj);

            delta[t][j] = B.log(j, O[t]) + Ztj + ln(sum);
        }
    }
}
\end{DoxyCode}
\hypertarget{group__gHMM_gae3026a883d9181ca6d0a45f2b90907cb}{
\index{Generic hidden Markov model solver.@{Generic hidden Markov model solver.}!forward\_\-backward\_\-algorithm@{forward\_\-backward\_\-algorithm}}
\index{forward\_\-backward\_\-algorithm@{forward\_\-backward\_\-algorithm}!Generic hidden Markov model solver.@{Generic hidden Markov model solver.}}
\paragraph[{forward\_\-backward\_\-algorithm}]{\setlength{\rightskip}{0pt plus 5cm}template$<$int States, class Btype , class Otype $>$ std::pair$<$std::vector$<$std::tr1::array$<$double, States$>$ $>$, std::vector$<$std::tr1::array$<$double, States$>$ $>$ $>$ forward\_\-backward\_\-algorithm (
\begin{DoxyParamCaption}
\item[{TooN::Matrix$<$ States $>$}]{A, }
\item[{TooN::Vector$<$ States $>$}]{pi, }
\item[{const Btype \&}]{B, }
\item[{const std::vector$<$ Otype $>$ \&}]{O}
\end{DoxyParamCaption}
)}}
\label{group__gHMM_gae3026a883d9181ca6d0a45f2b90907cb}


Run the forward-\/backwards algorithm and return the log partials (delta and epsilon). 


\begin{DoxyParams}{Parameters}
{\em A} & {\itshape A:\/} State transition probabilities. \\
\hline
{\em pi} & {\itshape $\pi$\/}: initial state probabilities. \\
\hline
{\em O} & {\itshape O\/} or {\itshape I:\/} the observed data (ie the images). \\
\hline
{\em B} & $B$: A function object giving the (log) probability of an observation given a state, and derivatives with respect to the parameters. \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
the log probability of observing all the data. 
\end{DoxyReturn}


Backward pass Epsilon is log beta 



Definition at line 443 of file forward\_\-algorithm.h.



References forward\_\-algorithm\_\-delta(), and ln().


\begin{DoxyCode}
{
    using namespace TooN;
    using namespace std;
    using namespace std::tr1;

    int states = pi.size();
    
    //delta[j][i] = delta_t(i)
    vector<array<double, States> > delta = forward_algorithm_delta(A, pi, B, O);

    ///Backward pass
    ///Epsilon is log beta
    vector<array<double, States> > epsilon(O.size());

    //Initialize beta to 1, ie epsilon to 0
    for(int i=0; i < states; i++)
        epsilon[O.size()-1][i] = 0;

    //Perform the backwards recursion
    for(int t=O.size()-2; t >= 0; t--)
    {
        for(int i=0; i < states; i++)
        {
            //Find a normalizing constant
            double Z = -HUGE_VAL;
            
            for(int j=0; j < states; j++)
                Z = max(Z, ln(A[i][j]) + B.log(j, O[t+1]) + epsilon[t+1][j]);
            
            double sum=0;
            for(int j= 0; j < states; j++)
                sum += exp(ln(A[i][j]) + B.log(j, O[t+1]) + epsilon[t+1][j] - Z);
      

            epsilon[t][i] = ln(sum) + Z;
        }
    }
    
    return make_pair(delta, epsilon);
}
\end{DoxyCode}
\hypertarget{group__gHMM_ga9e09dfeb90185e6608812cfa02685649}{
\index{Generic hidden Markov model solver.@{Generic hidden Markov model solver.}!select\_\-random\_\-element@{select\_\-random\_\-element}}
\index{select\_\-random\_\-element@{select\_\-random\_\-element}!Generic hidden Markov model solver.@{Generic hidden Markov model solver.}}
\paragraph[{select\_\-random\_\-element}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class A , class Rng $>$ int select\_\-random\_\-element (
\begin{DoxyParamCaption}
\item[{const A \&}]{v, }
\item[{const double}]{scale, }
\item[{Rng \&}]{rng}
\end{DoxyParamCaption}
)}}
\label{group__gHMM_ga9e09dfeb90185e6608812cfa02685649}


Select an element from the container v, assuming that v is a probability distribution over elements up to some scale. 


\begin{DoxyParams}{Parameters}
{\em v} & Uscaled probability distribution \\
\hline
{\em scale} & Scale of v \\
\hline
{\em rng} & Random number generator to use \\
\hline
\end{DoxyParams}


Definition at line 498 of file forward\_\-algorithm.h.



Referenced by sample\_\-unscaled\_\-log().


\begin{DoxyCode}
{
    double total=0, choice = rng()*scale;

    for(int i=0; i < (int)v.size(); i++)
    {
        total += v[i];  
        if(choice <= total)
            return i;
    }
    return v.size()-1;
}
\end{DoxyCode}
\hypertarget{group__gHMM_ga48e8bcf73f2d3d195aa2bd00dc341680}{
\index{Generic hidden Markov model solver.@{Generic hidden Markov model solver.}!sample\_\-unscaled\_\-log@{sample\_\-unscaled\_\-log}}
\index{sample\_\-unscaled\_\-log@{sample\_\-unscaled\_\-log}!Generic hidden Markov model solver.@{Generic hidden Markov model solver.}}
\paragraph[{sample\_\-unscaled\_\-log}]{\setlength{\rightskip}{0pt plus 5cm}template$<$int N, class Rng $>$ int sample\_\-unscaled\_\-log (
\begin{DoxyParamCaption}
\item[{std::tr1::array$<$ double, N $>$}]{a, }
\item[{Rng \&}]{rng}
\end{DoxyParamCaption}
)}}
\label{group__gHMM_ga48e8bcf73f2d3d195aa2bd00dc341680}


Select an element from the a, assuming that a stores unscaled log probabilities of the elements. 


\begin{DoxyParams}{Parameters}
{\em a} & Uscaled probability distribution, stored as logarithms. \\
\hline
{\em rng} & Random number generator to use \\
\hline
\end{DoxyParams}


Definition at line 516 of file forward\_\-algorithm.h.



References select\_\-random\_\-element().


\begin{DoxyCode}
{
    double hi = *max_element(a.begin(), a.end());
    double sum=0;

    for(unsigned int i=0; i < a.size(); i++)
    {
        a[i] = exp(a[i] - hi);
        sum += a[i];
    }

    return select_random_element(a, sum, rng);
}
\end{DoxyCode}
\hypertarget{group__gHMM_ga225966a4ff18994642fb6fc0a88fca1f}{
\index{Generic hidden Markov model solver.@{Generic hidden Markov model solver.}!backward\_\-sampling@{backward\_\-sampling}}
\index{backward\_\-sampling@{backward\_\-sampling}!Generic hidden Markov model solver.@{Generic hidden Markov model solver.}}
\paragraph[{backward\_\-sampling}]{\setlength{\rightskip}{0pt plus 5cm}template$<$int States, class StateType , class Rng $>$ std::vector$<$StateType$>$ backward\_\-sampling (
\begin{DoxyParamCaption}
\item[{TooN::Matrix$<$ States $>$}]{A, }
\item[{const std::vector$<$ std::tr1::array$<$ double, States $>$ $>$ \&}]{delta, }
\item[{Rng \&}]{rng}
\end{DoxyParamCaption}
)}}
\label{group__gHMM_ga225966a4ff18994642fb6fc0a88fca1f}


An implementation of the backwards sampling part of the forwards filtering/backwards sampling algorithm. 

See `Monte Carlo smoothing for non-\/linear time series', Godsill and Doucet, JASA 2004 
\begin{DoxyParams}{Parameters}
{\em A} & HMM transition matrix. \\
\hline
{\em delta} & Forward partial probabilities stored as logarithms. \\
\hline
{\em rng} & Random number generator to use \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
state at each time step. 
\end{DoxyReturn}


Definition at line 538 of file forward\_\-algorithm.h.



References ln().


\begin{DoxyCode}
{
    //Compute the elementwise log of A
    for(int r=0; r < A.num_rows(); r++)
        for(int c=0; c < A.num_cols(); c++)
            A[r][c] = ln(A[r][c]);

    std::vector<StateType> samples(delta.size());
    
    samples.back() = sample_unscaled_log<States, Rng>(delta.back(), rng);
    
    //A is A[t][t+1]

    for(int i=delta.size()-2; i >= 0; i--)
    {
        std::tr1::array<double, States> reverse_probabilities = delta[i];

        for(int j=0; j < States; j++)
            reverse_probabilities[j] += A[j][samples[i+1]];

        samples[i] = sample_unscaled_log<States, Rng>(reverse_probabilities, rng)
      ;
    }

    return samples;
}
\end{DoxyCode}
