Naivní Bayesův klasifikátor: spamový filtr, který funguje lépe, než by měl

Bayesova věta jako klasifikátor, učení počítáním slov, výpočet krok za krokem, problém nulové četnosti a Laplaceovo vyhlazení, přehnaná jistota a kalibrace, a proč naivní Bayes vyhrává, když je dat málo.

13 minut Matěj Žalmánek 2026-10-16

Série Základy AI Díl 51 z 83

Celá osnova série 83 z 83 témat hotovo

Co si odnesete

Jak naivní Bayes klasifikuje text a proč se učí jen počítáním.
Proč je potřeba vyhlazení a co způsobuje naivní předpoklad nezávislosti.
Kdy naivnímu Bayesovi věřit rozhodnutí, ale ne pravděpodobnost — a kdy porazí logistickou regresi.

Co se hodí znát předem: Podmíněná pravděpodobnost a Bayesova věta: jak změnit odhad, když se dozvíte něco nového, Logistická regrese: sigmoida, šance a křížová entropie

Koncem 90. let zaplavil e-mailové schránky spam a ručně psaná pravidla („zahoď vše, kde je VIAGRA“) přestávala stačit. V roce 2002 popsal Paul Graham v eseji A Plan for Spam filtr, který se pravidla naučí sám ze zpráv, které uživatel označil — a zachytil přes 99 % spamu. Za filtrem stála Bayesova věta a jedno odvážné zjednodušení. Tomu zjednodušení se říká „naivní“, protože skoro nikdy neplatí. A přesto model funguje překvapivě dobře. V tomhle dílu si ho postavíme a ukážeme, proč funguje — i kde lže.

Navazuje na díly Podmíněná pravděpodobnost a Bayesova věta a Logistická regrese.

1. Bayesova věta jako klasifikátor

Definice — naivní Bayesův klasifikátor

Nechť 𝒞 je konečná množina tříd, C náhodná veličina s hodnotami v 𝒞 (třída) a X₁, …, X_n diskrétní náhodné veličiny (příznaky) na témž pravděpodobnostním prostoru, P(C = c) > 0 pro každé c ∈ 𝒞. Zkráceně píšeme P(c) = P(C = c), P(x_i | c) = P(X_i = x_i | C = c) a podobně. Pro pozorované hodnoty x₁, …, x_n s P(x₁, …, x_n) > 0 dává Bayesova věta (díl Podmíněná pravděpodobnost)

P(c | x₁, …, x_n) = P(c) · P(x₁, …, x_n | c)/P(x₁, …, x_n).

Naivní předpoklad: příznaky jsou podmíněně nezávislé při dané třídě (definice níže), tj. pro každé c ∈ 𝒞 a všechny hodnoty x₁, …, x_n

P(x₁, …, x_n | c) = ∏_i=1ⁿ P(x_i | c).

Naivní Bayesův klasifikátor přiřadí pozorování (x₁, …, x_n) třídu

ĉ = argmax_{c ∈ 𝒞} P(c) ∏_i=1ⁿ P(x_i | c).

Jmenovatel P(x₁, …, x_n) na c nezávisí, proto je ĉ právě třída s největší aposteriorní pravděpodobností; píšeme P(c | x) ∝ P(c) ∏_i P(x_i | c), kde ∝ znamená „rovná se až na kladný násobek, který nezávisí na c“.

Laicky řečeno

Každé slovo zprávy je malý svědek. „Zdarma“ svědčí pro spam, „porada“ pro normální poštu. Naivní Bayes vyslechne svědky jednoho po druhém a jejich výpovědi vynásobí — jako by se mezi sebou nikdy nedomlouvali. To je ta naivita: slova „klikněte“, „na“ a „odkaz“ chodí skoro vždycky spolu, ale model je počítá jako tři nezávislé důkazy.

P(c | x₁, …, x_n) = P(c) · ∏_i=1ⁿ P(x_i | c)/P(x₁, …, x_n)

P(c | x₁, …, x_n): aposteriorní pravděpodobnost — jak pravděpodobná je třída c (spam), když už známe slova zprávy; to jediné nás zajímá
P(c): apriorní pravděpodobnost — jak častá je třída, než zprávu vůbec otevřeme; když chodí devět spamů z deseti, potřebuje normální zpráva silnější důkazy
∏ P(x_i | c): věrohodnost — jak dobře třída „vysvětluje“ pozorovaná slova; součin místo jedné společné pravděpodobnosti je právě ten naivní předpoklad
P(x₁, …, x_n): pravděpodobnost zprávy samé — pro všechny třídy stejná, takže pořadí tříd nemění; při rozhodování se vynechá (proto „∝“ v definici) a dopočte se jen jako součet čitatelů přes třídy, aby výsledky daly dohromady 1

Aposteriorní = apriorní × věrohodnost, vydělené tak, aby se pravděpodobnosti sečetly na jedničku.

Proč takové zjednodušení? Bez něj bychom potřebovali znát pravděpodobnost každé možné kombinace slov. Se slovníkem o 10 000 slovech je kombinací víc než atomů ve vesmíru. S naivním předpokladem stačí pro každé slovo a každou třídu jedno číslo — dají se spočítat z pár desítek zpráv.

Definice — podmíněná nezávislost

Nechť X, Y, C jsou diskrétní náhodné veličiny na témž pravděpodobnostním prostoru. X a Y jsou podmíněně nezávislé při daném C, právě když pro všechny hodnoty x, y, c s P(C = c) > 0 platí

P(X = x, Y = y | C = c) = P(X = x | C = c) · P(Y = y | C = c).

Ekvivalentně: pro všechna x, y, c s P(Y = y, C = c) > 0 platí P(X = x | Y = y, C = c) = P(X = x | C = c) — když třídu známe, druhé slovo o prvním nic dalšího neprozradí.

Obecněji jsou X₁, …, X_n (vzájemně) podmíněně nezávislé při daném C, právě když pro všechny hodnoty x₁, …, x_n, c s P(C = c) > 0 platí P(X₁ = x₁, …, X_n = x_n | C = c) = ∏_i=1ⁿ P(X_i = x_i | C = c). To naivní Bayes předpokládá pro všechna slova zprávy zároveň (z toho plyne podmíněná nezávislost každé dvojice i každé podmnožiny).

Podmíněná nezávislost není totéž co nezávislost. Slova „výhra“ a „zdarma“ spolu bez znalosti třídy souvisí (obě ukazují na spam, takže chodí spolu); naivní předpoklad tvrdí jen to, že uvnitř spamu už spolu nesouvisí.

Příklad — kolik čísel model potřebuje

Zjednodušme zprávu na to, které z 10 000 slov slovníku v ní jsou a které ne. Možných zpráv je 2^{10 000} ≈ 10^{3 010} (10 000 · log₁₀ 2 ≈ 3 010,3). Úplný model by pro každou třídu potřeboval pravděpodobnost každé z nich, tedy 2 · (2^{10 000} − 1) čísel; atomů ve viditelném vesmíru je řádově 10⁸⁰. S naivním předpokladem stačí pro každou třídu a každé slovo jedno P(slovo | třída): 2 · 10 000 = 20 000 čísel, plus jedno pro apriorní P(spam).

2. Učení je počítání

Napsali jsme si 24 trénovacích zpráv: 12 spamových a 12 normálních.

Všech 24 trénovacích zpráv

Spam:

Vyhrajte nový iPhone zdarma, stačí kliknout na odkaz
Gratulujeme, vyhráli jste 10 000 Kč, klikněte a získejte výhru
Zdarma půjčka bez registru, peníze ihned na účet
Exkluzivní nabídka jen dnes: sleva 90 % na hodinky
Klikněte zde a získejte bonus zdarma
Vaše výhra čeká, potvrďte údaje na odkazu
Zhubněte 10 kg za týden, zázračné tablety zdarma
Peníze z domova bez práce, klikněte na odkaz
Poslední šance: výhra 50 000 Kč čeká jen na vás
Levné léky bez receptu, doprava zdarma
Váš účet byl zablokován, ihned potvrďte údaje na odkazu
Získejte exkluzivní slevu, nabídka platí jen dnes

Normální:

