Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Recent approaches to learning structured predictors often require approximate inference for tractability; yet its effects on the learned model are unclear. Meanwhile, most learning algorithms act as if computational cost was constant within the model class. This paper sheds some light on the first issue by establishing risk bounds for max-margin learning with LP relaxed inference and addresses the second issue by proposing a new paradigm that attempts to penalize "time-consuming" hypotheses. Our analysis relies on a geometric characterization of the outer polyhedra associated with the LP relaxation. We then apply these techniques to the problem of dependency parsing, for which a concise LP formulation is provided that handles non-local output features. A significant improvement is shown over arc-factored models.

REFERENCES

• 1: Endre Boros , Peter L. Hammer, Pseudo-boolean optimization, Discrete Applied Mathematics, v.123 n.1-3, p.155-225, 15 November 2002
• 2: Buchholz, S., & Marsi, E. (2006). CoNLL-X shared task on multilingual dependency parsing. Conf. Comp. Nat. Lang. Learn., 189--210.
• 3: Cesa-Bianchi, N., Conconi, A., & Gentile, C. (2004). On the generalization ability of on-line learning algorithms. IEEE Trans. on Inf. Theory, 50, 2050--2057.
• 4: Chang, M., Ratinov, L., & Roth, D. (2008). Constraints as prior knowledge. Int. Conf. Mach. Learn. Workshop on Prior Knowledge for Text and Language Processing.
• 5: Chu, Y. J., & Liu, T. H. (1965). On the shortest arborescence of a directed graph. Science Sinica, 14, 1396--1400.
• 6: Clarke, J., & Lapata, M. (2008). Global inference for sentence compression: An integer linear programming approach. J. Art. Intel. Res., 31, 399--429.
• 7: Michael Collins, Discriminative training methods for hidden Markov models: theory and experiments with perceptron algorithms, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.1-8, July 06, 2002 [doi>10.3115/1118693.1118694]
• 8: Koby Crammer , Ofer Dekel , Joseph Keshet , Shai Shalev-Shwartz , Yoram Singer, Online Passive-Aggressive Algorithms, The Journal of Machine Learning Research, 7, p.551-585, 12/1/2006
• 9: Hal Daumé, III , Daniel Marcu, Learning as search optimization: approximate large margin methods for structured prediction, Proceedings of the 22nd international conference on Machine learning, p.169-176, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102373]
• 10: Denis, P., & Baldridge, J. (2007). Joint determination of anaphoricity and coreference resolution using integer programming. North. Am. Assoc. Comp. Ling.
• 11: Edmonds, J. (1967). Optimum branchings. J. Res. National Bureau of Standards, 71B, 233--240.
• 12: Jason M. Eisner, Three new probabilistic models for dependency parsing: an exploration, Proceedings of the 16th conference on Computational linguistics, August 05-09, 1996, Copenhagen, Denmark [doi>10.3115/992628.992688]
• 13: Thomas Finley , Thorsten Joachims, Training structural SVMs when exact inference is intractable, Proceedings of the 25th international conference on Machine learning, p.304-311, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390195]
• 14: Kulesza, A., & Pereira, F. (2007). Structured learning with approximate inference. Neur. Inf. Proc. Sys. 20, 785--792.
• 15: 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
• 16: Leonid A Levin, Average case complete problems, SIAM Journal on Computing, v.15 n.1, p.285-286, Feb. 1986 [doi>10.1137/0215020]
• 17: Magnanti, T., & Wolsey, L. (1994). Optimal Trees (Tech. Rep. 290--94). MIT, Op. Res. Center.
• 18: Martins, A. F. T., Smith, N. A., & Xing, E. P. (2009). Concise integer linear programming formulations for dependency parsing. Assoc. Comp. Ling. To appear.
• 19: McDonald, R., Lerman, K., & Pereira, F. (2006). Multilingual dependency analysis with a two-stage discriminative parser. Conf. Comp. Nat. Lang. Learn., 216--220.
• 20: McDonald, R., & Satta, G. (2007). On the complexity of non-projective data-driven dependency parsing. Int. Conf. Pars. Tech., 121--132.
• 21: Ryan McDonald , Fernando Pereira , Kiril Ribarov , Jan Hajič, Non-projective dependency parsing using spanning tree algorithms, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.523-530, October 06-08, 2005, Vancouver, British Columbia, Canada [doi>10.3115/1220575.1220641]
• 22: Ratliff, N., Bagnell, J., & Zinkevich, M. (2006). Subgradient methods for maximum margin structured learning. Int. Conf. Mach. Learn. Workshop on Learning in Structured Outputs Spaces.
• 23: Matthew Richardson , Pedro Domingos, Markov logic networks, Machine Learning, v.62 n.1-2, p.107-136, February 2006 [doi>10.1007/s10994-006-5833-1]
• 24: Riedel, S., & Clarke, J. (2006). Incremental integer linear programming for non-projective dependency parsing. Emp. Meth. Nat. Lang. Proc., 129--137.
• 25: Dan Roth , Wen-tau Yih, Integer linear programming inference for conditional random fields, Proceedings of the 22nd international conference on Machine learning, p.736-743, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102444]
• 26: Smith, D. A., & Eisner, J. (2008). Dependency parsing by belief propagation. Emp. Meth. Nat. Lang. Proc., 145--156.
• 27: Taskar, B., Guestrin, C., & Koller, D. (2004a). Max-margin markov networks. Neur. Inf. Proc. Sys. 16.
• 28: Ben Taskar , Vassil Chatalbashev , Daphne Koller, Learning associative Markov networks, Proceedings of the twenty-first international conference on Machine learning, p.102, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015444]
• 29: Taskar, B., Lacoste-Julien, S., & Jordan, M. (2006). Structured prediction via the extragradient method. Neur. Inf. Proc. Sys. 18, 1345--1352.
• 30: 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]
• 31: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Inference engines
      I.2.7 Natural Language Processing
          Subjects: Language parsing and understanding

General Terms:
Algorithms, Design, Theory