5. Ентропія об’єднання двох джерел.

Ентропію Н(А,В) об`єднання двох джерел А та В знаходимо через імовірність сумісної появи пар повідомлень а_{і ,}b_j для всіх і=1... k та j=1…l , яку позначимо р (а_{і ,}b_j ). Для цього складемо матрицю типу (2.23), що визначає розподіл сумісної безумовної ймовірності двох джерел:

Оскільки р (а_{і ,}b_j ) – це ймовірність сумісної появи двох повідомлень, ентропія Н(А,В) є середньою кількістю інформації, що припадає на два довільних повідомлення джерел А та В й визначається так:

Зрозуміло ,що

Оскільки р (а_{і ,}b_j ) = р (b_j, а_і ).

Розглянемо докладніше вираз (2.36). якщо врахувати (2.13), то можна записати

Згадавши, що логарифм добутку дорівнює сумі логарифмів , матимемо

Тепер потрібно врахувати, що згідно з (2.24)

Тому перша складова в(2.39) відповідно до (2.8) визначає безумовну ентропію джерела А, тобто

А друга складова відповідно до (2.22) є загальною умовою ентропією Н(В/А). Отже,

Властивість симетрії (2.37) дає змогу провести подібні перетворення ще раз і дістати інший вираз ентропії Н(А,В), а саме:

З урахуванням (2.40) і (2.41) загальну умовну ентропію можна визначити порівнянням безумовної ентропії об`єднання джерел та ентропії одного з них – А яи В:

Відзначимо такі основні властивості ентропії об`єднання двох джерел:

1. При статично незалежних повідомленнях джерел А та В ентропія об`єднання їх дорівнює сумі ентропії окремих джерел, тобто

2. При повній статичній залежності джерел А та В ентропія об`єднання їх дорівнює безумовній ентропії одного із джерел, тобто

3. Ентропія об`єднання двох джерел відповідає нерівності

Тема 4. Методи визначення ентропії.

План

1. Ентропія по Хартлі.

2. Ентропія по Шеннону.

3. Ентропія по Колмогорову та ентропія 3.

4. Ентропія по Шульцу та Мідлтону.

5. Ентропія по Николайчуку. Інші методи визначення ентропії.

1. Ентропія по Хартлі.

Першу спробу встановити кількісну міру інформації зробив у 1928 р. американський інженер Роберт Хартлі. Ця міра встановлювала здатність різних систем передавати інформацію.

Міру кількості інформації Роберт Хартлі встановив на основі запропонованої ним концепції вибору.

Згідно цієї концепції зв’язок між джерелом інформації (відправником) та її одержувачем (адресатом) здійснюється тільки в тому випадку, коли в системі є сукупність можливих повідомлень, із яких передавач вибирає певне окреме повідомлення. При цьому інформація, що передається окремим повідомленням, залежить від тієї множини інформації, із якої воно вибрано.

Перш за все повинна існувати група фізичних символів, які мають за погодженням відправника і адресату певний зміст. В даній передачі відправник мислительно вибирає той чи інший символ і за допомогою якого-небудь матеріального процесу спрямовує на цей символ одержувача інформації. В результаті послідовних виборів адресат одержить певну послідовність символів.

При кожному виборі вилучають всі інші символи, які могли б бути вибрані. По мірі виконання виборів вилучається все більша і більша кількість послідовностей можливих символів і інформація в адресата стає все більш точною. Наприклад, у реченні „студент ТНЕУ ” перше слово вилучає всі інші групи людей, всі інші об’єкти. Друге слово спрямовує увагу на приналежність студента до певного вузу. Проте, тут не виключаються можливості, що стосуються прізвища студента, його національності, місця проживання і т. п. Подальша інформація про все це може бути передана шляхом наступних виборів.

Нехай є m символів системи S, чи m дослідів з різними, рівно можливими послідовними станами системи. Тоді міра різноманітності множини станів системи задається формулою Хартлі

, (1.2)

