Programare bayesiană

Programarea bayesiană este un sistem formal și o metodologie pentru definirea modelelor probabilistice și rezolvarea problemelor atunci când nu sunt disponibile toate informațiile necesare.

Edwin Thompson Jaynes a propus să considere probabilitatea ca o alternativă și extensie a logicii pentru raționamentul rațional cu informații incomplete și incerte. În cartea sa fundamentală The Theory of Probability: The Logic of Science [1] , el a dezvoltat această teorie și a propus ceea ce el a numit „robot”, care nu era un dispozitiv fizic, ci o mașină de inferență care automatizează raționamentul probabilistic - ceva de genul unui Prolog pentru o teorie probabilități în loc de logică. Programarea bayesiană [2] este o implementare formală și concretă a acestui „robot”.

Programarea bayesiană poate fi gândită și ca un sistem algebric formal pentru specificarea modelelor de graf , cum ar fi, de exemplu, rețele bayesiene , rețele bayesiene dinamice filtre Kalman sau modele Markov ascunse . Într-adevăr, programarea bayesiană generalizează rețelele bayesiene și are o putere expresivă echivalentă cu graficele factorilor .

Sistem formal

Programul bayesian este un mijloc de specificare a unei familii de distribuții de probabilitate.

Următoarele sunt elementele de bază ale unui program bayesian:

{\text{Program}}{\begin{cases}{\text{Description}}{\begin{cases}{\text{Specificații}}(\pi ){\begin{cases}{\text{ Variabile}}\\{\text{Descompunere}}\\{\text{Forme}}\\\end{cases}}\\{\text{Identificare (pe baza }}\delta )\end{cases}} \\{\text{Întrebare}}\end{cases}}

Programul este construit dintr-o descriere (descriere în limba engleză ) și o întrebare ( întrebare în limba engleză ).
Descrierea este construită folosind o definiție ( , specificație ing. ) dată de programator și identificarea ( ing. identificare ) sau un proces de învățare pentru parametrii care nu sunt complet descriși în definiție, folosind un set de date ( ). $\pi$ $\delta$
Definiția este construită dintr-un set de variabile semnificative (variabile engleze ) , descompunere (descompunere engleză ) și un set de forme ( forme engleze ).
Formele sunt fie forme parametrice, fie întrebări către alte programe bayesiene.
Întrebarea specifică distribuția de probabilitate care trebuie calculată.

Descriere

Descrierea specifică o metodă eficientă pentru calcularea distribuției comune de probabilitate a unui set de variabile pentru un anumit set de date experimentale și o definiție a . Această distribuție comună se notează ca . ${\displaystyle \stanga\{X_{1},X_{2},\cdots,X_{N}\dreapta\))$ $\delta$ $\pi$ $P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)$

Pentru a specifica cunoștințele anterioare , programatorul trebuie să facă următoarele: $\pi$

Determinați setul de variabile semnificative , pe care este dată distribuția de probabilitate comună. ${\displaystyle \stanga\{X_{1},X_{2},\cdots,X_{N}\dreapta\))$
Descompuneți distribuția comună (despărțiți-o în probabilități independente sau condiționate adecvate ).
Determinați forma fiecăreia dintre aceste distribuții (de exemplu, pentru fiecare variabilă, alegeți una din lista de distribuții de probabilitate ).

Descompunere

Fie ca setul să conțină subseturi, variabilele sunt definite ca , fiecare dintre ele corespunde uneia dintre aceste subseturi. Fiecare variabilă se obține ca o conjuncție de variabile aparținând celui de-al -lea submulțime. O aplicare recursivă a teoremei lui Bayes duce la ${\displaystyle \stanga\{X_{1},X_{2},\ldots,X_{N}\dreapta\))$ $K$ $K$ $L_{1},\cdots, L_{K}$ $L_{k)$ $\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 \ dreapta)\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}}

Aplicarea ipotezei independenței condiționate ne permite să facem simplificări suplimentare. Ipoteza de independență condiționată pentru o variabilă este definită prin alegerea unei variabile dintre variabilele prezente în conjuncție . Notând prin conjuncția variabilelor alese și luând $L_{k)$ $X_{{n}}$ $L_{k-1}\wedge \cdots \wedge L_{2}\wedge L_{1)$ $R_{k)$

