Mixture-of-Parents Maximum Entropy Markov Models

by David S. Rosenberg, Dan Klein and Ben Taskar

Like skip-chain CRF, the mixture-of-parent MEMM also aims at utilizing the long-range interactions for NER problems. Skip-chain CRF, though, is beautiful in theory. The inference on it cannot be easily carried out (there are loops). This paper adds directed edges to the same r.v.s but with the assumption that Pr( y | pa(y) ) is a mixture of Pr( y | y') where y' in pa(y) (please note that x is omitted in this formulation and here we refer to a single element). With this, the conditional probability Pr(y | x) can still be calculated with dynamic programming (now we have to sum over all parents as well and here we refer to a sequence).

The tricky part they employed is the mixing proportion of the parent is assumed to be known as equal for one r.v. Then they can get a convex optimization problem which can be solved just as MEMM. By computing the gradient, L-BFGS can be applied. They actually have another objective (log conditional margins instead of log joint conditional) which is non-convex but it is well-behaved in practice.

The Infinite Markov Model

by Daichi Mochihashi and Eiichiru Sumita

The paper illustrates how it is possible to extend an n-gram model with Dirichlet process (here with Chinese restaurant process interpretation, actually a more general form is Pitman-Yor process). An n-gram model is simply an order-n Markov model, which can be presented with suffix tree. The generation can be then extended to arbitrary depth (unlike n-gram, the depth is fixed). The important thing is the inference part. The posterior is difficult to compute and we simply use a Gibbs sampler (the conditional posterior is easy to compute, a Beta distribution given a Beta prior).

Maybe we can try a variational version?

Max-Margin Markov Networks

by Ben Taskar, Carlos Guestrin and Daphne Koller

As we might see in CME, CRF, features are just as features in SVM, the parameters we are learning from data are learnt via those in logistic model. We know MLE is just one way of training discriminative models. Another widely-used rule is max margin. How can we model a structured output as in CRF (namely it is an MRF) with margins?

The idea comes from multi-class SVM: the predicted label defines a feature vector which should be separated from other vectors of different configurations for at least γ. But now we have a variable length of each sequence. Therefore it is reasonable to constrain the margin inquality to a certain scale of γ. The scale is simply the number of classification error. Like SVM, introducing slack variable for the unseparable case will get us the margin + loss expression. This optimization is still convex, but the constraints are too many since in multi-class discrimination, the configurations are comparatively fewer (c classes, then c-1 constraints for each sample). Now for a sequence of l labels and the number of values of y is c, we have c^l constraints.

The tackle this problem, they convert it into the dual problem. The dual variables can be regarded as a density (to a given scale). Though they are many, not every single variable must be computed. The structure of the MRF determines the necessary combinations of them: grouping them into edge dual variables and vertex dual variables gives us a polynomial-number of optimization variables. But now we have to satisfy the consistency the vectex variable now is the margin of related edge variables. Then we can convert the dual problem back into the prime one. The optimization is done in SVM's flavor, e.g. SMO.

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.