автор: Тан Тянь Тянь Тянь, девушка из гуманитарных наук, время от времени делится статьями по анализу данных и понимает данные с самой простой точки зрения. Знать колонку: Анализ экономических и управленческих данных

Скрытая марковская модель — едва ли не самая сложная модель, с которой приходится сталкиваться при обучении. модель скрытой лошади, алгоритм направления, неконтролируемое обучение Баума-Уэлча, алгоритм Витерби. Более четкое понимание Скрытой Марковской Модели, ведь на практике нам нужно всего лишь вызвать библиотеку, чтобы решить задачу одной строкой кода.

При вызове функции сегментации слов для сегментации слов используется принцип скрытой марковской модели HMM.

Конкретный принцип объясняется следующим образом:

1. Определение скрытой марковской модели

Скрытая модель Маркова — это вероятностная модель временных рядов, которая описывает процесс случайной генерации ненаблюдаемой случайной последовательности состояний из скрытой цепи Маркова, а затем генерации наблюдения из каждого состояния для генерации случайной последовательности наблюдений. Последовательность состояний, случайно генерируемых скрытой цепью Маркова, называется последовательностью состояний; каждое состояние порождает наблюдение, а результирующая случайная последовательность наблюдений называется последовательностью наблюдения. Каждая позиция последовательности, в свою очередь, может рассматриваться как момент.

Что такое скрытая цепь Маркова? Проще говоря, это означает рассматривать временную шкалу как цепочку, и каждый узел зависит только от первых N узлов. Точно так же, как когда вы открываете круг друзей, вы можете судить о том, что он собирается делать дальше, по недавнему статусу вашего друга.

Далее введем некоторые обозначения, чтобы выразить определение:

Пусть Q — множество всех возможных состояний, а V — множество всех возможных наблюдений.

где N — количество возможных состояний, а M — количество возможных наблюдений.

Состояние q невидимо, наблюдение v видимо. Применительно к системе маркировки частей речи слово — v, а часть речи — q.

I — последовательность состояний длины T, а O — соответствующая последовательность наблюдений.

Это можно понимать как обучающий набор данных слова (O) + часть речи (I) или словарь в системе сегментации китайских слов.

Задайте A как матрицу вероятности перехода состояния:

в,

— вероятность перехода в состояние qj в момент времени t+1 при условии, что момент времени t находится в состоянии qi.

На самом деле это представляет собой HMM первого порядка с предположением, что каждое состояние связано только с предыдущим состоянием.

B — матрица вероятности наблюдения:

в,

– вероятность генерации наблюдения vk при условии, что момент времени t находится в состоянии qj.

π — вектор вероятности начального состояния:

в,

— вероятность находиться в состоянии qj в момент времени t=1.

Скрытая марковская модель определяется вектором вероятности начального состояния π, матрицей вероятности перехода состояния A и матрицей вероятности наблюдения B. π и A определяют последовательность состояний, а B определяют последовательность наблюдения. Следовательно, Скрытая Марковская Модель может быть представлена ​​троичной записью, т.е.

Три переменные в скобках называются тремя элементами скрытой марковской модели. Добавление определенного набора состояний Q и последовательности наблюдений V составляет пятерку HMM.

Матрица вероятности перехода состояния A и вектор вероятности начального состояния π определяют скрытую цепь Маркова и генерируют ненаблюдаемую последовательность состояний. Матрица вероятности наблюдения B определяет, как наблюдения генерируются из состояний, а комбинация с последовательностью состояний определяет, как генерируется последовательность наблюдений.

Из определения скрытая марковская модель делает два основных предположения:

(1) Гипотеза однородного марковского свойства, т. е. предполагается, что состояние скрытой цепи Маркова в любой момент времени t зависит только от состояния в предыдущий момент времени и не имеет ничего общего с состоянием и наблюдением в другие моменты времени .

