Provost, Jefferson, Benjamin J. Kuipers, and Risto Miikkulainen. "Self-Organizing Distinctive-State Abstraction For Learning Robot Navigation." The University of Texas at Austin, Department of Computer Sciences. AI Technical Report 05-319. July 21, 2005. 10 pages.
A major challenge in reinforcement learning research is to extend methods that have worked well on discrete, shortrange, low-dimensional problems to continuous, high-diameter, high-dimensional problems, such as robot navigation using high-resolution sensors. Self-Organizing Distinctive-state Abstraction (SODA) is a new, generic method by which a robot in a continuous world can better learn to navigate by learning a set of high-level features and building temporally-extended actions to carry it between distinctive states based on those features. A SODA agent first uses a self-organizing feature map to develop a set of high-level perceptual features while exploring the environment with primitive, local actions. The agent then builds a set of high-level actions composed of generic trajectory-following and hill-climbing control laws that carry it between the states at local maxima of feature activations. In an experiment on a simulated robot navigation task, the SODA agent learns to perform a task requiring 300 small-scale, local actions using as few as 9 new, temporally-extended actions, significantly improving learning time over navigating with the local actions.
Whiteson, Shimon and Peter Stone. "Evolutionary Function Approximation for Reinforcement Learning." The University of Texas at Austin, Department of Computer Sciences. AI Technical Report 05-320. July 21, 2005. 33 pages.
Temporal difference methods are theoretically grounded and empirically effective methods for addressing sequential decision making problems with delayed rewards. Most problems of real-world interest require coupling TD methods with a function approximator to represent the value function. However, using function approximators requires manually making crucial representational decisions. This paper introduces evolutionary function approximation, a novel approach to automatically selecting function approximator representations that enable efficient individual learning. Our method evolves individuals that are better able to learn. We present a fully implemented instantiation of evolutionary function approximation which combines NEAT, a neuroevolutionary optimization technique, with Q-learning and Sarsa, two popular TD methods. The resulting NEAT+Q and NEAT+Sarsa algorithms automatically learn effective representations for neural network function approximators. This paper also introduces on-line evolution, which improves the on-line performance of evolutionary computation by borrowing selection mechanisms used in TD methods to choose individual actions and using them in evolution to select policies for evaluation. We evaluate our contributions with an extended empirical study in the autonomic computing domain of server job scheduling. The results demonstrate that evolutionary function approximation can substantially improve the performance of TD methods and on-line evolution can significantly improve evolutionary methods. This paper also presents additional tests that offer insight into what factors can make function approximation difficult in practice.
Kaczmarczyk, Lisa C. "The Acquisition of Intellectual Expertise: A Computational and Empirical Theory." The University of Texas at Austin, Department of Computer Sciences. AI Technical Report 05-321. August 4, 2005. 115 pages.
In order to develop intellectual expertise, a novice learner has to acquire cognitive abilities seen in experts: They need to be able to categorize problems before solving them, and be meta-cognitive about their learning, so that they can select the best problem-solving strategies. The process by which learners acquire these abilities is not well understood. The goal of this dissertation is to understand how instructional delivery methods can help learners acquire the cognitive abilities necessary to become experts. The study was motivated by initial structured interviews with mathematics faculty, which led to the formulation of three hypotheses: (1) Traditional sequential delivery methods inhibit learning and retention; (2) Integrated delivery methods increase learning and retention; (3) Incrementally increasing the complexity of the material will lead to the best performance. An artificial neural network was then used to test these hypotheses computationally. The network confirmed the hypotheses, demonstr ating that an Incremental delivery leads to better learning than Drill and Test learning or Fully Integrated learning. These computational conclusions led to the prediction that an Incremental Learning delivery method will encourage meta-cognitive abilities necessary to achieve expertise. This prediction was tested experimentally on human subjects. Qualitative and quantitative data from the human study verified that (1) Incremental learners develop the most effective study and test taking strategies; (2) Incremental learners have the best conceptual development; and (3) Incremental learners have the most positive reactions to learning. I hope that these results will benefit society, because by changing the way we educate students, more learners can pursue advanced study, and use their expert, creative insights to address society's most challenging problems.
D'Silva, Thomas. "Neuroevolution of a Robot Arm Controller." The University of Texas at Austin, Department of Computer Sciences. AI Technical Report 05-322. October 3, 2005. 6 pages.
Arm movements at stationary or moving targets are common in the motor repertoire of humans, but little is known on how the brain uses spatiovisual information concerning the locations of targets for the generation of arm movements and how it controls the different neural and muscular structures involved during the formation of arm trajectories. Newborn babies possess biological networks that are initally capable of performing only reflex actions. As infants learn about their surroundings and begin to comprehend their senses, their biological networks complexify allowing them to perform more intelligent motor control tasks. Using neuroevolution it is possible to evolve networks that can simulate infant motor development. Neuroevolution was used to evolve controllers for a simulated robot arm that can position the armÕs end-effector close to a stationary target and track moving targets.
Wong, Yuk Wah. "Learning for Semantic Parsing Using Statistical Machine Translation Techniques." The University of Texas at Austin, Department of Computer Sciences. AI Technical Report 05-323. October 18, 2005. 53 pages.
Semantic parsing is the construction of a complete, formal, symbolic meaning representation of a sentence. While it is crucial to natural language understanding, the problem of semantic parsing has received relatively little attention from the machine learning community. Recent work on natural language understanding has mainly focused on shallow semantic analysis, such as word-sense disambiguation and semantic role labeling. Semantic parsing, on the other hand, involves deep semantic analysis in which word senses, semantic roles and other components are combined to produce useful meaning representations for a particular application domain (e.g. database query). Prior research in machine learning for semantic parsing is mainly based on inductive logic programming or deterministic parsing, which lack some of the robustness that characterizes statistical learning. Existing statistical approaches to semantic parsing, however, are mostly concerned with relatively simple application domains in which a meaning r epresentation is no more than a single semantic frame. In this proposal, we present a novel statistical approach to semantic parsing, WASP, which can handle meaning representations with a nested structure. The WASP algorithm learns a semantic parser given a set of sentences annotated with their correct meaning representations. The parsing model is based on the synchronous context-free grammar, where each rule maps a natural-language substring to its meaning representation. The main innovation of the algorithm is its use of state-of-the-art statistical machine translation techniques. A statistical word alignment model is used for lexical acquisition, and the parsing model itself can be seen as an instance of a syntax-based translation model. In initial evaluation on several real-world data sets, we show that WASP performs favorably in terms of both accuracy and coverage compared to existing learning methods requiring similar amount of supervision, and shows better robustness to variations in task complexity and word order. In future work, we intend to pursue several directions in developing accurate semantic parsers for a variety of application domains. This will involve exploiting prior knowledge about the natural-language syntax and the application domain. We also plan to construct a syntax-aware word-based alignment model for lexical acquisition. Finally, we will generalize the learning algorithm to handle context-dependent sentences and accept noisy training data.
Karpov, Igor V., Thomas D'Silva, Craig Varrichio, Kenneth O. Stanley, and Risto Miikkulainen. "Integration and Evaluation of Exploration-Based Learning in Games." The University of Texas at Austin, Department of Computer Sciences. AI Technical Report 05-324. . 6 pages.
Video and computer games provide a rich platform for testing adaptive decision systems such as value-based reinforcement learning and neuroevolution. However, integrating such systems into the game environment and evaluating their performance in it is time and labor intensive. In this paper, an approach is developed for using general integration and evaluation software to alleviate these problems. In particular, the Testbed for Integrating and Evaluating Learning Techniques (TIELT: Aha & Molineaux (2004)) is used to integrate a neuroevolution learner with an off-the-shelf computer game Unreal Tournament(TM). The resulting system is successfully used to evolve an artificial neural network controller with basic navigation behavior. These results lead to formulating a set of requirements that make a general integration and evaluation system such as TIELT a useful tool for benchmarking adaptive decision systems.
Stone, Peter, Kurt Dresner, Peggy Fidelman, Nate Kohl, Gregory Kuhlmann, Mohan Sridharan, and Daniel Stronger. "The UT Austin Villa 2005 RoboCup Four-Legged Team." The University of Texas at Austin, Department of Computer Sciences. AI Technical Report 05-325. November 11, 2005. 14 pages.
The UT Austin Villa Four-Legged Team for RoboCup 2005 was a third-time entry in the ongoing series of RoboCup legged league competitions. The team development began in mid-January of 2003 without any prior familiarity with the Aibos. After entering a fairly non-competitive team in RoboCup 2003, the team made several important advances. By the July 2004 competition that took place in Lisbon, Portugal, it was one of the top few teams. After those first two years of intense development, the team's third year was devoted more to spinoff research than to development related to the competition. Building off of the team's previous two technical reports, this report details the changes made to the team between RoboCup 2004 and RoboCup 2005 in Osaka. Taken together, this and the previous technical reports provide the history and details of a relatively young RoboCup team that has quickly grown from a nascent project to an ongoing source of diverse and plentiful research results while becoming a highly-seeded team in competitions.
Kate, Rohit J. "A Kernel-based Approach to Learning Semantic Parsers." The University of Texas at Austin, Department of Computer Sciences. AI Technical Report 05-326. November 22, 2005. 34 pages.
Semantic parsing involves deep semantic analysis that maps natural language sentences to their formal executable meaning representations. This is a challenging problem and is critical for developing user-friendly natural language interfaces to computing systems. Most of the research in natural language understanding, however, has mainly focused on shallow semantic analysis like case-role analysis or word sense disambiguation. The existing work in semantic parsing either lack the robustness of statistical methods or are applicable only to simple domains where semantic analysis is equivalent to filling a single semantic frame. In this proposal, we present a new approach to semantic parsing based on string-kernel-based classification. Our system takes natural language sentences paired with their formal meaning representations as training data. For every production in the formal language grammar, a Support-Vector Machine (SVM) classifier is trained using string similarity as the kernel. Each classifier then gives the probability of the production covering any given natural language string of words. These classifiers are further refined using EM-type iterations based on their performance on the training data. Meaning representations for novel natural language sentences are obtained by finding the most probable semantic parse using these classifiers. Our experiments on two real-world data sets that have deep meaning representations show that this approach compares favorably to other existing systems in terms of accuracy and coverage. For future work, we propose to extend this approach so that it will also exploit the knowledge of natural language syntax by using the existing syntactic parsers. We also intend to broaden the scope of application domains, for example, domains where the sentences are noisy as typical in speech, or domains where corpora available for training do not have natural language sentences aligned with their unique meaning representations. We aim to test our system on the task of complex relation extraction as well. Finally, we also plan to investigate ways to combine our semantic parser with some recently developed semantic parsers to form committees in order to get the best overall performance.
Questions to trcenter@cs.utexas.edu