Лекція 8. Ймовірнісні методи класифікації. Наївний баєсів класифікатор #

Огляд #

У Лекції 7 ми будували класифікатори, що приймають однозначне рішення: дерево рішень веде об’єкт від кореня до листа й повертає один клас. Такі моделі не кажуть, наскільки вони впевнені. Але в аналітиці даних оцінка впевненості часто важливіша за саме рішення: банк хоче знати не лише «видати кредит чи ні», а ймовірність неповернення; поштова служба — не лише «спам чи ні», а міру «спамовості» листа, щоб порівняти її з порогом. Клас методів, що дають таку оцінку, називають ймовірнісними класифікаторами.

У цьому розділі ми будуємо найпоширеніший ймовірнісний класифікатор — наївний баєсів. Його ідея проста: за теоремою Байєса перевести відомі з даних умовні ймовірності ознак на апостеріорну ймовірність класу, а щоб зробити обчислення здійсненним — прийняти наївне припущення про умовну незалежність ознак. Ми виведемо формулу $P(C \mid x) \propto P(C)\prod_j P(x_j \mid C)$, навчимося оцінювати всі її множники частотами з навчальної вибірки, розберемо наскрізний приклад на тій самій вибірці «Спортивний канал», що й у Лекції 7, натрапимо на проблему нульових імовірностей і виправимо її згладжуванням Лапласа, зважимо переваги й недоліки методу і, нарешті, застосуємо його до класичної задачі — баєсового спам-фільтра. Наступна Лекція 9 переходить від класифікації (навчання з учителем) до кластеризації — пошуку структури в даних без наперед відомих класів.

Практичний бік. Апостеріорні ймовірності ви обчислюватимете «руками», а наївний баєсів класифікатор — програмою в Лабораторній роботі 8, де порівняєте його прогнози з деревом ID3 із Лабораторної 7.

Наскрізний приклад лекції — та сама навчальна вибірка «Спортивний канал», що й у Лекції 7: за трьома ознаками глядача (стать, дохід, чи він студент) передбачаємо, чи підписав він спортивний телеканал.

Цільова ознака «Спортивний канал?» має два значення; у вибірці 5 об’єктів класу «Так» і 5 класу «Ні» — класи збалансовані.

8.1 Ймовірнісна класифікація #

Нагадаємо задачу класифікації з Лекції 7: за значеннями предикторів (вхідних атрибутів) об’єкта передбачити значення цільової категоріальної ознаки — класу. Дерево рішень і One Rule повертали ярлик класу. Ймовірнісний підхід повертає більше.

Означення (ймовірнісна класифікація). Ймовірнісним називають класифікатор, який для кожного об’єкта $x$ оцінює ймовірність його належності до кожного з можливих класів — $P(C \mid x)$ для всіх $C$ — і лише потім (за потреби) обирає клас за цими ймовірностями.

Такий вихід багатший за просто ярлик. По-перше, він дає впевненість: об’єкт з $P(\text{Так} \mid x) = 0.99$ і об’єкт з $P(\text{Так} \mid x) = 0.51$ обидва дістануть клас «Так», але довіра до них різна. По-друге, ймовірність можна порівнювати з порогом, який залежить від ціни помилки: якщо пропустити хворого дорожче, ніж перестрахуватися, поріг для класу «здоровий» піднімають. По-третє, ймовірності природно впорядковують об’єкти (скоринг) — від найімовірніших підписників до найменш імовірних.

Щоб оцінити $P(C \mid x)$, потрібен місток від того, що легко порахувати з даних (як часто клас породжує таку ознаку), до того, що ми хочемо знати (який клас за цією ознакою). Цей місток дає теорема Байєса.

8.2 Теорема Байєса та баєсів класифікатор #

Умовну ймовірність і теорему Байєса введено в Лекції 1. Нагадаємо її у формі, зручній для класифікації.

Теорема (Байєса). Для класу $C$ та спостережуваного вектора ознак $x$

$$P(C \mid x) = \frac{P(x \mid C)\, P(C)}{P(x)}.$$

Кожен множник має свою назву й свою роль:

