1 Fault Tollerance and Bayesian Networks Progetto Tramp Applicazione di tecniche di intelligenza...

11

Fault Fault TolleranceTollerance and and

Bayesian Networks Bayesian Networks

Progetto TrampProgetto Tramp

Applicazione di tecniche di intelligenza artificiale Applicazione di tecniche di intelligenza artificiale per la realizzazione di sistemi fault tolerant per la realizzazione di sistemi fault tolerant

Ing. Alessandra Scotto di FrecaIng. Alessandra Scotto di FrecaPh.D. presso l’Università degli Studi di CassinoPh.D. presso l’Università degli Studi di Cassino

[email protected]@unicas.it

22

Fault ToleranceFault Tolerance Cosa vuol dire essere tolleranti ai guasti?Cosa vuol dire essere tolleranti ai guasti?

Prevedere i guasti prima chePrevedere i guasti prima chesi verifichino e recuperarli si verifichino e recuperarli

Il problema della previsione di guastiIl problema della previsione di guasti ClassificazioneClassificazione Apprendimento Apprendimento Costruzione di un modello!!Costruzione di un modello!!

33

La ClassificazioneLa Classificazione un problema di classificazione può essere:un problema di classificazione può essere:

Possiamo formularlo in termini probabilistici:Possiamo formularlo in termini probabilistici:

L’oggetto X ha peso = 100 g e diametro = 10cm è una mela o una pera?L’oggetto X ha peso = 100 g e diametro = 10cm è una mela o una pera?

P(oggetto = mela | peso = 100 g, diametro = 10cm ) = ??P(oggetto = mela | peso = 100 g, diametro = 10cm ) = ??P(oggetto = pera | peso = 100 g, diametro = 10cm ) = ??P(oggetto = pera | peso = 100 g, diametro = 10cm ) = ??

P(oggetto = mela | peso = 100 g, diametro = 10cm ) = 0.7P(oggetto = mela | peso = 100 g, diametro = 10cm ) = 0.7P(oggetto = pera | peso = 100 g, diametro = 10cm ) = 0.3P(oggetto = pera | peso = 100 g, diametro = 10cm ) = 0.3

44

Tecniche di ClassificazioneTecniche di ClassificazioneCome posso calcolare la P(oggetto = mela | peso = 100 g, diametro = 10cm ) ???Come posso calcolare la P(oggetto = mela | peso = 100 g, diametro = 10cm ) ???

Teorema di BayesTeorema di Bayes

P(A | B) = P(A | B) = P(B | A) P(A)P(B | A) P(A) P(B)P(B)

P (A | B) A Posteriori di A dato BP (B | A ) verosimiglianza (likelihood)P (A) A priori di AP (B) A priori di B

55

Classificazione in breve!Classificazione in breve!

66

Introduzione alle reti BayesianeIntroduzione alle reti Bayesiane

Elementi di ProbabilitàElementi di Probabilità Interpretazione Bayesiana della probabilità Interpretazione Bayesiana della probabilità Cosa è una Rete BayesianaCosa è una Rete Bayesiana Come viene usata per classificare Come viene usata per classificare (inferenza)(inferenza)

Costruzione di una Rete Bayesiana Costruzione di una Rete Bayesiana (apprendimento ottenuto dal (apprendimento ottenuto dal mix di conoscenza a priori e dall’osservazione dei dati)mix di conoscenza a priori e dall’osservazione dei dati)

Perché usare una Rete BayesianaPerché usare una Rete Bayesiana Scenari applicativiScenari applicativi

77

Elementi di probabilitàElementi di probabilità Definizione di probabilità:Definizione di probabilità:

Considerato un evento E la probabilità che esso si verifichi è il rapporto 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 fra il numero F dei casi favorevoli (al verificarsi di E) e il numero N dei casi possibili, giudicati egualmente probabili.casi possibili, giudicati egualmente probabili.

P(E) = F / NP(E) = F / N

Poiché l’ipotesi di eventi egualmente probabili è difficile da osservare si Poiché l’ipotesi di eventi egualmente probabili è difficile da osservare si preferisce la definizione frequentista:preferisce la definizione frequentista:

P(E) = limP(E) = limN->N->∞∞ F / N F / N

P(E) è un numero reale compreso tra 0 e 1 e la somma della probabilità 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)=1dell’evento e dell’evento negato deve fare uno P(E)+P(!E)=1

88

Elementi di probabilitàElementi di probabilità

Definizione di probabilitàDefinizione di probabilità

Media (o valore atteso di una variabile discreta X)Media (o valore atteso di una variabile discreta X) E [ X ] = E [ X ] = ΣΣi i xxi i P(xP(xii))

VarianzaVarianza Var(X) = E [ ( X Var(X) = E [ ( X -- E [ X ]) E [ X ])22 ] = E[ X ] = E[ X2 2 ] ] -- E [ X ] E [ X ]22

Probabilità congiunta Probabilità congiunta èè la probabilità che si verifichino congiuntamente più eventila probabilità che si verifichino congiuntamente più eventi P(A,B) = P (A P(A,B) = P (A ^ ^ B) B)

In In generalegenerale P(A,B) = P(A | B)P(B) = P(B | A) P(A)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) Nel caso in cui A e B siano indipendenti P(A,B) = P(A)* P(B)

Probabilità condizionataProbabilità condizionata È la probabilità dell’evento A condizionatamente a B: P(A | B) = P(A,B)/P(B)È la probabilità dell’evento A condizionatamente a B: P(A | B) = P(A,B)/P(B)

Teorema di BayesTeorema di BayesP(A | B) = P(A | B) = P(B | A) P(A)P(B | A) P(A)

P(B)P(B)

99

Elementi di probabilitàElementi di probabilità

Probabilità marginaleProbabilità marginale È la probabilità di un unico evento, questa può essere ottenuta dalla È la probabilità di un unico evento, questa può essere ottenuta dalla

congiunta sommando P(A)= congiunta sommando P(A)= ΣΣi i P(A,BP(A,Bii))

BBii

AAii

Ai=0 Ai=1Ai=0, Bi=0

Ai=1, Bi=1

Ai=0, Bi=1

Ai=1, Bi=0

1010

Interpretazione Interpretazione Probabilità BayesianaProbabilità Bayesiana Probabilità classica: è una proprietà fisica del mondoProbabilità classica: è una proprietà fisica del mondo

““E’la vera probabilità!!”E’la vera probabilità!!”

Probabilità Bayesiana: è il grado con il quale una persona crede che un evento X si Probabilità Bayesiana: è il grado con il quale una persona crede che un evento X si verifichi. verifichi.

E’una probabilità personale!!E’una probabilità personale!!

Al contrario della probabilità classica calcolata con l’approccio frequentista, le probabilità Al contrario della probabilità classica calcolata con l’approccio frequentista, le probabilità bayesiane beneficiano del fatto che sono richieste un numero di prove inferiore. bayesiane beneficiano del fatto che sono richieste un numero di prove inferiore.

ESEMPIO: ESEMPIO: Calcolare la probabilità che il Napoli vinca la prossima partita?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 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 egualmente possibili implica di avere definito in precedenza la probabilità nel momento stesso in cui la si definisce.cui la si definisce.

P(P(““Napoli vinca”) = 1/3 ??Napoli vinca”) = 1/3 ??

Nella definizione frequentista si potrebbe controllare l’almanacco e calcolate il limite N->infNella 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. 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à Da questi si acquisisce un grado di credenza(“belief”) tale da consentire la stima della probabilità

Gioca in casa?Gioca in casa? In che condizioni sono i sui giocatori?In che condizioni sono i sui giocatori?

P( “Napoli vinca”| conoscenza dei fattori condizionanti e dell’esperienza )P( “Napoli vinca”| conoscenza dei fattori condizionanti e dell’esperienza )

1111

Problema della punessa:Problema della punessa:quando la lancio essa cadrà sulla testa o sulla punta??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 Come faccio a stimare la probabilità che al prossimo lancio la punessa cada sulla testa avendo a disposizione N lanci precedenti?avendo a disposizione N lanci precedenti?

Grazie alla teoria Bayesiana:Grazie alla teoria Bayesiana:

Definendo D = {XDefinendo D = {X1 1 = h, X= h, X2 2 = h, X= h, X3 3 = t, ………, X= t, ………, XN N = t} dati osservati e = t} dati osservati e esperienza o conoscenza esperienza o conoscenza a priori del fenomenoa priori del fenomeno

Devo calcolareDevo calcolareP(XP(XN+1N+1= heads | D,= heads | D,))

