Sridhar Mahadevan - US grants

The aim of the proposed research is to study how autonomous agents can adapt to dynamic partially known task environments. Potential applications of such agents range from hardware robots that automate delivery chores to software programs that retrieve information from the Internet. This research will focus on an adaptive control paradigm called reinforcement learning. In this approach, agents acquire task skills through trial and error by selecting actions that maximize a reward function.Reinforcement learning has some problems. It converges extremely slowly, especially in large state space problems where rewards occur infrequently. Also, the learned skills transfer poorly across related tasks. This research will investigate using a novel modular task architecture to overcome these limitations of reinforcement learning. The proposed architecture decomposes composite multiple goal tasks into primitive subtasks that achieve each individual goal. It utilizes training time more efficiently by dynamically switching between learning different tasks based on their difficulty and importance. It increases transfer across tasks by reusing solutions learned to primitive subtasks using a weighted linear sum function. It solves recurrent tasks more effectively by using a reinforcement learning method that optimizes average reward. A detailed experimental study of the proposed architecture will be undertaken, using a variety of simulated and real robot testbeds.

IRI-9529108 Mahadevan, Sridhar University of South Florida $29,550 - 12 mos. Support for a Workshop on Reinforcement Learning This is support for a workshop that will bring together researchers in one of the most actively studied paradigms in the study of human and machine learning, reinforcement learning (RL). A three-day meeting of up to 30 leading researchers from a variety of fields, including machine learning, neural networks, artificial intelligence, robotics, and operations research, will attend the meeting. The goals of the meeting include (1) Understanding limitations of current RL systems, and defining promising directions for further research; (2) Clarifying the relationships between RL and existing work in fields such as operations research; (3) Identifying potential industrial applications of RL research. A 10-15 page report on the findings of the workshop will be produced, along with a summary suitable for WWW posting. It is intended also to discuss the establishment of an electronic newsgroup to facilitate communication among disparate groups working in RL-related areas.

9873531
Henderson
Mobile organisms make accurate behavioral decisions with extraordinary speed and flexibility in real-world environments despite incomplete knowledge about the state of the world and the effects of their actions. This ability must be shared by artificial agents such as mobile robots if they are to operate flexibly in similar environments. The main goal of the research is to undertake a detailed interdisciplinary study of sequential decision making across animals and robots, with a focus on real time learning and control of information gathering and navigational behaviors.

The project will take a comparative approach, combining psychophysical and cognitive research techniques from the study of human eye movement control, behavioral research techniques from the study of insect navigation, and computational methods from the study of mobile robots. All of these systems provide experimentally tractable test-beds for studying real-time decision making in partially observable environments.

The research is guided by a class of sequential decision making models called Markov decision processes (MDP). These models are attractive because they provide a formal framework for computing optimal behavior in uncertain environments. However, these models do not fully capture the complexity of decision making in organisms. We will explore extensions of the MDP framework using insights gained from the study of behavior in organisms and algorithms in artificial agents. This synergy will lead both to a better theoretical understanding of sequential decision making in biological organisms, and to the development of efficient algorithms for artificial agents.

A major outcome of the project will be to show how the design of artificial creatures (robots) can be guided by, and serve as a guide for, the study of sequential behavior in animals. Understanding the challenges that robot designers face, and the formal framework that they have developed to tackle these challenges, leads to novel questions about organisms behavior. Similarly, insights gained from organisms will help suggest ways for improving algorithms for building intelligent artificial agents.
***

This IGERT project examines the problem of sequential decision-making as a unifying framework for the study of several central topics in cognitive science: selective attention, navigation, language processing, and the coordination of action in multiple-agent groups. The overarching question our students are trained to investigate is the following: how is it possible for an agent to decide what actions to take to achieve long-term goals? We recognize that decision-making in complex environments is a sequential process, involving a series of episodes in which an agent, based on information available through its senses and stored in memory, selects the action appropriate for its goals. The problem is made difficult by perceptual uncertainty arising from sensory limitations and environmental complexity, by the challenge of sorting through the large space of actions available, and by inherent delays in feedback about the long-term consequences of actions. A wide variety of fundamental cognitive tasks can be cast as sequential decision-making problems. Understanding how such problems may be solved will be a critical component of a general theory of intelligent behavior in organisms, and will be essential for the design of truly intelligent machines. To study these problems, we adopt a comparative approach, combining insights from a range of model systems, including humans, non-human animals, robots, and intelligent software agents. This multidisciplinary framework will enable students to integrate ideas and methods from different fields that have been concerned with the study of sequential decision-making (psychology, behavioral biology, linguistics, and computer science), but that have so far remained largely separate. The training program is designed to create a new generation of scientists trained in this innovative, multidisciplinary approach. Graduate training will be focused on fundamental disciplinary education, a common set of courses focused on the sequential decision-making framework, and a strong emphasis on mentored, interdisciplinary research activities that span each student's entire graduate program.

