# Evolving Matrix-Factorization-Based Collaborative Filtering Using Genetic Programming
## 2 Materials and Methods
### Matrix Factorization  
MF, as in the traditional meaning of the term, consists of splitting a matrix \(A\in\mathbb{R}^{n\times m}\) into the product of two other matrices \(A=P\times Q\), \(P\in\mathbb{R}^{n\times k}\), \(Q\in\mathbb{R}^{k\times m}\). In other words, matrix factorization is a way of reducing a matrix into its constituent parts. This transformation is particularly convenient because it typically gives a more compact representation, hence making it easier to calculate more complex matrix operations.  
When applied to CF, MF is an embedding model. Given the sparse rating matrix \(R\in\mathbb{V}^{n\times m}\)--with \(n\) being the number of users (rows), \(m\) being the number of items (columns), and \(\mathbb{V}\) being the feasible ratings that a user is able to give to an item--the model learns both a user projection matrix \(P\in\mathbb{R}^{n\times k}\), where each row is a projection for a user; and an item projecting matrix \(Q\in\mathbb{R}^{m\times k}\), with each row representing an projection for an item. The projections are learned such that the product \(P\cdot Q^{T}\) is a good approximation of the ratings matrix \(R\).  
Note that MF generally provides a more compact representation than learning the full matrix, as the projection dimension \(k\) is usually much smaller than \(m\) and \(n\). Hence, MF finds latent structure in the data, assuming that observations lie close to a low-dimensional latent space.  
To learn the embeddings, MF becomes an optimization problem, whose target is to minimize the following objective function:  
\[\min_{p_{u,1},\ldots,p_{u,k},q_{i,1},\ldots,q_{i,k}}\sum_{(u,i)\in R}\left(r_{u,i }-h(p_{u,1},\ldots,p_{u,k},q_{i,1},\ldots,q_{i,k})\right)^{2}+\lambda(\sum_{ \alpha=1}^{k}p_{u,\alpha}^{2}+q_{i,\alpha}^{2}). \tag{1}\]  
Here, \(R\) represents the set of \((u,i)\) pairs for which the rating of the user \(u\) to the item \(i\), denoted \(\tau_{u,i}\), is known. The function \(h(p_{u,1},\ldots,p_{u,k},q_{i,1},\ldots,q_{i,k})\) is a mathematical function that aggregates user and item latent factors to compute model predictions, and \(\lambda\) is a regularization hyperparameter to avoid overfitting.  
Stochastic Gradient Descent (SGD) [13], an iterative method for optimizing an objective function with suitable smoothness properties such as differentiability, is usually applied as the optimization algorithm to minimize the aforementioned function and learn the embeddings. SGD's iterative process updates \(p_{u,\alpha}\) and \(q_{i,\alpha}\) according to Equations (2)-(4).  
\[e_{u,i}^{t}=r_{u,i}-h(p_{u,1}^{t},\ldots,p_{u,k}^{t},q_{i,1}^{t},\ldots,q_{i,k }^{t}), \tag{2}\]  
\[p_{u,\alpha}^{t+1}=p_{u,\alpha}^{t}+\gamma\left(e_{u,i}^{t}\cdot\frac{\partial h }{\partial p_{u,\alpha}}-\lambda p_{u,\alpha}^{t}\right), \tag{3}\]  
\[q_{i,\alpha}^{t+1}=q_{i,\alpha}^{t}+\gamma\left(e_{u,i}^{t}\cdot\frac{\partial h }{\partial q_{i,\alpha}}-\lambda q_{i,\alpha}^{t}\right), \tag{4}\]  
where \(\gamma\) is a hyperparameter to control the learning rate. It is customary to take, as aggregation function \(h\), the usual inner product of the latent factors:  
\[h(p_{u,1},\ldots,p_{u,k},q_{i,1},\ldots,q_{i,k})=\sum_{\alpha=0}^{k}p_{u, \alpha}\cdot q_{i,\alpha}. \tag{5}\]  
In this paper, we break from with the traditional assumption that the users' and items' factors must be combined in a linear fashion (i.e., using the inner product) and propose EMF, an evolutionary framework to generate varied aggregation functions \(h\) in order to improve the quality of the predictions made by a CF RS based on MF. How EMF explores and generates different \(h\) functions is described in Section 2.2.