<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
<div class="moz-text-html" lang="x-western"> <tt>Manfred Warmuth from
UC Santa Cruz will be giving today's colloquium at 4pm in CS room 105.&nbsp;
See abstract
below, or visit<br>
<br>
<a class="moz-txt-link-freetext"
 href="http://www.cs.princeton.edu/research/colloquia.php">http://www.cs.princeton.edu/research/colloquia.php</a><br>
<br>
<br>
Rob Schapire<br>
<br>
</tt>
<hr size="2" width="100%"><tt><br>
<br>
</tt>
<center><font size="+2"><b>Leaving the Span</b></font>
<p><font size="+1"><b>Manfred K. Warmuth</b></font>
<br>
University of California, Santa Cruz
</p>
</center>
<blockquote>
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.
  <p>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 <i>k</i>
instances only a weight space of dimension <i>k</i> can be spanned.</p>
  <p>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 <i>2<sup>k</sup></i>.</p>
  <p>(Joint work with S.V.N. Vishwanathan!)</p>
</blockquote>
<br>
<hr size="2" width="100%"></div>
<br>
<pre class="moz-signature" cols="72">-- 
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

<a class="moz-txt-link-freetext" href="http://www.cs.princeton.edu/~schapire">http://www.cs.princeton.edu/~schapire</a>
<a class="moz-txt-link-abbreviated" href="mailto:schapire@cs.princeton.edu">schapire@cs.princeton.edu</a>
</pre>
</body>
</html>