Machine à vecteurs de support

Dans l'apprentissage automatique , les machines à vecteurs de support ( SVM , également appelées réseaux à vecteurs de support ) sont des modèles de marge maximale supervisés avec des algorithmes d'apprentissage associés qui analysent les données pour la classification et l'analyse de régression . Développées aux laboratoires AT&T Bell les SVM sont l'un des modèles les plus étudiés, étant basées sur des cadres d'apprentissage statistique de la théorie VC proposés par Vapnik (1982, 1995) et Chervonenkis (1974).

En plus d'effectuer une classification linéaire , les SVM peuvent effectuer efficacement une classification non linéaire en utilisant l' astuce du noyau , en représentant les données uniquement par un ensemble de comparaisons de similarité par paires entre les points de données d'origine à l'aide d'une fonction du noyau, qui les transforme en coordonnées dans un espace de caractéristiques de dimension supérieure . Ainsi, les SVM utilisent l'astuce du noyau pour mapper implicitement leurs entrées dans des espaces de caractéristiques de dimension supérieure, où une classification linéaire peut être effectuée. Étant des modèles à marge maximale, les SVM sont résilients aux données bruyantes (par exemple, des exemples mal classés). Les SVM peuvent également être utilisés pour des tâches de régression , où l'objectif devient sensible.

L'algorithme de clustering à vecteurs de support , créé par Hava Siegelmann et Vladimir Vapnik , applique les statistiques des vecteurs de support, développées dans l'algorithme des machines à vecteurs de support, pour catégoriser les données non étiquetées. Ces ensembles de données nécessitent des approches d'apprentissage non supervisées , qui tentent de trouver un clustering naturel des données en groupes, puis de mapper de nouvelles données en fonction de ces clusters.

La popularité des SVM est probablement due à leur facilité d'analyse théorique et à leur flexibilité dans leur application à une grande variété de tâches, y compris les problèmes de prédiction structurée . Il n'est pas certain que les SVM aient de meilleures performances prédictives que d'autres modèles linéaires, tels que la régression logistique et la régression linéaire .

La classification des données est une tâche courante dans l'apprentissage automatique . Supposons que certains points de données donnés appartiennent chacun à l'une des deux classes, et que l'objectif est de décider dans quelle classe se trouvera un nouveau point de données . Dans le cas des machines à vecteurs de support, un point de données est considéré comme un vecteur bidimensionnel (une liste de nombres), et nous voulons savoir si nous pouvons séparer ces points avec un hyperplan bidimensionnel . C'est ce qu'on appelle un classificateur linéaire . Il existe de nombreux hyperplans qui pourraient classer les données. Un choix raisonnable comme meilleur hyperplan est celui qui représente la plus grande séparation, ou marge , entre les deux classes. Nous choisissons donc l'hyperplan de manière à ce que la distance entre lui et le point de données le plus proche de chaque côté soit maximisée. Si un tel hyperplan existe, il est connu sous le nom d' hyperplan à marge maximale et le classificateur linéaire qu'il définit est connu sous le nom de classificateur à marge maximale ; ou de manière équivalente, le perceptron de stabilité optimale .

Plus formellement, une machine à vecteurs de support construit un hyperplan ou un ensemble d'hyperplans dans un espace de dimension élevée ou infinie, qui peut être utilisé pour la classification , la régression ou d'autres tâches comme la détection de valeurs aberrantes. Intuitivement, une bonne séparation est obtenue par l'hyperplan qui a la plus grande distance au point de données d'entraînement le plus proche de n'importe quelle classe (ce qu'on appelle la marge fonctionnelle), car en général, plus la marge est grande, plus l' erreur de généralisation du classificateur est faible. Une erreur de généralisation plus faible signifie que l'implémenteur est moins susceptible de subir un surajustement .