де k – коефіцієнт пропорційності (масштабуванння, в залежності від вибраної одиниці вимірювання), а – основна система міри. Ця міра кількості інформації цілком узгоджується з інтуїтивними вимогами до такої міри. Справді, інтуїтивно відчувається, що кількість інформації у повідомленні буде тим більша, чим довше повідомлення і характеристика будь-якого об’єкта буде тим повнішою і кращою, чим більше різноманітних повідомлень є про нього. Наприклад, оцінка студента за 100 бальною системою краще відображає його знання, ніж за п’ятибальною. Зауважимо, що вибір основи логарифму а не є істотним. Оскільки , то перехід від однієї системи логарифмів до другої зводиться до множення функції f(m) = log m на сталий множник , тобто рівнозначний зміні одиниці вимірювання ступеня невизначеності .

Якщо вимірювання ведеться у двійковій системі, то k =1/ ln2, (біт), якщо в десятковій, то k =1/ ln10, (біт), якщо в експотенціальній, то k =1, (ніт).

Оскільки в інформаційних системах використовується двійкова система числення (двійкове кодування), то у формулі (1.2) доцільно покласти а=2.

(1.3)

З точки зору сучасної теорії систем, формулу (1.3) можна тлумачити так: -це кількість інформації в бітах, яка одержується повідомленням про знаходження системи в одному із m рівно можливих станів.

При цьому біт тут тлумачиться не так, як при технічному підході до оцінювання інформації, де біт – це кількість інформації, яку несе один двійковий розряд і біт є цілим числом.

В концепції вибору за Хартлі, біт – це кількість інформації, яку несе повідомлення про стан системи, яка може знаходитися тільки в одному з двох рівно можливих станів.

Біт – це кількість інформації, яка зменшує невизначеність системи рівно вдвічі.

В концепції Хартлі біт не є обов’язково цілим числом.

Приклад 1. Скільки біт інформації несе повідомлення про появу двохзначного 16-кового числа?

Оскільки всіх різних двохзначних 16-кових чисел є 15*16=240, то система може мати 240 рівноможливих станів. Отже, за формулою (1.3) маємо

(біт)

Формула Хартлі (1.3) відволікається від семантичних і якісних, індивідуальних властивостей системи, яка розглядається. Це основний позитив цієї формули. Формула Хартлі зручна для розв’язування деяких практичних задач, проте, в багатьох випадках вона мало придатна тому, що повністю ігнорує відмінності між характером наявних станів. Майже неймовірному стану певної системи тут надається такеж значення , як і цілком правдоподібному. Адже – всі стани рівно можливі.

Сам Хартлі вважав, що відмінності між окремими станами (результатами досліду) визначаються в першу чергу „психологічними факторами” і тому повинні бути враховані лише психологами, але аж ніяк інженерами та математиками.

Помилковість такої точки зору була показана американським математиком та інженером Клодом Шеноном. Про це мова йтиме в наступному параграфі.

Оскільки всіх станів системи є m і всі вони рівно ймовірні, то ймовірність випадкової появи будь-якого з них . Звідки

Підставивши це значення у формулу (1.3) дістанемо

.

Отже, отримали другу формулу Хартлі (1.4)

Приклад 2. Скільки біт інформації несе повідомлення про те, що ймовірність появи будь-якого із m станів системи дорівнює 0,37. Скориставшись формулою (1.4) дістанемо

(біт).

Має місце теорема Хартлі: Якщо у множині Х={х ,…, х } виділити довільний елемент х є Х, то для того , щоб знайти його, необхідно одержати не менше log m одиниць інформації.[7,с.54-57]

Приклад 3. Є 27 монет, із яких одна фальшива (легша). Скільки зважувань треба виконати, щоб виявити фальшиву монету?

Кожне зважування групи монет на терезах дає log 3 біт інформації (подумайте чому?). Всіх зважувань треба виконати Х. Отже, Х log 3= log 27. Звідки Х=3.