Probabilità BayesianaProbabilità Bayesiana

1212

InferenzaInferenza

Classificare il prossimo evento consiste nel calcolo della Classificare il prossimo evento consiste nel calcolo della probabilità di interesse dato un modello: fare inferenzaprobabilità di interesse dato un modello: fare inferenza

dati osservatidati osservati QueryQuery

x1 x2 x[N] x[N+1]

1414

Definendo Definendo corrispondente al possibile valore vero della probabilità fisica, a cui corrispondente al possibile valore vero della probabilità fisica, a cui nella teoria bayesiana ci si riferisce come “parametro” di cui posso calcolare una nella teoria bayesiana ci si riferisce come “parametro” di cui posso calcolare una A Priori p(A Priori p( | | ) ed un A Posteriori ) 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 Dal teorema di Bayes possiamo calcolare la probabilità a posteriori di dato D dato D (dati osservati) e (dati osservati) e conoscenza a priori: conoscenza a priori:

p(p( | D, | D, ) = ) = p(p( | | ) p (D | ) p (D | , , ) ) dove dove p(D | p(D | ) = p(D | ) = p(D | , , ) p() p( | | ) d ) d

P(D | P(D | ))

p(p( | | ) ) è la A Priori di è la A Priori di

p (D | p (D | , , ) è la likelihood che nel problema della punessa in cui le osservazioni si ) è la likelihood che nel problema della punessa in cui le osservazioni si D sono mutuamente indipendenti può essere considerata binomiale D sono mutuamente indipendenti può essere considerata binomiale

hh (1- (1-))tt

Probabilità BayesianaProbabilità Bayesiana

1515

Funzione di verosimiglianzaFunzione di verosimiglianza

La bontà del parametro La bontà del parametro viene misurata con la viene misurata con la funzione di verosimiglianza: funzione di verosimiglianza:

L (L (, D ) = P( D | , D ) = P( D | ) )

(una volta scelto (una volta scelto lo si testa vedendo quanto bene esso è capace di lo si testa vedendo quanto bene esso è capace di generare dati osservati)generare dati osservati)

Quindi la funzione di verosimiglianza della sequenza H, T,H,T ,T può Quindi la funzione di verosimiglianza della sequenza H, T,H,T ,T può

essere: L (essere: L ( ,D ) = ,D ) = .. (1- (1- ) ) .. .. (1 - (1 - ) ) .. (1 - (1 - ))

1616

statistica sufficientestatistica sufficiente

Per calcolare la funzione di verosimiglianza nel problema della punessa 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 sono richiesti solo h e t ossia il numero di volte che la punessa è caduta sulla testa e quello in cui è caduta sulla puntasulla testa e quello in cui è caduta sulla punta

h e t sono chiamate statistiche sufficienti per una distribuzione binomialeh e t sono chiamate statistiche sufficienti per una distribuzione binomiale

Una statistica sufficiente riassume dai dati le informazioni rilevanti per la Una statistica sufficiente riassume dai dati le informazioni rilevanti per la funzione di verosimiglianzafunzione di verosimiglianza

1717

A Priori 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

1818

Esempi di distribuzioni BetaEsempi 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!!

1919

In fineIn fine ….. …..

Mediando sui possibili valori di Mediando sui possibili valori di per determinare la per determinare la probabilità che al lancio N+1 la punessa cada sulla testa:probabilità che al lancio N+1 la punessa cada sulla testa:

P(XP(XN+1N+1=heads | D,=heads | D,) = ) = p( p( | D, | D, ) d) d

Usando la distribuzione Beta tale valore atteso di Usando la distribuzione Beta tale valore atteso di

rispetto alla distribuzione di p(rispetto alla distribuzione di p(/D,/D, ) diventa) diventa ::

Dove α = αh + αt e N è il numero di osservazioni totali

2020

… … più in generalepiù in generale

L’esempio della punessa descrive un caso in cui la variabile aleatoria da L’esempio della punessa descrive un caso in cui la variabile aleatoria da considerare assume valori discreti considerare assume valori discreti In questo caso abbiamo assunto che la distribuzioni a priori fosse una Beta In questo caso abbiamo assunto che la distribuzioni a priori fosse una Beta ma nel caso generale lama nel caso generale la

P(XP(XN+1N+1=heads | D,=heads | D,) = ) = p( p( | D, | D, ) d) d

