Lifting can greatly reduce the cost of inference on first-order probabilistic graphical models, but constructing the lifted network can itself be quite costly. In online applications (e.g., video segmentation) repeatedly constructing the lifted network for each new inference can be extremely wasteful, because the evidence typically changes little from one inference to the next. The same is true in many other problems that require repeated inference, like utility maximization, MAP inference, interactive inference, parameter and structure learning, etc. In this paper, we propose an efficient algorithm for updating the structure of an existing lifted network with incremental changes to the evidence. This allows us to construct the lifted network once for the initial inference problem, and amortize the cost over the subsequent problems. Experiments on video segmentation and viral marketing problems show that the algorithm greatly reduces the cost of inference without affecting the quality of the solutions.

This work proposes new approximate (and exact) inference methods for reasoning about an important and hard-to-compute property of the solution space of combinatorial problems, namely clusters of solutions. We introduce an approximate method that first reformulates the constraint satisfaction problem (CSP) as a "factor graph" over an extended set of variable domains, approximates the number of clusters using an exponential size expression defined over this factor graph, and then estimates the value of this expression using message passing techniques, specifically an extension of the belief propagation (BP) algorithm. We provide formal exactness results as well as an empirical evaluation attesting to the accuracy of our method in counting the number of solution clusters.

BLOG is a powerful language to express models with an unknown number of objects and identity uncertainty. Current inference engines for BLOG are either too slow or require users to write a model-specific proposal distribution. We describe here, ongoing work to design a new, fast, generic inference engine for BLOG called blogc. The new implementation uses Gibbs sampling for finite-valued variables and performs an analysis of the model to generate customized sampling code in C. We describe our algorithms and methods in the context of various commonly used models and demonstrate significant performance improvement.

Relational Continuous Models (RCMs) represent joint probability densities over attributes of objects, when the attributes have continuous domains. With relational representation, they can model joint probability distributions over large numbers of variables compactly in a natural way. This paper presents the first exact inference algorithm for RCMs at a lifted level, so that it scales up to large models of real world applications. The algorithm applies to relational pairwise models which are (relational) products of potentials of arity 2. Our algorithm is unique in two ways. First, it is an efficient lifted inference algorithm. When Gaussian potentials are used, it takes only linear time while existing methods take cubic time. Second, it is the first exact inference algorithm which handles RCMs in a lifted way. The algorithm is illustrated over an example from Econometrics. Experimental results show that our algorithm outperforms both a ground-level inference algorithm and an algorithm built with previously-known lifted methods

In this paper we study the sequential strategic interactive setting of two-person, two-stage, seller-offers bargaining under uncertainty. We model the epistemology of the problem in a finite interactive decision-theoretic framework and solve it for three types of agents of successively increasing (epistemological) sophistication (or, capacity to represent and reason with higher orders of beliefs). In particular, we remove common knowledge assumptions about the agents' epistemology which, if made, would be sufficient to imply the existence of a, possibly unique, game-theoretic equilibrium solution. In this context, we present a characterization of a monotonic relationship between an agent's optimal behavior and its beliefs under a particular moment-based ordering. Further, based on this characterization, we present the \emph{spread-accumulate} sampling technique -- a method of sampling an agent's higher order belief by generating ``evenly dispersed" beliefs for which we (pre)compute offline solutions. Then, we present a method for approximating higher order prior belief update to arbitrary precision by identifying a (previously solved) belief ``closest" to the true belief. In addition, these methods directly suggest a mechanism for achieving a balance between efficiency and the quality of the approximation -- either by generating a large number of offline solutions or by allowing the agent to search online for a ``closer" belief in the vicinity of best current solution.

We study the problem of achieving cooperation between two self-interested agents that play a sequence of randomly generated normal form games, each game played only once. To achieve cooperation we extend a model used to explain cooperative behavior by humans. We show how a modification of a pre-regularized particle filter can be used to detect the cooperation level of the opponent and play accordingly. We examine how properties of the games affect the ability of an agent to detect cooperation and explore the effects of different environments and different levels of conflict. We present results obtained in simulation on hundreds of randomly generated games.

In this work, we present maximum causal entropy correlated equilibria, a new solution concept that we apply to Markov games. This contribution extends the existing solution concept of maximum entropy correlated equilibria for normal-form games to settings with elements of dynamic interaction with a stochastic environment by employing the recently developed principle of maximum causal entropy. This solution concept is justified for two purposes: as a mechanism for prescribing actions, it reveals the least additional information about the agents' motives possible; and as a predictive estimator of actions for a group of agents assumed to behave according to an unknown correlated equilibrium, it has the fewest additional assumptions and minimizes worst-case action prediction log-loss. Importantly, equilibria for this solution concept are guaranteed to be unique and Markovian, enabling efficient algorithms for finding them.

Informational conflicts in operational policies cause agents to run into situations where responding based on the rules in one policy violates the same or another policy. Static checking of these conflicts is infeasible and impractical in a dynamic environment. This paper discusses a practical approach to handling policy conflicts in real-time domains within the context of a hierarchical military command and control simulated system that consists of a central command, squad leaders and squad members. All the entities in the domain function according to preset communication and action protocols in order to perform successful missions. Each entity in the domain is equipped with an instance of a metacognitive component to provide on-board/on-time analysis of actions and recommendations during the operation of the system. The metacognitive component is the Metacognitive Loop (MCL) which is a general purpose anomaly processor designed to function as a cross-domain plugin system. It continuously monitors expectations and notices when they are violated, assesses the cause of the violation and guides the host system to an appropriate response. MCL makes use of three ontologies—indications, failures and responses—to perform the notice, assess and guide phases when a conflict occurs. Conflicts in the set of rules (within a policy or between policies) manifest as expectation violations in the real world. These expectation violations trigger nodes in the indication ontology which, in turn, activate associated nodes in the failure ontology. The responding failure nodes then activate the appropriate nodes in the response ontology. Depending on which response node gets activated, the actual response may vary from ignoring the conflict to prioritizing, modifying or deleting one or more conflicting rules.

Knowledge compilation is a valuable tool for dealing with the computational intractability of propositional reasoning. In knowledge compilation, a representation in a source language is typically compiled into a target language in order to perform some reasoning task in polynomial time. One particularly popular target language is Deterministic Decomposable Negation Normal Form (d-DNNF). d-DNNF supports efficient reasoning for tasks such as consistency checking and model counting, and as such it has proven a useful representation language for Bayesian inference, conformant planning, and diagnosis. In this paper, we exploit recent advances in #SAT solving in order to produce a new state-of-the-art CNF → d-DNNF compiler. We evaluate the properties and performance of our compiler relative to C2D, the de facto standard for compiling to d-DNNF. Empirical results demonstrate that our compiler is generally one order of magnitude faster than C2D on typical benchmark problems while yielding a d-DNNF representation of comparable size.

Learning useful information when solving SAT or CSP problems to speed up a tree-search approaches, is one of the main explored tracks in various works. Such information are known as goods and nogoods and they aim to forbid to repetitively visit the same parts of the search space. Unfortunately and unlike nogoods, the exploitation of goods is limited to tree-search approaches based on the structural properties of the problem. In this paper, we propose to generalize and reformulate structural goods under SAT. We also propose a learning scheme of general goods and show their integration in a DPLL-like procedure.