Скрытые марковские модели
Постморфологический анализ
Марковские модели
Пример марковской модели
Вычисление вероятности последовательности
Скрытые марковские модели
Пример скрытой марковской модели
Пример скрытой марковской модели
Пример вычисления вероятности наблюдений
Почему важно рассмотрение HMM в автоматической обработке текста
Что такое HMM?
Что такое HMM?
Что такое HMM?
HMM формализм
HMM формализм
Вывод HMM
Оценка (Evaluation)
Оценка (Evaluation)
Форвардная процедура
Форвардная процедура
Форвардная процедура
Вычисление вероятности последовательности наблюдаемых событий
Вычисление вероятности последовательности наблюдаемых событий
Форвардный алгоритм: пример
Форвардный алгоритм
Декодирование
Декодирование: Best State Sequence
Алгоритм Витерби
Алгоритм Витерби
Алгоритм Витерби
Тот же пример для алгоритма Витерби
Пример: Алгоритм Витерби
Пример. Алгоритм Витерби
Применение HMM к POS-tagging
Пример: морфологическая неоднозначность
Откуда взять данные?
Фрагмент морфологической разметки в Национальном корпусе русского языка
Данные для примера
Лексические вероятности: уточнение
Лексические вероятности
Словарь и лексические вероятности
Анализ статистических алгоритмов снятия морфологической омонимии в русском языке
Разрешение морфологической неоднозначности в текстах на английском языке
Особенности английского языка
Задача исследования:
Алгоритмы
HMM
Задача алгоритмов:
Деление выборки на обучающую и тестирующую:
Оценка качества
Результаты
Выводы работы
Проблемы HMM
Как можно изменить процесс расчета переходов между состояниями?
Задание
2.70M
Category: programmingprogramming

Скрытые марковские модели. Разрешение морфологической неоднозначности

1. Скрытые марковские модели

Разрешение морфологической
неоднозначности

2. Постморфологический анализ

• =предсинтаксический анализ
• Предназначен для устранения морфологической
омонимии (многозначности) слов
–Выбор правильной леммы
–Уточнение морфологических характеристик
Основные методы
- Написание правил,
- Статистические методы, прежде всего, на основе
морфологически размеченного корпуса
-Скрытые марковские модели

3. Марковские модели

• Набор состояний: {s , s , , s }
1 2
N
• Процесс движется от одного состояния к другому,
порождая последовательность состояний :
si1 , si 2 , , sik ,
•Свойство марковской цепи: вероятность следующего
состояния зависит от состояния предыдущего:
P(sik | si1 , si 2 , , sik 1 ) P(sik | sik 1 )
• Чтобы определить марковскую сеть, должны быть
определены следующие вероятности
i P( si )
aij P( si | s j )

4. Пример марковской модели

0.3
0.7
Rain
Dry
0.2
0.8
• Два состояния : ‘Rain’ и ‘Dry’
• Вероятности переходов: P(‘Rain’|‘Rain’)=0.3 ,
P(‘Dry’|‘Rain’)=0.7 , P(‘Rain’|‘Dry’)=0.2, P(‘Dry’|‘Dry’)=0.8
• Исходные вероятности: P(‘Rain’)=0.4 , P(‘Dry’)=0.6

5. Вычисление вероятности последовательности

• По свойству марковской цепи, вероятность
последовательности состояний может быть найдена по
формуле
P( si1 , si 2 , , sik ) P( sik | si1 , si 2 , , sik 1 ) P( si1 , si 2 , , sik 1 )
P( sik | sik 1 ) P( si1 , si 2 , , sik 1 )
P( sik | sik 1 ) P( sik 1 | sik 2 ) P( si 2 | si1 ) P( si1 )
• Предположим, мы хотим подсчитать вероятность
последовательности: {‘Dry’,’Dry’,’Rain’,Rain’}.
P({‘Dry’,’Dry’,’Rain’,Rain’} ) =
P(‘Rain’|’Rain’) P(‘Rain’|’Dry’) P(‘Dry’|’Dry’) P(‘Dry’)=
= 0.3*0.2*0.8*0.6

6. Скрытые марковские модели

{s1 , s2 , , sN }
• Множество состояний:
•Процесс движется от состояния к состоянию :
• Выполняется свойство марковской цепи:
• Состояния – невидимы, но каждое состояние
порождает одно из M наблюдений - видимых состояний
{v1 , v2 , , vM }
•Чтобы определить скрытую марковскую цепь, нужно
определить
• Матрицу переходов A=(aij), aij= P(si | sj) ,
• Матрицу вероятностей наблюдаемых состояний
B=(bi (vm )), bi(vm ) = P(vm | si)
• Вектор начальных вероятностей =( i), i = P(si).
• Модель представлена M=(A, B, ).

7. Пример скрытой марковской модели

0.3
0.7
Low
High
0.2
0.6
Rain
0.4
0.8
0.4
0.6
Dry

8. Пример скрытой марковской модели

• Два состояния: ‘Низкое’ and ‘Высокое’ атм. давление.
• Два наблюдения: ‘Дождь’ and ‘Сухо’.
• Вероятности перехода: P(‘Low’|‘Low’)=0.3 ,
P(‘High’|‘Low’)=0.7 , P(‘Low’|‘High’)=0.2,
P(‘High’|‘High’)=0.8
• Вероятности наблюдения: P(‘Rain’|‘Low’)=0.6 ,
P(‘Dry’|‘Low’)=0.4 , P(‘Rain’|‘High’)=0.4 ,
P(‘Dry’|‘High’)=0.3 .
• Начальные вероятности: P(‘Low’)=0.4 , P(‘High’)=0.6 .

9. Пример вычисления вероятности наблюдений

• Хотим вычислить вероятность последовательности,
{‘Dry’,’Rain’}.
•Рассмотрим все возможные скрытые состояния:
P({‘Dry’,’Rain’} ) = P({‘Dry’,’Rain’} , {‘Low’,’Low’}) +
P({‘Dry’,’Rain’} , {‘Low’,’High’}) + P({‘Dry’,’Rain’} ,
{‘High’,’Low’}) + P({‘Dry’,’Rain’} , {‘High’,’High’})
где первый элемент:
P({‘Dry’,’Rain’} , {‘Low’,’Low’})=
P({‘Dry’,’Rain’} | {‘Low’,’Low’}) P({‘Low’,’Low’}) =
P(‘Dry’|’Low’)P(‘Rain’|’Low’) P(‘Low’)P(‘Low’|’Low)
= 0.4*0.6*0.4*0.3

10. Почему важно рассмотрение HMM в автоматической обработке текста

• Непосредственно имеем дело с неоднозначными
словами и конструкциями
• Нужно распознавать скрытые
– Части речи
– Лексические значения
– Типы именованных сущностей (организация,
персона, географическое место …)
– Определение тональности предложения
– и др.

11. Что такое HMM?

• Графическая модель
• Кружки – это состояния
• Стрелки обозначают вероятностные
зависимости между состояниями

12. Что такое HMM?

• Зеленые кружки – это скрытые состояния
• Зависят только от предыдущего состояния

13. Что такое HMM?

• Фиолетовые кружки – это наблюдаемые
состояния
• Зависят только от соответствующих
скрытых состояний

14. HMM формализм

S
S
S
S
S
K
K
K
K
K
• {S, K, P, A, B}
• S : {s1…sN } - значения скрытых состояний
• K : {k1…kM } – значения наблюдаемых состояний

15. HMM формализм

S
A
S
B
K
A
S
B
K
A
S
A
S
B
K
K
K
• {S, K, P, A, B}
• P { i} - вероятности начальных состояний
• A = {aij} - вероятности переходов между скрытыми
состояниями
• B = {bik} – вероятности наблюдаемых состояний

16. Вывод HMM

• Вычислить вероятность последовательности
наблюдаемых состояний (Evaluation)
• Имея последовательность наблюдаемых состояний,
вычислить наиболее вероятную последовательность
скрытых состояний (Decoding)
• Имея последовательность наблюдаемых состояний и
множество возможных моделей, определить какая
модель лучше соответствует данным (т.е. наблюдаемой
последовательности) (Learning)

17. Оценка (Evaluation)

o1
ot-1
ot
ot+1
oT
Имея последовательность наблюдаемых состояний
и модель, вычислить вероятность
последовательности наблюдаемых состояний
O (o1...oT ), ( A, B, P )
Вычислить P(O | )

18. Оценка (Evaluation)

x1
xt-1
xt
xt+1
xT
o1
ot-1
ot
ot+1
oT
P (O | )
T 1
b P a
x1 x1o1
{ x1 ... xT }
t 1
b
xt xt 1 xt 1ot 1
Сложность O (NT), где N – число
возможных вариантов состояний

19. Форвардная процедура

• Метод динамического программирования
• Определим переменную:
i (t ) P(o1...ot , xt i | )
Смысл переменной α: вероятность наблюдений o1, …ot
и при этом оказаться в состоянии i

20. Форвардная процедура

x1
xt-1
xt
xt+1
xT
o1
ot-1
ot
ot+1
oT
j (t 1)
P(o1...ot 1 , xt 1 j )
P(o1...ot 1 | xt 1 j ) P( xt 1 j )
P(o1...ot | xt 1 j ) P(ot 1 | xt 1 j ) P( xt 1 j )
P(o1...ot , xt 1 j ) P(ot 1 | xt 1 j )

21. Форвардная процедура

x1
xt-1
xt
xt+1
xT
o1
ot-1
ot
ot+1
oT
P(o1...ot , xt i, xt 1 j )P (ot 1 | xt 1 j )
i 1... N
P(o1...ot , xt 1 j | xt i )P( xt i ) P (ot 1 | xt 1 j )
i 1... N
P(o1...ot , xt i )P ( xt 1 j | xt i ) P (ot 1 | xt 1 j )
i 1... N
i (t )aijb jot 1
i 1... N

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

• Можем эффективно вычислять
• αT(I)=P(o1, o2,…oT, xT=i|μ)
• Как вычислить
• P(o1, o2,…oT |μ)?
• Как вычислить
• P(xT=i|o1, o2,…oT ,μ)?

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

• Можем эффективно вычислять
• αT(i)=P(o1, o2,…oT, xT=i|μ)
• Как вычислить
• P(o1, o2,…oT |μ) = Σi αT(i)
• Как вычислить
• P(xT=i|o1, o2,…oT ,μ)= αT(i)/(Σi αT(i))

24. Форвардный алгоритм: пример

25. Форвардный алгоритм

• Найти вероятность
последовательности:
• s r r s r (s- sun, r – rain)

26.

27.

28. Декодирование

• Вычислить вероятность последовательности
наблюдаемых состояний (Evaluation)
• Имея последовательность наблюдаемых состояний,
вычислить наиболее вероятную последовательность
скрытых состояний (Decoding)
• Имея последовательность наблюдаемых состояний и
множество возможных моделей, определить какая
модель лучше соответствует данным (т.е. наблюдаемой
последовательности) (Learning)

29. Декодирование: Best State Sequence

o1
ot-1
ot
ot+1
oT
• Найти множество состояний, которые наилучшим
образом объясняют последовательность видимых
состояний
• Viterbi algorithm
arg max P( X | O)
X

30. Алгоритм Витерби

x1
xt-1
j
o1
ot-1
ot
ot+1
oT
j (t ) max P( x1...xt 1 , o1...ot 1 , xt j, ot )
x1 ... xt 1
Последовательность состояний, которая
максимизирует вероятность увидеть заданную
последовательность видимых состояний во
время t-1, остановиться в состоянии j, и увидеть
заданное наблюдение во время t

31. Алгоритм Витерби

x1
xt-1
xt
xt+1
o1
ot-1
ot
ot+1
oT
j (t ) max P( x1...xt 1 , o1...ot 1 , xt j, ot )
x1 ... xt 1
j (t 1) max i (t )aijb jo
t 1
i
j (t 1) arg max i (t )aijb jo
i
t 1
Рекурсивное
вычисление

32. Алгоритм Витерби

x1
xt-1
xt
xt+1
xT
o1
ot-1
ot
ot+1
oT
Xˆ T arg max i (T )
i
Xˆ t ^ (t 1)
X t 1
P( Xˆ ) arg max i (T )
i
Вычисляем наиболее
вероятную
последовательность
состояний, двигаясь
назад

33.

34.

35.

36.

37.

38.

39. Тот же пример для алгоритма Витерби

40. Пример: Алгоритм Витерби

41. Пример. Алгоритм Витерби

42. Применение HMM к POS-tagging

• POS-tagging – морфологическая разметка
• HMM tagger: выбирает наиболее вероятную
последовательность тегов для каждого
предложения
– Дано предложение W=w1, w2, w3…, wn
- Вычислить наиболее вероятную
последовательность тегов T=t1, t2, …tn, которая
максимизирует
- Argmax P (t1, t2, …tn|w1, w2, …wn)

43. Пример: морфологическая неоднозначность

44. Откуда взять данные?

• Из корпуса с морфологической разметкой
– Русский язык:
• Корпус русского языка
• Открытый корпус (opencorpora.org)
– Английский язык
• Brown corpus
• Penn tree bank

45. Фрагмент морфологической разметки в Национальном корпусе русского языка


Я сидел на барском сиденье, дышал горячим ветром, бившим в лицо, ощущая в
то же время не истребимую никакими сквозняками пыль и легкий запах духов -катафалк с хорошей скоростью мчался по шоссе на юг. (Ю. Трифонов)
<s>Я{я=S,ед,од=им} сидел{сидеть=V,несов=изъяв,прош,ед,муж} на{на=PR}
барском{барский=A=ед,сред,пр} сиденье{сиденье=S,сред,неод=ед,пр},
дышал{дышать=V,несов=изъяв,прош,ед,муж} горячим{горячий=A=ед,муж,твор}
ветром{ветер=S,муж,неод=ед,твор},
бившим{бить=V,несов=прич,прош,ед,муж,твор} в{в=PR}
лицо{лицо=S,сред,неод=ед,вин}, ощущая{ощущать=V=несов,деепр,непрош}
в{в=PR} то{тот=A=ед,сред,вин} же{же=PART} время{время=S,сред,неод=ед,вин}
не{не=PART} истребимую{истребимый=A=ед,жен,вин}
никакими{никакой=A=мн,твор} сквозняками{сквозняк=S,муж,неод=мн,твор}
пыль{пыль=S,жен,неод,ед=вин} и{и=CONJ} легкий{легкий=A=ед,муж,вин,неод}
запах{запах=S,муж,неод=ед,вин}…

46. Данные для примера

47.

48.

49.

50.

51.

52.

53.

54.

55.

56.

57.

58.

59. Лексические вероятности: уточнение

• Мы считали p(w|t)
• Но
– Слово могло отсутствовать в корпусе или отсутствовать
в заданной части речи
– Не учитывается информация из морфологического
словаря
– Удобнее оценить p (t Iw)

60. Лексические вероятности


p(t | w) p( w)
p( w | t )
p(t | w)
p(t )
p(t )
• p(t) – априорная вероятность метки
• p(t|w) – вероятность метки для данного слова
• Можно положить
p(t | w)
c(t , w)
c( w)
• Где с () – количество вхождений
• Как учесть словарь?

61. Словарь и лексические вероятности