Bien que le problème initial puisse être formulé dans un espace de dimension finie, il arrive souvent que les ensembles à discriminer ne soient pas linéairement séparables dans cet espace. Pour cette raison, il a été proposé que l'espace de dimension finie initial soit mappé dans un espace de dimension beaucoup plus élevée, ce qui faciliterait probablement la séparation dans cet espace. Pour maintenir la charge de calcul raisonnable, les mappages utilisés par les schémas SVM sont conçus pour garantir que les produits scalaires de paires de vecteurs de données d'entrée peuvent être calculés facilement en termes de variables dans l'espace initial, en les définissant en termes d'une fonction noyau sélectionnée pour s'adapter au problème. Les hyperplans dans l'espace de dimension supérieure sont définis comme l'ensemble de points dont le produit scalaire avec un vecteur dans cet espace est constant, où un tel ensemble de vecteurs est un ensemble orthogonal (et donc minimal) de vecteurs qui définit un hyperplan. Les vecteurs définissant les hyperplans peuvent être choisis pour être des combinaisons linéaires avec des paramètres d'images de vecteurs de caractéristiques qui apparaissent dans la base de données. Avec ce choix d'hyperplan, les points de l' espace des caractéristiques qui sont mappés dans l'hyperplan sont définis par la relation Notez que si devient petit à mesure que s'éloigne de , chaque terme de la somme mesure le degré de proximité du point de test par rapport au point de base de données correspondant . De cette façon, la somme des noyaux ci-dessus peut être utilisée pour mesurer la proximité relative de chaque point de test par rapport aux points de données provenant de l'un ou l'autre des ensembles à discriminer. Notez le fait que l'ensemble de points mappés dans n'importe quel hyperplan peut être assez alambiqué en conséquence, permettant une discrimination beaucoup plus complexe entre des ensembles qui ne sont pas du tout convexes dans l'espace d'origine.

Les SVM peuvent être utilisés pour résoudre divers problèmes du monde réel :

• Les SVM sont utiles dans la catégorisation de texte et d'hypertexte , car leur application peut réduire considérablement le besoin d'instances de formation étiquetées dans les paramètres inductifs et transductifs standard . Certaines méthodes d' analyse sémantique superficielle sont basées sur des machines à vecteurs de support.
• La classification des images peut également être effectuée à l'aide de SVM. Les résultats expérimentaux montrent que les SVM atteignent une précision de recherche nettement supérieure à celle des schémas d'affinement de requête traditionnels après seulement trois à quatre cycles de rétroaction sur la pertinence. Cela est également vrai pour les systèmes de segmentation d'images , y compris ceux qui utilisent une version modifiée de SVM qui utilise l'approche privilégiée comme suggéré par Vapnik.
• Classification des données satellitaires comme données SAR à l'aide de SVM supervisées.
• Les caractères manuscrits peuvent être reconnus à l'aide de SVM.
• L'algorithme SVM a été largement appliqué dans les sciences biologiques et autres. Il a été utilisé pour classer les protéines avec jusqu'à 90 % des composés classés correctement. Des tests de permutation basés sur les poids SVM ont été suggérés comme mécanisme d'interprétation des modèles SVM. Les poids de la machine à vecteurs de support ont également été utilisés pour interpréter les modèles SVM dans le passé. L'interprétation post-hoc des modèles de machine à vecteurs de support afin d'identifier les caractéristiques utilisées par le modèle pour faire des prédictions est un domaine de recherche relativement nouveau qui revêt une importance particulière dans les sciences biologiques.

L'algorithme SVM original a été inventé par Vladimir N. Vapnik et Alexey Ya. Chervonenkis en 1964. En 1992, Bernhard Boser, Isabelle Guyon et Vladimir Vapnik ont ​​suggéré une façon de créer des classificateurs non linéaires en appliquant l' astuce du noyau aux hyperplans à marge maximale. L'incarnation de la « marge souple », telle qu'elle est couramment utilisée dans les progiciels, a été proposée par Corinna Cortes et Vapnik en 1993 et ​​publiée en 1995.

On nous donne un ensemble de données d'apprentissage de points de la forme où les sont soit 1 soit −1, chacun indiquant la classe à laquelle appartient le point. Chacun est un vecteur réel de dimension . Nous voulons trouver l'« hyperplan à marge maximale » qui sépare le groupe de points pour lequel du groupe de points pour lequel , qui est défini de telle sorte que la distance entre l'hyperplan et le point le plus proche de l'un ou l'autre groupe soit maximisée.

Tout hyperplan peut être écrit comme l'ensemble des points satisfaisant où est le vecteur normal (pas nécessairement normalisé) à l'hyperplan. Cela ressemble beaucoup à la forme normale de Hesse , sauf qu'il ne s'agit pas nécessairement d'un vecteur unitaire. Le paramètre détermine le décalage de l'hyperplan par rapport à l'origine le long du vecteur normal .

