Neparametrické odhady - Parzenova okna (Parzen windows)

Na předešlém cvičení jsme si vyzkoušeli odhadování pravděpodobnostních distribucí metodou maximální věrohodnosti. Předpokládali jsme, že známe analytický tvar distribuce a hledali jsme maximálně věrohodný odhad jejích parametrů. (Konkrétně: předpokládali jsme gaussovské rozdělení a odhadovali jsme parametry μ a σ.)

V mnoha reálných příkladech ale analytický tvar distribuce neznáme. V takovém případě lze použít tzv. neparametrické odhady. Na dnešním cvičení si vyzkoušíme neparametrický odhad distribuce metodou Parzenových oken.

(Termín "neparametrický odhad" může být trochu zavádějící. V podstatě jde opět o odhad parametru distribuce maximalizací věrohodnosti, pouze se používá jiný model distribuce a maximum věrohodnosti se nehledá analyticky, ale numericky.)

Formulace úlohy

Cílem úlohy je, stejně jako v předešlém cvičení, sestrojit bayesovský klasifikátor pro dvě třídy písmen. Apriorní pravděpodobnosti P(k) a hustoty pravděpodobností p(x|k) jsou neznámé. Máme ale k dispozici trénovací sadu trn_2000, ze které se tyto pravděpodobnosti pokusíme odhadnout. K odhadu distribucí p(x|k) použijeme Parzenova okna. Na základě odhadnutých distribucí sestrojíme bayesovský klasifikátor a jeho úspěšnost ověříme na nezávislé testovací sadě.

Písmena budeme klasifikovat na základě měření

x = (součet hodnot pixelů v levé polovině obrázku) - (součet hodnot pixelů v pravé polovině obrázku)

Zadání

  1. Stáhněte si a nahrajte do Matlabu soubor data_33rpz_cv05.mat.

    Soubor obsahuje proměnné:
       trn_2000 - struktura s trénovací sadou obrázků
       tst - struktura s testovací sadou obrázků
       Alphabet - abeceda


  2. Pro každý obrázek z trénovací sady trn_2000 spočtěte odezvu měření x. Výsledky uložte pro každou třídu zvlášť do vektorů X1, X2.

  3. Napište funkci y = my_parzen(x,X,sigma), která metodou Parzenových oken vypočte pro dané x odhad pravděpodobnosti p(x) na základě n naměřených hodnot X , (tj. X je vektor délky n ). Jako jádrovou funkci W(x) použijte normální rozdělení N(0, σ).

    Nápověda:     y = 1/n * Sum_i W(x-X(i))

    (Jádrové funkce se v některé literatuře značí symbolem φ(x)).

  4. Funkci my_parzen() nyní použijte pro odhad distribuce p(x|1). Do jednoho obrázku vykreslete normalizovaný histogram X1 a odhad distribuce p(x|1).
    - pro vyčíslení odhadu použijte vytvořenou funkci: p(x|1) = my_parzen(x,X1,sigma)
    - x volte např. od min(X1) do max(X1) s krokem 100
    Odhad vykreslete pro tři různá sigma, např. sigma = 80,800,1600.

    Očekávané výsledky:



  5. Pomocí krosvalidace,  maximalizací věrohodnosti, odhadněte optimální velikost parametru sigma. Použijte zjednodušenou verzi krosvalidace s dělením jen na dvě množiny (trénovací a validační).

    Postup:
    1. Nastudujte si techniku krosvalidace.
    2. Sadu X1 rozdělte na dvě stejně velké části X1a a X1b (doporučujeme použít funkci crossval()).
    3. Na části X1a odhadněte distribuci p(x|1) pro různá sigma a na druhé části (validační) vyčíslete logaritmus věrohodnosti L(sigma), tj:

      p(x|1) = my_parzen(x,X1a,sigma)
      L(sigma) = Sumx log( p(x|1) ), kde sčítáme přes všechna x z X1b.

    4. Krok 2 opakujte pro různá sigma, např. sigma = 100, 200,...,1000.
    5. Vykreslete do obrázku závislost věrohodnosti L(sigma) na sigma a vyberte optimální hodnotu sigma maximalizující věrohodnost

    Otázka: Jaké sigma by se našlo, pokud bychom množinu nerozdělili, ale hledali maximum věrohodnosti na celé množině?

    Poznámka: Použitý postup, při kterém jsme rozdělili trénovací množinu na dvě části, je zjednodušenou formou krosvalidace. Odvážnější studenti mohou použít její úplný tvar s dělením do více množin.

    Očekávané výsledky:

  6. Stejným způsobem odhadněte distribuci p(x|2).
  7. Odhadnuté distribuce p(x|1) a p(x|2) použijte pro bayesovskou klasifikaci dat v testovací sadě tst. (Apriorní pravděpodobnosti P(1),P(2) odhadněte na trénovací sadě stejným způsobem, jako v předešlém cvičení.) Vyčíslete chybu klasifikace.

Bonusová úloha

Doporučená literatura 


Created by Martin Urban and Karel Zimmerman, 28.10.2006, last update 07.04.2008 V.Franc