Linear programming support vector machines - Semantic Scholar

0 downloads 236 Views 250KB Size Report
Simulation results for both artificial and real data show that the generalization performance of our method is a good ..
Pattern Recognition 35 (2002) 2927 – 2936

www.elsevier.com/locate/patcog

Linear programming support vector machines Weida Zhou ∗ , Li Zhang, Licheng Jiao Key Laboratory for Radar Signal Processing, Xidian University, Xi’an, 710071, People’s Republic of China Received 3 May 2001; accepted 30 October 2001

Abstract Based on the analysis of the conclusions in the statistical learning theory, especially the VC dimension of linear functions, linear programming support vector machines (or SVMs) are presented including linear programming linear and nonlinear SVMs. In linear programming SVMs, in order to improve the speed of the training time, the bound of the VC dimension is loosened properly. Simulation results for both arti2cial and real data show that the generalization performance of our method is a good approximation of SVMs and the computation complex is largely reduced by our method. ? 2002 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved. Keywords: Statistical learning theory; VC dimension; Support vector machines; Generalization performance; Linear programming

1. Introduction Since the 1970s’, Vapnik et al. have applied themselves to the study of statistical learning theory [1–3]. Until the early of the 1990, a new kind of learning machines, support vector machine (SVM), was presented based on those theories [2,4,5]. The main study of statistical learning theory is the model of learning from examples, which can be described as: there are l random independent identically distributed examples (x1 ; y1 ); (x2 ; y2 ); : : : ; (xl ; yl ); ((x; y) ∈ (Rn ; R)) drawn according to the uniform probability distribution P(x; y); (P(x; y) = P(x)P(y | x)). Given a set of functions f(x; ); ∈ (where is a parameter set) from which the goal of learning from examples is to select a function f(x; 0 ) that can express the relationship between x and y in the best possible way. In general, in order to obtain f(x; 0 ), one has to minimize the expected risk functional  R( ) = L(y; f(x; ))P(x; y) dx dy; (1.1) where L(y; f(x; )) measures the loss between the response y to a given input x and the response f(x; a) provided ∗

Corresponding author. Fax: +86-29-823-6159. E-mail address: [email protected] (W. Zhou).

by the learning machine. The learning problems such as the problems of pattern recognition, regression estimation and density estimation may be taken as the same learning models with diFerent loss functions [2]. In this paper, we only deal with the problem of pattern recognition. Consider the following loss function  0 if y = f(x; ); L(y; f(x; )) = (1.2) 1 if y = f(x; ): Due to the probability distribution P(x; y) in Eq. (1.1) is unknown, the expected risk functional is replaced by the empirical risk functional 1 L(yi ; f(xi ; )): l i=1 l

Remp ( ) =

(1.3)

In order to know the quality of the empirical risk Remp ( ) to approximate the expected risk, Vapnik presented the following bound theorem [2]. With probability at least 1 −  (0 6  6 1), the inequality     4Remp ( ) R( ) 6 Remp ( ) + 1+ 1+ (1.4) 2  holds true. Where  = 4(h(ln(2l=h) + 1) − ln )=l and h is the VC dimension of the set of functions f(x; ), ∈ I.

0031-3203/02/$22.00 ? 2002 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved. PII: S 0 0 3 1 - 3 2 0 3 ( 0 1 ) 0 0 2 1 0 - 2

2928

W. Zhou et al. / Pattern Recognition 35 (2002) 2927 – 2936

From Eq. (1.4), we can see that the minimization of the expected risk R( ) is equal to the minimization of the two terms on the right-hand side of Eq. (1.4) at the same time. The 2rst term on the right of Eq. (1.4) Remp ( ) is minimized by learning process. The second term varies with the VC dimension h and the number of examples l. The smaller the VC dimension h and the larger the number of examples l, the smaller the value of the second term. In fact, the number of examples is 2nite. So for the case of a small example set, the minimization of the expected risk is implemented by minimizing the empirical risk and the VC dimension. Generally speaking, a complex target function set or a large hypothesis space is required for minimizing the empirical risk. But a small hypothesis space is requested for minimizing the VC dimension of the target function set. Therefore, the minimization problem is in a dilemma, the best solution of the problem is to take a compromise between them. Now, restrict the target function to the linear function. Similar to the set of -margin separating hyperplanes de2ned in Ref. [3], we de2ne the set of m -margin separating hyperplanes. Let us denote the target functions set by f(x; w; b) = wT x + b. If these functions classify an example x as follows:  1; wT x + b ¿ ; ¿0 (1.5) y= −1; wT x + b 6 − ; then the set f(x; w; b) = wT x + b is called the set of m -margin separating hyperplanes whose margin is m =

 ; ||w||2