Attention : la plupart de la littérature sur le sujet définit le biais de telle sorte que

Si les données d'apprentissage sont linéairement séparables , nous pouvons sélectionner deux hyperplans parallèles qui séparent les deux classes de données, de sorte que la distance entre eux soit la plus grande possible. La région délimitée par ces deux hyperplans est appelée la « marge », et l'hyperplan à marge maximale est l'hyperplan qui se trouve à mi-chemin entre eux. Avec un ensemble de données normalisé ou standardisé, ces hyperplans peuvent être décrits par les équations

et

Géométriquement, la distance entre ces deux hyperplans est , donc pour maximiser la distance entre les plans nous voulons minimiser . La distance est calculée en utilisant l' équation de distance d'un point à un plan . Nous devons également empêcher les points de données de tomber dans la marge, nous ajoutons la contrainte suivante : pour chaque soit ou Ces contraintes stipulent que chaque point de données doit se trouver du bon côté de la marge.

Cela peut être réécrit comme

Nous pouvons assembler ceci pour obtenir le problème d'optimisation :

Le et qui résolvent ce problème déterminent le classificateur final, , où est la fonction signe .

Une conséquence importante de cette description géométrique est que l'hyperplan de marge maximale est entièrement déterminé par ceux qui lui sont les plus proches (expliqué ci-dessous). Ceux-ci sont appelés vecteurs de support .

Pour étendre SVM aux cas dans lesquels les données ne sont pas linéairement séparables, la fonction de perte de charnière est utile

Notez qu'il s'agit de la i -ème cible (c'est-à-dire, dans ce cas, 1 ou −1), et qu'il s'agit de la i -ème sortie.

Cette fonction est nulle si la contrainte de (1) est satisfaite, autrement dit si elle se trouve du bon côté de la marge. Pour les données situées du mauvais côté de la marge, la valeur de la fonction est proportionnelle à la distance par rapport à la marge.

Le but de l’optimisation est alors de minimiser :

où le paramètre détermine le compromis entre l'augmentation de la taille de la marge et la garantie que la valeur se situe du bon côté de la marge (notez que nous pouvons ajouter un poids à l'un ou l'autre terme dans l'équation ci-dessus). En déconstruisant la perte de charnière, ce problème d'optimisation peut être massé comme suit : $0C>0$0}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c84d4126c6df243734f9355927c026df6b0d3859">

Ainsi, pour de grandes valeurs de , il se comportera de manière similaire au SVM à marge dure, si les données d'entrée sont classifiables linéairement, mais apprendra toujours si une règle de classification est viable ou non.

L'algorithme d'hyperplan à marge maximale original proposé par Vapnik en 1963 a construit un classificateur linéaire . Cependant, en 1992, Bernhard Boser, Isabelle Guyon et Vladimir Vapnik ont ​​suggéré une façon de créer des classificateurs non linéaires en appliquant l' astuce du noyau (proposée à l'origine par Aizerman et al. ) aux hyperplans à marge maximale. L'astuce du noyau, où les produits scalaires sont remplacés par des noyaux, est facilement dérivée dans la représentation duale du problème SVM. Cela permet à l'algorithme d'ajuster l'hyperplan à marge maximale dans un espace de caractéristiques transformé . La transformation peut être non linéaire et l'espace transformé de grande dimension ; bien que le classificateur soit un hyperplan dans l'espace de caractéristiques transformé, il peut être non linéaire dans l'espace d'entrée d'origine.

Il est à noter que travailler dans un espace de caractéristiques de dimension supérieure augmente l' erreur de généralisation des machines à vecteurs de support, bien qu'avec suffisamment d'échantillons, l'algorithme fonctionne toujours bien.

Certains noyaux courants incluent :

• Polynôme (homogène) : . En particulier, lorsque , cela devient le noyau linéaire.
• Polynôme (inhomogénéique) : .
• Fonction de base radiale gaussienne : pour . Parfois paramétrée à l'aide de .$0\gamma >0$0}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/775a6435e4270cddf2cd7dcb486c20f7f4bb8cee">
• Fonction sigmoïde ( tangente hyperbolique ) : pour certains (pas tous) et .$0\kappa >0$0}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f2d8b6e1180bd22cf9e92b0295ede259cb80db64">

Le noyau est lié à la transformation par l'équation . La valeur w est également dans l'espace transformé, avec . Les produits scalaires avec w pour la classification peuvent à nouveau être calculés par l'astuce du noyau, c'est-à-dire .

Le calcul du classificateur SVM (à marge souple) revient à minimiser une expression de la forme

Nous nous concentrons sur le classificateur à marge souple car, comme indiqué ci-dessus, le choix d'une valeur suffisamment petite pour donne le classificateur à marge dure pour les données d'entrée classifiables linéairement. L'approche classique, qui consiste à réduire (2) à un problème de programmation quadratique , est détaillée ci-dessous. Ensuite, des approches plus récentes telles que la descente de sous-gradient et la descente de coordonnées seront abordées.

La minimisation (2) peut être réécrite comme un problème d’optimisation contraint avec une fonction objective différentiable de la manière suivante.

Pour chaque nous introduisons une variable . Notons que est le plus petit nombre non négatif satisfaisant

Nous pouvons ainsi réécrire le problème d’optimisation comme suit

C’est ce qu’on appelle le problème primordial .

En résolvant le dual lagrangien du problème ci-dessus, on obtient le problème simplifié

C'est ce qu'on appelle le problème dual . Comme le problème de maximisation duale est une fonction quadratique soumise à des contraintes linéaires, il peut être résolu efficacement par des algorithmes de programmation quadratique .

Ici, les variables sont définies de telle sorte que

De plus, lorsque se trouve exactement du bon côté de la marge et lorsque se trouve sur la limite de la marge, il s'ensuit que peut être écrit comme une combinaison linéaire des vecteurs de support.

Le décalage, , peut être récupéré en trouvant un sur la limite de la marge et en résolvant

(Notez que depuis .)

Supposons maintenant que nous souhaitons apprendre une règle de classification non linéaire qui correspond à une règle de classification linéaire pour les points de données transformés. De plus, on nous donne une fonction noyau qui satisfait .

Nous savons que le vecteur de classification dans l'espace transformé satisfait

où, sont obtenus en résolvant le problème d'optimisation

Les coefficients peuvent être résolus en utilisant la programmation quadratique, comme précédemment. Là encore, nous pouvons trouver un indice tel que , de sorte que se trouve sur la frontière de la marge dans l'espace transformé, puis résoudre

Enfin,

Les algorithmes récents pour trouver le classificateur SVM incluent la descente de sous-gradient et la descente de coordonnées. Ces deux techniques se sont avérées offrir des avantages significatifs par rapport à l'approche traditionnelle lorsqu'il s'agit de traiter des ensembles de données volumineux et épars : les méthodes de sous-gradient sont particulièrement efficaces lorsqu'il existe de nombreux exemples d'apprentissage, et la descente de coordonnées lorsque la dimension de l'espace des caractéristiques est élevée.

Les algorithmes de descente de sous-gradient pour le SVM fonctionnent directement avec l'expression

Notez que est une fonction convexe de et . En tant que telle, les méthodes traditionnelles de descente de gradient (ou SGD ) peuvent être adaptées, où au lieu de faire un pas dans la direction du gradient de la fonction, un pas est fait dans la direction d'un vecteur sélectionné à partir du sous-gradient de la fonction . Cette approche présente l'avantage que, pour certaines implémentations, le nombre d'itérations ne s'adapte pas à , le nombre de points de données.

Algorithmes de descente de coordonnées pour le travail SVM à partir du problème dual

Pour chaque , de manière itérative, le coefficient est ajusté dans la direction de . Ensuite, le vecteur de coefficients résultant est projeté sur le vecteur de coefficients le plus proche qui satisfait les contraintes données. (En général, les distances euclidiennes sont utilisées.) Le processus est ensuite répété jusqu'à ce qu'un vecteur de coefficients presque optimal soit obtenu. L'algorithme résultant est extrêmement rapide en pratique, bien que peu de garanties de performance aient été prouvées.

La machine à vecteurs de support à marge souple décrite ci-dessus est un exemple d' algorithme de minimisation du risque empirique (ERM) pour la perte de charnière . Vues sous cet angle, les machines à vecteurs de support appartiennent à une classe naturelle d'algorithmes d'inférence statistique, et bon nombre de ses caractéristiques uniques sont dues au comportement de la perte de charnière. Cette perspective peut fournir un aperçu plus approfondi du fonctionnement et des raisons pour lesquelles les SVM fonctionnent, et nous permettre de mieux analyser leurs propriétés statistiques.

