Accurate max-margin training for structured output spaces

ABSTRACT

Tsochantaridis et al. (2005) proposed two formulations for maximum margin training of structured spaces: margin scaling and slack scaling. While margin scaling has been extensively used since it requires the same kind of MAP inference as normal structured prediction, slack scaling is believed to be more accurate and better-behaved. We present an efficient variational approximation to the slack scaling method that solves its inference bottleneck while retaining its accuracy advantage over margin scaling.

We further argue that existing scaling approaches do not separate the true labeling comprehensively while generating violating constraints. We propose a new max-margin trainer PosLearn that generates violators to ensure separation at each position of a decomposable loss function. Empirical results on real datasets illustrate that PosLearn can reduce test error by up to 25% over margin scaling and 10% over slack scaling. Further, PosLearn violators can be generated more efficiently than slack violators; for many structured tasks the time required is just twice that of MAP inference.

REFERENCES

• 1: Antoine Bordes , Léon Bottou , Patrick Gallinari , Jason Weston, Solving multiclass support vector machines with LaRank, Proceedings of the 24th international conference on Machine learning, p.89-96, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273508]
• 2: Bottou, L., & Bousquet, O. (2008). The tradeoffs of large scale learning. NIPS.
• 3: Yuri Boykov , Olga Veksler , Ramin Zabih, Fast Approximate Energy Minimization via Graph Cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.11, p.1222-1239, November 2001 [doi>10.1109/34.969114]
• 4: Koby Crammer , Yoram Singer, Ultraconservative online algorithms for multiclass problems, The Journal of Machine Learning Research, 3, p.951-991, 3/1/2003
• 5: Thorsten Joachims, Training linear SVMs in linear time, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150429]
• 6: Michael I. Jordan , Zoubin Ghahramani , Tommi S. Jaakkola , Lawrence K. Saul, An introduction to variational methods for graphical models, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 7: 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
• 8: LeCun, Y., Chopra, S., Hadsell, R., Marc'Aurelio, R., & Huang, F. (2006). A tutorial on energy-based learning. Predicting Structured Data. MIT Press.
• 9: McCallum, A., Nigam, K., Reed, J., Rennie, J., & Seymore, K. (2000). Cora: Computer science research paper search engine. http://cora.whizbang.com/.
• 10: Ryan McDonald , Koby Crammer , Fernando Pereira, Flexible text segmentation with structured multilabel classification, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.987-994, October 06-08, 2005, Vancouver, British Columbia, Canada [doi>10.3115/1220575.1220699]
• 11: Ryan McDonald , Koby Crammer , Fernando Pereira, Online large-margin training of dependency parsers, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, p.91-98, June 25-30, 2005, Ann Arbor, Michigan [doi>10.3115/1219840.1219852]
• 12: Peng, F., & McCallum, A. (2004). Accurate information extraction from research papers using conditional random fields. HLT-NAACL (pp. 329--336).
• 13: Ratliff, N., Bagnell, J., & Zinkevich, M. (2007). (online) subgradient methods for structured prediction. AIStats.
• 14: Sarawagi, S., & Cohen, W. W. (2004). Semi-markov conditional random fields for information extraction. NIPS.
• 15: Ben Taskar , Daphne Koller, Learning structured prediction models: a large margin approach, Stanford University, Stanford, CA, 2005
• 16: Taskar, B., Klein, D., Collins, M., Koller, D., & Manning, C. (2004). Max-margin parsing. EMNLP.
• 17: Ben Taskar , Simon Lacoste-Julien , Michael I. Jordan, Structured Prediction, Dual Extragradient and Bregman Projections, The Journal of Machine Learning Research, 7, p.1627-1653, 12/1/2006
• 18: Ioannis Tsochantaridis , Thorsten Joachims , Thomas Hofmann , Yasemin Altun, Large Margin Methods for Structured and Interdependent Output Variables, The Journal of Machine Learning Research, 6, p.1453-1484, 12/1/2005

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Minimax approximation and algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Inference engines
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory