2
$\begingroup$

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:

enter image description here enter image description here

Ref: https://github.com/taku910/crfpp/issues/30#issuecomment-213297301

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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).

Improve this answer
$\endgroup$
3
  • $\begingroup$ @QianHuang you're welcome. $\endgroup$
    – dontloo
    Commented Oct 17, 2016 at 6:35
  • $\begingroup$ @dontllo Since the beta is actually beta', and it should subtract the cost in calcExpectation(github.com/taku910/crfpp/blob/master/node.cpp#L35). But one more question I have is why it does not subtract the cost in calcExpectation(github.com/taku910/crfpp/blob/master/path.cpp#L15) as the beta is also beta' in that place. $\endgroup$
    – Qian Huang
    Commented Oct 17, 2016 at 6:48
  • $\begingroup$ @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. $\endgroup$
    – dontloo
    Commented Oct 17, 2016 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.