= 5: 76.08∗∗∗ , 0.70k = 6: 87.65∗∗∗ , 0.78k = 7: 111.06∗∗∗ , 2.57k = 8: 113.33∗∗∗ , 3.86k = 9: 117.60∗∗∗ , 3.88k = 10: 124.61∗∗∗ , 4.02k = 15: 143.77∗∗∗ , 5.35k = 20: 172.06∗∗∗ , 11.12
k = 1: 82.96, 0.59k = 2: 97.67∗∗∗ , 1.18k = 3: 98.78∗∗∗ , 1.58k = 4: 107.73∗∗∗ , 1.58k = 5: 117.94∗∗∗ , 1.62k = 6: 131.67∗∗∗ , 6.05k = 7: 132.71∗∗∗ , 6.21k = 8: 137.94∗∗∗ , 6.86k = 9: 141.91∗∗∗ , 6.94k = 10: 142.09∗∗∗ , 8.15k = 15: 151.57∗∗∗ , 10.13k = 20: 209.19∗∗∗ , 12.42
k = 1: 0.21, 0.01k = 2: 0.35, 0.19k = 3: 5.09∗∗ , 0.41k = 4: 5.41∗ , 0.70k = 5: 11.42∗∗ , 1.34k = 6: 15.64∗∗∗ , 1.73k = 7: 17.12∗∗∗ , 1.77k = 8: 17.84∗∗∗ , 1.77k = 9: 20.37∗∗∗ , 1.96k = 10: 23.13∗∗∗ , 1.99k = 15: 38.50∗∗∗ , 5.76k = 20: 46.12∗∗∗ , 11.42
k = 1: 20.59∗∗∗ , 0.06k = 4: 11.91∗∗∗ , 0.18k = 8: 10.15∗∗∗ , 0.48k = 12 : 7.34∗∗∗ , 0.42
k = 1: 86.81∗∗∗ , 0.59k = 4: 24.61∗∗∗ , 0.39k = 8: 14.02∗∗∗ , 0.85k = 12: 9.74∗∗∗ , 0.73
k = 1: 0.21, 0.01k = 4: 1.33, 0.17k = 8: 2.03∗∗ , 0.21k = 12: 1.74∗ , 0.32
The columns from left to right denote the null hypothesis, name of the test applied, time seriesinput, and the test statistic output per currency pair. ∗ , ∗∗ , and ∗∗∗ indicate rejection of the nullhypothesis at the 10%, 5%, and 1% significance level. k denotes the number of lags included in thetest regression
to the ones of a normal distribution. It is possible to remove heteroskedastic effects within the time series by estimating ARCH models, a family of models thatwas introduced by [115] and generalized as GARCH (Generalized ARCH) by [49].A GARCH model consists of two equations. The first is the conditional mean equation which has already been estimated in (8.12)–(8.14). The second equation is theconditional variance equation whose form determines the type of GARCH model.Academic literature has proposed many different types of GARCH models (see[50,51,318] for good surveys). The generic GARCH(1,1) model with one error termand one autoregressive term is22σt2 = (1 − α − β )σ 2 + αεt−1+ β σt−1
=σwhere
2
(8.18)
22+ α (εt−1− σ 2 ) + β (σt−1− σ 2)
σ2 =
ω1−α−β
(8.19)
with ω denoting the GARCH constant, α ≥ 0 denoting the GARCH error coefficient, and β ≥ 0 denoting the GARCH lag coefficient. An ordinary ARCH model isa special case of a GARCH specification in which there are no lagged forecast variances in the conditional variance equation. The GARCH(1,1) process is the most
8.2 Empirical Analysis
59
prominent specification for GARCH volatility models, being relatively easy to estimate and generally having robust coefficients that are interpreted naturally in termsof longterm volatilities and short-run dynamics. Many financial markets, includingstock and bond markets, have been successfully characterized by such models. Sincethere is a convergence in term structure forecasts to the long-term average volatilitylevel, the time series of any GARCH volatility forecast will be stationary. However, currencies tend to have volatilities that are not as mean-reverting as the ones ofother types of financial assets [151] or that may not mean-revert at all. In this casethe usual stationary GARCH models will not apply. Thus it might be more usefulin the currency markets to use a component GARCH model in order to regain theconvergence in GARCH term structures, by allowing for a time-varying long-termvolatility [117, 119, 120]. In components GARCH, σ 2 is replaced by a time-varyingpermanent component given by22qt = ω + ρ (qt−1 − ω ) + ζ (εt−1− σt−1)
(8.20)
Therefore the conditional variance equation in the components GARCH model is22σt2 = qt + α (εt−1− qt−1 ) + β (σt−1− qt−1 )
(8.21)
Equations (8.20) and (8.21) together define the components model. If ρ = 1, the permanent component to which long-term volatility forecasts mean-revert is just a random walk. While the components model has an attractive specification for currencymarkets, parameter estimates may lack robustness and therefore specification has topass diagnostic tests. We estimated the component GARCH model for EUR/GBPreturns as
Δ yt = −0.0382Δ yt−1 − 0.0462Δ yt−3 + εt(−1.56)
(−1.86)
qt = 3.05E − 05 + 0.9825(qt−1 − 3.05E − 05)(7.31)
(137.39)
(7.31)
(8.22)
22− σt−1)+ 0.0513(εt−1(5.59)
22σt2 = qt + 0.0568(εt−1− qt−1 ) − 0.9092(σt−1− qt−1 )(4.67)
(−29.01)
For EUR/USD returns the following model was estimated:
Δ yt = −0.6253Δ yt − 1 + 0.5666εt−1(−3.24)
(2.79)
qt = 4.11E − 05 + 0.9869(qt−1 −4.11E − 05)(11.78)
(161.67)
(11.78)
22− σt−1)+ 0.0227(εt−1(3.29)
22σt2 = qt − 0.0348(εt−1− qt−1 ) + 0.5296(σt−1− qt−1)(−2.02)
(−1.33)
(8.23)
60
8 Statistical Analysis of Daily Exchange Rate Data
The estimates of persistence in the long run component are ρ̂ = 0.9825 forEUR/GBP and ρ̂ = 0.9869 for EUR/USD, indicating that in both models thelong run component converges very slowly to the steady state. The short run volatility component also appears to be significantly different from zero in both models.LB Q-statistics as well as the F-statistics of the ARCH-LM test in Table 8.4 demonstrate that second-moment dependencies in the squared residuals of the componentGARCH models have now disappeared at any lag. However, this could not beachieved for EUR/JPY returns. The reason could be that volatility is higher in afalling EUR/JPY market than it is in a rising market. This observation is knownas leverage effect (see [120]). In other words volatility in the EUR/JPY market isan asymmetric phenomenon which cannot be captured by a symmetric componentGARCH model that is only able to model ordinary volatility clustering. Consequently, for EUR/JPY it is better to specify an asymmetric component GARCHmodel22− σt−1) + θ1 z1tqt = ω + ρ (qt−1 − ω ) + φ (εt−122σt2 = qt + α (εt−1− qt−1 ) + γ (εt−1− qt−1 )dt−1
(8.24)
2− qt−1 ) + θ2 z2t+ β (σt−1
where dt = 1 if εt < 0, and 0 otherwise. In this model positive shocks (εt > 0), andnegative shocks (εt < 0) have different effects on the conditional variance. Positiveshocks have an impact of α , while negative shocks have an impact of (α + γ ). Ifγ > 0 we say that a leverage effect exists in that negative shocks increase volatility.If γ = 0, the news impact is asymmetric. The asymmetric component model forEUR/JPY returns was estimated as
Δ yt = 0.0314Δ yt−1 + εt(1.29)
qt = 6.75E − 05 + 0.9932(qt−1 − 6.75E − 05)(5.14)
(339.60)
(5.14)
22− σt−1)+ 0.0369(εt−1
(8.25)
(5.38)
22σt2 = qt − 0.0477(εt−1− qt−1 ) + 0.2132(εt−1− qt−1 )dt−1(−1.94)
(5.91)
2−0.0013(σt−1− qt−1 )(−0.01)
We observe that in (8.25) the leverage effect term γ is significantly positive and soit appears that there is indeed an asymmetric effect. Note that it is important thatwe use the quasi-likelihood robust standard errors (z-values in brackets) since theresiduals are highly leptokurtic.
8.2 Empirical Analysis
61
8.2.5 NonlinearityFinally, we investigated the existence of nonlinear dependencies within the data.Hsieh [197] divides the realm of nonlinear dependencies into two broad categories– additive nonlinear dependence and multiplicative nonlinear dependence. Additive nonlinearity, also known as nonlinearity-in-mean, enters a process through itsmean or expected value, so that each element in the sequence can be expressed asthe sum of a zero-mean random element and a nonlinear function of past elements.With multiplicative nonlinearity, or nonlinearity-in-variance, each element can beexpressed as the product of a zero-mean random element and a nonlinear functionof past elements, so that the nonlinearity affects the process through its variance.Lee [248] examined the performance of a range of tests on nonlinear dependenciesacross a variety of data generating processes. They find that no single test dominatesall the others. In the light of this finding, it is advisable to use more than one test.One of the most general and widely used tests for detecting nonlinear dependenciesin a time series is the BDS test [60]. The BDS statistic has its origins in the correlation dimension plots of [175], which were developed for studying low-dimensionalchaos in time series in physics applications. A chaotic dynamic process is a complex, but deterministic, nonlinear dynamic process. A simple example is the logisticmap yt = 4yt−1 (1 − yt−1 ) where yt ∈ (0, 1). Such a process may look random, butis, at least in theory, potentially perfectly predictable. However, financial time seriesare more likely to follow nonlinear dynamic processes that are stochastic, rather thanones that are chaotic and deterministic (additive nonlinearities). The BDS statisticwas developed to detect the existence of any type of either of these two categoriesof nonlinear dynamics. Thus if the null hypothesis of i.i.d. is rejected, it is still notclear which of the two is the reason. For this reason we additionally apply Ramsey’sRESET Test [335] and the McLeod and Li Test [286]. The Ramsey RESET-Testchecks the null hypothesis of a correctly specified linear model by adding a certainnumber n of higher order fitted terms. If the coefficients of these terms are significantly different from zero, it can be inferred that the linear model is not goodenough due to existing additive nonlinear dynamics. In contrast, the McLeod and LiTest whose results have been separately discussed above, is useful for detecting multiplicative nonlinearities. For EUR/GBP and EUR/JPY, the test results on squaredARMA residuals, as depicted in Table 8.5, seem to correspond. The McLeod Litest finds significant multiplicative nonlinearities at the 1% level. In addition, theRamsey RESET test identifies additive nonlinearities at the 1% level, which is aparticularly interesting result if we consider that such nonlinearities are generallythought to be of second order nature. Since these two results are consistent with thestrong rejections of the null hypothesis at the 1% level by the BDS test statistic, itcan be concluded that linear model residuals of the EUR/GBP and EUR/JPY seriesare significantly determined by first and second order nonlinearities.After having removed multiplicative nonlinearities by the component GARCHmodels from (8.22) and (8.25), the BDS test statistic still rejects the null hypothesis of i.i.d. for both currency pairs. There are two possible explanations. First, although the McLeod Li Test results suggest the opposite, one might still think that
62
8 Statistical Analysis of Daily Exchange Rate Data
Table 8.5 Testing against LinearityNull
Test
Input
OutputEUR/GBP
EUR/JPY
EUR/USD
Linearity
RESET
ARMA-,Residualsof Δ yt
n = 1: 2.81∗
n = 2: 6.03∗∗∗n = 3: 4.83∗∗∗n = 4: 4.04∗∗∗
n = 1: 0.00n = 2: 6.64∗∗∗n = 3: 4.68∗∗∗n = 4: 4.59∗∗∗
n = 1: 0.0015n = 2: 0.1662n = 3: 3.2273∗∗n = 4: 2.4309∗∗
i.i.d.
BDS
ARMAResidualsof Δ yt
m = 2: 0.0099∗∗∗m = 3: 0.0172∗∗∗m = 4: 0.0235∗∗∗m = 5: 0.0268∗∗∗
m = 2: 0.0076∗∗∗m = 3: 0.0178∗∗∗m = 4: 0.0248∗∗∗m = 5: 0.0288∗∗∗
m = 2: −0.0007m = 3: 0.0001m = 4: 0.0014m = 5: 0.0025
GARCH(1,1)Residualsof Δ yt
m = 2: 0.0101∗∗∗m = 3: 0.0175∗∗∗m = 4: 0.0237∗∗∗m = 5: 0.0271∗∗∗
m = 2: 0.0076∗∗∗m = 3: 0.0178∗∗∗m = 4: 0.0248∗∗∗m = 5: 0.0288∗∗∗
m = 2: −0.0007m = 3: 0.0002m = 4: 0.0014m = 5: 0.0025
The columns from left to right denote the null hypothesis, name of the test applied, time seriesinput, and the test statistic output per currency pair. ∗ , ∗∗ , and ∗∗∗ indicate rejection of the nullhypothesis at the 10%, 5%, and 1% significance level. n denotes the number of fitted terms includedin the test regression. m denotes the number of correlation dimensions for which the test statisticis computed. For Ramsey’s RESET, the test statistics from the F-test are provided
the component GARCH models are prone to misspecification. Consequently, the rejection of the null would be due to excess multiplicative nonlinearities. Hsieh [197]examined the daily foreign exchange rates versus the USD for five major currencies– the GBP, the CAD, the DEM, the JPY, and the CHF. All five of these time seriesexhibit highly significant BDS statistics even after autocorrelation effects and linearholiday and day-of-the-week effects have been filtered out, thereby indicating theexistence of strong nonlinear dependencies within these data series. Hsieh furtherfinds that a GARCH(1,1) model with either a Student’s t or a generalized error distribution can describe the Canadian Dollar and the Swiss Franc exchange rates verywell and the Deutsche Mark exchange rate reasonably well. While a GARCH(1,1)model can also account for most of the nonlinear serial dependencies within theGBP and the JPY exchange rates, such GARCH models do not fit either of thesetime series very well. Similarly, [198] finds for value-weighted, size-decile portfolios of weekly stock returns from 1963 to 1987 that these returns also exhibitnonlinear serial dependencies and that conditional heteroskedasticity could be thesource of these nonlinearities, but that none of the ARCH models seem to adequately describe these data. However, we argue that based on our previous analyses,the presence of additive nonlinearities is more likely. Thus, although it is possiblefor exchange rates to be linearly uncorrelated and nonlinearly dependent ([197],p. 340), as is the case for the EUR/JPY time series, it is not only the changingof variances that is responsible for the rejection of i.i.d. in exchange rate changes([197], p. 359), but also the changing of the mean. For EUR/USD, contradictiveresults were obtained. On the one hand, additive and multiplicative nonlinearities
8.2 Empirical Analysis
63
could be detected separately by the RESET test and the McLeod Li test. On theother hand, these results could not be confirmed by the BDS test which would imply that ARMA residuals are i.i.d. The reason for this phenomenon could be foundin the power of the BDS test itself. According to [61], applying the BDS test toresiduals from some preliminary estimation of a fitted model can be problematicsince the resultant “nuisance parameter” problem affects the behavior of the BDSstatistic in finite samples and leads to the BDS test’s having an actual size greaterthan its nominal size. This problem is exacerbated and exists even for large sampleswhen the residuals come from a GARCH-type model, in which case the BDS testwill lack power to reject a false model.
8.2.6 ResultsThe purpose of above analysis was to examine the degree of randomness ofEUR/GBP, EUR/JPY, and EUR/USD time series statistically, in order to justifyour SVM approach to exchange rate forecasting. In supervised learning, it is assumed that a functional relationship is implicitly reflected within the input/outputpairings. However, this assumption may be questionable if the output data doesnot contain structure, but instead is severely corrupted by noise. Then it may bedifficult to identify a reliable functional relationship. It was shown that all threetime series contain statistically significant structure. EUR/GBP exhibits both lineardependencies, as well as nonlinear dependencies in the first and second moment.EUR/JPY does not exhibit linear dependencies but is significantly determined byfirst and second order nonlinearities. For EUR/USD, linear dependencies couldbe detected, but contradictive test results were obtained when examining potentialnonlinearities. Still it remains to be seen whether SVMs are able to exploit nonlinearrelationships out-of-sample and how they compare to linear benchmark models.
Chapter 9
Support Vector Classification
9.1 Binary Classification Problem (BCP)Computational geometry is the branch of computer science that studies algorithmsfor solving geometric problems. The input to a computational-geometry problemis typically a description of a set of geometric objects, such as a set of points, aset of line segments, or the vertices of a polygon. The output is a response to aquery about these objects (such as whether any of the lines intersect), or even a newgeometric object (such as a convex hull or a separating hyperplane). The problemunder consideration is the linear separability problem [112]. In the special case offinding whether two sets of points in general space can be separated, the linearseparability problem becomes the binary classification problem (BCP). The mostgeneral form of the BCP is the case of whether two sets of points in general spacecan be separated by k hyperplanes. This problem is referred to as the k-polyhedralseparability problem which has been formulated by [288] as follows:Problem 9.1. Given a sample of l points X = (x1 , . . . , xl ) , a partition of this sampleinto two disjoint sets S1 = {π1 , . . . , π p } ⊂ Rd and sets S2 = {ρ1 , . . . , ρq } ⊂ Rd , andan integer k, recognize whether there exist k hyperplanes (that is k nonzero vectorsw ∈ Rd and k numbers b) H j = {z : zT w j = b j }(w j ∈ Rd , b j ∈ R, j = 1, . . . , k) thatseparate the sets S1 and S2 through a boolean formula as follows. Associate witheach hyperplane H j a boolean variable ξ j . The variable ξ j is true at a point z ifzT w j > b j and false if zT w j < b j . It is not defined at points lying on the hyperplaneitself. A Boolean formula φ = φ (ξ1 , . . . , ξk ) separates the sets S1 and S2 if φ is trueat each of the points π1 , . . . , π p and false at each of the points ρ1 , . . . , ρq .
9.2 On the Computational Complexity of the BCPThe BCP is a well examined in computational geometry. Let us first consider thecase of separating S1 and S2 with one hyperplane, i.e., k = 1.C. Ullrich, Forecasting and Hedging in the Foreign Exchange Markets, Lecture Notesin Economics and Mathematical Systems 623, DOI: 10.1007/978-3-642-00495-7 9,c Springer-Verlag Berlin Heidelberg 2009
65
66
9 Support Vector Classification
Problem 9.2. Given a sample of l points X = (x1 , . . . , xl ) , and a partition of thissample into two disjoint sets S1 = {π1 , . . . , π p }⊂ Rd and sets S2 = {ρ1 , . . . , ρq }⊂ Rd , recognize whether there exist a hyperplane (that is a nonzero vector w ∈ Rdand one number b) H = {z ∈ Rd : wT z = b} (characterized by a nonzero vectorw ∈ Rd , and a scalar b) that separates the sets S1 and S2 in the sense that for eachpoint πi ∈ S1 , (πi )T wi < b and for each point ρi ∈ S2 , (ρi )T wi > b.If k = 1, the BCP can be formulated as a linear programing problem and is thereforesolvable in polynomial time. However, when two sets cannot be separated by onehyperplane, a natural problem is to find the minimum number of hyperplanes thatis required for their separation. For instance, if k = 1 the problem can be stated asfollows.Problem 9.3. Given a sample of l points X = (x1 , . . . , xl ) , and a partition of thissample into two disjoint sets S1 = {π1 , . . . , π p } ⊂ Rd and sets S2 = ρ1 , . . . , ρq } ⊂ Rd ,recognize whether there exist two hyperplanes H1 = {z : wT1 z = b1 } and H2 = {z :wT2 z = b2 }(w1 , w2 ∈ Rd ; b1 , b2 ∈ R) that separates the sets S1 and S2 in the senseexpressed by the following conditions: (i) For each point πi ∈ S1 ,both (πi )T w1 < b1and (πi )T w2 < b2 , (ii) For each point ρi ∈ S2 , either (ρi )T w1 > b1 or (ρi )T w2 > b2 .If k = 2, the problem becomes NP-complete and therefore cannot be solved by apolynomial time algorithm. This can be proven by reducing the reversible satisfiability problem with six literals per clause (Reversible 6-SAT), which is known tobe NP-complete, to the 2-BCP (see [288]). As a natural extension, the k-linear separability problem which generalizes the 2-linear separability problem must also beNP-complete.Moreover, it has been proven that for every fixed k and d the k-linear separability problem in Rd can be solved in polynomial time. If two sets S1 , S2 ∈ Rd areseparable with k hyperplanes, then there exist k pairs of complementary subsetsAi , Bi ⊂ S1 ∪ S2 (that is Ai ∪ Bi = S1 ∪ S2 , i = 1, . . . , k) such that Hi separates Ai fromBi . It thus follows that the separating hyperplanes can be chosen from a finite set.Each of the candidate hyperplanes is determined by some set of at most d + 1 points,together with a choice of at most d equalities w j = ±1. The number of such sets ofat most d + 1 points is polynomial in the cardinality of S1 ∪ S2 . Thus, the numberof combinations of k such sets is also polynomial. It follows that all the relevantconfigurations of hyperplanes can be enumerated in polynomial time. Furthermore,it takes polynomial time to check whether a given configuration actually separatesS1 from S2 which establishes the proof.Another important result on the computational complexity of the BCP has beengiven by [187] who proved that the following problem is NP-hard: given a set oflabeled examples, find the hyperplane that minimizes the number of misclassifiedexamples both above and below the hyperplane. This result implies that any methodfor finding the optimal split is likely to have exponential cost if we assume thatP = NP. We find this proof very relevant in the present context since classifiers areusually judged by how many points they classify correctly. Unfortunately, it is computationally infeasible to enumerate all 2d (l, d)T distinct hyperplanes and choosethe best. In order to cope with computational complexity, heuristic search methods
9.3 Supervised Learning
67
have been employed [188, 303]. However, any nonexhaustive deterministic algorithm is prone to getting stuck in a local minimum. A second possibility is to defineerror measures for which the problem of finding optimal hyperplanes can be solvedin polynomial time. For example, if one minimizes the sum of distances of misclassified examples, then the optimal solution can be found using linear programingmethods.
9.3 Supervised LearningWe approach the task of solving the BCP via machine learning. The field of machinelearning is concerned with the question of how to construct computer programs thatautomatically improve with experience [297]. More specifically, we concentrate onsupervised learning which is also known as learning from examples.Definition 9.1. Let y = f (x) denote an unknown functional relationship of an inputx and an output y. The goal is to learn the function f from a limited number oftraining examples. The examples of input/output functionality as expressed by a setD = ((x1 , y1 ), ..., (xl , yl )) , x ∈ Rn , y ∈ {−1, +1}
(9.1)
are referred to as training data.In supervised learning, it is therefore assumed that a functional relationship f alsoknown as the target function is implicitly reflected within the input/output pairings.The estimate of the target function which is learnt or output by the learning algorithm is known as the solution of the learning problem. In the case of classificationthis function is referred to as the decision function h. The decision function partitions the underlying vector space into two sets, one for each class. The classifier willclassify all the points on one side of the decision boundary as belonging to one classand all those on the other side as belonging to the other class. If the decision function is a hyperplane, then the classification problem is called linear, and the classesare called linearly separable. The decision function is chosen from a set of candidate functions, also known as hypotheses H, which map from the input space to theoutput domain. The choice of the set of hypotheses determines the hypothesis spaceand represents the first important concept of the learning strategy. The algorithmwhich takes the training data as input and selects a hypothesis from the hypothesisspace is termed learning algorithm and represents the second important ingredient.In order to obtain a reliable estimate of h by the learning algorithm, several aspects must be considered. First, the learnt function should be able to explain theexamples, i.e., h(x1 ) = y1 , h(x2 ) = y2 , h(xl ) = yl , as good as possible. Figure 9.1shows that there is also a second reason. The depicted training examples are perfectly explained by the dotted function as opposed to the linear function. Nevertheless, one is inclined to have more confidence in the straight line since it is morelikely to generalize better, i.e., work better on unseen examples.
68
9 Support Vector Classification
Fig. 9.1 Linear and nonlinearclassifier
Fig. 9.2 Generalization erroras the sum of estimation andapproximation error
f0(x)
GeneralizationError
ApproximationErrorfn(x)
fn,N(x) EstimationError
HypothesisSpace
Target space
The complexity of the hypothesis space, i.e., the class of functions which is authorized for solving the BCP, thus influences our confidence in the solution found.The formalization of this insight provides the core of statistical learning theorywhere the generalization ability is commonly quantified with respect to some error measure to the underlying function in the target space. This error measure istermed generalization error and represents the sum of two errors which may