Fault Tollerance
and
Bayesian Networks
Progetto Tramp
Applicazione di tecniche di intelligenza artificiale
per la realizzazione di sistemi fault tolerant
Ing. Alessandra Scotto di Freca
Ph.D. presso l’Università degli Studi di Cassino
[email protected]
1
Fault Tolerance

Cosa vuol dire essere tolleranti ai guasti?
Prevedere i guasti prima che
si verifichino e recuperarli

Il problema della previsione di guasti

Classificazione

Apprendimento

Costruzione di un modello!!
2
La Classificazione

un problema di classificazione può essere:

Possiamo formularlo in termini probabilistici:
L’oggetto X ha peso = 100 g e diametro = 10cm è una mela o una pera?
??
P(oggetto = mela | peso = 100 g, diametro = 10cm ) = 0.7
P(oggetto = pera | peso = 100 g, diametro = 10cm ) = ??
0.3
3
Tecniche di Classificazione
Come posso calcolare la P(oggetto = mela | peso = 100 g, diametro = 10cm ) ???
Teorema di Bayes
P(A | B) = P(B | A) P(A)
P(B)
P (A | B)
P (B | A )
P (A)
P (B)
A Posteriori di A dato B
verosimiglianza (likelihood)
A priori di A
A priori di B
4
Classificazione in breve!
5
Introduzione alle reti Bayesiane





Elementi di Probabilità
Interpretazione Bayesiana della probabilità
Cosa è una Rete Bayesiana
Come viene usata per classificare (inferenza)
Costruzione di una Rete Bayesiana (apprendimento ottenuto dal
mix di conoscenza a priori e dall’osservazione dei dati)


Perché usare una Rete Bayesiana
Scenari applicativi
6
Elementi di probabilità

Definizione di probabilità:

Considerato un evento E la probabilità che esso si verifichi è il rapporto
fra il numero F dei casi favorevoli (al verificarsi di E) e il numero N dei
casi possibili, giudicati egualmente probabili.
P(E) = F / N

Poiché l’ipotesi di eventi egualmente probabili è difficile da osservare si
preferisce la definizione frequentista:
P(E) = limN->∞ F / N
P(E) è un numero reale compreso tra 0 e 1 e la somma della probabilità
dell’evento e dell’evento negato deve fare uno P(E)+P(!E)=1
7
Elementi di probabilità

Definizione di probabilità

Media (o valore atteso di una variabile discreta X)


Varianza



Var(X) = E [ ( X - E [ X ])2 ] = E[ X2 ] - E [ X ]2
Probabilità congiunta è la probabilità che si verifichino congiuntamente più eventi

In generale P(A,B) = P(A | B)P(B) = P(B | A) P(A)

Nel caso in cui A e B siano indipendenti P(A,B) = P(A)* P(B)
P(A,B) = P (A ^ B)
Probabilità condizionata


E [ X ] = Σi xi P(xi)
È la probabilità dell’evento A condizionatamente a B: P(A | B) = P(A,B)/P(B)
Teorema di Bayes
P(A | B) = P(B | A) P(A)
P(B)
8
Elementi di probabilità

Probabilità marginale

È la probabilità di un unico evento, questa può essere ottenuta dalla
congiunta sommando P(A)= Σi P(A,Bi)
Bi
Ai=0,
Bi=1
Ai=1,
Bi=1
Ai=0 Ai=1
Ai=0,
Bi=0
Ai=1,
Bi=0
Ai
9
Interpretazione Probabilità Bayesiana

Probabilità classica: è una proprietà fisica del mondo
“E’la vera probabilità!!”

Probabilità Bayesiana: è il grado con il quale una persona crede che un evento X si
verifichi.
E’una probabilità personale!!
Al contrario della probabilità classica calcolata con l’approccio frequentista, le probabilità
bayesiane beneficiano del fatto che sono richieste un numero di prove inferiore.
ESEMPIO:
Calcolare la probabilità che il Napoli vinca la prossima partita?

nella definizione classica è contenuto un vizio logico. Il fatto di supporre che tutti i casi siano
egualmente possibili implica di avere definito in precedenza la probabilità nel momento stesso in
cui la si definisce.

P(“Napoli vinca”) = 1/3 ??

Nella definizione frequentista si potrebbe controllare l’almanacco e calcolate il limite N->inf

