14

A general framework of SVM in HDLSS settings
Yugo Nakayama
Graduate School of Pure and Applied Sciences
University of Tsukuba
Kazuyoshi Yata
Institute of Mathematics

University of Tsukuba
Makoto Aoshima

Institute of Mathematics

University of Tsukuba

1

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, \Pi_{i} , i ı, 2, having an
unknown mean vector \mu_{i} and unknown covariance matrix \Sigma_{i} for each i . We have independentand identically distributed (i.i. d. ) observations, x_{i1},x_{in_{\iota}} , from each \Pi_{i} . We assumen_{i}\geq 2, i=1,2 . Let x_{0} be an observation vector of an individual belonging to one of the twopopulations. Let N=n_{1}+n_{2} . We assume x_{0} and x_{ij}s are independent.
=In this paper, we consider classification in the HDLSS context such as

darrow\infty while N isfixed. In the HDLSS context, Hall et al. [6], Marron et al. [8] and Qiao et al. [12] considered
distance weighted classifiers. Hall et al. [7], Chan and Hall [5] and Aoshima and Yata [2]considered distance‐based cıassifiers. In particular, Aoshima and Yata [2] gave the misclassifi‐
cation rate adjusted classifier for multiclass, high‐dimensional data in which misclassification

rates are no more than specified thresholds. On the other hand, Aoshima and Yata [1, 3] con‐sidered geometric classifiers based on a geometric representation of HDLSS data. Aoshimaand Yata [4] considered quadratic classifiers in general and discussed asymptotic properties
and optimality of the classifiers under high‐dimension, non‐sparse settings. For linear SVM

in HDLSS settings, Hall et al. [6], Chan and Hall [5] and Qiao and Zhang [13] showed thatthe misclassification rates tend to zero as darrow\infty under certain severe conditions. Nakayama
et al. [9] investigated asymptotic properties of linear SVM for HDLSS data. They proposed

15
a bias‐corrected linear SVM and showed that it gives preferable performances compared tolinear SVM. On the other hand, Nakayama et al. [10] investigated asymptotic properties ofSVM with the Gaussian kernel for HDLSS data.

In this paper, we consider a general framework of SVM in the HDLSS context whereIn Section 2, we investigate asymptotic properties of SVM in theHDLSS. In Section 3, we give asymptotic properties of SVM for both the linear and thedarrow\infty while N is fixed.

Gaussian kernels.

2

A general framework of SVM
In this section, we consider a general framework of SVM.

2.1

Setup of SVM
Since HDLSS data are mostly separable by a hyperplane, we consider the hard‐margin

SVM as follows:

y(x)=w^{T}\phi(x)+b ,where \phi(\cdot) is a feature map,(1)is a weight vector and b is an intercept term. Let us writen_{1} and t_{j}=1
N
for j=n_{1}+1,. By differentiating the Lagrangian formulation with respect to w andb , we obtain the following dual form:
thatw(x_{1}, \ldots, x_{N})=(x_{11}, \ldots, x_{1n_{1}}, x_{21}, \ldots, x_{2n_{2}}) . Let t_{j}=-1 for j=1,

