# Robustε-Support Vector Regression

Authors: Yuan Lv; Zhong Gan
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Spheroid disturbance of input data brings great challenges to support vector regression; thus it is essential to study the robust regression model. This paper is dedicated to establish a robust regression model which makes the regression function robust against disturbance of data and system parameter. Firstly, two theorems have been given to show that the robust linearε-support vector regression problem could be settled by solving the dual problems. Secondly, it has been focused on the development of robust support vector regression algorithm which is extended from linear domain to nonlinear domain. Finally, the numerical experiments result demonstrates the effectiveness of the models and algorithms proposed in this paper.


---

## Body

## 1. Introduction

As a new machine learning algorithm, support vector machine (SVM) is based on the statistical learning theory which was proposed by Vapnik [1] and Wolfe dual programming theory. Compared with other learning algorithms, SVM possesses a rigorous foundation of mathematical theory, well-generalized ability, and global optimum, with the result that is widely used in pattern recognition and functional regression.In general, the input data is assumed to be accurate. However, in practice, the statistical errors and measuring errors of observed data are inevitable; that is, the data is disturbed. The effect of perturbation of input data on solving the regression problem is often neglected. Although SVR is robust, while the parameters are optimal, these parameters are usually reasonably sensitive to noise data and singular value. The robust optimization method, which focused on treatability of computation in the case of data points disturbing in convex sets, was first proposed by Soyster [2] and developed, respectively, by Ben-Tal and Nemirovski [3, 4] and El-Ghaoui et al. [5, 6]. Since then, Melvyn [7] presented more comprehensive collection of disturbance without increasing the computing difficulty, which enabled the rapid development of the robust optimization method. The research aimed on solving the programming problems with polyhedron disturbance or spheroid disturbance. Bertsimas and Sim [8] and Alizadeh and Goldfarb [9] put forward the robust linear programming degenerated into a second-order cone programming, second-order cone programming into a semidefinite programming, and semi-definite programming into the NP problem. Zhixia et al. [10] applied this method to classification problem and proposed the robust support vector classification. This paper aims to study the regression problems of spheroid disturbance by means of the robust optimization method and to establish a robust regression model which makes the regression functions highly robust for perturbed data and system parameters.


## 2. Theory

### 2.1. Training Set

Assume that the training set is(1)
T
=
{
(
χ
1
,
y
1
)
,
…
,
(
χ
m
,
y
m
)
}
,
where
(2)
χ
i
=
{
x
i
+
r
i
u
i
∥
u
i
∥
≤
1
}
,
i
=
1
,
…
,
m
.The input setx
i can be viewed as a sphere of radius r
i centering on the measured value x
i, r
i is closely related to measurement accuracy, and m is sample size.


### 2.2. Original Problem

Referring to the original problem of linearε-support vector regression, it is not difficult to derive the original problem of robust linear ε-support vector regression, which is a convex quadratic programming, by replacing the original input with the input collection χ
i:
(3)
min
⁡
w
,
b
,
ξ
,
(
1
2
)
·
∥
w
∥
2
+
C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
,
s
.
t
.
(
w
(
x
i
+
r
i
u
i
)
+
b
)
-
y
i
≤
ε
+
ξ
i
,
y
i
-
(
w
(
x
i
+
r
i
u
i
)
+
b
)
≤
ε
+
ξ
¯
i
,
ξ
i
,
ξ
¯
i
≥
0
,
i
=
1
,
…
,
m
.Theorem 1.
The necessary and sufficient conditions for the solution of the original optimization problem (3) are that w
*, b
*, ξ
*, and ξ
¯
* are the solutions for the following second-order cone programming:
(4)
min
⁡
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
(
1
2
)
·
(
u
-
v
)
+
C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
,
s
.
t
.
(
w
·
x
i
)
+
b
-
y
i
+
r
i
t
≤
ε
+
ξ
i
,
y
i
-
(
(
w
·
x
i
)
+
b
)
+
r
i
t
≤
ε
+
ξ
¯
i
,
ξ
i
,
ξ
¯
i
≥
0
,
i
=
1
,
…
,
m
,
u
+
v
=
1
,
(
u
t
v
)
∈
L
3
,
(
t
w
)
∈
L
n
+
1
,
where n is the dimensionality of the input data χ
i.Proof.
Since(5)
max
⁡
{
r
i
(
w
·
u
i
)
,
∥
u
i
∥
≤
1
}
=
r
i
∥
w
∥
,
min
⁡
{
r
i
(
w
·
u
i
)
,
∥
u
i
∥
≤
1
}
=
-
r
i
∥
w
∥
.
The original problem (3) can be converted to
(6)
min
⁡
w
,
b
,
ξ
,
(
1
2
)
·
∥
w
∥
2
+
C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
,
s
.
t
.
(
w
·
x
i
)
+
b
-
y
i
+
r
i
∥
w
∥
≤
ε
+
ξ
i
,
y
i
-
(
(
w
·
x
i
)
+
b
)
+
r
i
∥
w
∥
≤
ε
+
ξ
¯
i
,
ξ
i
,
ξ
¯
i
≥
0
,
i
=
1
,
…
,
m
.
If variablet is introduced, satisfying ∥
w
∥
≤
t, the above problem could prove to be a second-order cone programming:
(7)
min
⁡
w
,
b
,
ξ
,
(
1
2
)
·
t
2
+
C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
,
s
.
t
.
(
w
·
x
i
)
+
b
-
y
i
+
r
i
t
≤
ε
+
ξ
i
,
y
i
-
(
(
w
·
x
i
)
+
b
)
+
r
i
t
≤
ε
+
ξ
¯
i
,
ξ
i
,
ξ
¯
i
≥
0
,
i
=
1
,
…
,
m
,
∥
w
∥
≤
t
.
When variablesu and v are brought in, u and v are supposed to satisfy the linear constraint u
+
v
=
1 and the second-order cone constraint (
t
2
+
v
2
)
1
/
2
≤
u, and the nonlinear terms t
2 in the objective function are replaced with u
-
v; therefore, the problem (7) can be written as the problem (4). From the above, the problem (3) is equivalent to the problem (4).


