Support vector machine and its bias correction in high-dimension, low-sample-size settings
Yugo Nakayama Kazuyoshi Yata Makoto Aoshima












label1]Yugo Nakayama
[label1]Graduate School of Pure and Applied Sciences, University of Tsukuba, Ibaraki, Japan

label2]Kazuyoshi Yata
[label2]Institute of Mathematics, University of Tsukuba, Ibaraki, Japan

label2]Makoto Aoshimalabel3

[label3]Institute of Mathematics, University of Tsukuba, Ibaraki 305-8571, Japan; Fax: +81-29-853-6501
aoshima@math.tsukuba.ac.jp



In this paper, we consider asymptotic properties of the support vector machine (SVM) in high-dimension, low-sample-size (HDLSS) settings. 
We show that the hard-margin linear SVM holds a consistency property in which misclassification rates tend to zero as the dimension goes to infinity under certain severe conditions. 
We show that the SVM is very biased in HDLSS settings and its performance is affected by the bias directly. 
In order to overcome such difficulties, we propose a bias-corrected SVM (BC-SVM). 
We show that the BC-SVM gives preferable performances in HDLSS settings. 
We also discuss the SVMs in multiclass HDLSS settings.
Finally, we check the performance of the classifiers in actual data analyses.



Distance-based classifier HDLSS Imbalanced data Large p small n Multiclass classification

primary 62H30 secondary 62G20 










§ INTRODUCTION


High-dimension, low-sample-size (HDLSS) data situations occur in many areas of modern science such as genetic microarrays, medical imaging, text recognition, finance, chemometrics, and so on. 
Suppose we have independent and d-variate two populations, π_i, i=1,2, having an unknown mean vector _i and unknown covariance matrix _i (≥). 
We assume that (_i)/d ∈ (0,∞) as d→∞ for i=1,2. 
Here, for a function, f(·), “f(d) ∈ (0, ∞) as d→∞" implies lim inf_d→∞f(d)>0 and lim sup_d→∞f(d)<∞. 
Let Δ=_1-_2^2, where · denotes the Euclidean norm. 
We assume that lim sup_d→∞Δ/d<∞. 
We have independent and identically distributed (i.i.d.) observations, _i1,...,_in_i, from each π_i.
We assume n_i≥ 2, i=1,2. 
Let _0 be an observation vector of an individual belonging to one of the two populations.

We assume _0 and _ijs are independent.
Let N=n_1+n_2. 

In the HDLSS context, <cit.>, <cit.> and <cit.> considered distance weighted classifiers.
<cit.>, <cit.> and <cit.> considered distance-based classifiers.
In particular, <cit.> gave the misclassification rate adjusted classifier for multiclass, high-dimensional data in which misclassification rates are no more than specified thresholds. 
On the other hand, <cit.> considered geometric classifiers based on a geometric representation of HDLSS data. 
<cit.> considered a classifier based on the maximal data piling direction. 
<cit.> considered quadratic classifiers in general and discussed asymptotic properties and optimality of the classifies under high-dimension, non-sparse settings. 
In particular, <cit.> showed that the misclassification rates tend to 0 as d increases, i.e., 

    e(i)→ 0

under the non-sparsity such as Δ→∞ as d→∞, where e(i) denotes the error rate of misclassifying an individual from π_i into the other class. 
We call (<ref>) “the consistency property".
We note that a linear classifier can give such a preferable performance under the non-sparsity. 
Also, such non-sparse situations often appear in real high-dimensional data. 
See <cit.> for the details. 
Hence, in this paper, we focus on linear classifiers.

In the field of machine learning, there are many studies about the classification in the context of supervised learning. 
A typical method is the support vector machine (SVM). 
The SVM has versatility and effectiveness both for low-dimensional and high-dimensional data. 
See <cit.>, <cit.>, <cit.>, <cit.> and <cit.> for the details. 
Even though the SVM is quite popular, its asymptotic properties seem to have not been studied sufficiently.
In this paper, we investigate asymptotic properties of the SVM for HDLSS data. 

Now, let us use the following toy examples to see the performance of the hard-margin linear SVM given by (<ref>). 
We set N=20 and d=2^s, s=5,...,11. 
Independent pseudo random observations were generated from π_i: N_d(_i, _i), i=1,2.
We set _1= and _2=(1/3,...,1/3)^T, so that Δ=d/9. 
We considered three cases: 


(a) (n_1,n_2)=(10,10) and _1=_2=_d; 

(b) (n_1,n_2)=(6,14) and _1=_2=_d; and 

(c) (n_1,n_2)=(10,10), _1=0.6_d and _2=1.4_d,


where _d denotes the d-dimensional identity matrix.
Note that Δ>|(_1)/n_1-(_2)/n_2| for (a) to (c).
Then, from Theorem 1 in <cit.>, the classifier should hold (<ref>) for (a) to (c). 

We repeated 2000 times to confirm if the classifier does (or does not) classify _0∈π_i correctly and defined P_ir=0 ( 1) accordingly for each π_i (i=1,2).
We calculated the error rates, e(i)= ∑_r=1^2000P_ir/2000, i=1,2. 
Also, we calculated the average error rate, e={e(1)+e(2)}/2. 


Their standard deviations are less than 0.0112 from the fact that {e(i)}=e(i){1-e(i)}/2000≤ 1/8000.

In Figure <ref>, we plotted e(1), e(2) and e for (a) to (c).
We observe that the SVM gives a good performance as d increases for (a). 
Contrary to expectations, it leads undesirable performances both for (b) and (c). 
The error rates becomes small as d increases, however, e(1) and e(2) are quite unbalanced. 
We discuss some theoretical reasons in Section 2.2. 




In this paper, we investigate the SVM in the HDLSS context.
In Section 2, we show that the SVM holds (<ref>) under certain severe conditions. 
We show that the SVM is very biased in HDLSS settings and its performance is affected by the bias directly. 
In order to overcome such difficulties, we propose a bias-corrected SVM (BC-SVM) in Section 3.
We show that the BC-SVM improves the SVM even when n_is or _is are unbalanced as in (b) or (c) in Figure 1. 
In Section 4, we check the performance of the BC-SVM by numerical simulations and use the BC-SVM in actual data analyses.
In Section 5, we discuss multiclass SVMs in HDLSS settings. 



§ SVM IN HDLSS SETTINGS


In this section, we give asymptotic properties of the SVM in HDLSS settings.
Since HDLSS data are linearly separable by a hyperplane, we consider the hard-margin linear SVM. 



 §.§ Hard-margin linear SVM


We consider the following linear classifier:

    y()=^T+b,

where  is a weight vector and b is an intercept term. 
Let us write that (_1,...,_N)=(_11,...,_1n_1,_21,...,_2n_2).
Let t_j=-1 for j=1,...,n_1 and t_j=1 for j=n_1+1,...,N. 
The hard-margin SVM is defined by maximizing the smallest distance of all observations to the separating hyperplane.
The optimization problem of the SVM can be written as follows:

    _,b1/2^2

A Lagrangian formulation is given by 

    L(,b;)=1/2|| ||^2-∑_j=1^Nα_j{t_j(^T_j+b)-1},

where =(α_1,...,α_N)^T and α_js are Lagrange multipliers. 
By differentiating the Lagrangian formulation with respect to  and b, we obtain the following conditions: 

    =∑_j=1^Nα_jt_j _j   ∑_j=1^Nα_jt_j=0.

After substituting them into L(,b;), we obtain the dual form: 

    L()=∑_j=1^Nα_j-1/2∑_j=1^N∑_k=1^Nα_jα_kt_jt_k _j^T_k.

The optimization problem can be transformed into the following:

    _ L()

subject to 

    α_j≥ 0, j=1,...,N,   ∑_j=1^Nα_jt_j=0.

Let us write that 

    =(α̂_1,...,α̂_N)^T=_L() .

There exist some _js satisfying that t_jy(_j)=1 (i.e., α̂_j≠ 0).
Such _js are called the support vector.
Let Ŝ={j|α̂_j≠ 0, j=1,...,N} and N_Ŝ=#Ŝ, where # A denotes the number of elements in a set A.
The intercept term is given by

    b̂=1/N_Ŝ∑_j∈Ŝ(t_j-∑_k∈Ŝα̂_kt_k_j^T_k).

Then, the linear classifier in (<ref>) is defined by

    ŷ()=∑_k∈Ŝα̂_k t_k _k^T+b̂.

Finally, in the SVM, one classifies _0 into π_1 if ŷ(_0 )<0 and into π_2 otherwise. 
See <cit.> for the details.



 §.§ Asymptotic properties of the SVM in the HDLSS context


In this section, we consider the case when d→∞ while N is fixed. 
We assume the following assumptions: 

  
  (A-i)  (_ik-_i^2)/Δ^2→ 0 as d→∞ for i=1,2; 
  
  (A-ii)  (_i^2)/Δ^2→ 0 as d→∞ for i=1,2.

Note that (_ik-_i^2)=2(_i^2) when π_i is Gaussian, so that (A-i) and (A-ii) are equivalent when π_is are Gaussian.


Under (<ref>), it holds that as d→∞

    L()=∑_j=1^Nα_j- Δ/8(∑_j=1^Nα_j)^2{1+o_p(1)}
    -1/2((_1)∑_j=1^n_1α_j^2+
    (_2)∑_j=n_1+1^Nα_j^2).



Let δ=(_1)/n_1+(_2)/n_2 and Δ_*=Δ+δ. 
Under the constraint that ∑_j=1^Nα_j=C for a given positive constant C, we can claim that  

    max_{-1/2( (_1)∑_j=1^n_1α_j^2+(_2)∑_j=n_1+1^Nα_j^2)}
    =-C^2/8δ

when α_1=⋯ =α_n_1=C/(2n_1) and α_n_1+1=⋯ =α_N=C/(2n_2) under (<ref>). 
Then, by noting that lim inf_d→∞{(_i)/(Δ n_i)} >0 for i=1,2, 
from Lemma 1 it holds that 

    max_ L()= -Δ_*/8(C-4+o_p(1)/Δ_*)^2{1+o_p(1)}+2+o_p(1)/Δ_*

for given C(>0).
Hence, by choosing C≈ 4/Δ_*, we have the maximum of L() asymptotically. 


It holds that as d→∞

    α̂_j=2/Δ_*n_1{1+o_p(1)}  ;  
       α̂_j=2/Δ_*n_2{1+o_p(1)}  .
 
Furthermore, it holds that as d→∞

    ŷ(_0)=(-1)^iΔ/Δ_*+(_1)/n_1-(_2)/n_2/Δ_*+o_p(Δ/Δ_*)
 



From Lemma 2, all the data points are the support vectors under (A-i) and (A-ii) in the HDLSS context. 
<cit.> called this phenomenon the “data piling". 
See Sections 1 and 2 in <cit.> for the details. 


Let κ =(_1)/n_1-(_2)/n_2. 
From Lemma 2, it holds that as d→∞

    Δ_*/Δŷ(_0)=(-1)^i+κ/Δ+o_p(1)

when _0∈π_i, i=1,2. 
Hence, “κ /Δ" is the bias term of the (normalized) SVM. 
We consider the following assumption: 

  
  (A-iii)  lim sup_d→∞|κ|/Δ<1.



Under (A-i) to (A-iii), the SVM holds (<ref>). 



Under (A-i) and (A-ii), the SVM holds the following properties:

    e(1)→ 1   e(2)→ 0  lim inf_d→∞κ/Δ>1;
      
       e(1)→ 0   e(2)→ 1  lim sup_d→∞κ/Δ<-1.




For the SVM, <cit.> and <cit.> also showed (<ref>) and the results in Corollary 1 under different conditions. 
We emphasize that (A-i), (A-ii) and (A-iii) are milder than their conditions. 
Moreover, we can evaluate the bias of the SVM by using (<ref>). 


We expect from (<ref>) that, for sufficiently large d, e(1) and e(2) for the SVM become small and e(1) (or e(2)) is larger than e(2) (or e(1)) if κ/Δ>0 (or κ/Δ<0). 
Actually, in Figure 1, we observe that e(1) is larger than e(2) for (b) in which κ/Δ=6/7 and e(2) is larger than e(1) for (c) in which κ/Δ=-18/25. 
As for (a) in which κ =0, the SVM gives a preferable performance. 



 §.§ Asymptotic properties of the SVM when both d and N tend to infinity



