Constrained sampling and counting are two fundamental problems in artificial intelligence with a diverse range of applications, spanning probabilistic reasoning and planning to constrained-random verification. While the theory of these problems was thoroughly investigated in the 1980s, prior work either did not scale to industrial size instances or gave up correctness guarantees to achieve scalability. Recently, we proposed a novel approach that combines universal hashing and SAT solving and scales to formulas with hundreds of thousands of variables without giving up correctness guarantees. This paper provides an overview of the key ingredients of the approach and discusses challenges that need to be overcome to handle larger real-world instances.

The increasing penetration of renewable energy sources and electric vehicles raises important challenges related to the operation of electricity grids. For instance, the amount of power generated by wind turbines is time-varying and dependent on the weather, which makes it hard to match flexible electric vehicle demand and uncertain wind power supply. In this paper we propose a vehicle aggregation framework which uses Markov Decision Processes to control charging of multiple electric vehicles and deals with uncertainty in renewable supply. We present a grouping technique to address the scalability aspects of our framework. In experiments we show that the aggregation framework maximizes the profit of the aggregator while reducing usage of conventionally-generated power and cost of customers.

Malware phylogenetics help cybersecurity experts to quickly understand a new malware sample by placing the new sample in the context of similar samples that have been previously reverse engineered. Recently, researchers have begun using malware code as data to infer directed acyclic graphs (DAG) that model the evolutionary relationships among samples of malware. A DAG is the ideal model for a phylogenetic graph because it includes the merges and branches that are often present in malware evolution. We present a novel Bayesian network discovery algorithm for learning a DAG via statistical inference of conditional dependencies from observed data with an informative prior on the partial ordering of variables. Our approach leverages the information on edge direction that a human can provide and the edge presence inference which data can provide. We give an efficient implementation of the partial-order prior in a Bayesian structure discovery learning algorithm, as well as a related structure prior, showing that both priors meet the local modularity requirement necessary for the efficient Bayesian discovery algorithm. We apply our algorithm to learn phylogenetic graphs on three malicious families and two benign families where the ground truth is known; and show that compared to competing algorithms, our algorithm more accurately identifies directed edges.

Most modern network-based intrusion detection systems (IDSs) passively monitor network traffic to identify possible attacks through known vectors. Though useful, this approach has widely known high false positive rates, often causing administrators to suffer from a "cry wolf effect," where they ignore all warnings because so many have been false. In this paper, we focus on a method to reduce this effect using an idea borrowed from computer vision and neuroscience called active perception. Our approach is informed by theoretical ideas from decision theory and recent research results in neuroscience. The active perception agent allocates computational and sensing resources to (approximately) optimize its Value of Information. To do this, it draws on models to direct sensors towards phenomena of greatest interest to inform decisions about cyber defense actions. By identifying critical network assets, the organization's mission measures self-interest (and value of information). This model enables the system to follow leads from inexpensive, inaccurate alerts with targeted use of expensive, accurate sensors. This allows the deployment of sensors to build structured interpretations of situations. From these, an organization can meet mission-centered decision-making requirements with calibrated responses proportional to the likelihood of true detection and degree of threat.

In many situations, agents are required to use a set of strategies (behaviors) and switch among them during the course of an interaction. This work focuses on the problem of recognizing the strategy used by an agent within a small number of interactions. We propose using a Bayesian framework to address this problem. Bayesian policy reuse (BPR) has been empirically shown to be efficient at correctly detecting the best policy to use from a library in sequential decision tasks. In this paper we extend BPR to adversarial settings, in particular, to opponents that switch from one stationary strategy to another. Our proposed extension enables learning new models in an online fashion when the learning agent detects that the current policies are not performing optimally. Experiments presented in repeated games show that our approach is capable of efficiently detecting opponent strategies and reacting quickly to behavior switches, thereby yielding better performance than state-of-the-art approaches in terms of average rewards.

Over the last decade, building on advances in the areas of knowledge compilation and weighted model counting has drastically increased the scalability of inference in probabilistic logic programs. In this paper, we provide an overview of how this has been possible and point out some open challenges.

The role of decomposition-trees (also known as junction and clique trees) in probabilistic inference is widely known and has been the basis for many well known inference algorithms.Recent approaches have demonstrated that such trees have a "hidden structure," which enables the characterization of tractable problem instances as well as lead to insights that enable boosting the performance of inference algorithms. We consider the MPE problem on a Boolean formula in CNF where each literal in the formula is associated with a weight.We describe techniques for exploiting the junction-tree structure of these formulas in the context of a branch-and-bound algorithm for MPE.

Compiling a Bayesian network into a secondary structure, such as a junction tree or arithmetic circuit allows for offline computations before observations arrive, and quick inference for the marginal of all variables. However, query-based algorithms, such as variable elimination and recursive conditioning, that compute the posterior marginal of few variables given some observations, allow pruning of irrelevant variables, which can reduce the size of the problem. Madsen and Jensen show how lazy evaluation of junction trees can allow both compilation and pruning. In this paper, we adapt the lazy evaluation to arithmetic circuits, allowing the best of both worlds: pruning due to observations and query variables as well as compilation while exploiting local structure and determinism.

Increasingly large Knowledge Bases are being created, by crawling the Web or other corpora of documents, and by extracting facts and relations using machine learning techniques. To manage the uncertainty in the data, these KBs rely on probabilistic engines based on Markov Logic Networks (MLN), for which probabilistic inference remains a major challenge. Today's state of the art systems reduce the task of inference to weighted model counting and use an MCMC algorithm wrapped around SampleSAT to generate approximately uniform samples. This approach offers no theoretical error guarantees and, as we show, suffers from poor performance in practice. In this paper we describe SlimShot (Scalable Lifted Inference and Monte Carlo Sampling Hybrid Optimization Technique), a probabilistic inference engine for Web-Scale knowledge bases. SlimShot converts the MLN to a tuple-independent probabilistic database, then uses a simple Monte Carlo-based inference, with three key enhancements: (1) it combines sampling with safe query evaluation, (2) it estimates a conditional probability by jointly computing the numerator and denominator, and (3) it adjusts the proposal distribution based on the sample cardinality. In combination, these three techniques allow us to give formal error guarantees, and we demonstrate empirically that SlimShot outperforms today's state of the art probabilistic inference engines used in knowledge bases.

SAT and #SAT are at the heart of many important problem formulations in AI, the most prominent being reasoning and learning in first-order and probabilistic knowledge bases. In practice, all contemporary systems resort to domain closure: objects in the universe are all and only the ones mentioned in the knowledge base. This is in stark contrast to the natural ability of human beings to infer things about sensory inputs and unforeseen data: they infer the existence of objects from their observations; no predefined list of objects is given or known in advance. In this paper, we introduce the formal foundations for reasoning in open universes in a general way, purely based on SAT and #SAT technology.