domain: math stat info

text:
Mme Avec Eux

Laurence Broze

M Olivier

M Baba Thiam

Mme Mme Aurore Lavigne

Mme Sophie Dabo

Ophélie Guin

M Aboubakar Amiri

Mme M Camille Sabbah

Amélie Zill

Mme Mylène

Cantelli Uniforme

Risque Garanti

Complexité De

Keywords: Machine learning, Margin multi category classifiers, Uniform Glivenko-Cantelli, Guaranteed risk, Rademacher complexity

En tout premier lieu, je remercie le bon Dieu, Allah le tout puissant, de m'avoir donné la force pour survivre, la patience ainsi que le courage pour dépasser toutes les difficultés qui m'ont immensément guidé dans l'achèvement de cette thèse.

Un grand merci à mon directeur de thèse Monsieur Nicolas Wicker professeur à l'université de Lille, et à mon co-directeur Monsieur Yann Guermeur, Directeur de

First and foremost, I thank God almighty, Allah for giving me the strength to survive, patience, as well as the courage to overcome all difficulties that has immensely guided me in finishing this thesis.

I would like to express my sincere appreciation to my thesis advisor Nicolas Wicker professor at the University of Lille, and to my co-director Mr Yann Guermeur, Research Director at the CNRS, assigned to LORIA INRIA Nancy, who accompanied me during these years of work. I am grateful for the opportunity to do this thesis that you were able to grant me by allowing me to realize my dream, that of becoming a doctor in applied mathematics. Thank you Nicolas, thank you Yann, for everything and especially for your human and scientific qualities. I will never forget your kindness, your patience, your generosity, your research spirit, your effective comments and your valuable support during these years. Thank you Yann for the invitations to nancy, this has been a great pleasure working with you.

Many thanks to the members of the jury, who have done me the honor to study my work carefully: Khalid Benabdeslem and Faïcel Chamroukhi for having accepted to be rapporteurs of this thesis. I am also grateful to Marianne Clausel and Sophie Dabo-Niang for their commitment to take part in my jury committee as examiners.

My gratitude also goes to the foundation Walid Joumblatt for the university studies to give me the certificate of scholarship, and I thank Mr. Alaa Terro who facilitated all the administrative procedures. I would like to express my sincere thanks to all the teachers who taught me in the Lebanese university and university of Nice Sophia Antipolis and who by their skills supported me in the pursuit of my studies.

I thank all the staff of the Laboratory especially a big thank you to the members of the Probability and Statistics teams of the Paul Painlevé Laboratory in which I flourished during these years.

I would like to thank the secretariats Ludivine Fumery, Fatima Soulaimani, Soledad Cuenca for the order of missions and the computer scientists Sebastien Huart and Mohammed Khabzaoui. I would also like to thank the Executive Secretary Sabine Hertsoen, the Secretariat of Master 2 and PHD Student Aurore Smets and the Head of the printing Frédérique Maréchal for their kindness. I take these few lines to express my gratitude.

I would like to thank Mr. Nicolas Wicker who gave me the opportunity to take charge of teaching at the University of Lille 1. I then thank the University of Lille 3 for accepting me for a post ATER to teach during my thesis which was a pleasant and wonderful experience.

I extend a big thank you to the members of Lille 3 University (UFR MIME) especially with the teachers I taught with them, Mrs. Laurence Broze, Mr. Olivier Torres, Mr. Baba Thiam, Mrs. Aurore Lavigne, Ms. Sophie Dabo, Mrs. Ophélie Guin, Mr. Aboubakar Amiri, Mr. Camille Sabbah, Mrs. Amélie Zill and Mrs. Mylène Maida.

During this thesis, I had the pleasure of exchanging in good humor with many research professors and with many doctoral students. My gratitude goes to my friends in France for their support and for all the times we have spent together during these years, and I extend a big thank you to my friends in Lebanon (Amal Hamieh, Jihan, Joyce, Hiba, Diala, ...) for their encouragement and moral support ... simply for their friendship.

I warmly thank my family, my parents, my brothers (Adel, Khalil), my sisters (Nadima, Nour) and my grandparents who allowed me to lead these long studies without constraint and have always supported and encouraged me in this long journey and helped in the life. Thank you for your endless love, your encouragement and your emotional support. Thanks to the invaluable sacrifices you have given me, you have desired so much that I reach this goal. My success is for you! I would be grateful to you all my life, may God grant you long life in health! Finally, I reserve the last words of these thanks to my love OMAR, thank you darling for your constant support in the difficult moments of my work, thank you for your advice, your encouragement, your listening and your patience throughout these years.

Résumé

La théorie statistique de l'apprentissage est un domaine de la statistique inférentielle dont les fondements ont été posés par Vapnik à la fin des années 60. Il est considéré comme un sous-domaine de l'intelligence artificielle. Dans l'apprentissage automatique, les machines à vecteurs de support (SVM) sont un ensemble de techniques d'apprentissage supervisé destinées à résoudre des problèmes de discrimination et de régression.

Dans cette thèse, notre objectif est de proposer deux nouveaux problèmes d'apprentissage statistique: un portant sur la conception et l'évaluation d'une extension des SVM multiclasses et un autre sur la conception d'un nouveau noyau pour les machines à vecteurs de support.

Dans un premier temps, nous avons introduit une nouvelle machine à noyau pour la reconnaissance de modèle multi-classe: la machine à vecteur de support hyperbolique. Géométriquement, il est caractérisé par le fait que ses surfaces de décision dans l'espace de redescription sont définies par des fonctions hyperboliques. Nous avons ensuite établi ses principales propriétés statistiques. Parmi ces propriétés nous avons montré que les classes de fonctions composantes sont des classes de Glivenko-Cantelli uniforme, ceci en établissant un majorant de la complexité de Rademacher. Enfin, nous établissons un risque garanti pour notre classifieur.

Dans un second temps, nous avons créé un nouveau noyau s'appuyant sur la transformation de Fourier d'un modèle de mélange gaussien. Nous procédons de la manière suivante: d'abord, chaque classe est fragmentée en un nombre de sous-classes pertinentes, ensuite on considère les directions données par les vecteurs obtenus en prenant toutes les paires de centres de sous-classes d'une même classe. Parmi celles-ci, sont exclues celles permettant de connecter deux sous-classes de deux classes différentes. On peut aussi voir cela comme la recherche d'invariance par translation dans chaque classe. Nous l'avons appliqué avec succès sur plusieurs jeux de données dans le contexte d'un apprentissage automatique utilisant des machines à vecteurs support multi-classes.

Mots-clés. Apprentissage statistique, Classifieur multi-classe à marge, Glivenko-First, we introduced a new kernel machine for multi-class pattern recognition : the hyperbolic support vector machine. Geometrically, it is characterized by the fact that its decision boundaries in the feature space are defined by hyperbolic functions. We then established its main statistical properties. Among these properties we showed that the classes of component functions are uniform Glivenko-Cantelli, this by establishing an upper bound of the Rademacher complexity. Finally, we establish a guaranteed risk for our classifier.

Second, we constructed a new kernel based on the Fourier transform of a Gaussian mixture model. We proceed in the following way: first, each class is fragmented into a number of relevant subclasses, then we consider the directions given by the vectors obtained by taking all pairs of subclass centers of the same class. Among these are excluded those allowing to connect two subclasses of two different classes. We can also see this as the search for translation invariance in each class. It successfully on several datasets in the context of machine learning using multiclass support vector machines.

xix

List of Figures

Outline of the thesis

This thesis is organized in four main chapters that can be read independently of the others to some extent.

Chapter 1 is an autonomous introductory chapter, we will first present the state of the art in the field of statistical learning introducing the scientific context: supervised and unsupervised learning. Then we will present the problem of binary classification in both cases: linearly and non-linearly separable, and we will discuss the problem of multi-class classification. Finally, we will present the capacity measures among these, the Rademacher complexity.

Chapter 2, will introduce fundamental elements of kernel theory. The goal of this chapter is to explain the interest of kernel methods through motivating examples, to introduce essential notions such as kernels, positive semidefinite property of kernel function and kernel matrix and reproducing kernel Hilbert spaces. We also give the properties of the operations on the kernel function that will provide a new kernel. Finally we provide several examples of kernels that includes a large number of widely used kernels such as the polynomial kernels and the Gaussian kernel.

Chapter 3, we will introduce a new kernel machine for multi-class pattern recognition: the hyperbolic support vector machine. Its decision boundaries in the feature space are defined by hyperbolic functions. We will establish its main statistical properties.

Chapter 4, we will construct a novel kernel function obtained as a Fourier transform of a Gaussian mixture model with the purpose of detecting translation invariance inside classes, which is applied successfully on several datasets in the context of machine learning using multiclass support vector machines (MSVM).

Chapter 1 Preliminaries

Abstract In this chapter, some concepts, background methods and results are presented. We begin first with an introduction about the data classification method. Then we present the problem of discrimination. Support vector machines (SVM) are then presented in two steps: the algorithms of the SVM bi-classes and the use of SVM to realize polytomies. Finally, we presented the capacity measures that will help us in chapter 3.

Introduction

Statistical learning [35] is a paradigm that combines a set of methods and algorithms for extracting relevant information from the data, or learning behaviors from examples. Its applications are numerous and present in fields as varied as the search for information in large data sets (thematic segmentation of text, image mining, etc.) or biology (behavior of population, DNA chips, etc.). We distinguish two main issues in statistical learning: supervised learning on the one hand, and unsupervised learning on the other hand. Supervised learning is a type of machine learning that involves establishing rules of behaviour from a database containing examples of previously labelled cases. More precisely, this database is a set of input-output pairs {(x i , y i )} 1 i n ∈ X × Y where X is the input space and Y is the output space. The objective is then to learn how to predict, for any new input x, the output y.

According to the structure of Y we can be in two typical situations:

• When the space Y (which we will also call space of predictions) is finite, we call this task a problem of discrimination or classification, which is to assign a label to each input [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF]. A function from X to Y is usually called a classifier or a decision rule.

• When Y is a continuous set, typically Y = R, we are talking about problem of regression [START_REF] Györfi | A distribution-free theory of nonparametric regression[END_REF], the prediction function is then called a regressor.

Preliminaries

The unsupervised learning theory is a branch of machine learning that deals with the case where only the inputs {x i } 1 i n are available, without the outputs, i.e that learns from test data that has not been labeled. The most important problem is then to partition the data, also called clustering. This is to group the observations into different homogeneous groups (clusters), by ensuring that the data in each subset share common characteristics.

As part of this thesis, we focus specifically on the supervised learning problem.

Data classification methods

Data classification sets the basic steps for anticipating corresponding labels of new points on the basis of a pre-defined set of labeled training points specially in the domain of machine learning and statistics. It is considered to be one of the supervised learning problems and it is applied in various domains such as document classification, handwriting recognition, internet search engines, etc.

Instance-based learning methods, neural networks, decision trees, support vector machines and many other methods have been developed to deal with data classification problems.

Instance-based learning is a family of learning algorithms that compares instances seen in training, which have been stored in memory with new problem instances, instead of performing explicit generalization. The idea is based on the assumption that features which are used to describe labels are similar when instances are close. It is reasonable to use labels of closest instances to predict labels of new instances. However, it is tough to understand the relationship between labels and features from the unstructured algorithms. Such methods are very efficient to manage real life problems, for example handwritten digits and satellite image scenes. For example the k-nearest neighbor (k-NN) method, given a training set, to predict the label of a new data point, one assigns k closest points of the new point in the training set, and labels it with the majority label in the k closest neighbors. The closest neighbors are found with a distance which can be seen as a similarity measurement. For example, the distance can be chosen as the L p distance or the Minkowski distance. k is usually chosen using cross-validation [4] in real applications. A detailed discussion of instance based methods can be found in [ [1], [2], [3]].

Neural Networks (NNets) were firstly defined by the neurophysiologist Warren Mc-Culloch and the logician Walter Pitts in 1943. NNets are basically modeled referring to the model of the neural structure in the brain. In human brain, a neuron collects signals from other neurons through structures called dendrites, and sends out electrical activities through an axon which has thousands of branches. A synapse which is at the end of each branch converts activities from the axon to the connected neurones. The brain can perform highly complex computations due to the complication of the neurons networks. We focus on NNets which contain no cycles, called feedforward networks. NNets can be described as directed acyclic graphs, in which the nodes correspond to neurons and edges correspond to links between them. Each node accepts a weighted sum of outputs of the connected nodes related to the coming edges as input. NNets may contain several layers of nodes. In recent years, NNets have proven to be extremely proficient for numerous learning tasks because of the increased computational power to handle large datasets, and developments of new algorithms. Networks with multiple hidden layers, or what is called "Deep networks", have been successfully applied to many practical domains. A detailed overview can be found in [ [5], [6]].

Decision trees (DT) are tree models that describe the classification paths for training data, which are constructed by nodes and directed edges. DT tasks are an admired method for various machine learning. A node is called a leaf node if it has no children. A leaf node presents a label of one of the classes, otherwise it is an internal node. Each internal node shows a rule for splitting the input space by one of the features or a predefined criterion. A classification tree predicts the label of a new point by going from the root node of the tree model to a leaf. A general method for constructing a classification tree is a recursive procedure that allows you to choose the "best characteristic" on each node, then split the feature space in reference of the "best feature". The best decision is made at each node by following this way. Applying it recursively, until all learning points are well classified or no proper feature can be used as a node, a classification tree is obtained. Occasionally, classification trees may discriminate training data well, considering a high prediction error. However, limiting the number of nodes generated helps avoiding errors. A commonly used methodology in practice is to prune the tree after it is built. Algorithms for building a decision tree include C4.5 [9], ID3 [10] , and CART [11]. Classification trees are simple but powerful. With each division on each node, the feature space partition is fully described, which makes the classification path more readable. Yet, the partition is sensitive to small changes in input data points. Due to the hierarchical nature of the process, small changes can guide to a significantly different series of splits.

The random forest (RF) algorithm [6] [7], proposed in 2001 by Leo Breiman and Adèle Cutler, a general purpose classification and regression method has been extremely successful. The approach, which combines several randomized decision trees and aggregates their predictions by averaging, has shown excellent performance in settings where the number of variables is much larger than the number of observations. These trees are grown separately with randomly selected subsets of input data points and randomly selected subsets of variables. To predict a label of a new data point, RF takes the majority vote from the predicted labels of all trees therein. RF can handle many input variables without doing a 1. Preliminaries feature selection that's why it is said to run efficiently on large scale datasets and that is one of its greatest advantages. It can approximate missing data effectively as well, even when the missing data correspond to a large portion of the dataset. Interestingly, RF provides a measure of the importance of each variable. Support vector machines (SVM) aim to construct a linear separation maximizing the margin between data belonging to different classes. They can be applied to a nonlinear separation problem by using a kernel function to transform the input space to a higher feature space (see "kernel trick", based on Mercer's Theorem [START_REF] Mercer | XVI. Functions of positive and negative type, and their connection the theory of integral equations[END_REF]) which makes the problem linear. SVMs have already been well studied and achieve high accuracy in many applications. A detailed discussion of SVMs can be found in [ [12], [13], [14], [15], [16], [17]].

In this thesis, we are interested among these methods, in the classification problem based on the support vector machine, we give a detailed introduction of this method in the next section.

Support Vector Machines

In machine learning, SVM are supervised learning models with associated learning algorithms that analyze data used for classification and regression analysis. SVM were first invented by Vapnik and Chervonenkis [ [17]]. They have been widely studied by many researchers [ [18], [19], [12], [20], [21], [22], [23], [24], [25], [26]]. In 1992, Bernhard E. Boser, Isabelle M. Guyon and Vladimir N. Vapnik suggested a way to create non-linear classifiers by applying the kernel trick to maximum-margin hyperplanes [27]. The current standard incarnation (soft margin) was proposed by Corinna Cortes and Vapnik in 1993 and published in 1995 [28].

General operating principle of the SVMs

The perceptron is an algorithm for supervised learning of binary classifiers . A SVM, as a perceptron, finds a linear separator between the data points of two differents classes. In general, there may be several separators possible between classes (assuming the problem linearly separable) and a perceptron has no preference among them. In the SVM, however, we make a particular choice among all the possible separators: we want the one with the maximum "margin" [29].

Basic knowledge: Hyperplane, margin and support vectors

For two classes of examples given, the goal of SVM is to find a classifier that will separate the data and maximize the distance between these two classes. With SVM, this classifier is a linear classifier called hyperplane. In the following figure, we determine a hyperplane that separates the two sets of points. There are many hyperplanes that separate the two classes of examples. The principle of the SVM is to choose the one that will maximize the minimum distance between the hyperplane and the training examples (i.e. the distance between the hyperplane and the support vectors), this distance is called the margin [30]. Intuitively, having a wider margin provides more security when classifying a new example. Moreover, if we find the classifier that behaves best with respect to the learning data, it is clear that it will also be the one that will best classify the new examples. In the following figure, the right side shows us that with an optimal hyperplane, a new example remains well classified so that it falls in the margin. We see on the left side that with a smaller margin, the example is misclassified.

Preliminaries

Linearity and non-linearity

Among the SVM models, one can observe linearly separable cases and nonlinearly separable cases. The first ones are the simplest of SVM because they allow to easily find the linear classifier. In most real problems there isn't possible linear separation between the data, the maximum margin classifier can not to be used because it only works if the classes of training data are linearly separable. To overcome the disadvantages of non-linearly separable case, the idea of SVM is to change the data space. The nonlinear transformation of the data can allow a linear separation of the examples in a new space. So we will have a change of dimension. This new space is called "feature space" (redescription space). Indeed, intuitively, the larger the dimension of the redescription space, the greater the probability of finding a separating hyperplane between examples is high. This is illustrated by the following figure 1.6. So we have a transformation of a problem of nonlinear separation in the representation space into a problem of linear separation in a space of redescription of larger dimension. This nonlinear transformation is performed via a kernel function. In practice, some families of kernel functions are known and it returns to the user of SVM to perform tests to determine which one is best for their application. Examples of the following kernel: polynomial, Gaussian, sigmoïd and Laplacian.

We consider problems of discrimination in C categories. Let X denote the description space and Y the set of categories. Each object is represented by its description x ∈ X and the set Y of the categories y can be identified with the set of indices of the categories:

[ [1, C ]
].

SVM for binary classification

In the first part, we will talk about the hard-SVM which are used for linearly separable training sets, next we introduce soft-SVM for non-linearly separated datasets. Finally we present Soft-SVM with kernels.

Hard-SVM

In this section, we consider a binary classification problem (C = 2), for which the set of categories Y is identifiable at {-1, +1}. Assume that we are given n observations

(x 1 , y 1 ), • • • , (x n , y n ) ∈ X × {-1, 1}.
Given a test point x ∈ X , the goal is to guess the corresponding y ∈ {-1, +1} based on the n observations. Consider for instance X = R d , with d ∈ N . A way of fulfilling this goal is to find the "maximum-margin hyperplane" that divides the group of points x i for which y i = 1 from the group of points for which y i = -1, which is defined so that the distance between the hyperplane and the nearest point x i from either group is maximized.

We define the function g be a classifier, with real values from a class of functions G by: g(x) = w, x + b, where w ∈ R d is the normal vector to the hyperplane and b ∈ R is its relative position to the origin.

The separating hyperplane defined by {x ∈ R d : g(x) = 0}. Thus a new point x ∈ R d is assigned to the prediction function dr g defined as

dr g (x) = sgn(g(x)),
with sgn() is the the sign function of its argument.

We assume that the two classes are linearly separable, which means that there is a hyperplane able to classify the data. However, there is usually an infinity of separator hyperplanes that classify the data correctly. From all these hyperplanes, we seek to find a hyperplane that maximizes the margin between the samples and the separating hyper-plane.

One approach is to maximize the margin between two parallel hyperplanes that separate the two classes of data. This method is called the Hard-SVM. Since the separating hyperplane is g(x) = 0, the supporting hyperplane can be written as g(x) k for class y i = 1 and g(x) -k for class y i = -1, in which k > 0. After a rescaling, we require the supporting hyperplane to be g(x)

1 for class y i = 1 and g(x) for class y i = -1. Geometrically, the distance between these two hyperplanes is 2/ w 2 , so to maximize the distance between the planes (margin) is equivalent to minimize w 2 /2. Therefore, we obtain the following Hard-SVM formulation:

   min w,b 1 2 w 2 subject to y i ( w, x i + b) 1, i = 1, . . . , n.
(1.1) In general, it is also not possible to find a linear separator in the redescription space. It may also be that samples are mislabeled and that the separating hyperplane is not the best solution to the problem of classification. In 1995, Corinna Cortes and Vladimir Vapnik [12] proposed a technique called the Soft-SVM, which tolerates bad classifications.

Soft-SVM

If the two classes are not separable linearly, these two classes are found mixed around the separation hyperplane. The technique of the Soft-margin looks for a separator hyperplane 1. Preliminaries that minimizes the number of errors (points on the wrong side of the supporting hyperplanes) by introducing slack variables ξ i , which make it possible to release the constraints on the learning vectors. Let ξ i > 0, i = 1, . . . , n, be slack variables. The constraints in the Hard-SVM formulation can be reformulated as: We see that a slack variable ξ i penalizes an error vector (see Figure 1.8). Therefore the optimization problem in the case of non-separable data (Soft-SVM) is [12,13,26]:

y i ( w, x i + b) + ξ i 1, ξ i 0, i = 1, . . . , n.
             min w,b,ξ 1 2 w 2 + ζ n i=1 ξ i subject to y i ( w, x i + b) + ξ i 1, i = 1, . . . , n ξ i 0, i = 1, . . . , n, (1.2)
where ζ is a penalty parameter for misclassified points that compromise between margin width and misclassified points.

In constraints of Problem (1.2), since ξ i 0 and ξ i 1 -y i ( w, x i + b), we get an equality as follows:

ξ i = max{0, 1 -y i ( w, x i + b)}. (1.3)
So we have two situations:

• No error: ξ i = 0, which means that the i-th point is either correctly classified,

• Error:

ξ i = 1 -y i ( w, x i + b).
Using Eq. 1.3, we can now formulate the problem of optimization 1.2 as an unconstrained optimization problem:

min w,b 1 2 w 2 + ζ n i=1 max{0, 1 -y i ( w, x i + b)}. (1.4)
The term max{0, 1 -y i ( w, x i + b) is called "hinge loss" in statistics. From the problem (1.4), the SVM can be considered as regularized minimization problems where w 2 is a part of the regulation. In general, we can write SVM as follows,

min w,b 1 2 w 2 + ζ n i=1 l (y i , ( w, x i + b)) ,
where l is a loss function.

To obtain the dual formulation of problem 1.2, we introduce the multipliers of Lagrange β i and µ i , the Lagrangian function is given by:

L(w, b, ξ, β, µ) = 1 2 w 2 + ζ n i=1 ξ i - n i=1 β i (y i ( w, x i + b) -1 + ξ i ) - n i=1 µ i ξ i . (1.5)
The Lagrangian must be optimized with respect to w ,b, ξ i and the multipliers of Lagrange β i and µ i . By setting the partial derivatives to zero of the Lagrangian with respect to w ,b, ξ i , we obtain the following:

∂L ∂w = 0 ⇒ w = n i=1 β i y i x i , ∂L ∂ξ i = 0 ⇒ β i = ζ -µ i , ∀i, ∂L ∂b = 0 ⇒ 0 = n i=1 β i y i , β i , µ i , ξ i 0, ∀i.
Substituting these results in the equation of Lagrangian 1.5 we obtain the dual problem as follow:

                   max β -1 2 n i=1 n j=1 β i β j y i y j x i , x j + n i=1 β i subject to n i=1 β i y i = 0 ζ β i 0, i = 1, . . . , n.
(1.6)

Preliminaries

The decision function to classify a new observation x is always

dr g (x) = sgn ( n i=1 β i y i x i , x + b) .

Soft-SVM with kernels

In the case where the two classes are slightly non-linearly separable, the Soft-SVM are sufficient as the figure 1.8. In this part, we present a method, called soft-SVM with kernels, deals with the case where the two classes are strongly non-linearly separable (as Figure 1.9). In order to remedy the problem of the absence of a linear separator, the idea of kernel trick is to reconsider the problem in a space high-dimensional, possibly of infinite dimension. In this new space, it is then probable that there is a linear separation. The projection on a space of higher dimension makes it possible to perform linear operations equivalent to nonlinear operations on the input space, this projection is performed by the function of projection Φ defined as:

Φ : X -→ H x i -→ Φ(x i )
where the mapping space H is a Hilbert space and dim(H) d. Hence the optimization problem 1.6 will be reformulated as:

                   max β -1 2 n i=1 n j=1 β i β j y i y j Φ(x i ), Φ(x j ) + n i=1 β i subject to n i=1 β i y i = 0 ζ β i 0, i = 1, . . . , n.
(1.7)

The inner product imposed by the projection is more complex and very expensive in computing due to the large dimension of Φ, other functions called Kernel function can realize this computation without making explicit projection towards other spaces, the use of function Kernel to avoid projection is known as "Kernel Trick" [15]. In the following , the image space H through Φ is instantiated by H κ , where the mapping space H κ is the corresponding reproducing kernel Hilbert space (RKHS), with κ is a real-valued positive type function/kernel.

A kernel function is defined as:

κ : X × X -→ R (x i , x j ) -→ κ(x i , x j ) = Φ(x i ), Φ(x j ) Hκ .
To replace the projection function, a Kernel function must verify the Mercer's theorem which states that a kernel function represents the scalar product if it is positive definite.

We present some examples of kernel functions:

Degree d polynomial: κ(u, v) = (1 + u, v ) d ,
Radial Basis (RBF kernel):

κ(u, v) = exp -u -v 2 2σ 2 , Two-layer Neural Network: κ(u, v) = S (η u, v + c) ,
in which S is the sigmoïd function,

S(t) = 1 1 + e t .
We will present in Chapter 2 more details on the kernel theory.

By substituting the Kernel trick into the dual problem 1.6, the optimization problem is formulated as:

                   max β -1 2 n i=1 n j=1 β i β j y i y j κ(x i , x j ) + n i=1 β i subject to n i=1 β i y i = 0 ζ β i 0, i = 1, . . . , n.
(1.8)

Preliminaries

The decision function is given by:

dr g (x) = sgn ( n i=1 β i y i κ(x i , x) + b) .

SVM for multi-class classification

We place ourselves in the context of discrimination in C categories with C 3 . The principle of the SVM explained in the previous section is summarised in solving of binary classification problems, but the most classification problems are a multi-class problem. Hence the importance of extending the principle of SVM to the problems of more than two classes, there have been several attempts to combine binary classifiers to identify this problem (multi classes) [32], there are also attempts to incorporate the classification of several classes into the SVM process so that all classes are treated simultaneously [33].

In this section, we will discuss on strategies based on reducing the multi-class problem to multiple binary classification problems. We will then briefly explain some of the most widely used methods.

The combination of SVM bi-classes: a first step towards multi-class SVM

Decomposition methods can be used to address a multi-category discrimination problem (C 3) as a combination of dichotomous calculation problems. We are dealing here only with the two main decomposition methods.

One versus All

We are given a training dataset of n points of the form

(x 1 , y 1 ), • • • , (x n , y n ) where x i , i = 1, • • • , n is a vector of length d and y i ∈ Y = {1, • • • , C}
representing the class of the sample. A first approach is to create a classifier for each class, which separates the points of this class from all the other points. This method is called one-versus-rest (OVR abbreviated) or one-versus-all (OVA abbreviated). It consists in using a binary classifier (with real values) by category. The k th classifier is intended to distinguish the index category k from all the others. To assign an example, it is thus presented to C classifiers, and the decision is obtained according to the principle winner-takes-all: the label chosen is that associated with the classifier who returned the highest value. It is commonly quoted as older works evoking the use of this strategy with SVM [34] (see also [35]). In [35], the authors support the thesis that this approach, as simple as it is, when implemented with correctly parameterized SVM, obtains performances that are not significantly lower than those of the other methods. It should be emphasized, however, that it involves learning to allocate to very unbalanced categories, which often raises practical difficulties.

One versus one

Another approach of decomposition, just as intuitive, is the "one-versus-one" method (OVO for short) [START_REF] Friedman | Another approach to polychotomous classification[END_REF]. Usually attributed to Knerr and his coauthors [START_REF] Knerr | Single-layer learning revisited: A stepwise procedure for building and training a neural network[END_REF], it consists in using a classifier by couple of categories. The classifier indexed by the pair (k, l) (with 1 k < l C), is intended to distinguish the index category k from that of index l. To assign an example, so it is presented to C(C -1)/2 classifiers, and the decision is usually obtained by performing a majority vote (max-wins voting). There are several models of SVM multi classes (M-SVM) including Weston and Watkins model (WW) [33], Crammer and Singer (CS) [START_REF] Crammer | On the algorithmic implementation of multiclass kernelbased vector machines[END_REF], model of Lee, Lin and Wahba (LLW) [START_REF] Lee | Multicategory support vector machines: Theory and ap-plication to the classification of microarray data and satellite radiance data[END_REF] and Guermeur and Monfrini (MSVM2) [START_REF] Guermeur | A quadratic loss multi-class SVM for which a radiusmargin bound applies[END_REF]. We now describe the model of Weston and Watkins.

Weston and Watkins model

The first publication describing a multiclass SVM is [33] (see also [START_REF] Weston | Support vector machines for multi-class pattern recognition[END_REF]). It presents a model proposed independently by Vapnik and Blanz in slightly earlier oral communica- The binary SVM optimisation problem [35] is generalised to the following:

             min w,b,ξ 1 2 C k=1 w k 2 + ζ n i=1 k =y i ξ ik subject to ∀i, k = y i , w y i , Φ(x i ) + b y i w k , Φ(x i ) + b k + 2 -ξ ik , ξ ik 0, i = 1, . . . , n, k = {1, . . . , C}\y i .
(1.9)

This gives the decision function :

dr g (x) = argmax k [ w k , Φ(x) + b k ], k = 1, . . . , C.
We can use the Lagrangian to find the solution to this optimisation problem.

In the first part of thesis, we are interested in the problem of multiclass classification, we introduced a new margin multi category classifier based on classes of vector valued functions with one component function per category, it is a kernel machine. We found that separation surfaces are hyperbolic and this classifier generalizes the SVMs. We also exhibited the statistical properties of this classifier, among which Fisher consistency [START_REF] Liu | Fisher consistency of multicategory support vector machines[END_REF] and we showed that the classes of component functions are uniform Glivenko-Cantelli [START_REF] Dudley | Uniform and universal Glivenko-Cantelli classes[END_REF].

Hyperbolic kernel machine

This section presents the essential of our contributions to the theory of multi class SVM. We initially present the definition of Uniform Glivenko-Cantelli class . The definition of this property calls for the introduction of an intermediate definition.

Definition 1.1. (Empirical probability measure) Let (T , A T ) be a measurable space and let T be a random variable with values in T , distributed according to a probability measure P T on (T , A T ). For n ∈ N * , let T n = (T i ) 1 i n be an n-sample made up of independent copies of T . The empirical measure supported on this sample, P T,n , is given by

P T,n = 1 n n i=1 δ T i ,
where δ T i denotes the Dirac measure centered on T i .

Definition 1.2 (Uniform Glivenko-Cantelli class [START_REF] Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF][START_REF] Dudley | Uniform and universal Glivenko-Cantelli classes[END_REF]). Let the probability measures P T and P T,n be defined as in Definition 1.1. Let F be a class of real-valued functions on

T . Then for ∈ R * + , F is an -uniform Glivenko-Cantelli class if lim n-→+∞ sup P T P sup n n sup f ∈F E T ∼P T,n [f (T )] -E T ∼P T [f (T )] > = 0,
where P denotes the probability with respect to the sample. F is said to be a uniform Glivenko-Cantelli class if F is an -Uniform Glivenko-Cantelli class for all value of .

In this following, we shall refer to Uniform Glivenko-Cantelli classes by the abbreviation "GC classes". We can use the following three capacity measures to demonstrate that the component function class is GC class.

Capacity measures

We start by giving the definition of the capacity measures which are the covering-numbers that characterize "GC classes". The definition of these concepts, as well as those of the underlying concepts of cover and net, have been originally introduced in [START_REF] Kolmogorov | -entropy and -capacity of sets in function spaces[END_REF].

Definition 1.3. ( -cover, -net, covering numbers, and -entropy) Let (E, ρ) be a pseudo-metric space, E ⊂ E and ∈ R * + . An -cover of E is a coverage of E with open balls of radius the centers of which belong to E. These centers form an -net of E . A proper -net of E is an -net of E included in E . If E has an -net of finite cardinality, then its covering number N ( , E , ρ) is the smallest cardinality of its -nets:

N ( , E , ρ) = min {|E | : (E ⊂ E) ∧ (∀e ∈ E , ρ (e, E ) < )} .
If there is no such finite net, then the covering number is defined to be infinite. The corresponding logarithm, log 2 (N ( , E , ρ)), is called the minimal -entropy of E , or simply the -entropy of E . N (p) ( , E , ρ) will designate a covering number of E obtained by considering proper -nets only. In the finite case, we have thus:

N (p) ( , E , ρ) = min {|E | : (E ⊂ E ) ∧ (∀e ∈ E , ρ (e, E ) < )} .
In the following, we will define the functional pseudo-metric based on the L 2 -norm and on the uniform convergence norm.

∈ N * , let t n = (t i ) 1 i n ∈ T n . Then, ∀ (f, f ) ∈ F 2 , d 2,tn (f, f ) = f -f L 2 (µ tn ) = 1 n n i=1 (f (t i ) -f (t i )) 2 1 2 , 1. Preliminaries ∀ (f, f ) ∈ F 2 , d ∞,tn (f, f ) = f -f L∞(µ tn ) = max 1 i n |f (t i ) -f (t i )| .
where µ tn denotes the uniform probability measure on {t i : 1 i n}.

Definition 1.5. (Uniform covering numbers [START_REF] Williamson | Generalization performance of regularization networks and support vector machines via entropy numbers of compact operators[END_REF]) Let F be a class of real-valued functions on T and F ⊂ F. For p ∈ {2, ∞}, ∈ R * + , and n ∈ N * , the uniform covering number N p , F, n is defined as follows:

N p , F, n = sup tn∈T n N , F, d p,tn .
We define accordingly N (p) p , F, n as:

N (p) p , F, n = sup tn∈T n N (p) , F, d p,tn .
There are several results which connect the Uniform Glivenko-Cantelli condition of a given class of functions to estimates on the covering numbers of that class. All the results are stated for classes of functions which are bounded by 1 . The results remain valid for classes of functions with a uniformly bounded range up to a constant which depends only on that bound. The next result gives the notion of GC class and the covering numbers, this result is due to Dudley, Ghiné and Zinn [START_REF] Dudley | Uniform and universal Glivenko-Cantelli classes[END_REF].

Theorem 1.1. Let F be a class of real-valued bounded functions on T . Then, the following are equivalent:

1. F is a GC class. 2. For 1 p ∞, lim n→∞ log 2 (N p ( , F, n)) n = 0 , f or all > 0.
Another important of the capacity measure used to analyse GC classes is the generalization of the Vapnik-Chervonenkis (VC) dimension [START_REF] Vladimir | Necessary and sufficient conditions for the uniform convergence of means to their expectations[END_REF]. It characterizes the learnability of the class of real-valued (binary) classifiers is the fat-shattering dimension [START_REF] Kearns | Efficient distribution-free learning of probabilistic concepts[END_REF], also known as the γ-dimension. Definition 1.6. (Fat-shattering dimension [START_REF] Kearns | Efficient distribution-free learning of probabilistic concepts[END_REF]) Let F be a class of real-valued functions on T . For γ ∈ R * + , a subset s T n = {t i : 1 i n} of T is said to be γ-shattered by F if there is a vector b n = (b i ) 1 i n in R n such that, for all vector l n = (l i )

1 i n in {-1, 1} n , there is a function f ln in F satisfying ∀i ∈ [ [1, n] ] , l i (f ln (t i ) -b i ) γ.
The vector b n is called a witness to the γ-shattering. The fat-shattering dimension with margin γ of the class F, γ-dim (F), is the maximal cardinality of a subset of T γ-shattered by F, if such maximum exists. Otherwise, F is said to have infinite fat-shattering dimension with margin γ.

The connection between GC classes and the notion of the fat-shattering dimension defined above is the following fundamental result [START_REF] Vladimir | Necessary and sufficient conditions for the uniform convergence of means to their expectations[END_REF]: Theorem 1.2. Let F be a class of uniformly bounded real-valued functions on T , then it is a GC class if and only if it has a finite fat-shattering dimension for every γ > 0 , i.e. for every γ ∈ R * + , γ-dim (F) is finite.

The last capacity measure that gives the Uniform Glivenko Cantelli class is the Rademacher complexity. For n ∈ N * , a Rademacher sequence σ n is a sequence (σ i ) 1 i n of independent random signs, i.e., independent and identically distributed (i.i.d.) random variables taking the values -1 and 1 with probability 1 2 (symmetric Bernoulli or Rademacher random variables).

Definition 1.7. (Rademacher complexity)

Let (T , A T ) be a measurable space and let T be a random variable with values in T , distributed according to a probability measure P T on (T , A T ). For n ∈ N * , let T n = (T i ) 1 i n be an n-sample made up of independent copies of T and let σ n = (σ i ) 1 i n be a Rademacher sequence. Let F be a class of real-valued functions with domain T . The empirical Rademacher complexity of F is

Rn (F) = E σn sup f ∈F 1 n n i=1 σ i f (T i ) T n . The Rademacher complexity of F is R n (F) = E Tn Rn (F) = E Tnσn sup f ∈F 1 n n i=1 σ i f (T i ) .

Theorem 1.3 ([55]

). Let F be a class of uniformly bounded real-valued functions on T . Then, the following are equivalent:

1. F is a GC class. 1. Preliminaries 2. For n ∈ N * , lim n→∞ R n (F) = 0.
Chapter 3 shows that the class of function of our classifier is GC class by using the third capacity measure which is the Rademacher complexity. It means that we use the theorem 1.3, it suffices to establish that the Rademacher complexity of this class of function converges to 0, as n goes to infinity.

Useful properties of the (empirical) Rademacher complexity

The following theorem summarizes some of the properties of the Rademacher averages we shall use.

Theorem 1.4. Let (T , A T ) be a measurable space. Let F and F be classes of real-valued functions on T . Then, for n ∈ N * ,

1. If F ⊂ F , R n (F) R n (F ) . 2. For every c ∈ R, let c F = {cf : f ∈ F}, R n (cF) = |c| R n (F) . 3. Let F + F = {f + f : f ∈ F, f ∈ F } , R n (F + F ) R n (F) + R n (F ) .
4. If φ : R → R is a Lipschitz function with a constant L φ and satisfies φ(0) = 0, then

R n (φ • F) 2 L φ R n (F) ,
where φ • F = {φ(f (.)) : f ∈ F}.

In the next section, we want to upper bound of the empirical Rademacher complexity of kernel classes.

Empirical Rademacher complexity of the kernel classes

Theorem 1.5. Let κ : X × X -→ R be a positive definite, continuous functions. Suppose that κ is a bounded kernel with sup x∈X κ(x, x) = B < ∞, and let (H κ , , Hκ ) be its RKHS. For M > 0 be fixed, let

F = {f ∈ H κ : f Hκ M } . Then for any S = (x 1 , • • • , x n ), R S (F) M B √ n .
(1.10)

Proof. Fix S = (x 1 , . . . , x n ). Then R S (F) = 1 n E σn sup f ∈F n i=1 σ i f (x i ) = 1 n E σn sup f ∈F n i=1 σ i f, κ(., x i ) Hκ = 1 n E σn sup f ∈F f, n i=1
σ i κ(., x i ) Hκ (linearity of inner product)

1 n sup f ∈F f Hκ E σn   n i=1 σ i κ(., x i ) Hκ   (Cauchy Schwarz inequality ) M n E σn   n i=1 σ i κ(., x i ) Hκ   M n   E σn   n i=1 σ i κ(., x i ) 2 Hκ     1 2 (Jensen's inequality) = M n   E σn   n i=1 σ i κ(., x i ), n j=1 σ j κ(., x j ) Hκ     1 2 = M n E σn n i=1 n j=1
σ i σ j κ(., x i ), κ(., x j ) Hκ

1 2 = M n n i=1 n j=1 κ(x i , x j )E σn [σ i σ j ] 1 2 = M n n i=1 n j=1 κ(x i , x j )δ i,j 1 2
(where δ i,j is the Kronecker symbol)

= M n n i=1 κ(., x i ) 2 Hκ 1 2 (E σn [σ i σ j ] = 0, i = j) = M n n i=1 κ(x i , x i ) 1 2
(reproducing property 2.4)

M n √ nB 2 = M B √ n .
Inequality 1.5 has been established, which concludes the proof.

1. Preliminaries

Note. M n n i=1 κ(x i , x i ) = M n trace(K)
, where K is the kernel matrix with entries

K ij = κ(x i , x j ).
The proof of this theorem 1.5 will help us in the proof of the lemma 3.1 of chapter 3.

Chapter 2

Background: an Overview of Kernel Methods

Abstract In this chapter, we provide the fundamental theory of kernel methods. Firstly, we give a short introduction of kernel method. We then recall the basic concepts necessary for the kernel theory. We will present the positive semidefinite property of kernel function and kernel matrix, and we give some operations on kernel function which will provide a new kernel. Finally we introduce some popular kernels in applications.

Introduction

In machine learning, kernel methods are a class of pattern recognition algorithms, whose best known member is the support vector machine (SVM). The idea of kernel trick is to transform the representation space of input data into a higher dimension space, where a linear classifier can be used and obtain good performance. The linear discrimination in high-dimensional space (also called feature space) is equivalent to a non-linear discrimination in the original space. However, the computation of the inner product in the feature space can be calculated by the kernel function.

A kernel is a two-argument real-valued function over X × X (κ : X × X -→ R) such that for any x, y ∈ X

κ(x, y) = Φ(x), Φ(y) H (2.1)
for some inner-product space H such that Φ is a mapping from X to a feature space H

Φ : X -→ H (2.2)
2. Background: an Overview of Kernel Methods Kernel methods have achieved great success and should clarify the following aspects:

• Data points are mapped from an input space to a higher-dimensionnal feature space

• It is not necessary to know the coordinates in the feature space, we could be obtained by similarity information which are the inner products.

• Pairwise inner products can be calculated by the kernel function.

• The initial problem is anticipated to be a linear problem in the feature space even though it is not linear in the input space.

This can be illustrated by the Example 2.1.1. In this example, we consider a feature space two-dimension input space X ⊆ R 2 and its corresponding feature map

Φ : x = (x 1 , x 2 ) -→ Φ(x) = (x 2 1 , x 2 2 , √ 2x 1 x 2 ) ∈ H ⊆ R 3
We can compute the inner product between two points in the feature space, then we get

Φ(x), Φ(y) H = (x 2 1 , x 2 2 , √ 2x 1 x 2 ), (y 2 1 , y 2 2 , √ 2y 1 y 2 ) H = x 2 1 y 2 1 + x 2 2 y 2 2 + 2x 1 x 2 y 1 y 2 = (x 1 y 1 + x 2 y 2 ) 2 = x, y 2 H .
So the kernel function is

κ(x, y) = Φ(x), Φ(y) H = x, y 2 H .

Fundamental elements of the theory of kernel functions

This section presents the definitions and properties essential to understanding the theory of kernel. To well comprehend the kernel theory, the following fundamental elements need to be presented.

Hilbert space

Definition 2.1. (Inner Product Space) An inner product space X is a vector space with an associated inner product ., . : X × X -→ R that satisfies:

1. Symmetry

x, y = y, x ∀x, y ∈ X .

Bilinearity

αx + βy, z = α x+, z + β y, z ∀x, y, z ∈ X , ∀α, β ∈ R.

Positive Semi-Definiteness

x, x 0 ∀x ∈ X .

The inner product space is strict if

x, x = 0 ⇔ x = 0.

Note.

• A strict inner product space X has a natural norm given by x 2 = x, x . The associated metric is d(x, y) = x -y 2 .

• The space R d has the inner product x, y = x T y which yields the Euclidien norm:

x 2 2 = d i=1 x 2 i .
We now give the definition of Hilbert space.

Definition 2.2. A strict inner product space H is a Hilbert space if it is

• Complete: Every Cauchy sequence {h i ∈ H} ∞ i=1 such that lim n-→∞ sup m>n h n -h m = 0.
• Separable: There is a countable subset Ĥ = {h i ∈ H} ∞ i=1 such that for all h ∈ H and > 0, there exists h i ∈ Ĥ such that x i y i .

h i -h < .
• Inner-product generalized as

f, g = X f (x)g(x)dx,
where functions f satisfy X f (x) 2 dx < ∞.

Reproducing Kernel Hilbert Space

The definition of a Reproducing Kernel Hilbert Space (RKHS) calls for the following concepts that are essential in kernel definition. Definition 2.3. (Positive Semi-Definite Matrix) Matrix A is positive semi-definite (PSD) [1] if all its eigenvalues are non-negative (∀ i λ i (A) 0), i.e., for all x ∈ X :

x T Ax 0. Definition 2.4. (Positive Definite Matrix) Matrix A is positive definite if all its eigenvalues are positive (∀ i λ i (A) > 0), i.e., A is PSD and

x T Ax = 0 ⇔ x = 0. Definition 2.5. A symmetric function f : X × X -→ R is positive semi-definite if n i=1 n j=1 α i α j f (x i , x j ) = α T F α 0, ∀ (α 1 , • • • , α n ) ∈ R n , ∀ (x 1 , • • • , x n ) ∈ X n .
In the following, we introduce the main property of reproducing kernel Hilbert spaces:

Definition 2.6. (Reproducing Kernel Function [3]) κ(., .) is a reproducing kernel [2] of a Hilbert space H if f (x) = f, κ(x, .) H , ∀f ∈ H. (2.3)
Further, the space is called a Reproducing Kernel Hilbert Space (RKHS).

Remark. A reproducing kernel κ is finitely positive semi-definite function (FPSD).

Proof. The reproducing property is given by: ∀x, y ∈ X , κ(x, .), κ(y, .) H = κ(x, y).

(2.4)

∀ α 1 , • • • , α n ∈ R, ∀ x 1 , • • • , x n ∈ X we have: n i=1 n j=1 α i α j κ(x i , x j ) = n i=1 n j=1 α i α j κ(x i , .), κ(x j , .) H = n i=1 α i κ(x i , .), n j=1 α j κ(x j , .) H = n i=1 α i κ(x i , .) 2 H 0.
Definition 2.7. (Reproducing Kernel Hilbert Space [5]) A Reproducing Kernel Hilbert Space is a Hilbert space with a reproducing kernel, where the evaluation functions f (.) are bounded, i.e.

∃M > 0 : |δ x (f )| = |f (x)| M f H .

Characterization of kernels

In this section, we characterize the kernel function using another way, which also allows us to build new kernels.

Theorem 2.1. [4] κ : X × X -→ R is finitely positive semi-definite (FPSD) if and only there exists a Hilbert space H with feature map Φ : X -→ H such that κ(x, y) = Φ(x), Φ(y) H .

Theorem 2.2. (Moore-Aronszajn Theorem) If κ is symmetric and positive definite kernel on a set X . Then there is a unique Hilbert space of functions on X for which κ is a reproducing kernel.

Theorem 2.3. (Mercer Theorem) Let κ is a continuous kernel function that takes two variables x and y and map them to a real value such that κ(x, y) = κ(y, x). A kernel is non-negative definite if and only if:

f (x)κ(x, y)f (y)dxdy 0.
In association with a kernel κ, we can define an integral operator T κ , which, when applied to a function f (x), generates another function:

T κ (f (x)) = κ(x, y)f (y)dy = [T κ f ](x).
The eigenvalues and their correponding eigenfunctions of this operation are defined as:

T κ (φ i (x)) = κ(x, y)φ(y)dy = λ i φ i (x).
The eigenvalues λ i are non-negative and the eigenfunctions φ i (x) are orthonomal:

φ i (x)φ j (x)dx = δ ij .
The eigenfunctions corresponding to the non-zero eigenvalues form a set of basis functions so that the kernel can be decomposed in terms of them:

κ(x, y) = ∞ i=1 λ i φ i (x)φ j (y).

Kernel matrix

Given the fundamental concepts mentioned above which are necessary to build the theory of kernel, now we offer a formal definition of the kernel: Definition 2.8. κ : X × X -→ R is a valid kernel if it satisfies the following conditions • κ is symmetric: ∀x, y ∈ X , κ(x, y) = κ(y, x).

• κ is positive semi-definite. Definition 2.9. A kernel matrix (or Gram matrix) K is the matrix that results from applying κ to all pairs of data points in set

{x i } n i=1 ∈ X n K =       κ(x 1 , x 1 ) κ(x 1 , x 2 ) • • • κ(x 1 , x n ) κ(x 2 , x 1 ) κ(x 2 , x 2 ) • • • κ(x 2 , x n ) . . . . . . . . . . . . κ(x n , x 1 ) κ(x n , x 2 ) • • • κ(x n , x n )       that is, K ij = Φ(x i ), Φ(x j ) H = κ(x i , x j ).
Remark. The Gram matrix is symmetric since K ij = K ji and it is positive semi-definite.

Proof. For any vector α we have

α T Kα = n i,j=1 α i α j K ij = n i,j=1 α i α j Φ(x i ), Φ(x j ) H = n i=1 α i Φ(x i ), n j=1 α j Φ(x j ) H = n i=1 α i Φ(x i ) 2 H 0.
This property ensures that we have a valid kernel (positive semidefinite property), which allows us to manipulate the kernels regardless of the feature space.

Kernel constructions

In the previous section, we have seen that the necessary and sufficient condition for a function to be a reproducing kernel is that it be semi-definite positive. In this section we present some aspects of kernel engineering. More examples and properties can be found in [6,7]. We will enumerate some properties also called closure properties, which allow us to manipulate kernel functions to create more complex kernels. Proposition 2.1. (Closure Properties of Kernels [8,9]) κ 1 and κ 2 are assumed to be valid kernel functions on X × X , let f : X -→ R, Φ : X -→ R N , and κ 3 is a valid kernel on R N × R N . Then, the function κ : X × X -→ R which is defined by one of the following expressions for any x, y ∈ X is also a valid kernel.

1. κ(x, y) = κ 1 (x, y) + κ 2 (x, y).

κ(x, y)

= aκ 1 (x, y), ∀a ∈ R + . 3. κ(x, y) = κ 1 (x, y)κ 2 (x, y). 4. κ(x, y) = f (x)f (y).
5. κ(x, y) = κ 3 (Φ(x), Φ(y)).

Proof. Let K 1 and K 2 be the (n × n) Gram matrices of kernels κ 1 and κ 2 respectively and α ∈ R n be any vector. Recall that K is a positive semi-definite matrix if and only if ∀α, α T Kα 0.

1. K 1 + K 2 is kernel matrix corresponding to κ 1 + κ 2 . We have α T Kα = α T K 1 α + α T K 2 α 0.
So K 1 + K 2 is the positive semi-definite, i.e. the sum of two symmetric positive kernel is a valid kernel function.

K

= aK 1 =⇒ α T Kα = a.α T K 1 α 0.
Then the validity of a kernel is conserved after multiplication by a positive scalar.

3. Schur product theorem states that the Schur product (Hadamard product) of two positive semi-definite matrix is a also positive semi-definite matrix since the eigenvalues of the product are product of corresponding eigenvalues of the two matrices which are positive. Then the product of two kernel functions is a valid kernel function.

4. Using the feature map Φ : x -→ f (x), we have

κ(x, y) = f (x)f (y) = Φ(x), Φ(y) ,
thus κ is PSD.

5. Since κ 3 is a kernel, applying it to any set of vectors {Φ(x i )} n i=1 yields a PSD matrix.

Proposition 2.2. (Polynomial functions of a kernel output) Given a polynomial P : R -→ R with positive coefficients and let κ 1 is a valid kernel, then the function

κ(x, y) = P (κ 1 (x, y))
is a valid kernel.

Proof. The polynomial P is a linear combination of powers of the kernel κ 1 with positive coefficients. Since the powers of κ 1 are products of κ 1 by itself and thus valid kernels, their linear combination is also a valid kernel.

Proposition 2.3. (Exponential function of a kernel output) Let κ 1 is a valid kernel, the function

κ(x, y) = exp(κ 1 (x, y))
is a valid kernel.

Proof. We consider the Taylor series of exp(x) = 1 + x + x 2 2! + • • • . Thus, it is a limit of polynomials case. For more details of the proof of propositions 2.2 and 2.3 could be found in [7].

We have seen in this subsection some methods for modifying kernel from existing kernels while maintaining properties of symmetry and positivity.

Basic kernels

In this section, we introduce a family of symmetric, positive definite functions (hence kernels): translation-invariant kernels, and give examples of most popular kernel functions.

Polynomial kernel

Example 2.4.1. For a polynomial of degree s (s ∈ N ), the polynomial kernel is defined as

κ(x, y) = ( x, y + R) s ∀x, y ∈ X = R d ,
where R 0 is a free parameter trading off the influence of higher-order versus lowerorder terms in the polynomial. This kernel is called Inhomogeneous Polynomial kernel. When R = 0 the kernel is called homogeneous.

The following kernels are also very popular in applications that are actually special cases of polynomial kernel.

Example 2.4.2. (Linear kernels:) The Linear kernel is the simplest kernel function. It is given by the inner product.

κ(x, y) = x, y .

The linear kernel is a special case of polynomial kernels with R = 0 and s = 1. The mapping function Φ is the identity function, i.e. Φ(x) = x ∀x ∈ X .

Background: an Overview of Kernel Methods

It is obvious to show that the linear kernel is positive definite since

n i=1 n j=1 α i α j κ(x i , x j ) = n i=1 n j=1 α i α j x i , x j = n i=1 α i x i 2 0,
by linearity of the dot product.

Example 2.4.3. (Quadratic kernels:) Quadratic kernels are widely used in Speech Recognition. κ(x, y) = x, y 2 .

Translation-invariant kernels

We consider the class of translation invariant kernel functions which includes the class of radial kernels. This class contains exactly the kernels which can be defined only according to the difference of the kernel arguments. The property of this kernel as follow:

Proposition 2.4. Let us set X = R d for some d 1 and define κ as

∀x, y ∈ X , κ(x, y) = K(x -y),
where K : R d -→ R.

The function K is said to be positive definite if the corresponding kernel κ is positive definite. The general form of continuous translation invariant kernels on R d was discovered by Bochner [13]. Suppose that K is continuous, Bochner's theorem states that K is positive definite if and only if K is the Fourier transform of a bounded positive measure on R d ( [14], Theorem 20), that is

K(z) = R d e iw T z dV (w),
for some bounded positive measure V on R d .

Several instances of the family of translation-invariant kernels used kernels on R d such as:

Example 2.4.4. (Gaussian kernel)

Gaussian kernels have been proposed by Boser, Guyon and Vapnik [10,11,12], they are the most used kernels in the field of machine learning. The definition of a gaussian kernel is given in the following definition 2.10. Definition 2.10. A Gaussian kernel is defined as

κ(x, y) = e -x-y 2 2σ 2 , (2.5)
where σ is the positive parameter, called the kernel width, which controls the flexibility of gaussian kernels.

Alternatively, it could also be implemented using κ(x, y) = e -γ x-y 2 .

(2.6)

This type of kernel corresponds to K(z) = e -z 2 2σ 2 which is positive definite since K is the characteristic function of a N (0, 1

σ 2 I d ) Gaussian distribution.
The properties of Gaussian kernel are given as follow:

• As Φ(x) 2 = κ(x, x) = 1, ∀x ∈ X , then all the points have a norm equal to 1 in the feature space induced by a gaussian kernel.

• As Φ(x), Φ(y) = κ(x, y) > 0, ∀x, y ∈ X , then, all the points lie inside the same orthant in feature space.

• The mapping function Φ can not been given explicitly, because the feature space induced by a gaussian kernel is infinite-dimensional.

Example 2.4.5. (Exponential Kernel) The Exponential Kernel is closely related to the Gaussian kernel, with only the square of the norm left out.

κ(x, y) = e -x-y 2σ 2 .

(2.7)

It is also a translation-invariant kernel with K(z) = e -z 2σ 2 .

Example 2.4.6. (Laplace kernel) The Laplace kernel is completely equivalent to the exponential kernel, except that it is less sensitive to changes in the sigma parameter.

κ(x, y) = e -x-y σ .

(2.8)

Here K(z) = e -z σ corresponds to the characteristic function of a random vector rU , where U is uniform on the unit sphere of R d and r is independent of U and follows a Cauchy distribution with density function

f (t) = σ π(1+(σt) 2 ) .
Example 2.4.7. (Cauchy kernel:) The Cauchy kernel comes from the Cauchy distribution [15]. It is a long-tailed kernel and can be used to give long-range influence and sensitivity over the high dimension space.

The Cauchy kernel is a parametric kernel (with parameter σ > 0) with formula

κ(x, y) = 1 1 + x-y 2 σ 2 , ( 2
(f g)(x) = R d f (x )g(x -x) dx .
Then, the B-Spline kernel is given by the recursive formula:

κ(x, y) = B 2p+1 (x -y) f orallx, y ∈ R d , where p ∈ N with B i is a real-valued function on R d such that B i+1 = B i B 0 for each i 0.
The function B 2p+1 are positive definite and the kernel κ defines a translation-invariant kernel [16]. Some translation-invariant kernels such as the Gaussian kernel, the exponential kernel, the Laplace kernel and the Cauchy kernel admit actually in the more specific form

κ(x, y) = f (d(x, y)),
where d is a metric on X , and f : R + -→ R is a function. Usually, the metric arises from the dot product, d(x, y) = x -y =

x, y . These particular kernels are called radial kernels or radial basis function kernels (RBF kernels).

We will present several examples in chapter 4 as the kernels on graphs, fisher kernel, jittering kernels, etc. and we will construct a new kernel based on a Gaussian mixture model. We recall in the following the definition of the gaussian mixture model. Definition 2.11. (Gaussian Mixture Model) A Gaussian Mixture Model (GMM) is a parametric probability density function represented as a weighted sum of Gaussian component densities. The density of a Gaussian mixture model is given by:

f (x) = M j=0 τ j g j (x),
where τ j is a mixture proportion such that M j=0 τ j = 1, and g j (x) is a Gaussian function.

Chapter 3 Hyperbolic Kernel Machine

A new kernel machine for multi-class pattern recognition is introduced: the hyperbolic kernel machine. Its decision boundaries in the feature space are defined by hyperbolic functions. We establish its main statistical properties.

Introduction

The support vector machine (SVM) [5] is the first and main kernel machine [25] for pattern classification. Over the last two decades, a great many multi-class extensions (M-SVMs) have been introduced (see [6,4] for a survey). They were assessed in the framework of comparative experimental studies [8,4]. Their statistical properties and generalization performance were also extensively investigated (see for instance [12,11]). This chapter introduces a new kernel machine inspired by the M-SVMs. From a geometrical point of view, it is characterized by the fact that its decision boundaries in the feature space are defined by hyperbolic functions. We establish its main statistical properties.

The chapter is organized as follows. Section 3.2 is devoted to the definition of the new machine. Its statistical properties are established in Section 3.3. At last, we draw conclusions and outline our ongoing research in Section 3.4.

Hyperbolic kernel machine

The new classifier is devised in the following theoretical framework.

Theoretical framework

The learning problems we are interested in are C-category pattern classification problems. Let X denote the description space and Y the set of categories. Y can be identified with the set of indices of the categories, i.e., the set of the integers ranging from 1 to C, hereafter denoted by 1; C (we do not assume any structure in Y). We assume that (X , A X ) and (Y, A Y ) are measurable spaces and denote by A X ⊗ A Y the tensor-product sigma-algebra on the Cartesian product Z = X × Y. We make the hypothesis that the link between descriptions and categories can be characterized by an unknown probability measure P on the measurable space (X × Y, A X ⊗ A Y ). Let Z = (X, Y ) be a random pair with values in Z = X × Y, distributed according to P . The only access to P is via an m-sample Z m = (Z i ) 1 i m = ((X i , Y i )) 1 i m made up of independent copies of Z (in short Z m ∼ P m ). In this context of agnostic learning [9], a classifier is characterized by a triplet made up of a function class, a decision rule and an inductive principle. We now introduce the new kernel machine through the specification of the corresponding triplet.

Function class and decision boundaries

In the sequel, κ is a real-valued positive type function/kernel [3] on X 2 and H κ , •, • Hκ is the corresponding reproducing kernel Hilbert space (RKHS).

∀x ∈ X ,        argmax 1 k C h k (x) = 1 =⇒ dr h (x) = argmax 1 k C h k (x) argmax 1 k C h k (x) > 1 =⇒ dr h (x) = *
where |•| returns the cardinality of its argument and * stands for a dummy category.

Let the function h of H be characterized by the vectors

R C = (R k ) 1 k C ∈ R * + C and O C = (O k ) 1 k C ∈ (H κ ) C
. It stems from Definitions 3.1 and 3.2 that the boundaries between pairs of categories associated with h are either hyperbolic or linear in the feature space, depending on the value of R k -R l . Indeed, the formula defining the decision boundary between the categories k and l (for {k, l} lilliad.univ-lille.fr meaning that the classifier is linear in H κ . If R k = R l , the boundary is a sheet of a hyperboloid of two sheets, whose foci are O k and O l . The nature of the sheet depends on the sign of R k -R l . For further details, see Appendix .1

⊂ 1; C ) is R k -O k -κ x Hκ -R l + O l -κ x Hκ = 0. When R k = R l , this simplifies into O k 2 Hκ -O l 2 Hκ + 2 O l -O k , κ x Hκ = 0,

Function selection

To perform function selection on the class H, we specify a training problem that consists in minimizing a penalized data-fit term. This calls for the selection of a (margin) loss function. We use the parameterized truncated hinge loss, applied to the margin functions, a choice that bears the advantage to ensure Fisher consistency (see Section 3.3).

Definition 3.3 (Class of margin functions).

Let G be a class of functions from X into R C . For every g ∈ G, the margin function ρ g is the real-valued function on Z defined by:

∀ (x, k) ∈ Z, ρ g (x, k) = 1 2 g k (x) -max l =k g l (x) .
Then, the class ρ G is defined as follows: ρ G = {ρ g : g ∈ G} .

Definition 3.4 (Parameterized truncated hinge loss φ 2,γ ). For γ ∈ (0, 1], the parameterized truncated hinge loss φ 2,γ is defined by:

∀t ∈ R, φ 2,γ (t) = 1 {t 0} + 1 - t γ 1 {t∈(0,γ]} .
When using a margin loss function, the behavior of the margin functions outside the interval [0, γ] becomes irrelevant to characterize the generalization performance. The idea to exploit this property by means of a combination with a piecewise-linear squashing function can be traced back to [1]. The piecewise-linear squashing function that fits best with φ 2,γ is the function π γ . Definition 3.5 (Piecewise-linear squashing function π γ ). For γ ∈ (0, 1], the piecewiselinear squashing function π γ is defined by:

∀t ∈ R, π γ (t) = t1 {t∈(0,γ]} + γ1 {t>γ} .
Thus, when possible, the class ρ G is replaced with the following function class. Definition 3.6 (Function class ρ G,γ ). Let G be a class of functions from X into R C and ρ G the corresponding class of margin functions. For every pair (g, γ) ∈ G × (0, 1], the function ρ g,γ from Z into [0, γ] is defined by:

ρ g,γ = π γ • ρ g .
Then, the class ρ G,γ is defined as follows:

ρ G,γ = {ρ g,γ : g ∈ G} .
With these definitions at hand, the training problem can be defined as follows.

Definition 3.7 (Training problem of the hyperbolic kernel machine). Let κ be a kernel and H the function class associated with κ according to Definition 3.1. For z m = (z i ) 1 i m ∈ Z m , γ ∈ (0, 1] and λ ∈ R * + , the hyperbolic kernel machine associated with κ, z m , γ and λ, is obtained by solving the following optimization problem:

Problem 1. min h∈H m i=1 φ 2,γ • ρ h (z i ) + λ R C 2 2 s.t. ∀k ∈ 1; C , O k ∈ conv ({κ x i : y i = k}) .
Problem 1 is a non-convex optimization problem. There are many methods to solve it, among which: Metropolis-Hastings algorithm, Constrained Optimization by Linear Approximations (cobyla) with R, Solve Optimization problem with Nonlinear Objective and Constraints (solnl) with R, etc...

Statistical properties

The statistical properties considered in the sequel regard the consistency of the inductive principle and the generalization performance. Central in their formulations are the concepts of risk and margin risk, that we define now. Definition 3.8 (Risk and margin risk). Let G be a class of functions from X into R C . The expected risk of any function g ∈ G, L(g), is given by:

L (g) = E (X,Y )∼P 1 {ρg(X,Y ) 0} = P (dr g (X) = Y ) .
Its empirical risk measured on the m-sample Z m is:

L m (g) = E Z ∼Pm 1 {ρg(Z ) 0} = 1 m m i=1 1 {ρg(Z i ) 0}
(where P m is the empirical measure supported on Z m ). Given a class of margin loss functions φ γ parameterized by γ ∈ (0, 1], for every (ordered) pair (g, γ) ∈ G × (0, 1], the risk with margin γ of g, L γ (g), is defined as:

L γ (g) = E Z∼P [φ γ • ρ g (Z)] .
L γ,m (g) designates the corresponding empirical risk, measured on the m-sample Z m :

L γ,m (g) = E Z ∼Pm [φ γ • ρ g (Z )] = 1 m m i=1 φ γ • ρ g (Z i ) .
The first property we establish is Fisher consistency [12].

Fisher consistency

Proposition 3.1. Let G be the class of all the functions from X into R C . The minimizer g

* of E (X,Y ) [φ 2,γ • ρ g (X, Y )] over G satisfies the following: ∀x ∈ X , ∃k (x) ∈ argmax 1 k C P (Y = k | X = x) : ρ g * (x, k (x)) γ.
Proof. By disintegration (see Lemma 1.2.1 in [5]), there exists a map x → P (• | x) from X into the set of all probability measures on Y such that P is the joint distribution of (P (• | x)) x∈X and of the marginal distribution P X of P on X . Consequently,

E (X,Y ) [φ 2,γ • ρ g (X, Y )] = X ×Y φ 2,γ • ρ g (x, y) dP (x, y) = X C k=1 φ 2,γ • ρ g (x, k) P (Y = k | X = x) dP X (x) = E X C k=1 φ 2,γ • ρ g (X, k) P (Y = k | X) , from which it springs that ∀x ∈ X , g * ∈ argmin g∈G C k=1 φ 2,γ • ρ g (x, k) P (Y = k | X = x) .
Given x ∈ X and g ∈ G, by definition of ρ g , there is at most one value of k in 1; C such that ρ g (x, k) > 0. Suppose that there is none. Then according to Definition 3.4,

C k=1 φ 2,γ • ρ g (x, k) P (Y = k | X = x) = C k=1 P (Y = k | X = x) = 1. (3.1)
Suppose on the contrary that there exists

k * ∈ 1; C such that ρ g (x, k * ) > 0. Then C k=1 φ 2,γ • ρ g (x, k) P (Y = k | X = x) = 1 + (φ 2,γ • ρ g (x, k * ) -1) P (Y = k * | X = x) (3.2) < 1. (3.3)
It springs from (3.1) and (3.3) that g * satisfies:

∀x ∈ X , ∃! k (x) ∈ 1; C : ρ g * (x, k (x)) > 0.
Furthermore, due to (3.2), ∀x ∈ X ,

   k (x) ∈ argmax 1 k C P (Y = k | X = x) ρ g * (x, k (x)) γ , so that C k=1 φ 2,γ • ρ g * (x, k) P (Y = k | X = x) = 1 -max 1 k C P (Y = k | X = x) .
We now establish a guaranteed risk for our classifier.

Guaranteed risk

The capacity measure involved in our guaranteed risk is a Rademacher complexity.

Definition 3.9 (Rademacher complexity). Let (T , A T ) be a measurable space and let T be a random variable with values in T , distributed according to a probability measure P T on (T , A T ). For m ∈ N * , let T m = (T i ) 1 i m be an m-sample made up of independent copies of T and let σ m = (σ i ) 1 i m be a Rademacher sequence. Let F be a class of realvalued functions with domain T . The empirical Rademacher complexity of F given T m is

Rm (F) = E σm sup f ∈F 1 m m i=1 σ i f (T i ) T m . The Rademacher complexity of F is R m (F) = E Tm Rm (F) = E Tmσm sup f ∈F 1 m m i=1 σ i f (T i ) .
Theorem 3.1 (Theorem 5 in [7]). Let G be a class of functions from X into R C . For γ ∈ (0, 1], let ρ G,γ be the function class deduced from G according to Definition 3.6. For a fixed γ ∈ (0, 1] and a fixed δ ∈ (0, 1), with P m -probability at least 1 -δ,

sup g∈G (L (g) -L γ,m (g)) 2 γ R m (ρ G,γ ) + ln 1 δ 2m , (3.4)
where the margin loss function defining the empirical margin risk is the parameterized truncated hinge loss (Definition 3.4).

To upper bound the Rademacher complexity of interest, R m (ρ H,γ ), we resort to a structural result. The sharpest result of this kind is due to Maurer [13]. It is an improvement of the ones introduced in [10,11]. With Theorem 3.1 and Lemma 3.1 at hand, deriving a guaranteed risk for the hyperbolic kernel machine boils down to bounding from above R m H .

R m H R max 2 √ m + 1 2m 1 4 1 + Λ 2 O 2 + Λ 2 X + 2Λ O Λ X .
(3.5)

Conclusion

We are introduced a novel kernel machine for multi-class pattern recognition. First, the new margin multi category classifier is presented. This classifier is a kernel machine whose separation surfaces are hyperbolic and generalizes the SVM. Then, we exhibited its main statistical properties. We established an upper bound of the Rademacher complexity for this classifier. Finally, we deduced a guaranteed risk for the hyperbolic kernel machine.

Proof of Lemma 3.1

Proof. Due to the subadditivity of the supremum,

Rm H = E σm sup h∈ H 1 m m i=1 σ i h (x i ) 1 m E σm sup h∈ H m i=1 σ i R + sup h∈ H m i=1 σ i O -κ x i Hκ = 1 m E σm sup h∈ H m i=1 σ i R + 1 m E σm sup h∈ H m i=1 σ i O -κ x i Hκ . (3.6)
The first Rademacher complexity in the right-hand side of (3.6) can be upper bounded thanks to Lemma 3.2, which gives:

1 m E σm sup h∈ H m i=1 σ i R R max 2 √ m .
To upper bound the second Rademacher complexity, we resort to Lemma 3.3 and choose Φ to be the square root. This is possible due to the following inequality:

∀ (u, v, w) ∈ R 3 + , √ v - √ u √ w + 1 2 √ w |v -u| , (3.7)
which enables us to set c = m -1 4 and L Φ = 1 2 m 1 4 (corresponding to w = m -1 2 ). Then,

1 m E σm sup h∈ H m i=1 σ i O -κ x i Hκ 1 2m 1 4 1 + 1 √ m E σm sup h∈ H m i=1 σ i O -κ x i 2 Hκ
.

(3.8) We now bound the expectation in the right-hand side of (3.8).

E σm sup h∈ H m i=1 σ i O -κ x i 2 Hκ E σm sup h∈ H m i=1 σ i O 2 Hκ + m i=1 σ i κ x i 2 Hκ + 2 sup h∈ H m i=1 σ i O, κ x i Hκ Λ 2 O 2 √ m + E σm m i=1 σ i κ x i 2 Hκ + 2E σm sup h∈ H m i=1 σ i O, κ x i Hκ , (3.9)
where

E σm sup h∈ H m i=1 σ i O 2
Hκ has been bounded from above by means of Lemma 3.2.

The first expectation in the right-hand side of (3.9) can be bounded by means of Jensen's inequality, which gives:

E σm m i=1 σ i κ x i 2 Hκ   E σm   m i=1 σ i κ x i 2 Hκ 2     1 2 √ mΛ 2 X .
At last, the second expectation in the right-hand side of (3.9), associated with a class of linear functions, can be bounded by means of the Cauchy-Schwarz inequality and Jensen's inequality.

E σm sup h∈ H m i=1 σ i O, κ x i Hκ = E σm sup h∈ H O, m i=1 σ i κ x i Hκ Λ O E σm n i=1 σ i κ x i Hκ Λ O Λ X √ m.
Putting things together gives (3.5), thus concluding the proof.

Technical lemmas

Lemma 3.2. Let F be the class of constant functions on T whose values range from 0 to M F . Then

∀m ∈ N * , R m (F) M F 2 √ m . Proof. Let t m = (t i ) 1 i m ∈ T m . R m (F) = E σm sup f ∈F 1 m m i=1 σ i f (t i ) 1 m E σm M F 1 m i=1 σ i >0 m i=1 σ i = M F 2m E σm m i=1 σ i . (3.10)
The expectation in (3.10) can be upper bounded in the classical way using Jensen's inequality and the linearity of the expectation:

E σm m i=1 σ i   E σm   m i=1 σ i 2     1 2 = m i=1 m j=1 E σm [σ i σ j ] 1 2 = m i=1 m j=1 δ i,j 1 2 = √ m. (3.11)
A substitution of (3.11) into (3.10) concludes the proof.

Lemma 3.3. Let F be a class of real-valued functions on T . If Φ : R -→ R is a function such that there exist L Φ ∈ R * + and c ∈ R satisfying:

∀ (u, v) ∈ R 2 , |Φ (u) -Φ (v)| L Φ |u -v| + c, then Rm (Φ • F) L Φ Rm (F) + c 2 .
The proof is basically that of Talagrand's contraction lemma (see for instance Lemma 4.2 in [14]).

Proof.

Rm (Φ • F) = E σm sup f ∈F 1 m m i=1 σ i Φ • f (t i ) = 1 2m E σ m-1 sup f ∈F m-1 i=1 σ i Φ • f (t i ) + Φ • f (t m ) +E σ m-1 sup f ∈F m-1 i=1 σ i Φ • f (t i ) -Φ • f (t m ) = 1 2m E σ m-1 sup (f,f )∈F 2 m-1 i=1 σ i (Φ • f (t i ) + Φ • f (t i )) + Φ • f (t m ) -Φ • f (t m ) c 2m + 1 2m E σ m-1 sup (f,f )∈F 2 m-1 i=1 σ i (Φ • f (t i ) + Φ • f (t i )) + L Φ |f (t m ) -f (t m )| .
Since f and f are interchangeable, the absolute value can be removed, so that the inequality simplifies into

Rm (Φ • F) c 2m + 1 m E σm sup f ∈F m-1 i=1 σ i Φ • f (t i ) + L Φ σ m f (t m ) .
Iterating the process for i equal to m -1 down to 1 concludes the proof.

Proof of Equation 3.7.

For all w > 0 as the derivative is always decreasing. Indeed, if we suppose without loss of generality v u. The formula is obtained by considering the following various cases:

• If, u < w v, then √ v √ w + 1 2 √ w (v -w) √ w + 1 2 √ w (v -u). Then, √ v - √ u √ w + 1 2 √ w (v -u). • If, u v < w, then √ v - √ u √ w and thus √ v - √ u √ w + 1 2 √ w (v -u). • Otherwise, if w u v, then √ v - √ u 1 2 √ w (v -u) and thus √ v - √ u √ w + 1 2 √ w (v -u).
For our application we will take w = 1 √ m .

.

Geometric locus

Definition .10 (Hyperbola Definition). Formally, a hyperbola can be defined geometrically as follows: For two given points, the foci, a hyperbola is a set of points (locus of points) such that the difference between the distances to each focus is constant.

Shape of the separation surface We will determine the geometric locus of the points such that h k (x) -h l (x) = 0 to know the type of classifier. There are two cases:

In the first case if R k = R l then, h k (x) -h l (x) = O k -κ x Hκ -O l -κ x Hκ . Consequently if, h k (x) -h l (x) = 0 then we have, O k -κ x Hκ -O l -κ x Hκ = 0, this implies O k 2 Hκ -O l 2 Hκ + 2 O l -O k , κ
x Hκ = 0. Thus, in this case the classifier is linear, and we recognize the classical form of a SVM. Other way, we can find the type of classifier geometrically. The geometric locus of the points such that h k (x) -h l (x) = 0 is the mediator plane on segment [O k O l ], so it is a linear classifier.

In the second case if R k = R l , the geometric locus of the points such that h k (x)h l (x) = 0 is a hyperbola by definition .10, so in this case it is a non linear classifier.

Eccentricity of a hyperbola

We have O l -κ x Hκ -O k -κ x Hκ = R l -R k , then a = R l -R k 2
, where a is the distance between the center of the hyperbola and one of its vertices. The distance c of the foci to the center is called the focal distance, it's given by: c

= O l -O k Hκ 2
. Thus, the eccentricity e of a hyperbola is given by: e

= c a = O l -O k Hκ R l -R k .
.

Geometric locus in dimension 2

Let (-c, 0) and (c, 0) be the foci of a hyperbola centered at the origin. The hyperbola is the set of all points (x, y) such that the difference of the distances from (x, y) to the foci is constant. If (a, 0) is a vertex of the hyperbola, the distance from (-c, 0) to (a, 0) is a -(-c) = a + c. The distance from (c, 0) to (a, 0) is c -a. The sum of the distances from the foci to the vertex is

(a + c) -(c -a) = 2a.
If (x, y) is a point on the hyperbola, we can define the following variables: d2 = the distance from (c, 0) to (x, y) d1 = the distance from (c, 0) to (x, y) By definition of a hyperbola, d 2 -d 1 is constant for any point (x, y) on the hyperbola. We know that the difference of these distances is 2a for the vertex (a, 0). It follows that d 2 -d 1 = 2a for any point on the hyperbola. we will begin by applying the distance formula.

d 2 -d 1 = (x -(-c)) 2 + (y -0) 2 -(x -c) 2 + (y -0) 2 = (x + c) 2 + y 2 -(x -c) 2 + y 2 = 2a
Move radical to opposite side

(x + c) 2 + y 2 = (x -c) 2 + y 2 + 2a Square both sides (x + c) 2 + y 2 = (x -c) 2 + y 2 + 4a 2 + 4a (x -c) 2 + y 2 x 2 + 2cx + c 2 + y 2 = x 2 -2cx + c 2 + y 2 + 4a 2 + 4a (x -c) 2 + y 2 4cx -4a 2 = 4a (x -c) 2 + y 2 Divide by 4 cx -a 2 = a (x -c) 2 + y 2 Square both sides (cx -a 2 ) 2 = a 2 (x -c) 2 + y 2 c 2 x 2 -2a 2 cx + a 4 = a 2 x 2 -2cx + c 2 + y 2 Set b 2 = c 2 -a 2 (c 2 -a 2 )x 2 -a 2 y 2 = a 2 (c 2 -a 2 ) x 2 b 2 -a 2 y 2 = a 2 b 2 Divide both sides by a 2 b 2 x 2 b 2 a 2 b 2 - a 2 y 2 a 2 b 2 = a 2 b 2 a 2 b 2 x 2 a 2 - y 2 b 2 = 1.
This equation defines a hyperbola centered at the origin with vertices (±a, 0) and covertices (0, ±b).

.1.2 Geometric locus in dimension 3

Let O k = (0, 0, c) and O l = (0, 0, -c) be the foci of a hyperboloid. The hyperboloid of two sheets is the set of all points (x, y, z) such that the difference of the distances from (x, y, z) to the foci is constant.

O k -κ x -O l -κ x = R k -R l . We set K = R k -R l , O k -κ x = O l -κ x + K x 2 + y 2 + (z -c) 2 = x 2 + y 2 + (z + c) 2 + K Square both sides x 2 + y 2 + (z -c) 2 = x 2 + y 2 + (z + c) 2 + K 2 + 2K x 2 + y 2 + (z + c) 2 x 2 + y 2 + z 2 -2cz + c 2 = x 2 + y 2 + z 2 + 2cz + c 2 + K 2 + 2K x 2 + y 2 + (z + c) 2 Simplify expressions -4cz -K 2 = 2K x 2 + y 2 + (z + c) 2 Square both sides (-4cz -K 2 ) 2 = 2K x 2 + y 2 + (z + c) 2 2 16c 2 z 2 + 8cK 2 z + K 4 = 4K 2 x 2 + y 2 + (z + c) 2
Divide by 4

4c 2 z 2 + 2cK 2 z + K 4 4 = K 2 x 2 + y 2 + (z + c) 2 4c 2 z 2 + 2cK 2 z + K 4 4 = K 2 x 2 + y 2 + z 2 + 2cz + c 2 -K 2 x 2 -K 2 y 2 + (4c 2 -K 2 )z 2 = K 2 c 2 - K 4 4 = K 2 c 2 - K 2 4 = K 2 4c 2 -K 2 4 Set b 2 = c 2 - K 2 4 = 4c 2 -K 2 4 -K 2 x 2 -K 2 y 2 + 4b 2 z 2 = K 2 b 2 If K 2 = 0, divide both sides by K 2 b 2 - 1 b 2 x 2 - 1 b 2 y 2 + 4 K 2 z 2 = 1.
This equation defines a hyperboloid of two sheets. Also, this equation has one positive eigenvalue and two negative eigenvalues.

.

Geometric locus in dimension n

Let O k = (0, 0, • • • , 0, c) and O l = (0, 0, • • • , 0, -c) be the foci of a hyperboloid, The hyperboloid of two sheets is the set of all points

(x 1 , • • • , x n ) such that the difference of the distances from (x 1 , • • • , x n ) to the foci is constant. O k -κ x -O l -κ x = R k -R l . We set K = R k -R l , O k -κ x = O l -κ x + K x 2 1 + x 2 2 + • • • + x 2 n-1 + (x n -c) 2 = x 2 1 + x 2 2 + • • • + x 2 n-1 + (x n + c) 2 + K Square both sides x 2 1 + x 2 2 + • • • + x 2 n-1 + (x n -c) 2 = x 2 1 + x 2 2 + • • • + x 2 n-1 + (x n + c) 2 + K 2 + 2K x 2 1 + x 2 2 + • • • + x 2 n-1 + (x n + c) 2 (x n -c) 2 = (x n + c) 2 + K 2 + 2K x 2 1 + x 2 2 + • • • + x 2 n-1 + (x n + c) 2 x 2 n -2cx n + c 2 = x 2 n + 2cx n + c 2 + K 2 + 2K x 2 1 + x 2 2 + • • • + x 2 n-1 + (x n + c) 2 Simplify expressions -4cx n -K 2 = 2K x 2 1 + x 2 2 + • • • + x 2 n-1 + (x n + c) 2 Square both sides (-4cx n -K 2 ) 2 = 2K x 2 1 + x 2 2 + • • • + x 2 n-1 + (x n + c) 2 2 16c 2 x 2 n + 8cK 2 x n + K 4 = 4K 2 x 2 1 + x 2 2 + • • • + x 2 n-1 + (x n + c) 2 Divide by 4 4c 2 x 2 n + 2cK 2 x n + K 4 4 = K 2 x 2 1 + x 2 2 + • • • + x 2 n-1 + (x n + c) 2 4c 2 x 2 n + 2cK 2 x n + K 4 4 = K 2 x 2 1 + x 2 2 + • • • + x 2 n-1 + x 2 n + 2cx n + c 2 -K 2 x 2 1 -K 2 x 2 2 -• • • -K 2 x 2 n-1 + (4c 2 -K 2 )x 2 n = K 2 c 2 - K 4 4 = K 2 c 2 - K 2 4 = K 2 4c 2 -K 2 4 Set b 2 = 4c 2 -K 2 4 -K 2 x 2 1 -K 2 x 2 2 -• • • -K 2 x 2 n-1 + (4c 2 -K 2 )x 2 n -K 2 b 2 = 0.
This equation is a quadratic form. The matrix form of this equation is:

A =       -K 2 0 • • • 0 0 -K 2 • • • 0 . . . . . . . . . . . . 0 0 • • • 4c 2 -K 2      
The eigenvalues of A are:

λ 1 = -K 2 , • • • , λ n-1 = -K 2 and λ n = 4c 2 -K 2 .
Thus, there are one positive eigenvalue because c > K 2 and (n -1) negative eigenvalues, then the locus of the set of all points (x 1 , • • • , x n ) is a two-sheet hyperboloid.

Chapter 4 Consolidation Kernel

In this chapter, we introduce a novel kernel function obtained as a Fourier transform of a Gaussian mixture model with the purpose of detecting translation invariance inside classes. It is close to existing kernels but has never been expressed in this precise way. We have applied it successfully on several datasets in the context of machine learning using multiclass support vector machines.

Introduction

Kernel methods are robust statistical learning techniques [25,27], widely applied to various learning problems due to their versatility and good performance. Applications are wide and cover all possible structured or unstructured data types, e.g., general discrete structures [12], strings [18], weighted automata [4], etc. The only theoretical constraint is to have a positive type function or symmetric positive semidefinite (PSD) kernel [3], which implicitly specify an inner product in a reproducing kernel Hilbert space (RKHS). Thus, every data analysis algorithm that only makes use of inner products between data vectors can be transformed into a kernel method by the kernel trick, which consists in replacing the inner product by an arbitrary kernel function.

Kernel methods have become popular for various kinds of machine learning tasks, the most famous being the support vector machine (SVM) for classification [5]. SVM with a positive semidefinite kernel matrix has been applied successfully in many classification tasks including image retrieval, face recognition, and micro-array gene expression data analysis ([6, 25, 31]). Furthermore, in practice, it can prove successful even with indefinite kernels [1,8,10,19,28].

In this chapter, we address the problem of incorporating transformation invariance in a kernel used for classification. We introduce a new kernel constructed from the Fourier transform of a Gaussian mixture function. The underlying principle is that if a translation inside a class cannot be used to make closer points of different classes, then it could be used as a translation invariant. This is achieved by clustering classes into subclasses and reviewing the translations between subclasses centers. The simplest example we have in mind is the XOR case.

The rest of the chapter is organized as follows. In the following section, we review existing work dealing with the kernel design. Section 4.3 presents our kernel. The comparative study allowing its evaluation is the subject of Section 4.4. At last, we draw conclusions in Section 4.5.

State of the art on the transformation invariant kernels

We give a brief review of existing literature on kernel design. Kernels have been designed for a variety of data: graphs [15,9,30], string kernels [18,14,23] and hidden Markov models [13,32], to name just a few. For a good review, we can refer to the article of [16].

When it comes to transformation invariance, the simplest idea is based on the generation of virtual examples [22,21]. In this approach, new examples are created using the transformation at hand (translation or rotation for example) to enlarge the training set. A variant of it is the virtual support vector method [24]. There, the virtual examples are only generated from the support vectors (that utterly define the boundaries between the categories). The drawback is the enlarged memory and time complexities due to additionnal points.

Very close kernels to the virtual support vector method are the jittering kernels [7,8], where the transformation invariance is in the kernel itself, for instance κ * (x, x ) may be computed from a kernel κ using T * = argmin T ∈T κ(x, x) + κ(T x , T x ) -2κ(x, T x ), where T is a transformation group and κ * (x, x ) is equal to κ(x, T * x ). A similar approach is the tangent distance kernels which rely on the computation of the distance between sets of points R x and R x associated to the original points x and x and obtained by all possible transformations. This has been originally incorporated in SVMs as TD kernels in [10] and extensively studied in [29] for neural networks.

All these kernels can be generalized by computing an average kernel over all transformations. This gives rise to the Haar-integration kernel [26,11] defined for a standard kernel κ 0 and a transformation group T , which contains the admissible transformations [?, see]for a complete definition]ShulzMirbach1994. The idea is to compute the average of the kernel output κ 0 (T x, T x ) over all pairwise combinations of the transformed examples (T x, T x ), ∀ (T, T ) ∈ T 2 . The HI-kernel κ of κ 0 with respect to T is thus Finally, in this chapter we will make a particular use of the spectral mixture base kernels [34,35] in Equation (4.1):

κ SM (x, x ) = Q q=1 a q |Σ q | 1/2 (2π) p/2 exp - 1 2 Σ 1/2 q (x -x ) 2
2 cos ( x -x , 2πµ q 2 ) . (4.1)

The kernel κ SM has been defined for any parameters θ = (a q , µ q , Σ q ) 1 q Q thanks to Bochner's theorem and the flexibility of Gaussian mixture models. The underlying idea was to mimick the expressive power of deep learning architectures. Here, we will benefit from its flexibility to express translation invariance in data sets.

Consolidation kernel

The present work is inspired from a simple observation: a class can be so sparse that it becomes separated into several clusters. The idea is here to design a kernel bringing together these clusters. We proceed in the following way. First, each class is fragmented into a number of relevant subclasses. Second, we consider the directions given by all the vectors c 1 c 2 obtained in the following way: As, h d (t) is too complex to handle, we resort to a m-order Fourier expansion of h d which stands as follows:

h m d (t) = 1 3 + m j=1 a j cos 2πjt d
where a j are the Fourier coefficients of h d and are given by a j = 4 j 2 π 2 . The details are provided in the appendix. More precisely, our kernel, named consolidation kernel, is defined in the following way: Definition 4.1. The consolidation kernel κ is defined by: ∀(x, x ) ∈ (R p ) 2 , κ(x, x ) = τ 0 exp -

1 2 σ 2 0 x -x 2 2 + M i=1 τ i h d i c i 1 -c i 2 d i , x -x 2 exp{- 1 2 σ 2 i x -x 2 2 }
with M i=0 τ i = 1 and 1. k(x, x) = 1 for all x ∈ R p .

d i = c i 1 -c i 2 2 .
2. If M = 1 and τ 0 = 0, the kernel is translation invariant in the following sense κ(x + ν 1j , y) = κ(x, y) with ν 1j = j(c 1 1 -c 1 2 ).

Proof. This is immediate, indeed on one hand we have:

κ(x, x) = τ 0 e 0 + M i=1 τ i h d i (0)e 0 = 1
and on the other hand: Table 4.1: Information about the UCI data sets and Kaggle used in the experiments. The results produced by the WW-M-SVM for these data sets are given in Table 4.1. For each data set, we compare in Table 4.2 the training error rate and the recognition rate on the test set for the two kernels, with the parameter of σ given by 5 * dim(data). We observe that the Gaussian kernel is systematically outperformed.

κ(x + ν 1j , y) =h d 1 c 1 1 -c 1 2 d 1 , x + ν 1j -y =h d 1 jd 1 + c 1 1 -c

Consolidation Kernel

Conclusion

In this chapter, we have introduced a particular case of the spectral mixture kernel where emphasis has been put on translation invariance. Experimental results have proved that this kernel is worth being used considering in particular that it does not involve much more computation compared to a simple kernel as the Gaussian kernel. Perspectives would involve other ways of adding properties to the kernels and dealing with high-dimensional data.

Proposition .3. The Fourier series associated to the function of h d is written as follows:

Conclusion

This thesis contributes to provide a new kernel machines inspired by the multi-class support vector machine (M-SVM) and a novel kernel function obtained as a Fourier transform of a Gaussian mixture model.

In chapters 3, we are interested in are C-category pattern classification problems, under the assumption that all categories are finite. We introduced a new margin multi category classifier based on classes of vector valued functions with one component function per category. For each description, it provides a score per category and the selected category is the one associated with the highest score. This classifier is a kernel machine whose separation surfaces are hyperbolic and generalizes the SVM. We then established its main statistical properties. We founded an upper bound of the Rademacher complexity of this classifier this establishing by used Ledoux Talagrand Lemma. This bound converges to 0 at infinity, this showed that the classes of component functions are uniform Glivenko-Cantelli. We focus on parameterized truncated hinge loss function and we showed the Fisher consistency of this loss function. Finally, we established a guaranteed risk for our classifier using the bound of the Rademacher complexity. Furthermore, in chapter 4 we have introduced a new kernel function which obtained by the transform fourier of the gaussian mixture where emphasis has been put on translation invariance. We have applied this kernel on several datasets using multiclass support vector machines package and the results are compared to those obtained with the Gaussian kernel. Then, the experimental results proved that this kernel is worth being used considering in particular that it does not involve much computation in addition to a simple kernel as the Gaussian kernel.

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Data classification methods . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Support Vector Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.1 General operating principle of the SVMs . . . . . . . . . . . . . . . 8 1.3.1.1 Basic knowledge: Hyperplane, margin and support vectors 9 1.3.1.2 Why maximize the margin? . . . . . . . . . . . . . . . . . 10 1.3.1.3 Linearity and non-linearity . . . . . . . . . . . . . . . . . 11 1.3.2 SVM for binary classification . . . . . . . . . . . . . . . . . . . . . 12 1.3.2.1 Hard-SVM . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.2.2 Soft-SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.2.3 Soft-SVM with kernels . . . . . . . . . . . . . . . . . . . . 16 1.3.3 SVM for multi-class classification . . . . . . . . . . . . . . . . . . . 18 1.3.3.1 The combination of SVM bi-classes: a first step towards multi-class SVM . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.3.2 One versus All . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.3.3 One versus one . . . . . . . . . . . . . . . . . . . . . . . . 19

  Green squares and red dots are on the wrong side of the separating hyperplane. Soft-SVMs minimize the distances (ξ i ) of the points on the wrong side of the hyperplane and maximize the margin at the same time. . . . . . . . . . . . . . . . . . . . . 1.9 Classification case when two classes are strongly non-linearly separable. . . 1.10 Three classes separated by the method of one versus all with linear separator. 1.11 Multi-class classification by the method of one versus one. . . . . . . . . . 2.1 The initial data are transformed from the input space, by the transformation Φ, to a large space where the nonlinear problem becomes linear. . . . 4.1 Graph of function h d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 WW-M-SVM applied to XOR with both the consolidation kernel and the Gaussian kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 1 . 1 :

 11 Figure 1.1: The hyperplane H that separates the two sets of points.

Figure 1 . 2 :

 12 Figure 1.2: Support vectors.

Figure 1 . 3 :

 13 Figure 1.3: Optimal separating hyperplane, Support vectors and maximal margin.

1. 3 . 1 . 2

 312 Why maximize the margin?

Figure 1 . 4 :

 14 Figure 1.4: Best separating hyperplane.

  (a) Linearly separable case (b) Non-Linearly Separable case

Figure 1 . 6 :

 16 Figure 1.6: The nonlinear transformation of the data.

Figure 1 . 7 :

 17 Figure 1.7: Linearly separable classification problem in the (x 1 , x 2 ) space. Green squares and red dots represent different classes of points. The graph shows that for linearly separable training set, there are many possible hyperplanes separators and that the margin of two parallel supporting hyperplanes is equal to 2/ w 2 .

Figure 1 . 8 :

 18 Figure 1.8: Non-linearly separable classification problem. Green squares and red dots are on the wrong side of the separating hyperplane. Soft-SVMs minimize the distances (ξ i ) of the points on the wrong side of the hyperplane and maximize the margin at the same time.

Figure 1 . 9 :

 19 Figure 1.9: Classification case when two classes are strongly non-linearly separable.

Figure 1 . 10 :

 110 Figure 1.10: Three classes separated by the method of one versus all with linear separator.

Figure 1 .

 1 Figure 1.11: Multi-class classification by the method of one versus one.

  1. Preliminaries tions (personal communication by Volker Blanz), and later by other authors in various forms.

Definition 1 . 4 .

 14 (Pseudo-distance d 2,tn and d ∞,tn ) Let F be a class of real-valued functions on T . For n

Figure 2

 2

Figure 2 . 1 :

 21 Figure 2.1: The initial data are transformed from the input space, by the transformation Φ, to a large space where the nonlinear problem becomes linear.

Example 2 . 2 . 1 .

 221 (Hilbert Space Examples:) We give here several examples of Hilbert space • x, y = x T y. • x, y = ∞ i=1

. 9 )

 9 for every x, y ∈ R d . Example 2.4.8. (B-spline kernels:) Let B 0 = 1 B 1,d denoting the indicator function of the unit ball B 1,d of R d . For every function f, g : R d -→ R, let f g denote the convolution of f and g, that is

