# How to handle online time series forecast?

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.

-

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.

-
 The procedure you recommended , does it report when level shifts or time trend changes occur ? Does it detect changes in parameters or changes in variance over time ? Does it distinguish between seasonal auto-regressive memory and seasonal dummies ? – IrishStat Aug 24 '12 at 21:22 @IrishStat I think your question is rhetorical. If a model can have a simple recursion to update the model it can't have all the complexities that you describe. Sometimes it is more important to get a correct answer rather than a quick answer that is poor. That is why in my answer I said to only do it if the model fits the data well! – Michael Chernick Aug 24 '12 at 21:56 @IrishStat These methods are "non-parametric", which means that they don't assume any specific model of the data (they just "fit" the data). They don't report trend changes. They do report prediction error though, so if you want to find trend changes you can probably simply look at when the prediction error is sufficiently large. – Steven Aug 25 '12 at 10:56 I am not familiar with online sparse Gaussian processes but from looking at the linked article I don't think it is quite right to characterize them as "nonparameteric" as they use Gaussian processes for prior distributions and involve a number of parameters in their "Kalman-filter-like" recursiona. It seems that some model structure must be implicit in the formulation. I still think IrishStat's comments applies. – Michael Chernick Aug 25 '12 at 13:20

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.

-

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,

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

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.

-
 Hi Murat! I created a hyperlink to the paper you posted and centered your equations. See the post history if you're interested in seeing how to do this for future reference. There are also some helpful buttons along the top of the text box that appears when you're writing an answer that will do a lot of stuff automatically for you (e.g. entering pictures, links, bold/italics and more). (+1, btw) – Macro Aug 25 '12 at 15:01 @Macro I will check it out thanks! – muratoa Aug 25 '12 at 15:02

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..

-

@Emre I didnt know that. How can I programmatically do that? Suppose the code x <- c(1,2,3,4); f <- forecast(x); I know that f['model'] is a model, but how can I use that model latter when I do append(x, 5); forecast(x); ?

-