Bayesiansk programmering

Bayesiansk programmering är ett formellt system och metodik för att definiera probabilistiska modeller och lösa problem när inte all nödvändig information är tillgänglig.

Edwin Thompson Jaynes föreslog att man skulle betrakta sannolikhet som ett alternativ och en förlängning av logik för rationella resonemang med ofullständig och osäker information. I sin framträdande bok The Theory of Probability: The Logic of Science [1] utvecklade han denna teori och föreslog vad han kallade en "robot", som inte var en fysisk anordning, utan en inferensmaskin som automatiserar sannolikhetsresonemang - något i stil med en Prolog för en teoris sannolikheter istället för logik. Bayesiansk programmering [2] är en formell och konkret implementering av denna "robot".

Bayesiansk programmering kan också ses som ett formellt algebraiskt system för att specificera grafmodeller , som till exempel Bayesianska nätverk , dynamiska Bayesianska nätverk Kalman-filter eller dolda Markov-modeller . Faktum är att Bayesiansk programmering generaliserar Bayesianska nätverk och har en uttryckskraft som motsvarar faktorgrafer .

Formella system

Det Bayesianska programmet är ett sätt att specificera en familj av sannolikhetsfördelningar.

Följande är byggstenarna i ett Bayesian-program:

{\text{Program}}{\begin{cases}{\text{Description}}{\begin{cases}{\text{Specification}}(\pi ){\begin{cases}{\text{ Variabler}}\\{\text{Dekomposition}}\\{\text{Former}}\\\end{cases}}\\{\text{Identifiering (baserat på }}\delta )\end{cases}} \\{\text{Fråga}}\end{fall}}

Programmet är byggt av en beskrivning ( engelsk beskrivning ) och en fråga ( engelsk fråga ).
Beskrivningen är byggd med hjälp av någon definition ( , eng. specification ) som ges av programmeraren, och identifiering ( eng. identification ) eller en inlärningsprocess för parametrar som inte är fullständigt beskrivna i definitionen, med hjälp av en datamängd ( ). $\pi$ $\delta$
Definitionen är uppbyggd av en uppsättning signifikanta variabler ( engelska variabler ), dekomponering ( engelska decomposition ) och en uppsättning former ( engelska former ).
Formerna är antingen parametriska former eller frågor till andra Bayesianska program.
Frågan anger vilken sannolikhetsfördelning som ska beräknas.

Beskrivning

Beskrivningen specificerar en effektiv metod för att beräkna den gemensamma sannolikhetsfördelningen för en uppsättning variabler för en given uppsättning experimentella data och en viss definition av . Denna gemensamma fördelning betecknas som . ${\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)$

För att specificera förkunskaper måste programmeraren göra följande: $\pi$

Bestäm uppsättningen av signifikanta variabler , på vilka den gemensamma sannolikhetsfördelningen ges. ${\displaystyle \left\{X_{1},X_{2},\cdots ,X_{N}\right\))$
Bryt upp den gemensamma fördelningen (dela upp den i lämpliga oberoende eller villkorade sannolikheter ).
Bestäm formen för var och en av dessa fördelningar (välj till exempel en från listan över sannolikhetsfördelningar för varje variabel ).

Nedbrytning

Låt uppsättningen innehålla delmängder, variablerna definieras som , som var och en motsvarar en av dessa delmängder. Varje variabel erhålls som en konjunktion av variabler som tillhör den -: e delmängden. En rekursiv tillämpning av Bayes sats leder till ${\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 \ höger)\times P\left(L_{2}\mid L_{1}\wedge \delta \wedge \pi \right)\times \cdots \times P\left(L_{K}\mid L_{K-1 }\wedge \cdots \wedge L_{1}\wedge \delta \wedge \pi \right)\end{aligned}}

Genom att tillämpa hypotesen om villkorligt oberoende kan vi göra ytterligare förenklingar. Den villkorliga oberoendehypotesen för en variabel definieras av valet av någon variabel bland variablerna som finns i konjunktionen . Betecknar med konjunktionen av de valda variablerna och tar ${\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}\ mitten R_{k}\wedge \delta \wedge \pi \right)

Vi får

{\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 \ gånger P\left(L_{K}\mid R_{K}\wedge \delta \wedge \pi \right)\end{aligned}}

Denna förenkling av en gemensam distribution som en produkt av enklare distributioner kallas kedjeregeluppdelning

Detta säkerställer att varje variabel visas till vänster om den villkorliga raden minst en gång, vilket är ett nödvändigt och tillräckligt villkor för att skriva matematiskt korrekta beräkningar. .

Formulär

Varje distribution som förekommer i produkten associeras sedan antingen med en parametrisk form (det vill säga en funktion ) eller med en fråga till ett annat Baysian-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)$

När det är formen , är i allmänhet en vektor av parametrar som kan bero på antingen , eller , eller båda. När några av dessa parametrar beräknas med hjälp av datamängden sker träning. $f_{\mu }\left(L_{k}\right)$ $\mu$ ${\displaystyle R_{k))$ $\delta$ $\delta$

En viktig egenskap hos Bayesiansk programmering är möjligheten att använda frågor till andra Bayesianska program som en del av definitionen av ett nytt Bayesianskt program. erhålls av utdata som produceras av ett annat Bayesian-program givet definitionen och data . Detta liknar att anropa en subrutin i klassisk programmering och ger ett enkelt sätt att bygga hierarkiska modeller . $P\left(L_{k}\mid R_{k}\wedge \delta \wedge \pi \right)$ ${\widehat {\pi ))$ ${\widehat {\delta ))$

Fråga

Låt en beskrivning ges (dvs ), frågan erhålls genom att dela upp den i tre uppsättningar: de undersökta ( eng. sökte ) variablerna, kända ( eng. kända ) variabler och fria ( eng. fria ) variabler. $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\))$

De tre variablerna och definieras som konjunktionen av variablerna som hör till dessa uppsättningar . $Sökte$ $Känd$ $gratis$

En fråga definieras som en uppsättning distributioner

P\left(Searched\mid {\text{Known))\wedge \delta \wedge \pi \right)

sammansatt av "specificerade frågor" som en kardinal , där varje instansierad fråga är en fördelning $Känd$

P\left({\text{Searched}}\mid {\text{Known}}\wedge \delta \wedge \pi \right)

Slutsats

För en given gemensam fördelning är det alltid möjligt att beräkna vilken fråga som helst genom att tillämpa följande generella härledning: $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{Known}}\wedge \delta \wedge \pi \right)\\={}&\sum _{ \text{Fri}}\left[P\left({\text{Searched}}\wedge {\text{Fri}}\mid {\text{Känt}}\wedge \delta \wedge \pi \right)\ höger]\\={}&{\frac {\displaystyle \sum _{\text{Fri}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\wedge { \text{Känt}}\mid \delta \wedge \pi \right)\right]}{\displaystyle P\left({\text{Känt}}\mid \delta \wedge \pi \right)))\\ ={}&{\frac {\displaystyle \sum _{\text{Fri}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\wedge {\text{Känt }}\mid \delta \wedge \pi \right)\right]}{\displaystyle \sum _({\text{Free}}\wedge {\text{Searched}}}\left[P\left({\ text{Searched}}\wedge {\text{Free}}\wedge {\text{Känt}}\mid \delta \wedge \pi \right)\right]}}\\={}&{\frac {1 }{Z}}\times \sum _{\text{Fri}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\wedge {\text{Känt}}\ mid \delta \wedge \pi \right)\right]\end{aligned}}

där den första jämlikheten följer av marginaliseringsregeln , den andra följer av Bayes sats , och den tredje motsvarar den andra tillämpningen av marginalisering. Nämnaren visar sig vara en normaliseringsterm , och den kan ersättas med en konstant . $Z$

Teoretiskt låter detta dig lösa alla problem med Bayesiansk slutledning. Men i praktiken, i nästan alla fall, visar sig kostnaden för en uttömmande och korrekt beräkning vara för stor. $P\left({\text{Searched}}\mid {\text{Known}}\wedge \delta \wedge \pi \right)$

Genom att ersätta fogfördelningen med dess nedbrytning får vi

{\begin{aligned}&P\left({\text{Searched}}\mid {\text{Known}}\wedge \delta \wedge \pi \right)\\={}&{\frac { 1}{Z}}\summa _{\text{Fri}}\left[\prod _{k=1}^{K}\left[P\left(L_{i}\mid K_{i}\wedge \pi \right)\right]\right]\end{aligned}}

vilket vanligtvis är ett uttryck som är mycket enklare att beräkna, eftersom problemets dimension reduceras avsevärt genom nedbrytningen till produkten av fördelningar med lägre dimension.

Exempel

Bayesiansk skräppostdetektering

Målet med Bayesian skräppostfiltrering är att eliminera skräppost.

