Sparse Partitioning

Sparse Partitioning is a Bayesian regression method for identifying predictors that either individually or in combination with others affect a response variable. The method can be applied to any regression problem with binary or tertiary predictors. It is particularly aimed at high dimensional problems in which the number of predictors greatly exceeds the number of individuals. The method is described in detail in the following paper:

"Sparse Partitioning: A method to detect interactions in high dimensional regression problems with binary or tertiary predictors".

The pages on this website provide the source files for the method, accompanied by user instructions and two simple examples. In addition, the code used to generate the simulated datasets featured in the methodology paper is provided along with some of the simulated datasets.

Brief Outline of Sparse Partitioning

Consider a regression problem with n individuals and N predictors. Let the matrix Y (size n x 1) contains the responses and the matrix X (size n x N) contains the predictors. For the ith individual, Y_i denotes its response while X₁, X₂, ..., X_N denote its predictor values. The aim is to identify which predictors influence the response.

We suppose the response and the predictors are related by

E(Y) = l^-1 f(X).

where l is a link function (when the responses are continuous, this is the identity function; when the responses are binary, this is the logit function). We wish to identify details of the function f. In particular, we are interested in which predictors have an effect on the value f(X).

Sparse Partitioning considers the partitioning of the predictors defined by the function f. For example, consider a five predictor problem, with underlying relationship

f(X) = X₁ x X₂ + X₃.

The predictor set {1, 2, 3, 4, 5} can be partitioned as {G₀, G₁, G₂} = {{4,5}, {1, 2}, {3}}, where G₀ contains those predictors which make no contribution to f, while G₁ and G₂ contain groups of predictors that contribute.

Formally, the partitioning will take the form {1, 2, ..., N} = {G₀, G₁, G₂, ..., G_K}. G₀ contains predictors not associated with the response, while G₁, G₂, ..., G_K are groups of associated predictors. Interactions are permitted between predictors within the same group (in the example above, predictors 1 and 2 interact) but not between predictors across different groups. Therefore the underlying relationship can be written as

f(X) = f₁(X_G1) + f₂(X_G2) + ... + f_K(X_GK).

Sparse Partitioning searches for partitionings which have high posterior probabilities in light of the data.

It is suggested first time visitors visit the links below from left to right.