DEA PTI Perception et Traitement de l’Information

  • Published on
    20-Jan-2016

  • View
    31

  • Download
    2

Embed Size (px)

DESCRIPTION

DEA PTI Perception et Traitement de lInformation. Reconnaissance des formes Les mthodes base de noyaux S. Canu http://psichaud.insa-rouen.fr/~scanu/RdF. Buts de la RdF. D : Algorithme de Reconnaissance des Formes. Cest la forme y=D(x) . Une forme x (vecteur forme - PowerPoint PPT Presentation

Transcript

  • DEA PTI Perception et Traitement de lInformationReconnaissance des formesLes mthodes base de noyaux

    S. Canu

    http://psichaud.insa-rouen.fr/~scanu/RdF

  • Buts de la RdFD : Algorithme de Reconnaissancedes FormesUne forme x(vecteur formedes caractristiques)Cest la formey=D(x) Nous voulons un algorithme de RdF performant

  • RdF et apprentissageD : Algorithme de Reconnaissancedes FormesUne forme x(vecteur formedes caractristiques)Cest la formey=D(x) A : Algorithme dapprentissageEnsemble dapprentissage (chantillon)A priorisur lanature de la solution23Les problmes

  • Les mthodes base de NoyauCe qui se ressemble sassemble=zone dinfluence dun exempleEnsemble dapprentissage (chantillon)si x ressemble un xi, il aura ltiquette yi

  • Zone dinfluenceDfinition : Si d(x,xi) < b x appartient la zone dinfluence du point xib

  • Rgle de dcisionDfinition : 1-Si x appartient la zone dinfluence dun seul point xi, alors il a ltiquette yi2-Si x appartient la zone dinfluence de plusieurs points de mme tiquette, alors il a cette tiquette3-Si x appartient la zone dinfluence de plusieurs point dtiquette diffrentes, alors il y a rejet dambiguit4-Si x appartient la zone dinfluence daucun point, alors il y a rejet de distance12344b

  • Mise en uvrefor i = 1:n d(i) = norm((x-xi(i,:))/b);endind = find(d>seuil); b caractrise la zone dinfluence dun point

  • Pour b grandLa zone dambigut est trop importante

  • Pour b plus petitLa zone de rejet de distance est trop importanteil faut cumuler les influencesxx

  • NoyauDistance de la forme x toutes les forme de lensemble dapprentissageOn peut aussi modifier la zone dinfluence dun point

    au lieu davoir uniquement une influence de type tout ou rienon peut imaginer de nombreuses autres manires dont un point influence les autres : par exemple :

  • NoyauFrontire de dcisiond(x)=0d(x)=0Classe 1Classe 2

  • Noyau matlabd = 0

    for i = 1:n d = d + yi(i)*exp(-(norm(xi(i,:)-x).^2)/b);end

    D=sign(d);

  • Avec rejet d(x) est petit si x est loin des xi ou si les rouges et les bleus se compensentrejet de distance et rejet dambigut ?????Frontire de dcisiond(x)=rClasse 1Classe 2d(x)=-rrejet

  • Noyaux avec rejetsEst-ce une bonne ide ?Comment interprter d ?Comment choisir G ?Comment choisir b ?Comment choisir les seuils ?Classe 1Classe 2Rejet de distanceRejet dambigut

  • Est-ce une bonne ide ? Oui si cest universellement consistant

  • Comment choisir G : Autres noyaux

  • Exemples de noyauxNoyaux positifs et les autres

  • Universellement consistantDfinition : un noyau G est dit rgulier si il est non ngatif il existe une boule contre B de rayon r et une constante k telle que :

    Thorme :Erreur de notre rgleErreur de Bayes

  • Comment interprter le rgle de dcision ? Estimation de densit par des noyauxFentres de ParzenConsistance universelleStratgie de RdF : Cest la rgle du MAP

  • Discrimination avec les noyau de Parzen : rgle du MAP (3 classes)d1 = 0; d2 = 0; d3 = 0;for i = 1:n if(yi(i)=1); d1 = d1 + exp(-(norm(xi(i,:)-x).^2)/b); end; % Vraisemblance if(yi(i)=2); d2 = d2 + exp(-(norm(xi(i,:)-x).^2)/b); end; if(yi(i)=3); d3 = d3 + exp(-(norm(xi(i,:)-x).^2)/b); end;end

    pc1=length(x1); pc2=length(x2); pc3=length(x3);nt = pc1+pc2+pc3;pc1=pc1/nt; pc2=pc2/nt; pc3=pc3/nt; % probabilit a priorip = pc1*d1+pc2*d2+pc3*d3; % p(x) (thorme des probabilit totales)

    map1 = pc1*d1./p; map2 = pc2*d2./p; map3 = pc3*d3./p;

    seuil = .15; rejetD = 0.025;

    if (map1>(map2+seuil)) & (map1>(map3+seuil))); classe = 1elseif ((map2>(map1+seuil)) & (map2>(map3+seuil))); classe = 2elseif (map3>(map1+seuil)) & (map3>(map2+seuil))); classe = 3elseif (p

  • MAP sur 3 classes

  • Exemple sur 3 classes

  • Comment choisir b ?Minimiser lerreur en gnralisation :

    avec un ensemble de test

    avec une technique de rchantillonnage

    avec une borne sur lerreur

  • Mthode linairemthode des potentielsLes ci sont recherchs de manire minimiser la probabilit derreurLes ci traduisent linfluence du point dans le calcul de la solution

  • Mthodes non linaires : les RBFCasser la linarit : adapter le noyau au problme au lieu de choisir xi, optimiser la position du centre adapter la largeur de bande du noyau si on a de bon noyaux, on peu en rduire le nombre Les ci mi et bi sont recherchs de manire minimiser lerreur :ATTENTION : on a maintenant un problme de minimisation non linaire

  • Inconvnient des noyauxla maldiction de la dimensionnalitn points pour d dimensions Formulation gomtrique,Densit de lchantillonnage,Distance entre 2 points,Tous les points sont la frontire,Borne de Stone,En grande dimension la notion de distance ne veut pas dire grand chose

  • Densit de lchantillonnagen points pour d dimensionsX ~ N(0,1) d x = randn(10000,100)proj = x * x(1,:);hist(proj./proj(1))X ~ U(0,1) ddist(n,d) = Ej(mini |xi-xj|)n

  • ConclusionNoyau =distancemaldiction = reprsentationflexibilit = largeur de bandedes noyaux pour battre la maldiction ?vers la non linarit pour battre la maldiction !

  • TP matlabAller rechercher les donnes sur le WEB : psichaud.insa-rouen.fr\~scau\RdF\DataAcor.txtouvrir Matlab : et charger les donnesload 'DataAcor.txt'Xi = DataAcor;visualiser les donnes grce au programme visu.mcrire une programme matlab1. Netoyer les donnes (liminer les codes -9999)2. Normaliser3. diviser les donnes en apprentissage / test4. raliser lanalyse discriminante5. estimer les densits par la mthode de Parzen6. calculer et visualiser la matrice de confusion

    parzen3crejet

Recommended

View more >