Conditional Random Fields: Probabilistic Models for Segmenting and Labelling Sequences Data

by John Lafferty, Andrew McCallum and Fernando Pereira

CRF is simple a MRF conditional on the observation. In this paper they proposed a chain MRF for modeling sequential data (actually more complex models can be used, as in the Bayesian nets, e.g. higher-order Markov chains in HMM, MEMM). CRF has all fantasy merits of CME and other models in a way: 1) human-designed features can be used; 2) The ME learning is convex unlike HMM. It also avoids the label bias problem. That is given a Markov model with few branches, since the conditional probability is on the current transition, we would get a large probability even if the transition is wrong. It simply ignores the current observation. Then we find little discrimination of the right decoding with a wrong one (since each transition in either decoding has a large probability). This is because the belief network constrains the model on transition to a probability distribution, resulting a competition among states at one transition. A better way is to model the whole as a distribution (i.e. an undirected model is more suitable). The potential function does not have the normalization requirement and this leaves the competition to the sequence of transitions instead of states.

This observation is key to the design of CRF. Given a chain MRF, we would find the training procedure involves features not only f(x,y_t) as CME, but also transitional features f(x, y_t, y_t+1) as MEMM. By the representer theorem, the form of the result suggests GIS, IIS and other optimization algorithms that are applicable to CME may also apply to CRF. The optimization is no harder but since the normalizaton factor now simply depends on the whole sequence (unlike MEMM on the current observed data). I will check this derivation manually soon.

Maximum Entropy Markov Models for Information Extraction and Segmentation

by Andrew McCallum, Dayne Freitag and Fernando Pereira

MEMM is a modification of HMM such that: 1) we might use features in the model; 2) a discriminative model instead of a generative one. After all it is a Markov model trained in the ME way.

There are some important points in CME in NLP I want to address here: 1) the ME learning leads to an MRF; 2) in applications in NLP, it is a zero-order CRF; 3) the dual problem of the ME is MLE, whichcan be optimized in many ways, e.g. GIS (sth like coordinate descent), IIS, gradient-based search or L-BFGS.

In MEMM, unlike HMM in which each observation is determined by a Markov Chain (only on the current latent state), each latent state is determined by the current observation as well. This graphical model implies a factorization in which we need to model Pr( y_t+1 | y_t, x_t+1). For simplicity, we just write Pr( y | x ) since y_t is given (e.g. state 1) and we focus on this case. We use a feature-based method to model it. Let f_a( x, y ) be a feature, where a is a pair, indicating a binary feature on x and another on y, when both satisfied, makes a true value. This would be the same as CME. Then for each trasition we have a probability model.

MEMM is trained on each kind of transition (with different starting states). Then given a sequence of observations, the decoding (finding ys) can be calculated with dynamic programming method as HMM, only maximizing the conditional probability instead. If we do not have labels (y) in the training procedure, we must use one like Baum-Welch algorithm.

The later CRF model is simply an undirected version of MEMM. Some other work in NLP suggests MEMM is more expressive than the Moore HMM (the one we commonly use) but is less than Mealy HMM.