ITR: New directions in clustering and learning

Princeton University, Princeton NJ

Investigators

Abstract

New directions in clustering and learning Faced with ever-larger amounts of data, researchers, government institutions, corporations and even the general public seek tools that help them deal with large bodies of information, identify patterns in it, learn what these patterns mean, and act upon that information in a timely fashion. Developing such tools involves a novel and interesting blend of algorithms, statistics, AI, and machine learning. The project assembles a team of experts (four from academia and two from industry) in these areas to attack an interesting and meaningful subset of such problems which have the general flavor of clustering or learning. The defining philosophy of this proposal is that no clear boundary Separates the twin notions of clustering and learning. Clustering is usually driven by the end goal of learning, but can also be viewed as a learning task in itself since it results in a more compact description of the data. By the same token all learning involves clustering of some sort, and in fact this viewpoint is implicit in recent papers in the learning literature. The project takes an integrated view of the entire problem of learning patterns in data, starting from streaming computations that might produce representative sketches of the data as it streams by, to problems of clustering data into meaninful patterns (with attendant problems of outlier removal, multiobjective optimization etc.), to learning algorithms that fit sophisticated models (SVMs, bayesian nets, gaussian mixtures etc.) for inference and reasoning tasks. The investigators believe that all these disparate algorithmic efforts have unifying ideas. Furthermore, their synergistic approach throws up several interesting ideas of its own that could lead to significant advances. Examples: include using coding theoretic ideas in disparate applications such as Multiclass learning (a broad class of learning problems including text and speech categorization, part-of-speech tagging, gesture recognition etc.) and shape recognition in vision; the use of clustering ideas to do dimension reduction (offering an alternative to popular SVD based approaches), and using ideas from approximation algorithms and clustering to do near-optimal model fitting for models such as bayesian nets. The project also includes a management and educational plan that involves dissemination of the ideas of this research through development of new courses and also pieces of learning software that will be placed in the public domain. Algorithms developed in as part of this project will be tested on large datasets, including those obtained from Google Inc. Some algorithmic ideas will also be implemented in industry (including Google).