Введение

В какой-то момент в начальной школе, когда мы изучали грамматику, мы узнали, что слова можно разделить на различные категории, такие как существительное, глагол, прилагательное и т. Д. Эти категории помогают нам понять роль, которую играет слово в слове. приговор. P art o f S peech или POS теги - это процесс присвоения этих категорий (или ярлыков) словам . POS-теги - один из основных строительных блоков обработки естественного языка (NLP), поскольку он является предпосылкой для других процессов NLP.

Некоторые из тегов POS, с которыми мы часто сталкиваемся, - это единственное существительное (NN), местоимение (PRP), прилагательное (JJ), глагол (VB) и т. Д. В то время как люди, мы можем смотреть на предложение и интуитивно связывать теги POS с слова из опыта. Однако как мы можем обучить алгоритм для решения этой, казалось бы, простой задачи? Среди различных подходов к проблеме POS-тегов в этой статье мы рассмотрим вероятностный подход, основанный на скрытой марковской модели (HMM).

Ключевая проблема - назначить последовательность тегов t последовательности из n слов. Звучит достаточно просто !! Итак, допустим, у нас есть 3 слова, помеченные как w₁, w₂, w₃, и у нас есть набор из 6 тегов t₁, t₂… .. t₆. Нам нужно присвоить любой из тегов каждому 3 словам.

Однако есть проблема. Каждое слово может иметь любой из 6 тегов. Это означает, что существует 6 x 6 x 6 возможных последовательностей (6³), и нам нужно выяснить, какая последовательность тегов является правильной. Обобщая, можно сказать, что если у нас есть теги t, которые нужно присвоить n словам, существует t ^ n возможностей. Среди каждой из этих последовательностей нам нужно выбрать наиболее вероятную последовательность тегов.

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

Марковские процессы

Начнем с очень простого примера. Пусть это последовательность событий x₁, x₂, x₃, происходящих на дискретных временных шагах t₁, t₂, t₃. Какова вероятность того, что эта последовательность событий произойдет в первую очередь? Если задуматься, то возникает следующий вопрос:

Учитывая следующие вероятности, что такое P (x₃, x₂, x₁)?

  1. Вероятность x₁ в t₁, т. Е. P (x₁)
  2. Вероятность x₂ в t₂, если x₁ произошло в t₁, то есть P (x₂ | x₁),
  3. Вероятность того, что x₃ в t₃, если x₁, x₂ наступит в t₁, t₂. Формально это P (x₃ | x₂, x₁)

Мы можем переписать это как:

Уравнение 1 - это знаменитое правило цепочки вероятности. Это правило моделирует совместную вероятность двух или более событий. Подробнее об этом можно узнать здесь.

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

Это означает, что состояние в n зависит только от предыдущего состояния в n-1. Что это делает с уравнением. 1? Предполагая, что у нас есть марковский процесс, мы можем переписать уравнение 1 как:

Это также называется 1-марковским процессом. Если бы состояние зависело от прошлых k состояний, это был бы процесс k-марковский.

Условная вероятность и правило Бая

Условная вероятность дает нам вероятность события B при условии, что событие A произошло, выраженное как P (B | A). Чтобы вычислить P (B | A), нам нужно найти совместную вероятность A и B, заданную P (A, B), и предельную вероятность A, заданную P (A).

Мы можем использовать цепное правило из уравнения (1), чтобы расширить числитель. Таким образом, мы получили уравнение. 5. Это означает, что из всех результатов эксперимента уравнение 5 дает нам отношение того, как часто происходило событие B, при условии, что мы ограничимся только теми наблюдениями, в которых произошло событие A.

Мы можем расширить эту формулу до более чем двух переменных. Мы можем спросить, какова вероятность того, что исход будет C, учитывая наблюдения A, B. Математически мы запишем это как P (C | A, B).

Одно важное наблюдение об уравнении. 5: что, если события A и B независимы друг от друга. В этом случае P (B | A) = P (B), что, если подумать, совершенно очевидно. В уравнении. 6, если C не зависит от A, то уравнение 6 сводится к аналогичному уравнению. 5 для событий C и B.

