Ulrike von Luxburg

2018

slt Tang, C., Garreau, D., von Luxburg, U. When do random forests fail? In Proceedings Neural Information Processing Systems, Neural Information Processing Systems (NIPS 2018) , December 2018 (inproceedings)

arXiv link (url) [BibTex]

Comparison-Based Random Forests

Haghiri, S., Garreau, D., Luxburg, U. V.

International Conference on Machine learning (ICML), 2018 (conference)

slt

link (url) [BibTex]

slt Haghiri, S., Garreau, D., Luxburg, U. V. Comparison-Based Random Forests International Conference on Machine learning (ICML), 2018 (conference)

link (url) [BibTex]

Design and Analysis of the NIPS 2016 Review Process

Shah*, N., Tabibian*, B., Muandet, K., Guyon, I., von Luxburg, U.

Journal of Machine Learning Research, 19(49):1-34, 2018, *equal contribution (article)

ei slt

ei slt Shah*, N., Tabibian*, B., Muandet, K., Guyon, I., von Luxburg, U. Design and Analysis of the NIPS 2016 Review Process Journal of Machine Learning Research, 19(49):1-34, 2018, *equal contribution (article)

arXiv link (url) [BibTex]

Foundations of Comparison-Based Hierarchical Clustering

Ghoshdastidar, D., Perrot, M., von Luxburg, U.

2018, arXiv preprint (arXiv:1811.00928) (article)

slt

slt Ghoshdastidar, D., Perrot, M., von Luxburg, U. Foundations of Comparison-Based Hierarchical Clustering 2018, arXiv preprint (arXiv:1811.00928) (article)

Measures of distortion for machine learning

Vankadara, L., von Luxburg, U.

In Proceedings Neural Information Processing Systems, Neural Information Processing Systems (NIPS 2018) , 2018 (inproceedings)

slt

slt Vankadara, L., von Luxburg, U. Measures of distortion for machine learning In Proceedings Neural Information Processing Systems, Neural Information Processing Systems (NIPS 2018) , 2018 (inproceedings)

Practical Methods for Graph Two-Sample Testing

Ghoshdastidar, D., von Luxburg, U.

In Proceedings Neural Information Processing Systems, Neural Information Processing Systems (NIPS 2018) , 2018 (inproceedings)

slt

slt Ghoshdastidar, D., von Luxburg, U. Practical Methods for Graph Two-Sample Testing In Proceedings Neural Information Processing Systems, Neural Information Processing Systems (NIPS 2018) , 2018 (inproceedings)

Perrot, M., von Luxburg, U.

Boosting for Comparison-Based Learning

2018, arXiv preprint (arXiv:1810.13333) (article)

slt

slt Perrot, M., von Luxburg, U. Boosting for Comparison-Based Learning 2018, arXiv preprint (arXiv:1810.13333) (article)

2017

Comparison-based nearest neighbor search

Haghiri, S., Ghoshdastidar, D., von Luxburg, U.

In Artificial Intelligence and Statistics, Artificial Intelligence and Statistics (AISTATS), 2017 (inproceedings)

slt

2017

slt Haghiri, S., Ghoshdastidar, D., von Luxburg, U. Comparison-based nearest neighbor search In Artificial Intelligence and Statistics, Artificial Intelligence and Statistics (AISTATS), 2017 (inproceedings)

Kernel functions based on triplet comparisons

Kleindessner, M., von Luxburg, U.

In Proceedings Neural Information Processing Systems, Neural Information Processing Systems (NIPS), 2017 (inproceedings)

slt

slt Kleindessner, M., von Luxburg, U. Kernel functions based on triplet comparisons In Proceedings Neural Information Processing Systems, Neural Information Processing Systems (NIPS), 2017 (inproceedings)

Two-sample Hypothesis Testing for Inhomogeneous Random Graphs

Ghoshdastidar, D., Gutzeit, M., Carpentier, A., von Luxburg, U.

2017, arXiv preprint (arXiv:1707.00833) (article)

slt

slt Ghoshdastidar, D., Gutzeit, M., Carpentier, A., von Luxburg, U. Two-sample Hypothesis Testing for Inhomogeneous Random Graphs 2017, arXiv preprint (arXiv:1707.00833) (article)

Lens Depth Function and k-Relative Neighborhood Graph: Versatile Tools for Ordinal Data Analysis

Kleindessner, M., von Luxburg, U.

Journal of Machine Learning Research (JMLR), Journal of Machine Learning Research, 18, 2017 (article)

slt

slt Kleindessner, M., von Luxburg, U. Lens Depth Function and k-Relative Neighborhood Graph: Versatile Tools for Ordinal Data Analysis Journal of Machine Learning Research (JMLR), Journal of Machine Learning Research, 18, 2017 (article)

Two-sample tests for large random graphs using network statistics

Ghoshdastidar, D., Gutzeit, M., Carpentier, A., von Luxburg, U.

In Conference on Computational Learning Theory (COLT), Conference on Computational Learning Theory (COLT), 2017 (inproceedings)

slt

slt Ghoshdastidar, D., Gutzeit, M., Carpentier, A., von Luxburg, U. Two-sample tests for large random graphs using network statistics In Conference on Computational Learning Theory (COLT), Conference on Computational Learning Theory (COLT), 2017 (inproceedings)

Sajjadi, M. S. M., Alamgir, M., von Luxburg, U.

2016

Peer Grading in a Course on Algorithms and Data Structures: Machine Learning Algorithms do not Improve over Simple Baselines

Proceedings of the 3rd ACM conference on Learning @ Scale, pages: 369-378, (Editors: Haywood, J. and Aleven, V. and Kay, J. and Roll, I.), ACM, L@S, April 2016, (An earlier version of this paper had been presented at the ICML 2015 workshop for Machine Learning for Education.) (conference)

