«Это первый день моего участия в ноябрьском испытании обновлений, ознакомьтесь с подробностями события:Вызов последнего обновления 2021 г."

[Эта статья является переводом «Обработка речи и языка» 8.4, и в нее добавлены собственные мысли некоторых переводчиков]

1. Цепь Маркова

Марковское предположение: при предсказании будущего прошлое не имеет значения, имеет значение только настоящее.

$P(q_i = a|q_1...q_{i-1}) = P(q_i = a|q_{i−1})\qquad(8.3)$

Цепь Маркова в основном состоит из следующих частей:

формула	Примечание
Q = $q_1q_2 ...q_N$	набор из N состояний
A = $a_{11}a_{12} ...a_{N1} ...a_{NN}$	A представляет матрицу вероятности перехода,$a_{ij}$представляет вероятность перехода из состояния i в состояние j
$π = π_1, π_2,..., π_N$	Начальное распределение вероятностей, которому подчиняется состояние,$π_i$представляет вероятность того, что цепь Маркова начинается в состоянии i. если некоторое состояние j$π_j=0$, это означает, что эти состояния нельзя использовать в качестве начального состояния o цепи Маркова,$\sum_{i=1}^{n}π_i=1$

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

state=[hot、cold、warm]
π = [0.1, 0.7, 0.2]    //表示马尔可夫链初始状态是状态1(hot)的可能性为0.1

Матрица перехода А:

состояние (i\j)	hot	cold	warm
hot	0.6	0.1	0.3
cold	0.1	0.8	0.1
warm	0.3	0.1	0.6

В: Пожалуйста, используйте приведенные выше вероятности, чтобы рассчитать вероятность каждой из следующих последовательностей.

hot hot hot hot

cold hot cold hot

2. Скрытая марковская модель (The Hidden Markov Model)

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

Скрытые марковские модели также поддерживают наблюдаемые события (например, слова, которые мы видим на входе). и скрытые события (такие как теги части речи), которые мы считаем причинными в вероятностной модели

2.1 Компоненты HMM

ГМ состоит из следующих частей:

формула	Примечание
Q = $q_1q_2 ...q_N$	набор из N состояний
A = $a_{11}a_{12} ...a_{N1} ...a_{NN}$	A (матрица вероятности перехода) представляет матрицу вероятности перехода,$a_{ij}$представляет вероятность перехода из состояния i в состояние j такое, что для любого i$\sum_{j=1}^{n}a_{ij}=1$
$O = o_1o_2 ...o_T$	Последовательность наблюдений T, каждое из которых получено из числа сигналов мозга.
$B = b_i(o_t)$	Последовательность вероятностей наблюдения, также известная как вероятность эмиссии, представляет подчиненное состояние.$q_i$может производить наблюдения$o_t$Вероятность
$π = π_1, π_2,..., π_N$	Начальное распределение вероятностей, которому подчиняется состояние,$π_i$представляет вероятность того, что цепь Маркова начинается в состоянии i. если некоторое состояние j$π_j=0$, это означает, что эти состояния нельзя использовать в качестве начального состояния o цепи Маркова,$\sum_{i=1}^{n}π_i=1$

Скрытая марковская модель первого порядка состоит из двух упрощенных предположений Глоссарий$V = v_1, v_2,..., v_V$

1. Как и в цепях Маркова первого порядка, вероятность конкретного состояния зависит только от предыдущего состояния:

$P(q_i | q_1 \ldots q_{i-1}) = P(q_i | q_{i-1})\qquad(8.6)$

2. выходное наблюдение$o_i$Вероятность зависит только от состояния, которое произвело наблюдение$q_i$, независимо от любого другого состояния и других наблюдений:

$P(o_i | q_1, \ldots, q_i, \ldots, q_T, o_1, \ldots, o_i, \ldots, o_T) = P(o_i | q_i)\qquad(8.7)$

2.2 Компоненты тегера HMM

HMM состоит из двух компонентов: матрицы A и матрицы B.

Матрица A: вероятности перехода метки$P(t_i|t_{i-1})$, который представляет вероятность появления текущей метки с учетом предыдущей метки. Например, за модальным глаголом, скорее всего, будет следовать основная форма глагола, т. е. VB, как вrace, поэтому мы ожидаем, что эта вероятность будет высокой. Мы вычисляем оценку максимального правдоподобия этой вероятности перехода, подсчитывая количество вхождений первого и второго в корпусе.

$P(t_i|t_{i-1}) = \dfrac{C(t_{i-1}, t_i)}{C(t_{i-1})}\qquad(8.8)$

Набор тегов части речи:Woohoo. IBM.com/docs/this/Я тру...  

