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(a)cs.princeton.edu