Arxiv Peer-Grading dataset request [BibTex]

2016

ei Sajjadi, M. S. M., Alamgir, M., von Luxburg, U. Peer Grading in a Course on Algorithms and Data Structures: Machine Learning Algorithms do not Improve over Simple Baselines Proceedings of the 3rd ACM conference on Learning @ Scale, pages: 369-378, (Editors: Haywood, J. and Aleven, V. and Kay, J. and Roll, I.), ACM, L@S, April 2016, (An earlier version of this paper had been presented at the ICML 2015 workshop for Machine Learning for Education.) (conference)

Arxiv Peer-Grading dataset request [BibTex]

2015

Peer grading in a course on algorithms and data structures

Sajjadi, M. S. M., Alamgir, M., von Luxburg, U.

Workshop on Machine Learning for Education (ML4Ed) at the 32th International Conference on Machine Learning (ICML), 2015 (conference)

2015

ei Sajjadi, M. S. M., Alamgir, M., von Luxburg, U. Peer grading in a course on algorithms and data structures Workshop on Machine Learning for Education (ML4Ed) at the 32th International Conference on Machine Learning (ICML), 2015 (conference)

Sajjadi, M. S. M., Alamgir, M., von Luxburg, U.

Peer grading in a course on algorithms and data structures

Workshop on Crowdsourcing and Machine Learning (CrowdML) Workshop on Machine Learning for Education (ML4Ed) at at the 32th International Conference on Machine Learning (ICML), 2015 (conference)

ei Sajjadi, M. S. M., Alamgir, M., von Luxburg, U. Peer grading in a course on algorithms and data structures Workshop on Crowdsourcing and Machine Learning (CrowdML) Workshop on Machine Learning for Education (ML4Ed) at at the 32th International Conference on Machine Learning (ICML), 2015 (conference)

2013

How the result of graph clustering methods depends on the construction of the graph

Maier, M., von Luxburg, U., Hein, M.

ESAIM: Probability & Statistics, 17, pages: 370-418, January 2013 (article)

Abstract

We study the scenario of graph-based clustering algorithms such as spectral clustering. Given a set of data points, one rst has to construct a graph on the data points and then apply a graph clustering algorithm to nd a suitable partition of the graph. Our main question is if and how the construction of the graph (choice of the graph, choice of parameters, choice of weights) in uences the outcome of the nal clustering result. To this end we study the convergence of cluster quality measures such as the normalized cut or the Cheeger cut on various kinds of random geometric graphs as the sample size tends to innity. It turns out that the limit values of the same objective function are systematically dierent on dierent types of graphs. This implies that clustering results systematically depend on the graph and can be very dierent for dierent types of graph. We provide examples to illustrate the implications on spectral clustering.

2013

ei Maier, M., von Luxburg, U., Hein, M. How the result of graph clustering methods depends on the construction of the graph ESAIM: Probability & Statistics, 17, pages: 370-418, January 2013 (article)

von Luxburg, U., Alamgir, M.

Density estimation from unweighted k-nearest neighbor graphs: a roadmap

In Advances in Neural Information Processing Systems 26, pages: 225-233, (Editors: C.J.C. Burges and L. Bottou and M. Welling and Z. Ghahramani and K.Q. Weinberger), 27th Annual Conference on Neural Information Processing Systems (NIPS), 2013 (inproceedings)

ei von Luxburg, U., Alamgir, M. Density estimation from unweighted k-nearest neighbor graphs: a roadmap In Advances in Neural Information Processing Systems 26, pages: 225-233, (Editors: C.J.C. Burges and L. Bottou and M. Welling and Z. Ghahramani and K.Q. Weinberger), 27th Annual Conference on Neural Information Processing Systems (NIPS), 2013 (inproceedings)

2012

How the initialization affects the stability of the k-means algorithm

Bubeck, S., Meila, M., von Luxburg, U.

ESAIM: Probability and Statistics, 16, pages: 436-452, January 2012 (article)

Web DOI [BibTex]

2012

ei Bubeck, S., Meila, M., von Luxburg, U. How the initialization affects the stability of the k-means algorithm ESAIM: Probability and Statistics, 16, pages: 436-452, January 2012 (article)

Web DOI [BibTex]

Clustering: Science or Art?

von Luxburg, U., Williamson, R., Guyon, I.

In JMLR Workshop and Conference Proceedings, Volume 27, pages: 65-79, Workshop on Unsupervised Learning and Transfer Learning, 2012 (inproceedings)

Abstract

We examine whether the quality of dierent clustering algorithms can be compared by a general, scientically sound procedure which is independent of particular clustering algorithms. We argue that the major obstacle is the diculty in evaluating a clustering algorithm without taking into account the context: why does the user cluster his data in the rst place, and what does he want to do with the clustering afterwards? We argue that clustering should not be treated as an application-independent mathematical problem, but should always be studied in the context of its end-use. Dierent techniques to evaluate clustering algorithms have to be developed for dierent uses of clustering. To simplify this procedure we argue that it will be useful to build a \taxonomy of clustering problems" to identify clustering applications which can be treated in a unied way and that such an eort will be more fruitful than attempting the impossible | developing \optimal" domain-independent clustering algorithms or even classifying clustering algorithms in terms of how they work.

ei von Luxburg, U., Williamson, R., Guyon, I. Clustering: Science or Art? In JMLR Workshop and Conference Proceedings, Volume 27, pages: 65-79, Workshop on Unsupervised Learning and Transfer Learning, 2012 (inproceedings)

Alamgir, M., von Luxburg, U.

Shortest path distance in random k-nearest neighbor graphs

In Proceedings of the 29th International Conference on Machine Learning, International Machine Learning Society, International Conference on Machine Learning (ICML), 2012 (inproceedings)

ei Alamgir, M., von Luxburg, U. Shortest path distance in random k-nearest neighbor graphs In Proceedings of the 29th International Conference on Machine Learning, International Machine Learning Society, International Conference on Machine Learning (ICML), 2012 (inproceedings)

Kpotufe, S., von Luxburg, U.

2011

Pruning nearest neighbor cluster trees

In pages: 225-232, (Editors: Getoor, L. , T. Scheffer), International Machine Learning Society, Madison, WI, USA, 28th International Conference on Machine Learning (ICML), July 2011 (inproceedings)

Abstract

Nearest neighbor ($k$-NN) graphs are widely used in machine learning and data mining applications, and our aim is to better understand what they reveal about the cluster structure of the unknown underlying distribution of points. Moreover, is it possible to identify spurious structures that might arise due to sampling variability? Our first contribution is a statistical analysis that reveals how certain subgraphs of a $k$-NN graph form a consistent estimator of the cluster tree of the underlying distribution of points. Our second and perhaps most important contribution is the following finite sample guarantee. We carefully work out the tradeoff between aggressive and conservative pruning and are able to guarantee the removal of all spurious cluster structures while at the same time guaranteeing the recovery of salient clusters. This is the first such finite sample result in the context of clustering.

2011

ei Kpotufe, S., von Luxburg, U. Pruning nearest neighbor cluster trees In pages: 225-232, (Editors: Getoor, L. , T. Scheffer), International Machine Learning Society, Madison, WI, USA, 28th International Conference on Machine Learning (ICML), July 2011 (inproceedings)

Risk-Based Generalizations of f-divergences

García-García, D., von Luxburg, U., Santos-Rodríguez, R.

In pages: 417-424, (Editors: Getoor, L. , T. Scheffer), International Machine Learning Society, Madison, WI, USA, 28th International Conference on Machine Learning (ICML), July 2011 (inproceedings)

Abstract

We derive a generalized notion of f-divergences, called (f,l)-divergences. We show that this generalization enjoys many of the nice properties of f-divergences, although it is a richer family. It also provides alternative definitions of standard divergences in terms of surrogate risks. As a first practical application of this theory, we derive a new estimator for the Kulback-Leibler divergence that we use for clustering sets of vectors.

ei García-García, D., von Luxburg, U., Santos-Rodríguez, R. Risk-Based Generalizations of f-divergences In pages: 417-424, (Editors: Getoor, L. , T. Scheffer), International Machine Learning Society, Madison, WI, USA, 28th International Conference on Machine Learning (ICML), July 2011 (inproceedings)

JMLR Workshop and Conference Proceedings Volume 19: COLT 2011

Kakade, S., von Luxburg, U.

pages: 834, MIT Press, Cambridge, MA, USA, 24th Annual Conference on Learning Theory , June 2011 (proceedings)

ei Kakade, S., von Luxburg, U. JMLR Workshop and Conference Proceedings Volume 19: COLT 2011 pages: 834, MIT Press, Cambridge, MA, USA, 24th Annual Conference on Learning Theory , June 2011 (proceedings)

von Luxburg, U., Schölkopf, B.

Statistical Learning Theory: Models, Concepts, and Results

In Handbook of the History of Logic, Vol. 10: Inductive Logic, 10, pages: 651-706, (Editors: Gabbay, D. M., Hartmann, S. and Woods, J. H.), Elsevier North Holland, Amsterdam, Netherlands, May 2011 (inbook)

Abstract

Statistical learning theory provides the theoretical basis for many of today's machine learning algorithms and is arguably one of the most beautifully developed branches of artificial intelligence in general. It originated in Russia in the 1960s and gained wide popularity in the 1990s following the development of the so-called Support Vector Machine (SVM), which has become a standard tool for pattern recognition in a variety of domains ranging from computer vision to computational biology. Providing the basis of new learning algorithms, however, was not the only motivation for developing statistical learning theory. It was just as much a philosophical one, attempting to answer the question of what it is that allows us to draw valid conclusions from empirical data. In this article we attempt to give a gentle, non-technical overview over the key ideas and insights of statistical learning theory. We do not assume that the reader has a deep background in mathematics, statistics, or computer science. Given the nature of the subject matter, however, some familiarity with mathematical concepts and notations and some intuitive understanding of basic probability is required. There exist many excellent references to more technical surveys of the mathematics of statistical learning theory: the monographs by one of the founders of statistical learning theory ([Vapnik, 1995], [Vapnik, 1998]), a brief overview over statistical learning theory in Section 5 of [Sch{\"o}lkopf and Smola, 2002], more technical overview papers such as [Bousquet et al., 2003], [Mendelson, 2003], [Boucheron et al., 2005], [Herbrich and Williamson, 2002], and the monograph [Devroye et al., 1996].

ei von Luxburg, U., Schölkopf, B. Statistical Learning Theory: Models, Concepts, and Results In Handbook of the History of Logic, Vol. 10: Inductive Logic, 10, pages: 651-706, (Editors: Gabbay, D. M., Hartmann, S. and Woods, J. H.), Elsevier North Holland, Amsterdam, Netherlands, May 2011 (inbook)

Alamgir, M., von Luxburg, U.

Phase transition in the family of p-resistances

In Advances in Neural Information Processing Systems 24, pages: 379-387, (Editors: J Shawe-Taylor and RS Zemel and P Bartlett and F Pereira and KQ Weinberger), Twenty-Fifth Annual Conference on Neural Information Processing Systems (NIPS), 2011 (inproceedings)

Abstract

