# 2. Методичні вказівки

Цей розділ **самодостатній**: у ньому зібрано теорію наївного баєсового
класифікатора, потрібну для аудиторних задач ([3classroom.md](3classroom.md)) і
домашньої програми ([4task.md](4task.md)). Ширше ту саму теорію викладено в
[Лекції 8](../../Lectures/DA-L08.md).

## 2.1 Задача ймовірнісної класифікації

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

## 2.2 Теорема Байєса та правило класифікації

За теоремою Байєса апостеріорна ймовірність класу

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

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

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

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

Правдоподібність $P(x \mid C) = P(x_1, \dots, x_m \mid C)$ — ймовірність **цілої
комбінації** ознак — надійно оцінити частотою неможливо: комбінацій надто багато.
**Наївне припущення** вважає ознаки **умовно незалежними за класом**:

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

Звідси робоча формула методу:

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

Припущення часто хибне (ознаки бувають залежні), але для *вибору* класу
класифікатор усе одно працює на диво добре.

## 2.4 Оцінювання ймовірностей за частотами

Нехай вибірка має $N$ об'єктів, з них $N_C$ — класу $C$. Тоді

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

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

## 2.5 Класифікація та нормування

Для об'єкта $x$ обчислюють **оцінку** кожного класу $\text{score}(C) = P(C)\prod_j P(x_j \mid C)$,
обирають найбільшу, а щоб отримати **самі ймовірності** — нормують на суму оцінок
усіх класів (це і є знаменник $P(x)$ за формулою повної ймовірності):

$$ P(C \mid x) = \frac{\text{score}(C)}{\sum_{C'} \text{score}(C')}. $$

## 2.6 Проблема нульової ймовірності та згладжування Лапласа

Якщо значення ознаки **жодного разу** не трапилось у класі $C$, то
$P(x_j \mid C) = 0$ і **весь добуток занулюється** — навіть якщо решта ознак
переконливо свідчать на користь $C$. Це **проблема нульової ймовірності**
(переповнення). Її усуває **адитивне (лапласове) згладжування**:

$$ 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$). Пов'язана обчислювальна вада — **зникнення в
нуль** (underflow) добутку багатьох малих чисел; на практиці замість добутку
беруть **суму логарифмів** $\log P(C) + \sum_j \log P(x_j \mid C)$.

## 2.7 Порівняння з деревом ID3

Наївний Байєс і дерево рішень **ID3** ([Лекція 7](../../Lectures/DA-L07.md))
розв'язують ту саму задачу класифікації, але по-різному: дерево будує ієрархію
**однозначних** перевірок і повертає ярлик; наївний Байєс перемножує ймовірності
ознак і повертає ярлик **разом з упевненістю** $P(C \mid x)$. Їх зіставляють за
прогнозами на кожному об'єкті, за **точністю** (часткою правильних прогнозів) і за
**матрицею невідповідності** — таблицею, що показує, на скількох об'єктах методи
дали однакові/різні класи.

## 2.8 Демонстраційний приклад (на інших даних, ніж у задачах)

Розглянемо навчальну вибірку **«Морозиво»**: за **погодою** та **настроєм**
покупця передбачаємо, чи купить він морозиво.

| № | Погода | Настрій | Морозиво? |
|:--:|:--:|:--:|:--:|
| 1 | Спекотно | Гарний | Так |
| 2 | Спекотно | Гарний | Так |
| 3 | Спекотно | Поганий | Так |
| 4 | Прохолодно | Гарний | Так |
| 5 | Прохолодно | Поганий | Ні |
| 6 | Прохолодно | Поганий | Ні |
| 7 | Спекотно | Поганий | Ні |
| 8 | Прохолодно | Гарний | Ні |

Класи збалансовані: **4** «Так» $= \{1,2,3,4\}$ і **4** «Ні» $= \{5,6,7,8\}$, тож
$P(\text{Так}) = P(\text{Ні}) = 0.5$.

**(а) Умовні ймовірності (частоти).**

| Ознака $= v$ | $P(v \mid \text{Так})$ | $P(v \mid \text{Ні})$ |
|---|:--:|:--:|
| Погода $=$ Спекотно | $3/4 = 0.75$ | $1/4 = 0.25$ |
| Погода $=$ Прохолодно | $1/4 = 0.25$ | $3/4 = 0.75$ |
| Настрій $=$ Гарний | $3/4 = 0.75$ | $1/4 = 0.25$ |
| Настрій $=$ Поганий | $1/4 = 0.25$ | $3/4 = 0.75$ |

**(б) Класифікація об'єкта (Спекотно, Гарний настрій).**

$$ \text{score}(\text{Так}) = 0.5 \cdot 0.75 \cdot 0.75 = \tfrac{9}{32} \approx 0.281, \qquad
\text{score}(\text{Ні}) = 0.5 \cdot 0.25 \cdot 0.25 = \tfrac{1}{32} \approx 0.031. $$

Нормуємо:

$$ P(\text{Так} \mid x) = \frac{9/32}{9/32 + 1/32} = \frac{9}{10} = 0.900. $$

Прогноз — **«Так»** (купить) з упевненістю $0.9$. Симетрично для об'єкта
(Прохолодно, Поганий настрій) вийде $P(\text{Так} \mid x) = 1/10 = 0.100$, тобто
**«Ні»**.

**(в) Згладжування Лапласа (демонстрація механіки).** Хоча в цій вибірці нулів
немає, покажемо формулу. Обидві ознаки мають $m = 2$ значення, тож зі
згладжуванням

$$ P(\text{Спекотно} \mid \text{Так}) = \frac{3 + 1}{4 + 2} = \frac{4}{6} \approx 0.667, \qquad
P(\text{Прохолодно} \mid \text{Так}) = \frac{1 + 1}{4 + 2} = \frac{2}{6} \approx 0.333, $$

і сума $0.667 + 0.333 = 1$ — нормування збережено. Згладжування «підтягує»
ймовірності до середини (порівняйте $0.75 \to 0.667$), роблячи оцінки менш
категоричними.

## 2.9 Робочий контрольний список

- Спершу оцініть **апріорні** ймовірності $P(C) = N_C/N$ (або візьміть задані).
- Для кожної ознаки й кожного класу порахуйте **умовні** ймовірності
  $P(x_j = v \mid C) = N_{C,\,j=v}/N_C$; зведіть їх у таблицю.
- Оцінку класу рахуйте як **добуток** $P(C)\prod_j P(x_j \mid C)$; клас — за
  **argmax**; ймовірність — **нормуванням** на суму оцінок.
- Побачили **нуль** серед $P(x_j \mid C)$ — застосуйте **згладжування Лапласа**
  $\dfrac{\text{count} + 1}{N_C + m_j}$ (не забудьте $m_j$ у знаменнику).
- Для порівняння з **ID3** проженіть **обидва** класифікатори по тих самих
  об'єктах і зіставте прогнози з правдою (точність, матриця невідповідності).