How to handle online time series forecast?

Question

I have been dealing with the following problem. I have kind of a real time system and every time frame I read its current value, creating a time series (such as 1, 12, 2, 3, 5, 9, 1, ...). I'd like to know methods (statistical and machine learning) to forecast the next value in an online fashion (meaning every time a new value is read). I tried R's ARIMA and Weka's SMOreg, they result in good predictions, but they are kind of slow as every time a new value comes I have to redo the math.

P.S. It would be great also if the method had a confidence interval.

Answer 1

First you need to make a time-embedding of your data. E.g. take as the first input [1, 12, 2, 3] and the corresponding output [5], and as the second input you take [12, 2, 3, 5] and the corresponding output [9]. (This is embedding with delay 4 but you can choose another value that fits better. )

Now you have a valid prediction problem. To these data you can apply Online Gaussian Processes. This is a machine learning method which does exactly what you describe, and it provides confidence intervals.

If your model is non-stationary you can try the non-stationary extension, kernel recursive least-squares tracker. By the way, that paper includes Matlab code for stationary and nonstationary cases.

These methods are reasonably fast: their computational complexity is quadratic in terms of the number of data you store in memory (which is typically a small, representative part of all data processed). For faster methods I recommend for instance kernel least mean squares method, but their accuracy is less.

Answer 2

In your real-time system are the observation times inhomogenous and the data non-stationary? If you want something simple and fast I suggest using the inhomogenous EMA type operators:

Operators on Inhomogeneous Time Series

They update the EMA ($\text{value}$) with each new observation according to,

\begin{equation} \text{value} \: += \alpha \:(\text{newData} - \text{value}), \quad \alpha = 1 - \exp{(-\frac{\Delta t}{\tau})} \end{equation}

with $\tau$ a smoothing/tuning parameter. It is a simple way to estimate an expectation.

Also one can create a simple online median estimate via the update

\begin{align} \text{sg} &= sgn(\text{newData} - \text{med})\\ \text{med} +&= \epsilon \: (\text{sg} - \text{med}) \end{align}

In practice you want $\epsilon$ small (or decaying with more observations). Ideally $\epsilon$ should depend on how lopsided the updates are becoming; i.e. if $\text{med}$ actually equals the median then $\text{sg}$ should be uniform on $\{-1,1\}$. You can then extend this to a depth $d$ balanced binary tree type structure to get $2^{d+1}-1$ quantiles uniformly spaced.

The combination of the above should give you a decent online distribution of your data. The tree is tricky to get right, I have implementations of both in C++ if you are interested. I use both in practice a lot (financial real-time tick data) and they have worked well.

Answer 3

The Kalman filter is a recursive algorithm. It takes the new observation and combines it with the previous prediction. It would be good to use but only if it is an appropriate model for your data. I am not sure how easy it is to update the prediction interval.

Answer 4

I don't know if you tried this, but in R when you use the Arima function you can specify the model as an input. So, if initially you found an arima model let's say Arima(1,2,1) with respective smoothing components you can then fix the model in later iterations so it does not try to refit a model. If your data is stationary in that case, the predictions may be sufficiently good for you - and much faster.

Hope this helps..