We study the family of p-resistances on graphs for p ≥ 1. This family generalizes the standard resistance distance. We prove that for any fixed graph, for p=1, the p-resistance coincides with the shortest path distance, for p=2 it coincides with the standard resistance distance, and for p → ∞ it converges to the inverse of the minimal s-t-cut in the graph. Secondly, we consider the special case of random geometric graphs (such as k-nearest neighbor graphs) when the number n of vertices in the graph tends to infinity. We prove that an interesting phase-transition takes place. There exist two critical thresholds p^* and p^** such that if p < p^*, then the p-resistance depends on meaningful global properties of the graph, whereas if p > p^**, it only depends on trivial local quantities and does not convey any useful information. We can explicitly compute the critical values: p^* = 1 + 1/(d-1) and p^** = 1 + 1/(d-2) where d is the dimension of the underlying space (we believe that the fact that there is a small gap between p^* and p^** is an artifact of our proofs. We also relate our findings to Laplacian regularization and suggest to use q-Laplacians as regularizers, where q satisfies 1/p^* + 1/q = 1.

ei Alamgir, M., von Luxburg, U. Phase transition in the family of p-resistances In Advances in Neural Information Processing Systems 24, pages: 379-387, (Editors: J Shawe-Taylor and RS Zemel and P Bartlett and F Pereira and KQ Weinberger), Twenty-Fifth Annual Conference on Neural Information Processing Systems (NIPS), 2011 (inproceedings)

Alamgir, M., von Luxburg, U.

2010

Multi-agent random walks for local clustering

In Proceedings of the IEEE International Conference on Data Mining (ICDM 2010), pages: 18-27, (Editors: Webb, G. I., B. Liu, C. Zhang, D. Gunopulos, X. Wu), IEEE, Piscataway, NJ, USA, IEEE International Conference on Data Mining (ICDM), December 2010 (inproceedings)

Abstract

We consider the problem of local graph clustering where the aim is to discover the local cluster corresponding to a point of interest. The most popular algorithms to solve this problem start a random walk at the point of interest and let it run until some stopping criterion is met. The vertices visited are then considered the local cluster. We suggest a more powerful alternative, the multi-agent random walk. It consists of several agents connected by a fixed rope of length l. All agents move independently like a standard random walk on the graph, but they are constrained to have distance at most l from each other. The main insight is that for several agents it is harder to simultaneously travel over the bottleneck of a graph than for just one agent. Hence, the multi-agent random walk has less tendency to mistakenly merge two different clusters than the original random walk. In our paper we analyze the multi-agent random walk theoretically and compare it experimentally to the major local graph clustering algorithms from the literature. We find that our multi-agent random walk consistently outperforms these algorithms.

2010

ei Alamgir, M., von Luxburg, U. Multi-agent random walks for local clustering In Proceedings of the IEEE International Conference on Data Mining (ICDM 2010), pages: 18-27, (Editors: Webb, G. I., B. Liu, C. Zhang, D. Gunopulos, X. Wu), IEEE, Piscataway, NJ, USA, IEEE International Conference on Data Mining (ICDM), December 2010 (inproceedings)

Clustering stability: an overview

Foundations and Trends in Machine Learning, 2(3):235-274, July 2010 (article)

Abstract

A popular method for selecting the number of clusters is based on stability arguments: one chooses the number of clusters such that the corresponding clustering results are "most stable". In recent years, a series of papers has analyzed the behavior of this method from a theoretical point of view. However, the results are very technical and difficult to interpret for non-experts. In this paper we give a high-level overview about the existing literature on clustering stability. In addition to presenting the results in a slightly informal but accessible way, we relate them to each other and discuss their different implications.

ei von Luxburg, U. Clustering stability: an overview Foundations and Trends in Machine Learning, 2(3):235-274, July 2010 (article)

Getting lost in space: Large sample analysis of the resistance distance

von Luxburg, U., Radl, A., Hein, M.

In Advances in Neural Information Processing Systems 23, pages: 2622-2630, (Editors: Lafferty, J. , C. K.I. Williams, J. Shawe-Taylor, R. S. Zemel, A. Culotta), Curran, Red Hook, NY, USA, Twenty-Fourth Annual Conference on Neural Information Processing Systems (NIPS), 2010 (inproceedings)

Abstract

The commute distance between two vertices in a graph is the expected time it takes a random walk to travel from the first to the second vertex and back. We study the behavior of the commute distance as the size of the underlying graph increases. We prove that the commute distance converges to an expression that does not take into account the structure of the graph at all and that is completely meaningless as a distance function on the graph. Consequently, the use of the raw commute distance for machine learning purposes is strongly discouraged for large graphs and in high dimensions. As an alternative we introduce the amplified commute distance that corrects for the undesired large sample effects.

ei von Luxburg, U., Radl, A., Hein, M. Getting lost in space: Large sample analysis of the resistance distance In Advances in Neural Information Processing Systems 23, pages: 2622-2630, (Editors: Lafferty, J. , C. K.I. Williams, J. Shawe-Taylor, R. S. Zemel, A. Culotta), Curran, Red Hook, NY, USA, Twenty-Fourth Annual Conference on Neural Information Processing Systems (NIPS), 2010 (inproceedings)

2009

Generalized Clustering via Kernel Embeddings

Jegelka, S., Gretton, A., Schölkopf, B., Sriperumbudur, B., von Luxburg, U.

In KI 2009: AI and Automation, Lecture Notes in Computer Science, Vol. 5803, pages: 144-152, (Editors: B Mertsching and M Hund and Z Aziz), Springer, Berlin, Germany, 32nd Annual Conference on Artificial Intelligence (KI), September 2009 (inproceedings)

Abstract

We generalize traditional goals of clustering towards distinguishing components in a non-parametric mixture model. The clusters are not necessarily based on point locations, but on higher order criteria. This framework can be implemented by embedding probability distributions in a Hilbert space. The corresponding clustering objective is very general and relates to a range of common clustering concepts.

PDF PDF Web DOI [BibTex]

2009

ei Jegelka, S., Gretton, A., Schölkopf, B., Sriperumbudur, B., von Luxburg, U. Generalized Clustering via Kernel Embeddings In KI 2009: AI and Automation, Lecture Notes in Computer Science, Vol. 5803, pages: 144-152, (Editors: B Mertsching and M Hund and Z Aziz), Springer, Berlin, Germany, 32nd Annual Conference on Artificial Intelligence (KI), September 2009 (inproceedings)

PDF PDF Web DOI [BibTex]

A Geometric Approach to Confidence Sets for Ratios: Fieller’s Theorem, Generalizations, and Bootstrap

von Luxburg, U., Franz, V.

Statistica Sinica, 19(3):1095-1117, July 2009 (article)

Abstract

We present a geometric method to determine confidence sets for the ratio E(Y)/E(X) of the means of random variables X and Y. This method reduces the problem of constructing confidence sets for the ratio of two random variables to the problem of constructing confidence sets for the means of one-dimensional random variables. It is valid in a large variety of circumstances. In the case of normally distributed random variables, the so constructed confidence sets coincide with the standard Fieller confidence sets. Generalizations of our construction lead to definitions of exact and conservative confidence sets for very general classes of distributions, provided the joint expectation of (X,Y) exists and the linear combinations of the form aX + bY are well-behaved. Finally, our geometric method allows to derive a very simple bootstrap approach for constructing conservative confidence sets for ratios which perform favorably in certain situations, in particular in the asymmetric heavy-tailed regime.

PDF PDF Web [BibTex]

ei von Luxburg, U., Franz, V. A Geometric Approach to Confidence Sets for Ratios: Fieller’s Theorem, Generalizations, and Bootstrap Statistica Sinica, 19(3):1095-1117, July 2009 (article)

PDF PDF Web [BibTex]

Influence of graph construction on graph-based clustering measures

Maier, M., von Luxburg, U., Hein, M.

In Advances in neural information processing systems 21, pages: 1025-1032, (Editors: Koller, D. , D. Schuurmans, Y. Bengio, L. Bottou), Curran, Red Hook, NY, USA, Twenty-Second Annual Conference on Neural Information Processing Systems (NIPS), June 2009 (inproceedings)

Abstract

Graph clustering methods such as spectral clustering are defined for general weighted graphs. In machine learning, however, data often is not given in form of a graph, but in terms of similarity (or distance) values between points. In this case, first a neighborhood graph is constructed using the similarities between the points and then a graph clustering algorithm is applied to this graph. In this paper we investigate the influence of the construction of the similarity graph on the clustering results. We first study the convergence of graph clustering criteria such as the normalized cut (Ncut) as the sample size tends to infinity. We find that the limit expressions are different for different types of graph, for example the r-neighborhood graph or the k-nearest neighbor graph. In plain words: Ncut on a kNN graph does something systematically different than Ncut on an r-neighborhood graph! This finding shows that graph clustering criteria cannot be studied independently of the kind of graph they are applied to. We also provide examples which show that these differences can be observed for toy and real data already for rather small sample sizes.

ei Maier, M., von Luxburg, U., Hein, M. Influence of graph construction on graph-based clustering measures In Advances in neural information processing systems 21, pages: 1025-1032, (Editors: Koller, D. , D. Schuurmans, Y. Bengio, L. Bottou), Curran, Red Hook, NY, USA, Twenty-Second Annual Conference on Neural Information Processing Systems (NIPS), June 2009 (inproceedings)

Optimal construction of k-nearest-neighbor graphs for identifying noisy clusters

Maier, M., Hein, M., von Luxburg, U.

Theoretical Computer Science, 410(19):1749-1764, April 2009 (article)

Abstract

We study clustering algorithms based on neighborhood graphs on a random sample of data points. The question we ask is how such a graph should be constructed in order to obtain optimal clustering results. Which type of neighborhood graph should one choose, mutual k-nearest-neighbor or symmetric k-nearest-neighbor? What is the optimal parameter k? In our setting, clusters are defined as connected components of the t-level set of the underlying probability distribution. Clusters are said to be identified in the neighborhood graph if connected components in the graph correspond to the true underlying clusters. Using techniques from random geometric graph theory, we prove bounds on the probability that clusters are identified successfully, both in a noise-free and in a noisy setting. Those bounds lead to several conclusions. First, k has to be chosen surprisingly high (rather of the order n than of the order logn) to maximize the probability of cluster identification. Secondly, the major difference between the mutual and the symmetric k-nearest-neighbor graph occurs when one attempts to detect the most significant cluster only.

ei Maier, M., Hein, M., von Luxburg, U. Optimal construction of k-nearest-neighbor graphs for identifying noisy clusters Theoretical Computer Science, 410(19):1749-1764, April 2009 (article)

Bubeck, S., von Luxburg, U.

Nearest Neighbor Clustering: A Baseline Method for Consistent Clustering with Arbitrary Objective Functions

Journal of Machine Learning Research, 10, pages: 657-698, March 2009 (article)

Abstract

Clustering is often formulated as a discrete optimization problem. The objective is to find, among all partitions of the data set, the best one according to some quality measure. However, in the statistical setting where we assume that the finite data set has been sampled from some underlying space, the goal is not to find the best partition of the given sample, but to approximate the true partition of the underlying space. We argue that the discrete optimization approach usually does not achieve this goal, and instead can lead to inconsistency. We construct examples which provably have this behavior. As in the case of supervised learning, the cure is to restrict the size of the function classes under consideration. For appropriate small function classes we can prove very general consistency theorems for clustering optimization schemes. As one particular algorithm for clustering with a restricted function space we introduce nearest neighbor clustering. Similar to the k-nearest neighbor classifier in supervised learning, this algorithm can be seen as a general baseline algorithm to minimize arbitrary clustering objective functions. We prove that it is statistically consistent for all commonly used clustering objective functions.

ei Bubeck, S., von Luxburg, U. Nearest Neighbor Clustering: A Baseline Method for Consistent Clustering with Arbitrary Objective Functions Journal of Machine Learning Research, 10, pages: 657-698, March 2009 (article)

2008

Consistent Minimization of Clustering Objective Functions

von Luxburg, U., Bubeck, S., Jegelka, S., Kaufmann, M.

In Advances in neural information processing systems 20, pages: 961-968, (Editors: Platt, J. C., D. Koller, Y. Singer, S. Roweis), Curran, Red Hook, NY, USA, Twenty-First Annual Conference on Neural Information Processing Systems (NIPS), September 2008 (inproceedings)

Abstract

Clustering is often formulated as a discrete optimization problem. The objective is to find, among all partitions of the data set, the best one according to some quality measure. However, in the statistical setting where we assume that the finite data set has been sampled from some underlying space, the goal is not to find the best partition of the given sample, but to approximate the true partition of the underlying space. We argue that the discrete optimization approach usually does not achieve this goal. As an alternative, we suggest the paradigm of nearest neighbor clustering&amp;amp;amp;amp;amp;amp;amp;amp;amp;lsquo;&amp;amp;amp;amp;amp;amp;amp;amp;amp;lsquo;. Instead of selecting the best out of all partitions of the sample, it only considers partitions in some restricted function class. Using tools from statistical learning theory we prove that nearest neighbor clustering is statistically consistent. Moreover, its worst case complexity is polynomial by co nstructi on, and it can b e implem ented wi th small average case co mplexity using b ranch an d bound.

2008

ei von Luxburg, U., Bubeck, S., Jegelka, S., Kaufmann, M. Consistent Minimization of Clustering Objective Functions In Advances in neural information processing systems 20, pages: 961-968, (Editors: Platt, J. C., D. Koller, Y. Singer, S. Roweis), Curran, Red Hook, NY, USA, Twenty-First Annual Conference on Neural Information Processing Systems (NIPS), September 2008 (inproceedings)

Relating clustering stability to properties of cluster boundaries

Ben-David, S., von Luxburg, U.

In COLT 2008, pages: 379-390, (Editors: Servedio, R. A., T. Zhang), Omnipress, Madison, WI, USA, 21st Annual Conference on Learning Theory, July 2008 (inproceedings)

Abstract

In this paper, we investigate stability-based methods for cluster model selection, in particular to select the number K of clusters. The scenario under consideration is that clustering is performed by minimizing a certain clustering quality function, and that a unique global minimizer exists. On the one hand we show that stability can be upper bounded by certain properties of the optimal clustering, namely by the mass in a small tube around the cluster boundaries. On the other hand, we provide counterexamples which show that a reverse statement is not true in general. Finally, we give some examples and arguments why, from a theoretic point of view, using clustering stability in a high sample setting can be problematic. It can be seen that distribution-free guarantees bounding the difference between the finite sample stability and the true stability cannot exist, unless one makes strong assumptions on the underlying distribution.

ei Ben-David, S., von Luxburg, U. Relating clustering stability to properties of cluster boundaries In COLT 2008, pages: 379-390, (Editors: Servedio, R. A., T. Zhang), Omnipress, Madison, WI, USA, 21st Annual Conference on Learning Theory, July 2008 (inproceedings)

von Luxburg, U., Belkin, M., Bousquet, O.

Consistency of Spectral Clustering

Annals of Statistics, 36(2):555-586, April 2008 (article)

Abstract

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.

ei von Luxburg, U., Belkin, M., Bousquet, O. Consistency of Spectral Clustering Annals of Statistics, 36(2):555-586, April 2008 (article)

2007

A Tutorial on Spectral Clustering

Statistics and Computing, 17(4):395-416, December 2007 (article)

Abstract

In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement, can be solved efficiently by standard linear algebra software, and very often outperforms traditional clustering algorithms such as the k-means algorithm. On the first glance spectral clustering appears slightly mysterious, and it is not obvious to see why it works at all and what it really does. The goal of this tutorial is to give some intuition on those questions. We describe different graph Laplacians and their basic properties, present the most common spectral clustering algorithms, and derive those algorithms from scratch by several different approaches. Advantages and disadvantages of the different spectral clustering algorithms are discussed.

2007

ei von Luxburg, U. A Tutorial on Spectral Clustering Statistics and Computing, 17(4):395-416, December 2007 (article)

Cluster Identification in Nearest-Neighbor Graphs

Maier, M., Hein, M., von Luxburg, U.

In ALT 2007, pages: 196-210, (Editors: Hutter, M. , R. A. Servedio, E. Takimoto), Springer, Berlin, Germany, 18th International Conference on Algorithmic Learning Theory, October 2007 (inproceedings)

Abstract

Assume we are given a sample of points from some underlying distribution which contains several distinct clusters. Our goal is to construct a neighborhood graph on the sample points such that clusters are ``identified&lsquo;&lsquo;: that is, the subgraph induced by points from the same cluster is connected, while subgraphs corresponding to different clusters are not connected to each other. We derive bounds on the probability that cluster identification is successful, and use them to predict ``optimal&lsquo;&lsquo; values of k for the mutual and symmetric k-nearest-neighbor graphs. We point out different properties of the mutual and symmetric nearest-neighbor graphs related to the cluster identification problem.

ei Maier, M., Hein, M., von Luxburg, U. Cluster Identification in Nearest-Neighbor Graphs In ALT 2007, pages: 196-210, (Editors: Hutter, M. , R. A. Servedio, E. Takimoto), Springer, Berlin, Germany, 18th International Conference on Algorithmic Learning Theory, October 2007 (inproceedings)

Graph Laplacians and their Convergence on Random Neighborhood Graphs

Hein, M., Audibert, J., von Luxburg, U.

Journal of Machine Learning Research, 8, pages: 1325-1370, June 2007 (article)

Abstract

Given a sample from a probability measure with support on a submanifold in Euclidean space one can construct a neighborhood graph which can be seen as an approximation of the submanifold. The graph Laplacian of such a graph is used in several machine learning methods like semi-supervised learning, dimensionality reduction and clustering. In this paper we determine the pointwise limit of three different graph Laplacians used in the literature as the sample size increases and the neighborhood size approaches zero. We show that for a uniform measure on the submanifold all graph Laplacians have the same limit up to constants. However in the case of a non-uniform measure on the submanifold only the so called random walk graph Laplacian converges to the weighted Laplace-Beltrami operator.

PDF PDF [BibTex]

ei Hein, M., Audibert, J., von Luxburg, U. Graph Laplacians and their Convergence on Random Neighborhood Graphs Journal of Machine Learning Research, 8, pages: 1325-1370, June 2007 (article)

PDF PDF [BibTex]

Cluster Identification in Nearest-Neighbor Graphs

Maier, M., Hein, M., von Luxburg, U.

(163), Max-Planck-Institute for Biological Cybernetics, Tübingen, Germany, May 2007 (techreport)

Abstract

Assume we are given a sample of points from some underlying distribution which contains several distinct clusters. Our goal is to construct a neighborhood graph on the sample points such that clusters are ``identified‘‘: that is, the subgraph induced by points from the same cluster is connected, while subgraphs corresponding to different clusters are not connected to each other. We derive bounds on the probability that cluster identification is successful, and use them to predict ``optimal‘‘ values of k for the mutual and symmetric k-nearest-neighbor graphs. We point out different properties of the mutual and symmetric nearest-neighbor graphs related to the cluster identification problem.

ei Maier, M., Hein, M., von Luxburg, U. Cluster Identification in Nearest-Neighbor Graphs (163), Max-Planck-Institute for Biological Cybernetics, Tübingen, Germany, May 2007 (techreport)

2006

A Sober Look at Clustering Stability

Ben-David, S., von Luxburg, U., Pal, D.

In COLT 2006, pages: 5-19, (Editors: Lugosi, G. , H.-U. Simon), Springer, Berlin, Germany, 19th Annual Conference on Learning Theory, September 2006 (inproceedings)

Abstract

Stability is a common tool to verify the validity of sample based algorithms. In clustering it is widely used to tune the parameters of the algorithm, such as the number k of clusters. In spite of the popularity of stability in practical applications, there has been very little theoretical analysis of this notion. In this paper we provide a formal definition of stability and analyze some of its basic properties. Quite surprisingly, the conclusion of our analysis is that for large sample size, stability is fully determined by the behavior of the objective function which the clustering algorithm is aiming to minimize. If the objective function has a unique global minimizer, the algorithm is stable, otherwise it is unstable. In particular we conclude that stability is not a well-suited tool to determine the number of clusters - it is determined by the symmetries of the data which may be unrelated to clustering parameters. We prove our results for center-based clusterings and for spectral clustering, and support our conclusions by many examples in which the behavior of stability is counter-intuitive.

2006

ei Ben-David, S., von Luxburg, U., Pal, D. A Sober Look at Clustering Stability In COLT 2006, pages: 5-19, (Editors: Lugosi, G. , H.-U. Simon), Springer, Berlin, Germany, 19th Annual Conference on Learning Theory, September 2006 (inproceedings)

A tutorial on spectral clustering

(149), Max Planck Institute for Biological Cybernetics, Tübingen, August 2006 (techreport)

Abstract

In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement, can be solved efficiently by standard linear algebra software, and very often outperforms traditional clustering algorithms such as the k-means algorithm. Nevertheless, on the first glance spectral clustering looks a bit mysterious, and it is not obvious to see why it works at all and what it really does. This article is a tutorial introduction to spectral clustering. We describe different graph Laplacians and their basic properties, present the most common spectral clustering algorithms, and derive those algorithms from scratch by several different approaches. Advantages and disadvantages of the different spectral clustering algorithms are discussed.

ei von Luxburg, U. A tutorial on spectral clustering (149), Max Planck Institute for Biological Cybernetics, Tübingen, August 2006 (techreport)

von Luxburg, U., Bousquet, O., Belkin, M.

2005

Limits of Spectral Clustering

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)

