Ентропия и информация

Станчо Вълканов Павлов

свети Кирил и Методий ^{( 1 )}

Основни неравенства в теорията на информацията

Ентропия

Информацията за елементарно събитие се определя като логаритъм от реципрочната стойност на вероятността на събитието при основа 2:

Измерва се в битове.
Ако основата е друга – 10 или Неперовото число (e) мерните единици за информация се наричат съответно „дит” и „нат”.
Преходът от едни единици към други се осъществява с един коефициент, който се определя от формулата за смяна на основите: log_BA= log_aA/ log_aB
Ще считаме че логаритмите са натурални.

Средната стойност на информацията на елементарните събития се нарича ентропия.

Ако X е случайна величина със закон на разпределение Закон на разпределение на случайна величина _2ProbDistributin1

нейната ентропия е сума от вероятностите по логаритъма от тях, отчетена със знак минус^{( 3 )}.

Тя е неотрицателна величина, защото вероятностите са по-малки от 1.
Ако вероятносттта е нула считаме, че 0.ln0=0, защото

Ентропията не зависи от стойностите на случайната величина а от техните вероятности.
Затова можем да я считаме като функция на набор от неотрицателни числа със сума 1:
Ако наборът p се състои от неотрицателни числа със сума 1 то неговата ентропия е сумата от произведенията им по техните логаритми, отчетена със знак минус.

Ако n е броят на възможните стойности на случайната величина X то ентропията й има максимална стойност,
когато вероятностите на възможните стойности на X са едни и същи и са равни на 1/n.

Ентропията е мярка на неопределеността.
Това понятие е въведено в теорията на информатиката от нейния основател – Клод Шенон.
Осъзнавайки важността на величината

той се е обърнал към математическия корифей Джон фон Нейман с молба да го посъветва за името.
Джон фон Нейман отговорил: „Трябва да го наречеш „ентропия” по две причини:
първо – такова понятие под това име вече съществува в термодинамиката,
второ и по-важно – много от хората не разбират какво представлява всъщност ентропията,
и когато използваш това понятие в спор ти винаги ще го печелиш. ” ^{( 6 )} Изчисляването на ентропията е показано на тази страница. http://ek.roncho.net/Factory/HighMath3/Prob/Calculators/RandomVarsCalc.html

Закон за декомпозицията ( разлагането )

Нека наборът от вероятности (със сума 1)

е разделен на два набора със суми S₁ и S₂ .

Тогава наборите

са такива от вероятности, в смисъл че те се състоят от неотрицателни числа със сума 1.
При тези условия е в сила законът за декомпозицията ^{( 5 )}:

Функцията H е дефинирана за набор от неотрицателни числа (не непременно със сума единица ).
За нея са в сила свойствата:

Тогава, в условията на постановката на теоремата: Използваме свойствата на H(p) _3UsingOfProprty

Съвместна ентропия на две независими разпределения

Нека X и Y са случайни величини, заемащи съответно n и m стойности. Закон на разпределение на случайна величина _2ProbDistributin1

Закон на разпределение на случайна величина _4ProbDistributin1

Да образуваме нова, двумерна случайна величина (X, Y).
Съвместна ентропия се нарича величината

От формулата за условна вероятност (X,Y) ще има закон на разпределение P(X=X_i, Y=Y_j) = P(X=X_i). P(Y=Y_j / X=X_i) Условните вероятности не могат да бъдат изведени от законите на разпределение на X и Y, но ако случайните величини са независими то P(X=X_i, Y=Y_j) = p_i. q_j .
Като използваме означенията p_i и q_j за вероятностите за съвместната ентропията получаваме

Да пресметнем съвместна ентропия в случай на независими X и Y.
Ще покажем, че в този случай H(X, Y)= H(X)+H(Y)

Събираемите в матрица _4SumandsInMatrix1

Трябва да съберем всички n.m на брой събираеми.
Да съберем елементите от първия ред: Сумата в първия ред _4SumandsOfTheFirsttRow1

В първите скоби сумата е 1 защото q_j образуват набор.
Във вторите скоби си получава ентропията H(Y) със знак минус.
За сумата на събираемите от първия ред получаваме:

Подобно се получава, че сумата на елементите от i-тия ред е

Съвместна ентропия на две зависими разпределения
Средна условна ентропия

В случай, че X и Y не са независими се получава H(X, Y)= H(X) + E_X(H_Y(Y/X=X_i)).
Ще поясним второто събираемо
H_Y(Y/X=X_i) е ентропията на Y при условие , че X има стойност X_i .
Получената случайна величина ще зависи само от i.

Този израз ще наричаме условна ентропия на Y при условие X=X_i и ще го означим с h(i).
Тогава:

Тази величина се нарича средна условна ентропия на Y при условие X. Означава се и със символа H_X(Y) или с H(Y/X).
А сега да докажем равенството: H(X, Y)= H(X) + E_X(H_Y(Y/X=X_j))
То може словесно да се изкаже така:
Съвместната ентропия на две случайни величини X и Y е равна на ентропията на X плюс средната условна ентропия на Y при условие X^{( 2 )}.

За съвместната вероятност P(X=X_i,Y=Y_j) имаме:
P(X=X_i,Y=Y_j) = P(X=X_i). P(Y=Y_j /X=X_i) = p_i . P(Y=Y_j /X=X_i)
Условната вероятност ще означим с q_j/i .
Получаваме: P(X=X_i,Y=Y_j) = P(X=X_i). P(Y=Y_j /X=X_i) = p_i . P(Y=Y_j /X=X_i) = p_i . q_j/i .

Да подредим събираемите от двойната сума в таблица, както преди: Събираемите в матрица _5SumandsInMatrix

и да съберем по редове.
За първия ред получаваме: Сборът в първия ред _5SumInTheFirstRow

В първите скоби сумата е 1 защото q_j/1 образуват набор от неотрицателни числа със сума 1.
Във вторите скоби се получава условната ентропия на Y при условие X=X₁ със знак минус.
За сумата на събираемите от първия ред получаваме окончателно:

Подобни изрази се получават и за останалите редове.
Събирайки ги получаваме H(X, Y)= H(X) + E_X(H_Y(Y/X=X_i)) = H(X) + H_X(Y)

Да напишем отново израза за средна условна ентропия на Y спрямо X . Средна условна ентропия _5MiddleConditionalEntropy2

Ще докажем важното неравенство:

И още един път:

H_X(Y) ≤ H(Y)

При доказателството ще използваме това, че функцията y = f(x) = -x.lnx е вдлъбната.

За фиксирано j Средна условна ентропия _5MiddleConditionalEntropy3_1

От формулата за пълната верятност сумата в скобите е q_j .
Събирайки получените неравенства по индекса j получаваме търсеното.

Тогава разликата I ( X,Y )=H( Y ) - H_X( Y ) е неотрицателна.
Тя се нарича информация, получена от опита X за Y.
Информацията показва, доколко осъществяването на опита X намалява неопределеността на опита Y.

^{( 7 )}
Клод Шанън (30 април 1916 – 24 феврруари 2001)
Американски математик, електронен инжинер и криптограф , известен като „баща на теорията на информацията”