Monografie
Deset přednášek z teorie statistického a strukturního rozpoznávání Michail I. Schlesinger, Václav Hlaváč
Praha 1999 Vydavatelství ČVUT
1. přednáška Bayesovská úloha statistického rozhodování 1.1 Úvod ke zkoumání bayesovské úlohy Bayesovská teorie je jedním z pilířů statistického rozpoznávání. V první přednášce se seznámíme se základními pojmy teorie, formulujeme bayesovskou úlohu statistického rozhodování a dokážeme nejdůležitější vlastnosti úlohy. Tyto vlastnosti jsou považovány za obecně známé. Byli bychom rádi, kdyby tomu tak opravdu bylo, ale dost často můžeme pozorovat návrhy řešení, která přímo odporují výsledkům bayesovské teorie, i když na první pohled vypadají přirozeně. Svědčí to o tom, že znalost bayesovské teorie je jen zdánlivá. Taková neúplná znalost je možná horší než úplná neznalost. Zajisté měl pravdu kdosi, když řekl, že raději jedná s člověkem, který nepřečetl žádnou knihu než s někým, kdo přečetl jedinou knihu. Nepochopení a jen zdánlivá znalost úloh bayesovského rozhodování spočívá také v tom, že se jménem T. Bayese jsou spojovány různé výsledky v teorii pravděpodobnosti a statistickém rozhodování. Vzorec pro počítání s podmíněnými pravděpodobnostmi je znám jako Bayesův vzorec. Doporučení, jak se má za jistých předpokladů vybrat nejpravděpodobnější hodnota náhodné veličiny, se také nazývá Bayesovým jménem. Kromě toho i úlohám statistického rozhodování založeným na minimalizaci rizika a pokutách se říká bayesovské úlohy. V našich přednáškách se budeme zabývat především posledně jmenovanými úlohami. Uveďme základní pojmy a jejich značení, které využijeme i v dalších přednáškách.
1.2 Formulace bayesovské úlohy Nechť je nějaký objekt popsán dvěma parametry x a k. První z nich je pozorovatelný a druhý parametr je skrytý, tedy pro bezprostřední pozorování nepřístupný. Parametru x budeme říkat příznak objektu nebo pozorování. Příznak x bude nabývat hodnoty z jisté množiny X. Druhý parametr nazveme stavem objektu nebo skrytým parametrem. Označme symbolem K množinu hodnot skrytého parametru k. Označení D použijme pro množinu možných rozhodnutí. 1
9. přednáška
Regulární jazyky a odpovídající úlohy rozpoznávání
Nechť je δ[x, y] Kroneckerova funkce, pro kterou platí δ(x, y) = 1⊗ , jestliže x = y, a δ(x, y) = 0⊕ , jestliže x 6= y. Pro Kroneckerovu funkci také platí O f [x, y] δ[y, z] = f [x, z], y
tj. konvoluce s Kroneckerovou funkcí samu funkci nemění a mění jen označení jejího argumentu. Jestliže je polookruh tvořen operacemi min ve smyslu sčítání a + ve smyslu násobení, potom získají konvoluční výrazy dodatečné vlastnosti plynoucí z idempotentnosti sčítání, což znamená f ⊕ f = f . Nechť je f [x, y] funkce tvaru X × X → (R ∪ {∞}). Pro kteroukoliv funkci f N tohoto tvaru označíme f 0 [x, y] n Kroneckerovu funkci a f [x, y] konvoluci f [z, y] z f n−1 [x, z].
Lemma 9.2 O konvergenci součtu. Nechť množina X obsahuje k prvků. V takovém případě součet f 0 [x, y] ⊕ f 1 [x, y] ⊕ f 2 [x, y] ⊕ . . . ⊕ f n [x, y] při n → ∞ konverguje k funkci (δ ⊕ f )k−1 , tj. lim
n→∞
n M
f i [x, y] = (δ ⊕ f )
i=0
k−1
[x, y] . N
Důkaz.
Dokážeme nejdřív, že pro libovolné n platí n M i=0
n
f i = (δ ⊕ f ) .
(9.23)
Rovnost (9.23) je zjevně správná při n = 0 a n = 1. Jestliže n = 0, potom levá strana je δ a pravá strana je (δ ⊕ f )0 , což je také δ, protože podle definice jakákoliv funkce v nulté mocnině je δ. Jestliže n = 1, potom je levá i pravá strana rovnice (9.23) rovna δ ⊕ f . Dokážeme, že když je správná rovnice (9.23) pro některé n, je ona správná i pro n + 1. Z idempotentnosti, tj. f ⊕ f = f , plyne následující odvození ! ! n+1 n n+1 M M M M i i i f [x, y] = f [x, y] f [x, y] = i=0
i=0
=
n M i=0
426
i=1
i
f [x, y]
!
M
f [x, z]
n O M z
i=0
i
f [z, y]
!
=
Levensteinova aproximace posloupnosti větou regulárního jazyka 9.5 ! ! M n n O M OM f i [z, y] = f i [z, y] f [x, z] = δ[x, z] z
=
=
=
δ[x, z]
δ[x, z]
δ[x, y]
z
i=0
n O M
M
f [x, z]
M
f [x, z]
M
f [x, y]
z
f i [z, y]
i=0
O
δ[z, y]
z
n+1
M
!
i=0
=
f [z, y]
n
=
.
Vztah (9.23) je dokázán pro každou celou hodnotu n. Dokážeme teď hlavní tvrzení lemmatu 9.2. Ztotožníme množinu X s vrcholy grafu a hodnotu f (x, y), x ∈ X, y ∈ X, s délkou orientované hrany (šipky), která vychází z vrcholu x a míří do vrcholu y. Číslo f (x, y) je délkou nejkratší cesty z vrcholu xNdo vrcholu y za podmínky, že se cesta skládá z jedné šipky. Hodnota f (x, z) z f (z, y) je délkou nejkratší cesty z vrcholu x do vrcholu y za podmínky, že se cesta skládá ze dvou šipek. V obecném případě je f n (x, y) délkou nejkratší cesty z vrcholu x do vrcholu y za podmínky, že se cesta skládá z n šipek. Toto tvrzení má smysl i tehdy, když n = 0. Nejkratší cesta z x do y, která se neskládá z žádné šipky, je zjevně 0 = 1⊗ , jestliže a je ∞ = 0⊗ , Lnx = y, i 0 jestliže x 6= y. Je to tedy δ(x, y), tj. f (x, y). Součet i=0 f [x, y] je délkou nejkratší cesty z x do y, která se skládá z nanejvýš n šipek. Tato cesta nemůže procházet více než k − 1 šipkami. V opačném případě by tato cesta obsahovala cyklus, a to se při nezáporně definované funkci f nemůže stát. Z toho plyne, že při n ≥ k platí rovnice n M
f i [x, y] =
k−1 M
f i [x, y] .
i=0
i=0
Následkem už dokázané rovnosti (9.23) máme lim
n→∞
n M i=0
f i = (δ ⊕ f )
k−1
.
Dokázané lemma ukazuje konstruktivní způsob výpočtu nekonečného polynomu L ∞ i ∗ i=0 f . Dále budeme pro tento nekonečný polynom používat označení f , a to pro libovolnou funkci f : X × X → W . Na základě lemmatu 9.2 se pro jisté případy může ukázat konstruktivní způsob výpočtu konvolucí podle proměnné, která nabývá hodnot z nekonečné množiny, 427
Prof. Ing. Michail I. Schlesinger, DrSc. a prof. Ing. Václav Hlaváč, CSc. Deset přednášek z teorie statistického a strukturního rozpoznávání Vydalo Vydavatelství ČVUT, Zikova 4, 166 35 Praha 6, jako svou 9453. publikaci. Graficky upravil a systémem TEX vysázel Vít Zýka. Vytisklo Ediční středisko ČVUT, Zikova 4, Praha 6. 531 stran, 61 obrázků. Vydání první. Náklad 800 výtisků. Rozsah 42,10 AA, 42,43 VA. PLU 2329