### 2.3. Dual Problem

Introduce the Lagrange function:(8)
L
=
(
1
2
)
·
(
u
-
v
)
+
C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
+
∑
i
=
1
m
α
i
(
(
w
·
x
i
)
+
b
-
y
i
+
r
i
t
-
ε
-
ξ
i
)
+
∑
i
=
1
m
β
i
(
y
i
-
(
(
w
·
x
i
)
+
b
)
+
r
i
t
-
ε
-
ξ
¯
i
)
-
∑
i
=
1
m
θ
i
ξ
i
-
∑
i
=
1
m
η
i
ξ
¯
i
+
φ
·
(
u
+
v
-
1
)
-
z
u
u
-
z
v
v
-
δ
t
-
z
t
t
-
z
w
T
w
,
where α
,
β
,
θ
,
η
∈
R
m
,
φ
,
z
u
,
z
v
,
δ
,
z
t
∈
R
,
z
w
∈
R
n are the multipliers vectors corresponding to the constraints. Eliminating variables θ
,
η
,
z
t, and z
w, the following theorem can be obtained.Theorem 2.
The following second-order cone programming is the dual problem of the second-order cone programming (4). 									(9)
max
⁡
α
,
β
,
φ
,
δ
,
z
u
,
z
v
-
∑
i
=
1
m
α
i
(
y
i
+
ε
)
+
∑
i
=
1
m
β
i
(
y
i
-
ε
)
-
φ
,
s
.
t
.
z
u
-
φ
=
1
2
,
z
v
-
φ
=
-
1
2
,
0
≤
α
i
≤
C
,
0
≤
β
i
≤
C
,
z
u
≥
(
δ
2
+
z
v
2
)
1
/
2
,
∑
i
=
1
m
α
i
-
∑
i
=
1
m
β
i
=
0
,
i
=
1
,
…
,
m
,
j
=
1
,
…
,
m
,
δ
≤
∑
i
=
1
m
r
i
(
α
i
+
β
i
)
-
(
∑
i
=
1
m
∑
j
=
1
m
(
α
i
-
β
i
)
(
α
j
-
β
j
)
(
x
i
·
x
j
)
)
1
/
2
.Proof.
The feasible region of the second-order cone programming problem (4) is
(10)
D
=
{
(
∑
j
=
1
n
w
j
2
)
1
/
2
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∣
(
w
·
x
i
)
+
b
-
y
i
+
r
i
t
≤
ε
+
ξ
i
,
y
i
-
(
(
w
·
x
i
)
+
b
)
+
r
i
t
≤
ε
+
ξ
¯
i
,
ξ
i
,
ξ
¯
i
≥
0
,
i
=
1
,
…
,
m
,
u
≥
(
t
2
+
v
2
)
1
/
2
,
t
≥
(
∑
j
=
1
n
w
j
2
)
1
/
2
,
j
=
1
,
…
n
;
u
+
v
=
1
}
.
The feasible region of the dual problem (9) is
(11)
E
=
{
∑
i
=
1
m
α
i
α
,
β
,
φ
,
δ
,
z
u
,
z
v
∣
0
≤
α
i
≤
C
,
0
≤
β
i
≤
C
,
z
u
≥
(
δ
2
+
z
v
2
)
1
/
2
,
δ
≤
∑
i
=
1
m
r
i
·
(
α
i
+
β
i
)
-
(
∑
i
=
1
m
∑
j
=
1
m
(
α
i
-
β
i
)
(
α
j
-
β
j
)
(
x
i
·
x
j
)
)
1
/
2
,
z
u
-
φ
=
1
2
,
z
v
-
φ
=
-
1
2
,
∑
i
=
1
m
α
i
-
∑
i
=
1
m
β
i
=
0
,
i
=
1
,
…
,
m
,
j
=
1
,
…
,
m
}
.
Assuming that the optimal value of the problem (4) is p
*,
(12)
p
*
=