Può essere calcolata efficientemente e in forma chiusa ipotizzando Può essere calcolata efficientemente e in forma chiusa ipotizzando distribuzioni multinomiali, normali, Gamma, Poisson e normali multivariatedistribuzioni multinomiali, normali, Gamma, Poisson e normali multivariate

che includono anche il caso in cui X assume valori continui e quello in cui 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. invece di una signola X ho un vettore di variabili aleatorie.

Se ad esempio la modelliamo con una gaussiana il parametro da stimare Se ad esempio la modelliamo con una gaussiana il parametro da stimare sarà sarà ={media, varianza}={media, varianza}

Nel caso in cui X è un vettore di variabili aleatorie la P(Nel caso in cui X è un vettore di variabili aleatorie la P(XX) può essere ) può essere studiata tramite una rete bayesiana andando a considerare anche le studiata tramite una rete bayesiana andando a considerare anche le dipendenze tra variabili dipendenze tra variabili

2121

Problema di ClassificazioneProblema di Classificazione

Come usiamo le informazioni viste fin ora per costruire un classificatore? Come usiamo le informazioni viste fin ora per costruire un classificatore?

Bisogna capire a quale è l’evidenza dalla quale vogliamo trarre Bisogna capire a quale è l’evidenza dalla quale vogliamo trarre informazioni allo scopo di classificare !informazioni allo scopo di classificare !

Possiamo usare più informazioni contemporaneamente per ottenete Possiamo usare più informazioni contemporaneamente per ottenete risultati di classificazione miglioririsultati di classificazione migliori

2222

EsempioEsempio La storia:La storia: Paolo ha un nuovo allarme anti-scasso sulla sua autovettura che funziona molto bene 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 nel prevenire i furti, ma alcune volte risponde positivamente a piccole scosse di terremoto. Due vicini di casa di Paolo, Mary e vicini di casa di Paolo, Mary e JohnJohn, hanno promesso di avvisarlo nel caso scattasse l’allarme , hanno promesso di avvisarlo nel caso scattasse l’allarme mentre lui si trova al lavoro. mentre lui si trova al lavoro. JohnJohn chiama sempre quando scatta l’allarme, ma a volte si confonde 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 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.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 Problema: Stimare la probabilità che ci sia uno scassinatore sulla base di chi ha o no telefonato ( classificare un furto! ) telefonato ( classificare un furto! )

Variabili: Scassinatore(B), Terremoto(E), Allarme(A), Chiamata di John (J), Chiamata Variabili: Scassinatore(B), Terremoto(E), Allarme(A), Chiamata di John (J), Chiamata di Mary (M)di Mary (M)

Conoscenza richiesta per risolvere il problema: Conoscenza richiesta per risolvere il problema:

P(B, E, A, J, M)P(B, E, A, J, M) (distribuzione congiunta di probabilità)(distribuzione congiunta di probabilità)

Tale conoscenza viene usata per formalizzare il problema di classificazione come:Tale conoscenza viene usata per formalizzare il problema di classificazione come: P(B| E, A, J, M) apprendendo la congiunta precedente daP(B| E, A, J, M) apprendendo la congiunta precedente da i dati osservati D ossia dalle i dati osservati D ossia dalle

istanze degli stati del vettore di v.a. {B, E, A, J, M}istanze degli stati del vettore di v.a. {B, E, A, J, M}

2323

Nota la distribuzione congiunta Nota la distribuzione congiunta

Ho 25 valori che abbiamo assunto essre noti ma come faccia in genere per apprenderli ?

2424

Costruzione del modelloCostruzione del modello

Il dominio del problema è modellato attraverso una lista di variabili Il dominio del problema è modellato attraverso una lista di variabili X1, …, XnX1, …, Xn

La conoscenza del dominio del problema è rappresentata dalla sua La conoscenza del dominio del problema è rappresentata dalla sua distribuzione di probabilità congiunta P(X1, …, Xn)distribuzione di probabilità congiunta P(X1, …, Xn)

E la E la P(X1, …, Xn)P(X1, …, Xn) può essere descritta e calcolata con varie tecniche tra cui può essere descritta e calcolata con varie tecniche tra cui le reti Bayeianele reti Bayeiane

2525

Un modello grafico che descrive efficientemente le Un modello grafico che descrive efficientemente le probabilità congiunte di un insieme di variabiliprobabilità congiunte di un insieme di variabili

Nell’esempio precedente un BN consente di descrivere il comportamento Nell’esempio precedente un BN consente di descrivere il comportamento delle v.a. delle v.a. {{B, E, A, J, M}B, E, A, J, M} e calcolare efficientemente la e calcolare efficientemente la P(B, E, A, J, M)P(B, E, A, J, M)

Cosa è una rete Bayesiana?Cosa è una rete Bayesiana?

2626

Come?Come? Per mezzo di un Directed Acyclic Graph (DAG)Per mezzo di un Directed Acyclic Graph (DAG)i cui nodi rappresentano variabili aleatorie e gli archi le dipendenze tra esse: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.La mancanza di un arco denota l’indipendenza condizionata tra le variabili.

P(J | A,B,E,M) = P(J | A)P(J | A,B,E,M) = P(J | A)

Una rete Bayesiana èUna rete Bayesiana è definita per mezzo di: definita per mezzo di: Una struttura di rete S che codifica le indipendenze condizionali tra le Una struttura di rete S che codifica le indipendenze condizionali tra le

variabili Xvariabili X Un insieme di distribuzioni locali di probabilità PUn insieme di distribuzioni locali di probabilità P

2727

Causalità Causalità

Per rappresentare graficamente le relazioni di dipendenza condizionata, Per rappresentare graficamente le relazioni di dipendenza condizionata, bisogna costruire un grafo diretto bisogna costruire un grafo diretto

Se ad esempio tracciamo un arco che va da Xj a Xi 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 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 “genitori” del nodo Xi che in questo caso semplice contiene solo Xj

2828

Distribuzioni condizionateDistribuzioni condizionate

Ad ogni nodo è associata una la distribuzione condizionata, rappresentata da una Conditional Probability Table (CPT)

P(Xi | pa(Xi)) per ogni nodo Xi

2929

Conditional Probability Tables

3030

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 !!

Vantaggio della BN (1)Vantaggio della BN (1)

3131

è sempre possibile scrivere la probabilità congiunta è sempre possibile scrivere la probabilità congiunta tramite la “chain-rule”:tramite la “chain-rule”:

Fattorizzazione della CongiuntaFattorizzazione della Congiunta

Grazie all’assunzione di indipendenza condizionata tra le Grazie all’assunzione di indipendenza condizionata tra le variabili nel DAGvariabili nel DAG

3232

Grazie alla formulazione fatta, il dominio consente di identificare un sottoinsieme Grazie alla formulazione fatta, il dominio consente di identificare un sottoinsieme pa(Xi) (genitori di Xi) di {X1, …, Xi –1}pa(Xi) (genitori di Xi) di {X1, …, Xi –1} tale che: tale che: Dato pa(Xi), Xi è indipendente da tutte le variabili in {X1, …, Xi -1} tranne pa{Xi}, Dato pa(Xi), Xi è indipendente da tutte le variabili in {X1, …, Xi -1} tranne pa{Xi},

cioè:cioè:

P(Xi| X1, …, Xi –1) = P(Xi| pa(Xi))P(Xi| X1, …, Xi –1) = P(Xi| pa(Xi))

la distribuzione congiunta totale è definita come prodotto di termini locali:la distribuzione congiunta totale è definita come prodotto di termini locali:

P (XP (X11, … ,X, … ,Xnn) = ) = ππi = 1i = 1 P (X P (Xi i | pa ( X| pa ( Xi i ) )) )

P( j , m , a , b ,e)= P (j | a) P (m | a) P (a | b, e) P (b) P (e)P( j , m , a , b ,e)= P (j | a) P (m | a) P (a | b, e) P (b) P (e)

Probabilità congiunta:Probabilità congiunta:

3333

Inferenza - classificazioneInferenza - classificazione

Qual è la probabilità che ci sia uno scassinatore dato che Mary ha telefonato Qual è la probabilità che ci sia uno scassinatore dato che Mary ha telefonato

P(B = y | M = y)?P(B = y | M = y)?

Si calcolala probabilità marginale:Si calcolala probabilità marginale:

P(B , M) = P(B , M) = ΣΣE,A,J E,A,J P(B, E, A, J, M)P(B, E, A, J, M)

P(M) = P(M) = ΣΣB B P(B, M)P(B, M)

