[Colloquium] Fwd: TTIC Colloquium: Yoram Singer, Google Research

[Liv Leader]

When:     *Wednesday, March 30 @ 11*

Where:    *TTIC Conference Room #526*, 6045 S. Kenwood Avenue, 5th Floor

Who:      *Yoram Singer, *Google Research

Title:       *Entire Relaxation Path for Maximum Entropy Models*

We describe a relaxed and generalized notion of maximum entropy problems for
multinomial distributions. By introducing a simple re-parametrization we are
able to derive an efficient homotopy tracking for the entire relaxation
path.
The end result is an algorithm that can provide optimal probabilistic
estimates
for any relaxation parameter using linear space and sub-linear time.  We
also
show that the Legendre dual of the relaxed maximum entropy problem is the
task
of finding the maximum-likelihood estimator for an exponential distribution
with L1 regularization.  Hence, our solution can be used for problems such
as
language modeling with sparse parameter representation.  We describe a
simple
large deviation bound that holds for any relaxation parameter and conclude
with
a demonstration and a discussion of potential applications.

Acknowledgments:

The roots of this line of work go back to an open problem posed by the late
Sam
Roweis in summer 2009 during our collaboration at Google. The talk is mostly
based on recent joint work with Moshe Dubiner from Google. Thanks also to
Han
Liu (Johns Hopkins), Will Neveitt (Google), and John Duchi (UC Berkeley) for
their contributions to the original problem.

Host:     Joseph Keshet, jkeshet at ttic.edu


-- 
Liv Leader
Faculty Services

Toyota Technological Institute
6045 S Kenwood Ave, #504
Chicago, IL 60637
Phone- (773) 834-2567
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu



-- 
Liv Leader
Faculty Services

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