Ahoj, zítra v deset máme poradu, přineseš ty podklady
Posílám fotky z výletu, byl to krásný den
Můžeš prosím koupit cestou domů chleba a mléko
Schůzka se přesouvá na čtvrtek, dej vědět, jestli ti to vyhovuje
Díky za včerejšek, večeře byla výborná
V příloze posílám fakturu za září, splatnost je za týden
Zítra nepřijdu, jsem nemocný, doktor mi dal neschopenku
Nezapomeň, že v sobotu má babička narozeniny
Ahoj, máš čas v pátek na kafe
Posílám podklady k poradě, kouknu na ně ještě dnes večer
Vlak má zpoždění, budu doma až v osm
Děkuji za rychlou odpověď, objednávku potvrzuji

Definice — multinomický naivní Bayes a Laplaceovo vyhlazení

Nechť V je slovník — konečná neprázdná množina slov, |V| počet jejích prvků — a 𝒞 konečná množina tříd. Trénovací data jsou zprávy, každá je posloupnost slov z V a má třídu z 𝒞. Pro s ∈ V a c ∈ 𝒞 označme

počet(s, c) — počet výskytů slova s ve všech trénovacích zprávách třídy c;
N_c = ∑_{s ∈ V} počet(s, c) — celkový počet slov v trénovacích zprávách třídy c;
M_c — počet trénovacích zpráv třídy c a M = ∑_{c ∈ 𝒞} M_c počet všech trénovacích zpráv.

V multinomickém naivním Bayesovi je zpráva x posloupnost slov (s₁, …, s_m), s_j ∈ V, a v rámci třídy c se každé slovo táhne nezávisle z rozdělení P(· | c) na V, takže P(x | c) = ∏_j=1^m P(s_j | c). Bez vyhlazení se P(s | c) odhaduje relativní četností počet(s, c)/N_c. S Laplaceovým vyhlazením se ke každému počtu přičte 1:

P(s | c) = počet(s, c) + 1/N_c + |V|, s ∈ V.

Apriorní pravděpodobnost se odhaduje podílem zpráv, P(c) = M_c/M.

Laicky řečeno

Učení naivního Bayese je jedno projití dat a sčítání: kolikrát se které slovo objevilo ve spamu a kolikrát v normální poště. Žádný gradientní sestup, žádné iterace. Proto je tak rychlý — a proto ho šlo v roce 2002 pustit v každém poštovním programu. Naše spamové zprávy mají dohromady 95 slov, normální 98 a ve slovníku je 136 různých slov.

P(s | c) = počet(s, c) + 1/N_c + |V|

P(s | c): odhad, jak pravděpodobné je, že náhodně vybrané slovo zprávy třídy c bude právě s
počet(s, c): kolikrát se slovo objevilo v trénovacích zprávách třídy — jediná informace, kterou z dat bereme
+ 1: „pseudopočet“ — jako bychom každé slovo slovníku viděli v každé třídě o jednou víc; žádná pravděpodobnost pak nevyjde nulová
N_c: počet všech slov ve zprávách třídy (u nás 95 a 98) — dělením z počtu uděláme podíl, takže delší zprávy jedné třídy nezvýhodní její slova
+ |V|: vyrovná přičtené jedničky: přičetli jsme 1 každému z |V| = 136 slov, jmenovatel musí vzrůst o 136, aby se pravděpodobnosti přes slovník dál sčítaly na 1

Relativní četnost slova ve třídě, ke které jsme každému slovu přidali jeden vymyšlený výskyt.

Příklad — „zdarma“ a „klikněte“

„Zdarma“ je ve spamových zprávách 5× a v normálních ani jednou, „klikněte“ 3× a 0×. S N_spam = 95, N_normální = 98 a |V| = 136:

P(zdarma | spam) = 5 + 1/95 + 136 = 6/231 ≈ 0,0260, P(zdarma | normální) = 0 + 1/98 + 136 = 1/234 ≈ 0,0043.

P(klikněte | spam) = 3 + 1/95 + 136 = 4/231 ≈ 0,0173, P(klikněte | normální) = 0 + 1/98 + 136 = 1/234 ≈ 0,0043 (barvy podle vzorce výše).

Poměry 6/231/1/234 = 6 · 234/231 ≈ 6,08 a 4 · 234/231 ≈ 4,05 jsou ty, které uvidíme v tabulce níže. Bez vyhlazení by byl P(zdarma | spam) = 5/95 ≈ 0,0526 a P(zdarma | normální) = 0 — poměr nekonečný.

Věta — proč zrovna relativní četnost

Nechť V je konečný slovník, N ∈ ℕ, N ≥ 1, a pro každé s ∈ V nechť n_s ∈ {0, 1, 2, …} je počet výskytů slova s mezi N slovy třídy, ∑_{s ∈ V} n_s = N. Uvažujme model, který každé z N slov táhne nezávisle z V s pravděpodobnostmi θ = (θ_s)_{s ∈ V}, kde θ_s ≥ 0 a ∑_s θ_s = 1. Věrohodnost dat je

L(θ) = ∏_{s ∈ V} θ_s^n_s.

Pak L nabývá maxima pro θ_s = n_s/N, s ∈ V — odhad maximální věrohodnosti je relativní četnost.

Důkaz. Slova s n_s = 0 do L nepřispívají, a jakákoli kladná θ_s by jen ubrala ostatním, proto u nich θ_s = 0 = 0/N. Pro zbylá slova maximalizujeme ln L = ∑_s n_s ln θ_s za podmínky ∑_s θ_s = 1. Lagrangeova funkce ∑ n_s ln θ_s − λ(∑ θ_s − 1) má derivaci podle θ_s rovnou n_s/θ_s − λ = 0, takže θ_s = n_s/λ; z podmínky λ = ∑ n_s = N. Funkce ln L je konkávní, jde tedy o maximum. ∎

Laplaceovo vyhlazení dostaneme, když na θ položíme rovnoměrné apriorní rozdělení (Dirichletovo s parametry 1) a vezmeme střední hodnotu aposteriorního rozdělení: n_s + 1/N + |V|. Stejný vzorec je i odhad MAP při Dirichletově rozdělení s parametry 2.

3. Výpočet krok za krokem

Přijde zpráva „Klikněte na odkaz a potvrďte výhru zdarma“. Pro každé slovo spočteme, kolikrát je pravděpodobnější ve spamu než v normální zprávě:

Slovo	P(slovo \| spam)	P(slovo \| normální)	poměr
klikněte	0,0173	0,0043	4,05×
na	0,0346	0,0171	2,03×
odkaz	0,0130	0,0043	3,04×
a	0,0130	0,0085	1,52×
potvrďte	0,0130	0,0043	3,04×
výhru	0,0087	0,0043	2,03×
zdarma	0,0260	0,0043	6,08×

Všech sedm slov svědčí pro spam, nejsilněji „zdarma“ (6,08×) a „klikněte“ (4,05×). Apriorní pravděpodobnosti jsou stejné (12 a 12 zpráv), takže výsledné šance jsou prostě součin poměrů. V praxi se nenásobí pravděpodobnosti, ale sčítají jejich logaritmy — součin stovek malých čísel by v počítači podtekl na nulu. Výsledek: P(spam | zpráva) = 99,93 %.

s = ln P(spam)/P(normální) + ∑_i ln P(x_i | spam)/P(x_i | normální),
P(spam | x) = 1/1 + e^−s

s: logaritmus šancí spam : normální — kladný znamená spam, záporný normální zprávu; rozhoduje jen jeho znaménko
ln P(spam)/P(normální): výchozí náklon ještě před přečtením zprávy; u nás 12 : 12, takže ln 1 = 0 a nenaklání nikam
∑ ln P(x_i | spam)/P(x_i | normální): příspěvky slov — logaritmus změní součin poměrů na součet, takže každé slovo jen přičte své „body“ (kladné pro spam, záporné pro normální) a nic nepodteče
1/1 + e^−s: sigmoida převede šance zpátky na pravděpodobnost; dělá totéž co jmenovatel P(x) v Bayesově větě — srovná obě třídy tak, aby daly dohromady 1

Stejná Bayesova věta, jen pro poměr dvou tříd a v logaritmech; P(x) se v poměru zkrátí.

Příklad — první zpráva v logaritmech

Přirozené logaritmy poměrů z tabulky (pro slova v pořadí „klikněte“, „na“, „odkaz“, „a“, „potvrďte“, „výhru“, „zdarma“):

1,399 + 0,706 + 1,112 + 0,418 + 1,112 + 0,706 + 1,805 ≈ 7,257

(součet nezaokrouhlených hodnot; barvy podle vzorce výše). Apriorní člen je ln 12/12 = 0, takže s ≈ 7,257. Šance jsou e^7,257 ≈ 1 419 : 1 a P(spam) = 1/1 + e^−7,257 ≈ 99,93 %.

Proč logaritmy: samotné součty ln P(spam) + ∑ ln P(x_i | spam) = -29,544 a pro normální třídu -36,801 odpovídají pravděpodobnostem kolem 10⁻¹³ a 10⁻¹⁶, a to má zpráva jen sedm slov. Dlouhý e-mail s 200 slovy po P ≈ 0,004 by dal 0,004²⁰⁰ ≈ 10⁻⁴⁸⁰, což je pod nejmenším kladným číslem typu double (asi 4,9 · 10⁻³²⁴) — počítač vrátí 0. Jeho logaritmus 200 · ln 0,004 ≈ −1 104,3 je naopak úplně obyčejné číslo.

Druhá zpráva: „Posílám odkaz na fotky, potvrďte prosím, jestli dorazily“. Slova „odkaz“ a „potvrďte“ svědčí pro spam (3,04×), méně i „na“ (2,03×), ale „posílám“ (0,25×), „fotky“, „prosím“ a „jestli“ (každé 0,51×) pro normální zprávu. Slovo „dorazily“ model nikdy neviděl, a tak ho vynechá. Výsledek: P(spam) = 38,1 % — normální zpráva.

Celý model — učení i klasifikace — v pseudokódu:

# učení: jedno projití dat
for c in {spam, normální}:
    apriorní[c] = (počet zpráv třídy c) / (počet všech zpráv)
    for každé slovo s ve zprávách třídy c:
        počet[c][s] += 1
        N[c] += 1
V = množina všech slov ze všech trénovacích zpráv

# klasifikace zprávy x
for c in {spam, normální}:
    skóre[c] = ln apriorní[c]
    for každé slovo s ve zprávě x:
        if s not in V: continue          # neviděné slovo vynecháme
        skóre[c] += ln((počet[c][s] + 1) / (N[c] + |V|))
s = skóre[spam] − skóre[normální]
return P(spam | x) = 1 / (1 + e^(−s))

4. Problém nulové četnosti

Proč to přičítání jedničky? Zkusme ho vynechat. Slovo „klikněte“ se v normálních trénovacích zprávách neobjevilo ani jednou, takže P(„klikněte“ | normální) = 0. Celý součin pro normální třídu je pak nula, ať jsou ostatní slova jakákoli: první zpráva je spam se stoprocentní jistotou.

Laicky řečeno

Jeden svědek, který řekne „tohle jsem v normální poště nikdy neviděl“, přehlasuje všechny ostatní. U druhé zprávy je to ještě horší: „posílám“ ve spamu nebylo nikdy a „odkaz“ v normální poště nikdy, takže obě třídy vyjdou nulové a P(spam) = 0/0 — model neumí odpovědět vůbec. Přičtení jedničky každému slovu říká: „co jsme neviděli, není nemožné, jen vzácné.“ Je to stejný nápad jako bayesovský odhad MAP z dílu Statistika a odhady parametrů.

5. Naivita: správná rozhodnutí, přehnaná jistota

Co se stane, když stejný důkaz započítáme víckrát? Napíšeme druhou zprávu tak, že každé slovo zopakujeme dvakrát, potom třikrát. Žádná nová informace nepřibyla — ale naivní Bayes počítá každé opakování jako nezávislého svědka.

Každé slovo napsané	1×	2×	3×
P(spam), druhá zpráva	38,1 %	27,5 %	18,9 %
P(spam), první zpráva	99,93 %	99,99995 %	99,99999996 %

Rozhodnutí se nezmění — druhá zpráva zůstane normální, první spamem — ale jistota roste bez důvodu. Skutečné zprávy jsou plné závislých slov („klikněte na odkaz“, „bez registru“), a tak naivní Bayes stejný důkaz započítává pořád znovu. Pedro Domingos a Michael Pazzani v roce 1997 ukázali, proč to často nevadí: pro správnou klasifikaci stačí, aby správná třída vyšla největší, ne aby pravděpodobnosti byly přesné. Přehnaná jistota posune obě třídy, ale pořadí obvykle nezmění.

