^May June – 2008 ^July

This talk will describe some of the challenges currently addressed by Web Information Retrieval systems, namely search engines. The first generation of search engines closely resembled classic IR systems in their goal to return relevant documents to a user's query. Those systems relied mostly on on-page contents. The second generation of search engines added the links between Web pages to the mix, and differentiated between several types of information needs. Today's engines tap huge amounts of user generated content, and focus on helping users to complete tasks. This involves both assisting users to break down their tasks into sub-tasks, as well as interpretation, aggregation and integration of diverse content that allows users to more readily digest complex information. The talk will explore some of the search assistance tools available today and will highlight some of the technical challenges in their development.

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.

Secret-sharing schemes are an important tool used in many cryptographic protocols. In these schemes, a dealer holding a secret string distributes shares to the parties such that only pre-defined authorized subsets of participants can reconstruct the secret from their shares. The collection of pre-defined authorized subsets is called an access structure.

In this talk we will discuss ideal secret sharing schemes, that is, schemes in which the shares are taken from the same domain as the secrets (the domain of shares cannot be smaller). Brickell and Davenport have shown an interesting connection between ideal secret sharing schemes and matroids – a combinatorial structure that generalizes the linear independence. They give a necessary condition for an access structure to have an ideal secret sharing scheme – the access structure must be induced by a matroid. Seymour has proved that the necessary condition is not sufficient: There exists an access structure induced by the Vamos matroid that does not have an ideal scheme. We strengthen the result of Seymour by showing that the access structure induced by the Vamos matroid does not have a scheme that is close to being ideal. Our bounds are obtained by using non-Shannon inequalities for the entropy function.

The talk is based on joint works with Carles Padro and Noam Livne.

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.

Polygonal meshes dominate the representations of 3D graphics models due to their compactness and simplicity. Recent advances in design, modeling, and acquisition technologies have simplified the generation of 3D models, which have led to the generation of large 3D models. These models consist of millions of polygons and often exceed the rendering capabilities of advanced graphics hardware. Therefore, there is a need to reduce the complexity of these models to match the hardware's rendering capability, while maintaining their visual appearance. Numerous algorithms have been developed to reduce the complexity of graphics models. These include level-of-detail rendering with multi-resolution hierarchies, occlusion culling, and image-based rendering. View-dependent rendering approaches change the mesh structure at each frame to adapt to the appropriate level of detail. Traditional view-dependent rendering algorithms rely on the CPU to extract a level-of-detail representation. However, within the duration of a single frame, the CPU often fails to extract the frame's geometry. This limitation usually results in unacceptably low frame rates. In this presentation I will present new approaches for interactive view-dependent rendering of large polygonal datasets, which use the advanced features of modern graphics hardware, and free the CPU.

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.

Morphological disambiguation is the process of assigning one set of morphological features (e.g. ילד is a singular masculine noun – a child) to each individual word in a text. When the word is ambiguous (e.g. ילד can be alternatively analyzed as a verb – gave birth), a disambiguation procedure based on the word context must be applied (e.g. given the phrase ילד ירח, the noun analysis is more probable). The most common model for unsupervised learning of stochastic processes is Hidden Markov Models (HMM). In this generative model, a given sequence of observed events is considered to be the emitted output of a stochastic process, over a set of states. In order to estimate the parameters of the model, the Expectation Maximization (EM) algorithm of Baum-Welch is applied over the observed emissions. In the first part of this talk (a type of 'end of PhD. event'), I will overview the Hebrew morphological disambiguation problem, presenting a word-based text encoding, which enables EM learning of HMM model for this task. Then, we will discuss the influence of the initial conditions on the learning process, suggesting several methods for initial estimation of syntagmatic and morpho-lexical distributions.

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.