^May June – 2008 ^July

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.

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.

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.

Join work with Boaz Nadler.

Execution traces of software programs are sequences of events corresponding to the execution of low level procedures. Understanding the process that generated these traces can provide helpful insights as to the cause of failures, or the impact of program and user behavior on a service. An hierarchical segmentation of these events can provide the information needed for the understanding of the application behavior.

If time permits, I will also discuss another project: Title: Searching Large Indexes on Tiny Devices: Extending Binary Search with Character Pinning Abstract: Motivated by the shrinking size and increasing capacity of mobile devices, we consider the problem of helping a user to find an item of interest in a large sorted list of strings using a limited user interface. We extend the standard binary search tree by allowing characters from the prefix of the current item to be selected (pinned). BIO: I am a researcher at Microsoft Research, working in the Machine Learning and Applied Statistics group. I graduated from the Ben Gurion University, the Computer Science department on 2007, studying under the supervision of Prof. Ronen Brafman and Prof. Eyal Shimony. My main research interests lie in the control of processes, especially under partial observability (POMDPs). I am also interested in Planning, Data Mining, Machine Learning and Recommender Systems.

We present a new randomized algorithm for counting, rare-events simulation, uniform sampling on different regions, and approximating the solutions of quite general NP-hard combinatorial (integer) optimization problems. Similar to the existing randomized algorithms the proposed one is based on the MCMC (Gibbs) sampler equipped with importance sampler and it also uses a sequential sampling plan to decompose a ``difficult'' problem into a sequence of ``easy'' ones. The main differences between the existing and the proposed algorithm is that the latter one has a special device, called the ``cloning'' device, which makes our algorithm very fast and accurate. In particular it is well suited for solving problems associated with the Boltzmann distribution, like estimating the partition functions in an Ising model and for sampling random variables uniformly distributed on different convex bodies. We present efficient numerical results, while solving quite general integer and combinatorial optimization problems as well as counting ones, like satisfiability problem and Hamiltonian cycles. Bio: Reuven Rubinstein is a world known expert in stochastic modeling, applied probability and Monte Carlo simulation methods. He has written over 100 articles and published six books with Wiley and Springer. His citation index is in the top 5% among the scientists in OR and applied probability worldwide. Rubinstein spent most of his sabbatical years at top universities in the world including Columbia, Harvard, Michigan and Stanford University. He is a consultant to many leading firms, including IBM, Motorola and NEC. Rubinstein is the inventor of the popular score-function method in simulation analysis and the generic cross-entropy methods for combinatorial optimization and counting. For details on the cross-entropy, which includes over 100 publications, go to http://en.wikipedia.org/wiki/Cross-entropy_method.

Women who have given birth can testify that the process is not infinitesimally short. Objects are no different than babies in this respect: it takes time to mature a raw memory block into a live object, and during that time computation may occur. Consider a class /D/ that inherits from a class /B/. Then, (in most object oriented (OO) programming languages) the process of construction of a /D/-object includes an invocation of a suitable constructor of /B/, followed by an invocation of a constructor of /D/. What is the status of the object in the course of the evaluation of the constructor of /B/? On one hand, this object cannot be thought of as a mature, ordinary object of class /D/, since /D/'s constructor was not invoked yet. On the other hand, thinking of the object as an instance of class /B/, may lead to surprising results, e.g., in the case that /B/ is an abstract class. Concretely, suppose that /B/'s constructor invokes a dynamically bound member function implemented in both /B/ and /D/. The dominating /thesis/, taken by languages such as Java and C#, is that of /dynamic binding/ within constructors, i.e., /D/'s implementation is executed. The /anti-thesis/ of /static binding,/ taken in languages such as C++, dictates that /B/'s implementation is executed. This research sets its objective in understanding how such ``half-baked'' objects are used in actual programs. In a data set comprising a dozen software collection with over sixty thousand class, we found that although the potential for such a situation is non negligible i.e., there are many constructors that make calls to methods which /may /be overridden in derived classes, this potential is realized scarcely. We found this behavior in less than 1.5% of all constructors, inheriting from less than 0.5% of all constructors. Further, we find that over 80% of these incidents fall into eight "patterns", which can be relatively easily transformed into equivalent code which does not make pre-mature calls to methods. Another similarly undesirable situation occurs when a constructor exposes the self identity to external code, and this external code chooses to call methods overridden in the derived class. Our estimates on the prevalence of this exposition are less accurate due to the complexity of interprocedural dataflow analysis. The resulting estimates are high, but there are indications that it arises from a relatively small number of base constructors. Joint work with Tali Shragai

Many complex domains offer limited information about their exact state and the way actions affect them. There, autonomous agents need to make decisions at the same time that they learn action models and track the state of the domain. This combined problem can be represented within the framework of reinforcement learning in POMDPs, and is known to be computationally difficult.

In this presentation I will describe a new framework for such decision making, learning, and tracking. This framework applies results that we achieved about updating logical formulas (belief states) after deterministic actions. It includes algorithms that represent and update the set of possible action models and world states compactly and tractably. It makes a decision with this set, and updates the set after taking the chosen action. Most importantly, and somewhat surprisingly, the number of actions that our framework takes to achieve a goal is bounded polynomially by the length of an optimal plan in a fully observable, fully known domain, under lax conditions. Finally, our framework leads to a new stochastic-filtering approach that has better accuracy than previous techniques.

* Joint work with Allen Chang, Hannaneh Hajishirzi, Stuart Russell, Dafna Shahaf, and Afsaneh Shirazi (IJCAI'03,IJCAI'05,AAAI'06,ICAPS'06,IJCAI'07,AAAI'07).

Short Bio Eyal Amir is an Assistant Professor of Computer Science at the University of Illinois at Urbana-Champaign (UIUC) since January 2004. His research includes reasoning, learning, and decision making with logical and probabilistic knowledge, dynamic systems, and commonsense reasoning. Before UIUC he was a postdoctoral researcher at UC Berkeley (2001-2003), and did his Ph.D. on logical reasoning in AI. He received B.Sc. and M.Sc. degrees in mathematics and computer science from Bar-Ilan University, Israel in 1992 and 1994, respectively. Eyal a Fellow of the Center for Advanced Studies and of the Beckman Institute at UIUC (2007-2008), was chosen by IEEE as one of the "10 to watch in AI" (2006), received the NSF CAREER award (2006), and awarded the Arthur L. Samuel award for best Computer Science Ph.D. thesis (2001-2002) at Stanford University.

In this talk, we present on-line algorithms that can be used to explore an unknown polygonal environment by a point robot. Our algorithms compute visibility polygons only from a set of chosen points on the path of a robot, and the criteria for minimizing the cost for robotic exploration is to reduce the number of visibility polygons that the algorithms compute. Efficiency of these algorithms are measured using competitive ratio. We show that these exploration algorithms are also approximation algorithms for the art gallery problem with an additional visibility constraint.