Facoltà di Ingegneria
Dipartimento di Informatica ed Automazione
Tesi di Laurea Magistrale in
Ingegneria Gestionale e dell’Automazione
Anno Accademico 2012 - 2013
Laureando
Ludovico Pinzari
Relatore
Prof. Stefano Panzieri
Obiettivi
 Analitico:
Dempster Shafer
Theory of evidence
(DST)
 Metodologico:
Rule Based
Inference
Data Fusion System
(IDFS)
Indice
Caratteristiche modelli IDFS
Gestione del conflitto
Parameter Design problem
Unified Combination Rule α-model
Case Study: Plant Safety-Control
Conclusioni e Sviluppi Futuri
Tipologie di Incertezza
 Aleatoria: (Irriducibile,Oggettiva)
- Reti Bayesiane
Probabilità
singolo valore
 Epistemica: (Riducibile,Soggettiva)
- Imprecise Probability
- Possibility Theory
- Dempster and Shafer Theory
Interval Based Probability
Probabilità
intervallo di valori
1/26
Applicazioni della IBP
• Analisi del Rischio
- Stock Market
- Business and Marketing
• Sistemi Diagnostici
- Medici
- Processi Industriali
• Sistemi Di Navigazione Autonoma
- UV (Unmanned Aerial/Grounded Vehicle)
• Militare
- Target tracking/identification
• Biometrica
- Speech Recognition / Image processing
• Meccanica Quantistica
• …..
2/26
Perchè la DST ?
Probabilità
• Modello basato sulla teoria della
Insiemi
• Misura Esplicita dell’Incertezza: World Hypothesis
Closed
Universal
Open
Set
Misura
- Eventi elementari
Power Set
Ω = {A,B}
- Stati sconosciuti
Pr(Ø) = 0
Pr(Ω) = 1
- Ipotesi sconosciute
P(Ω) = {Ω,A,B,Ø} μ(P(Ω)): m
massa
0 ≤ Pr(Ø) ≤ 1
0 ≤ Pr(Ω) ≤ 1 • Flessibilità:
- UPDATING
AUB
m1
A
U
A
B
B
m2
Ω U Ø
m12
3/26
DST FRAMEWORK (CWH)
m : 2  [ 0 1 ]
m(Ø) = 0
 m( X ) 
1
X   (  ), X 
bel : 2  [ 0 1 ]
bel(A) =
 m ( X )
X  A, X 
Pr(Ø) = 0
bel(Ø) = 0
pl(Ø) = 0
Impossibile
pl : 2  [ 0 1 ]
pl(A) =
 m( B)
B  A , B 
Pr(Ω) = 1
bel(Ω) = 1
pl(Ω) = 1
Certo
4/26
Regole di Combinazione
Conjunctive Evidence (CE) :
RC
(m1  m2 ) ( A) 
 m ( B)  m (C ) ,
B C  A
1
2
A  
Disjunctive Evidence (DE) :
(m1  m2 ) ( A) 
 m ( B)  m (C ) ,
B C  A
1
(m1  m2      mn )( A)
2
A  
(m1  m2      mn )( A)
CE Pooling
Fiducia
DE Pooling
Diffidenza
(m1    mi  m j    mk  ml    mn )( A)
Trade-off Pooling
5/26
Il Problema del conflitto
Massa del Conflitto:
m12 ( ) 
m12 ( A) 
 m ( B)  m (C ) ,
B C 
1
B, C  
2
 m ( B)  m (C ) ,
B C  A
1
2
Prove
Discordi
A  
Prove
Comuni
Regola di Dempster
m1 ( A) 
m2 ( A) = m(A) =
Corpo Prove Consistenti
m12 ( )
m ( A)


A , 
12
=
m12 ( A)
1  m12 ( )
 m ( B)  m (C )
B C 
1
2

k D  m12 ( A)
Fattore di
Normalizzazione
Di
Dempster
6/26
Il Peso del conflitto
Con ( Bel1 , Bel 2 )  log (k D )   log  1  m( )

w
Dempster
• Supporta le Prove
Meno sostenute
• Sensibile per Alti valori
m( )  1
Con ( Bel1 , Bel 2 )  
m( )  0
Con ( Bel1 , Bel 2 )  0
Basso Conflitto
Situazioni
di Conflitto
Intermedie
Alto
Conflitto
7/26
La Gestione del conflitto
Ground Probability assignment:
q (A) 
q : 2  [ 0 1 ]
 m1 ( B)  m2 (C ) , A  
Prove
Comuni
B C  A
q ( ) 
 m ( B)  m (C ) ,
