Abstract
We propose a model for multiclass classification of time series to make a prediction as early and as accurate as possible. The matrix sequential probability ratio test (MSPRT) is known to be asymptotically optimal for this setting, but contains a critical assumption that hinders broad real-world applications; the MSPRT requires the underlying probability density. To address this problem, we propose to solve density ratio matrix estimation (DRME), a novel type of density ratio estimation that consists of estimating matrices of multiple density ratios with constraints and thus is more challenging than the conventional density ratio estimation. We propose a log-sum-exp-type loss function (LSEL) for solving DRME and prove the following: (i) the LSEL provides the true density ratio matrix as the sample size of the training set increases (consistency); (ii) it assigns larger gradients to harder classes (hard class weighting effect); and (iii) it provides discriminative scores even on class-imbalanced datasets (guess-aversion). Our overall architecture for early classification, MSPRT-TANDEM, statistically significantly outperforms baseline models on four datasets including action recognition, especially in the early stage of sequential observations.
Introduction: The Speed-Accuracy Tradeoff
In time-critical applications—such as medical diagnosis from sensor streams or threat detection in surveillance—waiting for a complete data sequence is often impossible. The goal is to classify incoming data as early as possible without sacrificing accuracy, a challenge known as the Speed-Accuracy Tradeoff (SAT).
While the Matrix Sequential Probability Ratio Test (MSPRT) is a theoretically optimal statistical tool for this task, its reliance on known probability density functions makes it impractical for complex, high-dimensional data like video. Researchers from NEC Corporation have addressed this by bridging the gap between MSPRT's theoretical optimality and the representational power of deep learning.
Bridging Theory and Practice: Density Ratio Matrix Estimation
The core innovation lies in reframing the problem as Density Ratio Matrix Estimation (DRME). Instead of modeling the complex probability densities directly, the proposed framework trains neural networks to estimate the Log-Likelihood Ratios (LLRs) between all pairs of classes.
By estimating these ratios, the model can leverage the MSPRT algorithm's decision-making logic. A classification is made as soon as one of the estimated LLRs crosses a predefined threshold, optimizing the "hitting time" for a desired error rate.
The Log-Sum-Exp Loss (LSEL)
To solve the DRME problem effectively, the authors introduced the Log-Sum-Exp Loss (LSEL). This loss function possesses three mathematically proven properties that make it superior for early classification:
- Consistency: The estimated ratios converge to the true mathematical ratios as training data increases.
- Hard Class Weighting: The loss function naturally assigns larger gradients to "hard" classes—those that are easily confused—forcing the model to focus on the most difficult distinctions.
- Guess-Aversion: It remains robust against class imbalance, preventing the model from defaulting to the most frequent class when evidence is sparse.
A key insight is that the standard logistic loss (a "sum-log-exp" form) is a weaker variant of LSEL. By placing the logarithm outside the summation, LSEL becomes significantly more sensitive to challenging examples, leading to faster convergence and better SAT optimization.
MSPRT-TANDEM Architecture
The MSPRT-TANDEM architecture integrates these concepts into a deep learning pipeline. It utilizes a temporal integrator (such as an LSTM) to process sequential features. These features are then converted into LLR matrices using a specialized "TANDEM formula" based on an N-th order Markov approximation. This approach avoids the vanishing gradient issues often encountered when training recurrent networks on long sequences.
One of the most significant practical advantages of MSPRT-TANDEM is its post-training flexibility. Unlike traditional models that require retraining for different speed or accuracy requirements, MSPRT-TANDEM allows users to adjust the SAT simply by changing the decision threshold after the model is trained.
Experimental Results
The framework was evaluated on four datasets: noisy variants of MNIST (NMNIST-H and NMNIST-100f) and real-world action recognition datasets (UCF101 and HMDB51).
As shown in the results, MSPRT-TANDEM consistently outperformed established baselines, including reinforcement learning approaches like EARLIEST. On the NMNIST-100f dataset, the model achieved high accuracy significantly faster than competitors, reaching 90% accuracy at a stage where the visual data would still be unclassifiable by humans. Statistical analysis confirmed that these performance gains are significant across all tested scenarios.
Conclusion
By combining the statistical optimality of MSPRT with a novel loss function designed for density ratio estimation, MSPRT-TANDEM provides a robust solution for early time-series classification. Its ability to handle hard classes, resist class imbalance, and offer post-training flexibility makes it a powerful tool for real-world applications where every millisecond counts.
Summary updated