Multi-way Interacting Regression via Factorization Machines
We propose a Bayesian regression method that accounts for multi-way interactions of arbitrary orders among the predictor variables. Our model makes use of a factorization mechanism for representing the regression coefficients of interactions among the predictors, while the interaction selection is guided by a prior distribution on random hypergraphs, a construction which generalizes the Finite Feature Model. We present a posterior inference algorithm based on Gibbs sampling, and establish posterior consistency of our regression model. Our method is evaluated with extensive experiments on simulated data and demonstrated to be able to identify meaningful interactions in applications in genetics and retail demand forecasting.
interactions are observed only infrequently, subject to a constraint that the interaction order (a.k.a. interaction depth) is given. Neither SVM nor FM can perform any selection of predictor interactions, but several authors have extended the SVM by combining it with 1 penalty for the purpose of feature selection (Zhu et al., 2004) and gradient boosting for FM (Cheng et al., 2014) to select interacting features. It is also an option to perform linear regression on as many interactions as we can and combine it with regularization procedures for selection (e.g. LASSO (Tibshirani, 1996) or Elastic net (Zou & Hastie, 2005)). It is noted that such methods are still not computationally feasible for accounting for interactions that involve a large number of predictor variables.
In this work we propose a regression method capable of adaptive selection of multi-way interactions of arbitrary order (MiFM for short), while avoiding the combinatorial complexity growth encountered by the methods described above. MiFM extends the basic factorization mechanism for representing the regression coefficients of interactions among the predictors, while the interaction selection is guided by a prior distribution on random hypergraphs. The prior, which does not insist on the upper bound on the order of interactions among the predictor variables, is motivated from but also generalizes Finite Feature Model, a parametric form of the well-known Indian Buffet process (IBP) (Ghahramani & Griffiths, 2005). We introduce a notion of the hypergraph of interactions and show how a parametric distribution over binary matrices can be utilized to express interactions of unbounded order. In addition, our generalized construction allows us to exert extra control on the tail behavior of the interaction order. IBP was initially used for infinite latent feature modeling and later utilized in the modeling of a variety of domains (see a review paper by Griffiths & Ghahramani (2011)).
In developing MiFM, our contributions are the following: (i) we introduce a Bayesian multi-linear regression model, which aims to account for the multi-way interactions among predictor variables; part of our model construction includes a prior specification on the hypergraph of interactions -in particular we show how our prior can be used to model the incidence matrix of interactions in several ways; (ii) we propose a procedure to estimate coefficients of arbitrary interactions structure; (iii) we establish posterior consistency of the resulting MiFM model, i.e., the property that the posterior distribution on the true regression function represented by the MiFM model contracts toward the truth under some conditions, without requiring an upper bound on the order of the predictor interactions; and (iv) we present a comprehensive simulation study of our model and analyze its performance for retail demand forecasting and case-control genetics datasets with epistasis. The unique strength of the MiFM method is the ability to recover meaningful interactions among the predictors while maintaining a competitive prediction quality compared to existing methods that target prediction only.
The paper proceeds as follows. Section 2 introduces the problem of modeling interactions in regression, and gives a brief background on the Factorization Machines. Sections 3 and 4 carry out the contributions outlined above. Section 5 presents results of the experiments. We conclude with a discussion in Section 6.
The paper presents a Bayesian method for regression problems where the response variables can depend on multi-way combinations of the predictors. Via a hyper graph representation of the covariates interactions, the model is obtained from a refinement of the Finite Feature Model.
The idea of modelling the interactions as the hyper edges of a hyper graph is interesting but the proposed model seems to be technically equivalent to the original Finite Mixture Model. Moreover, from the experimental results, it is hard to assess if the new parametrised extension is an improvement respect to the baseline.
Here are few questions and comments:
- is the idea of modelling interactions via an unbounded membership model new? Finite Mixture Models have been already used for predicting proteins interactions in [1], what are the key differences between that work and the proposed method?
- the main motivation for modelling nonlinear interactions via multi-way regression is the interpretability of the identified model. Given the data, can one expect the nonlinear realisation to be unique? I think that a brief discussion about the identifiability of the model would improve the quality of the paper.
- can the model handle higher powers of the same predictor (something like y = z x^2)? 
- the number of true interactions is usually expected to be very small respect to the number of all possible interactions. Does the model include a sparsity constraint on the coefficients/binary matrices? Is the low-rank assumption of the matrix V related to this?
- is the factorised form of the multi-way interactions (matrix V in equation 3) expected to be flexible enough? 
- In the experiments:
i) the true coefficients were chosen at random? Was there a threshold on their magnitude? 
ii) how is the `quality’ of the recovered coefficients defined? What is the difference between this and the `exact recovery’ of the interactions? 
iii) the standard FMM model (alpha=1) performs quite well independently of the number of multi-way interactions. Was that expected?     
iv) why does the random forest algorithm perform so well in the gene dataset and badly on the synthetic dataset? Why was the baseline (Elastic net algorithm) not used on the real-world experiments?  
————————————————
[1] Krause et al. 2006 Identifying protein complexes in high-throughput protein interaction screens using an infinite latent feature model