1
B C 
2
B, C  
m(Ø) = 0
m ()  q()  q( )
Non Normalizzo
m (A)  q (A)
Yager
divergenza
aleatorità
Aumento
l’incertezza
totale
Intermedio
q( )
Alto
Basso
Conflitto
UPDATE
Prove
Discordi
q ( )
m () 
1  q ( )
q( A)
m (A) 
1  q( )
Confermo le
Prove
Comuni
Dempster
convergenza
aleatorità
8/26
Unified Combination Rule
evidence
m (C) 
 f (C )  1,
q (C )
scaling

conflict
f (C )  q( )
CWH:
f (C )  0
C   ,C 
K
Updating Framework:
mku (C )  1  K  q( ) q(C),
C  ,

f (C ) f ( D)

q(C ) q( D)
C , D  , 
mku ( X )  1  K  q( ) q()  1  K  q( )  K  q( )
K  F (q( X ), q( ))
K - Operating Range:
K 0
YAGER’S
RULE
INTERPOLAZIONE
DEMPSTER’S RULE
KY  K  KD
q( A)
1  q( )
DEMPSTER’S
RULE
ESTRAPOLAZIONE
DEMPSTER’S RULE
NB: m(Ω) = q(Ω)
1
1  q( )  q()
KD  K  KI
INAGAKI’S
EXTRA
RULE
9/26
Parameter design Kd
KD  KI

1
1  q ( )
Agente 2
KD  
P(A)
w
P(B)
0
1
0
0
KD  4
w0
KD  1
Agente1 m2 ( A, B)
m1 ( A)  1
q( )
q ( A)
q (B )
w2
KD  2
4
KD 
3
w  0.4
1
0
0
1
0
1
w 1
0.75 0.25
0.25
0.75
0
0.25 0.75
0.75
0.25
0
0.5 0.5
0.5
0.5
0
q( )
10/26
Parameter design Ki
Agente 2
Ω (CWH)
mS1
mS2
mS3
mS4
A
0
0.25
0.5
0.75
B
0
0
0
0
Ω
1
0.75
0.5
0.25
Pl(A)=1
Bel(A)=0
A
0.75
0
B
Ω
A2S1    2
B
0.5
A
0.75 1
1
0.25
0
0
A
A
1
0.5
1
Pl(B)=1
Bel(B)=0
1
0.25
A2  1
B
A
B
Ω
Ω
Ω
A2S 2  1.75
A2S 3  1.5
A2S 4  1.25
11/26
Parameter design Ki
Agente 1
Label
Ω (CWH)
mS1
mS2
mS3
mS4
mS5
A
0
0
0
0
0
B
0.125
0.25
0.5
0.75
0.875
Ω
0.875
0.75
0.5
0.25
0.125
1
Pl(A)=0.875
Bel(A)=0
0.125
B
Ω
A1S1  1.875
0
1
0.25
A
B
Ω
A1S 2  1.75
1
0.5
A
1
0.25
0
0.5
0
Pl(B)=1
A
0.75
A2  1.125
B
0.75 1
A
B
Ω
Ω
A1S 3  1.5
A1S 4  1.25
12/26
Parameter design K
1
KI 
1  q( )  q()
K I  K D
K 0
q() K I  8 D
q( ) 0
q() 0.875
A
Ω
q( ) 0.1875
q() 0.1875
K I  1.6
K D  1.3
KI  KD
B
A
B
Ω
A
KI  1
q( ) 0
q() 0
0
1
B
Ω
KI  8
q( ) 0.875
q() 0
A
B
Ω
Nested Set
KI  KD
q( )
A
B
Ω
13/26
Parameter design K
Problema di Ottimizzazione
Universo delle
istanze
A
A
Ω
B
….
 K *  min f ( x1 ,.., xn , q( ), q())

gi ( x1 ,.., q( ), q()) , i  1,.., w
s.t :
Ω
K*v= ?
B
A
B
Ω
Trial and Error Tuning
X  
  f (d (m1 ( X ), m2 ( X )))

d (m1 ( X ), m2 ( X ))  0 1

?
K=
f(α)
14/26
α-parameter Model
 m ( B)  m (C ) ,
B C 
1
2
B, C  
  f ( KY , K D , K I )
?
?
α
   min ,  max 
K 
K 
KY  
KY
q(Ø)
q(Ø)

K
m(X)
?
KD  

KD
m(Ω)
KI  
K 

K

KI
15/26
α -> K Mapping
1

   1

1  q( )    q()
 1

 1     K D   0

 1  q( )
