Learning structured prediction models: a large margin approach

ABSTRACT

We consider large margin estimation in a broad range of prediction models where inference involves solving combinatorial optimization problems, for example, weighted graph-cuts or matchings. Our goal is to learn parameters such that inference using the model reproduces correct answers on the training data. Our method relies on the expressive power of convex optimization problems to compactly capture inference or solution optimality in structured prediction models. Directly embedding this structure within the learning formulation produces concise convex problems for efficient estimation of very complex and diverse models. We describe experimental results on a matching task, disulfide connectivity prediction, showing significant improvements over state-of-the-art methods.

REFERENCES

• 1: Altschul, S., Madden, T., Schaffer, A., Zhang, A., Miller, W., & Lipman (1997). Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleid Acids Res., 25, 3389--3402.
• 2: Altun, Y., Tsochantaridis, I., & Hofmann, T. (2003). Hidden markov support vector machines. Proc. ICML.
• 3: Baldi, P., Cheng, J., & Vullo, A. (2004). Large-scale prediction of disulphide bond connectivity. Proc. NIPS.
• 4: S. Belongie , J. Malik , J. Puzicha, Shape Matching and Object Recognition Using Shape Contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.509-522, April 2002 [doi>10.1109/34.993558]
• 5: Berman, H., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T., Weissig, H., Shindyalov, I., & Bourne, P. (2000). The protein data bank.
• 6: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 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: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 9: Edmonds, J. (1965). Maximum matching and a polyhedron with 0-1 vertices. Journal of Research at the National Bureau of Standards, 69B, 125 130.
• 10: Fariselli, P., & Casadio, R. (2001). Prediction of disulfide connectivity in proteins. Bioinformatics, 17, 957--964.
• 11: Heuberger, C. (2004). Inverse combinatorial optimization: A survey on problems, methods, and results. Journal of Combinatorial Optimization, 8.
• 12: Kabsch, W., & Sander, C. (1983). Dictionary of protein secondary structure: Pattern recognition of hydrogen-bonded and geometrical features.
• 13: Schrijver, A. (2003). Combinatorial optimization: Polyhedra and efficiency. Springer.
• 14: Ben Taskar , Daphne Koller, Learning structured prediction models: a large margin approach, Stanford University, Stanford, CA, 2005
• 15: 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]
• 16: Taskar, B., Guestrin, C., & Koller, D. (2003). Max margin Markov networks. Proc. NIPS.
• 17: Taskar, B., Klein, D., Collins, M., Koller, D., & Manning, C. (2004b). Max margin parsing. Proc. EMNLP.
• 18: 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]
• 19: Alessandro Vullo , Paolo Frasconi, Disulfide connectivity prediction using recursive neural networks and evolutionary information, Bioinformatics, v.20 n.5, p.653-659, March 2004 [doi>10.1093/bioinformatics/btg463]