Wykład 3, Informatyka Magisterskie SGGW, Teoria Informacji TI, Egzamin

//-->.pos {position:absolute; z-index: 0; left: 0px; top: 0px;}Teoria informacji, 14. 03.2013Mp1,p2, . . . ,pMq1,q2, . . . ,qMM∑pi=1i=1M∑qi=1i=1−∑pilogpii=1−∑pilogqii=1MMqi=1M−∑pilogpii=1MM1−∑pilogM=logMi=1H(X)=−∑pilogpii=1M LH(X,Y) =∑ ∑pi jlogpi ji=1 j=1˙3. Niepewno´c zwiazana z wi˛ cej niz jedna zmienna losowas´˛e˛˛˛˙Załozenie: Mamy dwie zmienne losoweX, Yzwiazane z tym samym do´wiadczeniem.XiYmaja rozkład łacznego prawdopo-˛s˛˛ ˛dobie´ stwa opisany funkcjan˛p(xi,yj) =pi j=P(X=xi,Y=yj) (i =1,. . . ,M; j=1,. . . ,L)˙W do´wiadczeniu mamyM·Lmozliwych zdarze´ , zdarzenie{X=xi,Y=yj}ma prawdopodobie´ stwop(xi,yj).Definiujemy łacznesnn˛niepewno´ciXiYjakosMLH(X,Y) =∑ ∑p(xi,yj)logp(xi,yj)i=1 j=1X1,X2, . . . ,XnH(X,Y) =−4.X\Yx1x2...xMP(Y)y1p11p21...pM1p1Lj=1Mx1,x2,...,xn∑p(x1,x2, . . . ,xn)logp(x1,x2, . . . ,xn).........pi j......yLp1Lp2L...pMLpLP(X)p1p2...pM1y2p12p22...pM2p2p(xi) =∑p(xi,yj)p(yj) =∑p(xi,yj)i=1H(X)=−∑p(xi)logp(xi) =−∑ ∑p(xi,yj)logp(xi)H(Y) =−∑p(yj)logp(yj) =−∑ ∑p(xi,yj)logp(yj)j=1MLj=1 i=1i=1Li=1 j=1L MMMLH(X)+H(Y) =−∑ ∑p(xi,yj)logqi j,i=1 j=1qi j=p(xi)p(yj)Z lematu−∑ ∑pi jlogpi ji=1 j=1ML−∑ ∑pi jlogqi ji=1 j=1LMLSprawdzenie∑ ∑qi j=∑p(xi)∑p(yj) =1·1=1i=1 j=1i=1j=1MLMTwierdzenie˙H(X,Y)H(X)+H(Y),gdzie równo´c wyst˛ puje wtedy i tylko wtedy, gdyXiYsa niezalezne,p(xi,yj) =p(xi)p(yj)s´e˛5. Niepewno´c warunkowas´Mamy dwie zmienne losoweXiY.˙˙Załózmy zeX=xi, wówczasYjest scharakteryzowane zbiorem prawdopodobie´ stw warunkowychp(yj|xi) (j=1,. . . ,L)n1˙Def.Warunkowa niepewno´cYdla kazdegoX=xi:H(Y|X=xi) =−∑p(yj|xi)logp(yj|xi)s´j=1L˙˙´Def.Warunkowa niepewno´cYdla kazdegoX,jako srednia wazona niepewno´ciH(Y|X=xi)s´sH(Y|X)=p(x1)H(Y|X=x1) +· · ·+p(xM)H(Y|X=xM) =−∑p(xi)∑p(yj|xi)logp(yj|xi)i=1j=1MLAlep(xi,yj) =p(xi)p(yj|xi)wi˛ ceH(Y|X)=−∑ ∑p(xi,yj)logp(yj|xi)i=1 j=1ML5.1 Wła´ciwo´ci niepewno´ci warunkowejsss1. Mamy dwie zmienne losoweXiY. Ujawniamy warto´cX.Pozostała niepewno´c zwiazana zYpowinna wynie´cH(Y|X)s´s´˛s´TwierdzenieH(X,Y) =H(X)+H(Y|X)=H(Y) +H(X|Y)p(x, y)=p(x)p(y|x)=p(y)p(x|y)Dowód.H(X,Y) =−∑ ∑p(xi,yj)logp(xi,yj) =−∑ ∑p(xi,yj)log[p(xi)p(yj|xi)] =−∑ ∑p(xi,yj)logp(xi)−∑ ∑p(xi,yj)logp(yj|xi) =i=1 j=1i=1 j=1MM L−∑p(xi)logp(xi)−∑ ∑p(xi,yj)logp(yj|xi) =H(X)+H(Y|X)i=1i=1 j=1i=1 j=1i=1 j=1MLMLMLML(H(Y ) +H(X|Y))˙2.TwierdzenieH(Y|X)H(Y)znak równo´ci wyst˛ puje wtedy i tylko wtedy, gdyXi Ysa niezaleznese˛DowódPoprzednio mieli´mysH(X,Y)H(X)+H(Y)H(X,Y) =H(X)+H(Y|X)H(X)+H(Y|X)H(X)+H(X)H(Y|X)H(Y)PrzykładMiara InformacjiMamy dwie monety, normalna (orzeł i reszka) i nienormalna (dwie reszki). Losowo wybieramy jedna, rzucamy dwa razy i˛˛˛˙notujemy liczb˛ reszek. Pytanie: Jak duzo informacji o tym, która moneta została wybrana, wynika z liczby wyrzuconych reszek?eB˛ dziemy mierzyli uzyskana informacj˛ redukcja niepewno´ci.e˛e˛sWprowadzamy dwie zmienne losoweX- wybór monety { nor, nie},Y- liczba wyrzuconych reszek w dwóch rzutach { 0,1,2}p(i)=npi(1−p)n−ii1p=2- prawodopodobie´ stwo wyrzucenia reszkinn=2 - liczba prób1p(0)=2(1)(1)2=40 221p(1)=2(1)1(1)1=21 221p(2)=2(1)2(1)=42 22p(x, y)=p(y|x)p(x)=p(x|y)p(y)p(y|x)=∑p(x|y)p(y)p(x|y)p(y)yX\Ynornie14112214∑y1112P(X,Y)X\Y 0 1 2111nor848nie0 012P(Y)1 1 5848p(x, y)=p(y|x)p(x)P(X|Y)X\Y 0 1 2nor1 115nie0 0451 1 1∑xP(X)12121p(x|y)=p(x,y)p(y)3

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

kachorra.htw.pl