Věta — zopakování slov násobí logaritmus šancí

Nechť x = (x₁, …, x_m) je zpráva ze slov slovníku V (neviděná slova jsou vynechaná), P(· | spam) a P(· | normální) jsou vyhlazené pravděpodobnosti multinomického modelu (všechny kladné) a k ∈ ℕ, k ≥ 1. Nechť x^(k) je zpráva, ve které je každé slovo x_i napsané k-krát, a s_k její logaritmus šancí podle vzorce výše. Pak

s_k = ln P(spam)/P(normální) + k · ∑_i=1^m ln P(x_i | spam)/P(x_i | normální).

Důkaz. Zpráva x^(k) obsahuje každé slovo x_i k-krát, takže se každý člen součtu ve vzorci pro s objeví k-krát, kdežto apriorní člen na zprávě nezávisí a je tam jen jednou. ∎

U nás je apriorní člen 0, takže s_k = k · s₁: znaménko (rozhodnutí) zůstane, velikost (jistota) roste bez omezení. Pro druhou zprávu je s₁ ≈ −0,485, tedy (barvy podle vzorce výše)

k = 2: s ≈ −0,970, P(spam) = 1/1 + e^0,970 ≈ 27,5 %,
k = 3: s ≈ −1,455, P(spam) = 1/1 + e^1,455 ≈ 18,9 %.

Pro první zprávu (s₁ ≈ 7,257) dává k = 2 hodnotu s ≈ 14,515 a P(spam) ≈ 1 − 5,0 · 10⁻⁷ = 99,99995 %. Totéž se děje se skutečně závislými slovy: dvě slova, která chodí vždy spolu, nesou informaci jednoho, ale model jejich příspěvek přičte dvakrát.

6. Kdy mu nevěřit: kalibrace

Na pár ručně psaných zprávách se nic změřit nedá, proto si zprávy vygenerujeme. Každá se skládá ze dvou až pěti frází jako „klikněte na odkaz“ nebo „posílám podklady“; některé fráze jsou společné oběma třídám a část frází je „z cizí třídy“, aby úloha nebyla triviální. Slova uvnitř frází jsou silně závislá — přesně to, co naivní Bayes neumí.

Definice — kalibrace

Nechť (X, Y) je náhodný příklad se třídou Y ∈ {0, 1} (1 = pozitivní, u nás spam) a nechť klasifikátor každému vstupu x přiřadí předpověď p̂(x) ∈ [0, 1] pravděpodobnosti, že Y = 1. Klasifikátor je kalibrovaný, právě když pro každé p ∈ [0, 1], které předpovídá s kladnou pravděpodobností, platí

P(Y = 1 | p̂(X) = p) = p,

tj. mezi příklady, kterým přisoudí pravděpodobnost p, je podíl skutečně pozitivních p. Na konečných datech (x₁, y₁), …, (x_n, y_n) se to ověřuje kalibračním grafem:

interval [0, 1] se rozdělí na koše — disjunktní intervaly B₁, …, B_m;
pro každý koš j se vezmou indexy I_j = {i : p̂(x_i) ∈ B_j} a pro neprázdné I_j se spočte průměrná předpověď 1/|I_j| ∑_{i ∈ I_j} p̂(x_i) a skutečný podíl pozitivních 1/|I_j| ∑_{i ∈ I_j} y_i;
každý koš je bod (průměrná předpověď, skutečný podíl).

Body dokonale kalibrovaného modelu leží (až na náhodné kolísání) na diagonále.

Laicky řečeno

Když předpověď počasí řekne „70 % déšť“, mělo by pršet asi v sedmi dnech z deseti takových. Když prší v pěti, předpověď je přehnaně sebejistá. Kalibrace neměří, jestli model trefuje, ale jestli jeho jistota odpovídá skutečnosti.

Kalibrace na 4 000 generovaných zprávách (modely naučené na 512)