Nella definizione bayesiana si vanno a cercare eventi che condizionano l’evento da prevedere.
Da questi si acquisisce un grado di credenza(“belief”) tale da consentire la stima della probabilità


Gioca in casa?
In che condizioni sono i sui giocatori?
P( “Napoli vinca”| conoscenza dei fattori condizionanti e dell’esperienza )
10
Probabilità Bayesiana

Problema della punessa:
quando la lancio essa cadrà sulla testa o sulla punta??
Come faccio a stimare la probabilità che al prossimo lancio la punessa cada sulla testa
avendo a disposizione N lanci precedenti?
Grazie alla teoria Bayesiana:
Definendo D = {X1 = h, X2 = h, X3 = t, ………, XN = t} dati osservati e  esperienza o conoscenza a
priori del fenomeno
Devo calcolare
P(XN+1= heads | D,)
11
Inferenza
Classificare il prossimo evento consiste nel calcolo della probabilità
di interesse dato un modello: fare inferenza

x1
x2
x[N]
dati osservati
x[N+1]
Query
12
Probabilità Bayesiana
Definendo  corrispondente al possibile valore vero della probabilità fisica, a cui
nella teoria bayesiana ci si riferisce come “parametro” di cui posso calcolare una
A Priori p( |  ) ed un A Posteriori p( | D, )
P(XN+1=heads | D,) =  p( | D, ) d = E p( | D, ) ()
valore atteso di  rispetto alla distribuzione p( | D, )
Dal teorema di Bayes possiamo calcolare la probabilità a posteriori di  dato D
(dati osservati) e  conoscenza a priori:
p( | D, ) =
p( |  ) p (D |  ,  ) dove p(D | ) =
P(D | )
p(D | , ) p( | ) d 
p( |  )
è la A Priori di 
p (D |  ,  ) è la likelihood che nel problema della punessa in cui le osservazioni si
D sono mutuamente indipendenti può essere considerata binomiale
h (1-)t
14
Funzione di verosimiglianza
La bontà del parametro  viene misurata con la
funzione di verosimiglianza:
L (, D ) = P( D |  )
(una volta scelto  lo si testa vedendo quanto bene esso è capace di
generare dati osservati)
Quindi la funzione di verosimiglianza della sequenza H, T,H,T ,T può
essere: L ( ,D ) =  . (1- ) .  . (1 - ) . (1 - )
15
statistica sufficiente
Per calcolare la funzione di verosimiglianza nel problema della punessa
sono richiesti solo h e t ossia il numero di volte che la punessa è caduta
sulla testa e quello in cui è caduta sulla punta
h e t sono chiamate statistiche sufficienti per una distribuzione binomiale
Una statistica sufficiente riassume dai dati le informazioni rilevanti per la
funzione di verosimiglianza
16
A Priori
Possiamo descrivere l’incertezza su  usando la densità di
probabilità:
p(| )
Un approccio comunemente adottato per esprimerla usa la distribuzione Beta:
Dove αh > 0 e αt >0 sono detti iperparametri della distribuzione Beta e
rappresentano il grado di conoscenza a priori
17
Esempi di distribuzioni Beta
Nel coso di assoluta ignoranza αh e αt rappresentano la condizione di
equiprobabilità, una volta note αh e αt la distribuzione a posteriori diventa:
α’h = αh + h e α’t = αt + t
quindi le osservazioni possono poi diventare la
conoscenza attuale!!
18
In fine
…..
Mediando sui possibili valori di  per determinare la
probabilità che al lancio N+1 la punessa cada sulla testa:
P(XN+1=heads | D,) =  p( | D, ) d
Usando la distribuzione Beta tale valore atteso di 
rispetto alla distribuzione di p(/D, ) diventa :
Dove α = αh + αt e N è il numero di osservazioni totali
19
… più in generale
L’esempio della punessa descrive un caso in cui la variabile aleatoria da
considerare assume valori discreti
In questo caso abbiamo assunto che la distribuzioni a priori fosse una Beta
ma nel caso generale la
P(XN+1=heads | D,) =  p( | D, ) d
Può essere calcolata efficientemente e in forma chiusa ipotizzando
distribuzioni multinomiali, normali, Gamma, Poisson e normali multivariate
che includono anche il caso in cui X assume valori continui e quello in cui
invece di una signola X ho un vettore di variabili aleatorie.
Se ad esempio la modelliamo con una gaussiana il parametro da stimare
sarà ={media, varianza}
Nel caso in cui X è un vettore di variabili aleatorie la P(X) può essere
studiata tramite una rete bayesiana andando a considerare anche le
dipendenze tra variabili
20
Problema di Classificazione
Come usiamo le informazioni viste fin ora per costruire un classificatore?
Bisogna capire a quale è l’evidenza dalla quale vogliamo trarre
informazioni allo scopo di classificare !
Possiamo usare più informazioni contemporaneamente per ottenete
risultati di classificazione migliori
21
Esempio

