Decomposition and approximation of underdetermined data.pdf Задан алфавит A0={a0 , a 1 , . . . , a m - 1 } основных символов. Пусть M = { 0 , 1 , . . . , m- 1}и каждому непустому T С M сопоставлен символ ay. Символы алфавита A = {ay :T С M} называются недоопределёнными, и доопределением символа ay . A считает-ся всякий основной символ ai , i . T. Символ aM, доопределимый любым основнымсимволом, называется неопределённым и обозначается *.Источник X, порождающий символы ay . A независимо с вероятностями py, на-зывается недоопределённым источником, а величинаH ( X ) = mini - Е Рт log Е Qi[,Q ^ т е м ieT J1 Работа выполнена при поддержке ОНИТ РАН по проекту 1.1 программы «Интеллектуальныеинформационные технологии, системный анализ и автоматизация».где logx = log2 x, минимум берется по наборам Q = (q^ i G M), qj ^ 0, ^ qj = 1,гемназывается его энтропией. Для недоопределённых данных эта величина играет рольэнтропии Шеннона [1].Источники X и Y будем называть равносильными и записывать X ~ Y, если длялюбого источника Z выполнено H ( X Z ) = H(YZ). Будем говорить, что источник X неслабее Y (Y не сильнее X ) , и записывать X ^ Y, если XY ~ X. Можно показать, чтоX ~ Y тогда и только тогда, когда X ^ Y и X ^ Y. Существуют эффективные (т. е.полиномиальные) алгоритмы проверки соотношений X ~ Y и X ^ Y. Преобразованияи отношения на множестве недоопределённых источников рассмотрены в [2].Под алфавитом A источника X будем понимать множество символов ат, для ко-торых рт > 0. Зададимся натуральным числом s и заменим в источнике X каждыйсимвол ат G A некоторым набором ат G {0,1, *}s . Полученный источник X будемрассматривать как произведение X1 . . . Xs источников, порождающих символы 0, 1и *, и будем называть разложением (соответствующим источнику X).Разложение X назовем декомпозицией источника X, если X ~ X. Разложение Xназовем аппроксимацией (нижней) источника X, если X ^ X и для всякого разложе-ния X', такого, что X' ^ X, выполнено X ^ X'. Очевидно, что если аппроксимациясуществует, она единственна с точностью до равносильности, и если декомпозициясуществует, аппроксимация является декомпозицией.Теорема 1. Для всякого недоопределённого источника аппроксимация существу-ет и может быть эффективно построена.Источник Xj , i = 1 , . . . , s, назовем устранимым из разложения Xi . . . Xs , еслиXi . . . Xs ~ Xi . . . X j - i X j + i . . . X s .Теорема 2. Существует эффективный алгоритм проверки устранимости источ-ника из разложения.Используя его, можно путём последовательного удаления устранимых источниковэффективно построить неизбыточную аппроксимацию (в частности, декомпозицию),из которой нельзя удалить ни одного источника без потери свойства быть аппрокси-мацией. Обобщением теоремы 2 является следующий факт.Теорема 3. Существует эффективный алгоритм проверки равносильности двухразличных разложений.Эта теорема позволяет сравнивать заданные разложения, но не даёт возможностиих порождать. Для порождения может быть использована система преобразований,гарантируемая следующей теоремой.Теорема 4. Существует (явно описана) полная система равносильных преобра-зований, позволяющая по всякому разложению построить любое равносильное емуразложение.Введём еще один вид декомпозиции. Рассмотрим разложение X = Xi . . . Xs,построенное по источнику X. Пусть, как и раньше, йт G {0,1, * } s означает набор, со-ответствующий символу ат G A, и пусть каждому символу аг G A0 приписан наборйг G {0,1}s . Наборы множества A0 = {йг : i G M} будем называть основными. Обозна-чим через {ат} множество доопределений набора йт и будем считать, что разложе-ние X порождает (с вероятностями рт > 0) множества {йт}. Ограничением разложе-ния XX на множество основных наборов назовем источник X^ , который порождает(с вероятностями py) множества {4y} П Ao. Скажем, что разложение XX образует де-композицию источника X на множестве основных наборов, если XA0 изоморфно X.Это означает, что { a T } П Ao = {ai : i . T }.Теорема 5. Для всякого недоопределённого источника существует и может бытьэффективно построена декомпозиция на множестве основных наборов.Число s источников в этой декомпозиции не превосходит min(|A|, |A0|), где | |означает мощность множества, и эта оценка по порядку неулучшаема.

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