nips nips2003 nips2003-124 nips2003-124-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ben Taskar, Carlos Guestrin, Daphne Koller
Abstract: In typical classification tasks, we seek a function which assigns a label to a single object. Kernel-based approaches, such as support vector machines (SVMs), which maximize the margin of confidence of the classifier, are the method of choice for many such tasks. Their popularity stems both from the ability to use high-dimensional feature spaces, and from their strong theoretical guarantees. However, many real-world tasks involve sequential, spatial, or structured data, where multiple labels must be assigned. Existing kernel-based methods ignore structure in the problem, assigning labels independently to each object, losing much useful information. Conversely, probabilistic graphical models, such as Markov networks, can represent correlations between labels, by exploiting problem structure, but cannot handle high-dimensional feature spaces, and lack strong theoretical generalization guarantees. In this paper, we present a new framework that combines the advantages of both approaches: Maximum margin Markov (M3 ) networks incorporate both kernels, which efficiently deal with high-dimensional features, and the ability to capture correlations in structured data. We present an efficient algorithm for learning M3 networks based on a compact quadratic program formulation. We provide a new theoretical bound for generalization in structured domains. Experiments on the task of handwritten character recognition and collective hypertext classification demonstrate very significant gains over previous approaches. 1
[1] Y. Altun, I. Tsochantaridis, and T. Hofmann. Hidden markov support vector machines. In Proc. ICML, 2003.
[2] D. Bertsekas. Nonlinear Programming. Athena Scientific, Belmont, MA, 1999.
[3] M. Collins. Parameter estimation for statistical parsing models: Theory and practice of distribution-free methods. In IWPT, 2001.
[4] R.G. Cowell, A.P. Dawid, S.L. Lauritzen, and D.J. Spiegelhalter. Probabilistic Networks and Expert Systems. Springer, New York, 1999.
[5] K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernelbased vector machines. Journal of Machine Learning Research, 2(5):265–292, 2001.
[6] R. Kassel. A Comparison of Approaches to On-line Handwritten Character Recognition. PhD thesis, MIT Spoken Language Systems Group, 1995.
[7] J. Lafferty, A. McCallum, and F. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. ICML01, 2001.
[8] J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988.
[9] J. Platt. Using sparseness and analytic QP to speed training of support vector machines. In NIPS, 1999.
[10] B. Taskar, P. Abbeel, and D. Koller. Discriminative probabilistic models for relational data. In Proc. UAI02, Edmonton, Canada, 2002.
[11] V.N. Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, New York, 1995.
[12] J. Yedidia, W. Freeman, and Y. Weiss. Generalized belief propagation. In NIPS, 2000.
[13] T. Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2:527–550, 2002.