# An Evolutionary Computation Approach for Twitter Bot Detection
## 4 Proposed Approach
### Genetic Programming  
The main difference between GP and GA is related to the type of individual and the way individuals evolve during the evolutionary process. In the context of GP, an individual is a tree where nodes correspond to user-defined primitives that can be, for instance, any kind of function, while the leaves are the terminals, that is, arguments of the tree and, eventually, randomly generated constants. In the proposed approach, the hypothesis function has the following form:  
\[h_{\text{GP}}^{\mathcal{M}}(\mathbf{x})=\texttt{int}(\mathcal{M}(\mathbf{x}) \leq 0) \tag{14}\]  
where \(\mathcal{M}:\mathbb{R}^{d}\rightarrow\mathbb{R}\) is a classification formula based on the best tree generated using GP, according to the fitness function. This tree is a combination of primitive functions applied to terminals and results that have been generated by other primitive functions in the tree. In our setting, the terminals are the \(d\) numerical features that characterize a user account \(u\), and, eventually, one or more ephemeral constants that are randomly generated by a uniform distribution defined on a range of possible values between zero and one. These terminals are chosen to populate the leaves of each tree. Instead, the internal nodes are populated by elements of a set of functions that, in our setting, consists of a set of strongly typed functions described as follows: \(a+b\), \(a-b\), \(ab\), \(2a\), \(\frac{a}{2}\), \(3a\), \(\frac{a}{3}\), \(-a\), where \(a,b\in\mathbb{R}\). Using this set of primitives enables us to potentially learn a model that resembles a mathematical formula composed of a combination of simple arithmetical operations. A model based on this structure could be interpreted at an operational level, and it can automatically perform feature selection and feature engineering tasks by combining subsets of the original input features that should help to discover the best decision boundaries for our problem. In particular, ephemeral constants randomly sampled between zero and one could play the role of weights or act as biases in some mathematical operation. In this setting, we can use GP to learn a tree-based model \(\mathcal{M}\) to maximize a given quality objective related to our detection problem. Specifically, our problem is a bi-objective optimization problem where we want to minimize two fitness functions: the mean squared error and the anti-reciprocal of the number of nodes of a given individual. The mean squared error is defined as follows:\[\text{MSE}_{GP}(\tilde{\mathcal{M}},\tilde{X},g)=\frac{\sum_{i=1}^{|\tilde{X}|}(h_{ GP}^{\mathcal{M}}(\tilde{X}^{i})-\tilde{y}_{i})^{2}}{|\tilde{X}|} \tag{15}\]  
while  
\[\mathcal{M}=\arg\min_{\tilde{\mathcal{M}}\in\mathcal{S}_{GP}}F_{GP}\bigg{(} \text{MSE}_{GP}(\tilde{\mathcal{M}},\tilde{X},\tilde{y}),-\frac{1}{|\tilde{ \mathcal{M}}|}\bigg{)} \tag{16}\]  
is the best individual discovered by the evolutionary process, \(\boldsymbol{S_{GP}}\) is the set of all possible trees that can be generated by GP, and \(F_{GP}\) is a weighted combination of the two objective functions of this problem. The second argument of \(F_{GP}\) is the anti-reciprocal of the number of nodes of a given tree, and this quantity is minimized along with the mean squared error to ensure the construction of classification models with a reasonably low number of nodes. This countermeasure should enable us to discover models that are potentially more interpretable than complex models with a large number of nodes and high depth. Resuming the problem of overfitting, \(\tilde{X}\), \(\tilde{y}\), and \(s\) are defined just as we described in the GA case. We use the same strategy as adopted in the GA process to reduce overfitting while allowing for better generalization of unseen data. In particular, an individual is evaluated on a random sample of training data that corresponds approximately to 60% of it, and because random sampling is repeated at the beginning of each generation, this expedient should avoid overfitting at the end of the evolutionary process.