Bayesovské programování

Bayesovské programování je formální systém a metodologie pro definování pravděpodobnostních modelů a řešení problémů, když nejsou k dispozici všechny potřebné informace.

Edwin Thompson Jaynes navrhl zvážit pravděpodobnost jako alternativu a rozšíření logiky pro racionální uvažování s neúplnými a nejistými informacemi. Ve své přelomové knize The Theory of Probability: The Logic of Science [1] tuto teorii rozvinul a navrhl to, co nazýval „robot“, což nebylo fyzické zařízení, ale inferenční stroj, který automatizuje pravděpodobnostní uvažování – něco jako Prolog pro teorii pravděpodobnosti místo logiky. Bayesovské programování [2] je formální a konkrétní implementace tohoto „robota“.

Bayesovské programování lze také chápat jako formální algebraický systém pro specifikaci grafových modelů , jako jsou například Bayesovské sítě , dynamické Bayesovské sítě Kalmanovy filtry nebo skryté Markovovy modely . Bayesovské programování ve skutečnosti zobecňuje bayesovské sítě a má výrazovou sílu ekvivalentní faktorovým grafům .

Formální systém

Bayesovský program je prostředkem pro specifikaci rodiny rozdělení pravděpodobnosti.

Níže jsou uvedeny stavební kameny Bayesovského programu:

{\text{Program}}{\begin{cases}{\text{Description}}{\begin{cases}{\text{Specification}}(\pi ){\begin{cases}{\text{ Proměnné}}\\{\text{Decomposition}}\\{\text{Forms}}\\\end{cases}}\\{\text{Identifikace (na základě }}\delta )\end{cases}} \\{\text{Question}}\end{cases}}

Program se skládá z popisu ( anglický popis ) a otázky ( anglický dotaz ).
Popis je vytvořen pomocí nějaké definice ( , eng. specifikace ) dané programátorem a identifikace ( eng. identifikace ) nebo procesu učení pro parametry, které nejsou plně popsány v definici, pomocí datové sady ( ). $\pi$ $\delta$
Definice je postavena ze sady významných proměnných ( anglicky variables ), rozkladu ( anglicky decomposition ) a sady forem ( anglické formy ).
Tvary jsou buď parametrické tvary nebo otázky k jiným bayesovským programům.
Otázka specifikuje rozdělení pravděpodobnosti, které se má vypočítat.

Popis

Popis specifikuje účinnou metodu pro výpočet společného rozdělení pravděpodobnosti množiny proměnných pro danou množinu experimentálních dat a určitou definici . Toto společné rozdělení se označuje jako . ${\displaystyle \left\{X_{1},X_{2},\cdots ,X_{N}\right\))$ $\delta$ $\pi$ $P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)$

Pro specifikaci předchozích znalostí musí programátor provést následující: $\pi$

Určete množinu významných proměnných , na kterých je dáno společné rozdělení pravděpodobnosti. ${\displaystyle \left\{X_{1},X_{2},\cdots ,X_{N}\right\))$
Rozložte společné rozdělení (rozbijte jej na vhodné nezávislé nebo podmíněné pravděpodobnosti ).
Určete tvar každého z těchto rozdělení (například pro každou proměnnou vyberte jedno ze seznamu rozdělení pravděpodobnosti ).

Rozklad

Nechť množina obsahuje podmnožiny, proměnné jsou definovány jako , z nichž každá odpovídá jedné z těchto podmnožin. Každá proměnná se získá jako spojení proměnných patřících do -té podmnožiny. Rekurzivní aplikace Bayesovy věty vede k ${\displaystyle \left\{X_{1},X_{2},\ldots ,X_{N}\right\))$ $K$ $K$ $L_{1},\cdots ,L_{K}$ ${\displaystyle L_{k))$ ${\displaystyle \left\{X_{k_{1)),X_{k_{2)),\cdots \right\))$ $k$

{\begin{aligned}&P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)\\={}&P \left(L_{1}\wedge \cdots \wedge L_{K}\mid \delta \wedge \pi \right)\\={}&P\left(L_{1}\mid \delta \wedge \pi \ vpravo)\krát P\vlevo(L_{2}\střed L_{1}\klín \delta \klín \pi \vpravo)\krát \cdots \krát P\vlevo(L_{K}\střed L_{K-1 }\wedge \cdots \wedge L_{1}\wedge \delta \wedge \pi \right)\end{aligned}}

Použití hypotézy podmíněné nezávislosti nám umožňuje provést další zjednodušení. Hypotéza podmíněné nezávislosti pro proměnnou je definována výběrem nějaké proměnné mezi proměnnými přítomnými ve spojení . Označení konjunkcí vybraných proměnných a převzetí ${\displaystyle L_{k))$ $X_{{n}}$ ${\displaystyle L_{k-1}\wedge \cdots \wedge L_{2}\wedge L_{1))$ ${\displaystyle R_{k))$

P\left(L_{k}\mid L_{k-1}\wedge \cdots \wedge L_{1}\wedge \delta \wedge \pi \right)=P\left(L_{k}\ střední R_{k}\klín \delta \klín \pi \right)

Dostaneme

{\begin{aligned}&P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)\\={}&P \left(L_{1}\mid \delta \wedge \pi \right)\times P\left(L_{2}\mid R_{2}\wedge \delta \wedge \pi \right)\times \cdots \ krát P\left(L_{K}\mid R_{K}\wedge \delta \wedge \pi \right)\end{aligned}}

Toto zjednodušení společného rozdělení jako produktu jednodušších rozdělení se nazývá rozklad podle řetězového pravidla