Abstract

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.

2005

ei von Luxburg, U., Bousquet, O., Belkin, M. Limits of Spectral Clustering 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)

From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians

Hein, M., Audibert, J., von Luxburg, U.

In Proceedings of the 18th Conference on Learning Theory (COLT), pages: 470-485, Conference on Learning Theory, 2005, Student Paper Award (inproceedings)

Abstract

In the machine learning community it is generally believed that graph Laplacians corresponding to a finite sample of data points converge to a continuous Laplace operator if the sample size increases. Even though this assertion serves as a justification for many Laplacian-based algorithms, so far only some aspects of this claim have been rigorously proved. In this paper we close this gap by establishing the strong pointwise consistency of a family of graph Laplacians with data-dependent weights to some weighted Laplace operator. Our investigation also includes the important case where the data lies on a submanifold of $R^d$.

ei Hein, M., Audibert, J., von Luxburg, U. From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians In Proceedings of the 18th Conference on Learning Theory (COLT), pages: 470-485, Conference on Learning Theory, 2005, Student Paper Award (inproceedings)

Towards a Statistical Theory of Clustering. Presented at the PASCAL workshop on clustering, London

von Luxburg, U., Ben-David, S.

Presented at the PASCAL workshop on clustering, London, 2005 (techreport)

