Dynamic Structure Embedded Online Multiple-Output Regression for Stream Data

Changsheng Li, Wei Fan, Weishan Dong, Qingshan Liu, Xiangfeng Wang, Xin Zhang

Abstract

Online multiple-output regression is an important machine learning technique for modeling, predicting, and compressing multi-dimensional correlated data streams. In this paper, we propose a novel online multiple-output regression method, called MORES, for stream data. MORES can dynamically learn the structure of the coefficients change in each update step to facilitate the model's continuous refinement. We observe that limited expressive ability of the regression model, especially in the preliminary stage of online update, often leads to the variables in the residual errors being dependent. In light of this point, MORES intends to dynamically learn and leverage the structure of the residual errors to improve the prediction accuracy. Moreover, we define three statistical variables to exactly represent all the seen samples for incrementally calculating prediction loss in each online update round, which can avoid loading all the training data into memory for updating model, and also effectively prevent drastic fluctuation of the model in the presence of noise. Furthermore, we introduce a forgetting factor to set different weights on samples so as to track the data streams' evolving characteristics quickly from the latest samples. Experiments on one synthetic dataset and three real-world datasets validate the effectiveness of the proposed method. In addition, the update speed of MORES is at least 2000 samples processed per second on the three real-world datasets, more than 15 times faster than the state-of-the-art online learning algorithm.

Introduction

In the era of big data, information often arrives as sequential, infinite streams—such as financial market ticks, sensor network readings, or weather monitoring data. These streams frequently exhibit "concept drift," where the underlying data distribution evolves over time. Traditional batch regression methods are ill-suited for these environments as they require re-training on the entire accumulated dataset, leading to prohibitive computational costs.

Existing online learning methods often struggle with two primary issues. First, they frequently ignore correlations between multiple outputs (e.g., temperature and humidity), treating them as independent tasks. Second, they face a trade-off between memory efficiency and noise robustness; methods that only consider the most recent data point are sensitive to noise, while those that store historical data eventually exceed memory limits.

Methodology: The MORES Algorithm

The proposed MORES (Multiple-Output REgression for Stream data) algorithm addresses these challenges through three innovative mechanisms:

1. Dynamic Structure Learning

Unlike standard approaches that use Euclidean distance, MORES employs the matrix Mahalanobis norm in its objective function. This enables the model to learn the underlying correlation structure of both the regression coefficients and the residual errors. By identifying dependencies in residual errors—common in the early stages of online updates—MORES can refine its predictions more effectively.

2. Lossless Data Compression

To maintain memory efficiency without sacrificing historical context, MORES utilizes three statistical variables ($C_{t,YY}, C_{t,XY}, C_{t,XX}$) that serve as a "running summary" of all observed data. This allows the model to calculate the total prediction loss incrementally, eliminating the need to store or reload previous samples.

Algorithm 1: The MORES update procedure using summary statistics.

3. Adaptive Forgetting Factor

A forgetting factor $\mu$ is introduced to weight recent samples more heavily. This allows the model to "forget" outdated patterns and rapidly adapt to evolving characteristics in the data stream.

Experimental Evaluation

The performance of MORES was evaluated against several state-of-the-art methods, including iS-PLS, ELLA, and OMTL, across diverse datasets: a synthetic dataset, a stock price dataset (IBM, Yahoo, Microsoft, Apple, Oracle), the Barrett WAM robotics dataset, and a large-scale weather dataset.

Accuracy and Efficiency

MORES consistently achieved the lowest Mean Absolute Error (MAE) across all real-world datasets. For instance, on the stock price dataset, MORES significantly outperformed all baselines, demonstrating the power of its structure-learning approach.

Mean Absolute Error (MAE) comparison on the stock price dataset.

Beyond accuracy, MORES demonstrated exceptional speed, processing between 4,352 and 5,015 samples per second on real-world data. This represents a 15 to 30-fold speedup compared to ELLA, a leading multi-task learning algorithm.

Conclusion

MORES provides a robust and high-speed solution for online multiple-output regression. By leveraging the structure of residual errors and employing efficient summary statistics, it achieves superior accuracy and remarkable computational efficiency. While currently focused on linear regression, future extensions could explore non-linear mappings and more complex forgetting mechanisms to handle abrupt concept drift in even more challenging streaming environments.

Summary updated

Abstract

Online multiple-output regression is an important machine learning technique for modeling, predicting, and compressing multi-dimensional correlated data streams. In this paper, we propose a novel online multiple-output regression method, called MORES, for stream data. MORES can \emph{dynamically} learn the structure of the coefficients change in each update step to facilitate the model's continuous refinement. We observe that limited expressive ability of the regression model, especially in the preliminary stage of online update, often leads to the variables in the residual errors being dependent. In light of this point, MORES intends to \emph{dynamically} learn and leverage the structure of the residual errors to improve the prediction accuracy. Moreover, we define three statistical variables to \emph{exactly} represent all the seen samples for \emph{incrementally} calculating prediction loss in each online update round, which can avoid loading all the training data into memory for updating model, and also effectively prevent drastic fluctuation of the model in the presence of noise. Furthermore, we introduce a forgetting factor to set different weights on samples so as to track the data streams' evolving characteristics quickly from the latest samples. Experiments on one synthetic dataset and three real-world datasets validate the effectiveness of the proposed method. In addition, the update speed of MORES is at least 2000 samples processed per second on the three real-world datasets, more than 15 times faster than the state-of-the-art online learning algorithm.
BibTeX
@misc{li2014dynamic,
  author = {Changsheng Li and Wei Fan and Weishan Dong and Qingshan Liu and Xiangfeng Wang and Xin Zhang},
  title = {{Dynamic Structure Embedded Online Multiple-Output Regression for Stream Data}},
  year = {2014},
  eprint = {1412.5732},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1412.5732},
}
Figure