This paper describes a machine learning approach to classifying the activities of players in games. Instances of activities generally are not identical because they play out in different contexts, so the challenge is to extract the "essences" of activities from instances. We show how this problem may be mapped to a sequence alignment problem, for which there are polynomial-time solutions. The method works well even when some features of activities are not observable (e.g., the emotional states of players). In fact, these features can in some conditions be inferred with high accuracy.

We propose an intelligent tutoring system that constructs a curriculum of hints and problems in order to teach a student skills with a rich dependency structure. We provide a template for building a multi-layered Dynamic Bayes Net to model this problem and describe how to learn the parameters of the model from data. Planning with the DBN then produces a teaching policy for the given domain. We test this end-to-end curriculum design system in two human-subject studies in the areas of finite field arithmetic and artificial language and show this method performs on par with hand-tuned expert policies.

Currently, most systems for human-robot teaching allow only one mode of teacher-student interaction (e.g., teaching by demonstration or feedback), and teaching episodes have to be carefully set-up by an expert. To understand how we might integrate multiple, interleaved forms of human instruction into a robot learner, we performed a behavioral study in which 44 untrained humans were allowed to freely mix interaction modes to teach a simulated robot (secretly controlled by a human) a complex task. Analysis of transcripts showed that human teachers often give instructions that are nontrivial to interpret and not easily translated into a form useable by machine learning algorithms. In particular, humans often use implicit instructions, fail to clearly indicate the boundaries of procedures, and tightly interleave testing, feedback, and new instruction. In this paper, we detail these teaching patterns and discuss the challenges they pose to automatic teaching interpretation as well as the machine-learning algorithms that must ultimately process these instructions. We highlight the challenges by demonstrating the difficulties of an initial automatic teacher interpretation system.

Europe and the U.S. both face the challenges of urban schools with low-achieving adolescent learners, many of whom are not proficient in the language of instruction. This paper describes the deployment and evaluation of the AnimalWatch intelligent tutoring system for mathematics in challenging classrooms. Previous studies demonstrated that AnimalWatch benefits 12–14 year-old students in relatively controlled conditions. The current study indicates that the system can help older, very low-achieving students in challenging secondary schools that serve diverse student populations.

Relational classification in networked data plays an important role in many problems such as text categorization, classification of Web pages, group finding in peer networks, etc. We have previously demonstrated that for a class of label propagating algorithms the underlying dynamics can be modeled as a two-state epidemic process on heterogeneous networks, where infected nodes correspond to classified data instances. We have also suggested a binary classification algorithm that utilizes non-trivial characteristics of epidemic dynamics. In this paper we extend our previous work by considering a three-state epidemic model for label propagation. Specifically, we introduce a new, intermediate state that corresponds to "susceptible" data instances. The utility of the added state is that it allows to control the rates of epidemic spreading, hence making the algorithm more flexible. We show empirically that this extension improves significantly the performance of the algorithm. In particular, we demonstrate that the new algorithm achieves good classification accuracy even for relatively large overlap across the classes

We describe the Hats simulator as an information fusion challenge problem. Hats is a virtual world in which many agents engage in individual and collective activities. Most agents are benign, some intend harm. Agent activities are planned by a generative planner. Playing against the simulator, the goal of the analyst is to identify and arrest harmful agents before they carry out their plans. The simulator provides both scalar and categorical information. Information fusion tasks in the Hats domain include assessing information value, choosing information collection strategies, tracking individuals and resources, identifying events, hypothesizing group membership, ascribing suspicion, and identifying plans. After each game, the analyst is assessed a set of scores including the cost of acquiring information, the cost of falsely accusing benign agents, and the cost of failing to detect harmful agents. The simulator is implemented and currently manages hundreds of thousands of agents