L( \alpha)=\sum_{j=1}^{N}\alpha_{j}-\frac{1}{2}\sum_{j=1_{J} ^{N}\sum_{=1}^{N} \alpha_{j}\alpha_{j'}t_{j}t_{j'}k(x_{j}, x_{j'}),where k(x_{j}, x_{j'})=\phi(x_{j})^{T}\phi(x_{j'}) is a kernel function, and \alpha=(\alpha_{1}, \ldots, \alpha_{N})^{T} and \alpha_{j}s are
Lagrange multipliers such as w= \sum_{j=1}^{N}\alpha_{j}t_{j}\phi(x_{j}) . The optimization problem can be trans‐
formed into the following:
subject to\arg\max_{\alpha}L(\alpha)\alpha_{j}\geq 0, j=1 , . . . , N , and\sum_{j=1}^{N}\alpha_{j}t_{j}=0.

(2)

Let us write that\hat{\alpha}=(\hat{\alpha}_{1}, \ldots,\hat{\alpha}_{N})^{T}=\arg\max_{\alpha} L(\alpha) subject to (2).
There exist some x_{j}s satisfying that t_{j}y(x_{j})= ı (i.e., \hat{\alpha}_{j}\neq 0 ). Such x_{j}s are called the support

vector. Let \hat{S}=\{j|\hat{\alpha}_{j}\neq 0, j= {\imath}, N\} and N_{\hat{S}}=\#\hat{S} , where \# A denotes the number of16elements in a set A . The intercept term is given by \hat{b}=N_{\hat{S} ^{-1}\sum_{j\in\hat{S} \{t_{j}-\sum_{j\in\hat{S} \hat{\alpha}_{j'}t_{j'}k(x_{j}, x_{j})\}.
Then, the classifier in (1) is defined by\hat{y}(x)=\sum_{j\in\hat{S} \hat{\alpha}_{j}t_{j}k(x, x_{j})+\hat{b}.

(3)Finally, in SVM, one classifies x_{0} into \Pi_{1} if \hat{y}(x_{0})<0 and into \Pi_{2} otherwise. See Vapnik [14]for the details. Let e(i) denote the error rate of misclassifying an individual from \Pi_{i} into theother class for i=1,2 . We claim that a classifier has consistency ife(i)=o(1) as darrow\infty for i

=

ı, 2.

(4)

In this paper, we investigate the following typical kernels.

(I) The linear kernel:k(x_{j}, x_{j'})=x_{j}^{T}x_{j'} ; and(II) The Gaussian kernel:k(x_{j}, x_{j'})=\exp(-\Vert x_{j}-x_{j'}\Vert^{2}/\gamma) ,where \gamma(>0) is a scale parameter.

2.2

Asymptotic properties of SVM
First, we assume the following assumption as

darrow\infty :(A‐i) k(x_{1j}, x_{1j'})=\beta_{1}+o_{P}(\triangle) for all 1\leq j<j'\leq n_{1} ;k(x_{1j}, x_{1j})=\beta_{2}+op(\triangle) for all 1\leq j\leq n_{1} ;k(x_{2j}, x_{2j'})=\beta_{3}+o_{P}(\triangle) for all 1\leq j<j'\leq n_{2} ;k(x_{2j}, x_{2j})=\beta_{4}+o_{P}(\triangle) for all 1\leq j\leq n_{2} ; andk(x_{1j}, x_{2j'})=\beta_{5}+o_{P}(\triangle) for alll \leq j\leq n_{1},1\leq j'\leq n_{2} ;k(x_{0}, x_{ij})=\beta_{2i-1}+o_{P}(\triangle) when x_{0}\in\Pi_{i} for all 1\leq j\leq n_{i} and i=1,2 ;k(x_{0}, x_{i'j})=\beta_{5}+o_{P}(\triangle) when x_{0}\in\Pi_{i} for all 1\leq j\leq n_{\iota'} and i'\neq i.
Here, \beta\iota is a variable (which may depend on d) for l=1 ,where \triangle>0, \beta_{2}-\beta_{1}\geq 0 and \beta_{4}-\beta_{3}\geq 0.

5 and \triangle=\beta_{1}+\beta_{3}-2\beta_{5},We note that \triangle is a distance between the two populations. For example, \triangle=\Vert\mu_{1}-\mu_{2}\Vert^{2} whenk(\cdot, \cdot) is the linear kernel. See Section 3.ı for the details. Let \eta_{1}=\beta_{2}-\beta_{1} and \eta_{2}=\beta_{4}-\beta_{3} . Wenote that \sum_{j=1}^{n_{1} \alpha_{j}=\sum_{j=n_{1}+1}^{N}\alpha_{j} ( =\alpha_{\star} , say) under (2). Then, from Section 2 of Nakayama
et al. [ı1], we have the following lemma.
Lemma 1 ([11]). Under (2) and (A‐i), it holds that as darrow\inftyL(\alpha)=2\alpha_{\star}-\frac{\Delta}{2}\alpha_{\star}^{2}-\frac{1}{2}(\eta_ {1}\sum_{J=1}^{n_{1} \alpha_{j}^{2}+\eta_{2}\sum_{j=n_{1}+1}^{N}\alpha_{j}^{2})+ o_{P}(Aa^{2}.).

17We can claim that\max\alpha\{-\frac{1}{2}(\eta_{1}\sum_{J=1}^{n_{1} \alpha_{J}^{2}+\eta_{2} \sum_{J^{=n}1+1}^{N}\alpha_{J}^{2})\}=-\frac{\alpha_{\star}^{2} {2}(\eta_{1} /n_{1}+\eta_{2}/n_{2})=\alpha_{n_{1}}=\alpha_{\star}/n_{1} and \alpha_{n_{1}+1}=
when \alpha_{1}==\alpha_{N}=\alpha_{\star}/n_{2} under (2). Let \triangle_{*}=\triangle+\eta_{1}/n_{1}+\eta_{2}/n_{2} . We consider the following condition:\lim_{dar ow}\inf_{\infty}\frac{\eta_{i} {\triangle}>0 for i=1,2 .

(5)Then, in a way similar to Section 2 of Nakayama et al. [9], from Lemma 1 it holds that

\max_{\alpha}L(\alpha)=-\frac{\triangle}{2}*(\alpha_{\star}-\frac{2+o_{P} ({\imath})}{\triangle_{*} )^{2}\{1+o_{P}(1)\}+\frac{2+o_{P}(1)}{\Delta_{*}(6)

under (2), (5) and (A‐i), so that \alpha_{\star}\approx 2/\triangle_{*} . Then, from (6), we have the following result.
Proposition 1 ([11]). Let \delta=\eta_{1}/n_{1}-\eta_{2}/n_{2} . Assume (A‐i) and (5). It holds that as darrow\infty\hat{\alpha}_{j}=\frac{2}{\Delta_{*}n_{1} \{1+o_{P}(1)\} for all\hat{\alpha}_{j}=\frac{2}{\triangle_{*}n_{2} \{1+o_{P}(1)\} for all
Furthermore, it holds that as

j=1,n_{1} ;j=n_{1}+1,

andN.

darrow\infty\hat{y}(x_{0})=\frac{\Delta}{\triangle_{*} ( -1)^{i}+\frac{\delta}{\triangle}+ o_{P}(1)when x_{0}\in\Pi_{i} for i=1,2.

Now, we consider the following condition:(C‐i)\lim\sup\frac{|\delta|}{\triangle}<1.
darrow\infty

For the misclassification rates, from Section 2 of Nakayama et al. [11], we have the followingresults.

Theorem 1 ([11]). Under (A‐i) and (C‐i), SVM (3) holds consistency (4).
Coroılary 1 ([11]). Under (A‐i), SVM (3) holds the following properties:e(1)=1+o(1) and e(2)=o(1) as darrow\infty
if\lim\dot{ \imath} nf\ rac{\delta}{\Delta}dar ow\infty>1 ; ande(1)=o(1) and e(2)=1+o(1) as darrow\infty
if(7)(8)\delta\lim_{dar ow}\sup_{\infty}\overline{\triangle}<-1.

For linear SVM, Nakayama et al. [9] showed consistency (4) and the results in Corollary
1. From Corollary 1, if |\delta| is larger than \triangle , SVM would give a bad performance. Nakayama
et al. [1ı] proposed a robust SVM in HDLSS settings.

183

Asymptotic properties of SVM with kernel functions (I) or(II)We assume that ıim \sup_{darrow\infty}\Vert\mu_{i}\Vert^{2}/d<\infty andtr(\Sigma_{i})/d\in(0, \infty) as darrow\infty for i=1,2.
Here, for a function, f(\cdot) , “ f(d)\in(0, \infty) as
implies \lim\inf_{darrow\infty}f(d)>0 and\lim\sup_{darrow\infty}f(d)<\infty . Similar to Aoshima and Yata [2], we assume the following assumption
darrow\infty ”

for \Pi_{i}s as necessary:n_{i} , be i.i. d . random p_{i} ‐vectors having E(z_{ij})=0 and Var(z_{ij})=(A‐ii) Let z_{ij}, j=1,
I_{p_{i} for each i(=1,2) and some p_{i} . Let z_{lj}=(z_{i1j}, \ldots, z_{ip_{\iota}j})^{T} whose components satisfy

that\lim\sup_{darrow\infty}E(z_{irj}^{4})<\infty for allrandE(z_{irj}^{2}z_{xsj}^{2})=E(z_{irj}^{2})E(z_{isj}^{2})=1

and

E(z_{irj}z_{isj}z_{itj}z_{iuj})=0

for all r\neq s, t, u . Then, the observations, x_{ij}s , from each \Pi_{i}(i=1,2) are given byn_{i} , where \Gamma_{i} is a d\cross p_{\dot{i}} matrix such that \Gamma_{i}\Gamma_{i}^{T}=\Sigma_{i}.
x_{ij}=\Gamma_{i}z_{ij}+\mu_{i}, j=1,
Note that z_{irj}s are i.i. d .

as the standard normal distribution when the \Pi_{i}s are Gaussianand \Gamma_{i}=H_{i}\Lambda_{i}^{1/2} , where A_{i}=diag(\lambda_{i(1)}, \ldots, \lambda_{i(d)}) is a diagonal matrix of eigenvalues,\lambda_{i(1)}\geq\geq\lambda_{i(d)}\geq 0 , and H_{i} is an orthogonal matrix of the corresponding eigenvectors.

Thus, (A‐ii) naturally holds when the \Pi_{i}s are Gaussian.

3.1
set

Linear kernel function (I)We consider linear SVM (LSVM), that is, the classifier (3) having kernel function (I). We\beta_{1}=\Vert\mu_{1}\Vert^{2}, \beta_{2}=\Vert\mu_{1}\Vert^{2}+tr(\Sigma_{1}), \beta_{3}=\Vert\mu_{2}\Vert^{2}, \beta_{4}=\Vert\mu_{2}\Vert^{2}+tr(\Sigma_{2}) and \beta_{5}=\mu_{1}^{T}\mu_{2}, sothat\triangle=\Vert\mu_{1}-\mu_{2}\Vert^{2} ( =\triangle_{(I)} , say) and \eta_{\dot{i}}=tr(\Sigma_{i}) ( =\eta_{i(I)} , say) for i=1,2.
We note that LSVM is invariant to linear transformations on the data set. Thus, in Section
3.1, we assume \mu_{2}=0 without loss of generality, so that \beta_{3}=\beta_{5}=0, \beta_{4}=\eta_{2(I)} and\triangle_{(I)}=\Vert\mu_{1}\Vert^{2} . In addition, we assume the following condition as darrow\infty :(C‐ii)\frac{tr(\Sigma_{i}^{2}) {\triangle_{(l)}^{2} =o(1)for i=

ı, 2.

Then, from Section 3 of Nakayama et al. [11], we have the following lemma.

Lemma 2 ([ıı]). Assume (A‐ii) and (C‐ii). Then, the assumption (A‐i) \dot{u} met for kernel

function (I).

By combining Lemma 2 with Theorem 1 and Corollary 1, we have the following results.

19
Corollary 2. For LSVM, one can claim that(4) holds if(8) holds if\lim_{dar ow}\sup_{\infty}\frac{|\delta_{(i)}|{\triangle_{(I)}< ı; (7) holds if \lim_{dar ow}\inf_{\infty}\frac{\delta_{(I)}{\triangle_{(I)}>1 ; and\lim_{dar ow}\sup_{\infty}\frac{\delta_{(I)} {\Delta_{(I)} <-1

under (A‐ii) and (C‐ii), where \dot{\delta}_{(I)}=\eta_{1(I)}/n_{1}-\eta_{2(I)}/n_{2}.

Nakayama et al. [9] provided a bias correction of linear SVM (BC‐LSVM). They com‐pared BC‐LSVM with LSVM both in numerical simulations and actual data analyses. They
concluded that BC‐LSVM gives adequate performances for HDLSS settings even when n_{i}sare quite unbalanced.

3.2

Gaussian kernel function (II)We consider Gaussian kernel SVM (GSVM), that is, the classifier (3) with kernel function(II). We set \beta_{1}=\exp\{-2tr(\Sigma_{1})/\gamma\} ( =\beta_{1(II)} , say), \beta_{3}=\exp\{-2tr(\Sigma_{2})/\gamma\} ( =\beta_{3(II)} , say),\beta_{2}=\beta_{4}=1 , and \beta_{5}=\exp[-\{tr(\Sigma_{1})+tr(\Sigma_{2})+\triangle_{(l)}\}/\gamma] ( =\beta_{5(Il)} , say), so that\triangle=\beta_{1(II)}+\beta_{3(II)}-2\beta_{5(II)} ( =\triangle_{(II)} , say) and\eta_{i}=1-\exp(-2tr(\Sigma_{i})/\gamma) ( =\eta_{i(II)} , say) for i=1,2.
We note that\triangle_{(II)}>0 when \mu_{1}\neq\mu_{2} or tr(\Sigma_{1})\neq tr(\Sigma_{2}) . Let tr(\Sigma_{\min})=\min_{i=1,2}tr(\Sigma_{i})and \psi=\exp\{-2tr(\Sigma_{\min})/\gamma\} . We assume the following condition as darrow\infty :( C ‐iii)\frac{tr(\Sigma_{i}^{2})+\Delta_{(I)}\{tr(\Sigma_{i}^{2})\^{1/2} {\min\{ gam a^{2}\Delta_{(I)}^{2}/\psi^{2},\gam a^{2}\ =o(1)for i=1,2.

Then, from Section 3 of Nakayama et al. [11], we have the following lemma.

Lemma 3 ([11]). Assume (A‐ii) and ( C‐iii). Then, the assumption (A‐i) is met for kernel

function (II).

By combining Lemma 3 with Theorem 1 and Corollary 1, we have the folıowing results.
Corollary 3. For GSVM, one can claim that(4) holds if(8) holds if\lim_{dar ow}\sup_{\infty}\frac{|\delta_{(I )}| {\triangle_{(I )} <1 ; (7) holds if \lim_{dar ow}\inf_{\infty}\frac{\delta_{(I )} {\triangle_{(I )} >1 ; and\lim_{dar ow}\sup_{\infty}\frac{\delta_{(I )} {\triangle_{(I )} <-1

under (A‐ii) and ( C‐iii), where \delta_{(II)}=\eta_{1(II)}/n_{1}-\eta_{2(II)}/n_{2}.

20Nakayama et al. [11] provided a bias correction of GSVM (BC‐GSVM). They compared
BC‐GSVM with GSVM both in numerical simulations and actual data analyses. They also
discussed the choice of \gamma.

Acknowledgements
The 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. The research of the third author was partially supported by Grants‐in‐Aid for

Scientific Research (A) and Challenging Research (Exploratory), JSPS, under Contract
Numbers 15H01678 and 17K19956.

References[1] M. Aoshima, K. Yata, Two‐stage procedures for high‐dimensional data, Sequential Anal.
30 (2011) 356‐399.
[2] M. Aoshima, K. Yata, A distance‐based, misclassification rate adjusted classifier for
multiclass, high‐dimensional data, Ann. Inst. Statist. Math. 66 (2014) 983‐1010.

[3] M. Aoshima, K. Yata, Geometric classifier for multiclass, high‐dimensional data, Sequen‐tial Anal. 34 (2015) 279‐294.
[4] M. Aoshima, K. Yata, High‐dimensional quadratic classifiers in non‐sparse settings,
arXiv:ı503.04549 (2015).
[5] Y.‐B. Chan, P. Hall, Scale adjustments for classifiers in high‐dimensional, low sample
size settings, Biometrika 96 (2009) 469‐478.

[6] P. Hall, J.S. Marron, A. Neeman, Geometric representation of high dimension, low sample
size data, J. R. Statist. Soc. B67 (2005) 427‐444.
[7] P. Hall, Y. Pittelkow, M. Ghosh, Theoretical measures of relative performance of classi‐fiers for high dimensional data with small sample sizes, J. R. Statist. Soc. B70 (2008)
159‐173.

[8] J.S. Marron, M.J. Todd, J, Ahn, Distance‐weighted discrimination, J. Amer. Statist.
Assoc. 102 (2007) 1267‐ı27l.
[9] Y. Nakayama, K. Yata, M. Aoshima, Support vector machine and its bias correction inhigh‐dimension, low‐sample‐size settings, J. Stat. Plan. Infer. 191 (2017) 88‐100.

2121[10] Y. Nakayama, K. Yata, M. Aoshima, Asymptotic properties of support vector machines
in HDLSS settings, RIMS Koukyuroku, 2047 (2017) 10‐18.
[11] Y. Nakayama, K. Yata, M. Aoshima, Bias‐corrected support vector machine with Gaus‐
sian kernel in high‐dimension, low‐sample‐size settings, submitted (2018).
[12] X. Qiao, H.H. Zhang, Y. Liu, M.J. Todd, J.S. Marron, Weighted distance weighted
discrimination and its asymptotic properties, J. Amer. Statist. Assoc. 105 (2010) 401‐414.

[13] X. Qiao, L. Zhang, Flexible high‐dimensional classification machines and their asymptoticproperties, J. Mach. Learn. Res. 16 (2015) 1547‐1572.

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