Learning Structure to Structure Mappings

NSF-Project IIS-0713483

Cornell University
Department of Computer Science

Project Goals

This goal of this proposal is to extend ongoing work on learning with structured output spaces in the support-vector-machine (SVM) framework. Such structured output spaces arise in problems where the prediction is not a univariate response (e.g. yes/no), but a structured object (e.g. a sequence, tree, or alignment). While recent work has uncovered how to discriminatively learn prediction rules for simple structures with limited interdependencies, research is needed to extend these methods to the complex structures needed for many applications (e.g. machine translation). This project aims to extend the structural SVM framework to such complex structures. Specifically, it focuses on the required gains in computational efficiency, broader classes of loss functions, and the use of unlabeled data to improve statistical efficiency.

People

Related Publications

[Joachims/etal/09a] T. Joachims, T. Finley, Chun-Nam Yu, Cutting-Plane Training of Structural SVMs, Machine Learning, 77(1):27-59, 2009.
[PDF]
[BibTeX] [Software]
[Joachims/etal/09b] T. Joachims, T. Hofmann, Yisong Yue, Chun-Nam Yu, Predicting Structured Objects with Support Vector Machines, Communications of the ACM, Research Highlight, 52(11):97-104, November, 2009 (with Technical Perspective by John Shawe-Taylor).
[Online]
[BibTeX]
[Joachims/Yu/09a]
 
T. Joachims, Chun-Nam John Yu, Sparse Kernel SVMs via Cutting-Plane Training, European Conference on Machine Learning (ECML), Machine Learning Journal, Special ECML Issue, 76(2-3):179-193, 2009.
[PDF]
[BibTeX(ECML Best Research Paper Award)
[Yu/Joachims/09a] Chun-Nam John Yu, T. Joachims, Learning Structural SVMs with Latent Variables, Proceedings of the International Conference on Machine Learning (ICML), 2009.
[PDF]
[BibTeX] [Software]
[Yu/etal/08a] Chun-Nam John Yu, T. Joachims, R. Elber, J. Pillardy, Support Vector Training of Protein Alignment Models, Journal of Computational Biology, 15(7): 867-880, September 2008.
[JCB Digital Library]
[BibTeX
[Yu/Joachims/08b] Chun-Nam John Yu, T. Joachims, Training Structural SVMs with Kernels Using Sampled Cuts, Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD), ACM, 2008.
[PDF]
[BibTeX
[Finley/Joachims/08a] T. Finley and T. Joachims, Training Structural SVMs when Exact Inference is Intractable, Proceedings of the International Conference on Machine Learning (ICML), 2008.
[PDF]
[BibTeX
[Yue/Joachims/08a] Yisong Yue and T. Joachims, Predicting Diverse Subsets Using Structural SVMs, Proceedings of the International Conference on Machine Learning (ICML), 2008.
[PDF]
[BibTeX] [Software]
[Yue/etal/07a] Yisong Yue, T. Finley, F. Radlinski, T. Joachims, A Support Vector Method for Optimizing Average Precision, Proceedings of the Conference on Research and Development in Information Retrieval (SIGIR), 2007.
[PDF] [BibTeX] [Software
[Yu/etal/07a] Chun-Nam Yu, T. Joachims, R. Elber, J. Pillardy, Support Vector Training of Protein Alignment Models, Proceeding of the International Conference on Research in Computational Molecular Biology (RECOMB), 2007.
[PDF] [BibTeX] [Software] 
[Joachims/06a] T. Joachims, Training Linear SVMs in Linear Time, Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD), ACM, 2006.
[Postscript] [PDF] [Software] (KDD Best Paper Award)
[Yu/Joachims/06a] Chun-Nam Yu and T. Joachims, Training Protein Threading Models Using Structural SVMs, ICML Workshop on Learning in Structured Output Spaces, 2006.
[PDF]
[Joachims/05a] T. Joachims, A Support Vector Method for Multivariate Performance Measures, Proceedings of the International Conference on Machine Learning (ICML), 2005.
[Postscript] [PDF]
[Software] (ICML Best Paper Award)
[Finley/Joachims/05a] T. Finley and T. Joachims, Supervised Clustering with Support Vector Machines, Proceedings of the International Conference on Machine Learning (ICML), 2005.
[Postscript] [PDF]  
(ICML Outstanding Student Paper Award)
[Joachims/Hopcroft/05a] T. Joachims and J. Hopcroft, Error Bounds for Correlation Clustering, Proceedings of the International Conference on Machine Learning (ICML), 2005.
[Postscript] [PDF]  
[Tsochantaridis/etal/05a] I. Tsochantaridis, T. Joachims, T. Hofmann, and Y. Altun, Large Margin Methods for Structured and Interdependent Output Variables, Journal of Machine Learning Research (JMLR), 6(Sep):1453-1484, 2005.
[PDF]  

[Tsochantaridis/etal/04a]

I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun, Support Vector Machine Learning for Interdependent and Structured Output Spaces, Proceedings of the International Conference on Machine Learning (ICML), 2004.
[Postscript]  [PDF]  

Acknowledgement and Disclaimer

This material is based upon work supported by the National Science Foundation under CAREER Award No. 0412894. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation (NSF).