Si usa infine la definizione di probabilità condizionataSi usa infine la definizione di probabilità condizionata

P(B = y | M = y)= P(B = y , M = y)* P(M = y)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)Classifico che lo scassinatore è in casa se P(B = y | M = y) > P(B = n | M = y)

3434

Vantaggio della BN (2)Vantaggio della BN (2) Se non assumessimo che alcune variabili sono condizionatamente Se non assumessimo che alcune variabili sono condizionatamente

indipendenti tra loro avremmo una complessità maggiore sia nella indipendenti tra loro avremmo una complessità maggiore sia nella costruzione del modello che nel fare inferenzacostruzione del modello che nel fare inferenza

Nell’esempio:Nell’esempio: Sono richiesti 31 valori di probabilità (2Sono richiesti 31 valori di probabilità (255-1)-1) Calcolare P(B = y | M = y) richiede un gran numero di addizioni (29)Calcolare P(B = y | M = y) richiede un gran numero di addizioni (29)

In generaleIn generale P(X1, …, Xn) richiede almeno 2P(X1, …, Xn) richiede almeno 2nn–1 valori per specificare la probabilità –1 valori per specificare la probabilità

congiuntacongiunta Inferenza e spazio di memorizzazione esponenzialiInferenza e spazio di memorizzazione esponenziali

3535

• Sono necessari due tipi di apprendimento uno della struttura e l’altro Sono necessari due tipi di apprendimento uno della struttura e l’altro delle probabilità condizionate delle probabilità condizionate

• Entrambi possono essere acquisiti dai dati con opportuni algoritmi Entrambi possono essere acquisiti dai dati con opportuni algoritmi di apprendimento di apprendimento

• È possibile costruire la struttura conoscendo un problema ed È possibile costruire la struttura conoscendo un problema ed andando a collegare le variabili in modo opportuno dando al andando a collegare le variabili in modo opportuno dando al collegamento il significato di causa->effetto come nel casocollegamento il significato di causa->effetto come nel caso

• I giudizi di indipendenza condizionale e/o causa ed effetto possono I giudizi di indipendenza condizionale e/o causa ed effetto possono influenzare la formulazione di problema influenzare la formulazione di problema

• le valutazioni di probabilità possono condurre ai cambiamenti nella le valutazioni di probabilità possono condurre ai cambiamenti nella struttura della retestruttura della rete

Come costruiamo una BNCome costruiamo una BN

3636

Esempio di costruzione di un grafoEsempio di costruzione di un grafo

Nel caso volessimo apprendere la struttura solo dai dati:Nel caso volessimo apprendere la struttura solo dai dati:

Scegliere un insieme di variabili che descrivono il dominio Scegliere un insieme di variabili che descrivono il dominio dell’applicazionedell’applicazione

Scegliere un ordine per le variabiliScegliere un ordine per le variabili

Partire dalla rete vuota ed aggiungere le variabili alla rete una per Partire dalla rete vuota ed aggiungere le variabili alla rete una per una in accordo all’ordine presceltouna in accordo all’ordine prescelto

Aggiungere l’i-sima variabile Xi e determinare pa(Xi) delle variabili Aggiungere l’i-sima variabile Xi e determinare pa(Xi) delle variabili già nella rete (X1, …, Xi –1) tale che:già nella rete (X1, …, Xi –1) tale che:

P(Xi| X1, …, Xi –1) = P(Xi| pa(Xi))P(Xi| X1, …, Xi –1) = P(Xi| pa(Xi))

Tracciare un arco da ognuna delle variabili in pa(Xi) a XiTracciare un arco da ognuna delle variabili in pa(Xi) a Xi

3737

Esempi: Esempi:

3838

Supponiamo di scegliere l’ordineSupponiamo di scegliere l’ordine M, J, A, B, EM, J, A, B, E

PP(J | M) = (J | M) = PP(J)?(J)?

Esempio di costruzione del grafoEsempio di costruzione del grafo

3939

Supponiamo di scegliere l’ordine Supponiamo di scegliere l’ordine M, J, A, B, EM, J, A, B, E

PP(J | M) = (J | M) = PP(J)? (J)? NoNo

PP(A | J, M) = (A | J, M) = PP(A | J)(A | J)?? PP(A | J, M) = (A | J, M) = PP(A)(A)??

Esempio di costruzione del grafoEsempio di costruzione del grafo

4343

Decidere l’indipendenza condizionale è difficile e la causalità può Decidere l’indipendenza condizionale è difficile e la causalità può essere appresa in modo totalmente inconsistente con quanto ci essere appresa in modo totalmente inconsistente con quanto ci viene dall’esperienza! viene dall’esperienza!

La rete diventa lievemente più complessa: abbiamo bisogno di 1 + 2 La rete diventa lievemente più complessa: abbiamo bisogno di 1 + 2 + 4 + 2 + 4 = 13 numeri+ 4 + 2 + 4 = 13 numeri

Abbiamo bisogno di metodo che ci guidi nella costruzione del grafoAbbiamo bisogno di metodo che ci guidi nella costruzione del grafo

Esempio: di costruzione del grafoEsempio: di costruzione del grafo

4444

Apprendimento Apprendimento

Il precedente metodo per costruire una BN risente di alcune Il precedente metodo per costruire una BN risente di alcune controindicazioni. In particolare, la scelta dell’ordine delle variabili è un task controindicazioni. In particolare, la scelta dell’ordine delle variabili è un task delicato. Scegliere un ordine sbagliato può portare la BN a degenerare delicato. Scegliere un ordine sbagliato può portare la BN a degenerare verso un grafo completamente connesso (caso peggiore)verso un grafo completamente connesso (caso peggiore)

Quali sono i requisiti per valutare la bontà di un grafo?Quali sono i requisiti per valutare la bontà di un grafo?ad esempio la likelihood:ad esempio la likelihood:

Esistono metodi di apprendimento che massimizzano la funzione diEsistono metodi di apprendimento che massimizzano la funzione di score score::

