Online machine learning algorithms for currency exchange prediction

Authors: Eleftherios Soulas and Dennis Shasha.
Date: April 2013

• Ongoing research on new type of Data Stream Management System (DBMS). Example of streaming database:
  • Aurora, MAIDS, Niagara, Telegraph
• Zhu and Shasha ¹⁾ using the first few coeffs of DFT transform to compute the distance between time series (eg. find the correlation).
• Zhao and Shasha ^{2) 3)} introduced a new sketch based data correlation strategy. Based on the Johnson-Lindenstrauss (JL) Lemma.
• Infos on statstream at: http://cs.nyu.edu/shasha/papers/statstream.html

• Goal: find correlation over windows from the same or different streams on synchronous and asynchronous (a.k.a. lagged) variations.
• Synchronous correlation: Given \(N_s\) streams, a start time \(t_{start}\) and a window size w, find, for each time window W of size w, all pairs of streams S1 and S2 such that S1 during time window W is highly correlated (over 0.95) with S2 during the same time window.
• Asynchronous correlation: allow for difference windows (with size w) W1 and W2.

• Cooperative : time series that exhibit a substantial degree of regularity. Reduction techniques: Fourier transforms ^{4) 5) 6)}, Wavelet transform ^{7) 8)}) , Singular Value Decomposition ⁹⁾ , Piecewise Constant Approximations ¹⁰⁾ .
• Uncooperative: Time series with no such periodical regularities.

• For uncooperative time series (for isntance returns of a stock), sketch-based approaches ¹¹⁾ can be used. We use random projection of the time series on random to exploit the bounds provided by the Johnson-Lindenstrauss lemma ¹²⁾.

• Notions of time-point, basic window and sliding window in Statstream framework.
• Benefits of basic window (bw): if asking correlations for \([t_i, t_{i+sw}]\), we get results at \([t_{i+bw},t_{i+sw+bw}]\).

• Intuition of Sketch approach ^{13) 14)} :
  • Given a point \(x \in \mathbb{R}^m\), we compute its dot product with d random vectors \(r_i \in 1,-1^m\).
  • The first random projection of x is given by \(y_1 = (x \cdot r_1, x \cdot r_2,\dots, x \cdot r_d)\)
  • We compute 2b more such random projections, so that we get \(y_1, y_2,\dots,y_{2b+1}\).
  • If w is another point \(w \in \mathbb{R}^m\), and \(z_1, z_2,\dots,z_{2b+1}\) are its projection using the same random vectors. Then the median of \(\|y_1 - z_1\|, \|y_2 - z_2\|, \dots, \|y_{2b+1} - z_{2b+1}\| \) is a good extimate of \(\|x - w\|\).
  • The estimate lies within a \(\theta(\frac 1d)\) factor of \(\|x - w\|\) with probability \(1 - {\frac 12}^b\).

• Sketch implementation in statstream uses a structured random vector approach, providing a 30 to 40 factor improvement in runtime.
• Example:
  • Build random vector \(r_{bw} = (r_0,r_1,\dots,r_{bw})\) where is \(r_i\) is 1 or -1 with probability 0.5.
  • Build control vector \(b = (b_0,b_1,\dots,b_{nb})\) where is \(b_i\) is 1 or -1 with probability 0.5. \(nb = \frac{sw}{bw}\).
  • Build the random vector for sliding window: \(r = (r_{bw}*b_0,r_{bw}*b_1,\dots,r_{bw}*b_{nb})\).

• Statstream implementation uses 60 random vectors.
• Pearson correlation is related to euclidian distance with: \(D^2(\hat{x},\hat{y}) = 2(1-corr(x,y))\).
• Sketches work much better tha SVD method (see results in section 2.2.9).

• Standard error is related to standard deviation by: \(SE_{\hat{x}} = \frac{std}{\sqrt{n}}\).

• Theoretical background for this paper given in ^{15) 16) 17) 18) 19) 20)}

• Regressor trained on a sliding window \([t_i,t_{i+sw}]\) and predicting \(t_{i+sw+1}\) with a linear model.
• We expect different outcomes with different window sizes: the window size that minimize the error is selected “off-line”.

• Here we randomly select which samples of the dataset would be candidate for training the model ⇒ using exponential random picking.

• Algorithm using warm start initialization ²¹⁾

• Problem of “catastrophic interference” ²²⁾

• Idea of adaptative learning rate for variants of stochastic gradient descent ²³⁾

• In the algorithm here a fixed learning rate is enough because of the sliding window usage.

• Absolute and relative error: \(\text{relative error}= \frac{\text{absolute error}}{\text{value of thing measured}}\)
• Mean squared error: \(MSE(y,\hat{y}) = \frac 1{n_{samples}} \sum\limits_{i=0}^{n_{samples}-1} (y_i - \hat{y}_i)^2\)
• Explained Variance score: \(ExpVar(y,\hat{y}) = 1 - \frac{Var\{y - \hat{y}\}}{Var\{y\}} \)
• \(R^2\) Score (eg. coefficient of determination): \(R^2(y,\hat{y}) = 1 - \frac {\sum_{i=0}^{n_{samples}-1} (y_i - \hat{y}_i)^2}{Var\{y\}}\) (Best possible score is 1.0, lower values are worse).

• Signals used in this algorithm for buy and sell:
  • if \(bid\_prediction_{t+1} > ask_t\), then buy at time t and sell later.
  • if \(ask\_prediction_{t+1} < bid_t\), then sell at time t and buy later.