We consider an adversarial online learning setting where a decision maker can choose an action in every stage of the game. In addition to observing the reward of the chosen action, the decision maker gets side observations on the reward he would have obtained had he chosen some of the other actions. The observation structure is encoded as a graph, where node i is linked to node j if sampling i provides information on the reward of j. This setting naturally interpolates between the well-known "experts" setting, where the decision maker can view all rewards, and the multi-armed bandits setting, where the decision maker can only view the reward of the chosen action. We develop practical algorithms with provable regret guarantees, which depend on non-trivial graph-theoretic properties of the information feedback structure. We also provide partially-matching lower bounds.

Using an interactive theorem prover to reason about programs involves a sequence of interactions where the user challenges the theorem prover with conjectures. Invariably, many of the conjectures posed are in fact false, and users often spend considerable effort examining the theorem prover's output before realizing this. We present a synergistic integration of testing with theorem proving, implemented in the ACL2 Sedan (ACL2s), for automatically generating concrete counterexamples. Our method uses the full power of the theorem prover and associated libraries to simplify conjectures; this simplification can transform conjectures for which finding counterexamples is hard into conjectures where finding counterexamples is trivial. In fact, our approach even leads to better theorem proving, e.g. if testing shows that a generalization step leads to a false conjecture, we force the theorem prover to backtrack, allowing it to pursue more fruitful options that may yield a proof. The focus of the paper is on the engineering of a synergistic integration of testing with interactive theorem proving; this includes extending ACL2 with new functionality that we expect to be of general interest. We also discuss our experience in using ACL2s to teach freshman students how to reason about their programs.

We consider in this paper the problem of supervised metric learning on normalized histograms. Normalized histograms arise frequently in natural language processing, computer vision, bioinformatics and more generally areas involving complex datatypes. Objects of interest in such areas are usually simplified and each represented as a bag of smaller features. The occurrence frequencies of each of these features in the considered object can then be represented as a histogram. For instance, the representation of images as histograms of pixel colors, SIFT or GIST features (Lowe 1 1999, Oliva and Torralba 2001, Douze et al. 2009); texts as bags-of-words or topic allocations (Joachims 2002, Blei et al. 2003, Blei and Lafferty 2009); sequences as n-grams counts (Leslie et al. 2002) and graphs as histograms of subgraphs (Kashima et al. 2003) all follow this principle. Various distances have been proposed in the statistics and machine learning literatures to compare two histograms(Deza and Deza 2009,§14), (Rachev 1991). Our focus is in this paper is on the family of transportation distances, which is both well motivated theoretically (Villani 2003, §7), (Rachev 1991, §5) and works well empirically (Rubner et al. 1997; 2000, Pele and Werman 2009). Transportation distances are particularly popular in computer vision, where, after the influential work of Rubner et al. (1997), they were called Earth Mover's Distances (EMD). Transportation distances in machine learning can be thought of as metadistances that build upon a metric on the features to form a distance on histograms of features.

Goal recognition is the task of inferring users’ goals from sequences of observed actions. By enabling player-adaptive digital games to dynamically adjust their behavior in concert with players’ changing goals, goal recognition can inform adaptive decision making for a broad range of entertainment, training, and education applications. This paper presents a goal recognition framework based on Markov logic networks (MLN). The model’s parameters are directly learned from a corpus of actions that was collected through player interactions with a non-linear educational game. An empirical evaluation demonstrates that the MLN goal recognition framework accurately predicts players’ goals in a game environment with multiple solution paths.

Drama Managers, a specific type of the more general Experience Manager, have become a common subject of study in the interactive narrative literature. With a range of representational and computational approaches, authors have repeatedly developed techniques that enable computers to generate, reason about, and adapt narratives in an interactive virtual setting. In order to fully realize an experience manager, seven representational and computational problems need to be solved, generally on a case-by-case basis. In other words, the choice to use an Experience Manager is the choice to model the design as, and implement solutions to, seven inter-dependent design problems. We explicitly articulate those design problems and provide a number of examples of methods that both motivate the design problems as well as illustrate a range of approaches to solving them.

