[Colloquium] TTI-C Talk 12/3 @ 3:00 pm

[Katherine Cumming]

TOYOTA TECHNOLOGICAL INSTITUTE TALK
 
Speaker: Rocco Servedio
Speaker's homepage: http://www1.cs.columbia.edu/%7Erocco/
 
 
Title: On Learning Random Decision Trees and DNF Formulas
 
 
Time: Friday, December 3rd, 3:00pm
Place: TTI-C conference room (1427 E. 60th St. - 2nd Floor) 
Abstract: The problem of average-case learning for decision trees is as
follows: a decision tree T (over Boolean features x1,...,xn) is chosen
at random from some natural distribution over decision trees. The
learning algorithm is given access to uniform random examples which are
labeled according to T. The job of the learning algorithm is to
efficiently construct a hypothesis function f which closely agrees with
the unknown randomly chosen tree T. Decision trees are an expressive
representation for Boolean functions which have proven hard to learn in
worst-case learning models. An even more challenging problem is that of
learning an unknown DNF (Disjunctive Normal Form formula, i.e. an AND of
ORs of Boolean variables) or CNF in the worst case. In this work we give
the first efficient algorithm for the average-case versions of these
learning problems. Our algorithm for decision trees runs in polynomial
time for random trees of logarithmic depth. Our algorithm for DNF and
CNF formulas runs in polynomial time for random formulas with a
subquadratic number of AND gates. The talk will be self-contained and
assumes no prior background in computational learning theory. This is
joint work with Jeff Jackson.
 
 
 
If you have questions, or would like to meet the speaker, please contact
Katherine at 4-1994 or kcumming at tti-c.org
 
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20041129/4c0f4b8e/attachment.htm