TL;DR
This paper introduces NonSTOP, a novel online learning framework for predicting non-stationary time series. By intelligently transforming data to handle trends and seasonality, NonSTOP achieves superior prediction performance. Crucially, it can automatically learn the best transformation online, making it robust to unknown data characteristics.
What Problem Does This Paper Address?
Real-world time series data, from stock prices to electricity demand, are rarely stationary. They often exhibit trends (like gradual increases or decreases) and seasonality (repeating patterns at fixed intervals). Traditional time series models, like ARMA, perform best on stationary data. While methods exist to handle non-stationarity (e.g., differencing for trends, seasonal differencing for seasonality), these often require prior knowledge of the data's characteristics or rely on offline analysis, which is impractical for streaming data. This paper addresses the challenge of building online prediction models that can effectively handle various forms of non-stationarity without prior knowledge.
Methods
The core idea is to transform the time series data before applying prediction algorithms. The authors propose a unified framework called TSP-OGD (Time Series Prediction using Online Gradient Descent) for univariate time series. This framework allows for applying known transformations (like differencing for trends or seasonal differencing) to make the series stationary, thereby improving prediction.
However, in real-world scenarios, the "correct" transformation is usually unknown. To tackle this, they introduce NonSTOP (NonSTationary Online Prediction), a meta-algorithm based on the "learning with experts" paradigm. NonSTOP maintains a set of "experts," where each expert is an instance of TSP-OGD with a different transformation applied. At each time step, NonSTOP uses a weighted majority approach to select a prediction from one of its experts, and then updates the weights of the experts based on their performance. This allows NonSTOP to dynamically learn which transformation is most effective for the incoming data.
For multivariate time series, they extend these ideas to handle cointegration, a phenomenon where multiple time series share a common trend. They propose an EC-VARMA-OGD algorithm that can simultaneously estimate the cointegrating relationships and the model parameters. NonSTOP can also incorporate these multivariate experts.
The theoretical contributions include sub-linear regret bounds for all proposed algorithms, meaning their accumulated prediction error grows slower than the total number of time steps. They also provide a data-dependent regret analysis for a specific case, offering insights into why transformations are beneficial.
Datasets
The paper evaluates its methods on a variety of datasets:
- Synthetic Data: Simulated SARIMA (Seasonal AutoRegressive Integrated Moving Average) and ARIMA (AutoRegressive Integrated Moving Average) processes were used to test the algorithms under controlled conditions.
- Real-World Univariate Data:
- Turkey electricity demand
- Daily births in Quebec
- Daily river flow from the Saugeen River
- Real-World Multivariate Data:
- Stock prices from Yahoo Finance (7 companies)
- S&P500 index
- Google Flu data
Key Insights and Ideas
- Transformations are Key: The most significant insight is that applying appropriate transformations to non-stationary time series can dramatically improve prediction performance, both theoretically and empirically. This is because transformations can reduce serial correlation, making the data behave more like stationary series.
- Online Learning for Unknown Transformations: The real power of NonSTOP lies in its ability to learn the best transformation online. This is a crucial step beyond existing methods that require pre-specifying transformations.
- Adaptability is Crucial: NonSTOP's ability to adapt its expert weights means it can handle situations where the underlying data generating process changes over time (e.g., switching from a seasonal to a trend-dominated pattern).
- Unified Framework: The TSP-OGD framework provides a general way to incorporate various transformations, and NonSTOP builds on this to create a flexible, online system.
Key Results
- Superior Performance: In empirical evaluations, NonSTOP consistently outperformed baseline methods (like ARMA-OGD and ARIMA-OGD) on both synthetic and real-world datasets, especially when the data exhibited significant non-stationarity.
- Adaptation in Action: Figure 2b demonstrates NonSTOP's ability to adapt: it initially weights a SARIMA expert heavily, but as the data switches to an ARIMA process, NonSTOP quickly shifts its focus to the ARIMA expert, outperforming others.
- Multivariate Gains: For multivariate datasets, accounting for cointegration (using EC-VARMA-OGD within NonSTOP) led to considerably stronger performance compared to models that ignored it. NonSTOP outperformed VARMA-OGD by at least a factor of 3 on the original scale for these datasets.
- Theoretical Guarantees: The proposed algorithms come with sub-linear regret bounds, providing theoretical assurance of their performance.
Limitations and Future Work
- Known Transformations: While NonSTOP can learn which transformation to use, it relies on a pre-defined set of possible transformations. The paper assumes these transformations are known a priori.
- Expert Set Size: The performance of NonSTOP can depend on the size and quality of the expert set. A larger set of experts might lead to better performance but also increased computational cost.
- Future Work: The authors plan to explore extensions for more complex models, such as long memory models (e.g., ARFIMA), and investigate how to handle even more complicated non-stationary artifacts. They also suggest exploring more sophisticated ways to select the set of experts.
Summary updated