Learning with expert advice as a scheme of on-line learning has been very successfully applied to various learning problems due to its strong theoretical basis. In this paper, for the purpose of times series prediction, we investigate the application of Aggregation Algorithm, which a generalisation of the famous weighted majority algorithm. The results of the experiments done, show that the Aggregation Algorithm performs very well in comparison to average.
A time series is a set of repeated observations of the same variable, such as stock
return or GNP. A time series consists of cyclic(for example daily uctuations),
seasonal(variation in data due to calender related e ect) or irregular e ects(any
movement other than seasonal or cyclic). Machine Learning methods are now
been used to analyse large data [
There exist two classes of modelling techniques for time series: statistical learning and competitive on-line learning [Anava et al., 2013], the former assumes that the observations are drawn from some unknown distribution. Representative techniques of this class include the well-known autoregressive moving average (ARMA) and its alike seen as a standard time-series modelling techniques. The motivation behind developing competative on-line learning algorithm is that the statistical(ARMA) models have strong distributional assumptions, due to which they have asymptotic guarantees [Kuznetsov and Mohri, 2016].
On-line learning has received a great attention from the machine learning community. Its origin goes back to the late 1980's and early 1990's with the advent of the paradigm of prediction with expert advice. The early work appeared in a number of seminal papers by [Haussler et al., 1994]. On-line learning consists of learning a sequentially presented set of training data upon arrival, without re-examining data that has been processed so far. In general on-line learning is practical for applications where the data set is large and cannot be processed at once due to memory constraints. Practically an on-line learner receives a new data instance, along with current hypothesis, checks if the data instance is covered by the current hypothesis and updates the hypothesis accordingly. The protocol of on-line learning can be summarized as follows: the learner receives an observation; the learner makes a decision; the learner receives the ground truth; learner incurs the loss and updates its hypothesis. The learning process is based on the minimisation of the loss (regret) which corresponds to the discrepancy between the loss and the loss of the best expert in hindsight.
Neural network is another approach used in time-series, in particular nancial
and economic time-series. Neural networks are universal function approximators
that can map any non-linear function [
Prediction models have parameters and we are faced with the problem of selecting the best set of parameters. If we have little information on the predictive behaviour of parameters, one may want to keep all models and predict using the average.
Methods of competitive prediction provide a better alternative to averaging.
The approach of this paper is drawn from the area of competitive on-line
prediction, where the goal is merging predictions of experts. In this paper we
merge predictions of time series models with respect to the square loss.
[DeSantis et al., 1988] for the rst time presented the Bayesian mixing scheme using
log-loss, later [Littlestone and Warmuth, 1989] presented what was known as
weighted majority algorithm and Vovk generalised them which resulted in
Aggregation Algorithm(AA) [
[Box et al., 2015] were the ones who probably launched auto-regressive integrated moving-average, the Box-Jenkins methodology eloberated by [Hibon and Makridakis, 1997]. The idea was extended to state-space representation, by [Durbin, 2004]. The book by [Hyndman and Athanasopoulos, 2014] captures broad spectrum of work on time series.
We develop an underlying system of obtaining predictions with the objective of comparing simple average against the AA.
The system we provide is a hybrid system i.e. the prediction comes from usual statistical learning approach which we brie y outline in this section along with the on-line protocol, then we use a competitive on-line learning algorithm on those predictions, which are outlined in the next section.
We highlight the usefulness of AA in time-series in a similar fashion as done
in [
The observed time series is a realization of a stochastic processes. A stochastic process is any collection of random variables Xt; t 2 T de ned on a common probability space , here t denotes the time. So T can be either discrete or continuous set of series. In our case we only deal with discrete-time series [Berchtold, 1995].
If a random variable X is indexed to time, we denote time by t, the observations fXt; t 2 Tg, where T is a time indexed set, for example it may be a set of integers. The stochastic process is described by a probability distribution for fXtg, where often elements lack independence. The distribution is usually characterized using the moments.
The objective of time-series models is to make predictions, so sometimes it is also referred as predictive inference. Time-series methods make prediction based on historical pattern of the data, measurements are taken at successive periods, such as over day, month, year etc. At the very heart of time series analysis lies ARMA models, mathematically represented as:
p Xt = X i=1
q X i=1 iXt i + iWt i + Wt (1) We can divide ARMA models into two parts, auto-regressive(AR) part and the moving-average(MA) part. The challenge is often to determine the correct order p and q for AR and MA part respectively. Generally the notation used is ARMA(p,q)1. So AR(p) can be represented by the following equation: p Xt = X i=1 iXt i + Wt (2) 1 The equations used for time-series ARMA,ARIMA,AR, and MA are adopted from [Liu et al., 2016] Similarly for MA(q) the following equation:
q
Xt = X iWt i + Wt
k sin
2 kt
m
+ k cos
where Xt is stationary, 2 Rp, 2 Rq parameters, and Wt is a Gaussian white
noise series with mean 0 and variance 2. The AR models is very similar to the
multiple linear regression models, except that the Xt is regressed on the past
values of Xt [Liu et al., 2016], whereas MA has been used for data
smoothing, without explicitly using the term moving average, they were described as
instantaneous averages by [
In practical situation often a time-series is not a realisation of a stationary process [Liu et al., 2016], so ARIMA(p; d; q) are used:
p q OdXt = X iOdXt i + X iWt i + Wt i=1 i=1 where OXt = Xt Xt 1, 2 Rp, 2 Rq, and Wt v N (0; 2). It is worth noting that ARMA(p; q) is a special case of ARIMA(p; 0; q).
Our main experiments uses data from Meteorology, so it is reasonable to
assume that there is some sort of cyclic behaviour or periodicity in it, which
is also justi ed in [Jones and Brelsford, 1967]. In order to tackle periodicity
we make use of the Fourier series. A Fourier series is a speci c type of in nite
mathematical series involving trigonometric functions, the series were introduced
by [baron Fourier, 1831]. Fourier series are used in applied mathematics, and
especially in physics and electronics, to express periodic functions such as those
that comprise communications signals in waveform, however Fourier series truly
began with the profound work of Fourier on heat conduction at the beginning of
the 19th century [
We now de ne the notion of game-theoretic frame work, or to be more speci c
we de ne [
The following notation is used { outcomes are denoted as !1; !2, they happen sequentially from the outcome space = [A; B], where A and B are the minimum and maximum(of a particular data for example). { predictions at time t is represented as t, and they belong to prediction space = fA; Bg. { 1; :::; N experts, there are nite number of experts and the experts space is denoted by . { we denote learner by L and its loss at time T as LossT (L) = PT t=1 ( t; !t), where t and !t and the expert loss is LossT ( ).
Following are the set of assumptions or rather a scenario under we work: { We do not assume that there is a model generating outcomes { Outcomes may be adversarial meaning, for example output of 1 every-time we predict zero { We have access to the experts predictions and expert prediction is incorporated or consulted before a prediction is given { The objective to be as close as possible to the best expert { Experts maybe adversarial too 2 An ARIMA is just the di erencing of ARMA model, if ARMA models are not stationary, but are di erence stationary then we call them ARIMA, where I is the number of di erence we took to make it stationary [Ghosh, 1976], but forcast package by Rob J Hyndman provides more exibility. 3 We used (5) in our experiment from the implementation in the package forecast by Rob J Hyndman, for details [Hyndman and Athanasopoulos, 2014]
The protocol for on-line prediction described in introduction and here can be formalised as follows:4 Protocol Prediction With Expert Advise for t = 1; 2; ::: do
2 predicts t 2 Learner output t 2 System output !t 2
2 su ers losses ( t ; !t)
Learner loss ( t; !t) end for
There are di erent loss functions that can be used, but for the purposes of
our experiment we use square-loss, the main reasons are as follows:
{ If the outcomes and predictions are bounded, square loss is bounded;
{ bounded square loss is mixable [
The weighted majority algorithm is very restrictive, so we go on a better algorithm, known as the Aggregating Algorithm(AA). The AA takes two parameters, a prior probability say W0 and the learning rate > 0. W0 is related to the weights and the 0 in the subscript makes it the initial weights. Before we describe the AA, we explain the mechanics of the algorithm i.e. obtaining the generalised prediction, later that can be easily used for the purposes of the actual prediction. At every step t experts weight is updated, so intuitively, if an expert makes a mistake we would reduce its weight, mathematically we represent this by using our de ned notation: gt(!) = log
Z
( t;! )Wt 1d
(6)
= WWtt 11((d )) in simple words W
where 2 and W represent the normalised
weights. For mathematical details and optimality of AA see [
Notice in (6) we use ! not !t, this is because we are at the moment making prediction. What AA does is uses a substitution function5 which maps the generalised prediction into .
In certain situations it may not be possible to use a substitution function
that perfectly maps to , we call such situations non-mixable scenario, however
4 The notation are adopted from [
Loss(AA) = Lossbest( ) +
log N
(7)
where 2 , is the learning rate, and N is the number of experts. This
bound (7) is shown [
We now formally present the pseudo-code, where parameters are > 0 and initial distribution is of q1; q2; ::; qn. This algorithm is also for the cases of nonmixable game.
Algorithm Aggregating Algorithm initialise weights w0n = qn; n = 1; 2; :::N for t = 1; 2; :: do notice experts prediction tn, n = 1; 2; :::; N weights normalisation ptn 1 = PiN=w1tnw1ti 1 solve the system (! 2 ) ( ; !) output a solution t notice !t experts weights update wtn = wtn 1e end for
C( ) log PN
n=1 ptn 1e ( tn;!t); n = 1; 2; :::; N ( tn;!) w.r.t and 4
Our experiments uses [
To be more explicit, rst 365 days were used to select the coe cients for the 18 models (experts for AA) and the value of k, then at each step these models give one step ahead prediction (experts predictions for AA) based on the previous observations.
Fig 1 demonstrates that AA follows the best expert, which in both ( A and C for minimum temperature data) experiments is ARIMA(0; 1; 0) with respective values of k. In our experiments overall loss of AA is even less than the best expert. This is because the best expert gives the lowest overall loss, however it does not give lower loss from the start, there are other experts who are able to compete with this expert and some outperform the best expert, all of this AA captures, and is able to outperform the best expert.
2.0e+09 1.5e+09 s s Lo1.0e+09 5.0e+08 0.0e+00 0 1000 2000
E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12 2000 Days 0 1000 3000 0 1000 3000 2.0e+09 1.5e+09 s so1.0e+09 L 5.0e+08 0.0e+00
0 1000 2000
E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12 3000 E13 E14 E15 E16
0 1000 E1 E2 E3 E4 2000
E5 E6 E7 E8 E9 E10 E11 E12 3000 E13 E14 E15 E16 0 1000 3000 2000
0 1000
3000 1904:307 respectively is violated by the average.
F
0 −50000 s s o L−100000 −150000 E17 E18 H 2.0e+09 1.5e+09 s so1.0e+09 L 5.0e+08 0.0e+00
AA vs Outcomes Daily Minimum Temperature
Daily Maximum Temperature ssLo 074e+− 0 4 0 3 0 2 0 1 0 0 + e 0 7 0 + e 2 − 7 0 + e 6 − 7 0 + e 8 − 7 0 ssLo 4e+− 0 500 1000 1500 2000 2500 3000
Days Fig. 4. The decreasing behaviour of the di erence between square losses of AA and average suggest that AA outperforms the average.
0 500 1000 1500 2000 2500 3000
Days 0 500 1000 1500 2000 2500 3000
Days One can compare Fig 2 (E and G for minimum temperature data) with Fig 1 and easily see averaging is not favourable, since the spread between the expert with maximum loss and the expert with minimum loss is colossal. Fig 3 shows that AA actually does very well in predicting the outcomes, only the extreme temperatures are missed mainly.
Fig 4 is the plot demonstrating the di erence between the AA and the average (AA minus average) square loss, since average is greater than the AA, hence the decreasing behaviour in the curve. 5
We have studied the performance of AA, and average on minimum temperature and maximum temperature data . We conclude that, best expert ARIMA(0; 1; 0) with k = 95 for maximum temperature data and k = 54 for minimum temperature data are outperformed by AA prediction, furthermore AA is signi cantly better than taking simple average as shown in Table 2 (the square loss of AA is substantially lower then the average) Fig 1 clearly show that the theoretical bound by AA has not been violated, due to which AA gives a better result than the simple average. Experts predictions are used by AA to produce a better overall result.
Waqas Jamil and Hamid Bouchachia has been supported by the European Commission under the Horizon 2020 Grant 687691 related to the project: PROTEUS: Scalable Online Machine Learning for Predictive Analytics and Real-Time Interactive Visualization.
Yuri Kalnishkan has been supported by the Leverhulme Trust through the grant RPG-2013-047 `Online self-tuning learning algorithms for handling historical information'. Anava et al., 2013. Anava, O., Hazan, E., Mannor, S., and Shamir, O. (2013). Online learning for time series prediction. In COLT, pages 172{184. baron Fourier, 1831. baron Fourier, J. B. J. (1831). Analyse des equations determinees, volume 1. Firmin Didot.
Berchtold, 1995. Berchtold, A. (1995). Autoregressive modelling of markov chains. In
Statistical Modelling, pages 19{26. Springer.
Box et al., 2015. Box, G. E., Jenkins, G. M., Reinsel, G. C., and Ljung, G. M. (2015).
Time series analysis: forecasting and control. John Wiley & Sons.
Bracewell, 1965. Bracewell, R. (1965). The fourier transform and its applications. New
York, 5.
Brown, 2004. Brown, R. G. (2004). Smoothing, forecasting and prediction of discrete time series. Courier Corporation.
DeSantis et al., 1988. DeSantis, A., Markowsky, G., and Wegman, M. N. (1988).
Learning probabilistic prediction functions. In Foundations of Computer Science, 1988., 29th Annual Symposium on, pages 110{119. IEEE.
D az-Robles et al., 2008. D az-Robles, L. A., Ortega, J. C., Fu, J. S., Reed, G. D., Chow, J. C., Watson, J. G., and Moncada-Herrera, J. A. (2008). A hybrid arima and arti cial neural networks model to forecast particulate matter in urban areas: The case of temuco, chile. Atmospheric Environment, 42(35):8331{8340.
Durbin, 2004. Durbin, J. (2004). Introduction to state space time series analysis. State
Space and unobserved component models: Theory and Applications, pages 3{25. Ghosh, 1976. Ghosh, N. (1976). Time series analysis and forecasting (the box-jenkins approach). Journal of the Operational Research Society, 27(3):644{644. Haurlan, 1968. Haurlan, P. (1968). Measuring Trend Values. Trade Levels. Haussler et al., 1998. Haussler, D., Kivinen, J., and Warmuth, M. K. (1998). Sequential prediction of individual sequences under general loss functions. IEEE Transactions on Information Theory, 44(5):1906{1925.
Haussler et al., 1994. Haussler, D., Littlestone, N., and Warmuth, M. K. (1994). Predicting f0, 1g-functions on randomly drawn points. Information and Computation, 115(2):248{292.
Hibon and Makridakis, 1997. Hibon, M. and Makridakis, S. (1997). Arma models and the box{jenkins methodology.
Holt, 2004. Holt, C. C. (2004). Forecasting seasonals and trends by exponentially weighted moving averages. International journal of forecasting, 20(1):5{10. Hu et al., 2007. Hu, W., Tong, S., Mengersen, K., and Connell, D. (2007). Weather variability and the incidence of cryptosporidiosis: comparison of time series poisson regression and sarima models. Annals of epidemiology, 17(9):679{688. Hyndman and Athanasopoulos, 2014. Hyndman, R. J. and Athanasopoulos, G.
(2014). Forecasting: principles and practice. OTexts.
Jones and Brelsford, 1967. Jones, R. H. and Brelsford, W. M. (1967). Time series with periodic structure. Biometrika, 54(3-4):403{408.
Kuznetsov and Mohri, 2016. Kuznetsov, V. and Mohri, M. (2016). Time series prediction and online learning. In 29th Annual Conference on Learning Theory, pages 1190{1213.
Littlestone and Warmuth, 1989. Littlestone, N. and Warmuth, M. K. (1989). The weighted majority algorithm. In Foundations of Computer Science, 1989., 30th Annual Symposium on, pages 256{261. IEEE.
Liu et al., 2016. Liu, C., Hoi, S. C., Zhao, P., and Sun, J. (2016). Online arima algorithms for time series prediction. In Thirtieth AAAI Conference on Arti cial Intelligence.