Feature Selection via Block-Regularized Regression

Se Young Kim, Eric P. XingUAI 2008 · DOI

Authors: Seyoung Kim and Eric Xing

Abstract

Identifying co-varying causal elements in very high dimensional feature space with internal structures, e.g., a space with as many as millions of linearly ordered features, as one typically encounters in problems such as whole genome association (WGA) mapping, remains an open problem in statistical learning. We propose a block-regularized regression model for sparse variable selection in a high-dimensional space where the covariates are linearly ordered, and are possibly subject to local statistical linkages (e.g., block structures) due to spacial or temporal proximity of the features. Our goal is to identify a small subset of relevant covariates that are not merely from random positions in the ordering, but grouped as contiguous blocks from large number of ordered covariates. Following a typical linear regression framework between the features and the response, our proposed model employs a sparsity-enforcing Laplacian prior for the regression coefficients, augmented by a 1st-order Markovian process along the feature sequence that "activates" the regression coefficients in a coupled fashion. We describe a sampling-based learning algorithm and demonstrate the performance of our method on simulated and biological data for marker identification under WGA.

Introduction: The Challenge of High-Dimensional Genomics

In fields like genomics, researchers perform Whole Genome Association (WGA) mapping to find genetic markers (SNPs) associated with specific traits or diseases. This is a classic "high-dimensional" problem: researchers may have millions of potential features (SNPs) but only a few hundred samples.

Standard tools like the Lasso are effective at enforcing sparsity—picking only a few features and setting the rest to zero. However, they treat every feature as independent. In reality, DNA is inherited in chunks; if one SNP is associated with a disease, its neighbors are likely associated too due to Linkage Disequilibrium (LD). Existing "Group Lasso" methods can handle blocks, but they require pre-defining boundaries before analysis. This paper proposes a method to perform feature selection and discover these block boundaries simultaneously.

Methodology: The Markovian Twist

The authors frame the problem as a linear regression where the goal is to estimate a vector of coefficients ($\beta$). Their innovation lies in the prior distribution placed on these coefficients:

  1. The "Spike-and-Slab" Foundation: Each coefficient $\beta_j$ is associated with a binary indicator variable $c_j$. If $c_j = 0$, the feature is "off." If $c_j = 1$, the feature is "on," and its value is drawn from a sparsity-enforcing Laplacian distribution.
  2. The Markovian Process: Instead of treating each $c_j$ as independent, the sequence of $c_j$ values is modeled as a 1st-order Markov Chain. The probability of a feature being "on" depends on whether its neighbor was "on."
  3. Biological Integration: Transition probabilities incorporate physical distance and known recombination rates. In regions where DNA rarely breaks, the model expects $c_j$ to stay in the same state as its neighbor, effectively "fusing" them into a block.
Posterior probability P(c) of feature activation across the genome. The proposed model (a) identifies contiguous blocks of relevant features, whereas standard methods (b) produce fragmented, noisy results.

Key Results and Performance

The model was evaluated on simulated genomes and real-world mouse haplotype data (8,217 SNPs across Chromosome 4).

Superior Precision and Robustness

In simulations with strong block structures, the block-regularized model significantly outperformed the Lasso and models with independent priors. It was much better at identifying the true "causal" SNPs without picking up as many false positives. As the signal-to-noise ratio increased, the performance gap between this method and the Lasso widened, demonstrating that the block structure is a powerful "hint" for the model to ignore random noise.

Comparison of estimated regression coefficients (β) across different models. The proposed block-regularized approach (a) recovers the underlying block structure more effectively than independent prior models (d, e), which fail to capture the spatial smoothness of the signal.

Biological Validation

On mouse data regarding sodium intake preference, the model identified regions consistent with traditional statistical tests but provided a much cleaner, more interpretable "block" view of the significant genetic regions. This spatial smoothness prevents the model from picking isolated, noisy SNPs and instead focuses on robust regions of association.

Conclusion

The proposed block-regularized regression offers a powerful generalization of sparse regression. By using data and biological priors to "decide" where a block of signal starts and ends, it moves beyond the limitations of pre-defined grouping. While the current implementation relies on computationally intensive Gibbs sampling, it sets a new standard for identifying co-varying causal elements in structured, high-dimensional spaces.

Summary updated

Abstract

Identifying co-varying causal elements in very high dimensional feature space with internal structures, e.g., a space with as many as millions of linearly ordered features, as one typically encounters in problems such as whole genome association (WGA) mapping, remains an open problem in statistical learning. We propose a block-regularized regression model for sparse variable selection in a high-dimensional space where the covariates are linearly ordered, and are possibly subject to local statistical linkages (e.g., block structures) due to spacial or temporal proximity of the features. Our goal is to identify a small subset of relevant covariates that are not merely from random positions in the ordering, but grouped as contiguous blocks from large number of ordered covariates. Following a typical linear regression framework between the features and the response, our proposed model employs a sparsity-enforcing Laplacian prior for the regression coefficients, augmented by a 1st-order Markovian process along the feature sequence that "activates" the regression coefficients in a coupled fashion. We describe a sampling-based learning algorithm and demonstrate the performance of our method on simulated and biological data for marker identification under WGA.
BibTeX
@inproceedings{kim2008feature,
  author = {Se Young Kim and Eric P. Xing},
  title = {{Feature Selection via Block-Regularized Regression}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2008},
  doi = {10.48550/arxiv.1206.3268},
}
Figure