Предположим, что есть коллекция документов \(D_1, ..., D_n\), помеченных как принадлежащая категории \(C_1, ..., C_k\).
Требуется определить категорию для нового документа \(D\).
При использовании вероятностного подхода ищем категорию \(C\) такую, что вероятность \(Р(C|D)\) максимальна.
Наивный метод Байеса ищет решение следующим образом:
Пусть \(T_1, T_2, ..., T_m\) - множество лексических терминов в \(D\).
Предположим, что нахождение элемента \(T\) на i-м месте \(D\) зависит только от категории \(C\) и,
учитывая наивные предположения, условно независимо от всех других элемнтов \(D\) и положения i.
Следовательно,
\[
P(D|C) = P(T_1|C) \times P(T_2|C) \times ... \times P(T_m|C),
\]
где \(P(T_i | C)\) означает "вероятность того, что документ категории \(C\) содержит по крайней мере
одно вхождение \(T_i\)".
Величины \(P(T_i | C)\) и \(P(C)\) оцениваются с использованием обучающей выборки:
- \(P(T_i | C)\) оценивается как относительная частота встречи (попадания) \(T_i\) в документах категории C.
- \(P(C)\) оценивается как доля документов в обучающей выборке, которые относятся к категории C.
И, наконец, заметим, что \(P(D)\) не зависит от категории \(C\). Поскольку данные документа D используем для того,
чтобы сравнить разные категории, вычислять \(P(D)\) нет необходимости.
Теперь для каждой категории \(C_i\) вычислим произведение
\begin{equation}\label{nbtext}
P(C_i) \times P(T_1 | C_i) \times P(T_2 | C_i)\times ... \times P(T_m | C_i)
\end{equation}
и выберем категорию, которая максимизирует это значение.
Заметим, что для реальных задач вычисление этого произведения вызовет проблемы с переполнением.
Чтобы этого избежать, вычисляется логарифм:
\[
\log (P(C_i) \times P(T_1 | C_i) \times P(T_2 | C_i) \times ... \times P(T_m | C_i)) =
\log (P(C_i)) + \log (P(T_1 | C_i)) + \log (P(T_2 | C_i)) + ... + \log (P(T_m | C_i)).
\]
Это преобразование показывает, что классификатор, построенный наивным Байесом, представляет собой линейный метод
разделения гиперплоскостью, под векторной моделью документов (одна гиперплоскость для двух категорий, набор гиперплоскостей для нескольких категорий).
Коррекция по Лапласу
Если в документе содержится лексический термин \(T\), которого нет ни в одном из документов категории \(C_j\), то \(P(T | C)\) будет
оценивается как 0. Тогда произведение (\ref{nbtext}) будет равно нулю, независимо от того, как обстоят дела с другими категориями \(C_i\).
Обычным решением является выполнение коррекции по Лапласу, путем увеличения всех отсчетов на единицу.
Пусть \(C_W\) - общее число вхождений слова \(W\) в документах категории \(C\), \(V\) - число разных слов в \(D\) и
\(|C|\) количество всех документов в категории \(C\). Оценим \(P(W | C)\) следующим образом
\[
P(W | C)=\frac{1 + C_W}{| C | + V}.
\]
Заметим, что \(\sum_{W\in D}P(W | D)=1\), как и должно быть.
Отметим некоторые особенности классификатора на основе наивных байесовских предположений.
Продолжительность проведения классификации: O (max (размер корпуса документов, количество разных слов * количество категорий)),
на практике это почти всегда O (размер корпуса документов).
Точность:
Плохая оценка вероятности, но в целом хорошие классификационные решения. Как правило, делает правильное предположение,
но решение является чрезмерным. Наивный байесовский классификатор не входит в список классификаторов высокого качества.
Надежный под шумом (робастность): Небольшие изменения в текстах или включение небольшого
число аномальных документов приводит к небольшим изменениям вероятности.
Использовать, когда: сравнительно короткое время работы более важно, чем точность. Если доступно очень большое количество
помеченного текста, лучшие результаты могут быть получены от грубого алгоритма на большом количестве
примеров, чем лучшим алгоритмом над набором данных, который должен быть намного меньше из-за ограничений времени работы.
Разметка текста с использованием модели k-gram
Ряд проблем в анализе естественного языка можно сформулировать в следующем виде:
предоставляется текст, который рассматривается как строка элементов и проблема состоит в том, чтобы назначить один терм из коллекции термов
для каждого из элементов.
Примеры:
- Элементы - это слова, а термы - части речи.
Здесь часто подразумевает более тонкие различия, чем обычные лингвистические категории. Например, «именованный объект», здесь
проблема распознавания включает категоризацию собственных существительных таких как личные имена, названия организаций,
географические названия и т.д.
- Элементы - это слова, а термы - значения слов (лексическая неоднозначность).
- Элементы представляют собой фонемы, которые анализируются в речи, а термы - это слова.
В статистическом обучении, как правило, предоставляется большой обучающий корпус (множество) правильно помеченного текста.
Таким образом, целью является извлечение шаблонов из обучающего корпуса, которые могут быть применены для маркировки нового текста.
Сформулируем проблему как поиск наиболее вероятной последовательности термов для данной последовательности элементов, то есть,
максимизация величины \(P(t_1, ... t_N|e_1,..., e_N),\) что означает "вероятность того, что строка термов \(t_1,... t_N\)
является строкой слов \(e_1, .... e_N\)".
Для начала применяем теорему Байеса
\[
P(t_1, ..., t_N| e_1, ..., e_N)=\frac{P(t_1, ..., t_N) \times P(e_1, ..., e_N |t_1, ..., t_N)}{P(e_1, ..., e_N )}
\]
Заметим, что знаменатель \(P(e_1, ..., e_N )\) зависит только от последовательности заданных элементов.
Поскольку это одно и то же для всех вариантов термов, то знаменатель можно проигнорировать (это называется «нормализующим фактором» и
единственным требованием является обеспечение того, чтобы сумма вероятностей по всем возможным последовательностям равнялась единице.)
Таким образом, проблема состоит в поиске последовательности термов, которые максимизируют произведение
\begin{equation}\label{term}
P(t_1, ..., t_N) \times P(e_1, ..., e_N |t_1, ..., t_N)
\end{equation}
Первый множитель - вероятность появления последовательности термов, прежде чем мы увидели, что представляют собой эти элементы.
Второй - вероятность, что последовательность термов \(t_1, ..., t_N\) будет создана как последовательность элементов
\(e_1, ..., e_N\).
Например, первый - вероятность того, что говорящий произнесет данное предложение ( иногда называемое «лингвистической» моделью),
второй - вероятность,что он произносил бы это так, как это слышал (так называемая «фонетическая» модель).
Второе выражение запишем следующим образом:
\[
P(e_1, ..., e_N |t_1, ..., t_N) = P(e_1|t_1, ..., t_N) \times P(e_2|t_1, ..., t_N) \times ... P(e_N|t_1, ..., t_N)
\]
Сделаем теперь следующее предположение о независимости:
\[
P(e_i| e_1, ... e_{i-1}, t_1, ... t_N) =P(e_i |t_i),
\]
то есть, как только мы установили \(i\)-й терм \(t_i\), вероятность любого элемента \(e_i\) не влияет на любой другой терм.
Сделав это предположение, мы можем переписать полученное соотношение в виде
\[
P(e_1|t_1) \times ... \times P(e_N|t_N)
\]
Теперь мы можем применить теорему Байеса к каждому из вышеуказанных факторов:
\[
P(e_i|t_i) =\frac{P(t_i| e_i) \times P(e_i)}{P(t_i)}
\]
все эти числа мы можем оценить из обучающего корпуса.
Теперь перейдем к первому множителю произведения (\ref{term}):
\(P(t_1, ... t_N)\) можем записать в виде,
\[
P(t_1, ... t_N) =P(t_1) \times P(t_2| t_1) \times P(t_3| t_1, t_ 2) \times
P(t_4| t_1, t_2, t_3) \times ... \times P(t_N| t_1,..., t_{N-1}).
\]
Сделаем второе предположение о независимости, известное как \( k \) -gram
(для некоторого малого целого \( k \), что зависимость \(i\)-го терма от всех предыдущих термов
фактически сводится к его зависимости от предыдущих \( k-1\) термов.
\[
P(t_i| t_1, ..., t_{i-1}) =P(t_i | t_{i+1-k}, ..., t_{i-1})
\]
Например, при \( k = 3 \) (обычный случай) получаем предположение триграммы
\[
P(t_i | t_1, ... t_{i-1}) =P(t_i| t_{i-2}, t_{i-1})
\]
При \( k = 2 \) получаем предположение о биграмме
\[
P(t_i | t_1, ..., t_{i-1}) = P(t_i| t_{i-1}).
\]
Заметим, что это вероятность увидеть указанный терм после \(k-1\) указаного терма в любой позиции предложения.
Чтобы упростить изложение, рассмотрим случай триграммы, то есть \(k = 3\).
Объединяя все вместе, получим соотношение
\[
P(t_1,..., t_N| e_1, ..., e_N)=
\frac{\prod_{i=1}^N P(t_i| t_{i-2},t_{i-1}) \times P(t_i| e_i) \times P(e_i)}{P(t_i)}.
\]
Опять же, поскольку \(e_i\) фиксированы, можем игнорировать множитель \(P(e_i)\), на который не влияет выбор терма и
все сводится к задаче максимизировать произведение
\[
\frac{\prod_{i=1}^N P(t_i| t_{i-2} t_{i-1}) \times P(t_i| e_i)}{ P(t_i)}.
\]
Проблема разреженных данных и сглаживание
Чтобы вычислить это произведение, понадобятся три типа вероятностей:
\(P(t_i | t_{i-2} t_{i-1}), P(t_i |e_i)\) и \(P(t_i)\).
Для их оценки используем обучающую выборку
\[
P(t_i| t_{i-2} t_{i-1}) =\mathcal{F}_C(t_i| t_{i-2} t_{i-1}),
\]
\[
P(t_i| e_i) =\mathcal{F}_C(t_i | e_i)
\]
и
\[
P(t_i)= \mathcal{F}_C(t_i)
\]
где
\(\mathcal{F}_C\) частота в обучающем корпусе \(C\).
К сожалению, есть проблемы, некоторые тройки термов \(t_{i-2},t_{i-1},t_i\)
могут фактически не встречаться в корпусе \(C\).
Если активная лексика составляет 10 000 слов, тогда в принципе может быть более триллиона разных триграмм и подавляющее большинство из них
невозможны.
Тем не менее, существует еще много триграмм, которые возможны и даже не маловероятны в своем появлении.
Решение, используемое для этой задачи, называется сглаживанием .
Для этого оцениваем вероятность того, что триграмма будет взвешенной суммой частоты триграмм, частоты биграмм, и частоты униграмм.
\[
P(t_i| t_{i-2} t_{i-1}) = w_3 \mathcal{F}_C (t_i| t_{i-2} t_{i-1}) + w_2 \mathcal{F}_C (t_i| t_{i-1}) + w_1 \mathcal{F}_C (t_i| t_{i-1})
\]
для некоторых фиксированных весов \(w_1, w_2, w_3\), которые в сумме дают единицу, например, \( w_1 = 0.1\), \( w_2 = 0.2\), \(w_3 = 0.7\).
Например, мы оцениваем вероятность увидеть «желе» после «железный гвоздь» в 0,7 раза больше частоты,
с которой «железный гвоздь» происходит от «желе» в корпусе, плюс в 0,2 раза больше частоты, с которой «гвоздь» происходит
от «желе» в корпусе, плюс в 0,1 раза больше частоты «желе» в корпусе.
Таким образом, мы даем триграммы, которые действительно встречаются в корпусе, и допускают возможность видеть новые триграммы
и даже новые биграммы.
