Наївний баєсовський класифікатор (Naive Bayes Classifier)
В основі NBC (Naive Bayes Classifier) лежить теорема Байєса.
(3.1)
де,
P(c|d) - ймовірність що документ d належить класу c, саме її нам треба розрахувати;
P(d|c) - ймовірність зустріти документ d серед усіх документів класу c;
P(c) - безумовна ймовірність зустріти документ класу c в корпусі документів;
P(d) - безумовна ймовірність документа d в корпусі документів.
Її сенс на обивательському рівні можна виразити таким чином. Теорема Байєса дозволяє переставити місцями причину і наслідок. Знаючи з якою ймовірністю причина призводить до якоїсь події, ця теорема дозволяє розрахувати ймовірність того що саме ця причина призвела до спостережуваної події.
Мета класифікації полягає в тому щоб зрозуміти до якого класу належить документ, тому нам потрібна не сама ймовірність, а найбільш ймовірний клас. Байєсовський класифікатор використовує оцінку апостеріорного максимуму (Maximum a posteriori estimation) для визначення найбільш ймовірного класу. Грубо кажучи, це клас з максимальною ймовірністю.
(3.2)
Тобто нам треба розрахувати ймовірність для всіх класів і вибрати той клас, який володіє максимальною ймовірністю. Зверніть увагу, знаменник (ймовірність документа) є константою і ніяк не може вплинути на ранжування класів, тому в нашому завданні ми можемо його ігнорувати.
(3.3)
Далі робиться припущення, яке і пояснює чому цей алгоритм називають наївним.
3.1. Припущення умовної незалежності
Якщо я вам скажу "вчора було темно ...", ви відразу зрозумієте про яке місце що йде мова, навіть якщо я не закінчу фразу. Так відбувається тому що в справжній мові ймовірність появи слова сильно залежить від контексту. Байєсівський класифікатор представляє документ як набір слів ймовірності яких умовно не залежать один від одного. Цей підхід іноді ще називається bag of words model. Виходячи з цього припущення умовна ймовірність документа апроксимується похідними умовними ймовірностями всіх слів, що входять в документ.
(3.1.1)
Цей підхід також називається Unigram Language Model. Мовні моделі відіграють дуже важливу роль в задачах обробки справжніх мов.
Підставивши отриманий вираз у формулу № 1 ми отримаємо:
(3.1.2)
Проблема арифметичного переповнення
При
досить великій довжині документа
доведеться перемножувати велику
кількість дуже маленьких чисел. Для
того щоб при цьому уникнути арифметичного
переповнення знизу найчастіше користуються
властивістю логарифму
добутку
.
Так як логарифм функція монотонна, її
застосування до обох частин виразу
змінить тільки його чисельне значення,
але не параметри при яких досягається
максимум. При цьому, логарифм від числа
близького до нуля буде числом негативним,
але в абсолютному значенні суттєво
більшим ніж вихідне число, що робить
логарифмічні значення ймовірностей
більш зручними для аналізу. Тому, ми
переписуємо нашу формулу з використанням
логарифму.
(3.2.1)
Основа логарифму в даному випадку не має значення. Ви можете використовувати як натуральний, так і будь-який інший логарифм.