Online Learning With Random Representations
- Richard S. Sutton, Department of Computing Science, University of Alberta
- Steven D. Whitehead, GTE Laboratories Incorporated, Waltham, MA
We consider the requirements of online learning---learning which must be done incrementally and in realtime, with the results of learning available soon after each new example is acquired. Despite the abundance of methods for learning from examples, there are few that can be used effectively for online learning, e.g., as components of reinforcement learning systems. Most of these few, including radial basis functions, CMACs, Kohonen's self-organizing maps, and those developed in this paper, share the same structure. All expand the original input representation into a higher dimensional representation in an unsupervised way, and then map that representation to the final answer using a relatively simple supervised learner, such as a perceptron or LMS rule. Such structures learn very rapidly and reliably, but have been thought either to scale poorly or to require extensive domain knowledge. To the contrary, some researchers (Rosenblatt, 1962; Gallant & Smith, 1987; Kanerva, 1988; Prager & Fallside, 1988) have argued that the expanded representation can be chosen largely at random with good results. The main contribution of this paper is to develop and test this hypothesis. We show that simple random-representation methods can perform as well as nearest-neighbor methods (while being more suited to online learning), and significantly better than backpropagation. We find that the size of the random representation does increase with the dimensionality of the problem, but not unreasonably so, and that the required size can be reduced substantially using unsupervised-learning techniques. Our results suggest that randomness has a useful role to play in online supervised learning and constructive induction.
Citation
R. Sutton, S. Whitehead. "Online Learning With Random Representations". International Conference on Machine Learning (ICML), Amherst, MA, USA, (ed: M. Kaufmann), pp 314-321, January 1993.| Keywords: | reinforcement, random, CMAC, machine learning |
| Category: | In Conference |
BibTeX
@incollection{Sutton+Whitehead:ICML93,
author = {Richard S. Sutton and Steven D. Whitehead},
title = {Online Learning With Random Representations},
Editor = {M. Kaufmann},
Pages = {314-321},
booktitle = {International Conference on Machine Learning (ICML)},
year = 1993,
}Last Updated: May 31, 2007Submitted by Staurt H. Johnson
