Наївна байєсова класифікація текстів.

Розглянемо метод навчання з учителем — мультиноміальний наївний метод Байєса (Naive Bayes — NB). У цьому методі імовірність того, що документ d належить класу c, обчислюється в такий спосіб:

. (1.1)

Тут - умовна імовірність того, що термін з'явиться в документі з класу c, — наша оцінка вкладу терміну в те, що документ буде належати класу с (міра правильного розпізнавання класу c по терміну , P(c) — апріорна імовірність того, що документ належить класу c. Якщо терміни документа не дозволяють чітко відокремити один клас від іншого, то варто вибрати той з них, що має більш високу апріорну імовірність. Послідовність складається з лексем документа d, які входять в словник документу, що використовується для класифікації, а — кількість таких лексем у документі d. Наприклад, послідовність для документа «Beijing and Taipei join the WTO», що складається з одного речення, може мати вигляд <Beijing, Taipei, join, WTO>, де = 4, після видалення стоп-слів and і the.

Мета класифікації текстів — знайти найкращий клас для документа. У методі NB найкращим вважається клас с_map, що має максимальну апостеріорну імовірність (maximum a posteriori - MAP).

(1.2)

Ми пишемо , а не P, тому що не знаємо справжніх параметрів P(c) і , а можемо лише оцінити їх за допомогою навчальних множин.

У рівності (1.2) перемножуються кілька умовних імовірностей, по одній для кожного значення . Це може призвести до переповнення машинної пам'яті і втрати значущих розрядів. Отже, краще замінити добуток імовірностей додаванням їх логарифмів. Клас з найбільшим значенням логарифма імовірності залишається найбільш ймовірним, тому що log(xy) = log(x) + log(y) і логарифмічна функція монотонна. Отже, у наївному методі Байєса насправді потрібно знайти точку максимуму наступної функції

Рівність (1.3) допускає просту інтерпретацію. Кожен логарифм умовної імовірності |c) — це вага, що вказує, наскільки важливий термін t_k для класу c. Аналогічно, апріорна імовірність — це вага, що характеризує відносну частоту класу c. Ті класи, що зустрічаються більш часто, частіше є правильними, ніж рідкісні. Таким чином, клас, сума логарифмів імовірностей і ваг термінів для якого має максимальне значення є аргументом на користь того, що документ належить цьому класу

Як оцінити імовірності і |c)? Спочатку спробуємо одержати оцінку максимальної правдоподібності, яка є відносною частотою і відповідає найбільш вірогідній величині кожного параметру при заданих навчальних даних. Для апріорних імовірностей оцінка має наступний вигляд

Тут — кількість документів у класі c, а — загальна кількість документів в колекції.

Оцінимо умовну імовірність |c) як відносну частоту терміна t у документі, що належить класу c

|c)= ,

Тут — кількість появ терміна t у навчальних документах із класу c з урахуванням багаторазових появ терміна в документі. Ця оцінка заснована на припущенні про позиційну незалежність: умовні імовірності появи терміну однакові незалежно від позиції цього терміну в документі і враховують тільки кількість появ терміну в документі.

З оцінкою максимальної правдоподібності позв'язана наступна проблема: якщо пара термін-клас не зустрічаються в навчальних даних, то відповідно і оцінка даного терміну для класу дорівнює нулю. Наприклад, якщо термін WTO у навчальних даних зустрічається тільки в документах класу China, то оцінка цього терміну для інших класів, наприклад, класу UK, дорівнюють нулю.

|UK)=0.

Тепер умовна імовірність класу UK щодо документа Britain is a member of the WTO, що складається з одного речення, дорівнює нулю, оскільки в рівності (4.1) ми перемножуємо умовні імовірності для всіх термінів. Очевидно, что модель повинна привласнювати класу UK високу імовірність, оскільки в пропозиції зустрічається термін Britain. Втім, не можна просто відкинути нульову імовірність для терміна WTO, незалежно від того наскільки багато є свідчень на користь класу UK, забезпечених іншими ознаками. Ця оцінка дорівнює нулю через рідкість терміна. Навчальні дані ніколи не бувають великими настільки, щоб частота рідких термінів оцінювалася адекватно, як, наприклад, частота терміна WTO у документах класу UK.

Для того щоб позбутися від нуля, ми використовуємо згладжування Лапласа (Laplace smoothing), просто додаючи одиницю до кожної частоти.

 

Тут = |V| — кількість термінів у словнику. Згладжування Лапласа можна інтерпретувати як апріорний рівномірний розподіл (кожен термін зустрічається в кожнім класі по одному разі), що потім уточнюється на основі навчальних даних, що надходять.