[Colloquium] Reminder: TTI-C Interns Talk: Tomorrow: August 30th (12:15 &2:00pm)

[Katherine Cumming]

TOYOTA TECHNOLOGICAL INSTITUTE TALKS
 
2005 Summer Interns
 
Speaker 1:  Nina Balcan, Carnegie Mellon University   
Speaker's homepage:  http://www.cs.cmu.edu/~ninamf/
 
Time:  Tuesday, August 30th @ 12:15pm - Lunch
Location:  TTI-C Conference Room 
 
 
Title: An Augmented PAC Model for Semi-Supervised Learning
 
 
Abstract: There has been growing interest in practice in using unlabeled
data together with labeled data in machine learning, and a number of
different approaches have been developed. However, the assumptions these
methods are based on are often quite distinct and not captured by
standard theoretical models. In this work we describe a PAC-style model
designed with semi-supervised learning in mind, that can be used to help
thinking about the problem of learning from labeled and unlabeled data
and many of the different approaches taken. Our model provides a unified
framework for analyzing when and why unlabeled data can help, and in
which one can discuss both algorithmic and sample complexity issues.
 
This is joint work with Avrim Blum.
 
 
 
Speaker 2:  Luis Rademacher, 
Speaker's homepage:  http://www-math.mit.edu/~lrademac/
 
Time:  Tuesday, August 30th @ 2:00 pm
Location:  TTI-C Conference Room
 
Title:  Matrix Approximation and Projective Clustering via Volume
Sampling.
 
 
Abstract:  Frieze et al. proved that a small sample of rows of a
   given matrix $A$ contains a low-rank approximation $D$ that
   minimizes $||A-D||_F$ to within small additive error, and the
   sampling can be done efficiently using just two passes over the
   matrix. We generalize this result in two
   ways. First, we prove that the additive error drops exponentially by
   iterating the sampling in an adaptive manner.  Using this result, we
   give a pass-efficient algorithm for computing low-rank approximation
   with reduced additive error.  Our second result is that using a
   natural distribution on subsets of rows (called {\em volume}
   sampling), there exists a subset of $k$ rows whose span contains a
   factor $(k+1)$ relative approximation and a subset of
   $k+k(k+1)/\eps$ rows whose span contains a $1+\eps$ relative
   approximation.  The existence of such a small certificate for
   multiplicative low-rank approximation leads to a PTAS for the
   following projective clustering problem: Given a set of points $P$
   in $\R^d$, and integers $k,j$, find a set of $j$ subspaces $F_1,
   \ldots, F_j$, each of dimension at most $k$, that minimize $\sum_{p
     \in P} \min_{i} d(p,F_i)^2$.
 
 
-----------------------------------------------------------------
 
If you have questions, or would like to meet the speaker, please contact
Katherine at 773-834-1994 or kcumming at tti-c.org.   For information on
future TTI-C talks and events, please go to the TTI-C Events page:
http://www.tti-c.org/events.html.  TTI-C (1427 East 60th Street,
Chicago, IL  60637)
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20050829/508a43ff/attachment.htm