Interactive narrative environments offer significant potential for creating engaging narrative experiences that are tailored to individual users. Increasingly, applications in education, training, and entertainment are leveraging narrative to create rich interactive experiences in virtual storyworlds. A key challenge posed by these environments is devising accurate models of director agents’ strategies that determine the most appropriate director action to perform for crafting customized story experiences. A promising approach is developing an empirically informed model of director agents’ decision-making strategies. In this paper, we propose a framework for learning models of director agent decision-making strategies by observing human-human interactions in an interactive narrative-centered learning environment. The results are encouraging and suggest that creating empirically driven models of director agent decision-making is a promising approach to interactive narrative.

The task of narrative visualization has been the subject of increasing interest in recent years. Much like data visualization, narrative visualization offers users an informative and aesthetically pleasing perspective on “storydata.” Automatically creating visual representations ofnarratives poses significant computational challenges due to the complex affective and causal elements, among other things, that must be realized in visualizations. In addition, narratives that are composed by novice writers pose additional challenges due to the disfluencies stemming from ungrammatical text. In this paper, we introduce the NARRATIVE THEATRE, a narrative visualization system under development in our laboratory that generates narrative visualizations from middle school writers’ text. The NARRATIVE THEATRE consists of a rich writing interface, a robust natural language processor, a narrative reasoner, and a storyboard generator. We discuss design issues bearing on narrative visualization, introduce the NARRATIVE THEATRE, and describe narrative corpora that have been collected to study narrative visualization. We conclude with a discussion of a narrative visualization research agenda.

We revisit the additive model learning literature and adapt a penalized spline formulation due to Eilers and Marx [4], to train additive classifiers efficiently. We also propose two new embeddings based two classes of orthogonal basis with orthogonal derivatives, which can also be used to efficiently learn additive classifiers. This paper follows the popular theme in the current literature where kernel SVMs are learned much more efficiently using a approximate embedding and linear machine. In this paper we show that spline basis are especially well suited for learning additive models because of their sparsity structure and the ease of computing the embedding which enables one to train these models in an online manner, without incurring the memory overhead of precomputing the storing the embeddings. We show interesting connections between B-Spline basis and histogram intersection kernel and show that for a particular choice of regularization and degree of the B-Splines, our proposed learning algorithm closely approximates the histogram intersection kernel SVM. This enables one to learn additive models with almost no memory overhead compared to fast a linear solver, such as LIBLINEAR, while being only 5 6 slower on average. On two large scale image classification datasets, MNIST and Daimler Chrysler pedestrians, the proposed additive classifiers are as accurate as the kernel SVM, while being two orders of magnitude faster to train.

This thesis derives, tests and applies two linear projection algorithms for machine learning under non-stationarity. The first finds a direction in a linear space upon which a data set is maximally non-stationary. The second aims to robustify two-way classification against non-stationarity. The algorithm is tested on a key application scenario, namely Brain Computer Interfacing.

Today, available methods that assess AI systems are focused on using empirical techniques to measure the performance of algorithms in some specific tasks (e.g., playing chess, solving mazes or land a helicopter). However, these methods are not appropriate if we want to evaluate the general intelligence of AI and, even less, if we compare it with human intelligence. The ANYNT project has designed a new method of evaluation that tries to assess AI systems using well known computational notions and problems which are as general as possible. This new method serves to assess general intelligence (which allows us to learn how to solve any new kind of problem we face) and not only to evaluate performance on a set of specific tasks. This method not only focuses on measuring the intelligence of algorithms, but also to assess any intelligent system (human beings, animals, AI, aliens?,...), and letting us to place their results on the same scale and, therefore, to be able to compare them. This new approach will allow us (in the future) to evaluate and compare any kind of intelligent system known or even to build/find, be it artificial or biological. This master thesis aims at ensuring that this new method provides consistent results when evaluating AI algorithms, this is done through the design and implementation of prototypes of universal intelligence tests and their application to different intelligent systems (AI algorithms and humans beings). From the study we analyze whether the results obtained by two different intelligent systems are properly located on the same scale and we propose changes and refinements to these prototypes in order to, in the future, being able to achieve a truly universal intelligence test.