Elements of underdetermined information theory.pdf ВведениеМетоды эффективного использования недоопределенной информации важны длямногих разделов информатики. С недоопределенными данными имеют дело в задачахраспознавания, управления, принятия решений, логического синтеза схем, сжатияи передачи данных, криптографии, генетики. Разнообразные применения указываютна целесообразность изучения недоопределенных данных в качестве самостоятельногообъекта подобно тому, как это делается в теории информации для полностью определенныхданных. Это предполагает создание единой системы понятий, введение и исследованиеинформационных характеристик недоопределенных данных, развитие и модификациюприменительно к ним принципов, методов и результатов классической теорииинформации, выявление закономерностей, характерных только для недоопределенныхданных, создание исчисления для формального преобразования выражений с участиемразных информационных характеристик, изучение эквивалентных преобразованийнедоопределенных данных, разработку теоретически обоснованных алгоритмов обращенияс ними.Ниже приводятся результаты, полученные в этих направлениях. Как будет видно,некоторые результаты и методы теории информации переносятся на недоопределен-ные данные, некоторые модифицируются соответствующим образом, а в некоторыхслучаях возникают новые эффекты. Установленные факты оказались полезными приисследовании задач, связанных с синтезом схем [12], процедурами голосования [14],распознаванием текстов [15].1. Нед ооп р ед ел енные данные и их энтропияПод недоопределенными данными будем понимать последовательности недоопреде-ленных символов. Каждому из них соответствует некоторое множество символов основногоалфавита, одним из которых он может быть замещен (доопределен). Дадимформальные определения.Пусть M = { 0 ,1 ,... , m - 1} - некоторое множество и каждому непустому подмножествуT С M сопоставлен символ а т . Алфавит всех символов ат обозначим черезA, а его подалфавит {а 0, a i , . .. , ат - 1 }, символы которого соответствуют элементаммножества M ,-через А0. Символы из А0 будем называть основными, из A - недо-определенными. Доопределением символа ат . A назовем всякий основной символ аг,i . T , а доопределением последовательности в алфавите A - любую последовательностьв алфавите A0, полученную из исходной заменой всех ее символов некоторымидоопределениями. Символ ам , доопределимый любым основным символом, играетособую роль. Его будем называть неопределенным и обозначать *.Пусть имеется источник X , порождающий символы ат . A независимо с вероятностямиp(aT) ^ 0, ^2тр(ат ) = 1. Набор вероятностей (р(ат ), T С M ) обозначим черезP и для источника X будем использовать обозначение (A ,P ). Такой источник будемназывать недоопределенным, а при выполнении условия р (а т) = 0 для ат . А0 - полностьюопределенным. В случае р(а т) = 0 для ат . A0 U { * } источник называетсячастично определенным. Подчеркнем, что мы различаем термины «недоопределен-ный» и «частично определенный». Иногда вместо обозначения (A, P ) источника Xбудем использовать (A;, P ;), где алфавит А; получен из A удалением всех или некоторыхсимволов ат с р (а т) = 0, а P' образован из P удалением соответствующих нулевыхкомпонент. В этих обозначениях полностью определенный источник может быть записанкак (A0, (p0, . . . , pm-1)), а частично определенный - как (A0 U { * }, (p0, . . . , pm-1, p*)),где обозначения pi и p* использованы вместо р(а^) и p(*) = р (ам ).Зададимся некоторым набором вероятностей Q = (qi, i . M ) символов аг . A0(?г ^ 0, q0 + ... + qm-1 = 1) и введем функциюЗдесь и дальше логарифмы двоичные. Энтропией источника X назовем величинуНаряду с H (P ) будем использовать обозначение H (X ). Указанная формула энтропиибыла предложена М. М. Бонгардом [1, с. 92] из некоторых эвристических соображенийв качестве меры неопределенности задач с несколькими ответами.Для полностью определенного источника (A0, (p0, . .. , pm-1)), в силу известного соотношения(q0v ,qm-1) i iвеличина H (P ) совпадает с энтропией Шеннона H (P ) = - ^ г pi logpi. Вместо источниковможно говорить об энтропии случайных опытов с недоопределенными исходами.2. Вычисление энтропииЭнтропия недоопределенного источника задана неявно, как минимум по Q функции(1). Для нахождения точек минимума полезен следующий критерий.Теорем а 1. Набор вероятностей Q минимизирует функцию H(P, Q) тогда и толькотогда, когда при каждом i, i . M , выполненоH (P ,Q) = - p (^ ) log X ! qi. (1)т CMH (P ) =m in H(P ,Q ). (2)(3)j-етгде строгое неравенство может иметь место лишь при тех i, для которых qi = 0.Д ок а зател ьст в о . Вогнутая по Q функция -H(P, Q) удовлетворяет условиямтеоремы 4.4.1 из [3]. По этой теореме необходимым и достаточным условием ее максимумав точке Q является существование такого Л, что -dH(P, Q )/dqi ^ Л, i G М ,где строгие неравенства могут соответствовать лишь нулевым значениям q^ В нашемслучае эти соотношения приобретают видlog e . ^ « Л, i G М. (5)т : ieT 2_^ qjj€TПоскольку равенства могут нарушаться лишь при нулевых qi, домножив на qi, получаемравенствар(ат )qi Л . ^ Л/Г Гг> = ;------- q^ i G М. (6Л)т^Тт . qj log ejeTПросуммировав их по i G М с учетом У т р (а т) = ^ i qi = 1 и того, что. qi. . p M * = . р(ат ) = . р Ы ,ieM т : ieT _2 _^ qj т _2_^ qj тjeT j-етнаходим, что Л = log e. Подставив значение Л в (5), получаем требуемое утверждение.^На базе этой теоремы может быть указан численный метод нахождения H (P ) [9].Введем оператор Q = U(Q), сопоставляющий набору Q = (q0, q i,. .. , qm-1) наборQ/ = (q0, qi, . . . , qm-1), гдеqi = , i = 0, 1, . . . ,m - 1.* т : ieJ j.-ет qjНетрудно проверить непосредственно, что оператор U переводит наборы вероятностейв наборы вероятностей. Домножив обе части (4) на qi и учитывая, что строгое неравенствов (4) может иметь место лишь при qi = 0, получаем равенстваР(ат )qi . ^ Л/Г ^2 ^ - = qi, i G M, (7)т : ieт qjj-етозначающие, что минимизирующий набор Q является неподвижной точкой оператораU. Приведем без доказательства утверждение из [9], дающее алгоритм вычисленияH (P ).Теорем а 2. Если Q(0) = (q00), ... , q((0-1) - произвольный набор вероятностей с положительнымикомпонентами и Q(v) = U (Q(v-1)), v = 1, 2, . . . , то при v ^ то последо-р («т )qiвательность H(P, Q(v)) сходится к H (P ).Таким образом, нахождение численного значения энтропии трудностей не вызывает.В некоторых содержательно важных случаях может быть получено явное выражениеэнтропии. Это относится, например, к частично определенным источникам,энтропия которых может быть найдена на основе следующего утверждения.Теорем а 3. Имеет место равенствоH (P ) = (1 - p (* ))H (P '),где P' = (p'(ат), T С M ) (включение строгое) - набор, полученный из P = ^ (а т ),T С M ) отбрасыванием компоненты p ^M ) = p(*) и пересчетом вероятностей p/(aт) == p ^ )/(1 - p (*) ) .Д ок а зат ел ьст в о . Для любого набора вероятностей Q = (qi, i . M ) выполненоlog EieM qi = 0, поэтому- E p k )lo g E qi = -(1 -p (*)) E ^ ^ log E qi.тем ieт т ем p( ) ieтВзяв минимум по Q, получаем нужное утверждение. ■С л ед стви е 1. Энтропия частично определенного источника X = (A0U{*}, (p0, . .. ,pm-1,p*)) задается выражениемh ( x ) = ( 1 -p*)H ( po , . . . , ,p: 1 ) = ( 1 -p*)lo g ( 1 -p*) - е pi logpi1 p 1 p 0 0 , непусто.Д ок а зат ел ьст в о . Неотрицательность очевидна. Пусть минимум H(P, Q) в (2)достигается на наборе Q0. Положим T 0 = {i . M | q0 > 0}. Если H (P ) = H(P, Q0) = 0,то для любого T с р (а т) > 0 выполнено У teT q° = 1, а потому T содержит T 0 ипересечение всех таких T непусто. Обратно, если пересечение непусто, то, назначивqi = 1 для некоторого i из этого пересечения и qj = 0 для всех j = i , получим набор Q ,для которого H(P, Q) = 0. ■Таким образом, энтропия H (X ) недоопределенного источника X равна 0, лишь еслипорождаемые им последовательности могут быть доопределены до последовательностейиз одинаковых символов. Этот факт обобщает известный результат для полностьюопределенного источника, энтропия которого равна 0 , лишь если он порождает последовательности,образованные одинаковыми символами.Укажем верхнюю границу энтропии источника X = (A, P ) в функции от распределения(p(t), 1 ^ t ^ m) числа t доопределений символов источника:Д ок а зател ьст в о . Эту оценку получим, вычислив H(P, Q) на наборе Q == (1/m , . . . , 1/m),Оценка достигается на наборе P , в котором всем t-элементным множествам T со-рии [3] следует, что в этом случае H(P, Q) минимизируется набором вероятностейq0 = . .. = qm-1 = 1/m. ■Если источник полностью определен, то p(1) = 1, p(t) = 0 для t ^ 2, и оценкатеоремы превращается в известную оценку H (P ) ^ log m.Теорем а 11. Функция H (P ) вогнута, т. е. для любых P = (p(aT), T С M ), P' == (p;(aT), T С M ) и числа а, 0 ^ а ^ 1, выполненоT: |T|=tТеорем а 10. Справедлива оценкаH (P ) ^ log m - Е P(t)log t1

Скачать электронную версию публикации