[Colloquium] TTIC Talks: Varun Kanade, Harvard

[Liv Leader]

REMINDER:

When:     Wednesday, February 8 @ 11 a.m.

Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor

Who:      Varun Kanade, Harvard

Title:       Agnostic boosting and other algorithms

Agnostic learning was introduced by Haussler (1992) and Kearns, Schapire and
Sellie (1994) as a generalization of Valiant's PAC Learning model (1984).
Unlike the PAC model, where the data is assumed to be labeled perfectly
according to some concept (e.g. linear spearator or decision tree), the
agnostic
model makes no assumption on how the data is actually labeled. The goal in
agnostic learning is to find a hypothesis that predicts almost as well as
the
best hypothesis from a certain class of interest. Thus, agnostic model
captures
real-word learning questions very well. However, constructing efficient
learning
algorithms in the agnostic setting has proved very difficult.

In this talk, we present a boosting algorithm in the agnostic setting. Our
boosting algorithm is a simple potential-based algorithm and is similar to
Adaboost, Madaboost and other practical boosting algorithms. A remarkable
property of our boosting algorithm is that it does not change the weight of
the
unlabeled examples, but instead only relabels the dataset. We show that
while of
theoretical interest in itself, this boosting algorithm also simplifies
greatly
known agnostic learning algorithms for decision trees and halfspaces.

We also consider one-sided error agnostic learning, where certain types of
errors are more costly than others. This captures many learning settings
such as
SPAM classification. We show that polynomial-sized DNFs can be learned in
this
model.

Parts of work is joint with Adam T. Kalai and Yishay Mansour.

Host: Nati Srebro, Nati at ttic.edu

-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
<http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120208/6c4a9a3f/attachment-0001.htm