Abstract

The goal of this paper is to discuss statistical aspects of clustering in a framework where the data to be clustered has been sampled from some unknown probability distribution. Firstly, the clustering of the data set should reveal some structure of the underlying data rather than model artifacts due to the random sampling process. Secondly, the more sample points we have, the more reliable the clustering should be. We discuss which methods can and cannot be used to tackle those problems. In particular we argue that generalization bounds as they are used in statistical learning theory of classification are unsuitable in a general clustering framework. We suggest that the main replacements of generalization bounds should be convergence proofs and stability considerations. This paper should be considered as a road map paper which identifies important questions and potentially fruitful directions for future research about statistical clustering. We do not attempt to present a complete statistical theory of clustering.

ei von Luxburg, U., Ben-David, S. Towards a Statistical Theory of Clustering. Presented at the PASCAL workshop on clustering, London Presented at the PASCAL workshop on clustering, London, 2005 (techreport)

Bousquet, O., von Luxburg, U., Rätsch, G.

2004

Advanced Lectures on Machine Learning

ML Summer Schools 2003, LNAI 3176, pages: 240, Springer, Berlin, Germany, ML Summer Schools, September 2004 (proceedings)

Abstract

Machine Learning has become a key enabling technology for many engineering applications, investigating scientific questions and theoretical problems alike. To stimulate discussions and to disseminate new results, a summer school series was started in February 2002, the documentation of which is published as LNAI 2600. This book presents revised lectures of two subsequent summer schools held in 2003 in Canberra, Australia, and in T{\"u}bingen, Germany. The tutorial lectures included are devoted to statistical learning theory, unsupervised learning, Bayesian inference, and applications in pattern recognition; they provide in-depth overviews of exciting new developments and contain a large number of references. Graduate students, lecturers, researchers and professionals alike will find this book a useful resource in learning and teaching machine learning.

2004

ei Bousquet, O., von Luxburg, U., Rätsch, G. Advanced Lectures on Machine Learning ML Summer Schools 2003, LNAI 3176, pages: 240, Springer, Berlin, Germany, ML Summer Schools, September 2004 (proceedings)

von Luxburg, U., Bousquet, O.

Distance-Based Classification with Lipschitz Functions

Journal of Machine Learning Research, 5, pages: 669-695, June 2004 (article)

Abstract

The goal of this article is to develop a framework for large margin classification in metric spaces. We want to find a generalization of linear decision functions for metric spaces and define a corresponding notion of margin such that the decision function separates the training points with a large margin. It will turn out that using Lipschitz functions as decision functions, the inverse of the Lipschitz constant can be interpreted as the size of a margin. In order to construct a clean mathematical setup we isometrically embed the given metric space into a Banach space and the space of Lipschitz functions into its dual space. To analyze the resulting algorithm, we prove several representer theorems. They state that there always exist solutions of the Lipschitz classifier which can be expressed in terms of distance functions to training points. We provide generalization bounds for Lipschitz classifiers in terms of the Rademacher complexities of some Lipschitz function classes. The generality of our approach can be seen from the fact that several well-known algorithms are special cases of the Lipschitz classifier, among them the support vector machine, the linear programming machine, and the 1-nearest neighbor classifier.

PDF PostScript PDF [BibTex]

ei von Luxburg, U., Bousquet, O. Distance-Based Classification with Lipschitz Functions Journal of Machine Learning Research, 5, pages: 669-695, June 2004 (article)

PDF PostScript PDF [BibTex]

A Compression Approach to Support Vector Model Selection

von Luxburg, U., Bousquet, O., Schölkopf, B.

Journal of Machine Learning Research, 5, pages: 293-323, April 2004 (article)

Abstract

In this paper we investigate connections between statistical learning theory and data compression on the basis of support vector machine (SVM) model selection. Inspired by several generalization bounds we construct "compression coefficients" for SVMs which measure the amount by which the training labels can be compressed by a code built from the separating hyperplane. The main idea is to relate the coding precision to geometrical concepts such as the width of the margin or the shape of the data in the feature space. The so derived compression coefficients combine well known quantities such as the radius-margin term R^2/rho^2, the eigenvalues of the kernel matrix, and the number of support vectors. To test whether they are useful in practice we ran model selection experiments on benchmark data sets. As a result we found that compression coefficients can fairly accurately predict the parameters for which the test error is minimized.

ei von Luxburg, U., Bousquet, O., Schölkopf, B. A Compression Approach to Support Vector Model Selection Journal of Machine Learning Research, 5, pages: 293-323, April 2004 (article)

Statistical Learning with Similarity and Dissimilarity Functions

pages: 1-166, Technische Universität Berlin, Germany, Technische Universität Berlin, Germany, 2004 (phdthesis)

ei von Luxburg, U. Statistical Learning with Similarity and Dissimilarity Functions pages: 1-166, Technische Universität Berlin, Germany, Technische Universität Berlin, Germany, 2004 (phdthesis)

von Luxburg, U., Bousquet, O., Belkin, M.

On the Convergence of Spectral Clustering on Random Samples: The Normalized Case

In Proceedings of the 17th Annual Conference on Learning Theory, pages: 457-471, Proceedings of the 17th Annual Conference on Learning Theory, 2004 (inproceedings)

ei von Luxburg, U., Bousquet, O., Belkin, M. On the Convergence of Spectral Clustering on Random Samples: The Normalized Case In Proceedings of the 17th Annual Conference on Learning Theory, pages: 457-471, Proceedings of the 17th Annual Conference on Learning Theory, 2004 (inproceedings)