La storia: Paolo ha un nuovo allarme anti-scasso sulla sua autovettura che funziona molto bene
nel prevenire i furti, ma alcune volte risponde positivamente a piccole scosse di terremoto. Due
vicini di casa di Paolo, Mary e John, hanno promesso di avvisarlo nel caso scattasse l’allarme
mentre lui si trova al lavoro. John chiama sempre quando scatta l’allarme, ma a volte si confonde
con il suono del telefono e avverte Paolo lo stesso. Mary ama ascoltare la musica a tutto volume
e qualche volta non sente l’allarme e non avverte Paolo.

Problema: Stimare la probabilità che ci sia uno scassinatore sulla base di chi ha o no
telefonato ( classificare un furto! )

Variabili: Scassinatore(B), Terremoto(E), Allarme(A), Chiamata di John (J), Chiamata
di Mary (M)

Conoscenza richiesta per risolvere il problema:
P(B, E, A, J, M)
(distribuzione congiunta di probabilità)

Tale conoscenza viene usata per formalizzare il problema di classificazione come:
P(B| E, A, J, M) apprendendo la congiunta precedente dai dati osservati D ossia dalle
istanze degli stati del vettore di v.a. {B, E, A, J, M}
22
Nota la distribuzione congiunta
Ho 25 valori che
abbiamo assunto
essre noti ma come
faccia in genere per
apprenderli ?
23
Costruzione del modello

Il dominio del problema è modellato attraverso una lista di variabili
X1, …, Xn

La conoscenza del dominio del problema è rappresentata dalla sua
distribuzione di probabilità congiunta P(X1, …, Xn)

E la P(X1, …, Xn) può essere descritta e calcolata con varie tecniche tra cui
le reti Bayeiane
24
Cosa è una rete Bayesiana?
Un modello grafico che descrive efficientemente le
probabilità congiunte di un insieme di variabili
Nell’esempio precedente un BN consente di descrivere il comportamento
delle v.a. {B, E, A, J, M} e calcolare efficientemente la P(B, E, A, J, M)
25
Come?
Per mezzo di un Directed Acyclic Graph (DAG)
i cui nodi rappresentano variabili aleatorie e gli archi le dipendenze tra esse:
La mancanza di un arco denota l’indipendenza condizionata tra le variabili.
P(J | A,B,E,M) = P(J | A)
Una rete Bayesiana è definita per mezzo di:

Una struttura di rete S che codifica le indipendenze condizionali tra le
variabili X

Un insieme di distribuzioni locali di probabilità P
26
Causalità
Per rappresentare graficamente le relazioni di dipendenza condizionata,
bisogna costruire un grafo diretto
Se ad esempio tracciamo un arco che va da Xj a Xi
tale operazione identifica in modo univoco il set pa(Xi) di “parents” o
“genitori” del nodo Xi che in questo caso semplice contiene solo Xj
27
Distribuzioni condizionate
Ad ogni nodo è associata una la distribuzione condizionata, rappresentata
da una Conditional Probability Table (CPT)
P(Xi | pa(Xi)) per ogni nodo Xi
28
Conditional Probability Tables
29
Vantaggio della BN (1)
In generale i casi per i queli bisogna calcolare la
probabilità sono 25 in realta 31 perché il 32esimo è
ottenuto per (1- tutti gli altri casi)
Nel caso si usi una rete bayesiana essi sono 1 + 1 + 4 +
2 + 2 = 8 !!
30
Fattorizzazione della Congiunta
è sempre possibile scrivere la probabilità congiunta
tramite la “chain-rule”:
Grazie all’assunzione di indipendenza condizionata tra le
variabili nel DAG
31
Probabilità congiunta:

Grazie alla formulazione fatta, il dominio consente di identificare un sottoinsieme
pa(Xi) (genitori di Xi) di {X1, …, Xi –1} tale che:
 Dato pa(Xi), Xi è indipendente da tutte le variabili in {X1, …, Xi -1} tranne pa{Xi},
cioè:
P(Xi| X1, …, Xi –1) = P(Xi| pa(Xi))

la distribuzione congiunta totale è definita come prodotto di termini locali:
P (X1, … ,Xn) =
π
i=1
P (Xi | pa ( Xi ) )
P( j , m , a , b ,e)= P (j | a) P (m | a) P (a | b, e) P (b) P (e)
32
Inferenza - classificazione

Qual è la probabilità che ci sia uno scassinatore dato che Mary ha telefonato
P(B = y | M = y)?

Si calcolala probabilità marginale:
P(B , M) = ΣE,A,J P(B, E, A, J, M)
P(M) = ΣB P(B, M)

Si usa infine la definizione di probabilità condizionata
P(B = y | M = y)= P(B = y , M = y)* P(M = y)

Classifico che lo scassinatore è in casa se P(B = y | M = y) > P(B = n | M = y)
33
Vantaggio della BN (2)

Se non assumessimo che alcune variabili sono condizionatamente
indipendenti tra loro avremmo una complessità maggiore sia nella
costruzione del modello che nel fare inferenza

Nell’esempio:



Sono richiesti 31 valori di probabilità (25-1)
Calcolare P(B = y | M = y) richiede un gran numero di addizioni (29)
In generale


P(X1, …, Xn) richiede almeno 2n–1 valori per specificare la probabilità
congiunta
Inferenza e spazio di memorizzazione esponenziali
34
Come costruiamo una BN
•
•
•
•
•
Sono necessari due tipi di apprendimento uno della struttura e
l’altro delle probabilità condizionate
Entrambi possono essere acquisiti dai dati con opportuni
algoritmi di apprendimento
È possibile costruire la struttura conoscendo un problema ed
andando a collegare le variabili in modo opportuno dando al
collegamento il significato di causa->effetto come nel caso
I giudizi di indipendenza condizionale e/o causa ed effetto
possono influenzare la formulazione di problema
le valutazioni di probabilità possono condurre ai cambiamenti
nella struttura della rete
35
Esempio di costruzione di un grafo
Nel caso volessimo apprendere la struttura solo dai dati:

Scegliere un insieme di variabili che descrivono il dominio
dell’applicazione

Scegliere un ordine per le variabili

Partire dalla rete vuota ed aggiungere le variabili alla rete una per
una in accordo all’ordine prescelto

Aggiungere l’i-sima variabile Xi e determinare pa(Xi) delle variabili
già nella rete (X1, …, Xi –1) tale che:
P(Xi| X1, …, Xi –1) = P(Xi| pa(Xi))

Tracciare un arco da ognuna delle variabili in pa(Xi) a Xi
36
Esempi:
37
Esempio di costruzione del grafo

Supponiamo di scegliere l’ordine M, J, A, B, E
P(J | M) = P(J)?
38
Esempio di costruzione del grafo

Supponiamo di scegliere l’ordine M, J, A, B, E
P(J | M) = P(J)? No
P(A | J, M) = P(A | J)? P(A | J, M) = P(A)?
39
Esempio: di costruzione del grafo:

Supponiamo di scegliere l’ordine M, J, A, B, E
P(J | M) = P(J)?No
P(A | J, M) = P(A | J)? P(A | J, M) = P(A)? No
P(B | A, J, M) = P(B | A)?
P(B | A, J, M) = P(B)?
40
Esempio: di costruzione del grafo:

Supponiamo di scegliere l’ordine M, J, A, B, E
P(J | M) = P(J)? No
P(A | J, M) = P(A | J)? P(A | J, M) = P(A)? No
P(B | A, J, M) = P(B | A)? Yes
P(B | A, J, M) = P(B)? No
P(E | B, A ,J, M) = P(E | A)?
P(E | B, A, J, M) = P(E | A, B)?
41
Example

Supponiamo di scegliere l’ordine M, J, A, B, E
P(J | M) = P(J)? No
P(A | J, M) = P(A | J)? P(A | J, M) = P(A)? No
P(B | A, J, M) = P(B | A)? Yes
P(B | A, J, M) = P(B)? No
P(E | B, A ,J, M) = P(E | A)? No
P(E | B, A, J, M) = P(E | A, B)? Yes
42
Esempio: di costruzione del grafo



