Accurate and Interpretable Factorization Machines

Liang Lan, Yu GengAAAI 2019 · DOI

Introduction

Factorization Machines (FMs) are widely used in machine learning for their ability to model high-order feature interactions efficiently. However, standard FMs face two significant hurdles: limited expressiveness and a lack of interpretability. Because they rely on polynomial expansions, they struggle with complex, non-polynomial patterns—such as concentric circles—and remain "black box" models where learned weights are difficult for humans to decipher.

To address these issues, we introduce Subspace Encoding Factorization Machines (SEFM). This model enhances standard FMs to capture complex nonlinear patterns while maintaining the linear-time efficiency and transparency of a scoring system.

Methodology: Subspace Encoding

The core innovation of SEFM is the Subspace Encoding technique. Instead of processing raw numerical values, the model discretizes the range of each continuous feature into $b$ equal-length "bins."

  1. Binning and One-Hot Encoding: Each feature is transformed into a sparse binary vector. Only the entry corresponding to the active bin is set to 1.
  2. Feature Mapping: As illustrated in Figure 1, this transformation maps input features into a high-dimensional subspace where interactions are modeled between discrete intervals.
  3. FM Integration: By applying a standard Factorization Machine to this binned representation, the model effectively learns contribution scores for every bin and every "grid cell" (the intersection of two bins from different features).
Subspace encoding process mapping features to discrete bins.

Unlike previous iterative binning methods, SEFM's fixed-length strategy allows it to utilize highly optimized FM solvers, maintaining a training complexity of $O(d)$, where $d$ is the number of features.

Experimental Evaluation

The performance of SEFM was evaluated against synthetic and real-world benchmarks:

  • Synthetic Data: Circles and Moons datasets were used to visualize decision boundaries in non-linearly separable 2D spaces.
  • Real-World Data: Five datasets from the Libsvm repository, including breast-cancer, splice, ijcnn, cod-rna, and webspam.

Key Results and Discussion

SEFM demonstrates a significant leap in accuracy over standard FMs. On synthetic datasets like Circles, standard FMs often fail to find the correct boundary, whereas SEFM achieves near 100% accuracy, comparable to the performance of SVMs with RBF kernels.

Comparison of decision boundaries for Liblinear, Libsvm-rbf, FM, and SEFM on the Circles dataset.

Performance and Efficiency

  • Accuracy: SEFM consistently outperformed linear models and standard FMs across all tested datasets. It matches the non-linear modeling power of RBF-SVMs while remaining computationally lighter.
  • Computational Speed: SEFM is significantly faster than other non-linear variants like Locally Linear Factorization Machines (LLFM). For instance, on the ijcnn dataset, SEFM trained in approximately 3.4 seconds, compared to over 106 seconds for LLFM.
  • Interpretability: The model functions as a "scoring system." Because it sums scores from specific bins and grid cells, the final prediction can be decomposed into human-readable components, similar to a medical diagnostic sheet.

Conclusion

SEFM bridges the gap between the high accuracy of kernel-based methods and the efficiency of linear models. By leveraging subspace encoding, it provides a non-parametric approach that is both powerful and interpretable. Future work may explore more sophisticated binning strategies, such as density-based discretization, to further refine performance on highly skewed data.

Summary updated

BibTeX
@inproceedings{lan2019accurate,
  author = {Liang Lan and Yu Geng},
  title = {{Accurate and Interpretable Factorization Machines}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33014139},
}
Figure