• $P(C)$ — апріорна ймовірність класу (що ми знаємо про клас до перегляду ознак: яка частка підписників узагалі);
• $P(x \mid C)$ — правдоподібність (англ. likelihood): наскільки ймовірно, що об’єкт класу $C$ має саме такі ознаки $x$;
• $P(C \mid x)$ — апостеріорна ймовірність (що ми знаємо про клас після перегляду ознак) — те, що нас цікавить;
• $P(x)$ — свідчення (англ. evidence): ймовірність побачити ознаки $x$ узагалі.

Означення (задача баєсівської класифікації). Об’єкту $x$ приписують клас з найбільшою апостеріорною ймовірністю (правило MAP, англ. maximum a posteriori):

$$\hat{C}(x) = \arg\max_{C} P(C \mid x) = \arg\max_{C} \frac{P(x \mid C)\, P(C)}{P(x)}.$$

Ключове спостереження: знаменник $P(x)$ не залежить від класу — для всіх класів він той самий. Тому при виборі класу його можна відкинути:

$$\hat{C}(x) = \arg\max_{C}\, P(x \mid C)\, P(C).$$

Величину $P(x \mid C)\, P(C)$ називатимемо оцінкою (незнормованою вагою) класу. Знаменник $P(x)$ знадобиться лише тоді, коли треба повернути самі ймовірності, а не тільки клас-переможець (§8.5).

8.3 Наївне припущення й апостеріорна ймовірність #

Здавалося б, лишилось оцінити $P(x \mid C)$ і $P(C)$ з даних — і задачу розв’язано. Апріорну ймовірність $P(C)$ справді оцінити легко. А от правдоподібність $P(x \mid C)$ ховає пастку.

Об’єкт описано вектором ознак $x = (x_1, x_2, \dots, x_m)$, тож $P(x \mid C) = P(x_1, x_2, \dots, x_m \mid C)$ — це ймовірність конкретної комбінації значень усіх ознак. Щоб оцінити її частотою, треба знайти в даних об’єкти того самого класу з точно таким самим набором усіх ознак. Але кількість можливих комбінацій зростає мультиплікативно: для наших трьох ознак зі $2$, $3$ і $2$ значеннями це $2 \cdot 3 \cdot 2 = 12$ комбінацій на кожен клас, а для десятка ознак — тисячі й мільйони. У навчальній вибірці з $10$ рядків більшість комбінацій жодного разу не трапляться, і надійно оцінити $P(x \mid C)$ неможливо. Це — прокляття розмірності.

Вихід дає наївне припущення.

Означення (наївне припущення про умовну незалежність). Ознаки вважають умовно незалежними за класом: якщо клас відомий, значення однієї ознаки не дає інформації про значення іншої. Формально

$$P(x_1, x_2, \dots, x_m \mid C) = \prod_{j=1}^{m} P(x_j \mid C).$$

Замість однієї важкої спільної ймовірності ми перемножуємо $m$ простих одновимірних — кожну з них легко оцінити частотою. Припущення називають «наївним», бо в реальних даних ознаки зазвичай залежні (дохід і статус студента корелюють). Дивовижно, але навіть коли припущення хибне, класифікатор часто працює добре: для вибору класу важливий не точний добуток, а те, який клас дає більший добуток, і систематичні перекоси нерідко однаково впливають на всі класи.

Підставивши наївне припущення в теорему Байєса, дістаємо робочу формулу методу.

Властивість (апостеріорна ймовірність наївного Байєса).

$$P(C \mid x) \;\propto\; P(C) \prod_{j=1}^{m} P(x_j \mid C),$$

де знак $\propto$ («пропорційно») ховає сталий для всіх класів множник $1/P(x)$. Клас обирають за найбільшою правою частиною.

8.4 Оцінювання ймовірностей за тренувальною вибіркою #

Формула §8.3 містить два типи множників — $P(C)$ та $P(x_j \mid C)$. Обидва оцінюють відносними частотами з навчальної вибірки (це оцінки методом максимальної правдоподібності).

Нехай навчальна вибірка має $N$ об’єктів, з них $N_C$ належать класу $C$.

Оцінка апріорної ймовірності класу:

$$P(C) = \frac{N_C}{N}.$$

Оцінка умовної ймовірності ознаки: для ознаки $j$ зі значенням $v$

$$P(x_j = v \mid C) = \frac{N_{C,\, j = v}}{N_C},$$

де $N_{C,\, j=v}$ — число об’єктів класу $C$, у яких ознака $j$ має значення $v$.

Іншими словами: щоб оцінити $P(\text{Дохід}=\text{Високий} \mid \text{Так})$, ми дивимося лише на підписників і рахуємо, яка їх частка має високий дохід.

У нашому прикладі клас збалансований, тож апріорні ймовірності

$$P(\text{Так}) = \frac{5}{10} = 0.5, \qquad P(\text{Ні}) = \frac{5}{10} = 0.5.$$

Умовні ймовірності зручно звести в таблицю, розбивши вибірку за класом і для кожної ознаки полічивши частоти (це рівно те, що показують окремі слайди приклади за кожним атрибутом). Класи: «Так» $= \{1,5,6,7,8\}$, «Ні» $= \{2,3,4,9,10\}$.

Зверніть увагу на два нулі: серед підписників немає жодного з низьким доходом ($P(\text{Низький} \mid \text{Так}) = 0$), а серед непідписників — жодного з високим ($P(\text{Високий} \mid \text{Ні}) = 0$). До цих нулів ми ще повернемося у §8.7 — вони спричиняють головну проблему методу.

8.5 Класифікація об’єкта #

Маючи таблицю ймовірностей, класифікувати об’єкт означає: обчислити оцінку $P(C)\prod_j P(x_j \mid C)$ для кожного класу, обрати найбільшу і — за потреби — знормувати оцінки в ймовірності.

