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.

We study the automatic reply of email business messages in Brazilian Portuguese. We present a novel corpus containing messages from a real application, and baseline categorization experiments using Naive Bayes and Support Vector Machines. We then discuss the effect of lemmatization and the role of part-of-speech tagging filtering on precision and recall. Support Vector Machines classification coupled with non-lemmatized selection of verbs and nouns, adjectives and adverbs was the best approach, with 87.3% maximum accuracy. Straightforward lemmatization in Portuguese led to the lowest classification results in the group, with 85.3% and 81.7% precision in SVM and Naive Bayes respectively. Thus, while lemmatization reduced precision and recall, part-of-speech filtering improved overall results.

The study of network sizes in digital social networks is a research question of significant interest. Here, we explore the phenomenon of trimming, which is the decrease in the size of one’s network, and analyze if the rules of social exchange theory – namely, status consistency and reciprocity- can affect trimming. To this end, we use a Hidden Markov Model to investigate the relationship between the frequency of interaction and one’s network size, in which we are able to control for the current size of one’s digital social network. We find that there are significant patterns in sharing tendencies in digital social networks. One is that users who do not share enough are the group that is most likely to be trimmed from a network. Another is that users prefer to have moderate sized networks, i.e. networks with 500 – 1000 friends and prefer friends with moderate sharing tendencies (sharing approximately once a week). We also find that one’s sharing preferences over time tend to align with moderate sharing.

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.

In this paper an extension to factorial hidden Semi Markov Models is introduced that allows modeling more than one sequence of emissions of the individual HMM chains, as well as a joint emission of all chains. Since exact inference in factorial hidden Markov Models is computationally intractable, an approximate inference technique is introduced that reduces the computational costs by first constraining the successor state space of the model, allowing state changes at statistically significant points in time (events) and by discarding low probability paths (truncating). Furthermore, by being agnostic about state durations the computational costs are further decreased. These assumptions allow for efficient inference that is less susceptible to local minima and allows one to specify the computational burden a priori. The performance of the inference technique is evaluated empirically on a synthetic data set whereas incorporating the feature emissions is evaluated on real world data in the context of energy disaggregation. Energy disaggregation tackles the problem of decomposing whole home energy measurements into the power traces of constituent appliances, and is a natural application for this type of models.

We first discuss certain problems with the classical probabilistic approach for assessing forensic evidence, in particular its inability to distinguish between lack of belief and disbelief, and its inability to model complete ignorance within a given population. We then discuss Shafer belief functions, a generalization of probability distributions, which can deal with both these objections. We use a calculus of belief functions which does not use the much criticized Dempster rule of combination, but only the very natural Dempster-Shafer conditioning. We then apply this calculus to some classical forensic problems like the various island problems and the problem of parental identification. If we impose no prior knowledge apart from assuming that the culprit or parent belongs to a given population (something which is possible in our setting), then our answers differ from the classical ones when uniform or other priors are imposed. We can actually retrieve the classical answers by imposing the relevant priors, so our setup can and should be interpreted as a generalization of the classical methodology, allowing more flexibility. We show how our calculus can be used to develop an analogue of Bayes' rule, with belief functions instead of classical probabilities. We also discuss consequences of our theory for legal practice.

This work discusses a closed-loop control strategy for complex systems utilizing scarce and streaming data. A discrete embedding space is first built using hash functions applied to the sensor measurements from which a Markov process model is derived, approximating the complex system's dynamics. A control strategy is then learned using reinforcement learning once rewards relevant with respect to the control objective are identified. This method is designed for experimental configurations, requiring no computations nor prior knowledge of the system, and enjoys intrinsic robustness. It is illustrated on two systems: the control of the transitions of a Lorenz 63 dynamical system, and the control of the drag of a cylinder flow. The method is shown to perform well.

Our matching problem setting is similar to the transductive setting for classification, from Vapnik [9], where there is a set of training examples with known inputs and class labels and a set of working examples with known inputs and unknown class labels, and the goal is to use the available training and working data to develop a classifier that classifies the working examples with a low error rate. For results on validation of network classifiers (rather than reconciliation algorithms) in transductive settings, refer to [10] and [11]. For theory and insight on why collective classification succeeds in general settings and validation methods for it, refer to [12]. For network reconciliation, we assume that we know some network data, consisting of some node data and the links, for both networks involved in the matching, and our goal is to use that network data to match nodes as accurately as possible between the networks. This paper presents a technique to compute probably approximately correct (PAC) bounds on the precision and recall of matching algorithms.