Solomon Eyal Shimony

B.S.E.E.: Technion, I.I.T. - 1982
Ph.D.: Brown University - 1991

Research Interests and Agenda

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.

Probabilistic Reasoning

Exploring the limits of tractability of probabilistic reasoning is an extremely important research direction to the UAI community. Proving that finding the MPE (most probable explanation, i.e. the most probable variable instantiation) in Bayes networks is NP hard, and further refining these boundaries, w.r.t. different topologies, such as directed-path k-connected networks, and according to whether the reasoning problem is a prediction problem (evidence at the top - an ``easier'' problem) or an explanation problem (evidence at the bottom - a ``harder'' problem) has been a significant part of this direction.

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.

Decision-making under uncertainty

Refined utility and preference models, and decision-making in these models are of major importance in the research community. Of special note are the new model and algorithms for specifying and resoning over subsets. The model uses TCP networks to specify preferences over statments relating to the cardinality of attribute-value occurences of items in the sets, allowing the model to be defined over an unknown set of items. Finding an optimal set is shown to be computationally intractable, but algorithms that perform well in practice, based on a reduction to sequences of constraint satisfaction problems, were developed.

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.

Other Research Directions

Graph mining is a field of increased recent interest, where we have applied graphical techniques to achieve more efficient algorithms based on using paths as a graph constructor, rather than edges or nodes. We have also shown theoretical properties of graph support measures: necessary and sufficient conditions for anti-monotonicity of the support measure (important for many common mining algorithms) are shown in terms of graphical operations on a structure known as the instance graph.

Past Professional Activities

  • Co-organizer, Israeli Association for Artificial Intelligence symposium, 2008.
  • Deputy head of computer science department at BGU, 2002-2014.
  • Chair, Paul Ivanier Center for Robotics and Production Management, 2004-2008.
  • Program co-chair, IEEE International Conference on Systems, Man, and Cybernetics 2006.
  • BISFAI-99 program co-chair - guest editor of special issue for selected papers - Annals of Math. and AI, Applied Intelligence.
  • Reviewer, JAIR, Artificial Intelligence, Approximate Reasoning, IEEE SMC, Annals of Math. and AI
  • Program Committee member, Uncertainty in Artificial Intelligence, 1994, 1995, 1997-2006

    Courses taught in past

    Contact Addresses


    Physical Address

    Building 37 (Alon Hi-Tech Building)
    Room 216
    Office hours: Tuesday 14-16

    Snail-Mail Address:

        Department of Computer Science
        Ben-Gurion  University of the Negev
        P.O. Box 653
        84105 Beer-Sheva
        Tel: (+972-8) 647-7857
        FAX: (+972-8) 647-2909