Get BackLast modified: Tue Nov 24 12:35:39 EST 1998
In many situations in which a software system learns, it must deal with a colossal amount of information. This talk is about ways to store that information in indirect ways (called Condensed Representations) that permit a broad range of statistical learning algorithms to do their processing almost as quickly as if they had only a little data. We will show how this can help with conventional supervised learning, with clustering, with Bayesian network learning and (if time permits) with certain classes of reinforcement learning.
We will begin with AD-trees, a new data structures that can empirically give a 50-fold to 1000-fold computational speedup for machine learning methods such as Bayes net structure finders, rule learners and feature selectors operating on large datasets. Many machine learning algorithms need to do vast numbers of counting queries (e.g. "How many records have Color=Blue, Nationality=British, Smoker=False, Status=Married, Nose=Big?"). We provide methods for which, subject to certain assumptions, the amortized costs of these kinds of operations can be shown to be independent of the number of records in the dataset. We empirically demonstrate that tractably-sized data structures can be produced for large real-world datasets.
We will then move to representations for dealing with real-valued data sources, and show new structures that allow very fast EM-based clustering (unsupervised learning) of data, hundreds of times faster than conventional methods on large datasets.
In the final segment we will demonstrate one way in which condensed representations can cache information useful not merely for statistical analysis, but also control. A data structure, called the "airport hierarchy" allows us to produce and represent policies for all possible start/goal combinations in certain classes of Markov Decision problems, with time and memory requirements only slightly greater than for a single goal.
Andrew Moore received a Phd in Computer Science from the University of Cambridge in 1991 (thesis topic: Robot Learning). He worked as a post-doc with Chris Atkeson at MIT AI lab for three years before joining CMU as an assistant professor in Robotics/CS in 1993. His research interests include: Autonomous learning systems for manufacturing, efficient algorithms for machine learning and reinforcement learning, finite production scheduling, and machine learning applied to optimization. His group is currently applying the results of their research to astrophysics data mining, drug discovery, inventory management, stochastic production scheduling and distributed power management.
Joint work with Mary Soon Lee
Get Back
Last modified: Tue Nov 24 12:35:39 EST 1998