che dipende dalle statistiche di Xi e dei sui parents che dipende dalle statistiche di Xi e dei sui parents In una rete causale lo score totale può essere scomposto in somma di In una rete causale lo score totale può essere scomposto in somma di termini locali! Permettendo un algoritmo di ricerca localetermini locali! Permettendo un algoritmo di ricerca locale

)|(log)( DSpSscore

4545

Come usare una BN per classificare?Come usare una BN per classificare?

Per usare una BN come un classificatore, occorre calcolare:Per usare una BN come un classificatore, occorre calcolare:

dove y rappresenta la dove y rappresenta la variabile classe variabile classe e x è l’istanza da classificare.e x è l’istanza da classificare. Usando la distribuzione di probabilità P(U) rappresentata dalla BN, possiamo Usando la distribuzione di probabilità P(U) rappresentata dalla BN, possiamo

scrivere che:scrivere che:

4646

Perché usare un una rete bayesiana?Perché usare un una rete bayesiana?

sono una struttura teorica molto utilizzata nell’ambito dell’apprendimento, della sono una struttura teorica molto utilizzata nell’ambito dell’apprendimento, della classificazione, della rappresentazione della conoscenzaclassificazione, della rappresentazione della conoscenza

combinano conoscenza a priori e dati combinano conoscenza a priori e dati

Imparano relazioni causali -> fattorizzo la probabilità congiunta Imparano relazioni causali -> fattorizzo la probabilità congiunta

I metodi Bayesiani sono importanti perché capaci di gestire data sets I metodi Bayesiani sono importanti perché capaci di gestire data sets incompleti e rumorosiincompleti e rumorosi

4747

Benefici di apprendere struttureBenefici di apprendere strutture

• Apprendimento efficiente: Apprendimento efficiente: modelli più accurati con meno datimodelli più accurati con meno dati

• Scoperta di proprietà strutturali del dominio Scoperta di proprietà strutturali del dominio

(grazie al comportamento di A posso prevedere la P(B|A) anche avendoa (grazie al comportamento di A posso prevedere la P(B|A) anche avendoa disposizione un ridotto numero di dati provenienti dal solo B)disposizione un ridotto numero di dati provenienti dal solo B)

• Aiuta ad ordinare eventi che avvengono sequenzialmente nella analisi Aiuta ad ordinare eventi che avvengono sequenzialmente nella analisi dell’inferenzadell’inferenza

• Predizione di effetti di azioniPredizione di effetti di azioni

4848

Limitazioni di una rete BayesianaLimitazioni di una rete Bayesiana

• Richiedono tipicamente una conoscenza iniziale di molte Richiedono tipicamente una conoscenza iniziale di molte probabilità … e la qualità e grado della conoscenza a probabilità … e la qualità e grado della conoscenza a priori giocano un ruolo importante priori giocano un ruolo importante

• Gli algoritmi di apprendimento strutturale hanno un costo Gli algoritmi di apprendimento strutturale hanno un costo computazionale significativocomputazionale significativo

4949

Utilizzo Utilizzo

Induce

Bayesian Network

Data +prior knowledge

5050

Scenario 1Scenario 1

Addestramento (lab)Addestramento (lab) esercizioesercizio

codec

UDP

IP

Data link

fisico

BER

jitter

PLR

BN

Q

Q̂

Computed QoERef.

P(Q | X1 ,…,XN)

5151

Scenario 2 (Gap Filler)Scenario 2 (Gap Filler)

Addestramento (in situ)Addestramento (in situ) esercizio esercizio

P(X5 | X1, X2 ,X3 , X4 )

X5 ??

X2

X1

X3

X4

5252

Classificazione tramite rete Classificazione tramite rete bayesianabayesiana

Studio reti BayesianeStudio reti Bayesiane Strumento potente calcolo veloce probabilità conguinte (dipendenze tra variabili Strumento potente calcolo veloce probabilità conguinte (dipendenze tra variabili

aleatorie)aleatorie)

Realizzazione di un classificatore Realizzazione di un classificatore

Contesto applicativo (Predittore Guasti Meccanici)Contesto applicativo (Predittore Guasti Meccanici) Evento a massima probabilità a posteriori dati gli osservabili Evento a massima probabilità a posteriori dati gli osservabili Cause scatenati del guasto (osservabili direttamente connessi col guasto)Cause scatenati del guasto (osservabili direttamente connessi col guasto)

Applicazioni Applicazioni Database di dati simulati Database di dati simulati Database di rilevazioni dal parco macchine (carrelli movimentatori) del porto di Database di rilevazioni dal parco macchine (carrelli movimentatori) del porto di

GenovaGenova

5353

Implementations in real life :Implementations in real life :

• DLR/ESA knowledge information miningDLR/ESA knowledge information mining• Microsoft products(Microsoft Office)Microsoft products(Microsoft Office)• Medical applications and Biostatistics (BUGS)Medical applications and Biostatistics (BUGS)• In NASA Autoclass projectfor data analysisIn NASA Autoclass projectfor data analysis• Collaborative filtering (Microsoft – MSBN)Collaborative filtering (Microsoft – MSBN)• Fraud Detection (ATT)Fraud Detection (ATT)• Speech recognition (UC , Berkeley )Speech recognition (UC , Berkeley )• Predizione incidentalità stradalePredizione incidentalità stradale• Carrelli movimentatori porto di GenovaCarrelli movimentatori porto di Genova

5454

Fault ToleranceFault Tolerance Nello specifico se il nostro scopo è prevedere i guasti in sistemi meccanici Nello specifico se il nostro scopo è prevedere i guasti in sistemi meccanici

che si trovano a bordo di camion che trasportano merci pericolose:che si trovano a bordo di camion che trasportano merci pericolose: Bisogna costruire un sistema affidabile Bisogna costruire un sistema affidabile Bisogna considerare che un guasto può provocare un nuovo guasto al motoreBisogna considerare che un guasto può provocare un nuovo guasto al motore

Dallo studio di uno specifico guasto potremmo trovare relazioni tra le cause:Dallo studio di uno specifico guasto potremmo trovare relazioni tra le cause:

Esempio: Esempio:

ho fuso il motore! ho fuso il motore!

quali sono le possibili cause?quali sono le possibili cause?

5555

Fault ToleranceFault Tolerance

Esercitazione in labEsercitazione in lab

temperatura dell’acqua altatemperatura dell’acqua alta poco olio nel motore poco olio nel motore ....

AA

BB

CC

……..

Realizzare una rete Bayesiana con il software Netica Realizzare una rete Bayesiana con il software Netica

Da cosa può dipendere la fusione di un motore?Da cosa può dipendere la fusione di un motore?

1 Fault Tollerance and Bayesian Networks Progetto Tramp Applicazione di tecniche di intelligenza...

Documents

Transcript of 1 Fault Tollerance and Bayesian Networks Progetto Tramp Applicazione di tecniche di intelligenza...