DEA Perception et Traitement de l’Information

  • Published on
    09-Jan-2016

  • View
    30

  • Download
    2

Embed Size (px)

DESCRIPTION

DEA Perception et Traitement de lInformation. Reconnaissance des formes Rgle de Bayes 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 des caractristiques). - PowerPoint PPT Presentation

Transcript

  • DEA Perception et Traitement de lInformationReconnaissance des formesRgle de Bayes

    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

  • Thorme de Bayes (et non la rgle)Ex : en franais P(e) = 0,12On choisi la source, et on metOn choisi une observation, et on dcideEx : aprs avoir observ x quelle est P(e|x) ?Attention la confusion source - action

  • illustrationsource 1source 2sans autre informationon dcide toujours quun pixel vient de la zone (source 1)

    car P(S1) > P(S2)

    A PRIORI

    que se passe til si lon connat un caratristique : xlintensit

  • illustrationsource 1source 2Caractristique : xlintensit

    on dcidelaction qui cotele moins cher

    en cout 0-1cest la classe maxA POSTERIORIxf(x|s1)f(x|s2)Les vraisemblances

  • illustrationf(x|s1)f(x|s2)Rgle de dcision

  • notationsespace des sourcesJ cot dune rgle de dcision(erreur de prdiction)

  • Cas particulier des 2 classes et cots 0-1

  • Cas particulier des 2 classes et cots 0-1Minimiser J(D) cest minimiser la probabilit derreur

  • Thorme fondamentalDfinition : rgle de dcision du maximum a posteriorixr(x)x*tel que r(x*)=1/2

  • Dfinition fondamentaleCot minimum = maximum posteriori = minimum derreurDfinitions : - D* est appele rgle de Bayes cest la rgle qui donne la plus petite probabilit derreur - le problme qui consiste rechercher D* est le problme de Bayes - J*=J(D*) est appele lerreur de BayesPour

  • Rsum : problme de RdFespace des sources(erreur de prdiction)

  • illustrationIllustration 1dpour deux classesfX(x,0) ~ N(m0,1)fX(x,1) ~ N(m1,1)r(x) = P(S=1|x)P(S=0|x) = 1-r(x)

  • Dmonstration du thorme fondamental(maximum a posteriori)Il est difficile de minimiser J(D) (dmonstration constructive)car la fonction cot nest pas drivable

  • Interprtation en terme de moindres carrsLa minimisation de lerreur quadratique mne la rgle de BaysLa minimisation de lerreur absolue aussi !

  • Rejet : rgle de ChowRejet dambiguitDfinition : rgle de dcision du maximum a posteriori1/21rAxclasse 0 rejet classe 1

  • Rejet de distance (Dubuisson)1/21rAxrejet de distance classe 0 rejet classe 1 rejet de distancerD = 0 et rA = .5 : rgle du MAP (bayes pour le cot 0-1)rD

  • illustrationIllustration 2dpour deux classesfX(x,0) ~ N(m0,1)fX(x,1) ~ N(m1,1)r(x) = P(S=1|x)P(S=0|x) = 1-r(x)P(x) = fX(x,0) + fX(x,1) rejet dambigut

  • illustration

  • Un exemple simpleS=0 vous ratez votre DEA, S=1 vous lavezX : le nombre dheures de travail par semaine

  • Un exemple simpleS=0 vous ratez votre DEA, S=1 vous lavezX : le nombre dheures de travail par semaine

  • Rsum : problme de RdFespace des sources(erreur de prdiction)

  • RdF : stratgie de Base1. Estimer

    2. Retrouver la rgle de BayesAlternative

    minimiser directement la probabilit derreur(estimer une densit est un problme trs difficile)

  • Comment comparer deux algorithmesSoit D1 et D2 deux algorithmes (kppv et arbres de dcision)Soit J1 = J(D1) lerreur de classification de D1 et J2 = J(D2)

    Imaginons que nous connaissions J1 et J2

    Sur un chantillon D1 est meilleur, sur un autre cest D2comment les comparer ?

    En moyenne : E(J) (lesprance sur tous les chantillons possibles)

    un algorithme est dit consistant si

    la probabilit derreur tend vers son minimum

    si cest vrai quelle que soit la distribution des exemples, lalgorithme est dit universellement consistantDfinition

  • Thorme (Stone 1977)Lalgorithme des kppv est un algorithme universellement consistantAttention : un bon algorithme peut donner un mauvais classifieur (on peu aussi gagner au loto)

  • A savoirVariable alatoire cas discret (un exemple) cas continu (un exemple)Probabilit, probabilit conditionnellefonction de rpartition et densitloi usuelles : bernouilli, binomiale, poisson, normaleEsprance, cas discret (un exemple)cas continu (un exemple)VarianceQuiz de 5 minutes maintenant

  • ConclusionUn problme de reconnaissance des formes se caractrisepar une loi priori, une vraisemblance (souvent inconnues),une fonction cot et un chantillon (souvent connus).

    La meilleure solution possible (souvent inconnue) la rgle de Bayes cest le MAP qui minimise la probabilit derreur

    Il faut en plus faire du rejet

    Reste savoir comment approcher la rgle de Bayes partir de lchantillon

    deux stratgies sont possibles : 1. Approcher les lois inconnues puis appliquer le principe du MAP (la rgle de bayes sur une approximation des lois)2. Minimiser directement une estimation de la probabilit derreur

Recommended

View more >