Standard max-margin structured prediction methods concentrate directly on the input-output mapping, and the lack of an elegant probabilistic interpretation causes limitations. In this paper, we present a novel framework called Maximum Entropy Discrimination Markov Networks (MaxEntNet) to do Bayesian max-margin structured learning by using expected margin constraints to define a feasible distribution subspace and applying the maximum entropy principle to choose the best distribution from this subspace. We show that MaxEntNet subsumes the standard max-margin Markov networks (M³N) as a spacial case where the predictive model is assumed to be linear and the parameter prior is a standard normal. Based on this understanding, we propose the Laplace max-margin Markov networks (LapM³N) which use the Laplace prior instead of the standard normal. We show that the adoption of a Laplace prior of the parameter makes LapM³N enjoy properties expected from a sparsified M³N. Unlike the L₁-regularized maximum likelihood estimation which sets small weights to zeros to achieve sparsity, LapM³N posteriorly weights the parameters and features with smaller weights are shrunk more. This posterior weighting effect makes LapM³N more stable with respect to the magnitudes of the regularization coefficients and more generalizable. To learn a LapM³N, we present an efficient iterative learning algorithm based on variational approximation and existing convex optimization methods employed in M³N. The feasibility and promise of LapM³N are demonstrated on both synthetic and real OCR data sets.

34 pages

*Department of Computer Science and Technology, Tsinghua University, Beijing 100084 China **Eric Xing, addressee for all correspondence, Carnegie Mellon University

This page maintained by [email protected]