nips nips2001 nips2001-144 nips2001-144-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Martin Szummer, Tommi Jaakkola
Abstract: To classify a large number of unlabeled examples we combine a limited number of labeled examples with a Markov random walk representation over the unlabeled examples. The random walk representation exploits any low dimensional structure in the data in a robust, probabilistic manner. We develop and compare several estimation criteria/algorithms suited to this representation. This includes in particular multi-way classification with an average margin criterion which permits a closed form solution. The time scale of the random walk regularizes the representation and can be set through a margin-based criterion favoring unambiguous classification. We also extend this basic regularization by adapting time scales for individual examples. We demonstrate the approach on synthetic examples and on text classification problems.
[1] Szummer, M; Jaakkola, T. (2000) Kernel expansions with unlabeled examples. NIPS 13.
[2] Jaakkola, T; Meila, M; Jebara, T. (1999) Maximum entropy discrimination. NIPS 12.
[3] Tishby, N; Slonim, N. (2000) Data clustering by Markovian relaxation and the Information Bottleneck Method. NIPS 13.
[4] Blum, A; Chawla, S. (2001) Learning from Labeled and Unlabeled Data using Graph Mincuts. ICML.
[5] Alon, N. et al (1997) Scale-sensitive Dimensions, Uniform Convergence, and Learnability. J. ACM, 44 (4) 615-631
[6] Tenenbaum, J; de Silva, V; Langford J. (2000) A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science 290 (5500): 2319-2323.
[7] Kondor, I; Lafferty J; (2001) Diffusion kernels in continuous spaces. Tech report CMU, to appear.