[talks] manfred warmuth talk at 4pm today

[Robert Schapire]

  Manfred Warmuth from UC Santa Cruz will be giving today's colloquium 
at 4pm in CS room 105.  See abstract below, or visit

http://www.cs.princeton.edu/research/colloquia.php


Rob Schapire

------------------------------------------------------------------------


*Leaving the Span*

*Manfred K. Warmuth*
University of California, Santa Cruz

    When linear models are too simple then the following "kernel trick"
    is commonly used: Expand the instances into a high-dimensional
    feature space and use any algorithm whose linear weight vector in
    feature space is a linear combination of the expanded instances.
    Linear models in feature space are typically non-linear in the
    original space and seemingly more powerful. Also dot products can
    still be computed efficiently via the use of a kernel function.

    However we discuss a simple sparse linear problem that is hard to
    learn with any algorithm that uses a linear combination of the
    embedded training instances as its weight vector, no matter what
    embedding is used. We show that these algorithms are inherently
    limited by the fact that after seeing /k/ instances only a weight
    space of dimension /k/ can be spanned.

    Surprisingly the same problem can be efficiently learned using the
    exponentiated gradient (EG) algorithm: Now the component-wise
    logarithms of the weights are essentially a linear combination of
    the training instances. This algorithm enforces "additional
    constraints" on the weights (all must be non-negative and sum to
    one) and in some cases these constraints alone force the rank of the
    weight space to grow as fast as /2^k /.

    (Joint work with S.V.N. Vishwanathan!)


------------------------------------------------------------------------

-- 
Princeton University
Department of Computer Science
35 Olden Street
Princeton, NJ  08540  USA

tel: +1 609 258 7726   fax: +1 609 258 1771
Computer Science Building, Room 407

http://www.cs.princeton.edu/~schapire
schapire at cs.princeton.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.cs.princeton.edu/pipermail/talks/attachments/20061025/4f191f06/attachment.htm