Содержание к диссертации
Введение
Глава 1. Сущность и особенности задач обработки числовых квазипериодических последовательностей 7
1.1. Современное состояние проблемы обработки числовых последовательностей 7
1.2. Задача обнаружения 12
1.3. Задача совместного обнаружения и различения 13
1.4. Задача распознавания кодовых слов 15
1.5. Выводы 18
Глава 2. Апостериорное обнаружение одинаковых фрагментов 20
2.1. Постановка задачи 20
2.2. Обнаружение как задача проверки гипотез о среднем 22
2.3. Функция правдоподобия и целевая функция 24
2.4. Алгоритм обнаружения 26
2.5. Мощность множества проверяемых гипотез 41
2.6. Временная и емкостная сложность алгоритма 44
2.7. Численное моделирование 49
2.8. Выводы 51
Глава 3. Апостериорное совместное обнаружение и различение фрагментов 54
3.1. Постановка задачи 54
3.2. Совместное обнаружение и различение как задача проверки гипотез о среднем 56
3.3. Функция правдоподобия и целевая функция 57
3.4. Алгоритм совместного обнаружения и различения 59
3.5. Временная и емкостная сложность алгоритма 61
3.6. Численное моделирование 63
3.7. Выводы 66
Глава 4. Распознавание кодовых слов, скрытых в числовых квазипериодических последовательностях 68
4.1. Постановка задачи 68
4.2. Распознавание кодовых слов как задача проверки гипотез о среднем 70
4.3. Функция правдоподобия и целевая функция 72
4.4. Алгоритм распознавания 74
4.5. Временная и емкостная сложность алгоритма 93
4.6. Численное моделирование 107
4.7. Выводы 109 Заключение 112
Приложение
Литература 126
- Задача совместного обнаружения и различения
- Обнаружение как задача проверки гипотез о среднем
- Совместное обнаружение и различение как задача проверки гипотез о среднем
- Распознавание кодовых слов как задача проверки гипотез о среднем
Задача совместного обнаружения и различения
Второй из ключевых задач обработки квазипериодических последовательностей является задача совместного обнаружения и различения подпоследовательностей фрагментов. Так же как и в задаче обнаружения, рассмотренной в предыдущем параграфе, для наблюдения доступна сумма уп = хп + єп, п = О,N -1, где хп, n=0,N -\, — ненаблюдаемая квазипериодическая последовательность, включающая неизвестное число подпоследовательностей-фрагментов, a (SQ, ..., дг_і)є Ф г — аддитивная помеха. Однако, в отличие от задачи обнаружения, в данном случае подпоследовательности-фрагменты, составляющие квазипериодическую последовательность, могут быть различны и являются элементами заданного алфавита. Задача совместного обнаружения и различения состоит в том, чтобы по доступным для наблюдения данным, во-первых, определить неизвестное число М фрагментов в последовательности и номера п\,..., п членов последовательности, соответствующих началам фрагментов (обнаружение фрагментов); во-вторых, классифицировать каждый из обнаруженных фрагментов как элемент алфавита (различение). Физическим аналогом ненаблюдаемой последовательности может служить импульсная последовательность, образованная импульсами нескольких типов, с ограничениями на интервал между моментами времени начал двух последовательных импульсов.
Для примера в верхней части рис. 1.2 изображена ненаблюдаемая квазипериодическая последовательность, включающая 5 фрагментов из алфавита, состоящего из двух эталонных последовательностей. В нижней части этого же рисунка изображена наблюдаемая последовательность уп, n-0,N-\.
Эту задачу, как и задачу обнаружения, можно рассматривать как специфическую (разладка носит квазипериодический характер) задачу о разладке случайной последовательности. От классических постановок ее отличает необходимость классифицировать каждую из обнаруженных (начинающихся в момент произошедшей разладки) подпоследовательностей-фрагментов как элемент заданного алфавита последовательностей. Таким образом, возникает необходимость решать совместно задачи обнаружения и классификации. Как показано в параграфе 1.1, класс подобных задач (классификация несинхронизированных данных) недостаточно хорошо изучен. Возможны два подхода к решению поставленной задачи.
Первый подход состоит в решении возникающих подзадач (обнаружения и различения) последовательно. Второй, альтернативный подход состоит в решении обеих задач одновременно. В последнем случае решение задач обнаружения и различения объединено в единый процесс. Проанализируем оба подхода.
В случае первого подхода (последовательное решение подзадач) работа алгоритма разбивается на два этапа. Первый этап состоит в решении задачи обнаружения и, очевидно, должен базироваться на методах обнаружения изменения свойств временных рядов (методах обнаружения разладки случайных последовательностей). Тогда на втором этапе производится классификация каждой из обнаруженных подпоследовательностей как элемента заданного алфавита, то есть решается задача различения. Для этой цели можно воспользоваться классическими методами распознавания. Краткий обзор алгоритмов, использующихся для решения задачи обнаружения и задачи классификации, приведен в п. 1.1.
В рамках второго подхода, задачи обнаружения и различения решаются одновременно, то есть решается задача классификации несинхронизированных по времени данных. Как уже отмечалось, алгоритмы решения подобных задач изучены слабо. В п. 1.1. были выделены два возможных направления решения поставленной задачи. Одним из вариантов является построение многопроходового алгоритма, опирающегося на многократное применение известного алгоритма [147] совместного обнаружения и различения известного числа подпоследовательностей-фрагментов в квазипериодической последовательности. Вторым, более предпочтительным, направлением решения является разработка однопроходового алгоритма (такого алгоритма до настоящего времени не существовало).
Таким образом, построение точного однопроходного алгоритма апостериорного типа для решения задачи совместного обнаружения и различения неизвестного числа подпоследовательностей-фрагментов является важной и до настоящего времени не решенной задачей обработки сигналов.
Третьей и наиболее сложной из рассматриваемых задач обработки является задача распознавания кодовых слов, скрытых от наблюдения в числовых квазипериодических последовательностях, включающих неизвестное число подпоследовательностей-фрагментов. В данной задаче, как и в рассмотренной ранее задаче совместного обнаружения и различения, ненаблюдаемая квазипериодическая последовательность хп, n = 0,N -\, включает в себя подпоследовательности-фрагменты, принадлежащие заданному алфавиту эталонных последовательностей. Однако, если в задаче совместного обнаружения и различения порядок следования фрагментов мог быть произвольным, то в задаче распознавания кодовых слов ненаблюдаемая квазипериодическая последовательность имеет более сложную структуру. Порядок следования фрагментов задается с помощью кодового слова w — упорядоченного набора эталонных последовательностей — принадлежащего фиксированному словарю W. Каждой квазипериодической последовательности можно сопоставить единственное кодовое слово из словаря. Каждому кодовому слову w є W соответствует множество квазипериодических последовательностей хп, n-0,N-\, содержащих однородные участки — серии одинаковых подпоследовательностей-фрагментов, причем каждый элемент кодового слова порождает собственную серию одинаковых подпоследовательностей-фрагментов в квазипериодической последовательности, а порожденные серии упорядочены так же, как и элементы кодового слова. Для наблюдения доступна сумма уп=хп+єп, n = 0,N-\, ненаблюдаемой квазипериодической последовательности хп, n = 0,N-\, и аддитивной гауссовской помехи (о,..., дг_і)є Ф0 г,, Задача распознавания состоит в том, чтобы по наблюдаемой последовательности уп, n = 0,N-\, определить кодовое слово weW, которое сопоставляется ненаблюдаемой последовательности хп, п = О, N -1.
Обнаружение как задача проверки гипотез о среднем
В целом, данные численного моделирования свидетельствуют о высокой помехоустойчивости алгоритма.
В главе 2 изложено решение задачи оптимального (максимально-правдоподобного) обнаружения неизвестного числа одинаковых подпоследовательностей-фрагментов в квазипериодической последовательности, искаженной некоррелированной гауссовской аддитивной помехой, в предположении, что моменты времени начала подпоследовательностей-фрагментов являются детерминированными (неслучайными) величинами. Решение задачи включает в себя статистическую постановку задачи (п. 2.1, 2.2); вывод целевой функции (п. 2.3); построение и обоснование апостериорного вычислительного алгоритма (п. 2.4); оценивание мощности множества проверяемых гипотез (п. 2.5); оценивание трудоемкости алгоритма (п. 2.6) и описание результатов численного моделирования (п. 2.7).
Показано, что для корректной постановки задачи обнаружения параметры задачи должны быть увязаны между собой. Эта связь, в виде ограничений, устанавливается в леммах 2.2.1-2.2.3 и утверждении 2.2.1. Эти же результаты позволяют интерпретировать задачу обнаружения как специфическую задачу проверки совокупности простых гипотез о среднем случайного гауссовского вектора. При этом наблюдаемый случайный вектор рассматривается как выборка из семейства нормальных распределений. Специфика задачи состоит в том, что: 1) указанное семейство распределений порождается множеством таких векторов средних значений, компоненты которых образуют всевозможные квазипериодические последовательности, составленные из неизвестного числа одинаковых подпоследовательностей-фрагментов; 2) мощность семейства распределений растет экспоненциально с ростом размерности вектора средних (анализ мощности семейства приведен в п. 2.5, леммы 2.5.1-2.5.3). Ввиду экспоненциальной мощности множества проверяемых гипотез, прямой перебор этой совокупности гипотез не представляется возможным.
В ситуации, когда априорное распределение на множестве проверяемых гипотез не определено, для построения вычислительного алгоритма был использован критерий максимального правдоподобия. Показано (лемма 2.3.1), что максимизация функции правдоподобия и поиск аргументов (искомых моментов времени начала подпоследовательностей-фрагментов), доставляющих этот максимум, сводится к решению задачи минимизации сепарабельной целевой функции с ограничениями в виде линейных неравенств. Леммы 2.4.1-2.4.5, теоремы 2.4.1, 2.4.2 и следствия 2.4.1-2.4.8 обосновывают вычислительный алгоритм решения задачи минимизации. Фактически эти результаты дают решение более общей экстремальной задачи, при этом естественные обобщения касаются лишь системы неравенств-ограничений, вид целевой функции при обобщении не изменился. При построении вычислительного алгоритма были реализованы оба подхода к решению задачи, отмеченные в первой главе, а именно: был построен многопроходовый алгоритм (теорема 2.4.1, следствия 2.4.1 и 2.4.3), основывающийся на имеющихся результатах, и новый однопроходовый (теорема 2.4.2, следствие 2.4.7). В результате анализа трудоемкости рассмотренных алгоритмов (следствия 2.6.1-2.6.4) оказалось, что построенный однопроходовый алгоритм дает существенный выигрыш по временным и емкостным затратам по сравнению с алгоритмом последовательного перебора по допустимым значениям числа подпоследовательностей-фрагментов. Из этих же результатов следует, что задача разрешима за время, полиномиально зависящее от длины обрабатываемой последовательности. И, наконец, результаты численного моделирования, приведенные в параграфе 2.7, свидетельствуют о высокой помехоустойчивости предложенного алгоритма.
Таким образом, построен и обоснован точный апостериорный вычислительный алгоритм решения задачи обнаружения неизвестного числа подпоследовательностей-фрагментов в квазипериодической последовательности, искаженной гауссовской помехой. Построенный алгоритм показывает, что первая из ключевых задач обработки квазипериодических последовательностей — задача обнаружения — полиномиально разрешима. В данной главе приведено обоснование и исследование апостериорного вычислительного алгоритма решения второй из ключевых задач обработки числовых квазипериодических последовательностей, а именно: задачи совместного обнаружения и различения подпоследовательностей-фрагментов в квазипериодической последовательности при наличии аддитивной помехи. Материалы данной главы опираются на работы [186,188,190,191].
Совместное обнаружение и различение как задача проверки гипотез о среднем
Как показано в предыдущем параграфе, ядром алгоритма совместного обнаружения и различения является решение экстремальной задачи (3.4.8), минимизации целевой функции F(rj) на множестве Q. В следствии 3.4.1 показано, что для вычисления минимума Fи определения оптимального набора f) можно использовать алгоритм минимизации целевой функции G(y/) на множестве Т. Временная и емкостная сложность этого алгоритма определена в следствии 2.6.3. Воспользуемся этим результатом для определения затрат по времени и памяти при реализацию алгоритма совместного обнаружения и различения.
Доказательство. В соответствии с леммой 3.4.1, алгоритм совместного обнаружения и различения состоит из двух этапов: 1) условное различение подпоследовательностей и 2) безусловное обнаружение и различение подпоследовательностей. Определим временную сложность реализации первого этапа алгоритма.
При каждом фиксированном ie{0,---,N-q} для вычисления значений пары функций d{i) и r(i) по формулам (3.4.3), (3.4.7) требуется О(К) элементарных операций. Поэтому для вычисления всех N-q + \ значений этих функций потребуется 0[K(N-q + l)J операций. Кроме того, для каждой фиксированной пары ie{0,---,N -q) и U е А вычисление значения функции d(i\U) по формуле (3.4.4) сопряжено с выполнением O(q) операций. Следовательно, для вычисления всех Kx(N-q + l) значений функции необходимо произвести 0[Kq(N q + \)] элементарных операций. Таким образом, для временной сложности первого этапа алгоритма имеем 0[K(N-q + l)]+ 0[Kq{N-q + l)]= 0[Kq(N-q + l)].
Далее, в соответствии со следствиями 3.4.1 и 2.6.2, трудоемкость вычисления F и оптимального набора і) есть величина порядка (Ттах - Гт;п + \)(N - q +1). Для определения оптимальной последовательности элементов алфавита по формуле (3.4.6) потребуется порядка М N -q + \ элементарных операций. Суммируя временные затраты на двух этапах, получим
Оценим затраты по памяти. На первом этапе алгоритма для сохранения начальных данных требуется Kq + N ячеек памяти (Kq — для хранения элементов алфавита и N — для хранения компонент наблюдаемого вектора). Кроме того, для сохранения значений \\U\\ , U є А, потребуется К ячеек, так как А = ЛГ. Еще 0(N-q + l) ячеек потребуется для сохранения значений пары функции d(i) и г(/)для всех ie[0,---,N -q]. Наконец, при каждом ie{0,---,N-q) для вычисления значений функции d(i) и г(г ) по формулам (3.4.3), (3.4.4) и (3.4.7) требуется 3 ячейки обновляемой памяти. Итак, емкостная сложность первого этапа алгоритма есть величина 0(Kq + N) + 0(N-q + \)
Опираясь на следствия 3.4.1 и 2.6.3, для емкостной сложности второго этапа алгоритма имеем оценку 0(N-q + \). Окончательно, Cs = 0(N + Kq) + 0(N-q + \) =
Таким образом, несмотря на необходимость проверки совокупности гипотез, имеющей экспоненциальную мощность, алгоритм совместного обнаружения и различения дает оптимальное (максимально правдоподобное) решение за полиномиальное время.
При проведении численных экспериментов варьировались как алфавит А, уровень шума а, так и параметры алгоритма Гтах, 7 ,N и q. Каждая зашумленная последовательность Y, подлежащая обработке, формировалась в соответствии с формулой (3.1.4) путем поэлементного сложения значений сгенерированной квазипериодической последовательности X(rj,w) со значениями последовательности Е, сгенерированной с помощью гауссовского датчика случайных чисел. Наборы т] моментов времени начала подпоследовательностей, а так же эталонные векторы U из алфавита А выбирались с помощью датчика равномерно распределенных случайных чисел.
Иллюстративные материалы, приведенные ниже, были получены в результате серии экспериментов по совместному обнаружению и различению, когда алфавит эталонных последовательностей состоял из двух элементов, то есть А = { С/ , Л }. В качестве элементов алфавита служили последовательности иу =\, ujf =-1, п = 0,...,39, которые можно рассматривать как разнополярные прямоугольные импульсы; значения параметров алгоритма: N = 500, Гтах=200, 7 =50 и # = 40. На рис. 3.1 в качестве примера приведены результаты работы алгоритма. В верхней части рисунка изображена последовательность компонент неискаженной ненаблюдаемой квазипериодической последовательности X{rj,w), порожденной наборами 77 = (75,189,241,367) и w-{ U\ ,1 2 ,Щ ,U\ ). В нижней части рисунка изображена зашумленная (при т = 1) наблюдаемая последовательность компонент вектора Y; в виде серых прямоугольников нанесены результаты обнаружения и различения: 7? = ( 77, 184, 239, 367) и w-( Ul[ , U2 , U2 , Uл ) Для наглядности, результаты обнаружения, в виде прямоугольных рамок нанесены и на верхнюю часть графика. Алгоритм точно определил число (4) эталонных подпоследовательностей и правильно идентифицировал каждую из них. На этапе обнаружения имеется незначительная ошибка.
Распознавание кодовых слов как задача проверки гипотез о среднем
Для примера на рисунке 4.1 приведены результаты работы алгоритма распознавания (попутно были решены мешающие задачи обнаружения и разбиения). В верхней части рисунка изображена неискаженная ненаблюдаемая квазипериодическая последовательность компонент вектора X(w, rj, S), где w=w =([Л ,U )eW, j]-(33,144, 200, 378, 433), 5 = (2, 5). В нижней части рисунка совмещены изображения зашумленной (при а = 1) наблюдаемой последовательности компонент вектора Y, а так же, в виде заштрихованных прямоугольников, результат работы алгоритма.
Прямоугольники, расположенные выше горизонтальной оси, соответствуют подпоследовательностям-фрагментам первого типа, а ниже — второго; под прямоугольниками нанесены числа из оптимального набора 77 = (34,131,199, 377, 443). Кроме того, для наглядности, результаты обнаружения, в виде прямоугольных рамок, изображены и в верхней части рисунка. Сопоставив верхний и нижний графики можно заметить, что, несмотря на наличие ошибки обнаружения, алгоритм точно распознал зашифрованное кодовое слово vr є W, точно определил число М = 5 подпоследовательностей-фрагментов в квазипериодической последовательности и правильно произвел разбиение. Очевидно, что при увеличении уровня помехи могут возникнуть ошибки распознавания. Естественно характеризовать точность алгоритма распознавания в терминах вероятности ошибочной классификации. Как отмечалось в параграфе 4.2, задачу распознавания можно интерпретировать как задачу проверки совокупности гипотез (4.2.6), поэтому алгоритм распознавания можно рассматривать как отображение (решающее правило) ср : 91 - {H(w), w є W) пространства 91 значений случайного вектора Y на совокупность (4.2.6) проверяемых гипотез.
Тогда вероятность ошибки распознавания На рисунке 4.2 приведен график оценки а вероятности ошибки распознавания а от уровня помехи а. Оценка получена при моделировании байесовской процедуры принятия решений. Априорные вероятности кодовых слов предполагались равными. Нетрудно заметить, что введение весовых коэффициентов в случае не совпадающих априорных вероятностей гипотез не представляет вычислительной сложности. В условиях равных априорных вероятностей распознаваемых кодовых слов, общее число V выборок (сгенерированных квазипериодических последовательностей, искаженных гауссовской помехой) было разбито на две группы — по V12 выборок в каждой. В первую группу попали выборки, порожденные кодовым словом мг е W, во вторую — кодовым словом w(2) є и/, Подсчет вероятности ошибочного распознавания был проведен по формуле d = (V\+V2)/2, где V\ и 2 — число неправильно распознанных выборок соответственно в первой и второй группах. При проведении эксперимента рассматривались V = 5000 выборок (по 2500 выборок на каждое кодовое слово), таким образом, каждая точка экспериментальной кривой при различных значениях уровня помехи была получена по 5000 выборок. В данной главе диссертационной работы рассмотрена задача распознавания кодовых слов, скрытых от наблюдения в порожденных квазипериодических последовательностях. При постановке задачи предполагается, что ненаблюдаемая квазипериодическая последовательность включает неизвестное число подпоследовательностей-фрагментов, принадлежащих заданному алфавиту эталонных последовательностей, которые упорядочены в соответствии с элементами кодового слова, принадлежащего заданному словарю. Кроме того, предполагается, что ненаблюдаемая последовательность искажена аддитивной гауссовской помехой с известной дисперсией. От классических задач распознавания поставленную задачу отличает необходимость совместно с задачей распознавания решать сопутствующие мешающие задачи обнаружения и разбиения (выделение серий фрагментов, соответствующих букве кодового слова). Так же как и в предыдущих главах, решение задачи включает в себя пять основных этапов: статистическая постановка задачи (п. 4.1, 4.2), вывод целевой функции (п. 4.3), построение и обоснование вычислительного алгоритма (п. 4.4), анализ зависимости временных и емкостных ресурсов, необходимых для реализации алгоритма от параметров задачи (п. 4.5) и численное моделирование (п. 4.6). Показано, что для корректной постановки задачи задаваемые параметры должны быть увязаны между собой. Эта связь зафиксирована в леммах 2.2.1-2.2.3, 4.2.1 и утверждении 2.2.1. Для построения вычислительного алгоритма задача распознавания кодовых слов была проинтерпретирована как специфическая задача проверки совокупности простых гипотез о среднем случайного гауссовского вектора (п. 4.2). Заметим, что данная задача проверки гипотез обладает теми же специфическими особенностями, что и ее аналоги, рассмотренные в предыдущих главах.
Основную проблему при организации процесса вычислений представляет экспоненциальный рост мощности множества проверяемых гипотез с увеличением длины обрабатываемой последовательности, кроме того, мощность этого множества линейно зависит от числа кодовых слов в словаре. Результаты параграфов 4.4. и 4.5 показывают, каким образом эта проблема может быть решена за полиномиальное время. Поскольку априорное распределение на множестве проверяемых гипотез не определено, для построения вычислительного алгоритма, так же как и в предыдущих главах, был использован критерий максимального правдоподобия. Показано (лемма 4.3.1), что сущность алгоритма распознавания кодовых слов состоит в вычислении минимума вспомогательной целевой функции и определении аргументов, доставляющих этот минимум. Структуру алгоритма минимизации раскрывает лемма 4.4.1. Показано, что алгоритм минимизации распадается на два этапа. Первый этап — условное обнаружение и разбиение подпоследовательностей, второй — распознавание. При этом второй этап реализуется путем простого перебора и не представляет вычислительных проблем. Ядром же алгоритма является первый этап, состоящий в решении задачи поиска экстремума сепарабельной целевой функции с ограничениями в виде линейных неравенств. Рекуррентные формулы для ее решения следуют из теорем 4.4.1, 4.4.2, леммы 4.4.2 и следствий 4.4.1-4.4.6. Фактически, в перечисленных утверждениях решена более общая дискретная экстремальная задача (обобщение касается лишь системы неравенств-ограничений и не затрагивает вида целевой функции). Как отмечалось в главе 1, существуют два возможных подхода к построению алгоритма распознавания: разработка многопроходового алгоритма последовательного перебора по допустимым значениям числа подпоследовательностей и разработка однопроходового.
Реализация первого подхода зафиксирована в теореме 4.4.1 и следствиях 4.4.2, 4.4.3, второго — в теореме 4.4.2 и следствии 4.4.5. Анализ временной и емкостной сложности, проведенный в параграфе 4.5 (следствия 4.5.1-4.5.4), устанавливает, что задача распознавания кодовых слов полиномиально разрешима, при полиномиальных затратах по памяти. Кроме того, показано, что построенный однопроходовыи алгоритм дает существенный выигрыш по временным и емкостным затратам по сравнению с многопроходовым алгоритмом последовательного перебора по допустимым значениям числа фрагментов. Результаты численного моделирования, свидетельствующие о высокой помехоустойчивости предложенного алгоритма, завершают исследование поставленной задачи распознавания кодовых слов.
