# ℓ

Authors: Xigao Shao; Kun Wu; Bifeng Liao
Journal: Computational Intelligence and Neuroscience
 (2012)

---

## Abstract

Linear multiple kernel learning model has been used for predicting financial time series. However,ℓ1-norm multiple support vector regression is rarely observed to outperform trivial baselines in practical applications. To allow for robust kernel mixtures that generalize well, we adopt ℓp-norm multiple kernel support vector regression  (1≤p<∞) as a stock price prediction model. The optimization problem is decomposed into smaller subproblems, and the interleaved optimization strategy is employed to solve the regression model. The model is evaluated on forecasting the daily stock closing prices of Shanghai Stock Index in China. Experimental results show that our proposed model performs better than ℓ1-norm multiple support vector regression model.


---

## Body

## 1. Introduction

Forecasting the future values of financial time series is an appealing yet difficult activity in the modern business world. As explained by Deboeck and Yaser [1, 2], the financial time series are inherently noisy, nonstationary, and deterministically chaotic. In the past, many methods were proposed for tackling this kind of problem. For instance, the linear models for forecasting the future values of stock prices include the autoregressive (AR) model [3], the autoregressive moving average (ARMA) model [4], and the autoregressive integrated moving average (ARIMA) model [4]. Over the last decade, nonlinear approaches have received increasing attention in financial time series prediction and have been proposed for a satisfactory answer to the problem. For example, Yao and Tan [5] used time series data and technical indicators as the input of neural networks to increase the forecast accuracy of exchange rates; Cao and Tay [6, 7] applied support vector machine (SVM) in financial forecasting and compared it with the multilayer back-propagation (BP) neural network and the regularized radial basis function (RBF) neural network; Qi and Wu [8] proposed a multilayer feed-forward network to forecast exchange rates; Pai and Lin [9] invested a hybrid ARIMA and support vector machines model in stock price forecasting; Pai et al. [10] presented a hybrid SVM model to exploit the unique strength of the linear and nonlinear SVM models in forecasting exchange rate; Kwon and Moon [11] proposed a hybrid neurogenetic system for stock trading; Hung and Hong [12] presented an improved ant colony optimization algorithm in a support vector regression (SVR) model, called SVRCACO, for selecting suitable parameters in exchange rate forecasting; Jiang and He [13] introduced local grey SVR (LG-SVR) integrated grey relational grade with local SVR for financial times eries forecasting; and so on.In comparison with the previous models, SVR with a single kernel function can exhibit better prediction accuracy because it conceives the structural risk minimization principle which considers both the training error and the capacity of the regression model [14, 15]. However, the researchers have to determine in advance the type of kernel function and the associated kernel hyper parameters for SVR. Unsuitably chosen kernel functions or hyper parameter settings may lead to significantly poor performance [16, 17].In recent years there has a lot of interest in designing principled regression algorithms over multiple cues, based on the intuitive notion that using more features should lead to better performance and decreasing the generalization error. When the right choice of features is unknown, learning linear combinations of multiple kernels is an appealing strategy. The approach with a optimization process is called multiple kernel learning (MKL). A first step towards a more realistic model of MKL was achieved by Lanckriet et al. [18], who showed that, given a candidate set of kernels, it is computationally feasible to simultaneously learn a support vector machine and a linear kernel combination at the same time. In MKL we need to solve a joint optimization problem while also learning the optimal weights for combing the kernels. Several practitioners have adopted the linear multiple kernels to deal with the practical problems. For example, Rakotomamonjy et al. [19] addressed the MKL problem through a weighted 2-norm regularization formulation and proposed an algorithm, named Simple MKL, for solving this MKL problem. Bach [20] proposed the asymptotic model consistency of the group Lasso. Zhang and Shen [21] presented multimodal multitask learning algorithm for joint prediction of multiple regression and classification variables in Alzheimer’s disease. Especially, Chi-Yuan Yeh and his coworkers [22] developed a two-stage MKL algorithm by incorporating sequential minimal optimization and the gradient projection method. The new method [22] performed better than previous ones for forecasting the financial time series. Previous approaches to multiple kernel learning (MKL) have promoted sparse kernel combinations to support interpretability and scalability. Unfortunately, sparsity at the kernel level may harm the generalization performance of the learner, therefore ℓ1-norm MKL is rarely observed to outperform trivial baselines in practical applications [23]. To allow for robust kernel mixtures that generalize well, the researchers extend ℓ1-norm MKL to arbitrary norms, that is, ℓp-norm MKL (1≤p<∞). For example, Marius Kloft et al. developed two efficient interleaved strategies for ℓp-norm MKL and showed that it can achieve better accuracy than ℓ1-norm MKL for real-world problems [23]; Francesco Orabona et al. presented a MKL optimization algorithm based on stochastic gradient descent for ℓp-norm MKL, which possessed a faster convergence rate as the number of kernels grows [24].In this paper, a multiple kernel learning framework is established for learning and predicting the stock prices. We present a regression model for the future values of stock prices, that is,ℓp-norm multiple kernel support vector regression (ℓp-norm MK-SVR), where 1≤p<∞. We decompose the optimization problem into smaller subproblem and adopt the interleaved optimization strategy to solve the regression model. Our experimental results show that ℓp-norm MK-SVR performs a better performance.The rest of this paper is arranged as follows. Section2 details the processing of the ℓp-norm MK-SVR model construction and describes the algorithm for our regression model. Experimental results are presented in Section 3. Section 4 concludes the paper and provides some future research directions.


## 2. Forecasting Methodology

### 2.1.ℓp-Norm Multiple Kernel Support Vector Regression

In this section, the idea ofℓp-norm multiple kernel support vector regression (ℓp-norm MK-SVR) is introduced formally.Let{xi,yi}i=1N, where xi∈Rn and yi∈R, be the training set. Each yi is the desired output value for the input vector xi. Consider a function ϕ(xi):Rn→H that maps the samples into a high, possibly infinite, dimensional space. A regression model is learned from the previous and used to predict the target values of unseen input vectors. SVR is a nonlinear kernel-based regression method which tries to locate a regression hyperplane with small risk in high-dimensional feature space [14]. Considering the soft margin formulation, the objective function and constraints for SVR should be solved, as follows:(1)minw~,bλ2〈w~,w~〉+1N∑i=1l(ξi+ξ^i)s.t.(〈w~,ϕ(xi)〉+b)-yi≤ε+ξi,s.t.yi-(〈w~,ϕ(xi)〉+b)≤ε+ξ^i,s.t.ξ,ξ^i≥0,i=1,2,…,N.SVR model usually uses a single mapping functionϕ and hence a single kernel function K. Although the SVR model has good function approximation and generalization capabilities, it is not fit for dealing with a data-set which has a locally varying distribution. For resolving this problem, we can construct a MK-SVR model. Combining multiple kernels instead of using a single one, ℓp-norm MK-SVR model can catch up the varying distribution very well. Therefore we can use the composite feature map ϕ which has a block structure:
(2)ϕ(x)=[d1ϕ1(x)×d2ϕ2(x)×⋯×dMϕM(x)]
to map the input space to the feature space, where d1,d2,…,dM are weights of component functions. Given a set of base kernels Kk which correspond the previous feature maps {ϕk}(k=1,2,…,M), linear MK-SVR aims to learn a linear combination of the base kernels as K=∑kdkKk. In learning with MK-SVR we aim at minimizing the loss on the training data with respect to the optimal kernel mixture ∑kdkKk in addition to regularizing d to avoid overfitting. The primal can therefore be formulated as
(3)minw~,bλ2(∑k∥w~k∥2)2+1N∑i=1l(ξi+ξ^i)+μ~Ω~[d]s.t.(〈w~,K(xi)〉+b)-yi≤ε+ξi,s.t.yi-(〈w~,K(xi)〉+b)≤ε+ξ^i,s.t.μ~>0,s.t.d1,d2,…,dM≥0,s.t.ξ,ξ^i≥0,i=1,2,…,N.
Previous research to MK-SVR employs the regularizer of the form  Ω~[d]=∥d∥1(d=(d1,d2,…,dM)) which can promote sparse kernel mixtures. However, sparsity is not always desirable, since the information carried in the zero-weighted kernels is lost. Therefore we propose to use nonsparse and thus more robust kernel mixtures by employing an ℓp-norm constraint with p>1, that is, Ω~[d]=∥d∥p2, and ∥d∥p=(∑k‍dkp)1/p, 1<p<∞. In (3), let dkw~k=wk, C=1/nλ, μ~=μλ, and the first equation be divided with λ, then the following ℓp-norm MK-SVR is obtained:
(4)minw,b12∑k∥wk∥22dk+C∑i=1l(ξi+ξ^i)+μ∥d∥p2s.t.(〈w,K(xi)〉+b)-yi≤ε+ξi,s.t.yi-(〈w,K(xi)〉+b)≤ε+ξ^i,s.t.μ>0,s.t.d1,d2,…,dM≥0,s.t.ξ,ξ^i≥0,i=1,2,…,N.An alternative approach previous equations has been considered by studiers. For example, Zien and Ong [25] upperbound the value of the regularizer ∥d∥1 and incorporate the regularizer as an additional constraint into the optimization problem. According to this thought, ℓp-norm MK-SVR model (4) can be transformed into the following form:
(5)minw,b12∑k‍∥wk∥22dk+C∑i=1l‍(ξi+ξ^i)s.t.(〈w,K(xi)〉+b)-yi≤ε+ξi,s.t.yi-(〈w,K(xi)〉+b)≤ε+ξ^i,s.t.∥d∥p2≤1,s.t.d1,d2,…,dM≥0,s.t.ξ,ξ^i≥0,i=1,2,…,N.It can be shown (see  the Appendix for details) that the dual of (5) is
(6)maxα^,α(yT(α^-α)-ε(α^+α))-∥(12dk∑i=1N∑j=1N(α^i-αi)(α^j-αj)Kk(xi,xj))k=1M∥p*s.t.1T(α^-α)=0,s.t.0≤α^,α≤C1,s.t.d1,d2,…,dM≥0,
where y=(y1,y2,…,yN)T, ε=(1,1,…,1)T, α=(α1,α2,…,αN)T∈RN, α^=(α^1,α^2,…,α^N)T∈RN, and p*=p/(p-1) is the dual norm of p. Suppose the optimal α^i*, αi*(i=1,2,…,N) and d1*,d2*,…,dM* are found by solving (6), the regression hyperplane for ℓp-norm MK-SVR model is given by(7)f*(x)=∑i=1N(α^i*-αi*)K(xi,x)+b*,
where b*=yj+ε-∑i=1N(α^i*-αi*)K(xi,xj) is obtained from any α^i* and αi*, with 0<α^i*,αi*<C1. In the following section, an efficient algorithm is proposed for solving the optimization problem (6).


### 2.2. An Optimistic Algorithm