K  f ( ) :
α
-1
0
1
 I  1
+1
D  0
Y  1
0
KI

K
K

KD

K

KY
?
16/26
Parameter design α
1
f (q( ),  ) 
1  q ( )
q ( )  1 
f (q( ))  w(q( ))
w(q( )
--------
1

0
  1   log 2 e
  0
1
1 / 4 1 / 2 3 / 4 15 / 16
q1 ( ) q ( )
2
q3 ( ) q ( )
4

KD
q5 ( )
1
KY
1
c
 0.1
0
 0.3
1/4
0.5
1/2
q( )
0.75
3/4
15/16
17/26
Parameter design α

1 i
1  q ( )

2
lim
1  q( )
q ( )  1
  log 2 e
f (q( ),  i )  w(q( ))
ci

q ( )  0
1/ 2
1/ 4
1
 0.96
 1.44
qi ( )

15 / 16 1  (1 / 16) 1
3/ 4
0
w(q( ))
0
f (q( ),  i )
1
1  (0.5) 1
1  (0.75) 1
q1 ( )
 0.3
q2 ( )
1  (0.25) 1
 0.48
q3 ( )
 0.83
 0.65
q4 ( )
q5 ( )
q( )
18/26
Parameter design α
 q(X )
A
KD
 q( X )  q()  q( )  1
Ω
B
KY , KD ,K I
Ω
0.3
A
B
 0.3
0
B
Ω
0.25
A
0.5625
A
KY
1
Regione
Critica
q(Ω)≈q(Ø)
Ω
A
 0.3 c
B
0.0625
A
B
B
1    1/ 4
Ω
A
A
B
1/ 4    0
B
KI
1  q( )  0.3 q()  0.25 q ()  0.25
Ω
A
B
indifferente
0    1
q()
19/26
Extended Model
 q( X ) 

K P  K I 1 
 q( ) 
S1  S 2
Si  2
Ω (CWH)
Bel
Pl
Bel
Pl
A
0.5
1
0
0.5
B
0
0.5
0.5
1
B = 0.25
C
0
0.5
0
0.5
C=0
2
5/ 3
∑q(X)
q(Ω)
q(Ø)
0.25
0.25
A = 0.25
3/ 2
1
ESTRAPOLAZIONE
YAGER
KY  0
DEMPSTER
KD  4 / 3
INAGAKI
KI  2
PINZARI’S RULE
KP  4
20/26
CASE STUDY
CONTROL POLICY (CP)
FAULT WARNING CP :
Segnalazione di una situazione imprevista
SAFETY PRESERVATION CP:
Mantenimento della condizione operativa
SAFETY
21/26
Power Set Mapping
Stato Incerto
Sicuro
m(GO:FW)
m(S) + m(Ω)
m(GO:SP)
m(S)
m(SD:SP)
m(U) + m(Ω)
{S,U}
{S}
P(Ω)
Non Sicuro
{U}
m(SD:FW)
m(U)
{Ø}
GO:
Attivo
Non Bloccare
SD:
Blocco
Non Attivare
22/26
Optimization problem K
DS = {GO,SD}
m(DS,CP) = f ( q ( ))
CP = {FW,SP}
Problema di Ottimizzazione per la soluzione più cautelativa

min
K* :  K
max

 K
K
mCP
(GO)
K
CP
m ( SD)
FAULT WARNING:
K  KY
KI 
SAFETY PRESERVATION:
GO
mY  m D  m I
GO
mY  m D  m I
SD
mY  m D  m I
SD
mY  m D  m I
I
I
DS  arg max{ mGO
, mSD
}
i {GO, SD}
Y
Y
DS  arg max{ mGO
, mSD
}
i {GO, SD}
23/26
Analisi sensitività K
Basso Conflitto
 q( X )  0.76
q( )  0.20
q()  0.04
24/26
Analisi sensitività K
Alto Conflitto
 q( X )  0.34
q( )  0.65
q ()  0.01
25/26
Conclusioni Sviluppi Futuri
• K-optimization problem
• Sequencing problem
  Dempster
((m1  m2 )  m3 )( A)  (m1  (m2  m3 ))( A)
• Processi non stazionari
t
?
t
((m1  m2 )  (m3  m4 ))( A)  ((m3  m4 )  (m1  m2 ))( A)
• Trade-off Pooling
(m1    mi  m j    mk  ml    mn )( A)
• Augmented Extended Model
KI
KP

26/26
Conoscere l’Ignoranza è forza
Ignorare la Conoscenza è debolezza
Domande?