P\left(L_{k}\mid L_{k-1}\wedge\cdots\wedge L_{1}\wedge\delta\wedge\pi\right)=P\left(L_{k}\ mijlocul R_{k}\wedge \delta \wedge \pi \right)

Primim

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

Această simplificare a unei distribuții comune ca produs al distribuțiilor mai simple se numește descompunere a regulilor în lanț

Acest lucru asigură că fiecare variabilă apare în stânga liniei condiționale cel puțin o dată, ceea ce este o condiție necesară și suficientă pentru a scrie calcule corecte din punct de vedere matematic. .

Formulare

Fiecare distribuție care apare în produs este apoi asociată fie cu o formă parametrică (adică o funcție ), fie cu o întrebare către un alt program baysian . $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)$

Când este forma , este, în general, un vector de parametri care pot depinde fie de , fie de , sau de ambele. Când unii dintre acești parametri sunt calculați folosind setul de date , are loc antrenamentul. $f_{\mu}\left(L_{k}\right)$ $\mu$ $R_{k)$ $\delta$ $\delta$

O caracteristică importantă a programării bayesiene este capacitatea de a folosi întrebări pentru alte programe bayesiene ca parte a definiției unui nou program bayesian. se obține prin rezultatul produs de un alt program bayesian având în vedere definiția și datele . Acest lucru este similar cu apelarea unei subrutine în programarea clasică și oferă o modalitate ușoară de a construi modele ierarhice . $P\left(L_{k}\mid R_{k}\wedge \delta \wedge \pi \right)$ ${\widehat {\pi ))$ ${\widehat {\delta ))$

Întrebare

Să fie dată o descriere (adică ), întrebarea se obține împărțind-o în trei seturi: variabilele investigate ( ing. căutate ), variabilele cunoscute ( ing. cunoscute ) și variabilele libere ( ing. libere ). $P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)$ ${\displaystyle \stanga\{X_{1},X_{2},\cdots,X_{N}\dreapta\))$

Cele trei variabile și sunt definite ca conjuncția variabilelor aparținând acestor mulțimi. $Căutate$ $cunoscut$ $gratuit$

O întrebare este definită ca un set de distribuții

P\left(Căutat\mid {\text {Cunoscut)}\wedge \delta \wedge \pi \right)

compus din „întrebări specificate” ca un cardinal , unde fiecare întrebare instanțiată este o distribuție $cunoscut$

P\left({\text{Căutate}}\mid {\text{Cunoscut}}\wedge \delta \wedge \pi \right)

Concluzie

Pentru o distribuție comună dată , este întotdeauna posibil să se calculeze orice întrebare aplicând următoarea derivație generală: $P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)$

{\begin{aliniat}&P\left({\text{Căutate}}\mid {\text {Cunoscut}}\wedge \delta \wedge \pi \right)\\={}&\sum _{ \text{Free}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\mid {\text{Known}}\wedge \delta \wedge \pi \right)\ dreapta]\\={}&{\frac {\displaystyle \sum _{\text{Free}}\left[P\left({\text{Căutate}}\wedge {\text{Free}}\wedge { \text{Cunoscut}}\mid \delta \wedge \pi \right)\right]}{\displaystyle P\left({\text{Cunoscut}}\mid \delta \wedge \pi \right)))\\ ={}&{\frac {\displaystyle \sum _{\text{Free}}\left[P\left({\text{Căutate}}\wedge {\text{Free}}\wedge {\text{Cunoscut }}\mid \delta \wedge \pi \right)\right]}{\displaystyle \sum _({\text{Free}}\wedge {\text{Căutate}}}\left[P\left({\ text{Căutat}}\wedge {\text{Free}}\wedge {\text{Cunoscut}}\mid \delta \wedge \pi \right)\right]}}\\={}&{\frac {1 }{Z}}\times \sum _{\text{Free}}\left[P\left({\text{Căutate}}\wedge {\text{Free}}\wedge {\text{Cunoscut}}\ mid \delta \wedge \pi \right)\right]\end{aliniat}}

unde prima egalitate rezultă din regula marginalizării , a doua rezultă din teorema lui Bayes , iar a treia corespunde celei de-a doua aplicații a marginalizării. Numitorul se dovedește a fi un termen de normalizare și poate fi înlocuit cu o constantă . $Z$

Teoretic, acest lucru vă permite să rezolvați orice problemă de inferență bayesiană. Cu toate acestea, în practică, în aproape toate cazurile, costul unui calcul exhaustiv și precis se dovedește a fi prea mare. $P\left({\text{Căutate}}\mid {\text{Cunoscut}}\wedge \delta \wedge \pi \right)$

Înlocuind distribuția comună cu descompunerea ei, obținem

{\begin{aliniat}&P\left({\text{Căutate}}\mid {\text{Cunoscut}}\wedge \delta \wedge \pi \right)\\={}&{\frac { 1}{Z}}\sum _{\text{Free}}\left[\prod _{k=1}^{K}\left[P\left(L_{i}\mid K_{i}\wedge \pi \right)\right]\right]\end{aliniat}}

care este de obicei o expresie mult mai simplu de calculat, deoarece dimensiunea problemei este redusă semnificativ prin descompunerea în produsul distribuțiilor de dimensiune inferioară.

Exemplu

Detectarea spam-ului bayesian

Scopul filtrării spam-ului Bayesian este de a elimina e-mailurile nedorite.

Formularea acestei probleme este destul de simplă. E-mailurile trebuie clasificate în una din două categorii: non-spam și spam. Singura informație disponibilă pentru a clasifica e-mailurile este conținutul acestora: setul de cuvinte. Utilizarea cuvintelor fără a ține cont de ordinea lor într-o propoziție este adesea denumită modelul sacului de cuvinte .

În plus, clasificatorul trebuie să fie capabil să se adapteze utilizatorului său și să învețe din experiență. Pornind de la setarea inițială standard, clasificatorul trebuie să-și modifice parametrii interni dacă utilizatorul nu este de acord cu decizia sa. Prin urmare, se va adapta criteriilor utilizatorului pentru a face distincția între non-spam și spam. Își va îmbunătăți propriile rezultate pe măsură ce întâlnește tot mai multe e-mailuri clasificate.

Variabile

Următoarele variabile sunt necesare pentru a scrie acest program:

$Spam$ : variabilă binară, false dacă e-mailul nu este spam, adevărat în caz contrar.
$W_{0},W_{1},\ldots,W_{N-1)$ : variabile binare. este adevărat dacă în text este prezent al-lea cuvânt din dicționar. $N$ $W_{n}$ $n$

Aceste variabile binare rezumă toate informațiile despre e-mail. $N+1$

Descompunere

Începând cu definirea distribuției comune și aplicând recursiv teorema lui Bayes , obținem:

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

Aceasta este o expresie matematică exactă.

Poate fi simplificat radical presupunând că probabilitatea ca un cuvânt să apară într-o anumită categorie de text (spam sau nu) este independentă de apariția altor cuvinte. O astfel de presupunere este naiv bayesian și, prin urmare, acest filtru de spam este un model bayesian naiv .

De exemplu, un programator ar putea presupune asta

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

și până la urmă obține

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

Această ipoteză este cunoscută sub numele de ipoteza Naive Bayes . Este „naiv” în sensul că independența dintre cuvinte nu este, evident, adevărată. De exemplu, neglijează complet faptul că apariția unei perechi de cuvinte poate fi mai semnificativă decât aparițiile izolate. Cu toate acestea, programatorul poate accepta această ipoteză și poate dezvolta acest model și rezultatul asociat pentru a testa cât de fiabil și eficient este.

Forme parametrice

Pentru a putea calcula distribuția comună, programatorul trebuie să specifice acum distribuțiile prezente în descompunere: $N+1$

$P({\text{Spam)})$ definit a priori, de exemplu, ca $P([{\text{Spam}}=1])=0,75$
Fiecare dintre forme poate fi specificată folosind regula Laplace (aceasta este o tehnică de netezire bazată pe un pseudo contor pentru a depăși problema frecvenței zero a cuvintelor nevăzute până acum): $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}}}$

unde este numărul de apariții ale celui de-al treilea cuvânt în e-mailurile non-spam și este numărul total de e-mailuri non-spam. În mod similar, este numărul de apariții ale celui de-al treilea cuvânt în e-mailurile spam și este numărul total de e-mailuri spam. $a_{f}^{n)$ $n$ $a_{f)$ $a_{t}^{n)$ $n$ $la}$

Identificare

$N$ formele nu au fost încă complet definite deoarece parametrii , , și nu au încă valori. $P(W_{n}\mid {\text{Spam})}$ $2N+2$ $a_{f}^{n=0,\ldots, N-1)$ $a_{t}^{n=0,\ldots, N-1)$ $a_{f)$ $la}$

Identificarea acestor parametri se poate face fie prin procesarea în lot a unui grup de e-mailuri clasificate, fie prin actualizarea progresivă a parametrilor prin clasificarea e-mailurilor de către utilizator pe măsură ce sosesc.

Ambele metode pot fi combinate: sistemul poate începe cu valorile implicite inițiale ale acestor parametri date dintr-o bază de date generalizată, iar apoi o anumită învățare incrementală se potrivește clasificatorului pentru fiecare utilizator individual.

Întrebare

Întrebarea care i se pune programului este: „care este probabilitatea ca acest text să fie spam, dacă se știe ce cuvinte sunt prezente în el și care nu?” Poate fi oficializat ca

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

care se poate calcula astfel:

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

În această expresie, numitorul se dovedește a fi constanta de normalizare . Nu este necesar să-l calculăm pentru a afla dacă avem de-a face cu spam. De exemplu, un truc simplu pentru a calcula un raport:

{\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{fals}}])}}\ ori \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}}

Acest calcul este mai rapid și mai convenabil deoarece necesită doar produse. $2N$

program bayesian

Programul Bayesian de filtrare a spamului este complet definit ca

\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{ cazuri}}\\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{Identificare (pe baza }}\ delta )\end{cases}}\\Qu:P({\text{Spam}}\mid w_{0}\land \ldots \land w_{n}\land \ldots \land w_{N-1}) \end{cazuri}}

Filtru bayesian, filtru Kalman și model Hidden Markov

Filtrele bayesiene (deseori denumite estimare Bayesiană recursivă ) sunt modele probabilistice generale pentru procese care se desfășoară în timp. Numeroase modele sunt cazuri speciale ale acestei abordări generale, cum ar fi filtrul Kalman sau modelul Markov ascuns .

Variabile

Variabile - o serie temporală de variabile de stare care sunt luate în considerare pe orizontul de timp în intervalul de la până la . $S^{0},\ldots, S^{T)$ $0$ $T$
Variabile - o serie temporală de variabile de observație pe același orizont. $O^{0},\ldots, O^{T)$

Descompunere

Descompunerea se bazează pe:

$P(S^{t}\mid S^{t-1})$ , numit model de sistem, model de tranziție sau model dinamic, care formalizează tranziția de la o stare la un moment dat la o stare la un moment dat ; $t-1$ $t$
$P(O^{t}\mid S^{t})$ , numit model de observație, care exprimă ceea ce poate fi observat în momentul în care sistemul este în stare ; $t$ $S^{t)$
starea initiala la timp : . $0$ $P(S^{0}\wedge O^{0})$

Forme parametrice

Alegerea formelor parametrice nu este limitată, iar opțiunile diferite duc la diferite modele binecunoscute: vezi mai jos filtrele Kalman și modelele Hidden Markov.

Întrebare

O întrebare comună pentru aceste modele este : care este distribuția de probabilitate a stării la momentul t având în vedere observațiile de la timp la t ? $P\left(S^{t+k}\mid O^{0}\wedge \cdots \wedge O^{t}\right)$ $t+k$ $0$ $t$

Cel mai general caz este filtrarea bayesiană, pentru care , ceea ce înseamnă că starea la momentul actual este determinată cu observații anterioare cunoscute. $k=0$

Cu toate acestea, este, de asemenea, posibil să se extrapoleze starea viitoare folosind observații din trecut sau să se efectueze netezire pentru a reconstrui starea trecută din observațiile făcute fie înainte, fie după un anumit moment în timp. $(k>0)$ $(k<0)$

Pot fi adresate întrebări mai avansate, așa cum se arată mai jos în secțiunea HMM.

Filtrele bayesiene au o proprietate recursivă foarte interesantă care contribuie foarte mult la atractivitatea lor. poate fi calculat simplu folosind următoarea formulă: $(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)\ ori P\left(S^{t-1}|O^{0}\wedge \cdots \wedge O^{t-1}\right)\right]\end{array}}

Un alt mod interesant de a privi această ecuație este să luăm în considerare existența a două faze: faza de anticipare și faza de evaluare:

În timpul fazei de predicție, starea este prezisă folosind un model dinamic și o estimare a stării din momentul anterior:

{\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)\time P\left(S^{t-1}|O^{0 }\wedge \cdots \wedge O^{t-1}\right)\right]\end{array}}

În timpul fazei de evaluare, predicția este fie confirmată, fie invalidată de ultima observație:

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

program bayesian

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}\stânga[P\stânga(S^{t}|S^{t-1}\dreapta)\ori P\left(O^{t}|S^{t}\dreapta)\dreapta]\ 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{Filtrare}}\\\left(k>0\right)\equiv {\text{Predicție}}\\\left(k<0\ dreapta)\equiv {\text{Netezire}}\end{array}}\end{cases}}\end{cases}}

Filtru Kalman

Cunoscutele filtre Kalman [3] sunt un caz special de filtre bayesiene.

Ele sunt date de următorul program bayesian:

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)\times P\left(O^{t}|S^{t}\wedge \pi \ dreapta)\right]\end{matrice}}\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} }

Variabilele sunt continue.
Modelele de tranziție și observație sunt definite folosind o distribuție Gaussiană , în care mediile sunt funcții liniare ale variabilelor de condiție. $P(S^{t}\mid S^{t-1}\wedge \pi )$ $P(O^{t}\mid S^{t}\wedge \pi )$

Folosind aceste ipoteze și o formulă recursivă, problema de inferență pentru a răspunde la o întrebare comună poate fi rezolvată analitic. Acest lucru are ca rezultat un algoritm extrem de eficient, care explică popularitatea filtrelor Kalman și numeroasele lor aplicații de zi cu zi. $P(S^{T}\mid O^{0}\wedge \cdots \wedge O^{T}\wedge \pi )$

Atunci când nu există modele evidente de tranziție și observație liniare, este adesea posibil, prin aplicarea unei expansiuni Taylor de ordinul întâi , să se considere aceste modele ca fiind liniare local. Această generalizare este de obicei numită filtru Kalman extins .

Modelul Markov ascuns

Modelele Markov ascunse (HMM) sunt un alt caz special foarte popular de filtre Kalman.

Ele sunt date de următorul program bayesian:

\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)\time 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{Matrice}}\\P\left(O^{t}\mid S^{t}\wedge \pi \right)\equiv {\text{Matrice}}\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]\ sfârșit{cazuri}}

Variabilele sunt considerate discrete.
Modelele de tranziție și observație sunt specificate folosind matrice de probabilitate. $P\left(S^{t}\mid S^{t-1}\wedge \pi \right)$ $P\left(O^{t}\mid S^{t}\wedge \pi \right)$
Întrebarea adresată cel mai des modelelor Markov ascunse este:

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

Care este cea mai probabilă secvență de stări care duc la starea actuală, având în vedere observațiile din trecut?

Raspunsul la aceasta intrebare poate fi obtinut printr-un algoritm foarte eficient - algoritmul Viterbi .

De asemenea, algoritmul Baum-Welsh a fost dezvoltat pentru HMM .

Aplicație

Aplicații academice

În ultimii 15 ani, programarea bayesiană a fost aplicată în multe universități pentru a dezvolta atât aplicații în robotică , cât și modele în științele vieții [4] .

Robotică

În robotică, programarea bayesiană a fost aplicată în robotica autonomă [5] [6] [7] [8] [9] , sisteme CAD robotizate [10] , sisteme avansate de asistență a șoferului [11] , control robotic al manipulatoarelor , robotică mobilă [12] [13] , interacțiune om-robot [14] , interacțiune om-vehicul (modele Bayesian de șofer autonom) [15] [16] [17] [18] [19] [20 ] , programarea și învățarea avatarurilor în jocuri video [21] și jocuri de strategie în timp real ( AI ). [22]

Științe ale vieții

În științele vieții, programarea bayesiană a fost folosită în științele vederii pentru a reconstrui forma din mișcare [23] , pentru a modela interacțiunea vizual-vestibulară [24] , și pentru a studia mișcarea sacadică a ochiului [25] ; în percepția și controlul vorbirii pentru a studia asimilarea timpurie a vorbirii [26] și apariția sistemelor articularo-acustice [27] ; pentru modelarea percepției și controlului textului scris de mână [28] .

Recunoașterea modelelor

Programarea bayesiană are aplicații potențiale în recunoașterea și sinteza vorbirii , recunoașterea imaginilor și procesarea limbajului natural . Aici folosește principiile composabilitatii (construirea reprezentărilor abstracte din părți), cauzalității (construirea complexului din părți) și învățarea de a învăța (folosind concepte recunoscute anterior pentru a facilita crearea de noi concepte) [29] .

