Théorie de l'information et codage

Marc Lelarge

Description

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 ∑

Sujets

• maths
• cours

Informations

• Publié par: pefav
• Publié le: 01 mars 2011
• Nombre de lectures: 61
• Langue: Français

Extrait

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´finition:enu’cnofdnOuqtiabivleontierd´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 1 3 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 fonction−fest convexe. Voiciuneproprie´te´caracte´ristiquedelaconvexite´quenouspourronsge´n´eraliserauxfonctionsde deux variables. Proposition 1Une fonctionfseusuad-sphdeenrgir´aetu´estsieluesteiosistnemsteeblvaesexnvco detoutessestangentes,c’est-a`-diresi,entoutpointx 0 , on a pour toutx: 0 f(x)≥f(x 0 ) +f(x 0 )(x−x 0 ).(1) Cetteine´galite´quis’´ecritaussif(x)≥L(x),o`uL(xs´rideeeilalae´ntse)fau pointx 0 , montre que l’approximationd’unefonctionconvexeparsaline´aris´eeesttoujoursunesous-estimationdelavaleur exacte.Lastricteconvexit´ecorresponda`lameˆmede´finition,maisavecuneine´galit´estricte. Preuve :´vreevexeicnfiibein´eettet´e(galinosop,)1sruoPuorpqrevunu’onefioctonncg(x) =f(x)−L(x) 0 00 et montrons quegest une fonction positive ou nulle. On ag(x 0 ) = 0 et d’autre partg(x) =f(x)−f(x 0 ). 0 00 00 Commefest croissante, on af(x)−f(x 0 )≤0 six≤x 0 etf(x)−f(x 0 )≥0 six≥x 0 . Donc la fonctiongourets´dceorsiastnpex≤x 0 et croissante pourx≥x 0 . Elle reste donc toujours positive. 0 Re´ciproquement,pourmontrerqueftsinpouxdensrotcroesdie´ocsntn,esiasx 0 etx 1 deItels que 0 0 x 0 ≤x 1 et montrons quef(x 0 )≤f(x 1 e(t´au1)´einliga.)’Lnioptx 0 est satisfaite si l’on prend pourxla valeurx 1 , 0 f(x 1 )≥f(x 0 ) +f(x 0 )(x 1 −x 0 ) etlameˆmein´egalite´aupointx 1 cette fois est satisfaite si l’on prend pourxla valeurx 0 0 f(x 0 )≥f(x 1 ) +f(x 1 )(x 0 −x 1 ). f x−f xf x−f x 0 1 01 0 0 Ilenr´esultequed’unepartf(x 0 )≤et d’autre part≤f(x 1 ) (en se souvenant x 1 −x 0 x 1 −x 0 0 0 quex 0 ≤x 1 u`o’D.)f(x 0 )≤f(x 1 ).✷ Lacaracte´risationpr´ec´edentesege´ne´ralisefacilementauxfonctionsdedeuxvariables: 2 D´efinition:On dit qu’une fonction (x, y)7→f(x, yd)e´irblvaesetconvexeosisargneehpiststu´e au-dessusdetoussesplanstangents,c’est-`a-diresientoutpoint(x 0 , y 0 ), on a pour tout (x, y) : ∂f ∂f f(x, y)≥f(x 0 , y 0 () +x 0 , y 0 ) (x−x 0 () +x 0 , y 0 ) (y−y 0 ) ∂x ∂y Ici encore laconvictestre´tixetresteicunetonefoitce´dnavirselberat´liga´einl’`aradnopserrocconcavesi songrapheestsitue´en-dessousdetoussesplanstangents(c’est-`a-direlorsqu’onauralameˆmeine´galite´ maisinverse´e).Anouveau,unefonctionfest concave lorsque la fonction−fest convexe. G´eom´etriquement,unefonctionconvexeaungraphehalersveutseottie´´teeirnedontncavlaco, comme 2 2 le bolf(x, y) =x+yelevsre´tiotseneiree´theapntdocolaavncitnooccnvaaenurgalorsqu’unefonc 2 2 bas comme le chapeauf(x, y) =9−x−y. Un planf(x, y) =ax+by+c`astecnvaeetalofsioc 2 2 convexe (mais pas strictement) et une sellef(x, y) =x−yn’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 d’uneseulevariable,cetted´erivabilite´la`n’entrainepasquelafonctionpuisseeˆtresuffisammentbienapproche´e parsaline´aris´ee.Pourquecesoitlecas,ilfaudrademandera`lafonctiond’ˆetred´eiffailbertne(voir par exemple http://fr.wikipedia.org/wiki/diffe´rentielle).

1