ACM-Infosys Foundation Award in the Computing Sciences  
Stanford University United States – 2007

For her work on combining relational logic and probability that allows probabilistic reasoning to be applied to a wide range of applications, including robotics, economics, and biology.

Prof. Koller's work on combining relational logic and probability is the most important of her many research contributions in Artificial Intelligence and Computer Science. It has transformed the way people handle uncertainty in large computer systems, such as heterogeneous databases, image understanding systems, biological and medical models, and natural language processing systems.

Her interest in this topic stems from her 1994 PhD dissertation. At that time logical reasoning and probabilistic reasoning were two distinct sub-fields in AI, with very little interaction. Prof. Koller and a few others recognized that relational logic and probability were complementary. Relational logic brings expressive power, but cannot handle the uncertainty that is inherent in most real-world domains. On the other hand, probability (and probability-based knowledge representation tools, like Bayesian networks and Markov models) provides a sound methodology for dealing with uncertainty, but is unable to reason about objects and the relations between them. The combination of relational logic and probability led to a new knowledge representation paradigm, known as relational probabilistic models. Prof. Koller's Computers and Thought Award Lecture at IJCAI 2001 established it as a major research area in AI.

Aside from establishing the foundations, Prof. Koller's algorithmic work brought these models into the realm of feasibility. A good knowledge representation language must be expressive, and must also support efficient inference and learning algorithms. During the last decade, she and her students have both added to the theory and built operational systems that apply these ideas to real-world domains involving millions of objects, variables, and relations. Her learning algorithms make it possible to construct large models of complex domains, for example in biology, epidemiology, and computer vision. Her inference algorithms make it possible to evaluate the probability of a query in a way that exploits all of the information available about the huge number of inter-linked objects in the domain.

Prof. Koller's work has influenced many other areas of computer science and other fields, including information retrieval from heterogeneous databases, natural language understanding, robotics, machine perception, economics, and biology. She has applied her approaches to a number of important real problems, including biological problems and robot perception problems.