Например, в корпусе WSJ слово MD появляется 13 124 раза, за ним следует VB 10 471 раз, поэтому его MLE оценивается как

$P(VB|MD) = \dfrac{C(MD, VB)}{C(MD)}=\dfrac{10471}{13124}=0.80\qquad(8.9)$

Примеры задач по маркировке частей речи

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

вероятность эмиссии$B$,$P(w_i|t_i)$, указывая на то, что данная метка$t_i$(например, MD), аналогом которого является данное слово$w_i$(как will) Вероятность. MLE для этой вероятности выбросов равен

$P(w_i|t_i) = \dfrac{C(t_i, w_i)}{C(t_i)}\qquad(8.10)$

Среди 13124 вхождений MD в корпусе WSJ соответствующее словоwillиз 4046 раз:

$P(will|MD) = \dfrac{C(MD, will)}{C(MD)}=\dfrac{4046}{13124}=0.31\qquad(8.11)$

Помните, что этот термин вероятности не спрашивает».willКакой наиболее вероятный ярлык для этого слова? "это будет апостериорная вероятность$P(MD|will)$,Напротив$P(will|MD)$Ответом является слегка извращенный вопрос: «Если бы нам нужно было сгенерировать MD, насколько вероятно, что этот модальный глагол будетwill? "

Как показано

По аналогии с цепью Маркова есть три состояния VB (глагол), MD (модальный глагол), NN (существительное), значение наблюдения$o_i$Представляет такие слова, как «будет», «назад» и т. д. , как видно из рисунка, матрица переходных вероятностей$A$и наблюдаемая вероятность$B$

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

расшифровка: Учитывая HMM$\lambda = (A, B)$и последовательность наблюдений$O = o_1, o_2, \ldots, o_T$В качестве входных данных найдите наиболее вероятную последовательность состояний$Q = q_1 q_2 q_3 \ldots q_T$.

Для маркировки частей речи указывается цель декодирования HMM.$n$последовательность слов$w_1 \ldots w_n$, выберите наиболее вероятную последовательность тегов$t_1 \ldots t_n$:

$\hat{t}_{1:n} = \argmax_{t_1 \ldots t_n} P(t_1 \ldots t_n | w_1 \ldots w_n)\qquad(8.12)$

На самом деле мы используем правило Байеса в HMM для расчета:

$\hat{t} _{1:n} = \argmax_{t_1 \ldots t_n} \dfrac{P(w_1 \ldots w_n | t_1 \ldots t_n) P(t_1 \ldots t_n)}{P(w_1 \ldots w_n)}\qquad(8.13)$

Продолжаем упрощать предыдущую формулу и сразу убираем знаменатель$P(w_1^n)$(Луна: Поскольку мы уже знаем эту последовательность слов, ее вероятность равна 1, что можно удалить напрямую)

$\hat{t} _{1:n} = \argmax_{t_1 \ldots t_n} {P(w_1 \ldots w_n | t_1 \ldots t_n) P(t_1 \ldots t_n)}\qquad(8.14)$

Теггер HMM делает еще два упрощения:

1. Вероятность появления слова зависит только от вероятности его собственной метки и не имеет ничего общего с соседними словами.

$P(w_1 \ldots w_n | t_1 \ldots t_n) \approx \prod_{i=1}^n P(w_i | t_i) \qquad(8.15)$

2. Вероятность появления метки зависит только от ее предыдущей метки, а не от всей последовательности меток.

$P(t_1 \ldots t_n) \approx \prod_{i=1}^n P(t_i | t_{i-1})\qquad(8.16)$

Из этих двух упрощений мы можем вывести формулу для наиболее вероятной последовательности меток из тегера биграмм:

$\hat{t} _{1:n} = \argmax_{t_1 \ldots t_n} P(t_1 \ldots t_n | w_1 \ldots w_n) \приблизительно \argmax_{t_1 \ldots t_n} \prod_{i=1}^ n \overbrace{P(w_i|t_i)}^{вероятность излучения} \overbrace{P(t_i|t_{i-1})}^{вероятность перехода}\qquad(8.17)$

2.3 Алгоритм Витерби (The Viterbi Algorithm)

Алгоритм декодирования HMM — Витерби, как показано на следующем рисунке (Viterbi)алгоритм. В качестве примера динамического программирования алгоритм Витерби подобен алгоритму минимального расстояния редактирования динамического программирования в главе 2 slp3.

