Exercices séparation linéaire et SVMs (8.4)

Exercice 33

L'exercice a pour objectif de démontrer qu'il n'existe pas de neurone linéaire à seuil calculant la fonction xor ce qui montre les limites de la séparation linéaire pour des fonctions Booléennes.

1. On "voit" qu'il est impossible de trouver une droite séparant les deux points de classe 1 des deux points de classe 0.
2. Pour le démontrer, considérons un séparateur linéaire d'équation w0+w1 x1+w2 x2=0. On écrit les quatre équations correspondant aux quatre exemples. Pour l'exemple (0,0), le neurone linéaire à seuil doit produire 0 donc on doit avoir w0 + 0 + 0 < 0 (1). Pour l'exemple (0,1), le neurone linéaire à seuil doit produire 1 donc on doit avoir w0 + 0 + w2 > 0 (2). Pour l'exemple (1,0), le neurone linéaire à seuil doit produire 1 donc on doit avoir w0 + w1 + 0 > 0 (3). Pour l'exemple (1,1), le neurone linéaire à seuil doit produire 0 donc on doit avoir w0 + w1 + w2 < 0 (4). Pour montrer que ces quatre inéquations n'ont pas de solution, il suffit d'ajouter les inéquations (1) et (4) pour obtenir w0 + w0 + w1 + w2 < 0 et d'ajouter les inéquations (2) et (3) pour obtenir w0 + w0 + w1 + w2 > 0. Les deux inéquations sont contradictoires et n'ont pas de solution.

Exercice 34

L'exercice montre que les fonctions or et and sur trois variables sont calculables par un neurone linéaire à seuil. Vous pouvez le montrer en écrivant les inéquations comme dans l'exercice précédent mais c'est un peu fastidieux donc nous allons faire fonctionner notre cerveau.

1. La fonction or prend la valeur 1 si et seulement au moins une des trois variables prend la valeur 1, ou encore elle vaut 0 si et seulement si les trois variables valent 0. On voit que les trois variables jouent le même rôle. Choisissons de prendre w1=w2=w3=1. Il suffit alors de bien choisir w0. Un choix est de prendre w0 = -0.5. Vous vérifiez alors que Heaviside(-0.5 + x + y + z ) = or(x,y,z).
2. Avec le même raisonnement, vous obtenez, par exemple, w0 = -2.5 et w1=w2=w3=1 et que Heaviside(-2.5 + x + y + z ) = and(x,y,z).

Exercice 35

L'exercice montre des fonctions Booléennes linéairement séparables et non linéairement séparables.

1. Pour les deux premiers cas, il suffit de généraliser la construction faite pour le and et le or dans l'exercice précédent. Pour (a), on pose w1=...=wn=1, si on veut un nombre d'entrées à 1 strictement supérieur à m, on prend w0 = -m-0.5, si on veut un nombre d'entrées à 1 supérieur ou égal à m, on prend w0 = -m+0.5. Pour (b), on pose w1=...=wn= -1, si on veut un nombre d'entrées à 1 strictement inférieur à m, on prend w0 = m-0.5, si on veut un nombre d'entrées à 1 inférieur ou égal à m, on prend w0 = m+0.5. Pour (c), on pose les poids de la partie droite égaux à +1, les poids de la partie gauche égaux à -1 et on prend w0=0.
2. Considérons un vecteur de coefficients w. Pour les vecteurs x1, ..., xp qui sont de la première classe, on a w.x1 >= 0, ..., w.xp >= 0 et donc w.x1 + ... + w.xp >= 0. Pour les vecteurs y1, ..., yp qui sont de la première classe, on a w.y1 < 0, ..., w.yp < 0 et donc w.y1 + ... + w.yp < 0. En utilisant les propriétés du produit scalaire, on peut encore écrire w.(x1 + ... + xp) >= 0 et w.(y1 + ... + yp) < 0. Ce qui nous mène à une contradiction et donc à l'impossibilité de trouver un séparateur linéaire défini par w si on suppose que (x1 + ... + xp) = (y1 + ... + yp).
3. Pour (a), on choisit (1,0,1,0) et (0,1,0,1) qui ne sont pas dans C, (1,1,0,0) et (0,0,1,1) qui sont dans C et qui vérifient (1,0,1,0) + (0,1,0,1) = (1,1,0,0) + (0,0,1,1) donc C n'est pas linéairement séparable. Notez que pour n<4, la classe définie par contiguïté est linéairement séparable. Pour (b), on considère les vecteurs non symétriques (1,0,1,0) et (0,1,0,1) et les vecteurs symétriques (1,0,0,1) et (0,1,1,0) qui vérifient (1,0,1,0) + (0,1,0,1) = (1,0,0,1) + (0,1,1,0). Pour (c), on peut remarquer que la fonction xor sur 2 variables correspond au cas n=2 et m=1.

Exercice 36

L'exercice a pour objectif d'illustrer le fonctionnement de l'algorithme par correction d'erreur et noter le nombre de passages complets de l'échantillon.

En suivant l'exemple 12 sur la présentation des exemples avec en vecteur initial (1,1,1), il faut 5 présentations complète de l'échantillon et passer par les vecteurs distincts de poids successifs (1,1,1), (0,1,1), (-1,1,0), (-2,0,0), (-1,1,1), (-2,1,0), (-1,2,1), (-2,2,0), (-3,1,0), (-2,2,1), (-3,1,1), (-2,2,2) et (-3,2,1). Un passage complet permet de vérifier que ce vecteur de coefficients classe correctement les quatre exemples. Pour le vecteur initial, (-0.5,-0.5,1), on obtient (-1.5,-0.5,0), (-0.5,0.5,1), (-1.5,0.5,0), (-0.5,1.5,1), (-1.5,1.5,0), (-2.5,0.5,0), (-1.5,1.5,1), (-2.5,0.5,1), (-1.5,1.5,2), (-2.5,1.5,1).

Exercice 37

L'exercice a pour objectif d'étudier le comportement de la correction d'erreur pour un échantillon non linéairement séparable.

J'ai choisi d'initialiser les poids à (1,1,1) et de passer les exemples dans l'ordre (0,0), (0,1), (1,0) et (1,1) de classes respectives -1, +1, +1 et -1. En procédant comme précédemment, on trouve la séquence de vecteurs de poids distincts (1,1,1), (0,1,1), (-1,0,0), (0,0,1), (-1,-1,0), (0,-1,1), (1,0,1), (0,-1,0), (-1,-1,0), (0,-1,1), (1,0,1) et (0,-1,0). On "voit" alors qu'on boucle sur ces quatre derniers vecteurs (-1,-1,0), (0,-1,1), (1,0,1) et (0,-1,0). Donc le programme ne termine pas ! On peut penser à modifier l'algorithme pour repérer que l'algorithme entre dans une boucle sans fin. Mais il existe des arguments théoriques (théorème 4 page 80) qui montrent que cette méthode n'est pas utilisable en pratique car la complexité de l'algorithme serait trop élevée.

Exercice 38

L'exercice montre que différentes initialisations conduisent à des séparateurs linéaires différents.

Dans l'exemple 13, nous avons obtenu le séparateur x2 = 1/3 x1 - 1/3.

