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

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

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

Поскольку состояния φ[i; k] – ненаблюдаемые, необходимо суммировать по всемих возможным значениям для вероятностей переходов между состояниями Ts[m],s[j] ивероятностей эмиссии Aik,s[j] , параметры которых предстоит оцениватьL = logKY!p x[i] | Ts[m], s[j] , Aik, s[j]=i=1=KXlog p x[i] | Ts[m], s[j] , Aik, s[j]=i=1=KXlog i=1=KX=i=1Xp x[i], φ[i] | Ts[m], s[j] , Aik, s[j]  =φ[i]log i=1KXX p x[i] | φ[i], Ts[m], s[j] , Aik, s[j] × p x[i] | Ts[m], s[j]  =φ[i]log Xφ[i]T0,φ[i;k]NYi=1!Aik,φ[i;k]NY!Tφ[i;k],φ[i;k−1]  .i=1(2.2.1)Правдоподобие для одного временного ряда факторизуется на три множителя, какрезультат того, что условные вероятности неявных в HMM-модели зависят толькоот значений переменных на одном временном шаге.

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

определения вероятности начального состояния;202. эмиссии символа;3. перехода в новое состояние;4. эмиссии символа; и т.д. n i oДля оценки параметров Ts[m],s[j] , Ak,s[j] может использоваться максимум правдоподобия, но поскольку рассматривается модель со скрытыми переменными, нижеиспользуется алгоритм ожидания-максимизации правдоподобия (the ExpectationMaximization algorithm) (называемый также алгоритмом Баума-Уолша (the BaumWelch algorithm) в контексте скрытой Марковской модели).

Однако чтобы использовать алгоритм ожидания-максимизации правдоподобия, необходимо вычислитьпредельные апостериорные вероятности каждого состояния p(φ[i; k] | x[i]) и определить вероятности переходов. Кроме этого, необходимо вычислить парные предельныеапостериорные вероятности p(φ[i; k], φ[i; k + 1] | x[i]). Их вычисление в скрытой Марковской модели основано на алгоритме динамического программирования, в контекстеэтой модели называемого алгоритмом прямой и обратной рекурсии.2.2.1Алгоритм прямой и обратной рекурсииПредположим необходимо вычислить правдоподобие наблюдаемых временных рядов при заданных значениях параметров (например, некоторые значения параметроввероятностей переходов и параметров вероятностей эмиссии).Из (2.2.1) следует, что это вычисление включает суммирование по всем возможным последовательностям состояний φ[i], с оценкой временной сложности O(KM N ),где K – это число наблюдаемых временных рядов длиной N , M – это число скрытых состояний в модели.

Но поскольку многие частичные пути являются общими для возможных последовательностей скрытых состояний, это вычисление может быть оптимизировано. Приведенный ниже алгоритм прямой и обратной рекурсии (Forward-Backward algorithm) выполняет необходимое суммирование с оценкой временной сложности O(KM N ) (если матрица переходов разреженная, временная оценка сложности будет меньше). Введем обозначение совместной вероятностиα[i; k; j] ≡ p (x[i; 1], x[i; 2], ..., x[i; k], φ[i; k] = s[j]). Для всех i и j, после инициализацииα[i; 1; j] ≡ Ai1,выполняется прямая рекурсия для k = 1, N :s[j]T0,s[j]21α[i; k; j] ≡Aik,s[j]MXα[i; k − 1; m]Ts[m],s[j] .(2.2.2)m=1Если рекурсия (2.2.2) завершена, то можно вычислитьp(x[i]) =MXp (x[i; 1], x[i; 2], ..., x[i; N ], φ[i; N ] = s[j]) =j=1MXα[i; N ; j](2.2.3)j=1Таким образом, логарифм правдоподобия L определяется какL=KXi=1log (p(x[i])) =KXlogi=1MX!α[i; N ; j] .(2.2.4)j=1Для вычисления предельных апостериорных вероятностей (marginals of the posterior)p(φ[i; k] | x[i]) и p(φ[i; k], φ[i; k + 1] | x[i]) используется формула Байеса и правилаусловной вероятностиp (x[i] | φ[i; k] = s[j]) p (φ[i; k] = s[j])=p(x[i])p (x[i; 1]...x[i; k] | φ[i; k] = s[j]) p (x[i; k + 1]...x[i] | φ[i; k] = s[j]) p (φ[i; k] = s[j])==p(x[i])p (x[i; 1]...x[i; k], φ[i; k] = s[j]) p (x[i; k + 1]...x[i] | φ[i; k] = s[j])=≡p(x[i])α[i; k; j]p (x[i; k + 1], ..., x[i] | φ[i; k] = s[j])≡p(x[i])p(φ[i; k] = s[j] | x[i]) =(2.2.5)иp(φ[i; k − 1] = s[j], φ[i, k] = s[m] | x[i]) =p (x[i] | φ[i; k − 1] = s[j], φ[i; k] = s[m]) p (φ[i; k − 1] = s[j], φ[i; k] = s[m])≡p(x[i])α[i; k − 1; j]p (x[i; k]...x[i, N ] | φ[i; k] = s[m]) Ts[j],s[m]≡.p(x[i])=(2.2.6)Вычисление совместных вероятностей β[i; k; j] ≡ p(x[i; k+1], x[i; k+2], ..., x[i; N ], φ[i; k] =s[j]) позволяет вычислить вероятности (2.2.5)–(2.2.6).

