Teaching - MAIAD


MAIAD: boosting pour la classification de texte

Soutenance le 18 janvier dans la salle habituelle

Nous allons procéder en 2 groupes:

Les personnes dont le nom commence par la lettre A -> K (inclus) viennent à 8h30 Les autres viennent dans le second créneau, à 10h45

Rappel des critères de notations de la soutenance:

- Clarté de la présentation

- Qualité de l'oral et des slides

- Originalité de présentation (insister sur les améliorations que vous avez apporté, ne pas passer trop de temps sur Adaboost/perceptron qui ont été expliqué en cours)

- Réponses aux questions

Les performances de vos méthodes seront évaluées dans une seconde note sur le rapport/code.

Les transparents sont bons, les problèmes rencontrés viennent de trois facteurs:

stabilité du perceptron

  • Afin de rendre le perceptron plus stable, il est utile de normaliser la mise à jour (sinon, chaque exemple contribue différemment à la mise à jour en fonction de sa position):
 W = W + (eps*Y(i)*X(i,:)/sqrt(sum(X(i,:).^2)));
  • Il peut également être utile d'introduire une marge, c'est à dire une zone d'ambiguité dans laquelle les points participent à la mise à jour de la solution même s'ils sont bien classés:
 if Y(i)*W*X(i,:)' < 1
      W = W + (eps*Y(i)*X(i,:)/sqrt(sum(X(i,:).^2)));
 endif

Calcul de l'erreur dans le boosting (et donc, calcul du alpha)

L'erreur doit être calculée sur la distribution Dt et non sur l'ensemble d'apprentissage. Le code qui permet d'aboutir simplement à ce résultat est proposé ci-dessous (on repère les indices des points mal classés puis on extrait la valeur correspondante de Dt).

 [X1,Y1]=GenAleat(X,Y,D);
 [W]=perceptron(X1,Y1,eps,maxIter);
 ypred = X*W';

 index = find(ypred.*Y<0);
 err = sum(D(index));
 alpha=1;
 if(err != 0)
    alpha=0.5*log((1-err)/err);
 endif

 D=D.*exp((-alpha)*Y.*sign(X*W'));
 D=D/sum(D);

Les hypothèses faibles renvoient -1 ou 1

Il faut prendre le signe de chaque prédiction faible avant de la pondérer avec un alpha. (C'est ce qui est noté dans les transparents mais j'ai induit certains d'entre vous en erreur sur ce point).

 % X mes données (avec un vecteur de 1)
 % W une matrice avec tous les coefficients de regressions (une reg/ligne)
 %   W : nBoost x 3
 % alpha : nBoost x 1
 ypred = sign(X*W')*alpha

Si vous omettez le seuillage sign, la décision reste linéaire quelque soit le nombre d'itération du boosting...

Sur l'exemple clowns, avec nBoost=60, voici ce que l'on obtient:

Petite remarque amusante

Souvent, avec le boosting, le classifieur le plus faible se révèle le plus efficace après la phase de boosting... Et c'est ce qui se passe si vous tracez successivement des droites horizontales/verticales.

Proposition d'implémentation:

 % t designe la variable d'iteration
 % la premiere dimension de X contient les 1
 % iter paire -> verticale
 % iter impaire -> horizontale
 if mod(t,2) == 0
      dim=[1,2];
 else
      dim=[1,3];
 endif

 [W]=perceptron(X1(:,dim),Y1,eps,maxIter);

 if mod(t,2) == 0
      W = [W 0];
 else
      W = [W(1) 0 W(2)];
 endif

Exemple de résultat: