Interactive Structure Learning

Speaker: Prof. Sanjoy Dasgupta
Affiliation: UC San Diego

Abstract:  We introduce interactive structure learning, an abstract problem in which a structure (classifier, clustering, topic model, knowledge graph, etc.) is to be learned, using unlabeled data as well as rounds of human interaction. This formalism covers many situations of practical interest, such as query-based classifier learning and interactive clustering.

Interactive structure learning presents a host of statistical and algorithmic challenges. We discuss two such results:

1. Learning from partial correction.

Earlier models of interaction have typically adopted a question-answer paradigm: the learner asks a question and a human expert answers it. Our abstract model allows a richer and more flexible interface, where the learner provides a small snapshot of its current model (for instance, the restriction of a clustering to a few points), and the expert can selectively fix any part of it.

This kind of feedback is not iid. Nonetheless, we show how statistical generalization bounds can be given for structures learned in this way. The proof technique may also be of interest in other situations with non-iid sampling.

2. Interactive hierarchical clustering.

We present a general-purpose algorithm for interactive structure learning and illustrate how it works in the case of hierarchical clustering.

Along the way, we present a novel cost function for hierarchical clustering, as well as an efficient algorithm for approximately minimizing this cost.

Biography: Sanjoy Dasgupta is a Professor in the Department of Computer Science and Engineering at UC San Diego. He works on algorithms for machine learning, with a focus on unsupervised and interactive learning.

For more information, contact Prof. Suhas Diggavi (suhasdiggavi@ucla.edu)

Date/Time:
Date(s) - Oct 16, 2017
12:30 pm - 1:30 pm

Location:
EE-IV Shannon Room #54-134
420 Westwood Plaza - 5th Flr., Los Angeles CA 90095