SIGNAL EXTRAPOLATION USING EMPIRICAL MODE DECOMPOSITION WITH FINANCIAL APPLICATIONS Nikolaos Tsakalozos, Konstantinos Drakakis, and Scott Rickard UCD CASL, University College Dublin, Belfield, Dublin 4, Ireland Email:
[email protected],
[email protected],
[email protected]
ABSTRACT In order to extrapolate a signal, Empirical Mode Decomposition is used to decompose it into simpler components. Each component is individually extrapolated linearly, and the final extrapolation value is produced as the sum of these individual values. This technique is applied on financial signals, with a view towards capturing the sign of the increment of the signal instead of the exact future value, and the results are compared to cubic spline extrapolation. 1. INTRODUCTION Signal extrapolation is the process of estimating future unknown values of a signal (defined here in the signal-theoretic sense, as a function of time) based on its present and past known values. In most practical signals of interest, the latter convey some information about the former, and thus partially determine them. Considering a causal transformation of the original signal, then, it may be possible to improve extrapolation for this new signal. It is also likely that known values of other signals convey some information about the signal under consideration, but this lies outside the scope of this work. The complexity of real world (e.g. financial) signals spearheaded research towards increasingly sophisticated extrapolation methods, as empirical tests kept revealing that pre-existing techniques were unsatisfactory in dealing with them [4]. Perhaps the cause of the problem was that little effort was put into understanding in depth the behavior of the signals, considering either too simple or generic signals instead. This work advocates that simple extrapolation techniques (such as linear extrapolation) suffice for even the most complicated signals, provided they are appropriately preprocessed based on their perceived structure. Specifically, the complexity of most natural signals can be attributed to activity in different time scales, so that each such signal can be viewed as the sum of several signals, each living in its own time scale [3]. Such signals are expected to be considerably simpler and smoother, and therefore much more suitable to extrapolate. This material is based upon works supported by the Science Foundation Ireland under Grant No. 05/YI2/I677, 06/MI/006 (Claude Shannon Institute), and 08/RFP/MTH1164.
Assuming then an expansion rule that can recover this particular, physically meaningful expansion can be found and used, the original problem of extrapolating a complicated signal is reduced to the extrapolation of several (mostly) simpler signals, for which linear extrapolation is (mostly) sufficient. An example of such an expansion rule is Empirical Mode Decomposition (EMD) [3], which offers a Fourier series-like expansion of any (discrete) signal consisting of finitely many and finite values (that is, of any signal of interest today), without relying on any of those conditions required by the Fourier transform but hardly ever observed in practice, such as stationarity and periodicity. EMD decomposes signals into a set of progressively slower varying Intrinsic Mode Functions (IMFs), each of which, with the possible exception of the last one, is a sinusoid-like signal: it is centered around the horizontal axis, and all local maxima (minima) are positive (negative), just like a sinusoid, except that both amplitude and frequency are allowed to vary. There is a well defined concept of instantaneous frequency for IMFs, so that EMD can be considered to be a generalized Fourier transform. In non-stationary signals, the last IMF of the expansion normally completes no full oscillation over the domain of the signal, and plays, therefore, the role of a drift, around which the remaining IMFs oscillate: it is known as the trend. On the downside, however, EMD remains an empirical and little studied transform, in staggering contrast to the rigorously and extensively studied Fourier transform. The caveat is that the most rapidly varying IMFs often consist of essentially uncorrelated values (in the context of both cross- and autocorrelation), so that history-based extrapolation is futile in this case. Such IMFs represent a fundamental limitation to one’s understanding of the signal’s behavior, set by the signal itself, and their impact increases along with the increase of their amplitude/energy over the amplitude/energy of the remaining IMFs. Effective extrapolation is possible for signals in which such IMFs are not significant. Section 2 presents the basics of the EMD algorithm, while Section 3 discusses signal extrapolation with an emphasis on financial signals: in particular, it considers an alternative extrapolation criterion, whereby predicting the sign of the increment of the signal correctly is more important than approximating the value itself. The state of the art is presented in Section 4, and the algorithm in Section 5. Finally, Section
6 presents the results of the new algorithm on the extrapolation of three financial signals, namely the hourly closing values of FTSE and Nasdaq, as well as the daily closing of the euro-dollar exchange rate, and compares it to classical spline extrapolation.
all valid n, lim fn,m is an IMF; and b) For all valid n, fn+1,1 m has strictly fewer local extrema compared to fn,1 .
2. EMPIRICAL MODE DECOMPOSITION
The usual criterion by which extrapolation effectiveness is measured is the proximity of the estimated value to the actual value of the signal. In other words, let f (i), i = 1, . . . , N be the signal under consideration, assume that the extrapolation scheme considered requires at least k known samples to work, and, for any n > k let fˆ(n) be the estimated (extrapolated) value of f (n). The extrapolation error can be defined as follows, considering the difference of the true and extrapolated value over their mean [4] (or in related ways, depending on the difference fˆ − f ): X fˆ(n) − f (n) (2) eDM (f ) = 2 . fˆ(n) + f (n) n>k
Let f (i), i = 1, . . . , N be a real-valued function. The EMD [3] produces functions fj , j = 1, . . . , m, and r, where m is determined by the algorithm and not known a priori, such that f=
m X
fj + r.
(1)
j=1
The functions fj , j = 1, . . . , m are the IMFs of f and are oscillatory in nature, while r, which does not perform a full oscillation over D = {1, . . . , N } (namely it has at most one internal extremum over D), is known as the trend of f . The EMD relies crucially upon the extraction of the envelope of f , which, by definition, consists of two distinct functions, the upper and the lower envelopes fu and fl , where fu is obtained through the cubic spline interpolation of all local maxima of f , and, similarly, fl is obtained through the cubic spline interpolation of all local minima of f . As a result, f tends to be “sandwiched” between fu and fl , though this is neither always true nor a requirement. The envelope, in turn, leads to the definition of the local mean of f pointwise as l = (fu + fl )/2. The IMFs can be thought of as sines with “variable width” and “fluctuating frequency”. They can be defined as those functions having the following two properties: a) All local maxima are positive and all local minima are negative; and b) The local mean is 0 everywhere. In practice, only approximate satisfaction of the latter property is required, and f is accepted as an IMF whenever, for a pre-specified > 0, the local mean satisfies klk < , where k · k denotes some function norm (such as the absolute maximum k · k∞ or the mean square value k · k2 ). Having discussed the envelope, and having defined what an IMF is, the description of the EMD algorithm can follow. Choose > 0 and initialize by setting f1,1 = f and n = m = 1; then, perform the following steps: 1. Compute the upper and lower envelopes fu,n,m and fl,n,m of fn,m and the local mean ln,m = (fu,n,m + fl,n,m )/2. 2. If kln,m k < , set fn = fn,m ; otherwise, set fn,m+1 = fn,m − ln,m , increase m by 1, and go to Step 1. 3. Set fn+1,1 = fn,1 − fn ; if this has either less than two local minima or less than two local maxima, set r = fn+1,0 and stop; otherwise, increase n by 1 and go to Step 1. Two empirically observed facts about the algorithm, which guarantee its termination, are the following: a) For
3. EXTRAPOLATION (WITH AN EMPHASIS IN FINANCE)
This makes perfect sense, if it is assumed that the goal of the extrapolation is to predict the exact value of the signal as closely as possible, which is undoubtedly true for many real world signals (including some financial ones [4]). There are important cases, however, where this error criterion is unsuitable. For example, assuming f represents an asset price in time, predicting future values of f with high accuracy is only of secondary importance. The most important prediction in this context is to determine whether the future price is going to rise or fall compared to the current level: in the former case, buying the asset now and selling it later will be profitable; in the latter, selling the asset now and re-buying it later will be profitable. In other words, the goal in this problem is not to minimize fˆ(n) − f (n) for the various k < n ≤ N , but to ensure that (fˆ(n)−f (n−1))·(f (n)−f (n−1)) > 0, namely that fˆ(n) − f (n − 1) and f (n) − f (n − 1) are of the same sign. The following two success rates are associated with this criterion: P |f (n) − f (n − 1)| |S(f )| , , rS (f ) = Pn∈S rH (f ) = N −k n>k |f (n) − f (n − 1)| where S(f ) = {n| k < n ≤ N, ˆ (f (n) − f (n − 1))(f (n) − f (n − 1)) > 0}. (3) rH measures the rate/probability of successful prediction of the sign of the increment of f , and has been considered in the literature before [5]. rS is a “soft” version of rH , where each prediction is weighted by the absolute actual increment, which is deemed to contribute positively if the sign is correctly predicted and negatively otherwise. The underlying principle behind the formulation of rS is that the larger the magnitude of an increment is, the larger are the profit opportunities, so it makes sense to focus on predicting correctly the sign of absolutely large increment.
Suppose f behaves like a martingale: then, for any m < n, E[f (n)|{f (i) : i ≤ m}] = f (m). This implies that setting fˆ(n) = f (n − 1) is essentially the best extrapolation strategy under eDM (this is usually referred to as the “na¨ıve” approximation). Nonetheless, this strategy is useless under rH or rS , as both rates default to 0 in this case. If the sign of the increment is predicted completely randomly every time, then rH → 0.5 as N → ∞. The success of an extrapolation strategy is measured, then, by the excess rH − 0.5. The condition rS > rH indicates that the extrapolation strategy considered is more successful in predicting the sign of increments of larger magnitude. 4. THE STATE OF THE ART It is, in general, difficult to have a clear view of research progress in the field of extrapolation, especially due to its links with financial forecasting. It is safe to assume that successful extrapolation techniques are usually considered proprietary/classified, and are not reported in public. In this sense, “we do not know what we do not know”. Regarding the technique about to be presented in this work, in particular, it is not clear how high rH should be in order for it to be considered as “successful”, or “more successful than others”. Seeking this information through private communication with interested third parties, consensus was reached on the fact that state of the art extrapolation achieves rH = 0.53 over signals similar to the ones considered here. EMD has been considered before in finance [1], and, in particular, in the context of prediction of crude oil prices, either in conjunction with neural networks [5], or in its improved form known as Ensemble EMD [7, 8], as well as of currency exchange rates [6]. However, data sets used therein are monthly values, hence the results are not directly comparable to the results obtained below.
s 1 1 2 5
2 5
1 1 2 5
2 5
1 1 2 5
2 5
5. THE ALGORITHM Having described all necessary components above, the actual description of the algorithm is now very simple. In order to determine fˆ(n), where n > k, a sample size M > 0 is fixed, and EMD is performed on the portion of the signal f (i), i = max(n−M, 1), . . . , n−1. Every resulting IMF and the trend are linearly extrapolated, and fˆ(n) is taken to be the sum of these extrapolation values. Unfortunately, as it will be seen below in more detail, the results obtained by this simple version of the algorithm are far from satisfactory. Therefore, instead of considering f directly, local averages of f will be considered, in order to improve performance. For any positive integer s, and any integer 0 ≤ t < s, set fs,t (i) =
1 s
s X j=1
f (t + (i − 1)s + j) for 1 ≤ i ≤
N −t . s
rH rS eDM A eDM N eDM S Euro-Dollar Exchange Rate – one step 48.6% 49.9% 0.0072 0.0050 0.0108 79.0% 89.1% 0.0020 0.0030 0.0018 54.9% 57.5% 0.0082 0.0062 0.0120 53.3% 57.0% 59.1% 64.3% 0.0112 0.0093 0.0160 58.5% 62.5% Euro-Dollar Exchange Rate – three steps 53.4% 55.3% 0.0213 0.0121 0.0569 49.1% 50.1% 56.0% 60.7% 0.0302 0.0187 0.0784 52.9% 52.3% Nasdaq – one step 48.4% 48.9% 0.0049 0.0033 0.0072 75.1% 84.9% 0.0018 0.0023 0.0017 56.0% 59.3% 0.0056 0.0043 0.0080 54.8% 58.2% 58.2% 60.6% 0.0083 0.0066 0.0116 56.6% 60.3% Nasdaq – three steps 52.8% 53.9% 0.0150 0.0085 0.0380 50.8% 51.4% 54.0% 52.7% 0.0230 0.0133 0.0557 50.1% 50.9% FTSE – one step 49.1% 50.3% 0.0036 0.0024 0.0054 74.9% 85.0% 0.0013 0.0017 0.0013 55.2% 58.3% 0.0042 0.0031 0.0059 54.8% 58.1% 57.7% 62.0% 0.0061 0.0049 0.0085 57.8% 62.3% FTSE – three steps 53.2% 54.4% 0.0111 0.0063 0.0279 50.9% 51.1% 53.5% 53.6% 0.0169 0.0098 0.0417 50.9% 52.7% Table 1. Extrapolation results
Clearly, f1,0 = f . Although, strictly speaking, fs,t no longer represents prices, it still represents a tradable quantity through options. It is, of course, possible, to extrapolate more distant values of the signal: given that f (i), i ≤ n − 1 are known, estimates fˆ(n − 1 + l), l ≥ 1 may be sought. The discussion so far focused on l = 1. 6. RESULTS The proposed algorithm from Section 5 has been tested on three data sets: a) The euro-dollar daily exchange rate until 21 Sep 2010 (3001 samples); b) The Nasdaq hourly closing value from 17 Dec 2002 to 31/03/2009 (12184 samples);
and c) The FTSE hourly closing value over the same period (13830 samples). The results are presented in Table 1, where the columns stand (from left to right) for the number of locally averaged points s (see Section 5), the rates rH and rS (see Section 3), and the extrapolation error eDM (see Section 3) computed using approximations yielded by the algorithm (A), the last observed value (“na¨ıve”, N), and the classical cubic spline extrapolation using the last five observed values (S). For s = 1 and one step extrapolation (l = 1, see Section 5), two rows are shown: the bottom one corresponds to the artificial, much smoother data data set generated by applying EMD (using Flandrin’s code [2]) to the original data set, discarding the first, most rapidly varying IMF, and then summing back the remaining ones (including the trend). For s = 2 and 5, two sets of values for rH and rS are shown: the top ones correspond to extrapolation by the algorithm, and the bottom ones by the cubic spline, respectively. The following conclusions can be drawn from the table. First, under eDM , the universally best performing extrapolation is the N-estimate: this is due to the fact that financial stochastic signals are, as is well known, martingales. Nevertheless, the A-estimate invariably beats the S-estimate, except for the artificial smoother data sets. Second, for s = 1 on the real data, rH and rS are very poor, essentially showing that the algorithm has no predictive abilities whatsoever, while for the artificial smoother data the corresponding values are very high. Third, for s = 2 and 5, and for one step extrapolation, rH and rS obtained by the algorithm almost invariably beat, if only by a small margin, their counterparts obtained by the cubic spline (the exception is s = 5 in FTSE), and invariably obey rH < rS ; for three steps extrapolation, they invariably and decisively beat their counterparts obtained by the cubic spline, and almost invariably obey rH < rS (the exception is s = 5 in Nasdaq). In brief, the algorithm performs better than the cubic spline, and is furthermore able to extrapolate more accurately the sign of the increment for larger absolute increments. Even for three steps extrapolation, the performance of the algorithm, as measured by rH and rS , is still very good. Further experiments indicate, as expected, that, in general, performance decays as the number of steps increases. It is clear that the main obstacle in the effective extrapolation of data “as is” (s = 1) by the algorithm is the most rapidly varying IMF, which is simply too strong and erratic. Analysis of this IMF in all three data sets leads to the conclusion that it exhibits the following universal features: a) its histogram has two peaks symmetrically placed around 0, and can, more precisely, be construed as the mixture of two identical bell-shaped distributions whose mean values are opposite numbers (a further investigation of whether these distributions are gaussian-like or heavy-tailed would certainly be interesting but is not attempted here); b) auto-correlation values are, in all cases, insignificant (below 5%), except for the first two values for each data set, which are negative and slightly sig-
nificant (up to 25%). As it is not clear if and how this small auto-correlation can be exploited further, this IMF can be construed as uncorrelated noise, impossible to extrapolate. Considering, instead, the signal of local averages for s > 1 heavily attenuates this IMF and improves extrapolation. 7. CONCLUSION An extrapolation algorithm based on Empirical Mode Decomposition was presented, and applied on three financial data sets, namely daily euro-dollar exchange rates, and hourly closing values of FTSE and Nasdaq. Its performance was evaluated based on both the classical approximation error of the unknown value, and on the percentage of the successful prediction of the sign of the next increment. Under the latter criterion, which is more suitable for financial data, the algorithm was found to outperform what is considered to be the highest percentage achievable till now. Moreover, the results remain acceptable for longer term extrapolation. 8. REFERENCES [1] K. Drakakis. “Application of Signal Processing to the Analysis of Financial Data.” IEEE Signal Processing Magazine, vol. 26(5), 2009, pp. 156–158, 160. [2] P. Flandrin. Matlab implementation of the EMD found at http://perso.ens-lyon.fr/patrick.flandrin/emd.html. [3] N.E. Huang, Z. Shen, S.R. Long, M.C. Wu, E.H. Shih, Q. Zheng, C.C. Tung, and H.H. Liu. “The Empirical Mode Decomposition method and the Hilbert spectrum for nonlinear and non-stationary time series analysis.” Proceedings of the Royal Society of London, Series A, vol. 454, 1998, pp. 903–995. [4] S. Makridakis and M. Hibon. “The M3-Competition: results, conclusions and implications.” International Journal of Forecasting, vol. 16, 2000, pp. 451–476. [5] L. Yu, S. Wang, and K.K. Lai. “Forecasting crude oil price with an EMD-based neural network ensemble learning paradigm.” Energy Economics, vol. 30, 2008, pp. 2623–2635. [6] L. Yu, S. Wang, and K.K. Lai. “A novel nonlinear ensemble forecasting model incorporating GLAR and ANN for foreign exchange rates.” Computers and Operations Research, vol. 32(10), 2005, pp. 2523–2541. [7] Z. Wu and N. Huang. “Ensemble Empirical Mode Decomposition: A Noise-Assisted Data Analysis Method.” Advances in Adaptive Data Analysis, vol. 1(1), 2009, pp. 1–41. [8] X. Zhang, K.K. Lai, and S. Wang. “A new approach for crude oil price analysis based on Empirical Mode Decomposition.” Energy Economics, vol. 30, 2008, pp. 2623–2635.
