UITWERKINGEN
12.2 Modellen van kennisgebaseerde diagnose
(Dit is de uitwerking van opgave 1 op pagina 701 van Introduction to knowledge systems.)
a Het aantal mogelijke hypothesen die je nodig hebt om patiënten te
categoriseren is groter dan het aantal ziekte-eenheden, omdat een patiënt verschillende
ziekten tegelijk kan hebben, die je allemaal wilt opnemen in je diagnose.
b Als er hoogstens 10 ziekten tegelijk bij een patiënt kunnen optreden, willen we
het aantal verschillende hypothesen schatten.
Als je dit nauwkeurig wilt doen, neem je de som van het aantal verschillende diagnosen met
i elemeneten, waarbij i van 1 tot 10 loopt. Uit het voorbeeld onderaan pagina 683 van
Stefik weten we dat de hypothesen die uit precies 10 elementen bestaan verreweg de
grootste bijdrage aan deze som leveren. Van zulke 10-element diagnoses zijn er (10.000 *
9999 * 9998 * 9997 * 9996 * 9995 * 9994 * 9993 * 9992 * 9991) / 10! = 2.7 * 10
(Dit is de uitwerking van opgave 9 op pagina 706 van Introduction to knowledge systems.)
Opgave 9 gaat erover hoe een verdeel-en-heers tactiek helpt om de tijds-complexiteit
laag te houden, ook als het aantal mogelijke hypothesen groot is.
a Als je een systeem hebt met n componenten die elk op precies één manier fout
kunnen zijn, zijn er n enkelvoudige hypothesen.
Er zijn n * (n - 1)/2 hypothesen die uit precies 2 fouten bestaan. Dus zijn er 1 + n + n *
(n - 1)/2 hypothesen die uit 0, 1 of 2 fouten bestaan.
b Er staat een foutje in de formulering van deze deelopgave. De derde regel begint
met het woord ``hypotheses, maar dat moet zijn ``faults.
HDM, de top-down hiërarchische methode, berust erop dat dezelfde diagnose methode DM op
ieder niveau gebruikt kan worden, dus dat de lagere niveaus in zekere zin erg op de hogere
lijken. Ook gebruikt HDM de single-fault hypothesis (de aanname dat er precies één
component fout is). Je kunt HDM wel aanpassen als je meervoudige fouten wilt opsporen:
diagnosticeer dan per niveau alle samengestelde hypothesen, en ga voor iedere fout in die
hypothese door naar het lagere, preciezere niveau.
c We vullen de tabel op pagina 708 van Stefik aan met de volgende waarden:
Bij case 2 krijg je in de kolom C(n) = n2 de waarde 162=256.
In de kolom C(n) = 2n krijg je de waarde 216 = 65.536.
Bij case 3 krijg je in de kolom C(n) = n2 de waarde 42=16.
In de kolom C(n) = 2n krijg je de waarde 24 = 16.
Bij case 5 krijg je in de kolom C(n)=n de waarde 4+4+4=12.
In de kolom C(n) = n2 krijg je de waarde 42+42+42=48.
In de kolom C(n) = 2n krijg je de waarde 24 +24 +24
= 48.
Als je de uikomsten van case 2 met die van case 4 vergelijkt, zie je dat beide methoden
een systeem met 16 primitieve componenten diagnosticeren, maar dat de uiteindelijke
complexiteit bij case 4 door de hiërarchische methode HDM veel kleiner is dan die van
methode DM bij case 2 (bijvoorbeeld in de kolom C(n) = 2n heeft case 2 de
waarde 65.536, en case 4 slechts 32).
d Je kunt een algemene uitdrukking geven voor de complexiteit van HDM, waarbij k
het aantal elementen van een diagnostische groep is per niveau, C(k) het aantal hypothesen
per niveau, en m het aantal niveaus. De complexiteit van HDM is dan namelijk m * C(k).
Bijvoorbeeld bij case 5 in de tabel geldt m=3, dus de complexiteit 3 * C(k) is in de drie
kolommen resp. 3 * 4=12, 3 * 42=48 en 3 * 24=48.
(Dit is de uitwerking van opgave 3 op pagina 701 van Introduction to knowledge systems.)
Corroboration betekent bekrachtiging of bevestiging. Stel dat we een systeem S hebben,
een verzameling P van componenten van S en een verzameling metingen D. Stel verder dat we
een verzameling correcte regels hebben voor het gedrag van de componenten uit P. Stel dat
de metingen uit D allemaal kloppen met deze regels, en dat de regels nieuwe data
voorspellen, die door nieuwe observaties bevestigd worden. Professor Digit denkt nu dat
alle componenten goed moeten werken.
Professor Digit heeft helaas geen gelijk. Immers, laten we als systeem S het bekende
voorbeeld TS-1 nemen, met als verzameling componenten P={A1, A2, M1, M2}. Stel dat in
werkelijkheid de opteller A2 in modus d werkt, dat wil zeggen hij laat het belangrijkste
bit vallen. Stel verder dat D de volgende observatie bevat: In1(A1) = 1, In2(A1) = 2,
In1(M1) = 3, In2(M1) = 1, In1(M2) = 1, Out = 6; dit klopt met de regels: (1 + 2) * 1 + (3
* 1) = 6. Stel bovendien dat je voorspelde en later bevestigde observatie als volgt is:
In1(A1) = 2, In2(A1) = 4, In1(M1) = 8, In2(M1) = 4, In1(M2) = 7, Out = 10. Ook dit klopt
met de regels: (2 + 4) * 7 + (8 * 4) = 10 mod 32.
De observaties kloppen met de regels, maar ze zijn duidelijk niet uitgebreid genoeg om er
de fout in A2 mee op te sporen.