Система QPSLab для анализа и рас

Система QPSLab для анализа и распознавания числовых последовательностей с квазипериодической структурой

Существует четыре базовых подхода к решению проблемы, которые опираются на комбинации двух способов обработки данных – последовательного (on-line) и апостериорного (off-line) – с двумя вариантами формализации содержательной проблемы – либо в виде задачи оценивания, либо в виде задачи проверки гипотез. В основе этих походов лежат классические статистические методы оценивания и проверки гипотез, предложенные и развитые в широко известных фундаментальных работах отечественных и зарубежных исследователей.

		Формализация задачи
		Оценивание	Проверка гипотез
Способ обработки	Последовательный (on-line)	+	+
	Апостериорный (off-line)	+	?

Хорошо изученными и традиционными при реализации информационных технологий являются три подхода, которые опираются на последовательный и апостериорный способы обработки последовательности в сочетании с формализацией содержательной задачи как задачи оценивания, а также последовательный способ обработки в комбинации с формулировкой задачи как задачи проверки гипотез. Четвертый подход, который опирается на формализацию содержательной задачи в виде задачи проверки гипотез в сочетании с off-line обработкой данных, не является традиционным. Он редко применяется на практике в виде технологий помехоустойчивой обработки структурированных данных из-за нетривиальных математических проблем вычислительного и оптимизационного плана, которые возникают при его реализации. Об этих проблемах сказано ниже. Здесь лишь отметим, что именно этот подход лежит в основе системы QPSLab.

Идея всех традиционных подходов к проблеме состоит в последовательном или поэтапном решении подзадач:

1) обнаружения моментов времени поступления (поиска расположения в массиве) информационно важных блоков, фрагментов или структурных элементов,

2) принятия решения о каждом обнаруженном блоке данных (т.е. их идентификация или классификация) либо оценивания искомых характеристик для каждого блока в отдельности (т.е. независимо от других блоков) по результатам решения первой подзадачи,

3) коррекции или уточнения (при необходимости) принятых решений или оценок по результатам решения двух предыдущих подзадач,

4) принятия решения о структуре в целом или ее оценивания.

Реализация традиционных подходов существенным образом опирается на методы оптимальной фильтрации (с целью очистки от помех), методы последовательного обнаружения разладки (скачкообразного изменений свойств) случайной последовательности, методы последовательной проверки гипотез и классические методы распознавания.

Как известно, недостаток этих подходов состоит в том, что в общем случае они не гарантируют оптимальность статистического решения по совокупности всех накопленных данных, несмотря на получение оптимального решения для каждой из последовательно решаемых подзадач (или для каждого из последовательно выполняемых этапов). Если модели данных и помех фиксированы, то ошибка, возникшая при решении предыдущей подзадачи (или на предыдущем этапе), в общем случае не может быть исправлена или уменьшена при решении последующей подзадачи (на следующем этапе). Ошибка принятия решения или оценивания по подмножеству данных (когда данные обрабатываются по мере их поступления) в общем случае не может быть меньше ошибки обработки по совокупности всех данных. Результат оптимизации, найденный по условным экстремумам, вычисленным на последовательно выполняемых этапах обработки данных, в общем случае может не совпадать с глобальным экстремумом.

Традиционные подходы ориентированы на получение результата с наименьшими временными затратами. Достоинство этих подходов состоит в том, что они позволяют конструировать так называемые «быстрые» алгоритмы и технологии. Это достоинство обусловлено тем, что при реализации традиционных подходов трудоемкие, затратные в вычислительном плане проблемы комбинаторной оптимизации, как правило, не возникают. Решение задачи условной оптимизации критерия на каждом из последовательных этапов обычно находится стандартными малотрудоемкими методами.

Напротив, реализованный в данной системе нетрадиционный подход потенциально более точен и трудоемок, так как изначально ориентирован на поиск оптимального решения по совокупности всех имеющихся (накопленных) данных. Этот подход редко применяется в приложениях (здесь речь идет лишь об алгоритмах с доказуемыми оценками точности, а не о широко распространенных эвристических технологиях), так как его реализация напрямую связана с решением специфических, как правило, неизученных задач комбинаторной оптимизации, к которым сводится поиск экстремума критерия качества решения (например, максимизация функционала правдоподобия). По этой причине мы называем нетрадиционный подход комбинаторным. Этот подход состоит в совместном (одновременном) решении указанных выше подзадач. Для его реализации необходимы апостериорные алгоритмы и технологии:

1) совместного обнаружения структурных элементов в массивах зашумленных данных и принятия решения об этих элементах;

2) совместного обнаружения и оценивания элементов структурированных данных;

3) совместного распознавания структур как единого целого и идентификации их элементов;

4) совместной классификации структур, разбиения их на структурные элементы и оценивания характеристик этих элементов.

Задачи комбинаторной оптимизации возникают при реализации нетрадиционного подхода из-за необходимости выбора наилучшего варианта (или оптимальной по заданному критерию гипотезы) из допустимой совокупности, мощность которой растет в лучшем случае экспоненциально с увеличением размера входа задачи, т.е. с увеличением числа членов обрабатываемой последовательности или с увеличением интервала наблюдения. Перебрать напрямую все варианты (гипотезы) из этой совокупности попросту нереально. Для выбора оптимального варианта требуется найти алгоритмическое решение оптимизационной задачи, показав либо ее полиномиальную разрешимость, либо NP-трудность. Здесь важно заметить, что задачи, в которых, число проверяемых гипотез растет экспоненциально с увеличением размерности задачи, в классической математической статистике не рассматриваются.

Экстремальные задачи, возникающие в рамках нетрадиционного подхода, специфичны для каждой из решаемых типовых проблем анализа данных и распознавания. Совокупность алгоритмов решения этих задач составляет основу нетрадиционного подхода. Однако универсального метода или алгоритма решения задач комбинаторной оптимизации, как известно, не существует. Поэтому систематизация и анализ сложности этих задач, а также построение полиномиальных алгоритмов с доказуемыми оценками точности для их решения – ключевые проблемы, решение которых необходимо для успешной реализации комбинаторного подхода в виде технологий. Не менее важная проблема – изучение статистических свойств получаемых решений (алгоритмов), особенно в тех случаях, когда комбинаторная задача оказывается NP-трудной. Сказанное в полной мере относится к алгоритмам и технологиям анализа и распознавания структурированных данных в виде числовых последовательностей, включающих квазипериодически перемежающиеся ненулевые информационные фрагменты одинаковой размерности.

Разработка системы и технологий, реализующих комбинаторный подход, опиралась на аппарат математической статистики, дискретной оптимизации, исследования операций, а также математическое моделирование. В соответствии с общепризнанными принципами математических исследований решение каждой типовой задачи было разбито на следующие последовательно выполняемые взаимосвязанные шаги:

1) формальная постановка содержательной задачи и ее формулировка в форме максимизации функционала правдоподобия или минимизации суммы квадратов уклонений;

2) выявление специфической экстремальной задачи, к которой редуцируется оптимизация критерия;

3) установление статуса алгоритмической сложности выявленной задачи;

4) обоснование полиномиального алгоритма с гарантированными оценками точности для решения этой задачи;

5) построение алгоритма обработки последовательности, ядром которого является алгоритм решения выявленной задачи комбинаторной оптимизации;

6) получение оценок временной и емкостной сложности обоснованных алгоритмов;

7) исследование точности алгоритма обработки данных;

При построении и анализе алгоритмов решения выявленных NP-трудных задач применяется специальная математическая техника. Для задач с детерминированными входами устанавливаются гарантированные уклонения алгоритмических решений от оптимума. Для задач со случайными входами используется техника вероятностного анализа, направленная на вычисление вероятности отыскания малотрудоемким алгоритмом решения с заданной точностью (вероятности срабатывания алгоритма). При этом конструируются малотрудоемкие асимптотически точные (статистически эффективные) алгоритмы, для которых конструктивно показывается существование оценок относительной погрешности и вероятности несрабатывания, стремящихся к нулю с ростом размерности задачи.

Практическая реализация системы и технологий существенным образом опирается на теоретические результаты, полученные в рамках проектов РФФИ № 94-01-00169, № 97-01-00866, № 00-01-00795, № 03-01-00036, № 06-01-00058, № 09-01-00032 и № 93-01-00-417, № 96-01-01591, № 99-01-00601, № 02-01-01153, № 05-01-00395, № 08-01-00516, ИНТАС № 00-217, № 04-77-7173, выполненных и выполняемых под руководством д.ф.-м.н. Кельманова А.В. и д.ф.-м.н. Гимади Э.Х. Подчеркнем, что в этих проектах решены фундаментальные математические проблемы, всплывающие при реализации комбинаторного подхода к решению проблемы помехоустойчивой off-line обработки массивов данных, имеющих квазипериодическую структуру.