High-order covariate interacted Lasso for feature selection

Lasso-type feature selection has been demonstrated to be effective in handling high dimensional data. Most existing Lasso-type models over emphasize the sparsity and overlook the interactions among covariates. Here on the other hand, we devise a new regularization term in the Lasso regression model to impose high order interactions between covariates and responses. Specifically, we first construct a feature hypergraph to model the high-order relations among covariates, in which each node corresponds to a covariate and each hyperedge has a weight corresponding to the interaction information among covariates connected by that hyperedge. For the hyperedge weight, we use multidimensional interaction information (MII) to measure the significance of different covariate combinations with respect to response. Secondly, we use the feature hypergraph as a regularizer on the covariate coefficients which can automatically adjust the relevance measure between a covariate and the response by the interaction weights obtained from hypergraph. Finally, an efficient alternating direction method of multipliers (ADMM) is presented to solve the resulting sparse optimization problem. Extensive experiments on different data sets show that although our proposed model is not a convex problem, it outperforms both its approximately convex counterparts and a number of state-of-the-art feature selection methods.