We consider the problem of modeling network interactions and identifying latent groups of network nodes. This problem is challenging due to the facts i) that the network nodes are interdependent instead of independent, ii) that the network data are very noisy (e.g., missing edges), and iii) that the network interactions are often sparse. To address these challenges, we propose a Sparse Matrix-variate t process Blockmodel (SMTB). In particular, we generalize a matrix-variate t distribution to a t process on matrices with nonlinear covariance functions. Due to this generalization, our model can estimate latent memberships for individual network nodes. This separates our model from previous t distribution based relational models. Also, we introduce sparse prior distributions on the latent membership parameters to select group assignments for individual nodes. To learn the model efficiently from data, we develop a variational method. When compared with several state-of-the-art models, including the predictive matrix-variate t models and mixed membership stochastic blockmodels, our model achieved improved prediction accuracy on real world network datasets.

Real-time heuristic search algorithms that precompute search space-specific databases have demonstrated exceptional performance in video-game pathfinding. We discuss the first steps towards extending these algorithms to other search spaces that also benefit from the real-time property. We present our initial progress in characterizing the performance of current algorithms based on the features of a search space, and discuss future directions of this research.

In the existing methods for solving matrix completion, such as singular value thresholding (SVT), soft-impute and fixed point continuation (FPCA) algorithms, it is typically required to repeatedly implement singular value decompositions (SVD) of matrices.When the size of the matrix in question is large, the computational complexity of finding a solution is costly. To reduce this expensive computational complexity, we apply Kronecker products to handle the matrix completion problem. In particular, we propose using Kronecker factorization, which approximates a matrix by the Kronecker product of several matrices of smaller sizes. Weintroduce Kronecker factorization into the soft-impute framework and devise an effective matrix completion algorithm.Especially when the factorized matrices have about the samesizes, the computational complexity of our algorithm is improved substantially.

With smart-phones becoming increasingly commonplace, there has been a subsequent surge in applications that continuously track the location of users. However, serious privacy concerns arise as people start to widely adopt these applications. Users will need to maintain policies to determine under which circumstances to share their location. Specifying these policies however, is a cumbersome task, suggesting that machine learning might be helpful. In this paper, we present a user-controllable method for learning location sharing policies. We use a classifier based on multivariate Gaussian mixtures that is suitably modified so as to restrict the evolution of the underlying policy to favor incremental and therefore human-understandable changes as new data arrives. We evaluate the model on real location-sharing policies collected from a live location-sharing social network, and we show that our method can learn policies in a user-controllable setting that are just as accurate as policies that do not evolve incrementally. Additionally, we highlight the strength of the generative modeling approach we take, by showing how our model easily extends to the semi-supervised setting.

The ability to understand natural-language instructions is critical to building intelligent agents that interact with humans. We present a system that learns to transform natural-language navigation instructions into executable formal plans. Given no prior linguistic knowledge, the system learns by simply observing how humans follow navigation instructions. The system is evaluated in three complex virtual indoor environments with numerous objects and landmarks. A previously collected realistic corpus of complex English navigation instructions for these environments is used for training and testing data. By using a learned lexicon to refine inferred plans and a supervised learner to induce a semantic parser, the system is able to automatically learn to correctly interpret a reasonable fraction of the complex instructions in this corpus.

Selection bias, caused by preferential exclusion of units (or samples) from the data, is a major obstacle to valid causal inferences, for it cannot be removed or even detected by randomized experiments. This paper highlights several graphical and algebraic methods capable of mitigating and sometimes eliminating this bias.

Set and multiset variables in constraint programming have typically been represented using subset bounds. However, this is a weak representation that neglects potentially useful information about a set such as its cardinality. For set variables, the length-lex (LL) representation successfully provides information about the length (cardinality) and position in the lexicographic ordering. For multiset variables, where elements can be repeated, we consider richer representations that take into account additional information. We study eight different representations in which we maintain bounds according to one of the eight different orderings: length-(co)lex (LL/LC), variety-(co)lex (VL/VC), length-variety-(co)lex (LVL/LVC), and variety-length-(co)lex (VLL/VLC) orderings. These representations integrate together information about the cardinality, variety (number of distinct elements in the multiset), and position in some total ordering. Theoretical and empirical comparisons of expressiveness and compactness of the eight representations suggest that length-variety-(co)lex (LVL/LVC) and variety-length-(co)lex (VLL/VLC) usually give tighter bounds after constraint propagation. We implement the eight representations and evaluate them against the subset bounds representation with cardinality and variety reasoning. Results demonstrate that they offer significantly better pruning and runtime.

Without commitment, this game is solvable by iterated Game theory provides a mathematical framework for rational strict dominance: U strictly dominates D for player 1; after action in settings with multiple agents. As such, algorithms removing D, L strictly dominates R for player 2. So for computing game-theoretic solutions are of great the iterated strict dominance outcome (and hence the only interest to the multiagent systems community in AI. equilibrium outcome) is (U, L), resulting in a utility of 1 for It has long been well known in game theory that being player 1. However, if player 1 can commit to a pure strategy able to commit to a course of action before the before player 2 moves, then player 1 is better off committing other player(s) move(s)--often referred to as a Stackelberg to D, thereby incentivizing player 2 to play R, resulting model (von Stackelberg 1934)--can bestow significant in a utility of 2 for player 1. Even better for player 1 is to advantages. In recent years, the problem of computing commit to a mixed strategy of (.49U,.51D); this still incentivizes an optimal strategy to commit to has started to receive player 2 to play R and results in an expected utility a significant amount of attention, especially in the multiagent of.49

The behavior and dynamics of complex systems are in focus of many research fields. The complexity of such systems comes not only from the number of their elements, but also from the unavoidable emergence of new properties of the system, which are not just a simple summation of the properties of its elements. The behavior of complex systems can be fitted with a number of well developed models, which, however, do not incorporate the modularity and the evolution of a system simultaneously. In this work, we propose a generalized model that addresses this issue. Our model is developed within the Random Set Theory’s framework and allows for reconstructing the stochastic evolution diagrams of complex systems.

Diversity-aware planning consists of generating multiple plans which, while solving the same problem, are dissimilar from one another. Quantitative plan diversity is domain-independent and does not require extensive knowledge-engineering effort, but can fail to reflect plan differences that are relevant to users. Qualitative plan diversity is based on domain-specific characteristics, thus being of greater practical value, but may require substantial knowledge engineering. We demonstrate a domain-independent diverse plan generation method that is based on customizable plan distance metrics and amenable to both quantitative and qualitative diversity. Qualitative plan diversity is obtained with minimal knowledge-engineering effort, using distance metrics which incorporate domain-specific content.