Home » Intelligenza Artificiale » 📋 URL
Introduciamo il nuovo concetto di inferenza approssimata, contrapposto rispetto all’inferenza trattata fin’ora—l’inferenza esatta—che presenta un costo computazionale molto elevato.
Probabilistic sampling
Esempio: estraendo 20 volte una pallina dalla vasca in figura, dove vengono riportate le percentuali esatte dei colori delle palline
saremo in grado di approssimare la distribuzione di probabilità del colore delle palline, trovando per esempio
{\bf\widehat{P}}=\left\langle\dfrac{8}{20},\,\dfrac{5}{20},\,\dfrac{7}{20}\right\rangle=\langle0.4,\,0.25,\,0.35\rangleChe approssima piuttosto bene l’effettiva distribuzione di probabilità del problema.
Tratteremo le seguenti classi di algoritmi di probabilistic sampling e le relative tecniche indicate di fianco:
- Direct sampling: prior sampling, rejection sampling, likelihood weighting
- Markov Chain Monte Carlo (MCMC): gibbs sampling
Prior sampling (esempi a priori)
Il prior sampling (esempi a priori) viene utilizzato per generare degli esempi dalla distribuzione di probabilità di un problema. Ripetendo tale procedimento N volte si arriverà a una definizione empirica della probabilità dei singoli eventi. Questa tecnica si affida sul fatto che la distribuzione di probabilità utilizzata sia sensata.
Esempio: ipotizzando di avere una rete come in figura, con le relative CPT
E struttura topologica
[\text{Cloudy, Sprinkler, Rain, GrassWet}]Dopo aver generato N esempi dalla distribuzione di probabilità della rete, possiamo aspettarci che la probabilità P(c,\,\neg s,\,r,\,g) sarà pari a
[\text{True, False, True, True}]Circa il 32.4\% delle volte, infatti si ha
\begin{aligned}
P(c,\,\neg s,\,r,\,g)&=P(g \mid r,\,\neg s)P(r \mid c)P(\neg s\mid c)P(c)\\
&=0.9\cdot 0.8\cdot (1-0.1)\cdot 0.5\\
&=0.324
\end{aligned}Esercizio: trovare la probabilità associata alla generazione seguente
[\text{True, True, True, False}]Soluzione
Stiamo cercando la probabilità P(c,\,s,\,r,\,\neg g), che possiamo calcolare dalle CPT, ed è pari a
\begin{aligned}
P(c,\,s,\,r,\,\neg g)&=P(\neg g\mid r,\,s)P(r\mid c)P(s\mid c)P(c)\\
&=(1-0.95)\cdot0.8\cdot0.1\cdot0.5\\
&=0.002
\end{aligned}Rejection sampling (esempi rifiutati)
Assumiamo di avere delle informazioni (evidence) {\bf e} sul problema e vogliamo calcolare {\bf P}(X \mid {\bf e}). L’idea di base parte da quella del prior sampling, generando anche in questo caso una lista di esempi, ma considerando questa volta soltanto gli esempi che non contraddiscono le informazioni che già abbiamo, rifiutando (rejecting) tutti gli altri che non sono consistenti con tali informazioni.
Esempio: supponiamo di voler trovare la distribuzione di probabilità {\bf P}(\text{Rain}\mid\text{Sprinkler=true}) basandoci su 100 esempi. Da tali esempi sappiamo che 73/100 volte è uscito \text{Sprinkler=False}, mentre delle restanti 27 sappiamo che 8/100 hanno \text{Rain=True}, mentre le altre 19/100 volte è uscito \text{Rain=False}. Stimare la distribuzione di probabilità richiesta.
Soluzione
Poiché vogliamo verificare quante volte piove, dato che \text{Sprinkler=True}, tutti gli esempi in cui \text{Sprinkler=False} verranno rifiutati, di fatto non utilizzandoli nel calcolo.
A questo punto dobbiamo dunque calcolare la probabilità per i diversi valori di \text{Rain}. Supponiamo dapprima \text{Rain}=\text{True}. Sappiamo ora che tale risultato è uscito 8 volte.
Supponendo ora \text{Rain}=\text{False} sappiamo invece che tale risultato è uscito 19 volte. Possiamo dunque esprimere la probabilità richiesta nel modo seguente
{\bf P}(\text{Rain}\mid\text{Sprinkler=true})=\alpha\langle8,\,19\rangleDa cui è poi necessario trovare il valore di \alpha per normalizzare l’intervallo di probabilità
\alpha=\dfrac{1}{8+19}\approx0.037\Rightarrow 0.037\langle8,\,19\rangle=\langle0.296,\,0.703\rangleNota: la somma tra le probabilità non è esattamente unitaria a causa dell’approssimazione del valore di \alpha.
Esercizio: Trovare la probabilità {\bf P}(\text{Rain}\mid\text{Cloudy=False}). Siamo a conoscenza dei seguenti dati su 100 esempi:
- 90/100:\text{Cloudy=True}
- 4/100:\text{Rain=True}
- 6/100:\text{Rain=False}
Soluzione
Scartiamo tutti gli esempi in contraddizione con le informazioni che abbiamo. Ci rimane
{\bf P}(\text{Rain}\mid\text{Cloudy=False})=\alpha\langle4,\,6\rangleTrovando \alpha=0.1 otteniamo poi
{\bf P}(\text{Rain}\mid\text{Cloudy=False})=\langle0.4,\,0.6\rangleLikelihood weighting (pesato sulla probabilità)
Il problema che nasce dal rejection sampling è che, come visto negli esercizi, spesso molti degli esempi vengono semplicemente scartati senza essere utilizzati. Vogliamo dunque trovare un metodo per utilizzare anche tali esempi.
L’idea del likelihood weighting è dunque quella di generare degli esempi che siano in accordo che le informazioni disponibili. Per generare tali esempi dobbiamo dunque fissare i valori delle variabili evidence, cosicché la rete generi ulteriori esempi nei quali tali valori sulle quali stiamole variabili su cui non abbiamo alcuna informazione, e pesarli poi ognuno per la propria probabilità di verificarsi.
Esempio: considerando la seguente rete
Dove abbiamo fissato a \text{Vero} i valori di \text{Cloudy} e \text{GrassWet}. Considerando come ordine topologico delle variabili
[\text{Cloudy, Sprinkler, Rain, GrassWet}]trovare la probabilità {\bf P}(\text{Rain} \mid c,\,g) assumendo {\bf P}(\text{Sprinkler}\mid c)=\text{Falso} e {\bf P}(\text{Rain}\mid c)=\text{Vero}.
Soluzione
La probabilità {\bf P}(\text{Rain} \mid c,\,g)={\bf P}(r \mid c,\,g) può essere scomposta in
{\bf P}(r \mid c,\,g)=P(g\mid r,\,s)\cancel{P(r\mid c)}\cancel{P(s\mid c)}P(c)Poiché i valori r e s non sono stati fissati non li utilizziamo nel calcolo finale della probabilità.
Ci è stato inoltre detto che {\bf P}(\text{Sprinkler}\mid c)=\text{Falso} e {\bf P}(\text{Rain}\mid c)=\text{Vero}, la probabilità P(g\mid r,\,s) che dobbiamo utilizzare è in realtà
P(g \mid r,\,\neg s)=0.9
Poiché P(c)=0.5 il peso finale sarà dato da
w=0.9\cdot0.5=0.45
Che rappresenta la probabilità di ottenere
[\text{True, False, True, True}]Esercizio: in riferimento al grafo dell’esempio precedente, considerando che sono stati generati 10 esempi diversi ed è stata ottenuta la seguente tabella dei pesi
Trovare le probabilità P(r\mid c,\,g) e P(\neg r,\mid c,\,g).
Soluzione
Per trovare P(r\mid c,\,g), avendo già i valori dei pesi, non ci resta che trovare i casi in cui \text{Rain=Vero}
\begin{aligned}
P(r\mid c,\,g)&=\dfrac{\displaystyle\sum_r w}{\displaystyle\sum w}\\[10pt]
&=\dfrac{0.45+0.475+0.45+0.45+0.45+0.475+0.45+0.45}{0.45+0.475+0.05+0.45+0.45+0.45+0.475+0.45+0.05+0.45}\\[10pt]
&\approx0.9733
\end{aligned}Per quanto riguarda P(\neg r,\mid c,\,g) invece dobbiamo trovare i casi in cui \text{Rain=Falso}, ovvero
\begin{aligned}
P(\neg r\mid c,\,g)&=\dfrac{\displaystyle\sum_{\neg r} w}{\displaystyle\sum w}\\[10pt]
&=\dfrac{0.05+0.05}{0.45+0.475+0.05+0.45+0.45+0.45+0.475+0.45+0.05+0.45}\\[10pt]
&\approx0.0267
\end{aligned}Gibbs sampling (esempi di Gibbs)
Iniziando da uno stato arbitrario, date delle informazioni (evidence) {\bf e}, l’algoritmo genera lo stato successivo tramite l’utilizzo di una variabile X_i non inclusa in {\bf e}, dato il suo Markov blanket.
Tale procedimento viene ripetuto più volte per cercare di approssimare la distribuzione di probabilità, mantenendo fissi i valori di {\bf e}.
Esempio:
…