Mixing independent classifiers

ABSTRACT

In this study we deal with the mixing problem, which concerns combining the prediction of independently trained local models to form a global prediction. We deal with it from the perspective of Learning Classifier Systems where a set of classifiers provide the local models. Firstly, we formalise the mixing problem and provide both analytical and heuristic approaches to solving it. The analytical approaches are shown to not scale well with the number of local models, but are nevertheless compared to heuristic models in a set of function approximation tasks. These experiments show that we can design heuristics that exceed the performance of the current state-of-the-art Learning Classifier System XCS, and are competitive when compared to analytical solutions. Additionally, we provide an upper bound on the prediction errors for the heuristic mixing approaches.

REFERENCES

• 1: L. B. Booker. Approximating value function in classifier systems. In L. Bull and T. Kovacs, editors, Foundations of Learning Classifier Systems, volume 183 of Studies in Fuzziness and Soft Computing. Springer Verlag, Berlin, 2005.
• 2: Martin Butz , Stewart W. Wilson, An Algorithmic Description of XCS, Revised Papers from the Third International Workshop on Advances in Learning Classifier Systems, p.253-272, September 15-16, 2000
• 3: Colt project: Open source libraries for high performance scientific and technical computing in java, 2004.
• 4: A. Dempster, N. Laird, and D. Rubin. Maximum likelihood from incomplete data via the EM alrogithm. Journal of the Royal Statistical Society, Series B, 39(1):1--38, 1977.
• 5: D. L. Donoho and I. M. Johnstone. Ideal spatial adaptation by wavelet shrinkage. Biometrika, 81:425--455, 1994.
• 6: J. Drugowitsch and A. M. Barry. Mixing Independent Classifiers. Technical Report 2006-13, University of Bath, U.K., November 2006.
• 7: J. Drugowitsch and A. M. Barry. A Formal Framework and Extensions for Function Approximation in Learning Classifier Systems. Machine Learning, in press.
• 8: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 9: S Haykin, Adaptive filter theory, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 10: R. Jacobs, M. Jordan, R. Jacobs, S. Nowlan, and G. Hinton. Adaptive mixtures of local experts. Neural Computation, 3:79--87, 1991.
• 11: Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, Prediction update algorithms for XCSF: RLS, Kalman filter, and gain adaptation, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144243]
• 12: R. S. Sutton. Gain adaptation beats least squares? In Proceedings of the Seventh Yale Workshop on Adaptive and Learning Systems, pages 161--166, 1992.
• 13: S. W. Wilson. Classifier Fitness Based on Accuracy. Evolutionary Computation, 3(2):149--175, 1995. http://prediction-dynamics.com/.
• 14: S. W. Wilson. Function Approximation with a Classifier System.In L. Spector, E. D. Goodman, A. Wu, W. B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. H. Garzon, and E. Burke, editors, GECCO-2001: Proceedings of the Genetic and Evolutionary Computation Conference, pages 974--981, San Francisco, California, USA, 7-11 July 2001. Morgan Kaufmann.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Least squares approximation

General Terms:
Algorithms, Performance, Theory

Keywords:
information fusion, learning classifier systems