Je m'intéresse aux résultats théoriques pour la capacité de généralisation des machines à vecteurs de support, par exemple les limites sur la probabilité d'erreur de classification et sur la dimension Vapnik-Chervonenkis (VC) de ces machines. Cependant, en lisant la littérature, j'ai eu l'impression que certains résultats récurrents similaires ont tendance à différer légèrement d'un auteur à l'autre, en particulier en ce qui concerne les conditions techniques requises pour une donnée donnée à tenir.
Dans ce qui suit, je rappellerai la structure du problème SVM et l'état 3 des principaux résultats de généralisation que j'ai régulièrement trouvés sous une forme ou une autre je donne 3 références principales tout au long de l'exposition.
Réglage du problème :
Supposons que nous ayons un échantillon de données de paires indépendantes et identiquement distribuées (iid) où pour tout , et . Nous construisons une machine à vecteur de support (SVM) qui maximise la marge minimale entre l'hyperplan de séparation défini par , et , et le point le plus proche parmi manière à séparer les deux classes définies par et . Nous laissons le SVM admettre quelques erreurs à travers une marge souple en introduisant des variables de mou - mais pour simplifier la notation, nous ignorons la possibilité de noyaux. Les paramètres de solution et sont obtenus en résolvant le programme d'optimisation quadratique convexe suivant:b ∗
Nous sommes intéressés par la capacité de généralisation de cette machine.
Dimension VC de Vapnik-Chervonenkis :
Un premier résultat est dû à (Vapnik, 2000), dans lequel il délimite la dimension VC d'un hyperplan séparateur, le théorème 5.1. Laisser, nous avons:
Ce résultat peut de nouveau être trouvé dans (Burges, 1998), théorème 6. Cependant, il semble que le théorème de Burges soit plus restrictif que le même résultat de Vapnik, car il doit définir une catégorie spéciale de classificateurs, appelés classificateurs tolérants aux écarts. à laquelle appartient le SVM , pour énoncer le théorème.
Limites de la probabilité d'erreurs :
Dans (Vapnik, 2000), le théorème 5.2 de la page 139 donne la limite suivante sur la capacité de généralisation SVM:
où est le nombre de vecteurs de support du SVM. Ces résultats semblent se retrouver dans (Burges, 1998), dans les équations (86) et (93) respectivement. Mais encore une fois, Burges semble différer de Vapnik car il sépare les composants au sein de la fonction minimale ci-dessus dans différents théorèmes, avec des conditions différentes.
Un autre résultat apparaissant dans (Vapnik, 2000), p.133, est le suivant. En supposant à nouveau que, pour tout , et en laissant et , nous définissons comme étant égal à:
Nous définissons également comme le nombre d'exemples de formation mal classés par le SVM. Ensuite, avec la probabilité nous pouvons affirmer que la probabilité qu'un exemple de test ne soit pas séparé correctement par l' hyperplan -marge c'est-à dire SVM avec la marge a la limite:
Cependant, dans (Hastie, Tibshirani et Friedman, 2009), p.438, un résultat très similaire est trouvé:
Conclusion :
Il me semble qu'il existe un certain degré de conflit entre ces résultats. En revanche, deux de ces références, bien que canoniques dans la littérature SVM, commencent à être légèrement anciennes (1998 et 2000), surtout si l'on considère que la recherche sur l'algorithme SVM a commencé au milieu des années 90.
Mes questions sont:
- Ces résultats sont-ils toujours valables aujourd'hui ou se sont-ils révélés erronés?
- Des limites plus strictes avec des conditions relativement lâches ont-elles été dérivées depuis lors? Si oui, par qui et où puis-je les trouver?
- Enfin, existe-t-il un matériel de référence qui synthétise les principaux résultats de généralisation concernant le SVM?
Références :
Vapnik, VN (1998). Théorie de l'apprentissage statistique , 1re édition, John Wiley & Sons
Vapnik, VN (2000). The Nature of Statistical Learning Theory , 2e édition, Springer
la source
Réponses:
Je ne connais pas la littérature à laquelle vous faites référence en détail, mais je pense qu'un résumé complet des limites de généralisation qui devraient être à jour peut être trouvé dans Boucheron et al. (2004) (lien: https://www.researchgate.net/profile/Olivier_Bousquet/publication/238718428_Advanced_Lectures_on_Machine_Learning_ML_Summer_Schools_2003_Canberra_Australia_February_2-14_2003_Tubingen_Germany_August_4-16_2003_Revised_Lectures/links/02e7e52c5870850311000000/Advanced-Lectures-on-Machine-Learning-ML-Summer-Schools-2003- Canberra-Australie-2-14 février 2003-Tuebingen-Allemagne-4-16-2003-Revised-Lectures.pdf # page = 176 )
Je vais esquisser une partie du SVM lié dans ce qui suit, en omettant les détails et les preuves.
Avant d'élaborer spécifiquement sur la liaison SVM, nous devons comprendre ce que les limites de généralisation tentent d'atteindre.
Supposons d'abord que la vraie probabilité est connue, alors le meilleur classificateur possible serait le classificateur bayésien, c'est-à-direP(Y=+1|X=x)
Le but de la théorie de l'apprentissage statistique est maintenant de trouver la différence entre un classifieur de classe (par exemple SVM) et le classifieur bayes, c'est-à-dire Notez que est la perte attendue des données donnée et est le meilleur classificateur possible dans la classe de modèle . Le terme est appelé erreur d'estimation et souvent le foyer car il peut être borné beaucoup plus facilement que l'erreur d'approximation (l'autre terme). Je vais également omettre l'erreur d'approximation ici.C
L'erreur d'estimation peut être encore décomposée avec Maintenant, cela peut être limité par deux étapes:Z
Bound utilisant l'inégalité McDiarmidZ−EZ
Lié avec la complexité de RademacherEZ Rn(C)=Esupg∈C|1/n∑ni=1l(g(Xi),Yi)|
En utilisant l'inégalité de McDiarmids, on peut montrer que si la fonction de perte se situe dans un intervalle ne dépassant pas , la première étape entraîne une limite de où est le niveau de confiance. Pour la deuxième étape, nous pouvons montrer que Si vous avez une fonction de perte discrète, c'est-à-dire non Lipschitz comme le 0-1 -loss, vous auriez besoin de la dimension VC pour délimiter davantage la complexité de Rademacher. Cependant, pour les fonctions L-lipschitz telles que la perte de charnière, cela peut être encore limité par oùB
la source