ЗАДАЧИ ПОМЕХОУСТОЙЧИВОГО АНАЛИЗА И РАСПОЗНАВАНИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, ВКЛЮЧАЮЩИХ ПОВТОРЯЮЩИЕСЯ УПОРЯДОЧЕННЫЕ НАБОРЫ ВЕКТОР–ФРАГМЕНТОВ
ЗАДАЧИ ПОМЕХОУСТОЙЧИВОГО АНАЛИЗА И РАСПОЗНАВАНИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, ВКЛЮЧАЮЩИХ ПОВТОРЯЮЩИЕСЯ УПОРЯДОЧЕННЫЕ НАБОРЫ ВЕКТОР–ФРАГМЕНТОВ
Авторы: Александр Кельманов, Людмила Михайлова, Сергей Хамидуллин
Аннотация: Рассматриваются некоторые задачи помехоустойчивого off-line анализа и распознавания числовых и векторных последовательностей, включающих повторяющиеся наборы квазипериодических фрагментов или векторов. Обоснованы эффективные алгоритмы решения этих задач, гарантирующие оптимальность решения по критерию максимального правдоподобия, в случае, когда помеха аддитивна и является гауссовской последовательностью независимых одинаково распределенных случайных величин.
Ключевые слова: структурированная последовательность, упорядоченный набор вектор-фрагментов, помехоустойчивое обнаружение и распознавание, дискретная экстремальная задача, off- line алгоритм.
ACM Classification Keywords: F.2. Analysis of Algorithms and Problem Complexity, G.1.6. Optimization, G2. Discrete Mathematics, I.5. Pattern Recognition
Conference: The paper is selected from International Conference «Classification, Forecasting, Data Mining» CFDM 2009, Varna, Bulgaria, June-July 2009
Введение
Объектом исследования настоящей работы являются проблемы анализа и распознавания структурированных данных – числовых и векторных последовательностей, в составе которых имеются повторяющиеся, чередующиеся и перемежающиеся информационно значимые фрагменты или векторы. Предмет исследования – некоторые варианты проблемы помехоустойчивого off-line анализа и распознавания последовательностей, включающих повторяющиеся упорядоченные наборы вектор- фрагментов в качестве структурных элементов, в предположении, что скрытые в шуме фрагменты или векторы из искомых наборов совпадают с компонентами упорядоченного эталонного набора векторов, принадлежащего заданному конечному множеству (словарю). Цель работы – обоснование алгоритмов решения этих задач.
Рассмотрим две содержательные задачи. Пусть в первой из них источник сообщений передает информацию об активном состоянии некоторого физического объекта в виде эталонного набора импульсов, имеющих одну и ту же известную длительность, но различную форму. Каждому импульсу соответствует некоторое промежуточное активное состояние объекта. Порядок импульсов фиксирован. Пассивному состоянию соответствует отсутствие каких-либо импульсов. На приемную сторону через канал передачи поступает последовательность квазипериодически чередующихся импульсов, искаженная аддитивным шумом. Термин «квазипериодически» означает, что интервал между двумя последовательными импульсами не одинаков, а лишь ограничен сверху и снизу некоторыми константами.
Моменты времени появления импульсов в принятой (наблюдаемой) зашумленной последовательности 1.Работа поддержана грантами РФФИ 09-01-00032, 07-07-00022 и грантом АВЦП Рособразования 2.1.1/3235. неизвестны. Требуется обнаружить упорядоченные наборы импульсов в наблюдаемой последовательности, т.е. определить моменты времени, в которые объект находился в активном состоянии.
Во второй содержательной задаче предполагается, что на приемную сторону поступает информация от различных физических объектов, число которых конечно. Каждому объекту однозначно соответствует известный уникальный упорядоченный векторный набор, элемент которого – результат измерения каких- либо характеристик этого объекта в промежуточном активном состоянии. Число промежуточных активных состояний у физических объектов не одинаково. В пассивном состоянии все измеряемые характеристики равны нулю. Упорядоченная совокупность промежуточных активных состояний соответствует активному состоянию этого объекта в целом. На приемную сторону поступает искаженная шумом квазипериодическая последовательность результатов измерения характеристик от неизвестного объекта. Требуется определить (распознать), от какого объекта поступила информация.
Ситуации, в которых возникают сформулированные содержательные задачи, характерны, в частности, для электронной разведки, геофизики, гидроакустики, телекоммуникации и других приложений. В обеих задачах возможны два случая, когда число принятых импульсов или число ненулевых векторных наборов в последовательности известно и неизвестно. Эти случаи для двух сформулированных содержательных задач проанализированы в настоящей работе.
Численное моделирование
Результаты численных экспериментов, представленные ниже в качестве примера, носят чисто иллюстративный характер. Они лишь демонстрируют работу алгоритмов и сущность рассмотренных задач для одномерных последовательностей.
На рис. 1 а изображена сгенерированная последовательность X, включающая 3 повтора набора фрагментов. На рис. 1 б представлена последовательность Y, подлежащая обработке (в этом примере уровень помехи превышает уровень сигнала). На рис. 1 в приведена последовательность X?, полученная с помощью алгоритма обнаружения, в условиях, когда число M задано. Прямоугольными рамками очерчены места расположения обнаруженного набора, найденные алгоритмом в зашумленной последовательности. Числовые данные под графиками соответствуют заданным (рис. 1 а) и найденным (рис. 1 б и 1 в) начальным номерам фрагментов. Рисунок иллюстрирует практически безупречную работу алгоритма в условиях, когда уровень сигнала ниже уровня помехи.
На рис. 2 представлены кривые оценок нормированной среднеквадратической ошибки eE || X X ||2 / eu, где E – символ математического ожидания, eu – оценка сверху для || X ||2. Кривая 1 получена с помощью алгоритма обнаружения при неизвестном числе M фрагментов, а кривая 2 – с помощью алгоритма, ориентированного на ситуацию, когда это число известно. Результаты получены при обработке одних и тех же 25000 сгенерированных последовательностей, в составе которых повторялся набор из трех фрагментов; места расположения фрагментов в последовательностях генерировались с помощью датчика случайных чисел.
Рис. 3 иллюстрирует зависимость от уровня помехи вероятности ошибки распознавания последовательностей, включавших повторы двух различных эталонных наборов, в составе которых имелось по тривектора. Теоретические оценки верхней и нижней границ вероятности ошибки распознавания u (? ) и? d (? ) в виде графиков приведены под номерами 1 и 4. Кривые 2 и 3 получены в условиях, когда число M было неизвестно и известно соответственно.
Оценка вероятности ошибки распознавания при каждом значении подсчитана по формуле (v1 v2 ) / 2, где v1 и v2 – число неверно опознанных последовательностей, сгенерированных по каждому эталонному набору. Моделировалась байесовская процедура принятия решения с равновероятными гипотезами (наборами). Каждая точка экспериментальной кривой ?? получена в результате усреднения 25000 значений. Рис. 2 и 3 демонстрируют легко доказуемый факт, что ошибка обнаружения и вероятность ошибки распознавания будут меньше в ситуации, когда число ненулевых фрагментов в последовательности известно, чем в ситуации, когда это число неизвестно.
Заключение
Рассмотренные задачи входят в большое семейство актуальных задач [6], к которым сводятся типовые проблемы помехоустойчивого off-line анализа и распознавания структурированных данных в виде числовых и векторных последовательностей, включающих повторяющиеся, чередующиеся и перемежающиеся информационно значимые векторы или фрагменты. В настоящей работе представлены эффективные алгоритмические решения четырех ранее не изученных задач из этого семейства.
Открытым остается вопрос о разрешимости обобщения рассмотренных задач обнаружения и распознавания на тот случай, когда вместо набора фрагментов, элементы которого упорядочены в соответствии с фиксированным набором векторов, требуется найти набор фрагментов с точностью до всевозможных перестановок элементов фиксированного векторного набора. Алгоритмы решения этих задач представляют значительный интерес для ряда упомянутых во введении приложений. Обоснование алгоритмов решения этих задач представляется делом ближайшей перспективы.
Авторы: Александр Кельманов, Людмила Михайлова, Сергей Хамидуллин
Аннотация: Рассматриваются некоторые задачи помехоустойчивого off-line анализа и распознавания числовых и векторных последовательностей, включающих повторяющиеся наборы квазипериодических фрагментов или векторов. Обоснованы эффективные алгоритмы решения этих задач, гарантирующие оптимальность решения по критерию максимального правдоподобия, в случае, когда помеха аддитивна и является гауссовской последовательностью независимых одинаково распределенных случайных величин.
Ключевые слова: структурированная последовательность, упорядоченный набор вектор-фрагментов, помехоустойчивое обнаружение и распознавание, дискретная экстремальная задача, off- line алгоритм.
ACM Classification Keywords: F.2. Analysis of Algorithms and Problem Complexity, G.1.6. Optimization, G2. Discrete Mathematics, I.5. Pattern Recognition
Conference: The paper is selected from International Conference «Classification, Forecasting, Data Mining» CFDM 2009, Varna, Bulgaria, June-July 2009
Введение
Объектом исследования настоящей работы являются проблемы анализа и распознавания структурированных данных – числовых и векторных последовательностей, в составе которых имеются повторяющиеся, чередующиеся и перемежающиеся информационно значимые фрагменты или векторы. Предмет исследования – некоторые варианты проблемы помехоустойчивого off-line анализа и распознавания последовательностей, включающих повторяющиеся упорядоченные наборы вектор- фрагментов в качестве структурных элементов, в предположении, что скрытые в шуме фрагменты или векторы из искомых наборов совпадают с компонентами упорядоченного эталонного набора векторов, принадлежащего заданному конечному множеству (словарю). Цель работы – обоснование алгоритмов решения этих задач.
Рассмотрим две содержательные задачи. Пусть в первой из них источник сообщений передает информацию об активном состоянии некоторого физического объекта в виде эталонного набора импульсов, имеющих одну и ту же известную длительность, но различную форму. Каждому импульсу соответствует некоторое промежуточное активное состояние объекта. Порядок импульсов фиксирован. Пассивному состоянию соответствует отсутствие каких-либо импульсов. На приемную сторону через канал передачи поступает последовательность квазипериодически чередующихся импульсов, искаженная аддитивным шумом. Термин «квазипериодически» означает, что интервал между двумя последовательными импульсами не одинаков, а лишь ограничен сверху и снизу некоторыми константами.
Моменты времени появления импульсов в принятой (наблюдаемой) зашумленной последовательности 1.Работа поддержана грантами РФФИ 09-01-00032, 07-07-00022 и грантом АВЦП Рособразования 2.1.1/3235. неизвестны. Требуется обнаружить упорядоченные наборы импульсов в наблюдаемой последовательности, т.е. определить моменты времени, в которые объект находился в активном состоянии.
Во второй содержательной задаче предполагается, что на приемную сторону поступает информация от различных физических объектов, число которых конечно. Каждому объекту однозначно соответствует известный уникальный упорядоченный векторный набор, элемент которого – результат измерения каких- либо характеристик этого объекта в промежуточном активном состоянии. Число промежуточных активных состояний у физических объектов не одинаково. В пассивном состоянии все измеряемые характеристики равны нулю. Упорядоченная совокупность промежуточных активных состояний соответствует активному состоянию этого объекта в целом. На приемную сторону поступает искаженная шумом квазипериодическая последовательность результатов измерения характеристик от неизвестного объекта. Требуется определить (распознать), от какого объекта поступила информация.
Ситуации, в которых возникают сформулированные содержательные задачи, характерны, в частности, для электронной разведки, геофизики, гидроакустики, телекоммуникации и других приложений. В обеих задачах возможны два случая, когда число принятых импульсов или число ненулевых векторных наборов в последовательности известно и неизвестно. Эти случаи для двух сформулированных содержательных задач проанализированы в настоящей работе.
Численное моделирование
Результаты численных экспериментов, представленные ниже в качестве примера, носят чисто иллюстративный характер. Они лишь демонстрируют работу алгоритмов и сущность рассмотренных задач для одномерных последовательностей.
На рис. 1 а изображена сгенерированная последовательность X, включающая 3 повтора набора фрагментов. На рис. 1 б представлена последовательность Y, подлежащая обработке (в этом примере уровень помехи превышает уровень сигнала). На рис. 1 в приведена последовательность X?, полученная с помощью алгоритма обнаружения, в условиях, когда число M задано. Прямоугольными рамками очерчены места расположения обнаруженного набора, найденные алгоритмом в зашумленной последовательности. Числовые данные под графиками соответствуют заданным (рис. 1 а) и найденным (рис. 1 б и 1 в) начальным номерам фрагментов. Рисунок иллюстрирует практически безупречную работу алгоритма в условиях, когда уровень сигнала ниже уровня помехи.
На рис. 2 представлены кривые оценок нормированной среднеквадратической ошибки eE || X X ||2 / eu, где E – символ математического ожидания, eu – оценка сверху для || X ||2. Кривая 1 получена с помощью алгоритма обнаружения при неизвестном числе M фрагментов, а кривая 2 – с помощью алгоритма, ориентированного на ситуацию, когда это число известно. Результаты получены при обработке одних и тех же 25000 сгенерированных последовательностей, в составе которых повторялся набор из трех фрагментов; места расположения фрагментов в последовательностях генерировались с помощью датчика случайных чисел.
Рис. 3 иллюстрирует зависимость от уровня помехи вероятности ошибки распознавания последовательностей, включавших повторы двух различных эталонных наборов, в составе которых имелось по тривектора. Теоретические оценки верхней и нижней границ вероятности ошибки распознавания u (? ) и? d (? ) в виде графиков приведены под номерами 1 и 4. Кривые 2 и 3 получены в условиях, когда число M было неизвестно и известно соответственно.
Оценка вероятности ошибки распознавания при каждом значении подсчитана по формуле (v1 v2 ) / 2, где v1 и v2 – число неверно опознанных последовательностей, сгенерированных по каждому эталонному набору. Моделировалась байесовская процедура принятия решения с равновероятными гипотезами (наборами). Каждая точка экспериментальной кривой ?? получена в результате усреднения 25000 значений. Рис. 2 и 3 демонстрируют легко доказуемый факт, что ошибка обнаружения и вероятность ошибки распознавания будут меньше в ситуации, когда число ненулевых фрагментов в последовательности известно, чем в ситуации, когда это число неизвестно.
Заключение
Рассмотренные задачи входят в большое семейство актуальных задач [6], к которым сводятся типовые проблемы помехоустойчивого off-line анализа и распознавания структурированных данных в виде числовых и векторных последовательностей, включающих повторяющиеся, чередующиеся и перемежающиеся информационно значимые векторы или фрагменты. В настоящей работе представлены эффективные алгоритмические решения четырех ранее не изученных задач из этого семейства.
Открытым остается вопрос о разрешимости обобщения рассмотренных задач обнаружения и распознавания на тот случай, когда вместо набора фрагментов, элементы которого упорядочены в соответствии с фиксированным набором векторов, требуется найти набор фрагментов с точностью до всевозможных перестановок элементов фиксированного векторного набора. Алгоритмы решения этих задач представляют значительный интерес для ряда упомянутых во введении приложений. Обоснование алгоритмов решения этих задач представляется делом ближайшей перспективы.
Комментарии (0)
RSS свернуть / развернутьТолько зарегистрированные и авторизованные пользователи могут оставлять комментарии.