In this section, we give asymptotic properties of the SVM when both d,N →∞ while N/d→ 0.
One may consider N=O(log d) for example. 
We assume the following assumptions: 

  
  (A-i')  N (_ik-_i^2)/Δ^2→ 0 as d,N→∞ for i=1,2; 
  
  (A-ii')  N^2 (_i^2)/Δ^2→ 0 as d,N→∞ for i=1,2;
   
  (A-iv)  lim inf_d,N→∞(_i)/Δ n_i> 0 for i=1,2.

Note that Δ^2/(_i^2)=O(d) from the facts that lim sup_d→∞Δ/d<∞ 
and (_i)/d∈ (0,∞) as d→∞ for i=1,2. 
Thus, N=o(d^1/2) when (A-ii') is met. 


Under (A-i'), (A-ii') and (A-iv), it holds that as d,N→∞

    ŷ(_0)=(-1)^iΔ/Δ_*+κ/Δ_*+o_p(Δ/Δ_*)




Under (A-i'), (A-ii') and (A-iv), the SVM holds the following properties:

    e(1)→ 0   e(2)→ 0  lim sup_d,N→∞|κ|/Δ<1;
      
       e(1)→ 1   e(2)→ 0  lim inf_d,N→∞κ/Δ>1;
      
       e(1)→ 0   e(2)→ 1  lim sup_d,N→∞κ/Δ<-1.






§ BIAS-CORRECTED SVM


As discussed in Section 2.2, if lim inf_d→∞|κ|/Δ>0, the SVM gives an undesirable performance. 
From Corollary 1, if lim inf_d→∞|κ|/Δ>1, one should not use the SVM. 
In order to overcome such difficulties, we consider a bias correction of the SVM.  

We estimate _i and _i by _in_i=∑_j=1^n_i_ij/n_i and _in_i=∑_j=1^n_i(_ij-_in_i)(_ij-_in_i)^T/(n_i-1).  
We estimate Δ_* by Δ̂_*=_1n_1-_2n_2^2.
Note that E(Δ̂_*)=Δ_*. 
Let κ̂=(_1n_1)/n_1-(_2n_2)/n_2. 
Note that E(κ̂)=κ. 
First, we consider the case when d→∞ while N is fixed. 


Under (A-i) and (A-ii), it holds that as d→∞ 

    κ̂/Δ̂_*=
    κ/Δ_*+o_p(Δ/Δ_*).



Now, we define the bias-corrected SVM (BC-SVM) by

    ŷ_BC(_0)=ŷ(_0)-κ̂/Δ̂_*,

where ŷ(_0) is given by (<ref>).
In the BC-SVM, one classifies _0 into π_1 if ŷ_BC(_0)<0 and into π_2 otherwise. 

By combining (<ref>) with Lemma 4, under (A-i) and (A-ii), it holds that as d→∞

    Δ_*/Δŷ_BC(_0)=(-1)^i+o_p(1)

when _0∈π_i, i=1,2. 


Under (A-i) and (A-ii), the BC-SVM holds (<ref>). 



One should note that the BC-SVM has the consistency property without (A-iii). 
<cit.> considered a different bias correction for the SVM. 
They showed the consistency property under some stricter conditions than (A-i) and (A-ii). 



<cit.> considered the distance-based classifier as follows: 
One classifies an individual into π_1 if y_AY(_0)<0 and into π_2 otherwise, 
where y_AY(_0)={_0-(_1n_1+_2n_2)/2}^T(_2n_2-_1n_1)-(_1n_1)/(2n_1)+(_2n_2)/(2n_2). 
Then, from Theorem 1 in <cit.>, 
under (A-ii), it holds that as d→∞

    (2/Δ)y_AY(_0)=(-1)^i+o_p(1)

when _0∈π_i, i=1,2. 



When both d,N →∞, we have the following result. 


Under (A-i'), (A-ii') and (A-iv), it holds for the BC-SVM that e(i)→ 0 as d,N→∞ for i=1,2. 





§ PERFORMANCES OF BIAS-CORRECTED SVM


In this section, we check the performance of the BC-SVM both in numerical simulations and actual data analyses. 



 §.§ Simulations



First, we checked the performance of the BC-SVM by using the toy examples in Figure 1. 
Similar to Section 1, we calculated the error rates, e(1), e(2) and e, by 2000 replications and plotted the results in Figure 2. 
We laid e(1), e(2) and e for the SVM by borrowing from Figure 1. 
As expected theoretically, we observe that the BC-SVM gives preferable performances even for (b) and (c) in which lim inf_d→∞|κ|/Δ>0. 


Next, we compared the performance of the BC-SVM with the SVM in complex settings. 
We set _1=, 
_1=( 0.3^|i-j|^1/3) and _2=( 0.4^|i-j|^1/3), where

    =[{0.5+1/(d+1)}^1/2,...,{0.5+d/(d+1)}^1/2].

Note that (_1)=(_2)=d. 

We considered two cases: 


_2=(1,...,1,0,...,0,-1,...,-1)^T (=_α(t), ) whose first t/2 elements are 1 and last t/2 elements are -1 for a positive even number t; and 

_2=(t^1/2/2,t^1/2/2,0,...,0,-t^1/2/2,-t^1/2/2)^T (=_β(t), ) whose 
first two elements are t^1/2/2 and last two elements are -t^1/2/2 for a positive number t. 


Note that Δ=t both for _α(t) and _β(t).
We generated _ij-_i, i=1,2; j=1,2,..., independently either from (I) N_d(,_i), i=1,2, or (II) a d-variate t-distribution, t_d(_i,10), i=1,2, with mean zero, covariance matrix _i and degrees of freedom 10. 
Note that (A-i) holds under (A-ii) for (I). 
Let d_*=2⌈ d^2/3/2 ⌉, where ⌈ x ⌉ denotes the smallest integer ≥ x.

We considered four cases: 


(d) _2=_α(d_*), (n_1,n_2)=(5,25) and d=2^s, s=6,...,12, for (I);  

(e) _2=_α(d_*), d=1000 and (n_1,n_2)=(4s,8s), s=1,...,7, for (II); 
 
(f) d=1000, (n_1,n_2)=(10,20) and _2=_α(2^s), s=1,...,7, for (II); and 
 
(g) d=1000, (n_1,n_2)=(10,20) and _2=_β(2^s), s=1,...,7, for (II). 
 


Note that Δ=d_*=o(d) and (A-ii) holds for (d) and (e) from the fact that (_i^2)=O(d), i=1,2. 
Also, note that  (A-i) holds for (d). 
However, (A-i) does not hold for (e) and (A-iii) does not hold both for (d) and (e). 
For (f) and (g), we note that Δ=2^s, s=1,...,7.
 
Especially, (g) is a sparse case such that the only four elements of _1-_2 are nonzero.

Similar to Section 1, we calculated the error rates, e(1), e(2) and e, by 2000 replications and plotted the results in Figure 3.




We observe that the SVM gives quite bad performances for (d) in Figure 3. 
The main reason must be due to the bias term in the SVM. 
Note that κ/Δ→∞ as d→∞ for (d). 
Thus e(1) becomes close to 1 as d increases. 
See Corollary 1 for the details. 
Also, the SVM gives bad performances for (e) to (g) when n_is are small or Δ is small. 
This is because κ/Δ becomes large when n_is are small or Δ is small. 
On the other hand, from Figures 2 and 3, the BC-SVM gives adequate performances 
even when n_is and _is are unbalanced.  
The BC-SVM also gives a better performance than the SVM even when Δ is small (or sparse).




 §.§ Examples: Microarray data sets


First, we used colon cancer data with 2000 (=d) genes given by <cit.> which consists of π_1: colon tumor (40 samples) and π_2: normal colon (22 samples).
We set n_1=n_2=10. 
We randomly split the data sets from (π_1,π_2) into training data sets of sizes (n_1,n_2) and test data sets of sizes (40-n_1,22-n_2). 

We constructed the BC-SVM and the SVM by using the training data sets. 
We checked accuracy by using the test data set for each π_i and denoted the misclassification rates by e(1)_r and e(2)_r. 
We repeated this procedure 100 times and obtained e(1)_r and e(2)_r, r=1,...,100, both for the BC-SVM and the SVM. 
We had the average misclassification rates as 
e(1) (=∑_r=1^100e(1)_r/100)=0.16, e(2) (=∑_r=1^100e(2)_r/100)=0.166 
and e (={e(1)+e(2) }/2)=0.163 for the BC-SVM,
and e(1)=0.158, e(2)=0.161 and e=0.159 for the SVM. 

By using all the samples, we considered estimating κ/Δ. 
We set m_1=40 and m_2=22. 
From Section 3.1 in <cit.>, an unbiased estimator of Δ was given by Δ̂_(m)=_1m_1-_2m_2^2-(_1m_1)/m_1-(_2m_2)/m_2. 
We estimated κ/Δ by 

    κ/Δ={(_1m_1)/n_1-(_2m_2)/n_2}/Δ̂_(m)

and had κ/Δ=0.003 for the 62 samples.
In view of (<ref>), we expect that the BC-SVM is asymptotically equivalent to the SVM in such cases. 
We estimated ((_1)/Δ,(_2)/Δ) by 
((_1m_1)/Δ̂_(m),(_2m_2)/Δ̂_(m))=(3.99,3.959).
It is difficult to estimate the standard deviation of the average misclassification rate. 
However, by noting that {e(i)}^1/2< {e(i)_r}^1/2=[e(i){1-e(i)}/(m_i-n_i)]^1/2,   
one may have an upper bound of the standard deviation for e(i) as 

    s_u(i)=[e(i){1-e(i)}/(m_i-n_i)]^1/2,

so that {∑_i=1^2s_u(i)^2/2 }^1/2 (=s_u, ) for e. 
For the BC-SVM, s_u(1)=0.067, s_u(2)=0.107 and s_u=0.089.

We summarized the results for various n_is in Table 1. 




Next, we used leukemia data with 7129 (=d) genes given by <cit.> which consists of π_1: ALL (47 (=m_1) samples) and π_2: AML (25 (=m_2) samples). 
We applied the BC-SVM and the SVM to the leukemia data and summarized the results in Table 2. 
When n_1 ≠ n_2, |κ/Δ| becomes large since
((_1m_1)/Δ̂_(m),(_2m_2)/Δ̂_(m))=(2.693,2.785).
As expected theoretically, we observe that the BC-SVM gives adequate performances compared to the SVM when |κ/Δ| is not small. 



Finally, we used myeloma data with 12625 (=d) genes given by <cit.> which consists of π_1: patients without bone lesions (36 (=m_1) samples) and π_2: patients with bone lesions (137 (=m_2) samples). 
We applied the BC-SVM and the SVM to the myeloma data and summarized the results in Table 3. 
When n_1 and n_2 are unbalanced, the SVM gives a very bad performance. 
This is because Δ in such cases is not sufficiently large since 
((_1)/Δ,(_2)/Δ)≈ ((_1m_1)/Δ̂_(m),(_2m_2)/Δ̂_(m))=(33.69,33.53), so that κ/Δ becomes too large when n_1 ≠ n_2. 
Especially when κ/Δ>1, e(1) of the SVM is too large. 
See Corollary 1 for the details. 
The BC-SVM also does not give a low error rate for this data because Δ is not sufficiently large. 
However, the BC-SVM gives adequate performances compared to the SVM especially when κ/Δ>1.

Throughout Sections 3 and 4, we recommend to use the BC-SVM rather than the SVM for high-dimensional data.







§ MULTICLASS SVMS


In this section, we consider multiclass SVMs in HDLSS settings. 
We have i.i.d. observations, _i1,...,_in_i, from each π_i (i=1,...,g), where g ≥ 3 and π_i has a d-dimensional distribution with an unknown mean vector _i and unknown covariance matrix _i (≥). 
We assume n_i≥ 2, i=1,...,g. 
Let Δ_ij=_i-_j^2 for i,j=1,...,g; i≠ j.
We assume that (_i)/d ∈ (0,∞) as d→∞ for i=1,...,g, 
and lim sup_d→∞Δ_ij/d<∞ for i,j=1,...,g; i≠ j. 
We consider the one-versus-one approach (the max-wins rule). 
See <cit.> and <cit.> for the details. 
Let N_g=∑_i=1^gn_i. 
First, we consider the case when d→∞ while N_g is fixed. 
We consider the following assumptions: 

  
  (B-i)  max_l=i,j(_lk-_l^2) /Δ_ij^2→ 0 as d→∞ for i,j=1,...,g; i≠ j;    
  
  (B-ii)  max_l=i,j(_l^2)/Δ_ij^2→ 0 as d→∞ for i,j=1,...,g; i≠ j.

Let κ_ij =(_i)/n_i-(_j)/n_j for i,j=1,...,g; i≠ j. 
We consider the following condition: 

  
  (B-iii)  lim sup_d→∞|κ_ij|/Δ_ij<1 
  for i,j=1,...,g; i≠ j.

From Theorem 1, for the one-versus-one approach by (<ref>), we have the following result. 


Under (B-i) to (B-iii), it holds for the multiclass SVM that 

    e(i)→ 0   .



From Theorem 2, for the one-versus-one approach by (<ref>), we have the following result. 


Under (B-i) and (B-ii), the multiclass BC-SVM holds (<ref>). 


Note that the BC-SVM satisfies the consistency property without (B-iii). 
Thus we recommend to use the BC-SVM in multiclass HDLSS settings. 

Next, we consider the case when both d,N_g→∞ while N_g/d→ 0. 
Similar to Section 2.3 and Corollary 3, 
the multiclass SVMs have the consistency property 
under some regularity conditions. 


We checked the performance of the multiclass SVMs by using leukemia data with 12582 (=d) genes given by 
<cit.> which consists of π_1: ALL (24 (=m_1) samples), 
π_2: MLL (20 (=m_2) samples) and 
π_3: AML (28 (=m_3) samples). 
We applied the multiclass BC-SVM and SVM to the leukemia and summarized the results in Table 4.
We had ((_1m_1)/Δ̂_12(m), (_2m_2)/Δ̂_12(m))=(2.724, 3.213), 
((_1m_1)/Δ̂_13(m),(_3m_3)/Δ̂_13(m))=(0.738,0.9) 
and ((_2m_2)/Δ̂_23(m),(_3m_3)/Δ̂_23(m))=(1.533,1.585), 
where Δ̂_ij(m)=_im_i-_jm_j^2-(_im_i)/m_i-(_jm_j)/m_j that is an unbiased estimator of Δ_ij. 
Thus |κ_ij/Δ_ij| must become large when n_i≠ n_j. 
Actually, the multiclass BC-SVM gives adequate performances for all the cases.








§ 


Throughout, let =_1-_2 and _*=(_1+_2)/2.

 
Under (A-ii), we have that as d→∞

    ^T_i/Δ^2 ≤(_i^2)^1/2/Δ=o(1),   i=1,2.

Then, by using Chebyshev's inequality, for any τ>0, under (A-ii), we have that 

    P(|(_j-_*)^T(_k-_*)-Δ/4 |≥τΔ )
       ≤ (τΔ)^-2E[{(_j-_*)^T(_k-_*)-Δ/4 }^2] 
       =O{(_1^2)+^T_1}/Δ^2=o(1)  ; 
       P(|(_j-_*)^T(_k-_*)-Δ/4 |≥τΔ ) 
       =O{(_2^2)+^T_2}/Δ^2=o(1)  ;  
       P(|(_j-_*)^T(_k-_*)+Δ/4 |≥τΔ )
       =O{(_1_2)+^T(_1+_2)}/Δ^2=o(1)

from the fact that (_1_2)≤{(_1^2)(_2^2)}^1/2.
From (<ref>), for any τ>0, we have that 

    P(| _j-_*^2-Δ/4-(_1) |≥τΔ )
       =O{(_1j-_1^2) +^T_1}/Δ^2=o(1)   ;    and
       P(|_j-_*^2-Δ/4-(_2) |≥τΔ )=o(1)

under (A-i) and (A-ii).
Here, subject to (<ref>), we can write for (<ref>) that

    L()=∑_j=1^Nα_j-1/2∑_j=1^N∑_k=1^Nα_jα_kt_jt_k (_j-_*)^T(_k-_*).

Then, by noting that α_j≥ 0 for all j subject to (<ref>), from (<ref>) and (<ref>), we have that 

    L()=   ∑_j=1^N α_j- Δ/8(∑_j=1^N α_j)^2-
    1/2((_1)∑_j=1^n_1α_j^2+
    (_2)∑_j=n_1+1^Nα_j^2)
       +o_p{Δ(∑_j=1^N α_j)^2  }

subject to (<ref>) under (A-i) and (A-ii).
It concludes the result.


 

By combining Lemma 1 with (<ref>) and (<ref>), we can claim the first result.

When Ŝ={1,...,N}, by noting that ∑_j=1^Nα̂_jt_j=0, we have that 

    ŷ(_0)=   ∑_j=1^N α̂_jt_j (_j-_*)^T(_0-_*)+∑_j=1^N α̂_jt_j (_j-_*)^T_*+b̂
    
    =   ∑_j=1^N α̂_jt_j (_j-_*)^T(_0-_*)
       +
    -n_1+n_2/N-1/N∑_j=1^N∑_k=1^N α̂_kt_k(_j-_*)^T(_k-_*).

From the first result of Lemma 2, (<ref>) and (<ref>), we have that as d→∞

    -n_1+n_2/N-1/N∑_j=1^N∑_k=1^N α̂_kt_k(_j-_*)^T(_k-_*)
       =-n_1+n_2/N+(n_1-n_2)Δ/Δ_*N+2
    (_1)-(_2)/Δ_*N+o_p( Δ/Δ_*) 
       =-n_1+n_2/N(δ/Δ_*)+2
    (_1)-(_2)/Δ_*N+o_p( Δ/Δ_*)  
       =
    (_1)/n_1-(_2)/n_2/Δ_*+o_p
    ( Δ/Δ_*)

under (A-i) and (A-ii). 
Similar to (<ref>), under (A-ii), we obtain that (_j-_*)^T(_0-_*)/Δ=(-1)^i+1/4+o_p(1) for j=1,...,n_1, and (_j-_*)^T(_0-_*)/Δ=(-1)^i/4+o_p(1) for j=n_1+1,...,N, when _0 ∈π_i (i=1,2). 
Then, from the first result of Lemma 2, under (A-i) and (A-ii), 
it holds that 

    ∑_j=1^Nα̂_jt_j (_j-_*)^T(_0-_*)=(-1)^iΔ/Δ_*
    +o_p( Δ/Δ_*)

when _0 ∈π_i for i=1,2. 
By combining (<ref>) with (<ref>) and (<ref>), 
we can conclude the second result.



By using (<ref>), the results are obtained straightforwardly. 




Similar to (<ref>), under (A-ii'),
from (<ref>), we have that as d,N→∞

    ∑_1≤ j< k≤ n_1 P(|(_j-_1)^T(_k-_1)|≥τΔ )=O(n_1^2(_1^2)/Δ^2)=o(1);
       ∑_n_1+1 ≤ j< k≤ N P(|(_j-_2)^T(_k-_2) |≥τΔ )=O(n_2^2(_2^2)/Δ^2)=o(1);
       ∑_j=1^n_1∑_k=n_1+1^N P(|(_j-_1)^T(_k-_2) |≥τΔ )=O(n_1n_2(_1_2)/Δ^2)=o(1);
       ∑_j=1^n_1 P(|(_j-_1)^T |≥τΔ )=O(n_1^T_1/Δ^2)=
    O(n_1(_1^2)^1/2/Δ)=o(1); 
         ∑_j=n_1+1^N P(|(_j-_2)^T |≥τΔ )=O(n_2(_2^2)^1/2/Δ) =o(1)

for any τ>0. 
Then, under (A-ii'), we have that 

    (_j-_*)^T(_k-_*)=Δ{1+o_p(1)}/4  ; 
       (_j-_*)^T(_k-_*)=Δ{1+o_p(1)}/4  ;  
       (_j-_*)^T(_k-_*)=-Δ{1+o_p(1)}/4
       .

On the other hand, for any τ>0, we have that 
∑_j=1^n_1 P(| _j-_*^2-Δ/4-(_1) |≥τΔ )= O{n_1 (_1j-_1^2) +n_1 ^T_1}/Δ^2=o(1) and 
∑_j=n_1+1^N
P(|_j-_*^2-Δ/4-(_2) |≥τΔ )=o(1) 
under (A-i') and (A-ii') as d,N→∞, 
so that 

    _j-_*^2=Δ{1+o_p(1)}/4+(_1)   ;  
       _j-_*^2=Δ{1+o_p(1)}/4+(_2)   .

Then, by combining (<ref>) with (<ref>) and (<ref>), we have (<ref>) as d,N→∞, 
subject to (<ref>) under (A-i') and (A-ii'). 
Similar to the proof of Lemma 2, 
by noting (A-iv), we can conclude the result. 




We have that 

    Δ̂_*-Δ_*=   ∑_i=1^2∑_j=1^n_i_ij-_i^2-(_i) /n_i^2+
    ∑_i=1^2∑_j≠ k^n_i(_ij-_i)^T(_ik-_i)/n_i^2
       +∑_i=1^2(-1)^i+1^T(_in_i-_i)-2(_1n_1-_1)^T
    (_2n_2-_2).

Note that E[{_ij-_i^2-(_i)}^2]=o(Δ^2) as d→∞ under (A-i) for all i,j. 
Also, 
note that E[{^T(_in_i-_i)}^2]=^T_i/n_i≤Δ(_i^2)^1/2/ n_i=o(Δ^2/n_i) as d→∞ under (A-ii) for i=1,2. 
Then, from (<ref>), we can claim that E{(Δ̂_*-Δ_*)^2}=o(Δ^2) under (A-i) and (A-ii), 
so that Δ̂_*=Δ_*+o_p(Δ). 
On the other hand, we have that 

    (_in_i)-(_i)=∑_j=1^n_i_ij-_i^2-(_i) /n_i
    -∑_j≠ k^n_i(_ij-_i)^T(_ik-_i)/n_i(n_i-1).

Then, similar to Δ̂_*, we can claim that (_in_i)=(_i)+o_p(Δ) for i=1,2, under (A-i) and (A-ii), so that κ̂=κ+o_p(Δ). 
Hence, by noting that |κ|/Δ_*≤ 1, we can claim the result. 



By using (<ref>), the result is obtained straightforwardly. 



From Lemma 3, we have (<ref>) as d,N→∞ under (A-i'), (A-ii') and (A-iv). 
We note that Lemma 4 holds even when d,N→∞. 
Hence, from (<ref>) and Lemma 4, we can claim the results.



By using Theorems 1 and 2, the results are obtained straightforwardly. 




§ ACKNOWLEDGEMENTS



Research of the second author was partially supported by 
Grant-in-Aid for Young Scientists (B), Japan Society for the Promotion of Science (JSPS), under Contract Number 26800078.
Research of the third author was partially supported by 
Grants-in-Aid for Scientific Research (A) and Challenging Exploratory Research, JSPS, under Contract Numbers 15H01678 and 26540010.

99

[Ahn and Marron (2010)]AM10 
Ahn, J., Marron, J.S., 2010. 
The maximal data piling direction for discrimination. 
Biometrika 97, 254-259.

[Alon et al. (1999)]A99
Alon, U., Barkai, N., Notterman, D.A., Gish, K., Ybarra, S., Mack, D., Levine, A.J., 1999.  
Broad patterns of gene expression revealed by clustering analysis of tumor 
and normal colon tissues probed by oligonucleotide arrays.
Proc. Natl. Acad. Sci. USA 96, 6745-6750.


[Aoshima and Yata (2011)]AY11
Aoshima, M., Yata, K., 2011.
Two-stage procedures for high-dimensional data. 
Sequential Anal. (Editor's special invited paper) 30, 356-399. 

[Aoshima and Yata (2014)]AY14 
Aoshima, M., Yata, K., 2014.
A distance-based, misclassification rate adjusted classifier for multiclass, high-dimensional data. 
Ann. Inst. Statist. Math. 66, 983-1010. 

[Aoshima and Yata (2015a)]AY15a
Aoshima, M., Yata, K., 2015a.
Geometric classifier for multiclass, high-dimensional data. 
Sequential Anal. 34, 279-294.

[Aoshima and Yata (2015b)]AY15b 
Aoshima, M., Yata, K., 2015b.
High-dimensional quadratic classifiers in non-sparse settings. arXiv:1503.04549. 


[Armstrong et al. (2002)]A02
Armstrong, S.A., Staunton, J.E., Silverman, L.B., Pieters, R., den Boer, M.L., Minden, M.D., Sallan, S.E., 
Lander, E.S., Golub, T.R., Korsmeyer, S.J., 2002.
MLL translocations specify a distinct gene expression profile that distinguishes a unique leukemia. 
Nature Genetics 30, 41-47. 


[Bishop (2006)]B06 
Bishop, C.M., 2006.
Pattern Recognition and Machine Learning. 
Springer, New York.


[Chan and Hall (2009)]CH09
Chan, Y.-B., Hall, P., 2009. 
Scale adjustments for classifiers in high-dimensional, low sample size settings.
Biometrika 96, 469-478. 

[Friedman (1996)]F96
Friedman, J., 1996.
Another approach to polychotomous classification. 
Technical report, Stanford University. 

[Golub et al. (1999)]G99
Golub, T.R., Slonim, D.K., Tamayo, P., Huard, C., Gaasenbeek, M., Mesirov, J.P., Coller, H., Loh, M.L., 
Downing, J.R., Caligiuri, M.A., Bloomfield, C.D., Lander, E.S., 1999. 
Molecular classification of cancer: class discovery and class prediction by gene expression monitoring.
Science 286, 531-537. 


[Hall et al. (2005)]H05
Hall, P., Marron, J.S., Neeman, A., 2005.
Geometric representation of high dimension, low sample size data.
J. R. Statist. Soc. B 67, 427-444.

[Hall et al. (2008)]H08
Hall, P., Pittelkow, Y., Ghosh, M., 2008.
Theoretical measures of relative performance of classifiers for high dimensional data with small sample sizes. 
J. R. Statist. Soc. B 70, 159-173.

[Hastie et al. (2009)]H09
Hastie, T., Tibshirani, R., Friedman, J., 2009.
The Elements of Statistical Learning: Data Mining, Inference, and Prediction (second ed.).
Springer, New York.


[Marron et al. (2007)]M07
Marron, J.S., Todd, M.J., Ahn, J., 2007.
Distance-weighted discrimination. 
J. Amer. Statist. Assoc. 102, 1267-1271.

[Qiao et al. (2010)]Q10
Qiao, X., Zhang, H.H., Liu, Y., Todd, M.J., Marron, J.S., 2010. 
Weighted distance weighted discrimination and its asymptotic properties.
J. Amer. Statist. Assoc. 105, 401-414.

[Qiao and Zhang (2015)]QZ15
Qiao, X., Zhang, L., 2015.
Flexible high-dimensional classification machines and their asymptotic properties.
J. Mach. Learn. Res. 16, 1547-1572.

[Schölkopf and Smola (2002)]SS02
Schölkopf, B., Smola, A.J., 2002. 
Learning with Kernels.

MIT Press, Cambridge. 


[Tian et al.(2003)]T03
Tian, E., Zhan, F., Walker, R., Rasmussen, E., Ma, Y., Barlogie, B., Shaughnessy, J.D. Jr., 2003. 
The role of the Wnt-signaling antagonist DKK1 in the development of osteolytic lesions in multiple myeloma. 
N. Engl. J. Med. 349, 2483-2494. 


[Vapnik (2000)]V00
Vapnik, V.N., 2000.
The Nature of Statistical Learning Theory (second ed.).
Springer, New York. 



