Příroda | Grafický model |
---|---|
Pojmenováno odkazem na | Thomas Bayes |
Ve vědě o počítačích a statistiky , je Bayesian síť je pravděpodobnostní grafický model, představující sadu náhodných veličin ve formě acyklického orientovaného grafu . Bayesiánská síť je intuitivně obojí:
Pro danou doménu (například lékařskou) popisuje kauzální vztah mezi sledovanými proměnnými graf . V tomto grafu nejsou vztahy příčin a následků mezi proměnnými deterministické, ale pravděpodobné . Pozorování jedné příčiny nebo několika příčin tedy systematicky nepřináší účinek nebo účinky, které na něm závisí, ale pouze mění pravděpodobnost jejich pozorování.
Zájmem Bayesovských sítí je současně zohlednit apriorní znalosti odborníků (v grafu) a zkušenosti obsažené v datech.
Bayesovské sítě se používají hlavně pro diagnostiku (lékařskou a průmyslovou ), analýzu rizik, detekci spamu a těžbu dat .
Obsluha, která pracuje na stroji, riskuje při nesprávném použití zranění. Toto riziko závisí na zkušenostech obsluhy a složitosti stroje. „Zkušenost“ a „složitost“ jsou dva určující faktory tohoto rizika (obr. 1).
Tyto faktory samozřejmě neumožňují vytvořit deterministický model. I když je obsluha zkušená a stroj jednoduchý, stále je možná nehoda. Roli mohou hrát i další faktory: obsluha může být unavená, vyrušená atd. Výskyt rizika je vždy náhodný, ale pravděpodobnost jeho výskytu závisí na identifikovaných faktorech.
Obrázek 1 níže představuje kauzální strukturu tohoto modelu (graf).
Obrázek 2 představuje pravděpodobnost závislosti: vidíme, že pravděpodobnost nehody se zvyšuje, pokud uživatel není příliš zkušený nebo je stroj složitý.
Vidíme zde, jak integrovat odborné znalosti (určující faktory) a data (například tabulka pravděpodobnosti nehody podle determinantů může pocházet ze statistik).
Budování Bayesovské sítě je tedy:
Graf se také nazývá „struktura“ modelu a pravděpodobnostní tabulky jeho „parametry“. Struktura a parametry mohou být poskytnuty odborníky nebo vypočteny z údajů, i když obecně je struktura definována odborníky a parametry počítány z experimentálních údajů.
Používání Bayesovské sítě se nazývá „ inference “. Bayesiánská síť je pak skutečně „kalkulačka podmíněné pravděpodobnosti“. Na základě pozorovaných informací se vypočítá pravděpodobnost nepozorovaných dat. Například v závislosti na symptomech pacienta se počítají pravděpodobnosti různých patologií kompatibilních s těmito příznaky. Můžeme také vypočítat pravděpodobnost nepozorovaných příznaků a odvodit nejzajímavější další vyšetření.
Existuje několik způsobů, jak definovat Bayesiánskou síť. Nejjednodušší vyjadřuje zákon společné pravděpodobnosti na množině náhodných proměnných modelovaných v síti. Bayesiánská síť je acyklický směrovaný graf G = (V, E), kde V je sada uzlů v síti a E je sada oblouků. S každým uzlem x patřícím do V grafu je spojeno následující podmíněné rozdělení pravděpodobnosti:
kde pa (x) představuje bezprostřední rodiče x ve VSada V je proto diskrétní sada náhodných proměnných. Každý uzel V je podmíněně nezávislý na svých potomcích, vzhledem k jeho přímým rodičům. Je tedy možné započítat podmíněné rozdělení pravděpodobnosti na všechny proměnné tak, že z nich vyrobíme součin:
Tento výsledek se někdy označuje JPD pro společné rozdělení pravděpodobnosti. Tuto definici lze nalézt v článku Bayesian Networks: Model of Self-Activated Memory for Evidence Reasoning , kde Judea Pearl zavádí pojem „Bayesian network“.
V příkladu uvedeném na obrázku 1 se pravděpodobnost kloubu rovná:
.Dalším způsobem, jak definovat Bayesiánskou síť, je vyhodnotit, zda acyklický směrovaný graf G = (V, E) splňuje globální Markovovu vlastnost (nazývanou zde směrovanou, vzhledem k povaze G) vzhledem k zákonu pravděpodobnosti P na množině proměnných V Nechť X, Y, S jsou tři podmnožiny V, takže X a Y jsou odděleny d, označeny (X | S | Y): globální vlastnost Markov vyjadřuje podmíněnou nezávislost mezi X a Y, tj. X je nezávislé na Y podmíněné na S. Formálně je vlastnost v orientovaném grafu následující:
Je vhodné definovat d-separaci pro „řízenou separaci“ nebo „orientovanou separaci“ v řízeném grafu. Podskupiny X a Y jsou d odděleny S právě tehdy, pokud je jakýkoli řetězec uzlů od X do Y „blokován“ S. U tří uzlů x patřících do X, y patřících do Y a s patřících do S, kanál je blokován v následujících dvou případech:
Intuice spočívá v tom, že S „blokuje“ informace mezi X a Y.
A konečně, podmíněná nezávislost, jak je uvedeno výše , vyjadřuje, že X je podmíněně nezávislé na Y dané S. Formálně:
kdyby a jen kdyby a Nebo jen tehdyVe výše uvedeném příkladu (obrázek 1) můžeme napsat, že zkušenost obsluhy je nezávislá na složitosti stroje, ale že je podmíněně závislá na složitosti stroje vzhledem k riziku „nehody“.
Závěrem lze konstatovat, že acyklický směrovaný graf G = (V, E) je Bayesiánská síť právě tehdy, pokud splňuje směrovanou globální Markovovu vlastnost vzhledem k zákonu pravděpodobnosti P nad množinou proměnných V.
Závěr v Bayesian sítě je výpočet zadních pravděpodobností v síti, s ohledem na nové informace pozorovat. Jedná se o výpočetní problém, protože díky operacím pravděpodobnosti a Bayesově teorému lze vypočítat všechny možné zadní pravděpodobnosti v síti. Vzhledem k souboru důkazů (instanovaných proměnných) Y je tedy problém odvození v G = (V, E) kalkulovat s . Pokud je Y prázdné (žádný důkaz), znamená to výpočet P (X). Intuitivně jde o zodpovězení otázky pravděpodobnosti v síti.
Ačkoli problém odvození závisí na složitosti sítě (čím jednodušší je topologie sítě, tím snazší je odvození), GF Cooper v roce 1987 ukázal, že v obecném případě se jedná o „ NP-tvrdý problém . Kromě toho Dagum a Luby také v roce 1993 ukázali, že najít aproximaci problému odvození v Bayesovské síti je také NP obtížné. Výsledkem těchto výsledků je, že přirozeně přicházejí dvě hlavní kategorie odvozovacích algoritmů: přesné odvozovací algoritmy, které počítají zadní pravděpodobnosti obecně v exponenciálním čase, a heuristiky, které spíše poskytují aproximaci zadních distribucí, ale s menší výpočetní složitostí. Přesněji řečeno, přesné inferenční algoritmy poskytují výsledek a důkaz, že výsledek je přesný, zatímco heuristika poskytuje výsledek bez důkazu jeho kvality (tj. V závislosti na případech může heurista také najít přesné řešení než velmi hrubé přiblížení).
Klasifikace problému odvození jako NP-hard je proto zásadním výsledkem. Aby prokázal svůj důkaz, považuje Cooper obecný problém P (X = x)> 0: je pravděpodobnost, že proměnná X nabude v Bayesovské síti hodnotu x větší než nula? Toto je problém s rozhodnutím (odpověď je ano nebo ne). Cooper nejprve ukazuje, že pokud je problém P (X = x)> 0 NP-úplný, pak P (X = x) je NP-obtížný, a proto je problém odvození v Bayesiánských sítích NP- obtížný. K prokázání NP-úplnost P (X = x)> 0, to polynomiálně redukuje na 3-SAT problém (klasický NP-úplný problém) na problém P (X = x)> 0: Nejprve se ukazuje, že konstrukci Bayesovské sítě z instance 3-SAT, označené C, lze provést s polynomiální složitostí; pak ukazuje, že C je splněno právě tehdy, když P (X = x)> 0 je pravda. Z toho vyplývá, že P (X = x)> 0 je NP-úplný.
Strojové učení se týká metod pro účely extrakce informace obsažené v datech. Jedná se o procesy umělé inteligence, protože umožňují systému vyvíjet se autonomně z empirických dat. V Bayesovských sítích lze strojové učení použít dvěma způsoby: k odhadu struktury sítě nebo k odhadu pravděpodobnostních tabulek sítě, v obou případech z dat.
Existují dvě hlavní rodiny přístupů ke studiu struktury Bayesovské sítě z dat:
Dynamická nebo dočasná Bayesiánská síť (často označovaná jako RBN nebo DBN pro Dynamic Bayesian Network ) je rozšířením Bayesovské sítě, která umožňuje reprezentovat vývoj náhodných proměnných jako funkci diskrétní sekvence, například časové kroky. Dynamický člen charakterizuje modelovaný systém, nikoli síť, která se nemění. Například počínaje sítí uvedenou na obr. 1 by mohl být systém zdynamizován vyjádřením, že budoucí riziko nehody závisí na riziku minulé a současné nehody. Intuice spočívá v tom, že čím více se vzájemně uspěje méně zkušených uživatelů, tím více se zvyšuje riziko nehody; naopak, postupnost zkušených uživatelů toto riziko v průběhu času snižuje. V tomto příkladu se říká, že proměnná „nehoda“ je dynamická, časová nebo trvalá.
Formálně je dynamická Bayesiánská síť definována jako pár . je klasická Bayesiánská síť představující apriorní (nebo počáteční) rozdělení náhodných proměnných; řečeno intuitivněji, je čas 0. je dynamická Bayesiánská síť se dvěma časovými kroky popisujícími přechod z časového kroku t-1 do časového kroku t , tj. pro jakýkoli uzel patřící , do směrovaného acyklického grafu, jak je představeno výše. Potom se zapíše společná pravděpodobnost časového kroku:
Rodiče uzlu, známého pro záznam , tak mohou být buď přímým rodičem v síti v čase t , nebo přímým rodičem v čase t-1 .
Zákon o faktorizované pravděpodobnosti kloubu se počítá „odvíjením“ sítě v časové posloupnosti, za podmínky, že je známa její délka, což bude uvedeno zde . Formálně, pokud je společná pravděpodobnost počáteční sítě , můžeme tedy v časovém kroku 0 napsat:
Dynamická Bayesovská síť tedy respektuje Markovovu vlastnost , která vyjadřuje, že podmíněné rozdělení v čase t závisí pouze na stavu v čase t-1 ve stochastickém procesu . Dynamické Bayesovské sítě jsou zobecněním pravděpodobnostních modelů časových řad, jako je skrytý Markovův model , Kalmanův filtr ...
Naivní Bayesiánský klasifikátor je typ lineárního klasifikátoru, který lze místo toho definovat jako zjednodušení Bayesiánských sítí. Jejich struktura je ve skutečnosti tvořena pouze dvěma úrovněmi: první obsahuje pouze jeden uzel, známý například , a druhá několik uzlů, které mají pouze jednoho rodiče . O těchto modelech se říká, že jsou naivní, protože předpokládají, že všechna vlákna jsou na sobě nezávislá. Vzhledem ke známým dětem je napsán společný zákon pravděpodobnosti Bayesovského klasifikátoru:
Tyto modely jsou zvláště vhodné pro problémy s automatickou klasifikací , kde představují možné nepozorované třídy domény a pozorované proměnné charakterizující každou třídu . Příkladem může být rozdělení jednotlivců v populaci do dvou skupin nebo tříd, „zdravých“ a „nemocných“, podle pozorovaných příznaků, jako je přítomnost horečky atd.
Příčinný diagram je síť Bayesian, ve kterém vazby mezi uzly představují příčinné vztahy. Kauzální diagramy se používají k provedení kauzální inference .