Metody pro spolupráci v bayesovském rozhodování s více účastníky

Jan Kracík

Ústav teorie informace a automatizace AV ČR, v.v.i., Oddělení adaptivních systémů

Úvod

Bayesovská teorie rozhodování, plně pravděpodobnostní návrh

Bayesovská teorie představuje normativní přístup k řešení úloh rozhodování za neurčitosti. V praxi se při návrhu optimální rozhodovací strategie vychází z těchto součástí:

• Parametrický pravděpodobnostní model, kterým se modeluje chování systému v závislosti na zvolených rozhodnutích, dřívějších stavech systému a neznámém parametru.
• Apriorní rozdělení pravděpodobnosti neznámého parametru modelu, kterým je reprezentována částečná znalost o chování systému.
• Cíle rozhodování jsou charakterizovány funkcí užitku, která všem případným důsledkům rozhodnutí přiřazuje číselně vyjádřenou míru jejich užitečnosti.

Alternativně lze pro popis cílů a návrh rozhodovací strategie využít takzvaný plně pravděpodobnostní návrh. Jeho princip spočívá v tom, že cíle rozhodování jsou popsány ideální hustotou pravděpodobnosti na celém systému a optimální rozhodovací strategie je pak volena jako znáhodněná a to tak, aby sdružená hustota pravděpodobnosti (daná modelem systému, rozhodovací strategií a apriorní hustotou) byla co nejblíže ideální hustotě ve smyslu Kullback-Leiblerovy divergence. Hlavním přínosem tohoto způsobu návrhu rozhodovací strategie je fakt, že má explicitní řešení, čímž odpadá výpočetně náročná maximalizace očekávané hodnoty užitkové funkce.

Motivace

V praxi je však použitelnost bayesovského rozhodování omezena rozsahem rozhodovací úlohy. To je způsobeno zejména výpočetní složitostí, která s rozměrností úlohy rychle narůstá. V případě rozsáhlých úloh je také často obtížné vyjádřit cíle rozhodování i pravděpodobnostní model systému ve tvaru potřebném pro přímé použití bayesovské teorie. Místo toho jsou často k dispozici pouze dílčí cíle a znalosti vztahující se k určitým částem systému, přimž tyto části se mohou zcela libovolně překrývat. V takových případech se přirozeně stává, že pro některé části systému je k dispozici více dílčích cílů které se vzájemně liší. Totéž pak platí i pro jednotlivé dílčí znalosti o chování systému.

Potřeba vhodného řešení pro velké rozhodovací úlohy vedla k myšlence návrhu distribuovaného rozhodování s více bayesovskými rozhodovači (účastníky). Tato úloha byla řešena v Oddělení adaptivních sysémů ÚTIA AVČR v rámci projektu BADDYR (Bayesian Adaptive Distributed Decision Making) k němuž prezentovaná disertační práce částečně přispěla. Návrh řešení distribuovaného rozhodování v rámci zmíněného projektu vychází z předpokladu, že v daném systému působí skupina bayesovských rozhodovačů, přičemž

• každý účastník se zabývá pouze určitou částí systému (okolí),
• okolí jednotlivých účastníků se mohou libovolně překrývat,
• parametrické modely jednotlivých okolí, apriorní hustoty na příslušných parametrech ani cíle jednotlivých účastníků nemusí být navzájem nijak konzistentní.

Pokud by ovšem každý z účastníků rozhodoval tak, jako kdyby byl jediným rozhodovačem ve své části systému, rozhodování skupiny jako celku by bylo neefektivní právě kvůli rozdílným cílům a znalostem. Neefektivnost takového rozhodování vyplývá z toho, že každý z účastníků získává informace o cílech a znalostech ostatních účastníků pouze nepřímo a to pozorováním jejich vlivu na chování systému. Takovýto způsob přenosu informací je ovšem velmi pomalý. Lze tak očekávat, že rozhodování celé skupiny se stane efektivnějším v případě, že jednotliví účastníci budou mít možnost mezi sebou komunikovat. Z důvodu požadované absence centrálního rozhodovače je pak jedinou možností přímá komunikace mezi účastníky, jejichž okolí se alespoň částečně překrývají. Dvojici takovýchto účastníků označujeme jako sousedy.