IGERT is an NSF-wide program intended to meet the challenges of educating Ph.D. scientists and engineers with the multidisciplinary backgrounds and the technical, professional, and personal skills needed for the career demands of the future. The program is intended to catalyze a cultural change in graduate education by establishing new, innovative models for graduate education and training in a fertile environment for collaborative research that transcends traditional disciplinary boundaries. In the fourth year of the program, awards are being made to twenty-two institutions for programs that collectively span all areas of science and engineering supported by NSF. The intellectual foci of this specific award reside in the Directorates for Social, Behavioral, and Economic Sciences; Computer and Information Science and Engineering; Engineering; Biological Sciences; and Education and Human Resources.

This project investigates reinforcement learning algorithms that use dynamic abstraction to exploit the spatial and temporal structure of complex environments to facilitate learning. The use of abstraction is one of the features of human intelligence that allows us to operate as effectively as we do in complex environments. We systematically ignore details that are not relevant to a task at hand, and we rapidly switch between abstractions when we focus on a succession of subtasks. For example, in planning everyday activities, such as driving to work, we abstract out irrelevant details such as the layout of objects inside the car, but when we actually drive, many of these details become relevant, such as the locations of the steering wheel and the accelerator. Different abstractions are appropriate for different tasks or subtasks, and the agent has to shift abstractions as it shifts to new tasks or to new subtasks.
This project combines the theory of options with factored state and action representations to give precise meaning to the concept of dynamic abstractions and to study methods for creating and exploiting them. It will develop formalisms for representing option models in terms of factored state and action representations by extending existing formalisms for single-step dynamic Bayes network models to the multi-time case. It will investigate how the multi-time formulation call facilitate creating and using dynamic abstractions. An algebraic theory of abstraction will be developed by extending relevant concepts from classical automata theory to multi-time factored models. Methods will be developed for learning compact multistep option models by extending an existing mixture model algorithm for learning transition models from single-step to multi-step models. In general the notion of dynamic abstraction will be a valuable tool to apply to many difficult optimization problems in large-scale manufacturing (e.g., factory process control), robotics (navigation), multi-agent coordination, and other state-of-the-art applications of reinforcement learning. Since this research combines ideas from the fields of decision theory, operations research, control theory, cognitive science, and AI, it may provide a useful bridge that has the potential to foster contributions in all of these fields.

The primary objective of this project is to develop new methods for optimizing an automated pedagogical agent to improve its teaching efficiency through customization to individual students based on information about their responses to individual problems, student individual differences such as level of cognitive development, spatial ability, memory retrieval speed, long-term retention, effectiveness of alternative teaching strategies (such as visual vs. computational solution strategies), and degree of engagement with the tutor. An emphasis will be placed on using machine learning and computational optimization methods to automate the process of developing efficient Intelligent Tutoring Systems (ITS) for new subject domains. The approach is threefold.
First, a methodology based on hierarchical graphical models and machine learning will be developed and evaluated for automating the creation of student models with rich representations of student state based on data collected from populations of students over multiple tutoring episodes. Second, methods will be developed and evaluated for deriving pedagogical decision strategies that are effective and efficient not just over the short-term (from one math problem to the next one), but over the long-term where retention over a period of at least one month is the objective. Third, a systematic study will be conducted of the role that known and powerful latent and instructional variables can have on performance through their inclusion in student models. Research in cognitive and educational psychology clearly shows the critical role that latent variables such as short-term memory and engagement play in learning, and that instructional variables such as over-learning and review, and massed and distributed practice have on the rate at which material is learned. The investigators jointly have strengths in the areas of intelligent tutoring, machine learning and optimization, and cognitive, mathematical and educational psychology, strengths that are needed in order to make the synergistic advances that are being proposed. Our preliminary simulations and classroom experiments suggest that we can significantly reduce the time it takes students to learn new material based on improved pedagogical decisions.
For intellectual merit, he proposed research should advance fundamental knowledge of the learning and teaching of basic mathematics and more advanced algebra and geometry. It should add to the set of growing statistical and computational techniques that are available to estimate the complex hidden hierarchical structures that govern human behavior. The research should also significantly broaden the capabilities of machine learning systems by addressing learning scenarios that are grounded on the real and challenging problem of mathematics education than the abstract scenarios typically studied at present. For broader impact, this foundational educational research will lead to the broadening of participation of underrepresented groups, especially women, in a variety of science, technology, engineering and mathematics (STEM) disciplines. It will advance discovery and understanding of learning and engagement as predictors of individual differences in learning and will result in intelligent tutors that are more sensitive to individual differences. It will unveil the extent to which students of different genders and cognitive abilities learn more efficiently with different forms of teaching. This research will benefit society as machine learning methods, which provide a core technology for building complex systems, will be applicable to a variety of teaching systems.