inf
⁡
⁡
{
(
1
2
)
·
(
u
-
v
)

+

C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
∣
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
D
}
.
Proceeding from the lower bound of the estimate ofp
*, the Lagrange function of the second-order cone programming problem (4) is introduced and written as L
(
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
):
(13)
∀
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
D
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
∈
E
,
L
(
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
)
≤
(
1
2
)
·
(
u
-
v
)
+
C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
,
inf
⁡
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
R
n
L
(
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
)
≤
inf
⁡
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
D
L
(
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
)
≤
inf
⁡
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
D
(
(
1
2
)
·
(
u
-
v
)
+
C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
)
.
let
(14)
g
(
α
,
β
,
φ
,
δ
,
z
u
,
z
v
)
=
inf
⁡
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
R
n
L
(
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
)
;
thus
(15)
g
(
α
,
β
,
φ
,
δ
,
z
u
,
z
v
)
≤
p
*
.
Formula (15) implies ∀
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
D
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
∈
E, g
(
α
,
β
,
φ
,
δ
,
z
u
,
z
v
) is the lower bound of p
*.
To get the optimal value, the maximal value ofg
(
α
,
β
,
φ
,
δ
,
z
u
,
z
v
), ∀
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
D
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
∈
E is need to be obtained. So, the dual problem (9) is deduced.


### 2.4. Robust SVR Algorithm

#### 2.4.1. Linear Robust SVR Algorithm

(1) The given training data should be written as the way of formulae (1)~(2).(2) By constructing and solving the second-order cone programming problem (9), the solution (
α
i
*
,
β
i
*
,
φ
*
,
δ
*
,
z
u
*
,
z
v
*
) can be obtained. Besides, it is necessary to select an appropriate penalty parameter C
>
0.(3) The solution(
w
*
,
b
*
) of the original problem (4) is acquired in the following way:
(16)
w
*
=
δ
*
∑
i
=
1
m
(
α
i
*
-
β
i
*
)
x
i
(
∑
i
=
1
m
(
α
i
*
+
β
i
*
)
r
i
-
δ
*
)
.Select a componentα
j of α or a component β
k of β, which is located in the open interval (0, C); if α
j is chosen, it is got as follows:
(17)
b
*
=
y
j
-
δ
*
∑
i
=
1
m
(
α
i
*
-
β
i
*
)
(
x
i
·
x
j
)
(
∑
i
=
1
m
(
α
i
*
+
β
i
*
)
r
i
-
δ
*
)
+
ε
+
r
i
δ
*
.Ifβ
k is chosen, it is got as follows:
(18)
b
*
=
y
k
-
δ
*
∑
i
=
1
m
(
α
i
*
-
β
i
*
)
(
x
i
·
x
k
)
(
∑
i
=
1
m
(
α
i
*
+
β
i
*
)
r
i
-
δ
*
)
-
ε
-
r
i
δ
*
.(4) Then regression function is established:(19)
f
(
x
)
=
δ
*
∑
i
=
1
m
(
α
i
*
-
β
i
*
)
(
x
i
·
x
)
(
∑
i
=
1
m
(
α
i
*
+
β
i
*
)
r
i
-
δ
*
)
+
b
.


#### 2.4.2. Nonlinear Robust SVR Algorithm