COLAB is an analysis environment in which multiple human analysts in different physical locations can collaborate to build hypotheses of unfolding scenarios. COLAB consists of two components: an instrumented analysis working environment built on a blackboard system, and a Web-based user interface that integrates the trellis hypothesis authoring and management tool with a query language. On the blackboard, analysts collect data and perform analyses using relational database queries and a set of analysis tools that include group identification and suspicion scoring algorithms. Evidence extracted from data analysis on the blackboard may then be incorporated in hierarchical argument structures in the trellis tool, combining evidence sources with user-supplied free text. Trellis arguments may then be shared between analysts and collaboratively authored. COLAB has been integrated with the Hats Simulator challenge domain and serves as a prototype mixed-initiative information fusion system

This paper describes an unsupervised algorithm for segmenting categorical time series into episodes. The VOTING-EXPERTS algorithm first collects statistics about the frequency and boundary entropy of ngrams, then passes a window over the series and has two "expert methods" decide where in the window boundaries should be drawn. The algorithm successfully segments text into words in four languages. The algorithm also segments time series of robot sensor data into subsequences that represent episodes in the life of the robot. We claim that VOTING-EXPERTS finds meaningful episodes in categorical time series because it exploits two statistical characteristics of meaningful episodes.

Exploratory data analysis (EDA) plays an increasingly important role in statistical analysis. EDA is difficult, however, even with the help of modern statistical software. We have developed an assistant for data exploration, based on AI planning techniques, that addresses some of the strategic shortcomings of conventional software. This paper illustrates the behavior of the system, gives a high level description of its design, and discusses its experimental evaluation.

Envelopes are a form of decision rule for monitoring plan execution. We describe one type, the DP (dynamic programming) envelope, that draws its decisions from a look-up table computed off-line by dynamic programming. Based on an abstract model of agent progress, DP envelopes let a developer approach execution monitoring as a problem that is independent of issues in agent design. We discuss the application of DP envelopes to a small transportation planning simulation, and discuss the issues that arise in an empirical analysis of the results.

Presents a methodology for learning complex dependencies in data based on streams of categorical time-series data. The streams representation is applicable in a variety of situations. A program's execution trace may be thought of as a stream. The various monitor readings of an intensive care unit may be thought of as concurrent streams. Our learning methodology, called 'dependency detection', examines one or more streams to characterize a recurring structure with a set of dependency rules. These dependency rules are useful not only as a description of how the data is structured, but as a means for predicting future stream states. Further, we describe a set of tools for program analysis that use dependency detection.

The paper describes two separate but synergistic tools for running experiments on large Lisp systems such as artificial intelligence planning systems, by which we mean systems that produce plans and execute them in some kind of simulator. The first tool, called CLIP (Common Lisp Instrumentation Package), allows the researcher to define and run experiments, including experimental conditions (parameter values of the planner or simulator) and data to be collected. The data are written out to data files that can be analyzed by statistics software. The second tool, called CLASP (Common Lisp Analytical Statistics Package), allows the researcher to analyze data from experiments by using graphics, statistical tests, and various kinds of data manipulation. CLASP has a graphical user interface (using CLIM, the Common Lisp Manager) and also allows data to be directly processed by Lisp functions.>

Statistical causal modeling techniques allow us to develop models of program behavior, but these techniques tend to be limited in what they can model: either continuing, repetitive influences or causal influences without cycles, but not both as appear in many environments. The paper describes how two statistical modeling techniques can be combined to suggest and test specific hypotheses about how the environment and the AI planner's design causally influence the planner's behavior. One technique, dependency detection, is designed to identify relationships (dependencies) between particular failures, the methods that repair them and the occurrence of failures downstream. Another method, path analysis, builds causal models of correlational data. Dependency detection operates over a series of events, and path analysis models within a temporal snapshot. We explain the integration of the techniques and demonstrate it on execution data from the Phoenix planner.>

A camera model that accounts for major sources of camera distortion, namely, radial, decentering, and thin prism distortions is presented. The proposed calibration procedure consists of two steps: (1) the calibration parameters are estimated using a closed-form solution based on a distribution-free camera model; and (2) the parameters estimated in the first step are improved iteratively through a nonlinear optimization, taking into account camera distortions. According to minimum variance estimation, the objective function to be minimized is the mean-square discrepancy between the observed image points and their inferred image projections computed with the estimated calibration parameters. The authors introduce a type of measure that can be used to directly evaluate the performance of calibration and compare calibrations among different systems. The validity and performance of the calibration procedure are tested with both synthetic data and real images taken by tele- and wide-angle lenses.>

