<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:st1="urn:schemas-microsoft-com:office:smarttags" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 11 (filtered medium)">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]--><o:SmartTagType
namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="Street"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="address"/>
<!--[if !mso]>
<style>
st1\:*{behavior:url(#default#ieooui) }
</style>
<![endif]-->
<style>
<!--
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman";}
a:link, span.MsoHyperlink
{color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{color:purple;
text-decoration:underline;}
p
{mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman";}
span.EmailStyle18
{mso-style-type:personal;
font-family:Arial;
color:windowtext;}
span.EmailStyle19
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle20
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle21
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle22
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle23
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle24
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle25
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle26
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle27
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle28
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle29
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle30
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle31
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle32
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle33
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle34
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle35
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle36
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle37
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle38
{mso-style-type:personal-reply;
font-family:Arial;
color:navy;}
@page Section1
{size:8.5in 11.0in;
margin:1.0in 1.25in 1.0in 1.25in;}
div.Section1
{page:Section1;}
-->
</style>
</head>
<body lang=EN-US link=blue vlink=purple>
<div class=Section1>
<p class=MsoNormal><font size=3 color=navy face=Arial><span style='font-size:
12.0pt;font-family:Arial;color:navy'>***This talk has been rescheduled to <b><span
style='font-weight:bold'>Wednesday May 28 </span></b>@11:00am.***<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
<div>
<div class=MsoNormal align=center style='text-align:center'><font size=3
face="Times New Roman"><span style='font-size:12.0pt'>
<hr size=2 width="100%" align=center tabindex=-1>
</span></font></div>
</div>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>When:
Wednesday,
May 28 @11:00am<b><font color=navy><span style='color:navy;font-weight:bold'><o:p></o:p></span></font></b></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>Where:
TTI-C Conference Room, <st1:Street w:st="on"><st1:address w:st="on">1427 E. 60<sup>th</sup>
St.</st1:address></st1:Street>, 2<sup>nd</sup> Floor<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p style='margin:0in;margin-bottom:.0001pt'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'>Who:
Aryeh Kontorovich, Weizmann Institute of Science<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'>Topic:
A Universal
Kernel for Learning Regular Languages<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'>We develop a novel approach to the classical
problem of learning regular languages from labeled samples. Rather than
attempting to construct small consistent automata (long known to be a very
difficult computational problem), we embed the strings in a Hilbert space and
compute a maximum-margin hyperplane, which becomes our classifier for new
strings. We accomplish this via a universal kernel that renders all regular
languages linearly separable. Under this kernel, the image of every regular
language is linearly separable from its complement in some finite-dimensional
space with a strictly positive margin. Thus, we are able to efficiently (in
sample size) compute a maximum-margin separating hyperplane (via SVM, for
example) and use margin bounds to control the generalization error.<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'>A brute-force computation of this
universal kernel has super-exponential complexity. We conjecture that this
problem is intractable (a likely candidate for #P-complete). However, we
propose a simple randomized scheme for efficiently obtaining an
$\eps$-approximation to our universal kernel. We show that the approximate
kernel preserves the distances and margins with low distortion, and therefore
may be used as a surrogate for the original one.<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'>To our knowledge, the framework we
propose is the only one capable of inducing unrestricted regular languages from
labeled samples (modulo standard cryptographic limitations). Along the way, we
touch upon several fundamental questions in complexity, automata, and machine
learning.<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'>Join work with Boaz Nadler.<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>Contact:
Nati Srebro,
TTI-C nati@tti-c.org
834-7493<o:p></o:p></span></font></p>
<p class=MsoNormal style='margin-bottom:12.0pt'><font size=3 color=navy
face=Arial><span style='font-size:12.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
</div>
</body>
</html>