I am trying to study hidden conditional random fields but I still have some fundamental questions about those methods. I would be immensely grateful if someone could provide some clarification over the notation used on most papers about the topic.

In several papers the most common form of the the HCRF model is given as:

$p(w|o;\theta) = \frac{1}{z(o; \theta)} \sum_{s} \exp{ \Psi(w, s, o; \theta) } $

In which $\theta$ is the parameter vector, $w$ is the class label, $o$ is the observation sequence, $s$ is the hidden state sequence and $\Psi$ is the potential function. However, I still could't figure out what $s$ means. Is it just a sequence of integer numbers, or is it actually a sequence of nodes in a graph? How one actually computes this summation?

Most papers I have read mention only that each $s_i \in S$ captures certain underlying structure of each class ($S$ being the set of hidden states in the model). But I still couldn't figure out what this actually means.

  • $\begingroup$ not a full answer, but what may help you is to "go backwards" and learn a more basic model, and then how this one "generalises" that more basic model. You may need to do this in several steps. do you get to choose $S$? like in a mixture model? This does look like a mixture model, where each "s" defines a "component". Kind of like saying "I have $S$ models, but I don't know the state which each individual observation is in. So I will average over these states" $\endgroup$ – probabilityislogic Mar 10 '11 at 11:17

I've posted my question in another site, where I also didn't receive the answer I was looking for. I answered my own question there and I decided to answer my own question here as well: In the case of a linear chain HCRF, the hidden state sequences are calculated in exactly the same way as in hidden Markov models.

The HCRF formulation using maximal cliques generalizes much of the structure of a general hidden Markov classifier. Hidden Markov classifiers are generally constructed by considering priors over each possible model and estimating the class label by computing its posterior probabilities. If we represent each model by a clique potential function, and restrict each potential function to a single class label, we can reproduce this exact structure in a HCRF. The only difference will be that parameters in a HCRF will not be constrained to probabilities, so we can also see that all possible solutions given by Markov classifiers are just a subset of the possible solutions given by HCRFs.

By the way, the summation I was referring to in the original question is intractable to compute in its given form. Since it represents the result of the potential function over all possible paths, in the case of a linear chain, instead of trying to compute this summation directly, we can proceed by computing the probability of each state/transition occurring in the model and multiplying this probability by the results of the potential function along those states/transitions in a single pass using the sum-product algorithm.

The model also does not need to be computed using EM. Since its gradient is readily available, one can just use any off-the-shelf function optimizer to do the job. Conjugate gradient or stochastic gradient updates seems to operate better since they can deal better with violations of convexity.

Please someone correct me if I got anything wrong. The best resource I have found so far to help understand CRFs and HCRFs (which are just CRFs with latent variables) has been this tutorial by C. Sutton. I hope it could be of some help for others also having the same questions.


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.