TL;DR
This paper introduces novel online and batch algorithms designed to handle datasets with missing features, a common problem in real-world applications. The proposed methods offer theoretical guarantees and demonstrate superior performance compared to existing imputation techniques on various benchmark datasets.
What Problem Does This Paper Address?
Many machine learning algorithms assume that all training examples are complete, meaning every feature is observed for every data point. However, in practice, datasets often suffer from missing or corrupted features due to various reasons like sensor failures, survey non-response, or occluded images. Standard approaches often involve imputing missing values before applying a learning algorithm, which can be suboptimal. This paper tackles the challenge of learning effectively directly from data with missing features, considering both adversarial and stochastic scenarios.
Methods
The authors propose two main algorithmic frameworks:
- Online Learning with Missing Features: This setting deals with data arriving sequentially, where both the data points and the missing features can be chosen adversarially. The key innovation here is a corruption-dependent hypothesis, where the predictor's weight vector can change based on which features are observed. This allows for more flexible and robust predictions compared to using a fixed hypothesis. They develop a mirror-descent-based algorithm with theoretical regret bounds.
- Batch Learning with Missing Features: In this setting, data is assumed to be drawn from a fixed, unknown distribution. The authors propose a novel imputation-based approach that jointly learns an imputation function (to fill in missing values) and a classification/regression hypothesis. They tackle the non-convexity of this joint optimization problem by introducing a convex relaxation using semi-definite programming. This leads to the "Imputed Ridge Regression" (IRR) algorithm.
Datasets
The algorithms were evaluated on several standard UCI repository datasets:
- Abalone
- Housing
- Optdigits
- Park
- Thyroid
- Splice
- Wine
The paper also discusses two types of artificial corruption introduced for experiments:
- Data-independent corruption: Features are randomly deleted independently.
- Data-dependent corruption: Features are deleted based on thresholding values.
The thyroid dataset is noted as having naturally occurring missing features.
Key Insights and Ideas
- Corruption-Dependent Hypotheses are Crucial: The paper strongly argues that simply using a fixed hypothesis on corrupted data is insufficient. Allowing the hypothesis to adapt to the observed features (i.e., the corruption pattern) is key to achieving robust performance.
- Joint Learning Outperforms Separate Imputation: By jointly learning the imputation and prediction functions, the algorithms can leverage the structure of the missingness to improve overall performance, rather than treating imputation as a pre-processing step.
- Convex Relaxation for Batch Learning: The non-convexity of jointly learning imputation and prediction is a significant hurdle. The proposed convex relaxation for batch learning provides a tractable way to find a good approximate solution.
- Theoretical Guarantees: The paper provides theoretical bounds on the regret for the online algorithm and generalization error for the batch algorithm, offering confidence in their performance.
Key Results
- Online Algorithm: Achieved regret bounds on the order of $O(\sqrt{T})$, where $T$ is the number of examples.
- Batch Algorithm (IRR): Demonstrated superior performance over baseline methods (zero-imputation, mean-imputation) on several datasets, especially under data-dependent corruption. For instance, on the splice dataset with independent corruption, the "sparse-reg" method (a variant of the online algorithm) showed significant improvement. The IRR algorithm also showed consistent improvement across various datasets and corruption levels.
- Empirical Performance: The proposed algorithms generally outperformed standard imputation methods, indicating the effectiveness of learning with missing features directly.
Limitations and Future Work
- Computational Cost of Batch Relaxation: The paper notes that standard Semi-Definite Programming (SDP) solvers can be slow for the convex relaxation in the batch setting, leading them to use a semi-infinite linear program (SILP) for approximation.
- Generalization of Batch Hypothesis Class: While the convex relaxation provides a tractable solution, the paper acknowledges that the resulting hypothesis class might be strictly more general than what can be achieved by a linear predictor and an imputation matrix.
- Future Work: The paper suggests exploring more complex interaction models between features and corruption patterns, as well as investigating the application of these methods to other learning tasks beyond classification and regression. The theoretical analysis could also be extended to more general settings.
Summary updated