# Evolving Matrix-Factorization-Based Collaborative Filtering Using Genetic Programming
## 2 Materials and Methods
### Genetic Programming  
Evolutionary Algorithms (EAs) [14] are a method of optimization and search based on populations of individuals, which represent candidate solutions to a given problem. By means of an iterative process inspired by the natural selection mechanism, new solutions are generated from the existing ones and solutions (i.e., individuals) that show a bad performance are discarded. The performance that guides the selection process is known as the fitness value of the individual. Selecting an adequate fitness function is crucial to success when designing an EA because it assigns a performance value to an individual which also guides the selection process. Hence, a bad fitness function makes it harder for the EA to find good solutions. Another important step in the design of an EA is choosing a suitable set of variation operators. These functions are responsible for taking several individuals as inputs and producing new ones that are slightly different. The main idea of this process is to introduce diversity within the population of solutions. GP [15] is a kind of algorithm belonging to the family of evolutionary computing. The distinctive feature of GP is the internal representation of the candidate solutions, which are coded with a tree structure. The internal nodes represent operations and functions of various kinds, while the leaf nodes correspond to input variables and constant values. Therefore, a candidate solution representsa computer program, since the nodes correspond to functions and operators, whose results serve as inputs for other functions that also operate on certain inputs. One of the features of GP algorithms is their ability to search and find novel solutions to the problem, subject to optimization. CF based on MF has exhibited a very good performance, so we planned to study whether we would be able to find aggregation functions of the latent factors \(h\) other than the usual inner product, that achieves a better performance. EMF, our proposed method, is a GP algorithm in which the individuals of the population are aggregated functions \(h\), as described in Section 2.1. To do so, leaf nodes of an individual are the projections of the users' ratings in the \(k\)-dimensional latent space: \(p_{u,A},q_{i,A}\). In addition to these, we included two constant values that might be considered as leaf nodes: 0.0 (Zero) and 1.0 (One), in order to increase the expressiveness in the aggregation functions \(h\) generated by the algorithm. Regarding the internal nodes, we decided to include both linear and nonlinear mathematical operators. The operations are shown in Table 1.  
To measure the quality of the solutions (i.e., the fitness function), we used the Mean Absolute Error (MAE) Equation (6) metric, defined as the averaged absolute difference between the real rating (\(r_{u,i}\)) and the prediction performed by the aggregation function \(h\):  
\[MAE=\frac{1}{\#R^{test}}\sum_{(u,i)\in R^{test}}|r_{u,i}-h(p_{u,1},\ldots,p_{u, k},q_{i,1},\ldots,q_{i,k})|, \tag{6}\]  
with \(R^{test}\) made up of those ratings from user \(u\) to item \(i\) (\(r_{u,i}\)) that were selected as test. Although the fitness function has been set up, there is a following explanation about how this fitness value is assigned to each individual. First, the aggregation function encoded by the individual is derived, as required by the SGD algorithm. To find the derivative of each individual, we built a Java library for symbolic derivation [16]. Then, the MF model is trained following the procedure described in Section 2.1, taking into account that the individual being evaluated is the aggregation function \(h\) of Equation (1). Finally, the quality of the trained model is evaluated against a test split of the dataset, computing the MAE and assigning this value as the fitness of the individual. On top of the aforementioned elements of the algorithm is the so-called breeding pipeline, that is, the precise process the individuals of the population follow during each generational step within the algorithm.