IT6 (Полный комплект лекций Г.А. Дьячкова), страница 3
Описание файла
Файл "IT6" внутри архива находится в папке "Полный комплект лекций Г.А. Дьячкова". PDF-файл из архива "Полный комплект лекций Г.А. Дьячкова", который расположен в категории "". Всё это находится в предмете "теория информации" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 3 страницы из PDF
ðÒÅÖÄÅ ÞÅÍ ÏÃÅÎÉ×ÁÔØ PN(2) , ÚÁÍÅÔÉÍ, ÞÔÏ × ÓÉÌÕ (25 ×) ÍÁÔÅÍÁÔÉÞÅÓËÏÅ ÏÖÉÄÁÎÉÅn0 =Xk;jP (j |k)Q(k)Q~ (j ) ln ~Q(j )≤Xk;j·¸P (j |k)Q(k)Q~ (j ) ~− 1 = 0; n = 1; N;Q(j )ÇÄÅ ÄÌÑ ÏÃÅÎËÉ (39) ÐÒÉÍÅÎÉÌÉ ÎÅÒÁ×ÅÎÓÔ×Ï ln x ≤ x − 1. ðÏÜÔÏÍÕ ÄÌÑ ÌÀÂÏÇÏ TÌÀÂÏÇÏ h~ ≥ 0, × ÓÉÌÕ (25) É ÕÔ×ÅÒÖÄÅÎÉÑ 1) ÌÅÍÍÙ 3, ÞÉÓÌÏ(39)≥(2)~ − ~(h~ ))};PN ≤ exp{−N (hTÇÄÅhP~(h~ ) = ln= lnhP0É(40)i~ P (j |k)~k;j Q(k )Q(j ) exp{h ln Q~ (j ) } =i~ 1−h~ P (j |k)h~ ; h~ > 0:k;j Q(k )Q(j )(41)ðÕÓÔØ 0 ≤ h~ ≤ 1 É −1 ≤ h ≤ 0. éÚ (41) ×ÙÔÅËÁÅÔ, ÞÔÏ ÐÏÓÌÅ ÚÁÍÅÎÙ ÐÅÒÅÍÅÎÎÏÊ h~ = 1+ hÍÏÖÎÏ ÎÁÐÉÓÁÔØ~ − ~(h~ ) = T + hT − Q (h);hT(42)ÇÄÅ Q (h), −1 ≤ h ≤ 0, ÏÐÒÅÄÅÌÅÎÏ (34).
ðÏÄÓÔÁ×É× (42) × (40) É ÕÞÉÔÙ×ÁÑ (38), ÐÏÌÕÞÉÍ,ÞÔÏ ÄÌÑ ÌÀÂÏÇÏ T , 0 < T < J (Q), É ÌÀÂÏÇÏ h, −1 ≤ h ≤ 0, ÏÄÎÏ×ÒÅÍÅÎÎÏ ×ÙÐÏÌÎÑÀÔÓÑ Ä×ÁÎÅÒÁ×ÅÎÓÔ×Á(1)PN ≤ exp{−N (hT − Q (h))};(43)(2)PN ≤ exp{−N (T + hT − Q (h))}:éÚ (43) ×ÙÔÅËÁÅÔ ÕÔ×ÅÒÖÄÅÎÉÅ 1) ÌÅÍÍÙ 8.2) ó×ÏÊÓÔ×Ï ÆÕÎËÃÉÉ EQ (T ), ÓÆÏÒÍÕÌÉÒÏ×ÁÎÎÙÅ × ÕÔ×ÅÒÖÄÅÎÉÉ 2) ÌÅÍÍÙ 8, Ñ×ÌÑÀÔÓÑÏÞÅ×ÉÄÎÙÍ ÓÌÅÄÓÔ×ÉÅÍ ÌÅÍÍÙ 7.ìÅÍÍÁ 8 ÄÏËÁÚÁÎÁ.éÚ ÌÅÍÍÙ 2 (ÓÍ. ÎÅÒÁ×ÅÎÓÔ×Ï (23)), ÌÅÍÍÙ 8 É ÎÅÒÁ×ÅÎÓÔ×Á M − 1 ≤ exp{RN } ×ÙÔÅËÁÅÔ ÜËÓÐÏÎÅÎÃÉÁÌØÎÁÑ ×ÅÒÈÎÑÑ ÇÒÁÎÉÃÁ ×ÅÒÏÑÔÎÏÓÔÉ ÏÛÉÂËÉ ÐÏÒÏÇÏ×ÏÇÏ ÄÅËÏÄÉÒÏ×ÁÎÉÑ,ËÏÔÏÒÕÀ ÄÁÅÔôÅÏÒÅÍÁ 3.
åÓÌÉ 0 < R < J(Q; P), ÔÏ ÄÌÑ äëâð (1) ÓÕÝÅÓÔ×ÕÅÔ (N; R){ËÏÄ X ,ÔÁËÏÊ ÞÔÏ ÐÒÉ ÄÅËÏÄÉÒÏ×ÁÎÉÉ Ó ÐÏÒÏÇÏÍ T , R≤T < J(Q; P), ÄÌÑ ÓÒÅÄÎÅÊ ×ÅÒÏÑÔÎÏÓÔÉÏÛÉÂËÉ P (X ) ÓÐÒÁ×ÅÄÌÉ×Á ÜËÓÐÏÎÅÎÃÉÁÌØÎÏ ÕÂÙ×ÁÀÝÁÑ Ó ÒÏÓÔÏÍ N ×ÅÒÈÎÑÑ ÇÒÁÎÉÃÁP (X ) ≤ exp{−NEQ (T )} + exp{−N [EQ (T ) + T − R]}:ðÕÓÔØ C | ÐÒÏÐÕÓËÎÁÑ ÓÐÏÓÏÂÎÏÓÔØ äëâð (1) É ÒÁÓÐÒÅÄÅÌÅÎÉÅ Q ÓÏ×ÐÁÄÁÅÔ Ó ÔÅÍÒ.×., ÎÁ ËÏÔÏÒÏÍ ÄÏÓÔÉÇÁÅÔÓÑ ÍÁËÓÉÍÕÍ × ÏÐÒÅÄÅÌÅÎÉÉ (11) ÐÒÏÐÕÓËÎÏÊ ÓÐÏÓÏÂÎÏÓÔÉ C , Ô.Å.13J(Q; P) = C . åÓÌÉ ×ÙÂÒÁÔØ ÐÏÒÏÇ T = R < C , ÔÏ ÉÚ ÔÅÏÒÅÍÙ 3 ×ÙÔÅËÁÅÔ ×ÅÒÈÎÑÑ ÇÒÁÎÉÃÁÄÌÑ EN (P; R) | ÓÒÅÄÎÅÊ ×ÅÒÏÑÔÎÏÓÔÉ ÏÛÉÂËÉ ÏÐÔÉÍÁÌØÎÏÇÏ (ÎÁÉÌÕÞÛÅÇÏ) (N; R){ËÏÄÁ.ôÅÏÒÅÍÁ 4.
äÌÑ ÌÀÂÏÇÏ R, 0 < R ≤ C ,EN (P; R) ≤ 2 exp{−NEQ (R)};ÇÄÅ ÐÏËÁÚÁÔÅÌØ ÜËÓÐÏÎÅÎÔÙ EQ (R) ÏÐÒÅÄÅÌÑÅÔÓÑ ÓÏÏÔÎÏÛÅÎÉÑÍÉ (34) É (37) ÐÒÉ T = R.ðÒÉ 0 < R < C ÆÕÎËÃÉÑ EQ (R) > 0 ÍÏÎÏÔÏÎÎÏ ÕÂÙ×ÁÅÔ, ×ÙÐÕËÌÁ ×ÎÉÚ É EQ (C ) = 0.6.4 ÷ÙÐÕËÌÏÓÔØ ÉÎÆÏÒÍÁÃÉÏÎÎÏÊ ÆÕÎËÃÉÉ÷ ÜÔÏÍ ÒÁÚÄÅÌÅ ÍÙ ÐÏËÁÖÅÍ, ÞÔÏ ÏÐÒÅÄÅÌÅÎÎÁÑ ÆÏÒÍÕÌÏÊ (10) ÉÎÆÏÒÍÁÃÉÏÎÎÁÑ ÆÕÎËÃÉÑJ(Q; W) =K−1 J−1XXx=0 y=0Q(x)·W (y|x)· log K −1Pk=0W (y|x)(44)Q(k)·W (y|k)Ñ×ÌÑÅÔÓÑ ×ÙÐÕËÌÏÊ ××ÅÒÈ ÆÕÎËÃÉÅÊ ÁÒÇÕÍÅÎÔÁ Q = {Q(x); x = 0; K − 1} É ×ÙÐÕËÌÏÊ ×ÎÉÚÆÕÎËÃÉÅÊ ÁÒÇÕÍÅÎÔÁ W = {W (y|x); x = 0; K − 1; y = 0; J − 1}. ÷ÙÐÕËÌÏÓÔØ ××ÅÒÈ ÉÍÅÅÔÓÕÝÅÓÔ×ÅÎÎÏÅ ÚÎÁÞÅÎÉÅ ÄÌÑ ÍÁËÓÉÍÉÚÁÃÉÉ ÉÎÆÏÒÍÁÃÉÏÎÎÏÊ ÆÕÎËÃÉÉ ÐÏ Q ÐÒÉ ×ÙÞÉÓÌÅÎÉÉ ÐÒÏÐÕÓËÎÏÊ ÓÐÏÓÏÂÎÏÓÔÉ, Á ×ÙÐÕËÌÏÓÔØ ×ÎÉÚ | ÄÌÑ ÍÉÎÉÍÉÚÁÃÉÉ ÉÎÆÏÒÍÁÃÉÏÎÎÏÊÆÕÎËÃÉÉ ÐÏ W ÐÒÉ ×ÙÞÉÓÌÅÎÉÉ "{ÜÎÔÒÏÐÉÉ.6.4.1 ÷ÙÐÕËÌÏÓÔØ ××ÅÒÈ ÐÏ QðÕÓÔØ q = (q(z ); z = 0; 1) | ÐÒÏÉÚ×ÏÌØÎÏÅ Ò.×.
ÎÁ {0; 1}. úÁÆÉËÓÉÒÕÅÍ Ä×Á ÐÒÏÉÚ×ÏÌØÎÙÈÒ.×. ÎÁ {0; 1; : : : ; K − 1}:Q0 = {Q(x|0); x = 0; K − 1};Q1 = {Q(x|1); x = 0; K − 1}É ÏÂÏÚÎÁÞÉÍ ÞÅÒÅÚ(Q = q(0)Q0 + q(1)Q1 =Q(x) : Q(x) =1Xz =0)q(z )Q(x|z ); x = 0; K − 1ÓÍÅÓØ ÜÔÉÈ ÒÁÓÐÒÅÄÅÌÅÎÉÊ. ÷ÙÐÕËÌÏÓÔØ ××ÅÒÈ ÉÎÆÏÒÍÁÃÉÏÎÎÏÊ ÆÕÎËÃÉÉ ÐÏ ÁÒÇÕÍÅÎÔÕ QÏÚÎÁÞÁÅÔ, ÞÔÏJ(Q; W) ≥ q(0) J(Q0 ; W) + q(1) J(Q1 ; W):(45)äÌÑ ÄÏËÁÚÁÔÅÌØÓÔ×Á (45) ÒÁÓÓÍÏÔÒÉÍ ÔÒÏÊËÕ ÓÌÕÞÁÊÎÙÈ ×ÅÌÉÞÉÎ (Z; X; Y ) Ó Ò.×.p(z; x; y) = q(z )Q(x|z )W (y|x);(46)ËÏÔÏÒÏÅ ÏÐÒÅÄÅÌÅÎÏ ÎÁ ÔÒÏÊËÁÈ (z; x; y), z = 0; 1, x = 0; K − 1, y = 0; J − 1. ïÔÍÅÔÉÍÓÌÅÄÕÀÝÉÅ ÔÒÉ ÏÞÅ×ÉÄÎÙÅ Ó×ÏÊÓÔ×Á Ò.×. (46):1. ÕÓÌÏ×ÎÏÅ Ò.×.
p(y|x; z ) = p(y|x) = W (y|x), Ô.Å. ÔÒÏÊËÁ (Z; X; Y ) | ÃÅÐØ íÁÒËÏ×Á;142. ÍÁÒÇÉÎÁÌØÎÏÅ Ò.×. p(x) ÓÏ×ÐÁÄÁÅÔ Ó Q(x), ÔÁË ËÁËp(x) =Xz;yp(z; x; y) =Xzq(z )Q(x|z ) = Q(x);3. ÐÒÉ ÆÉËÓÉÒÏ×ÁÎÎÏÍ z = 0; 1 ÕÓÌÏ×ÎÏÅ Ò.×. p(x; y|z ) Ñ×ÌÑÅÔÓÑ Ò.×. ÎÁ ÐÁÒÁÈ (x; y) ÓÍÁÒÇÉÎÁÌØÎÙÍ Ò.×.p(y|z ) =Xxp(x; y|z ) =XxQ(x|z )W (y|x):éÚ 1) É 2) ÓÌÅÄÕÅÔ, ÞÔÏ ÄÌÑ ÐÁÒÙ ÓÌÕÞÁÊÎÙÈ ×ÅÌÉÞÉÎ (X; Y ) ÉÎÆÏÒÍÁÃÉÑJ (X; Y ) = J(Q; W):(47)éÚ 1) É 3) ÓÌÅÄÕÅÔ, ÞÔÏ ÐÒÉ ÆÉËÓÉÒÏ×ÁÎÎÏÍ z = 0; 1 ÄÌÑ ÉÎÆÏÒÍÁÃÉÉ Iz Ò.×. p(x; y|z ) ÉÍÅÅÍIz ==Px;yPx;y)p(x; y|z ) log PP((yy|xz|z ) =(y|x)Q(x|z )W (y|x) log P QW(k|z )W (y|k) = J(Qz ; W):(48)käÌÑ Ò.×.
(46) ÕÓÌÏ×ÎÁÑ ÉÎÆÏÒÍÁÃÉÑJ (X ; Y |Z ) =1Xz =0q(z )Iz :ðÏÜÔÏÍÕ (48) ÏÚÎÁÞÁÅÔ, ÞÔÏ ÄÌÑ Ò.×. (46) ÕÓÌÏ×ÎÁÑ ÉÎÆÏÒÍÁÃÉÑJ (X ; Y |Z ) =1Xz =0q(z )J(Qz ; W):(49)ðÏÓËÏÌØËÕ ÄÌÑ ÃÅÐÉ íÁÒËÏ×Á (Z; X; Y ) ÕÓÌÏ×ÎÁÑ ÉÎÆÏÒÍÁÃÉÑ J (X ; Y |Z ) ≤ J (X ; Y ) (ÓÍ. §4),ÔÏ ÉÚ (47) É (49) ×ÙÔÅËÁÅÔ ÄÏËÁÚÙ×ÁÅÍÏÅ ÎÅÒÁ×ÅÎÓÔ×Ï (45).6.4.2 ÷ÙÐÕËÌÏÓÔØ ×ÎÉÚ ÐÏ WðÕÓÔØ q = (q(z ); z = 0; 1) | ÐÒÏÉÚ×ÏÌØÎÏÅ Ò.×. ÎÁ (0; 1). úÁÆÉËÓÉÒÕÅÍ Ä×Á ÐÒÏÉÚ×ÏÌØÎÙÈÕÓÌÏ×ÎÙÈ Ò.×. ÎÁ ÐÁÒÁÈ (x; y); x = 0; K − 1; y = 0; J − 1:W0 = (W0 (y|x); x = 0; K − 1; y = 0; J − 1);W1 = (W1 (y|x); x = 0; K − 1; y = 0; J − 1);É ÏÂÏÚÎÁÞÉÍ ÞÅÒÅÚW = q(0)W0 + q(1)W1 ;W = (W (y|x); x = 0; K − 1; y = 0; J − 1);W (y|x) =1Xz =0q(z )Wz (y|x);15ÓÍÅÓØ ÜÔÉÈ ÕÓÌÏ×ÎÙÈ ÒÁÓÐÒÅÄÅÌÅÎÉÊ. ÷ÙÐÕËÌÏÓÔØ ×ÎÉÚ ÉÎÆÏÒÍÁÃÉÏÎÎÏÊ ÆÕÎËÃÉÉ ÐÏ ÁÒÇÕÍÅÎÔÕ W ÏÚÎÁÞÁÅÔ, ÞÔÏJ(Q; W) ≤ q(0)·J(Q; W0 ) + q(1)·J(Q; W1 ):(50)äÌÑ ÄÏËÁÚÁÔÅÌØÓÔ×Á (50) ÒÁÓÓÍÏÔÒÉÍ ÔÒÏÊËÕ ÓÌÕÞÁÊÎÙÈ ×ÅÌÉÞÉÎ (Z; X; Y ) Ó Ò.×.p(z; x; y) = q(z )·Q(x)·Wz (y|x);(51)ËÏÔÏÒÏÅ ÏÐÒÅÄÅÌÅÎÏ ÎÁ ÔÒÏÊËÁÈ (z; x; y), z = 0; 1, x = 0; K − 1; y = 0; J − 1: ïÔÍÅÔÉÍÓÌÅÄÕÀÝÉÅ ÔÒÉ ÏÞÅ×ÉÄÎÙÅ Ó×ÏÊÓÔ×Á Ò.×.
(51):1. Ò.×. p(z; x) = p(z )·P (x) = q(z )Q(x), Ô.Å ×ÅÌÉÞÉÎÙ X É Z | ÎÅÚÁ×ÉÓÉÍÙ;2. ÄÌÑ ÐÁÒÙ (X; Y ) ÒÁÓÐÒÅÄÅÌÅÎÉÅ ×ÅÒÏÑÔÎÏÓÔÅÊp(x; y) =Xzp(z; x; y) =Xzq(z )·Q(x)Wz (y|x) = Q(x)·W (y|x);3. ÐÒÉ ÆÉËÓÉÒÏ×ÁÎÎÏÍ z = 0; 1 ÓÐÒÁ×ÅÄÌÉ×Ù ÒÁ×ÅÎÓÔ×Áp(x; y|z ) = Q(x)Wz (y|x); p(x|z ) = Q(x); p(y|z ) =XxQ(x)Wz (y|x):éÚ 2) ÓÌÅÄÕÅÔ, ÞÔÏ ÄÌÑ ÐÁÒÙ ÓÌÕÞÁÊÎÙÈ ×ÅÌÉÞÉÎ (X; Y ) ÉÎÆÏÒÍÁÃÉÑJ (X ; Y ) = J(Q; W):(52)ó×ÏÊÓÔ×Ï 3) ÏÚÎÁÞÁÅÔ, ÞÔÏ ÄÌÑ Ò.×. (51) ÕÓÌÏ×ÎÁÑ ÉÎÆÏÒÍÁÃÉÑJ (X ; Y |Z ) ==Pzq(z )Px;yPx;y;z|z )p(z; x; y) log p(xp(|zx;y)p(y|z ) =Q(x)Wz (y|x) log P QW(k()yW|xz)(y|k) ==kP(53)z q (z )J(Q; Wz ):ðÏÓËÏÌØËÕ ÄÌÑ ÎÅÚÁ×ÉÓÉÍÙÈ ×ÅÌÉÞÉÎ X É Z ÕÓÌÏ×ÎÁÑ ÉÎÆÏÒÍÁÃÉÑ J (X ; Y |Z )≥J (X ; Y )(ÓÍ.§4), ÔÏ ÉÚ (52) É (53) ×ÙÔÅËÁÅÔ ÄÏËÁÚÙ×ÁÅÍÏÅ ÎÅÒÁ×ÅÎÓÔ×Ï (50).16.
