32
$\begingroup$

I understand that HMMs (Hidden Markov Models) are generative models, and CRF are discriminative models. I also understand how CRFs (Conditional Random Fields) are designed and used. What I do not understand is how they are different from HMMs? I read that in the case of HMM, we can only model our next state on the previous node, current node, and transition probability, but in the case of CRFs we can do this and can connect an arbitrary number of nodes together to form dependencies or contexts? Am I correct here?

$\endgroup$
  • 2
    $\begingroup$ You should probably spell out HMM and CRF; acronyms can be tricky, especially for people who are not native English speakers. $\endgroup$ – Peter Flom May 6 '13 at 0:17
  • $\begingroup$ Readers of this comment may not like this answer, but if you really need to know the answer to this, the best way to understand is to read the papers yourself and form your own opinion. This takes a lot of time, but it's the only way to truly know what's going on and to be able to tell whether other people are telling you the truth $\endgroup$ – frank Jan 25 at 2:57
23
$\begingroup$

From McCallum's introduction to CRFs:

enter image description here

$\endgroup$
  • 4
    $\begingroup$ would you care to add your own intuition/insight/understanding to this - even if just pointing out the highlights (from your perspective)? $\endgroup$ – javadba Jan 14 '18 at 22:54
10
$\begingroup$

"Conditional Random Fields can be understood as a sequential extension to the Maximum Entropy Model". This sentence is from a technical report related to "Classical Probabilistic Models and Conditional Random Fields".

It is probably the best read for topics such as HMM, CRF and Maximum Entropy.

PS: Figure 1 in the link gives a very good comparison between them.

Regards,

$\endgroup$
4
$\begingroup$

As a side note: I would kindly ask you to maintain this (incomplete) list so that interested users have an easily accessible resource. The status quo still requires individuals to investigate a lot of papers and/or long technical reports for finding answers related to CRFs and HMMs.

In addition to the other, already good answers, I want to point out the distinctive features I find most noteworthy:

  • HMMs are generative models which try to model the joint distribution P(y,x). Therefore, such models try to model the distribution of the data P(x) which in turn might impose highly dependent features. These dependencies are sometimes undesirable (e.g. in NLP's POS tagging) and very often intractable to model/compute.
  • CRFs are discriminative models which model P(y|x). As such, they do not require to explicitly model P(x) and depending on the task, might therefore yield higher performance, in part because they need fewer parameters to be learned, e.g. in settings when generating samples is not desired. Discriminative models are often more suitable when complex and overlapping features are used (since modelling their distribution is often hard).
  • If you have such overlapping/complex features (as in POS tagging) you might want to consider CRFs since they can model these with their feature functions (keep in mind that you will usually have to feature-engineer these functions).
  • In general, CRFs are more powerful than HMMs due to their application of feature functions. For example, you can model functions like 1($y_t$=NN, $x_t$=Smith, $cap(x_{t-1})$=true) whereas in (first-order) HMMs you use the Markov assumption, imposing a dependency only to the previous element. I therefore see CRFs as a generalization of HMMs.
  • Also note the difference between between linear and general CRFs. Linear CRFs, like HMMs, only impose dependencies on the previous element whereas with general CRFs you can impose dependencies to arbitrary elements (e.g. the first element is accessed in the very end of a sequence).
  • In practice, you will see linear CRFs more often than general CRFs since they usually allow easier inference. In general, CRF inference is often intractable, leaving you with the only tractable option of approximate inference).
  • Inference in linear CRFs is done with the Viterbi algorithm as in HMMs.
  • Both HMMs and linear CRFs are typically trained with Maximum Likelihood techniques such as gradient descent, Quasi-Newton methods or for HMMs with Expectation Maximization techniques (Baum-Welch algorithm). If the optimization problems are convex, these methods all yield the optimal parameter set.
  • According to [1], the optimization problem for learning the linear CRF parameters is convex if all nodes have exponential family distributions and are observed during training.

[1] Sutton, Charles; McCallum, Andrew (2010), "An Introduction to Conditional Random Fields"

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