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

## Огляд

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

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

> **Практичний бік.** Апостеріорні ймовірності ви обчислюватимете «руками», а
> наївний баєсів класифікатор — **програмою** в
> [Лабораторній роботі 8](../Laboratory/Laboratory8/main.md), де порівняєте його
> прогнози з деревом ID3 із Лабораторної 7.

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

| № | Стать | Дохід | Студент? | Спортивний канал? |
|:--:|:--:|:--:|:--:|:--:|
| 1 | Ч | Високий | Так | Так |
| 2 | Ж | Середній | Ні | Ні |
| 3 | Ч | Низький | Так | Ні |
| 4 | Ж | Низький | Ні | Ні |
| 5 | Ч | Середній | Ні | Так |
| 6 | Ж | Високий | Ні | Так |
| 7 | Ж | Середній | Так | Так |
| 8 | Ч | Середній | Так | Так |
| 9 | Ж | Низький | Так | Ні |
| 10 | Ж | Середній | Ні | Ні |

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

---

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

Нагадаємо задачу класифікації з [Лекції 7](DA-L07.md): за значеннями
**предикторів** (вхідних атрибутів) об'єкта передбачити значення **цільової**
категоріальної ознаки — **класу**. Дерево рішень і 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](DA-L01.md). Нагадаємо її
у формі, зручній для класифікації.

> **Теорема (Байєса).** Для класу $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). $$

![Структура наївного Байєса: вузол класу з'єднаний стрілками з умовно незалежними за класом ознаками x1..xm.](img/l08_naive_structure.png)

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

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

> **Властивість (апостеріорна ймовірність наївного Байєса).**
> $$ P(C \mid x) \;\propto\; P(C) \prod_{j=1}^{m} P(x_j \mid C), $$
> де знак $\propto$ («пропорційно») ховає сталий для всіх класів множник
> $1/P(x)$. Клас обирають за найбільшою правою частиною.

![Схема наївного Байєса: апостеріорна ймовірність пропорційна добутку апріорної ймовірності та правдоподібності.](img/l08_prior_likelihood.png)

---

## 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\}$.

| Ознака $= v$ | $N_{\text{Так},\,v}$ | $P(v \mid \text{Так})$ | $N_{\text{Ні},\,v}$ | $P(v \mid \text{Ні})$ |
|---|:--:|:--:|:--:|:--:|
| Стать $=$ Ч | 3 | $3/5 = 0.6$ | 1 | $1/5 = 0.2$ |
| Стать $=$ Ж | 2 | $2/5 = 0.4$ | 4 | $4/5 = 0.8$ |
| Дохід $=$ Високий | 2 | $2/5 = 0.4$ | 0 | $0/5 = 0.0$ |
| Дохід $=$ Середній | 3 | $3/5 = 0.6$ | 2 | $2/5 = 0.4$ |
| Дохід $=$ Низький | 0 | $0/5 = 0.0$ | 3 | $3/5 = 0.6$ |
| Студент? $=$ Так | 3 | $3/5 = 0.6$ | 2 | $2/5 = 0.4$ |
| Студент? $=$ Ні | 2 | $2/5 = 0.4$ | 3 | $3/5 = 0.6$ |

Зверніть увагу на два **нулі**: серед підписників немає жодного з низьким доходом
($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')}. $$
> Знаменник — сума **всіх** незнормованих оцінок; після ділення ймовірності всіх
> класів дають у сумі одиницю.

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

```text
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: незнормовані оцінки класів 0.108 і 0.016 та апостеріорні ймовірності після нормування 0.871 і 0.129.](img/l08_posterior_bars.png)

**Приклад 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).

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

| № | Стать | Дохід | Студент? | $P(\text{Так} \mid x)$ | Прогноз | Справжній |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| 1 | Ч | Високий | Так | $1.000$ | Так | Так |
| 2 | Ж | Середній | Ні | $0.333$ | Ні | Ні |
| 3 | Ч | Низький | Так | $0.000$ | Ні | Ні |
| 4 | Ж | Низький | Ні | $0.000$ | Ні | Ні |
| 5 | Ч | Середній | Ні | $0.750$ | Так | Так |
| 6 | Ж | Високий | Ні | $1.000$ | Так | Так |
| 7 | Ж | Середній | Так | $0.529$ | Так | Так |
| 8 | Ч | Середній | Так | $0.871$ | Так | Так |
| 9 | Ж | Низький | Так | $0.000$ | Ні | Ні |
| 10 | Ж | Середній | Ні | $0.333$ | Ні | Ні |

![Апостеріорні ймовірності підписки P(Так|x) для всіх 10 об'єктів вибірки з порогом 0.5; кольором позначено прогнозований клас.](img/l08_posterior_all.png)

Наївний Байєс правильно класифікував **усі $10$** об'єктів навчальної вибірки —
правильність (за навчальними даними) $100\,\%$. Це рівно той самий результат, що
дало **дерево ID3** з [Прикладу 7.3](DA-L07.md): обидва методи безпомилкові на цій
вибірці й **збігаються в кожному рядку**. Різниця — у виході: дерево повертає
ярлик, наївний Байєс — ще й **ступінь упевненості** (порівняйте «граничний» рядок
$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$.

![Згладжування Лапласа для P(Дохід|Так): нульова ймовірність низького доходу стає 0.125, а суми ймовірностей зберігаються.](img/l08_laplace.png)

**Приклад 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*), а ознаки об'єкта-листа — **слова**,
що в ньому трапляються. Схема така:

```text
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$
звичайних листів, а три слова трапляються так:

| Слово $w$ | Спам-листів із $w$ | Звич. листів із $w$ | $b(w)$ | $g(w)$ | $p(w) = \dfrac{b}{b+g}$ |
|---|:--:|:--:|:--:|:--:|:--:|
| «виграш» | 16 | 2 | $0.8$ | $0.1$ | $0.8/0.9 \approx 0.889$ |
| «кредит» | 12 | 4 | $0.6$ | $0.2$ | $0.6/0.8 = 0.750$ |
| «зустріч» | 2 | 14 | $0.1$ | $0.7$ | $0.1/0.8 = 0.125$ |

![Ваги слів баєсового спам-фільтра: спамовість p(w) трьох слів порівняно з порогом 0.5.](img/l08_spam.png)

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

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

![Рішення спам-фільтра за усередненою вагою слів для листів «виграш кредит» і «зустріч кредит» з порогом 0.5.](img/l08_spam_emails.png)

Усереднення ваг — **спрощена** схема зі слайдів; строгий наївний Байєс
комбінує слова не середнім, а **добутком** (краще — сумою логарифмів). Для листа
«виграш кредит» строга формула
$$ 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](DA-L07.md).
- **Оцінка ризику й скоринг.** Там, де потрібне не рішення, а **ймовірність**
  (кредитний скоринг, ймовірність відтоку клієнта, медичний ризик), імовірнісний
  вихід наївного Байєса цінніший за ярлик дерева.
- **Відбір ознак.** Умовні ймовірності $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](DA-L07.md) на вибірці
   «Спортивний канал»: побудуйте таблицю, де для кожного з $10$ об'єктів стоять
   прогноз дерева, прогноз наївного Байєса та справжній клас. Скільки разів методи
   **не збіглися**? Яку додаткову інформацію дає наївний Байєс, якої немає в дерева?
10. Покажіть, що робота з **сумою логарифмів** $\log P(C) + \sum_j \log P(x_j \mid C)$
    дає той самий клас-переможець, що й добуток, але не переповнюється. Чому для
    цього обов'язкове згладжування (що станеться з $\log 0$)?