Chapter 2: Entropy and Mutual Information - UIC

1 University of Illinois at Chicago ECE 534, Fall 2009, Natasha DevroyeUniversity of Illinois at Chicago ECE 534, Fall 2009, Natasha DevroyeChapter 2: Entropy and Mutual InformationUniversity of Illinois at Chicago ECE 534, Fall 2009, Natasha DevroyeChapter 2 outline Definitions Entropy Joint Entropy , conditional Entropy Relative Entropy , Mutual Information Chain rules Jensen s inequality Log-sum inequality Data processing inequality Fano s inequalityUniversity of Illinois at Chicago ECE 534, Fall 2009, Natasha DevroyeDefinitionsA discrete random variableXtakes on valuesxfrom the discrete probability mass function (pmf) is described bypX(x)=p(x) = Pr{X=x},forx of Illinois at Chicago ECE 534, Fall 2009, Natasha DevroyeDefinitionsCopyright Cambridge University Press 2003.

2 On-screen viewing permitted. Printing not permitted. can buy this book for 30 pounds or $50. See for , Entropy ,andInferenceThischapter,anditss ibling,Chapter8, ,thenameofthesong,andwhatthenameoftheson gwascalled(Carroll,1998),wewillsometimes needtobecarefultodistinguishbetweenarand omvariable,thevalueoftherandomvariable, ,however,Iwillusethemostsimpleandfriendl ynotationpossible, ,ifsomethingis truewithprobability1 ,Iwillusuallysimplysaythatitis true . (x,AX,PX),wheretheoutcomexisthevalueofar andomvariable,whichtakesononeofasetofpos siblevalues,AX={a1,a2,..,ai,..,aI},havin gprobabilitiesPX={p1,p2,..,pI},withP(x=a i)=pi,pi 0and ai AXP(x=ai)= alphabet . :a z,andaspacecharacter - . (estimatedfromTheFrequentlyAskedQuestion sManualforLinux).

3 ,P(x=ai)maybewrittenasP(ai)orP(x). :P(T)=P(x T)= ai TP(x=ai).( )Forexample, ,V={a,e,i,o,u},thenP(V)= + + + + ( )AjointensembleXYisanensembleinwhicheach outcomeisanorderedpairx,ywithx AX={a1,..,aI}andy AY={b1,..,bJ}.WecallP(x,y) ,soxy x, Cambridge University Press 2003. On-screen viewing permitted. Printing not permitted. can buy this book for 30 pounds or $50. See for :Probabilitiesandensembles23abcdefghijkl mnopqrstuvwxyz yabcdefghijklmnopqrstuvwxyz 27possiblebigramsxyinanEnglishlanguagedo cument, (x)fromthejointprobabilityP(x,y)bysummat ion:P(x=ai) y AYP(x=ai,y).( )Similarly,usingbriefernotation,themargi nalprobabilityofyis:P(y) x AXP(x,y).( )ConditionalprobabilityP(x=ai|y=bj) P(x=ai,y=bj)P(y=bj)ifP(y=bj)"=0.

4 ( )[IfP(y=bj)=0thenP(x=ai|y=bj)isundefined .]WepronounceP(x=ai|y=bj) theprobabilitythatxequalsai,givenyequals bj . ,ab,ac,andzz;ofthese, ,P(x)andP(y), (x,y)wecanobtainconditionaldistributions ,P(y|x)andP(x|y),bynormalizingtherowsand columns,respectively( ).TheprobabilityP(y|x=q) ,thetwomostprobablevaluesforthesecondlet terygivenUniversity of Illinois at Chicago ECE 534, Fall 2009, Natasha DevroyeDefinitionsThe eventsX=xandY=yarestatistically independentifp(x,y)=p(x)p(y).The variablesX1,X2, XNare calledindependentif for all (x1,x2, ,xN) X1 X2 XNwe havep(x1,x2, xN)=N i=1pXi(xi).They are furthermore called identically distributed if all variablesXihave the samedistributionpX(x).University of Illinois at Chicago ECE 534, Fall 2009, Natasha DevroyeEntropy Intuitive notions?

5 2 ways of defining Entropy of a random variable: axiomatic definition (want a measure with certain ) just define and then justify definition by showing it arises as answer to a number of natural questionsDefinition:The entropyH(X) of a discrete random variableXwith pmfpX(x) isgiven byH(X)= xpX(x) logpX(x)= EpX(x)[logpX(X)]University of Illinois at Chicago ECE 534, Fall 2009, Natasha DevroyeOrder these in terms of entropyUniversity of Illinois at Chicago ECE 534, Fall 2009, Natasha DevroyeOrder these in terms of entropyUniversity of Illinois at Chicago ECE 534, Fall 2009, Natasha DevroyeEntropy examples 1 What s the Entropy of a uniform discrete random variable taking on K values? What s the Entropy of a random variable with What s the Entropy of a deterministic random variable?

6 X=[ , , , ],pX= [1/2; 1/4; 1/8; 1/8]!University of Illinois at Chicago ECE 534, Fall 2009, Natasha DevroyeEntropy: example 2 Copyright Cambridge University Press 2003. On-screen viewing permitted. Printing not permitted. can buy this book for 30 pounds or $50. See for Probability, Entropy ,andInferenceWhatdoyo unoticeaboutyoursolutions?Doeseachanswer dependonthedetailedcontentsofeachurn? (here,thattheballdrawnwasblack) , , :givenagenerativemodelfordatadgivenparam eters ,P(d| ),andhavingobservedaparticularoutcomed1, allinferencesandpredictionsshoulddependo nlyonthefunctionP(d1| ).Inspiteofthesimplicityofthisprinciple, (x)=log21P(x).( )Itismeasuredinbits.[Theword bit isalsousedtodenoteavariablewhosevalueis0 or1;Ihopecontextwillalwaysmakeclearwhich ofthetwomeaningsisintended.]

7 ]Inthenextfewchapters,wewillestablishtha ttheShannoninformationcontenth(ai)isinde edanaturalmeasureoftheinformationcontent oftheeventx= ,wewillshortenthenameofthisquantityto theinformationcontent .iaipih(pi) ,andx= :H(X) x AXP(x)log1P(x),( )withtheconventionforP(x)=0that0 log1/0 0,sincelim 0+ log1/ = , ,wemayalsowriteH(X)asH(p),wherepisthevec tor(p1,p2,..,pI). , (showninthefourthcol-umn)undertheprobabi litydistributionpi(showninthethirdcolumn ).Copyright Cambridge University Press 2003. On-screen viewing permitted. Printing not permitted. can buy this book for 30 pounds or $50. See for Probability, Entropy ,andInferenceWhatdoyo unoticeaboutyoursolutions?Doeseachanswer dependonthedetailedcontentsofeachurn? (here,thattheballdrawnwasblack) , , :givenagenerativemodelfordatadgivenparam eters ,P(d| ),andhavingobservedaparticularoutcomed1, allinferencesandpredictionsshoulddependo nlyonthefunctionP(d1| ).

8 Inspiteofthesimplicityofthisprinciple, (x)=log21P(x).( )Itismeasuredinbits.[Theword bit isalsousedtodenoteavariablewhosevalueis0 or1;Ihopecontextwillalwaysmakeclearwhich ofthetwomeaningsisintended.]Inthenextfew chapters,wewillestablishthattheShannonin formationcontenth(ai)isindeedanaturalmea sureoftheinformationcontentoftheeventx= ,wewillshortenthenameofthisquantityto theinformationcontent .iaipih(pi) ,andx= :H(X) x AXP(x)log1P(x),( )withtheconventionforP(x)=0that0 log1/0 0,sincelim 0+ log1/ = , ,wemayalsowriteH(X)asH(p),wherepisthevec tor(p1,p2,..,pI). , (showninthefourthcol-umn)undertheprobabi litydistributionpi(showninthethirdcolumn ).University of Illinois at Chicago ECE 534, Fall 2009, Natasha DevroyeEntropy: example 3 Bernoulli random variable takes on heads (0) with probability p and tails with probability 1-p.

9 Its Entropy is defined as H(p) := plog2(p) (1 p) log2(1 p)16 Entropy , RELATIVE Entropy , AND Mutual (p)FIGURE (p) that we wish to determine the value ofXwith the minimumnumber of binary questions. An efficient first question is IsX=a? This splits the probability in half. If the answer to the first question isno, the second question can be IsX=b? The third question can be IsX=c? The resulting expected number of binary questions requiredis This turns out to be the minimum expected number of binaryquestions required to determine the value ofX. In Chapter 5 we show thatthe minimum expected number of binary questions required to determineXlies betweenH(X)andH(X)+ JOINT Entropy AND CONDITIONAL ENTROPYWe defined the Entropy of a single random variable in Section Wenow extend the definition to a pair of random variables.

10 There is nothingreally new in this definition because(X,Y)can be considered to be asingle vector-valued random entropyH(X,Y)of a pair of discrete randomvariables(X,Y)with a joint distributionp(x,y)is defined asH(X,Y)= x X y Yp(x,y)logp(x,y),( )University of Illinois at Chicago ECE 534, Fall 2009, Natasha DevroyeEntropyThe entropyH(X)= xp(x) logp(x) has the following properties: H(X) 0, Entropy is always (X) = 0 iffXis deterministic(0 log(0) = 0). H(X) log(|X|).H(X)=log(|X|)iffXhas uniform distribution overX. SinceHb(X) = logb(a)Ha(X), we don t need to specify the base of the loga-rithm (bits vs. nat).Moving on to multiple RVsUniversity of Illinois at Chicago ECE 534, Fall 2009, Natasha DevroyeJoint Entropy and conditional entropyDefinition:Joint Entropy of a pair of two discrete random variablesXandYis:H(X,Y) := Ep(x,y)[logp(X,Y)]= x X y Yp(x,y) logp(x,y)Note:H(X|Y)!