Dans l'apprentissage supervisé, on dispose d'un ensemble d'exemples d'entraînement avec des étiquettes , et on souhaite prédire un . Pour ce faire, on formule une hypothèse , , telle que soit une « bonne » approximation de . Une « bonne » approximation est généralement définie à l'aide d'une fonction de perte , , qui caractérise à quel point une prédiction de . Nous voudrions alors choisir une hypothèse qui minimise le risque attendu :

Dans la plupart des cas, nous ne connaissons pas la distribution conjointe du risque empirique. Dans ces cas, une stratégie courante consiste à choisir l'hypothèse qui minimise le risque empirique :

Sous certaines hypothèses sur la séquence des variables aléatoires (par exemple, qu'elles sont générées par un processus de Markov fini), si l'ensemble des hypothèses considérées est suffisamment petit, le minimiseur du risque empirique se rapprochera étroitement du minimiseur du risque attendu à mesure que celui-ci augmente. Cette approche est appelée minimisation du risque empirique, ou GRE.

Pour que le problème de minimisation ait une solution bien définie, nous devons placer des contraintes sur l'ensemble des hypothèses considérées. Si est un espace normé (comme c'est le cas pour SVM), une technique particulièrement efficace consiste à ne considérer que les hypothèses pour lesquelles . Cela revient à imposer une pénalité de régularisation , et à résoudre le nouveau problème d'optimisation

Cette approche est appelée régularisation de Tikhonov .

Plus généralement, cela peut être une mesure de la complexité de l'hypothèse , de sorte que les hypothèses plus simples sont préférées.

Rappelons que le classificateur SVM (à marge souple) est choisi pour minimiser l'expression suivante :

À la lumière de la discussion ci-dessus, nous voyons que la technique SVM est équivalente à la minimisation du risque empirique avec régularisation de Tikhonov, où dans ce cas la fonction de perte est la perte de charnière

De ce point de vue, SVM est étroitement lié à d'autres algorithmes de classification fondamentaux tels que les moindres carrés régularisés et la régression logistique . La différence entre les trois réside dans le choix de la fonction de perte : les moindres carrés régularisés équivalent à une minimisation empirique du risque avec la perte au carré ; la régression logistique utilise la perte logarithmique .

La différence entre la perte de charnière et ces autres fonctions de perte est mieux exprimée en termes de fonctions cibles - la fonction qui minimise le risque attendu pour une paire donnée de variables aléatoires .

En particulier, on note conditionnellement à l'événement que . Dans le cadre de la classification, on a :

Le classificateur optimal est donc :

Pour la perte au carré, la fonction cible est la fonction d'espérance conditionnelle, ; Pour la perte logistique, c'est la fonction logit, . Bien que ces deux fonctions cibles donnent le classificateur correct, comme , elles nous donnent plus d'informations que ce dont nous avons besoin. En fait, elles nous donnent suffisamment d'informations pour décrire complètement la distribution de .

D'autre part, on peut vérifier que la fonction cible pour la perte de charnière est exactement . Ainsi, dans un espace d'hypothèses suffisamment riche — ou de manière équivalente, pour un noyau choisi de manière appropriée — le classificateur SVM convergera vers la fonction la plus simple (en termes de ) qui classe correctement les données. Cela étend l'interprétation géométrique du SVM — pour la classification linéaire, le risque empirique est minimisé par toute fonction dont les marges se situent entre les vecteurs de support, et le plus simple d'entre eux est le classificateur à marge maximale.

Les SVM appartiennent à une famille de classificateurs linéaires généralisés et peuvent être interprétés comme une extension du perceptron . Ils peuvent également être considérés comme un cas particulier de régularisation de Tikhonov . Une propriété particulière est qu'ils minimisent simultanément l' erreur de classification empirique et maximisent la marge géométrique ; c'est pourquoi ils sont également connus sous le nom de classificateurs à marge maximale .

Une comparaison du SVM avec d'autres classificateurs a été faite par Meyer, Leisch et Hornik.

