CTR (click-through rate) prediction plays an important role in content recommendation and delivery, and the FFM model is good at handling this kind of data. The FFM model is a variant of the FM model, or rather the FM model is a special case of the FFM model
Rough pipeline
- Convert the dataset format (using the LIBSVM or FFMs style)
- Compute the loss function (using the exponential loss function)
- Optimize the parameters (using the AdaGrad + SG strategy)
Converting the data format
LIBSVM format (does not store zero-valued features):
$$ label \quad feat1:val1 \quad feat2:val2 \quad ... \quad $$FFMs format:
$$label \quad field1:feat1:val1 \quad field2:feat2:val2 \quad ... \quad$$For different data types the conversion of the data format differs
For Categorical Features
For example, given the following sample:
$$Yes \quad P:ESPN \quad A:Nike \quad G:Male$$Converted to LIBSVM format:
$$Yes \quad P-ESPN:1 \quad A-Nike:1 \quad G-Male:1$$Converted to FFMs format:
$$Yes \quad P:P-ESPN:1 \quad A:A-Nike:1 \quad G:G-Male:1$$Numerical Features
Numerical features have two conversion formats: the first treats each feature as its own field (this method just duplicates the data without adding information); the second discretizes the data and converts the format as categorical features
For example:
| Accepted | AR | Hidx | Cite |
|---|---|---|---|
| Yes | 45.73 | 2 | 3 |
| No | 1.04 | 100 | 50,000 |
Format one:
$$Yes \quad AR:AR:45.73 \quad Hidx:Hidx:2 \quad Cite:Cite:3$$Format two:
$$Yes \quad AR:45:1 \quad Hidx:2:1 \quad Cite:3:1$$For format two, some information may be lost after discretization
Single-field Features
Features of this kind reduce the FFM model to the FM model
Computing the loss function
In CTR prediction, the commonly used optimization is:
$$ min_{\mathbf{w}} \quad \frac{\lambda}{2}||\mathbf{w}||^2_2+\sum_{i=1}^m log(1+exp(-y_i\phi(\mathbf{w},\mathbf{x}_i))) $$where the function $\phi(\mathbf{w},\mathbf{x}_i)$ is replaced by different functions depending on the model; for the FFM model we have:
$$ \phi_{FFM}(\mathbf{w},\mathbf{x})=\sum_{j_1=1}^n\sum_{j_2=j_1+1}^n (\mathbf{w}_{j1,f2}\cdot\mathbf{w}_{j2,f1})x_{j1}x_{j2} $$where $f_1$ and $f_2$ denote the fields of $j_1$ and $j_2$ respectively
Optimizing the parameters
The parameters are optimized with the SG + AdaGrad method
First the gradients are computed:
$$ \begin{aligned} \mathbf{g}_{j1,f2} \equiv \nabla_{\mathbf{w}_{j1,f2}}f(\mathbf{w}) = \lambda \cdot \mathbf{w}_{j1,f2}+\kappa\cdot\mathbf{w}_{j2,f1}x_{j1}x_{j2} \\ \mathbf{g}_{j2,f1} \equiv \nabla_{\mathbf{w}_{j2,f1}}f(\mathbf{w}) = \lambda \cdot \mathbf{w}_{j2,f1}+\kappa\cdot\mathbf{w}_{j1,f2}x_{j1}x_{j2} \end{aligned} \tag{1} $$where:
$$ \kappa = \frac{\partial{log(1+exp(-y\phi_{FFM}(\mathbf{w},\mathbf{x})))}}{\partial{\phi_{FFM}({\mathbf{w},\mathbf{x}}})} =\frac{-y}{1+exp(y\phi_{FFM}({\mathbf{w},\mathbf{x}}))} $$Then, with the AdaGrad algorithm, the squares of the gradients are accumulated:
$$ \begin{aligned} (G_{j1,j2})_d \leftarrow (G_{j1,f2})_d+(g_{j1,f2})_d^2 \\ (G_{j2,f1})_d \leftarrow (G_{j2,f1})_d+(g_{j2,f1})_d^2 \end{aligned} \tag{2} $$where d runs from 1 to k (k is a hyperparameter denoting the dimension of the latent vector)
Finally the relevant parameters are updated with:
$$ \begin{aligned} (w_{j1,f2})_d \leftarrow (w_{j1,f2})_d-\frac{\eta}{\sqrt{(G_{j1,f2})_d}}(g_{j1,f2})_d \\ (w_{j2,f1})_d \leftarrow (w_{j2,f1})_d-\frac{\eta}{\sqrt{(G_{j2,f1})_d}}(g_{j2,f1})_d \end{aligned} \tag{3} $$where $\eta$ is a hyperparameter — the learning rate. The initial values of $\mathbf{w}$ are drawn randomly from a uniform distribution over $[0,1/\sqrt{k}]$, and the initial value of G is set to 1 to prevent $(G_{j1,f2})_d^{-\frac{1}{2}}$ from becoming too large
Experiments show that normalizing each sample to a consistent length improves the training accuracy of the model, and that the model is fairly sensitive to its parameters
Overfitting strategy
The FFM model uses early stopping to prevent overfitting, with the following strategy:
- Split the dataset into a training set and a validation set
- After each training epoch, compute the model’s loss on the validation set
- If the loss increases, record the number of training epochs, stop training and go to step 4
- If needed, retrain the model on the full dataset for the number of epochs obtained in step 3
Some conclusions
Compared with the FM model, the FFM model introduces the concept of field, increasing the number of latent vectors. If n features belong to f fields, the second-order term of the FFM model has nf latent vectors, whereas FM can be regarded as a special case of FFM, namely the FFM model when all features belong to a single field
- The FFM model performs well on data that contains categorical features converted for binary classification
- If the converted dataset is not sparse enough, the FFM model may not perform very well
- The FFM model struggles to handle numerical features
The model has three hyperparameters:
- k, the dimension of the latent vectors; experiments show that its size has little effect on the model
- $\lambda$, the regularization coefficient; too large a value leads to underfitting, while too small a value easily overfits
- $\eta$, the learning rate; too large easily overfits, while too small makes the training error decrease slowly
Related libraries or frameworks:
Reference paper