ℓ
p-norm MK-SVR model (6) can be trained with several algorithms, for example, the Sequential Minimal Optimization algorithm [26] and multi-kernel learning with online-bath optimization [24]. In this paper, the interleaved optimization is used for the optimization scheme according to the idea of [23]. As a matter of fact, we can exploit the structure of ℓp-norm MK-SVR cost function by alternating between optimizing the linear combination of the base kernels K=∑kdkKk and the remaining variables as α^ and α. We can do so by setting up a two-stage optimization algorithm. The basic idea of the algorithm is to divide the optimization variables of ℓp-norm MK-SVR problem (6) into two groups, (α^,α) on one hand and d=(d1,d2,…,dM) on the other. Our procedure will alternatingly operate on those two stages via a block coordinate descent algorithm. Therefore the optimization d will be carried out analytically and the (α^,α) will be computed in the dual. The two stages are iteratively performed until the specified stopping criterion is met, as shown in Figure 1.Figure 1
ℓ
p-norm MK-SVR model learning algorithm (see [27]).In the first stage, the variables(α^,α) are kept fixed, that is, the (α^,α) are known. Then the optimal d in ℓp-norm MK-SVR model (6) can be calculated analytically by the following process.According to(A.4), let
(8)L=∑i=1Nyi(α^i-αi)-ε∑i=1N(α^i+αi)-12∑k=1Mdk∑i=1N∑j=1N(α^i-αi)(α^j-αj)Kk(xi,xj)+β(12∥d∥p2-12)-γTd.Set theL’s first partial derivatives with respect to dk, and let it be 0:
(9)∂L∂dk=0⇒β(∑kdkp)2/p-1dkp-1=γk+12∑i=1N‍∑j=1N‍(α^i-αi)(α^j-αj)Kk(xi,xj)⇒β(∑kdkp)2/p=∑k‍dk(γk+12∑i=1N‍∑j=1N‍(α^i-αi)×(α^j-αj)Kk(xi,xj)∑j=1N‍).
In the optimal point γk=0 holds, so the previous equation yields
(10)dk=12β(∑k∑i=1N∑j=1N(α^i-αi)(α^j-αj)Kk(xi,xj))(1/q)-(1/p)×(∑i=1N∑j=1N(α^i-αi)(α^j-αj)Kk(xi,xj))q/p,
where (1/p)+(1/q)=1, and k=1,2,…,M.In the second stage, the following algorithm is used. We give a chunking-based training algorithm (Algorithm1) via analytical update for ℓp-Norm MK-SVR. Kernel weighting d and (α^,α) are optimized in an interleaving way. The basic idea of this algorithm is to divide the optimal problem into an inner subproblem and an outer subproblem. The algorithm alternates between solving the two subproblems until convergence.Algorithm 1
1. Inputfm,i=f^i=α^i=0, gm,i=g^i=αi=0, ∀i=1,2,…,N; L=S=-∞, dk=(1/k)p,
∀
k
=
1,2
,
…
,
M.
2. Iterate
(1) Select2Q variables based on the gradient of (6): α^Q=α^i1,…,α^iQ, αQ=αi1,…,αiQ.
(2) Storeα^Qold=α^Q, αQold=αQ and new α^Q, αQ can be obtained according to (6) with
respect to the selected variables.
(3) Update gradientfm,i←fm,i+∑q=1Q‍(α^iq-α^iqold)Kk(xiq,xi), gm,i←gm,i+∑q=1Q‍(αiq-αiqold)Kk(xiq,xi),
∀k=1,2,…,M,i=1,2,…,N.
(4) Compute the quadratic termsSk=(1/2)∑i‍(fm,i-gm,i)(α^i-αi), ∀k=1,2,…,M.
(5)Lold=L, L=∑i‍yi(α^i-αi)-∑i‍ε(α^i+αi), Sold=S, S=∑k‍dkSk.
(6) If|1-(L-S)/(Lold-Sold)|≥ε, update dk with (10), ∀k=1,2,…,M,
else
break
endif
3. Outputα^,α,d.In every iteration process, the inner subproblem (α^ and α step) identifies the constraint that maximises (6) with fixing kernel weighting d. The outer subproblem (d step) is also called the restricted master problem. dk is computed with the (10), k=1,2,…,M.The interleaved optimization algorithm is depicted in Algorithm1, and the details of it are as follows.


#### 2.2.1. Initialization

Assume the original values ofα^i and αi are 0, for  all i=1,2,…,N, and the initial value of dk is 1/kp, for all k=1,2,…,M, where p>1 is a constant.


#### 2.2.2. Chunking and Carrying out with SVR

In the iteration process, the procedure is standard in chunking-based SVR solvers and is carried out bySVMlight, where Q is chosen as described in [28]. We implement the greedy second-order working set selection strategy of [28]. Rather than compute the gradient repeatedly, we speed up variable selection by caching, separately for each kernel. The cache needs to be updated every time we change α^Q and αQ in the reduced variable optimisation. In Algorithm 1, (4) and (5) compute the objective values of SVR. Finally, the analytical value of d is carried out in (10).


#### 2.2.3. Stopping Criterion

When the duality gap falls below a prespecified threshold, that is,|1-((L-S)/(Lold-Sold))|<ε, we terminate the algorithm and output α^, α, d.


## 2.1.ℓp-Norm Multiple Kernel Support Vector Regression

