Motivation and challenges
1.1. Motivation and challenges¶
ALCS were designed and thoroughly tested in problems where the concept or a function sought is essentially “logical” - meaning that it can be expressed by a combination of logical operators applied to attribute values [29]. However, in many problems, the solution cannot be conveyed solely by and, or, not operators because its discrimination surface is oblique - neither parallel nor perpendicular to the attribute axes. If the problem’s discrimination surface is oblique, the classifier rule can capture parts of space within hyper-rectangles, which can only approximate the function shape using multiple distinct classifiers.
The most popular family of LCS and the ALCS predecessor - XCS [30], was comprehensively evaluated for problems with non-linear decision surfaces and real-valued input. In 1999 Lanzi took an approach to use S-classifiers [31], where the classifier’s condition parts are Lisp S-expressions and can be based on arithmetic function primitives. In 2000 Wilson focused on continuous value inputs introducing XCSR implementation [32]. The condition attribute was an interval represented by a pair of numbers - the centre and the spread. He examined if the optimal decisive thresholds are found automatically in a modified Multiplexer benchmark problem. In the same year, he introduced an XCSI system [29], forming bounded intervals for integer inputs. One year later, in 2001, another implementation named XCSF [33] allowing piecewise-linear function approximation was proposed. For a function \(y=f(x)\), the system assumed that \(x\) is the input, \(y\) the payoff, and after a sufficient amount of sampling, the input space XCSF should converge to a population of rules that, over their respective input ranges, predict payoff well. In 2003 Stone and Bull scrupulously addressed the limitations of the XCSR system [34] and introduced two new interval representations alongside a more versatile benchmark problem. The ordered-bounded (OBR) and unordered-bounded (UBR) representations describe the interval using left \(x_1\) and right \(x_2\) bounds but in OBR \(x_1 < x_2\). By neglecting the explicit ordering, the system evolves better classifiers using the UBR representation. In 2005 Dam and Abbass also proposed a Min-Percentage approach [35], attempting to overcome some UBR drawbacks. Recent XCSR advancements aims to generate interpretable rules for high-dimensional data by employing encoder/decoder models for dimensionality reduction [36] [37]. Proposed modifications, by using deep-learning techniques, managed to obtain almost 99% accuracy on the MNIST database [38], where each data instance is represented by a vector of 784 values ranging \([0, 1]\).
In 2007, Cielecki [39] [40] proposed a real-valued modification towards GCS (Grammar-based Classifier Systems) in which the knowledge is represented by a Context-Free-Grammar in Chomsky normal form. The system evolves a population of rules where each one represents a single grammar. Preliminary tests were outperformed Stone’s XCSR system by creating a perfect set of easy to interpret classifiers.
For the ALCS, only the preliminary studies transforming the real-valued input using discretization methods were performed by Unold in 2016 [41]. This work tries to bridge the gap between advancements from various LCS implementations mentioned earlier and the anticipatory systems by introducing features and modifications for handling input signals, especially discretization or interval encoding representations. Such changes would greatly increase the potential applicability of the algorithm. However, due to the more complex rule structure of ALCS (additional prediction part) and the presence of other discovery components, certain limitations were observed and addressed herein. The biased exploration enhancement investigates the impact of optimizing the action selection method using specific strategies to stimulate knowledge formation [42]. On the other side, there is also a problem with long-action chains and diminishing reward that might occur when using fine-grained nominal representation for continuous data [43] - in this case, incorporating an average reward criterion resulted in a more distinct payoff landscape and faster knowledge acquisition.