Объединение правила цепочки с правилом Байя

Мы можем взять еще более сложную цепочку событий и применить правило цепочки к пугающей условной вероятности. Какова вероятность того, что произойдет A₁, A₂, A₃, если B₁, B₂, B₃ произошло. Как нам это написать, используя правило Бая? Рассмотрим следующее выражение.

Мы просто использовали правило Байя для LHS. Однако RHS по-прежнему выглядит немного сложнее, особенно числитель. Сначала мы берем второй операнд в числителе и применяем цепное правило, чтобы получить:

Применение правила цепочки к первому операнду дает нам:

Если вам интересно, почему мы не расширили знаменатель, держитесь. Скоро увидим, в этом нет необходимости !!

Наиболее вероятная последовательность тегов

Обратив внимание на теги POS, мы официально объявляем формулировку нашей проблемы. Для последовательности слов w₁, w₂, w₃ мы намерены найти наиболее вероятную последовательность тегов. Для простоты предположим, что у нас есть только 3 тега t₁, t₂, t₃. Если три тега, скажем, DT, VB и NN, то среди всех возможных комбинаций этих трех тегов нам нужно вычислить наиболее вероятный. Мы замечаем, что все дело в выборе одной из этих шести возможностей.

Выберем одну такую ​​последовательность t₁-t₂-t₃ (т.е. DT-VB-NN). Мы можем математически записать это как уравнение 10 ниже. Это просто вероятность этой последовательности тегов. Обратите внимание, что для остальных последовательностей будет еще пять таких уравнений. Однако для одной из этих последовательностей P будет наивысшим:

Здесь мы замечаем, что это похоже на уравнение 7. Давайте упростим оба операнда в числителе уравнения. 10 с помощью цепного правила, как мы сделали в уравнении. 8 и 9.

Теперь мы сделаем два очень важных предположения, которые станут краеугольным камнем наших следующих расчетов.

  • Вероятность слова зависит только от тега в этой позиции. Это означает, что он не зависит от предыдущего тега или соседних слов.
  • Текущий тег зависит только от предыдущего тега. Таким образом, предполагается, что последовательность тегов имеет Марковское свойство, как Ур. 2. Это называется предположением биграммы.

Если бы мы предположили, что текущий тег зависит от двух предыдущих тегов, то это было бы предположение триграммы. В общем, если текущий тег зависит от текущего слова и предыдущих тегов n-1, у нас возникает проблема с тегами n-грамм.

В этой статье мы рассматриваем n = 2. Таким образом, мы имеем проблему с разметкой 2-граммов или биграмм.

С этими двумя предположениями, примененными к уравнению. 11, мы получаем значительно упрощенные операнды.

Термины P (wᵢ | tᵢ) называются вероятностью выброса, то есть вероятностью слова wᵢ при условии, что тег равен tᵢ. Термины P (tᵢ | tᵢ₋₁) называются вероятностью перехода, т. Е. Вероятностью появления тега ti при условии, что предыдущий тег был tᵢ₋₁.

Теперь мы сосредоточимся на знаменателе в уравнении. 10. Когда мы заменяем различные последовательности тегов, мы замечаем, что последовательность слов остается неизменной. Изменится только числитель. Таким образом, для всех практических целей, когда мы пытаемся найти наиболее вероятную последовательность тегов, нам нужно только найти ту, которая максимизирует числитель в уравнении. 10. Таким образом, мы заменим знак равенства в уравнении (10) на знак пропорциональности.

Мы можем дополнительно разбить проблему максимизации, спросив, какой выбор тегов максимизирует условия в квадратных скобках по отдельности. Для согласованности отметим, что P (t₁) на самом деле означает P (t₁ | Начало), что означает «какова вероятность тега t₁, учитывая, что мы находимся в начале предложения?».

Чтобы выяснить, последовательность из трех тегов, которая максимизирует Eqn. 13 (помните, есть 6 возможных последовательностей), нам нужно вычислить уравнение. 13 для всех шести последовательностей и выберите ту, которая дает наибольшую вероятность. Формально это означает поиск той последовательности «1» из «3» тегов, которая максимизирует Eqn. 13. Написано так:

