PaperlayerView exact revision on arXiv

Source-linked AI summary

Higher-Order Factorization Machines

Mathieu Blondel, Akinori Fujino, Naonori Ueda, Masakazu Ishihata

arXiv:1607.07195v2stat.MLcs.LG

TL;DR

HOFMs lacked efficient algorithms for training arbitrary-order feature interactions, limiting their use despite the advantages of factorization machines. This paper develops ANOVA-kernel dynamic-programming methods for stochastic-gradient and coordinate-descent training, plus shared-parameter variants. Across four link-prediction tasks, HOFM and HOFM-shared-augmented achieved the best scores on three datasets, with the shared variant maintaining similar accuracy using a smaller model.

  • Problem

    Arbitrary-order HOFMs lacked efficient training algorithms, while naive prediction was polynomial-time and separate factor matrices required many parameters.

  • Method

    The paper uses ANOVA-kernel dynamic programming for linear-time evaluation and gradients, develops stochastic-gradient and coordinate-descent solvers, and introduces shared-parameter variants.

  • Results

    HOFM and HOFM-shared-augmented achieved the best scores on 3 out of 4 datasets, while HOFM-shared-augmented achieved similar accuracy to HOFM with a smaller model.

  • Takeaways & Limitations

    Shared-parameter HOFMs can reduce model size and prediction cost while maintaining similar accuracy to HOFM in the reported link-prediction experiments.

  • Takeaways & Limitations

    The inhomogeneous-kernel experiments set β1 = · · · = βm and k2 = · · · = km to avoid searching combinatorial hyper-parameter combinations.

Abstract

from arXiv · show

Factorization machines (FMs) are a supervised learning approach that can use second-order feature combinations even when the data is very high-dimensional. Unfortunately, despite increasing interest in FMs, there exists to date no efficient training algorithm for higher-order FMs (HOFMs). In this paper, we present the first generic yet efficient algorithms for training arbitrary-order HOFMs. We also present new variants of HOFMs with shared parameters, which greatly reduce model size and prediction times while maintaining similar accuracy. We demonstrate the proposed approaches on four different link prediction tasks.

1 Introduction

FMs efficiently model second-order feature combinations in high-dimensional data, but arbitrary-order HOFMs lacked efficient training and prediction procedures. The paper addresses this gap with efficient algorithms and shared-parameter variants.

  • 1 Introduction: FMs efficiently use second-order feature combinations in very high-dimensional data.They model combination weights with a low-rank matrix, enabling smaller and faster models than polynomial regression or kernel methods.
  • 1 Introduction: Arbitrary-order HOFMs had no efficient training algorithm, and naive prediction required polynomial time in the number of features.This prevented HOFMs from being applied to problems.
  • 1 Introduction: The paper presents efficient arbitrary-order HOFM algorithms and shared-parameter variants evaluated on four link prediction tasks.The algorithms use ANOVA-kernel dynamic programming for evaluation and gradients, while the variants reduce parameters and prediction time.

2 Factorization machines (FMs)

This section introduces FMs and HOFMs as low-rank models of distinct-feature combinations, then motivates ANOVA kernels as a computational perspective. Higher orders increase parameter requirements and create the need for efficient computation and parameter sharing.

  • Second-order FMs: Second-order FMs use a low-rank factorization to model interactions among distinct features.Their parameter count is O(dk) rather than O(d^2), and predictions can be computed in O(2dk) time.
  • Second-order FMs: FMs learn parameters by minimizing a non-convex regularized objective, with stochastic-gradient and coordinate-descent solvers available.The libfm implementations have per-epoch complexity O(2dkn).
  • Higher-order FMs: HOFMs extend FMs to feature combinations of orders 2 through m, using a separate factor matrix P^(t) for each order.The original formulation therefore requires m−1 matrices.
  • ANOVA-kernel perspective: The ANOVA kernel provides a kernel-machine view of FMs and HOFMs while restricting combinations to distinct features.Its key property is multi-linearity, and it can be interpreted as a polynomial kernel without replacement.
  • This paper: Naively evaluating an m-order HOFM takes O(d^m), while separate matrices can produce large models as m grows.The paper proposes linear-time algorithms and shared-parameter HOFM variants to address these costs.

3 Linear-time stochastic gradient algorithms for HOFMs