This project addresses a longstanding puzzle in artificial intelligence (AI): how can agents transform their temporal experience into multiscale task-independent representations that can effectively guide long-term task-specific behavior? The project will investigate a nonparametric framework combining task-independent learning with task-specific learning. Algorithmically, the framework comprises of four phases. Initially, agents learn a discrete manifold representation of a given environment, which can be viewed as a topological graph representing the states reachable through single or multi-step actions. Next, the graph is analyzed using spectral clustering techniques to reveal "bottlenecks," symmetries, and other geometric invariants. In the third phase, an orthonormal set of task-independent basis functions called proto-value functions are extracted from the environment's topology: These basis functions capture large-scale geometric invariants that all value functions on the state space must adhere to. In the final phase, proto-value functions are combined with rewards to approximate task-specific value functions.

The proposed framework unifies two previously disparate lines of research in AI: learning of behavior using value functions, pioneered by Arthur Samuel, and the learning of representations based on global state space analysis, pioneered by Saul Amarel. The theoretical basis for the framework draws upon links between discrete and continuous mathematics: Riemannian manifolds and the spectral theory of graphs; elliptic differential equations and abstract harmonic analysis on graphs. Specifically, the Hilbert space of smooth functions on a Riemannian manifold has a discrete spectrum based on the eigenfunctions of the Laplace-Beltrami operator. The applications of this theory to Markov decision processes will be explored, in particular the ability of Laplacian eigenfunctions or proto-value functions to both capture large-scale geometric structure and as well as approximate task-specific value functions. A novel class of algorithms termed Representation Policy Iteration (RPI) will be investigated, which interleave representation learning and behavior learning. The research thus also addresses a longstanding question not resolved in much previous work on approximation methods for solving large Markov decision processes: how can basis functions be generated automatically? The research will investigate the scalability of the proposed framework to larger problems, including both discrete factored state spaces as well as continuous state spaces. The testbeds include simulated discrete and continuous benchmark problems, simulated and real robot testbeds, and an information extraction task of maintaining the Reinforcement Learning Repository (RLR), the world's largest collection of documents and data relating to reinforcement learning.

Broader impacts of this project include algorithmic and theoretical insights leading to a unified approach to learning behavior and representation, as well as applications to real-world problems such as humanoid robotics and web repository maintenance. Additionally, this project will give valuable research experience to women graduate students and to undergraduate students from local four year colleges.

This project exercises and expands upon methods for automatic discovery of new representations at multiple temporal and spatial scales. The specific framework generalizes classical harmonic analysis, in particular wavelet-based methods, to graphs and manifolds, thereby greatly extending the scope and the desirable characteristics of this multiscale-analysis framework to domains with arbitrary geometries. This framework, termed diffusion wavelets because it is associated with a diffusion process that defines the different scales, has unique properties relevant to learning, function approximation, compression and denoising. The set of core problems that this project addresses include fast algorithms for construction of multiscale diffusion wavelets, approximation of functions on very large graphs and high-dimensional manifolds, out-of-sample extensions of functions on manifolds and graphs, compression and denoising of functions on data sets, perturbation analysis, and randomized algorithms for multiscale analysis. Challenging application domains are being investigated, including analysis of document corpora, Markov decision processes, and 3D image rendering. In each case, multiscale diffusion analysis yields interpretable and meaningful results. For example, when applied to Markov decision processes, diffusion wavelet analysis yields new optimization methods that dynamically aggregate states and actions at multiple levels of abstraction; and when applied to 3D computer graphics, it yields new compression methods that capture geometric features of objects at multiple resolutions.