Cílem disertační práce byl návrh vhodných metod, které by účastníkům umožnily sdílet a využít informace o cílech a znalostech sousedů a vedly tak ke zlepšení rozhodování celé skupiny.

Hlavní část práce se skládá ze tří kapitol:

1. Rozhodování s více účastníky
2. Nastavení globálních cílů
3. Bayesovské skládání znalostí

Rozhodování s více účastníky

V této části je formálně zavedena bayesovská rozhodovací úloha s více účastníky. Každý účastník má vlastní

• parametrický pravděpodobnostní model svého okolí,
• apriorní rozdělení pravděpodobnosti neznámého parametru modelu,
• ideální hustotu pravděpodobnosti na svém okolí.

Přestože hlavním cílem je návrh distribuovaného řešení, ukazuje se že je nezbytné jako mezistupeň uvažovat jistou formu globální rozhodovací úlohy na celém systému. Smyslem této globální úlohy je umožnit jednoznačné porovnání kvality různých distribuovaných řešení, tj. skupin rozhodovacích strategií navržených jednotlivými účastníky. Pouze na základě znalostí a cílů jednotlivých účastníků však nelze globální úlohu sestavit - v každém případě je nutné přijmout řadu dodatečných předpokladů které např. umožní modelovat zdroje nekonzistence znalostí jednotlivých účastníků. Vzhledem k obrovskému množství možných způsobů sestavení globální úlohy je jakékoliv systematické řešení tohoto problému nad rámec možností předložené práce. Místo toho byl zvolen jeden konkrétní postup na kterém byly ilustrovány případné možnosti pro spolupráci účastníků. Navíc tento postup umožnil odhalit některá problematická místa bayesovského rozhodovaní s více účastníky a v některých případech také naznačil možná řešení.

Nejdůležitější výsledky získané v této části práce lze shrnout následovně:

• Byla ilustrována nutnost uvažovat jistou globální rozhodovací úlohu v pozadí distribuovaného řešení.
• Bylo ukázáno, že bez dodatečných informací obecně nelze globální úlohu sestavit jako bayesovskou pouze na základě znalostí jednotlivých účastníků. K tomu by bylo zapotřebí modelovat vztah mezi znalostmi jednotlivých účastníku (míru jejich překryvu apod.). Informace nutné pro sestavení takového modelu však nelze získat od samotných účastníků.
• Ve speciálním případě, kdy apriorní hustoty jednotlivých účastníků mají tvar konjugované hustoty, lze jimi reprezentované znalosti ekvivalentně vyjádřit jako vzorek pozorovaných dat. Znalosti jednotlivých účastníků pak lze kombinovat přirozeným způsobem i přesto, že využívají rozdílné parametrické modely svých okolí. Tento speciální případ může dobře sloužit jako výchozí bod pro návrh řešení obecnějších případů.

Nastavení globálních cílů

Tato část práce se zabývá návrhem metody, která umožní nalézt cíle globální rozhodovací úlohy tak, aby byly v jistém smyslu co nejblíže dílčím cílům jednotlivých účastníků. Konkrétně se zde předpokládá, že účastníci využívají plně pravděpodobnostní návrh rozhodovací strategie. V takovém případě jsou cíle každého účastníka (lokální cíle) popsány ideální hustotou pravděpodobnosti na jeho okolí. Globální ideální hustota pravděpodobnosti je pak hledána tak, aby vážený součet Kullback-Leiblerových divergencí lokálních ideálních hustot a jim odpovídajících marginál hledané globální ideální hustoty byl co nejmenší. Váhy v tomto součtu představují volitelný parametr - čím větší je určitá váha, tím blíže jsou jsou globální cíle k cílům odpovídajícího účastníka.

