Pˇr´ıklady aplikac´ı bayesovsk´ych s´ıt´ı Jiˇr´ı Vomlel ´ ´ Ustav teorie informace a automatizace (UTIA) ˇ e republiky Akademie vˇ ed Cesk´ http://www.utia.cz/vomlel
Praha, 2. listopadu 2016
Obsah pˇredn´aˇsky
• Aplikace 1: Technick´ a diagnostika
Obsah pˇredn´aˇsky
• Aplikace 1: Technick´ a diagnostika • Aplikace 2: Adaptivn´ı testov´ an´ı znalost´ı
Obsah pˇredn´aˇsky
• Aplikace 1: Technick´ a diagnostika • Aplikace 2: Adaptivn´ı testov´ an´ı znalost´ı
ˇ ızen´ı rychlosti vozu F1 • Aplikace 3: R´
Technick´a diagnostika – optim´aln´ı strategie opravy • Pˇr´ıˇ ciny probl´emu (z´avady) C ∈ C.
Technick´a diagnostika – optim´aln´ı strategie opravy • Pˇr´ıˇ ciny probl´emu (z´avady) C ∈ C. • Akce A ∈ A - opravn´ e kroky, kter´e mohou odstranit z´avadu.
Technick´a diagnostika – optim´aln´ı strategie opravy • Pˇr´ıˇ ciny probl´emu (z´avady) C ∈ C. • Akce A ∈ A - opravn´ e kroky, kter´e mohou odstranit z´avadu. • Ot´ azky Q ∈ Q - kroky, kter´e mohou pomoci identifikovat, kde
je z´avada.
Technick´a diagnostika – optim´aln´ı strategie opravy • Pˇr´ıˇ ciny probl´emu (z´avady) C ∈ C. • Akce A ∈ A - opravn´ e kroky, kter´e mohou odstranit z´avadu. • Ot´ azky Q ∈ Q - kroky, kter´e mohou pomoci identifikovat, kde
je z´avada. • Ke kaˇ zd´e akci i ot´azce je pˇriˇrazena cena
(cA znaˇc´ı cenu akce A, cQ cenu ot´azky Q). Cena m˚ uˇze znamenat: – dobu potˇrebnou k proveden´ı akce ˇci ot´azky, – cenu za n´ahradn´ı d´ıl, kter´y pouˇzijeme – rizikovost akce – kombinaci v´yˇse uveden´eho.
Technick´a diagnostika laserov´e tisk´arny Trouble: svˇetl´y tisk. Troubleshooter: doporuˇc´ı kroky, kter´e vedou k odstranˇen´ı “trouble”
Technick´a diagnostika laserov´e tisk´arny Trouble: svˇetl´y tisk. Troubleshooter: doporuˇc´ı kroky, kter´e vedou k odstranˇen´ı “trouble” Akce a ot´azky A1 : Remove, shake and reseat toner A2 : Try another toner A3 : Cycle power Q1 : Is the printer configuration page printed light?
cena 5 15 1 2
Technick´a diagnostika laserov´e tisk´arny Trouble: svˇetl´y tisk. Troubleshooter: doporuˇc´ı kroky, kter´e vedou k odstranˇen´ı “trouble” Akce a ot´azky A1 : Remove, shake and reseat toner A2 : Try another toner A3 : Cycle power Q1 : Is the printer configuration page printed light? Moˇzn´e z´avady pˇri svˇetl´em tisku C1 : Toner low C2 : Defective toner C3 : Corrupted dataflow C4 : Wrong driver setting
P(Ci ) 0.4 0.3 0.2 0.1
cena 5 15 1 2
Bayesovsk´a s´ıt’ pro probl´em svˇetl´eho tisku Actions Causes Problem
A1
C1 A2
c1 c2 c3 c4
C2 A3 C3 Questions C4 Q1
Viz model v Huginu.
Oˇcek´avan´a cena opravy - ECR • Strategie m˚ uˇze skonˇcit ne´ uspˇeˇsnˇe - napˇr. jsme vyˇcerpali
vˇsechny moˇzn´e akce: - uplatn´ı se penalizace c(e` ) - penalizac´ı m˚ uˇze b´yt napˇr. cena, kterou zaplat´ıme za zavol´an´ı servisn´ıch technik˚ u
Oˇcek´avan´a cena opravy - ECR • Strategie m˚ uˇze skonˇcit ne´ uspˇeˇsnˇe - napˇr. jsme vyˇcerpali
vˇsechny moˇzn´e akce: - uplatn´ı se penalizace c(e` ) - penalizac´ı m˚ uˇze b´yt napˇr. cena, kterou zaplat´ıme za zavol´an´ı servisn´ıch technik˚ u • Strategie m˚ uˇze konˇcit vyˇreˇsen´ım probl´emu c(e` ) = 0.
Oˇcek´avan´a cena opravy - ECR • Strategie m˚ uˇze skonˇcit ne´ uspˇeˇsnˇe - napˇr. jsme vyˇcerpali
vˇsechny moˇzn´e akce: - uplatn´ı se penalizace c(e` ) - penalizac´ı m˚ uˇze b´yt napˇr. cena, kterou zaplat´ıme za zavol´an´ı servisn´ıch technik˚ u • Strategie m˚ uˇze konˇcit vyˇreˇsen´ım probl´emu c(e` ) = 0. • Z´ıskan´ a evidence
A = yes/no, A ∈ Proveden´e akce, e = Q = yes/no, Q ∈ Zodpovˇezen´e ot´azky
Oˇcek´avan´a cena opravy - ECR • Strategie m˚ uˇze skonˇcit ne´ uspˇeˇsnˇe - napˇr. jsme vyˇcerpali
vˇsechny moˇzn´e akce: - uplatn´ı se penalizace c(e` ) - penalizac´ı m˚ uˇze b´yt napˇr. cena, kterou zaplat´ıme za zavol´an´ı servisn´ıch technik˚ u • Strategie m˚ uˇze konˇcit vyˇreˇsen´ım probl´emu c(e` ) = 0. • Z´ıskan´ a evidence
A = yes/no, A ∈ Proveden´e akce, e = Q = yes/no, Q ∈ Zodpovˇezen´e ot´azky • P(e) ... pravdˇ epodobnost evidence e
Oˇcek´avan´a cena opravy - ECR • Strategie m˚ uˇze skonˇcit ne´ uspˇeˇsnˇe - napˇr. jsme vyˇcerpali
vˇsechny moˇzn´e akce: - uplatn´ı se penalizace c(e` ) - penalizac´ı m˚ uˇze b´yt napˇr. cena, kterou zaplat´ıme za zavol´an´ı servisn´ıch technik˚ u • Strategie m˚ uˇze konˇcit vyˇreˇsen´ım probl´emu c(e` ) = 0. • Z´ıskan´ a evidence
A = yes/no, A ∈ Proveden´e akce, e = Q = yes/no, Q ∈ Zodpovˇezen´e ot´azky • P(e) ... pravdˇ epodobnost evidence e • t(e) ... celkov´ a cena proveden´ych akc´ı a ot´azek
Oˇcek´avan´a cena opravy - ECR • Strategie m˚ uˇze skonˇcit ne´ uspˇeˇsnˇe - napˇr. jsme vyˇcerpali
vˇsechny moˇzn´e akce: - uplatn´ı se penalizace c(e` ) - penalizac´ı m˚ uˇze b´yt napˇr. cena, kterou zaplat´ıme za zavol´an´ı servisn´ıch technik˚ u • Strategie m˚ uˇze konˇcit vyˇreˇsen´ım probl´emu c(e` ) = 0. • Z´ıskan´ a evidence
A = yes/no, A ∈ Proveden´e akce, e = Q = yes/no, Q ∈ Zodpovˇezen´e ot´azky • P(e) ... pravdˇ epodobnost evidence e • t(e) ... celkov´ a cena proveden´ych akc´ı a ot´azek
X
ECR(s) = `∈Listy
strategie s
P(e` ) · (t(e` ) + c(e` ))
Ohodnocen´ı strategie opravy - ECR A1 = yes Q1 = no
A1 = no
A2 = no Q1 = yes A2 = yes
Ohodnocen´ı strategie opravy - ECR A1 = yes Q1 = no
A1 = no
A2 = no Q1 = yes A2 = yes
Strategie Q1
A1 A2
oˇcek´avan´a cena opravy (ECR) p(Q1 = no, A1 = yes) · + p(Q1 = no, A1 = no) ·
(cQ1 + cA1 + 0) (cQ1 + cA1 + cCS )
· ·
(cQ1 + cA2 + 0) (cQ1 + cA2 + cCS )
+ p(Q1 = yes, A2 = yes) + p(Q1 = yes, A2 = no)
C´ıl technick´e diagnostiky C´ıl: nal´ezt strategii s? takovou, ˇze pro vˇsechny strategie s plat´ı ECR(s? ) 6 ECR(s) .
C´ıl technick´e diagnostiky C´ıl: nal´ezt strategii s? takovou, ˇze pro vˇsechny strategie s plat´ı ECR(s? ) 6 ECR(s) . Polynomi´ alnˇ e ˇreˇsiteln´ au ´loha
C´ıl technick´e diagnostiky C´ıl: nal´ezt strategii s? takovou, ˇze pro vˇsechny strategie s plat´ı ECR(s? ) 6 ECR(s) . Polynomi´ alnˇ e ˇreˇsiteln´ au ´loha (1) kaˇzd´a akce ˇreˇs´ı pr´avˇe jednu z´avadu,
C´ıl technick´e diagnostiky C´ıl: nal´ezt strategii s? takovou, ˇze pro vˇsechny strategie s plat´ı ECR(s? ) 6 ECR(s) . Polynomi´ alnˇ e ˇreˇsiteln´ au ´loha (1) kaˇzd´a akce ˇreˇs´ı pr´avˇe jednu z´avadu, (2) vˇsechny akce jsou navz´ajem podm´ınˇenˇe nez´avisl´e pˇri zn´am´ych pˇr´ıˇcin´ach
C´ıl technick´e diagnostiky C´ıl: nal´ezt strategii s? takovou, ˇze pro vˇsechny strategie s plat´ı ECR(s? ) 6 ECR(s) . Polynomi´ alnˇ e ˇreˇsiteln´ au ´loha (1) kaˇzd´a akce ˇreˇs´ı pr´avˇe jednu z´avadu, (2) vˇsechny akce jsou navz´ajem podm´ınˇenˇe nez´avisl´e pˇri zn´am´ych pˇr´ıˇcin´ach (3) plat´ı, ˇze zaˇr´ızen´ı m´a v jednom okamˇziku pouze jednu z´avadu (single fault assumption)
C´ıl technick´e diagnostiky C´ıl: nal´ezt strategii s? takovou, ˇze pro vˇsechny strategie s plat´ı ECR(s? ) 6 ECR(s) . Polynomi´ alnˇ e ˇreˇsiteln´ au ´loha (1) kaˇzd´a akce ˇreˇs´ı pr´avˇe jednu z´avadu, (2) vˇsechny akce jsou navz´ajem podm´ınˇenˇe nez´avisl´e pˇri zn´am´ych pˇr´ıˇcin´ach (3) plat´ı, ˇze zaˇr´ızen´ı m´a v jednom okamˇziku pouze jednu z´avadu (single fault assumption) NP-tˇ eˇ zk´ au ´loha
C´ıl technick´e diagnostiky C´ıl: nal´ezt strategii s? takovou, ˇze pro vˇsechny strategie s plat´ı ECR(s? ) 6 ECR(s) . Polynomi´ alnˇ e ˇreˇsiteln´ au ´loha (1) kaˇzd´a akce ˇreˇs´ı pr´avˇe jednu z´avadu, (2) vˇsechny akce jsou navz´ajem podm´ınˇenˇe nez´avisl´e pˇri zn´am´ych pˇr´ıˇcin´ach (3) plat´ı, ˇze zaˇr´ızen´ı m´a v jednom okamˇziku pouze jednu z´avadu (single fault assumption) NP-tˇ eˇ zk´ au ´loha (1) nˇekter´e akce ˇreˇs´ı v´ıce neˇz dvˇe z´avady
Reprezentace prostoru vˇsech ˇreˇsen´ı AND/OR grafem A1 = no, Q1 = 1
A1 = no
A1 = no, Q1 = 2 A1 = no, A2 = no, Q1 = 1
Q1 = 1 A1 = no, A2 = no
∅
Q1 = 2
A1 = no, A2 = no, Q1 = 2 A2 = no, Q1 = 1
A2 = no
A2 = no, Q1 = 2
Algoritmy pro nalezen´ı optim´aln´ıho ˇreˇsen´ı
• vyuˇ zit´ı metod prohled´av´an´ı stavov´eho prostoru:
Algoritmy pro nalezen´ı optim´aln´ıho ˇreˇsen´ı
• vyuˇ zit´ı metod prohled´av´an´ı stavov´eho prostoru: • metoda vˇ etv´ı a mez´ı (branch and bound)
Algoritmy pro nalezen´ı optim´aln´ıho ˇreˇsen´ı
• vyuˇ zit´ı metod prohled´av´an´ı stavov´eho prostoru: • metoda vˇ etv´ı a mez´ı (branch and bound) • metody dynamick´ eho programov´an´ı
Algoritmy pro nalezen´ı optim´aln´ıho ˇreˇsen´ı
• vyuˇ zit´ı metod prohled´av´an´ı stavov´eho prostoru: • metoda vˇ etv´ı a mez´ı (branch and bound) • metody dynamick´ eho programov´an´ı • A? pro AND/OR grafy
Algoritmy pro nalezen´ı optim´aln´ıho ˇreˇsen´ı
• vyuˇ zit´ı metod prohled´av´an´ı stavov´eho prostoru: • metoda vˇ etv´ı a mez´ı (branch and bound) • metody dynamick´ eho programov´an´ı • A? pro AND/OR grafy
Prohled´av´an´ı prostoru vˇsech ˇreˇsen´ı je v´ypoˇcetnˇe n´aroˇcn´e.
Suboptim´aln´ı ˇreˇsen´ı v re´aln´em ˇcase BATS troubleshooter: • Vyvinut´ y v r´amci spoleˇcn´eho projektu Hewlett-Packard a
Aalborg University.
Suboptim´aln´ı ˇreˇsen´ı v re´aln´em ˇcase BATS troubleshooter: • Vyvinut´ y v r´amci spoleˇcn´eho projektu Hewlett-Packard a
Aalborg University. • Vyuˇ z´ıv´a nˇekolik heuristik zaloˇzen´ych na pomˇeru p/c.
Suboptim´aln´ı ˇreˇsen´ı v re´aln´em ˇcase BATS troubleshooter: • Vyvinut´ y v r´amci spoleˇcn´eho projektu Hewlett-Packard a
Aalborg University. • Vyuˇ z´ıv´a nˇekolik heuristik zaloˇzen´ych na pomˇeru p/c. Porovn´ an´ı optim´ aln´ıho ˇreˇsen´ı s BATS troubleshooterem Problem 53 Tray Overrun Load Pjam Scatter NotDupl Spots MIO1
|A| 6 9 11 12 13 14 9 16 10
|Q| 2 3 3 3 4 4 9 5 10
OPTIM 433.238 129.214 106.204 38.3777 124.323 115.410 70.6740 161.385 250.452
BATS 443.305 129.214 112.456 38.4229 124.365 115.862 73.5984 162.246 253.310
Adaptivn´ı test znalost´ı Q1 Q2
Q5
wrong
Q3
Q4
Q4
wrong
correct Q8
correct wrong
correct
Q5 Q7
Q2 Q6
wrong
Q7
Q1
Q8 Q9 Q10
correct wrong Q3
Q6
Q6
correct wrong Q8
Q4
Q9
correct wrong Q7
Q7
correct Q10
Pˇr´ıklad testu: Matematick´e operace se zlomky Dovednost
Pˇr´ıklad
CP
Porovn´av´an´ı (spoleˇcn´y ˇcitatel nebo jmenovatel)
1 2
> 31 ,
AD
Sˇc´ıt´an´ı (spoleˇcn´y jmenovatel)
1 7
+
2 7
=
1+2 7
=
3 7
SB
Odˇc´ıt´an´ı (spoleˇcn´y jmenovatel)
2 5
−
1 5
=
2−1 5
=
1 5
MT
N´asoben´ı
1 2
CD
Pˇrevod na spoleˇcn´y jmenovatel
CL
Kr´acen´ı
4 6
=
2·2 2·3
CIM
Pˇrevod na sm´ıˇsen´e zlomky
7 2
=
3·2+1 2
CMI
Pˇrevod na neprav´e zlomky
3 21 =
2 3
>
1 3
3 = 10 1 2 3 4 2, 3 = 6, 6
·
3 5
2 3
=
= 3 12
3·2+1 2
=
7 2
Myln´e postupy (Misconceptions) ˇ Cetnost v´yskytu v datech
Pˇr´ıklad MAD
a b
+
c d
=
a+c b+d
14.8%
MSB
a b
−
c d
=
a−c b−d
9.4%
MMT1
a b
·
c b
=
a·c b
14.1%
MMT2
a b
·
c b
=
a+c b·b
8.1%
MMT3
a b
·
c d
=
a·d b·c
15.4%
MMT4
a b
·
c d
=
a·c b+d
8.1%
MC
a bc =
a·b c
4.0%
Model studenta
HV2
AD
HV1
SB
ACMI
ACIM
ACL
ACD
CMI
CIM
CL
CD
MT
MMT1
MMT2
MMT3
CP
MAD
MSB
MC
MMT4
Model pro u´lohu T1
3 5 · 4 6
−
1 15 1 5 1 4 1 = − = − = = 8 24 8 8 8 8 2
Model pro u´lohu T1
3 5 · 4 6
−
1 15 1 5 1 4 1 = − = − = = 8 24 8 8 8 8 2
T 1 ⇔ MT & CL & ACL & SB & ¬MMT 3 & ¬MMT 4 & ¬MSB
Model pro u´lohu T1
3 5 · 4 6
−
1 15 1 5 1 4 1 = − = − = = 8 24 8 8 8 8 2
T 1 ⇔ MT & CL & ACL & SB & ¬MMT 3 & ¬MMT 4 & ¬MSB
CL
ACL
SB
MSB
MT MMT3
T1
MMT4 P(X1|T1)
X1
Model studenta spojen´y s modelem pro u´lohu T1 HV2
AD
HV1
SB
ACMI
ACIM
ACL
ACD
CMI
CIM
CL
CD
MT
MMT1
MMT2
MMT3
CP MAD
MSB
MC
T1
X1
MMT4
Adaptivn´ı test Opakujeme dva z´akladn´ı kroky: 1. odhadujeme u ´roveˇ n jednotliv´ych znalost´ı studenta
Adaptivn´ı test Opakujeme dva z´akladn´ı kroky: 1. odhadujeme u ´roveˇ n jednotliv´ych znalost´ı studenta 2. vyb´ır´ame vhodnou ot´azku na z´akladˇe odhadu u ´rovnˇe znalost´ı
Adaptivn´ı test Opakujeme dva z´akladn´ı kroky: 1. odhadujeme u ´roveˇ n jednotliv´ych znalost´ı studenta 2. vyb´ır´ame vhodnou ot´azku na z´akladˇe odhadu u ´rovnˇe znalost´ı Entropie jako m´ıra informace:
Adaptivn´ı test Opakujeme dva z´akladn´ı kroky: 1. odhadujeme u ´roveˇ n jednotliv´ych znalost´ı studenta 2. vyb´ır´ame vhodnou ot´azku na z´akladˇe odhadu u ´rovnˇe znalost´ı Entropie jako m´ıra informace: P • H (P(S)) = − s P(S = s) · log P(S = s)
entropy
1
0.5
0
0
0.5 probability
1
Adaptivn´ı test Opakujeme dva z´akladn´ı kroky: 1. odhadujeme u ´roveˇ n jednotliv´ych znalost´ı studenta 2. vyb´ır´ame vhodnou ot´azku na z´akladˇe odhadu u ´rovnˇe znalost´ı Entropie jako m´ıra informace: P • H (P(S)) = − s P(S = s) · log P(S = s)
entropy
1
0.5
0
0
0.5 probability
1
ˇ ım je entropie niˇzˇs´ı t´ım v´ıce toho o znalostech studenta v´ıme. • C´
Adaptivn´ı test Opakujeme dva z´akladn´ı kroky: 1. odhadujeme u ´roveˇ n jednotliv´ych znalost´ı studenta 2. vyb´ır´ame vhodnou ot´azku na z´akladˇe odhadu u ´rovnˇe znalost´ı Entropie jako m´ıra informace: P • H (P(S)) = − s P(S = s) · log P(S = s)
entropy
1
0.5
0
0
0.5 probability
1
ˇ ım je entropie niˇzˇs´ı t´ım v´ıce toho o znalostech studenta v´ıme. • C´ • Hladov´ y algoritmus: V kaˇzd´em kroku vybereme ot´azku, kter´a
nejv´ıce sniˇzuje entropii.
Kvalita predikce jednotliv´ych dovednost´ı 92
adaptive test fixed descending order fixed ascending order
90 88 86 84 82 80 78 76 74 0
2
4
6
8 10 12 14 Number of answered questions
16
18
20
Aplikace 3: F1 na okruhu v Silverstone
• D´ elka: 3.194 mil = 5.140 km • Pouˇ z´ıvan´y pˇri Velk´e cenˇe Velk´e Brit´anie v letech 2000 – 2009. • Nejrychlejˇs´ı okruh: Sebastian Vettel (2009), Red Bull-Renault
ˇ jednoho okruhu: 78.119 vteˇrin • Cas
Rozhodovac´ı diagram pro rychlostn´ı profil vozu F1 (pro dva segmenty)
Porovn´an´ı rychlostn´ıch profil˚ u
200 100
Max. allowed speed
0
Speed [km/h]
300
400
Omezen´ı na maxim´aln´ı rychlost
0
1000
2000
3000
Lap distance [m]
4000
5000
Porovn´an´ı rychlostn´ıch profil˚ u
200 100
Max. allowed speed Influence diagram
0
Speed [km/h]
300
400
ˇ sen´ı pomoc´ı rozhodovac´ıho diagramu – ˇcas 84.0 s. Reˇ
0
1000
2000
3000
Lap distance [m]
4000
5000
Porovn´an´ı rychlostn´ıch profil˚ u
200 100
Max. allowed speed Influence diagram Testing pilot
0
Speed [km/h]
300
400
ˇ sen´ı pomoc´ı rozhodovac´ıho diagramu – ˇcas 84.0 s. Reˇ Testovac´ı pilot – ˇcas 85.8 s. (S. Vettel 78.119 s.)
0
1000
2000
3000
Lap distance [m]
4000
5000
