Torby's Blog

Incremental exploration

2012-02-15T01:51:00.001-08:00

Learn from demonstration typically means learning from training data that are in the form of a relatively small number of complex sequences of observations and potentially actions. The strength of this learning paradigm is that the data provided is related to the crucial areas of the problem space. In the case of reinforcement learning, this would involve the key reward states and effective paths to these states from relevant starting states. However, due to the restricted part of a problem space that can be covered using this form of learning, it typically leads to brittle behaviours that are not able to compensate for perturbations that place the robot outside the known area. One solution to this problem is to use the training data to learn a policy that generalises across large areas of the problem space, such as the Nonlinear Dynamical Systems presented by Ijspeert et al. [3]. Another approach is to hard code a mechanism for returing to the known area such as the extension to Gaussian Mixture Models presented by Calinon [2]. Abbeel and Ng [1], argued, from their experience in the domain of autonomous helicopter control, that an explicit exploration policy is not required in order to improve performance up to or beyond that of the teacher. Instead, the natural perturbations would provide sufficient exploration.

Bill Smart and Leslie Kaelbling [5] developed the JAQL (Joystick and Q-learning?) algorithm to overcome this problem. The JAQL algorithms has two different learning phases. In the first phase, the robot is driven through the "interesting" parts of the problem space by a hand coded controller or by a human controller using a joystick. In the second phase, the policy learned was in control and responsible for further exploration, running in a more standard reinforcement learning mode. The JAQL algorithm has an explicit exploration policy designed to work with policies learnt from demonstration.

The JAQL exploration policy creates slight deviations from the greedy action by adding a small amount of Gaussian noise [4]. This policy creates actions that are "similar to, but different from", the greedy action.

Our RLSOM algorithm has so far been applied only to learning by demonstration, but should be capable of handling learning from exploration without other modifications that a reasonable exploration policy. This is one of the most exciting direction in which to take our research.

[1] Pieter Abbeel and Andrew Y. Ng, Exploration and apprenticeship learning in reinforcement learning. In the Proceedings of the 22nd International Conference on Machine Learning (ICML'05), pp1-8, August 7-11, Bonn, Germany, 2005.

[2] Sylvain Calinon, Robot Programming by Demonstration: A Probabilistic Approach. EPFL/CRC Press, 2009.

[3] Auke J. Ijspeert, Jun Nakanishi and Stefan Schaal, Movement imitation with nonlinear dynamical systems in humanoid robots. In the Proceedings of the International Conference on Robotics and Automation (ICRA'02), pp1398-1403, May 11 - 15, Washington, DC, 2002.

[4] William D. Smart, Making Reinforcement Learning Work on Real Robots. Ph.D. thesis, Department of Computer Science, Brown University, 2002.

[5] William D. Smart and Leslie Pack Kaelbling, Reinforcement Learning for Robot Control. In Mobile Robots XVI (Proceedings of the SPIE 4573), pp92-103, Douglas W. Gage and Howie M. Choset (eds.), Boston, Massachusetts, 2001.

Dimensions of cognition

2012-02-05T05:39:00.001-08:00

There is a history, in the science of AI and its related fields, to simplify problems to an extent where the solutions no longer contributed to our knowledge of cognition.

Three examples are symbolic problem solving, Computer Vision and Speech Recognition. While each of these areas have produced valuable technologies, in their own right, they have also, by narrowing their focus, removed themselves so far from the problems faced by animals, including humans, that their solutions have not provided major breakthroughs in our understanding of cognitive systems. One cannot criticize this work for simplifying and narrowing their studies, as this is a necessary part of developing working solutions to given problems. The specificity of their solutions however, raises the question of whether it is possible to develop systems that both solve a specific problem and also provide key insights into cognition. Cognition is, arguably, the ability to apply a general understanding of the world to new problems and situations, and, if so, cognition is the ability to generalize rather than specialize.

A generalist approach to modelling cognition raises two fundamental questions:

Generalize across what?
What kind of problems can provide tractable challenges for generalist cognitive systems?

By challenges being tractable we mean that it is possible to imagine solutions based on the incremental development or integration of existing technologies. There are many examples of interesting but intractable challenges for generalist cognitive systems. Most challenges requiring human-like cognitive abilities such as autonomous robot workers or companions are clearly still intractable, but many challenges which have, arguably, lower cognitive requirements, e.g., robotic sheep dogs, guard dogs, steeds or even pack animals, also look intractable w.r.t. many of the sub-problems they contain.

Beyond finding tractable challenges it is also interesting to consider whether we can identify a sequence of challenges that could form milestones along a path of increasingly high levels of generalist cognitive abilities. Following from the second question, we can also ask whether any such problems would be practical, by which we mean that solving them would provide a technology that could be useful to society.

Looking for dimensions of cognition, Stephen Mithen, in his book The prehistory of the mind, 1996, suggests a number of specialized intelligences that act as a foundation, or 'chapels' around an initial general intelligence. On top of these chapels, the 'superchapel' of meta-representation is then built, to provide the cognitive capabilities of modern humans. The specialized intelligences suggested by Steven Mithen are:

Technical intelligence
Natural history intelligence
Social intelligence
Linguistic intelligence

Before Steven Mithen, Anette Karmiloff-Smith, in her book Beyond Modularity: A developmental perspective on cognitive science built on Piaget and Fodor to suggest that a child's cognitive development takes place within five different domains before the process of representational redescription produces domain generic knowledge from the previous domain specific knowledge. Anette Karmiloff-Smith considers the following domains:

The child as a linguist
The child as a physicist
The child as a mathematician
The child as a psychologist
The child as a notator

These and other proposals of cognitive dimensions, including the traditional four F's (feeding, fighting, fleeing and mating) and theories from neuroscience, e.g., Joaquin M Fuster's book Cortex and Mind: Unifying Cognition.

Prioritized sweeping

2012-01-23T13:44:00.001-08:00

In considering how we can make our RLSOM algorithm more efficient, the idea of focusing the activation spreading around the area of maximum activity was raised (by my PhD student Georgios Pierris). This concept was formalised as 'prioritized sweeping' by Moore and Atkeson in 1993.

Like growing SOMs, this is a concept I would like to explore further.

Reference:

Moore, A.W., Atkeson, C.G.: Prioritized sweeping: Reinforcement learning with less data and less time. Machine Learning, 13:103–130, 1993.

Matching landscapes

2011-10-31T07:57:00.000-07:00

One of my PhD students had a very good idea today. In combining SOMs and RL we are defining two landscapes, the SOM landscape and the reward landscape. It would be very interesting to see if it would be possible to use the SOM landscape to approximate the RL landscape and, thus, calculate utilities for unexplored areas of the RL landscape. It brings to mind Ulrich Nehmzow's work on sub-symbolic planning.

John Pisokas and Ulrich Nehmzow, Performance Comparison of Three Subsymbolic Action Planners for Mobile Robots, Robotics and Autonomous Systems, 51(1):55-67, 2005

Must develop this idea further...

Dimensions of RLSOM

2011-10-17T01:17:00.000-07:00

At the Cognitive Robotics Research Centre at the University of Wales, Newport, we have been working on a reinforcement learning self-organizing map (RLSOM).
Without going into the details of the RLSOM algorithm, I'd liek to list some potential extensions:

From fixed length memory to primitives
STM Length and Learning Frequency
Representing space using decaying activation
Sparse representation of connections
One-shot and incremental learning
Pre-structuring hierarchies
Random connections across hierarchical levels

Stability

2010-09-27T05:53:00.000-07:00

I have remembered another feature that is required of efficient robot learning. This is stability, i.e., the ability to correct perturbed trajectory. Bugmann et al. (2006) demonstrate this property in an autonomous wheelchair. When perturbations occur, blind, i.e., open loop, reproduction of a learned trajectory will not lead the robot to a target. In order to reach the goal, the robot must be able to receive feedback and to correct the learned trajectory so that the final target is reached.

This feature has been described by Ijspeert et al. (2002) as an attractor landscape where the the learned policy will produce trajectories that move towards the ideal trajectory. This can be achieved through designing reward functions that promote the ideal trajectory. Algorithms that explore the landscape around this will produce an attractor landscape through the discounted rewards.

Features Necessary for Efficient Robot Learning

2010-09-23T03:43:00.000-07:00

I have been collecting features I think are necessary for efficient robot learning algorithms. Much of my research lately has been related to integrating these features into a single system.

The features so far are:

Sequential - Sequences of events in time. This is something artificial neural networks (ANNs) are typically not very good at.

Hierarchical - Hierarchical structures for long term memory (LTM). This enables reuse of low level behaviours and efficient encoding of observations. It is a well studied problem in reinforcement learning (RL) and Barto and Mahadevan (2003) have published a good review paper.

Incremental - Observations are processed in the sequence they are made without storing and revisiting old observations, improving the existing system before further observations are made. Reinke and Michalski (1988) first introduced this concept w.r.t. their incremental AQ algorithm for learning concept descriptions. Many ANNs are statistic, i.e., they need to repeatedly pass through batches of observations.

One-shot - Able to learn from a single, or a small number of, observations. Bayesian approaches to this problem have been published by Fei-Fei et al. (2003) and Maas and Kemp (2009). Instance-based learning algorithms such as the Nearest Sequence Memory (NSM) algorithm presented by McCallum (1996) are an extreme form of one-shot learning. Wu and Demiris (2010) recently published an algorithm that is both hierarchical and one-shot.

Auto-associative - Retrieving memory content using the content itself as a reference, e.g., retieving a stored image of a person's face using another image or a partially obscured image of that face. This is what neural networks are good at and it makes them able to handle noisy real world date. This is something RL algorithms are typically not so good at.

Future reward prediction - Predicting what actions will optimise future rewards in what world states. This is a core feature of RL algorithms (Sutton & Barto 1998).

Hidden state identification - Different world states can produce identical observations, e.g., two different corridors in a building can look exactly the same. The only way to tell these states apart is to remember observations from the past, e.g., you know what corridor you're in because you remember what floor you took the elevator to. Some, but not all, RL algorithms have this feature.

Cohen et al. (2002) have presented the Constructivist Learning Architecture (CLA) that was both sequential, hierarchical and auto-associative, using decaying node activities in a hierarchical self-organising map (SOM) or Kohonen network (Kohonen 2001).

My paper (2010) presented a hierarchical extension of McCallum's NSM algorithm that was both sequential, one-shot and hierarchical with future reward prediction and hidden state identification capabilities.

Pierris and I (2010) published an algorithm that used a version of the Cohen's CLA algorithm, the Compressed Sparse Code (CoSCo) SOM, to reproduce a humanoid robot motion demonstrated by a human teacher. This work went beyond the original work of Cohen et al. in that it repeatedly used the learned SOM for action selection in order to reproduce the motion.

In the future I aim to use the mechanisms I developed for the hierarchical NSM algorithm to extend Chaput's decaying activity hierarchical SOMs so that it can support future reward discount and hidden state identification. This will create an algorithm suitable for RL problems such as reaching.