Для всех k и j, выполняетсяинициализацияβ[i; N ; j] = 122и обратная рекурсия для k = N − 1, 1β[i; k; j] =MXTs[j],s[m] Aik+1,s[m] β[i; k + 1; m](2.2.7)m=1Если выполнены прямая (2.2.2) и обратная (2.2.7) рекурсии, определяющие α[i; k; j]и β[i; k; j], то предельные апостериорные вероятности (2.2.5) и (2.2.6) вычисляютсяпо формуламp(x[i]) =MXα[i; N ; j] ≡j=1MXα[i; k; j]β[i; k; j](2.2.8)j=1p(φ[i; k] = s[j] | x[i]) =p(φ[i; k − 1] = s[j], φ[i; k] = s[m] | x[i]) =α[i; k; j]β[i; k; j]p(x[i])α[i; k − 1; j]Ts[j],s[m] Aik,s[m] β[i; k; m]p(x[i])(2.2.9)(2.2.10)Эффективные вычисления правдоподобия и предельных апостериорных вероятностей (2.2.9)–(2.2.10) необходимы, поскольку параметры оцениваются посредствомалгоритма ожидания и максимизации правдоподобия.

После того как это обучениезавершено, представляет интерес апостериорная вероятность последовательностискрытых состояний p(φ | x[i]) , которая определяет степень уверенности в том, чтоименно эта последовательность состояний генерирует наблюдаемый временной ряд.Тогда по максимуму апостериорной вероятности для каждого наблюдаемого временного ряда можно определить наиболее вероятную последовательность скрытыхсостояний (the maximum a posteriori (MAP) sequence). Как и выше, это выполняетсяпосредством динамического программирования.2.2.2Алгоритм ВитербиЧтобы вычислить последовательность скрытых состояний для временного рядас номером i по максимуму апостериорной вероятности (MAP state sequence) φ̄[i] =argmax p(φ[i] | x[i]) следует, во-первых, учесть, что p(φ[i] | x[i]) ∝ p(φ[i], x[i]),φ[i]поскольку p(φ[i] | x[i]) =p(φ[i], x[i]).p(x[i])То есть, если найдена последовательность, котораядает наивысшее совместное правдоподобие, то это та же последовательность, что иполученная по максимуму апостериорной вероятности.

Пусть ρ[i; k; j] – вероятностьнаиболее правдоподобной частичной последовательности из начального моментавремени в состояние s[j] в момент времени k, т.е.ρ[i; k; j] ≡ p φ̄[1], ..., φ̄[k − 1], φ[i; k] = s[j], x[i; 1], ..., x[i; k] ,(2.2.11)23где φ̄[i; k] обозначает состояние в момент времени k вдоль наиболее правдоподобнойпоследовательности состояний. Тогда если для всех j известно значение ρ[i; N ; j],легко найти последнее состояние в последовательности состояний по максимумуапостериорной вероятности (через совместную вероятность)φ̄[i; N ] = s[m] , где m = argmax ρ[i; N ; j].jТакже, если для всех j известно значение ρ[i; N − 1; j], то можно найти второе из последних состояний последовательности скрытых состояний по максимумуапостериорной вероятностиφ̄[i; N − 1] = s[m] , где m = argmax ρ[i; N − 1; j] · Ts[j],φ̄[i;N ]и т.д.jТаким образом, последовательность по максимуму апостериорной вероятности можетбыть вычислена прямой рекурсией, которая идентична α-рекурсии (2.2.2) за исключением того, что оператор суммирования заменяется оператором максимума.

Такжезапоминается последовательность переходов между состояниями, которая приводит кмаксимуму на каждом временном шаге, и затем эта последовательность проходитсяназад, чтобы получить последовательность состояний по максимуму апостериорнойвероятности φ̄[i]. Для всех значений i и j производится инициализацияρ[i; k; j] = Ai1,s[j] · T0,s[j]и выполняется рекурсия для k = 1, Nρ[i; k; j] = Aik,s[j] max ρ[i; k − 1; m] · Ts[m],s[j]m(2.2.12)с сохранением обратных указателейτ [i; k; j] = argmax ρ[i; k − 1; m] · Ts[m],s[j] .(2.2.13)mЗатем заполняется последовательность состояний по максимуму апостериорной вероятности, начиная в момент времени k = Nφ̄[i; k] = s[j] , где j = argmax (ρ[i; N ; m]) ,mи проходя назад для k = N − 1, 1 через хранимые τ [i; k; j] (2.2.13) получаемφ̄[i; k] = s[j] , где j = argmax (τ [i; k + 1; m]) .m24Этот алгоритм поиска последовательности состояний скрытой Марковской модели помаксимуму апостериорной вероятности известен как алгоритм Витерби (the Viterbialgorithm) [48], [21].252.3Выравнивание и масштабирование асинхронных временных рядовПри обучении CPM-модели определяется скрытая запись (latent trace), вероятности переходов, управляющие Марковской эволюцией состояний времени и масштаба,суммарный уровень шума наблюдаемого временного ряда и его глобальный фактор масштаба.

После обучения скрытая запись имеет более высокое разрешение посравнению с ее копиями − наблюдаемыми временными рядами. Поэтому базовымипонятиями CPM-модели являются1. Скрытая запись, являющаяся базовым представлением без шума для наборанаблюдаемых временных рядов.2. Полученное в результате обучения отображение наблюдаемого времени (времени, в котором записан наблюдаемый временной ряд) и скрытого времени,индексируемого скрытой записью.

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

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