This article focuses on contributions that AI can make to address long-term educational goals. It describes five challenges that would support: (1) mentors for every learner; (2) learning twenty-first century skills; (3) interaction data to support learning; (4) universal access to global classrooms; and (5) lifelong and life-wide learning. A vision and brief research agenda are described for each challenge along with goals that lead to access to global educational resources and the reuse and sharing of digital educational resources. Instructional systems with AI technology are described that currently support richer experiences for learners and supply researchers with new opportunities to analyze vast data sets of instructional behavior from big databases, containing elements of learning, affect, motivation, and social interaction. Personalized learning is described using computational tools that enhance student and group experience, reflection, and analysis, and supply data for development of novel theory development.

Virtual humans are computer-generated characters designed to look and behave like real people. Studies have shown that virtual humans can mimic many of the social effects that one finds in human-human interactions such as creating rapport, and people respond to virtual humans in ways that are similar to how they respond to real people. We believe that virtual humans represent a new metaphor for interacting with computers, one in which working with a computer becomes much like interacting with a person and this can bring social elements to the interaction that are not easily supported with conventional interfaces. We present two systems that embody these ideas. The first, the Twins are virtual docents in the Museum of Science, Boston, designed to engage visitors and raise their awareness and knowledge of science. The second SimCoach, uses an empathetic virtual human to provide veterans and their families with information about PTSD and depression.

In robotics and video games, one often discretizes continuous terrain into a grid with blocked and unblocked grid cells and then uses path-planning algorithms to find a shortest path on the resulting grid graph. This path, however, is typically not a shortest path in the continuous terrain. In this overview article, we discuss a path-planning methodology for quickly finding paths in continuous terrain that are typically shorter than shortest grid paths. Any-angle path-planning algorithms are variants of the heuristic path-planning algorithm A* that find short paths by propagating information along grid edges (like A*, to be fast) without constraining the resulting paths to grid edges (unlike A*, to find short paths).

Intelligent game-based learning environments integrate commercial game technologies with AI methods from intelligent tutoring systems and intelligent narrative technologies. This article introduces the CRYSTAL ISLAND intelligent game-based learning environment, which has been under development in the authors’ laboratory for the past seven years. After presenting CRYSTAL ISLAND, the principal technical problems of intelligent game-based learning environments are discussed: narrative-centered tutorial planning, student affect recognition, student knowledge modeling, and student goal recognition. Solutions to these problems are illustrated with research conducted with the CRYSTAL ISLAND learning environment.

Part Two of the special issue of AI Magazine presents articles on some of the most interesting projects at the intersection of AI and Education. Included are articles on integrated systems such as virtual humans, an intellgent textbook a game-based learning environment as well as technology focused components such as student models and data mining. The issue concludes with an article summarizing the contemporary and emerging challenges at the intersection of AI and education.

A new shrinkage-based construction is developed for a compressible vector $\boldsymbol{x}\in\mathbb{R}^n$, for cases in which the components of $\xv$ are naturally associated with a tree structure. Important examples are when $\xv$ corresponds to the coefficients of a wavelet or block-DCT representation of data. The method we consider in detail, and for which numerical results are presented, is based on increments of a gamma process. However, we demonstrate that the general framework is appropriate for many other types of shrinkage priors, all within the L\'{e}vy process family, with the gamma process a special case. Bayesian inference is carried out by approximating the posterior with samples from an MCMC algorithm, as well as by constructing a heuristic variational approximation to the posterior. We also consider expectation-maximization (EM) for a MAP (point) solution. State-of-the-art results are manifested for compressive sensing and denoising applications, the latter with spiky (non-Gaussian) noise.

In this paper we formulate the nonnegative matrix factorisation (NMF) problem as a maximum likelihood estimation problem for hidden Markov models and propose online expectation-maximisation (EM) algorithms to estimate the NMF and the other unknown static parameters. We also propose a sequential Monte Carlo approximation of our online EM algorithm. We show the performance of the proposed method with two numerical examples.

It is the main goal of this paper to propose a novel method to perform matrix completion on-line. Motivated by a wide variety of applications, ranging from the design of recommender systems to sensor network localization through seismic data reconstruction, we consider the matrix completion problem when entries of the matrix of interest are observed gradually. Precisely, we place ourselves in the situation where the predictive rule should be refined incrementally, rather than recomputed from scratch each time the sample of observed entries increases. The extension of existing matrix completion methods to the sequential prediction context is indeed a major issue in the Big Data era, and yet little addressed in the literature. The algorithm promoted in this article builds upon the Soft Impute approach introduced in Mazumder et al. (2010). The major novelty essentially arises from the use of a randomised technique for both computing and updating the Singular Value Decomposition (SVD) involved in the algorithm. Though of disarming simplicity, the method proposed turns out to be very efficient, while requiring reduced computations. Several numerical experiments based on real datasets illustrating its performance are displayed, together with preliminary results giving it a theoretical basis.

The least absolute shrinkage and selection operator (lasso) and ridge regression produce usually different estimates although input, loss function and parameterization of the penalty are identical. In this paper we look for ridge and lasso models with identical solution set. It turns out, that the lasso model with shrink vector $\lambda$ and a quadratic penalized model with shrink matrix as outer product of $\lambda$ with itself are equivalent, in the sense that they have equal solutions. To achieve this, we have to restrict the estimates to be positive. This doesn't limit the area of application since we can easily decompose every estimate in a positive and negative part. The resulting problem can be solved with a non negative least square algorithm. Beside this quadratic penalized model, an augmented regression model with positive bounded estimates is developed which is also equivalent to the lasso model, but is probably faster to solve.

A recently proposed methodology called the Horizontal Visibility Graph (HVG) [Luque {\it et al.}, Phys. Rev. E., 80, 046103 (2009)] that constitutes a geometrical simplification of the well known Visibility Graph algorithm [Lacasa {\it et al.\/}, Proc. Natl. Sci. U.S.A. 105, 4972 (2008)], has been used to study the distinction between deterministic and stochastic components in time series [L. Lacasa and R. Toral, Phys. Rev. E., 82, 036120 (2010)]. Specifically, the authors propose that the node degree distribution of these processes follows an exponential functional of the form $P(\kappa)\sim \exp(-\lambda~\kappa)$, in which $\kappa$ is the node degree and $\lambda$ is a positive parameter able to distinguish between deterministic (chaotic) and stochastic (uncorrelated and correlated) dynamics. In this work, we investigate the characteristics of the node degree distributions constructed by using HVG, for time series corresponding to $28$ chaotic maps and $3$ different stochastic processes. We thoroughly study the methodology proposed by Lacasa and Toral finding several cases for which their hypothesis is not valid. We propose a methodology that uses the HVG together with Information Theory quantifiers. An extensive and careful analysis of the node degree distributions obtained by applying HVG allow us to conclude that the Fisher-Shannon information plane is a remarkable tool able to graphically represent the different nature, deterministic or stochastic, of the systems under study.