Constrained conditional models

Main reference: Chang et al. (2008) from Dan Roth's group.

CCM is an NLP modeling paradigm in which the objective functions are expressed as the linear combination of feature functions and constraints:

$f(x, y) = \sum_i w_i \phi_i (x,y) - \sum_j \rho_j C_j(x,y)$

At test time, an annotation is obtained by maximizing the objective function:

$y^* = \operatorname*{argmax}_{y \in \mathcal{Y}} f(x,y)$

Notice that the inference is global in the sense that when the output contains a lot of components (say, POS tags of a sentence, arguments of a predicate), they are chosen to jointly optimize a function. In other words, they are decided simultaneously. This is different from, e.g., transition systems which assign one piece of the output at a time.

	CCM	Transition-based
Inference	+ no error propagation	- suffer from error propagation
	- harder to implement, but there are general-purpose solvers (e.g. ILP solvers)	+ easier to implement
	- slower	+ faster (for greedy decoding, but also beam search)
Features	- restricted set of features (otherwise the model becomes intractable)	+ rich set of features
Examples	anything that uses LBJ (Rizzolo and Roth, 2010)	transition-based dependency parsing, e.g. MALT parser (Nivre et al. 2006)