Застосування штрих-коду для кодування інформації

1.2.3 Умовна  ентропія. Iнформацiя, що мiститься

 в одному дослiдi вiдносно iншого

 

Розглянемо два дослiди а i b, вiдповiдно з результатами А₁, A₂, ..., А_i, ..., A_m i результатами В₁, B₂, ..., В_j, ..., B_n i вiдомими iмовiрностями цих результатів Р(А₁), Р(А₂), ..., Р(A_i) i Р(В₁), Р(В₂), ..., Р(B_j). Вiзьмемо далi складний дослiд аb, який полягає в тому, що водночас здiйснюються дослiди а i b. Спробуємо обчислити середню власну iнформацiю, що мiститься в якому-небуть результатi складного дослiду (A_i, B_j) або, iншими словами, ентропiю дослiду ab. По визначенню ентропiя складного дослiду рiвна

H(a,b) = -SР(A_i,B_j) log P(A_i,В_j).   (1. 26)

              ^ij

 З iншого боку, ентропiя  першого дослiду a рiвна 

H(a,b) = -SР(A_i) log P(A_i)   (1. 27)

                 ⁱ

   Пiдставимо далi в (1. 27) Р(A_i), що входять в перший спiвмножник кожного доданку в виглядi

P(A_i) = -SP(A_i,В_j)    (1. 28).

               ^j

Вiдзначимо, що вираз (1. 28) являє собою  запис формули повної iмовiрностi для подiї A_i, тобто формулу (1. 12). Пiсля подстановки (1.28) в (1. 27) отримаємо

H(a) = -SSР(A_i,B_j) log P(A_i)  (1.29)

     ^{i   j}

Аналогiчно ентропiя дослiду b може бути представлена в виглядi

H(b) = -SSР(A_i,B_j) log P(В_j)  (1.30)

     ^{i   j}

Якщо a i b - незалежнi дослiди, то для  кожної пари результатiв A_i i B_j

P (A_i,B_j) = P(A_i) P(B_j),

   отже,

log Р(А_i,В_j)=log Р(A_i) + log Р(B_j).  (1.31)

   Пiдставляючи далi (1. 31) в (1. 26), отримаємо

H(a,b)= - SSР(A_i,B_j) log P(A_i) - SSР(A_i,B_j) log P(В_j)

        ^{i   j               i   j}

   Або, маючи на  увазi (1. 29) i (1. 30),

H (ab) =H (а) + H (b).     (1. 32)

Таким чином, при незалежних дослiдах ентропiя складного дослiду рiвна сумi ентропiй кожного дослiду.

В бiльш загальному випадку, коли дослiди залежнi, iмовiрнiсть пари результатів A_i, B_j може бути представлена в виглядi

 Р (А_i, В_j) =Р(А_i) Р(В_j).    (1. 33)

   Вiдповiдно

