Minimaxní úloha

V tomto cvičení se podíváme na minimaxní strategii rozhodování. Tedy na případ, kdy známe hustoty pravděpodobností, ale neznáme apriorní pravděpodobnosti.

Formulace minimaxní úlohy

Představte si, že náš bayesovský klasifikátor z druhého cvičení chceme použít v praxi na rozpoznávání segmentovaných písmen na SPZkách aut. Předpokládejme, že předem nevíme, poblíž kterého města bude náš systém nasazen. Neznáme tedy apriorní pravděpodobnost výskytu danného písmene (v různých částech republiky se písmena vyskytují různě často). Naším cílem je navrhnout klasifikátor, který minimalizuje chybu pro nejhorší případ apriorních pravděpodobností, tedy klasifikátor klasifikující na základě minimaxní strategie.

Rozhodnutí budeme, stejně jako v prvním cvičení, činit na základě jediného měření

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

Zadání

Úlohu si zjednodušíme na případ, kdy se na SPZce vyskytují pouze dvě písmena (vyberte si libovolná dvě z dodané abecedy). V následujícím textu budou pro přehlednost označeny A a B.

Stáhněte si a nahrajte do Matlabu soubor data_33rpz_cv03_minmax.mat. Jeho struktura je stejná jako v druhém cvičení, až na to, že nejsou uvedené apriorní pravděpodobnosti tříd, jelikož nejsou dopředu známé. Parametry distribucí P(x|k) jsou uložené v poli D, které pořadím odpovídá poli Alphabet.
Pro různé hodnoty apriorních pravděpodobností P(A) v intervalu 0-1 (např. 0.1, 0.2, ... 0.9) spočtěte a vykreslete do grafu:

Bayesovské riziko optimální bayesovské strategie pro dané apriorní pravděpodobnosti.
Bayesovské riziko strategie rozhodování, která je optimální pro P(A) = 0.25. Zkoumáme tedy, co se děje, když použijeme strategii optimální pro jednu danou apriorní pravděpodobnost, přičemž následná pozorování mají apriorní pravděpodobnost odlišnou.

Nápověda: Bude se vám hodit vztah (3) z prvního textu v doporučené literatuře.
Najděte optimální bayesovskou strategii pro danou apriorní pravděpodobnost P(A). Vykreslete maximální riziko této strategie, pokud by byla skutečná apriorní pravděpodobnost odlišná.

Nápověda: Využijte znalosti z přechozího bodu a toho, že P(A) se může měnit jen v intervalu 0-1.

Na základě vykreslených výsledků určete minimaxní strategii a její risk.

Bonusová úloha

Tato úloha není povinná. Prostudujte si řešení nebayesovských úloh v knize SH10 (Schlesinger, Hlaváč - Deset přednášek... viz níže), zejména kapitoly týkající se řešení minimaxní úlohy pomocí lineárního programování (viz. strany 25, 31, 35-38, 41 a 47). Použijte stejné zadání jako na cvičení. Tentokrát ale úlohu hledání minimaxního klasifikátoru řešte jako úlohu lineárního programování. Přístup je podrobněji popsán v SH10 na straně 47.

Nápověda

Místo spojitého příznakového prostoru je nutné použít diskrétní. Tj. odezvu příznaku nejdříve diskretizujeme na N ekvidistantních binů.
Hledanou strategii (klasifikační funkci) reprezentujte tabulkou α(i,k), kde α(i,k) značí pravděpodobnost klasifikace binu 'i' do třídy 'k'. (tj. α(i,k)>=0, sum(α(i,:))=1.)
Zapište úlohu v maticové formě dle vztahu (2.54, SH10, strana 47).
K numerickému vyřešení úlohy lineárního programování použijte funkci linprog.
Do jednoho obrázku si vykreslete hodnoty P(X|A), P(X|B) v jednotlivých binech a dále také znázorněte klasifikaci jednotlivých binů.
Porovnejte výsledky s úlohou ze cvičení.

Doporučená literatura

Minimaxní rozhodování (cvičení z minulého semestru)
Archív zápisů z přednášek rozpoznávání (33RPZ)
Michail I. Schlesinger, Václav Hlaváč. Deset přednášek z teorie statistického a strukturního rozpoznávání. Vydavatelství ČVUT, Praha 1999.

Created by Jan Šochman, last update 11.10.2007