Метод оценки развития газодинамических процессов с помощью скрытой марковской модели (1187404), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Три стандартных способа усовершенствования DTW-алгоритма:1. специфицировать минимальный/максимальный наклон пути искажения времени;2. специфицировать максимальную полосу для пути искажения времени (например,насколько этот путь может отклоняться от нейтрального пути;3. считать предпочтительным путь, состоящий из более коротких, либо долеедлинных шагов.Пример локального ограничения пути – это перечисление возможных точечныхотображений (i0 , j 0 ) , из которых путь искажения времени был продолжен в (i, j).

Так,13использование точечных отображений (i−1, j −1), (i−1, j −2), (i−2, j −1) как локального ограничения пути, приводит к следующему потенциальному результату: индексынекоторых элементов временных рядов могут быть пропущены в минимальном пути искажения времени. Это оправданно, если некоторые элементы выравниваемыхвременных рядов представляют случайные отклонения. При рассматриваемом локальном ограничении элементы матрицы D аккумулированных расстояний определяютсяпосредством рекурсииD[j; k] = d[j; k] + minD[j − 1; k − 1];D[j − 1; k − 2];D[j − 2; k − 1].(1.1.6)Рекурсия (1.1.6) представлена на рис.3.В процессе совершенствования DTW-алгоритмаисследовано много локальных ограничений(условий непрерывности), включая ассиметричные, при которых оказывается существенным порядок временных рядов.

Обзорразличных локальных ограничений содержится в [39].Рис. 3: Рекурсия (1.1.6) как отражениелокального ограничения(условия непрерывности)Преимущества DTW-алгоритма:• адекватно выполняет выравнивание временных рядов с различным темпомвременных изменений;• дает предсказуемые результаты.Проблемы, связанные с использованием DTW-алгоритма:• при формировании пути искажения времени локальные ограничения (условиянепрерывности) являются, до некоторой степени, произвольными;• при одновременном выравнивании нескольких временных рядов только одинвременной ряд может использоваться в качестве шаблона (прототипа).Из последнего замечания следует, что проблема выравнивания временных рядовплохо сформулирована. Для нее не существует единственного наилучшего решения.Например, если имеются временные ряды, представляющие записи речи несколькихдикторов с их собственным постоянным темпом, то неизвестно, какая шкала отсчетавремени будет наилучшей для отображения всех временных рядов. С равным правомможет использоваться шкала времени самого медленного, или самого быстрого из14дикторов, произносивших одну и ту же речь, или любая шкала времени между ними.Принцип «бритвы Оккама» (Occam’s razor principle) утверждает, что среди прочихравных самым лучшим является самое простое решение.

В рассматриваемой проблемевыравнивания временных рядов это означает, что шкала отсчета времени должна бытьтакой, в которой достигается наиболее простое отображение наблюдаемых временныхрядов (в эту шкалу отсчета), при условии, что не страдает качество выравниваниявременных рядов.151.2Другие подходы к выравниванию временных рядовВ работе [40] вводится модель кластеризации кривых (curve clustering model), вкоторой происходит обучение функции искажения времени h(t) для каждого временного ряда посредством оценки ее относительной кривизны w =D2 hDh.

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

Шаблон регрессии (regression template)обучается по критерию «Прокрустово ложе» (Procrustes fitting criterion). Хотя этоитеративное обучение шаблона может хорошо работать на практике, для него нетгарантии сходимости.В работе [41] вводится вероятностная модель, которая совместно осуществляеткластеризацию и выравнивает кривые. Часть модели, ответственная за выравнивание,представляется как регрессия в виде B-сплайна, в которой зависимая переменнаяy[i] – это амплитуда измеренного сигнала, а вход x[i] – это вектор временных элементов (i индексирует выравниваемые входные вектора).

Выравнивание реализуетсярегрессией посредством четырех параметров: a[i], b[i] – контролирующих масштабирование и смещение во времени, и c[i], d[i] – контролирующих масштабирование исмещение в пространстве амплитуд: y[i] = [a[i]x[i] − b[i]]β[i] + d[i] + ε[i], где β – этокоэффициенты регрессии и ε[i] – это Гауссов шум с нулевым средним и ковариацией σ 2 [i] , и a[i]x[i] − b[i] представляет матрицу регрессии (матрицу базиса сплайна)оцененную в преобразованном времени. Таким образом, метод учитывает измененияв масштабе сигнала при выравнивании. Отметим, что кроме коррекции времени,может потребоваться коррекция систематической разницы в амплитуде сигнала вкаждом временном отсчете (соответствующем фиксированной частоте дискретизациивремени).

Это проблема нормализации. Модель непрерывного профиля (ContinuousProfile Model (CPM)) позволяет решить обе эти проблемы.16Глава 2. Марковская модель непрерывного скрытогопрофиля2.1Модели непрерывных профилей (CPM-модели)Для одновременного анализа наборов асинхронных временных рядов используютсямодели непрерывных профилей (Continuous Profile Models (CPM) [42]. В этих генеративных (производящих) моделях, каждый временной ряд, принадлежащий одномуклассу, генерируется в результате преобразования с шумом единственной скрытойзаписи (latent trace).

Для временных рядов нескольких классов имеется одна скрытая запись на каждый класс, и временные ряды генерируются из соответствующейспецифической для класса скрытой записи. Скрытая запись – это базовое представление без шума для набора дублирующих друг друга наблюдаемых временных рядов.Наблюдаемый временной ряд генерируется CPM-моделью при продвижении черезпоследовательность скрытых состояний и эмиссии элемента этого временного ряда,как это происходит в скрытой Марковской модели (Hidden Markov Model (HMM)).Поскольку CPM-модель представляет собой скрытую Марковскую модель, здесьописаны ее наиболее существенные черты.Скрытая Марковская модель используется для моделирования временных рядов сдискретными или непрерывными значениями, и представляется двумя способами:1.

как случайная машина с конечным числом состояний (переходы между состояниями случайные, также как и эмиссия символов из этих состояний);2. как графическая модель, в которой скрытые/ненаблюдаемые состояния/переменныесвязаны друг с другом в направленной (ориентированной) цепочке, каждыйскрытый узел которой имеет потомка, являющегося наблюдаемой переменной(рис.4).Рис. 4: Последовательность состояний скрытой Марковской модели и эмиссия элементовнаблюдаемого временного ряда.17Представление скрытой Марковской модели, как графической модели, определяет для нее контекст родственных моделей в пространстве состояний (State SpaceModels) [43]. Например, метод Монте-Карло для Марковских цепей (Markov ChainMonte Carlo (MCMC)) используется, чтобы выполнить обучение/вывод [44] – [45].Независимо от принятого представления, скрытая Марковская модель имеет следующие основные характеристики:1. Наблюдаемые временные ряды генерируются при продвижении через случайнуюпоследовательность скрытых/ненаблюдаемых состояний, и в каждом скрытомсостоянии происходит случайная эмиссия элемента временного ряда.2.

Генерируемое элемент наблюдаемого временного ряда зависит только от скрытого состояния в текущий момент времени, а скрытое состояние в текущий моментвремени зависит только от предыдущего скрытого состояния (это называетсяМарковским свойством).3. Вычисления эффективно выполняются посредством динамического программирования, которое повторно использует частичные вычисления взамен полныхвычислений.Подробное описание скрытой Марковской модели приведено в [46].В CPM-модели каждое скрытое состояние представляет конкретной индекс скрытой записи, и эмиссия элемента из этого состояния зависит от элемента скрытойзаписи с этим индексом. Кроме этого, для учета изменения амплитуды в пределахвременного ряда и между наблюдаемыми временными рядами, к состояниям скрытого времени добавляется набор состояний скрытого масштаба, которые определяютмасштаб элемента временного ряда по отношению к соответствующему элементускрытой записи.

Таким образом, полное пространство скрытых состояний являетсяпроизведением пространства состояний скрытого времени и пространства состоянийскрытого масштаба. Наконец, каждый наблюдаемый временной ряд масштабируетсяпостоянным глобальным фактором масштаба.CPM-модель подобна скрытой Марковской модели профиля (Profile HMM), которая используется в молекулярной биологии для одновременного выравниваниянескольких дискретных последовательностей [47]. Profile-HMM-модель – это HMMмодель, переходы в которой ограничены состояниями ’Delete’ и ’Insert’, причем впервом состоянии отсутствует эмиссия.

Имеется также ограничение переходов слева направо (например, можно продвигаться только вперед по последовательности).18Поэтому, вывод в Profile-HMM-модели линейный по числу состояний (а не квадратичный, как в случае общей HMM-модели). Несколько последовательностей являются входами Profile-HMM-модели при обучении. После этого Profile-HMM-модельсодержит выдержку (квинтэссенцию) статистических свойств, разделяемых входными последовательностями.

Можно представлять CPM-модель, как условный аналогProfile-HMM-модели для случая непрерывных данных. Ниже описаны алгоритмы дляскрытой Марковской модели (HMM-модели).192.2Алгоритмы для скрытой марковской модели (HMM)Пусть x[i] = {x[i; k], k = 1, N } – K наблюдаемых временных рядов длиной N(рис.4). Пусть набор возможных состояний скрытой Марковской модели S = {s[j], j =1, M }. Для наблюдаемого временного ряда x[i] = {x[i; k], k = 1, N } временнаяпоследовательность скрытых состояний φ[i] = {φ[i; k], k = 1, N } (рис.4), где φ[i; k] ∈S.

В Марковской модели вероятности переходов между состояниями s[m] и s[j] –Ts[m],s[j] ≡ p(φ[i; k] = s[j] | φ[i; k − 1] = s[m]) не зависят от номера i временного ряда.При условии, что скрытая последовательность φ[i] в момент времени k имеет состояниеs[j], вероятность эмиссии x[i; k] равна Aik,s[j] ≡ p(x[i; k] | φ[i; k] = s[j]). При наличииэтой модели можно написать логарифм правдоподобия L наблюдаемых временныхрядов.

Характеристики

Список файлов ВКР