Maximum Entropy Discrimination Markov Networks

摘要

The standard maximum margin approach for structured prediction lacksa straightforward probabilistic interpretation of the learningscheme and the prediction rule. Therefore its unique advantages suchas dual sparseness and kernel tricks cannot be easily conjoined withthe merits of a probabilistic model such as Bayesian regularization,model averaging, and ability to model hidden variables. In thispaper, we present a new general framework called maximumentropy discrimination Markov networks (MaxEnDNet, or simply,MEDN), which integrates these two approaches and combines andextends their merits. Major innovations of this approach include: 1)It extends the conventional max-entropy discrimination learning ofclassification rules to a new structural max-entropydiscrimination paradigm of learning a distribution of Markovnetworks. 2) It generalizes the extant Markov networkstructured-prediction rule based on a point estimator of modelcoefficients to an averaging model akin to a Bayesian predictor thatintegrates over a learned posterior distribution of modelcoefficients. 3) It admits flexible entropic regularization of themodel during learning. By plugging in different prior distributionsof the model coefficients, it subsumes the well-known maximum marginMarkov networks (M3N) as a special case, and leads to a modelsimilar to an L₁-regularized M3N that is simultaneously primaland dual sparse, or other new types of Markov networks. 4) Itapplies a modular learning algorithm that combines existingvariational inference techniques and convex-optimization basedM3N solvers as subroutines.Essentially, MEDN can be understood as a jointly maximumlikelihood and maximum margin estimate of Markov network. Itrepresents the first successful attempt to combine maximum entropylearning (a dual form of maximum likelihood learning) with maximummargin learning of Markov network for structured input/outputproblems; and the basic principle can be generalized to learningarbitrary graphical models, such as the generative Bayesian networksor models with structured hidden variables. We discuss a number oftheoretical properties of this approach, and show that empirically itoutperforms a wide array of competing methods for structuredinput/output learning on both synthetic and real OCR and web dataextraction data sets. color="gray">