Таким образом, если у нас есть последовательность из n слов, ищущая последовательность из n тегов, мы просто заменяем индекс «3» на «n»:

Таким образом, мы свели задачу к поиску произведения последовательности излучения и вероятности перехода для каждого слова в предложении.

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

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

Подробное объяснение HMM выходит за рамки данной статьи, поэтому мы кратко обсудим это.

В HMM есть марковский процесс T (t₁, t₂, t₃), который скрыт для наблюдателя (в данном случае теги). Однако, когда процесс переходит из одного состояния в другое, он излучает определенные наблюдения W (w₁, w₂, w₃) в форме слов. Цель HMM - узнать о T, наблюдая за W.

Скрытый процесс T в момент t₁ может перейти в t₂ с вероятностью p₁₂. Он также может вернуться к самому себе с переходом вероятностью p₁₁. На этом этапе t₁ может испускать w₁, w₂ и w₃ с эмиссией вероятностями e₁₁, e₁₂ и e₁₃ соответственно. В момент t₃ дальнейший переход невозможен, так как это последний шаг процесса. Для постановки задачи нам не нужно углубляться в HMM.

Все вероятности излучения, происходящие из скрытого состояния, должны добавляться к 1. Точно так же все вероятности перехода, происходящие из скрытого состояния, также должны складываться с 1.

Пример

У нас есть все математические основы. Давайте теперь возьмем для примера предложение «великая стена». Интуитивно мы знаем, что лучшая последовательность тегов - это DT-JJ-NN, но можем ли мы быть уверены, что первый тег - это DT, за которым следуют JJ и NN? Сначала нас спрашивают, какой выбор тега максимизирует P (t₁ | «the»). Поскольку мы знаем, что P (t₁ | «the») ∝ P («the» | t₁) P (t₁ | Start), давайте ответим на следующие вопросы.

  • Какой начальный тег наиболее вероятен? Это NN, JJ или DT?
  • Если у нас есть наиболее вероятный начальный тег, какое слово будет выдаваться чаще всего?

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

  • P (DT | «the») ∝ P («the» | DT) * P (DT | Начало)
  • P (NN | «the») ∝ P («the» | NN) * P (NN | Начало)
  • P (JJ | «the») ∝ P («the» | JJ) * P (JJ | Начало)

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

Мы можем ясно видеть, что выбор DT в качестве тега для «the» максимизирует P (t₁ | «the»).

Теперь, когда мы нашли первый тег как DT, мы спрашиваем, какой выбор t₂ максимизирует P (t₂ | «большой»)? К настоящему времени мы знаем, что нам нужно выбрать тег для t₂, который максимизирует P («great» | t₂) * P (t₂ | t₁ = DT). Мы ищем три вероятности излучения и перехода и замечаем, что P (t₂ | «большой») максимизируется, если мы выбираем P (JJ | DT) * P («большой» | JJ).

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

Мы расположили слова и все возможные теги в трех столбцах. Алгоритм Витерби вычисляет наиболее оптимальный путь на решетчатой ​​диаграмме, чтобы для выбранного тега произведение вероятностей излучения и перехода было максимальным.

Реализация

Чтобы получить последовательность тегов для немаркированного предложения, мы должны иметь вероятности перехода и выброса для всех переходов тегов и всех выбросов слов. Мы можем построить их из помеченного документа и использовать его для создания нашего декодера Витерби. Давайте займемся кодированием !! (посетите мою страницу GitHub, чтобы получить доступ ко всей записной книжке).

Хорошее место для начала - поиск помеченного корпуса. Библиотека NLTK имеет богатый набор ресурсов, которые уже помечены и могут использоваться для создания декодера. В Книге NLTK есть глава, посвященная всем лексическим ресурсам, которые может предложить эта библиотека.

Следующий фрагмент кода загружает коллекцию Wall Street Journals в виде списка предложений с тегами POS.

