Ben Taskar
Daphne Koller
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.
- 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.Google Scholar
Cross Ref
- Altun, Y., Tsochantaridis, I., & Hofmann, T. (2003). Hidden markov support vector machines. Proc. ICML.Google Scholar
- Baldi, P., Cheng, J., & Vullo, A. (2004). Large-scale prediction of disulphide bond connectivity. Proc. NIPS.Google Scholar
- Belongie, S., Malik, J., & Puzicha, J. (2002). Shape matching and object recognition using shape contexts. IEEE Trans. Pattern Anal. Mach. Intell., 24. Google ScholarDigital Library
- Berman, H., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T., Weissig, H., Shindyalov, I., & Bourne, P. (2000). The protein data bank.Google Scholar
- Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge University Press. Google ScholarDigital Library
- Collins, M. (2002). Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. Proc. EMNLP. Google ScholarDigital Library
- Duda, R. O., Hart, P. E., & Stork, D. G. (2000). Pattern classification. New York: Wiley Interscience. 2nd edition. Google ScholarDigital Library
- Edmonds, J. (1965). Maximum matching and a polyhedron with 0-1 vertices. Journal of Research at the National Bureau of Standards, 69B, 125 130.Google ScholarCross Ref
- Fariselli, P., & Casadio, R. (2001). Prediction of disulfide connectivity in proteins. Bioinformatics, 17, 957--964.Google ScholarCross Ref
- Heuberger, C. (2004). Inverse combinatorial optimization: A survey on problems, methods, and results. Journal of Combinatorial Optimization, 8.Google ScholarCross Ref
- Kabsch, W., & Sander, C. (1983). Dictionary of protein secondary structure: Pattern recognition of hydrogen-bonded and geometrical features.Google Scholar
- Schrijver, A. (2003). Combinatorial optimization: Polyhedra and efficiency. Springer.Google Scholar
- Taskar, B. (2004). Learning structured prediction models: A large margin approach. Doctoral dissertation, Stanford University. Google ScholarDigital Library
- Taskar, B., Chatalbashev, V., & Koller, D. (2004a). Learning associative Markov networks. Proc. ICML. Google ScholarDigital Library
- Taskar, B., Guestrin, C., & Koller, D. (2003). Max margin Markov networks. Proc. NIPS.Google Scholar
- Taskar, B., Klein, D., Collins, M., Koller, D., & Manning, C. (2004b). Max margin parsing. Proc. EMNLP.Google Scholar
- Tsochantaridis, I., Hofmann, T., Joachims, T., & Altun, Y. (2004). Support vector machine learning for interdependent and structured output spaces. Proc. ICML. Google ScholarDigital Library
- Vullo, A., & Frasconi, P. (2004). Dirsulfide connectivity prediction using recursive neural networks and evolutionary information. Bioinformatics, 20, 653--659. Google ScholarDigital Library
Recommendations
Learning structured prediction models for interactive image labeling
CVPR '11: Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern RecognitionWe propose structured models for image labeling that take into account the dependencies among the image labels explicitly. These models are more expressive than independent label predictors, and lead to more accurate predictions. While the improvement ...
Tractable semi-supervised learning of complex structured prediction models
ECMLPKDD'13: Proceedings of the 2013th European Conference on Machine Learning and Knowledge Discovery in Databases - Volume Part IIISemi-supervised learning has been widely studied in the literature. However, most previous works assume that the output structure is simple enough to allow the direct use of tractable inference/learning algorithms (e.g., binary label or linear chain). ...
Learning convex QP relaxations for structured prediction
ICML'13: Proceedings of the 30th International Conference on International Conference on Machine Learning - Volume 28We introduce a new large margin approach to discriminative training of intractable discrete graphical models. Our approach builds on a convex quadratic programming relaxation of the MAP inference problem. The model parameters are trained directly within ...
Comments