The paper evaluates ANOVA kernels and their gradients with dynamic programming, enabling stochastic-gradient training of arbitrary-order HOFMs in linear time with respect to features and order.

  • Evaluation: Dynamic programming recursively evaluates the ANOVA kernel in O(dm) time and memory.A bottom-up table avoids the redundant computations caused by naive recursion.
  • Gradients: Reverse-mode differentiation computes the entire ANOVA-kernel gradient in O(dm) time and memory.The method propagates adjoints backward through the dynamic-programming table.
  • Stochastic gradient algorithms: Stochastic-gradient updates alternate over factor matrices and use the kernel gradient for each sampled instance.The subproblem for each degree is convex in each row of its factor matrix.
  • Stochastic gradient algorithms: O(m d k n) per epoch is the stochastic-gradient cost for arbitrary-order HOFMs, matching libfm when m = 2.This follows because kernel evaluation and gradient computation each cost O(dm).
  • Sparse data: Sparse inputs allow kernel and gradient computations to use only the nonzero feature support.The gradient has the same support as the input, and the kernel depends only on nonzero features when m ≤ nz(x).

4 Coordinate descent algorithm for arbitrary-order HOFMs

The coordinate-descent solver uses an alternative ANOVA-kernel recursion that avoids storing full dynamic-programming tables per sample. It reduces memory per sample but retains quadratic dependence on the maximum order, making it most suitable for small m.

  • Coordinate descent motivation: The original recursion is unsuitable for coordinate descent because coordinate updates would require synchronizing each sample’s dynamic-programming table.The paper therefore introduces an alternative recursion.
  • An alternative recursion: The alternative recursion evaluates arbitrary-order ANOVA kernels in O(md + m^2) time.It computes successive kernel degrees from A0(p, x) = 1 and A1(p, x) = ⟨p, x⟩.
  • Coordinate-wise derivatives: Caching D_t(p, x) reduces coordinate-descent memory complexity per sample to O(m) instead of O(dm).Forward-mode differentiation computes only the derivative of the coordinate being updated.
  • Use in a CD algorithm: The coordinate-descent update is monotonically non-increasing in objective value and is the exact coordinate-wise minimizer for squared loss.Its total epoch cost is O(τ(m)knz(X)), with τ(m) = m(m+1)/2−1 operations for the derivative computation.
  • Use in a CD algorithm: Because the coordinate-descent cost is quadratic in m, the algorithm is best suited to small orders, typically m ≤ 4.This boundary follows from the stated τ(m) dependence.

5 HOFMs with shared parameters

Shared-parameter HOFM variants combine multiple ANOVA degrees while reducing model size and prediction or gradient-computation costs. The all-subsets kernel further supports all distinct-feature combinations with uniform weights and O(d)-time evaluation and gradients.

  • Motivation: Separate degree-specific HOFM matrices require O(kdm) parameters and make prediction cost O(kdm^2).This motivates sharing parameters across degrees to reduce both storage and evaluation expense.
  • Inhomogeneous ANOVA kernel: The inhomogeneous ANOVA kernel combines degrees 1 through m using shared parameters with separately weighted kernels θ1, ..., θm.Unlike the homogeneous ANOVA kernel, it includes all degrees up to m and allows degree-specific weights.
  • Inhomogeneous ANOVA kernel: Recursive dynamic programming provides all lower-degree kernels while evaluating the inhomogeneous ANOVA kernel in O(dm) time.The same recursion exposes A1(p, x), ..., Am−1(p, x) in the final dynamic-programming-table column.
  • Learning shared parameters: Adding m−1 dummy features converts the homogeneous kernel Am into the inhomogeneous kernel A1→m, enabling automatic learning of the degree weights.The resulting augmented-data gradient costs O(dm + m^2), compared with O(dm^2) for separate-parameter HOFMs.
  • All-subsets kernel: The all-subsets kernel uses all distinct-feature combinations up to the number of nonzero features, with uniform weights, and learns its parameter vector p.It can be substituted into the training objective and gradient algorithms in place of Am.
  • All-subsets kernel: The all-subsets kernel and its gradient can each be evaluated in O(d) time.This provides its main computational advantage, particularly when instances are sparse even in very high-dimensional spaces.

6 Experimental results

