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

$\endgroup$
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).

$\endgroup$
  • $\begingroup$ @QianHuang you're welcome. $\endgroup$ – dontloo Oct 17 '16 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 Oct 17 '16 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 Oct 17 '16 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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