Пример предложения «г-н. Винкен - председатель Elsevier N.V., голландской издательской группы. ”отображается в виде списка кортежей следующим образом. В каждом кортеже есть слово и его тег.

[('Мистер', 'СУЩЕСТВИТЕЛЬНОЕ'), ('Винкен', 'СУЩЕСТВИТЕЛЬНОЕ'), ('есть', 'ГЛАГОЛ'), ('председатель', 'СУЩЕСТВИТЕЛЬНОЕ'), ('из', 'ADP'), ('Elsevier', 'СУЩЕСТВИТЕЛЬНОЕ'), ('NV', 'СУЩЕСТВИТЕЛЬНОЕ'), (',', '.'), ('The', 'DET'), ('голландский', 'СУЩЕСТВИТЕЛЬНОЕ'), ('публикация', 'ГЛАГОЛ'), ('группа', 'СУЩЕСТВИТЕЛЬНОЕ'), ('.', '.')]

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

  • Разделение поезд-тест оставляет 3718 обучающих и 196 тестовых предложений.
  • Количество помеченных обучающих слов составляет 95440, а помеченных тестовых слов - 5236.
  • Длина словаря 11017, имеется 12 уникальных тегов.

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

  • Для данного слова и тега вернуть кортеж, в котором указано количество раз, когда слово было отправлено из тега, и общее количество раз, когда этот тег возник.
  • Для заданных двух тегов t₁ и t₂ возвратите кортеж, в котором за t₁ следует t₁ и общее количество раз, когда t₁ произошло.

Фрейм данных tag_df предоставляет все возможности перехода между любым тегом t₁ (столбец) и t₂ (строка). Например, вероятность того, что за СУЩЕСТВИТЕЛЬНЫМ словом следует ГЛАГОЛ, равна 0,146889 (1-й столбец 5-й строки).

Теоретически мы также можем построить матрицу вероятности выбросов. Однако нам нужны два вложенных цикла, чтобы охватить все слова в словаре и все теги. С нашим размером словаря 11017 и 12 тегов это будет означать более 100 000 итераций. Есть способ лучше с этим справиться. Обратите внимание, что нам нужно вычислить P (w | t) только тех слов, которые мы встретим в тестовом наборе. Итак, когда мы просматриваем слова в тестовом наборе, мы можем вычислить P (w | t) на лету.

Функция Витерби берет последовательность слов и предсказывает последовательность тегов.

Теперь мы можем перебрать каждое предложение в тестовом наборе, удалить теги и отправить полученный список слов в функцию Витерби. Функция делает следующее.

  • Для каждого слова w в предложении вычислите P (w | ti) ∗ P (tᵢ | tᵢ-₁) для каждого из тегов. Мы используем набор поездов для вычисления этих вероятностей.
  • Выберите индекс максимального продукта и используйте его, чтобы указать на список тегов, чтобы предсказать тег для слова w.
  • Предсказанный тег сохраняется в списке tag_seq. Он используется для получения предыдущего тега, если мы не являемся началом предложения.
  • Если мы являемся началом предложения, предыдущий тег будет «.» (начальный тег).
  • Функция возвращает список кортежей, каждый из которых содержит слово и прогнозируемый тег.
  • В случае, если мы не находим слово в словаре, мы просто используем тег с максимальной вероятностью перехода.

В конце концов, у нас есть список pred_set, который представляет собой прогнозируемую версию набора тестов.

Когда мы сравниваем предсказанные теги и истинные теги, мы получаем следующие результаты.

Заключение

Мы построили простой вероятностный биграммный POS Tagger на основе HMM. Мы могли бы еще больше повысить производительность теггера, используя наиболее распространенный тег для неизвестных слов (то есть слов в тестовом наборе, которые не входят в набор для обучения). Тем не менее, тот же подход можно использовать и для построения моделей для распознавания именованных сущностей. Однако мы поговорим об этом в другой статье.

Оставайтесь с нами и наслаждайтесь обучением !!

Ссылки

Обработка естественного языка с помощью Python: Берд, Кляйн и Лопер

Обработка речи и языка: Джурафски и Мартин