Tím je zajištěno, že se každá proměnná objeví nalevo od podmíněného řádku alespoň jednou, což je nutná a postačující podmínka pro zápis matematicky správných výpočtů. .

Formuláře

Každá distribuce vyskytující se v produktu je pak spojena buď s parametrickou formou (tj. funkcí ), nebo s otázkou na jiný Baysovský program . $P\left(L_{k}\mid R_{k}\wedge \delta \wedge \pi \right)$ $f_{\mu }\left(L_{k}\right)$ $P\left(L_{k}\mid R_{k}\wedge \delta \wedge \pi \right)=P\left(L\mid R\wedge {\widehat {\delta ))\wedge { \widehat {\pi }}\right)$

Když je to forma , je obecně vektor parametrů, které mohou záviset na buď , nebo , nebo obou. Když jsou některé z těchto parametrů vypočítány pomocí datové sady , dojde k trénování. $f_{\mu }\left(L_{k}\right)$ $\mu$ ${\displaystyle R_{k))$ $\delta$ $\delta$

Důležitou vlastností bayesovského programování je možnost používat otázky k jiným bayesovským programům jako součást definice nového bayesovského programu. se získá výstupem vytvořeným jiným bayesovským programem daným definicí a daty . Je to podobné volání podprogramu v klasickém programování a poskytuje snadný způsob, jak vytvořit hierarchické modely . $P\left(L_{k}\mid R_{k}\wedge \delta \wedge \pi \right)$ ${\widehat {\pi ))$ ${\widehat {\delta ))$

Otázka

Nechť je uveden popis (tj. ), otázku získáme rozdělením do tří množin: vyšetřované ( angl. hledané ) proměnné, známé ( angl. známé ) proměnné a volné ( angl. volné ) proměnné. $P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)$ ${\displaystyle \left\{X_{1},X_{2},\cdots ,X_{N}\right\))$

Tři proměnné , a jsou definovány jako spojení proměnných patřících do těchto sad. $Searched$ $známý$ $zdarma$

Otázka je definována jako množina distribucí

P\left(Vyhledáváno\mid {\text{Známý))\wedge \delta \wedge \pi \right)

složený ze "specifikovaných otázek" jako kardinál , kde každá vytvořená otázka je distribucí $známý$

P\left({\text{Searched}}\mid {\text{Známý}}\wedge \delta \wedge \pi \right)

Závěr

Pro danou společnou distribuci je vždy možné vypočítat jakoukoli otázku použitím následující obecné derivace: $P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)$

{\begin{aligned}&P\left({\text{Searched}}\mid {\text{Známý}}\wedge \delta \wedge \pi \right)\\={}&\součet _{ \text{Free}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\mid {\text{Známý}}\wedge \delta \wedge \pi \right)\ vpravo]\\={}&{\frac {\displaystyle \sum _{\text{Free}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\wedge { \text{Známý}}\mid \delta \wedge \pi \right)\right]}{\displaystyle P\left({\text{Známý}}\mid \delta \wedge \pi \right)))\\ ={}&{\frac {\displaystyle \sum _{\text{Free}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\wedge {\text{Známý }}\mid \delta \wedge \pi \right)\right]}{\displaystyle \sum _({\text{Free}}\wedge {\text{Searched}}}\left[P\left({\ text{Hledaný}}\wedge {\text{Free}}\wedge {\text{Známý}}\mid \delta \wedge \pi \right)\right]}}\\={}&{\frac {1 }{Z}}\times \sum _{\text{Free}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\wedge {\text{Známý}}\ mid \delta \wedge \pi \right)\right]\end{aligned}}

kde první rovnost vyplývá z pravidla marginalizace , druhá vyplývá z Bayesova teorému a třetí odpovídá druhé aplikaci marginalizace. Jmenovatel se ukáže jako normalizační člen a může být nahrazen konstantou . $Z$

Teoreticky vám to umožňuje vyřešit jakýkoli problém Bayesovské inference. V praxi se však téměř ve všech případech náklady na vyčerpávající a přesný výpočet ukazují jako příliš vysoké. $P\left({\text{Searched}}\mid {\text{Známý}}\wedge \delta \wedge \pi \right)$

Nahrazením společného rozdělení jeho rozkladem získáme

{\begin{aligned}&P\left({\text{Searched}}\mid {\text{Známý}}\wedge \delta \wedge \pi \right)\\={}&{\frac { 1}{Z}}\součet _{\text{Free}}\left[\prod _{k=1}^{K}\left[P\left(L_{i}\mid K_{i}\wedge \pi \right)\right]\right]\end{aligned}}

což je obvykle výraz, který se počítá mnohem jednodušeji, protože dimenze problému je výrazně redukována rozkladem na součin distribucí nižší dimenze.

Příklad

Bayesovská detekce spamu

Cílem bayesovského filtrování spamu je eliminovat nevyžádané e-maily.

Formulace tohoto problému je poměrně jednoduchá. E-maily by měly být klasifikovány do jedné ze dvou kategorií: nespamové a nevyžádané. Jedinou informací dostupnou pro klasifikaci e-mailů je jejich obsah: sada slov. Použití slov bez zohlednění jejich pořadí ve větě se často nazývá model pytle slov .

Klasifikátor se navíc musí umět přizpůsobit svému uživateli a poučit se ze zkušeností. Počínaje standardním výchozím nastavením musí klasifikátor změnit své vnitřní parametry, pokud uživatel s jeho rozhodnutím nesouhlasí. Přizpůsobí se tedy kritériím uživatele pro rozlišení mezi nevyžádanou poštou a nevyžádanou poštou. Zlepší své vlastní výsledky, protože se bude setkávat se stále více utajovanými e-maily.

