Сигналы являются, пожалуй, наиболее распространенными видами информации, ставшими в последние два десятилетия типовыми объектами применения компьютеров для анализа данных. Широко известны системы распознавания речевых команд и даже слитной речи, анализа экономических трендов, а что касается программ автоматического чтения печатного текста, то их использование стало массовым.
Особый интерес к компьютерной обработке именно сигналов в значительной мере определяется тем фактом, что это естественные виды организации потоков информации о внешнем мире, получаемой человеком и другими высшими животными через органы чувств, главным образом, посредством осязания, обоняния, слуха и зрения, и играющей фундаментальную роль в формировании их поведения.
Под сигналом принято понимать любую физическую величину, изменение которой во времени несет информацию о мире, внешнем по отношению к тому объекту, который эту информацию воспринимает. С точки зрения организации компьютерной обработки, когда время вынужденно рассматривается как дискретная переменная, сигнал представляет собой упорядоченную последовательность либо чисел, либо символов, если физическая величина, несущая информацию, сама имеет дискретный характер. Впрочем, роль оси, упорядочивающей отдельные единицы информации в массив данных, не обязательно должно играть время, это может быть и любая другая ось, например, пространственная координата.
Конечной целью анализа сигнала или изображения, как правило, является принятие того или иного решения об их источнике, например, какой слово произнесено, если анализируется сигнал речи, либо какое слово написано, если к анализу предъявлено изображение фрагмента рукописного либо печеного текста. Задачи такого рода относятся к области компетенции теории распознавания образов, в свою очередь, входящей в круг проблем, обычно называемых проблемами моделирования интеллектуального поведения. Эти вопросы привлекали основное внимание теоретиков, и в результате именно теория распознавания достигла в последние десятилетия наибольших успехов.
Теория распознавания образов разрабатывает методы построения формальных правил соотнесения поступающего сигнала или изображения с одним из источников. Для того, чтобы можно было применить данную теорию, необходимо прежде указать, какие свойства сигнала или изображения существенны для принятия решения о его источнике и в каких единицах эти свойства должны измеряться. После того, как такие свойства выбраны, каждый конкретный сигнал характеризуется конкретным набором их значений или, как говорят, оказывается представленным в виде точки в пространстве полезных признаков.
Таким образом, прежде чем обратиться к теории построения правил распознавания в некотором уже зафиксированном пространстве признаков, необходимо решить несравненно более сложную проблему их выбора, то есть представления исходного массива данных в виде, удобном для принятия окончательного решения. К тому же, в очень многих прикладных задачах результат предварительной обработки массива данных имеет самостоятельную ценность.
В то же время вопросы предварительной обработки сигналов и изображений теоретически разработаны существенно слабее. Несмотря на тот факт, что разнообразным задачам и алгоритмам первичного анализа посвящена обширная литература [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], каждая из таких задач рассматривалась отдельно от других независимыми исследователями для решения конкретных прикладных задач. Методы обработки сигналов и изображений, разработанные для каждой частной задачи, используют специфические системы понятий и специфический математический аппарат [11, 12, 13, 14. 15, 16]. В публикациях, посвященных этим методам, как базовые теоретические положения, так и результирующие алгоритмы излагаются с использованием специальной терминологии, часто не пересекающейся с терминологией, используемой для изложения подходов к решению других задач.
Понимание аналогичности алгоритмических проблем, всегда или, по крайней мере, очень часто возникающих в самых, казалось бы, разных задачах, и изложение этих проблем в общих терминах некоторого единого формального языка позволило бы объединить разрозненные фрагменты опыта, накопленного при решении каждой из них, и существенно сэкономить усилия при построении алгоритмов решения новых задач.
Тема настоящего диссертационного исследования находится в русле но-^ вого научного направления в методологии анализа данных, ориентированного на преодоление этого противоречия [17, 18, 19, 20, 21, 22].
Необходимость обработки массивов данных У -{у, / = 1,., Л0, упорядоченных вдоль оси некоторого дискретного аргумента t — времени, частоты, пространственной координаты, -типична для практики технических и естественно-научных исследований. Мы будем называть такие массивы данных сигналами, несколько расширяя традиционное значение этого термина, изначально ориентированного на обозначение функций времени в теории связи.
В последние годы интенсивно разрабатывается единый подход если не ко всем, то, во всяком случае, к большинству из чрезвычайно широкого разнообразия задач анализа массивов упорядоченных данных, использующий так называемый вариационный принцип, уже давно нашедший широкое применение во многих других областях науки [19, 20, 21]. Данная диссертационная работа представляет собой составную часть этого цикла исследований, направленную на дальнейшее развитие вариационного подхода к построению алгоритмов анализа сигналов. Мы начнем с краткого изложения этой концепции и возникающих в связи с ней алгоритмических проблем, решение которых и составляет цель настоящего диссертационного исследования.
Задачу анализа предъявленного массива данных, в данном случае, сигналаt — AO, определенного на оси некоторого дискретного аргумента, практически всегда можно понимать как задачу выбора его модели X из не6 которого класса моделей ХеХ. Применительно к сигналам, естественно различать стационарные модели, передающие общую форму предъявленного сигнала в пределах всей области определения t еТ = {1,., 7V}, и нестационарные модели, призванные отражать изменение некоторого локального свойства сигнала вдоль его дискретной оси. Например, постоянное среднее значение сигнала или его спектр в виде совокупности коэффициентов представления по заданному базису с этой точки зрения следует рассматривать как стационарные модели, в то время как типичными представителями нестационарных моделей являются изменяющееся локальное среднее значение сигнала или последовательность его локальных спектров, полученные путем усреднения соответствующего свойства сигнала в некотором скользящем окне. Нестационарную модель сигнала следует искать в виде последовательности локальных моделей либо значений изменяющегося параметра некоторой общей локальной модели в каждой точке оси сигнала X = (х, t = 1,.,/V). В качестве априорной информации естественно принять предположение, что локальная модель изменяется, в основном, достаточно плавно, так что смежные локальные модели х-, и х, скорее всего, близки друг к другу за исключением, быть может, относительно редких скачков, кроме того возможно, что векторные переменные х, выражающие собой локальные модели, в разных точках оси сигнала могут иметь разную размерность.
Универсальный подход к оцениванию моделей массивов данных, в частности моделей нестационарных сигналов, дает вариационный принцип, заключающийся в поиске модели X из заданного семейства ХеХ путем минимизации подходящего критерия несоответствия между массивом и моделью X = argmin VeX J (X | У). Выбор множества X, возможных значений целевых переменных хеХ,, вытекающий из их характера, определяет область варьирования обобщенной переменной X в вариационной постановке, конкретной задачи обработки данных.
Использование вариационного принципа позволяет ставить исходные прикладные задачи анализа данных как формальные задачи минимизации вполне определенных целевых функций J (X | У), то есть функций, формально выражающих цель обработки, и переводить, таким образом, проблему эвристического конструирования алгоритмов в точные термины теории оптимизации.
Важно лишь так выбрать класс целевых функций, чтобы было гарантировано существование эффективного достаточно быстрого алгоритма поиска точки минимума X = X (Y), выступающей в качестве результата обработки. Алгоритм минимизации целевых функций из выбранного класса и будет играть роль универсального обобщенного алгоритма обработки массивов данных определенного вида [21, 23].
В данной диссертационной работе рассматривается ряд примеров типовых задач анализа нестационарных сигналов: задача сглаживания сигнала, задача спектрально-временного и авторегрессионого анализа, задача анализа портфеля инвестиционной компании. Показано, что все эти задачи являются частными случаями задачи оценивания нестационарной регрессии, адекватнй многим приложениям [24, 25]. В работах [21, 23, 26,] обнаружено, что задача оценивания нестационарной регрессии естественным образом сводится к задаче квадратичной оптимизации относительно последовательности действительных векторных аргументов Аг = (х (eR", t = ,., N)
Л .V
7(х,., хЛ,)= Y (x, — х")' Q°(x, — х")+ У (А, х, -х,)7 U,(A, X, — х,)-> min .
ТТ 71 Vl v являющейся частным случаем задачи минимизации парно-сепарабельной целевой функции
J (xn., x л.) =) +) с зависящими от данных квадратичными узловыми функциями vj/,(x-), оценивающими степень несогласованности значения каждого локального параметра модели х, с формой сигнала в некоторой малой окрестности текущей точки t, и квадратичными функциями связи уДх, рх,), выражающими несогласованность значений каждой пары соседних локальных параметров с априорными представлениями об искомой нестационарной модели.
Вообще говоря, задача парно-сепарабельной квадратичной оптимизации эквивалентна системе линейных уравнений с блочно-трехдиагональной матрицей коэффициентов при неизвестных х,., хл, которая легко решается методом прогонки за число операций, пропорциональное числу векторных переменных /V. В данном диссертационном исследовании предложена интерпретация метода прогонки, как варианта более общего метода динамического программирования, предложенного около сорока лет назад американским математиком Ричардом Беллманом [27, 28, 48] и заключающегося в замене исходной задачи поиска минимума функции многих аргументов последовательностью существенно более простых задач минимизации промежуточных функций одного аргумента, называемых функциями Беллмана [29, 30]. Хотя основная процедура динамического программирования принципиально основана на предположении, что целевые переменные принимают лишь конечное множество значений, она распространяется в [20, 21] на случай непрерывных переменных для квадратичных парно-сепарабельных целевых функций путем введения понятия параметрического семейства функций Беллмана, которые также оказываются квадратичными. Получающаяся при этом процедура оптимизации, заключающаяся в рекуррентном пересчете и запоминании параметров квадратичных функций Беллмана, есть ни что иное как метод прогонки для решения соответствующей блочно-трехдиагональной системы линейных уравнений.
На основе такой интерпретации метода прогонки в работе [31] предложены алгоритмы решения ряда типовых задач анализа сигналов, сводящихся к задаче оценивания нестационарной регрессии. Разработанные алгоритмы опираются на процедуру динамического программирования «впереди навстречу», основанную на понятиях левой и правой функций Беллмана и альтернативную по отношению к традиционной процедуре «вперед и обратно».
Раздельное вычисление левой и правой функций Беллмана позволило построить эффективную в вычислительном отношении процедуру скользящего контроля для верификации нестационарной модели путем последовательного сравнения экспериментального значения каждого элемента сигнала с его предсказанным значением по модели, построенной без участия этого элемента. Понятие двухсторонних функций Беллмана позволило также построить критерий обнаружения нарушений гладкости изменения оцениваемого параметра нестационарного сигнала.
В данной работе рассматривается задача оценивания нестационарной регрессии в случае, когда по условию решаемой прикладной задачи на искомую последовательность векторных параметров нестационарной модели сигнала X = (х,(= 1,.,/V) наложены линейные ограничения в виде линейных равенств и неравенств.
Вообще говоря, задача минимизации квадратичной целевой функции с линейными ограничениями, охватывающими сразу все переменные, является классической задачей квадратичного программирования. Для решения общей задачи квадратичного программирования существует множество численных методов — симплекс-метод, метод наискорейшего спуска и др. [32, 33, 34, 47, 52, 53] - имеющих полиномиальную вычислительную сложность относительно числа переменных N.
Заметим, что общая задача квадратичной оптимизации без ограничений также имеет полиномиальную вычислительную сложность относительно числа векторных переменных, которая снижается до линейной в случае парной сепарабельности целевой функции. Однако в обоих случаях наложение линейных ограничений на все переменные в совокупности приводит к задаче квадратичного программирования общего вида, причем нет методов, позволяющих использовать факт парной сепарабельности целевой функции для снижения полиномиальной вычислительной сложности задачи.
В данной работе рассматривается частный случай задачи оценивания' нестационарной регрессии с линейными ограничениями на искомые коэффициенты, характерный для многих приложений, когда ограничения сводятся к последовательности ограничений на отдельные векторные переменные х, eR t = 1,.,/V :
A, х, +с, >0,.
B, х,+f,=0
Задачу минимизации квадратичной парно-сепарабельной целевой функции с ограничениями типа в данной работе предлагается называть задачей парно-сепарабельного квадратичного программирования.
Для задач этого типа в диссертации предлагаются два алгоритма решения, обладающие линейной вычислительной сложностью относительно числа векторных переменных N. Оба алгоритма существенно используют процедуру динамического программирования для минимизации парно-сепарабельных квадратичных функций без ограничений, рассмотренную в работах [17, 20, 21, 31] и основанную на рекуррентном пересчете параметров квадратичных функций Беллмана.
Теоретически, линейная вычислительная сложность алгоритма оптимизации по числу переменных квадратичной парно-сепарабельной целевой функции при наличии индивидуальных ограничений на переменные обеспечивается прямым применением процедуры динамического программирования. Однако численная реализация такой процедуры для непрерывных переменных оказывается затруднительной, поскольку, как показано в диссертации наличие неравенств в ограничениях выводит очередную функцию Беллмана из конечно-параметрического семейства квадратичных функций, даже если предположить, что предыдущая функция Беллмана квадратична.
Первый алгоритм, предлагаемый в данной работе, построен по итерационному принципу и реализует метод наискорейшего спуска, применяемый для решения двойственной задачи. Наиболее сложным в вычислительном отношении шагом такого алгоритма является вычисление на каждой итерации очередного градиента двойственной целевой функции. Алгоритм эксплуатирует тот факт, что искомый градиент определяется точкой минимума функции Лагранжа по целевым переменным Х = (хп t = ,., N) без ограничений при фиксированных значениях множителей Лагранжа, полученных на предыдущей итерации, причем функция Лагранжа квадратична и парно-сепарабельна. В силу этого обстоятельства точка ее минимума может быть найдена процедурой квадратичного динамического программирования, эквивалентной процедуре прогонки, за число операций, пропорциональное числу переменных, А. Таким образом, по своей вычислительной сложности итерационный алгоритм решения задачи минимизации парно-сепарабельной функции с индивидуальными ограничениями на векторные переменные сводится к многократному применению процедуры динамического программирования с линейной вычислительной сложностью для решения аналогичной задачи без ограничений, причем число повторений равно числу итераций.
Однако существует класс вариационных задач анализа нестационарных сигналов, алгоритмическое решение которых связано с необходимостью многократного определения оптимального значения целевой переменной в отдельно взятой точке оси аргумента при разных моделях сигнала без пересчета оптимальных значений в других точках. Это такие задачи, как, например, задача обнаружения нарушений гладкости изменения оцениваемого параметра, задача оценивания дисперсии шума наблюдения в модели нестационарной регрессии, задача подбора класса нестационарной модели и т. д. [35, 36, 37, 38] Таким образом, объем вычислений возрастает пропорционально квадрату длины сигнала /V2, в то время как оценивание последовательности векторов коэффициентов регрессии с помощью метода наискорейшего спуска требует объема вычислений, пропорционального лишь длине сигнала N. Эффективные алгоритмы решения таких задач не могут быть построены в рамках метода наискорейшего спуска.
Второй алгоритм, предлагаемый в данной работе, представляет собой приближенную реализацию процедуры динамического программирования вперед и навстречу" для случая с ограничениями, позволяющую решать обозначенные выше задачи за два прохода сигнала с числом операций, про
12 порциональным его длине N. Этот алгоритм не является итерационным и эквивалентен однократному применению процедуры динамического программирования, имеющей линейную вычислительную сложность, но на каждом шаге рекуррентного пересчета вместо точной функции Беллмана, не являющейся квадратичной, он использует квадратичное приближение к ней в малой окрестности точки ее минимума. В силу такой эвристической замены алгоритм не дает, строго говоря, точного решения задачи парно-сепарабельного квадратичного программирования, но многочисленные эксперименты свидетельствуют о достижении хорошего приближения к точке минимума целевой функции.
Разработанные вариационные алгоритмы восстановления нестационарной регрессии использованы в диссертации для построения программно-алгоритмического комплекса анализа экономических данных восстановления структуры портфеля инвестиционной компании.
Диссертация состоит из шести глав. В первой главе рассмотрены примеры типовых задач анализ сигналов, являющие частными случаями задачи восстановления нестационарной регрессии и приводящие к необходимости решения задачи парно-сепарабельного квадратичного программирования с ограничениями, сформулированы основные задачи исследования. Во второй главе предлагается процедура решения задачи парно-сепарабельного квадратичного программирования, линейная по числу векторных переменных и опирающаяся на известный метод решения задач квадратичного программирования — метод наискорейшего спуска. В третьей главе показывается невозможность непосредственного применения метода прогонки и процедуры динамического программирования для решения задачи парно-сепарабельного квадратичного программирования. Предлагается приближенная реализация процедуры динамического программирования «вперед и навстречу» для случая с ограничениями, основанная на замене в каждый момент времени неквадратичных фикций Беллмана квадратичными. В четвертой главе разработанный. приближенный алгоритм применяется для построения алгоритма сглаживания сигналов с автоматическим подбором степени сглаживания и сохранением локальных особенностей исходного сигнала. В пятой главе проводится экспериментальное исследование предложенных алгоритмов на предмет точности и быстродействия. Показывается, что при применении приближенного метода динамического программирования не происходит сколько-нибудь существенной потери качества. Кроме того, показано, что этот метод обеспечивает более высокое быстродействие по сравнению с методом наискорейшего спуска, т.к. находит решение задачи за один цикл работы процедуры «вперед и навстречу». В то время, как в методе наискорейшего спуска количество применений процедуры «вперед и навстречу» пропорционально числу итераций
6 Основные выводы
1. Дана формальная постановка обобщенной задачи анализа широкого класса нестационарных сигналов как задачи парно-сепарабельного квадратичного программирования.
2. Разработан асимптотически точный итерационный метод решения задачи парно-сепарабельного квадратичного программирования, основанный на методе наискорейшего спуска, использующий на каждой итерации метод прогонки и имеющий линейную вычислительную сложность относительно числа векторных переменных.
3. Разработан неитерационный алгоритм решения задачи парно-сепарабельного квадратичного программирования, на основе приближенной реализации процедуры динамического программирования.
4. Разработан алгоритм оценивания параметров нестационарной модели сигнала с сохранением его локальных особенностей с помощью применение приближенной процедуры динамического программирования.
5. Разработан алгоритм определения требуемой степени сглаживания при оценивании нестационарной модели сигнала на основе метода скользящего контроля с применением приближенной процедуры динамического программирования.
6. Исследована вычислительная сложность предложенных алгоритмов анализа нестационарных сигналов и показана, что она является линейной относительно длины сигнала.
7. Экспериментально исследована точность приближенной реализации метода динамического программирования при оценивании нестационарных моделей сигналов. Показано, что не происходит сколько-нибудь существенной потери точности при применении приближенного метода динамического программирования по сравнению с точными методами квадратичного программирования.