The experiments evaluate HOFMs for link prediction and compare their solvers and model variants. HOFM and HOFM-shared-augmented achieve the strongest overall performance, while shared parameters reduce model size without sacrificing similar accuracy.

  • Application to link prediction: HOFMs convert link prediction into supervised learning by concatenating the feature vectors of two nodes and predicting their link.Positive and negative node pairs form the training examples.
  • Compared models: The compared models include standard HOFM, shared-parameter HOFMs, all-subsets, polynomial networks, and low-rank bilinear regression.The shared variants use ANOVA-derived kernels, while the baselines include bilinear and polynomial alternatives.
  • Experimental setup: The evaluation measures test-set area under the ROC curve using equal numbers of sampled positive and negative training examples, with k = 30.The regularization parameter β is selected by cross-validation.
  • Link-prediction results: HOFM and HOFM-shared-augmented achieved the best scores on 3 out of 4 datasets and outperformed low-rank bilinear regression on 3 out of 4 datasets.HOFM-shared-augmented matched HOFM accuracy despite using a smaller model.
  • Link-prediction results: HOFM-shared-simplex generally did not improve over HOFM-shared-augmented, while all-subsets and polynomial networks were usually worse except on GD.The GD dataset was the exception for both comparisons.
  • Solver comparison: Coordinate descent performs well for m ≤3 but deteriorates for m ≥4, when L-BFGS becomes advantageous.AdaGrad and L-BFGS have per-epoch costs that scale linearly with m, but AdaGrad diverged for learning rates 1, 0.1, and 0.01.

7 Conclusion and future directions

The paper presents training algorithms for HOFMs and shared-parameter variants, then identifies extensions to AUC optimization, distributed training, and deep-learning frameworks. These directions build on the proposed stochastic-gradient and dynamic-programming algorithms.

  • Conclusion: The paper presents the first training algorithms for HOFMs and introduces HOFM variants with shared parameters.The conclusion restates the paper’s two central contributions.
  • Future directions: The algorithms are expected to be especially useful for objectives that directly maximize AUC because stochastic-gradient updates can sample positive-negative pairs.The conclusion also notes that a distributed second-order FM algorithm should be extendable to HOFMs.
  • Future directions: The dynamic-programming algorithms could be integrated into deep-learning frameworks to compose ANOVA kernels with other layers.TensorFlow is given as an example framework.

A Dataset descriptions

The experiments use four link-prediction datasets spanning co-author, metabolic-network, gene-disease, and recommender-system tasks. Each dataset represents nodes with feature vectors and defines positive links from domain-specific observations or thresholds.

  • NIPS: NIPS is a co-author graph with 2,037 authors represented by 13,649-dimensional bag-of-words vectors and 4,140 positive samples.For NIPS, the two node feature matrices are identical.
  • Enzyme: Enzyme is a metabolic network with 668 enzymes represented by concatenated phylogenetic, gene-expression, and gene-location features.The three feature groups total 325 dimensions, and similarity scores are binarized at 0.95.
  • Gene-Disease: Gene-Disease contains 3,209 diseases and 12,331 genes represented by similarity-based and feature vectors.Disease representations use MimMiner similarity scores, while gene representations use 25,275 features.

B Additional experiments

Additional solver experiments compare AdaGrad, L-BFGS, and coordinate descent on the Enzyme, Gene-Disease, and Movielens 100K datasets. The results are reported in Figures 2, 3, and 4, respectively.

  • Additional experiments: AdaGrad, L-BFGS, and coordinate descent were compared on Enzyme, Gene-Disease, and Movielens 100K.The corresponding results appear in Figures 2, 3, and 4.

B.2 Recommender system experiments

The experiments compare solvers and models across graph-link and recommender-system tasks, while the paper develops efficient reverse-mode differentiation for higher-order recursions. On Movielens 1M and Last.fm, All-subsets performs relatively well.

  • Model comparisons: For Movielens 1M and Last.fm, the study compares recommender-system models using the same setting as prior work.Each rating vector concatenates one-hot encodings of the user and item indices.
  • Model comparisons: All-subsets performs relatively well on the two recommender-system tasks.The comparison results are reported in Figure 5.
  • Efficient differentiation: Reverse-mode differentiation computes the entire gradient of the alternative recursion efficiently, with total cost O(dm + m2).The procedure computes adjoints in reverse order and then forms ∇Am(p, x); the stated cost assumes the recursion quantities were previously computed.
  • Efficient differentiation: A Vandermonde-matrix multiplication reduces the cost of one gradient step to O(d log2 m) when m ≤ d.The reduction uses the Moenck-Borodin algorithm.
Loading 1607.07195v2…