By making the following modifications to the algorithm shown in Section2.4.1, the nonlinear robust SVR algorithm can be constructed:(1)
Kernel functionK
(
x
i
,
x
j
) (common kernel functions include Gaussian kernel function, polynomial kernel function, Cauchy kernel function, and Laplace kernel function) is introduced; replace the inner products (
x
i
·
x
j
) and (
x
i
·
x
) appearing in the linear robust SVR algorithm shown in Section 2.4.1, with K
(
x
i
,
x
j
) and K
(
x
i
,
x
);
(2)
SubstituteR
i for r
i appearing in the second-order cone programming (9).To getR
i, the mapping should be written as X
=
Φ
(
x
); obviously, ∥
χ
i
-
x
i
∥
≤
r
i is equivalent to
(20)
∥
Φ
(
χ
i
)
-
Φ
(
x
i
)
∥
2
=
(
(
Φ
(
χ
i
)
-
Φ
(
x
i
)
)
·
(
Φ
(
χ
i
)
-
Φ
(
x
i
)
)
)
=
K
(
χ
i
,
χ
i
)
-
2
K
(
χ
i
,
x
i
)
+
K
(
x
i
,
x
i
)
=
F
(
∥
χ
i
-
x
i
∥
)
≤
R
i
2
.
So R
i
=
F
(
r
i
).


## 2.1. Training Set

Assume that the training set is(1)
T
=
{
(
χ
1
,
y
1
)
,
…
,
(
χ
m
,
y
m
)
}
,
where
(2)
χ
i
=
{
x
i
+
r
i
u
i
∥
u
i
∥
≤
1
}
,
i
=
1
,
…
,
m
.The input setx
i can be viewed as a sphere of radius r
i centering on the measured value x
i, r
i is closely related to measurement accuracy, and m is sample size.


## 2.2. Original Problem

Referring to the original problem of linearε-support vector regression, it is not difficult to derive the original problem of robust linear ε-support vector regression, which is a convex quadratic programming, by replacing the original input with the input collection χ
i:
(3)
min
⁡
w
,
b
,
ξ
,
(
1
2
)
·
∥
w
∥
2
+
C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
,
s
.
t
.
(
w
(
x
i
+
r
i
u
i
)
+
b
)
-
y
i
≤
ε
+
ξ
i
,
y
i
-
(
w
(
x
i
+
r
i
u
i
)
+
b
)
≤
ε
+
ξ
¯
i
,
ξ
i
,
ξ
¯
i
≥
0
,
i
=
1
,
…
,
m
.Theorem 1.
The necessary and sufficient conditions for the solution of the original optimization problem (3) are that w
*, b
*, ξ
*, and ξ
¯
* are the solutions for the following second-order cone programming:
(4)
min
⁡
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
(
1
2
)
·
(
u
-
v
)
+
C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
,
s
.
t
.
(
w
·
x
i
)
+
b
-
y
i
+
r
i
t
≤
ε
+
ξ
i
,
y
i
-
(
(
w
·
x
i
)
+
b
)
+
r
i
t
≤
ε
+
ξ
¯
i
,
ξ
i
,
ξ
¯
i
≥
0
,
i
=
1
,
…
,
m
,
u
+
v
=
1
,
(
u
t
v
)
∈
L
3
,
(
t
w
)
∈
L
n
+
1
,
where n is the dimensionality of the input data χ
i.Proof.
Since(5)
max
⁡
{
r
i
(
w
·
u
i
)
,
∥
u
i
∥
≤
1
}
=
r
i
∥
w
∥
,
min
⁡
{
r
i
(
w
·
u
i
)
,
∥
u
i
∥
≤
1
}
=
-
r
i
∥
w
∥
.
The original problem (3) can be converted to
(6)
min
⁡
w
,
b
,
ξ
,
(
1
2
)
·
∥
w
∥
2
+
C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
,
s
.
t
.
(
w
·
x
i
)
+
b
-
y
i
+
r
i
∥
w
∥
≤
ε
+
ξ
i
,
y
i
-
(
(
w
·
x
i
)
+
b
)
+
r
i
∥
w
∥
≤
ε
+
ξ
¯
i
,
ξ
i
,
ξ
¯
i
≥
0
,
i
=
1
,
…
,
m
.
If variablet is introduced, satisfying ∥
w
∥
≤
t, the above problem could prove to be a second-order cone programming:
(7)
min
⁡
w
,
b
,
ξ
,
(
1
2
)
·
t
2
+
C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
,
s
.
t
.
(
w
·
x
i
)
+
b
-
y
i
+
r
i
t
≤
ε
+
ξ
i
,
y
i
-
(
(
w
·
x
i
)
+
b
)
+
r
i
t
≤
ε
+
ξ
¯
i
,
ξ
i
,
ξ
¯
i
≥
0
,
i
=
1
,
…
,
m
,
∥
w
∥
≤
t
.
When variablesu and v are brought in, u and v are supposed to satisfy the linear constraint u
+
v
=
1 and the second-order cone constraint (
t
2
+
v
2
)
1
/
2
≤
u, and the nonlinear terms t
2 in the objective function are replaced with u
-
v; therefore, the problem (7) can be written as the problem (4). From the above, the problem (3) is equivalent to the problem (4).


## 2.3. Dual Problem

Introduce the Lagrange function:(8)
L
=
(
1
2
)
·
(
u
-
v
)
+
C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
+
∑
i
=
1
m
α
i
(
(
w
·
x
i
)
+
b
-
y
i
+
r
i
t
-
ε
-
ξ
i
)
+
∑
i
=
1
m
β
i
(
y
i
-
(
(
w
·
x
i
)
+
b
)
+
r
i
t
-
ε
-
ξ
¯
i
)
-
∑
i
=
1
m
θ
i
ξ
i
-
∑
i
=
1
m
η
i
ξ
¯
i
+
φ
·
(
u
+
v
-
1
)
-
z
u
u
-
z
v
v
-
δ
t
-
z
t
t
-
z
w
T
w
,
where α
,
β
,
θ
,
η
∈
R
m
,
φ
,
z
u
,
z
v
,
δ
,
z
t
∈
R
,
z
w
∈
R
n are the multipliers vectors corresponding to the constraints. Eliminating variables θ
,
η
,
z
t, and z
w, the following theorem can be obtained.Theorem 2.
The following second-order cone programming is the dual problem of the second-order cone programming (4). 									(9)
max
⁡
α
,
β
,
φ
,
δ
,
z
u
,
z
v
-
∑
i
=
1
m
α
i
(
y
i
+
ε
)
+
∑
i
=
1
m
β
i
(
y
i
-
ε
)
-
φ
,
s
.
t
.
z
u
-
φ
=
1
2
,
z
v
-
φ
=
-
1
2
,
0
≤
α
i
≤
C
,
0
≤
β
i
≤
C
,
z
u
≥
(
δ
2
+
z
v
2
)
1
/
2
,
∑
i
=
1
m
α
i
-
∑
i
=
1
m
β
i
=
0
,
i
=
1
,
…
,
m
,
j
=
1
,
…
,
m
,
δ
≤
∑
i
=
1
m
r
i
(
α
i
+
β
i
)
-
(
∑
i
=
1
m
∑
j
=
1
m
(
α
i
-
β
i
)
(
α
j
-
β
j
)
(
x
i
·
x
j
)
)
1
/
2
.Proof.
The feasible region of the second-order cone programming problem (4) is
(10)
D
=
{
(
∑
j
=
1
n
w
j
2
)
1
/
2
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∣
(
w
·
x
i
)
+
b
-
y
i
+
r
i
t
≤
ε
+
ξ
i
,
y
i
-
(
(
w
·
x
i
)
+
b
)
+
r
i
t
≤
ε
+
ξ
¯
i
,
ξ
i
,
ξ
¯
i
≥
0
,
i
=
1
,
…
,
m
,
u
≥
(
t
2
+
v
2
)
1
/
2
,
t
≥
(
∑
j
=
1
n
w
j
2
)
1
/
2
,
j
=
1
,
…
n
;
u
+
v
=
1
}
.
The feasible region of the dual problem (9) is
(11)
E
=
{
∑
i
=
1
m
α
i
α
,
β
,
φ
,
δ
,
z
u
,
z
v
∣
0
≤
α
i
≤
C
,
0
≤
β
i
≤
C
,
z
u
≥
(
δ
2
+
z
v
2
)
1
/
2
,
δ
≤
∑
i
=
1
m
r
i
·
(
α
i
+
β
i
)
-
(
∑
i
=
1
m
∑
j
=
1
m
(
α
i
-
β
i
)
(
α
j
-
β
j
)
(
x
i
·
x
j
)
)
1
/
2
,
z
u
-
φ
=
1
2
,
z
v
-
φ
=
-
1
2
,
∑
i
=
1
m
α
i
-
∑
i
=
1
m
β
i
=
0
,
i
=
1
,
…
,
m
,
j
=
1
,
…
,
m
}
.
Assuming that the optimal value of the problem (4) is p
*,
(12)
p
*
=

