Какво трябва да знаем:     Условна вероятност   Основни неравенства в теорията на информацията   Теория на информацията

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

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

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

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

Ентропия

Информацията за елементарно събитие се определя като логаритъм от реципрочната стойност на вероятността на събитието при основа 2:
Информация на елементарно събитие _2InformationOfElEvent
Измерва се в битове.
Ако основата е друга – 10 или Неперовото число (e) мерните единици за информация се наричат съответно „дит” и „нат”.
Преходът от едни единици към други се осъществява с един коефициент, който се определя от формулата: logBA= logaA/ logaB
Ще считаме че логаритмите са натурални.
Средната стойност на информацията на елементарните събития се нарича ентропия.
Ентропия _2Entropy1

Ако X е случайна величина със закон на разпределение
Закон на разпределение на случайна величина _2ProbDistributin1
нейната ентропия е сума от вероятностите по логаритъма от тях, отчетена със знак минус ( 3 ).
Ентропия на разпределение _2Entropy2
Тя е неотрицателна величина, защото вероятностите са по-малки от 1.
Ако вероятносттта е нула считаме, че 0.ln0=0, защото Граница _2Limit1
Ентропията не зависи от стойностите на случайната величина а от техните вероятности.
Затова можем да я считаме като функция на набор от неотрицателни числа със сума 1:
Ако наборът p се състои от неотрицателни числа със сума 1 то неговата ентропия е сумата от произведенията им по техните логаритми, отчетена със знак минус.
Ентропия на набор от неотрицателни числа със сума 1 _2Entropy3
Ако n е броят на възможните стойности на случайната величина X то ентропията й има максимална стойност,
когато вероятностите на възможните стойности на X са едни и същи и са равни на 1/n.
Максимална ентропия _2MaxEntropy
Ентропията е мярка на неопределеността.
Понятието „ентропия” е въведено в теорията на информатиката от нейния основател – Клод Шенон.
Осъзнавайки важността на величината       Израз за ентропията _2EntrophyFormula той се е обърнал към математическия корифей Джон фон Нейман с молба за съвет за подходящо име на това ново понятие.
Джон фон Нейман отговорил: „Трябва да го наречеш „ентропия” по две причини:
първо – такова понятие под това име вече съществува в термодинамиката,
второ и по-важно – много от хората не разбират какво представлява всъщност ентропията,
и когато използваш това понятие в спор ти винаги ще го печелиш. ” ( 6 ) Изчисляването на ентропията е показано на тази страница. http://ek.roncho.net/Factory/HighMath3/Prob/Calculators/RandomVarsCalc.html

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

Нека наборът от вероятности (със сума 1)         Начален набор от вероятности _3Suit1         е разделен на два набора със суми S1 и S2 .
Разлагането на два набора _3Suit2

Тогава наборите         Наборите с прим са такива от вероятности ( нормирани ) _3Suit3         са такива от вероятности, в смисъл че те се състоят от неотрицателни числа със сума 1.
При тези условия е в сила законът за декомпозицията ( 5 ):
закон за декомпозицията _3LowOfDecomposition


Функцията H е дефинирана за набор от неотрицателни числа (не непременно със сума единица ).
За нея са в сила свойствата:
Докажете ги сами! _3ProofAlone
Тогава, в условията на постановката на теоремата:
Използваме свойствата на H(p) _3UsingOfProprty

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


Нека X и Y са случайни величини, заемащи съответно n и m стойности.
Закон на разпределение на случайна величина _2ProbDistributin1
Закон на разпределение на случайна величина _4ProbDistributin1
Да образуваме нова, двумерна случайна величина (X, Y).
Съвместна ентропия се нарича величината
Съвместна ентропия  _4JontEntropy1

От формулата за условна вероятност (X,Y) ще има закон на разпределение
P(X=Xi, Y=Yj) = P(X=Xi). P(Y=Yj / X=Xi)
Условните вероятности не могат да бъдат изведени от законите на разпределение на X и Y, но ако случайните величини са независими то P(X=Xi, Y=Yj) = pi. qj .
Като използваме означенията pi и qj за вероятностите за съвместната ентропията получаваме
Съвместна ентропия  _4JontEntropy2

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

Събираемите в матрица _4SumandsInMatrix1
Трябва да съберем всички n.m на брой събираеми.
Да съберем елементите от първия ред:
Сумата в първия ред _4SumandsOfTheFirsttRow1
В първите скоби сумата е 1 защото qj образуват набор.
Във вторите скоби си получава ентропията H(Y) със знак минус.
За сумата на събираемите от първия ред получаваме:
Без отчитане на началния минус _4WithoutMinus1

Подобно се получава, че сумата на елементите от i-тия ред е Без отчитане на началния минус _4WithoutMinus1_1 Окончателно _4AtLast

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

В случай, че X и Y не са независими се получава H(X, Y)= H(X) + EX(HY(Y/X=Xi)).
Ще поясним второто събираемо
HY(Y/X=Xi) е ентропията на Y при условие , че X има стойност Xi .
Получената случайна величина ще зависи само от i.
Условна ентропия на Y при условие X=Xi    _5ConditionalEntropy
Този израз ще наричаме условна ентропия на Y при условие X=Xi и ще го означим с h(i).
Тогава:
Средна условна ентропия _5MiddleConditionalEntropy1

Този израз ще наричаме средна условна ентропия на Y при условие X.       Означава се и със символа HX(Y)
А сега да докажем равенството: H(X, Y)= H(X) + EX(HY(Y/X=Xj))
То може словесно да се изкаже така:
Съвместната ентропия на две случайни величини X и Y е равна на ентропията на X плюс средната условна ентропия на Y при условие X ( 2 ).

Съвместна ентропия _5JointEntropy1

За съвместната вероятност P(X=Xi,Y=Yj) имаме:
P(X=Xi,Y=Yj) = P(X=Xi). P(Y=Yj /X=Xi) = pi . P(Y=Yj /X=Xi)
Условната вероятност ще означим с qj/i .
Получаваме: P(X=Xi,Y=Yj) = P(X=Xi). P(Y=Yj /X=Xi) = pi . P(Y=Yj /X=Xi) = pi . qj/i .
Просто заместване _5SimpleSubstitution1

Да подредим събираемите от двойната сума в таблица, както преди:
Събираемите в матрица _5SumandsInMatrix
и да съберем по редове.
За първия ред получаваме:
Сборът в първия ред _5SumInTheFirstRow
В първите скоби сумата е 1 защото qj/1 образуват набор от неотрицателни числа със сума 1.
Във вторите скоби се получава условната ентропия на Y при условие X=X1 със знак минус.
За сумата на събираемите от първия ред получаваме окончателно:
Сборът в първия ред на матрицата без началния минус _5WithoutInitialMinus
Подобни изрази се получават и за останалите редове.
Събирайки ги получаваме H(X, Y)= H(X) + EX(HY(Y/X=Xi)) = H(X) + HX(Y)

Да напишем отново израза за средна условна ентропия на Y спрямо X . Средна условна ентропия _5MiddleConditionalEntropy2
Ще докажем важното неравенство:         Неравенство _5InEquality1 И още един път:

HX(Y) ≤ H(Y)

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

Средна условна ентропия _5MiddleConditionalEntropy3

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

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

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

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

Литература

Какво ще научим:
                 

Теория на вероятностите