ADEPT project to merge two sub-fields of machine learning
05 March 2008
Predicting unknown quantities is a fundamental part of science and engineering. For example, in medicine one might wish to predict whether a person has a cancerous tumour or not based on a scan; or in manufacturing, whether an industrial machine is producing faulty devices or not. The field of Artificial Intelligence has studied many techniques to produce good predictors. The last decade of research has seen the development of "population-based" techniques.
Instead of using a single predictor, these build teams of predictors and combine the decisions of the individuals through a voting or averaging process. Both theory and experiments show this reliably improves upon using a single predictor -- as they say two heads are better than one. A nice feature is that these methods are predictor-independent, meaning they can combine any kind of predictors (e.g. neural networks, decisions trees) into a team.
This project aims to unify two sub-fields of Artificial Intelligence that deal with these population-based predictor-independent techniques: Ensemble Methods and Learning Classifier Systems. Ensemble Methods have produced some of the most powerful predictors of the last decade; the most well-known is called "AdaBoost", and has been dubbed "the best off-the-shelf predictor in the world" (Professor Leo Breiman, University of California at Berkeley).
These methods have been widely applied in many areas; however, one important area not yet investigated is "multi-step" problems. These are problems where decisions in the past and present can affect what the best decisions in the future will be---for example choosing to play a certain opening strategy in chess means certain moves are less favourable later on in the game.
Our most difficult multi-step problem will be optimising elevator scheduling to minimise the amount of time between pressing an elevator call button and the arrival of the elevator. It is surprisingly difficult to optimise the movement of elevators in a large building. For example the Empire State Building has 73 elevators serving 102 floors. There are more possible configurations than there are grains of sand on all the beaches in the world. Most ensemble methods cannot be directly applied to this kind of problem.
Learning Classifier Systems are a class of nature-inspired algorithms that can dynamically generate and adjust sets of predictors, and are capable of tackling these multi-step problems. Traditional ensemble methods have not considered the multi-step domain, but have strong theoretical foundations to build upon. Learning Classifier Systems do not have such a strong theory base, but have been intensely studied on multi-step problems. This project will create hybrid methods using theory and practice from these two quite disparate fields. We will advance the state-of-the-art in both fields and increase research capacity for tackling several problem classes, focusing in particular on multi-step problems.