Annals of Statistics, 36(2):555-586, April 2008 (article)
Consistency is a key property of statistical algorithms when the data
is drawn from some underlying probability distribution. Surprisingly,
despite decades of work, little is known about consistency of most
clustering algorithms. In this paper we investigate consistency of
the popular family of spectral clustering algorithms, which clusters
the data with the help of eigenvectors of graph Laplacian matrices. We
develop new methods to establish that for increasing sample size,
those eigenvectors converge to the eigenvectors of certain limit
operators. As a result we can prove that one of the two major classes
of spectral clustering (normalized clustering) converges under very
general conditions, while the other (unnormalized clustering) is only
consistent under strong additional assumptions, which are not always
satisfied in real data. We conclude that our analysis provides strong
evidence for the superiority of normalized spectral clustering.
In Advances in neural information processing systems 18, pages: 33-40, (Editors: Weiss, Y. , B. Schölkopf, J. Platt), MIT Press, Cambridge, MA, USA, Nineteenth Annual Conference on Neural Information Processing Systems (NIPS), May 2006 (inproceedings)
Many real-world classification problems involve the prediction of multiple inter-dependent variables forming some structural dependency. Recent progress in machine learning has mainly focused on supervised classification of such structured variables. In this paper, we investigate structured classification in a semi-supervised setting.
We present a discriminative approach that utilizes the intrinsic geometry of input patterns revealed by unlabeled data points and we derive a maximum-margin formulation of semi-supervised learning for structured variables. Unlike transductive algorithms, our formulation naturally extends to new test points.
In Advances in Neural Information Processing Systems 17, pages: 857-864, (Editors: Saul, L. K., Y. Weiss, L. Bottou), MIT Press, Cambridge, MA, USA, Eighteenth Annual Conference on Neural Information Processing Systems (NIPS), July 2005 (inproceedings)
An important aspect of clustering algorithms is whether the partitions constructed on finite samples converge to a useful clustering of the whole data space as the sample size increases. This paper investigates this question for normalized and unnormalized versions of the popular spectral
clustering algorithm. Surprisingly, the convergence of unnormalized spectral clustering is more difficult to handle than the normalized case. Even though recently some first results on the convergence of normalized spectral clustering have been obtained, for the unnormalized case
we have to develop a completely new approach combining tools from numerical integration, spectral and perturbation theory, and probability. It turns out that while in the normalized case, spectral clustering usually converges to a nice partition of the data space, in the unnormalized case
the same only holds under strong additional assumptions which are not always satisfied. We conclude that our analysis gives strong evidence for the superiority of normalized spectral clustering. It also provides a basis
for future exploration of other Laplacian-based methods.
Our goal is to understand the principles of Perception, Action and Learning in autonomous systems that successfully interact with complex environments and to use this understanding to design future systems