L'efficacité de SVM dépend de la sélection du noyau, des paramètres du noyau et du paramètre de marge souple . Un choix courant est un noyau gaussien, qui a un seul paramètre . La meilleure combinaison de et est souvent sélectionnée par une recherche de grille avec des séquences de et à croissance exponentielle , par exemple, ; . En général, chaque combinaison de choix de paramètres est vérifiée à l'aide d' une validation croisée , et les paramètres avec la meilleure précision de validation croisée sont sélectionnés. Alternativement, des travaux récents sur l'optimisation bayésienne peuvent être utilisés pour sélectionner et , nécessitant souvent l'évaluation de beaucoup moins de combinaisons de paramètres que la recherche de grille. Le modèle final, qui est utilisé pour tester et classer les nouvelles données, est ensuite formé sur l'ensemble de la formation en utilisant les paramètres sélectionnés.

Les inconvénients potentiels du SVM incluent les aspects suivants :

• Nécessite un étiquetage complet des données d'entrée
• Probabilités d'appartenance à une classe non étalonnée — SVM est issu de la théorie de Vapnik qui évite d'estimer les probabilités sur des données finies
• Le SVM n'est directement applicable que pour les tâches à deux classes. Par conséquent, il faut appliquer des algorithmes qui réduisent la tâche multi-classe à plusieurs problèmes binaires ; voir la section SVM multi-classe.
• Les paramètres d'un modèle résolu sont difficiles à interpréter.

Le SVM multiclasse vise à attribuer des étiquettes aux instances en utilisant des machines à vecteurs de support, où les étiquettes sont tirées d'un ensemble fini de plusieurs éléments.

L'approche dominante pour y parvenir consiste à réduire le problème multiclasse unique en plusieurs problèmes de classification binaire . Les méthodes courantes pour une telle réduction comprennent :

• Création de classificateurs binaires qui font la distinction entre l'une des étiquettes et les autres ( un contre tous ) ou entre chaque paire de classes ( un contre un ). La classification des nouvelles instances pour le cas un contre tous est effectuée par une stratégie où le gagnant remporte tout, dans laquelle le classificateur avec la fonction de sortie la plus élevée attribue la classe (il est important que les fonctions de sortie soient calibrées pour produire des scores comparables). Pour l'approche un contre un, la classification est effectuée par une stratégie de vote à gains maximum, dans laquelle chaque classificateur attribue l'instance à l'une des deux classes, puis le vote pour la classe attribuée est augmenté d'un vote, et enfin la classe avec le plus de votes détermine la classification de l'instance.
• Graphe acyclique dirigé SVM (DAGSVM)
• Codes de sortie de correction d'erreur

Crammer et Singer ont proposé une méthode SVM multiclasse qui transforme le problème de classification multiclasse en un seul problème d'optimisation, plutôt que de le décomposer en plusieurs problèmes de classification binaire. Voir également Lee, Lin et Wahba et Van den Burg et Groenen.

Les machines à vecteurs de support transductif étendent les SVM dans la mesure où elles peuvent également traiter des données partiellement étiquetées dans un apprentissage semi-supervisé en suivant les principes de la transduction . Ici, en plus de l'ensemble d'apprentissage , l'apprenant reçoit également un ensemble

d'exemples de test à classer. Formellement, une machine à vecteurs de support transductif est définie par le problème d'optimisation primal suivant :

Réduire (en )