(2) Предположение о независимости наблюдения, то есть предполагается, что наблюдение в любой момент времени зависит только от состояния цепи Маркова в этот момент и не имеет ничего общего с другими наблюдениями и состояниями.

2 Процесс генерации последовательности наблюдений

Согласно определению скрытой марковской модели процесс генерации последовательности наблюдений O длины T описывается следующим образом:

Алгоритм формирования последовательности наблюдений:

Вход: скрытая марковская модель, длина последовательности наблюдений

Выход: последовательность наблюдений

(1) По распределению начального состоянияпроизводить состояние

(2) Пусть t=1

(3) По состояниюНаблюдаемое распределение вероятностейгенерировать

(4) По статусуРаспределение вероятности перехода состоянияпроизводить состояние

Пусть t=t+1, если t

2.1 Python-реализация генерации последовательности наблюдений

Алгоритм сначала инициализирует два вектора длины T, затем генерирует первое состояние в соответствии с начальным распределением состояний pi, извлекает распределение вероятностей наблюдений, соответствующих состояниям, и генерирует наблюдение.

Следующим шагом является извлечение распределения вероятности перехода состояния в соответствии с предыдущим состоянием для создания состояния, а затем извлечение распределения вероятности наблюдения, соответствующего состоянию, для создания наблюдения. Повторите этот шаг, чтобы получить векторы наблюдения и состояния длины T.

код показывает, как показано ниже:

import numpy as npclass HMM():    def __init__(self, A, B, pi):        self.A = A        self.B = B        self.pi = pi    def simulate(self, T):        # draw_from接受一个概率分布，然后生成该分布下的一个样本。            def draw_from(probs):            return np.where(np.random.multinomial(1, probs) == 1)[0][0]        observations = np.zeros(T, dtype=int)        states = np.zeros(T, dtype=int)            states[0] = draw_from(self.pi)        observations[0] = draw_from(self.B[states[0], :])        for t in range(1, T):            states[t] = draw_from(self.A[states[t-1], :])            observations[t] = draw_from(self.B[states[t], :])        return states, observationsскопировать код

3 Три основные проблемы скрытых марковских моделей

(1) Проблема расчета вероятности. данная модельи последовательность наблюдения, рассчитанный в моделиВероятность появления следующей последовательности наблюдений O.

(2) Проблемы с обучением. известная последовательность наблюдений, расчетная модельтакие, что наблюдаемая вероятность последовательности в этой моделимаксимум. То есть использовать метод оценки максимального правдоподобия для оценки параметров.

(3) Проблема прогнозирования, также известная как проблема декодирования. известная модельи последовательность наблюдения, найти условную вероятность для заданной последовательности наблюденийсамая большая последовательность состояний. То есть, учитывая последовательность наблюдений, найти наиболее вероятную соответствующую последовательность состояний.

В следующих разделах будут представлены решения этих основных проблем одно за другим.

4 Алгоритм расчета вероятности

В этом разделе представлены прямой и обратный алгоритмы для вычисления вероятности последовательности наблюдений.Прямой и обратный алгоритм заключается в том, чтобы найти прямую вероятность первого состояния или обратную вероятность последнего состояния, а затем перейти назад или назад.Он может быть выдвинута вперед.

4.1 Прямой алгоритм

Прямая вероятность с учетом скрытой марковской модели, последовательность наблюдений до момента времени t определяется каки статусВероятность - это прямая вероятность, обозначаемая как

Перспективную вероятность можно найти рекурсивнои вероятность последовательности наблюдений.

Прямой алгоритм для вероятности последовательности наблюдений:

Вход: скрытая марковская модель, последовательность наблюдения;

Выход: вероятность последовательности наблюдений.

(1) Начальное значение

Определение прямой вероятности определяет в общей сложности два условия: одно — это последовательность наблюдений на данный момент, а другое — текущее состояние. Следовательно, расчет начального значения также имеет два элемента (наблюдение и состояние), один — вероятность начального состояния, а другой — вероятность появления в текущем наблюдении.