Formuleringen av detta problem är ganska enkel. E-postmeddelanden bör klassificeras i en av två kategorier: icke-spam och spam. Den enda information som finns tillgänglig för att klassificera e-postmeddelanden är deras innehåll: uppsättningen av ord. Användningen av ord utan att ta hänsyn till deras ordningsföljd i en mening kallas ofta för påsemodellen .

Dessutom måste klassificeraren kunna anpassa sig till sin användare och lära sig av erfarenhet. Med utgångspunkt från standardinställningen måste klassificeraren ändra sina interna parametrar om användaren inte håller med sitt beslut. Den kommer därför att anpassa sig till användarens kriterier för att skilja mellan icke-spam och spam. Det kommer att förbättra sina egna resultat eftersom det möter fler och fler hemligstämplade e-postmeddelanden.

Variabler

Följande variabler krävs för att skriva detta program:

$Spam$ : binär variabel, falsk om e-postmeddelandet inte är skräppost, sant annars.
${\displaystyle W_{0},W_{1},\ldots ,W_{N-1))$ : binära variabler. är sant om det -e ordboksordet finns i texten. $N$ $W_{n}$ $n$

Dessa binära variabler sammanfattar all information om e-postmeddelandet. $N+1$

Nedbrytning

Om vi börjar med definitionen av den gemensamma fördelningen och tillämpar Bayes sats rekursivt får vi:

{\begin{aligned}&P({\text{Spam}}\wedge W_{0}\wedge \cdots \wedge W_{N-1})\\={}&P({\text{Spam} })\times P(W_{0}\mid {\text{Spam)))\times P(W_{1}\mid {\text{Spam))\wedge 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 }}

Detta är ett exakt matematiskt uttryck.

Det kan radikalt förenklas genom att anta att sannolikheten för att ett ord förekommer i en given textkategori (spam eller inte) är oberoende av förekomsten av andra ord. Ett sådant antagande är naivt bayesianskt , och därför är detta spamfilter en naiv bayesiansk modell.

Till exempel kan en programmerare anta det

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

och så småningom få

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)))]

Detta antagande är känt som det naiva Bayes-antagandet . Det är "naivt" i den meningen att oberoende mellan ord uppenbarligen inte är sant. Till exempel försummar den fullständigt det faktum att förekomsten av ett ordpar kan vara mer betydande än isolerade förekomster. Programmeraren kan dock acceptera denna hypotes och kan utveckla denna modell och dess tillhörande utdata för att testa hur tillförlitlig och effektiv den är.

Parametriska former

För att kunna beräkna den gemensamma fördelningen måste programmeraren nu specificera fördelningarna som finns i nedbrytningen: $N+1$

$P({\text{Spam)))$ definieras a priori, till exempel som $P([{\text{Spam}}=1])=0,75$
Var och en av formerna kan specificeras med hjälp av Laplace-regeln (detta är en utjämningsteknik baserad på en pseudoräknare för att övervinna problemet med nollfrekvens av hittills osynliga ord): $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}}}$

var är antalet förekomster av det e ordet i icke-spam-e-postmeddelanden och är det totala antalet icke-spam-e-postmeddelanden. På samma sätt är antalet förekomster av det e ordet i skräppostmeddelanden och är det totala antalet skräppostmeddelanden. ${\displaystyle a_{f}^{n))$ $n$ ${\displaystyle a_{f))$ ${\displaystyle a_{t}^{n))$ $n$ $på}$

Identifiering

$N$ formulär har ännu inte helt definierats eftersom parametrarna , , och ännu inte har värden. $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))$ $på}$

Identifieringen av dessa parametrar kan göras antingen genom att batchbearbeta en grupp av sekretessbelagda e-postmeddelanden, eller genom att stegvis uppdatera parametrarna genom att klassificera e-postmeddelanden av användaren när de anländer.

Båda metoderna kan kombineras: systemet kan börja med initiala standardvärden för dessa parametrar som ges från en generaliserad databas, och sedan passar viss inkrementell inlärning klassificeraren för varje enskild användare.

Fråga

Frågan som ställs till programmet är: "Vad är sannolikheten att denna text är spam, om man vet vilka ord som finns i den och vilka inte?" Det kan formaliseras som

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

som kan räknas ut så här:

{\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}}

I detta uttryck visar sig nämnaren vara normaliseringskonstanten . Det är inte nödvändigt att beräkna det för att ta reda på om vi har att göra med spam. Till exempel, ett enkelt knep för att beräkna ett förhållande:

{\begin{aligned}&{\frac {P([{\text{Spam}}={\text{true}}]\mid w_{0}\wedge \cdots \wedge w_{N-1 })}{P([{\text{Spam}}={\text{falskt}}]\mid w_{0}\wedge \cdots \wedge w_{N-1)))))\\={} & {\frac {P([{\text{Spam}}={\text{true}}])}{P([{\text{Spam}}={\text{false}}])}}\ gånger \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}}

Denna beräkning är snabbare och bekvämare eftersom den bara kräver produkter. $2N$

Bayesianskt program

Det Bayesianska spamfilterprogrammet är helt definierat som

\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{ case}}\\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{Identifiering (baserat på }}\ delta )\end{cases}}\\Qu:P({\text{Spam}}\mid w_{0}\land \ldots \land w_{n}\land \ldots \land w_{N-1}) \end{cases}}

Bayesian filter, Kalman filter och Hidden Markov modell

Bayesianska filter (ofta kallade rekursiv Bayesiansk uppskattning ) är generella probabilistiska modeller för processer som utvecklas över tiden. Många modeller är specialfall av detta allmänna tillvägagångssätt, såsom Kalman-filtret eller den dolda Markov-modellen .

Variabler

Variabler - en tidsserie av tillståndsvariabler som beaktas på tidshorisonten i intervallet från till . ${\displaystyle S^{0},\ldots ,S^{T))$ $0$ $T$
Variabler - en tidsserie av observationsvariabler på samma horisont. ${\displaystyle O^{0},\ldots ,O^{T))$

Nedbrytning

Nedbrytningen baseras på:

$P(S^{t}\mid S^{t-1})$ , kallad systemmodell, övergångsmodell eller dynamisk modell, som formaliserar övergången från ett tillstånd vid en tidpunkt till ett tillstånd vid en tidpunkt ; $t-1$ $t$
$P(O^{t}\mid S^{t})$ , kallad observationsmodellen, som uttrycker vad som kan observeras vid den tidpunkt då systemet är i tillstånd ; $t$ ${\displaystyle S^{t))$
initialt tillstånd vid tidpunkten : . $0$ $P(S^{0}\wedge O^{0})$

Parametriska former

Valet av parametriska former är inte begränsat, och olika alternativ leder till olika välkända modeller: se Kalman-filter och Hidden Markov-modeller nedan.

Fråga

En vanlig fråga för dessa modeller är : vad är sannolikhetsfördelningen för tillståndet vid tidpunkten t givet observationerna från tid till t ? $P\left(S^{t+k}\mid O^{0}\wedge \cdots \wedge O^{t}\right)$ $t+k$ $0$ $t$

Det mest allmänna fallet är Bayesisk filtrering, för vilket , vilket innebär att tillståndet för närvarande bestäms med kända tidigare observationer. $k=0$

Det är dock också möjligt att extrapolera det framtida tillståndet med hjälp av tidigare observationer, eller att utföra utjämning för att rekonstruera det tidigare tillståndet från observationer gjorda antingen före eller efter en viss tidpunkt. $(k>0)$ $(k<0)$

Mer avancerade frågor kan ställas, som visas nedan i avsnittet HMM.

Bayesiska filter har en mycket intressant rekursiv egenskap som i hög grad bidrar till deras attraktionskraft. kan enkelt beräknas med följande formel: $(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}\right)\times \sum _{S^{t-1}}\left[P\left(S^{t}|S^{t-1}\right)\ gånger P\left(S^{t-1}|O^{0}\wedge \cdots \wedge O^{t-1}\right)\right]\end{array}}

Ett annat intressant sätt att se på denna ekvation är att överväga förekomsten av två faser: förväntningsfasen och utvärderingsfasen:

Under prediktionsfasen förutsägs tillståndet med hjälp av en dynamisk modell och en uppskattning av tillståndet i föregående ögonblick:

{\begin{array}{ll}&P\left(S^{t}|O^{0}\wedge \cdots \wedge O^{t-1}\right)\\=&\summa _ {S^{t-1}}\left[P\left(S^{t}|S^{t-1}\right)\ gånger P\left(S^{t-1}|O^{0 }\wedge \cdots \wedge O^{t-1}\right)\right]\end{array}}

Under utvärderingsfasen bekräftas eller ogiltigförklaras förutsägelsen av den senaste observationen:

{\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 }}

Bayesianskt 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)\ gånger 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 )\\\left(k=0\right)\equiv {\text{Filterering}}\\\left(k>0\right)\equiv {\text{Prediction}}\\\left(k<0\ höger)\equiv {\text{Smoothing}}\end{array}}\end{cases}}\end{cases}}

Kalman filter

De välkända Kalmanfiltren [3] är ett specialfall av Bayesianska filter.

De ges av följande Bayesianska 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 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)\ gånger P\left(O^{t}|S^{t}\wedge \pi \ höger)\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} }

Variablerna är kontinuerliga.
Övergångs- och observationsmönstren definieras med en Gauss-fördelning , där medelvärdena är linjära funktioner av tillståndsvariablerna. $P(S^{t}\mid S^{t-1}\wedge \pi )$ $P(O^{t}\mid S^{t}\wedge \pi )$

Med hjälp av dessa hypoteser och en rekursiv formel kan slutledningsproblemet för att besvara en vanlig fråga lösas analytiskt. Detta resulterar i en extremt effektiv algoritm, som förklarar populariteten för Kalman-filter och deras många vardagliga applikationer. $P(S^{T}\mid O^{0}\wedge \cdots \wedge O^{T}\wedge \pi )$

När det inte finns några uppenbara linjära övergångs- och observationsmodeller är det ofta fortfarande möjligt, genom att tillämpa en första ordningens Taylor-expansion , att betrakta dessa modeller som linjära lokalt. Denna generalisering brukar kallas det utökade Kalman-filtret .

Dold Markov-modell

Hidden Markov Models (HMMs) är ett annat mycket populärt specialfall av Kalman-filter.

De ges av följande Bayesianska program:

\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{fall}}\\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]\ slut{cases}}

Variabler anses vara diskreta.
Övergångs- och observationsmodeller specificeras med hjälp av sannolikhetsmatriser. $P\left(S^{t}\mid S^{t-1}\wedge \pi \right)$ $P\left(O^{t}\mid S^{t}\wedge \pi \right)$
Frågan som oftast ställs till Hidden Markov Models är:

\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]

Vilken är den mest sannolika sekvensen av tillstånd som leder till det nuvarande tillståndet, givet tidigare observationer?

Svaret på denna fråga kan erhållas genom en mycket effektiv algoritm - Viterbi-algoritmen .

Den Baum-Welsh-algoritmen utvecklades också för HMM .

Applikation

Akademiska ansökningar

Under de senaste 15 åren har Bayesiansk programmering använts vid många universitet för att utveckla både tillämpningar inom robotik och modeller inom biovetenskap [4] .

Robotics

Inom robotteknik har Bayesiansk programmering tillämpats inom autonom robotik [5] [6] [7] [8] [9] , robotiska CAD-system [10] , avancerade förarassistanssystem [11] , robotstyrning av manipulatorer , mobil robotik [12] [13] , interaktion mellan människa och robot [14] , interaktion mellan människor och fordon (bayesianska autonoma förarmodeller) [15] [16] [17] [18] [19] [20 ] , programmering och inlärning av avatarer i videospel [21] och strategispel i realtid ( AI ). [22]

Livsvetenskap

Inom biovetenskapen har Bayesiansk programmering använts inom synvetenskaperna för att rekonstruera form från rörelse [23] , för att modellera visuell-vestibulär interaktion [24] och för att studera saccadisk ögonrörelse [25] ; i uppfattningen och kontrollen av tal för att studera den tidiga assimileringen av tal [26] och uppkomsten av artikulära-akustiska system [27] ; för modellering av uppfattningen och kontrollen av handskriven text [28] .

Mönsterigenkänning

Bayesiansk programmering har potentiella tillämpningar inom taligenkänning och -syntes , bildigenkänning och naturligt språkbehandling . Här används principerna för kompositabilitet (att bygga abstrakta representationer från delar), kausalitet (bygga komplex från delar) och lära sig att lära (använda tidigare erkända begrepp för att underlätta skapandet av nya begrepp) [29] .

Bayesiansk programmering och möjlighetsteori

Jämförelsen mellan probabilistiska tillvägagångssätt (inte bara Bayesiansk programmering) och möjlighetsteorier fortsätter att vara en diskussionsfråga.

Möjlighetsteorier som till exempel fuzzy mängder [30] , fuzzy logic [31] och möjlighetsteorin i sig [32] erbjuder olika alternativ för att modellera osäkerhet med hjälp av sannolikhet. De hävdar att sannolikheten är otillräcklig eller obekväm för att modellera vissa aspekter av ofullständig eller osäker kunskap.

Försvaret av den probabilistiska ansatsen bygger huvudsakligen på Cox' teorem , som består av fyra postulat angående rationellt resonemang under osäkerhet. Den visar att den enda matematiska modellen som uppfyller dessa postulat är sannolikhetsteorin. Beviset är att något annat tillvägagångssätt än sannolikhetsteori bryter mot ett av dessa postulat.

Bayesiansk programmering och probabilistisk programmering

Målet med probabilistisk programmering är att kombinera sfären av klassiska programmeringsspråk med probabilistisk modellering (särskilt Bayesianska nätverk ) för att kunna hantera osäkerhet och samtidigt använda programmeringsspråkens uttryckskraft för att beskriva komplexa modeller.

Utökade klassiska programmeringsspråk inkluderar logiska språk, som föreslagits i Probabilistic Horn Abduction [ 33 ] , Independent Choice Logic [34] , PRISM [35] och ProbLog Prolog-språket .

Det kan också vara en förlängning av funktionella programmeringsspråk (i huvudsak LISP och Scheme ) som IBAL eller Church . De underliggande språken i tillägget kan också vara objektorienterade , som i fallet BLOG och FACTORIE, eller mer standard, som i CES och FIGARO Arkiverad 1 februari 2016 på Wayback Machine .

Syftet med Bayesiansk programmering är något annorlunda. Jaynes position "sannolikhet som logik" hävdar att sannolikhet är en förlängning och ett alternativ till logik, på vilken hela teorin om rationalitet, algoritmer och programmering kan byggas om [1] . Bayesiansk programmering letar inte efter ett sätt att utvidga klassiska språk, den försöker ersätta dem med ett nytt förhållningssätt till sannolikhetsbaserad programmering som tar hänsyn till ofullständighet och osäkerhet.

En exakt jämförelse av semantiken och uttryckskraften hos Bayesiansk och probabilistisk programmering är fortfarande en öppen fråga.

Se även

Anteckningar

