Abstract:
A method and apparatus for the prediction of time series data, specifically, the prediction of a foreign currency exchange rate. The method disclosed transforms the time series data into a difference of a series, compresses the transformed data using a log transformation, converts the compressed data into symbols, and subsequently trains one or more neural networks on the symbols such that a prediction is generated. Alternative embodiments demonstrate the conversion by a self-organizing map and training by a recurrent neural network.

Description:
This is a continuation of application Ser. No. 08/628,442 filed Apr. 5, 1996, now abandoned. 
    
    
     FIELD OF THE INVENTION 
     This invention relates generally to the field of time series data prediction, and in particular to a method and apparatus for predicting daily foreign exchange rates. 
     BACKGROUND OF THE INVENTION 
     The volume of the foreign exchange market is staggering. In 1989, for example, about 650 billion dollars per day was exchanged. Of the currencies exchanged in the foreign exchange market, the most important are: the US dollar (which acts as a reference currency), the Japanese Yen, the British Pound, the German Mark, and the Swiss Franc. Given the importance and volume of foreign currency exchanged, many financial institutions are trying to predict foreign exchange rates using a variety of proprietary methods. See, for example, Jean Y. Lequarre, &#34;Foreign Currency Dealing: A Brief Introduction&#34;, in Time Series Prediction: Forecasting the Future and Understanding the Past&#34;, A. S. Weigend and N. A. Gershenfeld, eds., Addison-Wesley, 1993. 
     Unfortunately, however, foreign exchange rate data exhibit very high noise, and significant non-stationarity thereby minimizing their predictability. Attempts to overcome the high noise inherent in foreign exchange rate data using an overparameterised model and/or techniques such as weight decay or weight elimination to control overfitting have been described by A. S. Weigend, B. A. Huberman, and D. E. Rumelhart in an article entitled &#34;Predicting Sunspots and Exchange Rates with Connectionist Networks&#34;, which appeared in Nonlinear Modeling and Forecasting, SFI Studies in the Sciences of Complexity Proc., Vol. XII, Addison-Wesley, 1992, but have met with only limited success. 
     Neural network technology has been of great interest in recent years, and has recently been applied to the problem of predicting noisy time series data. For example, U.S. Pat. No. 5,444,819 (issued to Michiro Negishi on Aug. 22, 1995, hereinafter referred to as the &#39;819 patent) teaches a system into which time series data are input and moving average values and their differences are generated. As taught by the patentees, a standard neural network is trained on the averages, differences, and a pattern class to predict the value of change. 
     A method and apparatus for retrieving signals embedded in noise and subsequently analyzing the signals was shown in U.S. Pat. No. 5,402,520 (issued to Bonnie S. Schnitta on Mar 6, 1992 and hereinafter referred to as the &#39;520 patent). The apparatus disclosed in this patent includes an input device for receiving input signals having noise and at least one noise filter retrieves data signals embedded in the input signals. 
     Despite initial optimism for neural network technology, its effect to date on the prediction of noisy time series data such as foreign currency exchange data has been limited. Consequently, a continued need exists in the art for methods and apparatus which quickly, efficiently, and accurately allow prediction from noisy time series data and in particular, to predict daily foreign exchange rates. 
     SUMMARY OF THE INVENTION 
     The above problem is solved and an advance is made over the prior art in accordance with the principles of the invention wherein a prediction is made of a time series of data which oftentimes exhibits significant nonstationarity and noise. 
     Viewed from one aspect, the invention is directed to an apparatus for predicting time series data. The invention includes: a preprocessing module for transforming the data; a symbolic conversion module which produces a sequence of symbols from the transformed data; and a grammatical inference module which predicts a given quantity from the sequence of symbols. Enhancements to the apparatus include a confidence estimation module which estimates a confidence of the given quantity, a rule extraction module which extracts one or more rules, and a rule interpretation module which produces predictions using the extracted rules. 
     Viewed from another aspect, the invention is directed to a method for predicting time series data. The method disclosed transforms the time series data into a difference of a series, compresses the transformed data using a log transformation, converts the compressed data into symbols, and subsequently trains one or more neural networks on the symbols such that a prediction is generated. Alternative embodiments demonstrate the conversion by a self-organizing map and training by a recurrent neural network. 
     Other advantages and features will become apparent from the following drawings, detailed description, and claims. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The teachings of the present invention can be readily understood by considering the following detailed description in conjunction with the accompanying drawings, in which: 
     FIG. 1 is a graph of exemplary time-series data; 
     FIG. 2 is a flow chart showing the processing of time-series data according to the teachings of the present invention; 
     FIG. 3 is an illustration of a self-organizing map; 
     FIG. 4 is an illustration of an Ellman neural network; 
     FIG. 5 is an illustration of a sample extracted automata; and 
     FIG. 6 is a block diagram of a system for predicting time-series data according to the teachings of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     A preferred embodiment of the invention will now be described while referring to the figures, several of which may be simultaneously referred to during the course of the following description. Before thoroughly describing the method and apparatus which is the subject of the present invention, however, a discussion of the theoretical background is helpful. 
     Particularly, the efficient market hypothesis (EMH) has found broad acceptance in the financial community and in its weak form, asserts that the price of an asset reflects all of the information that can be obtained from past prices of the asset, i.e., the movement of the price is unpredictable. See, for example, H. White, &#34;Economic Prediction Using Neural Networks: The Case of IBM Daily Stock Returns,&#34; in the proceedings of the IEEE Conference on Neural Networks, pages 451-458. 
     The best prediction of a price is the current price when the actual price follows what is generally called a random walk. One argument in support of the EMH is that if any profit opportunities appear, they will be exploited immediately by traders, and thereby disappear. Conversely, arguments against the EMH include the fact that not all information reaches all traders simultaneously, and that traders with more sophisticated methods may be able to make better use of the available information. 
     Assuming the validity of the EMH, then a financial series can be modeled as the addition of a noise component at each step: 
     
         x(k+1)=x(k)+ε(k),                                  (1) 
    
     where ε(k) is a zero mean Gaussian variable with variance σ and x(k) is the value of the time series at step k. The best estimation is: 
     
         x(k+1)=x(k)                                                (2) 
    
     In other words, if the series is truly a random walk, then the best estimate for the next time period is equal to the current estimate. Now, if it is assumed that there is a predictable component to the series, then: 
     
         x(k+1)=x(k)+f(x(k),x(k-1), . . . ,x(k-n+1))+ε(k)   (3) 
    
     may be used where ε(k) is a zero mean Gaussian variable with variance σ, and f(·) is a nonlinear function in its arguments. In this case, the best estimate is given by 
     
         x(k+1)=x(k)+f(x(k),x(k-1), . . . ,x(k-n+1))                (4) 
    
     Attempts at prediction using this model are problematic as the series often contains a trend. For example, and with reference to FIG. 1, a neural network trained on section A has no chance of generalizing to the test data in section B, because the model was not trained with data in this range. Those skilled in the art can readily appreciate that neural networks are good at interpolation, and not extrapolation. 
     A common solution to this is to use the model 
     
         δ(k+1)=f(δ(k),δ(k-1), . . . ,δ(k-n+1))+ν(k),(5) 
    
     where 
     
         δ(k+1)x(k+1)-x(k)                                    (6) 
    
     and ν(k) is a zero mean Gaussian variable with variance σ. In this case, the best estimate is 
     
         δ(k+1)=f(δ(k),δ(k-1), . . . ,δ(k-n+1)).(7) 
    
     Note that the first order differences are being used instead of the raw time series. 
     With reference to FIG. 2, there is shown a block diagram of the system which is the subject of the present invention. Specifically, raw financial series 200 are received by differencing block 210, whose output is processed at log compression block 220 which compresses the dynamic range of the series and reduces the effect of any outlying data. Next, quantization/symbolic encoding is performed at block 230, and grammatical inference (see, for example, C. L. Giles et al, &#34;Second-Order Recurrent Neural Networks for Grammatical Inference,&#34; 1991 IEEE INNS International Conference on Neural Networks, IEEE Press, Piscataway, N.J., 1992) at block 240 which results in change prediction output 250. 
     The above process starts with a set of raw time series values y(k), k=1, 2, . . . , N, and y(k) ε . These values denote the daily closing prices of a particular financial time series, however, they could be any time series. Next, the first difference of the series, y(k), is taken as follows: 
     
         δ(k)=y(k)-y(k-1),                                    (8) 
    
     which results in δ(k), δ(k) ε , k=1, 2, . . . , N-1. 
     In order to compress the dynamic range of the series and reduce the effect of outliers, a log transformation of the data is used, namely: 
     
         x(k)=sign(δ(k))(log(|δ(k)|+1)),(9) 
    
     which results in x(k), k=1, 2, . . . , N-1, x(k) ε. However, for some time series this is not necessary. Other compression methods may be used for other time series. 
     Next, a delay embedding of this series is considered, 
     
         X(k,d.sub.1)=(x(k),x(k-1),x(k-2), . . . ,x(k-d.sub.1 +1)), (10) 
    
     where d 1  is the delay embedding dimension and X(k,d 1 ) is a state vector. 
     This delay embedding forms the input to a self-organizing map (SOM). Consequently, the SOM input is the last d 1  values of the log transformed delta time series. The output of the SOM is a topographical location of the winning node, where each node represents one symbol in the resulting grammatical inference problem. 
     As used in the present invention, the SOM can be represented by the equation 
     
         S(k)=g(X(k,d)),                                            (11) 
    
     where S(k) ε  0, 1, 2, . . . n s  -1!, n s  is the number of symbols (nodes) for the SOM. By way of convenience, each node in the SOM is assigned an integer index ranging from 0 to the number of nodes minus 1. 
     Next, an Elman recurrent neural network is trained on the sequence of outputs from the SOM. Those skilled in the art can readily appreciate that many recurrent networks may be used. For the recurrent network: 
     
         O(k+1)=C.sup.T z.sub.k +c.sub.0                            (12) 
    
     and 
     
         z.sub.k =F.sub.n.sbsb.h (Az.sub.k-1 +Bu.sub.k +b),         (13) 
    
     where C is a n h  ×n o  vector representing the weights from the hidden layer to the output nodes, n h  is the number of hidden nodes, n o  is the number of output nodes, c 0  is a scalar, and z k , z k  ε  n .sbsp.h is an n h  ×1 vector which denotes the outputs of the hidden layer neurons. 
     Additionally, u k  is a d 2  ×1 vector, where d 2  is the embedding dimension used for the the input window of symbols that is presented to the SOM. As such, u k  may be represented by: ##EQU1## and A and B are matrices of appropriate dimensions which represent the feedback weights from the hidden nodes to the hidden nodes and the weights from the input layer to the hidden layer respectively. Similarly, F n .sbsb.h is a n h  ×1 vector containing the sigmoid functions, b is a n h  ×1 vector that denotes the bias of each hidden layer neuron, O(k) is a n o  ×1 vector containing the outputs of the network, and n o  is 2. 
     Consequently, 
     
         O(k+1)=F.sub.1 (δ(k),δ(k-1),δ(k-2),δ(k-3),δ(k-4))(15) 
    
     or 
     
         O(k+1)=F.sub.2 (y(k),y(k-1),y(k-2),y(k-3),y(k-4),y(k-5)).  (16) 
    
     As an example of how the recurrent neural network could be trained, the net could have two outputs whereby the first output is trained to predict the probability of a positive change in the series, and the second output is trained to predict the probability of a negative change. 
     The self-organizing map (SOM), described by Teuvo Kohonen in an article entitled &#34;The Self-Organizing Map,&#34; which appeared in Proceedings of the IEEE, vol. 78, pp. 1464-1480, in 1980, is an unsupervised learning process which learns a distribution of a set of patterns without any class information. In particular, a pattern is projected from a possibly high dimensional input space  to a position in the map, a low dimensional display space . Oftentimes, the display space  is divided into a grid having a number of intersections wherein each intersection is represented in the network by a neuron. Information is encoded as the location of an activated neuron. The SOM, unlike most classification or clustering techniques, preserves the topological ordering of classes in the input space  in the resulting display space . Similarity as measured using a metric in the input space , is preserved in the display space . 
     In operation, the SOM defines a mapping from an input space  n  onto a topologically ordered set of nodes, usually in a lower dimensional space . An example of such a two-dimensional SOM is shown in FIG. 3. A reference vector, m i  ≡ μ i1 , μ i2 , . . . , μ in  ! T  ε n , is assigned to each node in the SOM. 
     During training, each input x is compared to all the m i  obtaining the location of the closest match according to a particular metric. The input point is mapped to this location in the SOM. 
     Nodes in the SOM are updated according to the metric and their position in relation to the winning node. For example, nodes may be updated according to: 
     
         m.sub.i (t+1)=m.sub.i (t)+h.sub.ci (t) x(t)-m.sub.i (t)!,  (17) 
    
     where t is the time during learning and h ci  (t) is the neighborhood function, a smoothing kernel which is maximum at m c . Usually, h ci  (t)=h(∥r c  -r i  ∥,t), where r c  and r i  represent the locations of nodes in the SOM output space . r c  is the node with the closest weight vector to the input sample and r i  ranges over all nodes. h ci  (t) approaches 0 as ∥r c  -r i  ∥ increases and also as t approaches ∞. A widely applied neighborhood function is: ##EQU2## where α(t) is a scalar valued learning rate and σ(t) defines the width of the kernel. Those skilled in the art can readily appreciate that a SOM can be viewed as a non-linear projection of the probability density, p(x), of the input patterns x. 
     As described, the nodes in the display space  encode the information contained in the input space  n . Since there are M nodes in , this implies that the input pattern vectors x ε  n  are transformed to a set of M symbols, while preserving their original topological ordering in  n . Thus, if the original input patterns are highly noisy, the quantization into the set of M symbols while preserving the original topological ordering can be understood as a form of filtering. The amount of filtering is controlled by M. If M is large, this implies there is little reduction in the noise content of the resulting symbols. On the other hand, if M is small, this implies that there is a &#34;heavy&#34; filtering effect, resulting in only a small number of symbols. 
     With reference now to FIG. 4, one example of a recurrent neural network which could be used for grammatical inference in the present invention is the Elman neural network. As is shown in FIG. 4, the Elman neural network has feedback from each of the hidden nodes to all of the hidden nodes. The set of M symbols from the output of the SOM are discretely encoded in a linear fashion into a single input for the recurrent neural network (e.g. if M=3, the single input is either -1, 0, or 1). Those skilled in the art will readily recognize that linear encoding is justified by the topographical order of the symbols. In order to facilitate the training of the recurrent network, an input window of is used, i.e. a number of the most recent symbols are presented to separate input neurons of the recurrent neural network. 
     According to the teachings of the present invention, non-stationarity of the signal is advantageously overcome by building models based on a short time period only. Specifically, models are trained using a certain number of data points. Separate models may be trained for prediction at various times. 
     The extraction of symbolic knowledge greatly aids the interpretability of the solution. The ordered triple of a discrete Markov process ({state; input→next-state}) can be extracted from a recurrent neural network and used to form an equivalent deterministic finite state automata (DFA). While this extraction can be done by clustering the activation values of the recurrent state neurons, automata extracted using this process can only recognize regular grammars. Note that as used herein, a regular grammar G is a 4-tuple G={S, N, T, P} where S is the start symbol, N and T are non-terminal and terminal symbols, respectively, and P represents productions of the form A→a or A→aB where A, B ε N and αε T. 
     A method which can be used for automata extraction in the present invention is the same as described C. L. Giles, et. al., in an article entitled &#34;Learning and Extracting Finite State Automata with Second-Order Recurrent Neural Networks&#34;, which appeared in Neural Computation, 4(3), pp. 393-495, 1992. However, other extraction methods can be used and are known in the art. 
     A sample extracted automata for the British Pound is shown in FIG. 5. The DFA has been minimized using minimization techniques known in the art. 
     Summarizing the DFA extraction method, the state z k  is first divided into q cells, i.e., z ki , i=1, 2, . . . , n h  is divided into q segments. Hence the total number of quantized states is q n .sbsp.h. By running the inputs u k , k=1, 2, . . . , N through the network, the corresponding set of activations z k , k=1, 2, . . . , N can be obtained. These activations are often clustered in the activation space and quantize to the same value. 
     For a given input sequence, the path through the DFA may be followed. For the example given in FIG. 5, ##EQU3## and the output is given by ##EQU4## where S i , i=0, 1, 2 are the output symbols from the SOM. (In FIG. 12 S 1  is the dotted line, S 2  is the gray line, and S 3 , is the solid line). n i , i=1, 2, . . . , 9 are the nodes in the minimized DFA. 
     The DFA nodes, n i , i=1, 2, . . . , 9 are not related to any physical entities. Nevertheless, the extracted DFA may be linked back to the original time series as follows: 
     1. Transforming the SOM input data sequence, X(k, d 1 ), into the SOM output symbols, giving, →; and 
     2. Following the path of these symbols through the DFA and determining if the current state corresponds to a positive or negative change. 
     Hence, for a given sequence of financial data, the transitions in the DFA may be determined. 
     A block diagram of one embodiment is shown in FIG. 6. Specifically, time series data 600 is received by pre-processing module 610, which transforms the input data. In a preferred embodiment, the pre-processing module may contain differencing module 611 which reduces any nonstationarity of the data, and compression module 613, which generates a log compression of the data. 
     Symbolic conversion module 620 which preferrably is performed with self-organizing map 621, produces a sequence of symbols from the transformed data. Grammatical inference module 630, having one or more recurrent neural networks 631 or employing other grammatical inference methods, predicts a given quantity from the sequence of symbols. 
     Alternatively, the prediction system may include confidence estimation module 650 which estimates a confidence of the given quantity using any of a variety of metrics. 
     Rule interpretation module 640, advantageously produces predictions using the extracted rules. 
     It should now be quite evident to those skilled in the art, that while the invention was shown and described in detail in the context of a preferred embodiment, and with various modifications thereto, a wide variety of other modifications can be made without departing from the scope of our inventive teachings.