Expertní systémy Neurčitost – Bayesovské sítě Jan Górecki Název prezentace Název projektu Rozvoj vzdělávání na Slezské univerzitě v Opavě Registrační číslo projektu CZ.02.2.69/0.0./0.0/16_015/0002400 Logolink_OP_VVV_hor_barva_cz •Neurčitost je charakteristickým rysem složitých systémů. Vlastní povaha reality způsobuje, že poznatky, které z ní získáváme, jsou neurčité či vágní. – Neurčitost (opakování) csvukrs –problémy s daty; např.: •chybějící nebo nedostupná data •nespolehlivá data (např. z důvodu chyb měření) •nepřesná nebo nekonzistentní reprezentace dat Příčiny neurčitosti (opakování) csvukrs –nejisté znalosti; např.: •znalost nemusí být platná ve všech případech •znalost může obsahovat vágní pojmy. – Příčiny neurčitosti (opakování) csvukrs •Bayesovská síť (Bayesian belief network) je orientovaný acyklický graf, jehož uzlům odpovídají náhodné proměnné a vazby reprezentují kauzální závislosti mezi těmito proměnnými. Bayesovské sítě csvukrs •Hrana X ® Y znamená, že X kauzálně ovlivňuje Y (pozorování X poskytuje kauzální podporu Y, pozorování Y poskytuje diagnostickou podporu pro X). Bayesovská síť umožňuje provádět prediktivní i diagnostické inference. Bayesovské sítě csvukrs •Každému uzlu je přiřazena tabulka rozdělení pravděpodobnosti. Jestliže uzel nemá žádné předchůdce (rodiče), jedná se o nepodmíněnou pravděpodobnost, v opačném případě jde o podmíněnou pravděpodobnost. – Bayesovské sítě csvukrs •Nechť G = (V, E) je orientovaný acyklický graf a nechť v Î V. •Definujme následující množiny: • C(v) = {u Î V | (u, v) Î E}, • D(v) = {w Î V | existuje cesta z v do w }, • A(v) = {x Î V | x ¹ v a x Ï C(v) È D(v)}. • •Množina C(v) je množinou bezprostředních předchůdců (rodičů) uzlu v, D(v) je množinou všech následníků uzlu v (nejen bezprostředních). V případě bayesovské sítě prvky C(v) nazýváme také příčinami. – Pojmy potřebné pro definici bayesovské sítě csvukrs •Nechť (W, P) je pravděpodobnostní prostor, kde W = W1 ´ … ´ Wn , a nechť Xi (i = 1, … , n) je projekce W na Wi (tj. Xi : W ® Wi je náhodná proměnná). Nechť (V, E) je orientovaný acyklický graf, kde V = {X1, … , Xn }. Definice bayesovské sítě csvukrs •Řekneme, že (V, E, P) je bayesovská síť, jestliže pro všechna Xi Î V a všechna W Í A(Xi) jsou Xi a W podmíněně nezávislé při daném C(Xi). To znamená, že když W = {Y1, …, Yk}, C(Xi) = {Z1, …, Zm}, • P(Y1 Ù … Ù Yk Ù Z1 Ù … Ù Zm) ¹ 0, pak •P(Xi | Y1 Ù … Ù Yk Ù Z1 Ù … Ù Zm) = P(Xi | Z1 Ù … Ù Zm). Definice bayesovské sítě csvukrs •Zjednodušeně řečeno, když známe příčiny Xi , nic jiného než Xi samotné nebo jeho následníci nám nemůže dát nějaké další informace o Xi . Místo pojmu bayesovská síť se někdy užívají pojmy kauzální síť či influenční diagram. – Definice bayesovské sítě csvukrs •Nechť X je náhodná proměnná s oborem hodnot O(X) a P je pravděpodobnost. Symbolem P(X) rozumíme funkci definovanou na O(X) tak, že pro x Î O(X) je P(x) = P(X = x) . – Poznámky k symbolice csvukrs •Zápisy pravděpodobností můžeme dále zjednodušit následujícím způsobem. Nechť V = {X1, … , Xn}, C(Xi) = {Z1, … , Zm}. Pak definujeme •P(V) = P({X1} È … È {Xn}) = P(X1, … , Xn) = P(X1 Ù … Ù Xn), •P(Xi | C(Xi)) = P(Xi | Z1, … , Zm) = P(Xi | Z1 Ù … Ù Zm). Poznámky k symbolice csvukrs •Pomocí uvedené symboliky můžeme definici bayesovské sítě přepsat takto: Řekneme, že (V, E, P) je bayesovská síť, jestliže pro všechna • Xi Î V a všechna W Í A(Xi), P(W È C(Xi)) ¹ 0, platí, že • P(Xi | W È C(Xi)) = P(Xi | C(Xi)). – Poznámky k symbolice csvukrs –Nechť (V, E, P) je bayesovská síť. Pak platí: – – – Vlastnosti bayesovské sítě csvukrs •Nechť (V, E) je orientovaný acyklický graf, kde V = {X1, … , Xn }, přičemž Xi jsou proměnné s obory hodnot O(Xi). Nechť f(X | C(X)) • je nezáporná reálná funkce taková, že • pro všechny kombinace hodnot proměnných z C(X). Pak • W = O(X1) ´ … ´ O(Xn) a • definují pravděpodobnostní prostor, pro nějž (V, E, P) je bayesovská síť. Přitom P(X | C(X)) je buď 0 nebo f(X | C(X)). – Vlastnosti bayesovské sítě csvukrs –1. Specifikujeme veličiny X1, … , Xn a jejich obory hodnot O(Xi). Konstrukce bayesovské sítě csvukrs –1. Specifikujeme veličiny X1, … , Xn a jejich obory hodnot O(Xi). Konstrukce bayesovské sítě csvukrs •2. Zkonstruujeme orientovaný acyklický graf (V, E), kde • V = {X1, … , Xn}, vyjadřující kauzální závislosti mezi veličinami. Konstrukce bayesovské sítě csvukrs 3.Odhadneme pravděpodobnost P tak, že odhadneme P(X | C(X)) pro všechna X, všechny hodnoty X a všechny kombinace hodnot proměnných z C(X). Podle předchozí věty je nezbytné splnění pouze těchto podmínek: 4. 4. Konstrukce bayesovské sítě csvukrs •Problém řešený pomocí bayesovské sítě je možno zjednodušeně formulovat takto: • Problém pro bayesovskou síť csvukrs • Nechť je dána bayesovská síť (V, E, P) a množiny U Í V, W Í V, U Ç W = Æ. Jsou-li zadány hodnoty proměnných z množiny U, je třeba zjistit P(W | U). Problém pro bayesovskou síť csvukrs •Po zadání hodnot některých proměnných se provádí inference, což znamená přepočet podmíněných pravděpodobností pro ostatní proměnné. Inference v bayesovské síti je založena na Bayesových vzorcích. Problém pro bayesovskou síť csvukrs •Obecně je výše zmíněný problém NP-těžký, což znamená, že pro něj neexistují algoritmy s polynomiální časovou složitostí. Pokud bayesovská síť nemá speciální strukturu, je nutné použít aproximační techniky, které jsou obvykle založeny na nějakých transformacích bayesovské sítě na jednodušší tvar. – Problém pro bayesovskou síť csvukrs •Řekneme, že bayesovská síť je jednoduše souvislá, jestliže mezi každými dvěma uzly existuje právě jedna neorientovaná cesta. Jednoduše souvislá bayesovská síť csvukrs •Jednoduše souvislá síť se také nazývá polystrom nebo les. Zvláštním případem polystromu je strom, což je graf, kde každý uzel má nejvýše jednoho rodiče. – Jednoduše souvislá bayesovská síť csvukrs •Pro polystromovou bayesovskou síť existují algoritmy pro inferenci, které mají polynomiální časovou složitost. – Jednoduše souvislá bayesovská síť csvukrs •pro modelování a vysvětlení chování problémů v různých oblastech např. model chování vody v krajině Typické použití Bayesovských sítí csvukrs •pro nalezení nejpravděpodobnějších konfigurací proměnných – např. při automatickém rozpoznávání řeči nebo při dekódování zakódovaných zpráv Typické použití Bayesovských sítí csvukrs •pro podporu rozhodování při nejisté informaci - použití teorie maximalizace očekávaného užitku Typické použití Bayesovských sítí csvukrs •pro nalezení dobrých strategií pro řešení problémů v oblastech s nejistotou - např. technická diagnostika laserových tiskáren, nebo návrh adaptivních testů. • Typické použití Bayesovských sítí csvukrs Děkuji za pozornost Některé snímky převzaty od: RNDr. Jiří Dvořák, CSc. dvorak@fme.vutbr.cz