LEERKERN

12.3 Hypothesediscriminatie

Introductie

Dit is de moeilijkste paragraaf van het hoofdstuk. Hypothesediscriminatie gaat erover hoe door het doen van de juiste extra metingen zo efficiënt mogelijk de verzameling kandidaathypothesen verkleind kan worden tot er één juiste diagnose overblijft.

12.3.1 Shannon-entropie

Lees uit Stefik: paragraaf 9.2.3 (pagina 690 tot en met 700).

Er staan drie foutjes in regels 2 tot en met 5 op pagina 692 van Stefik:
– in regel 2: exercise 2 moet zijn exercise 4
– in regel 3: exercise 3 moet zijn exercise 5
– in regel 4: exercise 4 moet zijn exercise 6.

Bij hypothesediscriminatie gaat het er niet zozeer om bevestiging te krijgen voor bepaalde hypothesen, maar veeleer om hypothesen uit te sluiten. Stel bijvoorbeeld dat ziekte Z1 als symptomen S1, S2 en S3 heeft, terwijl ziekte Z2 als symptomen S1, S2 en S4 heeft, en we hebben S1 en S2 al geobserveerd. Het heeft dan niet veel zin om meer observaties te doen die de favoriete hypothese Z1 bevestigen; we zijn juist op zoek naar een bewijs dat het niet Z2 kan zijn. Bij hypothese-discriminatie willen we dus zoveel mogelijk hypothesen uitsluiten, waarna de juiste diagnose overblijft. Denk hierbij aan het beroemde citaat van Sherlock Holmes uit Arthur Conan Doyle’s ‘The adventure of the blanched soldier’: ‘When you have eliminated all which is impossible, then whatever remains, however improbable, must be the truth’.

Het boek van Stefik geeft een inleiding in de Shannon-entropie. Shannon en Weaver schreven al in 1949 hun boek ‘A mathematical theory of communication’ waarin deze maat voor informatiewaarde gegeven wordt om te bepalen hoe men zo efficiënt mogelijk informatie kan overbrengen. Bij de toepassing van hun theorie op diagnose geldt in het algemeen: hoe hoger de entropie (dit is verwant aan chaos), des te meer informatie zal er nog nodig zijn om een juiste diagnose te vinden.

Stefik gebruikt de notatie logp voor de natuurlijke logaritme (met basis e) van p. In Nederland gebruiken we hiervoor meestal de notatie lnp, maar dit werkboek past zich wat dit betreft aan bij Stefik.

12.3.2 Meetpunten kiezen

Het gedeelte onder de kop ‘The selection of probe points’ bevat de moeilijkste theorie van het hele hoofdstuk.

We lichten de terminologie kort in het Nederlands toe:
– H(ti = v
ik): de entropie van de verzameling kandidaten horend bij gemeten waarde vik bij meetpunt ti
– p(ti = v
ik): de geschatte kans dat vik de waarde van de meting bij meetpunt ti zal zijn
– He(ti): de verwachte of geschatte entropie van meetpunt ti. Deze wordt berekend door een gewogen som van de mogelijke waarden van H(ti = v
ik) te nemen; de gewichten zijn de kansen p(ti = vik) op die waarden.

Wat gebeurt er nu bij het kiezen van een nieuw meetpunt? We willen het meetpunt zodanig kiezen dat een meting daar onze diagnose zoveel mogelijk zal verscherpen. Echter, we weten niet van tevoren wat de meting daar zal zijn, dus we moeten rekening houden met verschillende mogelijke meetwaarden. Voor al deze mogelijke waarden berekenen we de Shannon-entropie van de verzameling kandidaten die nog over zou zijn als die waarde werd gemeten. Omdat sommige meetwaarden waarschijnlijker zijn dan andere, willen we dat die meest waarschijnlijke meetwaarden het grootste gewicht in de schaal leggen als we de totale ‘verwachte entropie’ van het meetpunt gaan uitrekenen. De totale verwachte entropie van een meetpunt wordt dan gedefinieerd als de som van producten: voor iedere mogelijke meetwaarde de kans op die meetwaarde maal de Shannon-entropie van de verzameling kandidaten die nog over zou zijn als die waarde werd gemeten. In een formule wordt de verwachte entropie als volgt gedefinieerd (zie de definitie onderaan pagina 693 uit Stefik):

He(ti) = Sp(ti = vik) * H(ti =vik)

Uiteindelijk kiezen we dan het meetpunt waarvan de verwachte entropie zo laag mogelijk is.
Soms hebben we geluk en is die verwachte entropie gelijk aan 0. Zo hebben we in de situatie van figuur 9.17 op pagina 694 een meetpunt, namelijk T1, dat altijd uitsluitsel geeft. Men neemt voor het gemak aan dat er geen onbekende fouten of meervoudige fouten kunnen optreden. Dan kunnen er maar twee meetwaarden optreden bij T1, namelijk T1 = 2 en T1 = 0. Met T1 = 2 is er maar een kandidaat consistent, namelijk [M2s], die een Shannon-entropie oplevert van 0. Met T1 = 0 is er ook maar een kandidaat consistent, namelijk [A1s], die ook een Shannon-entropie van 0 geeft. In dit geval hoeft men niet eens meer de kansen op de twee meetwaarden uit te rekenen om te zien dat de verwachte entropie gelijk is aan 0 + 0 = 0 (zie ook figuur 9.19 op pagina 696).

> Extra uitleg 12.3.1 Figuur 9.16

> Extra uitleg 12.3.2 Figuur 9.17

> Opgave 12.3.1

> Opgave 12.3.2

> Opgave 12.3.3

> Opgave 12.3.4