Learning structural SVMs with latent variables

ABSTRACT

We present a large-margin formulation and algorithm for structured output prediction that allows the use of latent variables. Our proposal covers a large range of application problems, with an optimization problem that can be solved efficiently using Concave-Convex Programming. The generality and performance of the approach is demonstrated through three applications including motiffinding, noun-phrase coreference resolution, and optimizing precision at k in information retrieval.

REFERENCES

• 1: Timothy L. Bailey , Charles Elkan, Unsupervised Learning of Multiple Motifs in Biopolymers Using Expectation Maximization, Machine Learning, v.21 n.1-2, p.51-80, Oct./Nov. 1995 [doi>10.1007/BF00993379]
• 2: Zhe Cao , Tao Qin , Tie-Yan Liu , Ming-Feng Tsai , Hang Li, Learning to rank: from pairwise approach to listwise approach, Proceedings of the 24th international conference on Machine learning, p.129-136, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273513]
• 3: Chapelle, O., Do, C., Le, Q., Smola, A., & Teo, C. (2008). Tighter bounds for structured estimation. Adv. in Neural Inf. Process. Syst. (pp. 281--288).
• 4: Ronan Collobert , Fabian Sinz , Jason Weston , Léon Bottou, Trading convexity for scalability, Proceedings of the 23rd international conference on Machine learning, p.201-208, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143870]
• 5: Felzenszwalb, P., McAllester, D., & Ramanan, D. (2008). A Discriminatively Trained, Multiscale, Deformable Part Model. Proc. Computer Vision and Pattern Recognition Conf. (pp. 1--8).
• 6: Thomas Finley , Thorsten Joachims, Supervised clustering with support vector machines, Proceedings of the 22nd international conference on Machine learning, p.217-224, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102379]
• 7: Herbrich, R., Graepel, T., & Obermayer, K. (2000). Large margin rank boundaries for ordinal regression. In Advances in large margin classifiers, chapter 7, 115--132. MIT Press.
• 8: Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
• 9: Joachims, T., Finley, T., & Yu, C. (To appear). Cutting-plane training of structural SVMs. Machine Learning.
• 10: K. C. Kiwiel, Proximity control in bundle methods for convex, Mathematical Programming: Series A and B, v.46 n.1, p.105-122, Jan. 1990 [doi>10.1007/BF01585731]
• 11: Liu, T., Xu, J., Qin, T., Xiong, W., & Li, H. (2007). LETOR: Benchmark dataset for research on learning to rank for information retrieval. SIGIR Workshop on Learning to Rank for Information Retrieval.
• 12: Patrick Ng , Uri Keich, GIMSAN, Bioinformatics, v.24 n.19, p.2256-2257, October 2008 [doi>10.1093/bioinformatics/btn408]
• 13: Vincent Ng , Claire Cardie, Improving machine learning approaches to coreference resolution, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073102]
• 14: Petrov, S., & Klein, D. (2007). Discriminative Log-Linear Grammars with Latent Variables. Adv. in Neural Inf. Process. Syst. (p. 1153).
• 15: Smola, A., Vishwanathan, S., & Hofmann, T. (2005). Kernel methods for missing variables. Proc. of the Int. Conf. on Artif. Intell. and Stat. (p. 325).
• 16: Taskar, B., Guestrin, C., & Koller, D. (2003). Max-margin Markov networks. Adv. in Neural Inf. Process. Syst. (p. 51).
• 17: 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]
• 18: Marc Vilain , John Burger , John Aberdeen , Dennis Connolly , Lynette Hirschman, A model-theoretic coreference scoring scheme, Proceedings of the 6th conference on Message understanding, November 06-08, 1995, Columbia, Maryland [doi>10.3115/1072399.1072405]
• 19: Sy Bor Wang , Ariadna Quattoni , Louis-Philippe Morency , David Demirdjian, Hidden Conditional Random Fields for Gesture Recognition, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.1521-1527, June 17-22, 2006 [doi>10.1109/CVPR.2006.132]
• 20: Wang, Y., & Mori, G. (2008). Max-margin hidden conditional random fields for human action recognition (Technical Report TR 2008--21). School of Computing Science, Simon Fraser University.
• 21: A. L. Yuille , Anand Rangarajan, The concave-convex procedure, Neural Computation, v.15 n.4, p.915-936, April 2003 [doi>10.1162/08997660360581958]
• 22: Alexander Zien , Ulf Brefeld , Tobias Scheffer, Transductive support vector machines for structured variables, Proceedings of the 24th international conference on Machine learning, p.1183-1190, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273645]

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.6 Optimization
          Subjects: Convex programming

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation; Feature evaluation and selection
  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