Multiple Instance Learning for Efficient Sequential Data Classification on Resource-constrained Devices

Don Dennis, Chirag Pabbaraju, Harsha Vardhan Simhadri, Prateek JainNeurIPS 2018 · OpenReview

Introduction

Researchers from Microsoft Research India have developed EMI-RNN, a framework that makes complex sequential data classification (like speech or gesture recognition) up to 72x more efficient. By combining Multiple Instance Learning (MIL) with early-prediction strategies, they enable high-accuracy deep learning on "tiny" devices like Arduinos and Raspberry Pi Zeros that were previously too resource-constrained to handle standard LSTMs.

The Challenge of Always-On Edge Devices

The Internet of Things (IoT) relies heavily on "always-on" sensors—such as a wristband detecting a gesture or a smart speaker listening for a wake-word. Traditionally, these tasks use a "sliding window" approach: the device constantly captures a chunk of data and runs a Recurrent Neural Network (RNN) or LSTM to see if an event occurred.

However, this approach is incredibly wasteful for two main reasons:

  1. Signature Sparsity: The actual "signature" of an event (like saying "Hey Cortana") usually occupies only a tiny fraction of the captured window. The rest is just background noise.
  2. Resource Constraints: Tiny edge devices have very little RAM and processing power. Running a full LSTM over long windows of high-frequency data is often computationally impossible or drains the battery instantly.

The authors aim to bridge this gap by creating a model that only looks for the "important" parts of the data and stops processing as soon as it's confident in a prediction.

The EMI-RNN Approach

The authors propose a two-pronged approach called EMI-RNN (Early Multi-Instance RNN) to tackle these inefficiencies:

Multiple Instance Learning for sequential data
  • MI-RNN (Multiple Instance Learning): Instead of treating a long sequence as one giant data point, the model treats it as a "bag" of smaller, overlapping "instances" (sub-windows). During training, the algorithm learns to identify which specific sub-windows actually contain the class signature. It uses an iterative thresholding technique to refine these labels, effectively "pruning" the noise out of the training process.
  • E-RNN (Early Prediction): Standard LSTMs usually make a prediction only after seeing the entire sequence. E-RNN is trained to predict at every time step. If the model’s confidence passes a certain threshold early on, it "short-circuits" and exits, saving the remaining computation.
  • EMI-RNN (The Hybrid): This combines both techniques. It uses MIL to find the most "signature-dense" windows and then applies early prediction to those windows to minimize the lag and compute cost.

Crucially, this method is "architecture-agnostic," meaning it can be wrapped around LSTMs, GRUs, or even CNN-LSTMs.

Key Insights

  • Noise is the Majority: In real-world IoT, "no-event" (noise) is the most common state. The authors found that noise can be identified very quickly—often within the first few time steps—allowing the device to stay in a low-power state most of the time.
  • MIL as a Denoiser: By using Multiple Instance Learning, the model doesn't just learn to classify; it learns where the important information is. This actually improved accuracy over baseline LSTMs because the model stopped trying to find "meaning" in the background noise.
  • Theoretical Breakthrough: The paper provides a mathematical analysis showing that their MIL algorithm converges to a global optimum at a linear rate in simple settings. This is a significant theoretical contribution to the field of non-homogeneous MIL, which is usually considered NP-hard.

Results and Performance

The researchers evaluated EMI-RNN on five diverse sequential datasets: HAR-6 (human activity), Google-13 (keyword spotting), STCI-2 (wake-word detection), GesturePod-6 (gesture recognition), and DSA-19 (daily sensing).

Accuracy gain vs. Computation saved across datasets
  • Massive Speedups: On the GesturePod-6 benchmark, EMI-RNN required 72x less computation than a standard LSTM while actually improving accuracy by 1%.
  • Compute Savings: Across four of the five datasets, the method saved 65–90% of computation without any loss in accuracy.
  • Real-World Deployment: The authors successfully deployed these models for real-time prediction on a Raspberry Pi Zero and Arduino-compatible devices—tasks that the baseline LSTM models simply could not perform in real-time.
  • Accuracy Gains: For keyword spotting (Google-13), the method provided a 2% accuracy boost while being 2-3x faster.

Limitations and Future Work

While highly effective for IoT sensors, the current study focuses primarily on fixed-length sensor data. The authors suggest that applying this to Natural Language Processing (NLP), where sequence lengths vary wildly, would be a valuable next step. Additionally, while the theoretical analysis is a strong start, it assumes a "simple separable setting." Extending this proof to more complex, non-linear neural network distributions and formalizing it for classification loss (like cross-entropy) remains an open challenge.

Summary updated

Abstract

We study the problem of fast and efficient classification of sequential data (such as time-series) on tiny devices, which is critical for various IoT related applications like audio keyword detection or gesture detection. Such tasks are cast as a standard classification task by sliding windows over the data stream to construct data points. Deploying such classification modules on tiny devices is challenging as predictions over sliding windows of data need to be invoked continuously at a high frequency. Each such predictor instance in itself is expensive as it evaluates large models over long windows of data. In this paper, we address this challenge by exploiting the following two observations about classification tasks arising in typical IoT related applications: (a) the "signature" of a particular class (e.g. an audio keyword) typically occupies a small fraction of the overall data, and (b) class signatures tend to be discernible early on in the data. We propose a method, EMI-RNN, that exploits these observations by using a multiple instance learning formulation along with an early prediction technique to learn a model that achieves better accuracy compared to baseline models, while simultaneously reducing computation by a large fraction. For instance, on a gesture detection benchmark [ 25 ], EMI-RNN improves standard LSTM model’s accuracy by up to 1% while requiring 72x less computation. This enables us to deploy such models for continuous real-time prediction on a small device such as Raspberry Pi0 and Arduino variants, a task that the baseline LSTM could not achieve. Finally, we also provide an analysis of our multiple instance learning algorithm in a simple setting and show that the proposed algorithm converges to the global optima at a linear rate, one of the first such result in this domain. The code for EMI-RNN is available at: https://github.com/Microsoft/EdgeML/tree/master/tf/examples/EMI-RNN
BibTeX
@inproceedings{dennis2018multiple,
  author = {Don Dennis and Chirag Pabbaraju and Harsha Vardhan Simhadri and Prateek Jain},
  title = {{Multiple Instance Learning for Efficient Sequential Data Classification on Resource-constrained Devices}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=SJWtSv-_WS},
}
Figure