Proměnné

K napsání tohoto programu jsou nutné následující proměnné:

$spam$ : binární proměnná, false , pokud e-mail není spam, v opačném případě true .
${\displaystyle W_{0},W_{1},\ldots ,W_{N-1))$ : binární proměnné. je pravdivé , pokud je v textu přítomno -té slovo ze slovníku. $N$ $W_{n}$ $n$

Tyto binární proměnné shrnují všechny informace o e-mailu. $N+1$

Rozklad

Počínaje definicí společného rozdělení a rekurzivní aplikací Bayesova teorému dostaneme:

{\begin{aligned}&P({\text{Spam}}\wedge W_{0}\wedge \cdots \wedge W_{N-1})\\={}&P({\text{Spam} })\krát P(W_{0}\mid {\text{Spam)))\krát P(W_{1}\mid {\text{Spam))\klín W_{0})\\&\times \ cdots \\&\times P\left(W_{N-1}\mid {\text{Spam}}\wedge W_{0}\wedge \cdots \wedge W_{N-2}\right)\end{aligned }}

Toto je přesný matematický výraz.

Lze to radikálně zjednodušit za předpokladu, že pravděpodobnost výskytu slova v dané kategorii textu (spam nebo ne) je nezávislá na výskytu jiných slov. Takový předpoklad je naivní bayesovský , a proto je tento spamový filtr naivním bayesovským modelem.

To by například mohl předpokládat programátor

P(W_{1}\mid {\text{Spam}}\land W_{0})=P(W_{1}\mid {\text{Spam}})

a nakonec získat

P({\text{Spam}}\land W_{0}\land \ldots \land W_{N-1})=P({\text{Spam}})\prod _{n=0} ^{N-1}[P(W_{n}\mid {\text{Spam)))]

Tento předpoklad je známý jako naivní Bayesův předpoklad . Je to „naivní“ v tom smyslu, že nezávislost mezi slovy zjevně neplatí. Například zcela opomíjí skutečnost, že výskyt dvojice slov může být významnější než ojedinělé výskyty. Programátor však může tuto hypotézu přijmout a může vyvinout tento model a jeho související výstup, aby otestoval, jak je spolehlivý a účinný.

Parametrické tvary

Aby mohl programátor vypočítat společné rozdělení, musí nyní specifikovat rozdělení přítomné v rozkladu: $N+1$

$P({\text{Spam)))$ definované a priori, například jako $P([{\text{Spam}}=1])=0,75$
Každá z forem může být specifikována pomocí Laplaceova pravidla (jedná se o vyhlazovací techniku založenou na pseudo čítači k překonání problému nulové frekvence dosud neviděných slov): $N$ $P(W_{n}\mid {\text{Spam)))$
1. $P(W_{n}\mid [{\text{Spam}}={\text{false}}])={\frac {1+a_{f}^{n}}{2+a_{ F}}}$
2. $P(W_{n}\mid [{\text{Spam}}={\text{true}}])={\frac {1+a_{t}^{n}}{2+a_{ t}}}$

kde je počet výskytů druhého slova v e-mailech, které nejsou spamem, a je celkový počet e-mailů, které nejsou spamem. Podobně je počet výskytů tohoto slova ve spamových e-mailech a je celkový počet spamových e-mailů. ${\displaystyle a_{f}^{n))$ $n$ ${\displaystyle a_{f))$ ${\displaystyle a_{t}^{n))$ $n$ $v}$

Identifikace

$N$ formuláře ještě nebyly plně definovány, protože parametry , , a ještě nemají hodnoty. $P(W_{n}\mid {\text{Spam)))$ $2N+2$ ${\displaystyle a_{f}^{n=0,\ldots ,N-1))$ ${\displaystyle a_{t}^{n=0,\ldots ,N-1))$ ${\displaystyle a_{f))$ $v}$

Identifikaci těchto parametrů lze provést buď dávkovým zpracováním skupiny klasifikovaných e-mailů, nebo postupnou aktualizací parametrů klasifikací e-mailů uživatelem při jejich příchodu.

Obě metody lze kombinovat: systém může začít s výchozími výchozími hodnotami těchto parametrů danými ze zobecněné databáze a poté určité inkrementální učení vyhovuje klasifikátoru pro každého jednotlivého uživatele.

Otázka

Otázka, která je programu položena, zní: "Jaká je pravděpodobnost, že tento text je spam, pokud je známo, která slova se v něm vyskytují a která ne?" Lze to formalizovat jako

P({\text{Spam}}\mid w_{0}\wedge \cdots \wedge w_{N-1})

které lze vypočítat takto:

{\begin{aligned}&P({\text{Spam}}\mid w_{0}\wedge \cdots \wedge w_{N-1})\\={}&{\frac {\displaystyle P ({\text{Spam)))\prod _{n=0}^{N-1}[P(w_{n}\mid {\text{Spam)))]}{\displaystyle \sum _{\ text{Spam}}[P({\text{Spam}})\prod _{n=0}^{N-1}[P(w_{n}\mid {\text{Spam}})]]} }\end{aligned}}

V tomto výrazu se ukáže, že jmenovatelem je normalizační konstanta . Není nutné jej počítat, abychom zjistili, zda máme co do činění se spamem. Například jednoduchý trik pro výpočet poměru:

{\begin{aligned}&{\frac {P([{\text{Spam}}={\text{true}}]\mid w_{0}\wedge \cdots \wedge w_{N-1 })}{P([{\text{Spam}}={\text{false}}]\mid w_{0}\wedge \cdots \wedge w_{N-1)))))\\={} & {\frac {P([{\text{Spam}}={\text{true}}])}{P([{\text{Spam}}={\text{false}}])}}\ krát \prod _{n=0}^{N-1}\left[{\frac {P(w_{n}\mid [{\text{Spam}}={\text{true}}])}{ P (w_{n}\mid [{\text{Spam}}={\text{false}}])}}\right]\end{aligned}}

Tento výpočet je rychlejší a pohodlnější, protože vyžaduje pouze produkty. $2N$

Bayesovský program

Bayesovský program filtru nevyžádané pošty je plně definován jako

\Pr {\begin{cases}Ds{\begin{cases}Sp(\pi ){\begin{cases}Va:{\text{Spam)),W_{0},W_{1}\ldots W_{N-1}\\Dc:{\begin{cases}P({\text{Spam}}\land W_{0}\land \ldots \land W_{n}\land \ldots \land W_{N -1})\\=P({\text{Spam)))\prod _{n=0}^{N-1}P(W_{n}\mid {\text{Spam)))\end{ případy}}\\Fo:{\begin{cases}P({\text{Spam}}):{\begin{cases}P([{\text{Spam}}={\text{false}}]) =0,25\\P([{\text{Spam}}={\text{true}}])=0,75\end{cases}}\\P(W_{n}\mid {\text{Spam}}) :{\begin{cases}P(W_{n}\mid [{\text{Spam}}={\text{false}}])\\={\frac {1+a_{f}^{n} }{2+a_{f))}\\P(W_{n}\mid [{\text{Spam}}={\text{true}}])\\={\frac {1+a_{t }^{n}}{2+a_{t}}}\end{cases}}\\\end{cases}}\\\end{cases}}\\{\text{Identifikace (na základě }}\ delta )\end{cases}}\\Qu:P({\text{Spam}}\mid w_{0}\land \ldots \land w_{n}\land \ldots \land w_{N-1}) \end{cases}}

Bayesovský filtr, Kalmanův filtr a skrytý Markovův model

Bayesovské filtry (často označované jako rekurzivní Bayesovský odhad ) jsou obecné pravděpodobnostní modely pro procesy, které se odvíjejí v průběhu času. Speciálními případy tohoto obecného přístupu jsou četné modely, jako je Kalmanův filtr nebo skrytý Markovův model .

Proměnné

Proměnné - časová řada stavových veličin, které jsou uvažovány v časovém horizontu v rozmezí od do . ${\displaystyle S^{0},\ldots ,S^{T))$ $0$ $T$
Proměnné - časová řada pozorovaných proměnných na stejném horizontu. ${\displaystyle O^{0},\ldots ,O^{T))$

Rozklad

Rozklad je založen na:

$P(S^{t}\mid S^{t-1})$ , nazývaný systémový model, přechodový model nebo dynamický model, který formalizuje přechod ze stavu v určitém okamžiku do stavu v určitém okamžiku ; $t-1$ $t$
$P(O^{t}\mid S^{t})$ , tzv. pozorovací model, který vyjadřuje, co lze pozorovat v době , kdy je systém ve stavu ; $t$ ${\displaystyle S^{t))$
počáteční stav v čase : . $0$ $P(S^{0}\wedge O^{0})$

Parametrické tvary

Výběr parametrických forem není omezen a různé možnosti vedou k různým dobře známým modelům: viz Kalmanovy filtry a skryté Markovovy modely níže.

Otázka

Společná otázka pro tyto modely zní : jaké je rozdělení pravděpodobnosti stavu v čase t za předpokladu pozorování od času do t ? $P\left(S^{t+k}\mid O^{0}\wedge \cdots \wedge O^{t}\right)$ $t+k$ $0$ $t$

Nejobecnějším případem je Bayesovské filtrování, pro které , což znamená, že současný stav je určen známými předchozími pozorováními. $k=0$

Je však také možné extrapolovat budoucí stav pomocí minulých pozorování nebo provést vyhlazení pro rekonstrukci minulého stavu z pozorování provedených buď před, nebo po určitém časovém okamžiku. $(k>0)$ $(k<0)$

Mohou být položeny pokročilejší otázky, jak je uvedeno níže v části HMM.

Bayesovské filtry mají velmi zajímavou rekurzivní vlastnost, která velkou měrou přispívá k jejich přitažlivosti. lze jednoduše vypočítat pomocí následujícího vzorce: $(k=0)$ $P\left(S^{t}|O^{0}\wedge \cdots \wedge O^{t}\right)$ $P\left(S^{t1}\mid O^{0}\wedge \cdots \wedge O^{t-1}\right)$

{\begin{array}{ll}&P\left(S^{t}|O^{0}\wedge \cdots \wedge O^{t}\right)\\=&P\left(O^ {t}|S^{t}\vpravo)\krát \součet _{S^{t-1}}\vlevo[P\vlevo(S^{t}|S^{t-1}\vpravo)\ krát P\left(S^{t-1}|O^{0}\wedge \cdots \wedge O^{t-1}\right)\right]\end{array}}

Dalším zajímavým způsobem, jak se podívat na tuto rovnici, je zvážit existenci dvou fází: fáze předvídání a fáze hodnocení:

Během fáze predikce se stav předpovídá pomocí dynamického modelu a odhadu stavu v předchozím okamžiku:

{\begin{array}{ll}&P\left(S^{t}|O^{0}\wedge \cdots \wedge O^{t-1}\right)\\=&\sum _ {S^{t-1}}\left[P\left(S^{t}|S^{t-1}\right)\krát P\left(S^{t-1}|O^{0 }\wedge \cdots \wedge O^{t-1}\right)\right]\end{array}}

Během fáze hodnocení je předpověď buď potvrzena, nebo vyvrácena posledním pozorováním:

{\begin{aligned}&P\left(S^{t}\mid O^{0}\wedge \cdots \wedge O^{t}\right)\\={}&P\left(O^ {t}\mid S^{t}\right)\times P\left(S^{t}|O^{0}\wedge \cdots \wedge O^{t-1}\right)\end{aligned }}

Bayesovský program

Pr{\begin{cases}Ds{\begin{cases}Sp(\pi ){\begin{cases}Va:\\S^{0},\cdots ,S^{T},O^{ 0},\cdots ,O^{T}\\Dc:\\{\begin{cases}&P\left(S^{0}\wedge \cdots \wedge S^{T}\wedge O^{0} \wedge \cdots \wedge O^{T}|\pi \right)\\=&P\left(S^{0}\wedge O^{0}\right)\times \prod _{t=1}^ {T}\left[P\left(S^{t}|S^{t-1}\right)\krát P\left(O^{t}|S^{t}\right)\right]\ end{cases}}\\Fo:\\{\begin{cases}P\left(S^{0}\wedge O^{0}\right)\\P\left(S^{t}|S^ {t-1}\right)\\P\left(O^{t}|S^{t}\right)\end{cases}}\end{cases}}\\Id\end{cases}}\ \Qu:\\{\begin{cases}{\begin{array}{l}P\left(S^{t+k}|O^{0}\wedge \cdots \wedge O^{t}\right )\\\levá (k=0\vpravo)\ekviv {\text{Filtrování}}\\\levá(k>0\vpravo)\ekviv {\text{Predpověď}}\\\levá(k<0\ vpravo)\equiv {\text{Smoothing}}\end{array}}\end{cases}}\end{cases}}

Kalmanův filtr

Speciálním případem bayesovských filtrů jsou známé Kalmanovy filtry [3] .

Jsou dány následujícím Bayesovským programem:

Pr{\begin{cases}Ds{\begin{cases}Sp(\pi ){\begin{cases}Va:\\S^{0},\cdots ,S^{T},O^{ 0},\cdots ,O^{T}\\Dc:\\{\begin{cases}&P\left(S^{0}\wedge \cdots \wedge O^{T}|\pi \right)\ \=&\left[{\begin{array}{c}P\left(S^{0}\wedge O^{0}|\pi \right)\\\prod _{t=1}^{T }\left[P\left(S^{t}|S^{t-1}\wedge \pi \right)\krát P\left(O^{t}|S^{t}\wedge \pi \ right)\right]\end{array}}\right]\end{cases}}\\Fo:\\{\begin{cases}P\left(S^{t}\mid S^{t-1} \wedge \pi \right)\equiv G\left(S^{t},A\bullet S^{t-1},Q\right)\\P\left(O^{t}\mid S^{ t}\wedge \pi \right)\equiv G\left(O^{t},H\bullet S^{t},R\right)\end{cases}}\end{cases}}\\Id\ end{cases}}\\Qu:\\P\left(S^{T}\mid O^{0}\wedge \cdots \wedge O^{T}\wedge \pi \right)\end{cases} }

Proměnné jsou spojité.
Vzorce přechodu a pozorování jsou definovány pomocí Gaussova rozdělení , ve kterém jsou prostředky lineární funkce proměnných podmínek. $P(S^{t}\mid S^{t-1}\wedge \pi )$ $P(O^{t}\mid S^{t}\wedge \pi )$

Pomocí těchto hypotéz a rekurzivního vzorce lze problém odvození pro zodpovězení běžné otázky analyticky vyřešit. Výsledkem je extrémně účinný algoritmus, který vysvětluje popularitu Kalmanových filtrů a jejich mnoho každodenních aplikací. $P(S^{T}\mid O^{0}\wedge \cdots \wedge O^{T}\wedge \pi )$

Pokud neexistují žádné zjevné lineární přechodové a pozorovací modely, často je stále možné pomocí Taylorova rozšíření prvního řádu považovat tyto modely za lineární lokálně. Toto zobecnění se obvykle nazývá rozšířený Kalmanův filtr .

Skrytý Markovův model

Dalším velmi oblíbeným speciálním případem Kalmanových filtrů jsou skryté Markovovy modely (HMM).

Jsou dány následujícím Bayesovským programem:

\Pr {\begin{cases}Ds{\begin{cases}Sp(\pi ){\begin{cases}Va:\\S^{0},\ldots ,S^{T},O^ {0},\ldots ,O^{T}\\Dc:\\{\begin{cases}&P\left(S^{0}\wedge \cdots \wedge O^{T}\mid \pi \right )\\=&\left[{\begin{array}{c}P\left(S^{0}\wedge O^{0}\mid \pi \right)\\\prod _{t=1} ^{T}\left[P\left(S^{t}\mid S^{t-1}\wedge \pi \right)\times P\left(O^{t}\mid S^{t} \wedge \pi \right)\right]\end{array}}\right]\end{cases}}\\Fo:\\{\begin{cases}P\left(S^{0}\wedge O^ {0}\mid \pi \right)\equiv {\text{Matrix}}\\P\left(S^{t}\mid S^{t-1}\wedge \pi \right)\equiv {\ text{Matrix}}\\P\left(O^{t}\mid S^{t}\wedge \pi \right)\equiv {\text{Matrix}}\end{cases}}\end{cases} }\\Id\end{cases}}\\Qu:\\\max _{S^{1}\wedge \cdots \wedge S^{T-1}}\left[P\left(S^{1 }\wedge \cdots \wedge S^{T-1}\mid S^{T}\wedge O^{0}\wedge \cdots \wedge O^{T}\wedge \pi \right)\right]\ end{cases}}

Proměnné jsou považovány za diskrétní.
Přechodové a pozorovací modely jsou specifikovány pomocí pravděpodobnostních matic. $P\left(S^{t}\mid S^{t-1}\wedge \pi \right)$ $P\left(O^{t}\mid S^{t}\wedge \pi \right)$
Nejčastěji kladená otázka na Hidden Markov Models je:

\max _{S^{1}\wedge \cdots \wedge S^{T-1}}\left[P\left(S^{1}\wedge \cdots \wedge S^{T-1 }\mid S^{T}\wedge O^{0}\wedge \cdots \wedge O^{T}\wedge \pi \right)\right]

Jaká je nejpravděpodobnější posloupnost stavů vedoucí k současnému stavu, vezmeme-li v úvahu minulá pozorování?

Odpověď na tuto otázku lze získat pomocí velmi účinného algoritmu - Viterbiho algoritmu .

Pro HMM byl vyvinut také Baum-Welsh algoritmus .

Aplikace

Akademické přihlášky

Během posledních 15 let bylo bayesovské programování aplikováno na mnoha univerzitách k vývoji aplikací v robotice i modelů ve vědách o živé přírodě [4] .

Robotika

V robotice se Bayesovské programování uplatnilo v autonomní robotice [5] [6] [7] [8] [9] , robotických CAD systémech [10] , pokročilých asistenčních systémech řidiče [11] , robotickém řízení manipulátorů , mobilní robotika [12] [13] , interakce člověk-robot [14] , interakce člověk-vozidlo (Bayesovské modely autonomních řidičů) [15] [16] [17] [18] [19] [20 ] , programování a učení avatarů ve videohrách [21] a strategických hrách v reálném čase ( AI ). [22]

Vědy o živé přírodě

Ve vědách o živé přírodě se Bayesovské programování používá ve vědách o vidění k rekonstrukci formy z pohybu [23] , k modelování vizuálně-vestibulární interakce [24] a ke studiu saccadického pohybu očí [25] ; ve vnímání a ovládání řeči studovat ranou asimilaci řeči [26] a vznik kloubně-akustických systémů [27] ; pro modelování vnímání a ovládání ručně psaného textu [28] .

Rozpoznávání vzorů

Bayesovské programování má potenciální aplikace v rozpoznávání a syntéze řeči , rozpoznávání obrazu a zpracování přirozeného jazyka . Zde využívá principy komposability (budování abstraktních reprezentací z částí), kauzality (stavba komplexu z částí) a učení se učit (používání dříve uznávaných pojmů k usnadnění tvorby pojmů nových) [29] .

Bayesovské programování a teorie možností

Srovnání mezi pravděpodobnostními přístupy (nejen Bayesovské programování) a teoriemi možností je nadále předmětem debaty.

Teorie možností, jako jsou například fuzzy množiny [30] , fuzzy logika [31] a samotná teorie možností [32] nabízejí různé alternativy pro modelování nejistoty pomocí pravděpodobnosti. Tvrdí, že pravděpodobnost je nedostatečná nebo nepohodlná pro modelování určitých aspektů neúplných nebo nejistých znalostí.

Obhajoba pravděpodobnostního přístupu je založena především na Coxově teorému , který se skládá ze čtyř postulátů týkajících se racionálního uvažování za nejistoty. Ukazuje, že jediný matematický model, který tyto postuláty splňuje, je teorie pravděpodobnosti. Důkazem je, že jakýkoli jiný přístup než teorie pravděpodobnosti porušuje jeden z těchto postulátů.

Bayesovské programování a pravděpodobnostní programování

Cílem pravděpodobnostního programování je spojit oblast klasických programovacích jazyků s pravděpodobnostním modelováním (zejména bayesovské sítě ) tak, abychom se dokázali vypořádat s nejistotou a zároveň využili vyjadřovací sílu programovacích jazyků k popisu složitých modely.

Rozšířené klasické programovací jazyky zahrnují logické jazyky, jak je navrženo v Probabilistic Horn Abduction [ 33 ] , Independent Choice Logic [34] , PRISM [35] a ProbLog jazyka Prolog .

Může to být také rozšíření funkčních programovacích jazyků (v podstatě LISP a Scheme ), jako je IBAL nebo Church . Základní jazyky rozšíření mohou být také objektově orientované , jako v případě BLOG a FACTORIE, nebo standardnější, jako na CES a FIGARO Archived 1 February 2016 at Wayback Machine .

Účel bayesovského programování je poněkud odlišný. Jaynesova pozice „pravděpodobnosti jako logiky“ tvrdí, že pravděpodobnost je rozšířením a alternativou k logice, na jejímž vrcholu lze přestavět celou teorii racionality, algoritmů a programování [1] . Bayesovské programování nehledá způsob, jak rozšířit klasické jazyky, snaží se je nahradit novým přístupem k programování založenému na pravděpodobnosti, který bere v úvahu neúplnost a nejistotu.

Přesné srovnání sémantiky a vyjadřovací síly bayesovského a pravděpodobnostního programování je stále otevřenou otázkou.

Viz také

Poznámky

