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
Пример марковской модели

По свойству марковской цепи, вероятность последовательности состояний может быть найдена по формуле
Предположим, мы хотим подсчитать вероятность последовательности: {‘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
Вычисление вероятности последовательности

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

Dry
0.6
0.6
0.4
0.4
Пример скрытой марковской модели

Два состояния: ‘Низкое’ 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 .
Пример скрытой марковской модели

Хотим вычислить вероятность последовательности, {‘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
Пример вычисления вероятности наблюдений

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

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

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

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

HMM формализм
{S, K, Π, Α, Β}
S : {s1…sN } - значения скрытых состояний
K : {k1…kM } – значения наблюдаемых состояний
S
S
S
K
K
K
S
K
S
K

HMM формализм
{S, K, Π, Α, Β}
Π = {πι} - вероятности начальных состояний
A = {aij} - вероятности переходов между скрытыми состояниями
B = {bik} – вероятности наблюдаемых состояний
A
B
A
A
A
B
B
S
S
S
K
K
K
S
K
S
K

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

o1
ot
ot-1
ot+1
Имея последовательность наблюдаемых состояний и модель, вычислить вероятность последовательности наблюдаемых состояний
Оценка (Evaluation)

Оценка (Evaluation)
Сложность O (NT), где N – число возможных вариантов состояний

Форвардная процедура
Метод динамического программирования
Определим переменную:
Смысл переменной α: вероятность наблюдений o1, …ot и при этом оказаться в состоянии i

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

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

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

Вычисление вероятности последовательности
наблюдаемых событий
Можем эффективно вычислять
α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))

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

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

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

Декодирование:
Best State Sequence
Найти множество состояний, которые наилучшим образом объясняют последовательность видимых состояний
Viterbi algorithm

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

Алгоритм Витерби
Рекурсивное
вычисление
x1
xt-1
xt
xt+1

Алгоритм Витерби
Вычисляем наиболее вероятную последовательность состояний, двигаясь назад
x1
xt-1
xt
xt+1
xT

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты

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

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

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