Скрытая марковская модель (HMM) для интеллектуальных алгоритмов

предисловие

Предыдущая «модель Маркова» в основном изучает вероятность последовательностей, которые можно непосредственно наблюдать. Цепи Маркова могут быть установлены с помощью гипотезы Маркова для решения некоторых проблем с последовательностями. Но иногда наблюдаемый объект не является целевым объектом, с которым мы имеем дело, его законы скрыты в наблюдаемом объекте, и существует определенная корреляция между наблюдаемым событием и скрытым событием, в этом случае используется скрытая марковская модель ( ХМ).

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

Скрытая марковская модель

Скрытая марковская модель представляет собой модель ориентированного графа.Модель графа может явно выражать вероятность корреляции между переменными.Модель общего графа также имеет условное случайное поле.Узлы представляют переменные, а связь между узлами представляет вероятность корреляции между два. Модель HMM описывается следующими определениями:

Пусть множество всех возможных состояний системы есть $S = \{s_1,s_2,...s_n\}$ , множество всех наблюдаемых объектов $V=\{v_1,v_2,...v_m\}$ , то всего имеется n скрытых состояний и m явных состояний.

Затем установите последовательность состояний в общей сложности T раз E = (e_1,e_2,...e_T) , соответствующий последовательности наблюдений с T моментами O = (o_1,o_2,...o_T) , эти два слова легко понять. Тег части речи, соответствующий nlp, представляет собой предложение, а тег части речи этого предложения, например, «я/есть/китаец/человек» и «местоимение/глагол/ существительное/существительное».

Модель вероятности Hidden Markov Существует три основных группы: вероятность перехода и вероятность наблюдения начальной вероятности состояния.

Существует вероятность перехода между состояниями системы, и задана матрица перехода $A = [a_{ij}]_{n \times n}$ , потому что есть n скрытых состояний, поэтому это n строк и n столбцов. Формула для расчета вероятности:

$a_{ij} = P(e_{t+1} = s_j | e_t =s_i) ,\quad 1 \le i,j \le n$

Это означает, что состояние в любой момент времени t s_i , то состояние в следующий момент будет s_j Вероятность , то есть вероятность перехода двух состояний в любой момент времени.

Матрица вероятности наблюдения $B = [b_{ij}]_{n \times m}$ ,в $b_{ij} = P(o_t=v_j|e_t=s_i), \quad 1 \le i\le n,1 \le j\le m$ , который используется для представления того, что в любой момент времени t, если состояние s_i , то генерируется наблюдаемое состояние v_k Вероятность.

Кроме того, существует вероятность начального состояния $\pi =(\pi_1,\pi_2,...,\pi_n)$ , который используется для представления вероятности появления каждого состояния в начальный момент, где $\pi_i=P(e_1=s_i),\quad i=1,2,...,n$ , то есть состояние в момент времени t=1 равно s_i Вероятность.

Подводя итог, можно использовать скрытую марковскую модель с $\lambda = [A,B,\pi]$ описывать.

Важные предположения

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

три вопроса

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

Проблема правдоподобия, то есть, учитывая скрытую марковскую модель, вычислить вероятность последовательности наблюдений. $P(O|\lambda)$ , например для HMM, какова вероятность вычисления последовательности «Я китаец».
Задача прогнозирования, также известная как проблема декодирования, задается последовательностью наблюдений O и скрытой марковской моделью для поиска наиболее соответствующей ей последовательности скрытых состояний E. Можно также сказать, что последовательность скрытых состояний выводится из последовательности наблюдений . Например, для HMM известна последовательность «Я китаец», и вычисляется ее последовательность частей речи.
Задача обучения, то есть при заданной последовательности наблюдений O и соответствующей ей последовательности состояний E, обучает лучшие параметры модели, чтобы она могла наилучшим образом описать последовательность наблюдений. Например, Скрытая Марковская Модель обучается с помощью известной последовательности «Я/Да/Китай/Люди» и последовательности состояний «Местоимение/Глагол/Существительное/Существительное».

Расчет задач правдоподобия

Первая проблема связана с вычислением вероятности последовательности.Если вероятности всех возможных последовательностей перечислить и просуммировать, объем вычислений будет довольно большим, поэтому необходим более эффективный метод, то есть прямой алгоритм.

Сначала определитепрямая вероятность.Для указанного HMM последовательность наблюдения части последовательности наблюдения в определенное время t равна o_1,o_2,...o_t и статус s_i Вероятность - это прямая вероятность, обозначаемая как $\alpha(i) = P(o_1,o_2,...o_t,e_t=s_i|\lambda)$ .

Последовательность наблюдений может быть получена рекурсией следующим образом $P(O|\lambda)$ .

начальное значение n состояний, $\alpha_1(i) = \pi_i b_i(o_1) ,\quad i=1,2,...n$

Время t рекурсивно увеличивает вероятность от 1 до T-1, $\alpha_{t+1}(i) = \begin{bmatrix} \sum _{j=1}^{n}\alpha_t(j)a_{ji}\end{bmatrix}b_i(o_{t+1}),\quad i+1,2,...,n$

Накопить сумму в момент времени T, $P(O|\lambda) = \sum_{i=1}^{n} \alpha_T(i)$

Видно, что разные состояния имеют разные начальные значения, и значением является состояние s_i и наблюдаемое значение равно o_1 Совместная вероятность $o_{t+1}$ Вероятность наблюдения ; суммирует форвардную вероятность в момент времени T, чтобы получить окончательный результат, который представляет собой сумму возможностей различных состояний в последний момент времени. Весь процесс можно лучше понять с помощью следующей диаграммы, как насчет этого? Это знакомо? Как и в полносвязной нейронной сети, каждый узел связан, и каждый узел будет иметь соответствующий компонент для следующего уровня узлов.

проблема предсказания

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

проблемы с обучением

Третья проблема — это проблема обучения, и здесь мы рассматриваем только метод обучения с учителем. Пусть обучающая выборка будет $\{ (O_1,E_1),(O_2,E_2),...(O_k,E_k)\}$ , где k — объем выборки. Вероятность перехода, вероятность наблюдения и вероятность начального состояния могут быть рассчитаны методом оценки максимального правдоподобия.

Пусть k отсчетов разделены по состоянию во все моменты времени t s_i А время t+1 делится на состояние s_j Частота $U_{ij}$ , то вероятность перехода $a_{ij} = \frac{U_{ij}}{\sum_{j=1}^{n}U_{ij}} ,\quad i=1,2,...n;j=1,2,...,n$ . Затем установите состояние в образце на s_i и наблюдаемое значение равно e_j Частота $V_{ij}$ , то вероятность наблюдения $b_{ij}=\frac{V_ij}{\sum_{j=1}^{m}V_{ij}},\quad i=1,2,...n;j=1,2,...,m$ . Начальное состояние напрямую вычисляет начальное состояние в k выборках как s_i Частота.

Как создать последовательность наблюдений

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

demo

https://github.com/sea-boat/TextAnalyzer/tree/master/src/main/java/com/seaboat/text/analyzer/tagging

------------- Рекомендуем прочитать ------------

Резюме моей статьи за 2017 год — машинное обучение

Краткое изложение моих статей за 2017 год — Java и промежуточное ПО

Резюме моих статей 2017 года — глубокое обучение

Краткое изложение моих статей за 2017 год — исходный код JDK

Резюме моей статьи за 2017 год — обработка естественного языка

Резюме моих статей 2017 года — Java Concurrency

------------------рекламное время----------------

Меню официальной учетной записи было разделено на «распределенное», «машинное обучение», «глубокое обучение», «НЛП», «глубина Java», «ядро параллелизма Java», «исходный код JDK», «ядро Tomcat», и т.д. Там может быть один стиль, чтобы удовлетворить ваш аппетит.

Моя новая книга «Анализ проектирования ядра Tomcat» продана на Jingdong, и нуждающиеся друзья могут ее купить. Спасибо друзья.

Зачем писать «Анализ проектирования ядра Tomcat»

Добро пожаловать, чтобы следовать: