Abstract
This paper introduces a simple yet powerful online classification framework based on maximizing the mutual information between features and labels. By treating classification as a search for the label that creates the cleanest statistical signal in a co-occurrence matrix, the authors develop highly efficient algorithms for standard online learning, abstention, and active learning. These methods rival or exceed the performance of state-of-the-art online learners without requiring complex hyperparameter tuning, making them highly practical for large-scale, high-dimensional data streams.
Introduction
In real-world applications, data often arrives in continuous streams (online learning), and obtaining ground-truth labels can be prohibitively expensive (active learning). Traditional classifiers typically rely on complex geometric or probabilistic models that require careful tuning of trade-off parameters to maintain performance. This paper addresses two primary challenges: quantifying uncertainty to enable intelligent abstention or label requests, and reducing parameter sensitivity to create a more robust "out of the box" classifier.
The core insight is that correct labels sharpen the statistical dependency between features and classes, while incorrect labels introduce noise. By maximizing the Mutual Information ($I_{fl}$) between features and labels, the model effectively finds the most organized version of the data.
Methods
The proposed framework centers on a co-occurrence matrix $C$ where rows represent features and columns represent labels. A high-quality classification results in a clear block structure within this matrix, which is quantified by mutual information.
The Algorithms
- oMaxI (Online Max Information): For each new instance, the algorithm evaluates every possible label and selects the one that maximizes the mutual information of the updated co-occurrence matrix.
- oAbMaxI (Abstain): The model calculates an uncertainty score based on the difference between the best and second-best labels. If the difference is below a threshold, the model abstains from prediction to maintain high precision.
- oAcMaxI (Active): In an active learning context, the model requests the true label only when its internal uncertainty score is high.
To ensure the approach is viable for high-speed streams, the authors derived a local update rule based on the Sequential Information Bottleneck (sIB) technique. This reduces the computational complexity to $O(N_l N_f)$, where $N_l$ is the number of labels and $N_f$ is the number of features.
Experimental Setup
The authors evaluated the framework on five diverse text classification corpora, ranging from medium-sized datasets like 20 Newsgroups (20NG) and Reuters-21578 to large-scale datasets like the full RCV1 (800k+ documents) and a .gov web crawl (700k+ documents). These datasets present significant challenges due to their high dimensionality and multi-label nature.
Key Results
In standard online learning scenarios, oMaxI demonstrated superior or competitive accuracy compared to established benchmarks such as Perceptron (Per), Passive-Aggressive (PA), and Adaptive Regularization of Weight Vectors (AROW). Notably, oMaxI was significantly more robust on the multi-labeled RCV1 dataset, where other methods often suffered from low recall.
Beyond raw accuracy, the active learning variant (oAcMaxI) proved remarkably efficient. On the RCV1 dataset, it achieved high accuracy while requesting labels for less than 4% of the documents. Furthermore, the uncertainty-based abstention mechanism allowed for precise control over the precision-recall trade-off; for instance, on the 20NG dataset, precision increased from 76% to 87% by abstaining on the most uncertain third of the data.
Conclusion and Future Work
The information-maximization approach provides a principled, parameter-free alternative to traditional online classifiers. While the current derivation assumes a single-label assignment, the method's strong performance on multi-label datasets suggests it is a robust proxy for data structure. Future work includes extending the theory to explicitly handle multi-label assignments and exploring "batch mode" processing to further enhance accuracy.
Summary updated