UITWERKINGEN

12.3 Hypothesediscriminatie

Uitwerking 12.3.1

(Dit is de uitwerking van opgave 4 op pagina 701 van ‘Introduction to knowledge systems’.)

a – Als er precies twee kandidaten zijn met gelijke kans, zoals in figuur 9.22, dan geldt voor de Shannon-entropie:

H = -S pi log pi = - (0,5 log(0,5) + 0,5 log(0,5)) = -log(0,5) = 0,693147

b – Als er precies vijf kandidaten zijn met gelijke kans, zoals in figuur 9.23, dan geldt voor de Shannon-entropie:

H = - S pi log pi = - (0,2 log(0,2) + 0,2 log(0,2) + 0,2 log(0,2) + 0,2 log(0,2) + 0,2 log(0,2)) = -log(0,2) = 1,609438

De Shannon-entropie is groter dan bij onderdeel a. Dat is niet zo gek, omdat bij a de situatie duidelijk al meer uitgekristalliseerd is: daar hoef je nog maar één hypothese te elimineren, tegen nog vier bij b.
c – Als er precies 10 kandidaten zijn met gelijke kans, dan geldt voor de Shannon-entropie:

H = - S pi log pi = - 10 * 0,1 log(0,1) = -log(0,1) = 2,302585

Als er precies 20 kandidaten zijn met gelijke kans, dan geldt voor de Shannon-entropie:

H = - S pi log pi = - 20 * 0,05 log(0,05) = -log(0,05) = 2,995732

Als er precies n kandidaten zijn met gelijke kans, dan geldt voor de Shannon-entropie:

H = - S pi log pi = - n*1/n *log(1/n) = -log(1/n). Deze waarde gaat naar oneindig als n naar oneindig gaat.
Het is niet vreemd dat bij een groter aantal kandidaten met gelijke kans de entropie steeds groter wordt: je moet telkens meer kandidaten uitsluiten.
d – Als er twee kandidaten zijn waarvan de ene een veel grotere kans heeft dan de ander, zoals in figuur 9.24, geldt voor de Shannon-entropie:

H = - S pi log pi = -(0,9 log(0,9) + 0,1 log (0,1)) = -(-0,0948245 -0,2302585) = 0,325083.

Deze entropie is kleiner dan bij de twee kandidaten met gelijke kans uit onderdeel a. Ook intuïtief is de situatie hier beter dan bij a: je kunt je er hier op richten om de tweede kleine kandidaat te elimineren, en je maakt een grote kans (0,9) dat je daarmee goed zit.
e – Als er maar één kandidaat is met kans 1, dan geldt voor de Shannon-entropie:

H = - S pi log pi = -1 log 1 = 0

De entropie (chaos) is 0, want er is inderdaad volledige duidelijkheid over de juiste diagnose.
f – Als er één kandidaat is met grote kans (0,995) en daarnaast vijf kandidaten met zeer kleine kans (0,001 per stuk), dan geldt voor de Shannon-entropie:

H = -S pi log pi = -(0,995 log(0,995) + 5 * 0,001 log (0,001)) = -(-0,0049875 - 0,0345388) = 0,039526.

Deze uitkomst lijkt meer op onderdeel e dan op onderdeel d, omdat hier bij f de eerste kandidaat zo’n grote kans heeft, dat hij de totale uitkomst klein houdt. Ook intuïtief is de situatie hier beter dan bij d, omdat je nu nog veel meer kans hebt dan bij d dat je goed zit als je je erop concentreert om de (vijf) kleine kandidaatjes te elimineren.
Als de vijf kleine kandidaatjes gecombineerd zouden zijn tot één kandidaat met kans 0,005, dan geldt voor de Shannon-entropie:

H = - S pi log pi = -(0,995 log(0,995) + 0,005 log (0,005)) = -(-0,0049875 - 0,0264916) = 0,031479

Dit is iets kleiner dan de entropie met vijf losse kleine kandidaten. Het is ook intuïtief moeilijker om vijf kleine kandidaten per stuk te elimineren dan hun combinatie.

> Opgave 12.3.1

Uitwerking 12.3.2