sous réserve de (pour tout et n'importe quel )

et

Les machines à vecteurs de support transductifs ont été introduites par Vladimir N. Vapnik en 1998.

La machine à vecteurs de support structurée est une extension du modèle SVM traditionnel. Alors que le modèle SVM est principalement conçu pour les tâches de classification binaire, de classification multiclasse et de régression, la SVM structurée élargit son application pour gérer les étiquettes de sortie structurées générales, par exemple les arbres d'analyse, la classification avec taxonomies, l'alignement de séquences et bien d'autres.

Une version de la SVM pour la régression a été proposée en 1996 par Vladimir N. Vapnik , Harris Drucker, Christopher JC Burges, Linda Kaufman et Alexander J. Smola. Cette méthode est appelée régression à vecteur de support (SVR). Le modèle produit par la classification à vecteur de support (comme décrit ci-dessus) ne dépend que d'un sous-ensemble des données d'apprentissage, car la fonction de coût pour la construction du modèle ne se soucie pas des points d'apprentissage qui se trouvent au-delà de la marge. De manière analogue, le modèle produit par SVR ne dépend que d'un sous-ensemble des données d'apprentissage, car la fonction de coût pour la construction du modèle ignore toutes les données d'apprentissage proches de la prédiction du modèle. Une autre version de SVM connue sous le nom de machine à vecteur de support des moindres carrés (LS-SVM) a été proposée par Suykens et Vandewalle.

Former le SVR d'origine signifie résoudre

minimiser

sujet à

où est un échantillon d'apprentissage avec une valeur cible . Le produit scalaire plus l'intercept est la prédiction pour cet échantillon et est un paramètre libre qui sert de seuil : toutes les prédictions doivent être dans une plage des prédictions vraies. Des variables d'écart sont généralement ajoutées ci-dessus pour permettre les erreurs et pour permettre une approximation dans le cas où le problème ci-dessus est irréalisable.

En 2011, Polson et Scott ont montré que le SVM admet une interprétation bayésienne grâce à la technique d' augmentation des données . Dans cette approche, le SVM est considéré comme un modèle graphique (où les paramètres sont connectés via des distributions de probabilité). Cette vue étendue permet l'application de techniques bayésiennes aux SVM, telles que la modélisation flexible des caractéristiques, le réglage automatique des hyperparamètres et la quantification prédictive de l'incertitude . Récemment, une version évolutive du SVM bayésien a été développée par Florian Wenzel, permettant l'application des SVM bayésiens aux big data . Florian Wenzel a développé deux versions différentes, un schéma d'inférence variationnelle (VI) pour la machine à vecteurs de support du noyau bayésien (SVM) et une version stochastique (SVI) pour la SVM bayésienne linéaire.

Les paramètres de l'hyperplan à marge maximale sont dérivés en résolvant l'optimisation. Il existe plusieurs algorithmes spécialisés pour résoudre rapidement le problème de programmation quadratique (QP) qui découle des SVM, s'appuyant principalement sur des heuristiques pour décomposer le problème en morceaux plus petits et plus faciles à gérer.

Une autre approche consiste à utiliser une méthode de point intérieur qui utilise des itérations de type Newton pour trouver une solution aux conditions de Karush-Kuhn-Tucker des problèmes primal et dual. Au lieu de résoudre une séquence de problèmes décomposés, cette approche résout directement le problème dans son ensemble. Pour éviter de résoudre un système linéaire impliquant la grande matrice du noyau, une approximation de rang faible de la matrice est souvent utilisée dans l'astuce du noyau.

Une autre méthode courante est l'algorithme d'optimisation minimale séquentielle de Platt (SMO), qui décompose le problème en sous-problèmes bidimensionnels qui sont résolus de manière analytique, éliminant ainsi le besoin d'un algorithme d'optimisation numérique et d'un stockage de matrice. Cet algorithme est conceptuellement simple, facile à mettre en œuvre, généralement plus rapide et possède de meilleures propriétés d'échelle pour les problèmes SVM difficiles.

Le cas particulier des machines à vecteurs de support linéaires peut être résolu plus efficacement par le même type d'algorithmes utilisés pour optimiser son proche cousin, la régression logistique ; cette classe d'algorithmes comprend la descente sous-gradient (par exemple, PEGASOS ) et la descente coordonnée (par exemple, LIBLINEAR ). LIBLINEAR a des propriétés de temps d'apprentissage intéressantes. Chaque itération de convergence prend un temps linéaire par rapport au temps nécessaire à la lecture des données d'apprentissage, et les itérations ont également une propriété de convergence Q-linéaire , ce qui rend l'algorithme extrêmement rapide.

Les SVM du noyau général peuvent également être résolus plus efficacement en utilisant la descente de sous-gradient (par exemple P-packSVM ), en particulier lorsque la parallélisation est autorisée.

Les SVM du noyau sont disponibles dans de nombreuses boîtes à outils d'apprentissage automatique, notamment LIBSVM , MATLAB , SAS, SVMlight, kernlab, scikit-learn , Shogun , Weka , Shark, JKernelMachines, OpenCV et autres.

Le prétraitement des données (normalisation) est fortement recommandé pour améliorer la précision de la classification. Il existe quelques méthodes de normalisation, telles que le min-max, la normalisation par mise à l'échelle décimale, le score Z. La soustraction de la moyenne et la division par la variance de chaque caractéristique sont généralement utilisées pour le SVM.