log Р (А_i,В_j) = log Р(A_i) + logPA_i(B_j).  (1. 33')

   Тут PA_i(B_j) означає умовну iмовiрнiсть результата В_j, якщо вiдомо, що дослiд а закiнчився результатом A_i. Підставляючи (1. 33') в (1. 20), отримаємо

H(a,b) = -SSР(A_i,B_j) log P(A_i) - SSР(A_i,B_j) log PA_i(В_j)    (1.34)

        ^{i   j               i   j}

Перша сума в виразi (1.34) являє собою (1.29) або ентропiю дослiду а. Другу суму в (1.34) називають умовною  ентропiєю дослiду b, припускаючи, що який-небуть результат дослiду а мав мiсце. Цю ентропiю дослiду b за умови дослiду а позначимо H_a(b). Тодi ентропiя складного дослiду, тобто (1. 34), може бути записана

H (а, b)=H (a) + H_a(b).     (1. 35)

   По визначенню умовна  ентропiя являє собою вираз

       (1.36) 

або, маючи на увазi (1. 33),

    (1.37)

         ^{i              j} 

Внутрiшня сума в виразi (1. 37), очевидно, являє собою ентропiю дослiду b за умови, що дослiд a закiнчився конкретним результатом A_i. Справдi ця внутрiшня сума нiчим не вiдрiзняється вiд виразу (1.19), за винятком того, що замiсть iмовiрностей Р(B_j) тут стоять iмовiрностi результатiв B_j при умовi, що був конкретний результат A_i. Цю умовну ентропiю дослiду b при конкретному результатi дослiду а позначимо через HA_i(b)

НА_i(b) = - SРA_i(B_j) log PA_i(В_j)      (1.38)

         ^j 

При цьому вираз (1. 37), тобто умовна ентропiя дослiду b при дослiдi a, може бути представлено як усереднення виразу (1. 38) по всiм результатам дослiду а, тобто по всiм А_i

Н_a(b) = - SР(A_j)HA_i(В_j)       (1.39)

       ⁱ 

Таким чином, умовна ентропiя дослiду b при дослiдi а являє собою середню  власну iнформацiю, що полягає в результатi дослiду b в середньому при будь-якому  результатi дослiду а.

Розглянемо властивостi умовної  ентропiї.

1. Якщо дослiди a i b незалежнi, те  умовна ентропiя рiвна безумовнiй 

H_a(b) = H (b).      (1.40)

Властивiсть (1.40) безпосередньо слiдує  з порiвняння формул (1.32) i (1.35), виведених  вiдповiдно для випадкiв незалежних i залежних дослiдiв.

2. Якщо результати першого дослiду, скажемо дослiду а, повнiстю  визначають результати iншого дослiду b (тобто дослiд а визначає дослiд  b), то умовна ентропiя рiвна  нулю 

H_a (b) = 0.      (1.41)

Дiйсно, бо при цьому всi РA_i(B_j) рiвнi або одиницi або нулю, в вiдповiдностi з (1.38) величина HA_i(b) рiвна нулю для всiх результатiв А_i дослiду а. НA_i(b)=0, тому вираз (1. 39) перетворюється в нуль.

3. Умовна ентропiя завжди менша  або рiвна безумовної ентропiї,  тобто

H_a(b) £ H (b).      (1.42)

Знак рiвностi має мiсце при  незалежностi дослiду а i b (див. властивiсть 1).

Для доказу спiввiдношення (1. 42) утворимо рiзницю

H_a(b) - H (b) = -SSР(A_i,B_j) log PA_i(В_j) -(- SSР(A_i,B_j) log P(В_j)) =   (1.43)

        ^{i   j                   i   j}

= - SSР(A_i,B_j) log (P(В_j)/PA_i(В_j))

         ^{i   j}              

Застосуємо до виразу (1.43) властивiсть логарифмiчної функцiї (1. 23), поклавши тут w = Р(B_j)/PA_i(B_j). Тодi

H_a(b) - H (b) £ log e SSР(A_i,B_j)(P(В_j)/PA_i(В_j) - 1)=0

  ^{i    j}

Дiйсно, права частина цiєї нерiвностi легко може бути записана як

log e [SР(A_i)SР(B_j) - 1] =0

^{i  j}

що тотожно рiвна нулю. Отже, H_a(b) - H (b) £ 0, тобто доведена нерiвнiсть (1.42). Знак рiвностi має мiсце при w=0, тобто при P(B_j)/PA_i(B_j) =1 для будь-яких А_i i B_j, або тодi, коли дослiди а i b незалежнi.

Ми отримали результат, що умовна ентропiя  дослiду b, якщо проведений дослiд а, завжди менша або рiвна ентропiї  дослiду b. Однак умовна ентропiя дослiду b при конкретному результатi дослiду а, HA_i(b) може бути i меншою i бiльшою ентропiї дослiду b, Н(b). Цей факт можна пояснити слiдуючим чином. Для одних результатiв А_i має мiсце HA_i(b) < H(b), для iнших, навпаки, HA_i(b) буде бiльше H(b). Але в середньому в сенсi формули (1. 39) ентропiя H_а(b) буде завжди менша або рiвна ентропiї H (b).

Пояснимо сказане прикладом.

Нехай хворий страждає яким-небуть одним  з трьох захворювань B₁, B₂, B₃. При цьому iмовiрнiсть того, що вiн страждає першим захворюванням, рiвна Р(B₁)=0.98, а iмовiрностi iнших захворювань вiдповiдно рiвнi Р(B₂) =P(B₃) =0,01. Подальше дослiдження хворого a може мати два результата А₁ i A₂, причому результат А₁ виключає захворювання B₁, а результат A₂ повнiстю пiдтверджує наявнiсть захворювання B₁ i, отже, виключає захворювання B₂ i В₃. Обчислимо ентропiю (невизначенiсть) ситуацiї до проведення дослiдження a. Тодi

H(b)= - [P(B₁) log P(B₁) + P(B₂) log P(B₂) + P(B₃) log P(B₃)] =

= - [0,98 log0,98 + 0,01 log 0,01 + 0,01 log 0,01] = 0,16 бiт. 

Вiдзначимо, що Р(A₂) =0, 98, а Р(A₁) = 0, 02, бо поява цих результатов еквiвалентна подiям B₁ i notВ₁. Крiм того, очевидно, що PA₁(B₁) = 0, PA₁(B₂)=PA₁(B₃) = ¹/₂, бо результат А₁ виключає захворювання B₁ i при цьому залишаються два рiвноiмовiрних захворювання: В₂ i B₃. З iншого боку, PA₂(B₁)=1 i  PA₂(B₂) = PA₂(B₃) = 0. Обчислимо тепер ентропiю (невизначенiсть) ситуацiї при конкретних результатах дослiдження a

НА₁(b)= - [PA₁(B₁) log PA₁(B₁)+РА₁(B₂) log PA₁(B₂)+РA₁(B₃) log PA₁(B₃)] =

= 0 + ¹/₂log2 + ¹/₂log2= 1 бiт,

НА₂(b)= - [PA₂(B₁) log PA₂(B₁)+PA₂(B₂) log PA₂(B₂)+PA₂(B₃) log PA₂(B₃)] =

=0 + 0 + 0 = 0.

Таким чином, ми бачимо, що результат А₁ збiльшує ентропiю (невизначенiсть) ситуацiї, а результат А₂ зменшує. Цей факт має просте фiзичне обгрунтування. Справдi, до проведення дослiдження a, розподiл iмовiрностей захворювань був таким, що ми могли бути майже впевненi в тому, що хворий страждає захворюванням В₁, i в цьому сенсi невизначенiсть ситуацiї була надто невелика (0, 16 бiт).

Однак, якщо в результатi дослiдження a з'являється результат A₁ (що в загалi-то малоймовiрно, але можливо), то в цьому випадку виявиться, що хворий може мати яке-небуть одне з двох рiвноможливих захворювань B₂ або B₃. В цьому випадку невизначенiсть ситуацiї виявиться вже значно бiльшою (1 бiт). Але якщо в результатi дослiду a виникне результат А₂ (що вiдбувається в переважнiй бiльшостi випадкiв, в середньому в 98 випадках з 100), та це твердо вкаже на наявнiсть у хворого захворювання В₁, i, отже жодної невизначенностi бiльше не буде (HA₂(b)=0). Середня ж ентропiя ситуацiї b за умови проведення iспиту а буде все-таки менша, нiж Н(b)

H_a(b) = Р(А₁)НA₁(b)+Р(А₂)НA₂(b)=0, 02·1+0, 98·0=0, 02 бiт,

тобто

H_a(b) < H(b).

4. Оскiльки всяка ентропiя додатня,  то вираз (1. 38) iстотно додатнiй,  а отже, додатня i (1. 39). Отже,

H_a(b) ³ 0.      (1.44)

Об'єднуючи (1. 42) i (1. 44), отримаємо

0 £ H_a(b) £ H (b).     (1.45)

5. В якостi п'ятої  властивостi умовної ентропiї виведемо  тотожнiсть

Н(а) + H_a(b) = H (b) + H_b(a).   (1.46)

Вираз (1.46) безпосередньо  слiдує з того факту, що складний дослiд ab нiчим нe вiдрiзняється вiд дослiду ba. Отже,

H(аb) = H(ba)

або

H(a) + H_a(b) = H(b) + H_b(a).

Розглянемо тепер питання  про середню iнформацiю, що мiститься  в одному дослiдi вiдносно iншого, або, iнакше кажучи, про середню вiдносну iнформацiю. Нехай невизначенiсть, зв'язана з деяким дослiдом b, виражається ентропiєю H(b). Здiйснення деякого iншого дослiду а зменшує невизначенiсть дослiду b. Це виражається в тому, що умовна ентропiя ситуацiї b пiсля проведення дослiду a стає меншою, нiж ентропiя ситуацiї b, тобто

H_a(b) £ H(b).

Різниця H(b) - H_a(b) являє собою зменшення невизначеностi дослiду b або, iншими словами, зменшення середньої власної iнформацiї в дослiдi b. Це зменшення власної iнформацiї в дослiдi b прeдcтавляє собою ту кiлькiсть iнформацiї, що несе дослiд a вiдносно дослiду b. В вiдповiдностi з цим середньою iнформацiєю одного дослiду вiдносно iншого називають вираз

I(ab) = H(b) - H_a(b).    (1.47)

Враховуючи вираз (1.46), можемо записати

H(b) - H_a(b) = H(a) - H_b(a)    (1. 48)

або

I(ab) = I(ba)      (1. 49)

Таким чином, середня iнформацiя, що полягає в одному дослiдi вiдносно iншого, рiвна середнiй iнформацiї, укладеній  в iншому дослiдi вiдносно першого. Оскiльки умовна ентропiя - величина iстотно додатня, то з (1. 47) i (1. 48) слiдує, що

I(ab) £ H (a), I (ab) £ H (b).   (1. 50)

   Нерівність (1. 50) виражае  той факт, що середня iнформацiя,  що мiститься в одному дослiдi  вiдносно iншого, менша, нiж iнформацiя,  укладена в середньому в кожному  результатi цього дослiду вiдносно самого себе.

Вiдноcна iнформацiя, що мiститься  в конкретному результатi дослiду a, тобто в А_i, вiдносно всiх результатів дослiду b (в середньому) в вiдповiдностi з визначенням (1. 47), рiвна

I (A_ib) = H (b) - HA_i(b).    (1.51)

 Вона може бути i додатньою i вiдємною, оскiльки НА_i(b) може бути i менше, i бiльше Н(b). В протилежнiсть цьому iнформацiя I(ab) завжди додатня, оскiльки Н_а(b) завжди менше або рiвне H(b). Якщо же нас цiкавить iнформацiя, що мiститься в конкретному результаті дослiду ab (тобто в A_i) вiдносно конкретного результату дослiду b (тобто B_j), то в вирзi (1.51) слiд опустити усереднення по результатам B_j. Тодi отримаємо

I(А_i, В_j) = - log Р(B_j) - (- log PA_i(Bj)) = log (PA_i(B_j)/P(B_j)),

тобто вираз (1. 17).

 

1.2.4 Надлишковість

 

Маємо деяку систему дослiдів a₁, a₂, ..., a_m. Власна середня кiлькiсть iнформацiї на один результат кожного окремого дослiду рiвна його ентропiї

I(a₁) = Н(a₁),

I(a₂) = Н(a₂),

. . . . . . . . . . . . .

I(a_m) = Н(a_m),

Власна середня кiлькiсть iнформацiї на один результат складного дослiду, являючого собою сукупнiсть дослiдiв a₁, ..., a_m, рiвна ентропiї складного дослiду    I(a₁, ..., a_m) = H(a₁, ..., a_m).

Якщо дослiди a₁, ..., a_m незалежнi, то в вiдповiдностi з (1. 32)

H (а₁, ..., a_m) = H(a₁) + H(a₂) + ... + H(a_m)

або

I (a₁, ..., a_m) = SI(a_i)    (1.52)

 ⁱ

Однак, якщо дослiди a₁, ..., a_m залежнi, то в вiдповiдностi з (1. 32), (1. 35) i (1.42)

H(а₁, ..., a_m) £ H(a₁) + H(a₂) + ... + H(a_m)

або

I (а₁, ..., a_m) £ I(a₁) + I(a₂) + ... + I(a_m)   (1.53)