In this section, the idea ofℓp-norm multiple kernel support vector regression (ℓp-norm MK-SVR) is introduced formally.Let{xi,yi}i=1N, where xi∈Rn and yi∈R, be the training set. Each yi is the desired output value for the input vector xi. Consider a function ϕ(xi):Rn→H that maps the samples into a high, possibly infinite, dimensional space. A regression model is learned from the previous and used to predict the target values of unseen input vectors. SVR is a nonlinear kernel-based regression method which tries to locate a regression hyperplane with small risk in high-dimensional feature space [14]. Considering the soft margin formulation, the objective function and constraints for SVR should be solved, as follows:(1)minw~,bλ2〈w~,w~〉+1N∑i=1l(ξi+ξ^i)s.t.(〈w~,ϕ(xi)〉+b)-yi≤ε+ξi,s.t.yi-(〈w~,ϕ(xi)〉+b)≤ε+ξ^i,s.t.ξ,ξ^i≥0,i=1,2,…,N.SVR model usually uses a single mapping functionϕ and hence a single kernel function K. Although the SVR model has good function approximation and generalization capabilities, it is not fit for dealing with a data-set which has a locally varying distribution. For resolving this problem, we can construct a MK-SVR model. Combining multiple kernels instead of using a single one, ℓp-norm MK-SVR model can catch up the varying distribution very well. Therefore we can use the composite feature map ϕ which has a block structure:
(2)ϕ(x)=[d1ϕ1(x)×d2ϕ2(x)×⋯×dMϕM(x)]
to map the input space to the feature space, where d1,d2,…,dM are weights of component functions. Given a set of base kernels Kk which correspond the previous feature maps {ϕk}(k=1,2,…,M), linear MK-SVR aims to learn a linear combination of the base kernels as K=∑kdkKk. In learning with MK-SVR we aim at minimizing the loss on the training data with respect to the optimal kernel mixture ∑kdkKk in addition to regularizing d to avoid overfitting. The primal can therefore be formulated as
(3)minw~,bλ2(∑k∥w~k∥2)2+1N∑i=1l(ξi+ξ^i)+μ~Ω~[d]s.t.(〈w~,K(xi)〉+b)-yi≤ε+ξi,s.t.yi-(〈w~,K(xi)〉+b)≤ε+ξ^i,s.t.μ~>0,s.t.d1,d2,…,dM≥0,s.t.ξ,ξ^i≥0,i=1,2,…,N.
Previous research to MK-SVR employs the regularizer of the form  Ω~[d]=∥d∥1(d=(d1,d2,…,dM)) which can promote sparse kernel mixtures. However, sparsity is not always desirable, since the information carried in the zero-weighted kernels is lost. Therefore we propose to use nonsparse and thus more robust kernel mixtures by employing an ℓp-norm constraint with p>1, that is, Ω~[d]=∥d∥p2, and ∥d∥p=(∑k‍dkp)1/p, 1<p<∞. In (3), let dkw~k=wk, C=1/nλ, μ~=μλ, and the first equation be divided with λ, then the following ℓp-norm MK-SVR is obtained:
(4)minw,b12∑k∥wk∥22dk+C∑i=1l(ξi+ξ^i)+μ∥d∥p2s.t.(〈w,K(xi)〉+b)-yi≤ε+ξi,s.t.yi-(〈w,K(xi)〉+b)≤ε+ξ^i,s.t.μ>0,s.t.d1,d2,…,dM≥0,s.t.ξ,ξ^i≥0,i=1,2,…,N.An alternative approach previous equations has been considered by studiers. For example, Zien and Ong [25] upperbound the value of the regularizer ∥d∥1 and incorporate the regularizer as an additional constraint into the optimization problem. According to this thought, ℓp-norm MK-SVR model (4) can be transformed into the following form:
(5)minw,b12∑k‍∥wk∥22dk+C∑i=1l‍(ξi+ξ^i)s.t.(〈w,K(xi)〉+b)-yi≤ε+ξi,s.t.yi-(〈w,K(xi)〉+b)≤ε+ξ^i,s.t.∥d∥p2≤1,s.t.d1,d2,…,dM≥0,s.t.ξ,ξ^i≥0,i=1,2,…,N.It can be shown (see  the Appendix for details) that the dual of (5) is
(6)maxα^,α(yT(α^-α)-ε(α^+α))-∥(12dk∑i=1N∑j=1N(α^i-αi)(α^j-αj)Kk(xi,xj))k=1M∥p*s.t.1T(α^-α)=0,s.t.0≤α^,α≤C1,s.t.d1,d2,…,dM≥0,
where y=(y1,y2,…,yN)T, ε=(1,1,…,1)T, α=(α1,α2,…,αN)T∈RN, α^=(α^1,α^2,…,α^N)T∈RN, and p*=p/(p-1) is the dual norm of p. Suppose the optimal α^i*, αi*(i=1,2,…,N) and d1*,d2*,…,dM* are found by solving (6), the regression hyperplane for ℓp-norm MK-SVR model is given by(7)f*(x)=∑i=1N(α^i*-αi*)K(xi,x)+b*,
where b*=yj+ε-∑i=1N(α^i*-αi*)K(xi,xj) is obtained from any α^i* and αi*, with 0<α^i*,αi*<C1. In the following section, an efficient algorithm is proposed for solving the optimization problem (6).


## 2.2. An Optimistic Algorithm