(1.6)

where || · ||2 denotes l2 -norm, namely Euclidean distance. There is a conclusion about the VC dimension of the set of m -margin separating hyperplanes. Let vectors x ∈ X belong to a sphere of radius R. Then the set of m -margin separating hyperplanes has the VC dimension h bounded by the inequality:  2

R h 6 min ; n + 1; (1.7) m2 where n is the dimension of input space. From Eq. (1.7), we can see that if the VC dimension of the target functions set h is ¡ n, then h varies inversely with the margin m2 . In this way, f(x; w0 ; b0 ) can be approached by minimizing the empirical risk functional and maximizing the separating margin m , which is the structural risk in SVMs introduced by Vapnik: Rstructure ( ) = CRemp ( ) +

1 ; m2

(1.8)

where the constant C ¿ 0 is a parameter chosen by the users and is a parameter of the target function set. For l random independent identically distributed examples (x1 ; y1 ); (x2 ; y2 ); : : : ; (xl ; yl ); ((x; y) ∈ (Rn ; R)), the linear

SVMs for pattern recognition have the following optimization problem [4]: min

 1 ||w||22 + C i; 2 i=1

s:t:

yi ((w · xi ) + b) ¿ 1 − i ;

l

i

¿ 0;

(1.9)

i = 1; : : : ; l;

where (·; ·) denotes the inner product. Minimizing the 2rst term in Eq. (1.9) 12 ||w||22 plays the role of controlling the capacity of the learning machine and avoiding the over2tting of the machine. While minimizing the second term is to minimize the empirical risk. The Wolfe dual programming of Eq. (1.9) is [4] max

W ( ) =

l 

i −

i=1

s:t:

l 

l 1 i j yi yj (xi · xj ); 2 i; j=1

i yi = 0;

(1.10)

(1.11)

i=1

i ∈ [0; C];

i = 1; : : : ; l:

(1.12)

The decision function has the following form: f(x) =

l 

i yi (xi · x) + b

(1.13)

i=1

and y = sgn(f(x)):

(1.14)

The kernel functions are introduced in linear SVMs, which leads to nonlinear SVMs [4]: max

W ( ) =

l 

i −

i=1 l 

s:t:

l 1 i j yi yj K(xi · xj ) 2 i; j=1

i yi = 0

(1.16)

(1.17)

i=1

i ∈ [0; C];

i = 1; : : : ; l:

(1.18)

And then the decision function can be written as f(x) =

l 

i yi K(xi · x) + b:

(1.19)

i=1

In a nutshell, the theory foundation of SVMs (statistical learning theory) is rather perfect. But training a SVM requires the solution of a quadratic programming (QP) optimization that is not easy to implement, in particular for large-scale problems. Based on the statistical learning theory, the linear programming SVMs that are extremely simple without explicitly solving QP problems are proposed.

W. Zhou et al. / Pattern Recognition 35 (2002) 2927 – 2936

The denominator in Eq. (2.2) is translated into a constraint. Since the constant c has no eFect on solving of linear programming, it can be ignored. In doing so, we have the following programming:

2. Linear programming support vector machines (LPSVMs) 2.1. Linear LPSVMs Lemma 2.1. [6]: the equivalence of vector norm in n-dimension linear space V n . Let ||x|| and ||x||& be any vector norms in a 4nite dimension linear space V n . The norms include lp -norm; weight-norm and others. Then there exist two positive constants 0 ¡ c1 ¡ + ∞ and 0 ¡ c2 ¡ + ∞ such that c1 ||x||& 6 ||x|| 6 c2 ||x||&

∀x ∈ V

2929

n

LP1:

max

L=r

(2.4)

s:t:

yi (wT xi + b) ¿ r

i = 1; : : : ; l;

r¿0 −1 6 wj 6 1 j = 1; : : : ; n: The decision function takes the form

holds true.

f(x; w; b) = wT x + b

Theorem 2.2. Given the examples set ((x1 ; y1 ); : : : ; (xi ; yi ); : : : ; (xl ; yl )); (x; y) ∈ (Rn ; R) and the vectors x belong to a sphere of radius R. If the set of m -margin separating hyperplanes f(x; w; b) = wT x + b classify vectors x as follows:  1; wT x + b ¿ ;  ¿ 0: y= −1; wT x + b 6 − ;

and the output of pattern recognition is

