Bayesova klasifikace

Test na vzácnou nemoc má devadesátidevítiprocentní spolehlivost a tobě vyšel pozitivní. Kolik je pravděpodobnost, že jsi nemocný?

Většina lidí řekne 99 %. Když nemoc postihuje jednoho z deseti tisíc, je správná odpověď necelé jedno procento. Rozdíl mezi těmi dvěma čísly je celý obsah téhle stránky a jmenuje se apriorní pravděpodobnost.

Bayesův klasifikátor je jediný klasifikátor v téhle wiki, který má dokazatelně minimální chybu, pokud znáš správná rozdělení. Zbytek téhle stránky je o tom, proč je nikdy neznáš a co se s tím dá dělat.

Předpokládá to klasifikaci a rozpoznávání, zejména diskriminační funkce a zápis arg max. Základní pravděpodobnost stačí na úrovni „co je podmíněná pravděpodobnost", nic víc.

K čemu to je

Cílem je klasifikace v situacích, kdy se třídy překrývají. To je normální stav věcí - dva různé objekty můžou mít stejné příznaky a žádná hranice je od sebe neoddělí bezchybně.

Minimální vzdálenost ani perceptron s tím neumí nic udělat. Nakreslí hranici a hotovo. Bayesův přístup místo hranice počítá pravděpodobnost každé třídy a vybere nejpravděpodobnější - a tím zároveň řekne, jak si je jistý.

Dvě věci, které musíš znát

Apriorní pravděpodobnost P(ωr) je předpoklad o výskytu třídy před pozorováním dat. Kolik procent klientů banky dostane úvěr. Kolik procent e-mailů je spam. Kolik procent lidí má tu nemoc.

Podmíněná hustota p(x|ωr) je rozložení dat uvnitř třídy, anglicky likelihood. Jak vypadají příznaky u lidí, kteří tu nemoc mají.

Rozdíl mezi p(x|ω) a P(ω|x) je to jediné, co musíš na téhle stránce pochopit. První říká „jak vypadají data, když je to spam". Druhá říká „jaká je šance, že je to spam, když data vypadají takhle". Prohození těch dvou je klasický omyl a je to přesně ta chyba, kterou lidi udělají u testu na vzácnou nemoc.

Bayesův vzorec

P(ωr|x) = p(x|ωr) · P(ωr) / p(x)

Slovy: aposteriorní pravděpodobnost je likelihood krát apriorní, děleno normalizací.

Jmenovatel je normalizační konstanta, které se říká evidence:

p(x) = Σ p(x|ωi) · P(ωi)     přes všechna i = 1..R

Rozhodovací pravidlo se pak jmenuje MAP (maximum a posteriori):

ω* = arg max [ p(x|ωr) · P(ωr) ]
     r=1..R

Všimni si, že p(x) ve vzorci pro ω* chybí, a je to správně. Je stejné pro všechny třídy, takže na arg max nemá vliv. Počítat ho musíš jen tehdy, když chceš skutečnou pravděpodobnost a ne jen rozhodnutí - třeba když chceš říct „spam s pravděpodobností 0,97".

Spočítej si to: rozhodování o úvěru

Modelový příklad. Apriorní pravděpodobnosti:

P(PUJ) = 0,667      úvěr poskytnout
P(NEP) = 0,333      úvěr neposkytnout

Podmíněné hustoty pro příznak „vysoký zůstatek":

p(x_vys | PUJ) = 0,91
p(x_vys | NEP) = 0,12

Výpočet:

P(PUJ) · p(x_vys|PUJ) = 0,667 · 0,91 ≈ 0,607
P(NEP) · p(x_vys|NEP) = 0,333 · 0,12 ≈ 0,040

0,607 > 0,040, tedy ω* = PUJ - úvěr poskytnout.

Zkus si na tom, co apriorní pravděpodobnost dělá. Kdyby byly obě třídy stejně časté (0,5 a 0,5), poměr by byl 0,455 proti 0,060 - tedy pořád ve prospěch úvěru, ale těsněji. Apriorní pravděpodobnost rozhoduje hlavně tam, kde jsou likelihoody blízko sebe, a přesně to je případ vzácné nemoci z úvodu.

Naivní Bayes

Až sem to bylo hezké, ale je tu problém. Pro odhad p(x|ω) u vektoru s n příznaky bys potřeboval sdružené rozdělení všech n proměnných. U dvaceti binárních příznaků to je milion hodnot na každou třídu a ty je z dat nikdy neodhadneš.

Naivní Bayesův klasifikátor to řeší předpokladem, který je zjevně nepravdivý: příznaky xj jsou podmíněně nezávislé při znalosti třídy ωs.

p(x|ωs) = Π p(xj|ωs)     přes j = 1..n

Rozhodovací pravidlo:

ω* = arg max [ P(ωs) · Π p(xj|ωs) ]
       s

Z milionu hodnot se rázem stane dvacet. To je celý přínos naivního předpokladu a je to důvod, proč se používá.

A teď to zajímavé: i přes porušení předpokladu nezávislosti dosahuje NBC překvapivě vysoké přesnosti. Slova ve větě zjevně nezávislá nejsou - po „úrokové" následuje „sazby" mnohem častěji než náhoda. Klasifikátor přesto funguje.

Důvod je v tom, že NBC nepotřebuje správné pravděpodobnosti, potřebuje správné pořadí. Odhady jsou špatné, často o řády, ale chyba táhne oběma třídám stejným směrem a arg max vyjde správně.

Využití: klasifikace textu (spam filtry) a diagnostika.

Spočítej si to: úvěr podruhé

Trénovací data o dvanácti klientech. Uchazeč má středně vysoký zůstatek a je nezaměstnaný.

P(ANO) · P(STRED|ANO) · P(NE|ANO) = 0,667 · 0,25 · 0,625 = 0,1042
P(NE)  · P(STRED|NE)  · P(NE|NE)  = 0,333 · 0,5  · 0,25  = 0,0416

0,1042 > 0,0416, tedy uchazeč bude zařazen do třídy ÚVĚR (ANO).

Podívej se na to podrobněji, protože je to poučné. Jednotlivé podmíněné pravděpodobnosti mluví proti úvěru: P(STRED|ANO) = 0,25 je menší než P(STRED|NE) = 0,5. Přesto vyhraje ANO, protože apriorní pravděpodobnost 0,667 a vyšší P(NE|ANO) to přetlačí. Takhle přesně se ta metoda chová - jednotlivé indicie se násobí a rozhoduje součin, ne jednotlivosti.

Kde Bayesova klasifikace přestává platit

Nulová pravděpodobnost zabije celý součin. Když se v trénovacích datech nějaká hodnota příznaku pro danou třídu nevyskytla, je p(xj|ωs) = 0 a celý součin je nula - bez ohledu na to, jak dobře sedí ostatních devatenáct příznaků. U spamového filtru stačí jedno neznámé slovo. Řeší se to vyhlazováním (Laplaceovo, aditivní): ke každému čítači se přičte malá konstanta, typicky jedna. Tohle je věc, kterou musíš mít, ne kterou si můžeš vybrat.

Podtečení při násobení. Násobíš dvacet čísel menších než jedna a v float z toho vyjde nula. V praxi se proto počítá součet logaritmů místo součinu:

log P(ωs) + Σ log p(xj|ωs)

arg max se tím nezmění, protože logaritmus je rostoucí.

Silně závislé příznaky metodu položí. Ne že by přestala fungovat, ale začne být přehnaně sebejistá. Když do modelu dáš tentýž příznak dvakrát, jeho vliv se umocní na druhou. Odtud plyne, proč se před NBC vyplatí vybrat příznaky a odstranit duplicity.

Apriorní pravděpodobnosti z trénovacích dat nemusí platit v provozu. Když natrénuješ spamový filtr na datech, kde je 50 % spamu, a nasadíš ho tam, kde je 5 %, bude nadhodnocovat spam. Apriorní pravděpodobnosti se dají nastavit ručně a u nevyvážených úloh se to dělat má.

Bayes je optimální jen se správnými rozděleními. Věta o minimální chybě platí, když p(x|ω) a P(ω) znáš přesně. V praxi je odhaduješ z konečného vzorku, takže optimalita je teoretická meta, ne záruka.

Co se na tom nejčastěji rozbije

Co si odnést

P(ω|x) = p(x|ω)·P(ω) / p(x). Aposteriorní = likelihood krát apriorní, děleno evidencí.

p(x) se u arg max počítat nemusí. Je stejné pro všechny třídy.

Apriorní pravděpodobnost rozhoduje u vzácných tříd. Test s 99% spolehlivostí na nemoc jednoho z deseti tisíc dá pozitivní výsledek správně v necelém procentu případů.

Naivní předpoklad je nepravdivý a přesto funguje. Klasifikátor potřebuje správné pořadí, ne správná čísla.

Vyhlazování je povinné. Jedna nulová pravděpodobnost zabije celý součin.

Počítej v logaritmech. Jinak podtečeš.

Kam dál

• Příznakové metody - odkud se berou ta xj, do kterých se dosazuje
• Metriky a vyhodnocení - jak porovnat NBC s ostatními klasifikátory
• Klasifikace a rozpoznávání - kam Bayes zapadá mezi ostatní přístupy
• Nástroje pro UI - GaussianNB a MultinomialNB ve scikit-learn