Pourquoi transformer les données en un espace d'entités de grande dimension dans lequel les classes sont linéairement séparables conduit à un sur-ajustement?

10

J'ai lu dans mon livre (classification des modèles statistiques par Webb et Wiley) dans la section sur les SVM et les données linéairement non séparables:

Dans de nombreux problèmes pratiques du monde réel, il n'y aura pas de frontière linéaire séparant les classes et le problème de la recherche d'un hyperplan de séparation optimal n'a pas de sens. Même si nous devions utiliser des vecteurs d'entités sophistiqués, , pour transformer les données en un espace d'entités de grande dimension dans lequel les classes sont linéairement séparables, cela conduirait à un sur-ajustement des données et donc à une faible capacité de généralisation .Φ(x)

Pourquoi transformer les données en un espace d'entités de grande dimension dans lequel les classes sont linéairement séparables conduit à un sur-ajustement et à une faible capacité de généralisation?

Gigili
la source

Réponses:

8

@ffriend a un bon article à ce sujet, mais de manière générale, si vous vous transformez en espace d'entités de grande dimension et que vous vous entraînez à partir de là, l'algorithme d'apprentissage est «forcé» de prendre en compte les entités d'espace supérieur, même si elles n'ont rien à voir avec les données d'origine, et n'offrent aucune qualité prédictive.

Cela signifie que vous n'allez pas généraliser correctement une règle d'apprentissage lors de la formation.

Prenons un exemple intuitif: supposons que vous vouliez prédire le poids à partir de la taille. Vous disposez de toutes ces données, correspondant aux poids et hauteurs des personnes. Disons que très généralement, ils suivent une relation linéaire. Autrement dit, vous pouvez décrire le poids (W) et la taille (H) comme:

W=mHb

, où est la pente de votre équation linéaire et est l'ordonnée à l'origine, ou dans ce cas, l'ordonnée à l'origine.mb

Disons que vous êtes un biologiste chevronné et que vous savez que la relation est linéaire. Vos données ressemblent à un nuage de points orienté vers le haut. Si vous conservez les données dans l'espace bidimensionnel, vous y placerez une ligne. Cela pourrait ne pas toucher tous les points, mais c'est correct - vous savez que la relation est linéaire et vous voulez quand même une bonne approximation.

Disons maintenant que vous avez pris ces données bidimensionnelles et que vous les avez transformées en un espace dimensionnel supérieur. Ainsi, au lieu de seulement , vous ajoutez également 5 autres dimensions, , , , et .HH2H3H4H5H2+H7

Vous allez maintenant trouver des coefficients du polynôme pour ajuster ces données. Autrement dit, vous voulez trouver les coefficients pour ce polynôme qui «correspond le mieux» aux données:ci

W=c1H+c2H2+c3H3+c4H4+c5H5+c6H2+H7

Si vous faites cela, quel type de ligne obtiendriez-vous? Vous en obtiendriez un qui ressemblerait beaucoup à l'intrigue d'extrême droite de @ffriend. Vous avez surchargé les données, car vous avez «forcé» votre algorithme d'apprentissage à prendre en compte des polynômes d'ordre supérieur qui n'ont rien à voir avec quoi que ce soit. Biologiquement parlant, le poids dépend de la taille de façon linéaire. Cela ne dépend pas de ou de n'importe quel non-sens d'ordre supérieur.H2+H7

C'est pourquoi si vous transformez les données en dimensions d'ordre supérieur à l'aveugle, vous courez un très gros risque de sur-ajustement et de ne pas généraliser.

Spacey
la source
6

Disons que nous essayons de trouver une fonction qui se rapproche d'un ensemble de points 2D sur la plaine en utilisant une régression linéaire (ce qui est essentiellement à peu près ce que fait SVM). Sur 3 images sous les croix rouges se trouvent des observations (données d'entraînement) et 3 lignes bleues représentent des équations avec différents degrés de polynôme utilisées pour la régression.

entrez la description de l'image ici

La première image est générée par équation linéaire. Comme vous pouvez le voir, cela reflète assez mal les points. C'est ce qu'on appelle le sous- ajustement , car nous avons donné trop peu de "degré de liberté" à l'algorithme d'apprentissage (polynôme de trop petit degré). La deuxième image est bien meilleure - nous avons utilisé un polynôme de deuxième degré et cela semble assez bon. Cependant, si nous augmentons davantage le "degré de liberté", nous obtenons la 3ème image. La ligne bleue vient juste à travers les croix, mais croyez-vous que cette ligne décrit vraiment la dépendance? Je ne pense pas. Oui, sur l'ensemble d'apprentissage, l'erreur d'apprentissage (distance entre les croix et la ligne) est très petite, mais si nous ajoutons une observation de plus (par exemple, à partir de données réelles), l'erreur est probablement beaucoup plus importante que si nous utilisions l'équation de la seconde image. Cet effet est appelé sur- ajustement- nous essayons de suivre les données de formation de trop près et de résoudre les problèmes. L'utilisation de polynômes d'une seule variable est un exemple simple de noyau - au lieu d'une dimension ( ), nous en utilisons plusieurs ( , , , etc.). Vous pouvez voir que la traduction des données dans un espace de dimension supérieure peut aider à surmonter le sous-ajustement , mais cela peut également conduire à un sur-ajustement . Le vrai défi est de trouver ce qui est "juste". Quelques conseils pour vos recherches ultérieures sur ce sujet. Vous pouvez détecter le sur-ajustement avec une procédure appelée validation croiséexxx2x3. En bref, vous divisez vos données en, disons, 10 parties, en prenez 9 pour la formation et 1 pour la validation. Si l'erreur sur l'ensemble de validation est beaucoup plus élevée que sur l'ensemble de train, alors vous avez une surcharge. La plupart des algorithmes d'apprentissage automatique utilisent certains paramètres (par exemple les paramètres des noyaux dans SVM) qui permettent de surmonter le sur-ajustement. En outre, un mot clé populaire ici est la régularisation - modification de l'algorithme qui affecte directement le processus d'optimisation, disant littéralement "ne suivez pas les données de formation de trop près".

BTW, je ne suis pas sûr que DSP soit le bon site pour ce genre de questions, vous serez probablement intéressé à visiter CrossValidated aussi.

ami
la source
Cela a été - volé - emprunté aux conférences vidéo d'Andrew Ng sur l'apprentissage automatique. À moins que ce ne soit vous, Dr Ng. Dans ce cas, recherchez-vous un doctorant pour votre laboratoire? (Les conférences peuvent être trouvées sur coursera.com pour ceux d'entre vous qui sont intéressés)
CyberMen
@CyberMen: il a été volé à images.google.com :) Mais oui, la notation est très similaire à celle de Ng. Et je recommanderais certainement son cours (et d'autres articles) pour une introduction à l'apprentissage automatique.
ffriend
Je pense que DSP est le bon endroit pour ce genre de question, entre autres sites SE au moins.
Gigili
2

Avez-vous lu plus loin?

À la fin de la section 6.3.10:

"Cependant, il y a souvent des paramètres du noyau qui doivent être définis et un mauvais choix peut conduire à une mauvaise généralisation. Le choix du meilleur noyau pour un problème donné n'est pas résolu et des noyaux spéciaux ont été dérivés pour des problèmes particuliers, par exemple la classification de documents "

ce qui nous amène à la section 6.3.3:

" Les noyaux acceptables doivent être exprimables comme un produit intérieur dans un espace de fonctionnalité, ce qui signifie qu'ils doivent satisfaire la condition de Mercer"

Noyau par leur propre zone assez difficile, vous pouvez avoir de grandes données où dans différentes parties doivent appliquer différents paramètres, tels que le lissage, mais ne savez pas exactement quand. Par conséquent, une telle chose est assez difficile à généraliser.

sigrlami
la source
Je lis "4.2.5 Soutenir les machines vectorielles" comme je l'ai dit, je ne sais pas de quelle section 6 vous parlez. Étant donné que le paragraphe après ce que j'ai mentionné dans la question n'a rien à ce sujet, j'ai pensé que je ferais mieux de le poser ici.
Gigili
Désolé, je l'ai mélangé avec la reconnaissance de modèle statistique également par Webb, que je regarde en ce moment et qui a les mêmes chapitres.
sigrlami