As the availability and size of digital information repositories continues to burgeon, the problem of extracting deep semantic structure from high-dimensional data becomes more critical. This project addresses the fundamental problem of transfer learning, in particular it investigates methods for aligning multiple heterogeneous data sets to find correspondences and extract shared latent semantic structure. Domains of applicability include automatic machine translation, bioinformatics, cross-lingual information retrieval, perceptual learning, robotic control, and sensor-based activity modeling. The proposed research will investigate a geometric framework for transfer learning based on finding correspondences between data by aligning their projections onto lower dimensional manifolds. The proposed research will investigate a broad spectrum of approaches to manifold alignment, including one-step vs. two-step alignment, instance-based vs. feature-based alignment, semi-supervised vs. unsupervised alignment, and finally one-level vs. multi-scale alignment. Visualization tools that use alignment information will be developed to facilitate interactive learning from data analysis. To aid the processing of large data sets, the parallel computational power of modern graphics processing units (GPUs) will be exploited.

Given the rapidly increasing availability of digital data sets from a diverse variety of domains, the scientific question of extracting knowledge from massive unstructured information repositories is becoming ever more critical. The proposed research combines the study of machine learning algorithms for discovering latent correspondences between seemingly disparate data sets, and the development of visualization tools to aid human interpretation of high-dimensional data. Empirical studies on a variety of real-world applications will be carried out, ranging from bioinformatics, Internet web archives, multilingual text, and sequential time-series data sets. The broader impacts of the proposed research include algorithmic advances in the analysis and visualization of high-dimensional data, and empirical studies on a variety of real-world applications. The data sets and software developed in this research will be disseminated through the web. The research will be communicated through a variety of conferences, workshops and seminars in several disciplines ranging from computer science, engineering, mathematics, and statistics. The PIs will make significant efforts to recruit underrepresented groups, including women and other minorities, in this research. New course material on advanced data analysis and visualization will be developed based on the proposed research.

Since the development of its earliest technical foundations more than 40 years ago, the Internet?s dominant communication paradigm has been packet-based, host-to-host communication. However, as the Internet has matured and increasingly more applications have been developed on top of this communication abstraction, there is a growing realization that many user applications are primarily concerned with accessing content rather than communicating with a specific host. In this content-centric view, emphasis is placed on what is obtained rather than from where it is obtained, and content search, dissemination (routing), and storage are consequently of increased importance. Indeed, several 'clean slate' approaches towards Internet architecture have emphasized in-network content naming, search, routing, and storage (including in-network caching ) as key architectural components of a next-generation Internet architecture.

Intellectual Merit. This project undertakes fundamental research on developing the modeling and performance evaluation tools/methodologies, and on designing and evaluating approaches for a key architectural element of these content-centric network architectures - dynamic, demand-driven, in-network, content caching. This effort will develop bounding deterministic performance models of caching networks based on a -characterization of content request streams, probabilistic bounds performance using stochastic bounding techniques, and approximate performance models for networks of caches based on reduced-load approximation techniques. The research will also investigate several simple best-effort algorithms for content-caching and content-location; here, the focus will be on the underlying approaches themselves rather than their embodiment in any particular content-centric network architecture.

Broader Impact. The modeling and analysis of in-network caching - a component of many content-centric next generation network architectures - will provide tools and techniques for analyzing such networks in much the same way that network calculi and reduced-load approximations have served as foundations for bounding and approximate analyses of complex queueing and blocking networks that have been used to model a wide range of packet-switched and circuit-switched networks and their protocols. The project's investigation of specific simple, 'best effort' content-caching and content-location algorithms is based on the belief that just as a best-effort Internet service model has proven to be 'good enough' compared with more sophisticated network architectures, best-effort caching may similarly prove 'good enough' when compared to more stateful and more complex request routing and cache-content management approaches. This would be a lesson with far-reaching impact. Graduate research assistants and undergraduate REU students will be mentored as part of this project, helping to educate the next generation of networking researchers. Involvement of minority graduate students will be coordinated through the Northeast Alliance for Graduate Education and the Professoriate (NEAGEP). Research results will be adopted into a widely-disseminated graduate networking course taught at the University of Massachusetts.

A fundamental challenge in machine learning is the design of computational agents that, rather than being explicitly programmed, autonomously learn complex tasks in stochastic real-world environments. Past approaches, such as reinforcement learning algorithms for solving Markov decision processes, scale poorly to large state spaces. The proposed research addresses this curse of dimensionality by investigating a novel framework combining reinforcement learning and online convex optimization, in particular mirror descent and related algorithms. Mirror descent scales significantly better than classical first-order gradient descent in high-dimensional state spaces, by using a distance-generating function specific to a particular state space geometry.

