Solomon Eyal Shimony
My research focuses on structured probabilistic reasoning and its derivatives, in patricular decision-making under uncertainty. Within these fields, the structure of the distributions and utility functions, represented as a graphical model (such as a Bayes network representing the distributions, or a CP network representing the preference structure) is crucial. Much of my research is aimed at exploiting such structure, towards effective schemes for reasoning over these models, both in theory and in practice.
In earlier works, we defined ``irrelevance-based independence'', a dependency structure that has since become known as ``context-specific independence''. Typically defined on top of a graphical probability model such as a Bayes network, this refined version allows specifying that variables are independent given specific instantiations of other random variables, rather than given all possible such instantiations as is standard for Bayes networks. This refined model is more complicated, but allows for many more cases where independence can be stated, and thus this notion allows for a more compact representation of specific types of multi-variate distributions, such as the well-known noisy or. That in turn enables improving performance of reasoning algorithms in networks that exhibit such structure. As a result, this notion is exploited in the community for efficient probabilistic reasoning.
Numerous AI applications use some form of weights or heuristics, in order to convey uncertainty or incompleteness, such as in abductive reasoning for natural language interpretation. It is crucial to attach a probabilistic semantics to these weights if possible, as that makes the treatment of these weights more disciplined, by exposing hidden assumptions, as well as frequently allowing improved heuristics. Papers using this methodology include a probabilistic semantics for weighted abduction, where the costs of assumed literals behave like negative logarithm of the probability that the event specified by the literal occurs. The semantics in this case highlights the independence assumption underlying the weighted abduction scheme. Another case is probability-based heuristics for constraint satisfaction problems, where an estimate for the number of solutions under different independence assumptions can be beneficially used as a value-ordering search heuristic. Finally, the observation that kappa-calculus is a valid semantics for degrees of evidence also helps understand assumptions implicit in the degrees of evidence model.
For the more standard utility function representation, solving various classes of partially observable markov decision processes (POMDP) is an important computationally intractable problem. Techniques relying on meta-reasoning aspects of flexible computation have shown to be applicable, for example in reasoning over what ``backup'' actions to perform in belief-point based algorithms. Using problem structure, i.e. the way the value functions and the distributions are defined in terms of the variables composing the states of the POMDP, is another way to go. Special cases of POMDP, such as the observation subset selection problem, when the dependency model has the right structure, such as a chain, or a tree, can be solved in polynomial time. In fact, this research finds immediate application in such problems encountered by our industrial partners in the IMG4 consortium.
Decision making under uncertainty for robots, both real and simulated, is an important application area, and requires understanding both in spatial issues and structured probability models. We pioneered the research on uncertain data models and models for uncertain spatial data that are recently becoming popular. Increased research community interest in AI in games has renewed examination of such issues, and an abstaction that we are currently examining is the path planning under uncertainty problem known as the Canadian traveller problem (CTP) and its variants. In this problem, a weighted graph is given, but some of its edges may be blocked. The actual state of an edge becomes known to the agent only upon reaching an incident vertex. This problem and its variants with remote sensing, which is also a sort of POMDP, is a large unexplored territory in my research plan for the next several years.
Yet another application of decision-making under uncertainty is that of meta-reasoning. Here we try to optimize computational actions performed to reach certain computational goals. One well-known but underexplored domain is rational meta-reasoning for search, initially introduced circa 1990. In recent work we applied this methodology to selecting heuristics to deploy during CSP search. Another ongoing direction is finding what to sample in Monte-Carlo tree search.
Building 37 (Alon Hi-Tech Building) Room 216 Office hours: Tuesday 14-16
Department of Computer Science Ben-Gurion University of the Negev P.O. Box 653 84105 Beer-Sheva Israel Tel: (+972-8) 647-7857 FAX: (+972-8) 647-2909