Théorie de l'information et codage

De
Publié par

Théorie de l'information et codage 2010/2011 Cours 4 — 8 mars 2011 Enseignant: Marc Lelarge Scribe: Louis Jachiet Pour information – Page web du cours Propriétés de l'entropie et de l'information mutuelle 4.1 Rappel (X,Y) ? p(x, y) = P(X = x,Y = y) Définition 4.1.1 entropie (jointe) : H(X,Y) = ? ∑ x?X ∑ y?Y p(x, y) log p(x, y) (logarithme en base 2) entropie conditionnelle : H(Y|X) = ∑ x?X p(x)H(Y|X = x) = ? ∑ x?X p(x) ∑ y?Y p(y|x) log p(y|x) = ? ∑ x?X ∑ y?Y p(x, y) log p(y|x). Théorème 4.1.1 règle de la chaîne H(X,Y) = H(X) +H(Y|X) Démonstration. On utilise p(x, y) = p(x)p(y|x) de telle sorte que : H(X,Y) = ? ∑ x?X ∑ y?Y p(x, y) log p(x, y) = ? ∑ x?X ∑ y?Y p(x, y) log p(x) ? ∑ x?X ∑ y?Y p(x

  • inégalités de convexité théorème

  • bn ≥

  • distance de kullbak-leibler

  • règles de la chaîne théorème

  • théorème précédent

  • bi ∑


Publié le : mardi 1 mars 2011
Lecture(s) : 82
Tags :
Source : di.ens.fr
Nombre de pages : 3
Voir plus Voir moins
Universit´edeNice D´epartementdeMath´ematiques
Ann´ee2007-2008 LicenceMI/SM1eann´ee
Analyse : notes du cours 4 Extrema d’une fonction de deux variables 1.Convexit´e: De´nition:enucnofdnOuqtiabivleontierd´x7→f(x) estconvexesur un intervalleI=]a, b[Rsi sa de´rive´eestcroissantesurI(etstrictement convexesi elle est strictement croissante). On dit qu’elle est 1 concavere´dasistseee´viroisd´ece(etsantstrictement concaveroecsaismeted´ntstsecirtiselletne.) 2 13 Ainsix7→xetx7→sont convexes surRet ]0,+[ respectivement. La fonctionx7→xn’est x ni convexe ni concave surRmais elle est convexe sur [0,+[ et concave sur ],0]. Notons qu’une fonctionfest concave si et seulement si la fonctionfest convexe. Voiciuneproprie´te´caracte´ristiquedelaconvexite´quenouspourronsge´n´eraliserauxfonctionsde deux variables. Proposition 1Une fonctionfseusuad-sphdeenrgir´aetu´estsieluesteiosistnemsteeblvaesexnvco detoutessestangentes,cest-a`-diresi,entoutpointx0, on a pour toutx: 0 f(x)f(x0) +f(x0)(xx0).(1) Cetteine´galite´quis´ecritaussif(x)L(x),o`uL(xs´rideeeilalae´ntse)fau pointx0, montre que lapproximationdunefonctionconvexeparsaline´aris´eeesttoujoursunesous-estimationdelavaleur exacte.Lastricteconvexit´ecorresponda`lameˆmede´nition,maisavecuneine´galit´estricte. Preuve :´vreevexeicnibein´eettet´e(galinosop,)1sruoPuorpqrevunuonefioctonncg(x) =f(x)L(x) 0 00 et montrons quegest une fonction positive ou nulle. On ag(x0) = 0 et d’autre partg(x) =f(x)f(x0). 0 00 00 Commefest croissante, on af(x)f(x0)0 sixx0etf(x)f(x0)0 sixx0. Donc la fonctiongourets´dceorsiastnpexx0et croissante pourxx0. Elle reste donc toujours positive. 0 Re´ciproquement,pourmontrerqueftsinpouxdensrotcroesdie´ocsntn,esiasx0etx1deItels que 0 0 x0x1et montrons quef(x0)f(x1e(t´au1)´einliga.)Lnioptx0est satisfaite si l’on prend pourxla valeurx1, 0 f(x1)f(x0) +f(x0)(x1x0) etlameˆmein´egalite´aupointx1cette fois est satisfaite si l’on prend pourxla valeurx0 0 f(x0)f(x1) +f(x1)(x0x1). f xf xf xf x 01 01 00 Ilenr´esultequedunepartf(x0)et d’autre partf(x1) (en se souvenant x1x0x1x0 0 0 quex0x1u`oD.)f(x0)f(x1).Lacaracte´risationpr´ec´edentesege´ne´ralisefacilementauxfonctionsdedeuxvariables: 2 D´enition:On dit qu’une fonction (x, y)7→f(x, yd)e´irblvaesetconvexeosisargneehpiststu´e au-dessusdetoussesplanstangents,cest-`a-diresientoutpoint(x0, y0), on a pour tout (x, y) : ∂f ∂f f(x, y)f(x0, y0() +x0, y0) (xx0() +x0, y0) (yy0) ∂x ∂y Ici encore laconvictestre´tixetresteicunetonefoitce´dnavirselberat´liga´einl`aradnopserrocconcavesi songrapheestsitue´en-dessousdetoussesplanstangents(cest-`a-direlorsquonauralameˆmeine´galite´ maisinverse´e).Anouveau,unefonctionfest concave lorsque la fonctionfest convexe. G´eom´etriquement,unefonctionconvexeaungraphehalersveutseottie´´teeirnedontncavlaco, comme 2 2 le bolf(x, y) =x+yelevsre´tiotseneiree´theapntdocolaavncitnooccnvaaenurgalorsquunefonc 2 2 bas comme le chapeauf(x, y) =9xy. Un planf(x, y) =ax+by+c`astecnvaeetalofsioc 2 2 convexe (mais pas strictement) et une sellef(x, y) =xyn’est ni concave ni convexe. 1 Enfait,lanotiondeconvexite´existeplusg´en´eralement,pourtoutefonctionde´rivableounon(voirparexemple http ://fr.wikipedia.org/wiki/fonction convexe) 2 On appelle iciableerivd´eillseC.e´seaptrtmieonntsaucasodnetsrfaoinrceqnoiopiufenutcnod´uxiver`essdede duneseulevariable,cetted´erivabilite´la`nentrainepasquelafonctionpuisseeˆtresusammentbienapproche´e parsaline´aris´ee.Pourquecesoitlecas,ilfaudrademandera`lafonctiondˆetred´eiailbertne(voir par exemple http://fr.wikipedia.org/wiki/diffe´rentielle).
1
2.Conditionsdoptimalite´dusecondordre On a vu que pour trouver les extrema d’une fonctionx7→f(xdestfa`aeeircereesoh,r)pal`ime rechercher ses points critiques. Parmi ces points critiques, certains sont l’argument d’un maximum local, d’autres l’argument d’un minimum local et d’autres ni l’un ni l’autre. Pour savoir dans quel cas l’on se trouve,ilsutenfaitdeconnaˆıtrelaconcavite´delafonction,cest-`a-diredesavoirdistinguersielleest convexe (c’est la cas d’un minimum) , concave (c’est le cas d’un maximum) ou ni l’un ni l’autre. Pour les 0 00 fonctionsdeuxfoisd´erivables,lacroissancestrictedefcorrespond au fait quef >cee0stdae´rciossna 00 strictea`f <:tnaviusere`tir0elI.e´rntluscele
Proposition2Conditiondoptimalite´dusecondordre:Soitx7→f(x)une fonction deux fois d´erivablesur]a, b[et soitcun point de]a, b[: 0 00 – sif(c) = 0etf(c)>0alorscest un minimum local def. 0 00 – sif(c) = 0etf(c)<0alorscest un maximum local def.
Le corollaire suivant est souvent utile dans les applications :
Corollaire 3Si une fonction strictement convexef:]a, b[7→Rpec,euqitsetnioeunps`edcritointpso l’argument de son minimum global et il est unique.
Danslecasdesfonctionsdedeuxvariables,cestunequantit´eappele´eleetmrde´ensiestHanin, qui se 00 calculefacilement`apartirdesd´eriv´eespartiellessecondes,quivajouerlerˆoledelade´rive´esecondef. Maisauparavante´tendonsauxfonctionsdedeuxvariableslesd´enitionsdextre´malocauxetglobaux. 2 D´enition:On dit qu’une fonctionf(x, yemainodnuruseine´d)D ⊆Rs`edposuenmaximum local ∗ ∗∗ ∗∗ ∗ au point (x ,y)∈ Ds’il existe un rectangleI×J=]xε, x+ε[×]xδ, x+δ[ contenu dansD ∗ ∗ sur lequelf(x, y)f(x ,yint(utpoentoaiteligaeet´sastsftie)cistettee´nix, y)∈ Dil s’agit d’un maximum globalugpeuorionanaloed´enitnutnemmedive´anO.minimum localetminimum global.
Proposition4Conditiondoptimalite´dusecondordre:Soit(x, y)7→f(x, y)une fonction deux 0 0 foisde´rivablesurdomaineouvertD=]a, b[×]a , b[coseeslliertpaeseunitnoctnossednsdontles4d´eriv´e et soit(xc, yc)un point deD. Soit  2 2 22 ∂ f∂ f∂ f D=D(x, y) =(x, y) (x, y)(x, y). 2 2 ∂x ∂y∂x∂y
2 – SiGradf(xc, yc) = 0etD(xc, yc)>0avec2(xc, yc)>0alors(xc, yc)est un minimum local de ∂x la fonctionf. 2 ∂ f – SiGradf(xc, yc) = 0etD(xc, yc)>0avec2(xc, yc)<0alors(xc, yc)est un maximum local de ∂x la fonctionf.
3.D´eterminationdesextremaglobauxparlam´ethode`atroise´tapes.Comme pour les fonctions dunevariables,ondisposedunem´ethodesimplepourtrouverlaplusgrandeetlapluspetitevaleur d’une fonction (x, y)7→f(x, ylbleiravd)e´inedomaueleorsqDctanglerlsuueeqeelleell´dtsinetseeernu 3 (avecsonbord),unpolygoˆne(avecsonbord)ouplusge´n´eralementundomaineborn´ede´nipardes in´egalite´slargesportantsurdespolynoˆmes.Pourlocalisercesdeuxextre´maglobaux,ilsuteneetde proc´ederentroise´tapes: 1. Trouvertous les points critiques defopni(lugest`odereluclacruelavalteendiraetl)nustfen ces points. 2. Trouverles extrema defrobudtnemgeseuqad,serncirtnoithca`ursbole(erdfest une fonction duneseulevariablea`laquelleonpeutappliquerlam´ethode`atroise´tapes). 3.Laplusgrandeetlapluspetitevaleurstrouv´eesauxdeuxe´tapespr´ec´edentessontlesextrema cherche´s.
2 3 Une partie deRest diteeobe´nrndraec)rngta[lesilexisteun(possbielemtnrte`gsM, M]×[M, M] qui la contient.
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.