inf
⁡
⁡
{
(
1
2
)
·
(
u
-
v
)

+

C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
∣
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
D
}
.
Proceeding from the lower bound of the estimate ofp
*, the Lagrange function of the second-order cone programming problem (4) is introduced and written as L
(
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
):
(13)
∀
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
D
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
∈
E
,
L
(
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
)
≤
(
1
2
)
·
(
u
-
v
)
+
C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
,
inf
⁡
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
R
n
L
(
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
)
≤
inf
⁡
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
D
L
(
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
)
≤
inf
⁡
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
D
(
(
1
2
)
·
(
u
-
v
)
+
C
∑
i
=
1
m
(
ξ
i
+
ξ
¯
i
)
)
.
let
(14)
g
(
α
,
β
,
φ
,
δ
,
z
u
,
z
v
)
=
inf
⁡
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
R
n
L
(
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
)
;
thus
(15)
g
(
α
,
β
,
φ
,
δ
,
z
u
,
z
v
)
≤
p
*
.
Formula (15) implies ∀
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
D
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
∈
E, g
(
α
,
β
,
φ
,
δ
,
z
u
,
z
v
) is the lower bound of p
*.
To get the optimal value, the maximal value ofg
(
α
,
β
,
φ
,
δ
,
z
u
,
z
v
), ∀
w
,
b
,
ξ
,
ξ
¯
,
u
,
v
,
t
∈
D
,
α
,
β
,
φ
,
δ
,
z
u
,
z
v
∈
E is need to be obtained. So, the dual problem (9) is deduced.


## 2.4. Robust SVR Algorithm

### 2.4.1. Linear Robust SVR Algorithm

(1) The given training data should be written as the way of formulae (1)~(2).(2) By constructing and solving the second-order cone programming problem (9), the solution (
α
i
*
,
β
i
*
,
φ
*
,
δ
*
,
z
u
*
,
z
v
*
) can be obtained. Besides, it is necessary to select an appropriate penalty parameter C
>
0.(3) The solution(
w
*
,
b
*
) of the original problem (4) is acquired in the following way:
(16)
w
*
=
δ
*
∑
i
=
1
m
(
α
i
*
-
β
i
*
)
x
i
(
∑
i
=
1
m
(
α
i
*
+
β
i
*
)
r
i
-
δ
*
)
.Select a componentα
j of α or a component β
k of β, which is located in the open interval (0, C); if α
j is chosen, it is got as follows:
(17)
b
*
=
y
j
-
δ
*
∑
i
=
1
m
(
α
i
*
-
β
i
*
)
(
x
i
·
x
j
)
(
∑
i
=
1
m
(
α
i
*
+
β
i
*
)
r
i
-
δ
*
)
+
ε
+
r
i
δ
*
.Ifβ
k is chosen, it is got as follows:
(18)
b
*
=
y
k
-
δ
*
∑
i
=
1
m
(
α
i
*
-
β
i
*
)
(
x
i
·
x
k
)
(
∑
i
=
1
m
(
α
i
*
+
β
i
*
)
r
i
-
δ
*
)
-
ε
-
r
i
δ
*
.(4) Then regression function is established:(19)
f
(
x
)
=
δ
*
∑
i
=
1
m
(
α
i
*
-
β
i
*
)
(
x
i
·
x
)
(
∑
i
=
1
m
(
α
i
*
+
β
i
*
)
r
i
-
δ
*
)
+
b
.


### 2.4.2. Nonlinear Robust SVR Algorithm

By making the following modifications to the algorithm shown in Section2.4.1, the nonlinear robust SVR algorithm can be constructed:(1)
Kernel functionK
(
x
i
,
x
j
) (common kernel functions include Gaussian kernel function, polynomial kernel function, Cauchy kernel function, and Laplace kernel function) is introduced; replace the inner products (
x
i
·
x
j
) and (
x
i
·
x
) appearing in the linear robust SVR algorithm shown in Section 2.4.1, with K
(
x
i
,
x
j
) and K
(
x
i
,
x
);
(2)
SubstituteR
i for r
i appearing in the second-order cone programming (9).To getR
i, the mapping should be written as X
=
Φ
(
x
); obviously, ∥
χ
i
-
x
i
∥
≤
r
i is equivalent to
(20)
∥
Φ
(
χ
i
)
-
Φ
(
x
i
)
∥
2
=
(
(
Φ
(
χ
i
)
-
Φ
(
x
i
)
)
·
(
Φ
(
χ
i
)
-
Φ
(
x
i
)
)
)
=
K
(
χ
i
,
χ
i
)
-
2
K
(
χ
i
,
x
i
)
+
K
(
x
i
,
x
i
)
=
F
(
∥
χ
i
-
x
i
∥
)
≤
R
i
2
.
So R
i
=
F
(
r
i
).


