В предыдущей статье о 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. Подробную информацию о реализации см. в блокноте.

Вывод

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

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

Ссылка: