Timezone: »

 
Oral
Cluster Stability for Finite Samples
Ohad Shamir · Naftali Tishby

Tue Dec 04 05:00 PM -- 05:20 PM (PST) @
in Session 3: Theory and Sequential Decision Making »

Cluster stability has recently received growing attention as a cluster validation criterion in a sample-based framework. However, recent work [2] has shown that as the sample size increases to infinity, any clustering model will usually become asymptotically stable. This led to the conclusion that stability is lacking as a theoretical and practical tool. The discrepancy between this conclusion and the success of stability in practice has remained an open question, which we attempt to address. Our theoretical approach is that stability, as used by cluster validation algorithms, is similar in certain respects to measures of generalization in a model-selection framework. In such cases, the model chosen governs the convergence rate of generalization bounds. By arguing that these rates are more important than the sample size, we are led to the prediction that stability-based cluster validation algorithms should not degrade with increasing sample size, despite the asymptotic universal stability. This prediction is substantiated by a theoretical analysis as well as several empirical results. We conclude that stability remains a meaningful theoretical and practical criterion for cluster validity over finite samples.

Author Information

Ohad Shamir (Weizmann Institute of Science)
Naftali Tishby (The Hebrew University Jerusalem)

Naftali Tishby, is a professor of computer science and the director of the Interdisciplinary Center for Neural Computation (ICNC) at the Hebrew university of Jerusalem. He received his Ph.D. in theoretical physics from the Hebrew University and was a research staff member at MIT and Bell Labs from 1985 to 1991. He was also a visiting professor at Princeton NECI, the University of Pennsylvania and the University of California at Santa Barbara. Dr. Tishby is a leader of machine learning research and computational neuroscience. He was among the first to introduce methods from statistical physics into learning theory, and dynamical systems techniques in speech processing. His current research is at the interface between computer science, statistical physics and computational neuroscience and concerns the foundations of biological information processing and the connections between dynamics and information.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors