Avi Pfeffer

AIJ Journal 2025 Journal Article

Coltrane: A domain-independent system for characterizing and planning in novel situations

• Bryan Loyall
• Avi Pfeffer
• James Niehaus
• Michael Harradon
• Paola Rizzo
• Alex Gee
• Joe Campolongo
• Tyler Mayer

AI systems operating in open-world environments must be able to adapt to impactful changes in the world, immediately when they occur, and be able to do this across the many types of changes that can occur. We are seeking to create methods to extend traditional AI systems so that they can (1) immediately recognize changes in how the world works that are impactful to task accomplishment; (2) rapidly characterize the nature of the change using the limited observations that are available when the change is first detected; (3) adapt to the change as well as feasible to accomplish the system's tasks given the available observations; and (4) continue to improve the characterization and adaptation as additional observations are available. In this paper, we describe Coltrane, a domain-independent system for characterizing and planning in novel situations that uses only natural domain descriptions to generate its novelty-handling behavior, without any domain-specific anticipation of the novelty. Coltrane's characterization method is based on probabilistic program synthesis of perturbations to programs expressed in a traditional programming language describing domain transition models. Its planning method is based on incorporating novel domain models in an MCTS search algorithm and on automatically adapting the heuristics used. Both a formal external evaluation and our own demonstrations show that Coltrane is capable of accurately characterizing interesting forms of novelty and of adapting its behavior to restore its performance to pre-novelty levels and even beyond.

AAMAS Conference 2011 Conference Paper

Reasoning Patterns in Bayesian Games

• Dimitrios Antos
• Avi Pfeffer

Bayesian games have been traditionally employed to describe and analyze situations in which players have private information or are uncertain about the game being played. However, computing Bayes-Nash equilibria can be costly, and becomes even more so if the common prior assumption (CPA) has to be abandoned, which is sometimes necessary for a faithful representation of real-world systems. We propose using the theory of reasoning patterns in Bayesian games to circumvent some of these difficulties. The theory has been used successfully in common knowledge (non-Bayesian) games, both to reduce the computational cost of finding an equilibrium and to aid human decision-makers in complex decisions. In this paper, we first show that reasoning patterns exist for every decision of every Bayesian game, in which the acting agent has a reason to deliberate. This implies that reasoning patterns are a complete characterization of the types of reasons an agent might have for making a decision. Second, we illustrate practical applications of reasoning patterns in Bayesian games, which allow us to answer questions that would otherwise not be easy in traditional analyses, or would be extremely costly. We thus show that the reasoning patterns can be a useful framework in analyzing complex social interactions.

IJCAI Conference 2011 Conference Paper

Using Emotions to Enhance Decision-Making

• Dimitrios Antos
• Avi Pfeffer

We present a novel methodology for decision-making by computer agents that leverages a computational concept of emotions. It is believed that emotions help living organisms perform well in complex environments. Can we use them to improve the decision-making performance of computer agents? We explore this possibility by formulating emotions as mathematical operators that serve to update the relative priorities of the agent's goals. The agent uses rudimentary domain knowledge to monitor the expectation that its goals are going to be accomplished in the future, and reacts to changes in this expectation by "experiencing emotions. " The end result is a projection of the agent's long-run utility function, which might be too complex to optimize or even represent, to a time-varying valuation function that is being myopically maximized by selecting appropriate actions. Our methodology provides a systematic way to incorporate emotion into a decision-theoretic framework, and also provides a principled, domain-independent methodology for generating heuristics in novel situations. We test our agents in simulation in two domains: restless bandits and a simple foraging environment. Our results indicate that emotion-based agents outperform other reasonable heuristics for such difficult domains, and closely approach computationally expensive near-optimal solutions, whenever these are computable, yet requiring only a fraction of the cost.

AIJ Journal 2010 Journal Article

Agent decision-making in open mixed networks

• Ya'akov Gal
• Barbara Grosz
• Sarit Kraus
• Avi Pfeffer
• Stuart Shieber

Computer systems increasingly carry out tasks in mixed networks, that is in group settings in which they interact both with other computer systems and with people. Participants in these heterogeneous human–computer groups vary in their capabilities, goals, and strategies; they may cooperate, collaborate, or compete. The presence of people in mixed networks raises challenges for the design and the evaluation of decision-making strategies for computer agents. This paper describes several new decision-making models that represent, learn and adapt to various social attributes that influence people's decision-making and presents a novel approach to evaluating such models. It identifies a range of social attributes in an open-network setting that influence people's decision-making and thus affect the performance of computer-agent strategies, and establishes the importance of learning and adaptation to the success of such strategies. The settings vary in the capabilities, goals, and strategies that people bring into their interactions. The studies deploy a configurable system called Colored Trails (CT) that generates a family of games. CT is an abstract, conceptually simple but highly versatile game in which players negotiate and exchange resources to enable them to achieve their individual or group goals. It provides a realistic analogue to multi-agent task domains, while not requiring extensive domain modeling. It is less abstract than payoff matrices, and people exhibit less strategic and more helpful behavior in CT than in the identical payoff matrix decision-making context. By not requiring extensive domain modeling, CT enables agent researchers to focus their attention on strategy design, and it provides an environment in which the influence of social factors can be better isolated and studied.

AAMAS Conference 2010 Conference Paper

Decision Making with Dynamically Arriving Information

• Meir Kalech
• Avi Pfeffer

Decision making is the ability to decide on the best alternative among a set of candidates based on their value. In many real-world domains the value depends on events that occur dynamically, so that the decision is based on dynamically changing uncertain information. When there is a cost to waiting for more information, the question is when to make the decision. Do you stop and make the best decision you can, given the information you have so far, or do you wait until more information arrives so you can make a better decision? We propose a model that characterizes the influence of dynamic information on the utility of the decision. Based on this model, we present an optimal algorithm that guarantees the best time to stop. Unfortunately, its complexity is exponential in the number of candidates. We present an alternative framework in which the different candidates are solved separately. We formally analyze the alternative framework, and show how it leads to a range of specific heuristic algorithms. We evaluate the optimal and the simplest heuristic algorithms through experiments, and show that the heuristic algorithm is much faster than the optimal algorithm, and the utility of the winner it finds is close to the optimum.

UAI Conference 2010 Conference Paper

Learning Game Representations from Data Using Rationality Constraints

• Xi Alice Gao
• Avi Pfeffer

While game theory is widely used to model strategic interactions, a natural question is where do the game representations come from? One answer is to learn the representations from data. If one wants to learn both the payoffs and the players’ strategies, a naive approach is to learn them both directly from the data. This approach ignores the fact the players might be playing reasonably good strategies, so there is a connection between the strategies and the data. The main contribution of this paper is to make this connection while learning. We formulate the learning problem as a weighted constraint satisfaction problem, including constraints both for the fit of the payoffs and strategies to the data and the fit of the strategies to the payoffs. We use quantal response equilibrium as our notion of rationality for quantifying the latter fit. Our results show that incorporating rationality constraints can improve learning when the amount of data is limited.

AAMAS Conference 2010 Conference Paper

Representing Bayesian Games Without a Common Prior

• Dimitrios Antos
• Avi Pfeffer

Game-theoretic analyses of multi-agent systems typically assume that all agents have full knowledge of everyone's possible moves, information sets and utilities for each outcome. Bayesian games relax this assumption by allowing agents tohave different "types, " representing different beliefs aboutthe game being played, and to have uncertainty over otheragents' types. However, applications of Bayesian games almost universally assume that all agents share a commonprior distribution over everyone's type. We argue, in concordwith certain economists, that such games fail to accuratelyrepresent many situations. However, when the commonprior assumption is abandoned, several modeling challengesarise, one of which is the emergence of complex belief hierarchies. In these cases it is necessary to specify which partsof other agents' beliefs are relevant to an agent's decision-making (or need be known by that agent). We address thisissue by suggesting a concise way of representing Bayesiangames with uncommon priors. Our representation centersaround the concept of a block, which groups agents' view of(a) the game being played and (b) their posterior beliefs. This allows us to construct the belief graph, a graphicalstructure that allows agents' knowledge of other agents' beliefs to be carefully specified. Furthermore, when agents'views of the world are represented by extensive form games, our block structure places useful semantic constraints onthe extensive form trees. Our representation can be usedto naturally represent games with rich belief structures andinteresting predicted behavior.

IJCAI Conference 2009 Conference Paper

• Dimitrios Antos
• Avi Pfeffer

We propose a novel method for helping humans make good decisions in complex games, for which common equilibrium solutions may be too difficult to compute or not relevant. Our method leverages and augments humans’ natural use of arguments in the decision making process. We believe that, if computers were capable of generating similar arguments from the mathematical description of a game, and presented those to a human decision maker, the synergies would result in better performance overall. The theory of reasoning patterns naturally lends itself to such a use. We use reasoning patterns to derive localized evaluation functions for each decision in a game, then present their output to humans. We have implemented this approach in a repeated principal-agent game, and used it to generate advice given to subjects. Experimental results show that humans who received advice performed better than those who did not.

IJCAI Conference 2009 Conference Paper

• Avi Pfeffer

Probabilistic programming languages allow a modeler to build probabilistic models using complex data structures with all the power of a programming language. We present CTPPL, an expressive probabilistic programming language for dynamic processes that models processes using continuous time. Time is a first class element in our language; the amount of time taken by a subprocess can be specified using the full power of the language. We show through examples that CTPPL can easily represent existing continuous time frameworks and makes it easy to represent new ones. We present semantics for CTPPL in terms of a probability measure over trajectories. We present a particle filtering algorithm for the language that works for a large and useful class of CTPPL programs.

JAAMAS Journal 2009 Journal Article

Specifying and monitoring economic environments using rights and obligations

• Loizos Michael
• David C. Parkes
• Avi Pfeffer

Abstract We provide a formal scripting language to capture the semantics of economic environments. The language is based on a set of well-defined design principles and makes explicit an agent’s rights, as derived from property, and an agent’s obligations, as derived from restrictions placed on its actions either voluntarily or as a consequence of other actions. Coupled with the language is a run-time system that is able to monitor and enforce rights and obligations in an agent-mediated economic environment. The framework allows an agent to formally express guarantees (obligations) in relation to its actions, and the run-time system automatically checks that these obligations are met and verifies that an agent has appropriate rights before executing an action. Rights and obligations are viewed as first-class goods that can be transferred from one agent to another. This treatment makes it easy to define natural and expressive recursive statements, so that, for instance, one may have rights or obligations in selling or trading some other right or obligation. We define fundamental axioms about well-functioning markets in terms of rights and obligations, and delineate the difference between ownership and possession, arguably two of the most important notions in economic markets. The framework provides a rich set of action-related constructs for modeling conditional and non-deterministic effects, and introduces the use of transactions to safely bundle actions, including the issuing of rights and taking on of obligations. By way of example, we show that our language can represent a variety of economic mechanisms, ranging from simple two-agent single-good exchanges to complicated combinatorial auctions. The framework, which is fully implemented, can be used to formalize the semantics of markets; as a platform for prototyping, testing and evaluating agent-mediated markets; and also provide a basis for deploying an electronic market.

UAI Conference 2009 Conference Paper

Temporal Action-Graph Games: A New Representation for Dynamic Games

• Albert Xin Jiang
• Kevin Leyton-Brown
• Avi Pfeffer

In this paper we introduce temporal action graph games (TAGGs), a novel graphical representation of imperfect-information extensive form games. We show that when a game involves anonymity or context-specific utility independencies, its encoding as a TAGG can be much more compact than its direct encoding as a multiagent influence diagram (MAID). We also show that TAGGs can be understood as indirect MAID encodings in which many deterministic chance nodes are introduced. We provide an algorithm for computing with TAGGs, and show both theoretically and empirically that our approach improves significantly on the previous state of the art.

AAMAS Conference 2008 Conference Paper

Colored Trails: A Multiagent System Testbed for Decision-Making Research

• Sevan Ficici
• Avi Pfeffer
• Ya'akov Gal
• Barbara Grosz
• Stuart Shieber

UAI Conference 2008 Conference Paper

Identifying reasoning patterns in games

• Dimitrios Antos
• Avi Pfeffer

We present an algorithm that identifies the reasoning patterns of agents in a game, by iteratively examining the graph structure of its Multi-Agent Influence Diagram (MAID) representation. If the decision of an agent participates in no reasoning patterns, then we can effectively ignore that decision for the purpose of calculating a Nash equilibrium for the game. In some cases, this can lead to exponential time savings in the process of equilibrium calculation. Moreover, our algorithm can be used to enumerate the reasoning patterns in a game, which can be useful for constructing more effective computerized agents interacting with humans.

UAI Conference 2008 Conference Paper

Learning and Solving Many-Player Games through a Cluster-Based Representation

• Sevan G. Ficici
• David C. Parkes
• Avi Pfeffer

In addressing the challenge of exponential scaling with the number of agents we adopt a cluster-based representation to approximately solve asymmetric games of very many players. A cluster groups together agents with a similar “strategic view” of the game. We learn the clustered approximation from data consisting of strategy profiles and payoffs, which may be obtained from observations of play or access to a simulator. Using our clustering we construct a reduced “twins” game in which each cluster is associated with two players of the reduced game. This allows our representation to be individuallyresponsive because we align the interests of every individual agent with the strategy of its cluster. Our approach provides agents with higher payoffs and lower regret on average than model-free methods as well as previous cluster-based methods, and requires only few observations for learning to be successful. The “twins” approach is shown to be an important component of providing these low regret approximations.

AAMAS Conference 2008 Conference Paper

Modeling how Humans Reason about Others with Partial Information

• Sevan Ficici
• Avi Pfeffer

Computer agents participate in many collaborative and competitive multiagent domains in which humans make decisions. For computer agents to interact successfully with people in such environments, an understanding of human reasoning is beneficial. In this paper, we investigate the question of how people reason strategically about others under uncertainty and the implications of this question for the design of computer agents. Using a situated partialinformation negotiation game, we conduct human-subjects trials to obtain data on human play. We then construct a hierarchy of models that explores questions about human reasoning: Do people explicitly reason about other players in the game? If so, do people also consider the possible states of other players for which only partial information is known? Is it worth trying to capture such reasoning with computer models and subsequently utilize them in computer agents? We compare our models on their fit to collected data. We then construct computer agents that use our models in one of two ways: emulating human behavior and playing best response to the model. After building our agents, we deploy them in further human-subjects trials for evaluation. Our results indicate that people do reason about other players in our game and also reason under uncertainty. Better models are shown to yield more successful computer agents.

AAMAS Conference 2008 Conference Paper

Simultaneously Modeling Humans' Preferences and their Beliefs about Others' Preferences

• Sevan Ficici
• Avi Pfeffer

In strategic multiagent decision making, it is often the case that a strategic reasoner must hold beliefs about other agents and use these beliefs to inform its decision making. The behavior thus produced by the reasoner involves an interaction between the reasoner’s beliefs about other agents and the reasoner’s own preferences. A significant challenge faced by model designers, therefore, is how to model such a reasoner’s behavior so that the reasoner’s preferences and beliefs can each be identified and distinguished from each other. In this paper, we introduce a model of strategic reasoning that allows us to distinguish between the reasoner’s utility function and the reasoner’s beliefs about another agent’s utility function as well as the reasoner’s beliefs about how that agent might interact with yet other agents. We show that our model is uniquely identifiable. That is, no two different parameter settings will cause the model to give the same behavior over all possible inputs. We then illustrate the performance of our model in a multiagent negotiation game played by human subjects. We find that our subjects have slightly incorrect beliefs about other agents in the game.

IJCAI Conference 2007 Conference Paper

• Avi Pfeffer
• Subrata Das
• David Lawless
• Brenda Ng

Many dynamic systems involve a number of entities that are largely independent of each other but interact with each other via a subset of state variables. We present global/local dynamic models (GLDMs) to capture these kinds of systems. In a GLDM, the state of an entity is decomposed into a globally influenced state that depends on other entities, and a locally influenced state that depends only on the entity itself. We present an inference algorithm for GLDMs called global/local particle filtering, that introduces the principle of reasoning globally about global dynamics and locally about local dynamics. We have applied GLDMs to an asymmetric urban warfare environment, in which enemy units form teams to attack important targets, and the task is to detect such teams as they form. Experimental results for this application show that global/local particle filtering outperforms ordinary particle filtering and factored particle filtering.

NeurIPS Conference 2007 Conference Paper

Discovering Weakly-Interacting Factors in a Complex Stochastic Process

• Charlie Frogner
• Avi Pfeffer

Dynamic Bayesian networks are structured representations of stochastic pro- cesses. Despite their structure, exact inference in DBNs is generally intractable. One approach to approximate inference involves grouping the variables in the process into smaller factors and keeping independent beliefs over these factors. In this paper we present several techniques for decomposing a dynamic Bayesian network automatically to enable factored inference. We examine a number of fea- tures of a DBN that capture different types of dependencies that will cause error in factored inference. An empirical comparison shows that the most useful of these is a heuristic that estimates the mutual information introduced between factors by one step of belief propagation. In addition to features computed over entire factors, for efficiency we explored scores computed over pairs of variables. We present search methods that use these features, pairwise and not, to find a factor- ization, and we compare their results on several datasets. Automatic factorization extends the applicability of factored inference to large, complex models that are undesirable to factor by hand. Moreover, tests on real DBNs show that automatic factorization can achieve significantly lower error in some cases.

AAAI Conference 2007 Conference Paper

On the Reasoning Patterns of Agents in Games

• Avi Pfeffer

What reasoning patterns do agents use to choose their actions in games? This paper studies this question in the context of Multi-Agent Influence Diagrams (MAIDs). It defines several kinds of reasoning patterns, and associates each with a pattern of paths in a MAID. We asks the question, what reasoning patterns have to hold in order for an agent to care about its decision? The answer depends on what strategies are considered for other agents’ decisions. We introduce a new solution concept, called well-distinguishing (WD) strategies, that captures strategies in which all the distinctions an agent makes really make a difference. We show that when agents are playing WD strategies, all situations in which an agent cares about its decision can be captured by four reasoning patterns. We furthermore show that when one of these four patterns holds, there are some MAID parameter values such that the agent actually does care about its decision.

AAAI Conference 2007 Conference Paper

Sampling with Memoization

• Avi Pfeffer

UAI Conference 2006 Conference Paper

Approximate Separability for Weak Interaction in Dynamic Systems

• Avi Pfeffer

One approach to monitoring a dynamic system relies on decomposition of the system into weakly interacting subsystems. An earlier paper introduced a notion of weak interaction called separability, and showed that it leads to exact propagation of marginals for prediction. This paper addresses two questions left open by the earlier paper: can we define a notion of approximate separability that occurs naturally in practice, and do separability and approximate separability lead to accurate monitoring? The answer to both questions is afirmative. The paper also analyzes the structure of approximately separable decompositions, and provides some explanation as to why these models perform well.

AAMAS Conference 2006 Conference Paper

Predicting People's Bidding Behavior in Negotiation

• Yakov Gal
• Avi Pfeffer

UAI Conference 2005 Conference Paper

Asynchronous Dynamic Bayesian Networks

• Avi Pfeffer
• Terry Tai

Systems such as sensor networks and teams of autonomous robots consist of multiple autonomous entities that interact with each other in a distributed, asynchronous manner. These entities need to keep track of the state of the system as it evolves. Asynchronous systems lead to special challenges for monitoring, as nodes must update their beliefs independently of each other and no central coordination is possible. Furthermore, the state of the system continues to change as beliefs are being updated. Previous approaches to developing distributed asynchronous probabilistic reasoning systems have used static models. We present an approach using dynamic models, that take into account the way the system changes state over time. Our approach, which is based on belief propagation, is fully distributed and asynchronous, and allows the world to keep on changing as messages are being sent around. Experimental results show that our approach compares favorably to the factored frontier algorithm.

IJCAI Conference 2005 Conference Paper

Continuous Time Particle Filtering

• Brenda Ng
• Avi Pfeffer
• Richard

We present the continuous-time particle filter (CTPF) – an extension of the discrete-time particle filter for monitoring continuous-time dynamic systems. Our methods apply to hybrid systems containing both discrete and continuous variables. The dynamics of the discrete state system are governed by a Markov jump process. Observations of the discrete process are intermittent and irregular. Whenever the discrete process is observed, CTPF samples a trajectory of the underlying Markov jump process. This trajectory is then used to estimate the continuous variables using the system dynamics determined by the discrete state in the trajectory. We use the unscented Kalman-Bucy filter to handle nonlinearities and continuous time. We present results showing that CTPF is more stable in its performance than discrete-time particle filtering, even when the discrete-time algorithm is allowed to update many more times than CTPF. We also present a method for online learning of the Markov jump process model that governs the discrete states.

AAAI Conference 2005 Conference Paper

Functional Specification of Probabilistic Process Models

• Avi Pfeffer

Agents that handle complex processes evolving over a period of time need to be able to monitor the state of the process. Since the evolution of a process is often stochastic, this requires probabilistic monitoring of processes. A probabilistic process modeling language is needed that can adequately capture our uncertainty about the process execution. We present a language for describing probabilistic process models. This language is functional in nature, and the paper argues that a functional language provides a natural way to specify process models. In our framework, processes have both states and values. Processes may execute sequentially or in parallel, and we describe two alternative forms of parallelism. An inference algorithm is presented that constructs a dynamic Bayesian network, containing a variable for every subprocess that is executed during the course of executing a process. We present a detailed example demonstrating the naturalness of the language.

AAMAS Conference 2004 Conference Paper

Reasoning about Rationality and Beliefs

• Gal Yakov
• Avi Pfeffer

AAAI Conference 2004 Conference Paper

Repeated Observation Models

• Avi Pfeffer

Repetition is an important phenomenon in a variety of domains, such as music, computer programs and architectural drawings. A generative model for these domains should account for the possibility of repetition. We present repeated observation models (ROMs), a framework for modeling sequences that explicitly allows for repetition. In a ROM, an element is either generated by copying a previous element, or by using a base model. We show how to build ROMs using ngrams and hidden Markov models as the base model. We also describe an extension of ROMs in which entire subsequences are repeated together. Results from a music modeling domain show that ROMs can lead to dramatic improvement in predictive ability.

AAMAS Conference 2003 Conference Paper

A Language for Modelling Agents` Decision Making Processes in Games

• Ya`akov Gal
• Avi Pfeffer

UAI Conference 2003 Conference Paper

Loopy Belief Propagation as a Basis for Communication in Sensor Networks

• Christopher Crick
• Avi Pfeffer

Sensor networks are an exciting new kind of computer system. Consisting of a large number of tiny, cheap computational devices physically distributed in an environment, they gather and process data about the environment in real time. One of the central questions in sensor networks is what to do with the data, i.e., how to reason with it and how to communicate it. This paper argues that the lessons of the UAI community, in particular that one should produce and communicate beliefs rather than raw sensor values, are highly relevant to sensor networks. We contend that loopy belief propagation is particularly well suited to communicating beliefs in sensor networks, due to its compact implementation and distributed nature. We investigate the ability of loopy belief propagation to function under the stressful conditions likely to prevail in sensor networks. Our experiments show that it performs well and degrades gracefully. It converges to appropriate beliefs even in highly asynchronous settings where some nodes communicate far less frequently than others; it continues to function if some nodes fail to participate in the propagation process; and it can track changes in the environment that occur while beliefs are propagating. As a result, we believe that sensor networks present an important application opportunity for UAI

UAI Conference 2002 Conference Paper

Factored Particles for Scalable Monitoring

• Brenda Ng
• Leonid Peshkin
• Avi Pfeffer

Exact monitoring in dynamic Bayesian networks is intractable, so approximate algorithms are necessary. This paper presents a new family of approximate monitoring algorithms that combine the best qualities of the particle filtering and Boyen-Koller methods. Our algorithms maintain an approximate representation the belief state in the form of sets of factored particles, that correspond to samples of clusters of state variables. Empirical results show that our algorithms outperform both ordinary particle filtering and the Boyen-Koller algorithm on large systems.

UAI Conference 2001 Conference Paper

Sufficiency, Separability and Temporal Probabilistic Models

• Avi Pfeffer

Suppose we are given the conditional probability of one variable given some other variables.Normally the full joint distribution over the conditioning variablesis required to determine the probability of the conditioned variable.Under what circumstances are the marginal distributions over the conditioning variables sufficient to determine the probability ofthe conditioned variable?Sufficiency in this sense is equivalent to additive separability ofthe conditional probability distribution.Such separability structure is natural and can be exploited forefficient inference.Separability has a natural generalization to conditional separability.Separability provides a precise notion of weaklyinteracting subsystems in temporal probabilistic models.Given a system that is decomposed into separable subsystems, exactmarginal probabilities over subsystems at future points in time can becomputed by propagating marginal subsystem probabilities, rather thancomplete system joint probabilities.Thus, separability can make exact prediction tractable.However, observations can break separability,so exact monitoring of dynamic systems remains hard.

AAAI Conference 2000 Conference Paper

Semantics and Inference for Recursive Probability Models

• Avi Pfeffer

In recent years, there have been several proposals that extend the expressive power of Bayesian networks with that of relational models. These languages open the possibility for the specification of recursive probability models, where a variable might depend on a potentially infinite (but finitely describable) set of variables. These models are very natural in a variety of applications, e. g. , in temporal, genetic, or language models. In this paper, we provide a structured representation language that allows us to specify such models, a clean measure-theoretic semantics for this language, and a probabilistic inference algorithm that exploits the structure of the language for efficient query-answering.

IJCAI Conference 1999 Conference Paper

Learning Probabilistic Relational Models

• Nir Friedman
• Use Getoor
• Daphne Kollen
• Avi Pfeffer

A large portion of real-world data is stored in commercial relational database systems. In contrast, most statistical learning methods work only with "flat" data representations. Thus, to apply these methods, we are forced to convert our data into a flat form, thereby losing much of the relational structure present in our database. This paper builds on the recent work on probabilistic relational models (PRMs), and describes how to learn them from databases. PRMs allow the properties of an object to depend probabilistically both on other properties of that object and on properties of related objects. Although PRMs are significantly more expressive than standard models, such as Bayesian networks, we show how to extend well-known statistical methods for learning Bayesian networks to learn these models. We describe both parameter estimation and structure learning — the automatic induction of the dependency structure in a model. Moreover, we show how the learning procedure can exploit standard database retrieval techniques for efficient learning from large datasets. We present experimental results on both real and synthetic relational databases.

UAI Conference 1999 Conference Paper

SPOOK: A system for probabilistic object-oriented knowledge representation

• Avi Pfeffer
• Daphne Koller
• Brian Milch
• Ken T. Takusagawa

In previous work, we pointed out the limitations of standard Bayesian networks as a modeling framework for large, complex domains. We proposed a new, richly structured modeling language, {em Object-oriented Bayesian Netorks}, that we argued would be able to deal with such domains. However, it turns out that OOBNs are not expressive enough to model many interesting aspects of complex domains: the existence of specific named objects, arbitrary relations between objects, and uncertainty over domain structure. These aspects are crucial in real-world domains such as battlefield awareness. In this paper, we present SPOOK, an implemented system that addresses these limitations. SPOOK implements a more expressive language that allows it to represent the battlespace domain naturally and compactly. We present a new inference algorithm that utilizes the model structure in a fundamental way, and show empirically that it achieves orders of magnitude speedup over existing approaches.

UAI Conference 1997 Conference Paper

Object-Oriented Bayesian Networks

• Daphne Koller
• Avi Pfeffer

Bayesian networks provide a modeling language and associated inference algorithm for stochastic domains. They have been successfully applied in a variety of medium-scale applications. However, when faced with a large complex domain, the task of modeling using Bayesian networks begins to resemble the task of programming using logical circuits. In this paper, we describe an object-oriented Bayesian network (OOBN) language, which allows complex domains to be described in terms of inter-related objects. We use a Bayesian network fragment to describe the probabilistic relations between the attributes of an object. These attributes can themselves be objects, providing a natural framework for encoding part-of hierarchies. Classes are used to provide a reusable probabilistic model which can be applied to multiple similar objects. Classes also support inheritance of model fragments from a class to a subclass, allowing the common aspects of related classes to be defined only once. Our language has clear declarative semantics: an OOBN can be interpreted as a stochastic functional program, so that it uniquely specifies a probabilistic model. We provide an inference algorithm for OOBNs, and show that much of the structural information encoded by an OOBN--particularly the encapsulation of variables within an object and the reuse of model fragments in different contexts--can also be used to speed up the inference process.

AIJ Journal 1997 Journal Article

Representations and solutions for game-theoretic problems

• Daphne Koller
• Avi Pfeffer

A system with multiple interacting agents (whether artificial or human) is often best analyzed using game-theoretic tools. Unfortunately, while the formal foundations are well-established, standard computational techniques for game-theoretic reasoning are inadequate for dealing with realistic games. This paper describes the Gala system, an implemented system that allows the specification and efficient solution of large imperfect information games. The system contains the first implementation of a recent algorithm, due to Koller, Megiddo and von Stengel. Experimental results from the system demonstrate that the algorithm is exponentially faster than the standard algorithm in practice, not just in theory. It therefore allows the solution of games that are orders of magnitude larger than were previously possible. The system also provides a new declarative language for compactly and naturally representing games by their rules. As a whole, the Gala system provides the capability for automated game-theoretic analysis of complex real-world situations.