La relation entre le nombre de vecteurs de support et le nombre d'entités

12

J'ai exécuté un SVM sur un ensemble de données donné et j'ai fait l'observation suivante: Si je modifie le nombre de fonctionnalités pour la construction du classificateur, le nombre de vecteurs de support résultants sera également modifié.

Je voudrais savoir comment expliquer ce genre de scénario.

machine-learning classification svm kernel-trick user3269
la source
Quels étaient le type et le style de ces fonctionnalités supplémentaires? Où ressemblent-ils à des variantes des fonctionnalités existantes ou à des fonctionnalités plus récentes qui, selon vous, pourraient avoir un pouvoir de résolution supplémentaire?
Philip Oakley
Il s'agit d'un problème de classification des documents et les fonctionnalités supplémentaires ne sont que des mots. J'ai utilisé unigram pour créer un espace de fonctionnalités.
user3269
Étant donné la réponse de @ marc, qui a fait le changement, le nombre de vecteurs a-t-il augmenté avec le nombre de caractéristiques, ou l'inverse.
Philip Oakley
@Phillip, ma réponse d'origine était fausse. Je pense que la réponse modifiée est exacte maintenant.
Marc Shivers

Réponses:

13

Si vous regardez le problème d'optimisation que SVM résout:

minw,ξ,b{12‖w‖2+C∑i=1nξi}

st pour toutyi(w⋅xi−b)≥1−ξi,    ξi≥0,i=1,…n

les vecteurs de support sont ceux où le . En d'autres termes, ce sont les points de données qui sont soit mal classés, soit proches de la frontière.ξ i > 0xiξi>0

Comparons maintenant la solution à ce problème lorsque vous disposez d'un ensemble complet de fonctionnalités, au cas où vous jetez certaines fonctionnalités. Jeter une fonctionnalité équivaut fonctionnellement à conserver la fonctionnalité, mais en ajoutant une contrainte pour la fonctionnalité que nous voulons supprimer. jwj=0j

Lorsque vous comparez ces deux problèmes d'optimisation et que vous effectuez des calculs mathématiques, il s'avère qu'il n'y a pas de relation difficile entre le nombre de fonctionnalités et le nombre de vecteurs de support. Cela pourrait aller dans les deux sens.

Il est utile de penser à un cas simple. Imaginez un cas à 2 dim où vos caractéristiques négatives et positives sont regroupées autour de (-1, -1) et (1,1), respectivement, et sont séparables avec un hyperplan de séparation diagonal avec 3 vecteurs de support. Imaginez maintenant que vous supprimiez la fonction de l'axe des y, de sorte que vos données soient désormais projetées sur l'axe des x. Si les données sont toujours séparables, disons à x = 0, vous vous retrouveriez probablement avec seulement 2 vecteurs de support, un de chaque côté, donc l'ajout de la fonction y augmenterait le nombre de vecteurs de support. Cependant, si les données ne sont plus séparables, vous obtiendrez au moins un vecteur de support pour chaque point situé du mauvais côté de x = 0, auquel cas l'ajout de la fonction y réduirait le nombre de vecteurs de support.

Donc, si cette intuition est correcte, si vous travaillez dans des espaces d'entités de très haute dimension, ou si vous utilisez un noyau qui correspond à un espace d'entités de haute dimension, alors vos données sont plus susceptibles d'être séparables, donc l'ajout d'une fonctionnalité aura tendance pour ajouter simplement un autre vecteur de support. Alors que si vos données ne sont pas actuellement séparables et que vous ajoutez une fonctionnalité qui améliore considérablement la séparabilité, vous êtes plus susceptible de voir une diminution du nombre de vecteurs de support.

Marc Shivers
la source