Классификация документов

Наивная байесовская модель является вероятностным методом обучения. Вероятность того, что документ d попадёт в класс c записывается как ${\displaystyle P(c|d)}$. Поскольку цель классификации - найти самый подходящий класс для данного документа, то в наивной байесовской классификации задача состоит в нахождении наиболее вероятного класса c_m

${\displaystyle c_{m}={\underset {c\in C}{\operatorname {argmax} }}\,P(c|d)}$

Вычислить значение этой вероятности напрямую невозможно, поскольку для этого нужно, чтобы обучающее множество содержало все (или почти все) возможные комбинации классов и документов. Однако, используя формулу Байеса, можно переписать выражение для ${\displaystyle P(c|d)}$

${\displaystyle c_{m}={\underset {c\in C}{\operatorname {argmax} }}\,{\frac {P(d|c)P(c)}{P(d)}}={\underset {c\in C}{\operatorname {argmax} }}\,P(d|c)P(c)}$

где знаменатель ${\displaystyle P(d)}$ опущен, так как не зависит от c и, следовательно, не влияет на нахождение максимума; P(c) - вероятность того, что встретится класс c, независимо от рассматриваемого документа; P(d|c) - вероятность встретить документ d среди документов класса c.

Используя обучающее множество, вероятность P(c) можно оценить как

${\displaystyle {\hat {P}}(c)={\frac {N_{c}}{N}}}$

где ${\displaystyle N_{c}}$ - количество документов в классе c, N - общее количество документов в обучающем множестве. Здесь использован другой знак для вероятности, поскольку с помощью обучающего множества можно лишь оценить вероятность, но не найти её точное значение.

Чтобы оценить вероятность ${\displaystyle P(d|c)=P(t_{1},t_{2},...,t_{n_{d}}|c)}$, где ${\displaystyle t_{k}}$ - терм из документа d, ${\displaystyle n_{d}}$ - общее количество термов в документе (включая повторения), необходимо ввести упрощающие предположения (1) о условной независимости термов и (2) о независимости позиций термов. Другими словами, мы пренебрегаем, во-первых, тем фактом, что в тексте на естественном языке появление одного слова часто тесно связано с появлением других слов (например, вероятнее, что слово интеграл встретится в одном тексте со словом уравнение, чем со словом бактерия), и, во-вторых, что вероятность встретить одно и то же слово различна для разных позиций в тексте. Именно из-за этих грубых упрощений рассматриваемая модель естественного языка называется наивной (тем не менее она является достаточно эффективной в задаче классификации). Итак, в свете сделанных предположений, используя правило умножения вероятностей независимых событий, можно записать

${\displaystyle P(d|c)=P(t_{1},t_{2},...,t_{n_{d}}|c)=P(t_{1}|c)P(t_{2}|c)...P(t_{n_{d}}|c)=\prod _{k=1}^{n_{d}}P(t_{k}|c)}$

Оценка вероятностей ${\displaystyle P(t|c)}$ с помощью обучающего множества будет

${\displaystyle {\hat {P}}(t|c)={\frac {T_{ct}}{T_{c}}}}$

где ${\displaystyle T_{ct}}$ - количество вхождений терма t во всех документах класса c (и на любых позициях - здесь существенно используется второе упрощающее предположение, иначе пришлось бы вычислить эти вероятности для каждой позиции в документе, что невозможно сделать достаточно точно из-за разреженности обучающих данных - трудно ожидать, чтобы каждый терм встретился в каждой позиции достаточное количество раз); ${\displaystyle T_{c}}$ - общее количество термов в документах класса c. При подсчёте учитываются все повторные вхождения.

После того, как классификатор "обучен", то есть найдены величины ${\displaystyle {\hat {P}}(c)}$ и ${\displaystyle {\hat {P}}(t|c)}$, можно отыскать класс документа

${\displaystyle c_{m}={\underset {c\in C}{\operatorname {argmax} }}\,{\hat {P}}(d|c){\hat {P}}(c)={\underset {c\in C}{\operatorname {argmax} }}{\hat {P}}(c)\prod _{k=1}^{n_{d}}{\hat {P}}(t_{k}|c)}$

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

${\displaystyle c_{m}={\underset {c\in C}{\operatorname {argmax} }}[\log {\hat {P}}(c)+\sum _{k=1}^{n_{d}}\log {\hat {P}}(t_{k}|c)]}$

Эта формула имеет простую интерпретацию. Шансы классифицировать документ часто встречающимся классом выше, и слагаемое ${\displaystyle \log {\hat {P}}(c)}$ вносит в общую сумму соответствующий вклад. Величины же ${\displaystyle \log {\hat {P}}(t|c)}$ тем больше, чем важнее терм t для идентификации класса c, и, соответственно, тем весомее их вклад в общую сумму.