Naivní Bayes je přehnaně sebejistý na obou koncích. Když tvrdí „spam s jistotou nad 95 %“ (průměrně 98,9 %), je to spam jen v 85,1 % případů. Když tvrdí „pod 5 %“ (průměrně 0,9 %), je spamem 6,9 % zpráv. Logistická regrese, která váhy slov učí společně a závislosti tak bere v úvahu, leží skoro na diagonále: její nejjistější koš má předpověď 97,6 % a skutečnost 96,5 %. Pokud tedy pravděpodobnost z naivního Bayese chcete použít jako pravděpodobnost — třeba k výpočtu očekávané ztráty — musíte ji nejdřív překalibrovat.

Definice — Plattova překalibrace

Nechť původní klasifikátor dává pro vstup x logaritmus šancí s(x) ∈ ℝ a nechť (x₁, y₁), …, (x_m, y_m), y_i ∈ {0, 1}, je kalibrační množina — data, která model při učení neviděl; s_i = s(x_i). Plattova překalibrace nahradí předpověď modelu funkcí

p′(x) = σ(a · s(x) + b),

kde σ je sigmoida a parametry a, b ∈ ℝ minimalizují křížovou entropii na kalibrační množině,

(a, b) = argmin_{a, b} −1/m ∑_i=1^m [y_i ln σ(as_i + b) + (1 − y_i) ln(1 − σ(as_i + b))].

Je to tedy logistická regrese s jediným vstupem s. Postup navrhl John Platt (1999) pro skóre metody SVM; funguje pro jakýkoli model, jehož skóre je správně seřazené, jen špatně škálované.

p′ = σ( a · s + b )

p′: překalibrovaná pravděpodobnost spamu — to, co chceme, aby „80 %“ znamenalo spam v osmi případech z deseti
σ: sigmoida σ(z) = 1/1 + e^−z —výsledek musí zůstat mezi 0 a 1 a pro a = 1, b = 0 vrátí přesně původní předpověď naivního Bayese
a: „ztlumení“ — přehnaně sebejistý model má logaritmy šancí příliš velké; a < 1 je stáhne k nule, a protože a > 0, pořadí zpráv (a tedy ani to, která je spamovější) se nezmění
s: logaritmus šancí podle naivního Bayese (oranžová křivka v grafu) — veškerá informace o zprávě, kterou máme
+ b: posun — opraví systematický náklon k jedné třídě, např. když se podíl spamu v provozu liší od trénovacích dat

Na 1 000 dalších generovaných zprávách vyjde a ≈ 0,38 a b ≈ -0,33. Logaritmy šancí naivního Bayese jsou tedy zhruba 2,6× větší, než by měly být — sedí to s tím, že slova u nás chodí ve frázích po dvou až třech a model je počítá jako samostatné svědky. Zpráva, které naivní Bayes přisoudí 99 % (s = ln 99 ≈ 4,595), dostane po překalibraci σ(0,379 · 4,595 − 0,326) ≈ 80,5 % (barvy podle vzorce výše). Na 4 000 testovacích zprávách se nejjistější koš (nad 95 %) změní z předpovědi 98,9 % a skutečnosti 85,1 % na 97,2 % a 98,4 %, nejnižší (pod 5 %) z 0,9 % a 6,9 % na 2,6 % a 2,3 %. Do košů „pod 5 %“ a „nad 95 %“ ale teď padne méně zpráv (519 a 124 místo 1464 a 879) — model přestal být jistý tam, kde k tomu neměl důvod.

7. Proč ho přesto používat: málo dat

Andrew Ng a Michael Jordan v roce 2002 porovnali naivního Bayese s logistickou regresí a ukázali, že naivní Bayes se k nejlepší přesnosti, které je schopný, přiblíží s mnohem menším počtem trénovacích příkladů. Logistická regrese pak má nakonec často přesnost vyšší, ale potřebuje k ní víc dat. Na našich generovaných zprávách:

Přesnost podle počtu trénovacích zpráv (průměr z 20 opakování) naivní Bayes logistická regrese

Se 32 zprávami má naivní Bayes 74,0 % a logistická regrese 71,6 %; se 128 zprávami 78,9 % proti 77,3 %. U 256 zpráv jsou skoro stejně (79,6 % a 79,5 %) a u 512 už vede logistická regrese, 80,9 % proti 80,2 %. Naivní předpoklad je silné omezení: model se nemusí učit nic o tom, jak slova spolupracují, takže vystačí s málem dat — ale ani se to nikdy nenaučí.

Definice — generativní a diskriminativní model

Nechť X je náhodný vektor příznaků a C náhodná třída s hodnotami v konečné množině 𝒞.

Generativní model popisuje, jak data vznikají: odhaduje P(c) a P(x | c) pro všechna c ∈ 𝒞 (tím i společné rozdělení P(x, c) = P(c) P(x | c)) a aposteriorní pravděpodobnost dopočítá Bayesovou větou P(c | x) = P(c) P(x | c)/∑_{c′ ∈ 𝒞} P(c′) P(x | c′).
Diskriminativní model odhaduje přímo P(c | x) jako funkci x (nebo jen rozhodovací pravidlo, tj. hranici mezi třídami) a o rozdělení x nepředpokládá nic.

Naivní Bayes je generativní, logistická regrese diskriminativní.

Překvapivé je, že oba modely mají stejný tvar. Když v logaritmu šancí sečteme stejná slova dohromady (n_s = kolikrát je slovo s ve zprávě), dostaneme:

s(x) = w₀ + ∑_{s ∈ V} n_s · w_s

s(x): logaritmus šancí spam : normální; přes sigmoidu dává P(spam | x) — přesně jako u logistické regrese
w₀: práh: u naivního Bayese ln P(spam)/P(normální), u logistické regrese naučený posun
n_s: příznak — počet výskytů slova ve zprávě; oba modely vidí zprávu jako „pytel slov“ a pořadí slov je jim jedno
w_s: váha slova: naivní Bayes ji spočítá z četností, každou zvlášť, jako ln P(s | spam)/P(s | normální); logistická regrese ji hledá gradientním sestupem všechny najednou, takže si dvě slova z jedné fráze mohou váhu rozdělit

Naivní Bayes je lineární klasifikátor — liší se od logistické regrese jen tím, jak si váhy najde.

Odtud i výsledek Nga a Jordana: když má zpráva d možných příznaků, naivní Bayes se ke své nejlepší přesnosti dostane už s počtem příkladů řádu log d (každou váhu odhaduje zvlášť z prostých četností), logistická regrese obecně potřebuje řádově d příkladů — zato může dojít k lepší hranici, protože ji neomezuje předpoklad nezávislosti.

Proto naivní Bayes dodnes slouží jako první model, se kterým se cokoli porovnává: učí se okamžitě, běží na čemkoli, zvládne milion slov ve slovníku a dá se mu rozumět — u každého slova vidíte, kolikrát posouvá šance. Nasazuje se na klasifikaci textů, třídění zákaznických dotazů nebo jako rychlý filtr před dražším modelem.

8. Shrnutí

Naivní Bayes počítá P(třída) · ∏ P(slovo | třída) a předpokládá, že slova jsou v rámci třídy nezávislá.
Učení je jen počítání slov; zprávu s „klikněte na odkaz … zdarma“ označil za spam s pravděpodobností 99,93 %.
Bez Laplaceova vyhlazení rozhodne jediné neviděné slovo — nebo model neodpoví vůbec (0/0).
Zdvojením slov se rozhodnutí nemění, ale jistota roste; na generovaných zprávách „98,9 %“ znamenalo ve skutečnosti 85,1 %.
S málo daty je lepší než logistická regrese (74,0 % proti 71,6 % na 32 zprávách), s hodně daty ho logistická regrese předežene.

Chcete si to osahat? Nechte AI agenta postavit naivního Bayese na vlastní poště — exportujte složku spamu a složku doručené pošty — a nechte si vypsat deset slov, která nejvíc posouvají šance na spam.

Máte na to jiný názor? Napište na support@coden-app.com.

Naivní Bayesův klasifikátor: spamový filtr, který funguje lépe, než by měl

1. Bayesova věta jako klasifikátor

2. Učení je počítání

3. Výpočet krok za krokem

4. Problém nulové četnosti

5. Naivita: správná rozhodnutí, přehnaná jistota

6. Kdy mu nevěřit: kalibrace

7. Proč ho přesto používat: málo dat

8. Shrnutí

Agent na vašem počítači, ovládaný z telefonu