Shai Ben-David, David R. Cheriton School of Computer Science Clustering
1,645 views · Published 1 November 2017 · 1:00:04 · Indexed 27 October 2026
Channel: uwaterloo · 2017 · Education
Unsupervised learning is widely recognized as one of the most important challenges facing machine learning nowadays. However, in spite of hundreds of papers on the topic being published every year, current theoretical understanding and practical implementations of such tasks, and in particular of clustering, is very rudimentary. My talk will focus on clustering. The first challenge I will address 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, currently there exists no methodical guidance for clustering tool selection for a given clustering task. I will explain the severity of this problem and 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). 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 survey 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.