Hidden Markov Models have been used frequently in the audio domain to identify underlying musical structure. Much less work has been done in the purely symbolic realm. Recently, a substantial amount of expert-labelled symbolic musical data has been injected into the research community. The new availability of data allows for the application of machine learning models to purely symbolic tasks. Similarly, the continued expansion of the field of machine learning provides new perspectives and implementations of machine learning methods, which are powerful tools when approaching complex musical challenges. This research explores the use of an extended probabilistic model such as the Hidden Semi-Markov Model (HSMM) to approach the task of automatic harmonization. One distinct advantage of the HSMM is that it is able to automatically differentiate harmonic boundaries, through its inclusion of an extra parameter: duration. In this way, a melody can be harmonized automatically in the style of a particular corpus. In the case of this research, the corpus was in the style of Rock 'n' Roll.

A key functionality provided by interactive narrative systems is narrative adaptation: tailoring story experiences in response to users’ actions and needs. We present a data-driven framework for dynamically tailoring events in interactive narratives using modular reinforcement learning. The framework involves decomposing an interactive narrative into multiple concurrent sub-problems, formalized as adaptable event sequences (AESs). Each AES is modeled as an independent Markov decision process (MDP). Policies for each MDP are induced using a corpus of user interaction data from an interactive narrative system with exploratory narrative adaptation policies. Rewards are computed based on users’ experiential outcomes. Conflicts between multiple policies are handled using arbitration procedures. In addition to introducing the framework, we describe a corpus of user interaction data from a testbed interactive narrative, CRYSTAL ISLAND, for inducing narrative adaptation policies. Empirical findings suggest that the framework can effectively shape users’ interactive narrative experiences.

Computational models of goal recognition hold considerable promise for enhancing the capabilities of drama managers and director agents for interactive narratives. The problem of goal recognition, and its more general form plan recognition, has been the subject of extensive investigation in the AI community. However, there have been relatively few empirical investigations of goal recognition models in the intelligent narrative technologies community to date, and little is known about how computational models of interactive narrative can inform goal recognition. In this paper, we investigate a novel goal recognition model based on Markov Logic Networks (MLNs) that leverages narrative discovery events to enrich its representation of narrative state. An empirical evaluation shows that the enriched model outperforms a prior state-of-the-art MLN model in terms of accuracy, convergence rate, and the point of convergence.

Player classification allows for considerable improvements on both game analytics and game adaptivity. With this paper we aim at reversing the ad-hoc tendency in player classification methods, by proposing an approach to player classification that can be integrated across different games and genres and is particularly suited to be used by game designers. This paper describes our generic method of interaction-based player classification, which consists of three components: (i) intercepting player interactions, (ii) finding player types through fuzzy cluster analysis and (iii) classification using Hidden Markov Models (HMM). To showcase our method we developed Blindmaze, a simple web-based hidden maze game publicly available, featuring a bounded set of interactions. All data collected from a game is interaction-based, requiring minimal implementation effort from the game developers. It is concluded that our method makes player classification even more available by making it generic and re-usable across different games.

In this paper we outline a method of procedurally generating maps using Markov Chains. Our method attempts to learn what makes a "good" map from a set of given human-authored maps, and then uses those learned patterns to generate new maps. We present an empirical evaluation using the game "Super Mario Bros.," showing encouraging results.

Gaussian Graphical Models (GGMs) or Gauss Markov random fields are widely used in many applications, and the trade-off between the modeling capacity and the efficiency of learning and inference has been an important research problem. In this paper, we study the family of GGMs with small feedback vertex sets (FVSs), where an FVS is a set of nodes whose removal breaks all the cycles. Exact inference such as computing the marginal distributions and the partition function has complexity $O(k^{2}n)$ using message-passing algorithms, where k is the size of the FVS, and n is the total number of nodes. We propose efficient structure learning algorithms for two cases: 1) All nodes are observed, which is useful in modeling social or flight networks where the FVS nodes often correspond to a small number of high-degree nodes, or hubs, while the rest of the networks is modeled by a tree. Regardless of the maximum degree, without knowing the full graph structure, we can exactly compute the maximum likelihood estimate in $O(kn^2+n^2\log n)$ if the FVS is known or in polynomial time if the FVS is unknown but has bounded size. 2) The FVS nodes are latent variables, where structure learning is equivalent to decomposing a inverse covariance matrix (exactly or approximately) into the sum of a tree-structured matrix and a low-rank matrix. By incorporating efficient inference into the learning steps, we can obtain a learning algorithm using alternating low-rank correction with complexity $O(kn^{2}+n^{2}\log n)$ per iteration. We also perform experiments using both synthetic data as well as real data of flight delays to demonstrate the modeling capacity with FVSs of various sizes.

We consider the problem of recovering block-sparse signals whose structures are unknown \emph{a priori}. Block-sparse signals with nonzero coefficients occurring in clusters arise naturally in many practical scenarios. However, the knowledge of the block structure is usually unavailable in practice. In this paper, we develop a new sparse Bayesian learning method for recovery of block-sparse signals with unknown cluster patterns. Specifically, a pattern-coupled hierarchical Gaussian prior model is introduced to characterize the statistical dependencies among coefficients, in which a set of hyperparameters are employed to control the sparsity of signal coefficients. Unlike the conventional sparse Bayesian learning framework in which each individual hyperparameter is associated independently with each coefficient, in this paper, the prior for each coefficient not only involves its own hyperparameter, but also the hyperparameters of its immediate neighbors. In doing this way, the sparsity patterns of neighboring coefficients are related to each other and the hierarchical model has the potential to encourage structured-sparse solutions. The hyperparameters, along with the sparse signal, are learned by maximizing their posterior probability via an expectation-maximization (EM) algorithm. Numerical results show that the proposed algorithm presents uniform superiority over other existing methods in a series of experiments.

Relational data-like graphs, networks, and matrices-is often dynamic, where the relational structure evolves over time. A fundamental problem in the analysis of time-varying network data is to extract a summary of the common structure and the dynamics of the underlying relations between the entities. Here we build on the intuition that changes in the network structure are driven by the dynamics at the level of groups of nodes. We propose a nonparametric multi-group membership model for dynamic networks. Our model contains three main components: We model the birth and death of individual groups with respect to the dynamics of the network structure via a distance dependent Indian Buffet Process. We capture the evolution of individual node group memberships via a Factorial Hidden Markov model. And, we explain the dynamics of the network structure by explicitly modeling the connectivity structure of groups. We demonstrate our model's capability of identifying the dynamics of latent groups in a number of different types of network data. Experimental results show that our model provides improved predictive performance over existing dynamic network models on future network forecasting and missing link prediction.

Markov decision processes (MDPs) provide a class of stochastic optimisation models that have found wide applicability to problems in Operational Research. The standard methods for computing an optimal policy are based on value iteration, policy iteration and linear programming algorithms (White 1993). Each approach has its advantages and disadvantages. In particular, each step in value iteration is relatively computationally inexpensive but the value function may take some time to converge and the algorithm provides no direct check that it has computed the optimal value function and an optimal policy. Conversely, each step in policy iteration may be computationally expensive but the algorithm can be proved to converge in a finite number of steps, confirms when it has converged and automatically identifies the optimal value function and an optimal policy on exit.

Crowdsourcing requesters are trapped between a rock and a hard place. Typically they specify their crowdsourcing workflows procedurally, but current languages commit them to overly strict and static policies that waste human effort. While optimizing workflows with more sophisticated tools like POMDPs can significantly reduce labor costs, such advanced AI techniques are hard to use and understand. We report on our progress in developing Clowder, a system that provides the user with an adaptive programming language that looks and feels like Lisp, yet abstracts over POMDPs so that non-experts can write POMDPs without knowing anything about them. Such a system frees requesters from needing to resort to suboptimal techniques that use approximate heuristics or hire a planning expert to formally define and solve their problems.