(2) Рекурсивная пара

Каждая рекурсия также состоит из двух частей: фигурные скобки — это вероятность того, что текущее состояние равно i, а первые t последовательности наблюдений соответствуют требованиям, а за скобками — вероятность того, что состояние i произойдет при наблюдении t+1. .

(3) Прекращение

Поскольку в момент времени T существует всего N состояний, в которых происходит последнее наблюдение, окончательный результат состоит в суммировании этих вероятностей.

4.2 Реализация прямого алгоритма на Python

код показывает, как показано ниже:

 1def forward(self, obs_seq): 2    """前向算法""" 3    N = self.A.shape[0] 4    T = len(obs_seq) 5    F = np.zeros((N, T)) 6    F[:, 0] = self.pi * self.B[:, obs_seq[0]] 7    for t in range(1, T): 8        for n in range(N): 9            F[n, t] = np.dot(F[:, t-1], (self.A[:, n])) * self.B[n, obs_seq[t]]10    return Fскопировать код

4.3 Обратный алгоритм

Обратный алгоритм эквивалентен обратной рекурсии прямого алгоритма.Подробности см. на стр. 178 книги.

4.4 Реализация обратного алгоритма на Python

код показывает, как показано ниже:

 1def backward(self, obs_seq): 2    """后向算法""" 3    N = self.A.shape[0] 4    T = len(obs_seq) 5    M = np.zeros((N, T)) 6    M[:, T-1] = 1 7    # 或者M[:, -1:] = 1，列上表示最后一行 8    for t in reversed(range(T-1)): 9        for n in range(N):10            M[n, t] = np.dot(self.A[n, :], M[:, t+1]) * self.B[n, obs_seq[t+1]]11    return Mскопировать код

5 учебных вопросов

Алгоритм Баума-Уэлча также является алгоритмом EM, известная последовательность наблюдений, расчетная модельтакие, что наблюдаемая вероятность последовательности в этой моделимаксимум. То есть использовать метод оценки максимального правдоподобия для оценки параметров. И как решить эту задачу оценки, здесь используется алгоритм Баума-Уэлча. 

Подробное объяснение алгоритма см. по адресу: https://blog.csdn.net/u014688145/article/details/53046765?locationNum=7&fps=1.

5.1 Реализация алгоритма Баума-Уэлча на Python

код показывает, как показано ниже:

 1def EM(self, observation, criterion=0.05): 2    """EM算法进行参数学习""" 3    n_state = self.A.shape[0] 4    n_sample = len(observation) 5    done = 1 6    while done: 7        Alpha = self.forward(observation) 8        Beta = self.backward(observation) 9        xi = np.zeros((n_state, n_state, n_sample-1))10        gamma = np.zeros((n_state, n_sample))11        for t in range(n_sample-1):12            denom = np.sum(np.dot(Alpha[:, t].T, self.A) * self.B[:, observation[t+1]].T * Beta[:, t+1].T)13            sum_gamma1 = np.sum(Alpha[:, t] * Beta[:, t])14            for i in range(n_state):15                numer = Alpha[i, t] * self.A[i, :] * self.B[:, observation[t+1]].T * Beta[:, t+1].T16                xi[i, :, t] = numer/denom17            gamma[i, t] = Alpha[i, t] * Beta[i, t] / sum_gamma118        last_col = Alpha[:, n_sample-1].T * Beta[:, n_sample-1]19        gamma[:, n_sample-1] = last_col / np.sum(last_col)20        # 更新参数21        n_pi = gamma[:, 0]22        n_A = np.sum(xi, 2) / np.sum(gamma[:, :-1], 1)23        n_B = np.copy(self.B)24        num_level = self.B.shape[1]25        sum_gamma = 026        a = 027        for lev in range(num_level):28            for h in range(n_state):29                for t in range(n_sample):30                    sum_gamma = sum_gamma + gamma[h, t]31                    if observation[t] == lev:32                        a = a + gamma[h, t]33                n_B[h, lev] = a / sum_gamma34                a = 035        # 检查阈值36        if np.max(np.abs(self.pi-n_pi)) < criterion and np.max(np.abs(self.B-n_B)) < criterion \37                and np.max(np.abs(self.A-n_A)) < criterion:38            done = 039        self.A, self.B, self.pi = n_A, n_B, n_pi40    return self.A, self.B, self.piскопировать код

