Hidden states in hidden conditional random fields

This seems very, very interesting. Would this work as well as HCRFs in the recognition of continuous sequences (such as in speech recognition, or in the recognition of temporal signals in general)? Could you please summarize the advantages of your model over the later approach? I am still reading your paper. Thanks.

If I understood HCRFs correctly, a key difference between the two models is that HCRFs are assigning a single label to a time series/structured object, whereas hidden-unit CRFs assign a label to each node (like you would do in speech recognition, part-of-speech tagging etc.).

If you would have a HCRF with a hidden state sequence and a label sequence, inference would become intractable. Inference in hidden-unit CRFs is tractable because all hidden units are conditionally independent.

Another difference is in the type of hidden units. In HCRFs, you have a sequence of multinomial hidden units, so you'd have K^T possible hidden-unit states (with K the number of possible states, and T the time series length). The hidden-unit CRF has H binary hidden units for each frame, so a total number of (2^H)^T hidden states. In hidden-unit CRFs, however, the hidden states at time t do not influence the hidden states at time t+1.

If the transition weights in the hidden-unit CRF all have the same value, the model reduces to a sequence of discriminative RBMs. Discriminative RBMs have the theoretically interesting property that they are universal approximators of p(y|x) for discrete data x.

@Laurens: Nice work!

Traditionally CRFs are trained to maximize joint likelihood over the whole structure (marginalized likelihood in the case of hidden units), but there are formulations for optimizing per position loss as well. In my view any kind of conditional undirected graphical model with latent variables could be called a HCRF, but I am not sure how the term is used in general.

The primary strength of your model seems to be the increased modeling power due to the non-linearity introduced by the hidden units. Another potential way to introduce non-linearity would be to use Mercer kernels together with hidden units. Do you have any intuition as how this would fare against using RBMs?

I think that model is investigated here. I guess my main concern with that model would be that it scales quadratically in the number of training sequences(?), making it unsuitable for typical NLP and speech applications.

One could also use non-stochastic hidden units to get the non-linearity, as was done in [2][one of the first CRF models] (which was published years before Lafferty et al. published their seminal CRF paper).

Thanks, I am aware of the LDCRF paper, but I never quite understood the motivation of their approach. The multinomial hidden units (one per frame) have a very limited capacity to describe latent structure in the data, and to obtain a model that is tractable, the LDCRF needs to sacrifice the connections that model temporal relations between class label (for instance, that an article is often followed by a noun).

In general, inference with hidden state and label sequences is intractable because the resulting graph contains loops. As a result, the sum over all possible hidden/label sequences that needs to be evaluated to compute the partition does not factorize anymore, prompting the use of approximate inference algorithms such as loopy belief propagation.

There may be some cases in which exact inference can still be performed. For instance, consider a factorial CRF with two label chains; one with K possible labels and one with L possible labels. You could also view this model as a linear-chain CRF with K x L possible labels, so exact summing over (K x L) ^ 2 may still be feasible. I assume something like this happens in the Sutton paper.

In general, this quickly gets out of hand though: in hidden-unit CRFs with H hidden units and K labels, we would need to sum over (2^H x K) ^ 2 possible values. In section 3.2 of the DCRF paper, this is described as well; the section discusses an approximate inference method based on loopy belief propagation.

Thanks for the answer. I noticed that you summed P(w, 000, o; theta) twice. Was it a typo, or was it on purpose? Anyway, I initially thought of that, but assuming HCRFs have one hidden node for each observation this indeed seemed quite intractable to me. Am I still missing something?

Thanks for catching the typo.

Yes, it is intractable, but then again inference on many other useful models is also intractable. The most common solutions seem to be training with EM (i.e., instead of maximizing P(w|o;theta) you maximize E_s[log P(w|o,s,theta)] using a point approximation of s, which is tractable in some scenarios), variational mean field (same thing as EM except you use a richer distribution over s instead of a point approximation), gibbs sampling (it's at first non obvious how you can update the parameters with gibbs sampling, but see Michael Wick's SampleRank http://www.cs.umass.edu/~mwick/MikeWeb/Publications_files/wick09samplerank.pdf ), loopy belief propagation (to do this well you need to take care of the nonconvergence problem or use some estimation method that can deal with noisy gradients such as SGD), and probably other techniques.

Note that if you make a Markov assumption on the hidden state sequence, then you can use standard Viterbi to find the optimal hidden state assignment for a fixed observation sequence. The difficulty is that you need to sum over the joint hidden and observed sequences for the partition function and when performing joint inference. In the Sung and Jurafsky paper they use an N-best approximation, where they replace sum_Y sum_S[...] with sum_L sum_S [...] in the partition function, where L is the N most probable sequences of observation labels. Unfortunately I am not familiar with the N-best search algorithms used in that paper, but they seem to be using some kind of beam search.