Нормування спирається на формулу повної ймовірності для знаменника: оскільки класи вичерпні й несумісні, $P(x) = \sum_{C'} P(x \mid C')P(C')$ — це просто сума оцінок усіх класів. Тому

Формула нормування.

$$P(C \mid x) = \frac{P(C)\prod_j P(x_j \mid C)}{\displaystyle\sum_{C'} P(C')\prod_j P(x_j \mid C')}.$$

Знаменник — сума всіх незнормованих оцінок; після ділення ймовірності всіх класів дають у сумі одиницю.

Повний алгоритм — навчання (підрахунок частот) і класифікація:

NaiveBayesTrain(навчальна вибірка D, ознаки A, клас y):
  N <- |D|
  для кожного класу C:
      P(C) <- N_C / N                       # апріорна ймовірність
      для кожної ознаки j із A:
          для кожного значення v ознаки j:
              P(x_j = v | C) <- N_{C, j=v} / N_C   # умовна ймовірність
  повернути таблиці P(C) і P(x_j | C)

NaiveBayesClassify(об'єкт x = (x_1,...,x_m)):
  для кожного класу C:
      score(C) <- P(C)
      для j = 1..m:
          score(C) <- score(C) * P(x_j | C)   # наївний добуток
  Z <- сума score(C) за всіма класами
  для кожного C:  P(C | x) <- score(C) / Z    # нормування
  повернути argmax_C P(C | x)  та  всі P(C | x)

Складність навчання — один прохід по вибірці (лінійна за розміром даних), а класифікація одного об’єкта — $O(m \cdot |\text{класів}|)$. Саме ця дешевизна робить наївний Байєс привабливим для великих і потокових даних.

8.6 Наскрізний приклад: «Спортивний канал» #

Застосуємо алгоритм до кількох рядків вибірки, а потім зведемо результат для всіх десяти. Апріорні ймовірності — $P(\text{Так}) = P(\text{Ні}) = 0.5$; умовні ймовірності беремо з таблиці §8.4.

Приклад 8.1 (упевнений об’єкт: рядок 8). Об’єкт $8$ — (Ч, Середній, студент Так). Обчислимо оцінки обох класів:

$$\text{score}(\text{Так}) = P(\text{Так})\,P(\text{Ч} \mid \text{Так})\,P(\text{Середній} \mid \text{Так})\,P(\text{Так} \mid \text{Так}) = 0.5 \cdot 0.6 \cdot 0.6 \cdot 0.6 = 0.108,$$

$$\text{score}(\text{Ні}) = 0.5 \cdot 0.2 \cdot 0.4 \cdot 0.4 = 0.016.$$

Нормуємо:

$$P(\text{Так} \mid x_8) = \frac{0.108}{0.108 + 0.016} = \frac{0.108}{0.124} = \frac{27}{31} \approx 0.871.$$

Апостеріорна ймовірність підписки $\approx 0.871 > 0.5$, тож прогноз — «Так» (справжній клас теж «Так»).

Приклад 8.2 (об’єкт на користь «Ні»: рядок 2). Об’єкт $2$ — (Ж, Середній, студент Ні):

$$\text{score}(\text{Так}) = 0.5 \cdot 0.4 \cdot 0.6 \cdot 0.4 = 0.048, \qquad \text{score}(\text{Ні}) = 0.5 \cdot 0.8 \cdot 0.4 \cdot 0.6 = 0.096.$$

$$P(\text{Так} \mid x_2) = \frac{0.048}{0.048 + 0.096} = \frac{0.048}{0.144} = \frac{1}{3} \approx 0.333.$$

Оскільки $0.333 < 0.5$, прогноз — «Ні» (справжній клас «Ні»).

Приклад 8.3 (нуль занулює добуток: рядок 1). Об’єкт $1$ — (Ч, Високий, студент Так):

$$\text{score}(\text{Так}) = 0.5 \cdot 0.6 \cdot 0.4 \cdot 0.6 = 0.072, \qquad \text{score}(\text{Ні}) = 0.5 \cdot 0.2 \cdot \underbrace{0.0}_{P(\text{Високий}\mid\text{Ні})} \cdot 0.4 = 0.$$

Множник $P(\text{Високий} \mid \text{Ні}) = 0$ обнуляє всю оцінку класу «Ні», тож $P(\text{Так} \mid x_1) = 0.072 / 0.072 = 1.000$ — модель абсолютно впевнена. Так само рядок $3$ (Ч, Низький, Так) дає $P(\text{Так}) = 0$ через $P(\text{Низький} \mid \text{Так}) = 0$. Ця «абсолютна впевненість» через єдиний нуль — двосічна: тут вона випадково правильна, але загалом небезпечна (§8.7).

Проробивши те саме для всіх десяти об’єктів, дістаємо підсумкову таблицю апостеріорних імовірностей (звірено обчисленням; збігається зі слайдом-підсумком лекції):

Наївний Байєс правильно класифікував усі $10$ об’єктів навчальної вибірки — правильність (за навчальними даними) $100\,\%$. Це рівно той самий результат, що дало дерево ID3 з Прикладу 7.3: обидва методи безпомилкові на цій вибірці й збігаються в кожному рядку. Різниця — у виході: дерево повертає ярлик, наївний Байєс — ще й ступінь упевненості (порівняйте «граничний» рядок $7$ з $P = 0.529$ і «впевнений» рядок $8$ з $P = 0.871$ — дерево між ними не розрізняє).

Типова помилка (плутати оцінку з імовірністю). Добуток $P(C)\prod_j P(x_j \mid C)$ сам по собі не є ймовірністю — це незнормована оцінка, і сума таких оцінок за класами зазвичай не дорівнює $1$. Ймовірність дістають лише після ділення на суму всіх оцінок (§8.5). Для вибору класу нормування не потрібне; воно потрібне, коли ви звітуєте саму ймовірність.

8.7 Проблеми наївного Байєса #

Метод має три характерні слабкі місця.

Залежність атрибутів #

Наївне припущення (§8.3) вважає ознаки умовно незалежними, та в реальних даних це рідко так. Якщо дві ознаки сильно корелюють (наприклад, «дохід» і «має власне житло»), наївний Байєс фактично враховує спільну інформацію двічі й може давати надто категоричні ймовірності (близькі до $0$ чи $1$). На рейтинг класів це часто не впливає, але числу $P(C \mid x)$ як «справжній імовірності» тоді довіряти не можна. Виправлення — обирати менш корельовані ознаки або скористатися повнішими моделями (баєсові мережі).

Проблема нульових імовірностей (переповнення) #

Якщо якесь значення ознаки жодного разу не трапилось у класі $C$, то $P(x_j \mid C) = 0$, і весь добуток $P(C)\prod_j P(x_j \mid C)$ занулюється — незалежно від того, наскільки переконливі решта ознак. Один нуль «перекриває» будь-які інші свідчення.

У нашій вибірці саме так поводяться два нулі з §8.4. Розгляньмо об’єкт $3$ — (Ч, Низький, студент Так). Стать «Ч» ($P = 0.6$ на користь «Так») і статус студента ($P = 0.6$ на користь «Так») обидва схиляють до підписки, проте

$$\text{score}(\text{Так}) = 0.5 \cdot 0.6 \cdot \underbrace{0.0}_{\text{Низький}\mid\text{Так}} \cdot 0.6 = 0 \;\Rightarrow\; P(\text{Так} \mid x_3) = 0.$$

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

Із цим пов’язана й обчислювальна біда: коли ознак багато, добуток багатьох малих імовірностей стає надзвичайно малим і може зникнути в нуль через скінченну точність чисел (underflow). Тому на практиці працюють не з добутком, а з сумою логарифмів:

$$\log\!\Big(P(C)\prod_j P(x_j \mid C)\Big) = \log P(C) + \sum_j \log P(x_j \mid C),$$

що зберігає порядок класів, але не переповнюється (за умови, що жодне $P(x_j \mid C)$ не дорівнює точно нулю — а це знову вимагає згладжування, §8.8).

Проблема відсутніх атрибутів #

Якщо в об’єкта, який класифікують, немає значення якоїсь ознаки (пропуск у даних), відповідний множник просто пропускають у добутку: наївна структура це дозволяє, бо решта множників від нього не залежать. Об’єкт класифікують за наявними ознаками. (Пропуски в навчальній вибірці враховують інакше — не рахуючи такі об’єкти при оцінці відповідної умовної ймовірності.)

8.8 Адитивне (Лапласове) згладжування #

Проблему нульових імовірностей розв’язує адитивне згладжування: до кожного підрахунку додають невеличку «уявну» кількість, щоб жодна ймовірність не була точним нулем.

Означення (згладжування Лапласа). Оцінку умовної ймовірності замінюють на

$$P(x_j = v \mid C) = \frac{N_{C,\, j=v} + 1}{N_C + m_j},$$

де $m_j$ — кількість різних значень ознаки $j$. Додавання $1$ у чисельнику «дарує» кожному значенню один уявний об’єкт, а додавання $m_j$ у знаменнику зберігає нормування ($\sum_v P(x_j = v \mid C) = 1$).

Одиниця в чисельнику — окремий випадок ($\alpha = 1$) загальнішого згладжування з довільним $\alpha > 0$ у чисельнику й $\alpha m_j$ у знаменнику; при $\alpha = 1$ його називають лапласовим, при менших $\alpha$ — Лідстоуновим.

Приклад 8.4 (згладжені ймовірності для «Спортивний канал»). Ознаки мають $m_{\text{Стать}} = 2$, $m_{\text{Дохід}} = 3$, $m_{\text{Студент}} = 2$ значень. Тоді, наприклад, для класу «Так» ($N_C = 5$):

$$P(\text{Низький} \mid \text{Так}) = \frac{0 + 1}{5 + 3} = \frac{1}{8} = 0.125 \quad (\text{було } 0),$$

$$P(\text{Високий} \mid \text{Так}) = \frac{2 + 1}{5 + 3} = \frac{3}{8} = 0.375, \qquad P(\text{Середній} \mid \text{Так}) = \frac{3 + 1}{5 + 3} = \frac{4}{8} = 0.5,$$

і сума трьох згладжених імовірностей доходу $0.125 + 0.375 + 0.5 = 1$ — як і має бути. Так само зникає й другий нуль: $P(\text{Високий} \mid \text{Ні}) = (0+1)/(5+3) = 0.125$.

Приклад 8.5 (як згладжування «лікує» об’єкт 3). Повернімося до об’єкта $3$ — (Ч, Низький, студент Так), який без згладжування діставав $P(\text{Так}) = 0$. Зі згладженими ймовірностями ($P(\text{Ч} \mid \text{Так}) = 4/7$, $P(\text{Низький} \mid \text{Так}) = 1/8$, $P(\text{Так} \mid \text{Так}) = 4/7$; а для «Ні» — $P(\text{Ч} \mid \text{Ні}) = 2/7$, $P(\text{Низький} \mid \text{Ні}) = 1/2$, $P(\text{Так} \mid \text{Ні}) = 3/7$):

$$\text{score}(\text{Так}) = 0.5 \cdot \tfrac{4}{7} \cdot \tfrac{1}{8} \cdot \tfrac{4}{7} = \tfrac{1}{49} \approx 0.0204, \qquad \text{score}(\text{Ні}) = 0.5 \cdot \tfrac{2}{7} \cdot \tfrac{1}{2} \cdot \tfrac{3}{7} = \tfrac{3}{98} \approx 0.0306.$$

$$P(\text{Так} \mid x_3) = \frac{1/49}{1/49 + 3/98} = \frac{2}{5} = 0.400.$$

Тепер модель уже не відкидає клас «Так» категорично: вона оцінює його ймовірність у $0.400$ і схиляється до «Ні» (справжній клас) лише з помірною перевагою $0.600$ проти $0.400$. Замість фальшивої абсолютної впевненості — чесна невизначеність. Прогноз лишився правильним, а на всій вибірці згладжений наївний Байєс так само дає $100\,\%$ правильності — але його ймовірності «м’якші» (крайні $0.000$ і $1.000$ підтягуються до середини).

Типова помилка (забути $m_j$ у знаменнику). Часто додають $1$ у чисельник, але забувають додати $m_j$ (число значень ознаки) у знаменник. Тоді суми ймовірностей за значеннями перестають дорівнювати $1$, і оцінки різних ознак стають неспівмірними. Знаменник має зростати рівно на стільки, скільки «уявних» об’єктів ви додали загалом, — по одному на кожне значення.

8.9 Переваги та недоліки #

Переваги:

• Швидкість. Навчання — один прохід по даних (лінійне), класифікація — кілька множень. Метод масштабується на великі й потокові дані.
• Прозорість. Кожну умовну ймовірність можна прочитати й пояснити: видно, яка саме ознака й наскільки схилила рішення до того чи іншого класу.
• Стійкість до нерелевантних ознак. Ознака, розподілена в класах однаково, дає майже однакові множники всім класам і на вибір майже не впливає — «шумні» атрибути метод фактично відкидає самі собою.
• Мала потреба в даних для старту. Оскільки оцінюють лише одновимірні ймовірності $P(x_j \mid C)$, метод дає розумні результати навіть на порівняно невеликих вибірках (на відміну від оцінки спільного розподілу).

Недоліки:

• Хибне припущення незалежності. Коли ознаки залежні, самі числа $P(C \mid x)$ спотворені (надто близькі до $0$/$1$), хоча рейтинг класів часто зберігається.
• Врахування лише індивідуальних значень. Метод «бачить» кожну ознаку окремо й не вловлює взаємодій між ними (наприклад, коли небезпечна саме комбінація двох ознак, а не кожна поодинці).
• Чутливість до нулів. Без згладжування єдине незнайоме значення обнуляє клас (§8.7).
• Потреба у представницькій вибірці. Оцінки ймовірностей надійні лише тоді, коли навчальні дані добре відображають генеральну сукупність; на зсунутій вибірці апріорні та умовні ймовірності будуть систематично неправильні.

8.10 Баєсів спам-фільтр #

Класичне застосування наївного Байєса — фільтрація спаму. Тут два класи: $\text{спам}$ і $\text{не спам}$ (англ. ham), а ознаки об’єкта-листа — слова, що в ньому трапляються. Схема така:

1. Розбити повідомлення на слова (токени).
2. Для кожного слова оцінити "спамовість" p(w) — імовірність, що лист спам,
   якщо він містить це слово.
3. Обчислити усереднену вагу слів повідомлення.
4. Якщо усереднена вага > порогу — надіслати лист у спам.

Спамовість окремого слова оцінюють за Байєсом, порівнюючи, як часто слово трапляється в спамі й у звичайній пошті.

Означення (спамовість слова). Нехай $b(w)$ — частка спам-листів, що містять слово $w$, а $g(w)$ — частка звичайних листів, що містять $w$. За рівних апріорних ймовірностей класів спамовість слова

$$p(w) = \frac{b(w)}{b(w) + g(w)}.$$

Це апостеріорна ймовірність «лист — спам» за умови наявності самого слова $w$: $p(w) \to 1$ для суто спамових слів, $p(w) \to 0$ для суто «чистих».

Приклад 8.6 (ваги слів). Нехай навчальна база має $20$ спам- і $20$ звичайних листів, а три слова трапляються так:

Приклад 8.7 (рішення за усередненою вагою). Візьмемо поріг $0.5$.

• Лист «виграш кредит»: усереднена вага $(0.889 + 0.750)/2 = 0.819 > 0.5$ $\Rightarrow$ спам.
• Лист «зустріч кредит»: $(0.125 + 0.750)/2 = 0.438 < 0.5$ $\Rightarrow$ не спам.

Усереднення ваг — спрощена схема зі слайдів; строгий наївний Байєс комбінує слова не середнім, а добутком (краще — сумою логарифмів). Для листа «виграш кредит» строга формула

$$P(\text{спам}) = \frac{p_1 p_2}{p_1 p_2 + (1-p_1)(1-p_2)} = \frac{0.889 \cdot 0.750}{0.889 \cdot 0.750 + 0.111 \cdot 0.250} \approx 0.96$$

дає ще впевненіший результат, ніж усереднення ($0.82$). Обидві схеми відносять лист до спаму; добуткова просто рішучіша.

Покращення спам-фільтра (зі слайдів) прибирають типові вади базової схеми:

• Проблема рідкісних слів. Слово, що трапилося раз-двічі, дає ненадійну $p(w)$ (у крайньому разі $0$ чи $1$) — його згладжують (§8.8) або зважують за частотою.
• Прибирання нейтральних слів. Слова з $p(w) \approx 0.5$ (сполучники, прийменники) не несуть інформації; їх відкидають, лишаючи лише найінформативніші.
• Аналіз повторів. Багаторазова поява слова в листі підсилює його вагу.
• Послідовності слів (патерни). Замість окремих слів беруть біграми/фрази («безкоштовний кредит»), що частково повертає втрачені деревом залежності.
• Попередня обробка тексту. Зведення слів до основи (стемінг), нижній регістр, видалення розділових знаків — щоб «Виграш», «виграш» і «виграшу» рахувались як одне слово.

Застосування в аналітиці даних #

• Класифікація тексту. Спам-фільтри, визначення тематики документів, аналіз тональності відгуків — наївний Байєс залишається сильним базовим методом для тексту (слова природно є «незалежними» ознаками-лічильниками).
• Швидкий базовий класифікатор. Завдяки лінійному навчанню його беруть як перший орієнтир, з яким порівнюють складніші моделі — так само, як OneR був базою для дерев у Лекції 7.
• Оцінка ризику й скоринг. Там, де потрібне не рішення, а ймовірність (кредитний скоринг, ймовірність відтоку клієнта, медичний ризик), імовірнісний вихід наївного Байєса цінніший за ярлик дерева.
• Відбір ознак. Умовні ймовірності $P(x_j \mid C)$ показують, які значення ознак найсильніше пов’язані з класом, — це самостійний інструмент розвідки даних.

Підсумок #

• Ймовірнісний класифікатор оцінює $P(C \mid x)$ для кожного класу, а не лише повертає ярлик; це дає впевненість, поріг за ціною помилки та скоринг.
• Теорема Байєса $P(C \mid x) = \dfrac{P(x \mid C)P(C)}{P(x)}$; для вибору класу знаменник $P(x)$ відкидають: $\hat{C} = \arg\max_C P(x \mid C)P(C)$.
• Наївне припущення про умовну незалежність ознак зводить важку спільну правдоподібність до добутку одновимірних: $P(C \mid x) \propto P(C)\prod_j P(x_j \mid C)$.
• Множники оцінюють частотами: $P(C) = N_C/N$, $P(x_j = v \mid C) = N_{C,\,j=v}/N_C$; клас обирають за argmax, а ймовірності дістають нормуванням на суму оцінок усіх класів.
• На вибірці «Спортивний канал» наївний Байєс дав апостеріорні $P(\text{Так})$ по рядках $1.00;\,0.33;\,0.00;\,0.00;\,0.75;\,1.00;\,0.53;\,0.87;\,0.00;\,0.33$ і безпомилково класифікував усі $10$ об’єктів — той самий результат, що й дерево ID3 з Лекції 7, але з оцінкою впевненості.
• Проблеми: залежність атрибутів; нульові ймовірності (один $P(x_j \mid C) = 0$ занулює добуток) та обчислювальне переповнення; відсутні атрибути.
• Згладжування Лапласа $P(x_j = v \mid C) = \dfrac{N_{C,\,j=v} + 1}{N_C + m_j}$ усуває нулі, зберігаючи нормування (об’єкт $3$: $P(\text{Так})$ з $0.000$ стало $0.400$).
• Баєсів спам-фільтр: спамовість слова $p(w) = \dfrac{b(w)}{b(w) + g(w)}$, усереднена (чи, строго, добуткова) вага слів листа, порівняння з порогом.

Вправи #

Для розігріву #

1. Поясніть різницю між апріорною $P(C)$ та апостеріорною $P(C \mid x)$ ймовірностями класу. Який множник теореми Байєса «переводить» одну в іншу?
2. Чому при виборі класу знаменник $P(x)$ можна відкинути, а при звітуванні ймовірності — ні? Що стоїть у знаменнику після нормування?
3. Сформулюйте наївне припущення про умовну незалежність. Наведіть приклад двох ознак, для яких воно явно хибне.

Стандартні #

4. Використавши таблицю ймовірностей §8.4, класифікуйте «руками» об’єкт $7$ — (Ж, Середній, студент Так) — і переконайтесь, що $P(\text{Так} \mid x_7) \approx 0.529$.
5. Обчисліть без згладжування апостеріорну ймовірність для об’єкта $5$ — (Ч, Середній, студент Ні) — і поясніть, чому вона дорівнює рівно $0.75$.
6. Застосуйте згладжування Лапласа до всіх умовних імовірностей класу «Ні» ($N_C = 5$; $m$: Стать $2$, Дохід $3$, Студент $2$) і перевірте, що для кожної ознаки згладжені ймовірності дають у сумі $1$.
7. У спам-базі з Прикладу 8.6 оцініть спамовість листа «виграш зустріч» двома способами — усередненням ваг і добутковою формулою — і порівняйте з порогом $0.5$.

Підвищеної складності #

8. Доведіть, що згладжена оцінка $P(x_j = v \mid C) = \dfrac{N_{C,\,j=v} + 1}{N_C + m_j}$ задовольняє умову нормування $\sum_{v} P(x_j = v \mid C) = 1$ (сума за всіма $m_j$ значеннями ознаки).
9. Порівняйте наївний Байєс і дерево ID3 з Лекції 7 на вибірці «Спортивний канал»: побудуйте таблицю, де для кожного з $10$ об’єктів стоять прогноз дерева, прогноз наївного Байєса та справжній клас. Скільки разів методи не збіглися? Яку додаткову інформацію дає наївний Байєс, якої немає в дерева?
10. Покажіть, що робота з сумою логарифмів $\log P(C) + \sum_j \log P(x_j \mid C)$ дає той самий клас-переможець, що й добуток, але не переповнюється. Чому для цього обов’язкове згладжування (що станеться з $\log 0$)?

Lectures/DA-L08.md · 46.9 KB · updated 2026-08-05 09:43