Legendre Polynomial Kernel: Application in SVM

Habib Rebei¹, Nouf S. H. Alharbi²

¹Department of Mathematics, College of Science, Qassim University, Buraydah, Kingdom of Saudi Arabia.
²Department of Mathematics, College of Science and Arts in Nabhaniya, Qassim University, Buraydah, Kingdom of Saudi Arabia.

DOI: 10.4236/jamp.2022.105121                

Abstract

In machines learning problems, Support Vector Machine is a method of classification. For non-linearly separable data, kernel functions are a basic ingredient in the SVM technic. In this paper, we briefly recall some useful results on decomposition of RKHS. Based on orthogonal polynomial theory and Mercer theorem, we construct the high power Legendre polynomial kernel on the cube [-1,1]^d. Following presentation of the theoretical background of SVM, we evaluate the performance of this kernel on some illustrative examples in comparison with Rbf, linear and polynomial kernels.

Keywords

SVM, Polynomial Legendre Kernel, Classification Problem, Mercer Theorem

1. Introduction

The approach of reproducing kernel function has many applications in probability theory, in statistics and recently in machine learning (see [1] [2] [3]). They have been applied in many fields and domains of life sciences such as pattern recognition, biology, medical diagnosis, chemistry and bio-informatics.

It is well-known from many years that data sets can be modeled by a family of points $\mathcal{X}\subset {ℝ}^d$ and similarity between them is given by an inner product on ${ℝ}^d$. The classification problem consists of separating these points into classes with respect to given properties. In the simplest situation, the points are linearly separable in the sense that there exists an hyperplane $H_s$ separating the two classes.

Support vector machines (SVMs) have become a very powerful tool in machine learning in particular in classification problems and regression ( [1] [4] [5]). In classification problem, we can consider only two-classes of data, so we speak about a binary classification. Also we can rencounter more than two classes of data. This is called a multi-task classification problem. In our cases, we focus on binary classification and the application of kernel functions in SVM classification.

In simplest situations, the linear SVM technic allows to find the optimal hyperplane separating points in two classes. Unfortunately, in concrete examples, these points are not linearly separable. Then, one can traduce similarity of points in term of positive definite kernel function k on $\mathcal{X}$. This leads to invent a new technic named non-linear SVM which combines linear SVM and kernel tools.

Mathematically, this new approach of non-linear SVM is related to the Kolmogorov representation $\left(\mathcal{H}\mathrm{,}\Phi \right)$, where $\mathcal{H}$ represents the feature space and $\Phi$ is the feature map (see [1]). Since separation expresses a degree of similarity between points in the same class, Vapnick used the kernel approach to translate the problem from initial space ${ℝ}^d$ to the feature space. The transfer between initial space and the feature space is made under the feature map and similarities are expressed by the inner product in the feature space which is given by a kernel k. The crucial idea of the kernel function methods is that non-linearly separable points can be transformed to linearly separable points in the feature space guarding similarities which is expressed by

$\langle \Phi \left(x_i\right)\mathrm{,}\Phi \left(x_j\right)\rangle =k\left(x_i\mathrm{,}{x}_j\right)\mathrm{.}$

Furthermore, the solution of the classification problem using non-linear SVM is given by the decision function which depends only on the kernel and support vectors ( $x_i\in S$ ). Precisely, it takes the following form

$F\left(x\right)=sgn\left(b+{\displaystyle \underset{x_i\in S}{\sum }}{\alpha }_{i}k\left(x_i\mathrm{,}x\right)\right)\mathrm{.}$

Since the choice of the kernel function is not canonic, the first problem of this approach is how to choose a suitable kernel function for such given data points. The second problem is that the feature space has an infinite dimensional and this causes a technical problem in modeling computational algorithm for such a solution. This problem is also related to the feature map $\Phi$ which is in general unknown. In our case, we use the Mercer decomposition theorem in order to obtain a type polynomial kernel having a good separation property. This means that infinite dimensional feature space can be approximated by finite dimensional feature space. This reduces the dimensionality of new data in feature space.

The paper is organized as follows: In Section 2, we recall some known results on Reproducing Kernel Hilbert Space (RKHS in what follow), in particular, the Mercer decomposition theorem 2.2 and the high power kernel theorem 2.3. Section 3 is devoted to the main result in which we introduce the one-dimensional Legendre polynomial kernel $K_n$ and we give its canonical decomposition in term of Legendre orthogonal polynomials (see Theorem 3.1). Next, we deduce the high power Legendre polynomial kernel $K_n=K_n^d$ defined on the cube ${\left[-\mathrm{1,1}\right]}^d$ for which the feature space $H_n={\mathcal{H}}_n^{\otimes d}$ is the tensor product Hilbert space of the RKHS associated with $K_n$. In Section 4, we recall the theoretical foundation of linear and non-linear SVMs. In Section 4, we give some illustrative examples in order to evaluate the performance of the Legendre polynomial kernel in comparison with some predefined kernels in Python.

2. Preliminaries

In this section, we begin by describing the RHKS and its associated kernel. Then we give the decomposition of a given positive definite kernel on a measure space $\mathcal{X}$ (see Theorem 2.2).

Definition 1. (Positive definite kernel).

Let $\mathrm{<mo>\; |\; </mo>}XX$ be a nonempty set. A symmetric function $k\mathrm{<mo>\; :\; </mo>}\mathcal{X}\times \mathcal{X}\to ℝ$ is called positive definite kernel if,

${\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\displaystyle \underset{j=1}{\overset{n}{\sum }}}{a}_i{a}_{j}k\left(x_i,x_j\right)\ge 0\forall n\ge 1,a_1,\cdots ,a_n\in ℝ,x_1,\cdots ,x_n\in \mathcal{X}$ (2.1)

and for mutually distinct $x_i$, the equality holds only when all the $a_i$ are zero.

Clearly that every inner product is a positive definite function. Moreover if $\mathcal{H}$ is any Hilbert space and $\mathcal{X}$ a nonempty set and $\varphi \mathrm{<mo>\; :\; </mo>}\mathcal{X}\to \mathcal{H}$, then the function $h\left(x\mathrm{,}y\right)\mathrm{<mo>\; :\; </mo>}=\langle \varphi \left(x\right)\mathrm{,}\varphi \left(y\right)\rangle$ is a positive definite.

Now let $\mathcal{H}$ be a Hilbert space of functions mapping from some non-empty set $\mathcal{X}$ to $ℝ$, i.e., $\mathcal{H}$ is considered as a subset of ${ℝ}^{\mathcal{X}}$. We write the inner product on $\mathcal{H}$ as

$\langle f\mathrm{,}g\rangle \mathrm{,}f\mathrm{,}g\in \mathcal{H}$

and the associated norm will be denoted by

${\Vert f\Vert }_2={\langle f\mathrm{,}f\rangle }^{\frac{1}{2}}\mathrm{,}f\in \mathcal{H}\mathrm{.}$

We may alternatively write the function f as $f(\cdot )$, to indicate it takes an argument in $\mathcal{X}$.

Definition 2. (Reproducing kernel Hilbert space).

Let $\left(\mathcal{H}\mathrm{,}\langle \cdot \mathrm{,}\cdot \rangle \right)$ be a Hilbert space of $ℝ$ -valued functions defined on a non-empty set $\mathcal{X}$. We say that $\mathcal{H}$ is a Reproducing Kernel Hilbert Space if there exists a kernel function $k\mathrm{<mo>\; :\; </mo>}\mathcal{X}\times \mathcal{X}\to ℝ$ such that the following properties are satisfied:

1) $\forall x\in \mathcal{X}$, $k_x\mathrm{<mo>\; :\; </mo>}=k\left(\mathrm{.,}x\right)\in \mathcal{H}$,

2) $\forall x\in \mathcal{X}$, $\forall f\in \mathcal{H}$, $f\left(x\right)=\langle k_x\mathrm{,}f\rangle$ (the reproducing property).

Remark 1. From the reproducing property, we note that

$k\left(x\mathrm{,}y\right)=k_y\left(x\right)=\langle k_x\mathrm{,}{k}_y\rangle =\langle k\left(\mathrm{.,}x\right)\mathrm{,}k\left(\mathrm{.,}y\right)\rangle \mathrm{,}x\mathrm{,}y\in \mathcal{X}\mathrm{.}$ (2.2)

Thus necessarily, k is positive definite. Note also that reproducing kernel k associated with $\mathcal{H}$, it is unique.

Theorem 2.1. (Moore-Aronszajn [6])

Let $k\mathrm{<mo>\; :\; </mo>}\mathcal{X}\times \mathcal{X}\to ℝ$ be a positive definite kernel. There is a unique RKHS $\mathcal{H}\subset {ℝ}^{\mathcal{X}}$ with reproducing kernel k. Moreover, if space

${\mathcal{H}}_0=span\left[{\left\{k_x\right\}}_{x\in \mathcal{X}}\right]$ (2.3)

is endowed with the inner product

${\langle f,g\rangle }_{{\mathcal{H}}_0}={\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\displaystyle \underset{j=1}{\overset{m}{\sum }}}{\alpha }_i{\beta }_{j}k\left(x_i,y_j\right),$ (2.4)

where $f={\displaystyle {\sum }_{i=1}^n}{\alpha }_i{k}_{x_i}$ and $g={\displaystyle {\sum }_{j=1}^m}{\beta }_j{k}_{y_j}$, then $\mathcal{H}$ is the completion of ${\mathcal{H}}_0$ w.r.t the inner product (4).

Now let us consider a compact metric space $\mathcal{X}$ and a finite Borel measure $\nu$ on it. We consider a positive definite continuous kernel on $\mathcal{X}$. Let $S_k$ be the linear map

$S_k\mathrm{<mo>\; :\; </mo>}{L}_2\left(\mathcal{X}\mathrm{<mo>\; ;\; </mo>}\nu \right)\to \mathcal{C}\left(\mathcal{X}\right)\mathrm{,}$

$\left(S_{k}f\right)\left(x\right)={\displaystyle {\int }_{\mathcal{X}}}k\left(x,y\right)f\left(y\right)\text{d}\nu (\; y\; )$

and $T_k=I_k\circ S_k$, where $I_k\mathrm{<mo>\; :\; </mo>}\mathcal{C}\left(\mathcal{X}\right)$ ↪ $L_2\left(\mathcal{X}\mathrm{<mo>\; ;\; </mo>}\nu \right)$. Then we have the following results:

Theorem 2.2. (Mercer’s theorem [6])

1) $T_k$ is a compact self-adjoint positive definite from $L_2\left(\mathcal{X}\mathrm{<mo>\; ;\; </mo>}\nu \right)$ to itself. It is called the integral operator corresponding to the kernel k.

2) There exists an ortho-normal system ${\left\{{\tilde{e}}_j\right\}}_{j\in J}$ of eigenvectors of $T_k$ with eigenvalues ${\left\{{\lambda }_j\right\}}_{j\in J}$, where J is at most countable set of indices, corresponding to the strictly positive eigenvalues of $T_k$ such that

$T_k\left(f\right)={\displaystyle \underset{j\in J}{\sum }}{\lambda }_j\langle {\tilde{e}}_j\mathrm{,}f\rangle {\tilde{e}}_j\mathrm{,}f\in L_2\left(\mathcal{X}\mathrm{,}\nu \right)\mathrm{.}$ (2.5)

3) For all $x\mathrm{,}y\in \mathcal{X}$

$k\left(x\mathrm{,}y\right)={\displaystyle \underset{j\in J}{\sum }}{\lambda }_j{e}_j\left(x\right)e_j\left(y\right)\mathrm{,}$ (2.6)

where $e_j={\lambda }_j^{-1}{S}_k{\tilde{e}}_j\in \mathcal{C}\left(\mathcal{X}\right)$ and where the convergence is uniform on $\mathcal{X}\times \mathcal{X}$, and absolute for each pair $\left(x\mathrm{,}y\right)\in \mathcal{X}\times \mathcal{X}$.