Алгоритм Витерби сначала строит матрицу вероятностей илисетка(lattice), где каждый столбец для каждого наблюдения$o_t$, для каждого состояния на диаграмме состояний в строке. Следовательно, в одном комбинаторном автомате каждый столбец (наблюдаемое значение$o_t$) для каждого состояния$q_i$Есть одна ячейка. На рисунке ниже показаноJanet will back the billРешетка, соответствующая этому предложению.

каждая ячейка сетки,$v_t(j)$, представляющий данный HMM$\lambda$перед "увидеть"$t$наблюдения и пройти через наиболее вероятную последовательность состояний$q_1, \ldots, q_{t-1}$после государства$j$Вероятность. каждая ячейка$v_t(j)$Значение вычисляется рекурсивно, то есть каждый раз выбирается наиболее вероятный путь к ячейке. Формально вероятность, представленная каждой ячейкой, равна

$v_t(j) = \max_{q_1, \ldots, q_{t-1}} P(q_1 \ldots q_{t-1}, o_1, o_2 \ldots o_t, q_t = j | \lambda)\qquad(8.18)$

Мы делаем это, беря максимальное значение из всех предыдущих возможных последовательностей состояний.$\max_{q_1, \ldots, q_{t-1}}$представить наиболее вероятный путь. Как и другие алгоритмы динамического программирования, алгоритм Витерби рекурсивно заполняет каждую ячейку. Учитывая, что мы рассчитали, что во времени$t-1$— вероятность пребывания в каждом состоянии, поэтому мы можем принять максимальную вероятность всех путей расширения в текущую ячейку как текущее время$t$значение вероятности. на время$t$заданное состояние, когда$q_j$, его значение$v_t(j)$Метод расчета

$v_t(j) = \max_{i=1}^N v_{t-1}(i) a_{ij} b_j(o_t) \qquad(8.19)$

формула	Примечание
$v_{t-1}(i)$	Вероятность пути Витерби в предыдущий момент
$a_{ij}$	предыдущее состояние$q_i$к текущему состоянию$q_j$Вероятность перехода
$b_j(o_t)$	учитывая текущее состояние$j$, наблюдаемое значение$o_t$Вероятность наблюдения за состоянием

Пример: Джанет поддержит счет, цель состоит в том, чтобы получить правильную последовательность меток:

Janet/NNP will/MD back/VB the/DT bill/NN

На рисунке выше (8.11) показаны возможные метки для каждого слова и выделена правильная последовательность частей речи, соответствующая предложению из этих скрытых состояний. А часть речи (состояние) реализуется как слово (значение наблюдения) с вероятностью 0. Состояние отображается серым цветом (типа DT невозможно -> Джанет)

Тогда разберем подробно:

На рис. 8.12 показаны вероятности перехода между состояниями.$a_{ij}$матрица:

То есть вероятность того, что предыдущий момент — MD, а следующий момент — VB, равна 0,7968.

$P(VB|MD)=0.7968$

На рис. 8.13 показано$b_i(o_t)$вероятность, т. е. с учетом меткинаблюдаемое значениевероятность

На рис. 8.14 показана подробная версия рис. 8.11, сетка Витерби, используемая для вычисления оптимальной последовательности скрытых состояний для последовательности наблюдений «Джанет поддержит счет».

имеют$N=5$столбец состояния. Начнем со столбца 1 (соответствующего словуJanet), установите значение Витерби каждой ячейки как вероятность перехода$\pi$(государство$i$Начальная вероятность , которую мы можем получить из рис. 8.12<s>срок) то есть$P(NNP|start)=0.2767$(вероятность метки NNP в качестве начала равна 0,2767), и мы можем видеть, что при этой метке ячейки словоJanetНаблюдаемое значение вероятности . Большинство ячеек в этом столбце - нули$v_1(7)=P(Janet|DT)=0$,так как JanetСлово не может быть ни одной из этих меток. Читатель должен увидеть это на рис. 8.14.

Далее обновитеwillкаждой ячейке столбца. Для каждого состояния мы вычисляем по уравнению 8.19.$viterbi[s,t]$, взяв максимальное значение разброса всех путей, ведущих к текущей ячейке в предыдущем столбце. Мы привели значения для ячеек MD, VB и NN. Каждая ячейка берет максимальное значение из 7 ячеек в предыдущем столбце, умноженное на соответствующую вероятность перехода; в этом примере большинство из них — нули. Затем умножьте на соответствующую вероятность наблюдения и возьмите максимальное значение. В этом примере конечное значение (Примечание переводчика: максимальное значение), 2.772e-8, статус NNP из предыдущего столбца. Читатель может продолжить заполнение оставшихся ячеек на рис. 8.14 и вернуться назад, чтобы увидеть, вернул ли алгоритм Витерби правильную последовательность состояний NNP MD VB DT NN.