A Synchrosqueezed Wavelet Transform assisted machine learning framework for time series forecasting Contributions to KDWEB poster session, a.d. 2016 Marco Stocchi, Ilaria Lunesu, Simona Ibba, Gavina Baralla, and Michele Marchesi Dept. of Electric and Electronics Engineering, University of Cagliari, Italy, {marco.stocchi,ilaria.lunesu,simona.ibba, gavina.baralla,michele.marchesi}@diee.unica.it Abstract. The attention of researchers in the field of signal analysis has recently been captured by several kinds of reassignment techniques. Among the reallocation methods the Synchrosqueezing approach maps a continuous wavelet transform from the time-scale to the time-frequency plane, allowing a much more definite and consistent representation of the frequency content of a signal. Its mathematical foundations prove that the Synchrosqueezing Wavelet Transform is directly related to the Empirical Mode Decomposition - EMD, since both methods allow the decomposition of a signal having finite energy in its intrinsic mode func- tions, each having time-varying frequency and amplitude. We develop a fast1 C++ implementation of the Synchrosqueezed Wavelet Transform - SST suitable for the synchronic extrusion of instantaneous frequency in- formation from univariate time series. Such module, totally configurable and adaptable to input datasets having different statistical properties, can be coupled with a predictor system to the purpose of real value fore- casting. We project such a composite application and plan to research the forecasting accuracy achievable, using different types of non parametric statistical estimators or neural regressors. Keywords: query trends, machine learning, wavelets, synchrosqueezing 1 Introduction In the last few years signal decomposition has been often employed to improve the forecasting capabilities of predictor systems. Among all the time-frequency 1 ISO/IEC 14882:2014 conformant C++ implementation compiled with speed max- imization optimization, inline functions expansion and intrinsic functions enabled, target machine x64. 2 M. Stocchi, I. Lunesu, S. Ibba, G. Baralla, and M. Marchesi analysis models suitable to be applied to univariate data series, one of the most simple yet effective method is the Empirical Mode Decomposition, researched in the late 90s by Huang et al. [2]. EMD is an empirical method, based on a sifting procedure aimed to identifi- cate a signal’s components, each of them featured by both amplitude and phase modulation. Sometimes it is compared to other analysis methods, such as Fourier Transforms or Wavelet decomposition. This approach is suitable to study signals which exhibits non-linearities and non-stationarity properties. The procedure al- lows signal decomposition in completely and closely orthogonal basis which may be expressed as the sum of the components of the form A(t)cos(φ(t)), plus a residual series. Such decomposition can be considered as a generalized Fourier series, in which the components phases and amplitudes are not constrained to be constant. Interest in such approach motivated Wu and Huang [3] in fur- ther research innovations, that brought them to formulate the Ensemble EMD (EEMD), in which the fixed number of intrinsic mode functions - IMFs of a series are found after having perturbated the signal with gaussian noise; the result is an improved IMF identification at a slightly higher computational cost. The interest and absolute generalized utility of EMD and EEMD intrigued researchers to ex- plore the possible mathematical foundations involved in the aforesaid empirical approaches. In recent years, Daubechies et al. [1] developed a new method called Syn- chrosqueezed Wavelet Transform, (SST), with the same objective of EMD, but providing a solid mathematical basis. They started from the theory of the Con- tinuous Wavelet Transform, (CWT), adding a procedure that reassigns the signal energy in the frequency domain. We believe that the use of SST method, used as a pre-processing signal module, could greatly enhance the forecasting accuracy of a predictor. Signal decomposition allows to extract some extra information which can be used in the machine learning field. This is the main technical argument of the present paper and it will be described in the next sections. The authors are planning to develop and develop a prediction system suitable for the analysis of streaming datasets such as the search engine query trends. We develop a fast C++ implementation of the Synchrosqueezing Wavelet Trans- form (see footnote 1), such system being configurable according to the specific properties of different types of input datasets. This paper is organized as follows: Section 2 provides the theoretical foun- dations of the SST, section 3 provides a description of several aspects of the implementation, referencing the features of the SST algorithm. Also, it depicts plannings for the most important machine learning aspects of the forecasting system. The last section provides the authors conclusions and portrays further research directions. 2 Description and implementation of SST A Continuous Wavelet Tranform - CWT allows the time-varying analysis of the frequency content of a signal f (t) having finite energy. Choosing an appropriate 3 mother wavelet function ψ(t) such that its Fourier transform ψ̂(ξ) = 0, ξ < 0, (hence a complex wavelet), the CWT of f (t) is defined as a series of parametric convolutions of the signal and the complex conjugate of scaled versions of the wavelet function. After the reassignment of the CWT, the vector of frequencies ω can be partitioned in equivalence classes having a chosen bandwidth, and the reconstruction is a piecewise performed function, thus creating the set of intrinsic mode functions mi (t) meant to be the original series components. From each mi (t), instantaneous amplitudes and phases can be recovered. Our actual position is to explore the possible machine learning approaches based on an input series preprocessing operation performed via the SST. For the scope of the present demonstration we develop a fast C++ imple- mentation of the SST algorithm, in which the complex wavelet function ψ(t) can be selected via parametric polymorphism. In order to be able to effectively use the system for prediction purposes, given the evident heaviness of the stepwise calculations, efficiency is considered paramount. Also, considering the structure of the CWT algorithm, hyperthreading is possible and, depending on the tar- get machine features, compiled code could run even more efficiently. Note that a concurrent implementation of the CWT could be feasible even implementing it using alternative algorithms; as such, a parallel implementation of the CWT portion of the SST is already under development. Several search engine query trends series are downloaded for automated test- ing and debugging purposes. We perform extensive analysis and synthesis tests on the gathered datasets in order to compare the reconstruction accuracies. Finally we are going to choose the wavelet function which gives the lower recon- struction error results. The system must be able to read streaming datasets such as the above mentioned search trends chunked with a fixed length window, the latter sliding from the beginning of the series to the last known data sample. Following the obtained empirical results we can consider feasible the cre- ation of a prediction system based on learning the features extracted by a SST preprocessing module. IMFs can be used as a training set for a prediction system such as a group of cooperating neural networks, hence forecasting the one step ahead value of each IMF using neural regression and summing up all the different contribu- tions to synthesize the final real value forecast. Also, a different approach could be to train a set of Nf detached perceptrons to forecast the one-step ahead instantaneous frequencies of the series. Let us recall that a Synchrosqueezed Wavelet Tranforms outputs a matrix Tf (ω, b) of size {Nf , N }, where Nf is the size of the frequencies vector F , and N is the size of an unpadded (i.e. raw) input series. Hence the number of inde- pendent neural regressors would be confined to be Nf . Each perceptron atom would be responsible to learn the ωf (a, b) rate of change in time direction, i.e. ∂ ∂t ωf (a, b), in order to be able to analytically find the one-step ahead ωf (a, b+1) value having empirically read the previous ωf (a, b). Having presented different possibile development directions, it should be now clear that the use of the SST as an assisting module to a time series prediction 4 M. Stocchi, I. Lunesu, S. Ibba, G. Baralla, and M. Marchesi system might introduce many innovation features in the machine learning field. We are going to explore all the above mentioned implementation paths and test them using the Bitcoin search engine queries datasets. Also, since it is possible to find in the literature several benchmark methods to the Bitcoin price prediction, in order to focus on the estimate of the forecasting accuracy of the system, we plan to test the latter using the Bitcoin price series (the hourly close data of the Bitcoin - US Dollar exchange rates - BTCUSD). 3 Conclusions The Synchrosqueezing Wavelet Transform allows an adaptive signal decomposi- tion on time-frequency plane and it is useful for analyzing multicomponent sig- nals. After a decomposition, signals can be written as a sum of intrinsic modes, this means that the SST can be used for prediction purposes. It is our opinion that such transform paves the way to novel machine learning approaches that focus on learning the rates of change of time series instead of fitting their values; such approaches could easily become a very active area of research in the next few years. Advantages to have such a type of system, totally configurable and flexible, are multiple. It is a completely dedicated implementation, customizable and reliable enough to be adapted to every kind of input dataset. Furthermore it allows to change or modify the algorithm code according to specific requirements. Independent graphics modules help us to detect errors and misconceptions dur- ing the development phase as well as when testing the selected datasets for research purposes. The combination of the SST and a prediction system might open the path to different and novel research directions. Actually we are in- vestigating about the applicability of the system in several interesting domains: Inflation forecasting, smart cities energy consumption, influenza prediction, eco- nomic fluctuations forecasts. Acknowledgments. We would like to express gratitude to Eugene Brevdo for his contribution to determine several theoretical misconceptions related to the SST, allowing us to find both poisonous and subtle bugs on the first implemen- tation of the system preprocessing module. References 1. I. Daubechies, J. Lu, and Hau-Tieng W. Synchrosqueezed wavelet transforms: An empirical mode decomposition-like tool. Applied and Computational Harmonic Analysis, 30:243–261, 2011. 2. N. Huang. The empirical mode decomposition and the hilbert spectrum for non- linear and non-stationary time series analysis. Proc. R. Soc. Lond., 454:903–995, 1998. 3. Z. Wu and N.E. Huang. Ensemble empirical mode decomposition: a noise-assisted data analysis method. Advances in Adaptive Data Analysis, 1:1–41, 2009.