4) The Hilbert space

$\mathcal{H}=\left\{f={\displaystyle \underset{j\in J}{\sum }}{a}_j{e}_j:\left(\frac{a_j}{\sqrt{{\lambda }_j}}\right)\in {\mathcal{l}}^2\left(J\right)\right\}$

endowed with the inner product

${\langle {\displaystyle \underset{j\in J}{\sum }}{a}_j{e}_j,{\displaystyle \underset{j\in J}{\sum }}{b}_j{e}_j\rangle }_{\mathcal{H}}={\displaystyle \underset{j\in J}{\sum }}\frac{a_j{b}_j}{{\lambda }_j}$ (2.7)

is the RKHS associated with k.

Theorem 2.3. (Power of kernel [4] [7])

Let k be a kernel on $\mathcal{X}$. Then

$K_d\left(x,y\right):={\displaystyle \underset{i=1}{\overset{d}{\prod }}}k\left(x_i,y_i\right),x=\left(x_1,\cdots ,x_d\right),y=\left(y_1,\cdots ,y_d\right)\in {\mathcal{X}}^d$

is a kernel on ${\mathcal{X}}^d$. In addition, there is an isometric isomorphism between ${\mathcal{H}}_K$ and the Hilbert space tensor product ${\mathcal{H}}_k^{\otimes d}$.

Example 1. Here we give some most known kernels used in SVM.

1) The linear kernel: $k_{lin}\left(x\mathrm{,}y\right)=\langle x\mathrm{,}y\rangle +c$, $c\ge 0$.

2) The polynomial kernel: $k_{poly}\left(x\mathrm{,}y\right)={\left(a\langle x\mathrm{,}y\rangle +b\right)}^m$, $a>0$, $b\ge 0$, $m\ge 1$.

3) The exponential kernel: $k_{exp}\left(x\mathrm{,}y\right)={\text{e}}^{\sigma \langle x\mathrm{,}y\rangle }$, $\sigma >0$.

4) The radial basis function (Rbf): $k_{rbf}\left(x,y\right)={\text{e}}^{-\gamma {\Vert x-y\Vert }^2}$, $\gamma >0$. It is also called the Guassian kernel.

5) The sigmoid kernel: $k_{sigm}\left(x,y\right)=\tanh \left(\langle x,y\rangle +c\right)$, $c\ge 0$.

3. Legendre Polynomial Kernel and High Power Legendre Polynomial Kernel

Let us consider the family of Legendre polynomials ${\left\{L_n\right\}}_{n\ge 0}$ defined by the following recurrence relation (see [8])

$\{\begin{array}{l}{L}_0\left(x\right)=1,L_1\left(x\right)=x,\\ L_{n+1}\left(x\right)=x{L}_n\left(x\right)-w_n{L}_{n-1}\left(x\right),n\ge 1,\end{array}$ (3.1)

where

$w_n=\frac{n^2}{\left(2n-1\right)\left(2n+1\right)},n\ge 1.$ (3.2)

It well-known [8] that they are orthogonal w.r.t the inner product

$\langle f\mathrm{,}g\rangle \mathrm{<mo>\; :\; </mo>}={\displaystyle {\int }_{-1}^1}f\left(x\right)g\left(x\right)\text{d}x\mathrm{.}$

Moreover we have

${\Vert L_n\Vert }^2=w_1\cdots w_n\mathrm{.}$ (3.3)

In order to apply the Mercer theorem in SVM, we consider the Legendre polynomial kernel defined on ${\left[-\mathrm{1,1}\right]}^2$ by

$K_n\left(x,y\right)={\displaystyle \underset{k=0}{\overset{n}{\sum }}}{L}_k\left(x\right)L_k\left(y\right).$ (3.4)

Theorem 3.1. Let

${\mathcal{H}}_n=\left\{f={\displaystyle \underset{k=0}{\overset{n}{\sum }}}{\alpha }_k{L}_k,{\alpha }_k\in ℝ\right\}$ (3.5)

be the linear space generated by this family ${\left\{L_k\right\}}_{0\le k\le n}$. Then

1) ${\mathcal{H}}_n$ is a Hilbert space endowed with the inner product

$\langle {\displaystyle \underset{i=0}{\overset{n}{\sum }}}{\alpha }_i{L}_i,{\displaystyle \underset{j=0}{\overset{n}{\sum }}}{\beta }_j{L}_j\rangle ={\displaystyle \underset{j=0}{\overset{n}{\sum }}}{\alpha }_j{\beta }_j$ (3.6)

2) The sequence ${\left\{L_k\right\}}_{0\le k\le n}$ is an orthonormal basis of ${\mathcal{H}}_n$.

3) ${\mathcal{H}}_n$ is a RKHS with reproducing kernel $K_n$.

4) The feature map associated with $K_n$ is

${\varphi }_n:\left[-1,1\right]\to {\mathcal{H}}_n,t\mapsto \varphi \left(t\right)={\displaystyle \underset{j=0}{\overset{n}{\sum }}}{L}_j\left(t\right)L_j.$

Proof. First: Clearly that (3.6) defines a inner product on ${\mathcal{H}}_n$, for which ${\mathcal{H}}_n$ becomes an Hilbert space since it has a finite dimension.

Second: Form the definition of the inner product (3.6), clearly that ${\left\{L_k\right\}}_{0\le k\le n}$ is an orthonormal system of ${\mathcal{H}}_n$ whose cardinality coincides with the dimension of ${\mathcal{H}}_n$. Thus it is an orthonormal basis of ${\mathcal{H}}_n$.

Third: Let us consider the operator $S_n$ defined on ${\mathcal{H}}_L:=L^2\left(\left[-1,1\right]\right)$ by

$S_n\mathrm{<mo>\; :\; </mo>}f\mapsto {\displaystyle {\int }_{-1}^1}{K}_n\left(x\mathrm{,}y\right)f\left(y\right)\text{d}y\in \mathcal{C}\left(\left[-\mathrm{1,1}\right]\right)\mathrm{.}$

Setting $T_n=I_n\circ S_n$, where $I_n$ is the canonic injection of $\mathcal{C}\left(\left[-\mathrm{1,1}\right]\right)$ into ${\mathcal{H}}_L$.

1) $K_n$ is positive definite. In fact

$\begin{array}{c}{\displaystyle \underset{1\le i,j\le m}{\sum }}{a}_i{a}_j{K}_n\left(x_i,x_j\right)={\displaystyle \underset{1\le i,j\le m}{\sum }}{a}_i{a}_j{\displaystyle \underset{k=0}{\overset{n}{\sum }}}{L}_k\left(x_i\right)L_k\left(x_j\right)\\ ={\displaystyle \underset{k=0}{\overset{n}{\sum }}}{\displaystyle \underset{1\le i,j\le m}{\sum }}{a}_i{a}_j{L}_k\left(x_i\right)L_k\left(x_j\right)\\ ={\displaystyle \underset{k=0}{\overset{n}{\sum }}}{\left({\displaystyle \underset{i=1}{\overset{m}{\sum }}}{a}_i{L}_k\left(x_i\right)\right)}^2\ge 0.\end{array}$

2) $T_n$ is symmetric since $K_n$ is symmetric, so by Mercer theorem 2.2, $T_n$ is self-adjoint compact and positive definite.

3) For all $j=0,1,\cdots ,n$, we have

$\begin{array}{c}{T}_n\left(L_j\right)\left(x\right)={\displaystyle {\int }_{-1}^1}{K}_n\left(x,y\right)L_j\left(y\right)\text{d}y\\ ={\displaystyle {\int }_{-1}^1}\left({\displaystyle \underset{k=0}{\overset{n}{\sum }}}{L}_k\left(x\right)L_k\left(y\right)\right)L_j\left(y\right)\text{d}y\\ ={\displaystyle \underset{k=0}{\overset{n}{\sum }}}{\displaystyle {\int }_{-1}^1}{L}_k\left(x\right)L_k\left(y\right)L_j\left(y\right)\text{d}y\\ ={\displaystyle \underset{k=0}{\overset{n}{\sum }}}{L}_k\left(x\right){\displaystyle {\int }_{-1}^1}{L}_k\left(y\right)L_j\left(y\right)\text{d}y\\ ={\displaystyle \underset{k=0}{\overset{n}{\sum }}}{L}_k\left(x\right){\Vert L_j\Vert }^2{\delta }_{k,j}\\ ={\Vert L_j\Vert }^2{L}_j\left(x\right).\end{array}$

So the eigenvectors of $T_n$ are exactly the polynomials $L_j$ and the corresponding eigenvalues are ${\lambda }_j={\Vert L_j\Vert }^2$. Thus $\left\{L_j\mathrm{,}0\le j\le n\right\}$ is an orthonormal basis of ${\mathcal{H}}_n$ formed by eigenvectors of $T_n$.

From Mercer theorem 2.2, The RKHS associated with $K_n$ is given by

${\mathcal{H}}_{K_n}=\left\{f={\displaystyle \underset{j=0}{\overset{n}{\sum }}}{\alpha }_j{L}_j,\frac{{\alpha }_j}{\sqrt{{\lambda }_j}}\in l^2\right\}$

Since $\frac{{\alpha }_j}{\sqrt{{\lambda }_j}}\in l^2$ for all sequence ${\alpha }_j$, the space ${\mathcal{H}}_{K_n}$ coincides with ${\mathcal{H}}_n$ given by (3.5). Thus ${\mathcal{H}}_n$ is the RKHS associated with the reproducing kernel $K_n$.

The reproducing property is immediate from Mercer theorem but also it can be checked by hand using (3.6)

$\langle K_n\left(x,\cdot \right),f(\cdot )\rangle =\langle {\displaystyle \underset{k=0}{\overset{n}{\sum }}}{L}_k\left(x\right)L_k(\cdot ),{\displaystyle \underset{j=0}{\overset{n}{\sum }}}{\alpha }_j{L}_j(\cdot )\rangle ={\displaystyle \underset{k=0}{\overset{n}{\sum }}}{\alpha }_k{L}_k\left(x\right)=f\left(x\right).$

Forth: The feature map is given by

Let ${\varphi }_n$ given by

${\varphi }_n:\left[-1,1\right]\to {\mathcal{H}}_n,t\mapsto {\varphi }_n\left(t\right)={\displaystyle \underset{i=0}{\overset{n}{\sum }}}{L}_j\left(t\right)L_j(\cdot ).$

So from (3.6), we get

$\langle {\varphi }_n\left(s\right),{\varphi }_n\left(t\right)\rangle =\langle {\displaystyle \underset{i=0}{\overset{n}{\sum }}}{L}_i\left(s\right)L_i,{\displaystyle \underset{j=0}{\overset{n}{\sum }}}{L}_j\left(t\right)L_j\rangle ={\displaystyle \underset{j=0}{\overset{n}{\sum }}}{L}_j\left(s\right)L_j\left(t\right)=K_n\left(s,t\right).$ □

Now let us consider the set $\mathcal{X}={\left[-\mathrm{1,1}\right]}^d$. Define the high power Legendre polynomial kernel function $K_n\mathrm{<mo>\; :\; </mo>}\mathcal{X}\times \mathcal{X}\to ℝ$ as follows:

$K_n\left(x\mathrm{,}y\right)={\displaystyle \underset{i=1}{\overset{d}{\prod }}}{K}_n\left(x_i\mathrm{,}{y}_i\right)={\displaystyle \underset{i=1}{\overset{d}{\prod }}}{\displaystyle \underset{k=0}{\overset{n}{\sum }}}{L}_k\left(x_i\right)L_k\left(y_i\right)\mathrm{,}x=\left(x_1\mathrm{,}\cdots \mathrm{,}{x}_d\right)\mathrm{,}y=\left(y_1\mathrm{,}\cdots \mathrm{,}{y}_d\right)\mathrm{.}$ (3.7)

Let us introduce $H_n={\mathcal{H}}_n^{\otimes d}=\underset{d\text{-times}}{\underset{︸}{{\mathcal{H}}_n\otimes \cdots \otimes {\mathcal{H}}_n}}$ called the d--times tensor product of ${\mathcal{H}}_n$.

It’s known that $H_n$ is a real Hilbert space endowed with the inner product

${\langle f|g\rangle }_{H_n}={\displaystyle \underset{i=1}{\overset{d}{\prod }}}\langle f_i\mathrm{,}{g}_i\rangle \mathrm{,}f=f_1\otimes \cdots \otimes f_d\mathrm{,}g=g_1\otimes \cdots \otimes g_d\in H_n\mathrm{,}{f}_i\mathrm{,}{g}_i\in {\mathcal{H}}_n\mathrm{.}$ (3.8)

For $\left(x\mathrm{,}y\right)\in \mathcal{X}\times \mathcal{X}$, we have

$K_n\left(x\mathrm{,}y\right)={\displaystyle \underset{i=1}{\overset{d}{\prod }}}{K}_n\left(x_i\mathrm{,}{y}_i\right)={\displaystyle \underset{i=1}{\overset{d}{\prod }}}\langle {\varphi }_n\left(x_i\right)\mathrm{,}{\varphi }_n\left(y_i\right)\rangle ={\langle \underset{i=1}{\overset{d}{{\displaystyle \otimes }}}{\varphi }_n\left(x_i\right)\mathrm{<mo>\; |\; </mo>}\underset{i=1}{\overset{d}{{\displaystyle \otimes }}}{\varphi }_n\left(y_i\right)\rangle }_{H_n}\mathrm{.}$ (3.9)

Define now the function ${\Phi }_n\mathrm{<mo>\; :\; </mo>}\mathcal{X}\to H_n$ given by

${\Phi }_n\left(x\right)=\underset{i=1}{\overset{d}{{\displaystyle \otimes }}}{\varphi }_n\left(x_i\right)\mathrm{,}x=\left(x_1\mathrm{,}\cdots \mathrm{,}{x}_d\right)\mathrm{.}$ (3.10)

by substituting (3.10) in (3.9), we get

$K_n\left(x\mathrm{,}y\right)={\langle {\Phi }_n\left(x\right)|{\Phi }_n\left(y\right)\rangle }_{H_n}\mathrm{.}$ (3.11)

Hence $K_n$ is a kernel, with the feature map ${\Phi }_n$ and feature space $H_n$.

Now, applying Theorem 2.3 to the kernel $K_n$, we deduce the following result.

Corollary 3.1.1. The space $H_n$ is a RKHS with corresponding kernel $K_n$.

4. Application of Kernels in Classification Problem

The binary classifications means that given a date points $\mathcal{X}={\left(x_i\right)}_{1\le i\le L}\subset {ℝ}^d$ which are belonging to two classes. One is denoted Class(1), the other is denoted Class(−1). To each point $x_i$ we associate $y_i=\pm 1$ indicating to which class $x_i$ belongs. The points ${\left(x_i\right)}_{1\le i\le L}$ are called training points. The idea of SVM is to find an hyperplane ${\mathcal{H}}_S$ separating the two classes and construct a decision function f from which a new point can be classified (x belongs to Class(1) or x belongs to Class(−1)).

4.1. Support Vector Machine: Linearly Separable Classification

When the training samples $\mathcal{X}={\left(x_i\right)}_{1\le i\le L}\subset {ℝ}^d$ are linearly separable, we speak about a linear classification (i.e., there exists an hyperplane separating the two classes), the idea of SVM is the following:

Let us consider the set of training points, ${\left\{\left(x_i\mathrm{,}{y}_i\right)\right\}}_{1\le i\le L}$, where $x_i=\left(x_i^{\left(1\right)}\mathrm{,}\cdots \mathrm{,}{x}_i^{\left(d\right)}\right)\in {ℝ}^d$ and the corresponding labels $y_i\in \left\{-\mathrm{1,1}\right\}$. The first step is to find an hyperplane ${\mathcal{H}}_S$ in the space ${ℝ}^d$ separating the two classes. The second step is to construct the decision function f.

Support Vectors are the examples closest to the separating hyperplane ${\mathcal{H}}_S$ and the aim of SVM is to orientate this hyperplane in such a way as to be as far as possible from the closest members of both classes. For example in 2-dimensional space this means that we can draw a line on a graph of $x_i$ v.s $x_j$ separating the two classes. In high dimensional space ( $d>2$ ), the line will be replaced by an affine hyperplane ${\mathcal{H}}_S$, i.e., $\dim {\mathcal{H}}_S=d-1$ (see Figure 1).

Step.1.

Recall that any affine hyperplane is described by the equation

$w\cdot x+b=0,$

where “ $\cdot$ ” is the dot product in ${ℝ}^d$ and w is normal to the hyperplane. So we have to determinate the appropriate values of w and b for the hyperplane ${\mathcal{H}}_S$. If we now just consider the points that lie closest to the separating hyperplane, i.e., the Support Vectors (shown in circles in the diagram), then the two planes ${\mathcal{H}}_1$ and ${\mathcal{H}}_{-1}$ that these points lie on can be described by:

Figure 1. Separating hyperplane and marginal distance.

$x_i\cdot w+b=1\text{for}{\mathcal{H}}_1$ (4.1)

$x_i\cdot w+b=-1\text{for}{\mathcal{H}}_{-1}$ (4.2)

Referring to Figure 1, we define ${\delta }_1$ as being the distance from ${\mathcal{H}}_1$ to the hyperplane ${\mathcal{H}}_S$ and ${\delta }_2$ from ${\mathcal{H}}_{-1}$ to it. The hyperplane’s equidistance from ${\mathcal{H}}_1$ and ${\mathcal{H}}_{-1}$ means that $\delta ={\delta }_1={\delta }_2$. The quantity $\delta$ is known as the SVM’s margin. In order to orientate the hyperplane to be as far from the Support Vectors as possible, we need to maximize this margin. It is known from [1] that this margin is equal to

$\delta =\frac{1}{\Vert w\Vert }.$

Now the problem is to find w and b such that the marginal distance $\delta$ is maximal and for all $i=1,\cdots ,L$,

$w\cdot x_i+b\ge 1\text{for}x\in {\mathcal{H}}_1\text{and}w\cdot x_i+b\le -1\text{for}x\in {\mathcal{H}}_{-1}\mathrm{.}$ (4.3)

This is equivalent to the optimization problem under constraint

$\min \left(\frac{1}{2}{\Vert w\Vert }^2\right)\text{S}\text{.T}{y}_i\left(w\cdot x_i+b-1\right)\ge 0\forall i=\mathrm{1,}\cdots \mathrm{,}L\mathrm{,}$ (4.4)

which is in fact a quadratic programming optimization (Q.P-optimization). Using the Lagrange multipliers $\lambda =\left({\lambda }_1\mathrm{,}\cdots \mathrm{,}{\lambda }_L\right)$, where ${\lambda }_i\ge 0$ $\forall i=1,\cdots ,L$, the problem (4.4) will be equivalent to

$\underset{\lambda }{\max }\left[{\displaystyle \underset{i=1}{\overset{L}{\sum }}}{\lambda }_i-\frac{1}{2}\lambda H{\lambda }^{\text{T}}\right]\text{S}\text{.T}{\lambda }_i\ge \mathrm{0,}{\displaystyle \sum }{\lambda }_i{y}_i=\mathrm{0,}$ (4.5)

where

$H={\left(H_{i,j}\right)}_{1\le i,j\le L}={\left(y_i{y}_j{x}_i\cdot x_j\right)}_{1\le i,j\le L}.$

This is a convex quadratic optimization problem, and we run a QP--solver which will return $\lambda$. Thus we can deduce w and b which are given by [1]

$w={\displaystyle \underset{i=1}{\overset{L}{\sum }}}{\lambda }_i{y}_i{x}_i;b=\frac{1}{N_S}{\displaystyle \underset{s\in S}{\sum }}\left(y_s-{\displaystyle \underset{k\in S}{\sum }}{\lambda }_k{y}_k{x}_k\cdot x_s\right),$ (4.6)

where S the set of the support vectors $x_s$ (i.e., the vectors of indices i corresponding to ${\lambda }_i>0$ ) and $N_S$ is the number of support vectors.

Step.2.

The second step is to create the decision function f which determines to which class a new point belongs. From [1], the decision function is given by

$f\left(x\right)=sgn\left(y_i\left(w\cdot x_i+b\right)-1\right)\in \left\{\pm 1\right\}\mathrm{.}$ (4.7)

Thus for a new data x, $f\left(x\right)=1$ means x belongs to the first class and $f\left(x\right)=-1$ means that x belongs to the second class.

In practise, in order to use an SVM to solve a linearly separable, binary classification problem we need to:

1) Create the matrix $H=\left(H_{i\mathrm{,}j}\right)\in M_L\left(ℝ\right)$, where $H_{i,j}=y_i{y}_j{x}_i\cdot x_j$.

2) Find $\lambda$ so that

${\displaystyle \underset{i=1}{\overset{L}{\sum }}}{\lambda }_i-\frac{1}{2}\lambda H{\lambda }^{\text{T}}$

is maximized, subject to the constraints ( ${\lambda }_i\ge 0$ and $\forall i$, ${\displaystyle {\sum }_{i=1}^L}{\lambda }_i{y}_i=0$ ).

This is can be done using a QP solver.

3) Calculate $w={\displaystyle {\sum }_{i=1}^L}{\lambda }_i{y}_i{x}_i$.

4) Determine the set of Support Vectors S by finding the indices such that ${\lambda }_i>0$.

5) Calculate $b=\frac{1}{N_S}{\displaystyle {\sum }_{s\in S}}\left(y_s-{\displaystyle {\sum }_{k\in S}}{\lambda }_k{y}_k{x}_k\cdot x_s\right)$.

6) Each new point $x^{\prime }$ is classified by evaluating $f\left(x^{\prime }\right)=sgn\left(w\cdot x^{\prime }+b\right)$.

4.2. SVM for Data That Is Not Fully Linearly Separable

In order to extend the SVM methodology to handle data that is not fully linearly separable, we relax the constraints (4.3) slightly to allow for misclassified points. This is done by introducing a positive slack variable ${\xi }_i\ge 0$, $i=1,\cdots ,L$

$w\cdot x_i+b\ge 1-{\xi }_i\text{for}{y}_i=+\mathrm{1,}$

$w\cdot x_i+b\le -1+{\xi }_i\text{for}{y}_i=-1.$

which can be combined into:

$y_i\left(w\cdot x_i+b\right)-1+{\xi }_i\ge 0\forall i=1,\cdots ,L.$ (4.8)

In this soft margin SVM, data points on the incorrect side of the margin boundary have a penalty that increases with the distance from it. As we are trying to reduce the number of misclassifications, a sensible way to adapt our objective function (4.8) from previously, is to find

$\min \left(\frac{1}{2}{\Vert w\Vert }^2+C{\displaystyle \underset{i=1}{\overset{L}{\sum }}}{\xi }_i\right)\text{S}\text{.T}{y}_i\left(w\cdot x_i+b\right)-1+{\xi }_i\ge 0\forall i=\mathrm{1,}\cdots L\mathrm{,}$ (4.9)

where the parameter C controls the trade-off between the slack variable penalty and the size of the margin.

Similarly to what have been done in the previous case, the Lagrange method leads to the following convex quadratic optimization problem

$\underset{\lambda }{\max }\left[{\displaystyle \underset{i=1}{\overset{L}{\sum }}}{\lambda }_i-\frac{1}{2}\lambda H{\lambda }^{\text{T}}\right]\text{S}\text{.T}0\le {\lambda }_i\le C\mathrm{,}{\displaystyle \sum }{\lambda }_i{y}_i=0.$ (4.10)

