# A Question on forward-backward algorithm in CRF++

I’m a beginner of CRF++. A question have plagued me for many days. I’m exhausted~

Why the code in calcBeta() is so like calcAlpha()?

You know they two are very different in original forward-backward algorithm of HMM:

Let's rewrite your formulas for short as $$\alpha_j(t)=\log(\sum_k\exp(\alpha_k(t-1)+g(s_j,s_k)))+h(s_j,x_t)$$ $$\beta_j(t)=\log(\sum_k\exp(\beta_k(t+1)+g(s_k,s_j)+h(s_k,x_{t+1})))$$ In $\beta_j$, we can not take the $h(s_k,x_{t+1})$ out of the parenthesis as in $\alpha_j$ because it is dependent of $k$. Therefore you're suggesting that calcBeta should be different from calcAlpha.
If we define $\beta'_j$ as $$\beta'_j(t)=\beta_j(t)+h(s_j,x_{t})$$ we'll get $$\beta'_j(t)=\log(\sum_k\exp(\beta_k(t+1)+g(s_k,s_j)+h(s_k,x_{t+1})))+h(s_j,x_{t})$$$$=\log(\sum_k\exp(\beta'_k(t+1)+g(s_k,s_j)))+h(s_j,x_{t})$$ which is in the same form as $\alpha_j$.
In fact the code is computing $\beta'_j(t_n)$, and that's why later in the calcExpectation function when computing the marginals it needs to subtract the additional $h(s_j,x_{t})$ term (cost).
• @QianHuang hi I'm not very familiar with the code, I suppose the other function is the marginal of a path, which is different of the marginal of a node. You can take a look at cs.columbia.edu/~mcollins/fb.pdf, the two marginals correspond to the $\mu(j,a)$ and $\mu(j,a,b)$ terms. – dontloo Oct 17 '16 at 7:28