Then there exist a constant 0 ¡ c ¡+∞ without depending on examples (x; y) and the parameters w and b such that the bound inequality   c2 · R2 · ||w||2& h 6 min ;n + 1 (2.1) 2

yi (wT xi + b) ¿ r

i = 1; : : : ; l;

r ¿ 0; where ||w||& is any vector norm and c is a constant. If ||w||& is 2-norm, then c = 1. Now consider l∞ -norm ||x||∞ . Certainly there exists a positive constant c without the set of examples and the parameters of the target functions set such that  2 2

c · R · ||w||2∞ h 6 min ;n + 1 2 holds on. And so Eq. (2.2) can be rewritten as r : L= c||w||∞

(2.3)

(2.7)

where sgn(·) is the sign function. For the nonseparable case, we have the following linear programming by introducing positive slack variable i : LP2:

min

L = −r + C

l 

(2.8)

i i=1

s:t:

yi (wT xi + b) ¿ r −

i

i = 1; : : : ; l;

(2.9)

r¿0 −1 6 wj 6 1 j = 1; : : : ; n; i

The proof of Theorem 2.2 is shown in Appendix A. The theorem can lead to the following programming directly. Given the examples set ((x1 ; y1 ); : : : ; (xi ; yi ); : : : ; (xl ; yl )); (x; y) ∈ (Rn ; R) and the set of linear target functions f(x; w; b) = wT x + b. We introduce the structural risk according to Theorem 2.2. At 2rst, we will start with the linearly separable case, or without error. r max L = (2.2) c||w||&

(2.6)

y = sgn(f(x; w; b));

holds true. Where ||w||& is any vector norm.

s:t:

(2.5)

¿ 0 i = 1; : : : ; l;

where C ¿ 0 is a constant. The decision function of the nonseparable case is the same as the separable case. 2.2. Nonlinear LPSVMs Similar to the nonlinear SVMs [1– 4], here we get the nonlinear LPSVMs by adopting the kernel functions K(xi ; xj ) [7]. In Eqs. (2.5) and (2.9), the relationship between weights w and vectors x is expressed by the form of dot products, (w · x). Now suppose we 2rst mapped the examples from n-dimensional space into some high-dimensional Euclidean space H : ( : Rn → H: Then of course the training algorithm would only depend on the examples through dot products in H , i.e. on functions of the form (((xi ) · ((xj )). If there were a kernel function K such that K(xi ; xj ) = ((xi ) · ((xj ), we would only need to use K in the training algorithm and would need to know what the mapping function ( is. Theorem 2.3. Given the set of examples ((((x1 ); y1 ); : : : ; (((xi ); yi ); : : : ; (((xl ); yl )); (((x); y) ∈ (H; R). The vectors x belong to a sphere of radius R. Let the set of target

2930

W. Zhou et al. / Pattern Recognition 35 (2002) 2927 – 2936

functions be f(x) =

l 

i yi ((xi ) · ((x) + b =

i=1

l 

i yi K(xi ; x) + b:

i=1

(2.10)

And the decision on examples x takes the form  1; f(x) ¿ ; y= ¿0 −1; f(x) 6 − ;

i=1

then there exist a constant 0 ¡ c ¡ + ∞ without depending the examples (x; y) and the parameter of the target functions set and b such that   c2 · R2 · || ||2& h 6 min ;n + 1 (2.11) 2 holds on. Where = ( 1 · · · l )T and || ||& is any vector norm. The proof of Theorem 2.3 is shown in Appendix B. Similar to linear LPSVMs, consider || ||∞ . We can have the following programming: LP3:

max s:t:

L=r

(2.12)  l 

yi f(xi ) = yi

 j yj K(xj ; xi ) + b ¿ r

j=1

i = 1; : : : ; l;

(2.13)

r¿0 −1 6 k 6 1

k = 1; : : : ; l:

f(x) =

i yi K(xi ; x) + b

(2.14)

i=1

and the output of pattern recognition is y = sgn(f(x)):

(2.15)

For the nonseparable case, we introduced the slack variables i to get the following linear programming: LP4:

min s:t:

L = −r + C

l 

yi f(xi ) = yi

(2.16)

i i=1  l 

 j yj K(xj ; xi ) + b

j=1

¿r −

i

i = 1; : : : ; l;

(2.17)

r¿0 −1 6 k 6 1 i

¿0

s:t:

yi f(xi ) = yi

 l 

 j yj (xj · xi ) + b

j=1

¿r −

i

i = 1; : : : ; l;

(2.19)

r¿0 −1 6 k 6 1 k = 1; : : : ; l; i

¿ 0 i = 1; : : : ; l:

3. Simulation experiments Four experiments have been done. For linear LPSVMs, a set of arti2cial data was used in experiments. And for nonlinear LPSVMs, the dual-spiral data, the handwritten digital data and the DS-CDMA multiuser detection data were adopted. For the sake of comparison, we used the programs in Matlab Optimization toolboxes (Version 5.3) for both quadratic programming support vector machines (or QPSVMs) and LPSVMs. 3.1. The experiment on arti4cial data

The decision function is l 

In Section 2.1, the linear LPSVMs are obtained under the hypothesis of linear target functions set f(x; w; b) = wT x + b. For high-dimensional examples (namely the number of examples is less than or equal to the dimension of example),

we can use the target functions f(x) = li=1 i yi (xi · x) + b, and then get the following linear LPSVMs: l  LP5: min L = −r + C (2.18) i

k = 1; : : : ; l;

i = 1; : : : ; l;

where C ¿ 0 is a constant. The decision function is identical to Eqs. (2.14) and (2.15).

Let us consider two-class arti2cial linear separable data. 100 training examples and 200 test ones are generated randomly according √ to√the uniform √ distribution √ √in rectangles√((0; 0); (1= 2; 1= 2); (0; 2); (−1= 2; 1= 2)) and √ √ √ √ √ √ ((1= 2; 1= 2); ( 2; 2); (1= 2; 3= 2); (0; 2)). The results are shown in Table 1 and Fig. 1. The results lead us to conclude that the training speed of LPSVMs is faster than that of QPSVMs without loss in the classi2cation performance. 3.2. The experiment on the dual-spiral data The dual-spiral problem is referred to as “touchstone” to test the ability of learning algorithm, which requires us to classify the points on one spiral from ones on another spiral in two-dimensional Cartesian coordinates [8]. In this experiment, we used Gaussian kernel K(xi ; xj ) = exp(−|xi − xj |2 =2p2 ) with p = 8. The results are shown in Table 2 and Fig. 2. From the results in Table 2 it can be concluded that the training speed of LPSVMs has been improved remarkably. The VC dimension of LPSVMs is larger than that of QPSVMs, so in theory the generalization performance of LPSVMs is worse than that of QPSVMs,

W. Zhou et al. / Pattern Recognition 35 (2002) 2927 – 2936

2931

Table 1 The results of arti2cial data Learning model

No. of training examples

No. of testing examples

Training time (s)

Recognition error (%)

R2 =m2

QPSVMs LPSVMs

100 100

200 200

16.2 0.8

0.5 0.5

7820.2 7820.2

Fig. 1. The results of arti2cial data obtained by LPSVMs. The real line is f(x) = 0, the dotted lines are f(x) = ±r.

which is not be con2rmed by the recognition errors in Table 2 because of the examples without noise. From Fig. 2 we can see that the generalization performance of LPSVMs is worse than that of QPSVMs. At the cost of generalization performance the training speed of LPSVMs is improved. Fortunately the loss in generalization performance is tolerable because the recognition errors is invisible. 3.3. The experiment on the handwritten digits data The experiment data is the MNIST database of 60,000 training and 10,000 testing handwritten digits from AT& T Research Labs 1 , which has been taken from the experiment data in Refs. [9 –11]. Since the database is large, we only had two-class examples belonging to the classes “6” and “9”, respectively, and normalized these examples. The kernel function is Gaussian kernel with p = 30. From the results shown in Table 3, we can conclude that the training time of QPSVMs increases exponentially as the increase of the number of examples, while that of LPSVMs increases linearly. Therefore, LPSVMs at least make an order of magnitude improvement in training speed. 3.4. Multiuser detection in DS-CDMA system Code division multiple access (or CDMA) is characterized by its soft capacity, dynamic sharing of channel 1

URL: www.research.all.com./∼vann/ocr/moist.

resources, high anti-jamming capability and others [12]. The introduction of Multiuser detection technique is to solve the multiple access interference problems (mainly caused by the nonorthogonality of the signature waveform, the asynchronization and the multipath propagation) in wireless communication, which improves the quality and the quantity of communication. Simultaneously, the high complex requirement of signal processing in CDMA systems leads to a wide attention in the 2eld of signal processing. Multiuser detection is a new direction in CDMA systems [13,14]. Many methods of signal processing have been proposed to solve multiuser detection. But from the view of the 2nal goal of multiuser detection, it can be taken as a pattern recognition problem. The goal of multiuser detection is to obtain the minimal bit-error-rate, so the optimal measure of detectors’ performance is the very principle of the minimum probability of error, not others such as minimum mean-square error, maximum signal-to-noise rate and so on. There exists close relationship or even equivalence between those signal processing principles and the principle of the minimum probability of error, but diFerence in many cases. At present, the methods for pattern recognition have received considerable attention in multiuser detection. Here, we take the multiuser detection problem as a fourth experiment. The baseband signal of multiuser detection in a synchronous DS-CDMA system can be expressed as x(t) =

K 

Ai bi (j)si (t − jT ) + ,n(t);

t ∈ [jT; jT + T ];

i=1

where T is the symbol interval, {bi (j) ∈ {−1; 1}} is the bit transmitted by the ith user, Ai is the received amplitude of the ith user, 12 A2i is referred to as the energy of the ith user, si (t); t ∈ [0; T ] is the deterministic signature waveform assigned to the ith user and n(t) is white Gaussian noise with unit power spectral density. It is assumed that si (t) is supported only on the interval [0; T ] and has unit energy and that {bi (j)} is a collection of independent equiprobable ±1 random variables. We sample the input signal at a rate of 1=Ts . If let Ts = T=N , where N is the spreading gain, then the sampling rate is equal to the chip rate. On the interval t ∈ [jT; jT + T ], we have a vector form x(j) =

K  i=1

Ai bi (j)si + ,n(j);

x(j); si ; n(j) ∈ RN ×1 :

2932

W. Zhou et al. / Pattern Recognition 35 (2002) 2927 – 2936

Table 2 The results of the dual-spiral data Learning model

No. of training examples

No. of testing examples

Training time (s)

Recognition error (%)

R2 =m2

QPSVMs LPSVMs

252 252

628 628

4103.5 199.7

0 0

192.7 679.1

Fig. 2. The result of the dual-spiral data obtained by LPSVMs is shown in (a) and QPSVMs in (b). The real lines are f(x) = 0 and the dotted lines are f(x) = ±r.

Table 3 The results of the handwritten digital data No. of training examples

No. of testing examples

LPSVMs

100 + 100

1009+95 8 1009 + 95 8 1009 + 95 8 1009 + 95 8 1009 + 95 8

200 + 200 300 + 300 400 + 400 500 + 500

QPSVMs Recognition error (%)

R2 =m2

117.0

1.4

175.4

187.0

1.0

47.3

369.3

1.2

311.9

2117.4

1.1

60.4

546.1

0.7

323.4

5978.1

1

73.2

823.3

1.0

355.8

18509.5

0.875

87.7

1076.0

0.8

402.0

100878.7

Training time (s)

The baseband signal of multiuser detection in an asynchronous DS-CDMA system can be expressed as x(t) =

K 

Training time (s)

t ∈ [jT; jT + T ];

i=1

where .i is a relative oFset, given .1 6 .2 6 · · · 6 .i 6 · · · 6 .K . Synchronizing the signal with the expected

0.7

R2 =m2

101.8

kth user and sampling at the chip rate, we get x(j) = Ak bk (j)sk +

Ai bi (j)si (t − jT − .i ) + ,n(t);

Recognition error (%)

K 

Ai bi (j)si + ,n(j);

i=1 i=k

x(j); sk ; n(j) ∈ RN ×1 ; where bi and si denote the equivalent bit stream and the signature waveform of the ith user, respectively. In general, an

4.02 0.93 0.15 0.02 0 13.9 10.3 10.4 62.1 65.0 22998.70 14552.81 11293.65 10354.11 9694.48 7.09 1.22 0.58 0.09 0.01 6.7 5.7 6.3 13.1 13.8 1919.42 1428.43 1025.14 952.64 866.61 2.83 0.45 0.04 0 0 10.0 12.9 10.9 11.8 14.0 2898.54 1872.21 1167.98 1035.83 933.21

Recognition error (%) Training time (s) Recognition error (%) Training time (s) Recognition error (%) Training time (s) R2 =m2

C = 10

Linear QPSVMs

R2 =m2

RBF LPSVMs

p1 = 406; C = 10; 000

R2 =m2

RBF QPSVMs

p1 = 406; C = 10; 000

R2 =m2

asynchronous user can be transformed into two synchronous users. Consider a DS-CDMA system. Signature waveform is Golden code with 31 bits. Let the power of the expected user be denoted by PEU . A relative power Prui is de2ned by the power ratio of the ith user to the expected user, namely Prui = PIUi =PEU where PIUi = 12 A2i is the power of the ith user and PEU = 12 A2k the expected user. Similarly Gaussian noise power is expressed as PN = NPrn PEU , where N is spreading gain and Prn is the relative power of noise. We performed synchronous and asynchronous multiuser detection by using SVM techniques. The results are shown in Tables 4 and 5. The baseband signal of multiuser detection was sampled to generate the examples. Approximately the examples have normal distribution with diFerent mean vectors and a common covariance matrix. According to Raudys [15], we randomly took the training examples N = 100 ≈ 3p, where p denotes the dimension of examples and the test ones 10,000 in each run. Table 4 shows the results of synchronous multiuser detection. The number of users is 10, the power of expected user is 1, the relative power of other users is Pru2 =· · ·=Pru5 =10(db) and Pru6 =· · ·=Pru10 =20(db) and the relative power of Gaussian noise is shown in Table 4. The results of asynchronous multiuser detection are given in Table 5. The number of asynchronous users is 6 and each of asynchronous users (including the expected one) has three propagation paths. Let the power of the expected user be 1. The relative power of other users is Pru2 = Pru3 = 10(db) and Pru4 = Pru5 = Pru6 = 20(db). The power of each path is identical for the same user. The relative power of Gaussian noise is indicated in Table 5. In this experiment, the recognition errors of training examples are identical for LPSVMs and QPSVMs. The parameters of RBF are obtained by using leave-one-out methods of QPSVMs [16], so they are optimal for QPSVMs. Experimental results support LPSVMs presented and witness the validity of LPSVMs. The bound of VC dimension in LPSVMs is loosened to some extent, which leads to the loss in generalization performance that is tolerable. Thus, LPSVMs have linear structure risk by relaxing the VC bound and improve the speed of training.

2933 9168.76 10356.89 9364.60 8285.64 8785.74

W. Zhou et al. / Pattern Recognition 35 (2002) 2927 – 2936

Training time (s)

3.9 3.8 3.5 3.4 3.1

Prn (dB)

−8 −10 −12 −14 −16

1.41 0.22 0.04 0.01 0

C = 10

Recognition error (%)

Linear LPSVMs

Gauss noise

Linear programming SVMs are proposed based on the statistical learning theory, in particular the theory of capacity control, VC dimension and structural risk. The bound of VC dimension in LPSVMs is loosened to some extent, which leads to the loss in generalization performance that is tolerable. Training LPSVMs is simpler than QPSVMs, especially for large-scale problems. LPSVMs at least make an order magnitude improvement in the training speed, so it is worth while losing some generalization performance. We note that the VC dimension of LPSVMs is larger than that of QPSVMs in Section 3.4, but the generalization error

Table 4 Synchronous multiuser detection

4. Conclusion and discussion

2.21 0.86 0.15 0 0 11.2 10.0 8.5 9.1 11.3 4.89 1.11 0.58 0.22 0 1536.42 941.44 654.44 599.53 582.80 18.35 16.92 16.77 16.77 16.77

3.8 3.7 4.0 3.6 3.6

20771.73 15857.43 21215.86 10166.39 9160.26

Recognition error (%) Training time (s) Recognition error (%) R2 =m2 Recognition error (%)

Training time (s)

R2 =m2

RBF QPSVMs p1 = 490; C = 10; 000

11.8 13.4 11.5 11.6 12.4 2423.21 1577.35 742.98 752.97 742.05 17.55 16.82 16.77 16.77 16.77 5.8 5.4 4.4 4.9 4.6 −8 −10 −12 −14 −16

Training time (s) Recognition error (%) Training time (s) Prn

R2 =m2

RBF LPSVMs p1 = 490; C = 10; 000 Linear LPSVMs C = 100

Linear QPSVMs C = 100

of LPSVMs is smaller than that of QPSVMs in linear case, which is not strange. As we know, SVMs de2ne a structure risk by the empirical risk and the VC dimension and give a bound to the expected risk. Although SVM algorithm can guarantee the structure risk converge to the expected risk with increasing number of examples. The structure risk is not the expected one exactly. Especially the bound of the expected risk is not very accuracy for the 2nite number of examples. It is possible that other learning machines get better generalization performance than SVMs, for example, Euclidean distance classi2er is the optimal one for Gaussian model [15]. Roughly we agree to the viewpoint in Ref. [17]: SVMs are the general and very eScient statistical learning model, but not the optimal. Priori information is helpful for us to select proper learning machine. In fact it is the problem concerned by statistical theory researchers that how to introduce the priori information into SVMs to obtain good generalization performance. Presently in QPSVMs many algorithms for large-scale problems have been developed, such as Chunking algorithm [18], Osuna algorithm [19] and SMO algorithm [20]. Further studies will aim to 2nd the algorithm for large-scale problems in LPSVMs. In addition the property (say geometry) of LPSVMs deserves further research.

Acknowledgements Thanks to all those who contributed to the data sets used in this paper. This work was supported in part by grants of the Nature Science fund (No. 69772029) and the National “863” project number 863-306-06-06-1.

Appendix A. Proof of Theorem 2.2

Gauss noise

Table 5 Asynchronous multiuser detection

16002.10 16209.39 18451.13 9293.04 8948.62

W. Zhou et al. / Pattern Recognition 35 (2002) 2927 – 2936

R2 =m2

2934

Proof. Given the examples set ((x1 ; y1 ); : : : ; (xi ; yi ); : : : ; (xl ; yl )); (x; y) ∈ (Rn ; R). The examples belong to a sphere of radius R. The set of m -margin separating hyperplanes f(x; w; b) = wT x + b classi2es examples x as follows:  1; wT x + b ¿ ;  ¿ 0; y= −1; wT x + b 6 − ; according to Eqs. (1.6) and (1.7); then the upper bounds on the VC dimension of the set of m -margin separating hyperplanes  2

R · ||w||22 h 6 min ; n + 1: (A.1) 2 In terms of Lemma 2.1; there exist 0 ¡ c ¡ + ∞ with no dependence with the vector w such that ||w||2 6 c||w||&

(A.2)

W. Zhou et al. / Pattern Recognition 35 (2002) 2927 – 2936

holds true. Where ||w||& is any vector norm. Hence; we have the upper bounds on the VC dimension 



R2 · ||w||22 ;n + 1 2   c2 · R2 · ||w||2& 6 min ; n + 1: 2

h 6 min

De/nition 2.3 (Weight-norm [6]). Let A be any nth positive de2nite matrix and x ∈ Rn be row vectors. Then a function ||x||A = (xT Ax)1=2 is a kind of vector norm called weight-norm; or ellipse-norm. By the de2nition of weight-norm, Eq. (5:7) is a weight-norm. We have

Appendix B. Proof of Theorem 2.3 Proof. Given the examples set ((((x1 ); y1 ); : : : ; (((xi ); yi ); : : : ; (((xl ); yl )); (((x); y) ∈ (H; R). The examples belong to a sphere of radius R. The set of the target functions l 

l 

i yi K(xi ; x) + b

(B.1)

i=1

classi2es examples x as follows:  y=

1;

||w||22 = T K = ||a||2K :

f(x) ¿ ;

−1; f(x + b) 6 − ;

 ¿ 0:

Thus, Theorem is proved.

f(x) = w · ((x) + b;

References

where w=

l 

i yi ((xi ):

(B.3)

i=1

In H ; according to Eq. (5:5) we have ||w||22 = w · w =

l  l 

i j yi yj ((xi ) · ((xj )

i=1 j=1

=

l  l 

i j yi yj K(xi ; xj ):

(B.4)

i=1 j=1

Let K denote a l × l matrix K(i; j) = yi yj K(xi ; xj ) and = ( 1 ; : : : ; l )T . Then Eq. (5:6) can be rewritten as ||w||22 = aT Ka:

(B.5)

(B.8)

holds true. Where || ||& is any vector norm. Combining Eqs. (5:8), (5:9) and (5:10), we have the bounds on the VC dimension:  2 T

R · K h 6 min ;n + 1 2

 2 R · || ||2K ;n + 1 = min 2   c2 · R2 · || ||2& ; n + 1: 6 min 2

The set of the target functions is identical to a hyperplane in the space H : (B.2)

(B.7)

According to Lemma 2.1, there exits a constant 0 ¡ c ¡+∞ without depending on and K such that || ||K 6 c|| ||&

i yi ((xi ) · ((x) + b

i=1

=

(B.6)

In the following we introduce the concept of weight-norm.

Thus Theorem 2.2 is proved.

f(x) =

In terms of Eqs. (1.6) and (1.7); the bounds is  2

R · ||w||22 h 6 min ;n + 1 2  2 T

R · K ; n + 1: = min 2

2935

[1] V. Vapnik, Statistical Learning Theory, Wiley-Interscience Publication, New York, 1998. [2] V. Vapnik, The Nature of Statistical Learning Theory, Springer, NY, 1995. [3] V. Vapnik, An overview of statistical learning theory, IEEE Transac. Neural Networks 10 (5) (1999) 988–999. [4] C.J.C. Burges, A tutorial on support vector machines for pattern recognition, Data Min. Knowledge Discovery 2 (1998) 121–167. [5] A.J. Smola, B. SchVolkopf, A tutorial on support vector regression, NeuroCOLT Technical Report NC-TR-98-030, Royal Holloway College, University of London, UK, 1998. [6] W.P. Cheng, K.Y. Zhang, Z. Xu et al. (Eds.), Matrix Theory. Xi’an: North-West Industry University Press, Xi’an, China, 1989. [7] G. Wahba, An introduction to model building with reproducing kernel hilbert spaces, Technical Report 1020, University of Wisconsin-Madison, Statistics Dept. 2000. [8] K.J. Lang, M.J. Witbrock, Learning to tell two spirals apart, Proceedings of the 1989 Connectionist Models Summer School, 1989, pp. 52– 61.

2936

W. Zhou et al. / Pattern Recognition 35 (2002) 2927 – 2936

[9] B. SchVolkopf, C. Burges, V. Vapnik, Extracting support data for a given task, in: M. Fayyad, R. Uthurusamy (Eds.), Proceedings, First International Conference on Knowledge Discovery & Data Mining, Menlo Park, AAAI Press, http://www.kernel-machines.org/ 1995. [10] B. SchVolkopf, C. Burges, V. Vapnik, Incorporating invariances in support vector learning machines, in: C. von der Malsburg, W. von Seelen, J.C. Vorbrggen, B. SendhoF (Eds.), Arti2cial Neural Networks — ICANN’96, Berlin, Lecture Notes in Computer Science, Vol. 1112, Springer, Berlin, 1996, pp. 47–52. [11] C.J.C. Burges, B. SchVolkopf, Improving the accuracy and speed of support vector learning machines, in: M. Mozer, M. Jordan, T. Petsche (Eds.), Advances in Neural Information Processing Systems 9, MIT Press, Cambridge, MA, 1997, pp. 375 –381. [12] S. Verdu, Multiuser Detection, Cambridge University Press, Cambridge, 1996. [13] U. Madhow, Blind adaptive interference suppression for timing acquisition and demodulation in direct-sequence CDMA systems, IEEE Trans. Commun. 46 (1998) 1065–1075.

[14] X. Wang, H.V. Poor, Blind multiuser detection: a subspace approach, IEEE Trans. Inform. Theory 44 (1998) 677–691. [15] S. Raudys, Evolution and generalization of a size neurone, II. Complexity of statistical classi2ers and sample size consideration, Neural Networks 11 (1998) 297–313. [16] T. Joachims. Estimating the generalization performance of a SVM eSciently, LS VIII-Report 25, UniversitVat Dortmund, Germany. Available in URL: (www.kernel-machine.com/.) [17] S. Raudys, How good are support vector machines, Neural Networks 13 (2000) 17–19. [18] V. Vapnik, Estimation of Dependencies Based on Empirical Data, Nauka, Moscow, 1979 (in Russian) (English translation: Springer, New York, 1982). [19] E. Osuna, R. Freund, G. Girosi, Improved training algorithm for support vector machines, Proceedings of the IEEE NNSP’97, Amelia Island, 1997. [20] J. Platt, Fast training of support vector machines using sequential minimal optimization, in: B. SchVolkopf, C.J.C. Burges, A.J. Smola (Eds.), Advances in Kernel Methods — Support Vector Learning, MIT Press, Cambridge, MA, 1999, pp. 185 –208.

About the Author—WEIDA ZHOU received his B.S. in Engineering from Xidian University, Xi’an, China, in 1996. Since 1998 he has been working towards the M.S. degree and the Ph.D. degree at Xidian University. His research interests include machine learning, learning theory and data mining. About the Author—LI ZHANG received her B.S. degree in Electronic Engineering from Xidian University, Xi’an, China. Since 1997 she has been working towards the M.S. degree and the Ph.D. degree at Xidian University. Her research interests have been in the areas of pattern recognition, machine learning and data mining. About the Author—LICHENG JIAO received his B.S. from Shanghai Jiaotong University, Shanghai, China, in 1982, the M.S. degree and Ph.D. degree from Xi’an Jiaotong University, Xi’an, China, in 1984 and 1990, respectively. He is currently Professor and Subdecanal of Graduate School. His research interests include neural network, data mining, nonlinear intelligence signal processing and communication.