ℓ
p-norm MK-SVR model (6) can be trained with several algorithms, for example, the Sequential Minimal Optimization algorithm [26] and multi-kernel learning with online-bath optimization [24]. In this paper, the interleaved optimization is used for the optimization scheme according to the idea of [23]. As a matter of fact, we can exploit the structure of ℓp-norm MK-SVR cost function by alternating between optimizing the linear combination of the base kernels K=∑kdkKk and the remaining variables as α^ and α. We can do so by setting up a two-stage optimization algorithm. The basic idea of the algorithm is to divide the optimization variables of ℓp-norm MK-SVR problem (6) into two groups, (α^,α) on one hand and d=(d1,d2,…,dM) on the other. Our procedure will alternatingly operate on those two stages via a block coordinate descent algorithm. Therefore the optimization d will be carried out analytically and the (α^,α) will be computed in the dual. The two stages are iteratively performed until the specified stopping criterion is met, as shown in Figure 1.Figure 1
ℓ
p-norm MK-SVR model learning algorithm (see [27]).In the first stage, the variables(α^,α) are kept fixed, that is, the (α^,α) are known. Then the optimal d in ℓp-norm MK-SVR model (6) can be calculated analytically by the following process.According to(A.4), let
(8)L=∑i=1Nyi(α^i-αi)-ε∑i=1N(α^i+αi)-12∑k=1Mdk∑i=1N∑j=1N(α^i-αi)(α^j-αj)Kk(xi,xj)+β(12∥d∥p2-12)-γTd.Set theL’s first partial derivatives with respect to dk, and let it be 0:
(9)∂L∂dk=0⇒β(∑kdkp)2/p-1dkp-1=γk+12∑i=1N‍∑j=1N‍(α^i-αi)(α^j-αj)Kk(xi,xj)⇒β(∑kdkp)2/p=∑k‍dk(γk+12∑i=1N‍∑j=1N‍(α^i-αi)×(α^j-αj)Kk(xi,xj)∑j=1N‍).
In the optimal point γk=0 holds, so the previous equation yields
(10)dk=12β(∑k∑i=1N∑j=1N(α^i-αi)(α^j-αj)Kk(xi,xj))(1/q)-(1/p)×(∑i=1N∑j=1N(α^i-αi)(α^j-αj)Kk(xi,xj))q/p,
where (1/p)+(1/q)=1, and k=1,2,…,M.In the second stage, the following algorithm is used. We give a chunking-based training algorithm (Algorithm1) via analytical update for ℓp-Norm MK-SVR. Kernel weighting d and (α^,α) are optimized in an interleaving way. The basic idea of this algorithm is to divide the optimal problem into an inner subproblem and an outer subproblem. The algorithm alternates between solving the two subproblems until convergence.Algorithm 1
1. Inputfm,i=f^i=α^i=0, gm,i=g^i=αi=0, ∀i=1,2,…,N; L=S=-∞, dk=(1/k)p,
∀
k
=
1,2
,
…
,
M.
2. Iterate
(1) Select2Q variables based on the gradient of (6): α^Q=α^i1,…,α^iQ, αQ=αi1,…,αiQ.
(2) Storeα^Qold=α^Q, αQold=αQ and new α^Q, αQ can be obtained according to (6) with
respect to the selected variables.
(3) Update gradientfm,i←fm,i+∑q=1Q‍(α^iq-α^iqold)Kk(xiq,xi), gm,i←gm,i+∑q=1Q‍(αiq-αiqold)Kk(xiq,xi),
∀k=1,2,…,M,i=1,2,…,N.
(4) Compute the quadratic termsSk=(1/2)∑i‍(fm,i-gm,i)(α^i-αi), ∀k=1,2,…,M.
(5)Lold=L, L=∑i‍yi(α^i-αi)-∑i‍ε(α^i+αi), Sold=S, S=∑k‍dkSk.
(6) If|1-(L-S)/(Lold-Sold)|≥ε, update dk with (10), ∀k=1,2,…,M,
else
break
endif
3. Outputα^,α,d.In every iteration process, the inner subproblem (α^ and α step) identifies the constraint that maximises (6) with fixing kernel weighting d. The outer subproblem (d step) is also called the restricted master problem. dk is computed with the (10), k=1,2,…,M.The interleaved optimization algorithm is depicted in Algorithm1, and the details of it are as follows.


### 2.2.1. Initialization

Assume the original values ofα^i and αi are 0, for  all i=1,2,…,N, and the initial value of dk is 1/kp, for all k=1,2,…,M, where p>1 is a constant.


### 2.2.2. Chunking and Carrying out with SVR

In the iteration process, the procedure is standard in chunking-based SVR solvers and is carried out bySVMlight, where Q is chosen as described in [28]. We implement the greedy second-order working set selection strategy of [28]. Rather than compute the gradient repeatedly, we speed up variable selection by caching, separately for each kernel. The cache needs to be updated every time we change α^Q and αQ in the reduced variable optimisation. In Algorithm 1, (4) and (5) compute the objective values of SVR. Finally, the analytical value of d is carried out in (10).


### 2.2.3. Stopping Criterion

When the duality gap falls below a prespecified threshold, that is,|1-((L-S)/(Lold-Sold))|<ε, we terminate the algorithm and output α^, α, d.


## 2.2.1. Initialization

Assume the original values ofα^i and αi are 0, for  all i=1,2,…,N, and the initial value of dk is 1/kp, for all k=1,2,…,M, where p>1 is a constant.


## 2.2.2. Chunking and Carrying out with SVR

In the iteration process, the procedure is standard in chunking-based SVR solvers and is carried out bySVMlight, where Q is chosen as described in [28]. We implement the greedy second-order working set selection strategy of [28]. Rather than compute the gradient repeatedly, we speed up variable selection by caching, separately for each kernel. The cache needs to be updated every time we change α^Q and αQ in the reduced variable optimisation. In Algorithm 1, (4) and (5) compute the objective values of SVR. Finally, the analytical value of d is carried out in (10).


## 2.2.3. Stopping Criterion

When the duality gap falls below a prespecified threshold, that is,|1-((L-S)/(Lold-Sold))|<ε, we terminate the algorithm and output α^, α, d.


## 3. Experimental Results

In this section, two experiments on a real financial time series have been carried out to assess the performance ofℓp-norm MK-SVR. The motivation behind the two experiments are to compare the performance of our proposed method with that of other methods, that is, single kernel support vector regression (SKSVR) [29] and ℓ1-norm MK-SVR [22]. All calculations are performed with programs developed in MATLAB R2010a.


### 3.1. Experiment I

Firstly, we compare the performance ofℓp-norm MK-SVR with that of SKSVR. In this experiment, the daily stock closing prices of Shanghai Stock Index in China for the period of January 2003 to December 2007 are used, and the training/validating/testing data set is generated by a one-season moving-window testing approach. Following the way done in [29], three data sets, data1 to data3, are formed. For instance, data1 contains the daily stock closing prices from January 2003 to December 2006 are selected as the training data set, the daily stock closing prices from January 2007 to March 2007 are selected as the validating data set, the daily stock closing prices from April 2007 to June 2007 are selected as the testing data set. The corresponding time periods for data 1 to data 3 are listed in Table 1.Table 1
The data sets for the first experiment.
Dataset
Training
Validating
Testing
data1
2003/1–2006/12
2007/1–2007/3
2007/4–2007/6
data2
2003/4–2007/3
2007/4–2007/6
2007/7–2007/9
data3
2003/7–2007/6
2007/7–2007/9
2007/10–2007/12According to [29], we can derive training patterns (xt,yt) based on the original daily stock closing prices P={p1,…,pt…} for SKSVR and ℓp-norm MK-SVR. Let EMAn(t)=EMAn(t-1)+α × (pt-EMAn(t-1)) be the n-day exponential moving average of the tth day, where pt is the tth day daily stock closing prices and α=2/(n+1), then the output variable yt can be defined as
(11)yt=RDP+5(t)=EMA3t-EMA3(t-5)EMA3(t-5)×100.
Let xt=(xt,1,xt,2,xt,3,xt,4,xt,5) be the input vector and let RDP-n(t)=(100×(pt-pt-n))/pt-n be the lagged relative difference in percentage of price (RDP). Moreover, We can obtain a transformed closing price EW~An(t) by subtracting a n-day EMA from the closing price, that is,
(12)EW~An(t)=pt-EWAn(t).Based on in the previously mentioned, the input variables can be defined asxt,1=EW~A15(t-5), xt,2=RD~P-5(t-5), xt,3=RD~P-10(t-5), xt,4=RD~P-15(t-5), and xt,3=RD~P-20(t-5). We adopt the root mean squared error (RMSE) for performance comparison, that is,
(13)RMSE=1T∑t=1T‍(yt-y^t)2,
where yt and y^t are desired output and predicted output, respectively.There are three parameters that should be determined in advance for SKSVR,that is, C, ε, and γ for using RBF kernel. The forecasting performance of SKSVR is examined with C=1 and ε=0.005. Because the forecasting performance obtained by SKSVR is effected by the parameter γ, we try with different settings of it from 0.01 to 3 with a stepping factor of 0.05. Figure 2 shows the RMSE for performance on the three data sets by SKSVR. The figure shows that SKSVR requires different γ settings for different data sets to obtain the best performance. For example, the best performance for data 1 occurs when 0.35≤γ≤0.45. The best RMSE values obtained by SKSVR are listed in Table 2.Table 2
The comparison of RMSE values between SKSVR andℓp-norm MK-SVR.
Methods
Data1
Data2
Data3
SKSVR
0.179
0.183
0.197
ℓ
p norm (p = 1.05)
0.161
0.177
0.186
ℓ
p norm (p = 1.001)
0.163
0.174
0.189
ℓ
p norm (p = 1.15)
0.166
0.179
0.183Figure 2
Forecasting performance of SKSVR with different hyperparameters.Forℓp-norm MK-SVR training model, we adopt RBF kernel K(x,xk)=exp{-∥xi-xj∥22/σ2}. A kernel combining 60 different RBF kernels is considered,that is, 0.01≤1/σ2≤3 with step 0.05. Hence, the kernel matrix is combined with a weighted sum of 60 kernel matrices, that is, K~=d1K1+d2K2+⋯+d60K60 where d1 denotes the kernel weight for the first kernel matrix with 1/σ2=0.01 and d2 denotes the kernel weight for the second kernel matrix with 1/σ2=0.06, and so on. For the three data sets, the RMSE values obtained by ℓp-norm MK-SVR are listed in Table 2, too. Obviously when p=1.05, 1.001, and 1.15, ℓp-norm MK-SVR model performs better than SKSVR one for data1 data set, data2 data set, and data3 data set, respectively.


### 3.2. Experiment II

Secondly, we compare the performance ofℓp-norm MK-SVR with that of ℓ1-norm MK-SVR. In this experiment, the daily stock closing prices of Shanghai Stock Index in China for the period of January 2008 to December 2011 are used, and the training/validating/testing data set is generated by a one-season moving-window testing approach. Following the way done in Tay and Cao [29], three data sets, D-I to D-III, are formed. The corresponding time periods for D-I to D-III are listed in Table 3.Table 3
The data sets for the second experiment.
Dataset
Training
Validating
Testing
D-I
2008/1–2010/12
2011/1–2011/3
2011/4–2011/6
D-II
2008/4–2011/3
2011/4–2011/6
2011/7–2011/9
D-III
2008/7–2011/6
2011/7–2011/9
2011/10–2011/12We also adopt RMSE (13) for performance comparison. For ℓ1-norm MK-SVR and ℓp-norm MK-SVR training model, a kernel combining 40 different RBF kernels is considered, that is, 1/σ2∈{0.01,0.02, …,0.09,0.1,0.2,…,0.9,1,2,…,9,10,20,…,100,200,300,400}. Hence, the kernel matrix is combined with a weighted sum of 40 kernel matrices,that is, K~=d1K1+d2K2+⋯+d40K40 where d1 denotes the kernel weight for the first kernel matrix with 1/σ2=0.01 and d2 denotes the kernel weight for the second kernel matrix with 1/σ2=0.02, and so on. For the three data sets, the RMSE values obtained by ℓ1-norm MK-SVR and ℓp-norm MK-SVR are listed in Table 4. Obviously when p=6/5, 4/3, and 8/7, ℓp-norm MK-SVR model performs better than ℓ1-norm MK-SVR one for D-I data set, D-II data set, and D-III data set, respectively. Figure 3 shows the forecasting results for D-I and D-II by the two regression models.Table 4
The comparison of RMSE values betweenℓ1-norm MK-SVR and ℓp-norm MK-SVR.
Methods
D-I
D-II
D-III
ℓ
1 norm
0.182
0.189
0.178
ℓ
p norm (p = 6/5)
0.175
0.183
0.179
ℓ
p norm (p = 4/3)
0.185
0.181
0.180
ℓ
p norm (p = 8/7)
0.190
0.191
0.171Forecasting results byℓ1-norm MK-SVR and ℓp-norm MK-SVR.
(a)
(b)
(c)
(d)Furthermore, we can use a statistical test proposed by Diebold and Mariano [30] to assess the statistical significance of the forecasts by ℓp-norm MK-SVR model. The loss-differential series of ℓ1-norm MK-SVR and ℓp-norm MK-SVR are shown in Figures 4 and 5. According to [30], we adopt the asymptotic test S1=d-/(2πf^d(0))/T as the test statistic, where di=r1i2-r2i2 is the loss-differential series of ℓ1-norm MK-SVR and ℓp-norm MK-SVR models, r1 and r2 denote the forecasting errors; 2πf^d(0) is the weighted sum of the available sample autocovariances: 2πf^d(0)=∑τ=-(T-1)T-1‍1*(τ/S(T))γ^d(T), where T is the sample size, γ^d(T)=(1/T)∑t=|τ|+1T‍(dt-d-)(dt-|τ→|-d-), and 1*(τ/S(T)) is the lag window, defined as (14)1*(τS(T))={1,if|τS(T)|≤1,0,otherwise,
where S(T)=k-1; k reports the number of forecasting steps ahead.Figure 4
Loss differential (ℓ1-MKSVR to ℓp-MKSVR) of D-I.Figure 5
Loss differential (ℓ1-MKSVR to ℓp-MKSVR) of D-II.We denoteU1 as the forecasting accuracy of ℓ1-norm MK-SVR and Up as the forecasting accuracy of ℓp-norm MK-SVR. Under the null hypothesis: U1=Up, the test was performed at the 0.05 and 0.10 significant levels [12]. The test results are shown in the following Table 5. For the three data sets, all asymptotic tests reject H0:U1=Up. The test result shows that ℓp-norm MK-SVR model indeed improves the forecasting accuracy in comparison with ℓ1-norm MK-SVR model.Table 5
Asymptotic test.
Stock closing prices
α
=
0.05
α
=
0.10
D-I
S
1
=
1.756,
S
1
=
1.756,
P value = 0.0359
P value = 0.0359
D-II
S
1
=
1.832,
S
1
=
1.832,
P value = 0.0416
P value = 0.0416
D-III
S
1
=
1.579,
S
1
=
1.579,
P value = 0.0258
P value = 0.0258We briefly mention that the superior performance ofℓp-norm MK-SVR model (p>1) is not surprising. When we use the sparsity-inducing norm (p=1), some of the kernel weights are forced to become zero, and the corresponding kernel will be eliminated leading to some information loss. The daily stock closing prices do not carry large parts of overlapping information, and the information is discriminative. So a nonsparse kernel mixture can access more information and perform more robustly.


## 3.1. Experiment I

Firstly, we compare the performance ofℓp-norm MK-SVR with that of SKSVR. In this experiment, the daily stock closing prices of Shanghai Stock Index in China for the period of January 2003 to December 2007 are used, and the training/validating/testing data set is generated by a one-season moving-window testing approach. Following the way done in [29], three data sets, data1 to data3, are formed. For instance, data1 contains the daily stock closing prices from January 2003 to December 2006 are selected as the training data set, the daily stock closing prices from January 2007 to March 2007 are selected as the validating data set, the daily stock closing prices from April 2007 to June 2007 are selected as the testing data set. The corresponding time periods for data 1 to data 3 are listed in Table 1.Table 1
The data sets for the first experiment.
Dataset
Training
Validating
Testing
data1
2003/1–2006/12
2007/1–2007/3
2007/4–2007/6
data2
2003/4–2007/3
2007/4–2007/6
2007/7–2007/9
data3
2003/7–2007/6
2007/7–2007/9
2007/10–2007/12According to [29], we can derive training patterns (xt,yt) based on the original daily stock closing prices P={p1,…,pt…} for SKSVR and ℓp-norm MK-SVR. Let EMAn(t)=EMAn(t-1)+α × (pt-EMAn(t-1)) be the n-day exponential moving average of the tth day, where pt is the tth day daily stock closing prices and α=2/(n+1), then the output variable yt can be defined as
(11)yt=RDP+5(t)=EMA3t-EMA3(t-5)EMA3(t-5)×100.
Let xt=(xt,1,xt,2,xt,3,xt,4,xt,5) be the input vector and let RDP-n(t)=(100×(pt-pt-n))/pt-n be the lagged relative difference in percentage of price (RDP). Moreover, We can obtain a transformed closing price EW~An(t) by subtracting a n-day EMA from the closing price, that is,
(12)EW~An(t)=pt-EWAn(t).Based on in the previously mentioned, the input variables can be defined asxt,1=EW~A15(t-5), xt,2=RD~P-5(t-5), xt,3=RD~P-10(t-5), xt,4=RD~P-15(t-5), and xt,3=RD~P-20(t-5). We adopt the root mean squared error (RMSE) for performance comparison, that is,
(13)RMSE=1T∑t=1T‍(yt-y^t)2,
where yt and y^t are desired output and predicted output, respectively.There are three parameters that should be determined in advance for SKSVR,that is, C, ε, and γ for using RBF kernel. The forecasting performance of SKSVR is examined with C=1 and ε=0.005. Because the forecasting performance obtained by SKSVR is effected by the parameter γ, we try with different settings of it from 0.01 to 3 with a stepping factor of 0.05. Figure 2 shows the RMSE for performance on the three data sets by SKSVR. The figure shows that SKSVR requires different γ settings for different data sets to obtain the best performance. For example, the best performance for data 1 occurs when 0.35≤γ≤0.45. The best RMSE values obtained by SKSVR are listed in Table 2.Table 2
The comparison of RMSE values between SKSVR andℓp-norm MK-SVR.
Methods
Data1
Data2
Data3
SKSVR
0.179
0.183
0.197
ℓ
p norm (p = 1.05)
0.161
0.177
0.186
ℓ
p norm (p = 1.001)
0.163
0.174
0.189
ℓ
p norm (p = 1.15)
0.166
0.179
0.183Figure 2
Forecasting performance of SKSVR with different hyperparameters.Forℓp-norm MK-SVR training model, we adopt RBF kernel K(x,xk)=exp{-∥xi-xj∥22/σ2}. A kernel combining 60 different RBF kernels is considered,that is, 0.01≤1/σ2≤3 with step 0.05. Hence, the kernel matrix is combined with a weighted sum of 60 kernel matrices, that is, K~=d1K1+d2K2+⋯+d60K60 where d1 denotes the kernel weight for the first kernel matrix with 1/σ2=0.01 and d2 denotes the kernel weight for the second kernel matrix with 1/σ2=0.06, and so on. For the three data sets, the RMSE values obtained by ℓp-norm MK-SVR are listed in Table 2, too. Obviously when p=1.05, 1.001, and 1.15, ℓp-norm MK-SVR model performs better than SKSVR one for data1 data set, data2 data set, and data3 data set, respectively.


## 3.2. Experiment II

Secondly, we compare the performance ofℓp-norm MK-SVR with that of ℓ1-norm MK-SVR. In this experiment, the daily stock closing prices of Shanghai Stock Index in China for the period of January 2008 to December 2011 are used, and the training/validating/testing data set is generated by a one-season moving-window testing approach. Following the way done in Tay and Cao [29], three data sets, D-I to D-III, are formed. The corresponding time periods for D-I to D-III are listed in Table 3.Table 3
The data sets for the second experiment.
Dataset
Training
Validating
Testing
D-I
2008/1–2010/12
2011/1–2011/3
2011/4–2011/6
D-II
2008/4–2011/3
2011/4–2011/6
2011/7–2011/9
D-III
2008/7–2011/6
2011/7–2011/9
2011/10–2011/12We also adopt RMSE (13) for performance comparison. For ℓ1-norm MK-SVR and ℓp-norm MK-SVR training model, a kernel combining 40 different RBF kernels is considered, that is, 1/σ2∈{0.01,0.02, …,0.09,0.1,0.2,…,0.9,1,2,…,9,10,20,…,100,200,300,400}. Hence, the kernel matrix is combined with a weighted sum of 40 kernel matrices,that is, K~=d1K1+d2K2+⋯+d40K40 where d1 denotes the kernel weight for the first kernel matrix with 1/σ2=0.01 and d2 denotes the kernel weight for the second kernel matrix with 1/σ2=0.02, and so on. For the three data sets, the RMSE values obtained by ℓ1-norm MK-SVR and ℓp-norm MK-SVR are listed in Table 4. Obviously when p=6/5, 4/3, and 8/7, ℓp-norm MK-SVR model performs better than ℓ1-norm MK-SVR one for D-I data set, D-II data set, and D-III data set, respectively. Figure 3 shows the forecasting results for D-I and D-II by the two regression models.Table 4
The comparison of RMSE values betweenℓ1-norm MK-SVR and ℓp-norm MK-SVR.
Methods
D-I
D-II
D-III
ℓ
1 norm
0.182
0.189
0.178
ℓ
p norm (p = 6/5)
0.175
0.183
0.179
ℓ
p norm (p = 4/3)
0.185
0.181
0.180
ℓ
p norm (p = 8/7)
0.190
0.191
0.171Forecasting results byℓ1-norm MK-SVR and ℓp-norm MK-SVR.
(a)
(b)
(c)
(d)Furthermore, we can use a statistical test proposed by Diebold and Mariano [30] to assess the statistical significance of the forecasts by ℓp-norm MK-SVR model. The loss-differential series of ℓ1-norm MK-SVR and ℓp-norm MK-SVR are shown in Figures 4 and 5. According to [30], we adopt the asymptotic test S1=d-/(2πf^d(0))/T as the test statistic, where di=r1i2-r2i2 is the loss-differential series of ℓ1-norm MK-SVR and ℓp-norm MK-SVR models, r1 and r2 denote the forecasting errors; 2πf^d(0) is the weighted sum of the available sample autocovariances: 2πf^d(0)=∑τ=-(T-1)T-1‍1*(τ/S(T))γ^d(T), where T is the sample size, γ^d(T)=(1/T)∑t=|τ|+1T‍(dt-d-)(dt-|τ→|-d-), and 1*(τ/S(T)) is the lag window, defined as (14)1*(τS(T))={1,if|τS(T)|≤1,0,otherwise,
where S(T)=k-1; k reports the number of forecasting steps ahead.Figure 4
Loss differential (ℓ1-MKSVR to ℓp-MKSVR) of D-I.Figure 5
Loss differential (ℓ1-MKSVR to ℓp-MKSVR) of D-II.We denoteU1 as the forecasting accuracy of ℓ1-norm MK-SVR and Up as the forecasting accuracy of ℓp-norm MK-SVR. Under the null hypothesis: U1=Up, the test was performed at the 0.05 and 0.10 significant levels [12]. The test results are shown in the following Table 5. For the three data sets, all asymptotic tests reject H0:U1=Up. The test result shows that ℓp-norm MK-SVR model indeed improves the forecasting accuracy in comparison with ℓ1-norm MK-SVR model.Table 5
Asymptotic test.
Stock closing prices
α
=
0.05
α
=
0.10
D-I
S
1
=
1.756,
S
1
=
1.756,
P value = 0.0359
P value = 0.0359
D-II
S
1
=
1.832,
S
1
=
1.832,
P value = 0.0416
P value = 0.0416
D-III
S
1
=
1.579,
S
1
=
1.579,
P value = 0.0258
P value = 0.0258We briefly mention that the superior performance ofℓp-norm MK-SVR model (p>1) is not surprising. When we use the sparsity-inducing norm (p=1), some of the kernel weights are forced to become zero, and the corresponding kernel will be eliminated leading to some information loss. The daily stock closing prices do not carry large parts of overlapping information, and the information is discriminative. So a nonsparse kernel mixture can access more information and perform more robustly.


## 4. Summary and Prospect

In this paper, anℓp-norm MK-SVR model for stock market price forecasting is proposed. The model conceives an optimization scheme of unprecedented efficiency and provides a really efficient implementation. In an empirical evaluation, we show that ℓp-norm MK-SVR can improve predictive accuracies on relevant real-world data sets. Although we focus on volatility forecasting of stock markets in this paper, our ℓp-norm MK-SVR model could be applied to more general financial forecasting problems. Therefore in the future we will apply our ℓp-norm MK-SVR model for other financial markets, such as exchange markets.



---

*Source: 601296-2012-12-29.xml*