Abstract: Unsupervised learning is widely recognized as one of the most important challenges facing machine learning nowadays.However, unlike supervised learning, our current theoretical understanding of those tasks,and in particular of clustering, is very rudimentary. Although hundreds of clustering papers are being published every year, there is hardly any work reasoning about clustering independently of any particular algorithm, objective function, or generative data model.
My talk will focus on such clustering research. I will discuss two aspects in which theory could play a significant role in guiding the use of clustering tools. The first is model selection - how should a user pick an appropriate clustering tool for a given clustering problem, and how should the parameters of such an algorithmic tool be tuned? In contrast with other common computational tasks, in clustering, different algorithms often yield drastically different outcomes. Therefore, the choice of a clustering algorithm may play a crucial role in the usefulness of an output clustering solution. However, there currently exist no methodical guidance for clustering tool selection for a given clustering task. I will describe some recent proposals aiming to address this crucial lacuna.
The second aspect of clustering that I will address is the complexity of computing a cost minimizing clustering (given some clustering objective function). Once a clustering model(or objective) has been picked, the task becomes an optimization problem.
While most of the clustering objective optimization problems are computationally infeasible, they are being carried out routinely in practice.This theory-practice gap has attracted significant research attention recently. I will describe some of the theoretical attempts to address this gap and discuss how close do they bring us to a satisfactory understanding of the computational resources needed for achieving good clustering solutions.
Bio: I grew up in Jerusalem. I studied physics, mathematics and psychology at the Hebrew University, receiving my PhD in pure math under the supervision of Saharon Shelah and Menachem Magidor. In I 1987 joined the CS Department at the Technion. I held visiting faculty positions at the Australian National University in Canberra (1997-8) and at Cornell University (2001-2004). In August 2004 I moved to Canada as a professor at the School of Computer Science at the University of Waterloo.
I have served as an editor in a couple of CS theory journals, as a Program Committee chair, and member of the steering committees for COLT and ALT (the major ML theory conferences) and several times as area chair for NIPS and ICML.
My research interests span a wide spectrum of topics in the foundations of computer science and its applications, with a particular emphasis on statistical and computational machine learning. The common thread throughout my research is aiming to provide mathematical formulation and understanding of real world problems. In particular, I have been looking at popular machine learning and data mining paradigms that seem to lack clear theoretical justification (such as unsupervised learning, clustering, transfer learning, semi-supervised learning and crowd sourcing).