## 2.4.1. Linear Robust SVR Algorithm

(1) The given training data should be written as the way of formulae (1)~(2).(2) By constructing and solving the second-order cone programming problem (9), the solution (
α
i
*
,
β
i
*
,
φ
*
,
δ
*
,
z
u
*
,
z
v
*
) can be obtained. Besides, it is necessary to select an appropriate penalty parameter C
>
0.(3) The solution(
w
*
,
b
*
) of the original problem (4) is acquired in the following way:
(16)
w
*
=
δ
*
∑
i
=
1
m
(
α
i
*
-
β
i
*
)
x
i
(
∑
i
=
1
m
(
α
i
*
+
β
i
*
)
r
i
-
δ
*
)
.Select a componentα
j of α or a component β
k of β, which is located in the open interval (0, C); if α
j is chosen, it is got as follows:
(17)
b
*
=
y
j
-
δ
*
∑
i
=
1
m
(
α
i
*
-
β
i
*
)
(
x
i
·
x
j
)
(
∑
i
=
1
m
(
α
i
*
+
β
i
*
)
r
i
-
δ
*
)
+
ε
+
r
i
δ
*
.Ifβ
k is chosen, it is got as follows:
(18)
b
*
=
y
k
-
δ
*
∑
i
=
1
m
(
α
i
*
-
β
i
*
)
(
x
i
·
x
k
)
(
∑
i
=
1
m
(
α
i
*
+
β
i
*
)
r
i
-
δ
*
)
-
ε
-
r
i
δ
*
.(4) Then regression function is established:(19)
f
(
x
)
=
δ
*
∑
i
=
1
m
(
α
i
*
-
β
i
*
)
(
x
i
·
x
)
(
∑
i
=
1
m
(
α
i
*
+
β
i
*
)
r
i
-
δ
*
)
+
b
.


## 2.4.2. Nonlinear Robust SVR Algorithm

By making the following modifications to the algorithm shown in Section2.4.1, the nonlinear robust SVR algorithm can be constructed:(1)
Kernel functionK
(
x
i
,
x
j
) (common kernel functions include Gaussian kernel function, polynomial kernel function, Cauchy kernel function, and Laplace kernel function) is introduced; replace the inner products (
x
i
·
x
j
) and (
x
i
·
x
) appearing in the linear robust SVR algorithm shown in Section 2.4.1, with K
(
x
i
,
x
j
) and K
(
x
i
,
x
);
(2)
SubstituteR
i for r
i appearing in the second-order cone programming (9).To getR
i, the mapping should be written as X
=
Φ
(
x
); obviously, ∥
χ
i
-
x
i
∥
≤
r
i is equivalent to
(20)
∥
Φ
(
χ
i
)
-
Φ
(
x
i
)
∥
2
=
(
(
Φ
(
χ
i
)
-
Φ
(
x
i
)
)
·
(
Φ
(
χ
i
)
-
Φ
(
x
i
)
)
)
=
K
(
χ
i
,
χ
i
)
-
2
K
(
χ
i
,
x
i
)
+
K
(
x
i
,
x
i
)
=
F
(
∥
χ
i
-
x
i
∥
)
≤
R
i
2
.
So R
i
=
F
(
r
i
).


## 3. Numerical Experiments

### 3.1. Linear Numerical Experiment

Example 1.
Given that objective function isy
=
2
x
(
x
∈
[
1,10
]
), the training set could be written as the way of formulae (1)~(2), where x
i is 10 equidistant points distributed in the interval [
1,10
]. r
i can be regarded as a constant which equals 0.5. The disturbance of data u
i is a random number which is located in the interval [
-
1,1
], where i
=
10. The methods of standard SVR and robust SVR shown in Section 2.4.1 are employed to regress and fit the objective function. Then the errors of ten test points, which are randomly selected, are analysed and compared. The results are shown in Table 1.Table 1
Table of error analysis of linear function regression.
Test points
Algorithm
Linear standard SVR
Linear robust SVR
Point 1
0.4388
0.0062
Point 2
0.3316
0.0065
Point 3
0.2244
0.0068
Point 4
0.1172
0.0072
Point 5
0.0100
0.0075
Point 6
0.0972
0.0078
Point 7
0.2044
0.0082
Point 8
0.3117
0.0085
Point 9
0.4189
0.0089
Point 10
0.5261
0.0092
AVG
0.2680
0.0077


### 3.2. Nonlinear Numerical Experiments

