# EEG Feature Extraction Using Genetic Programming for the Classification of Mental States
## 3 Proposed Enhanced System
### Augmented Feature Extraction with Genetic Programming: \({}^{+}\)Fegp  
Recognized as one of the most important tasks in a classification system, our main proposal is focused on the improvement of the feature extraction stage. One of the discovered complexities found during the implementation of the reference system is that the data of the study are highly varied and uncorrelated within the same class, and overlapped between both classes. This yields a non-trivial problem for any supervised learning system. A suitable strategy would be to build a non-linear model that produces new features, which further increase the inter-class distance and reduce the intra-class dispersion. Based on this, a GP-based algorithm is proposed with the objective of improving the classification accuracy for the reference system. Another goal for the proposal is to be highly flexible, not explicitly depending on any specific pre-processing or classifier blocks. A diagram for this algorithm is depicted in Figure 6, hereafter referred to as \({}^{+}\)FEGP, for augmented Feature Extraction with GP. Similar research on feature extraction with GP has been conducted. [PERSON] et al. [25] proposed first an individual representation with a single root node, where a special node called 'F' can be inserted into any part of the tree, which produces a new feature. Other than this enhancement, no special search operators were used for their system. On the other hand, [PERSON] et al. [58] used a canonical GP individual representation, where a single tree produces a new feature, a rather simple proposal that nevertheless produced competitive results for the classification of signals from epileptic seizures. A similar approach was followed by [PERSON] et al. in [59], where a single root node representation with a custom fitness function was used to evolve mouse trajectories by employing EEG signals. The authors used a strongly typed GP, a variant in which there is an explicit constraint on the data type allowed in the terminals and functions. In a previous work [40], we used GP as a classifier for the detection of epileptic stages, taking as input simple statistics from each trial. Figure 5: Genetic Programming (GP) flowchart in a nutshell. The present proposal builds upon previous works in [10; 57], where the Multidimensional Multiclass Genetic Programming (M3 GP) algorithm was presented. M3 GP also uses some additional search operators to add or remove complete features during the run, but mostly relies on a canonical GP implementation with a single objective function that only takes into account the training accuracy and a static parametrization of the GP settings. On the other hand, \({}^{+}\)FEGP includes a wider variety of search operators, a specialized local fitness measure to account for the fact that each solution is a collection of subtrees, dynamic parameters that control how the search is performed at different moments during the evolution, a regularized fitness function to control over-fitting and achieve better generalization, and a specialized initialization procedure to account for the extremely large feature space in this problem domain. Each of these features will now be explained in greater detail. 1. **Individual representation. ** The representation is also based on a tree structure, but it involves a multi-tree with a single root node, such that each individual defines a mapping of the form \(K:\mathbb{R}^{k}\rightarrow\mathbb{R}^{r}\), where \(k\) is the number of input features and \(r\) is the number of newly constructed features. Each of these subtrees are constructed in the same way as in a canonical GP (see Figure 7). No calculation is executed at the root node; it is rather used as a container for the output of the evolving \(r\) subtrees. Each subtree works as a non-linear transformation of the input features into a new space that is expected to simplify the classification. Moreover, the number of new features \(r\) can vary among individuals.