We run a QP-solver which will return $\lambda$. The values of w and b are calculated in the same way as (4.6), though in this instance the set of Support Vectors used to calculate b is determined by finding the indices i for which $0<{\lambda }_i<C$.

In practise, we need to:

1) Create the matrix H, where $H_{i,j}=y_i{y}_j{x}_i\cdot x_j$.

2) Select a suitable value for the parameter C which determines how significantly misclassifications should be treated.

3) Find $\lambda$ satisfying

${\displaystyle \underset{i=1}{\overset{L}{\sum }}}{\lambda }_i-\frac{1}{2}\lambda H{\lambda }^{\text{T}}\text{is}\text{maximized}\text{S}\text{.T}0\le {\lambda }_i\le C\forall i\text{and}{\displaystyle \underset{i=1}{\overset{L}{\sum }}}{\lambda }_i{y}_i=0.$

This is done using a QP-solver.

4) Calculate $w={\displaystyle {\sum }_{i=1}^L}{\lambda }_i{y}_i{x}_i$.

5) Determine the set of Support Vectors S by finding the indices such that $0<{\lambda }_i<C$.

6) Calculate $b=\frac{1}{N_S}{\displaystyle {\sum }_{s\in S}}\left(y_s-{\displaystyle {\sum }_{k\in S}}{\lambda }_k{y}_k{x}_k\cdot x_s\right)$.

7) Each new point $x^{\prime }$ is classified by evaluating

$f\left(x^{\prime }\right)=sgn\left(w\cdot x^{\prime }+b\right)=sgn\left[\left({\displaystyle \underset{i=1}{\overset{L}{\sum }}}{\lambda }_i{y}_i{x}_i\cdot x^{\prime }\right)+b\right]\mathrm{.}$

4.3. Non-Linear SVM

In the case when the data points are not linearly separable, i.e., there is no hyperplane separating data in two classes, we have to insert some modification on the data in order to obtain a linearly separable points. This is based on the kernel functions. It is worth noting that in the case of linearly separable data, the decision function requires only the dot product of the data points $x_i$ and the input vector x with each $x_i$. In fact, when applying the SVM technic to linearly separable data we have started by creating a matrix H and the scalar b from the dot product of our input variables

$H_{i,j}=y_i{y}_j{x}_i\cdot x_j;b=\frac{1}{N_S}{\displaystyle \underset{s\in S}{\sum }}\left(y_s-{\displaystyle \underset{k\in S}{\sum }}{\lambda }_k{y}_k{x}_k\cdot x_s\right).$

This is an important constatation for the Kernel Trick. In fact the dot product will be replaced by such a kernel which also a positive definite function. The idea is based on the choice of such kernel function k and the trick is to maps the data into a high-dimensional feature space $\mathcal{H}$ via a transformation $\varphi$ related to k, in such way that the transformed data are linearly separable. $\varphi$ is called feature map $\varphi \mathrm{<mo>\; :\; </mo>}\mathcal{X}\to \mathcal{H}$. When this hyperplane is back into the original space it describes a surface.

Similarly to the previous section, we adopt the same procedure of separation at the level of the feature space $\mathcal{H}$. This leads to the following steps.

1) Choose a kernel function k.

2) Create the matrix H, where $H_{i\mathrm{,}j}=y_i{y}_{j}k\left(x_i\mathrm{,}{x}_j\right)$.

3) Choose how significantly misclassifications should be treated, by selecting a suitable value for the parameter C.

4) Determine $\lambda$ so that

${\displaystyle \underset{i=1}{\overset{L}{\sum }}}{\lambda }_i-\frac{1}{2}\lambda H{\lambda }^{\text{T}}$

is maximal under the constraint $0\le {\lambda }_i\le C$ $\forall i$ and ${\displaystyle {\sum }_{i=1}^L}{\lambda }_i{y}_i=0$.

This is can be done by using a QP-solver.

5) Determine the set of Support Vectors S by finding the indices such that $0<{\lambda }_i<C$.

6) Calculate $b=\frac{1}{N_S}{\displaystyle {\sum }_{s\in S}}\left(y_s-{\displaystyle {\sum }_{i\in S}}{\lambda }_i{y}_{i}k\left(x_i\mathrm{,}{x}_s\right)\right)$.

7) Each new point $x^{\prime }$ is classified by evaluating

$f\left(x^{\prime }\right)=sgn\left(w\cdot x^{\prime }+b\right)=sgn\left[\left({\displaystyle \underset{i=1}{\overset{L}{\sum }}}{\lambda }_i{y}_{i}k\left(x_i\mathrm{,}{x}^{\prime }\right)\right)+b\right]\mathrm{.}$

Note that in general, the feature map $\varphi$ is unknown so w is also unknown. But we don’t need it! We need only the values of the kernel at the training points (i.e., $k\left(x_i\mathrm{,}{x}_j\right)$ for all $i\mathrm{,}j$ ) to know b, and $k\left(x_i\mathrm{,}{x}^{\prime }\right)$ to determine the values of the decision function f at the input vector $x^{\prime }$.

5. Numerical Simulations

Dataset of female patients with minimum twenty one year age of Pima Indian population has been taken from UCI machine learning repository. This dataset is originally owned by the National institute of diabetes and digestive and kidney diseases. In this dataset, there are total 768 instances classified into two classes: diabetic and non diabetic with eight different risk factors: Pregnancies, Glucose, Blood Pressure, Skin Thickness, Insulin, BMI, Diabetes Pedigree Function and Age. To diagnose diabetes for Pima Indian population, performance of all kernels is evaluated upon parameters like Accuracy, precision, recall score, F₁ score and execution time.

Before giving experiment results, we would like to recall some characteristics of the confusion matrix (Table 1) and related metric evaluation.

5.1. Terminology and Derivations from a Confusion Matrix

Table 1. Confusion Matrix.

where:

- (TP) is the number of True Positive cases (real positive cases and detected positive),

- (TN) is the number of True Negative cases (real negative cases and detected negative),

- (FP) is the number of False Positive cases (real negative cases and detected positive),

- (FN) is the number of False Negative cases (real positive cases and detected negative),

- (PP) is the number of Predicted Positive cases $\text{PP}=\text{TP}+\text{FP}$,

- (PN) is the number of Predicted Negative cases $\text{PN}=\text{FN}+\text{TN}$,

- (RP) is the number of Real Positive cases $\text{RP}=\text{TP}+\text{FN}$,

- (RN) is the number of Real Negative $\text{RN}=\text{FP}+\text{TN}$,

- The Total Population is given by

$Tp=\text{PP}+\text{PN}=\text{RP}+\text{RN}\mathrm{.}$

These are some metrics used in order to compare performance of Legendre polynomial kernel with linear, rbf and polynomial kernels.

- Precision (or positive predictive value PPV) has been used to determine classifier’s ability that provides correct positive predictions of diabetes.

$\text{PPV}=\frac{\text{TP}}{\text{TP}+\text{FP}}\mathrm{.}$

- Recall score (or true positive rate or sensitivity) is used in our work to find the proportion of actual positive cases of diabetes correctly identified by the classifier used.

$\text{TPR}=\frac{\text{TP}}{\text{RP}}=\frac{\text{TP}}{\text{TP}+\text{FN}}\mathrm{.}$

- Precision and recall score provide F₁ score, so this score takes into account of both. It is the harmonic mean of precision and sensitivity:

${\text{F}}_{\text{1}}=\frac{\text{2PPV}\times \text{TPR}}{\text{PPV}+\text{TPR}}\mathrm{.}$

- Accuracy (ACC) is the ratio of true positives and true negatives to all positive and negative observations. In other words, accuracy tells us how often we can expect our machine learning model will correctly predict an outcome out of the total number of times it made predictions.

$\text{ACC}=\frac{\text{TP}+\text{TN}}{\text{RP}+\text{RN}}=\frac{\text{TP}+\text{TN}}{\text{TP}+\text{TN}+\text{FP}+\text{FN}}\mathrm{.}$

5.2. Numerical Results

Since Legendre polynomial kernel is defined on ${\left[-\mathrm{1,1}\right]}^d$, a scaling procedure is needed in order to make data in $\left[-\mathrm{1,1}\right]$. For this, we suggest the following transformation $z_i^{\left(j\right)}=\frac{2x_i^{\left(j\right)}-\left(M_j+m_j\right)}{M_j-m_j},j=1,\cdots ,d,i=1,\cdots ,L$, where $M_j={\max }_{1\le i\le L}{x}_i^{\left(j\right)};m_j={\min }_{1\le i\le L}{x}_i^{\left(j\right)}.$

The confusion matrices corresponding to each kernels mentioned above are given in Figures 2-5, where the test size is 0.05 and the penalty coefficient C= 0.01.

Figure 2. Polynomial Legendre kernel.

Figure 3. Liner kernel.

Figure 4. Rbf kernel.

Figure 5. Polynomial kernel.

In order to show the powerful separation properties of the kernel defined by (3.1), our numerical simulations were carried out on the diabetes detection model mentioned above. In this example we apply SVM with different kernels in Pima Indian diabetes dataset in order to compare the performance of the Legendre polynomial kernel with linear, rbf, polynomial kernels with respect to their Accuracy, Precision, Recall score, F₁ score and Execution time (see Table 2).

Table 2. Numerical results.

The programs were implemented in Python.3.7 a Windows 7 computer with 3G memory. The test size is equal to 0.2 and the penalty is taken to be C= 0.001.

5.3. Conclusion

Form the comparative table above, it is clear that the polynomial Legendre kernel have a good separation property with a good precision and accuracy w.r.t the classical predefined kernel in Python. Essentially, we have shown that it is not necessary to have an RKHS with an infinite dimension in order to separate by an hyperplane all dataset in the feature space. In fact we can obtain a good classification with non big degree $N=20$. The more N increases, the more we obtain a better separation. The only disadvantage is the time required to fit the model with the polynomial Legendre kernel. The idea used here can be generalized with arbitrary sequence of orthogonal polynomials in order to get new kernel functions. The performance of separation property depends on the polynomials sequence and it should be tested on some examples of dataset.

Acknowledgements

The authors gratefully acknowledge Qassim University, represented by the Deanship of Scientific Research, for the support for this research.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Cortes, C. and Vapnik, V. (1995) Support-Vector Networks. Machine Learning, 20, 273-297. https://doi.org/10.1007/BF00994018
[2]	Chatterjee, R. and Yu, T. (2017) Generalized Coherent States, Reproducing Kernels and Quantum Support Vector Machines. arXiv:1612.03713v2.
[3]	Abbassa, N., Abdessamad, A. and Bahri, S.M. (2019) Regularized Jacobi Wavelets Kernel for Support Vector Machines. Statistics, Optimization & Information Computing, 7, 669-685. https://doi.org/10.19139/soic-2310-5070-634
[4]	Jakkula, V. (2010) Tutorial on Support Vector Machine (SVM). School of EECS, Washington State University, Pullman.
[5]	Hastie, T., Tibshirani, R. and Friedman, J. (2009) The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer-Verlag, New York. https://doi.org/10.1007/978-0-387-84858-7
[6]	Aronszajn, N. (1950) Theory of Reproducing Kernels. Transactions of the American Mathematical Society, 686, 337-404. https://doi.org/10.1090/S0002-9947-1950-0051437-7
[7]	De Vito, E., Umanità, V. and Villa, S. (2011) An Extension of Mercer Theorem to Vector-Valued Measurable Kernels. arXiv:1110.4017v1.
[8]	Rebei, H., Riahi, A. and Chammam, W. (2022) Hankel Determinant of Linear Combination of the Shifted Catalan Numbers. Multilinear Algebra.