Example 2.
Given that objective function isy
=
x
2
(
x
∈
[
0.5
,
10
]
), the training set could be written in the way of formulae (1)~(2), where x
i is 20 equidistant points distributed in the interval [
0.5,10
]. r
i can be regarded as a constant which equals 0.05. The disturbance of data u
i is a random number which is located in the interval [
-
1,1
], where i
=
20. The methods of standard SVR and robust SVR shown in Section 2.4.2 are employed to regress and fit the objective function. Then the errors of ten test points, which are randomly selected, are analysed and compared. The results are given in Table 2.Table 2
Table of error analysis of nonlinear function regression.
Test points
Algorithm
Nonlinear standard SVR
Nonlinear robust SVR
Point 1
0.1898
0.0511
Point 2
0.0668
0.0466
Point 3
0.0788
0.0385
Point 4
0.2183
0.0270
Point 5
0.2929
0.0119
Point 6
0.3589
0.0066
Point 7
0.5538
0.0287
Point 8
0.0887
0.0542
Point 9
0.0331
0.0833
Point 10
0.1305
0.1158
AVG
0.2012
0.0464


### 3.3. Discussion

Obviously, the system parameters are very robust. In addition, it is shown that the forecast errors of the robust method are lower than that of the standard SVM method in Table1. A similar conclusion can also be presented in Table 2. In short, the robust SVR method has been validated to be of advantage in the field of regression analysis with perturbation problem.


## 3.1. Linear Numerical Experiment

Example 1.
Given that objective function isy
=
2
x
(
x
∈
[
1,10
]
), the training set could be written as the way of formulae (1)~(2), where x
i is 10 equidistant points distributed in the interval [
1,10
]. r
i can be regarded as a constant which equals 0.5. The disturbance of data u
i is a random number which is located in the interval [
-
1,1
], where i
=
10. The methods of standard SVR and robust SVR shown in Section 2.4.1 are employed to regress and fit the objective function. Then the errors of ten test points, which are randomly selected, are analysed and compared. The results are shown in Table 1.Table 1
Table of error analysis of linear function regression.
Test points
Algorithm
Linear standard SVR
Linear robust SVR
Point 1
0.4388
0.0062
Point 2
0.3316
0.0065
Point 3
0.2244
0.0068
Point 4
0.1172
0.0072
Point 5
0.0100
0.0075
Point 6
0.0972
0.0078
Point 7
0.2044
0.0082
Point 8
0.3117
0.0085
Point 9
0.4189
0.0089
Point 10
0.5261
0.0092
AVG
0.2680
0.0077


## 3.2. Nonlinear Numerical Experiments

Example 2.
Given that objective function isy
=
x
2
(
x
∈
[
0.5
,
10
]
), the training set could be written in the way of formulae (1)~(2), where x
i is 20 equidistant points distributed in the interval [
0.5,10
]. r
i can be regarded as a constant which equals 0.05. The disturbance of data u
i is a random number which is located in the interval [
-
1,1
], where i
=
20. The methods of standard SVR and robust SVR shown in Section 2.4.2 are employed to regress and fit the objective function. Then the errors of ten test points, which are randomly selected, are analysed and compared. The results are given in Table 2.Table 2
Table of error analysis of nonlinear function regression.
Test points
Algorithm
Nonlinear standard SVR
Nonlinear robust SVR
Point 1
0.1898
0.0511
Point 2
0.0668
0.0466
Point 3
0.0788
0.0385
Point 4
0.2183
0.0270
Point 5
0.2929
0.0119
Point 6
0.3589
0.0066
Point 7
0.5538
0.0287
Point 8
0.0887
0.0542
Point 9
0.0331
0.0833
Point 10
0.1305
0.1158
AVG
0.2012
0.0464


## 3.3. Discussion

Obviously, the system parameters are very robust. In addition, it is shown that the forecast errors of the robust method are lower than that of the standard SVM method in Table1. A similar conclusion can also be presented in Table 2. In short, the robust SVR method has been validated to be of advantage in the field of regression analysis with perturbation problem.


## 4.  Conclusions

(1)
In the paper, a robustε-SVR model has been proposed, considering the input data as the convex set of spheroid disturbance, and two important theorems are also given: it is proved by Theorem 1 that the convex quadratic programming problem can be written as the second-order cone programming. Based on duality theory, the dual problem can be deduced by Theorem 2. By solving the dual problem, the optimal solution of original problem is obtained.
(2)
By virtue of kernel function, the robust linearε-SVR model could be promoted to the nonlinear domains. Finally, the numerical experiments demonstrate the robustness and effectiveness of the proposed algorithm.



---

*Source: 373571-2014-02-20.xml*