Laplace maximum margin Markov networks

ABSTRACT

We propose Laplace max-margin Markov networks (LapM³N), and a general class of Bayesian M³N (BM³N) of which the LapM³N is a special case with sparse structural bias, for robust structured prediction. BM³N 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 M³N as a special case. An efficient learning algorithm based on variational inference and standard convex-optimization solvers for M³N, and a generalization bound are offered. Our method outperforms competing ones on both synthetic and real OCR data.

REFERENCES

• 1: Altun, Y., Tsochantaridis, I., & Hofmann, T. (2003). Hidden markov support vector machines. ICML.
• 2: Galen Andrew , Jianfeng Gao, Scalable training of L¹-regularized log-linear models, Proceedings of the 24th international conference on Machine learning, p.33-40, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273501]
• 3: Bartlett, P., Collins, M., Taskar, B., & McAllester, D. (2004). Exponentiated gradient algorithms for larg-margin structured classification. NIPS.
• 4: Bennett, K. P., & Mangasarian, O. L. (1992). Robust linear programming discrimination of two linearly inseparable sets. Optim. Methods Softw, 23--34.
• 5: Antoni B. Chan , Nuno Vasconcelos , Gert R. G. Lanckriet, Direct convex relaxations of sparse SVM, Proceedings of the 24th international conference on Machine learning, p.145-153, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273515]
• 6: Miroslav Dudík , Steven J. Phillips , Robert E. Schapire, Maximum Entropy Density Estimation with Generalized Regularization and an Application to Species Distribution Modeling, The Journal of Machine Learning Research, 8, p.1217-1260, 12/1/2007
• 7: Mário A. T. Figueiredo, Adaptive Sparseness for Supervised Learning, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.9, p.1150-1159, September 2003 [doi>10.1109/TPAMI.2003.1227989]
• 8: Amir Globerson , Terry Y. Koo , Xavier Carreras , Michael Collins, Exponentiated gradient algorithms for log-linear structured prediction, Proceedings of the 24th international conference on Machine learning, p.305-312, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273535]
• 9: Jaakkola, T., Meila, M., & Jebara, T. (1999). Maximum entropy discrimination. NIPS.
• 10: Ata Kabán, On Bayesian classification with Laplace priors, Pattern Recognition Letters, v.28 n.10, p.1271-1282, July, 2007 [doi>10.1016/j.patrec.2007.02.010]
• 11: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 12: John Langford , Matthias Seeger , Nimrod Megiddo, An Improved Predictive Accuracy Bound for Averaging Classifiers, Proceedings of the Eighteenth International Conference on Machine Learning, p.290-297, June 28-July 01, 2001
• 13: Lebanon, G., & Lafferty, J. (2001). Boosting and maximum likelihood for exponential models. NIPS.
• 14: Lee, S.-I., Ganapathi, V., & Koller, D. (2006). Efficient structure learning of markov networks using l1-regularization. NIPS.
• 15: Qi, Y. A., Szummer, M., & Minka, T. P. (2005). Bayesian conditional random fields. AISTATS.
• 16: Ratliff, N. D., Bagnell, J. A., & Zinkevich, M. A. (2007). (online) subgradient methods for structured prediction. AISTATS.
• 17: Taskar, B., Guestrin, C., & Koller, D. (2003). Max-margin markov networks. NIPS.
• 18: Taskar, B., Lacoste-Julien, S., & Jordan, M. I. (2006). Structured prediction via the extragradient method. NIPS.
• 19: Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. J. Royal. Statist. Soc., B, 267--288.
• 20: Ioannis Tsochantaridis , Thomas Hofmann , Thorsten Joachims , Yasemin Altun, Support vector machine learning for interdependent and structured output spaces, Proceedings of the twenty-first international conference on Machine learning, p.104, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015341]
• 21: Wainwright, M. J., Ravikumar, P., & Lafferty, J. (2006). High-dimensional graphical model selection using l1-regularized logistic regression. NIPS.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Inference engines
      I.2.6 Learning
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection; Pattern analysis
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory