Large-scale classification based on support vector machine

INTERNATIONAL DOCTORAL SCHOOL OF THE USC Ziad Akram Ali Hammouri PhD Thesis Large-scale classification based on support vector machine Santiago de Compostela, 2022 Doctoral Programme in Information Technology Research TESE DE DOUTORAMENTO LARGE-SCALE CLASSIFICATION BASED ON SUPPORT VECTOR MACHINE Ziad Akram Ali Hammouri ESCOLA DE DOUTORAMENTO INTERNACIONAL DA UNIVERSIDADE DE SANTIAGO DE COMPOSTELA PROGRAMA DE DOUTORAMENTO EN INVESTIGACIÓN EN TECNOLOXÍAS DA INFORMACIÓN SANTIAGO DE COMPOSTELA 2022 DECLARACIÓN DO AUTOR DA TESE Don Ziad Akram Ali Hammouri Presento a miña tese, titulada Large-scale classification based on support vector machine, seguindo o procedemento adecuado ao Regulamento, e declaro que: 1. A tese abarca os resultados da elaboración do meu traballo. 2. De ser o caso, na tese faise referencia ás colaboracións que tivo este traballo. 3. Confirmo que a tese non incorre en ningún tipo de plaxio doutros autores nin de traballos presentados por min para a obtención doutros títulos. 4. A tese é a versión definitiva presentada para a súa defensa e coincide a versión impresa coa presentada en formato electrónico. E comprométome a presentar o Compromiso Documental de Supervisión no caso de que o orixinal non estea na Escola. En Santiago de Compostela, Marzo de 2022 Asdo. Ziad Akram Ali Hammouri Autor da tese AUTORIZACIÓN DO DIRECTOR DA TESE Don Manuel Fernández Delgado Profesor Titular de Universidad da Área de Ciencias da Computación e Intelixencia Artificial, Departamento de Electrónica e Computación, Universidade de Santiago de Compostela, en condición de director da presente tese, titulada Large-scale classification based on support vector machine, INFORMA: Que a presente tese correspóndese co traballo realizado por Don Ziad Akram Ali Hammouri, baixo a miña dirección, e autorizo a súa presentación, considerando que reúne os requisitos esixidos no Regulamento de Estudos de Doutoramento da USC, e que como director desta non incorre nas causas de abstención establecidas na Lei 40/2015. En Santiago de Compostela, Marzo de 2022 Asdo. Manuel Fernández Delgado Director da tese I dedicate this work to my mother, father and brother Khaled for their endless support. 2 Contents O seguinte paso é o “clasificador de marxe branda”, que considera problemas de clasificación binarios que non se poden separar correctamente usando unha función ou fronteira linear. Neste caso, é imposible acadar un erro de entrenamento nulo, de modo que hai que atopar un equilibrio ou compromiso entre a minimización dos riscos empírico e estructural, o cal da lugar á aparición do “hiper-parámetro de regularización” para ponderar ambos riscos. Hai que destacar tamén que, neste caso da marxe branda no que as clases non se poden separar cunha fronteira linear, non so o tempo requerido depende da complexidade dos datos, senón que o proceso de resolución iterativa podería non rematar satisfactoriamente, é decir, non atopar unha solución válida, ou incluso podería non rematar nunca, como acontece con datos grandes. Neste punto aparece o segundo ingredente esencial no elevado desempeño da SVM, xunto coa minimización do risco estructural. Este segundo ingredente é o uso dunha proxección de tipo cerne non linear para potenciar a función de clasificación linear. Esta proxección emprégase para mapear os datos a un espazo de características de dimensionalidade meirande co orixinal, aumentando así as posibilidades de que unha función linear de clasificación acade resultados aceptábeis, noutras palabras, aumentando a separabilidade linear dos datos proxectados. A función cerne actúa como unha medida xeralizada de similaridade no espazo de características, e o denominado “truco do cerne” (kernel trick en inglés) permite efectuar esta proxección de modo implícito, sen necesidade dunha definición explícita para a mesma, xa que o cálculo dos parámetros entrenábeis da SVM so usa os valores da función cerne (similaridade xeralizada) aplicados sobre pares de datos. O único prezo a pagar é que o cerne debe ser adaptado aos datos dispoñíbeis, e isto require a sintonización dos seus hiper-parámetros. No caso do cerne gausiano, que é o máis empregado pola súa boa calidade, o único hiperparámetro é o ancho da función gausiana. Esta introducción á teoría da SVM remata explicando as estratexias para a súa extensión a problemas de clasificación multi-clase usando SVMs binarias. Isto introduce un custe computacional adicional que pode resultar importante cando o número de clases é elevado. Aínda que a tese actual centrarase exclusivamente en problemas de clasificación, a introducción describe tamén a extensión da SVM a problemas de regresión (support vector regression ou SVR). Para isto, emprégase unha función de custe ε -insensíbel, que so considera que a SVR comete un erro cando a distancia entre os valores verdadeiro e predito superan un umbral ε . O desenvolvemento matemático para problemas de regresión está relacionado co correspondente a clasificación, podéndose usar o mesmo tipo de cerne e sintonización de hiper-parámetros. Contents 3 Unha vez exposta a teoría da SVM para clasificación (denotada co acrónimo SVC), o capítulo 2 presenta a aproximación proposta nesta tese, denominada fast support vector classifier (FSVC) para convertir a SVC nun algoritmo eficiente que poda ser executado sobre un elevado número de datos, con dimensionalidade elevada e con moitas clases. Este método FSVC publicouse no artigo [16]. Preliminarmente, realízase unha revisión das causas da ineficiencia da SVC con datos grandes, derivadas directamente da teoría descrita no capítulo 1. Estas causas inclúen a execución dun proceso de entrenamento con complexidade crecente co cubo do número de datos, requerindo un espazo de almacenamento que medra co seu cadrado. O almacenamento dos vectores de soporte (datos seleccionados no entrenamento da SVC) e máis dos seus coeficientes asociados tamén require un espazo de almacenamento considerábel para datos grandes. Outro aspecto problemático é a sintonización dos hiper-parámetros, incluíndo a regularización, que afortunadamente pode non ser sintonizada xa que non é moi sensíbel, e os hiper-parámetros do cerne, como o ancho no caso do cerne gausiano, que si ten grande relevancia na calidade da aprendizaxe. A elevada dimensionalidade dos datos tamén afecta ao cálculo das distancias entre datos, necesarias para calcular o cerne. Finalmente, en problemas con moitas clases debe entrenarse un elevado número de SVCs binarias, que medra co cadrado do número de clases, ralentizando enormemente a execución da SVC. A partires dos problemas diagnosticados realízase unha exposición das ideas aportadas nesta tese para resolvelos. En primeiro lugar, proponse un algoritmo de entrenamento eficiente definido por unha fórmula analítica pechada que calcula os parámetros entrenábeis da SVM directamente a partir dos datos, sen necesidade de ningún método numérico iterativo de optimización que poda resultar lento ou incluso non rematar nunca, en caso de non atopar solucións válidas, como acontece coa SVC. Concretamente, o método proposto permite calcular os coeficientes do cerne aplicado aos datos de entrenamento e teste, e máis o termo independente da función de clasificación linear no espazo de características. Este método de entrenamento resulta moito máis rápido que a SVC clásica, pero ten o inconvinte de que require tódolos datos de entrenamento, o cal resulta lóxico tratándose dunha expresión pechada. Nembargantes, isto non é aceptábel cando se traballa con datos grandes. Comparada co entrenamento eficiente, o método clásico de entrenamento da SVC ten a vantaxe de que so require unha parte dos datos de entrenamento (os vectores de soporte), aínda que normalmente representa unha porcentaxe importante do total dos datos. Polo tanto, o entrenamento eficiente proposto non é dabondo, xa que a pesar de ser máis rápido, require almacenar tódolos datos, e non so os vectores de soporte. Por esta razón, a tese actual propón 4 Contents tamén un método eficiente para o cálculo do cerne, consistente en substituir os datos de entrenamento orixinais por unha representación comprimida dos mesmos. Con este obxectivo, créase unha colección de prototipos asociados a cada clase, que se van actualizando a medida que se percorren os datos de entrenamento. O número de prototipos está limitado, de maneira que o consumo de memoria e o número de iteracións non medra indefinidamente para datos grandes. Inicialmente, empréganse os datos de cada clase para definir os seus prototipos asociados, ata acadar o número máximo de prototipos por clase. A partir dese momento, cada dato actualiza o seu prototipo máis cercano entre os da clase á que pertence. Esta actualización require calcular as distancias entre o dato e os prototipos da súa clase, o cal é eficiente e escala co tamano dos datos porque o número de prototipos por clase está limitado e ten un valor reducido. A ponderación entre o prototipo actual e o dato novo ven definida polo número de datos usados ata o momento para actualizar o prototipo. O obxectivo é que cada prototipo sexa a media dos datos desta clase para os cais este prototipo foi o máis cercano. Finalmente, os prototipos de cada clase actúan como promedios dos seus datos orixinais, agrupados por similaridades, pero dunha maneira máis eficiente que almacenando os propios datos, o cal non é posíbel cando os datos son grandes. Unha das causas máis importantes da lentitude da SVC é a necesidade de sintonizar os hiper-parámetros, xa que isto require probar con distintos valores e seleccionar aqueles que proporcionan mellores resultados. Pero isto implica entrenar e testear a SVC con cada valor, o cal ralentiza enormemente o seu funcionamento. No caso da SVC con cerne gausiano, os hiper-parámetros son a regularización e o ancho do cerne. A tese actual contribúe cun método de sintonización que resulta moi eficiente porque non require executar a SVC para seleccionar o valor óptimo. Dado que o entrenamento eficiente antes mencionado non emprega proceso de optimización ningún, o hiper-parámetro de regularización desaparece en FSVC, quedando somentes a sintonización do ancho do cerne gausiano. Para seleccionar o seu valor, faise uso do concepto de función “cerne ideal”, entendida como unha función de similaridade xeralizada que separa correctamente as dúas clases, aplicándose sobre dous datos e valendo 1 se os dous son da mesma clase e 0 en caso contrario. O método proposto selecciona o ancho da gausiana que proporciona un cerne máis similar ao ideal. Para isto, calcula a matriz de cerne ideal e as matrices de cerne gausiano para cada valor do ancho nunha colección de valores pre-definida na literatura e considerada estándar. O ancho mellor é o que da unha diferencia media menor, en valor absoluto, entre ambas matrices. O tamano das mesmas está determinado polo número de datos, de modo que para executar este método en datos grandes Contents 5 é necesario usar os prototipos no canto dos datos orixinais. Hai que notar que este método de sintonización é válido para calquera tipo de cerne, non so para o cerne gausiano, e tamén para outros métodos baseados en cernes, como por exemplo kernel principal component analysis (Kernel PCA). É amplamente coñecido na literatura que con datos de elevada dimensionalidade o uso de cernes non lineares, como o gausiano, non aumenta o acerto comparado cun cerne linear, aínda que resulta moito máis lento. Isto débese a que a dimensionalidade orixinal xa é moi elevada, e proxectar a un espazo de meirande dimensión non aporta nada. O uso dun cerne linear en FSVC leva a unha simplificación dos cálculos, que pasan a ser extremadamente eficientes. Con respecto á clasificación multi-clase, FSVC usa por defecto a aproximación one-vs-one (OVO), con varias FSVCs binarias que separan entre pares de clases. O número de FSVCs binarias medra cadráticamente co número de clases, o cal resulta inaceptábel cando este último é moi elevado. Neste caso, FSVC pode usar a estratexia one-vs-all (OVA), que so necesita tantas FSVCs binarias como clases, o cal resulta moito máis eficiente en datos grandes con moitas clases. O capítulo 2 reporta o algoritmo FSVC completo, incluíndo o cálculo eficiente do cerne mediante prototipos, a sintonización eficiente do ancho do cerne gausiano, a clasificación multi-clase usando as estratexias OVO e OVA para números de clases baixo e alto, respectivamente, e as etapas de entrenamento e teste da FSVC binaria, usando por defecto un cerne gausiano ou linear, este último preferíbel con datos multi-dimensionais. Tamén se realiza unha análise da complexidade computacional de FSVC, que é linear nos números de entradas e de datos de entrenamento e teste, e cadrático ou linear no número de clases usando OVO ou OVA, respectivamente. O traballo experimental empregou unha extensa colección de 22 datos de pequeno tamano (menos de 15000 datos, dimensionalidade ata 617 e ata 26 clases) e outros 22 datos de tamano grande (31.5 millóns de datos, dimensionalidade ata 30000 e ata 131 clases). Analízase detalladamente o comportamento dos distintos elementos de FSVC: entrenamento eficiente, cálculo eficiente do cerne, sintonización eficiente do ancho de cerne, cerne linear para dimensionalidades elevadas e aproximación OVA para datos con moitas clases. Executáronse 4 versións alternativas de SVC: con e sen entrenamento eficiente, cálculo eficiente do cerne (é decir, uso de prototipos) e sintonización eficiente do ancho do cerne gausiano. Tamén se executaron 6 versións de FSVC: con e sen entrenamento eficiente, cálculo eficiente do cerne (prototipos), sintonización eficiente, cerne linear para datos de elevada dimensionalidad, aproximación 6 Contents OVA para datos con moitas clases, e cerne linear con OVA para datos multi-dimensionais con moitas clases. Comparando as distintas versións de SVC, o factor que máis reduce o acerto é o entrenamento eficiente, mentres a sintonización eficiente incluso aumenta o acerto e os prototipos reducen lixeiramente o acerto. Considerando a sintonización eficiente, para algúns datos o ancho que minimiza a diferencia media absoluta entre as matrices de cerne ideal e gausiana pode non proporcionar o mellor acerto, caso no cal selecciónase o ancho que maximiza a derivada desta diferencia. O método FSVC comparouse coa SVC gausiana e linear implementadas polas librarías LibSVM e LibLinear, consideradas os estándares de ouro para SVM con cernes gausiano e linear, respectivamente, e máis co direct kernel perceptron (DKP), que é unha aproximación eficiente anteriormente proposta para a SVC. O acerto de FSVC é moi cercano á SVC con cerne gausiano e ó DKP, e superior á SVC linear. Ademais, FSVC é moito máis rápida que as outras alternativas. Cos datos grandes ata 31 millóns, 30,000 entradas e 131 clases, onde a SVC gausiana ou o DKP non poden ser executados, a FSVC execútase en tódolos datos mentres a SVC linear falla nos máis grandes, aínda que está deseñada específicamente para datos de elevada dimensionalidade. A FSVC tamén se comparou con varias implementacións eficientes de SVC para datos grandes, incluindo primal estimated sub-gradient solver for SVM (Pegasos-SVM), SVM with sublinear importance-sampling bi-stochastic algorithm (SVM-SIMBA), indefinite core vector machine (ICVM) e doubly stochastic gradient (DSG), que obtiveron menos acerto que FSVC sendo máis lentos e non podendo ser executados nos datos grandes nos que FSVC si se executou. A sintonización eficiente revelouse como a parte do algoritmo FSVC que máis contribúe a acelerar a execución comparada con SVC, mentres o entrenamento eficiente e o cálculo eficiente do cerne (prototipos) son similares entre si pero contribúen bastante menos. Tamén se comparou FSVC co método steady-state genetic algorithm for instance selection (SGA), un popular algoritmo evolucionario para a selección de patróns de entrenamento, revelando que a selección xenética é lenta e non pode aplicarse con datos moi grandes, resultando limitada a datos pequenos onde a SVC clásica xa se executa sen reducción dos datos. Un dos aspectos importantes de FSVC é o manexo da memoria RAM, xa que isto permite a súa execución en datos dun tamano case arbitrariamente elevado sen que se produzan erros por falta de memoria. É decir, aínda que o entrenamento sexa lento, non fallará por causa dunha memoria insuficiente. Para isto, realizouse un estudo do consumo de memoria de FSVC, elaborándose un algoritmo que selecciona automáticamente o tamano do bloque de datos a ler Contents 7 dende disco. Este bloque é maior ou menor dependendo da memoria dispoñíbel e do tamano dos datos, evitando fallos de memoria e acelerando ou ralentizando a execución con datos pequenos ou grandes. A eficacia deste método probouse executando exitosamente FSVC nos datos grandes incluso con memoria limitada, mentres a SVC linear fallou na maioría destes datos. Esta regulación do tamano dos bloques de datos permite executar FSVC sobre datos grandes incluso en dispositivos con baixa memoria ou potencia computacional. O método proposto para a sintonización eficiente dos hiper-parámetros do cerne gausiano en FSVC é a aportación desta tese que máis contribúe a acelerar a execución de FSVC comparada con SVC. Por este motivo, o capítulo 3 presenta un estudo máis detallado deste algoritmo, denominado ideal kernel tuning (IKT), como método de sintonización do ancho do cerne gausiano para a SVC clásica. Este traballo foi enviado para a súa publicación [15], atópandose neste momento en segunda revisión. A sección 3.1 realiza unha revisión dos métodos existentes na literatura para a selección de modelos na SVM. A idea básica de IKT (sección 3.2) consiste en seleccionar o ancho que minimiza a diferencia media en valor absoluto entre as matrices de cerne ideal e de cerne gausiano, esta última dependente do ancho. Dado que este método baséase nas dúas matrices, ambas con tamano definido polo número de datos, a súa formulación para a SVC orixinal require o uso de prototipos que permitan a súa execución sobre datos grandes. Polo tanto, a sintonización eficiente débese executar conxuntamente co cálculo eficiente do cerne descrito no capítulo 2, é decir, xunto co uso de prototipos. Nalgúns datos, a diferencia mínima entre as matrices de cerne ideal e cerne gausiano correspóndese cos valores mínimo ou máximo do ancho da gausiana. Nestes casos o acerto máximo non se acada na diferencia mínima, senón na máxima derivada da diferencia, de modo que o ancho selecciónase como o que maximiza a derivada desta diferencia. Na clasificación multi-clase, todas as SVCs binarias usan o mesmo valor do ancho, seleccionado considerando as dúas clases máis poboadas. O traballo experimental (sección 3.3) compara sobre un conxunto de 37 problemas de clasificación de ata 1 millón de patróns o método proposto IKT con outras 5 técnicas competidoras na literatura, todos eles usados para seleccionar o ancho do cerne para entrenar unha SVC clásica. Estas técnicas son o kernel density estimation (KDE), que selecciona o ancho óptimo maximizando unha medida de separabilidade entre clases baseada no cerne gausiano; o método estándard grid-search (GS), que selecciona o ancho que maximiza o acerto sobre un conxunto separado de datos; a optimización xenética; a optimización mediante particleswarm optimization (PSO); e a optimización bayesiana. Os métodos GS, xenético, PSO e 8 Contents bayesiano requiren entrenar e testear varias veces a SVC para seleccionar o ancho da gausiana, e polo tanto espérase que sexan máis lentos. O IKT acada un dos mellores acertos, so lixeiramente por debaixo dos métodos xenético e bayesiano. Ademais, IKT é 105 veces máis rápido que KDE, 163 veces máis rápido que GS, e miles de veces máis rápido que o xenético, PSO e bayesiano. Esta diferencia en velocidade aumenta co tamano dos datos. De feito, os métodos xenético e PSO non poden ser executados nos 6 datos máis grandes da colección. Considerando o consumo de memoria RAM, o método KDE, que é o segundo máis rápido logo de IKT, require 400 veces máis memoria que IKT, mentres que os outros métodos requiren memorias similares a IKT. De feito, IKT non require máis de 10MB en ningún caso, mentres KDE chega a usar ata 25GB nos datos máis grandes. Globalmente, IKT acada o mesmo acerto pero sendo moitísimo máis rápido que as alternativas existentes e mantendo un baixo consumo de memoria. Polo tanto, é unha opción moi interesante para datos de calquera tipo, pequenos, medianos ou grandes, aínda que neste último caso, unha vez seleccionado o ancho óptimo, a SVC clásica non podería ser executada por usar demasiados datos de entrenamento. O traballo futuro inclúe extender a formulación de FSVC a problemas de regresión; deseñar aproximacións máis eficientes que OVO e OVA para datos grandes con moitas clases; definir un entrenamento eficiente que acede mellores taxas de acerto sen perder velocidade de execución; e empregar a información proporcionada pola matriz de cerne para mellorar a eficiencia da SVC. Palabras chave: aprendizaxe automática, clasificación, máquina de vectores de soporte, datos grandes, sintonización de hiper-parámetros, cerne gausiano, dimensionalidade elevada, clasificación multi-clase. CHAPTER 1 THE SUPPORT VECTOR MACHINE The current thesis belongs to the field of machine learning, a field of artificial intelligence that is classical but has recently achieved great interest from the research community. Machine learning algorithms or models are oriented to extract information from data, in two main paradigms. The supervised methods use data in order to predict some value (named often as “output”) using other values (named usually as “inputs”). The value to be predicted is used as a label in order to adjust the method (during a stage named “training”) in such a way that it reproduces the relation between inputs and output. This label is what provides “supervision”. The unsupervised methods extract information from the available data without any kind of label, in order to create groups of data that are similar in some sense, as in the “clustering” methods or to reduce the number of inputs (data dimensionality) by removing redundant or unuseful information. There are also additional machine learning paradigms, such as reinforcement learning, where the learning machine is rewarded or punished depending on the quality of its predictions without supervised labels, or semi-supervised learning, that combines unlabeled and a small amount of labeled data in order to refine the quality of unsupervised learning in scenarios where labels are very expensive to achieve. Within the supervised paradigm, classification is one of the kinds of problems most studied in the literature. The objective of classification is to assign a discrete (class) label as output to a vector of input data, that is used by the machine to predict the class label, expectably with a reasonable accuracy or reliability as if it were an oracle. The other relevant kind of problems in machine learning is commonly known as regression, that is conceptually similar to classification but the output to be predicted is a continue numeric value instead a discrete class label. 10 Chapter 1. The support vector machine Indeed, both classification and regression can be considered as the same problem: to predict the values of an unknown function (output) using other data (inputs). This prediction requires to learn (i.e., to calculate a value for) a set of trainable parameters from a collection of examples, each composed by the the value of the unknown function and by the corresponding input data. During training, the set of parameters are adjusted to fit the predicted function to the collection of examples. This collection is expected to be representative enough of the function to be learnt, in order to allow a good accuracy in the prediction issued by the machine learning model. When the value to be predicted is a discrete class label, classification is achieved. From this point of view, regression can be considered more general than classification or including classification as a specific case. However, classification is much more popular in the practice than regression, so in general many machine learning techniques are more oriented to classification than to regression, while others are equally used for both tasks. There is a wide variety of well-known machine algorithms that are able to learn to predict a function, either continuous or discrete, such as k-nearest neighbors, linear and logistic regression, decision trees, neural networks and ensembles of different families, such as bagging, boosting and random forests, among others. In the current thesis we will focus on one of the classifiers that achieve state-of-the-art performance: the so called support vector machine (SVM). This algorithm was initially proposed in 1960’s, but it achieved a wide popularity in the middle 1990’s, when Corinna Cortes and Vladimir Vapnik [5] formulated it for general machine learning. Since then, the SVM became widely used both for classification (support vector classifier, SVC) and regression (support vector regression, SVR), due to its high performance, specially using radial basis kernels, that make it a state-of-the-art machine learning method over a wide variety of applications [1] because: 1) it optimizes a convex function without local extremes that may drive training into sub-optimal solutions, as happens with some neural networks; and 2) it is easy of use and configure, mainly with respect to the hyper-parameter tuning, because a standard collection of hyper-parameter values is valid for most applications [20]. 1.1 Hard-margin SVM In the following, the notation defined by [40] and listed in Table 1.1, will be used. Let {xn}N n=1 be the set of training data (henceforth named as patterns). Vectors are in lowercase bold font, as columns, while matrices are designed with bold uppercase symbols. Let Nbe the number 1.1. Hard-margin SVM 11 of training patterns. Let xn= (xn1,...,xnI)be the n-th training pattern, where Iis the number of inputs, or the dimensionality of the input pattern. In the following, we will consider a twoclass (or binary) SVC, so let Q=2 be the number of classes. Let cn∈ {1,2}be the class label of xn. We also define yn=−1 (resp. yn=1) for xnwith cn=1 (resp. cn=2). Symbol Meaning Symbol Meaning NNumber of training patterns INumber of inputs xnn-th traning pattern xni i-th input of xn QNo. of classes cnClass label ∈ {1...Q}of xn ynTrue output ∈ {±1}for xnHSVC hyperplane wVector that defines HbOffset of H xTest pattern TNumber of test patterns ρ Margin of HHnFunction for H:Hn=wTxn+b LLagrange function α nHard Lagrange multiplier for xn VSet of indices of support vectors CRegularization hyper-parameter ξ nSlack variable β nSoft Lagrange multiplier for xn σ RBF kernel spread ε With of insensitive loss function ξ n, ξ ∗ nUpper,lower slack variables α n, α ∗ nUpper, lower Lagrange multipliers PNo. training and test patterns Table 1.1: Symbols used in the text and meaning of each one. Let us consider a linearly separable classification problem, so that a linear classification function is able to discriminate correctly the samples (or training patterns) of both classes without errors. In this case, the SVC is named “hard-margin classifier”. A linear classifier is defined by a hyperplane, named as H, whose equation is H(x) = wTx+b=0, where w is a column vector perpendicular to H,while wTis the transposed of w(row vector), xis the column vector where His calculated and bis the hyperplane offset, so that b=H(0). The output y(x)of the binary SVC, that is a linear classifier, for a pattern xis given by: y(x) = sign[H(x)] = sign(wTx+b)(1.1) where sign(t) = 1 when t≥0 and sign(t) = −1 otherwise, so the classifier output is +1 on one side of Hand output −1 on the other side. Note that wand bare the trainable parameters of the SVC. The distance φ nbetween Hand a training pattern xnis given by: φ n=|Hn| |w|=|wTxn+b| |w|(1.2) 18 Chapter 1. The support vector machine L(w,b,~ ξ ,~ α ,~ β ) = |w|2 2+C N ∑ n=1 ξ n− N ∑ n=1 β n ξ n− N ∑ n=1 α nyn(wTΦ(xn)+b)−1+ ξ n(1.30) Derivating Lwith respect to wand equaling to zero gives: w= N ∑ n=1 α nynΦ(xn)(1.31) Derivating Lwith respect to b,~ ξ ,~ α and ~ β , we achieve the dual optimization problem, i.e., find {~ α ,b}: maximize L(~ α ) = ~ α T1−~ α TK~ α 2,s.t. ~ α Ty=0,0≤ α n≤C β n ξ n=0, α n(yn"N ∑ m=1 α mK(xn,xm)+b#−1+ ξ n)=0,n=1,...,N(1.32) Now, the kernel matrix K, of size N×Nas in the previous sections, has elements defined as Knm =K(xn,xm). Using a non-linear kernel, the direct calculation of the weight vector w is not possible because the space where wresides is hidden or implicit. Therefore, just the Lagrange multipliers α nmust be calculated using an optimization method. As in the hard and soft margin case, α n=0 except when xnis a support vector. Once ~ α is calculated, wis given by eq. 1.31 and the SVC output is: y(x) = signwTΦ(x)+ b=sign"∑ n∈V α nynΦ(xn)TΦ(x)+b#= =sign"∑ n∈V α nynK(xn,x)+b#(1.33) where the kernel trick Φ(xn)TΦ(x) = K(xn,x)was used again. The calculation of the weight vector win the feature space is replaced by the calculation of the kernel function K, given by some of the expressions in eqs. 1.26-1.29, for the support vectors {xn}n∈Vand the test pattern x. 1.4 Alternative SVM solvers Some other methods exist for training the SVC, including sub-gradient descent, that pursues to minimize directly: 1.5. Multi-class classification 19 J(w,b) = |w|2 2+C N ∑ n=1 max[0,1−yn(wTxn+b)] (1.34) An advantage of this method is that the number of required iterations does not scale very fast with N. A solver of this type is the primal estimated sub-gradient solver for SVM, named as Pegasos-SVM [39]. An alternative solver method is coordinate descent [19], that maximizes the dual form: J(~ α ) = ~ α T1−~ α TK~ α 2s.t. ~ α Ty=0,0≤ α n≤C,n=1,...,N(1.35) This method adjusts iteratively α nin the direction of ∂ J(~ α ) ∂α n for n=1,...,N, and projects ~ α on its nearest ~ α 0that verifies the constraints. The process iterates until an optimal ~ α is achieved. 1.5 Multi-class classification When the classification problem has Q>2 classes, it is reduced to several binary classification problems. The most common strategies are “one-vs-one” (OVO) and “one-vs-all” (OVA). The former uses a different binary SVC to discriminate between each pair of classes. This strategy requires Q(Q−1)/2 binary SVCs, each trained using only the training patterns of its pair of classes. The predicted class label is decided by voting among the binary SVCs. On the contrary, the OVA approach uses only Qbinary SVS, each discriminating between a class and the remaining ones, being trained with the whole training set. The OVO method usually achieves better performance, although for high Qthe number of required binary SVCs, that raises with Q2, may become inefficient compared to OVA, that often achieves lower performance but only requires Qbinary SVCs. Alternative approaches include directed acyclic graph SVC [34], that also uses Q(Q−1)/2 binary SVCs, error correcting output codes [9] and direct multi-class optimization [7]. 1.6 Support vector regression Although in this thesis we will center on classification, the SVM was also extended for regression problems. This was done by transposing the concept of support vector (a training pattern that is inside the hyperplane margin) to vectors that lie inside a margin around the value of the function (output) to be predicted. The support vector regression (SVR) only considers those 20 Chapter 1. The support vector machine training patterns for what the SVR output is farther from the true output than a threshold ε . This is implemented by the so-called ε -insensitive cost function, defined as: f(t, ε ) = (t|t| ≤ ε 0|t|> ε leading to the popular ε -SVR. Considering a kernel mapping Φ(x), the ε -SVR is a linear regressor in the feature space defined by: y(x) = wTΦ(x)+b(1.36) The slack variables ξ nand ξ ∗ ndefine the upper and lower margins, respectively, with respect to the true output yn: ξ n=max[0,(wTΦ(x)+b)−yn− ε ](1.37) ξ ∗ n=max[0,yn−(wTΦ(x)+b)− ε ](1.38) The primal optimizacion problem is the following: minimize |w|2 2+C N ∑ n=1 ( ξ n+ ξ ∗ n)(1.39) s.t. wTΦ(x)+b−yn≤ ε + ξ n(1.40) yn−wTΦ(x)−b≤ ε + ξ ∗ n(1.41) ξ n, ξ ∗ n≥0,n=1,...,N(1.42) Following a process analogous to the soft-margin classifier, we achieve the dual problem, defined by: minimize ∆~ α TK∆~ α 2+ ε N ∑ n=1 ( α n+ α ∗ n)+ N ∑ n=1 yn( α n− α ∗ n)(1.43) s.t. ~ ε T∆~ α =0,0≤ α n, α ∗ n≤C,n=1,...,N(1.44) where ∆~ α =~ α −~ α ∗and Kis the kernel matrix with elements {K(xm,xn)}N mn=1. Once ~ α and ~ α ∗are calculated, the output is given by: y(x) = ∑ n∈V ∆ α nK(xn,x)+b(1.45) 1.7. Objectives of this thesis 21 where ∆ α n= α n− α ∗ nand the offset bis calculated as: b=     yn−∑ m∈V α mymK(xm,xn)− ε α n<C yn−∑ m∈V α mymK(xm,xn)+ ε α ∗ n<C being xnany support vector. 1.7 Objectives of this thesis The current thesis is focused on the support vector machine with radial basis kernel for largescale classification problems. The objective of the work is to formulate a SVC-based classification method efficient enough to be executed on large datasets, either because the number of patterns, inputs or classes is high. In order to propose this method, several limitations of the classical SVC must be addressed. One of the main drawbacks of the SVC is the complexity of its training stage, derived from the need to solve a quadratic optimization problem whose speed and memory requirements strongly depend on the number of training patterns. This drawback hinders the execution of SVC on datasets larger than several tens of thousand patterns, depending on the number of inputs. Related to this issue is the selection of the support vectors, that is a very slow process when the training set is really large. On the other hand, the need to perform hyper-parameter tuning for the regularization and the kernel parameter(s), namely the spread when RBF kernels are used, also requires to execute many times the cycle of training and test over large datasets, and this strongly slows down the SVC execution. These issues will be studied and solutions will be proposed in the chapters 2 and 3 of the current thesis. Specifically, chapter 2 presents our proposal, named fast support vector classifier (FSVC), that is designed to be of low complexity and scalable with the dataset size. This method has been published in [16]. First, the reasons of the high computational cost of SVC for large datasets are analyzed. Then, the FSVC is described in sections 2.1-2.6, describing the differences with respect to SVC, reporting the FSVC pseudo-code and analyzing its computational complexity. Sections 2.7-2.18 report the results in terms of performance, time and memory requirements, discuss the experimental work and compare to other existing methods, including alternative SVM solvers, core vector machines and evolutionary traning set selection methods. Chapter 3 extends the efficient method proposed for hyper-parameter tuning, named ideal kernel tuning (IKT), for the classical SVC. This work that has been submitted for publication [15], being currently in second revision. Section 3.1 reviews the literature about 22 Chapter 1. The support vector machine model selection in SVC and section 3.2 describes the proposed algorithm. The results and comparison with other model selection methods in the literature are reported in section 3.3. Finally, chapter 4 presents the conclusions of this research. CHAPTER 2 FAST SUPPORT VECTOR CLASSIFIER There are several reasons that justify the low efficiency of SVC with RBF kernels on large datasets: 1. The calculation of the Lagrange multipliers { α n}n∈Vand of the offset brequires to solve a constrained quadratic optimization problem which with a complexity of O(N3), i.e., of order N3, or that raises with N3, where Nis the number of training patterns [23]. On the other hand, the required memory scales as O(N2). Besides, the SVC training requires to know simultaneously {xn}N n=1, so the whole training set must be stored in memory during training, which may be difficult with large Nand I. 2. After training, only the N′support vectors and coefficients {xn, α n}n∈V, and the offset b, must be stored in memory because the calculation of K(xn,x)for a test pattern x in eq. 1.33 requires to evaluate |xn−x|for n∈ V, and this requires to store {xn}n∈V. Although the number N′of support vectors verifies N′≤N, usually N′raises with N, so that even the storage of only the N′support vectors becomes a serious limitation for large Nand I. 3. The training process does not provide values for Cand σ , so their values must be previously selected, becoming hyper-parameters that must be tuned because their values, specially σ , have a strong influence over the SVC learning ability and test performance. Often, this tuning proceeds by selecting the values that provide the highest performance over separated validation sets (“grid-search” or related approaches), that requires to repeat the training-testing cycle of SVC so many times as the number of combinations 24 Chapter 2. Fast support vector classifier of values of Cand σ . This process may be expensive for large datasets. Alternative approaches exist [22, 43, 48], but they require either to iterate the train-test cycle or to perform calculations whose computational cost may also be unpractical for large-scale datasets. 4. With a large number Iof inputs, the calculation of differences |xn−xm|for the RBF kernel K(xn,xm)in eq. 1.32 requires large memory space for data storing and becomes very time-consuming. 5. When the number Qof classes is large, the OVO approach used by the SVC may be slow because Q(Q−1)2 binary SVCs are required, which becomes unpractical even for medium Qvalues. For instance, when Q=10 the number of required binary SVCs is Q(Q−1)2=45, so the training must be repeated 45 times. Note that usually the hyper-parameter tuning is performed only once and the selected values are used for all the binary SVCs. This high computational cost has been identified in the literature as one major drawback of the SVC [23]. There exist alternative methods of selection of training patterns [24, 31, 32], e.g. using evolutionary algorithms [35, 47], or clustering [4] in order to reduce the memory consumption or the number of iterations. However, these approaches do not allow to reduce a very large dataset to a size low enough to train a standard SVC on it. On the other hand, these methods have an intrinsic computational cost that limits its application to medium size datasets. They can not be applied to large datasets because they would not finish never. Other alternatives are core vector machines [44] and other coreset based methods, that compress the data providing a fast solution that approximates the optimal SVM on the whole data. These approaches have been applied in the literature to continuous unbounded data streams. Random features methods [21] such as double stochastic gradient [8] replace the RBF kernel by an explicit mapping to a random Fourier feature space, although the number of features required to achieve a competitive performance may reach about a hundred thousands, so these methods may also be costly in terms of time and memory. The solutions proposed in the current thesis to these drawbacks are described in sections 2.1 to 2.5. The proposed method, named fast support vector classifier (FSVC), for an efficient large-scale support vector classification [16] is compiled by algorithms 1-4 in section 2.6. The experimental work studies the performance of FSVC and the influence of the training algorithm (section 2.8), efficient kernel (2.9), spread tuning (2.10), large dimensionality (2.11) and 2.1. Efficient training 25 high number of classes (2.12). The FSVC has also been compared to other standard methods (section 2.13), other solvers (2.14) including some of the cited above, and evolutionary train set selection methods (2.17). Finally, the elapsed times and memory use are studied in sections 2.16 and 2.18, respectively. 2.1 Efficient training The high cost of the iterative numerical optimization process in the classical SVC makes it unpractical for large-scale datasets, so an efficient alternative for SVC should avoid it. The reduced SVM [25] and proximal parametrical SVC [49] use a faster closed-form solution for the training, but they are not practical for large datasets because they require the inversion of large matrices with N2elements. This section proposes an efficient training method that is inspired in the SVC ideas but is fast, direct (non-iterative) and has a closed-form analytical expression, without any numerical iterative optimization nor matrix inversion. 2.1.1 One pattern per class Let us consider a binary classification problem with only N=2 patterns x1and x2, with c1=1 and c2=2. Let us also consider a hyperplane Hwith equation H(x) = wTx+b=0 separating both classes in the feature space generated by a nonlinear kernel mapping Φassociated to a RBF kernel function as in eq. 1.26, although any other kernel might be used. The output of this linear classifier for a test pattern xis y(x) = sign(wTΦ(x) + b), where b=H(0)is the hyperplane offset and wis a vector in the feature space perpendicular to Hthat is chosen directed to the side of Hwhere Φ2=Φ(x2)with c2=2 is placed. The training must find {w,b}that maximizes the distance φ nfrom Φn, with n=1,2, to H. This distance is given by: φ n(w,b) = wTΦn+b |w|,n=1,2 (2.1) The choice of wimplies that φ 2>0 and φ 1<0. With only two patterns, the distance between patterns and hyperplane can be maximized selecting {w,b}such that φ 1=− φ 2and therefore: wTΦ1+b |w|=−wTΦ2+b |w|→b=−wT(Φ1+Φ2) 2(2.2) Replacing bin eq. 2.1, we have: 26 Chapter 2. Fast support vector classifier φ n=wT |w|Φn−Φ1+Φ2 2,n=1,2 (2.3) Since wpoints to the side of Hwhere Φ2is located, we must maximize φ 2and simultaneously minimize φ 1, so wmust be parallel to: Φ2−Φ1+Φ2 2=Φ2−Φ1 2(2.4) Excluding norm factors, wcan be selected as w=Φ2−Φ1. Replacing win eq. 2.2, using that wTΦ(x) = K(x2,x)−K(x1,x)and replacing {w,b}in the SVC output, its expresion remains: y(x) = sign(K(x2,x)−K(x1,x)+b),b=K(x1,x1)−K(x2,x2) 2(2.5) 2.1.2 Several patterns per class With N1,N2>1 training patterns for classes 1 and 2, the distance φ n(w,b)is given by the same eq. 2.1, but for n=1,...,N, with N=N1+N2. In order to calculate {w,b}, the hyperplane Hin the feature space should be placed half-way between both classes and with the optimal orientation to maximize the distance to patterns of both classes. To find such a hyperplane is a hard computational task that requires an iterative optimization process similar to eq. 1.30, and this is unpractical for large-scale datasets. A simpler alternative, whose performance might still be competitive, is to require that the average distance from the patterns of one class to H should be equal, and of opposite sign, to the same magnitude for the other class: ∑ n=1 φ n N1=−∑ n=2 φ n N2(2.6) where the notation “n=1” in the summation means “for all the training patterns xnwith cn=1”. Substituting φ nfrom eq. 2.1 to eq. 2.6 and multiplying by |w|, we achieve: ∑ n=1 wTΦn+b N1=−∑ n=2 wTΦn+b N2(2.7) b=−∑ n=1 wTΦn 2N1−∑ n=2 wTΦn 2N2(2.8) where Φn=Φ(xn). Analogously to the previous section, wmust be calculated to maximize the sum for both classes of the average distance between patterns and hyperplane. These 2.2. Efficient kernel calculation 27 distances are positives (resp. negatives) for class 2 (resp. class 1), so that wmust be selected in order to maximize the following amount: ∑ n=2 φ n(w,b) N2−∑ n=1 φ n(w,b) N1(2.9) Substituting φ n(w,b)from eq. 2.1 for n=1,...,N, we achieve: ∑ n=2 wTΦn+b N2|w|−∑ n=1 wTΦn+b N1|w|= =wT |w| ∑ n=2 Φn N2−∑ n=1 Φn N1!(2.10) This expression is maximized when wis parallel to the vector between parenthesis, so w can be selected as: w=∑ n=2 Φn N2−∑ n=1 Φn N1(2.11) Replacing win eq. 2.8, the offset bis given by: b=∑ nm=1 knm 2N2 1 −∑ nm=2 knm 2N2 2 (2.12) where knm =K(xn,xm) = ΦT nΦmand the sum over “nm =1” means “for all xnand xmwith cn=1 and cm=1”. Substituting wfrom eq. 2.11 on the classifier output, we achieve: y(x) = sign ∑ n=2 kn(x) N2−∑ n=1 kn(x) N1+b!(2.13) where kn(x) = K(xn,x) = ΦT nΦ(x)and bis given by eq. 2.12. This closed-form expression allows the direct calculation of the classifier output and should be faster than the iterative training methods. However, it requires to calculate {knm}nm=1and {knm}nm=2in order to achieve the offset b, and kn(x)for every test pattern xand for all the training patterns {xn}N n=1. 2.2 Efficient kernel calculation Since no selection of support vectors is done in eq. 2.13, the whole training set {xn}N n=1should be stored in memory, which is obviously not affordable with large datasets. Remember that 34 Chapter 2. Fast support vector classifier Algorithm 3: Two-class Fast SVC training. 1Algorithm: FSVCtrain({p1l}L1 l=1,{p2l}L2 l=1, σ ) Data: pql:l-th prototype of class q=1,2; σ : RBF kernel spread Result: S: binary FSVC 2RBF kernel only———————————————— 3K(pql,pqm, σ )←exp−|pql −pqm|2 2 σ 2 4{kqlm ←K(pql ,pqm, σ )}2,Lq q=1,lm=1 5b← L1 ∑ lm=1 k1lm 2L2 1 − L2 ∑ lm=1 k2lm 2L2 2 ;S ← {{pql}2,Lq ql=1,b, σ } 6Linear kernel only——————————————— 7w← L2 ∑ l=1 p2l L2− L1 ∑ l=1 p1l L1 8b← L1 ∑ lm=1 pT 1lp1m 2L2 1 − L2 ∑ lm=1 pT 2lp2m 2L2 2 ;S ← {w,b} Algorithm 4: Two-class Fast SVC test. 1Algorithm: FSVCtest(S,x) Data: S: binary FSVC; x∈IRI: test pattern Result: y∈IR: output of the binary FSVC 2RBF kernel: S={{pql}2,Lq ql=1,b, σ }———————— 3{kql(x)←K(pql ,x, σ )}2,Lq ql=1// K(pql ,x, σ )defined in line 3 of algorithm 3 4y(x)← L2 ∑ l=1 k2l(x) L2− L1 ∑ l=1 k1l(x) L1+b 5Linear kernel: S={w,b}———————————— 6y←wTx+b 2.6. Complexity analysis 35 of class cn(lines 2-11 of algorithm 1). Its complexity scales as O(NIL), although Lis a pre-defined constant that does not scale with the dataset size. 2. The spread tuning (lines 13-17 of algorithm 1) requires to calculate the (2L)2distances between the Lprototypes (of dimension I) of classes 1 and 2, and to calculate A( σ )for the 27 values of σ in Σ(eq. 2.23). This process is of complexity O(I). 3. With multi-class OVO classification, each of the Q(Q−1)/2 binary FSVCs requires (2L)2distances between prototypes to calculate {kqlm}2,L q=1,lm=1(eq. 2.19, line 16 in algorithm 1), which is of complexity O(IQ2). 4. The test step (lines 20-27 and 29-37 in algorithm 2 for OVO and OVA multi-class approaches, respectively, and algorithm 4 for two classes) requires 2Lvalues {kql (x)}2,L ql=1 for the Ttest patterns (see Table 1.1), of dimension I, and for the Q(Q−1)/2 binary FSVCs, which is O(Q2TI). Overall, the complexity of FSVC is O(NIQ2T), so it is linear in N,Iand Tand quadratic in the number of classes Q. This complexity depends only on the dataset size (N,I,Qand T), as opposed to the standard SVC, whose speed is known to be different for datasets of the same size depending on their classification complexity (e.g., level of class overlap). The FSVCL, which uses linear kernel (see subsection 2.11 below), has not the item 2 in the previous list, but it keeps the quadratic complexity in Q. However, FSVCA and FSVCLA use the OVA approach (subsection 2.12), so their complexity on items 3-4 is linear in Q(the sorting of line 33 in algorithm 2 does not scale with the dataset size because only a constant number Lof values are involved). −1 0 1 −1 −0.5 0 0.5 1 −1 0 1 −1 −0.5 0 0.5 1 −1 0 1 −1 −0.5 0 0.5 1 Figure 2.1: Left: circle-in-the-square dataset. Center: prototypes created by FSVC. Right: classification results. It is interesting to show some illustrative example of the operation of FSVC for a 2D classification problem, mainly in the context of prototype determination (see section 2.2). 36 Chapter 2. Fast support vector classifier Figure 2.1 displays the classical circle-in-the-square classification dataset, with 5,000 patterns randomly generated and classified inside and outside a zero-centered circle of radius 0.5. The left panel shows the whole dataset, each pattern colored by its class label. The center panel shows the L=100 prototypes of each class created by FSVC from the training set (2,500 patterns). The right panel shows the classification developed by FSVC on the test set (the remaining 2,500 patterns), that is fairly accurate although with some errors on the class border. 2.7 Experimental setup We compared FSVC and two state-of-the-art SVM-based classifiers: Libsvm [3], with RBF kernel (henceforth named SVC), and Liblinear (named LSVC), with linear kernel, that is designed for large-scale high-dimensional problems [11]. We also compared FSVC with the direct kernel perceptron (DKP), an efficient SVC-based classifier [13]. We used a collection of 44 classification datasets selected from the UCI Machine Learning Repository and from the Kaggle repository2(datasets arabic,devanagari and fruits). Table 2.1 reports the 22 small datasets (below 15,000 patterns, where the SVC can be executed, upper part of the table) and 22 large datasets (above 15,000 patterns, lower part), sorted by increasing populations, with their numbers of inputs and classes. On the large datasets, with up to 31 millions of patterns (wesad), 30,000 inputs and 131 classes (fruits), only FSVC and LSVC were executed, because SVC and DKP spend too much time and memory and are not able to finish their execution. Note that there are some differences in N,Iand Qwith respect to the UCI dataset information, e.g. in wesad and har. The algorithms were codified on the Octave3 language v. 4.2.2, and the experiments were run under a computer with 8 Intel©CoreT M i74790K processors at 4GHz equipped with 32GB RAM and operative system Kubuntu 18.04. The program for FSVC is publicly available4. The experimental methodology was 4-fold cross-validation, with 2 training, 1 validation and 1 test folds on the small datasets. The values of the hyper-parameters, Cand γ =1/2 σ 2 for SVC and γ for DKP, were selected to achieve the highest average kappa over the validation sets using the classical grid-search methodology. Since FSVC and LSVC have no hyper-parameter tuning and do not require a validation dataset, the 4-fold cross-validation on the large datasets used 3 training and 1 test folds, excepting hepmass,imseg,mnist, 2https://www.kaggle.com/datasets (March, 2022). 3http://octave.org (March, 2022). 4persoal.citius.usc.es/manuel.fernandez.delgado/papers/fsvc (March, 2022). 2.7. Experimental setup 37 Original name Dataset N I Q Fertility fertility 100 23 2 Breast tissue tissue 106 9 6 Hepatitis hepatitis 155 19 2 Wine quality wine 178 13 3 Sonar, mines vs. rocks sonar 208 60 2 Seeds seeds 210 7 3 Heart (Statlog) heart 270 28 2 Ionosphere ionosphere 351 33 2 Dermatology dermatology 366 130 6 Monks monks 432 17 2 Breast cancer Wisconsin (original) wdbc 569 30 2 Synthetic control chart time series synthetic 600 60 6 Australian credit approval australian 690 43 2 Mammographic mass mammograph 961 5 2 German credit german 1,000 65 2 Isolet isolet 1,559 617 26 Image segmentation imseg 2,310 18 7 Abalone abalone 4,177 8 3 Landsat satellite (Statlog) sat 6,435 36 6 Musk (v.2) musk 6,598 166 2 Electrical Grid Stability grid 10,000 13 2 Nursery nursery 12,958 27 4 Arabic handwritten characters arabic 16,800 1,024 28 Magic gamma telescope magic 19,020 10 2 Letter recognition letter 20,000 16 26 Shuttle (Statlog) shuttle 58,000 9 7 MNIST mnist 70,000 784 10 WISDM smartphone and smartwatch activity and biometrics wisdm 73,803 92 18 Fruits 360 fruits 90,380 30,000 131 Devanagari character devanagari 92,000 1,024 46 IJCNN 2001 Competition ijcnn1 141,691 22 2 Covertype covtype 581,012 54 7 Poker hand poker 1,025,010 10 2 KDD Cup 1999 kddcup 4,000,000 122 23 SUSY susy 5,000,000 18 2 Record linkage comparison patterns record 5,749,132 11 2 Physical unclonable functions physical 6,000,000 128 2 Detection of IoT botnet attacks baiot 7,062,606 115 11 HEPMASS hepmass 10,500,000 28 2 HIGGS higgs 11,000,000 28 2 Human Activity Recognition from Continuous Ambient Sensor Data human 13,956,557 36 42 Kitsune network attack kitsune 21,017,597 115 9 Heterogeneity Activity Recognition har 29,097,887 14 6 Wearable stress and affect detection wesad 31,470,603 8 4 Table 2.1: List of the small (top) and large (bottom) classification datasets. physical,poker and fruits, that used the original separated train and test files without 4-fold cross-validation. The performance measurement was the Cohen kappa score [27], that evaluates the agreement between the true class label and the class predicted by the classifier discarding the agreement by change, e.g. with unbalanced datasets. Sections 2.8-2.12 below study the influence of the aspects of FSVC described in sections 2.1-2.5, respectively. Section 2.13 compares FSVC to the other approaches in terms of per- 38 Chapter 2. Fast support vector classifier Training method Kernel calculation Tuning method Kernel type Multi-class approach SVC Libsvm Support vectors Grid-search RBF One-vs-one SVC1 Efficient All patterns " " " SVC3 Libsvm Prototypes " " " SVC2 " Support vectors Efficient " " FSVC1 Efficient All patterns Grid-search " " FSVC2 " Prototypes Grid-search " " FSVC " Prototypes Efficient " " FSVCL " " " Linear " FSVCA " " " RBF One-vs-all FSVCLA " " " Linear One-vs-all Table 2.2: Versions of SVC and FSVC (in bold those features which are different from the original SVC or FSVC). The symbol "means ‘equal as above’. formance and time. Sections 2.14 and 2.15 compare FSVC with other SVM solvers and other spread tuning methods in the literature. Section 2.16 compares times of SVC with and without the algorithmic modifications proposed on this thesis. Section 2.17 compares FSVC with evolutionary training set selection methods, and section 2.18 discusses the memory requirements of FSVC. Dataset SVC SVC1 SVC2 SVC3 FSVC1 FSVC2 fertility -1.6 4.1 30.7 -1.6 6.5 15.9 tissue 62.1 59.1 63.9 62.1 49.7 49.7 hepatitis 36.2 48.7 34.7 36.2 52.9 52.9 wine 97.5 95.8 97.5 97.5 95.8 95.8 sonar 63.2 41.4 71.8 63.2 50.1 50.1 seeds 89.1 87.2 89.2 89.1 83.5 83.5 heart 35.9 26.4 43.0 37.0 18.5 18.5 ionosphere 86.8 56.8 82.3 84.5 61.4 62.7 dermatology 95.2 95.6 89.6 95.2 97.0 97.0 monks 100.0 93.5 100.0 100.0 85.2 81.0 wdbc 87.6 81.4 89.5 83.9 79.2 80.2 synthetic 97.4 95.0 99.0 97.4 93.2 93.2 australian 70.1 66.7 60.3 71.0 66.3 67.2 mammograph 65.2 57.2 61.9 63.0 58.3 58.7 german 33.6 36.8 36.7 36.1 39.0 35.8 isolet 95.2 86.1 95.4 95.2 83.7 83.7 imseg 89.1 80.8 90.7 89.1 81.1 81.1 abalone 33.8 29.5 33.9 32.4 28.8 29.7 sat 89.8 77.2 89.2 86.7 78.7 78.4 musk 98.8 78.2 97.2 82.0 74.9 80.8 grid 99.2 87.9 96.8 94.2 88.6 81.1 nursery 100.0 96.7 100.0 82.5 95.5 76.3 Average 73.8 67.4 75.1 71.7 66.7 66.1 p-value — 0.1697 0.9625 0.4595 0.1300 0.0803 Table 2.3: Kappa (in %) of SVC, SVC1, SVC2, SVC3, FSVC1 and FSVC2 on the small datasets (in bold values below SVC by more than 15%). 2.8. Influence of efficient training 39 2.8 Influence of efficient training In order to evaluate the influence of the efficient training (subsection 2.1), we compared the kappa achieved by SVC on the small datasets with a version of SVC, named SVC1 (2nd row in Table 2.2), that uses the proposed efficient training with all the training patterns; and with a version of FSVC, named FSVC1 (5th row in Table 2.2), that uses efficient training but without efficient kernel (it uses all the training patterns instead of class prototypes) and grid-search for spread tuning (selection of the σ with the highest average kappa over the validation sets). Their kappa values are reported by Table 2.3, alongside with the p-value of the Wilcoxon ranksum test, developed using the Matlab function ranksum, comparing them to SVC. In most datasets the SVC1 and FSVC1 achieve kappa similar to SVC, with average values (67.4% and 66.7%) only 6-7% below SVC overcoming 15% only in 3 of 22 datasets, so the efficient training is often an accurate approximation to SVC that can be applied on large datasets. The difference is not statistically significant (p=0.1697) but explains the averate loss from SVC (73.8%) to FSVC (67.1%) in Table 2.5 below. Considering times (see Table 2.10 in section 2.16 below), the SVC1 speeds up the SVC about 5 times in average over the small and some large datasets, although the use of the whole training set in SVC1 (that does not use prototypes) reduces this difference for in large datasets. 2.9 Influence of efficient kernel calculation The method described in subsection 2.2 for the efficient kernel calculation, based on the use of prototypes instead of support vectors, is tested by comparing SVC with SVC3 (3rd row in Table 2.2), a version of SVC trained on these prototypes, and with FSVC2 (6th row in Table 2.2), a version of FSVC which combines efficient training and prototypes with grid-search for spread tuning. The impact of using prototypes instead of all the patterns in SVC3 and FSVC2 (see Table 2.3) is also fairly low. Considering SVC3, the average kappa values is 71.7%, only 2% below SVC, with p-value=0.4595, being below SVC by more than 15% in only 2 of 22 datasets. With respect to FSVC2, the average kappa is 66.1%, with lower p-value=0.080, only 7% below SVC, being below SVC by more than 15% in only 6 22 datasets. The speed up of SVC3 with respect to SVC (see Table 2.10 in section 2.16 below) raises fastly with the dataset size, being 6.11 times faster on average over the small and some large datasets. 40 Chapter 2. Fast support vector classifier 0.44 0.46 0.48 0.5 2−5 20 25 FSVC abalone A(σ) 0 10 20 2−5 20 25 FSVC2 abalone Kappa (%) 0.46 0.48 0.5 0.52 2−5 20 25 dermatology 0 20 40 60 80 2−5 20 25 dermatology 0.48 0.485 0.49 0.495 0.5 2−5 20 25 musk 0 20 40 60 80 2−5 20 25 musk Figure 2.2: Upper panels: examples of function A( σ )of eq. 2.22 for datasets abalone,dermatology and musk. Lower panels: profiles of kappa vs. σ achieved by FSVC2 with grid-search tuning on these datasets. 2.10 Influence of efficient RBF spread tuning The upper panels in Figure 2.2 plot the function A( σ )of eq. 2.22 for three datasets. The left example, with a clear minimum on A( σ ), is the most frequent case, although some datasets (dermatology,fertility and hepatitis) exhibit a sigmoid-like profile (upper center panel) for A( σ ). The lower panels exhibit the kappa achieved by FSVC2 (see subsection 2.9), which uses grid-search tuning, on these datasets. In the lower left and center panels, there is a region of low kappa values located on the left (low σ values) and kappa increases when σ raises. The majority of the datasets that we studied exhibits this increasing sigmoid profile of kappa vs. σ . Although the σ with the highest kappa in the lower panel does not exactly match the lowest Ain the upper panel, the minimum of Ais usually located inside the region of high kappa values. Indeed, alongside with the minimum of A, the highest value σ =max{2−i+1 2}13 i=−13 =26also achieves kappa very near to the maximum. There are also some datasets (monks and musk) where the kappa profile has a maximum (lower right panel in Figure 2.2) instead of a sigmoid profile, and the highest σ , or the σ that minimizes A, give poor performance, but the highest kappa (low right panel) matches the place where A( σ )reaches its left asymptotic value (upper right panel), henceforth named 2.10. Influence of efficient RBF spread tuning 41 0 5 10 15 20 25 30 35 40 45 0 10 20 30 40 50 60 70 80 90 100 Dataset Kappa (%) σ maximum Minimum of A Left corner of A Figure 2.3: Kappa achieved by FSVC for each dataset using σ ∗= σ max, in blue, σ ∗=argmin{A}, in red, and σ ∗ on the left corner of A, in green. “the left corner” of the minimum of A( σ ). Thus, three tuning methods can be considered: 1) to select σ ∗on the maximum value σ max =26, which avoids the spread tuning; 2) to select, following eq. 2.23, the value σ ∗=argmin σ {A( σ )}; and 3) to select σ ∗on the left corner of A( σ ). This corner can be found by starting from the lowest value σ min =2−7, and searching the first value of σ where the derivative A′( σ )overcomes a threshold value τ , set empirically to τ =0.05maxA′( σ ), i.e., the 5% of the maximum of A′( σ ). Figure 2.3 plots the kappa achieved by FSVC using these three tuning methods. The horizontal axis identifies the datasets, sorted by decreasing Kappa of FSVC using σ ∗= σ max (blue line), in order to enhance the figure visualization. Blue and red lines, which correspond to σ ∗=26and σ ∗=argmin{A( σ )}, respectively, achieve in general similar results, while the green points, that correspond to σ ∗on the left corner of A( σ ), see the upper right panel of Fig. 2.2, achieves much less kappa excepting some datasets, where it overcomes methods 1 and 2. This figure suggests that method 1, which does not require tuning, works well usually (its performance is very near the maximum in 34 of 44 datasets), in 7 datasets method 3 is required to achieve good performance, and only in 3 datasets method 2 slightly overcomes method 1. The influence of the efficient spread tuning can be estimated by comparing the performance and time of SVC on the small datasets with RBF kernel spread selected: 1) using the proposed efficient tuning, a version of SVC named SVC2 in Table 2.2; 2) using the kernel density estimation (KDE), proposed in [28]; and 3) using the standard grid-search (SVC). Table 2.3 above and Table 2.9 in section 2.15 report these results: the SVC2 (average kappa 42 Chapter 2. Fast support vector classifier 75.1%) outperforms KDE (74.1%) and SVC (73.8%), being in average 27 times faster than SVC and so fast as KDE. Another way to estimate the influence of the efficient spread tuning is to compare FSVC and FSVC2 (6th row in Table 2.2), that uses grid-search, whose average kappa (66.1% in Table 2.3) is only slightly lower than FSVC (67.1% in Table 2.5) with nonsignificant difference to SVC (p=0.0803). Since the efficient tuning raises the performance of SVC2 compared to SVC, and grid-search reduces the performance of FSVC2 compared to FSVC, our method seems to perform similarly to grid-search but being faster. 2.11 Influence of large dimensionality Table 2.4 (upper part) reports kappa and time per fold achieved by FSVC and FSVCL, a version of FSVC that uses linear kernel (8th row in Table 2.2), in high-dimensional datasets with more than 100 inputs. The times are in format h:m:s, m:s or s.ss, where h, m and s mean hours, minutes and seconds. Note that 1.02 means 1.02 sec., while 1:03 means 1 minute and 3 sec. or 63 sec. The FSVCL outperforms FSVC on dataset fruits, with 30,000 inputs and 131 classes, by almost 10 points being about 5 times faster, which confirms that the former is a good choice for large datasets with many inputs. However, on datasets kitsune and musk FSVC outperforms FSVCL by 12 and 53 points, respectively. Globally, FSVC achieves higher average kappa than FSVCL (52.0% vs. 46.4%) although the latter is about 2 times faster in average. 2.12 Influence of large number of classes The middle part of Table 2.4 reports the kappa and time per fold of FSVC (that uses the OVO approach) and FSVCA (that uses the OVA approach, described in 9th row of Table 2.2) on multi-class datasets with more than 5 classes. Note that, for each dataset, S=Q(Q−1)/2 is the number of binary SVCs required when the OVO approach is used. On the fruits dataset, FSVCA uses L=50, instead of the default value (L=100), due to the large I=30,000 and Q=131, so that W=Z=1 and only one prototype of the first Lclasses is selected for the negative classes. The FSVCA achieves better kappa than FSVC in all the datasets, with an average of 56.8% vs. 53.6%. Surprisingly, the times of FSVCA are slightly higher than FSVC, what may be caused by: 1) the vectorization of FSVC, that reduces the slowness caused by the quadratic number of binary FSVCs compared to FSVCA; and 2) the time required by FSVCA to manage prototype indices for the negative classes (lines 30-37 in algorithm 2). The lower 2.13. Comparison of FSVC, SVC, LSVC and DKP 43 Kappa (%) Time(s/fold) Dataset N I FSVC FSVCL FSVC FSVCL dermatology 366 130 95.6 95.9 0.10 0.09 isolet 1,559 617 86.2 85.4 1.79 1.41 musk 6,598 166 78.7 25.4 1.84 1.81 arabic 16,800 1,024 21.1 21.6 1:06 27.48 mnist 70,000 784 72.7 71.1 1:46 1:25 fruits 90,380 30,000 32.0 41.6 5:28:9 1:24:17 devanagari 92,000 1,024 57.9 53.1 11:58 2:16 kddcup 4,000,000 122 70.1 69.6 17:23 10:56 physical 6,000,000 128 0.2 0.2 14:14 13:33 baiot 7,062,606 115 38.3 38.8 39:19 24:23 kitsune 21,017,597 115 19.5 7.5 1:32:27 1:13:26 Average 52.0 46.4 46:02 19:10 Dataset N Q S FSVC FSVCA FSVC FSVCA tissue 106 6 15 57.3 59.3 0.01 0.06 dermatology 366 6 15 95.6 96.2 0.10 0.17 synthetic 600 6 15 95.4 96.8 0.09 0.18 isolet 1,559 26 325 86.2 85.3 1.79 2.00 sat 6,435 6 15 74.5 77.7 0.52 0.68 arabic 16,800 28 378 21.1 22.1 1:06 58.80 letter 20,000 26 325 77.2 78.3 1.29 1.50 shuttle 58,000 7 21 82.8 87.6 1.35 1.58 mnist 70,000 10 45 72.7 74.9 1:46 2:49 wisdm 73,803 18 153 30.8 30.5 19.47 22.95 fruits 90,380 131 8,515 32.0 32.6 5:28:9 4:55:48 devanagari 92,000 46 1,035 57.9 59.3 11:58 7:23 covtype 581,012 7 21 39.6 40.0 57.45 1:12 kddcup 4,000,000 23 253 70.1 91.9 17:23 52:00 baiot 7,062,606 11 55 38.3 46.4 39:19 38:12 human 13,956,557 42 861 12.4 12.5 50:21 58:39 kitsune 21,017,597 9 36 19.5 27.9 1:32:27 1:40:16 har 29,097,887 6 15 1.9 3.3 24:24 24:44 Average 53.6 56.8 31:34 32:22 Dataset N I Q FSVC FSVCLA FSVC FSVCLA arabic 16,800 1,024 28 21.1 22.2 1:06 1:48 fruits 90,380 30,000 131 32.0 41.3 5:28:9 1:10:42 devanagari 92,000 1,024 46 57.9 53.1 11:58 10:01 Average 37.0 38.9 1:53:44 27:30 Table 2.4: Kappa and time per fold of FSVC and FSVCL (linear kernel) in high-dimensional datasets (upper part), by FSVC and FSVCA (one-vs-all) in multi-class datasets (middle part, here S=Q(Q−1)/2) and by FSVC and FSVCLA (linear kernel, one-vs-all) in high-dimensional multi-class datasets (lower part). part of Table 2.4 compares FSVC and FSVCLA (linear kernel and OVA approach, 10th row in Table 2.2) on the datasets with more than 1,000 inputs and 5 classes, simultaneously. The average performance of FSVCLA is better than FSVC (38.9% vs. 37.0%), being also four times faster in average. 50 Chapter 2. Fast support vector classifier Kappa (%) Time (s) Dataset FSVC ICVM FSVC ICVM fertility 1.8 3.9 0.02 1.10 tissue 57.3 42.8 0.02 2.73 hepatitis 48.7 37.9 0.06 1.94 wine 98.3 93.2 0.12 2.72 sonar 54.1 33.1 0.17 4.17 seeds 87.8 83.4 0.05 3.83 heart 27.8 69.1 0.14 6.39 ionosphere 59.6 53.2 0.12 9.52 dermatology 95.6 93.9 0.38 24.08 monks 89.8 31.9 0.20 21.16 wdbc 81.3 83.1 0.19 15.53 synthetic 95.4 93.2 0.34 53.68 australian 66.5 65.8 0.31 46.85 mammograph 59.3 56.5 0.12 94.11 german 37.2 19.1 0.58 151.92 isolet 86.2 46.1 7.18 1372.87 imseg 81.4 7.4 0.11 3.28 abalone 30.0 -1.2 0.52 23.70 sat 74.5 22.6 2.07 80.06 musk 78.7 29.0 7.35 34.15 grid 81.5 73.0 1.17 88.00 nursery 76.5 59.2 1.86 170.36 arabic 21.1 3.1 263.67 193.10 magic 46.3 28.5 1.75 115.26 letter 77.2 9.9 5.16 114.48 Average 64.6 45.5 — 105.77 p-value — 0.028 — 4.5e-07 Table 2.8: Comparison of FSVC and ICVM over the small datasets. The FSVC was also compared with the double stochastic gradient (DSG) approach [8], an example of random feature based method [21], on the adult (named in [8] as census-in come, with 50,000 patterns) and mnist8m datasets. Using 4-fold cross-validation, FSVC and LSVC achieve errors of 24.1% and 16.6%, respectively, while [8] reports an error of 15% for DSG, very near to LSVC and 9% below FSVC, although the experimental methodologies may differ. Concerning times, FSVC spends about 6 seconds for training, similar to LSVC and below DSG (about 8 s.). With respect to the mnist8m dataset, we followed the instructions7to download the dataset and SGD code, running SGD and FSVC on the PCA transformed training and test data (8,100,000 and 10,000 patterns, respectively, with 100 inputs). The SGD achieves an accuracy of 99.33% spending 21,755 seconds (about 6 hours) and 5.8GB of RAM, while FSVC achieves accuracy of 84.62%, spending 21 minutes 22 seconds and 6.15 MB of RAM. Although the difference in accuracy is about 15%, the FSVC is 17 times faster and requires 965 times less memory than SGD. Overall, SGD seems to achieve 7https://github.com/zixu1986/Doubly_Stochastic_Gradients/tree/master/matlab (March, 2022). 2.15. Comparison with other spread tuning methods 51 higher performance on these datasets, although the gap might be caused by differences in experimental methodologies, being much slower and with much larger memory requirements than FSVC. SVC2 KDE SVC Dataset Kappa(%) Time(s) Kappa(%) Time(s) Kappa(%) Time(s) fertility 30.7 0.25 10.4 0.11 -1.6 0.37 tissue 63.9 0.05 60.6 0.07 62.1 0.41 hepatitis 34.7 0.05 30.8 0.11 36.2 0.55 wine 97.5 0.03 97.5 0.08 97.5 0.65 sonar 71.8 0.51 71.8 0.18 63.2 1.07 seeds 89.2 0.03 90.6 0.08 89.1 0.58 heart 43.0 0.17 43.0 0.27 35.9 1.51 ionosphere 82.3 0.26 82.3 0.36 86.8 1.84 dermatology 89.6 0.34 94.9 0.48 95.2 6.60 monks 100.0 0.31 100.0 0.51 100.0 6.56 wdbc 89.5 0.38 89.5 0.58 87.6 3.44 synthetic 99.0 0.26 99.0 0.34 97.4 7.29 australian 60.3 0.49 60.3 0.91 70.1 7.29 mammograph 61.9 0.83 61.9 1.51 65.2 42.64 german 36.7 1.12 32.9 1.92 33.6 18.56 isolet 95.4 8.85 95.4 9.37 95.2 432.66 imseg 90.7 0.11 89.9 0.14 89.1 0.43 abalone 33.9 5.68 33.9 10.01 33.8 548.48 sat 89.2 5.18 89.2 8.15 89.8 486.63 musk 97.2 35.84 99.0 61.64 98.8 1176.59 grid 96.8 63.90 96.8 115.89 99.2 538.42 nursery 100.0 24.21 100.0 38.42 100.0 2040.47 Average 75.1 — 74.1 1.58 73.8 27.68 p-value — — 1.000 0.53 0.963 8.9e-04 Table 2.9: Kappa and time of SVC2, KDE and SVC for RBF kernel spread tuning on the small datasets. 2.15 Comparison with other spread tuning methods Table 2.9 reports the kappa and time achieved by SVC on the small datasets tuning the RBF kernel spread with: a) the proposed method, version SVC2 on line 4 of Table 2.2; b) the kernel density estimation (KDE) proposed by [28]; and c) with the standard grid-search, version SVC on line 1 of Table 2.2. In the first two approaches, that are designed for binary classification, the optimal spread is estimated using the training patterns of classes 1 and 2. The kappa columns of the row “Average” report the average kappa over the datasets, while the time columns report the average ratio between the times of KDE or SVC and the time of SVC2. The row “p-value” reports the p-values of the Wilcoxon tests comparing the kappa and times of KDE and SVC to SVC2. The results show that the average performance of SVC2 is higher than KDE and SVC (75.1% vs. 74.1% and 73.8%, respectively), although the differences are 52 Chapter 2. Fast support vector classifier not statistically significant (p=1 and p=0.962, respectively). With respect to times, SVC2 is so fast as KDE and 27 times faster than SVC (significant difference with p=9·10−4). However, it should be noted that our approach in FSVC uses a limited number of prototypes per class, so it is more scalable than KDE with the number of patterns. 2.16 Time comparison of SVC, SVC1, SVC2 and SVC3 Table 2.10 reports the time spent by SVC divided by the time spent by SVC1 (that uses efficient training, 2nd row in Table 2.2), SVC2 (that uses efficient tuning of the RBF kernel spread, 4th row in Table 2.2) and SVC3 (that uses efficient kernel, 3rd row in Table 2.2), on the small and some large datasets. The last rows report the average of these ratios and the pvalue of the test comparing the times of SVC and each column. The SVC1 is faster than SVC in 17 of 25 datasets (where tSVC/tSVC1 >1). In the other 8 datasets (e.g., imseg) SVC is faster because SVC1, despite using efficient training, needs the whole training set, while SVC is sparse and only needs the support vectors. In average, SVC is 5.20 times slower than SVC1, so the time of SVC1 is about 19% of the time of SVC. Analogously, SVC2 and SVC3 spend about 3% and 16% of the time of SVC, respectively. Note also that this ratios raise fastly with the dataset size. The main speed-up (about 35 times) with respect to SVC is achieved by SVC2 (efficient tuning), with a significant difference (p=0.0023). There are some exceptions (the SVC2 ratio is below 1 in dataset shuttle) where the calculation of the kernel matrix Kin line 16 of algorithm 1 is slow due to the high Nand to the absence of efficient kernel calculation in SVC2. The efficient training (SVC1) and efficient kernel calculation (SVC3) speed up the SVC about 5-6 times and are not statistically significant (p=0.45 and p=0.56, respectively). 2.17 Comparison with evolutionary training set selection Table 2.11 reports, for several small and large datasets of our collection, the kappa and time per fold of FSVC, SVC and SGA+SVC, i.e., SVC using the training set selected by steadystate genetic algorithm for instance selection (SGA), an evolutionary algorithm for training set selection [2] implemented by the Keel software8. The SGA is used to select training patterns, while the validation and test sets are left unchanged. The time of SGA is the sum of the time 8https://keel.es (March, 2022). 2.17. Comparison with evolutionary training set selection 53 Dataset tSVC/tSVC1 tSVC/tSVC2 tSVC/tSVC3 fertility 1.61 1.48 0.90 tissue 0.25 8.20 0.75 hepatitis 1.67 11.00 0.92 wine 0.82 21.67 0.84 sonar 2.14 2.10 0.93 seeds 0.62 19.33 0.84 heart 2.56 8.88 1.02 ionosphere 2.22 7.08 0.96 dermatology 0.94 19.41 1.06 monks 6.76 21.16 1.25 wdbc 2.23 9.05 0.91 synthetic 0.66 28.04 0.96 australian 4.03 14.88 1.18 mammograph 19.83 51.37 3.90 german 5.10 16.57 1.68 isolet 0.51 48.89 1.09 imseg 0.08 3.91 0.98 abalone 19.68 96.56 12.78 sat 2.67 93.94 5.47 musk 5.71 32.83 9.55 grid 7.23 8.43 6.16 nursery 7.16 84.28 12.47 magic 30.00 27.17 43.31 letter 0.49 224.16 5.50 shuttle 5.00 0.73 37.43 Average 5.20 34.44 6.11 p-value 0.45 0.0023 0.56 Table 2.10: Times spent by SVC divided by times of SVC1, SVC2 and SVC3 on the small and some large datasets. spent by SGA to select the training patterns and by SVC to train (on the reduced training set), validate and test. The last column reports the percentage of reduction of SGA in the training set size. The results show that SGA reduces very much the size of the training set (89-98%) without a large reduction in the performance. However, the training set selection requires much more time than SVC and FSVC training due to its high computational complexity, being much slower than training and becoming the most relevant component of the elapsed time. Besides, the SGA achieves memory errors in datasets arabic,mnist and larger. In dataset wisdm (not included in the Table 2.11), the SGA did not finish in 5 days (120h), so we did not try in datasets larger than fruits. Therefore, SGA is able to select the training set while keeping the performance only in small datasets, where SVC can already be run without training selection. Besides, the low speed and high memory requirements of SGA hinders to reduce large datasets, where the selection would be really useful because SVC can not be run on the whole training set. 54 Chapter 2. Fast support vector classifier Kappa(%) Time(s)/fold Dataset FSVC SVC SGA FSVC SVC SGA Red.(%) abalone 30.0 33.8 32.4 0.13 1.82 1:37 96.7 sat 77.7 89.9 87.2 0.68 2:02 9:32 97.8 musk 78.7 98.8 90.1 1.84 4:54 40:30 95.7 grid 81.5 99.2 97.9 0.29 2:15 14:48 92.9 nursery 76.5 100.0 99.9 0.47 8:30 42.58 91.0 arabic 22.1 62.5 — 58.8 29:14:43 — — magic 46.3 71.4 69.2 0.44 1:59:22 57:06 92.9 letter 78.3 96.3 94.7 1.50 1:02:46 1:28:09 89.2 shuttle 87.6 99.8 99.6 1.58 6:03:59 9:27:20 93.7 mnist 74.9 96.9 — 2:49 28:19:22 — — Table 2.11: Kappa and time per fold of FSVC, SVC and SGA, and % of reduction of SGA on the training set size. Name Symbol Size Name Symbol Size Train patterns {xn}BN n=1IBNClass labels {cn}BN n=1BN Prototypes {pql }Q,L ql=1QLI Number of prototypes {Nql }Q,L ql=1QL Ideal kernel {Jlm}2L lm=1(2L)2Distances |p1l−p2m|(2L)2 Train kernel {Klm}2L lm=1(2L)2Test patterns {xn}BT n=1IBT Test kernel {kq(xn)}Q,BT qn=1QBTWeights {zns}BT,S ns=1SBT Votes {vnq}BT,Q nq=1QBTOutput {yn}BT n=1BT Table 2.12: Memory required by the largest data matrices used by FSVC with RBF kernel and OVO approach, being S=Q(Q−1)/2. 2.18 Memory usage The FSVC reads the training and test patterns from file disks by blocks in order to reduce the number of disk reads. A low block size Vmeans smaller matrices, that may speed up the mathematical operations, but also more disk reads, that may slow the execution down. On the contrary, high Vmeans larger matrices, that may slow down the calculations, but also less disk reads, that may speed up the execution. Besides, it also requires more memory M, limited by the available memory M. In principle, the weight of each component (low or high V) on the execution speed is unknown. In order to estimate Mfrom V, Table 2.12 reports the sizes of the largest data matrices used by FSVC with RBF kernel and OVO multi-class approach. Each training pattern has Iinputs and the class label, so its size is I+1. Given V, the default number Yof patterns per block is Y=max(1,⌊V I+1⌋), in such a way that Y=1 when I+1>V, that might happen for high I. The number of training patterns per block is BN=min(N,Y), because it must be BN=Nwhen N<Y, i.e., the number BNof training 2.18. Memory usage 55 patterns per block can not overcome the number Nof available training patterns. The train pattern block is of size IBN(first item in Table 2.12). The class labels is a vector of size BN. Considering Nq>Lfor q=1,...,Q, for large datasets, the QL prototypes, each of length I, have a size of QLI. The number of prototypes for the Qclasses is a matrix of size QL. Considering the RBF kernel spread tuning, in multi-class problems σ is the same for all the FSVCs, being selected using prototypes of classes 1 and 2. Thus, the ideal kernel matrix J, the distances |p1l−p2m|between prototypes land mof both classes and the kernel matrix K (eq. 2.21) have (2L)2values each one. With Ttest patterns, the number of test patterns per block is BT=min(T,Y), so that BT=Twhen T<Y. The block of test patterns {xn}BT n=1is of size IBT. The test kernel values kqn (eq. 2.18): kqn =kq(xn) = Lq ∑ l=1 kql(xn),q=1,...,Q;n=1,...,BT(2.26) are QBTvalues. The test weights zns for classes q(s)and r(s): zns =kqn Lq −krn Lr +bs,n=1,...,BT;s=1,...,S(2.27) (see eq. 2.18) require SBTvalues, where S=Q(Q−1)/2, being qand rthe second and first class of the s-th binary FSVC in an OVO approach. The class votes vnq (line 19 in algorithm 2) for the n-th test pattern are given by: vnq =∑ s∈Aq zns −∑ s∈Bq zns,n=1,...,BN;q=1,...,Q(2.28) where Aq(resp. Bq) is the set of binary FSVCs where class qis the first (resp. second). Finally, the output ynof the multi-class FSVC is: yn=argmax q=1,...,Q {vnq},n=1,...,BT(2.29) which requires BTvalues. Algorithm 5 describes the procedure to select the block size V given the available memory (M) and the dataset size, defined by N,I,Qand T. The FSVC sets a starting value V=106, then it calculates Y,BNand BT. Using Table 2.12, the required memory M0=M(BN,I,Q,L,BT)can be estimated as: M(BN,I,Q,L,BT) = IBN+BN+QLI +QL +3(2L)2+IBT+QBT+SBT+QBT+BT= = (I+1)BN+QL(I+1)+12L2+Q2+3Q+2(I+1) 2BT(2.30) 56 Chapter 2. Fast support vector classifier Algorithm 5: Selection of the memory data block size V. 1Algorithm: BlockSize(M,N,I,Q,L,T) Data: M: available memory; N: no. train patterns; I: no. inputs; Q: no. classes; L: max. prototypes/class; T: no. test patterns Result: V: data block size 2 ε ←0.1; η ←0.25; V←106 3while true do 4Y←max1,V I+1;BN←min(N,Y);BT←min(T,Y) 5M0←M(BN,I,Q,L,BT)// M= memory required according to eq. 2.30 6if Y=1then 7if M0>Mthen 8error: Block with just 1 pattern does not fit in memory 9end 10 break 11 end 12 if M0< η Mthen 13 break 14 end 15 V←(1− ε )V 16 end Let us η <1 be the percentage of the available memory Mthat can be used. When M0< η M, the current Vis accepted as valid block size. Otherwise, Vis reduced to (1− ε )V, with ε =0.1. A default value for η =0.25 can be used, that uses 25% of memory, although a higher percentage might also be used. It may happen, specially in high-dimensional datasets, that V<I+1, so that Y=1, i.e., only a pattern is read each time because it is very large. In this case, Vis accepted even if M0≥ η Min order to guarantee that BN,BT≥1, i.e., the training and test block have at least one pattern (line 10 in algorithm 5). The process continues iteratively, updating V,Y,BN,BTand M0until either M0< η M(line 13) or Y=1. A very extreme case would be that Y=1 and M0>Mbecause a data block with only one pattern (Y=1) does not fit in the available memory (line 8). This might only happen with very high Iand/or Q, that can not be reduced as BNor BT, for the avaliable memory, and in this case the algorithm would fail to select an adequate V. Table 2.13 (columns labeled as “M=32GB”) reports the time and memory (measured using the Octave whos command) spent by FSVC, and the memory required by LSVC on the 2.18. Memory usage 57 large datasets, alongside with their populations (N). In order to ensure that FSVC reduces V in response to the memory restrictions (see the next paragraph) according to algorithm 5, the starting value was raised from V=106(default value) to V=107. The LSVC requires more memory than FSVC in all the datasets (columns 4 and 5) excepting letter, overcoming 1GB in 6 out of 22 datasets and failing by lack of memory on fruits,har,kitsune and wesad. In average (last row), LSVC requires 12.5 times more memory (1.5GB) than FSVC (191MB). The FSVC only overcomes 1GB on fruits, due to its high Q=131 and I=30,000, and human, due to its high Q=42. M=32GB M=2GB FSVC LSVC FSVC LSVC Dataset NTime Mem. Mem. Mem. Time Time arabic 16,800 1:52 73M 132M 73M 1:53 — magic 19,020 0.54 2M 2M 2M 0.46 0.40 letter 20,000 1.48 17M 3M 17M 1.38 0.74 shuttle 58,000 1.71 6M 6M 6M 1.53 1.01 mnist 70,000 3:01 74M 419M 74M 3:08 — wisdm 73,803 30.45 43M 52M 43M 29.10 26.23 fruits 90,380 8:33:41 1.5G — 338M 2:57:33 — devanagari 92,000 14:13 152M 720M 152M 12:57 — ijcnn1 141,691 8.26 8M 31M 8M 7.59 4.43 covtype 581,012 1:44 104M 245M 104M 1:44 27.51 poker 1,025,010 48.94 59M 94M 59M 44.17 21.13 kddcup 4,000,000 35:33 225M 3.7G 225M 35:35 — susy 5,000,000 4:28 70M 734M 70M 4:22 — record 5,749,132 3:29 109M 537M 109M 3:39 — physical 6,000,000 23:57 88M 5.8G 88M 23:14 — baiot 7,062,606 55:35 118M 6.1G 118M 56:10 — hepmass 10,500,000 13:39 80M 2.3G 80M 14:11 — higgs 11,000,000 14:03 138M 2.4G 138M 14:09 — human 13,956,557 1:30:59 2.0G 3.9G 509M 55:10 — kitsune 21,017,597 2:22:29 192M — 192M 2:22:46 — har 29,097,887 25:56 330M — 330M 25:33 — wesad 31,470,603 15:58 252M — 252M 15:49 — Average 14:40 191M 1.5G 104M 12:39 Table 2.13: Time(in sec./fold) and memory (in MB or GB) required by FSVC and LSVC on the large datasets with 32GB and 2GB of available memory (M). An additional experiment executed FSVC and LSVC on the large datasets using the same computer but with only M=2GB, instead of M=32GB, in order to show how FSVC uses algorithm 5 to adjust Vuntil M0< η Mor Y=1. In order to perform this, we ran the Linux command ulimit -Sv 2097152, in order to set a soft limit of 2,097,152 KB (2 GB) on the virtual memory before running FSVC and LSVC. Last three columns of Table 2.13, under label “M=2GB”, report the time and memory spent by FSVC and the time spent by LSVC, which fails by lack of memory on 15 out of 22 large datasets. The FSVC reduces the average 58 Chapter 2. Fast support vector classifier memory from 191MB to 104MB (columns 4 and 6 in the last row). Indeed, the memory required by FSVC does not change excepting on the fruits dataset, where L=10 was used due to the large I=30,000 and to the constraint M=2GB, reducing from 1.5GB to 338MB, and human, where the high Qreduces Vfrom 107to 2.3·106, and the required memory from 2GB (still much lower than LSVC, that requires 3.9GB on this dataset) to 509MB. Using 2GB, the times of FSVC are surprisingly reduced on fruits (2.8 times, from 8h 33m 41s to 2h 57m 33s. In this dataset, the high initial time compared to Table 2.6 is caused by the high value V=107. The reduction in time is caused by the decreasing from L=50 to L=10. The time is also reduced in human (1.6 times), because the lower block size V=2.3·106allows smaller matrices and faster calculations. The average time of FSVC (columns 3 and 7 of the last row) decreased from 14m 40s using M=32GB to 12m 39s using M=2GB, so the reduction in memory does not slow down FSVC necessarily. CHAPTER 3 IDEAL KERNEL TUNING The support vector classifier (SVC) is a very popular classification method [5] with stateof-the-art performance, particularly combined with the RBF kernel [12]. Before the training stage, two hyper-parameters must be set: regularization (C) and kernel spread ( σ ), that measures how large the differences between patterns must be to drive the kernel function towards zero. The optimal σ value depends on the data properties and is, in general, different for each dataset. Sub-optimal values often lead to an important loss in the SVC performance. The spread tuning is usually performed using the “grid-search” strategy, that performs training with several σ values from a pre-specified collection and selects the value with the best average performance on a collection of separated validation sets. The experimental literature has proven that the collection of values for Cand σ proposed in [20] is adequate for a vast majority of the applications. This fact highly simplifies the SVC usage because only a repetitive train-test loop must be performed, and no expert knowledge is required to achieve a fine tuning. However, to train and test the SVC many times is very time-consuming for large datasets. 3.1 Related work The literature about “model selection” for SVC reports several approaches for spread selection alternatives to grid-search. The kernel density estimation (KDE) selects the σ value that maximizes a function of disimilarity between two classes that is based on the RBF kernel [28] and does not require to train the SVC. Genetic algorithms [14] have been used to select C and σ by optimizing the test performance over small datasets (in the paper, up to 768 training 66 Chapter 3. Ideal kernel tuning upper right plot, where the minimum Dqis very near to D1or DE, and the highest performance (lower right) is achieved in the σ qwith the highest slope of Dqin absolute value (upper right). In these cases, |Dj−D1|< δ , when the minimum is located near D1, or |DE−Dj|< δ , when the minimum is located near DE, being jcalculated in eq. 3.7 and δ =|DE−D1|/10 a threshold (lines 20-22 of algorithm 6). When this happens, the absolute value of the derivative of {Dq}E q=1, denoted as {Fq}E q=1, is calculated as F1=0 and Fq=|Dq−Dq−1|for q=2,...,E, and the optimal spread σ ∗is set to σ j, being jthe index that maximizes {Fq}E q=1: σ ∗= σ j,j=argmax q=1,...,E {Fq}(3.8) Since IKT is based on the kernel matrix for two-class classification problems, it is also appliable to kernel types other than RBF, such as polinomial kernels, and to other kernel-based methods, such as Kernel PCA [50]. Also, IKT can only be applied to select the values of the kernel hyper-parameters, such as the RBF spread or the offset and degree of a polinomial kernel, but not to select other SVC hyper-parameters, such as the regularizationC, that are not related to kernel. The size Lof the kernel matrix Kin IKT does not depend on the dimensionality Iof the training patterns, so that IKT scales well with I, although of course the calculation of Knm =K(xn,xm)is slower when Iraises. In large-scale datasets with high N, the RBF spread can also be selected using IKT due to the upper limit U≤2L(see line 16 of algorithm 6) for the size of the kernel matrix K, caused by the limited number of prototypes (eq. 3.3). However, the SVC training is very slow when Nis high and becomes not practical despite of the efficiency of IKT to select the spread. 3.3 Results and discussion The proposed method ideal kernel tuning (IKT) was programmed in the Octave1scientific computing language version 5.2. The σ selected by IKT is used to train and test the SVC implemented by the Libsvm library [3] using 4-fold cross validation with 3 folds for training (excepting grid-search, see below) and 1 fold for test in each trial. We compared IKT with five state-of-the-art methods for selecting the RBF kernel spread: 1. Kernel density estimation (KDE), implemented in Octave and applied on the two most populated classes [28]. 1http://www.octave.org (March, 2022). 3.3. Results and discussion 67 Table 3.2: Kappa (in %) achieved by each method and dataset. Dataset IKT KDE GS GA PSO Bayes tissue 58.0 64.9 61.1 59.6 61.7 64.8 hepatitis 39.3 35.4 42.4 30.4 30.4 31.5 wine 97.5 95.0 97.5 96.6 96.6 95.8 sonar 76.9 71.8 68.9 77.9 58.5 76.0 seeds 91.3 90.5 90.6 88.5 89.8 89.2 heart 53.5 53.5 55.7 61.8 67.0 66.2 voting 89.8 89.8 88.9 87.3 86.0 89.4 ionosphere 84.1 83.5 81.7 84.7 87.1 83.5 dermatology 95.6 95.6 96.6 95.9 96.2 95.9 german 28.1 29.1 28.5 34.0 38.3 41.3 monks 100.0 100.0 100.0 100.0 100.0 100.0 wdbc 89.1 88.4 86.9 85.1 84.8 88.6 synthetic 99.2 99.4 98.8 99.0 99.0 98.4 australian 63.1 63.1 57.8 64.4 67.9 67.2 energy 90.4 90.4 92.3 91.2 92.9 92.5 pima 30.2 40.4 28.0 38.0 47.3 45.5 vehicle 78.1 78.1 76.5 79.4 75.4 75.6 annealing 98.6 98.3 98.1 97.8 97.2 97.5 tic 97.2 97.7 97.2 97.5 97.0 96.8 mammograph 62.1 64.1 46.4 66.3 63.5 63.9 isolet 95.0 95.1 94.5 79.4 93.6 93.6 imseg 90.7 89.9 91.0 89.3 83.9 89.6 abalone 32.9 32.6 23.6 32.6 32.6 33.0 sat 89.4 89.2 89.0 89.5 89.5 89.1 musk 98.9 99.2 98.7 99.0 99.0 99.1 usps 97.4 97.3 96.8 90.6 95.7 97.3 grid 96.8 97.9 97.6 98.1 98.0 98.7 nursery 100.0 100.0 100.0 100.0 100.0 100.0 magic 71.0 71.0 63.3 71.0 70.9 70.2 letter 96.8 96.8 97.0 97.4 97.4 97.4 chess 89.0 88.6 88.8 89.3 89.4 89.3 adult 52.9 53.6 18.0 – 56.0 56.0 shuttle 99.7 99.7 99.8 – 99.8 99.8 mnist 83.5 83.5 80.7 – – 80.7 wisdm 89.1 75.0 90.3 – – 90.3 ijcnn1 95.4 – 81.8 – – 95.7 poker 13.4 17.6 21.8 – 22.9 21.8 Average 78.8 78.2 76.4 79.7 78.4 80.0 2. Grid-search (GS), also implemented in Octave, that selects the spread σ with the highest performance over a validation set with the 50% of the three training folds, randomly selected respecting the relative class populations. 3. Genetic algorithm (GA), implemented in the R statistical computing language2by the GA package. 4. Particle-swarm optimization (PSO), implemented by the pso package in R. 2http://www.r-project.org (March, 2022). 68 Chapter 3. Ideal kernel tuning 20 40 60 80 100 Kappa (%) monks nursery shuttle synthetic musk annealing wine usps tic letter grid dermatology ijcnn1 isolet seeds imseg energy votingsat wisdm wdbc chess ionosphere mnist vehicle sonar magic australian mammograph tissue heart adult hepatitis abalone pima german poker ITK KDE GS Figure 3.2: Kappa (in %) achieved by IKT, KDE and GS. 5. Bayesian optimizer (Bayes), implemented by the rBayesianOptimization package [43], also in R. The methods KDE and GS optimize the classification performance of the SVC implemented by the Libsvm library in Octave, while GA, PSO and Bayes use the svm function of the kernlab R package. All the methods use the SVC with the same regularization hyperparameter C=100, named cost in kernlab, so its value was not tuned. This choice is the same for all the methods, so it does not condition the fair comparison between them, but avoids possible interactions between tuning of both hyper-parameters. Since IKT, KDE and GS are implemented in Octave, while GA, PSO and Bayes are implemented in R, the comparison of the elapsed times among algorithms might seem somehow conditioned by the use of different programming languages. However, we must think that there is no a priori reason to suggest that one language is faster or slower than the other. In fact, it is common in the literature to compare the performance and speed of methods programmed in different languages. On the other hand, translating an algorithm to other language (e.g., the methods in Octave to R, or vice versa) would not be convenient because the new implementation might be sub-optimal in terms of speed or have programming errors, so the speed of the method 3.3. Results and discussion 69 or the correctness of the results might be compromised. The best choice is then to compare the original algorithm implementations provided by their authors, whenever available, under the hypothesis that language efficiencies are similar and that algorithms are optimally coded in each language, so the differences in performance and speed are caused exclusively by the algorithms themselves. Table 3.3: Time (in s.) spent by each method and dataset. Dataset IKT KDE GS GA PSO Bayes tissue 0.005 0.010 0.023 2.0 0.9 535 hepatitis 0.010 0.035 0.048 3.2 1.2 319 wine 0.009 0.028 0.038 2.5 1.0 220 sonar 0.032 0.060 0.079 7.3 2.5 152 seeds 0.008 0.039 0.025 2.0 0.9 196 heart 0.021 0.086 0.063 6.7 2.2 128 voting 0.031 0.212 0.075 9.1 2.7 137 ionosphere 0.035 0.143 0.080 7.9 3.1 230 dermatology 0.052 0.085 0.324 29.8 8.8 23.3 german 0.059 0.540 0.573 48.5 11.6 19.8 monks 0.048 0.245 0.350 8.7 4.5 140 wdbc 0.055 0.211 0.157 17.0 3.5 18.9 synthetic 0.067 0.080 0.324 37.3 10.5 65.1 australian 0.091 0.313 0.309 27.7 7.4 20.8 energy 0.042 0.260 0.178 24.4 4.6 88.9 pima 0.041 0.367 0.276 19.3 3.8 30.8 vehicle 0.074 0.128 0.396 37.5 7.8 41.9 annealing 0.064 0.427 0.786 53.5 12.4 180 tic 0.046 0.486 0.925 51.4 18.4 132 mammograph 0.030 0.429 0.517 27.3 6.7 68.9 isolet 1.47 0.720 42.4 2793 1109 313 imseg 0.014 0.020 0.061 3.9 1.7 8.6 abalone 0.100 3.19 8.66 574 161 78.5 sat 0.442 3.69 15.9 2149 439 101 musk 2.06 18.0 123 8872 1244 279 usps 4.50 41.5 1336 36154 3143 1111 grid 0.290 36.6 46.5 1423 225 59.4 nursery 0.459 25.1 140 7257 2226 332 magic 0.470 137 161 13673 2503 218 letter 0.819 1.40 126 26796 4378 361 chess 1.28 28.4 753 70106 14253 1208 adult 10.4 1967 17215 – 85099 17155 shuttle 1.43 2921 18.6 – 469 101 mnist 105 1299 85583 – – 163685 wisdm 11.4 30.1 4436 – – 18067 ijcnn1 384 – 12493 – – 16029 poker 0.775 670 733 – 12686 1017 Average – 105 163 5549 1760 6420 The six methods were executed on a collection of 37 datasets (Table 3.1) selected from the UCI Machine Learning Repository [10] with up to 70,000 training patterns, 1,000,000 test patterns, 784 inputs and 26 classes. The experiments ran on a desktop computer with the following features: Intel Core i7-9700K processor (8 cores) at 3.6GHz with 64GB RAM 70 Chapter 3. Ideal kernel tuning under operating system Kubuntu 20.04. The performance, measured by the Cohen kappa statistic [27]. The time elapsed by the selection of the kernel spread and the memory required by the tuning method were recorded for each method. Table 3.2 reports the kappa achieved by the 6 methods. The missing values correspond to datasets where the method failed due to out-of-memory errors or did not finish within 6 days (518,400 seconds). The average values of the last line are calculated, for each method, over all the datasets excluding those with fails. The IKT, GS and Bayes never fail, while KDE fails on dataset ijcnn1, PSO fails in three datasets (mnist,wisdm and ijcnn1) and GA fails in the 6 largest datasets. The kappa values for each dataset are in general very similar for the different methods, with some exceptions: GS achieves 18% in dataset adult, where IKT, KDE, PSO and Bayes achieve 52-56%; and GA achieves 79.4% in isolet, while the other methods achieve 94%. The average values are also similar, being Bayes the best (80%), followed by GA (79.7%), IKT (78.8%), PSO (78.4%) and KDE (78.2%), while GS performs slightly worse (76.4%). Figure 3.2 plots the kappa values of IKT, KDE and GS, sorted by decreasing values. The GS is below the other methods in four datasets (ijcnn1, mammograph,adult and abalone), while KDE is twice above (datasets tissue and pima) and once below IKT (dataset wisdm). Table 3.3 reports the time spent by each method to select σ , excluding the SVC training and test. The last row reports, for all the methods excepting IKT and for each dataset, the ratio of the time spent by that method on that dataset divided by the time spent by IKT on the same dataset, averaged over all the datasets excluding fails. This average says how many times the method is slower than IKT. The times spent by IKT are very small and raise very slowly with the dataset size. In some cases the times are higher compared to datasets with similar size: isolet (1.47 s. while the previous dataset mammograph spends 0.03 and the next dataset imseg spends 0.014), because the high Iand Qslow down the prototype learning; musk, usps and adult, also due to their high I;mnist due to the large I=784 and Q=10. The KDE is also fast, but slower than IKT, in some cases with high difference: in usps,grid and nursery, KDE spends 41, 36 and 25 s., while IKT spends 4.5, 0.29 and 0.45 s. Larger differences occur in adult, where IKT and KDE spend 10.4 and 1,967 s., and shuttle (1.43 and 2,921 s.), because the two most populated classes (1 and 4) have 40,856 of 43,483 training patterns, so KDE is much slower than IKT, that uses a reduced number of class prototypes. In fact, KDE fails in dataset ijcnn1 by lack of memory. Given that GS requires to train and test the SVC many times, it is much slower than IKT and KDE, specially 3.3. Results and discussion 71 10-2 10-1 100 101 102 103 104 105 Time (s,log scale) tissue seeds wine hepatitis imseg heart mammograph voting sonar ionosphere pima energy tic monks dermatology wdbc german annealing synthetic vehicle australian abalone gridsat nursery magic poker letter chess shuttle isolet musk usps adult wisdm mnist ijcnn1 IKT KDE GS Figure 3.3: Time (in s.) spent by IKT, KDE and GS. in datasets adult (17,215 s. with GS, 10.4 and 1,967 s. with IKT and KDE) and mnist (85,583 s. with GS, 105 and 1,299 s. with IKT and KDE, respectively). However, GS is much faster than KDE in dataset shuttle (18.6 and 2,921 s., respectively), because the SVC training in the former is relatively fast, while the latter is slow as we explained above. The GA is clearly the slowest method, in fact it does not finish after days of execution in the six largest datasets. The PSO is also slow, but faster than GA in all the datasets, failing only in the three largest datasets. Finally, the Bayes method is slower than GA and PSO in the small datasets, but faster in the largest ones, and it does not fail in any dataset, as opposite to GA and PSO. In average over all datasets, KDE and GS are 105 and 163 times (two orders of magnitude) slower than IKT, while GA, PSO and Bayes are 5,549, 1,760 and 6,420 times (three-four orders of magnitude) slower than IKT. The number corresponding to Bayes is somehow confusing, because it seems to be the slowest tuning method, but in the large datasets where GA and PSO do not fail they are slower than Bayes. Similarly to GS, the large times of GA, PSO and Bayes are expectable because they require to train and test the SVC. 72 Chapter 3. Ideal kernel tuning Table 3.4: Memory (in MB) required by each method and dataset. Dataset IKT KDE GS GA PSO Bayes tissue 0.04 0.02 0.02 0.04 0.04 0.04 hepatitis 0.38 0.23 0.05 0.05 0.05 0.05 wine 0.26 0.16 0.05 0.05 0.05 0.05 sonar 0.81 0.45 0.24 0.12 0.12 0.12 seeds 0.28 0.18 0.03 0.04 0.04 0.05 heart 0.98 0.67 0.10 0.06 0.06 0.07 voting 1.0 1.7 0.09 0.06 0.05 0.06 ionosphere 1.1 1.1 0.21 0.11 0.10 0.11 dermatology 1.1 0.43 0.52 0.20 0.20 0.20 german 1.2 8.7 0.41 0.15 0.15 0.16 monks 1.0 1.6 0.10 0.06 0.06 0.06 wdbc 1.1 2.9 0.34 0.14 0.14 0.14 synthetic 1.0 0.42 0.71 0.25 0.25 0.26 australian 1.3 4.3 0.35 0.14 0.14 0.14 energy 1.0 3.5 0.14 0.07 0.07 0.07 pima 0.99 5.1 0.13 0.07 0.07 0.07 vehicle 1.1 1.7 0.32 0.13 0.12 0.13 annealing 1.2 5.5 0.53 0.20 0.20 0.20 tic 1.2 8.0 0.32 0.11 0.11 0.12 mammograph 0.98 8.0 0.09 0.06 0.06 0.07 isolet 11.8 0.55 18.6 5.7 5.7 5.7 imseg 0.16 0.06 0.11 0.07 0.06 0.07 abalone 1.2 70.9 0.70 0.24 0.24 0.24 sat 2.6 80.0 4.7 1.4 1.4 1.4 musk 7.9 380 19.9 6.4 6.3 6.4 usps 8.0 756 45.6 13.7 13.7 13.7 grid 1.9 859 2.7 0.81 0.81 0.81 nursery 3.2 634 4.2 1.1 1.1 1.1 magic 2.3 3106 3.9 1.2 1.2 1.2 letter 3.3 22.6 8.9 1.9 1.9 1.9 chess 8.1 659 13.7 3.3 3.3 3.3 adult 8.2 20505 94.3 – 29.5 29.5 shuttle 4.4 25474 3.7 – 3.4 3.4 mnist 9.7 2660 690 – – 344 wisdm 3.6 641 80.7 – – 39.1 ijcnn1 4.5 – 49.6 – – 18.3 poker 3.5 9547 4.3 – 2.1 2.1 Average — 383.9 3.9 0.313 0.4 1.8 Figure 3.3 plots the time spent by IKT, KDE and GS in all the datasets. The plots of KDE and GS are almost always above IKT, with the only exception of isolet, where the high Qslows down the prototype learning of IKT (1.47 s.), that is slower than KDE (0.72 s.). Generally, IKT is between one and two orders of magnitude faster than KDE and GS. To avoid confusion in the figure, the times of GA, PSO and Bayes are not plotted, but they are much higher in all the datasets. Table 3.4 reports the RAM memory required by each method and dataset, excluding the memory used by the SVC training and prediction, that is much larger. Thanks to the limitation on the number of class prototypes, the memory required by IKT is below 10 MB even in the 3.3. Results and discussion 73 10-2 10-1 100 101 102 103 104 105 Memory (MB,log scale) tissue hepatitis wine sonar seeds heart voting ionosphere dermatology german monks wdbc synthetic australian energy pima vehicle annealing tic mammograph isolet imseg abalonesat musk usps grid nursery magic letter chess adult shuttle mnist wisdm ijcnn1 poker IKT KDE GS GA PSO Bayes Figure 3.4: Memory consumption (in MB) of each algorithm. largest datasets, much below the capability of a today’s standard desktop computer. On the contrary, the memory requirements of KDE raise in dataset abalone (N=2,090, memory of 70.9 MB) reaching large values in datasets adult (20.5 GB, that is a huge amount of memory for a medium sized dataset), shuttle (25.4 GB), mnist (2.6 GB) and poker (9.5 GB), due to the high number of training patterns of the two most populated classes: 24,422 in adult, 40,856 in shuttle, 12,873 in mnist and 25,010 in poker. The GS uses also more memory than IKT, specially in datasets larger than musk. The GA and PSO require small amounts of memory. Bayes requires less memory than IKT in the small datasets, and more memory in the large datasets: adult (29.5 MB and 8.2 MB with Bayes and IKT, respectively), mnist (344 MB and 9.7 MB), wisdm (39.1 MB and 3.6) and ijcnn1 (18.3 MB and 4.5 MB). The last line reports the ratio of the memory requirements of each method divided by IKT excluding datasets with fails: the KDE, GS and Bayes require 400, 4 and 2 times more memory, respectively, than IKT. The memory of GA and PSO is so low as IKT on the small datasets, being unknown on the largest datasets because they fail. Figure 3.4 plots the memory consumption of the six methods. The memory of IKT raises only very slowly with the dataset size even for the largest datasets. In the small datasets GA, PSO and Bayes 74 Chapter 3. Ideal kernel tuning are below IKT, but in the large datasets GS and PSO do not run and Bayes overcomes IKT, while KDE is the most expensive and GS also overcomes IKT. CHAPTER 4 CONCLUSION The current thesis proposes methods that allow to execute the radial basis function (RBF) kernel-based support vector classifier (SVC) on large-scale classification problems. It is widely known in the literature that SVC is not able to process datasets beyond several thousands of training patterns, depending on the pattern dimensionality and on the number of classes. Although there are approaches in the literature that try to allow the execution of SVC over large datasets, they are usually focused to training set selection, often by means of complex selection methods that are slow for really large datasets. On the other hand, alternative SVC solvers are not efficient enough so as to be executed on large datasets. The proposed approach, named fast support vector classifier (FSVC), is inspired on the SVC theory and designed to allow the classification of large datasets with many patterns, inputs and classes. It uses a closed-form expression that directly calculates the output of the binary SVC from the training patterns in an efficient way. The use of a closed-form expression for the calculation of the SVC trainable parameters is very fast, but requires the storage in memory of the whole training set, so it does not scale pretty well with the number of training patterns. In order to avoid storing the whole training set in memory, the FSVC uses a small number of prototypes representing each class, being scalable to highly populated datasets. As well, the size of the trainable parameters, that raises with the dataset size for small datasets, is upper bounded for large sizes, so that FSVC can still be executed when the dataset population raises to tens of millions of training patterns. One of the most important issues in the SVC performance is the tuning of the RBF kernel spread. This process is very relevant because the performance is very sensitive to the spread 82 Bibliography [35] A. Rosales-Pérez, S. García, J.A. González, C.A. Coello, and F. Herrera. An evolutionary multiobjective model and instance selection for support vector machines with Pareto-based ensembles. IEEE T Evol Comput, 21(6):863–877, 2017. [36] A. Rosales-Pérez, J.A. González, C.A. Coello, H.J. Escalante, and C.A. Reyes-García. Surrogate-assisted multi-objective model selection for support vector machines. Neurocomputing, 150:163–172, 2015. [37] V. Saradhi and K. Girish. Effective parameter tuning of SVMs using radius/margin bound through data envelopment analysis. Neural Proc Lett, 41:125–138, 2015. [38] F.M. Schleif and P. Tino. Indefinite core vector machine. Patt Recogn, 71:187–195, 2017. [39] S. Shalev-Shwartz, Y. Singer, N. Srebro, and A. Cotter. Pegasos: primal estimated sub-gradient solver for SVM. Math Program Ser B, 127:3—30, 2011. [40] J. Shawe-Taylor and S. Sun. A review of optimization methodologies in support vector machines. Neurocomputing, 74:3609–3618, 2011. [41] H. Shi, H. Xiao, J. Zhou, N. Li, and H. Zhou. Radial basis function kernel parameter optimization algorithm in support vector machine based on segmented dichotomy. In Intl Conf Syst Inform, pages 383–388, 2018. [42] A. Tharwat and T. Gabel. Parameters optimization of support vector machines for imbalanced data using social ski driver algorithm. Neural Comput Appl, 32:6925–6938, 2020. [43] A. Tharwat, A.E. Hassanien, and B.E. Elnaghi. A BA-based algorithm for parameter optimization of support vector machine. Patt Recogn Lett, 93:13–22, 2017. [44] I. Tsang, J. Kwok, and P. Cheung. Core vector machines: fast SVM training on very large datasets. J Mach Learn Res, 6:363–392, 2005. [45] M. Tukan, C. Baykal, D. Feldman, and D. Rus. On coresets for support vector machines. In Intl Conf Theory Appl Models Comput, pages 287–299, 2020. [46] V. Vapnik. Statistical learning theory. Wiley-Interscience, 1998. Bibliography 83 [47] N. Verbiest, J. Derrac, C. Cornelis, S. García, and F. Herrera. Evolutionary wrapper approaches for training set selection as preprocessing mechanism for support vector machines: Experimental evaluation and support vector analysis. Appl Soft Comput, 38:10–22, 2016. [48] W. Wang, Z. Xu, W. Lu, and X. Zhang. Determination of the spread parameter in the Gaussian kernel for classification and regression. Neurocomputing, 55:643–663, 2003. [49] Z. Wang, Y. Shao, and T. Wu. Proximal parametric-margin support vector classifier and its applications. Neural Comput Appl, 24:755–764, 2014. [50] C. Zhang, F. Nie, and S. Xiang. A general kernelization framework for learning algorithms based on kernel PCA. Neurocomputing, 73(4):959–967, 2010. List of Figures Fig. 2.1 Left: circle-in-the-square dataset. Center: prototypes created by FSVC. Right: classification results. . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Fig. 2.2 Upper panels: examples of function A( σ )of eq. 2.22 for datasets abalone, dermatology and musk. Lower panels: profiles of kappa vs. σ achieved by FSVC2 with grid-search tuning on these datasets. . . . . . . . . . . . . . 40 Fig. 2.3 Kappa achieved by FSVC for each dataset using σ ∗= σ max, in blue, σ ∗= argmin{A}, in red, and σ ∗on the left corner of A, in green. . . . . . . . . . 41 Fig. 2.4 Time of FSVC and LSVC per pattern, input and class on the large datasets vs. dataset size. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Fig. 2.5 Time spent by FSVC, time estimated (6·10−7PIQ) for FSVC and time of LSVC on the large datasets vs. dataset size. . . . . . . . . . . . . . . . . . . 47 Fig. 3.1 Difference Dq(upper panels) and performance (lower panels) vs. σ qfor datasets letter (left panels) and pima (right panels). . . . . . . . . . . . 64 Fig. 3.2 Kappa (in %) achieved by IKT, KDE and GS. . . . . . . . . . . . . . . . . . 68 Fig. 3.3 Time (in s.) spent by IKT, KDE and GS. . . . . . . . . . . . . . . . . . . . 71 Fig. 3.4 Memory consumption (in MB) of each algorithm. . . . . . . . . . . . . . . 73 List of Tables Tabla 1.1 Symbols used in the text and meaning of each one. . . . . . . . . . . . . . 11 Tabla 1.2 Values of ξ nand meaning. . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Tabla 2.1 List of the small (top) and large (bottom) classification datasets. . . . . . . 37 Tabla 2.2 Versions of SVC and FSVC (in bold those features which are different from the original SVC or FSVC). The symbol "means ‘equal as above’. . . . . 38 Tabla 2.3 Kappa (in %) of SVC, SVC1, SVC2, SVC3, FSVC1 and FSVC2 on the small datasets (in bold values below SVC by more than 15%). . . . . . . . 38 Tabla 2.4 Kappa and time per fold of FSVC and FSVCL (linear kernel) in highdimensional datasets (upper part), by FSVC and FSVCA (one-vs-all) in multi-class datasets (middle part, here S=Q(Q−1)/2) and by FSVC and FSVCLA (linear kernel, one-vs-all) in high-dimensional multi-class datasets (lower part). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Tabla 2.5 Kappa and time/fold of FSVC, SVC, LSVC and DKP on small datasets (in bold the kappa values of FSVC that are below SVC by more than 15 points). 44 Tabla 2.6 Kappa and time per fold achieved by FSVC and LSVC, and ratio tLSVC/tFSVC, on the large datasets. The last two columns report the training and test times per pattern of FSVC. The values with asterisk (∗) are calculated discarding dataset fruits as an outlier. . . . . . . . . . . . . 45 Tabla 2.7 Comparison of FSVC, linear (LP) and RBF (RP) Pegasos, and SIMBA (SMB) on the binary datasets. . . . . . . . . . . . . . . . . . . . . . . . . 48 Tabla 2.8 Comparison of FSVC and ICVM over the small datasets. . . . . . . . . . 50 Tabla 2.9 Kappa and time of SVC2, KDE and SVC for RBF kernel spread tuning on the small datasets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 88 List of Tables Tabla 2.10 Times spent by SVC divided by times of SVC1, SVC2 and SVC3 on the small and some large datasets. . . . . . . . . . . . . . . . . . . . . . . . . 53 Tabla 2.11 Kappa and time per fold of FSVC, SVC and SGA, and % of reduction of SGA on the training set size. . . . . . . . . . . . . . . . . . . . . . . . . 54 Tabla 2.12 Memory required by the largest data matrices used by FSVC with RBF kernel and OVO approach, being S=Q(Q−1)/2. ............. 54 Tabla 2.13 Time(in sec./fold) and memory (in MB or GB) required by FSVC and LSVC on the large datasets with 32GB and 2GB of available memory (M). 57 Tabla 3.1 Classification problems: total (P) and training (N) patterns, inputs (I) and classes (Q)................................... 65 Tabla 3.2 Kappa (in %) achieved by each method and dataset. . . . . . . . . . . . . . 67 Tabla 3.3 Time (in s.) spent by each method and dataset. . . . . . . . . . . . . . . . 69 Tabla 3.4 Memory (in MB) required by each method and dataset. . . . . . . . . . . . 72 This thesis proposes the fast support vector classifier, an efficient implementation of the radial basis function support vector machine (SVM) for large-scale classification problems. It achieves performance near the state-of-the-art, being much faster than existing approaches over datasets up to 31 million patterns, 30,000 inputs and 131 classes. It also adjusts the memory requirements, allowing to be executed on datasets of almost arbitrary size. The thesis also proposes the ideal kernel tuning, an efficient tuning method for the Gaussian kernel spread of the SVM, that is the fastest compared to other five methods in the literature, with performance very near to the best and reduced memory requirements.