IT6 (Полный комплект лекций Г.А. Дьячкова)
Описание файла
Файл "IT6" внутри архива находится в папке "Полный комплект лекций Г.А. Дьячкова". PDF-файл из архива "Полный комплект лекций Г.А. Дьячкова", который расположен в категории "". Всё это находится в предмете "теория информации" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
á.ç.äØÑÞËÏ×ôÅÏÒÉÑ ÉÎÆÏÒÍÁÃÉɧ6.ðÒÑÍÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ ÄÌÑ ÄÉÓËÒÅÔÎÏÇÏËÁÎÁÌÁ ÂÅÚ ÐÁÍÑÔÉóÏÄÅÒÖÁÎÉÅ1. ðÏÒÏÇÏ×ÏÅ ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÄÌÑ ÄÉÓËÒÅÔÎÏÇÏ ËÁÎÁÌÁ ÂÅÚ ÐÁÍÑÔÉ (äëâð), ÄÅËÏÄÉÒÕÀÝÁÑ ÆÕÎËÃÉÑ ÐÏÒÏÇÏ×ÏÇÏ ÄÅËÏÄÅÒÁ ÄÌÑ Ä×ÏÉÞÎÏÇÏ ÓÉÍÍÅÔÒÉÞÎÏÇÏ ËÁÎÁÌÁ (äóë).2. ÷ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ ÐÏÒÏÇÏ×ÏÇÏ ÄÅËÏÄÅÒÁ ÄÌÑ äëâð.3. çÒÁÎÉÃÁ ÓÌÕÞÁÊÎÏÇÏ ËÏÄÉÒÏ×ÁÎÉÑ ÄÌÑ ×ÅÒÏÑÔÎÏÓÔÉ ÏÛÉÂËÉ ÐÏÒÏÇÏ×ÏÇÏ ÄÅËÏÄÅÒÁ.4. ðÒÑÍÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ Ï ÓÒÅÄÎÅÊ ×ÅÒÏÑÔÎÏÓÔÉ ÏÛÉÂËÉ äëâð.5.
ðÒÑÍÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ Ï ÍÁËÓÉÍÁÌØÎÏÊ ×ÅÒÏÑÔÎÏÓÔÉ ÏÛÉÂËÉ äëâð.6. ôÅÏÒÅÍÁ Ï ÂÏÌØÛÉÈ ÕËÌÏÎÅÎÉÑÈ (ôâõ) ÄÌÑ ÓÕÍÍÙ ÎÅÚÁ×ÉÓÉÍÙÈ ÄÉÓËÒÅÔÎÙÈ ÏÄÉÎÁËÏ×ÏÒÁÓÐÒÅÄÅÌÅÎÎÙÈ ÓÌÕÞÁÊÎÙÈ ×ÅÌÉÞÉÎ.7. ÷Ù×ÏÄ ÜËÓÐÏÎÅÎÃÉÁÌØÎÏÊ ÇÒÁÎÉÃÙ ×ÅÒÏÑÔÎÏÓÔÉ ÏÛÉÂËÉ ÄÌÑ äëâð Ó ÐÏÍÏÝØÀ ôâõ.8. ÷ÙÐÕËÌÏÓÔØ ××ÅÒÈ ÉÎÆÏÒÍÁÃÉÉ J(Q; W) ÐÏ ×ÈÏÄÎÏÍÕ ÒÁÓÐÒÅÄÅÌÅÎÉÀ Q.9. ÷ÙÐÕËÌÏÓÔØ ×ÎÉÚ ÉÎÆÏÒÍÁÃÉÉ J(Q; W) ÐÏ ÕÓÌÏ×ÎÏÍÕ ÒÁÓÐÒÅÄÅÌÅÎÉÀ W.6.1 ïÐÒÅÄÅÌÅÎÉÑ, ÏÂÏÚÎÁÞÅÎÉÑ É ÆÏÒÍÕÌÉÒÏ×ËÁ ÔÅÏÒÅÍÙâÕÄÅÍ ÒÁÓÓÍÁÔÒÉ×ÁÔØ ÄÉÓËÒÅÔÎÙÊ ËÁÎÁÌ ÂÅÚ ÐÁÍÑÔÉ (äëâð) Ó ÍÁÔÒÉÃÅÊ ÐÅÒÅÈÏÄÎÙÈ×ÅÒÏÑÔÎÏÓÔÅÊP = kP (j |k)k; k = 0; K − 1; j = 0; J − 1;ÉÍÅÀÝÉÊ K ≥2 ×ÈÏÄÎÙÈ É J ≥2 ×ÙÈÏÄÎÙÈ ÓÉÍ×ÏÌÏ×, ËÏÔÏÒÙÅ ÏÔÏÖÄÅÓÔ×ÉÍ Ó ÃÅÌÙÍÉ ÞÉÓÌÁÍÉ ÏÔ 0 ÄÏ K − 1 É ÏÔ 0 ÄÏ J − 1, ÓÏÏÔ×ÅÔÓÔ×ÅÎÎÏ.
þÉÓÌÏ P (j |k) ÏÚÎÁÞÁÅÔ ×ÅÒÏÑÔÎÏÓÔØÐÏÌÕÞÉÔØ ÎÁ ×ÙÈÏÄÅ ËÁÎÁÌÁ Ó×ÑÚÉ ÓÉÍ×ÏÌ j , ÅÓÌÉ ÎÁ ×ÈÏÄ ËÁÎÁÌÁ ÂÙÌ ÐÏÄÁÎ ÓÉÍ×ÏÌ k. åÓÌÉÖÅ ÐÏ ËÁÎÁÌÕ ÐÅÒÅÄÁÎÏ ÓÌÏ×Ï x = (x1 ; : : : ; xN ), xi = 0; K − 1, ÄÌÉÎÙ N , ÔÏ ×ÅÒÏÑÔÎÏÓÔØÐÏÌÕÞÉÔØ ÎÁ ×ÙÈÏÄÅ ÓÌÏ×Ï y = (y1 ; : : : ; yN ), yj = 0; J − 1, ÏÐÒÅÄÅÌÑÅÔÓÑ ÓÏÏÔÎÏÛÅÎÉÅÍPN (y|x) ,NYn=1P (yn |xn ):(1)ðÕÓÔØ X = (x(1); x(2); : : : ; x(M ));|ËÏÄ ÏÂßÅÍÁ M . ëÏÄÏ×ÏÅ ÓÌÏ×Ï ÄÌÉÎÙ Nx(m) = (x1 (m); x2 (m); : : : ; xN (m)); xn (m) = 0; K − 1; n = 1; N;ÐÏÓÙÌÁÅÔÓÑ ÐÏ ËÁÎÁÌÕ, ÅÓÌÉ ÐÅÒÅÄÁ×ÁÅÍÏÅ ÓÏÏÂÝÅÎÉÅ = m, m = 1; M .
ðÒÉ ÜÔÏÍ, ÓÏÇÌÁÓÎÏ (1), ×ÅÒÏÑÔÎÏÓÔØ ÐÏÌÕÞÉÔØ ÎÁ ×ÙÈÏÄÅ ËÁÎÁÌÁ Ó×ÑÚÉ ÓÌÏ×Ï y = (y1 ; y2 ; : : : ; yN ) ÅÓÔØPN (y|x(m)) =NYn=11P (yn |xn (m)):(2)ëÁË É × §2, ÂÕÄÅÍ ÒÁÓÓÍÁÔÒÉ×ÁÔØ (N; R){ÂÌÏËÏ×ÙÅ ËÏÄÙ, Ô.Å. ËÏÄÙ X ÏÂßÅÍÁM , dexp{RN }e;(3)ÇÄÅ ÐÁÒÁÍÅÔÒ R > 0, ÎÁÚÙ×ÁÅÍÙÊ ÓËÏÒÏÓÔØÀ ËÏÄÁ ÎÅ ÚÁ×ÉÓÉÔ ÏÔ ÄÌÉÎÙ ÂÌÏËÁ N .ïÐÉÓÁÎÉÅ ÄÅËÏÄÉÒÏ×ÁÎÉÑ, Ô.Å. ×ÙÞÉÓÌÅÎÉÑ ÓÏÏÂÝÅÎÉÑ ÁÄÒÅÓÁÔÁ ÐÏ ×ÙÈÏÄÎÏÍÕ ÓÉÇÎÁÌÕy Ó ÐÏÍÏÝØÀ ÄÅËÏÄÉÒÕÀÝÅÊ ÆÕÎËÃÉÉD(y) = m; ÅÓÌÉ y ∈ Dm ; m = 1; M + 1;(0; J − 1)N = D1 + D2 + : : : + DM + DM +1 ;ÐÏÞÔÉ ÄÏÓÌÏ×ÎÏ ÐÏ×ÔÏÒÑÅÔ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÅÅ ÏÐÉÓÁÎÉÅ ÄÌÑ Ä×ÏÉÞÎÏÇÏ ÓÌÕÞÁÑ ÉÚ §2.
îÁÐÏÍÎÉÍ, ÞÔÏ ÐÒÉ m = 1; M ÕÓÌÏ×ÎÁÑ ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ ËÏÄÁ X :Pm (X ) , Pr{ 6= ~ | = m} =Xy∈D mPN (y|x(m));(4)Á ÓÒÅÄÎÑÑ ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ ËÏÄÁ X :P (X ) , Pr{ 6= ~} =÷×ÅÄÅÍ ÔÁËÖÅP ∗ (X ) ,maxm=1;M1MMXm=1Pm (X ):Pm (X )|(5)(6)ÍÁËÓÉÍÁÌØÎÕÀ ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ ËÏÄÁ X .ïÔÍÅÔÉÍ, ÞÔÏ Ó ÐÏÍÏÝØÀ ÒÁÓÓÕÖÄÅÎÉÊ, ÐÏÞÔÉ ÄÏÓÌÏ×ÎÏ ÐÏ×ÔÏÒÑÀÝÉÈ ÒÁÓÓÕÖÄÅÎÉÑ ÉÚ§2, ÍÏÖÎÏ ÐÏËÁÚÁÔØ, ÞÔÏ ÄÌÑ ÚÁÄÁÎÎÏÇÏ ËÏÄÁ X ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÐÏ ÍÁËÓÉÍÕÍÕ ÐÒÁ×ÄÏÐÏÄÏÂÉÑ (íð{ÄÅËÏÄÉÒÏ×ÁÎÉÅ), ËÏÇÄÁ(íð ) , {y : ∀ m0 6=m; P (y|x(m0 )) ≤ P (y|x(m))};Dm = DmNN(7)ÍÁËÓÉÍÉÚÉÒÕÅÔ ÓÒÅÄÎÀÀ ×ÅÒÏÑÔÎÏÓÔØ ÐÒÁ×ÉÌØÎÏÇÏ ÒÅÛÅÎÉÑ1 − P (X ) =1MM XXm=1 y∈DmPN (y|x(m));(8)Ô.Å. ÍÉÎÉÍÉÚÉÒÕÅÔ ÓÒÅÄÎÀÀ ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ P (X ).äÌÑ ÚÁÄÁÎÎÙÈ N , R > 0 É ÍÁÔÒÉÃÙ P = kP (j |k)k ÐÅÒÅÈÏÄÎÙÈ ×ÅÒÏÑÔÎÏÓÔÅÊ äëâð (1)××ÅÄÅÍ ÓÒÅÄÎÀÀ ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ ÏÐÔÉÍÁÌØÎÏÇÏ (ÎÁÉÌÕÞÛÅÇÏ) (N; R){ËÏÄÁEN (P; R) , min P (X );X;DÇÄÅ ÍÉÎÉÍÕÍ ÓÒÅÄÎÅÊ ×ÅÒÏÑÔÎÏÓÔÉ ÏÛÉÂËÉ ÂÅÒÅÔÓÑ ÐÏ ×ÓÅ×ÏÚÍÏÖÎÙÍ (N; R){ËÏÄÁÍ É ÄÅËÏÄÉÒÕÀÝÉÍ ÆÕÎËÃÉÑÍ.
áÎÁÌÏÇÉÞÎÏ ÏÐÒÅÄÅÌÑÅÔÓÑ ÍÁËÓÉÍÁÌØÎÁÑ ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ ÏÐÔÉÍÁÌØÎÏÇÏ (ÎÁÉÌÕÞÛÅÇÏ) (N; R){ËÏÄÁ∗EN(P; R) , min P ∗ (X ) ≥ EN (P; R):X;D2ðÕÓÔØ Q = (Q(0); : : : ; Q(K − 1)) | ÒÁÓÐÒÅÄÅÌÅÎÉÅ ×ÅÒÏÑÔÎÏÓÔÅÊ ÎÁ ×ÙÈÏÄÎÙÈ ÓÉÍ×ÏÌÁÈ~ = (Q~ (0); : : : ; Q~ (J − 1)), ÇÄÅËÁÎÁÌÁ (1), Á QQ~ (j ) =K−1Xk=0Q(k)P (j |k); j = 0; J − 1;(9)ÓÏÏ×ÅÔÓÔ×ÕÀÝÅÅ ÒÁÓÐÒÅÄÅÌÅÎÉÅ ×ÅÒÏÑÔÎÏÓÔÅÊ ÎÁ ×ÙÈÏÄÎÙÈ ÓÉÍ×ÏÌÁÈ ËÁÎÁÌÁ (1).
äÌÑ ÒÁÓÓÍÁÔÒÉ×ÁÅÍÏÇÏ äëâð Ó ÆÉËÓÉÒÏ×ÁÎÎÏÊ ÐÅÒÅÈÏÄÎÏÊ ÍÁÔÒÉÃÅÊ P = kP (j |kk, k = 0; K − 1,j = 0; J − 1, ××ÅÄÅÍ ÉÎÆÏÒÍÁÃÉÏÎÎÕÀ ÆÕÎËÃÉÀ ËÁÎÁÌÁJ(Q; P) ,K−1 J−1XXk=0P (j |k)Q(k)P (j |k) log ~ ;Q(j )j =0(10)ÏÐÒÅÄÅÌÅÎÎÕÀ ÎÁ ÍÎÏÖÅÓÔ×Å ×ÅÒÏÑÔÎÏÓÔÎÙÈ ÒÁÓÐÒÅÄÅÌÅÎÉÊ Q. þÉÓÌÏC = C (P) , max J(Q; P)Q(11)ÎÁÚÙ×ÁÅÔÓÑ ÐÒÏÐÕÓËÎÏÊ ÓÐÏÓÏÂÎÏÓÔØÀ ËÁÎÁÌÁ ÂÅÚ ÐÁÍÑÔÉ ÎÁ ÅÄÉÎÉÃÕ ×ÒÅÍÅÎÉ. ÷ §4 ÂÙÌÁÄÏËÁÚÁÎÁ ÏÂÒÁÔÎÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ, ËÏÔÏÒÁÑ ÕÔ×ÅÒÖÄÁÌÁ, ÞÔÏlimN →∞EN (P; R) ≥ 1 −C;RÁ ÐÏÔÏÍÕ ÐÒÉ R > C ×ÅÌÉÞÉÎÁ EN (P; R) 6→ 0 ÐÒÉ N → ∞.
áÎÁÌÏÇÉÞÎÙÊ ÒÅÚÕÌØÔÁÔ,ÏÞÅ×ÉÄÎÏ, ÓÐÒÁ×ÅÄÌÉ× É ÄÌÑ EN∗ (P; R).úÁÍÅÞÁÎÉÅ 1. ÷ ÒÁÚÄÅÌÅ 6.4 ÂÕÄÅÔ ÐÏËÁÚÁÎÏ, ÞÔÏ ÉÎÆÏÒÍÁÃÉÏÎÎÁÑ ÆÕÎËÃÉÑ (10) Ñ×ÌÑÅÔÓÑ ×ÙÐÕËÌÏÊ ××ÅÒÈ ÆÕÎËÃÉÅÊ ÁÒÇÕÍÅÎÔÁ Q. ðÏÜÔÏÍÕ, × ÓÉÌÕ ÉÚ×ÅÓÔÎÏÊ ÔÅÏÒÅÍÙ ëÕÎÁ{ôÁËËÅÒÁ, ÎÅÏÂÈÏÄÉÍÙÅ ÕÓÌÏ×ÉÑ ÜËÓÔÒÅÍÕÍÁ × (11), ×ÙÞÉÓÌÑÅÍÙÅ ÐÏ ÔÅÏÒÅÍÅ ìÁÇÒÁÎÖÁ,ÂÕÄÕÔ ÔÁËÖÅ ÄÏÓÔÁÔÏÞÎÙÍÉ É ÜËÓÔÒÅÍÁÌØÎÏÅ ÒÁÓÐÒÅÄÅÌÅÎÉÅ Q Ñ×ÌÑÅÔÓÑ ÒÅÛÅÎÉÅÍ ÓÉÓÔÅÍÙÕÒÁ×ÎÅÎÉÊ@ J(Q; P)= ; ÐÒÉ ×ÓÅÈ k, ÄÌÑ ËÏÔÏÒÙÈ Q(k) > 0;@Q(k)@ J(Q; P)≤ ; ÐÒÉ ×ÓÅÈ k , ÄÌÑ ËÏÔÏÒÙÈ Q(k ) = 0:@Q(k)íÎÏÖÉÔÅÌØ ìÁÇÒÁÎÖÁ ×ÙÂÉÒÁÅÔÓÑ ÔÁËÉÍ ÏÂÒÁÚÏÍ, ÞÔÏÂÙ ÍÁËÓÉÍÕÍ × (11) ÉÍÅÌ ÍÅÓÔÏÐÒÉK−1Xk=0Q(k) = 1:îÁÛÁ ÄÁÌØÎÅÊÛÁÑ ÃÅÌØ | ÄÏËÁÚÁÔÅÌØÓÔ×Ï ÓÌÅÄÕÀÝÉÈ Ä×ÕÈ ÔÅÏÒÅÍ, ËÏÔÏÒÙÅ ÎÁÚÙ×ÁÀÔÓÑÐÒÑÍÙÍÉ ÔÅÏÒÅÍÁÍÉ ûÅÎÎÏÎÁ ÄÌÑ äëâð.ôÅÏÒÅÍÁ 1. (ôÅÏÒÅÍÁ ûÅÎÎÏÎÁ Ï ÓÒÅÄÎÅÊ ÏÛÉÂËÅ). åÓÌÉ R < C , ÔÏ ÓÕÝÅÓÔ×ÕÅÔ (N; R){ËÏÄ X É ÄÅËÏÄÉÒÏ×ÁÎÉÅ D = D(y), ÄÌÑ ËÏÔÏÒÙÈ P (X ) → 0 ÐÒÉ N → ∞.ôÅÏÒÅÍÁ 2.
(ôÅÏÒÅÍÁ ûÅÎÎÏÎÁ Ï ÍÁËÓÉÍÁÌØÎÏÊ ÏÛÉÂËÅ). åÓÌÉ R < C , ÔÏ ÓÕÝÅÓÔ×ÕÅÔ(N; R){ËÏÄ X ∗ É ÄÅËÏÄÉÒÏ×ÁÎÉÅ D∗ = D∗ (y), ÄÌÑ ËÏÔÏÒÙÈ P ∗ (X ∗ ) → 0ÐÒÉ N → ∞.3éÚ ÔÅÏÒÅÍ 1 É 2 ×ÙÔÅËÁÅÔóÌÅÄÓÔ×ÉÅ. (ðÒÑÍÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ). åÓÌÉ 0 < R < C; ÔÏ ÓÕÝÅÓÔ×ÕÅÔlimN →∞EN (P; R) =lim E (P; R) = 0:N →∞ N∗6.2 äÏËÁÚÁÔÅÌØÓÔ×Á ÔÅÏÒÅÍ 1 É 26.2.1 ðÏÒÏÇÏ×ÏÅ ÄÅËÏÄÉÒÏ×ÁÎÉÅúÁÆÉËÓÉÒÕÅÍ ÐÒÏÉÚ×ÏÌØÎÏÅ ÒÁÓÐÒÅÄÅÌÅÎÉÅ ×ÅÒÏÑÔÎÏÓÔÅÊ (Ò.×.) Q = (Q(0); : : : ; Q(K − 1)) ÎÁ×ÈÏÄÎÏÍ ÁÌÆÁ×ÉÔÅ ËÁÎÁÌÁ (1) É ÏÂÏÚÎÁÞÉÍ ÞÅÒÅÚQN (x) ,NYn=1Q(xn ) |(12)ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÅÅ ÒÁÓÐÒÅÄÅÌÅÎÉÅ{ÐÒÏÉÚ×ÅÄÅÎÉÅ ÎÁ ×ÈÏÄÎÙÈ ÓÌÏ×ÁÈ x = (x1 ; x2 : : : ; xN ) ËÁÎÁÌÁ (1).
îÁ ×ÙÈÏÄÎÙÈ ÓÌÏ×ÁÈ y = (y1 ; : : : ; yN ) ××ÅÄÅÍ ÒÁÓÐÒÅÄÅÌÅÎÉÅ ×ÅÒÏÑÔÎÏÓÔÅÊQ~ N (y) ,XxQN (x)PN (y|x);(13)ËÏÔÏÒÏÅ ×ÏÚÎÉËÁÅÔ ÎÁ ×ÙÈÏÄÅ ËÁÎÁÌÁ (1), ÅÓÌÉ ÎÁ ÅÇÏ ×ÈÏÄÅ ÓÌÏ×Ï x ÉÍÅÅÔ Ò.×. (12). ÷ÏÓÐÏÌØÚÏ×Á×ÛÉÓØ ÉÚ×ÅÓÔÎÙÍ ÐÒÁ×ÉÌÏÍNXYx i=1f (xi ; yi ) =NYà K −1Xi=1x=0!f (x; yi ) ;ËÏÔÏÒÏÅ ÓÐÒÁ×ÅÄÌÉ×Ï ÄÌÑ ÌÀÂÏÊ ÆÕÎËÃÉÉ Ä×ÕÈ ÐÅÒÅÍÅÎÎÙÈ f (x; y), ÍÏÖÅÍ ÎÁÐÉÓÁÔØ, ÞÔÏQ~ N (y) =NYi=1Q~ (yi );(14)~ = (Q~ (0); : : : ; Q~ (J − 1)) ÎÁ ×ÙÈÏÄÎÙÈ ÓÉÍ×ÏÌÁÈ ËÁÎÁÌÁ (1) ÏÐÒÅÄÅÌÅÎÏ (9).ÇÄÅ Ò.×. QîÁ ÍÎÏÖÅÓÔ×Å ÐÁÒ (x; y) ÏÐÒÅÄÅÌÉÍ ÆÕÎËÃÉÀNPN (y|x) XP (y |x )IN (x; y) , log ~=log N~ i i ;QN (y)Q(yi )i=1(15)ÇÄÅ ×ÔÏÒÏÅ ÒÁ×ÅÎÓÔ×Ï ×ÙÔÅËÁÅÔ ÉÚ (1) É (14).
äÌÑ ËÏÄÁ X = (x(1); : : : ; x(M )) ÒÁÓÓÍÏÔÒÉÍÐÏÒÏÇÏ×ÙÊ ÄÅËÏÄÅÒ, ËÏÔÏÒÙÊ ÒÁÂÏÔÁÅÔ ÓÌÅÄÕÀÝÉÍ ÏÂÒÁÚÏÍ. ðÏ ÐÏÌÕÞÅÎÎÏÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ y ÄÅËÏÄÅÒ ×ÙÞÉÓÌÑÅÔ ÓÔÁÔÉÓÔÉËÕ I (m) , IN (x(m); y) ÄÌÑ ËÁÖÄÏÇÏ ËÏÄÏ×ÏÇÏ ÓÌÏ×Áx(m), m = 1; M . úÁÔÅÍ ÄÅËÏÄÅÒ ÓÒÁ×ÎÉ×ÁÅÔ ×ÓÅ ÓÔÁÔÉÓÔÉËÉ I (m) Ó ÞÉÓÌÏÍ T ·N , ÇÄÅ T | ÎÅËÏÔÏÒÙÊ ÆÉËÓÉÒÏ×ÁÎÎÙÊ ÐÁÒÁÍÅÔÒ (ÐÏÒÏÇ).
åÓÌÉ ÉÍÅÅÔÓÑ ÏÄÎÏ É ÔÏÌØËÏ ÏÄÎÏ ÚÎÁÞÅÎÉÅ m,ÄÌÑ ËÏÔÏÒÏÇÏ I (m) > T ·N , ÔÏ ÄÅËÏÄÅÒ ÐÒÉÎÉÍÁÅÔ ÒÅÛÅÎÉÅ Ï ÔÏÍ, ÞÔÏ ÐÏ ËÁÎÁÌÕ ÐÅÒÅÄÁ×ÁÌÏÓØ ÓÌÏ×Ï x(m). ÷ ÐÒÏÔÉ×ÎÏÍ ÓÌÕÞÁÅ ÐÒÏÉÚ×ÏÄÉÔ ÓÔÉÒÁÎÉÅ, ÏÔËÁÚÙ×ÁÑÓØ ÐÒÉÎÉÍÁÔØÒÅÛÅÎÉÅ.äÌÑ ÄÁÎÎÏÇÏ ÓÐÏÓÏÂÁ ÐÒÉÎÑÔÉÑ ÒÅÛÅÎÉÑ ÐÒÉ ÐÅÒÅÄÁÞÅ ÓÌÏ×Á x(m) ÏÛÉÂÏÞÎÏÅ ÒÅÛÅÎÉÅ(ÎÅÏÂÎÁÒÕÖÅÎÁÑ ÏÛÉÂËÁ) ÐÒÏÉÓÈÏÄÉÔ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÓÔÁÔÉÓÔÉËÁ I (m)≤T ·N4É ÓÕÝÅÓÔ×ÕÅÔ ÒÏ×ÎÏ ÏÄÎÏ ÚÎÁÞÅÎÉÅ m0 6=m ÄÌÑ ËÏÔÏÒÏÇÏ I (m0 ) > T ·N: ðÒÁ×ÉÌØÎÏÅ ÒÅÛÅÎÉÅÐÒÉ ÐÅÒÅÄÁÞÅ ÓÌÏ×Á x(m) ÐÒÏÉÓÈÏÄÉÔ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÓÔÁÔÉÓÔÉËÁ I (m) > T ·NÉ ÄÌÑ ×ÓÅÈ ÚÎÁÞÅÎÉÊ m0 6=m ÓÔÁÔÉÓÔÉËÁ I (m0 )≤T ·N:úÁÍÅÞÁÎÉÅ 2.
äÌÑ ÒÁÓÓÍÁÔÒÉ×ÁÅÍÏÇÏ ÐÏÒÏÇÏ×ÏÇÏ ÄÅËÏÄÉÒÏ×ÁÎÉÑ ÏÂÌÁÓÔÉ ÄÅËÏÄÉÒÏ×Á(T )ÎÉÑ Dm; m = 1; M; ÐÒÉ ÉÓÐÏÌØÚÏ×ÁÎÉÉ ÐÏÒÏÇÁ T > 0 ÚÁÄÁÅÔÓÑ ÓÌÅÄÕÀÝÉÍ ÏÂÒÁÚÏÍT = {y : I (x(m); y) > T ·N; É ÄÌÑ ÌÀÂÏÇÏ m0 6=m ÚÎÁÞÅÎÉÅDmNIN (x(m0 ); y) ≤ T ·N }:ðÒÉÍÅÒ 1. ðÏÒÏÇÏ×ÏÅ ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÄÌÑ äóë Ó ×ÅÒÏÑÔÎÏÓÔØÀ ÏÛÉÂËÉ p, 0 < p < 1=2.÷ÙÂÅÒÅÍ × ËÁÞÅÓÔ×Å Ò.×. Q = (1=2; 1=2), ÎÁ ËÏÔÏÒÏÍ ÄÏÓÔÉÇÁÅÔÓÑ ÐÒÏÐÕÓËÎÁÑ ÓÐÏÓÏÂÎÏÓÔØ~ = (1=2; 1=2) É ÄÌÑ ÌÀÂÏÇÏ y ×ÅÒÏÑÔÎÏÓÔØäóë ÂÅÚ ÐÁÍÑÔÉ C = log 2−h(p). ôÏÇÄÁ ÏÞÅ×ÉÄÎÏ Q−NQ~ N (y) = 2 . ðÏÜÔÏÍÕ, ÓÏÇÌÁÓÎÏ ÏÐÒÅÄÅÌÅÎÉÀ (15) É ÏÐÒÅÄÅÌÅÎÉÀ äóë × §2,pIN (x; y) = N log 2·(1 − p) + (x; y) log; 0 < p < 1=2:1−póÌÅÄÏ×ÁÔÅÌØÎÏ, ÐÏÌÏÖÉ×T ∗ = T ∗ (p; T ) =log 2(1 − p) − T;log 1−p p(T )ÏÂÌÁÓÔÉ ÄÅËÏÄÉÒÏ×ÁÎÉÑ Dm, m = 1; M , ÍÏÖÎÏ ÚÁÐÉÓÁÔØ × ×ÉÄÅ(T ) = {y : (x(m); y) < T ∗ N; Á ÄÌÑ ÌÀÂÏÇÏ m0 6= mDmÒÁÓÓÔÏÑÎÉÅ èÜÍÍÉÎÇÁ (x(m0 ); y) ≥ T ∗ N }:ðÕÓÔØ 1(N ) = 1 (x(m); T ) | ÕÓÌÏ×ÎÁÑ ×ÅÒÏÑÔÎÏÓÔØ ÔÏÇÏ, ÞÔÏ ÓÔÁÔÉÓÔÉËÁ I (m)≤T ·NÐÒÉ ÕÓÌÏ×ÉÉ, ÞÔÏ ÐÏ ËÁÎÁÌÕ ÂÙÌÏ ÐÅÒÅÄÁÎÏ ÓÌÏ×Ï x(m). äÌÑ m0 6=m ××ÅÄÅÍ 2(N ) (m0 ) =2 (x(m0 ); T ) | ÕÓÌÏ×ÎÕÀ ×ÅÒÏÑÔÎÏÓÔØ ÔÏÇÏ, ÞÔÏ ÓÔÁÔÉÓÔÉËÁ I (m0 ) > T ·N ÐÒÉ ÕÓÌÏ×ÉÉ, ÞÔÏÐÏ ËÁÎÁÌÕ ÂÙÌÏ ÐÅÒÅÄÁÎÏ ÓÌÏ×Ï x(m).
éÍÅÅÍ1(N ) =2(N ) (m0 ) =XyXyPN (y|x(m))T (x(m); y);PN (y|x(m))·[1 − T (x(m0 ); y)]; m0 6= m;(16)ÇÄÅ ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÁÑ ÆÕÎËÃÉÑT (x; y) ,½1; ÅcÌÉ IN (x; y) ≤ T ·N;0; ÅcÌÉ IN (x; y) > T ·N;(17)Á IN (x; y) ÏÐÒÅÄÅÌÅÎÁ (15).äÁÌÅÅ ÐÏÄ ÏÛÉÂËÏÊ ÂÕÄÅÍ ÐÏÄÒÁÚÕÍÅ×ÁÔØ ÓÉÔÕÁÃÉÀ ÌÉÂÏ ÓÔÉÒÁÎÉÑ ÌÉÂÏ ÎÅÏÂÎÁÒÕÖÅÎÎÏÊ ÏÛÉÂËÉ. éÚ ÏÐÉÓÁÎÎÏÇÏ ×ÙÛÅ ÁÌÇÏÒÉÔÍÁ ÐÏÒÏÇÏ×ÏÇÏ ÄÅËÏÄÉÒÏ×ÁÎÉÑ ×ÙÔÅËÁÅÔ5ìÅÍÍÁ 1. (çÒÁÎÉÃÁÏÛÉÂËÉ ÐÏÒÏÇÏ×ÏÇÏ ÄÅËÏÄÅÒÁ). äÌÑ ÌÀÂÏÇÏ ÆÉËÓÉÒÏ×ÁÎÎÏÇÏ ËÏÄÁX = (x(1); : : : ; x(M )) ÐÒÉ ÐÏÒÏÇÏ×ÏÍ ÄÅËÏÄÉÒÏ×ÁÎÉÉ ÕÓÌÏ×ÎÁÑ ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ (4) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÎÅÒÁ×ÅÎÓÔ×ÕMX(N )Pm (X ) ≤ 1 +2(N ) (m0 ):m0 6=m(18)äÌÑ ÐÏÌÕÞÅÎÉÑ ×ÅÒÈÎÉÈ ÏÃÅÎÏË ×ÅÒÏÑÔÎÏÓÔÅÊ 1(N ) É 2(N ) (m0 ) ÐÒÉÍÅÎÑÅÔÓÑ ÐÒÅÄÌÏÖÅÎÎÙÊ ûÅÎÎÏÎÏÍ ÍÅÔÏÄ ÓÌÕÞÁÊÎÏÇÏ ËÏÄÉÒÏ×ÁÎÉÑ.6.2.2 íÅÔÏÄ ÓÌÕÞÁÊÎÏÇÏ ËÏÄÉÒÏ×ÁÎÉÑòÁÓÓÍÏÔÒÉÍ ÁÎÓÁÍÂÌØ (N; R){ËÏÄÏ× X = (x(1); : : : ; x(M )), ÇÄÅ Ò.×.