In many modern data science problems, practitioners face a "large $d$, small $n$" scenario: there are thousands of potential features (like genes in bioinformatics or pixels in image processing) but only a handful of training examples. To prevent overfitting in these high-dimensional spaces, researchers typically assume sparsity—the idea that only a small subset of features actually influences the target variable.
While traditional tools like the Lasso or the Bayesian "horseshoe prior" are excellent at enforcing sparsity, they generally treat features as independent entities. In reality, features often act in coordinated groups, such as genes operating within the same biological pathway. Existing "group feature selection" methods can handle this, but they usually require a human expert to define the groups beforehand. This paper introduces a probabilistic model that tackles the challenge of inducing those dependency structures automatically from the training data itself, leveraging multi-task learning.
Methods: Extending the Horseshoe Prior
The authors build their approach on the horseshoe prior, a popular Bayesian tool for sparsity characterized by an infinitely tall "spike" at zero (to aggressively squash irrelevant coefficients) and "heavy tails" (to allow relevant coefficients to remain large without over-penalization).
To move beyond independent feature selection, the authors introduce several key innovations:
- Latent Dependency Modeling: They decompose the standard horseshoe prior into a ratio of latent Gaussian variables. By introducing a correlation matrix ($C$) between these latent variables, the model can capture dependencies in the feature selection process itself.
- Low-Rank Parameterization: Estimating a full $d \times d$ correlation matrix is statistically impossible when $d$ is large and $n$ is small (the curse of dimensionality). To solve this, they parameterize $C$ using a low-rank approximation, reducing the parameter count from $O(d^2)$ to $O(md)$.
- Multi-task Learning (MTL) Integration: To further combat overfitting, the model assumes that multiple related tasks share the same underlying feature dependency structure ($C$). Crucially, while the rules for which features are related are shared, the specific relevant features and their coefficients can still differ between tasks.
- Expectation Propagation (EP): Because exact Bayesian inference is mathematically intractable for this complex model, the authors employ Expectation Propagation—a sophisticated approximation technique—to keep computations efficient at an $O(Kn^2d)$ complexity.
Experiments and Key Insights
The model, dubbed HSDep, was evaluated on two primary types of data to test its ability to discover hidden structures:
- Synthetic Data: The authors generated 64 tasks where features were organized into hidden groups of 8. The goal was to see if the model could recover the underlying block-diagonal correlation matrix without prior knowledge.
- MNIST Handwritten Digits: The model was tasked with reconstructing images of the digits '3' and '5', treating individual pixels as features. The objective was to see if the model could learn spatial dependencies (e.g., recognizing that neighboring pixels are often relevant or irrelevant together).
Key Results
HSDep consistently outperformed several benchmarks, including the standard independent horseshoe (HSST), joint feature selection (HSMT), and "dirty models" (DM).
- Synthetic Accuracy: As shown in the results table, HSDep achieved a reconstruction error of 0.21, significantly lower than the next best competitor, the Boltzmann Machine-based model (BM, 0.24), and vastly outperforming the independent task approach (HSST, 0.29).
- Structure Recovery: The qualitative success of the model is evident in the estimated correlation matrices. The model successfully recovered the block-diagonal structures in the synthetic tests, effectively "discovering" the feature groups that other models would need to be explicitly told about upfront.
- Spatial Awareness in MNIST: On the image data, HSDep reached an error of 0.20, while the standard independent horseshoe lagged at 0.36. The model learned that if one pixel is relevant for identifying a digit, its neighbors likely are too. It induced a spatial correlation map purely from the regression task, without relying on explicit "image-aware" architectures like Convolutional Neural Networks.
Limitations and Future Work
While Expectation Propagation makes the model tractable, the $O(Kn^2d)$ computational cost means it might struggle with very large sample sizes ($n$) per task. However, it excels in the "small $n$" regime it was specifically designed for.
Currently, the model assumes a linear relationship between features and targets. Extending this framework to non-linear or deep architectures represents a powerful next step. Additionally, the authors suggest that applying this approach to "sparse coding"—where the feature matrix itself is unknown and must be learned alongside the dependencies—is a highly promising avenue for future research.
Summary updated