UITWERKINGEN

12.2 Modellen van kennisgebaseerde diagnose

Uitwerking 12.2.1

(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
29; de hele som zal dan tussen de 2.7 * 1029 en de 1030 liggen, een enorm aantal.
c – Als er n mogelijke ziekte-eenheden zijn, dan zijn er 2
n verschillende hypothesen mogelijk; een hypothese bestaat namelijk uit een bepaalde combinatie van ja's en nee's voor alle n de ziekte-eenheden, en er zijn 2n zulke combinaties. Bij het voorbeeld van de internisten zijn dat er dus 210.000, dat is ongeveer 103000 mogelijke hypothesen. Een internist kan natuurlijk nooit al deze hypothesen checken: er moet flink in gesnoeid worden.

> Opgave 12.2.1

Uitwerking 12.2.2

(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.

> Opgave 12.2.2

Uitwerking 12.2.3

(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.

> Opgave 12.2.3