Содержание к диссертации
Введение
1 Проблема оценивания нестационарной модели сигнала и основные задачи исследования 15
1.1 Задачи оценивания нестационарной модели сигнала с ограничениями на значения параметров 15
1.1.1 Задача сглаживания знакопостоянного и монотонного сигнала 15
1.1.2 Задачи авторефессионного и спектрально-временного анализа .21
1.1.3 Задача оценивания портфеля инвестиционной компании 25
1.1.4 Задача оценивания нестационарной рефессии как обобщенная задача оценивания нестационарной модели сигнала 31
1.2 Задача оценивания нестационарной рефессии с офаничениями на значения коэффициентов как задача парно-сепарабельного квадратичного профаммирования 33
1.3 Существующие методы оценивания нестационарной рефессии 37
1.4 Вычислительная сложность задачи квадратичного профаммирования 40
1.5 Основные задачи исследования 46
2 Асимптотически точный итерационный метод наискорейшего спуска для решения задачи парно-сепарабельного квадратичного профаммирования 49
2.1 Двойственная форма задачи парно-сепарабельного квадратичного профаммирования 49
2.2 Градиент двойственной целевой функции по вектору множителей Лафанжа 52
2.3 Метод прогонки для вычисления фадиента двойственной целевой функции 53
2.4 Допустимо направление и выбор тага наискорейшего спуска
2.5 Итерационный алгоритм парно-сепарабельного квадратичного программирования 62
3 Безитерационный алгоритм динамического программирования для приближенного решения задачи парно-сепарабельного квадратичного программирования 65
3.1 Общая структура процедуры динамического программирования для оптимизации парно-сепарабельной целевой функции 65
3.2 Алгоритм динамического программирования «вперед и навстречу».. 68
3.3 Неквадратичность функций Белл мана 73
3.4 Квадратичная аппроксимация функций Беллмана 75
3.5 Приближенный алгоритм динамического программирования 85
4 Алгоритмы оценивания нестационарной регрессии 88
4.1 Алгоритм оценивания дисперсии аддитивного шума 88
4.2 Выбор скрытой модели динамики последовательности коэффициентов регрессии 91
4.3 Сохранение локальных особенностей последовательности коэффициентов регрессии 95
5 Экспериментальное исследование алгоритмов парно-сепарабельного - квадратичного программирования 1 07
5.1 Сравнительное исследование точности алгоритмов 107
5.2 Сравнение быстродействия алгоритмов 1 1 1
6 Основные выводы 1 13
Список литературы 1 14
- Задача оценивания нестационарной рефессии как обобщенная задача оценивания нестационарной модели сигнала
- Вычислительная сложность задачи квадратичного профаммирования
- Итерационный алгоритм парно-сепарабельного квадратичного программирования
- Алгоритм динамического программирования «вперед и навстречу»..
Введение к работе
Сигналы являются, пожалуй, наиболее распространенными видами информации, ставшими в последние два десятилетия типовыми объектами применения компьютеров для анализа данных. Широко известны системы распознавания речевых команд и даже слитной речи, анализа экономических трендов, а что касается программ автоматического чтения печатного текста, то их использование стало массовым.
Особый интерес к компьютерной обработке именно сигналов в значительной мере определяется тем фактом, что это естественные виды организации потоков информации о внешнем мире, получаемой человеком и другими высшими животными через органы чувств, главным образом, посредством осязания, обоняния, слуха и зрения, и играющей фундаментальную роль в формировании их поведения.
Под сигналом принято понимать любую физическую величину, изменение которой во времени несет информацию о мире, внешнем по отношению к тому объекту, который эту информацию воспринимает. С точки зрения организации компьютерной обработки, когда время вынужденно рассматривается как дискретная переменная, сигнал представляет собой упорядоченную последовательность либо чисел, либо символов, если физическая величина, несущая информацию, сама имеет дискретный характер. Впрочем, роль оси, упорядочивающей отдельные единицы информации в массив данных, не обязательно должно играть время, это может быть и любая другая ось, например, пространственная координата.
Конечной целью анализа сигнала или изображения, как правило, является принятие того или иного решения об их источнике, например, какой слово произнесено, если анализируется сигнал речи, либо какое слово написано, если к анализу предъявлено изображение фрагмента рукописного либо печатного текста. Задачи такого рода относятся к области компетенции теории распознавания образов, в свою очередь, входящей в круг проблем, обычно
называемых проблемами моделирования интеллектуального поведения. Эти вопросы привлекали основное внимание теоретиков, и в результате именно теория распознавания достигла в последние десятилетия наибольших успехов.
Теория распознавания образов разрабатывает методы построения формальных правил соотнесения поступающего сигнала или изображения с одним из источников. Для того, чтобы можно было применить данную теорию, необходимо прежде указать, какие свойства сигнала или изображения существенны для принятия решения о его источнике и в каких единицах эти свойства должны измеряться. После того, как такие свойства выбраны, каждый конкретный сигнал характеризуется конкретным набором их значений или, как говорят, оказывается представленным в виде точки в пространстве полезных признаков.
Таким образом, прежде чем обратиться к теории построения правил распознавания в некотором уже зафиксированном пространстве признаков, необходимо решить несравненно более сложную проблему их выбора, то есть представления исходного массива данных в виде, удобном для принятия окончательного решения. К тому же, в очень многих прикладных задачах результат предварительной обработки массива данных имеет самостоятельную ценность.
В то же время вопросы предварительной обработки сигналов и изображений теоретически разработаны существенно слабее. Несмотря на тот факт, что разнообразным задачам и алгоритмам первичного анализа посвящена обширная литература [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], каждая из таких задач рассматривалась отдельно от других независимыми исследователями для решения конкретных прикладных задач. Методы обработки сигналов и изображений, разработанные для каждой частной задачи, используют специфические системы понятий и специфический математический аппарат [11, 12, 13, 14. 15, 16]. В публикациях, посвященных этим методам, как базовые теоретические положения, так и результирующие алгоритмы излагаются с ислользова-
ниєм специальной терминологии, часто не пересекающейся с терминологией, используемой для изложения подходов к решению других задач.
Понимание аналогичности алгоритмических проблем, всегда или, по крайней мере, очень часто возникающих в самых, казалось бы, разных задачах, и изложение этих проблем в общих терминах некоторого единого формального языка позволило бы объединить разрозненные фрагменты опыта, накопленного при решении каждой из них, и существенно сэкономить усилия при построении алгоритмов решения новых задач.
Тема настоящего диссертационного исследования находится в русле нового научного направления в методологии анализа данных, ориентированного на преодоление этого противоречия [17, 18, 19, 20, 21, 22].
Необходимость обработки массивов данных Y -{уп t = \,...,N), упорядоченных вдоль оси некоторого дискретного аргумента / - времени, частоты, пространственной координаты, -типична для практики технических и естественно-научных исследований. Мы будем называть такие массивы данных сигналами, несколько расширяя традиционное значение этого термина, изначально ориентированного на обозначение функций времени в теории связи.
В последние годы интенсивно разрабатывается единый подход если не ко всем, то, во всяком случае, к большинству из чрезвычайно широкого разнообразия задач анализа массивов упорядоченных данных, использующий так называемый вариационный принцип, уже давно нашедший широкое применение во многих других областях науки [19, 20, 21]. Данная диссертационная работа представляет собой составную часть этого цикла исследований, направленную на дальнейшее развитие вариационного подхода к построению алгоритмов анализа сигналов. Мы начнем с краткого изложения этой концепции и возникающих в связи с ней алгоритмических проблем, решение которых и составляет цель настоящего диссертационного исследования.
Задачу анализа предъявленного массива данных, в данном случае, сигнала Ґ -'(}',> * = 1,...,^), определенного на оси некоторого дискретного аргумента,
практически всегда можно понимать как задачу выбора его модели X из не-
которого класса моделей ХєА. Применительно к сигналам, естественно различать стационарные модели, передающие общую форму предъявленного сигнала в пределах всей области определения t еТ = {1,...,7V}, и нестационарные модели, призванные отражать изменение некоторого локального свойства сигнала вдоль его дискретной оси. Например, постоянное среднее значение сигнала или его спектр в виде совокупности коэффициентов представления по заданному базису с этой точки зрения следует рассматривать как стационарные модели, в то время как типичными представителями нестационарных моделей являются изменяющееся локальное среднее значение сигнала или последовательность его локальных спектров, полученные путем усреднения соответствующего свойства сигнала в некотором скользящем окне. Нестационарную модель сигнала следует искать в виде последовательности локальных моделей либо значений изменяющегося параметра некоторой общей локальной модели в каждой точке оси сигнала X =(х,, t = \,...,N). В качестве априорной информации естественно принять предположение, что локальная модель изменяется, в основном, достаточно плавно, так что смежные локальные модели х,_, и х,, скорее всего, близки друг к другу за исключением, быть может, относительно редких скачков, кроме того возможно, что векторные переменные х,, выражающие собой локальные модели, в разных точках оси сигнала могут иметь разную размерность.
Универсальный подход к оцениванию моделей массивов данных, в частности моделей нестационарных сигналов, дает вариационный принцип, заключающийся в поиске модели X из заданного семейства X еХ путем минимизации подходящего критерия несоответствия между массивом и моделью X - argmin VeX J(X \ Y). Выбор множества X, возможных значений целевых переменных х, еХ, , вытекающий из их характера, определяет область
варьирования обобщенной переменной X в вариационной постановке, конкретной задачи обработки данных.
Использование вариационного принципа позволяет ставить исходные прикладные задачи анализа данных как формальные задачи минимизации вполне определенных целевых функций J(X | Y), то есть функций, формально выражающих цель обработки, и переводить, таким образом, проблему эвристического конструирования алгоритмов в точные термины теории оптимизации.
Важно лишь так выбрать класс целевых функций, чтобы было гарантировано существование эффективного достаточно быстрого алгоритма поиска
точки минимума X = X(Y), выступающей в качестве результата обработки. Алгоритм минимизации целевых функций из выбранного класса и будет играть роль универсального обобщенного алгоритма обработки массивов данных определенного вида [21, 23].
В данной диссертационной работе рассматривается ряд примеров типовых задач анализа нестационарных сигналов: задача сглаживания сигнала, задача спектрально-временного и авторефессионого анализа, задача анализа портфеля инвестиционной компании. Показано, что все эти задачи являются частными случаями задачи оценивания нестационарной рефессии, адекватнй многим приложениям [24, 25]. В работах [21, 23, 26,] обнаружено, что задача оценивания нестационарной рефессии естественным образом сводится к задаче квадратичной оптимизации относительно последовательности действительных векторных аргументов X = (х, є R", t = 1,..., Л/)
Л .V
7(х,,...,хЛ,)=У(х, -xI'/Q^x, -х) + У(А,х,_, -х,)1 U,(A,x,_, - х,)-> min .
являющейся частным случаем задачи минимизации парно-сепарабельной целевой функции
j(X],...,x v)=Х,1,^дх,)+Х^*(х<-| 'х<)
с зависящими от данных квадратичными узловыми функциями vj/,(x;), оценивающими степень несогласованности значения каждого локального параметра модели х, с формой сигнала в некоторой малой окрестности текущей
точки t, и квадратичными функциями связи у,(х,_,,х,), выражающими несогласованность значений каждой пары соседних локальных параметров с априорными представлениями об искомой нестационарной модели.
Вообще говоря, задача парно-сепарабельной квадратичной оптимизации эквивалентна системе линейных уравнений с блочно-трехдиагональной матрицей коэффициентов при неизвестных x,,...,x;V, которая легко решается методом прогонки за число операций, пропорциональное числу векторных переменных /V . В данном диссертационном исследовании предложена интерпретация метода прогонки, как варианта более общего метода динамического программирования, предложенного около сорока лет назад американским математиком Ричардом Беллманом [27, 28, 48] и заключающегося в замене исходной задачи поиска минимума функции многих аргументов последовательностью существенно более простых задач минимизации промежуточных функций одного аргумента, называемых функциями Беллмана [29, 30]. Хотя основная процедура динамического программирования принципиально основана на предположении, что целевые переменные принимают лишь конечное множество значений, она распространяется в [20, 21] на случай непрерывных переменных для квадратичных парно-сепарабельных целевых функций путем введения понятия параметрического семейства функций Беллмана, которые также оказываются квадратичными. Получающаяся при этом процедура оптимизации, заключающаяся в рекуррентном пересчете и запоминании параметров квадратичных функций Беллмана, есть ни что иное как метод прогонки для решения соответствующей блочно-трехдиагональной системы линейных уравнений.
На основе такой интерпретации метода прогонки в работе [31] предложены алгоритмы решения ряда типовых задач анализа сигналов, сводящихся к задаче оценивания нестационарной регрессии. Разработанные алгоритмы опираются на процедуру динамического программирования «вперед ;и навстречу», основанную на понятиях левой и правой функций Беллмана и альтернативную по отношению к традиционной процедуре «вперед и обратно».
Задача оценивания нестационарной рефессии как обобщенная задача оценивания нестационарной модели сигнала
Инвестиционная компания - это тип финансового посредника. Они привлекают средства инвесторов и приобретают на них финансовые активы, такие, как например акции, облигации и другие ценные бумаги. В свою очередь инвесторы получают определенные права в отношении приобретенных компанией финансовых активов и получаемой от них прибыли. В самой простой и наиболее распространенной форме инвестиционная компания имеет только один тип инвесторов - акционеров. Данные акционеры напрямую владеют компанией и опосредованно владеют финансовыми активами, принадлежащими этой компании. Для индивидуального инвестора существует два преимущества вложения средств в такие компании вместо прямого инвестирования в финансовые активы, которыми владеют данные компании. Во-первых, экономия, на масштабе и, во-вторых, профессиональное управление активами.
Совокупность финансовых активов, которыми владеет инвестиционная компания называется ее портфелем или портфолио. Целью деятельности любой инвестиционной компании является увеличение стоимости ее портфеля. Вообще говоря, финансовая инвестиционная компания не обязана информировать общественность, и даже своих акционеров, о составе своего портфеля, считая его (состав) своей профессиональной тайной. Естественно, что и собственные акционеры, и инвестиционные компании-конкуренты, отдали бы много за то, чтобы обладать информацией о составе портфеля. Единственной информацией о деятельности инвестиционной компании, к которой открыт свободный доступ, является индекс ее доходности в каждый момент времени. Кроме того, известны котировки всех акций на фондовом рынке, где ведет свою деятельность данная инвестиционная компания, независимо от того, входят ли они в портфель данной инвестиционной компании или нет. Задачей нашего исследования будет восстановление процентного состава портфеля инвестиционной компании в каждый момент времени по известным значениям уровня доходности инвестиционной компании и котировкам акций на фондовом рынке.
В 1952 г. Гарри Марковиц опубликовал фундаментальную работу [41], которая является основой подхода к инвестициям с точки зрения современной теории формирования портфеля. Подход Марковица начинается с предположения, что инвестор в момент времени t имеет конкретную сумму денег І..-ДЛЯ инвестирования. Эти деньги будут инвестированы на определенный промежуток времени, называемый периодом владения. В конце периода владения, в момент времени ґ + 1, инвестор может продать часть акций, использовав доход для внутреннего потребления или реинвестировать полученные деньги в другие активы, изменив таким образом структуру портфеля. Решение о том, какое из действий выбрать, инвестор принимает, исходя из стремления увеличить стоимость портфеля в момент времени / + 1 по отношению к моменту времени /.
Эффективность управления портфелем принято согласно Марковицу оценивать с помощью показателя, который называют доходностью портфеля [41] и вычисляют следующим образом Здесь Wt обозначает совокупную цену покупки всех ценных бумаг, входящих в портфель в момент времени /; Wl+i - совокупную рыночную стоимость этих ценных бумаг в момент времени / + 1 и, кроме того, совокупный денежный доход от обладания данными ценными бумагами с момента времени t до момента t +1. Альтернативный метод вычисления доходности портфеля, более подходящий для целей нашей задачи, был предложен Уильямом Шарпом [42]. Этот метод предполагает вычисление доходности портфеля как средневзвешенной суммы доходностей ценных бумаг, являющихся компонентами портфеля. Существенным ограничением данной модели является то, что состав портфеля инвестора предполагается принципиально постоянным и неизменным в течение всего периода владения. Введение этого ограничения было обусловлено тем, что на тот момент еще не существовало эффективных способов решения задачи восстановления нестационарной регрессии, возникающей в результате предположения о нестационарьости портфеля. В данной работе будут предложены эффективные алгоритмы для решения задачи восстановления нестационарной регрессии, поэтому можно отказаться от предположения о постоянстве процентного состава портфеля. Получим модель динамическую модель портфеля из модели (1.14) путем следующих преобразований. Сначала сделаем ряд переобозначений. Совокупная цена акций И7 в момент времени / может быть вычислена как где nl - число различных активов в портфеле инвестора, z\ - цена одной акции /-го актива и т\ - количество акций /-го вида в портфеле в момент времени /.
Вычислительная сложность задачи квадратичного профаммирования
Очевидно, что задача восстановления нестационарной последовательности коэффициентов регрессии приводит к необходимости решения задачи квадратичного программирования специфического вида: с парно-сепарабельной целевой функцией и ограничениям, наложенным на отдельные векторные переменные. На основе анализа литературы было установлено, что существующие методы решения подобного рода задача распадаются на две группы.
Методы, принадлежащие к первой группе, такие как симплекс-метод, метод наискорейшего спуска, непосредственно решают возникающую задачу квадратичного программирования, не учитывая парную сепарабельность задачи. Эти методы являются итерационными и асимптотически точными. Как следствие, их вычислительная сложность пропорциональна кубу числа переменных в составе регрессионной последовательности.
Методы, составляющие вторую группу, принципиально ориентированы на парную сепарабельность задачи и активно используют в своей основе алгоритм динамического профаммирования Беллмана, позволяющий заменить исходную задачу последовательностью существенно более простых задач минимизации промежуточных функций одного аргумента, называемых функциями Беллмана. Однако, численная реализация процедуры динамического профаммирования возможна лишь для тех задач анализа сигналов, в которых множество значений целевых переменных X является конечным, поскольку только в этом случае можно запомнить функции Беллмана в виде таблиц их значений. В то же время во многих задачах анализа сигналов, например, таких как задачи сглаживания, спектрально-временного анализа, целевые переменные являются принципиально непрерывными, и к этим задачам неприменима классическая процедура динамического программирования, чрезвычайно привлекательная своей простотой и высоким быстродействием. В работе [50] метод динамического программирования был распространен на случай непрерывных переменных для квадратичных целевых функций, но этот метод оказывается неприменимым в случае наличия ограничений в виде неравенств, ограничивающих целевые переменные.
Кроме того, существует класс вариационных задач анализа нестационарных сигналов, алгоритмическое решение которых связано с необходимостью многократного определения оптимального значения целевой переменной в отдельно взятой точке оси аргумента при разных моделях сигнала без пересчета оптимальных значений в других точках. Это прежде всего задача оценивания дисперсии аддитивного шума и задача оценивания нарушений гладкости в последовательности коэффициентов регрессии. Эффективные алгоритмы решения таких задач не могут быть построены в рамках классической процедуры динамического программирования «вперед и обратно».
В соответствии с отмеченными аспектами недостаточности существующей алгоритмической схемы вариационного подхода к анализу упорядоченных массивов данных для решения целого ряда практических задач обработки сигналов в данной диссертации ставятся следующие основные задачи исследования: 1. Формальная постановка класса задач оценивания нестационарной модели сигнала как задач парно-сепарабельного квадратичного программирования. 2. Разработка асимптотически точного итерационного алгоритма решения задачи парно-сепарабельного квадратичного программирования, учитывающего специфику целевой функции задачи и обеспечивающего линейную вычислительную сложность относительно числа векторных переменных в отличие от полиномиальной вычислительной сложности алгоритмов решения задачи квадратичного программирования общего вида. и. как следствие, линейную вычислительную сложность алгоритма оценивания нестационарной модели сигнала относительно его длины. 3. Разработка неитерационного алгоритма решения .задачи парно-сепарабельного квадратичного программирования, на основе приближенной реализация процедуры динамического программирования, обеспечивающего неитерационное оценивание нестационарной модели сигнала. 4. Создание альтернативной версии процедуры динамического программирования для оптимизации парно-сепарабельных целевых функций с индивидуальными ограничениями на переменные, обеспечивающей независимое определение оптимальных значений отдельных целевых переменных. 5. Создание методов верификации нестационарной модели сигнала на осно ве принципа скользящего контроля.
Итерационный алгоритм парно-сепарабельного квадратичного программирования
Покажем, что найденное таким образом допустимое направление будет удовлетворять неравенствам (2.23). Очевидно, что найденный вектор допустимого направления удовлетворяет второму неравенству (2.23) /г(А 0, / є / , т.к. его компоненты, соответствующие активным ограничениям А., =0 неотрицательны. Подставим выражение (2.24) для h в первое неравенство в (2.23): что и требовалось. Если h =0, то А 0 есть решение двойственной задачи, а х(А ) -решение исходной задачи квадратичного программирования (2.1)-(2.2). в противном случае вектор h определяет допустимое направление спуска. Минимизируя -W(X) из точки А, вдоль направления п так, чтобы не нарушить неотрицательности множителей Лагранжа, приходим к новой точке А + = А +а h , где а 0 - параметр, определяющий длину шага в допус- тимом направлении. Если параметр a = const, то мы получаем метод градиента. Метод наискорейшего спуска заключается в рассмотрении параметра а как переменной, тогда -W(X +ahk)--Wk(a) будет функцией переменной а. Это квадратичная функция одного аргумента -ff (oO = Ро + Р(с + Р сг . точка минимума которой указывает очередное значение вектора множителей Лагранжа А/и = Хк + a hk . Поскольку предыдущее значение допустимо Хк 0, то в силу условия (2.24) и вытекающего из него очевидного неравенства a 0 допустимо и очередное значение А, + 0. Для вычисления оптимального значения длины шага а необходимо определить значения параметров (З ,, Р, и fik2 квадратичной функции W{a). Для этого достаточно вычислить по формуле три значения функции И7 (a) = W{Xk + an ) для трех разных значений длины шага, например a = 0,1,-1, после чего искомые параметры легко могут быть найдены из решения следующей системы трех линейных уравнений".
После того, как найдено оптимальное значение шага ак и новое значение множителей Лагранжа А. " = А, +а h , необходимо проверить находится ли новая точка А/ + внутри допустимой области А. 0. Если вектор А/" не принадлежит допустимой области, то необходимо скорректировать значение шага ак. Обозначим через J множество индексов отрицательных компонент вектора A/"1: Jk - lj : А, "1"1 0, j = \,...,т\. Вычислим скорректированное значение шага следующим образом:В результате можно сформулировать алгоритма итерационный алгоритм парно-сепарабельного квадратичного программирования.
Для реализации метода наискорейшего спуска необходимо выбрать начальное приближение А,0. В качестве начального приближения можно выбрать точку А,=0, которая соответствует предположению, что точка минимума исходной задачи квадратичного парно-сепарабельного программирования с ограничениями-неравенствами лежит внутри ограничений. Пусть на к-й итерации получен вектор множителей Лагранжа А .
Определим вектор коэффициентов регрессии х(А, ) как результат минимизации функции Лагранжа при фиксированном значении А = А с помощью процедуры «вперед и навстречу». Затем, используя найденное значение вектора коэффициентов определим вектор фадиента h двойственной функции в точке А по формуле (2.8) и допустимое направление спуска hk по формуле (2.24). Если вектор, задающий допустимое направление нулевой hk =0, то А - оптимальное решение двойственной задачи, а найденный вектор коэффициентов рефессии х(А, ) есть оптимальное решение исходной задачи квадратичного программирования. В противном случае, оптимизируя функцию Лагранжа из точки "к вдоль допустимого направления, как это было описано в разделе 2.4, приходим к новой точке +. Таким образом, по своей вычислительной сложности итерационный алгоритм решения задачи минимизации парно-сепарабельной функции с индивидуальными ограничениями на векторные переменные сводится к многократному применению процедуры динамического программирования с линейной вычислительной сложностью для решения аналогичной задачи без ограничений, причем число повторений равно числу итераций.
Основным достоинством метода наискорейшего спуска является то, что он позволяет получить сколь угодно точное решение задачи при неограниченном увеличении числа итераций.
В то же время в процессе анализа сигналов часто приходится решать смежные задачи, например задачу обнаружения нарушений гладкости изменения оцениваемого параметра, задачу оценивания дисперсии шума наблюдения в модели нестационарной регрессии, задачу подбора класса нестационарной модели и т.д. Общим у этих задач является то, что их алгоритмическое решение связано с необходимостью многократного определения оптимального значения целевой переменной в отдельно взятой точке оси аргумента при разных моделях сигнала без пересчета оптимальных значений в других точках. Таким образом, объем вычислений возрастает пропорционально квадрату длины сигнала N , в то время как оценивание последовательности векторов коэффициентов регрессии требует объема вычислений, пропорционального лишь длине сигнала /V. Процедура «вперед и навстречу», разработанная для решения задачи восстановления коэффициентов нестационарной регрессии без ограничений, обеспечивает независимое определение оптимальных значений отдельных целевых переменных. В следующей главе предлагается приближенная реализация процедуры динамического программирования «вперед и навстречу» для случая с ограничениями, позволяющая решать обозначенные выше задачи за два прохода сигнала с числом операций, пропорциональным его длине N .
Алгоритм динамического программирования «вперед и навстречу»..
Таким образом, мы приходим к следующем алгоритму выбора степени сглаживания при анализе нестационарных сигналов. Сигнал обрабатывается при нескольких пробных значениях параметра сглаживания и, изменяющихся в некотором интервале от минимального до максимального, и всякий раз оценивается дисперсия аддитивного шума модели D(u\. В качестве оптимальной степени сглаживания выбирается значение параметра, доставляющего минимальное значение дисперсии:Все задачи анализа сигналов, рассмотренные в главе 1, являются задачами обобщенного сглаживания в том смысле, что минимизация обобщенной целевой функции направлена на согласование размытых локальных оценок, даваемых узловыми функциями \\i,(xl) за счет штрафов на несовпадение значений соседних целевых переменных, налагаемых функциями связи уДх, ,, ,).
Сглаживание размытых локальных оценок имеет своей целью максимальное подавление локальных возмущений без существенного ущерба точности восстановления последовательность значений скрытого параметра нестационарного сигнала X = (x,,...,.vv), поскольку в основе такого подхода к анализу сигналов лежит априорное предположение, что искомая последовательность является достаточно гладкой, и умеренная степень сглаживания в процессе оценивания не может ее существенно исказить.
Однако при обработке сигналов часто возникает ситуация, когда такое априорное предположение не является вполне адекватным природе анализируемого сигнала, и необходимо допустить наличие явных разрывов в подлежащей восстановлению скрытой последовательности параметров нестационарной модели, замаскированных шумом в анализируемом сигнале. В литературе задачи такого рода рассматриваются только для обычного сглаживания сигналов (раздел 1.1.1), и их принято называть задачами сглаживания с сохранением границ. Здесь мы рассмотрим задачу и основную процедуру обобщенного сглаживания с сохранением границ, которые могут быть применены к более широкому классу операций, нежели простое подавление шума. В частности, предлагаемый подход адекватен рассмотренным в главе задачам оценивания нестационарной регрессии (раздел 1.1.4) и спектрально-временного анализа (раздел 1.1.2).
Всякий алгоритм сглаживания с сохранением границ неизбежно является нелинейным, даже если основная процедура сглаживания линейна. Сегодня известно множество методов нелинейного сглаживания [57], среди которых лидирующее место занимают, пожалуй, медианная фильтрация и новые методы, основанные на конкурирующих фильтрах Калмана [58].
Несмотря на большое число методов сглаживания с сохранением границ, все они опираются на предположение о том, что два соседних разрыва, подлежащие обнаружению, всегда расположены не ближе, чем эффективная минимальная ширина окна, достаточного для достижения необходимой степени сглаживания. При нарушении этого предположения алгоритм сглаживания будет воспринимать два последовательных скачка в сигнале или изображении как единый фрагмент шума и попытается подавить их.
Однако для многих прикладных задач характерно требование распознавания именно близко расположенных особенностей исходного сигнала, включая короткие выбросы, без потери степени сглаживания вокруг них. Именно такая необходимость побуждает к поиску альтернативных путей обнаружения разрывов в сглаживаемых сигналах. Основная идея предлагаемого здесь подхода состоит в поочередном поиске отдельных точек разрыва и внесении их в модель сигнала таким образом, что на каждом шаге ищется наиболее очевидная из еще не описанных особенностей [26].
Каждая из основанных на модельных представлениях функций связи уД х рХ,) необходима для наложения индивидуального штрафа на различия в значениях в соответствующей паре соседних элементов, т.е. на несглаженность полученного массива на паре соседних узлов цепи (t — \,t), поэтом)
Чем быстрее возрастает функция связи, рассматриваемая как несоответствие между х,_, и х/5 быть может только в одном направлении в пространстве R" , тем более сглаженным будет результат обработки сигнала х, в соседних точках (/-1,/) в этом направлении. В частности, если уДх, ,,х;) = 0 в некотором направлении, то это означает что соответствующий вид скачка в R" разрешен, т.е. узаконен в модели и будет полностью сохранен в ходе обработки данных.
Несмотря на тот факт, что мы не будем проводить в этой работе никакие вероятностные аналогии, вариационный подход к задачам обобщенной обработки сигналов выражает конечную сущность статистического подхода в марковском предположении о скрытом процессе. А именно, процедуры динамического программирования делают использование цепочечной сепарабельности целевой функции очень похожей на калмановскую фильтрацию и сглаживанием сигналов, и только поэтому алгоритмы описанные в [58] должны рассматриваться как непосредственные прародители более общих методов рассматриваемых в этой работе.