The proposed framework enables several significant algorithmic advances in the design of autonomous machine learning agents: a new class of first-order mirror-descent based methods for learning sparse solutions to Markov decision processes will be developed that scale significantly significantly better than previous second-order methods; novel hierarchical methods for solving semi-Markov decision processes will be investigated; and finally, applications to a variety of high-dimensional Markov decision processes will be explored.

The anticipated outcomes of the proposed work include foundational advances in designing autonomous agents that learn to solve sequential decision-making problems, which will impact a large number of target applications from manufacturing to robotics and scheduling. The educational goal includes the development of a graduate-level course in online convex optimization for sequential decision-making, as well as interdisciplinary tutorials to enhance the cross-fertilization of ideas from applied mathematics and optimization to machine learning and artificial intelligence.

With support from the Chemical Measurements and Imaging program, Professors Melinda Dyar of Mt. Holyoke College and Sridhar Mahadevan of University of Massachusetts at Amherst and their students will use laser-induced breakdown spectroscopy (LIBS) measurements, including laboratory investigations of standard materials at varying experimental conditions, to develop numerical methods that will address limitations to the broad application of LIBS imposed by matrix effects and plasma variability. State-of-the-art dimensionality reduction and transfer learning methods from machine learning and statistics will be used to build innovative LIBS-based predictive models. These investigations will extend classical methods in statistics for dealing with multiple paired data sets, such as canonical correlational analysis, to deal with unlabeled data, and extract nonlinear low-dimensional regularities in the data. The project includes the design of a suite of model-building tools that can deal with a range of problems and optimization objectives, including different types of correspondence information available across datasets, diversity of global objectives ranging from preserving local to global geometry, and producing linear or nonlinear mappings to lower-dimensional factors.

Laser-induced breakdown spectroscopy (LIBS) is a chemical analysis tool that uses the light emitted by a sample when a focused laser pulse generates a plasma at the sample surface. LIBS has a number of features that make it particularly useful for field use, including rapid analysis, minimal sample preparation and suitability for stand-off, that is remote, detection. Moreover, LIBS can detect and quantify light elements that are not always measured using other methods. Consequently, LIBS is well-suited to many applications including, defense interests (e.g., military explosive detection, illegal drug detection, airport security), in-situ analysis of archeological sites, field work at hazardous waste sites, and geological resource exploration. However, utilization of LIBS measurements is limited by signal variability with measurement and sample conditions. This project launches an integrated research program to couple state of the art LIBS instrumentation at Mount Holyoke College to equally state of the art numerical methodology in artificial intelligence and machine learning at the nearby University of Massachusetts to increase the utility of LIBS measurements. This project will provide an interdisciplinary training environment that includes undergraduate, graduate and post-doctoral researchers.

Many problems in science today require the analysis of massive datasets.
This project investigates the fundamental problem of extracting latent hidden regularities from high-dimensional scientific data sets, specifically from two different types of spectroscopic measurements -- three-dimensional hyperspectral imaging used in remote sensing of the Earth and other planets, and one-dimensional spectral signals arising from chemical analyses from laser-induced breakdown spectroscopy (LIBS), such as used currently by the Curiosity rover on Mars. The project is applying recent advances in deep learning, optimization, and machine learning to practical real-world scientific applications involving the analysis of materials from Earth and outer space, such as Mars, as well as the mapping of Martian and terrestrial surfaces through hyperspectral imagery.

Deep learning uses multi-layer neural networks to construct a hierarchy of latent representations of high-dimensional datasets. This project designs novel architectures and algorithms for deep learning, and applies them to spectroscopic domains, such as LIBS and hyperspectral imaging. Three challenges from spectroscopic domains guide the research. First, in many applications such as the Curiosity rover on Mars, the number of available LIBS spectra are limited as it requires an active sensing operation followed by transmission of data by a robot situated millions of miles from Earth. A further challenge is that data from Mars is inherently unlabeled, and instrumental variations and terrain variations between Earth and Mars require solving a key transfer learning problem. For hyperspectral imaging, the project is extending work on deep learning applied to two-dimensional images to data that involves two spatial dimensions as well as the third spectral dimension, where images are recorded at multiple wavelengths. This project explores a variety of ways of designing new convolutional neural networks and other approaches that can effectively exploit the third spectral dimension.