Definition 3 . 1 (

 31 Function classes H and H). Let κ be a kernel. The function class H is the class of all real-valued functions h on X such that∀x ∈ X , h(x) = R -O -κ x Hκ , for some R ∈ R * + and O ∈ H κ .Then the function class at the basis of a C-category hyperbolic kernel machine is the class H = HC . Definition 3.2 (Decision rule). For every function h = (h k ) 1 k C ∈ H, a decision rule dr h is specified in the following way:

  Thèse de Aya El Dakdouki, Université de Lille, 2019 © 2019 Tous droits réservés.

Lemma 3 . 1 .

 31 Let H be a function class satisfying Definition 3.1 with the following restrictions: sup x∈X κ x | Hκ Λ X , sup h∈ H R R max and sup h∈ H O Hκ Λ O . Then,

T 2 κ

 2 0 (T x, T x ) dT dT , under the condition of existence of the integral.

1. c 1 d 2 t 2 - 4 d t + 1 ,

 11 and c 2 are subclass centers associated with the same class; 2. the vector c 1 c 2 does not connect two subclasses of two different classes.Let {c i1 c i2 : i ∈ 1; M } be the set of all such vectors.Along each of them, we want the kernel value to oscillate somehow according to the periodic function h d defined on R as follows:∀k ∈ Z, ∀t ∈ [0, d) , h d (kd + t) = 4and depicted in Figure4.1.

1 Figure 4 . 1 :

 141 Figure 4.1: Graph of function h d .

Definition 4 . 2 .c i 1 -c i 2 c i 1 -c i 2 Proposition 4 . 1 (

 4211241 The consolidation kernel κ m is defined as:∀(x, x ) ∈ (R p ) 2 , κ m (x, x ) = τ 0 exp{-where a 0 , . . . , a m are the first terms of the Fourier series of h d i and µ ij = Properties of the kernel κ).

  2 cos(jtw) with w = 2π d .Proof. Since the function h d is even then its coefficients b j (h d ) = 0 and the coefficients a 0 (h d ) and a j (h d ) stand as follows:

  1.1 The hyperplane H that separates the two sets of points. . . . . . . . . . . . 1.2 Support vectors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Optimal separating hyperplane, Support vectors and maximal margin. . . . 1.4 Best separating hyperplane. . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 The nonlinear transformation of the data. . . . . . . . . . . . . . . . . . . 1.7 Linearly separable classification problem in the (x 1 , x

2 ) space. Green squares and red dots represent different classes of points. The graph shows that for linearly separable training set, there are many possible hyperplanes separators and that the margin of two parallel supporting hyperplanes is equal to 2/ w 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8 Non-linearly separable classification problem.

Thèse de Aya El Dakdouki, Université de Lille, 2019 © 2019 Tous droits réservés. lilliad.univ-lille.fr

Hyperbolic Kernel MachineThèse de Aya El Dakdouki, Université de Lille, 2019 © 2019 Tous droits réservés. lilliad.univ-lille.fr

Thèse de Aya El Dakdouki, Université de Lille, 2019 © 2019 Tous droits réservés. lilliad.univ-lille.fr Thèse de Aya El Dakdouki, Université de Lille, 2019 © 2019 Tous droits réservés. lilliad.univ-lille.fr

http://www.cis.upenn.edu/∼crammer/code-index.html Thèse de Aya El Dakdouki, Université de Lille,

© 2019 Tous droits réservés. lilliad.univ-lille.fr

Consolidation Kernel Thèse de Aya El Dakdouki, Université de Lille, 2019 © 2019 Tous droits réservés. lilliad.univ-lille.fr

Remerciements Acknowledgments

bourse, et je remercie Monsieur Alaa Terro qui m'a facilité toutes les démarches administratives.

Je tiens à exprimer mes sincères remerciements à tous les accorde longue vie en santé! Enfin, je réserve les derniers mots de ces remerciements à mon amour OMAR, merci chéri de ton soutien permanent dans les moments difficiles de mon travail, merci de tes conseils, ton encouragement, ton écoute et ta patience tout au long de ces années.

Proof.

by series integral comparison .

Consequently, in practice if one wants lower than 10 -2 , m should be taken at least equal to 41. By the preceding Proposition 4.2, we deduce that the kernel is not computationally too demanding as the number of terms is linear in M .

Application

Experimental Setup

The new kernel is assessed in the framework of a comparative study where the reference is provided by the Gaussian kernel. Both kernels are incorporated in a multi-class SVM (M-SVM): the one of [33], hereafter referred to as the WW-M-SVM. The package implementing it is MSVMpack [17]. For each data set and each class, five subclasses are obtained by means of the k-means algorithm.

XOR Problem

To gain insight into the way our method works, we start by studying a toy example: the well-known XOR problem. Then, the number of subclasses can be obviously set to two. In each subclass in the square [1, 9] 2 , 20 points are taken represented by rounds and crosses according to their class. This is the training set which is represented in the first drawing, once training is done, we test the classifier for the grid of 1000000 points represented in Figure 4.2 with the consolidation kernel k m and the Gaussian kernel. The translation invariance on this example can be clearly observed.

Data Set Description

We have used different data sets in the experiments: Yeast, glass identification, BUPA liver disorders,vertebral column, abalone, madelon, letter recognition, avila, breast, image segmentation, MAGIC Gamma Telescope, credit, EEG Eye Statex, HTRU2, wine and covertype datasets from the UCI machine learning repository [2] and the Banana dataset and Digit Recognizer from Kaggle.com. The USPS-500 data set is a subset of the USPS data provided with the MCSVM 1 software (K. Crammer's own implementation in C of his M-SVM model (CS) named MCSVM).

Each data set is divided into a training set and a test set. These data sets we used in this experiment are described in Table 4 To ascertain that the score difference between the Gaussian kernel and the consolidation kernel, we have tested statistically whether the difference in performance of two kernels is significant or not. Let p 1 and p 2 be the recognition rates of the Gaussian kernel and k m respectively. The hypothesis tests are given by:

The test statistic is calculated by the following formula:

Perspectives

The work presented in this thesis has an interesting potential for future research:

In chapter 3, we have presented a new hyperboloïd kernel machine for multi-class pattern recognition. We introduced an optimization problem of the hyperbolïd kernel machine. We reformulate the Problem 1 to obtain optimization problem with a slack variables ξ i .

Indeed,

• if ρ h (z i ) 0, then ξ i 1 =⇒ ξ i = 1 and φ 2,γ •ρ h (z i ) = 1, therefore ξ i = φ 2,γ •ρ h (z i ).

• if ρ h (z i ) > γ, then ξ i 1 -ρ h (z i ) γ , so ξ i = 0, therefore ξ i = φ 2,γ • ρ h (z i ).

• if ρ h (z i ) ∈ (0, γ), then ξ i 1 -ρ h (z i ) γ , therefore

As a perspective, further studies will be needed to solve this optimization problem. We will use the method of Metropolis Hasting.

Furthermore, we will use the consolidation kernel of the chapter 4 on this optimization problem and compare this result with another kernel.