Regole probabilistiche o con inferenza complessa

Un primo semplice esempio di regole probabilistiche semplici è il seguente.

run(""" % probabilità che piova oggi, che sia soleggiato 0.3::piove. 0.6::soleggiato. % se piove o non è soleggiato, è probabile che rubino l’ombrello 0.7::furto :- piove; not(soleggiato). query(furto). """)
{furto: 0.40599999999999997}
Possiamo poi vedere come considerando un'evidenza vengano rideterminate a posteriori le probabilità dei fatti.
run(""" % probabilità che piova oggi o che sia soleggiato 0.3::piove. 0.6::soleggiato. % se piove o non è soleggiato, è probabile che rubino l’ombrello 0.7::furto :- piove; not(soleggiato). evidence(furto,true). query(piove). query(soleggiato). """)
{soleggiato: 0.31034482758620685, piove: 0.5172413793103448}

Occorre chiarire a questo punto che la probabilità non è riferita alla regola, che è sempre deterministica, bensì al fatto che ne è conseguenza.

L'uso di regole con inferenza complessa in ProbLog spazia da concetti fondamentali come il Noisy-OR a modelli più avanzati come le reti bayesiane e le catene di Markov.
In particolare il costrutto Noisy-OR, che si verifica quando più regole possono dedurre la stessa testa e le loro probabilità si combinano come cause indipendenti di un effetto comune, è un pilastro della complessità in ProbLog che quindi permette di modellare scenari in cui un evento può essere causato da diverse fonti che non si escludono a vicenda.

run(""" 0.9::scende_pressione. 0.5::aumenta_umidità. 0.7::alta_temperarura. 0.5::piove :- scende_pressione; aumenta_umidità; alta_temperarura. 0.9::piove :- scende_pressione, aumenta_umidità, alta_temperarura. query(piove). """)
{piove: 0.63425}

Un altro esempio mostra come a regole probabilistiche si possono associare fatti del tipo evidence per ottenere attraverso Bayes probabilità condizionate.

run(""" % Contesto (4 persone) person(1). person(2). person(3). person(4). friend(1,2). friend(2,1). friend(2,4). friend(3,2). friend(4,2). % Probabilità che una persona sia stressata (causa intrinseca) 0.3::stress(X) :- person(X). % Probabilità che una persona ne influenzi un'altra (influenza sociale) 0.2::influences(X,Y) :- person(X), person(Y). % REGOLE COMPLESSE: Una persona fuma se è stressata o se è influenzata da un amico che fuma smokes(X) :- stress(X). smokes(X) :- friend(X,Y), influences(Y,X), smokes(Y). % Conseguenza: se fuma, ha l'asma con probabilità 0.4 0.4::asthma(X) :- smokes(X). % EVIDENZA: sappiamo che la persona 2 fuma e che la persona 4 non influenza la 2 evidence(smokes(2),true). evidence(influences(4,2),false). % QUERY: qual è la probabilità che le altre persone fumino e abbiano l'asma? query(smokes(1)). query(smokes(3)). query(smokes(4)). query(asthma(1)). query(asthma(2)). """)
{asthma(2): 0.4000000000000001, smokes(3): 0.44000000000000006, smokes(4): 0.44000000000000006, smokes(1): 0.5087719298245614, asthma(1): 0.20350877192982456}

Anche il prossimo esempio mostra come codificare una rete bayesiana in ProbLog, modellando relazioni di dipendenza più articolate dove la probabilità di un evento (l'allarme) dipende da una combinazione di condizioni (scasso, terremoto, e loro assenza)

run(r""" % Probabilità a priori 0.7::burglary. 0.2::earthquake. % REGOLE COMPLESSE: La probabilità dell'allarme dipende da diverse condizioni 0.9::alarm :- burglary, earthquake. 0.8::alarm :- burglary, \+earthquake. 0.1::alarm :- \+burglary, earthquake. % Nota: non c'è regola per alarm se non c'è né scasso né terremoto (probabilità 0) % EVIDENZA: l'allarme è scattato evidence(alarm,true). % QUERY: qual è la probabilità a posteriori di scasso e terremoto? query(burglary). query(earthquake). """)
{earthquake: 0.22758620689655182, burglary: 0.9896551724137931}
L'inferenza calcola la probabilità condizionata P(Query | Evidence). Usando il teorema di Bayes, il motore di inferenza combina le probabilità di tutte le cause (scasso, terremoto) che possono spiegare l'evidenza osservata (l'allarme), andando oltre la semplice moltiplicazione di probabilità indipendenti.

Un esempio di catena di Markov è il seguente.

run(""" % Tempi ammessi :- use_module(library(lists)). time(T) :- between(0,10,T). % Stato iniziale (deterministico) sole(0). % Transizioni della catena di Markov 0.8::sole(T) :- time(T), T_1 is T-1, sole(T_1). 0.2::pioggia(T) :- time(T), T_1 is T-1, sole(T_1). 0.4::sole(T) :- time(T), T_1 is T-1, pioggia(T_1). 0.6::pioggia(T) :- time(T), T_1 is T-1, pioggia(T_1). % Query: probabilità che piova query(pioggia(_)). """)
{pioggia(2): 0.2608, pioggia(1): 0.2, pioggia(3): 0.2653107200000001, pioggia(4): 0.24846484684800013, pioggia(5): 0.22481322401464335, pioggia(6): 0.20027013897506535, pioggia(7): 0.17710833184943614, pioggia(8): 0.15608069681792516, pioggia(9): 0.13731951314991805, pioggia(10): 0.12071588616806395}

Un altro esempio mostra un'inferenza complessa basata su vincoli. Si genera una stringa casuale e si chiede la probabilità che contenga la sottostringa "bb", dato che la stringa è un palindromo .

run(""" % Probabilità di scegliere 'a' o 'b' per ogni posizione N 0.5::pick(N, a) ; 0.5::pick(N,b). % Una stringa di lunghezza N è un palindromo se la sottostringa dalla posizione 1 alla posizione N è palindroma. palindrome(N) :- palindrome(1,N). % Terminazione della ricorsione: Se l'indice sinistro N1 e quello destro N2 si sono incrociati fine del controllo di tutti i caratteri. palindrome(N1,N2) :- N1 > N2. % Nel caso l lunghezza sia dispari il carattere centrale è arbitrario palindrome(N,N) :- pick(N,_). % REGOLE COMPLESSE (RICORSIVE): il carattere in posizione N1 deve essere uguale a quello in N2 palindrome(N1,N2) :- N1 < N2, pick(N1,X), pick(N2,X), N1p1 is N1+1, N2m1 is N2-1, palindrome(N1p1,N2m1). % Regola per verificare la presenza di "bb" consecutivi in una stringa lunga N bb(N) :- Max is N-1, between(1,Max,I), pick(I,b), Ip1 is I+1, pick(Ip1,b). % Vincolo e Query len(5). evidence(palindrome(X)) :- len(X). % Dato che la stringa è un palindromo query(bb(X)) :- len(X). % Qual è la probabilità che contenga "bb"? """)
{bb(5): 0.375}
L'efficienza dell'inferenza è una sfida cruciale. L'approccio "naive" (generare tutte le stringhe e poi filtrare) è proibitivo. Questo esempio utilizza un metodo "generate-and-test" più efficiente (spesso con forward inference) che costruisce la stringa rispettando direttamente i vincoli del palindromo, riducendo drasticamente lo spazio delle possibili combinazioni da esplorare .

Questi esempi illustrano come le regole probabilistiche di ProbLog possano modellare e risolvere problemi con dipendenze cicliche, probabilità condizionate e vincoli complessi, ben oltre semplici modelli.

Si consideri anche il seguente esempio in cui la testa della regola è composta, una Annotated Disjunction, in cui si ha mutua esclusione, solo uno dei componenti della testa potrà essere vero, non sono indipendenti tra loro.

run(""" %Un dado truccato 0.1::face(1); 0.1::face(2); 0.1::face(3); 0.2::face(4); 0.2::face(5); 0.3::face(6) :- roll. % lanciamo il dado roll. even :- face(2); face(4); face(6). % Query query(even). """)
{even: 0.6000000000000001}
Possiamo anche campionare
from problog.tasks import sample from problog.program import PrologString model = PrologString(""" %Un dado truccato 0.1::face(1); 0.1::face(2); 0.1::face(3); 0.2::face(4); 0.2::face(5); 0.3::face(6) :- roll. % lanciamo il dado roll. even :- face(2); face(4); face(6). % Query query(even). """) [s for s in sample.sample(model, n=5, format='dict')]
[{even: False}, {even: False}, {even: True}, {even: True}, {even: True}]

Esaminiamo il paradosso di Monty Hall.

run(r""" 1/3::prize(1) ; 1/3::prize(2) ; 1/3::prize(3). member(X,[X|T]). member(X,[H|T]) :- member(X,T). 0.5::open_door(A) ; 0.5::open_door(B) :- member(A, [1,2,3]), member(B, [1,2,3]), A < B, \+ prize(A), \+ prize(B), \+ select_door(A), \+ select_door(B). open_door(A) :- member(A, [1,2,3]), member(B, [1,2,3]), \+ prize(A), prize(B), \+ select_door(A), \+ select_door(B). win_keep :- select_door(A), prize(A). win_switch :- member(A, [1,2,3]), \+ select_door(A), prize(A), \+ open_door(A). select_door(1). query(prize(_)). query(select_door(_)). query(win_keep). query(win_switch). """)
{prize(1): 0.3333333333333333, win_keep: 0.3333333333333333, prize(3): 0.3333333333333333, win_switch: 0.6666666666666666, prize(2): 0.3333333333333333, select_door(1): 1.0}

Infine consideriamo il seguente esempio, un modello tratto da SWIFT: Compiled Inference for Probabilistic Programs di un'urna contenente palline di due colori, verde e blu. Il numero di palline è sconosciuto a priori e viene modellato utilizzando una distribuzione uniforme. Dopo aver estratto due volte una pallina e aver osservato che è verde, l'obiettivo è dedurre il numero di palline presenti nell'urna.
Si fa qui uso anche della libreria dei predicati SWI-Prolog come member/2, append/3, reverse/2, flatten/2, sum_list/2 e numlist/3 che consentono la manipolazione standard delle liste con ulteriori predicati probabilistici come select_weighted(+ID, +Weights, +Values, ?Value, ?Rest) che seleziona un valore da una lista in base ai pesi associati, select_uniform(+ID, +Values, ?Value, ?Rest) che eleziona un valore in modo uniforme da una lista, groupby(?List, ?Groups) che aggruppa gli elementi della lista, sub_list(?List, ?Before, ?Length, ?After, ?SubList) che estrae una sottolista, make_list(Len, Elem, List) che crea una lista di una lunghezza specificata.

run(""" :- use_module(library(lists)). % Il numero di palline può essere 1, 2, 3 o 4 con probabilità 1/4 num_balls(X) :- select_uniform(id, [1,2,3,4], X, _). % Per ogni pallina la probabilità che sia blu è 0.9 e che sia verde è 0.1. 0.9::color(Ball, blue); 0.1::color(Ball, green). % Estrai una pallina a caso (con estrazione uniforme) usando l'identificatore Id, e il suo colore è C draw_ball(Id, C) :- num_balls(TBs), findall(Bs, between(1,TBs,Bs), L), select_uniform(Id, L, B, _), color(B, C). % queste evidenze cambiano le probabilià del numero di palline evidence(draw_ball(0, green)). evidence(draw_ball(1, green)). query(num_balls(_)). """)
{num_balls(1): 0.4395604395604395, num_balls(3): 0.17582417582417595, num_balls(4): 0.14285714285714296, num_balls(2): 0.24175824175824145}

Possiamo vedere come incorporare nel programma ProbLog un predicato definito in Python.

from problog import get_evaluatable from problog.program import PrologString from problog.engine import DefaultEngine from problog.extern import problog_export from scipy.stats import poisson @problog_export('+list', '+int', '-list') def poisson_probs(values, k): probs = poisson.pmf(values, k) total = sum(probs) return [float(prob/total) for prob in probs] program_code = (""" :- use_module(library(lists)). num_balls(X) :- findall(N, between(1,4,N), L), poisson_probs(L, 2, Probs), select_weighted(0, Probs, L, X, _). 0.9::color(Ball, blue); 0.1::color(Ball, green). draw_ball(D, C) :- num_balls(TBs), findall(Bs, between(1,TBs,Bs), L), select_uniform(D, L, B, _), color(B, C). evidence(draw_ball(0, green)). evidence(draw_ball(1, green)). query(num_balls(_)). """) def run_with_extern(code, externs): """externs: lista di tuple (funzione, '+tipo', '+tipo', ..., '-tipo')""" engine = DefaultEngine() problog_export.database = engine.prepare(PrologString(code)) for func, *types in externs: problog_export(*types).__call__(func, modname=None) return get_evaluatable().create_from(problog_export.database).evaluate() run_with_extern(program_code, [(poisson_probs, '+list', '+int', '-list')])
{num_balls(1): 0.5194805194805191, num_balls(3): 0.13852813852813875, num_balls(4): 0.056277056277056266, num_balls(2): 0.285714285714286}