Avec l'initialisation par le vecteur (-3,0,1), si on passe l'exemple (0,2) (le vecteur (1,0,2) en ajoutant l'entrée x0 égale à 1) de classe +1, on modifie les poids en (-2,0,3). Si on continue à faire passer les exemples, le vecteur de poids n'est plus jamais modifié et donc l'algorithme converge vers le séparateur linéaire d'équation x2 = 1.5.

Avec l'initialisation par le vecteur (-3,-1,-1), si on passe les exemples dans le même ordre que dans l'exemple 13, on trouve les vecteurs de poids différents successifs (-3,-1,-1), (4,0,1.5), (3,-2,1.5). Ce vecteur de poids n'est plus jamais modifié et définit le séparateur linéaire d'équation x2 = 4/3 x1 -2.

Exercice 39

L'exercice étudie des caractérisations et propriétés des fonctions convexes.

1. La fonction exp(x) est convexe sur R, la fonction max{0,x} est convexe sur R, la fonction 3x^2 est convexe sur R, la fonction -x^2 est concave sur R, la fonction log(x) est concave sur R, la fonction x^3 n'est pas convexe sur R, n'est pas concave sur R, est convexe sur [0,infty[ et est concave sur ]-infty,0].
2. La dérivée de f(x) = x^3 est f'(x) = 3 x^2 et sa dérivée seconde est f"(x) = 6x. Cette dérivée seconde est positive sur [0,infty[ et donc f est convexe sur [0,infty[. Elle est négative sur ]-infty,0] et donc f est concave sur ]-infty,0].
3. Prenons deux fonctions convexes f1 et f2 sur un intervalle I. Considérons la fonction f1+f2. Si les fonctions sont dérivables ou deux fois dérivables, on peut faire la preuve en utilisant les caractérisations de la question précédente. Dans le cas général, considérons deux réels a et b de l'intervalle I, on a alors (f1+f2)(lambda a + (1-lambda) b) = f1(lambda a + (1-lambda)b) + f2(lambda a + (1-lambda) b) par définition de f1+f2. On peut alors utiliser le fait que f1 et f2 soient convexes pour affirmer que cette quantité est inférieure à lambda f1(a) + (1-lambda) f1(b) + lambda f2(a) + (1-lambda) f2(b). En regroupant les termes et en utilisant la définition de f1+f2, ce terme est égal à lambda (f1+f2)(a) + (1-lambda) (f1+f2)(b). Donc, pour tous réels a et b de I et tout lambda de [0,1), nous avons (f1+f2)(lambda a + (1-lambda) b) <= lambda (f1+f2)(a) + (1-lambda) (f1+f2)(b). Donc f1+f2 est convexe.
4. Prenons f1(x) = x^2 et f2(x) = x qui sont deux fonctions convexes sur R. La fonction f1-f2 est convexe sur R car sa dérivée seconde est 2 toujours positive. La fonction f2-f1 est concave sur R car sa dérivée seconde est -2 toujours négative. On ne peut rien dire de la différence de deux fonctions convexes.

Exercice 40

L'exercice applique le gradient stochastique pour comprendre les différences avec la correction d'erreur. Notez que le pas de gradient de 0.5 n'est pas une valeur usuelle car on choisit en général une valeur plus petite. Certains algorithmes diminuent le pas de gradient avec les étapes.

Faisons passer l'exemple (0,2) de classe +1. La sortie calculée avec le vecteur de coefficients (-3,0,1) est -3 x 1 + 0 x 0 + 1 x 2 = -1. On applique la formule (4.8) de la page 89, on obtient le vecteur de coefficients (-2.5,0,2). On fait passer l'exemple (1,1) de classe +1. La sortie calculée vaut -0.5. On obtient le vecteur de coefficients (-2.125,0.375,2.375). On fait passer l'exemple (1,2.5) de classe +1. La sortie calculée vaut 4.1875. On obtient le vecteur de coefficients (-2.921875,-0.421875,0.3828125). Il faut alors itérer ce calcul qui n'est pas possible manuellement et nécessite l'écriture d'un programme avec un critère d'arrêt.

Pour le fait que la solution est meilleure, nous avons vu dans l'exercice 38 que le séparateur linéaire obtenu avec l'algorithme par correction d'erreur dépend fortement de l'initialisation. En général, la descente de gradient va produire un séparateur plus robuste que la correction d'erreur.

Exercice 41

L'exercice illustre des notions de base sur les SVMs.

1. Les exemples sont décrits par une seule valeur réelle. Les réels 1, 3 et 5 sont de classe -1 et les réels 7 et 9 sont de classe +1. Cet échantillon est bien linéairement séparable avec un séparateur défini par le réel 6. Une bibliothèque SVM avec noyau linéaire lancée sur cet échantillon trouve bien ce séparateur. Elle donne 4 vecteurs de support alors qu'on aurait pu penser que les deux vecteurs 5 et 7 suffisent. Ceci est dû au fait qu'avec un choix de C (le paramètre de régularisation) par défaut, les vecteurs de support de la marge sont choisis comme étant 3 et 9 donc avec une marge plus grande. Les vecteurs dans la marge, ici les vecteurs 5 et 7 sont aussi considérés comme des vecteurs de support. Donc on a quatre vecteurs de support 3,5,7 et 9. On peut pénaliser les erreurs et la présence de points dans la marge en augmentant C. Pour une valeur de C assez grande, on trouve alors le séparateur défini par 6 et deux vecteurs de support 5 et 7.
2. Les exemples sont décrits par une seule valeur réelle et on constate que l'échantillon n'est pas linéairement séparable car il n'existe pas de réel qui coupe la droite en deux demi-droites contenant pour l'une les points de classe -1 et pour l'autre les points de classe +1. En s'inspirant de l'exemple 17 page 96, on peut penser qu'un noyau polynomial de degré 2 va permettre de séparer l'échantillon.

Exercice 42

L'exercice illustre une étude où il faut choisir le paramètre de régularisation C.

• La procédure majoritaire associe à tout exemple la classe 1. Son erreur sur S est 700/2000 = 35% et son erreur sur V est 345/1000 = 34.5 %. Notez que la répartition des classes dans les ensembles S et V est proche car les exemples sont tirés aléatoirement et vous devez toujours vérifier cela.
• Le paramètre de régularisation règle un compromis entre erreur et largeur de la marge. C petit privilégie une marge grande quitte à avoir des exemples mal classés ou dans la marge. C grand pénalise les erreurs donc privilégie une marge petite avec peu d'erreurs et peu de points dans la marge.

1. Les erreurs pour les valeurs de C 1, 5, 10, 20, 50 et 200 sont sur S de 315/2000 = 15.75%, 15%, 14%, 12.5%, 10.05% et 8.75% et sur V sont 20.5%, 19.5%, 18%, 16.7%, 15.5% et 17.3%.
2. Lorsque C augmente, l'erreur mesurée sur S diminue ce qui correspond à recherche une hypothèse faisant peu d'erreurs sur l'échantillon quitte à diminuer la marge. Lorsque C augmente, l'erreur mesurée sur V diminue puis recroit. Pour C trop petit, on peut avoir des hypothèses trop générales qui n'apprennent pas suffisamment. Pour C trop grand, on peut générer des hypothèses trop spécialisées sur l'échantillon S qui ne généralisent pas bien.
3. Les erreurs sur T ne sont pas données dans l'énoncé !
4. On choisit C=50 qui produit la meilleure erreur estimée sur V.
5. Pour estimer l'erreur réelle, on ne peut pas utiliser l'erreur sur V car V a servi à apprendre (pour choisir C). On peut utiliser l'erreur mesurée sur un ensemble test T qui aurait été laissé de côté.
6. Son argument affirmant que choisir un noyau complexe amène toujours de meilleurs résultats est faux. En effet, il faut choisir une classe d'hypothèses bien adaptée au problème et la séparation linéaire (donc un noyau linéaire) donne de bons résultats sur des problèmes pas trop complexes ou des problèmes en très grande dimension comme le classement de textes. Par contre, chercher un meilleur noyau peut être intéressant et donc il aurait pu être utile de faire des expériences plus complètes pour choisir simultanément le noyau et le paramètre C.

Exercice 43

L'exercice illustre une étude pour le choix du noyau.

1. On choisit un noyau polynomial de degré 2 qui a la plus petite erreur sur V.
2. L'erreur sur V ne peut pas être utilisée pour estimer l'erreur réelle car V a servi en apprentissage pour choisir le noyau.
3. Il faudrait disposer d'un ensemble test T non utilisé précédemment.