Abstract
High-dimensional datasets with few observations ("small $n$, large $m$") present significant challenges for feature selection, particularly in multi-task learning (MTL) environments. Traditional MTL methods often enforce rigid "all-or-nothing" feature sharing across tasks, leading to noise or missed biological signals. This paper introduces the Multiple Inclusion Criterion (MIC), a penalized-likelihood method based on the Minimum Description Length (MDL) principle. MIC enables flexible, partial feature sharing across arbitrary subsets of tasks. By "borrowing strength" from related tasks, MIC produces models that are significantly sparser and more interpretable than state-of-the-art alternatives while maintaining or improving predictive accuracy.
Introduction
In fields such as genomics, researchers frequently encounter datasets where the number of potential features (e.g., genetic markers) vastly exceeds the number of observations. Multi-task learning (MTL) addresses this by solving related problems simultaneously, leveraging shared information. However, the standard approach to feature selection in MTL is often binary: a feature is either selected for all tasks or none.
This rigid assumption is often violated in practice. For instance, a specific gene might influence a subset of drug responses but be irrelevant to others. Forcing such a feature into all models introduces unnecessary noise, while treating each task independently fails to exploit the shared underlying biology. The Multiple Inclusion Criterion (MIC) provides a "middle ground," allowing for flexible, partial sharing of features across tasks.
Methodology: The Multiple Inclusion Criterion
MIC is grounded in the Minimum Description Length (MDL) principle, which treats model selection as a data compression problem. The optimal model is defined as the one that minimizes the total number of bits required to transmit both the model parameters and the data.
Two-Level Sparsity and Coding Scheme
Unlike traditional methods, MIC implements an $\ell_0 - \ell_0$ penalty structure. It determines not only if a feature is globally relevant but also specifically which tasks should include it. The total "cost" of including a feature is calculated in bits, accounting for the index of the feature, the subset of tasks that utilize it, and the precision of the coefficients.
The mathematical framework relies on several key variables defined in the table above. By optimizing the description length, MIC naturally balances model complexity and fit without requiring manual hyperparameter tuning (e.g., $\lambda$ in Lasso).
Optimization and Search
Since $\ell_0$ optimization is NP-hard, the authors employ a greedy stepwise search. To ensure computational feasibility for high-dimensional biological data, they utilize branch-and-bound techniques. This approach allows the algorithm to efficiently navigate the search space of thousands of features.
Key Insights: Borrowing Strength
The core innovation of MIC is its ability to "borrow strength." When a feature is already included in several tasks, the marginal cost (in bits) to include it in an additional related task decreases. This encourages the discovery of commonalities across tasks without mandating them.
As shown in Table 2, "Partial MIC" offers a flexible cost structure. While RIC is most efficient for features relevant to only a single task ($k=1$) and Full MIC is most efficient for features shared by all tasks ($k=h$), Partial MIC provides the optimal "middle ground" for the common case of partial sharing ($k=h/4$). Empirically, this flexibility allows Partial MIC to outperform both rigid alternatives across diverse real-world scenarios.
Experimental Evaluation
The authors evaluated MIC against several benchmarks, including BBLasso and AndoZhang, using both synthetic and real-world biological datasets.
Yeast Growth and Breast Cancer Data
On a yeast growth dataset (20 tasks, 6,715 features), Partial MIC achieved the lowest test error (0.38). More importantly, it demonstrated extreme sparsity, selecting only 4 features (22 total coefficients) to achieve this performance. In contrast, BBLasso selected 63 features (1,268 coefficients), resulting in a much less interpretable model. Similar results were observed in a breast cancer dataset, where MIC successfully identified a small, highly predictive set of gene-expression features.
Performance and Robustness
Synthetic tests confirmed that MIC maintains high precision and recall. It effectively identifies "true" underlying features while avoiding the inclusion of spurious noise, a common failure mode for competing methods in high-dimensional settings. Furthermore, the optimized search algorithm proved efficient; in one instance, MIC completed a task in a fraction of the time required by the AndoZhang method.
Conclusion and Future Work
The Multiple Inclusion Criterion represents a significant advancement in multi-task feature selection. By leveraging the MDL principle, it provides a principled, parameter-free way to discover partial sharing patterns in complex data. Its ability to produce extremely sparse yet accurate models makes it particularly valuable for biological discovery.
Future research may focus on extending the MIC framework to non-linear models or developing even faster optimization paths, such as a "regularization path" algorithm similar to LARS, to further improve scalability for massive datasets.
Summary updated