MORES: Online Incremental Multiple-Output Regression for Data Streams

Changsheng Li, Weishan Dong, Qingshan Liu, Xin Zhang

TL;DR

This paper introduces MORES, a novel online learning algorithm for predicting multiple outputs from streaming data. MORES dynamically learns the underlying structures of both regression coefficients and residual errors, leading to improved accuracy and adaptability to evolving data streams, while maintaining high computational efficiency.

What Problem Does This Paper Address?

Traditional machine learning often deals with static datasets. However, many real-world scenarios involve data streams – continuous, potentially infinite sequences of data arriving over time. Examples include financial markets, sensor networks, and internet traffic. Predicting multiple related outputs from such streams (e.g., weather forecasts for multiple locations, or joint torques for multiple robotic arm joints) is crucial but challenging. Existing methods struggle with the dynamic nature of data streams, requiring retraining on the entire dataset, which is computationally expensive and memory-intensive. Furthermore, simply treating each output independently can miss valuable correlations, and early-stage models might exhibit dependent residual errors, further degrading performance. This paper aims to bridge this gap by proposing an online method that efficiently learns from streaming data, captures inter-output dependencies, and adapts to changes over time.

Methods

The core of MORES lies in its objective function, which is optimized incrementally at each time step. It addresses limitations of simpler online regression methods by:

  • Dynamic Structure Learning: Instead of just updating regression coefficients, MORES explicitly learns the structure of the regression coefficient matrix (using Mahalanobis norm) and the residual errors (using a matrix Γ). This allows the model to capture correlations between outputs.
  • Efficient Residual Error Modeling: To handle correlations in residual errors, MORES uses the Mahalanobis distance instead of the standard Euclidean distance. This is crucial because limited model expressiveness in early stages can lead to dependent residuals.
  • Incremental Loss Calculation: To avoid loading all historical data, MORES defines three statistical variables (Ct,YY, Ct,xy, Ct,xx) that summarize past data. This allows for incremental calculation of the prediction loss, making it memory-efficient and preventing drastic model fluctuations due to noise.
  • Forgetting Factor: A forgetting factor (μ) is introduced to assign different weights to samples, giving more importance to recent data. This helps the model adapt to evolving data streams.
  • Alternating Optimization: The optimization problem is solved using an alternating strategy, optimizing for P (regression coefficients), Ω (structure of regression coefficients), and Γ (structure of residual errors) iteratively.

Two divergence metrics are proposed for learning the structure of regression coefficients: quantum relative entropy (MORES-QE) and LogDet divergence (MORES-LD).

Datasets

The paper evaluates MORES on three real-world datasets:

  • Barrett WAM dataset: Used for modeling the inverse dynamics of a 7-DOF robotic arm. This dataset has 16,200 samples with 21 input features and 7 output variables (joint torques).
  • Stock Price Dataset: Daily stock prices of five companies (IBM, Yahoo, Microsoft, Apple, Oracle) from 2010 to 2013. This is framed as an autoregressive problem where past prices predict future prices.
  • Weather Dataset: Contains sensor data (wind speed, direction, pressure, etc.) collected every five minutes from a network on the south coast of England, spanning 1.5 years (143,034 samples).

Key Insights and Ideas

  • Inter-output correlations are critical: Simply treating each output as an independent task (like in some PA algorithms) is suboptimal. Dynamically learning the relationships between outputs significantly improves prediction accuracy.
  • Residual error structure matters: The errors left over after prediction are not always independent, especially early in training. Modeling their structure (using Mahalanobis distance) is key to robust performance.
  • Memory efficiency is achievable: By cleverly summarizing historical data into a few statistical variables, MORES avoids the need to store or re-scan the entire dataset, making it practical for streaming scenarios.
  • Adaptability is paramount: Data streams evolve. The forgetting factor and dynamic learning mechanisms allow MORES to adjust to these changes, outperforming methods that assume stationarity.
  • Divergence metrics have similar impact: Both quantum relative entropy and LogDet divergence metrics for learning coefficient structure yielded comparable, strong results, suggesting flexibility in implementation.

Key Results

  • Superior Accuracy: MORES (both QE and LD variants) consistently outperformed baseline methods (PA-I, PA-II, iS-PLS, SOMOR) across all three real-world datasets in terms of Mean Absolute Error (MAE). For instance, on the stock price prediction task, MORES-LD achieved significant relative accuracy improvements over PA-II (e.g., 33.6% for IBM).
  • Efficiency: MORES demonstrated high computational efficiency, processing at least 2000 samples per second on the tested datasets, which is significantly faster than state-of-the-art online learning algorithms.
  • Effectiveness of Components: Ablation studies (e.g., WRL, DRR, DRC-QE, DRC-LD) showed that dynamically learning both regression coefficient structure and residual error structure, and combining them (as in MORES), leads to the best performance.
  • Forgetting Factor Impact: The forgetting factor was shown to be beneficial, with optimal performance achieved for values between 0.6 and 0.9, indicating the importance of recent data in evolving streams.

Limitations and Future Work

  • Parameter Sensitivity: While the paper suggests MORES is not highly sensitive to α and β, parameter tuning is still required. The optimal value for η was found to be around 0.1 for the weather dataset.
  • Preliminary Stage: The paper acknowledges that during the very early stages of online update (before a threshold Tmin), the learned structures for Ω and Γ might not be well-formed, and thus Ω and Γ are not updated until t ≥ Tmin.
  • Future Work: The authors suggest that further improvements could be made by exploring more efficient programming languages or parallel implementations to further boost update speeds. The paper also implicitly suggests that exploring other divergence metrics or regularization techniques could be fruitful.

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{li2014mores,
  author = {Changsheng Li and Weishan Dong and Qingshan Liu and Xin Zhang},
  title = {{MORES: Online Incremental Multiple-Output Regression for Data Streams}},
  year = {2014},
  eprint = {1412.5732},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1412.5732},
}
Figure