(Dit is de uitwerking van opgave 6 op pagina 705 van ‘Introduction to knowledge systems’.)

Deze opgave laat enkele aannamen zien achter de uitspraak dat de Shannon-entropie het aantal metingen telt dat nog nodig is voordat er een diagnose gesteld kan worden. Hier wordt de log-functie met basis 2 in plaats van basis e gebruikt.

a – i – Als er maar één kandidaat is met kans 1, dan geldt voor de Shannon-entropie: H = - S pi log2 pi = -1 log2 1 = 0
ii – Bij twee kandidaten met kans 0,5 geldt H = -
S pi log2 pi = - (0,5 log2 (0,5) + 0,5 log2 (0,5)) = -log2 (2-1) = --1 = 1
iii – Bij vier kandidaten met kans 0,25 geldt H = -
S pi log2 pi = - (4 * 0,25 * log2 (0,25)) = -log2 (2-2)= --2 = 2
iv – Bij 2k kandidaten, alle met kans 1/2k, geldt H=-
S pi log2 pi =- (2k * 1/2k * log2 (1/2k)) = -log2 (2-k) = -k = k
b – De berekeningen in deel a doen denken aan zoeken in een binaire boom. Immers, bij een boom met 2 kandidaten (diepte 1) is één meting nodig om beide bladeren te onderscheiden. Bij een binaire boom van diepte k met 2k bladeren moet je k metingen doen om bij het juiste blad uit te komen.
c – In wat voor situaties is het mogelijk om, gemiddeld, met één meting meer dan de helft van de kandidaten uit te sluiten? Neem een situatie zoals in figuur 9.26 waarin één hypothese veel waarschijnlijker is dan alle vijf andere. Probeer dan een meting te doen die die eerste hypothese van alle andere onderscheidt. Stel bijvoorbeeld dat je eerste hypothese angina is (een bacterieziekte) en de andere vijf zijn vijf verschillende soorten griep (virusziekten). Dan wil je een test doen die kan uitsluiten dat er van een virusziekte sprake is. Gemiddeld (met 0,995 kans) zal deze test goed uitpakken en vijf hypothesen ineens elimineren.

> Opgave 12.3.2

Uitwerking 12.3.3

(Dit is de uitwerking van opgave 11 op pagina 709 van ‘Introduction to knowledge systems’.)

Zie het antwoord in ‘Introduction to knowledge systems’op bladzijde 846.

Overigens, er is bij deze antwoorden een foutje in de paragraafnummering geslopen:
– 9.1 moet zijn 9.2
– 9.2 moet zijn 9.3
– 9.3 moet zijn 9.4

> Opgave 12.3.3

Uitwerking 12.3.4

a – Als de schakeling correct zou zijn en de inputs zijn A = 3, B = 8, C = 5 en D = 6 dan resulteren outputs E = 5 en F = 5, zie onderstaande uitwerking waarin bij iedere component is aangegeven wat de output is.

f120302.gif (1763 bytes)

De resulterende outputs zijn echter 5 en 8 en dus niet in overeenstemming met wat er volgens het model uit had moeten komen.
b – De eerste aanwijzing, dat alleen componenten verdacht zijn die stroompopwaarts van de fout liggen, levert b, c, d, f, g en i als verdachte componenten. De tweede aanwijzing, dat niet iedere invoerwaarde de uitvoerwaarde beïnvloedt, leidt tot de constatering dat de opgetreden output F=8 te maken moet hebben met de input B = 8 en dat dus foute componenten stroomafwaarts van input B moeten liggen. Dit levert b, c, f, g en i als verdachte componenten.
c – Als bijvoorbeeld component b geen MAX- maar een MIN-component is, dan blijkt dat geen effect te hebben op de outputs, dus component b is niet meer verdacht.
Als component c een MAX-component is, dan komt de output overeen met de gemeten output. Component c is dus verdacht.
Op soortgelijke wijze volgt verder dat alleen component f ook nog verdacht is.
d – Dezelfde systematiek volgend met de gewijzigde inputs leidt tot de conclusie dat component f verkeerd is.

> Opgave 12.3.4