3
$\begingroup$

I have a question about the label bias problem in HMM and CRF.

I understand that HMM and MEMM suffer from the label bias problem, which is a preference for states with fewer transitions. The problem is due to the fact that in HMM and MEMM use local probabilities (each probability has to sum to 1), and thus, states with fewer transitions have a larger probability for its transitions. CRF alleviates this problem by global normalization, so that local potentials don't have to sum to 1.

What I am confused about is its relationship to I-equivalence between HMM/MEMM and CRF. Consider the following graphical models over variables $Y_{1:T}$ (where $X$ can be viewed as always given):

  • Directed graph $D$: $$Y_1\rightarrow Y_2\rightarrow\cdots\rightarrow Y_T $$
  • Undirected graph $G$: $$Y_1 - Y_2 - \cdots - Y_T $$

It's obvious that $D$ and $G$ have the same I-map, thus being I-equivalent.

In both cases, the inference objective is to find $$Y_{1:T}^*=\operatorname{argmax}_{Y_{1:T}} p(Y_1,\cdots, Y_T)$$ However, $D$ suffers from the label bias problem, whereas $G$ doesn't.

I am wondering if $G$ has a stronger power of modeling joint probabilities than $D$ (i.e., $D$'s hypothesis class is a subset of $G$) despite their I-equivalence.

I would appreciate any insight. Thanks.

$\endgroup$
1
  • $\begingroup$ A note: HMMs do not suffer from label bias. It's important to consider $X$ in the model, rather than taking it as given. It helps to inform why only MEMMs show label bias. $\endgroup$ – Arya McCarthy Mar 30 at 21:08
1
$\begingroup$

Expanding on my comment: the answer is clearer when you realize that you can't ignore the observed variables. They affect each model differently. As it turns out, the MEMM is not I-equivalent to the linear-chain CRF and HMM.

As a recap, the HMM looks like this:

y1 -> y2 -> y3 -> ... -> yn
 |     |     |            |
 v     v     v            v
x1    x2    x3           xn

The MEMM looks like this:

y1 -> y2 -> y3 -> ... -> yn
 ʌ     ʌ     ʌ            ʌ
 |     |     |            |
x1    x2    x3           xn

While the skeleton is the same, this has different immoralities than the HMM. (Note the v-structure at each $y_i$ for $i>1$; the HMM doesn't have immoralities.) That means that the MEMM's I-map is different from the HMM's I-map.

Finally, the linear-chain CRF.

y1 —— y2 —— y3 —— ... —— yn
 |     |     |            |
 |     |     |            |
x1    x2    x3           xn

This is I-equivalent to the HMM, but not to the MEMM. (Try moralizing both if you are not convinced.)


This website explains in depth why HMMs don't suffer from label bias, but MEMMs do. The MEMM always has one unit of probability mass to mete out among the choices for the next state (“conservation of score mass”; Bottou, 1991). In the HMM, the observation modulates how much mass there is to distribute. And, of course, the CRF is globally normalized; there's no constraint on the mass.

$\endgroup$

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.