A closed-form approximate matrix-weighted solution for estimating motion parameters from point correspondences in two stereo image pairs is presented. The corresponding algorithm is noniterative and fast. Simulation shows that the solution is significantly more reliable than the unweighted and the scalar-weighted solutions, except when the number of point correspondences is less than seven. The matrix-weighted least squares solution can be used as a final solution if the speed requirement does not allow iterations. An approach to optimal estimation of the motion parameters and the structure of the three-dimensional points is also introduced. In experiments with a calibrated real stereo setup, the motion parameters and depth maps were automatically computed from real-world images. Some ground truths were used to validate the accuracy of these results.>

The issue of optimal motion and structure estimation from monocular image sequences with a rigidity scene is addressed. The method has the following characteristics: the dimension of the search space in the nonlinear optimization is drastically reduced by exploiting the relationship between structure and motion parameters; the degree of reliability of the observations and estimates is effectively taken into account; the proposed formulation allows arbitrary interframe motion; and the information about the structure of the scene, acquired from previous images, is systematically integrated into the new estimations. It is shown that any scale factor associated with two consecutive images in a monocular sequence is determined by the scale factor of the first two images. The simulations and experiments with long image sequences of real world scenes indicate that the optimization method developed greatly reduces the computational complexity and substantially improves the motion and structure estimation over that produced by linear algorithms.>

A camera model is presented which accounts for major sources of camera distortion: radial, decentering, and thin-prism distortions. The proposed calibration procedure consists of two steps. In the first step, calibration parameters are estimated using a closed-form solution based on a distortion-free camera model. In the second step, the parameters estimated in the first step are improved iteratively through nonlinear optimization, taking into account camera distortions. According to minimum-variance estimation, the objective function to be minimized is the mean-square discrepancy between the observed image points and their inferred image projections computed with the estimated calibration parameters. A type of measure is introduced which can be used to directly evaluate the performance of the calibration and compare calibrations among different systems. The validity and the performance of the calibration procedure are tested on real images taken by wide-angle lenses. Results consistently show significant improvements over less complete camera models.>

An explicit representation of control called strategy frames is described. The control of several well-known expert systems can be described in terms of strategy frames, although their control is actually encoded in an interpreter. One advantage of strategy frames is that complex control strategies emerge from their interaction, so complex interpreters are not necessary. This idea is illustrated in the context of a process control problem.>

The roles of evaluation in empirical artificial intelligence (AI) research are described, in an idealized cyclic model and in the context of three case studies. The case studies illustrate the pitfalls in evaluation and the contributions of evaluation at all stages of the research cycle. Evaluation methods are contrasted with those of the behavioral sciences, and it is concluded that AI must define and refine its own methods. To this end, several experiment schemas and many specific evaluation criteria are described. Recommendations are offered in the hope of encouraging the development and practice of evaluation methods in AI. The first case study illustrates problems with evaluating knowledge-based systems, specifically a portfolio management expert system called FOLIO. The second study focuses on the relationship between evaluation and the evolution of the GRANT system, specifically, how the evaluations changed as GRANT's knowledge base was sealed up. Third, the cyclic nature of a given research model is examined.>

Choosing an appropriate document representation and search strategy for document retrieval has been largely guided by achieving good average performance instead of optimizing the results for each individual query. A model of retrieval based on plausible inference gives us a different perspective and suggests that techniques should be found for combining multiple sources of evidence (or search strategies) into an overall assessment of a document's relevance, rather than attempting to pick a single strategy. In this paper, we explain our approach to plausible inference for retrieval and describe some preliminary experiments designed to test this approach. The experiments use a spreading activation search to implement the plausible inference process. The results show that significant effectiveness improvements are possible using this approach.