Programarea bayesiană și teoria posibilităților

Comparația dintre abordările probabilistice (nu doar programarea bayesiană) și teoriile posibilităților continuă să fie o chestiune de dezbatere.

Teoriile posibilităților, cum ar fi, de exemplu, mulțimile fuzzy [30] , logica fuzzy [31] și teoria posibilității în sine [32] oferă diverse alternative pentru modelarea incertitudinii folosind probabilitatea. Ei susțin că probabilitatea este insuficientă sau incomodă pentru modelarea anumitor aspecte ale cunoștințelor incomplete sau incerte.

Apărarea abordării probabilistice se bazează în principal pe teorema lui Cox , care constă din patru postulate privind raționamentul rațional în condiții de incertitudine. Ea arată că singurul model matematic care satisface aceste postulate este teoria probabilității. Dovada este că orice altă abordare decât teoria probabilității încalcă unul dintre aceste postulate.

Programare bayesiană și programare probabilistică

Scopul programării probabilistice este de a combina domeniul limbajelor de programare clasice cu modelarea probabilistică (în special rețelele bayesiene ) pentru a putea face față incertitudinii și, în același timp, a utiliza puterea expresivă a limbajelor de programare pentru a descrie complexe. modele.

Limbajele de programare clasice extinse includ limbaje logice, așa cum sunt propuse în Probabilistic Horn Abduction [ 33 ] , Independent Choice Logic [34] , PRISM [35] și ProbLog limbajului Prolog .

Poate fi, de asemenea, o extensie a limbajelor de programare funcționale (în esență LISP și Scheme ) precum IBAL sau Church . Limbile de bază ale extensiei pot fi, de asemenea , orientate pe obiecte , ca în cazul BLOG și FACTORIE, sau mai standard, ca în CES și FIGARO Arhivat 1 februarie 2016 la Wayback Machine .

Scopul programării bayesiene este oarecum diferit. Poziția lui Jaynes „probabilitatea ca logică” susține că probabilitatea este o extensie și o alternativă a logicii, pe deasupra căreia poate fi reconstruită întreaga teorie a raționalității, a algoritmilor și a programării [1] . Programarea bayesiană nu caută o modalitate de a extinde limbajele clasice, ea caută să le înlocuiască cu o nouă abordare a programării bazate pe probabilități care ține cont de incompletitudinea și incertitudinea.

O comparație exactă a semanticii și puterii expresive a programării bayesiene și probabilistice este încă o întrebare deschisă.

Vezi și

Note