6 алгоритмов прогнозирования

6.1 Алгоритм Витерби

ввод: модельи наблюдения;

вывод: оптимальный путь.

⑴Инициализация

(2) Рекурсия. правильно

(3) Прекращение

(4) Оптимальный возврат пути. правильно

найти оптимальный путь.

6.2 Реализация алгоритма Витерби на Python

Алгоритм Витерби — это алгоритм динамического программирования, используемый для нахождения последовательности состояний скрытого пути Витерби, которая с наибольшей вероятностью создаст последовательность наблюдаемых событий. Алгоритм Витерби на самом деле является задачей оптимального выбора многоступенчатой, пошаговой, многоступенчатой ​​модели.Все выборки на каждом шаге сохраняют минимальную общую стоимость (или максимальное значение) текущего выбора от всех предыдущих шагов до текущего шаг и текущая стоимость Выбор предыдущих шагов в кейсе. После вычисления всех шагов по очереди оптимальный путь выбора находится путем возврата.

код показывает, как показано ниже:

 1def viterbi(self, obs_seq): 2    """viterbi算法预测状态序列""" 3    N = self.A.shape[0] 4    T = len(obs_seq) 5    P = np.zeros((N, T)) 6    prev_point = np.zeros((N, T)) 7    prev_point[:, 0] = 0 8    P[:, 0] = self.pi * self.B[:, obs_seq[0]] 9    for t in range(1, T):10        for n in range(N):11            P[n, t] = np.max(P[:, t - 1] * self.A[:, n]) * self.B[n, obs_seq[t]]12            prev_point[n, t] = np.argmax(P[:, t - 1] * self.A[:, n] * self.B[n, obs_seq[t]])13    return P, prev_pointскопировать код

6.3 Python-реализация генерации оптимального пути

Оптимальный путь на самом деле является частью алгоритма Витерби.Когда оптимальное состояние i в момент времени T определено, оптимальный путь затем находится путем возврата.

код показывает, как показано ниже:

 1def build_path(self, obs_seq): 2    """return the optimal path""" 3    P, prev_point = self.viterbi(obs_seq) 4    T = len(obs_seq) 5    opt_path = np.zeros(T) 6    last_state = np.argmax(P[:, T-1]) 7    opt_path[T-1] = last_state 8    for t in reversed(range(T-1)): 9        opt_path[t] = prev_point[int(opt_path[t+1]), t+1]10    last_path = reversed(opt_path)11    return last_pathскопировать код

6.4 Практика

Протестируйте с данными случая в «Статистических методах обучения», код выглядит следующим образом:

 1if __name__ == '__main__': 2    # 用《统计学习方法》中的案例进行测试 3    A = np.array([[0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5]]) 4    B = np.array([[0.5, 0.5], [0.4, 0.6], [0.7, 0.3]]) 5    pi = np.array([0.2, 0.4, 0.4]) 6    test1 = HMM(A, B, pi) 7    obs_seq = [0, 1, 0] 8    print(test1.forward(obs_seq)) 9    print(test1.backward(obs_seq))10    print(test1.viterbi(obs_seq))11    print(test1.build_path(obs_seq))12    print(test1.EM(obs_seq))скопировать код

Ссылаться на:

1. Ли Ханг, Статистические методы обучения [M], Пекин: Издательство Университета Цинхуа, 2012 г.

Ферма кода Скрытая марковская модель: http://www.hankcs.com/ml/hidden-markov-model.html