• Можно считать, что все словарные метки слова w входят в
корпус раз (например, =0.5)
• Тогда получим:
c(t , w)
p(t | w)
c( w) | T ( w) |
• где T(w) – это количество тегов для w
• Для новых несловарных слов p(t|w) считается на основе
совокупности признаков (машинное обучение)

62. Анализ статистических алгоритмов снятия морфологической омонимии в русском языке

Егор Лакомкин
Иван Пузыревский
Дарья Рыжова
(2013)

63. Разрешение морфологической неоднозначности в текстах на английском языке

• Методы:
Как правило, статистические
алгоритмы на основе марковских
моделей
• Точность: ~96%

64. Особенности английского языка

• Бедная морфология
морфологическая разметка фактически сводится к
POS-теггингу
• Фиксированный порядок слов
можно опираться только на локальный контекст
слова (ближайших соседей) без учёта дальних
зависимостей (т.е. достаточно марковских моделей
первого порядка)

65. Задача исследования:

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

66. Алгоритмы

• Набор скрытых величин Y (состояний модели =
наборов грамматических тегов); составляют
марковскую цепь первого порядка
• Набор наблюдаемых величин X (наблюдений) ~
словоформ
Словоформы заменяем на 3-буквенные
окончания:
– Сокращаем количество наблюдаемых состояний
– Практически не теряем полезную информацию
(поскольку в РЯ почти вся морфологическая
информация сосредоточена в окончании)

67. HMM

• Обучение:
Сбор статистик по корпусу:
– P(yi|yj) – матрица переходов
– P(xk|yi) – вероятности наблюдений
прил
сущ
глаг
-ные
-чки
-ают

68. Задача алгоритмов:

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

69. Деление выборки на обучающую и тестирующую:

• Кросс-валидация (5 фолдов):
– Деление выборки на 5 частей:
4 обучающие + 1 тестирующая
– 5 серий подсчётов
– Усреднение результата

70. Оценка качества

• Определение верхней и нижней границы:
– Верхняя граница: процент случаев, когда среди гипотез
Mystem’а есть правильная;
– Нижняя: «частотная снималка» (слову приписывается
наиболее частотный вариант разбора, без учёта контекста)
• Качество работы алгоритма (= точность):
Сравнение с «золотым стандартом» - с эталонным разбором
НКРЯ:
– общая точность
– точность по знакомым словам
– точность по незнакомым словам
• Не учитывались:
– Инициалы, аббревиатуры, цифры;
– Сложные слова с дефисом (ср. бело-кремовый)

71. Результаты

Части речи
Теги (род, число, падеж и
др.)
Общ.
Зн.
Незн.
Общ.
Зн.
Незн.
Нижн.гр.
.8590
.8586
.8885
.6817
.6836
.5525
HMM
.9482
.9489
.8996
.8873
.8909
.6550
.9895
.9081
.9741
.7017
Верхн.гр.

72. Выводы работы

• POS-теггинг – на приличном уровне,
• Разрешение неоднозначности по
расширенным тегам – довольно низкий
уровень точности. Случаи, особенно часто
разбираемые ошибочно:
– Местоимения
– Имена собственные
– Субстантивация прилагательных
– Омонимия падежных форм (номинатив vs.
аккузатив)

73. Проблемы HMM

• Метки рассматриваются как единое целое,
невозможно извлечь отдельные признаки
– В русском языке: тег – это сущ. в род. падеже ед.
числа
• Ограниченный просмотр состояний – обычно
биграммы
• Не учитываются дистантные зависимости
– Договор о разоружении сторон был подписан
– Договор – именительный или винительный падеж
• Состояние не зависит от соседних слов
– Обмануть друга vs. соврать другу

74. Как можно изменить процесс расчета переходов между состояниями?

• HMM: учитываются два фактора в простой
комбинации
• Для определения вероятности переходов
между состояниями нужно: учитывать
значительно больше факторов
• Когда нужна комбинация факторов ->
машинное обучение

75. Задание

English     Русский Rules