↑ 1 2 Jaynes, Edwin T. Teorie pravděpodobnosti: Logika vědy . - Cambridge University Press , 2003. - ISBN 0-521-59271-2 .
↑ Bessière, P.; Mazer, E.; Ahuactzin, JM.; Mekhnacha, K. Bayesovské programování . - Chapman & Hall/CRC, 2013. - ISBN 9781439880326 .
↑ Kalman, RE Nový přístup k problémům lineárního filtrování a predikce // Transactions of the ASME--Journal of Basic Engineering: journal. - 1960. - Sv. 82 . — S. 33——45 . - doi : 10.1115/1.3662552 .
↑ Bessière, P.; Laugier, C. & Siegwart, R. Pravděpodobnostní uvažování a rozhodování v senzoricko-motorických systémech . — Springer, 2008. - ISBN 978-3-540-79007-5 .
↑ Lebeltel, O.; Bessière, P.; Diard, J.; Mazer, E. Bayesian Robot Programming (anglicky) // Advanced Robotics. - 2004. - Sv. 16 , č. 1 . — S. 49——79 . - doi : 10.1023/b:auro.0000008671.38949.43 .
↑ Diard, J.; Gilet, E.; Simonin, E.; Bessière, P. Inkrementální učení Bayesovských senzomotorických modelů: od nízkoúrovňového chování k rozsáhlé struktuře prostředí // Connection Science : journal. - 2010. - Sv. 22 , č. 4 . - str. 291--312 . - doi : 10.1080/09540091003682561 .
↑ Pradalier, C.; Hermosillo, J.; Koike, C.; Braillon, C.; Bessière, P.; Laugier, C. The CyCab: robot podobný autu navigující autonomně a bezpečně mezi chodci // Robotics and Autonomous Systems: journal. - 2005. - Sv. 50 , č. 1 . — S. 51——68 . - doi : 10.1016/j.robot.2004.10.002 .
↑ Ferreira, J.; Lobo, J.; Bessière, P.; Castelo Branco, M.; Dias, J. Bayesian Framework for Active Artificial Perception // IEEE Transactions on Systems, IEEE Transactions on Systems, Man, and Cybernetics, Part B: journal. - 2012. - Sv. 99 . — S. 1——13 .
↑ Ferreira, JF; Dias, JM Pravděpodobnostní přístupy k robotickému vnímání . — Springer, 2014.
↑ Mekhnacha, K.; Mazer, E.; Bessière, P. Návrh a implementace bayesovského CAD modeláře pro robotické aplikace (anglicky) // Advanced Robotics : journal. - 2001. - Sv. 15 , č. 1 . — S. 45——69 . doi : 10.1163 / 156855301750095578
↑ Coue, C.; Pradalier, C.; Laugier, C.; Fraichard, T.; Bessière, P. Bayesian Occupancy Filtering for Multitarget Tracking: an Automotive Application // International Journal of Robotics Research : deník. - 2006. - Sv. 25 , č. 1 . — S. 19——30 . - doi : 10.1177/0278364906061158 .
↑ Vasudevan, S.; Siegwart, R. Bayesovská prostorová konceptualizace a klasifikace míst pro sémantické mapy v mobilní robotice // Robotika a autonomní systémy : časopis. - 2008. - Sv. 56 , č. 6 . - str. 522--537 . - doi : 10.1016/j.robot.2008.03.005 .
↑ Perrin, X.; Chavarriaga, R.; Colas, F.; Seigwart, R.; Millan, J. Brain-coupled interakce pro semi-autonomní navigaci asistenčního robota // Robotics and Autonomous Systems: journal. - 2010. - Sv. 58 , č. 12 . - S. 1246--1255 . - doi : 10.1016/j.robot.2010.05.010 .
↑ Rett, J.; Dias, J.; Ahuactzin, JM. Bayesovské uvažování pro analýzu pohybu Labana používanou v interakci člověk-stroj // Int . J. of Reasoning-based Intelligent Systems: journal. - 2010. - Sv. 2 , ne. 1 . — S. 13——35 . - doi : 10.1504/IJRIS.2010.029812 .
↑ Möbus, C.; Eilers, M.; Garbe, H. & Zilinski, M. (2009), Pravděpodobnostní a empiricky zakotvené modelování agentů v (částečných) scénářích kooperativního provozu , v Duffy, Vincent G., Digitální modelování člověka , Poznámky k přednáškám z informatiky, svazek 5620, Second International konference, ICDHM 2009, San Diego, CA, USA: Springer, str. 423-432, ISBN 978-3-642-02808-3 , doi : 10.1007/978-3-642-02809-0_45 Archivováno 11. června 2018 na Wayback Machine
↑ Möbus, C. & Eilers, M. (2009), Další kroky k modelování řidičů podle bayesovského programovacího přístupu , v Duffy, Vincent G., Digital Human Modeling , Lecture Notes in Computer Science, Volume 5620, Second International Conference, ICDHM 2009, San Diego, CA, USA: Springer, s. 413-422, ISBN 978-3-642-02808-3 , doi : 10.1007/978-3-642-02809-0_44 Archivováno 10. června 2018 na Wayback Machine
↑ Eilers, M.; Möbus, C. (2010). „Lernen eines modularen Bayesian Autonomous Driver Mixture-Behaviors Modells (BAD MoB) Modells“ (PDF) . V Kolrep, H.; Jurgensohn, Th. Fahrermodellierung - Zwischen kinematischen Menschmodellen und dynamisch-kognitiven Verhaltensmodellen . Fortschrittsbericht des VDI in der Reihe 22 (Mensch-Maschine-Systeme). Düsseldorf, Německo: VDI-Verlag. str. 61–74. ISBN 978-3-18-303222-8 . Archivováno 3. února 2014 na Wayback Machine
↑ Möbus, C.; Eilers, M. Handbook of Research on Ambient Intelligence and Smart Environments: Trends and Perspectives / Mastrogiovanni, F.; Chong, N.-Y.. - Hershey, Pennsylvania (USA): IGI Global publishings, 2011. - S. 460-512. — ISBN 9781616928575 . - doi : 10.4018/978-1-61692-857-5.ch023 .
↑ Eilers, M.; Möbus, C. (2011). „Naučení se relevantních vjemů modulárních hierarchických bayesovských modelů ovladačů pomocí bayesovského informačního kritéria.“ V Duffy, VG Digitální modelování člověka . LNCS 6777. Heidelberg, Německo: Springer. str. 463-472. DOI : 10.1007/978-3-642-21799-9_52 . ISBN 978-3-642-21798-2 .
↑ Eilers, M.; Möbus, C. (2011). „Učení Bayesovského modelu směsi chování autonomních řidičů (BAD-MoB)“ . V Duffy, VG pokroky v aplikovaném digitálním modelování člověka . LNCS 6777. Boca Raton, USA: CRC Press, Taylor & Francis Group. str. 436-445. ISBN 978-1-4398-3511-1 . Archivováno 1. února 2014 na Wayback Machine
↑ Le Hy, R.; Arrigoni, A.; Bessière, P.; Lebetel, O. Teaching Bayesian Behaviors to Videoher Characters // Robotika a autonomní systémy: časopis. - 2004. - Sv. 47 , č. 2-3 . - str. 177--185 . - doi : 10.1016/j.robot.2004.03.012 .
↑ Synnaeve, G. Bayesian Programming and Learning for Multiplayer Video Games . — 2012.
↑ Colas, F.; Droulez, J.; Wexler, M.; Bessière, P. Jednotný pravděpodobnostní model vnímání trojrozměrné struktury z optického toku // Biologická kybernetika : časopis. - 2008. - S. 132--154 .
↑ Laurens, J.; Droulez, J. Bayesovské zpracování vestibulární informace // Biologická kybernetika. - 2007. - Sv. 96 , č. 4 . - str. 389--404 . - doi : 10.1007/s00422-006-0133-1 .
↑ Colas, F.; Flacher, F.; Tanner, T.; Bessière, P.; Girard, B. Bayesovské modely výběru pohybu očí s retinotopickými mapami (anglicky) // Biological Cybernetics : journal. - 2009. - Sv. 100 , č. 3 . — S. 203——214 . - doi : 10.1007/s00422-009-0292-y .
↑ Serkhane, J.; Schwartz, JL.; Bessière, P. Stavba mluvícího dětského robota Příspěvek ke studiu získávání řeči a evoluce // Interaction Studies : journal. - 2005. - Sv. 6 , č. 2 . - str. 253--286 . - doi : 10.1075/is.6.2.06ser .
↑ Moulin-Frier, C.; Laurent, R.; Bessière, P.; Schwartz, JL.; Diard, J. Nepříznivé podmínky zlepšují rozlišitelnost sluchových, motorických a percepčně-tuo-motorických teorií vnímání řeči: průzkumná bayesovská modelovací studie // Language and Cognitive Processes : journal. - 2012. - Sv. 27 , č. 7-8 . — S. 1240——1263 . - doi : 10.1080/01690965.2011.645313 .
↑ Gilet, E.; Diard, J.; Bessière, P. Bayesian Action–Perception Computational Model: Interaction of Production and Recognition of Cursive Letters (anglicky) // PLOS One : journal / Sporns, Olaf. - 2011. - Sv. 6 , č. 6 . — P.e20387 . - doi : 10.1371/journal.pone.0020387 . - .
↑ Nový algoritmus pomáhá strojům učit se stejně rychle jako lidé . www.gizmag.com (22. ledna 2016). Datum přístupu: 23. ledna 2016. Archivováno z originálu 24. ledna 2016. (neurčitý)
↑ Zadeh, Lofti, A. Fuzzy sady // Information and Control : deník. - 1965. - Sv. 8 , č. 3 . — S. 338——353 . - doi : 10.1016/S0019-9958(65)90241-X .
↑ Zadeh, Lofti, A. Fuzzy logika a přibližné uvažování // Synthese : deník. - 1975. - Sv. 30 , č. 3——4 . - str. 407-428 . - doi : 10.1007/BF00485052 .
↑ Dubois, D.; Prade, H. Teorie možností, teorie pravděpodobnosti a logiky více hodnot: objasnění // Ann . Matematika. Artif. Intel. : deník. - 2001. - Sv. 32 , č. 1——4 . — S. 35——66 . - doi : 10.1023/A:1016740830286 .
↑ Poole, D. Pravděpodobnostní únos rohů a Bayesovské sítě // Umělá inteligence. - 1993. - Sv. 64 . - str. 81-129 . - doi : 10.1016/0004-3702(93)90061-F .
↑ Poole, D. The Independent Choice Logic pro modelování více agentů za nejistoty // Artficial Intelligence: journal. - 1997. - Sv. 94 . - str. 7-56 . - doi : 10.1016/S0004-3702(97)00027-1 .
↑ Sato, T.; Kameya, Y. Učení parametrů logických programů pro symbolicko-statistické modelování (anglicky) // Journal of Artificial Intelligence Research : deník. - 2001. - Sv. 15 . - str. 391--454 . Archivováno z originálu 12. července 2014.

Literatura

Kamel Mekhnacha. Bayesovské programování . - Chapman a Hall/CRC, 2013. - ISBN 978-1-4398-8032-6 . Bayesovské programování . Chapman a Hall/CRC. ISBN 978-1-4398-8032-6.

Odkaz

Doprovodný web knihy "Bayesian Programming", kde si můžete stáhnout ProBT a inferenční engine. Archivováno z originálu 23. listopadu 2013. (Angličtina)
Bayesian-programming.org Archivováno 23. listopadu 2013. , propagující bayesovské programování, s podrobnými informacemi a četnými publikacemi. (Angličtina)