Transferable XCS

ABSTRACT

Traditional accuracy-based XCS classifier system generally learns and evolves classifiers from scratch when facing each particular problem. Inspired by humans with the ability to learn new skills by inducing knowledge from related problems, transfer learning (TL) focuses on leveraging the knowledge of source domains to help the problem solving of another different but related domain. This paper attempts to combine XCS and TL to propose a novel extension transferable XCS (tXCS). tXCS utilizes the inherent characteristics of XCS, that naturally discovers expressive classifiers as the generalized knowledge of domains, to realize the classifier transfer from source domains to a target domain that makes it learn faster, which is conceptually different from the previous integrations between XCS and TL. The systematic study is presented to verify the ability of knowledge transfer between domains with different degrees of similarity, which has been pointed out to be the challenge of TL. We demonstrate that tXCS can significantly speed up the learning efficiency of canonical XCS in both of single-step and multi-step benchmark problems.

References

1. I. M. Alvarez, W. N. Browne, and M. Zhang. Reusing learned functionality to address complex boolean functions. In SEAL, pages 383--394, 2014.
2. J. Bacardit and M. Butz. Data mining in learning classifier systems: Comparing XCS with GAssist. In Learning Classifier Systems, pages 282--290. 2007.
3. K. Bache and M. Lichman. UCI machine learning repository, 2013.
4. E. Bernado-Mansilla and J. M. Garrell-Guiu. Accuracy-based learning classifier systems: models, analysis and applications to classification tasks. Evol. Comput., 11(3):209--238, 2003.
5. M. V. Butz. XCSJava 1.0: An implementation of the XCS classifier system in Java. Technical Report No. 2000027, Illinois Genetic Algorithms Laboratory, UIUC, 2000.
6. M. V. Butz, D. E. Goldberg, and P. L. Lanzi. Gradient descent methods in learning classifier systems: Improving XCS performance in multistep problems. IEEE Trans. on Evol. Comput., 9(5):452--473, 2005.
7. M. V. Butz, T. Kovacs, P. L. Lanzi, and S. W. Wilson. Toward a theory of generalization and learning in XCS. IEEE Trans. on Evol. Comput., 8(1):28--46, 2004.
8. M. V. Butz and M. Pelikan. Studying XCS/BOA learning in boolean functions: structure encoding and random boolean functions. In Proceedings of the annual conference on Genetic and Evol. Comput., pages 1449--1456, 2006.
9. M. V. Butz and S. W. Wilson. An algorithmic description of XCS. Soft Computing, 6(3-4):144--153, 2002.
10. W. Dai, Q. Yang, G.-R. Xue, and Y. Yu. Boosting for transfer learning. In Proceedings of the international conference on Machine learning, pages 193--200, 2007.
11. S. Dzeroski, L. De Raedt, and K. Driessens. Relational reinforcement learning. Machine Learning, 43(1-2):7--52, 2001.
12. L. Feng, Y. Ong, M. Lim, and I. W. Tsang. Memetic search with interdomain learning: A realization between CVRP and CARP. IEEE Trans. Evolutionary Computation, 19(5):644--658, 2015.
13. M. Iqbal, W. Browne, and M. Zhang. Reusing building blocks of extracted knowledge to solve complex, large-scale boolean problems. IEEE Trans. on Evol. Comput., 18(4):465--480, 2014.
14. G. Konidaris, I. Scheidwasser, and A. Barto. Transfer in reinforcement learning via shared features. Journal of Machine Learning Research, 13:1333--1371, 2012.
15. T. Kovacs. XCS classifier system reliably evolves accurate, complete, and minimal representations for boolean functions. In Soft comput. in eng. design and manufacturing, pages 59--68. Springer, 1998.
16. T. Kovacs. Genetics-based machine learning. In Handbook of Natural Computing, pages 937--986. Springer, 2012.
17. P. L. Lanzi. An analysis of generalization in the XCS classifier system. Evol. Comput., 7(2):125--149, 1999.
18. P. L. Lanzi, W. Stolzmann, and S. W. Wilson. Learning classifier systems: from foundations to applications. Springer, 2000.
19. P. Larra~naga and J. A. Lozano. Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation. Kluwer Academic Publishers, 2002.
20. X. Li, S. Mabu, and K. Hirasawa. A novel graph-based estimation of the distribution algorithm and its extension using reinforcement learning. IEEE Trans. Evol. Comput., 18(1):98--113, 2014.
21. D. Mellor. Policy transfer with a relational learning classifier system. In Proceedings of the workshops on Genetic and Evol. Comput., pages 82--84, 2005.
22. S. J. Pan and Q. Yang. A survey on transfer learning. IEEE Trans. on Knowledge and Data Engineering, 22(10):1345--1359, 2010.
23. M. Pelikan, M. Hauschild, and P. Lanzi. Transfer learning, soft distance-based bias, and the hierarchical BOA. In Parallel Problem Solving from Nature - PPSN XII, pages 173--183. 2012.
24. R. Santana, A. Mendiburu, and J. A. Lozano. Structural transfer using EDAs: An application to multi-marker tagging snp selection. In IEEE Congr. on Evol. Comput., pages 3221--3228, 2012.
25. X. Shi, Q. Liu, W. Fan, and P. Yu. Transfer across completely different feature spaces via spectral embedding. IEEE Trans. on Knowledge and Data Engineering, 25(4):906--918, 2013.
26. O. Sigaud and S. W. Wilson. Learning classi er systems: a survey. Soft Computing, 11(11):1065--1078, 2007.
27. K. O. Stanley, D. B. D'Ambrosio, and J. Gauci. A hypercube-based encoding for evolving large-scale neural networks. Artif. Life, 15(2):185--212, 2009.
28. R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.
29. M. E. Taylor and P. Stone. Cross-domain transfer for reinforcement learning. In Proceedings of the international conference on Machine learning, pages 879--886, 2007.
30. M. E. Taylor and P. Stone. Transfer learning for reinforcement learning domains: A survey. Journal of Machine Learning Research, 10:1633--1685, 2009.
31. R. J. Urbanowicz and J. H. Moore. Learning classifier systems: a complete introduction, review, and roadmap. Journal of Artificial Evolution and Applications, 2009:1--25, 2009.
32. P. Verbancsics and K. O. Stanley. Evolving static representations for task transfer. Journal of Machine Learning Research, 11:1737--1769, 2010.
33. C. J. C. H. Watkins. Learning from delayed rewards. PhD thesis, University of Cambridge, 1989.
34. S. W. Wilson. ZCS: A zeroth level classifier system. Evol. Comput., 2(1):1--18, 1994.
35. S. W. Wilson. Classifier tness based on accuracy. Evol. Comput., 3(2):149--175, 1995.
36. S. W. Wilson. Mining oblique data with XCS. In Advances in Learning Classifier Systems, pages 158--174. 2001.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Multi-task learning

        • Transfer learning

    • Machine learning algorithms

      • Dynamic programming for Markov decision processes

        • Q-learning

    • Machine learning approaches

      • Bio-inspired approaches

        • Genetic algorithms