В предыдущей статье о Ngram мы сохраняли вероятности N последовательностей слов в словарях, чтобы выяснить, какие слова следует выбирать с наибольшей вероятностью. В этой статье мы рассмотрим вероятность на уровне символов с использованием Наивного Байеса.
Наивный Байес для данных временных рядов
Альтернативный подход состоит в том, чтобы вместо этого посмотреть на частоту каждой буквы и попытаться вывести из них закономерность. Этот вероятностный алгоритм использует маркировку каждого символа различными категориальными метками. Мы можем пометить каждый из символов в слове как:
S: однобуквенное слово
B: начальная буква
M: средняя буква
E : Конечная буква
В качестве примера строки «thisisatest», которая должна соответствовать «это тест», мы бы пометили ее следующим образом:
Feature: t h i s i s a t e s t Tag: B M M E B E S B M M E
Мы ищем вероятность каждой буквы с учетом ее метки. Например, вычислите вероятность буквы «t», если у нее есть метка «B» — начальная буква. Мы можем использовать Наивный байесовский метод для расчета его вероятности.
Начиная с теоремы Байеса, мы вычисляем условную вероятность метки y с учетом функции x, которая представляет собой входную последовательность букв. Мы бы хотели иметь:
Чтобы переписать это с точки зрения функций x и метки y, мы имеем:
Вектор x — это список функций, но в нашем случае это только одна функция — символ. Знаменатель P(x) считается нормализованным множителем, поэтому им можно пренебречь. Наивный Байес предполагает, что входные значения являются условно независимыми, что означает, что пара меток y и входных данных x не зависит от других пар. На основании этого упрощения получаем:
У нас есть x, так как функция набора состоит из букв от «a» до «z». У нас есть только одна функция, поэтому m=1. Тогда y — это метка в наборе S, B, M, E. P(x|y) — это условная вероятность x при заданном г. Этот алгоритм является генеративным подходом, поскольку он моделирует совместную вероятность входа x и метки y.
Модель пытается предсказать тег для данного персонажа. Например, 't', скорее всего, будет помечен как B (начальная буква) вместо E (конечная буква), учитывая данные нашего примера со словами 'this' и 'тест'. Наивный Байес обрабатывает каждую пару букв и тегов независимо. Предполагается, что входные значения (символы) условно независимы. Именно поэтому ее называют наивной моделью.
Пример
Итак, вернемся к примеру «thisisestest» выше. Нам нужно рассчитать вероятность соединения меток, которая имеет всего 11 меток. У нас есть одно символьное слово «S», 3 начальные буквы «B», 4 средние буквы «M» и 3 конечные буквы «E». Таким образом, вероятность каждой метки следующая:
P(S) = 1/11 P(B) = 3/11 P(M) = 4/11 P(E) = 3/11
Условная вероятность для буквы «t» с учетом ее тега S равна нулю, если ее тег B равен двум («это», «тест»), с учетом ее тега M равно нулю, а с учетом его тега E равно единице ("тест").
P(t|S) = 0 P(t|B) = 2/11 -- 'this', 'test' P(t|M) = 0 P(t|E) = 1/11 -- 'test'
Чтобы вычислить тег для буквы «т» из нашего тренировочного предложения, у нас есть.
P(y,x) = P(x|y)P(y) -- x='t' (only 1 feature) p(S,t) = P(t|S)P(S) = 0 * 1/11 = 0 P(B,t) = P(t|B)P(B) = 2/11 * 3/11 = 0.05 p(M,t) = P(t|M)P(M) = 0 * 4/11 = 0 p(E,t) = P(t|E)P(E) = 1/11 * 3/11 = 0.02
Для данной входной буквы «t» алгоритм предскажет тег как B (начальная буква), поскольку он имеет наибольшую вероятность.
Этот подход рассматривает только символ за раз и предполагает, что последовательность независима. В нашем случае это не очень хорошо, поскольку мы видим, что пара вход/тег не является независимой. Не похоже, что это подходит для нашего варианта использования. Но один из основных вариантов использования наивного байесовского метода — это классификация текста, например, предсказание спама, а не спама в электронной почте. См. один из наших вариантов использования Наивного Байеса для классификации текста кхмерского документа в этой статье. В этом случае у нас есть гораздо больше функций (например, список слов в тексте) для оценки алгоритма, а не только одна в нашем примере здесь.
В качестве сравнения с нашим окончательным алгоритмом CRF, который является последним алгоритмом в этой серии, мы пытаемся реализовать наивный байесовский алгоритм, используя те же функции, что и в CRF. Наш тест показывает точность 89% на кхмерских документах. В качестве предостережения, мы используем немного другой подход, чем упомянутый здесь, только с двумя тегами (1 = начало слова, 0 = иначе вместо «S», «B», «M», «E»). Мы используем 14 функций и реализуем их с помощью одноразового кодирования, что дает нам более 11 000 функций. Без горячего кодирования точность алгоритма составляет всего 62%. Кроме того, мы внедрили кластерный подход кхмерских символов. Мы объясним это более подробно в серии статей о реализации CRF. Подробную информацию о реализации см. в блокноте.
Вывод
В этой статье мы исследуем теорему Байеса и покажем детали и пример наивного Байеса. Мы видим, что Наивный Байес делает предположение об условной независимости меток и признаков. Это не очень хорошо работает с данными временных рядов, такими как последовательности символов в задаче сегментации слов.
Далее мы можем рассмотреть алгоритм, учитывающий последовательность символов и не делающий предположения об условной независимости входных значений. Этот алгоритм называется скрытой марковской моделью.
- Далее: НЛП: сегментация текста с использованием скрытой марковской модели
- Вернуться к серии: Сегментация кхмерского текста с использованием условных случайных полей
Ссылка:
- [1] Роман Клингер. Катрин Томанек. Классические вероятностные модели и. Условные случайные поля. Отчет по разработке алгоритмов. ТР07–2–013. декабрь 2007 г.