Prediction update algorithms for XCSF: RLS, Kalman filter, and gain adaptation

ABSTRACT

We study how different prediction update algorithms influence the performance of XCSF. We consider three classical parameter estimation algorithms (NLMS, RLS, and Kalman filter) and four gain adaptation algorithms (K1, K2, IDBD, and IDD). The latter have been shown to perform comparably to the best algorithms (RLS and Kalman), but they have a lower complexity. We apply these algorithms to update classifier prediction in XCSF and compare the performances of the seven versions of XCSF on a set of real functions. Our results show that the best known algorithms still perform best: XCSF with RLS and XCSF with Kalman perform significantly better than the others. In contrast, when added to XCSF, gain adaptation algorithms perform comparably to NLMS, the simplest estimation algorithm, the same used in the original XCSF. Nevertheless, algorithms that perform similarly generalize differently. For instance: XCSF with Kalman filter evolves more compact solutions than XCSF with RLS and gain adaptation algorithms allow better generalization than NLMS.

REFERENCES

• 1: Martin V. Butz , Kumara Sastry , David E. Goldberg, Strong, Stable, and Reliable Fitness Pressure in XCS due to Tournament Selection, Genetic Programming and Evolvable Machines, v.6 n.1, p.53-77, March 2005 [doi>10.1007/s10710-005-7619-9]
• 2: M. V. Butz and S. W. Wilson. An algorithmic description of XCS. Journal of Soft Computing, 6(3-4):144--153, 2002.
• 3: S. A. Glantz and B. K. Slinker. Primer of Applied Regression & Analysis of Variance. McGraw Hill, 2001. second edition.
• 4: G. C. Goodwin and K. S. Sin. Adaptive Filtering: Prediction and Control. Prentice-Hall information and system sciences series, Mar. 1984.
• 5: M. E. Harmon and L. C. B. III. Multi-player residual advantage learning with general function. Technical report, Air Force Base Ohio: Wright Laboratory, 1996.
• 6: Simon Haykin, Adaptive filter theory (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 7: Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, Extending XCSF beyond linear approximation, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068319]
• 8: P. L. Lanzi, D. Loiacono, S. W. Wilson, and D. E. Goldberg. Generalization in the XCSF classifier system: Analysis, improvement, and extension. Technical Report 2005012, Illinois Genetic Algorithms Laboratory - University of Illinois at Urbana-Champaign, 2005.
• 9: P. L. Lanzi, D. Loiacono, S. W. Wilson, and D. E. Goldberg. XCS with computed prediction for the learning of Boolean functions. In Proceedings of the IEEE Congress on Evolutionary Computation - CEC-2005, pages 588--595, Edinburgh, UK, Sept. 2005. IEEE.
• 10: P. L. Lanzi, D. Loiacono, S. W. Wilson, and D. E. Goldberg. Prediction update algorithms for XCSF: Rls, kalman filter, and gain adaptation. Technical Report 2006008, Illinois Genetic Algorithms Laboratory - University of Illinois at Urbana-Champaign, 2006.
• 11: R. S. Sutton. Adapting bias by gradient descent: An incremental version of delta-bar-delta. In Proceedings of the Tenth National Conference on Artificial Intelligence, pages 171--176. MIT Press, 1992.
• 12: R. S. Sutton. Gain adaptation beats least squares? In Proceedings of the Seventh Yale Workshop on Adaptive and Learning Systems, pages 161--166. Yale University, New Haven, CT, 1992.
• 13: Bernard Widrow , Marcian E. Hoff, Adaptive switching circuits, Neurocomputing: foundations of research, MIT Press, Cambridge, MA, 1988
• 14: Stewart W. Wilson, Classifiers that approximate functions, Natural Computing: an international journal, v.1 n.2-3, p.211-234, June 2002

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

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

General Terms:
Algorithms, Performance

Keywords:
Kalman filter, LCS, XCS, prediction update