Decidere l’indipendenza condizionale è difficile e la causalità può
essere appresa in modo totalmente inconsistente con quanto ci
viene dall’esperienza!
La rete diventa lievemente più complessa: abbiamo bisogno di 1 + 2
+ 4 + 2 + 4 = 13 numeri
Abbiamo bisogno di metodo che ci guidi nella costruzione del grafo
43
Apprendimento
Il precedente metodo per costruire una BN risente di alcune
controindicazioni. In particolare, la scelta dell’ordine delle variabili è un task
delicato. Scegliere un ordine sbagliato può portare la BN a degenerare
verso un grafo completamente connesso (caso peggiore)

Quali sono i requisiti per valutare la bontà di un grafo?
ad esempio la likelihood:

Esistono metodi di apprendimento che massimizzano la funzione di score:
score ( S )  log p( S | D)
che dipende dalle statistiche di Xi e dei sui parents
In una rete causale lo score totale può essere scomposto in somma di
termini locali! Permettendo un algoritmo di ricerca locale
44
Come usare una BN per classificare?

Per usare una BN come un classificatore, occorre calcolare:


dove y rappresenta la variabile classe e x è l’istanza da classificare.
Usando la distribuzione di probabilità P(U) rappresentata dalla BN, possiamo
scrivere che:
45
Perché usare un una rete bayesiana?
sono una struttura teorica molto utilizzata nell’ambito dell’apprendimento, della
classificazione, della rappresentazione della conoscenza

combinano conoscenza a priori e dati

Imparano relazioni causali -> fattorizzo la probabilità congiunta

I metodi Bayesiani sono importanti perché capaci di gestire data sets
incompleti e rumorosi
46
Benefici di apprendere strutture
•
Apprendimento efficiente: modelli più accurati con meno dati
•
Scoperta di proprietà strutturali del dominio
(grazie al comportamento di A posso prevedere la P(B|A) anche avendoa
disposizione un ridotto numero di dati provenienti dal solo B)
•
Aiuta ad ordinare eventi che avvengono sequenzialmente nella analisi
dell’inferenza
•
Predizione di effetti di azioni
47
Limitazioni di una rete Bayesiana
•
•
Richiedono tipicamente una conoscenza iniziale di molte
probabilità … e la qualità e grado della conoscenza a
priori giocano un ruolo importante
Gli algoritmi di apprendimento strutturale hanno un costo
computazionale significativo
48
Utilizzo
Data +prior
knowledge
Induce
Bayesian Network
49
Scenario 1


Addestramento (lab)
esercizio
Ref.
Computed QoE
codec
UDP
IP
Q
Q̂
PLR
jitter
BN
BER
Data link
fisico
P(Q | X1 ,…,XN)
50
Scenario 2 (Gap Filler)


Addestramento (in situ)
esercizio
X3
X4
X2
X5
??
P(X5 | X1, X2 ,X3 , X4 )
X1
51
Classificazione tramite rete bayesiana

Studio reti Bayesiane

Strumento potente calcolo veloce probabilità conguinte (dipendenze tra variabili
aleatorie)

Realizzazione di un classificatore

Contesto applicativo (Predittore Guasti Meccanici)



Evento a massima probabilità a posteriori dati gli osservabili
Cause scatenati del guasto (osservabili direttamente connessi col guasto)
Applicazioni


Database di dati simulati
Database di rilevazioni dal parco macchine (carrelli movimentatori) del porto di
Genova
52
Implementations in real life :
•
•
•
•
•
•
•
•
•
DLR/ESA knowledge information mining
Microsoft products(Microsoft Office)
Medical applications and Biostatistics (BUGS)
In NASA Autoclass projectfor data analysis
Collaborative filtering (Microsoft – MSBN)
Fraud Detection (ATT)
Speech recognition (UC , Berkeley )
Predizione incidentalità stradale
Carrelli movimentatori porto di Genova
53
Fault Tolerance

Nello specifico se il nostro scopo è prevedere i guasti in sistemi meccanici
che si trovano a bordo di camion che trasportano merci pericolose:


Bisogna costruire un sistema affidabile
Bisogna considerare che un guasto può provocare un nuovo guasto al motore
Dallo studio di uno specifico guasto potremmo trovare relazioni tra le cause:
Esempio:
ho fuso il motore!
quali sono le possibili cause?
54
Fault Tolerance
Esercitazione in lab
Da cosa può dipendere la fusione di un motore?



temperatura dell’acqua alta
poco olio nel motore
..
A
B
C
….
Realizzare una rete Bayesiana con il software Netica
55