Výsledky získané v této části práce jsou následující:

• Je nalezena nutná podmínka, kterou musí sdružená hustota pravděpodobnosti splňovat pro to, aby minimalizovala vážený součet Kullback-Leiblerových divergencí.
• Je dokázáno, že za dodatečného předpokladu je tato podmínka rovněž postačující.
• Rovnice představující postačující podmínku není ve většině případů analyticky řešitelná. Byl proto navržen iterační algoritmus pro přibližné řešení minimalizační úlohy. Jeho konvergence k minimu je dokázána.
• Pro diskrétní náhodné veličiny je iterační algoritmus snadno implementovatelný. V případě spojitých veličin však nastává problém s nevhodnou formou získaných aproximací, neboť pro ně neexistuje společná konečně-rozměrná parametrizace. Tento problém byl vyřešen zavedením zobecněného EM algoritmu. S jeho využitím pak lze aproximace hledat v předem zvolené třídě distribucí - např. konečných gaussovských směsí.

Bayesovské skládání znalostí

V poslední části práce je navržena metoda, pomocí které může bayesovský rozhodovač využít informaci ve formě hustoty pravděpodobnosti na datech ke zlepšení svých znalostí o systému, tj., úpravě své apriorní hustoty pravděpodobnosti na neznámých parametrech. Ve speciálním případě, kdy předávaná hustota má tvar empirické hustoty z jistého vzorku dat, vede navržená metoda ke stejnému výsledku jako přímé využití těchto dat. V rozhodovacích úlohách s více účastníky pak lze tuto metodu využít pro výměnu znalostí mezi sousedy a to i v případě, že oba sousedé využívají rozdílné parametrické modely a jejich znalosti jsou tak reprezentovány apriorními distribucemi na zcela odlišných parametrech. Ačkoliv je v obecném případě takovýto způsob předávání informací pouze přibližný, lze ukázat, že za jistých předpokladů lze tímto způsobem předávat informaci zcela přesně. Další výhodou je, že pro parametrické modely z exponenciální rodiny se výpočet redukuje na nalezení očekávané hodnoty postačující statistiky.

Závěr

Hlavní přínosy disertační práce lze shrnout do následujících bodů:

• Byla provedena případová studie bayesovského rozhodování s více účastníky, která umožnila odhalit problematická místa navrhovaného řešení.
• Pro potřeby nalezení společných cílů rozhodování byl navrženo algoritmické řešení úlohy minimalizace váženého součtu Kullback-Leiblerových divergencí zadaných marginálních hustot pravděpodobnosti a odpovídajících marginál hledané hustoty.
• Byla navržena metoda, která bayesovskému rozhodovači umožní využít informaci ve formě hustoty pravděpodobnosti na datech ke zlepšení znalosti o systému, tj. úpravě apriorní distribuce. Tato metoda je využita pro výměnu informací mezi sousedícími účastníky využívajícími rozdílné parametrické modely svých okolí.

• Bylo navrženo zobecnění známého EM algoritmu, které lze využít k aproximaci složité hustoty pravděpodobnosti konečnou směsí hustot z exponenciální rodiny (např. gaussovskou směsí).
• Metodu navrženou pro výměnu informací mezi sousedy lze dobře využít k zabudování expertní informace ve formě pravděpodobnostní distribuce na datech do apriorna bayesovského rozhodovače.

Prezentovaná práce obsahuje rovněž některé otevřené problémy.

• Úloha bayesovského rozhodování s více účastníky je v současném stavu stále nedostatečně formulována. Je třeba lépe specifikovat jak výchozí předpoklady (omezená výpočetní kapacita účastníků, apod.), tak požadavky vztahující se k formě globální úlohy.
• Návrh distribuovaného rozhodování není zcela dořešen. Navržené metody představují spíše technické prostředky pro spolupráci účastníků. Návrh konkrétních strategií spolupráce - kdy, kdo, s kým má spolupracovat, případně jakou část informací vyměňovat - zůstává otevřeným problémem.