Laplace maximum margin Markov networks

We propose Laplace max-margin Markov networks (LapM3N), and a general class of Bayesian M3N (BM3N) of which the LapM3N is a special case with sparse structural bias, for robust structured prediction. BM3N generalizes extant structured prediction rules based on point estimator to a Bayes-predictor using a learnt distribution of rules. We present a novel Structured Maximum Entropy Discrimination (SMED) formalism for combining Bayesian and max-margin learning of Markov networks for structured prediction, and our approach subsumes the conventional M3N as a special case. An efficient learning algorithm based on variational inference and standard convex-optimization solvers for M3N, and a generalization bound are offered. Our method outperforms competing ones on both synthetic and real OCR data.