CAREER: Algorithms for Unsupervised Learning

University Of California-San Diego, La Jolla CA

Investigators

Abstract

The goal of this research is to develop algorithms with rigorous performance guarantees for core machine learning tasks. Although the most common guarantee in the current literature is that of local optimality in the solution space, this project aims to use stronger performance criteria, such as quantitative bounds on the ratio by which the cost of the learned solution exceeds that of the global optimum, both to guide the development of new algorithms and to compare existing ones. This project will focus on two canonical unsupervised learning tasks: hierarchical clustering and learning the structure of directed probabilistic (Bayesian) nets. Both models are already in widespread use for analyzing massive data sets; better algorithms will increase their effectiveness and reliability, and will involve technical tools that are likely to be of broader use for other machine learning and statistical tasks. The results of this research project will be integrated into a new course that focuses on algorithmic aspects of machine learning; the resulting educational materials will be made available to the academic community.