↑ 1 2 Jaynes, Edwin T. Sannolikhetsteori: Vetenskapens logik . - Cambridge University Press , 2003. - ISBN 0-521-59271-2 .
↑ Bessière, P.; Mazer, E.; Ahuactzin, JM.; Mekhnacha, K. Bayesiansk programmering . - Chapman & Hall/CRC, 2013. - ISBN 9781439880326 .
↑ Kalman, RE Ett nytt tillvägagångssätt för linjära filtrerings- och prediktionsproblem // Transaktioner av ASME--Journal of Basic Engineering: journal. - 1960. - Vol. 82 . — S. 33——45 . - doi : 10.1115/1.3662552 .
↑ Bessière, P.; Laugier, C. & Siegwart, R. Probabilistiska resonemang och beslutsfattande i sensoriska-motoriska system . — Springer, 2008. - ISBN 978-3-540-79007-5 .
↑ Lebeltel, O.; Bessière, P.; Diard, J.; Mazer, E. Bayesian Robot Programming (engelska) // Advanced Robotics. - 2004. - Vol. 16 , nr. 1 . — S. 49——79 . - doi : 10.1023/b:auro.0000008671.38949.43 .
↑ Diard, J.; Gilet, E.; Simonin, E.; Bessière, P. Inkrementell inlärning av Bayesianska sensorimotoriska modeller: från lågnivåbeteenden till storskalig struktur av miljön // Connection Science: journal. - 2010. - Vol. 22 , nr. 4 . - S. 291--312 . - doi : 10.1080/09540091003682561 .
↑ Pradalier, C.; Hermosillo, J.; Koike, C.; Braillon, C.; Bessière, P.; Laugier, C. CyCab: en billiknande robot som navigerar autonomt och säkert bland fotgängare // Robotics and Autonomous Systems : journal. - 2005. - Vol. 50 , nej. 1 . — S. 51——68 . - doi : 10.1016/j.robot.2004.10.002 .
↑ Ferreira, J.; Lobo, J.; Bessière, P.; Castelo Branco, M.; Dias, J. A Bayesian Framework for Active Artificiell Perception // IEEE Transactions on Systems, IEEE Transactions on Systems, Man, and Cybernetics, Del B : tidskrift. - 2012. - Vol. 99 . — S. 1——13 .
↑ Ferreira, JF; Dias, JM Probabilistiska tillvägagångssätt för robotuppfattning . — Springer, 2014.
↑ Mekhnacha, K.; Mazer, E.; Bessière, P. Utformningen och implementeringen av en Bayesiansk CAD-modellerare för robotapplikationer (engelska) // Advanced Robotics : journal. - 2001. - Vol. 15 , nr. 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 : journal. - 2006. - Vol. 25 , nr. 1 . — S. 19——30 . - doi : 10.1177/0278364906061158 .
↑ Vasudevan, S.; Siegwart, R. Bayesiansk rymdkonceptualisering och platsklassificering för semantiska kartor i mobil robotik // Robotics and Autonomous Systems : journal. - 2008. - Vol. 56 , nr. 6 . - S. 522--537 . - doi : 10.1016/j.robot.2008.03.005 .
↑ Perrin, X.; Chavarriaga, R.; Colas, F.; Seigwart, R.; Millan, J. Hjärnkopplad interaktion för semi-autonom navigering av en hjälprobot // Robotics and Autonomous Systems : journal. - 2010. - Vol. 58 , nr. 12 . - P. 1246--1255 . - doi : 10.1016/j.robot.2010.05.010 .
↑ Rett, J.; Dias, J.; Ahuactzin, JM. Bayesian resonemang för Laban Movement Analysis som används i människa-maskin interaktion // Int . J. of Reasoning-based Intelligent Systems: journal. - 2010. - Vol. 2 , nr. 1 . — S. 13——35 . - doi : 10.1504/IJRIS.2010.029812 .
↑ Möbus, C.; Eilers, M.; Garbe, H. & Zilinski, M. (2009), Probabilistic and Empirical Grounded Modeling of Agents in (Partial) Cooperative Traffic Scenarios , i Duffy, Vincent G., Digital Human Modeling , Lecture Notes in Computer Science, Volym 5620, Second International Conference, ICDHM 2009, San Diego, CA, USA: Springer, sid. 423-432, ISBN 978-3-642-02808-3 , doi : 10.1007/978-3-642-02809-0_45 Arkiverad 11 juni 2018 på Wayback Machine
↑ Möbus, C. & Eilers, M. (2009), Further Steps Towards Driver Modeling enligt Bayesian Programming Approach , i Duffy, Vincent G., Digital Human Modeling , Lecture Notes in Computer Science, Volym 5620, Second International Conference, ICDHM 2009, San Diego, CA, USA: Springer, sid. 413-422, ISBN 978-3-642-02808-3 , doi : 10.1007/978-3-642-02809-0_44 Arkiverad 10 juni 2018 på Wayback Machine
↑ Eilers, M.; Möbus, C. (2010). "Lernen eines modularen Bayesian Autonomous Driver Mixture-of-Behaviors (BAD MoB) Modeller" (PDF) . I Kolrep, H.; Jürgensohn, Th. Fahrermodellierung - Zwischen kinematischen Menschmodellen und dynamisch-kognitiven Verhaltensmodellen . Fortschrittsbericht des VDI in der Reihe 22 (Mensch-Maschine-Systeme). Düsseldorf, Tyskland: VDI-Verlag. pp. 61–74. ISBN 978-3-18-303222-8 . Arkiverad 3 februari 2014 på 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 publications, 2011. - P. 460-512. — ISBN 9781616928575 . - doi : 10.4018/978-1-61692-857-5.ch023 .
↑ Eilers, M.; Möbus, C. (2011). "Lär dig de relevanta uppfattningarna om modulära hierarkiska Bayesianska drivrutinsmodeller med hjälp av ett Bayesianskt informationskriterium." I Duffy, VG Digital Human Modeling . LNCS 6777. Heidelberg, Tyskland: Springer. pp. 463-472. DOI : 10.1007/978-3-642-21799-9_52 . ISBN 978-3-642-21798-2 .
↑ Eilers, M.; Möbus, C. (2011). "Lärande av en Bayesian Autonomous Driver Mixture-of-Behaviors (BAD-MoB) Model" . I Duffy, VG framsteg inom tillämpad digital mänsklig modellering . LNCS 6777. Boca Raton, USA: CRC Press, Taylor & Francis Group. pp. 436-445. ISBN 978-1-4398-3511-1 . Arkiverad 1 februari 2014 på Wayback Machine
↑ Le Hy, R.; Arrigoni, A.; Bessière, P.; Lebetel, O. Teaching Bayesian Behaviours to Video Game Characters // Robotics and Autonomous Systems: journal. - 2004. - Vol. 47 , nr. 2-3 . - S. 177--185 . - doi : 10.1016/j.robot.2004.03.012 .
↑ Synnaeve, G. Bayesian programmering och lärande för multiplayer-videospel . — 2012.
↑ Colas, F.; Droulez, J.; Wexler, M.; Bessière, P. En enhetlig probabilistisk modell av uppfattningen av tredimensionell struktur från optiskt flöde // Biological Cybernetics : journal. - 2008. - S. 132--154 .
↑ Laurens, J.; Droulez, J. Bayesiansk bearbetning av vestibulär information // Biologisk cybernetik. - 2007. - Vol. 96 , nr. 4 . - S. 389--404 . - doi : 10.1007/s00422-006-0133-1 .
↑ Colas, F.; Flacher, F.; Tanner, T.; Bessière, P.; Girard, B. Bayesianska modeller för urval av ögonrörelser med retinotopiska kartor (engelska) // Biological Cybernetics : journal. - 2009. - Vol. 100 , nej. 3 . — S. 203——214 . - doi : 10.1007/s00422-009-0292-y .
↑ Serkhane, J.; Schwartz, JL.; Bessière, P. Building a talking baby robot Ett bidrag till studiet av talförvärv och evolution // Interaction Studies : journal. - 2005. - Vol. 6 , nr. 2 . - S. 253--286 . - doi : 10.1075/is.6.2.06ser .
↑ Moulin-Frier, C.; Laurent, R.; Bessière, P.; Schwartz, JL.; Diard, J. Adverse conditions förbättra särskiljbarheten av auditiva, motoriska och percep-tuo-motoriska teorier om taluppfattning: en utforskande Bayesian modelleringsstudie // Language and Cognitive Processes: journal. - 2012. - Vol. 27 , nr. 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 (engelska) // PLOS One : journal / Sporns, Olaf. - 2011. - Vol. 6 , nr. 6 . — P.e20387 . - doi : 10.1371/journal.pone.0020387 . - .
↑ Ny algoritm hjälper maskiner att lära sig lika snabbt som människor . www.gizmag.com (22 januari 2016). Datum för åtkomst: 23 januari 2016. Arkiverad från originalet 24 januari 2016. (obestämd)
↑ Zadeh, Lofti, A. Luddiga uppsättningar // Information och kontroll : journal. - 1965. - Vol. 8 , nr. 3 . — S. 338——353 . - doi : 10.1016/S0019-9958(65)90241-X .
↑ Zadeh, Lofti, A. Luddrig logik och ungefärliga resonemang // Synthese : journal. - 1975. - Vol. 30 , nej. 3——4 . - S. 407--428 . - doi : 10.1007/BF00485052 .
↑ Dubois, D.; Prade, H. Possibility Theory, Probability Theory and Multiple-Valued Logics: A Clarification // Ann . Matematik. Artif. Intel. : journal. - 2001. - Vol. 32 , nr. 1——4 . — S. 35——66 . - doi : 10.1023/A:1016740830286 .
↑ Poole, D. Probabilistic Horn abduction and Bayesian networks // Artificiell intelligens. - 1993. - Vol. 64 . - S. 81-129 . - doi : 10.1016/0004-3702(93)90061-F .
↑ Poole, D. The Independent Choice Logic för modellering av flera agenter under osäkerhet // Artficial Intelligence: journal. - 1997. - Vol. 94 . - S. 7-56 . - doi : 10.1016/S0004-3702(97)00027-1 .
↑ Sato, T.; Kameya, Y. Parameterinlärning av logikprogram för symbolisk-statistisk modellering (engelska) // Journal of Artificial Intelligence Research : journal. - 2001. - Vol. 15 . - S. 391--454 . Arkiverad från originalet den 12 juli 2014.

Litteratur

Kamel Mekhnacha. Bayesiansk programmering . - Chapman och Hall/CRC, 2013. - ISBN 978-1-4398-8032-6 . Bayesiansk programmering . Chapman och Hall/CRC. ISBN 978-1-4398-8032-6.

Länk

Medföljande webbplats för boken "Bayesian Programmering", där du kan ladda ner ProBT och inferensmotorn. Arkiverad från originalet den 23 november 2013. (Engelsk)
Bayesian-programming.org Arkiverad 23 november 2013. , som främjar Bayesiansk programmering, med detaljerad information och många publikationer. (Engelsk)