↑ 1 2 Jaynes, Edwin T. Teoria probabilității: logica științei . - Cambridge University Press , 2003. - ISBN 0-521-59271-2 .
↑ Bessière, P.; Mazer, E.; Ahuactzin, JM.; Mekhnacha, K. Programare Bayesiană . - Chapman & Hall/CRC, 2013. - ISBN 9781439880326 .
↑ Kalman, RE A New Approach to Linear Filtering and Prediction Problems // Tranzacțiile ASME--Journal of Basic Engineering : journal. - 1960. - Vol. 82 . — P. 33——45 . - doi : 10.1115/1.3662552 .
↑ Bessière, P.; Laugier, C. & Siegwart, R. Raționamentul probabilistic și luarea deciziilor în sistemele senzoriale-motorii . — Springer, 2008. - ISBN 978-3-540-79007-5 .
↑ Lebeltel, O.; Bessière, P.; Diard, J.; Mazer, E. Programarea robotilor Bayesian (engleză) // Robotică avansată. - 2004. - Vol. 16 , nr. 1 . — P. 49——79 . - doi : 10.1023/b:auro.0000008671.38949.43 .
↑ Diard, J.; Gilet, E.; Simonin, E.; Bessière, P. Învățare incrementală a modelelor senzoriomotorii bayesiene: de la comportamentele de nivel scăzut la structura la scară largă a mediului // Connection Science : jurnal. - 2010. - Vol. 22 , nr. 4 . - P. 291--312 . - doi : 10.1080/09540091003682561 .
↑ Pradalier, C.; Hermosillo, J.; Koike, C.; Braillon, C.; Bessière, P.; Laugier, C. CyCab: un robot asemănător mașinii care navighează autonom și în siguranță printre pietoni // Robotică și sisteme autonome : jurnal. - 2005. - Vol. 50 , nr. 1 . — P. 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 Artificial Perception // IEEE Transactions on Systems, IEEE Transactions on Systems, Man, and Cybernetics, Part B : journal. - 2012. - Vol. 99 . — P. 1——13 .
↑ Ferreira, JF; Dias, JM Abordări probabilistice ale percepției robotice . — Springer, 2014.
↑ Mekhnacha, K.; Mazer, E.; Bessière, P. Proiectarea și implementarea unui modelator CAD bayesian pentru aplicații robotice (engleză) // Advanced Robotics : journal. - 2001. - Vol. 15 , nr. 1 . — P. 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 // Jurnalul Internațional de Cercetare în Robotică : jurnal. - 2006. - Vol. 25 , nr. 1 . — P. 19——30 . - doi : 10.1177/0278364906061158 .
↑ Vasudevan, S.; Siegwart, R. Conceptualizarea spațiului bayesian și clasificarea locului pentru hărți semantice în robotica mobilă // Robotics and Autonomous Systems : journal. - 2008. - Vol. 56 , nr. 6 . - P. 522--537 . - doi : 10.1016/j.robot.2008.03.005 .
↑ Perrin, X.; Chavarriaga, R.; Colas, F.; Seigwart, R.; Millan, J. Brain-coupled interaction for semi-autonomous navigation of an assistive robot // 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. Raționament bayesian pentru analiza mișcării Laban utilizată în interacțiunea om-mașină // Int . J. de Reasoning-based Intelligent Systems: jurnal. - 2010. - Vol. 2 , nr. 1 . — P. 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 , în Duffy, Vincent G., Digital Human Modeling , Lecture Notes in Computer Science, volumul 5620, Second International Conferință, ICDHM 2009, San Diego, CA, SUA: Springer, p. 423-432, ISBN 978-3-642-02808-3 , doi : 10.1007/978-3-642-02809-0_45 Arhivat 11 iunie 2018 la Wayback Machine
^ Möbus , C. & Eilers, M. (2009), Further Steps Towards Driver Modeling according to the Bayesian Programming Approach , în Duffy, Vincent G., Digital Human Modeling , Lecture Notes in Computer Science, volumul 5620, a doua conferință internațională, ICDHM 2009, San Diego, CA, SUA: Springer, p. 413-422, ISBN 978-3-642-02808-3 , doi : 10.1007/978-3-642-02809-0_44 Arhivat 10 iunie 2018 la Wayback Machine
↑ Eilers, M.; Möbus, C. (2010). „Lernen eines modularen Bayesian Autonomous Driver Mixture-of-Behaviors (BAD MoB) Modeles” (PDF) . În Kolrep, H.; Jurgensohn, Th. Fahrermodellierung - Zwischen kinematischen Menschmodellen und dynamisch-kognitiven Verhaltensmodellen . Fortschrittsbericht des VDI in der Reihe 22 (Mensch-Maschine-Systeme). Düsseldorf, Germania: VDI-Verlag. pp. 61–74. ISBN 978-3-18-303222-8 . Arhivat pe 3 februarie 2014 la Wayback Machine
↑ Möbus, C.; Eilers, M. Handbook of Research on Environment Intelligence and Smart Environments: Trends and Perspectives / Mastrogiovanni, F.; Chong, N.-Y.. - Hershey, Pennsylvania (SUA): IGI Global publications, 2011. - P. 460-512. — ISBN 9781616928575 . - doi : 10.4018/978-1-61692-857-5.ch023 .
↑ Eilers, M.; Möbus, C. (2011). „Învățarea percepțiilor relevante ale modelelor de driver bayesiene ierarhice modulare utilizând un criteriu de informare bayesian.” În Duffy, VG Digital Human Modeling . LNCS 6777. Heidelberg, Germania: 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). „Învățarea unui model Bayesian de amestec de comportamente pentru șofer autonom (BAD-MoB)” . În Duffy, VG progresează în modelarea umană digitală aplicată . LNCS 6777. Boca Raton, SUA: CRC Press, Taylor & Francis Group. pp. 436-445. ISBN 978-1-4398-3511-1 . Arhivat la 1 februarie 2014 la Wayback Machine
↑ Le Hy, R.; Arrigoni, A.; Bessière, P.; Lebetel, O. Teaching Bayesian Behaviors to Video Game Characters // Robotics and Autonomous Systems: journal. - 2004. - Vol. 47 , nr. 2-3 . - P. 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. Un model probabilistic unificat al percepției structurii tridimensionale din fluxul optic // Biological Cybernetics : journal. - 2008. - P. 132--154 .
↑ Laurens, J.; Droulez, J. Prelucrarea bayesiană a informațiilor vestibulare // Cibernetică biologică. - 2007. - Vol. 96 , nr. 4 . - P. 389--404 . - doi : 10.1007/s00422-006-0133-1 .
↑ Colas, F.; Flacher, F.; Tanner, T.; Bessière, P.; Girard, B. Modele bayesiene de selecție a mișcărilor oculare cu hărți retinotopice (engleză) // Biological Cybernetics : journal. - 2009. - Vol. 100 , nr. 3 . — P. 203——214 . - doi : 10.1007/s00422-009-0292-y .
↑ Serkhane, J.; Schwartz, JL.; Bessière, P. Construirea unui robot pentru bebeluși care vorbește O contribuție la studiul achiziției și evoluției vorbirii // Studii de interacțiune : jurnal. - 2005. - Vol. 6 , nr. 2 . - P. 253--286 . - doi : 10.1075/is.6.2.06ser .
↑ Moulin-Frier, C.; Laurent, R.; Bessière, P.; Schwartz, JL.; Diard, J. Condițiile adverse îmbunătățesc distingerea teoriilor auditive, motorii și percep-tuo-motorii ale percepției vorbirii: un studiu explorator de modelare Bayesian // Language and Cognitive Processes : journal. - 2012. - Vol. 27 , nr. 7-8 . — P. 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 (engleză) // PLOS One : journal / Sporns, Olaf. - 2011. - Vol. 6 , nr. 6 . — P.e20387 . - doi : 10.1371/journal.pone.0020387 . - Cod biblic .
↑ Noul algoritm ajută mașinile să învețe la fel de repede ca oamenii . www.gizmag.com (22 ianuarie 2016). Data accesului: 23 ianuarie 2016. Arhivat din original pe 24 ianuarie 2016. (nedefinit)
↑ Zadeh, Lofti, A. Fuzzy sets // Information and Control : jurnal. - 1965. - Vol. 8 , nr. 3 . — P. 338——353 . - doi : 10.1016/S0019-9958(65)90241-X .
↑ Zadeh, Lofti, A. Logica fuzzy și raționamentul aproximativ // Sinteză : jurnal. - 1975. - Vol. 30 , nr. 3——4 . - P. 407--428 . - doi : 10.1007/BF00485052 .
↑ Dubois, D.; Prade, H. Teoria posibilității, teoria probabilității și logica cu valori multiple: o clarificare // Ann . Matematică. Artif. Intel. : jurnal. - 2001. - Vol. 32 , nr. 1——4 . — P. 35——66 . - doi : 10.1023/A:1016740830286 .
↑ Poole, D. Probabilistic Horn abduction and Bayesian networks // Artificial Intelligence. - 1993. - Vol. 64 . - P. 81-129 . - doi : 10.1016/0004-3702(93)90061-F .
↑ Poole, D. The Independent Choice Logic for modeling multiple agents under uncertainty // Inteligența artificială: jurnal. - 1997. - Vol. 94 . - P. 7-56 . - doi : 10.1016/S0004-3702(97)00027-1 .
↑ Sato, T.; Kameya, Y. Învățarea parametrilor programelor logice pentru modelarea simbolic-statistică (engleză) // Journal of Artificial Intelligence Research : jurnal. - 2001. - Vol. 15 . - P. 391--454 . Arhivat din original pe 12 iulie 2014.

Literatură

Kamel Mekhnacha. Programare Bayesiană . - Chapman și Hall/CRC, 2013. - ISBN 978-1-4398-8032-6 . Programare Bayesiană . Chapman și Hall/CRC. ISBN 978-1-4398-8032-6.

Link

Site însoțitor al cărții „Programarea Bayesiană”, de unde puteți descărca ProBT și motorul de inferență. Arhivat din original pe 23 noiembrie 2013. (Engleză)
Bayesian-programming.org Arhivat 23 noiembrie 2013. , promovând programarea bayesiană, cu informații detaliate și numeroase publicații. (Engleză)