2 Rozhodovací problém Rozhodovací problém je problém s více možnými řešeními. Jde tedy o problémy se kterými se setkáváme v běžném životě. Základním krokem každého rozhodování je proces volby, tedy posuzování jednotlivých variant a výběr varianty optimální. Matematická formulace tohoto problému je námětem této kapitoly.
2.1 Obecná rozhodovací úloha V této kapitole se budeme zabývat rozhodovací úlohou vyjádřenou následujícím formalizmem. Nechť rozhodovatel (subjekt, který se rozhoduje) má k dispozici množinu rozhodnutí D, která mohou vést k některému prvku z množiny výsledků A (někdy se místo množiny rozhodnutí uvažuje množina otázek a místo množiny výsledků množina alternativ). Jednotlivé alternativy (prvky množiny výsledků) můžeme často uspořádat s využitím preferenční relace ». Podle typu kritérií používaných při rozhodování mluvíme o rozhodování s jedním kritériem nebo o rozhodování při více kritériích. V prvním případě je definována jediná preferenční relace, ve druhém případě je preferenčních relací více a každá z nich může definovat jiné uspořádání. V této situaci jsou tři základní možné přístupy jak hledat optimální rozhodnutí: •
lexikografický – kritéria jsou uspořádána podle důležitosti a optimalizují se postupně,
•
paralelní – uvažujeme všechna kritéria současně,
•
agregační – z dílčích kritérií sestrojíme jedno souhrnné.
Preferenční relaci je možno nahradit užitkovou funkcí u: A → R tak, že ∀ a1, a2 ∈ A: u(a1) ≥ u(a2) ⇔ a1 » a2 Vlastní rozhodování pak můžeme formálně definovat rozhodovací funkcí d, která každému prvku r z množiny rozhodnutí D (resp. z množiny odpovědí na otázky) přiřadí nějaký prvek a z množiny A: d(r) = a Řešením rozhodovací úlohy tedy bude nalezení rozhodovací funkce d, která bude v nějakém smyslu optimální.
2.1.1.1 Metoda větví a mezí (branch and bound) Metoda větví a mezí je obecná metoda hledání optimálního řešení nějaké úlohy. Optimální řešení předpokládá existenci výše uvedené užitkové funkce. Metoda je založena na myšlence postupného rozkládání množiny všech řešení na podmnožiny, ze kterých pouze některé budou moci obsahovat optimální řešení. Def. 2.1: Rozkladem množiny A rozumíme systém {A1,…,Ak} jeho disjunktních množin, které jí pokrývají: Ai ⊆ A, pro všechna i = 1,…,k Ai ∩ Aj = ∅, pro i ≠ j k
∪A i =1
i
=A
Předpokládejme, že pro každý prvek nějakého rozkladu R = {A1,…,Ak} umíme spočítat dolní a horní odhady užitkové (či jiné kriteriální) funkce
b(Ai) ≤ u(a) pro všechna řešení a ∈ Ai B(Ai) ≥ u(a) pro všechna řešení a ∈ Ai Potom, pokud kriteriální funkce u vyjadřuje „zisk“ (neboli – hledáme řešení, které tuto hodnotu maximalizuje), pak hledáme takový rozklad R*, který 1. obsahuje jednoprvkovou množinu Aj 2. b(Aj) ≥ B(Ai) pro všechna i = 1,…,k Pokud kriteriální funkce u vyjadřuje „ztrátu“ (neboli – hledáme řešení, které tuto hodnotu minimalizuje), pak hledáme takový rozklad R*, který 3. obsahuje jednoprvkovou množinu Aj 4. B(Aj) ≤ b(Ai) pro všechna i = 1,…,k
Aj pak obsahuje (jediné) optimální řešení. Metoda větví a mezí je založena na konstrukci posloupnosti rozkladů R1, R2,… takových, že rozklad Ri je zjemněním rozkladu Ri-1. Toto zjemnění vznikne tak, že jednou množinu A ∈ Ri rozdělíme na podmnožiny (proces větvení). Meze v názvu metody jsou horní a dolní odhady kriteriální funkce počítané pro prvky jednotlivých rozkladů.
2.2 Chyba rozhodování Snad nejdůležitější otázkou v procesu rozhodování je, jaké chyby se mohu dopustit. Abychom mohli chybu rozhodování definovat, předpokládejme, že známe pravděpodobnostní rozdělení na kartézském součinu množiny rozhodnutí a množiny výsledků Pro jednoduchost dále uvažujme množinu výsledků tvořenou dvěma alternativami: a1 a a2. (tato podkapitola je zpracována dle Chyba! Nenalezen zdroj odkazů.). Pro každou rozhodovací funkci
d: D → {a1, a2} můžeme definovat pravděpodobnosti chyb dvou druhů. První odpovídá situaci, kdy skutečnosti odpovídá a1 ale rozhodovací funkce d volí a2 (označme tuto pravděpodobnost pd(a1→ a2), druhá odpovídá situaci, kdy skutečnosti odpovídá a2 ale rozhodovací funkce d volí a1 (označme tuto pravděpodobnost pd(a2→ a1).
pd(a1→ a2) = ∑r∈D,d(r)=a2 P(r | a1) = ∑r∈D P(r | a1)(1 - δ(d(r),a1)) a
pd(a2→ a1) = ∑r∈D,d(r)=a1 P(r | a2) = ∑r∈D P(r | a2)(1 - δ(d(r),a2)) kde
⎧1 ⎩0
δ ( a, b) = ⎨
pro a = b pro a ≠ b
Příklad 2.1: Uvažujme, že množina rozhodnutí je dvouprvková (označme 0 a 1). Potom existují čtyři rozhodovací funkce di: {0,1} → { a1, a2}
d1(0) = a1,
d1(1) = a1
d2(0) = a1,
d2(1) = a2
d3(0) = a2,
d3(1) = a1
d4(0) = a2,
d4(1) = a2
Z definice pravděpodobnosti chyb dostáváme:
pdi(a1→ a2)
pdi(a2→ a1)
d1
0
P(0|a2) + P(1|a2)
d2
P(1|a1)
P(0|a2)
d3
P(0|a1)
P(1|a2)
d4 P(0|a1) + P(1|a1)
0
Je tedy vidět, že chyby rozhodnutí skutečně závisí na pravděpodobnostním rozdělení P. Def. 2.1: Rozhodovací funkce d1 dominuje rozhodovací funkci d2, jestliže buď
pd1(a2 → a1) ≤ pd2(a2 → a1) a zároveň
pd1(a1→ a2) < pd2(a1→ a2)
pd1(a2 → a1) < pd(a1 → a2) a zároveň
pd1(a1→ a2) ≤ pd1(a1→ a2)
nebo
Def. 2.2: Rozhodovací funkce d je přípustná, jestliže neexistuje rozhodovací funkce, která by dominovala funkci d.
Obě definice ozřejmí pokračování příkladu 2.1: 1. Bude-li rozdělení P(r,a) ve tvaru
P a1
a2
0
0.2 0.3
1
0.1 0.4
Budou pravděpodobnosti chyb pro jednotlivé rozhodovací funkce
pdi(a1→ a2) pdi(a2→ a1) d1
0
1
d2
1/3
3/7
d3
2/3
4/7
d4
1
0
(při výpočtu musíme vyjít z toho, že
P (r | a) =
P (r, a) ) P(a)
Z tabulky vidíme, že rozhodovací funkce d1, d2 a d4 jsou přípustné, ale rozhodovací funkce d3 není přípustná, neboť je dominována funkcí d2. 2. Bude-li rozdělení P(r,a) ve tvaru
P a1
a2
0
0.1 0.3
1
0.2 0.4
Budou pravděpodobnosti chyb pro jednotlivé rozhodovací funkce
pdi(a1→ a2) pdi(a2→ a1) d1
0
1
d2
2/3
3/7
d3
1/3
4/7
d4
1
0
A tedy všechny rozhodovací funkce budou přípustné. Věta 2.1: Jestliže existují kladná čísla w(a1) a w(a2) taková, že rozhodovací funkce ⎧ a pro w(a1 ) P(r | a1 ) > w(a 2 ) P(r | a 2 ) , d (r ) = ⎨ 1 ⎩a 2 pro w(a1 ) P(r | a1 ) < w(a 2 ) P(r | a 2 ) potom je rozhodovací funkce d přípustná.
Věta 2:2: Jestliže je rozhodovací funkce d(r) definována způsobem uvedeným ve větě 1, pak tato rozhodovací funkce minimalizuje hodnotu
w(a1)pd(a1→a2) + w(a2)pd(a2→a1) a je tedy pro daná w(a1) a w(a2) optimální.
Větu 2.2 můžeme využít při hledání optimální rozhodovací funkce v různých situacích: 1. Bayesovsky optimální rozhodovací funkce minimalizuje celkovou střední chybu rozhodování definovanou jako
RP(d) = P(a1)pd(a1→a2) + P(a2)pd(a2→a1) = 2
2
∑∑ P(ai ) P(r | ai )(1 − δ (d (r), ai )) = ∑∑ P(r, ai )(1 − δ (d (r), ai )) i =1 r∈D
i =1 r∈D
je tedy w(a1) =P(a1) a w(a2) = P(a2) 2. Rozhodovací funkce optimální vzhledem ke kritériu maximální věrohodnosti dostáváme, pokud minimalizujeme chybu definovanou jako
RP(d) = pd(a1→a2) + pd(a2→a1) Potom w(a1) =1 a w(a2) = 1. V některých situacích můžeme znát tzv. cenu jednotlivých chyb. Chyby a1→a2 a a2→a1 totiž nemusí být symetrické. Je jistě větší chybou půjčit peníze nespolehlivé osobě, která je nevrátí (proděláme), než nepůjčit osobě spolehlivé, která by peníze vrátila i s úroky (nevyděláme). Podobně je jistě větší chybou nerozpoznat chorobu u nemocného pacienta (což může vést k značným zdravotním komplikacím), než diagnostikovat chorobu u pacienta zdravého (a provádět u něj další vyšetření). V takových situacích se zavádí tzv. chybová (též ztrátová) funkce, pomocí které hodnotíme ztrátu v situaci, kdy správná alternativa je a1 a my volíme a2 resp. naopak:
e: {a1, a2} × {a1, a2} → [0,∞) Pak můžeme definovat celkové riziko či celkovou střední ztrátu jako 2
2
R P (d ) = ∑∑ P(r, ai )e(a i , d (r )) = ∑∑ P(ai ) P(r | ai )e(ai , d (r )) i =1 r∈D
i =1 r∈D
Za (běžného) předpokladu, že e(a,a) = 0 je optimální rozhodovací funkce opět definována větou 1, přičemž
w(a1) = e(a1,a2) w(a2) = e(a2,a1).
Výše uvedené úvahy vycházejí z toho, že známe pravděpodobnostní rozložení situací, které mohou nastat. Ne vždy je tento předpoklad reálný. Často se musíme spokojit s neúplnou znalostí. V takovém případě můžeme použít princip maximální entropie nebo princip minimaxu.
1. Podle principu maximální entropie vybereme rozdělení s nejvyšší Shannonovskou entropií ⎛ 2 ⎞ H ( PH ) = max⎜⎜ − ∑∑ P(r,ai ) log P(r, ai ) ⎟⎟ P ⎝ i =1 r∈D ⎠
2. Podle principu minimaxu bereme v úvahu kritérium, které odpovídá maximální možné chybě, které se můžeme dopustit 2
max R p (d ) = max ∑∑ P(r, ai )(1 − δ (d (r ), ai )) P
P
i =1 r∈D
Tuto chybu pak chceme hledanou rozhodovací funkcí minimalizovat 2
d opt = arg min max ∑∑ P(r, ai )(1 − δ (d (r ), ai )) d
P
i =1 r∈D
Příklad 2.2: Opět uvažujme dvouprvkovou množinu rozhodnutí (označme 0 a 1) a tedy čtyři rozhodovací funkce di: {0,1} → { a1, a2}
d1(0) = a1,
d1(1) = a1
d2(0) = a1,
d2(1) = a2
d3(0) = a2,
d3(1) = a1
d4(0) = a2,
d4(1) = a2
Mějme ale tentokráte dvě rozdělení P1 a P2 definované na D × { a1, a2}:
P1
a1
a2
P2
a1
a2
0
0.2 0.1
0
0.1 0.6
1
0.4 0.3
1
0.1 0.2
Bayesovsky optimální funkce bude funkce, která přiřadí hodnotě r∈D tu alternativu, pro kterou je P(r,ai) větší. Tedy pro rozdělení P1 je bayesovsky optimální rozhodovací funkce d1 a pro rozdělení P2 je bayesovsky optimální rozhodovací funkce d4. Při hledání optimální rozhodovací funkce dle kritéria maximální věrohodnosti musíme pracovat s podmíněnými pravděpodobnostmi P(r| ai), přičemž P (r, ai ) P (r | a i ) = P(ai ) Pracujeme tedy s tabulkami
P1(r|ai)
a1
a2
P2(r|ai) a1
a2
0
2/6 1/4
0
1/2 6/8
1
4/6 3/4
1
1/2 2/8
ze kterých plyne, že pro rozdělení P1 je optimální rozhodovací funkce d2 a pro rozdělení P2 je optimální rozhodovací funkce d3. Opět totiž hledáme rozhodovací funkci, která přiřadí hodnotě r∈D alternativu s větší pravděpodobností (tentokrát ale podmíněnou). Princip maximální entropie vede k tomu, že z rozdělení P1 a P2 vybereme rozdělení P1. Vybíráme totiž rozdělení s větší hodnotu entropie:
H(P1) = -(-0,14 - 0,10 - 0,16 - 0,16) = 0,5558 H(P2) = -(-0,10 - 0,13 - 0,10 - 0,14) = 0,4729 Pro rozdělení P1 je, jak již víme, optimální rozhodovací funkcí d1 (v případě požadavku na bayesovskou optimalitu), případně d2 (v případě kritéria maximální věrohodnosti).
Podle principu minimaxu musíme spočítat chybu RP(d) pro všechny čtyři rozhodovací funkce a obě rozdělení. Při výpočtu použijeme vztah 2
R p (d ) = ∑∑ P (r, a i )(1 − δ (d (r ), ai )) i =1 r∈D
Tedy např.
RP1(d1) = P1(0, a2) + P1(1, a2) = 0.1 + 0.3 = 0.4 Všechny hodnoty této chyby vidíme v následující tabulce. Tučně jsou vyznačeny maximální hodnoty chyby pro obě rozdělení. Jako optimální vybereme tu rozhodovací funkci, která má nejmenší hodnotu tohoto maxima; vybereme tedy rozhodovací funkci d3.
di
RP1(d)
RP2(d)
d1
0.4
0.8
d2
0.5
0.7
d3
0.5
0.3
d4
0.6
0.2
2.3 Rozhodovací strategie Předpokládejme, že množina rozhodnutí i množina výsledků jsou konečné. Pak můžeme Kritérium hodnotící optimalitu rozhodnutí vzhledem k výsledku vyjádřit pomocí matice (Obr. 2.1). Je-li tímto kritériem užitek, pak optimální rozhodnutí užitek maximalizuje, je-li tímto kritériem cena, pak optimální rozhodnutí cenu minimalizuje
.
⎛ u11 ⎜ rozhodnutí ⎜ u 21 ⎜ ⎜ ⎜u ⎝ k1
výsledek u12 … u1t ⎞ ⎟ u 22 … u 2t ⎟ ⎟ … ⎟ u k 2 … u kl ⎟⎠
⎛ c11 ⎜ rozhodnutí ⎜ c 21 ⎜ ⎜ ⎜c ⎝ k1
výsledek c12 … c1t ⎞ ⎟ c 22 … c2t ⎟ ⎟ … ⎟ ck 2 … ckl ⎟⎠
Obr. 2.1 Kritérium optimality
2.3.1 Rozhodování za určitosti (jistoty) Rozhodovací funkce d přiřadí každému rozhodnutí jediný výsledek.
2.3.2 Rozhodování za rizika Rozhodovací funkce d přiřadí každému rozhodnutí nějaké známé rozložení pravděpodobnosti na množině V. Skutečný výsledek je vybírán na základě této pravděpodobnosti. Optimální rozhodnutí i* je to, které maximalizuje střední hodnotu užitku l
i = arg max ∑ u ij p j *
i
j =1
resp. minimalizuje střední hodnotu ceny l
i * = arg min ∑ cij p j i
j =1
2.3.3 Rozhodování za neurčitosti Rozhodovací funkce d přiřadí každému rozhodnutí nějakou podmnožinu výsledků, neznáme ale jejich pravděpodobnosti (nevíme, který výsledek nastane). Jak už bylo uvedeno výše, existují dvě základní strategie jak postupovat:
•
Garanční (minimaxová) strategie vychází z toho, že očekáváme (z hlediska našich preferencí) nejméně příznivý výsledek Tedy v případě, že kritériem je užitek, hledáme rozhodnutí i* takové, že
i * = arg max min u ij i
j
a v případě, že kritériem je cena, hledáme rozhodnutí i* takové, že
i * = arg min max u ij i
j
•
Princip maximální entropie je založen na předpokladu rovnoměrného rozdělení pravděpodobností jednotlivých výsledků, tedy že pi = pj. V případě, že kritériem užitek, hledáme rozhodnutí i* takové, že l
i * = arg max ∑ u ij i
j =1
a v případě, že kritériem je cena, hledáme rozhodnutí i* takové, že l
i * = arg min ∑ cij i
j =1
2.3.4 Riziko vs. Neurčitost Princip rozhodování za rizika a neurčitosti osvětlí následující příklad převzatý ze [Štecha]. Pan Novák stojí před úkolem objednat uhlí na zimu. Ze zkušenosti ví, že pokud bude zima mírná, stačí mu 10q uhlí, pokud bude normální, bude potřebovat 15q a pokud bude tuhá, bude potřebovat 20q. V létě je cena 1q uhlí 100,- Kč. Pokud bude nakupovat zimě, bude cena záviset na průběhu zimy. Při mírné zimě bude cena za 1q uhlí rovněž 100,- Kč, při normální zimě bude cena za 1q uhlí 150,Kč a při tuhé zimě bude cena za 1q uhlí 200,- Kč. Rozhodovacím problémem pana Nováka je tedy kolik uhlí má koupit v létě. Daná úloha má tři možná rozhodnutí (odpovědi na otázku kolik uhlí koupit v létě) a tři možné výsledky (alternativní průběhy zimy). Kritériem hodnocení jednotlivých variant je cena, kterou pan Novák ve výsledku zaplatí (pokud v létě koupí méně uhlí, než bude potřebovat, musí něco dokoupit v zimě). Hodnotu kritéria pro jednotlivé varianty ukazuje následující tabulka. mírná zima normální zima tuhá zima v létě 10 1000
1750
3000
v létě 15 1500
1500
2500
v létě 20 2000
2000
2000
Při rozhodování při riziku musí pan Novák znát pravděpodobnosti jednotlivých podob zimy. Řekněme, že P(mírná) = 0.4 P(normální) = 0.5 P(tuhá) = 0.1 Pan Novák vybere rozhodnutí (řádek i), které bude minimalizovat hodnotu
∑j pjaij pro i=1 je ∑j pjaij = 0.4⋅1000 + 0.5⋅1750 + 0.1⋅3000 = 1575 pro i=2 je ∑j pjaij = 0.4⋅1500 + 0.5⋅1500 + 0.1⋅2500 = 1600 pro i=3 je ∑j pjaij = 0.4⋅2000 + 0.5⋅2000 + 0.1⋅2000 = 2000 Pan Novák tedy v létě koupí 10q uhlí.
Při rozhodování za neurčitosti pan Novák pravděpodobnosti jednotlivých podob zimy nezná:
•
při použití minimaxové strategie pan Novák vybere to rozhodnutí i, pro které maxj (aij) bude minimální. Pan Novák tedy v létě koupí 20q uhlí, neboť ve třetím řádku je maximální hodnota minimální ze všech řádkových maxim.
•
při použití principu maximální entropie pan Novák vybere to rozhodnutí i, pro které
∑j aij bude minimální. (Přesně vzato, budeme opět minimalizovat výraz ∑j pjaij, ale protože pj je při rovnoměrném rozdělení konstanta, můžeme ji zanedbat). pro i=1 je ∑j aij = 1000 + 1750 + 3000 = 5750 pro i=2 je ∑j aij = 1500 + 1500 + 2500 = 5500 pro i=3 je ∑j aij = 2000 + 2000 + 2000 = 6000 Pan Novák tedy v létě koupí 15q uhlí.
Cvičení: 1) Banka. Bankéř se rozhoduje, zda poskytne půjčku klientovi. Pokud půjčí klientovi, který půjčku splatí, získá 10. Pokud půjčí klientovi, který nesplatí, ztratí 5. Pokud nepůjčí klientovi, který by půjčku splatil, ztratí 1 a pokud nepůjčí klientovi, který by nesplatil, zůstane na 0. Přitom ví, že pravděpodobnost, že klient je bonitní, je 0.9. Jak se má bankéř rozhodnout dle pravidla minimaxu, dle bayesova kritéria a dle principu maximální entropie?
Literatura: 1. Jiroušek R.: Metody reprezentace a zpracován.ní znalostí v umělé inteligenci. Skripta VŠE, 1995 2. Štecha J.: Optimální rozhodování a řízení. FEL ČVUT, 1999.
