Constructing Complexity-efficient Features in XCS with Tree-based Rule Conditions
This work addresses efficiency issues in LCS for researchers in evolutionary computation and machine learning, but it is incremental as it builds on existing XOF and CF methods.
The paper tackled the problem of structural inefficiency in tree-based Code Fragments (CFs) used in Learning Classifier Systems (LCS) by proposing two measures: a CF-fitness update considering structural complexity and a niche-based CF generation method. The results showed significantly increased structural efficiency, measured by the rule 'generality rate', leading to faster learning performance in the Hierarchical Majority-on problem without needing a user-set depth limit.
A major goal of machine learning is to create techniques that abstract away irrelevant information. The generalisation property of standard Learning Classifier System (LCS) removes such information at the feature level but not at the feature interaction level. Code Fragments (CFs), a form of tree-based programs, introduced feature manipulation to discover important interactions, but they often contain irrelevant information, which causes structural inefficiency. XOF is a recently introduced LCS that uses CFs to encode building blocks of knowledge about feature interaction. This paper aims to optimise the structural efficiency of CFs in XOF. We propose two measures to improve constructing CFs to achieve this goal. Firstly, a new CF-fitness update estimates the applicability of CFs that also considers the structural complexity. The second measure we can use is a niche-based method of generating CFs. These approaches were tested on Even-parity and Hierarchical problems, which require highly complex combinations of input features to capture the data patterns. The results show that the proposed methods significantly increase the structural efficiency of CFs, which is estimated by the rule "generality rate". This results in faster learning performance in the Hierarchical Majority-on problem. Furthermore, a user-set depth limit for CF generation is not needed as the learning agent will not adopt higher-level CFs once optimal CFs are constructed.