Expertsystemen. Marco Wiering CGN A126 Tel

Expertsystemen

Marco Wiering CGN A126 Tel. 030−2539209 [email protected]

Inleiding en inperking (1) • Expertsystemen en Artificial Intelligence (AI) • Wat is intelligentie?

Inleiding en inperking (2)

Inleiding en inperking (3) • Herkennen versus definiëren van intelligentie • AI is the study of the computations that make it •

possible to perceive, reason and act”

Data

Knowledge

Databases Opslag, queries

Knowledge−based systems Redeneren

Opbouw (1)

• Expertsystemen – Definitie en architectuur – Kennisrepresentatie – Logische kennisrepresentatie – Regel−gebaseerde systemen – Redeneerstrategieën

Opbouw (2) • Expertsystemen (vervolg) – Trace en uitlegfaciliteiten – Voorbeelden – Knowledge engineering – Trends in expertsystemen

• Demonstratie expertsysteem – Harthulp via de ambulancedienst

• Samenvatting en conclusie

Expertsysteem voor psychiatrie • Van algemeen naar specifiek (eind ’60er jaren) – Beperkt domein

• Joseph Weizenbaum – ELIZA ELIZA Men are all alike. IN WHAT WAY They’re always bugging us about something or other. CAN YOU THINK OF A SPECIFIC EXAMPLE

Eliza (2) ELIZA (vervolg) Well, my boyfriend made me come here. YOUR BOYFRIEND MADE YOU COME HERE He says I’m depressed much of the time. I AM SORRY TO HEAR THAT YOU ARE DEPRESSED It’s true. I’m unhappy. SO YOU THINK COMING HERE WILL HELP YOU NOT TO BE UNHAPPY I need some help, that much seems certain. WHAT WOULD IT MEAN TO YOU IF YOU GOT SOME HELP Perhaps I could learn to get along with my mother. TELL ME MORE ABOUT YOUR FAMILY

Definitie expertsysteem (1) • • • •

Een expertsysteem is een programma dat binnen een bepaald domein, gebruikmakend van AI, een oplossing kan geven voor een probleem op het niveau van een domeinexpert

• Een expertsysteem gebruikt daarbij veel • domeinkennis en stelt, waar nodig, vragen aan • de gebruiker

Definitie expertsysteem (2) • Expertsysteem = kennis + inferentie – Kennis bevindt zich in de domein specifieke – knowledge base (kennisbank) – Inferentie (automatisch redeneren) is de – manipulatie van geformaliseerde kennis om – nieuwe kennis af te leiden – Inferentie vindt plaats met behulp van de – inference engine (inferentie machine)

Architectuur CONSULTATIESYSTEEM GEBRUIKERS INTERFACE UITLEG FACILITEIT

TRACE FACILITEIT

INFERENTIE MACHINE

KENNISBANK

GEBRUIKER

Verschillen

• Dankzij de scheiding van kennis en inferentie • zijn Expert System Shells ontstaan

Positieve & negatieve aspecten • Positief – Beschikbaarheid van zeldzame kennis – Consistente (hoge) kwaliteit van de resultaten – Grote flexibiliteit

• Negatief – Verzamelen van kennis – Acceptatie – Actualiteit

Kennisrepresentatie • Formalisme voor het vastleggen van kennis in • de computer, maar eventueel ook op papier – − Logica – − Regels – − Semantische netten – − Frames

Logische Kennisrepresentatie • Ontologie : beschrijving van de belangrijke • concepten in een gegeven domein. • vb. Dieren, zoogdieren, mensen, katten, honden • Kennis: in logische zinnen of axioma’s: • Zoogdier(x) −> Dier(x) • Mens(x) −> Zoogdier(x) • Nu leiden we af: Mens(x) −> Dier(x)

Logische Kennisrepresentatie (2) • − Maak een vocabulaire (ontologie) • − Encodeer algemene regels voor het • probleem domein • − Encodeer de specifieke instantie • − We onderscheiden: objecten, categorieen, • eigenschappen, relaties, acties

Regel−gebaseerde systemen (1) • If {conditions} then {conclusion} • De conclusion kan een assertion of een action • zijn: – Rule−based deduction systems – Rule−based reaction systems

Regel−gebaseerde systemen (3) • Bij kip en kalkoen wordt witte wijn gedronken object meal attribute appetizer main_course desert wine

(meal, appetizer, shrimp) (meal, main_course, turkey) (meal, desert, brownies)

if same(meal, main_course, chicken) or same(meal, main_course, turkey) then add(meal, wine, white)

Regel−gebaseerde systemen (2) • Onderdelen van een regel−gebaseerd systeem – Een kennisbank bestaande uit • De regelverzameling • Het object schema

– Een feitenverzameling • Het object schema met toegekende waarden

Regel−gebaseerde systemen (4) • Het onderscheid tussen regels en feiten wordt • geëxploiteerd • Inferentie door herhaald selecteren en uitvoeren • van regels op basis van de beschikbare feiten if same(meal, main_course, chicken) or same(meal, main_course, turkey) then add(meal, wine, white) (meal, appetizer, shrimp) (meal, main_course, turkey) (meal, desert, brownies)

(meal, wine, white)

Redeneerstrategieën • Bottom−up inferentie – Werken vanuit een feitenverzameling

• Top−down inferentie – Werken vanuit een doel

Zookeeper Regel− % Biological class verzameling Z1: If ?x has hair then ?x is a mammal ... ... % Carnivore or ungulate

% Animal identities Z9: If ?x is a carnivore ?x has tawny color ?x has dark spots then ?x is a cheetah ... ...

Z5: If ?x is a mammal Z15: If ?x is a bird ?x eats meat ?x is a good flyer then ?x is a carnivore then ?x is an albatross ... ... ... ... Tweety has hair Tweety eats meat

Feiten− verzameling Tweety has tawny color Tweety has dark spots

Bottom−up inferentie Regel− % Biological class verzameling

% Animal identities

1

Z1: If ?x has hair then ?x is a mammal ... ... % Carnivore or ungulate

2

3

Z9: If ?x is a carnivore ?x has tawny color ?x has dark spots then ?x is a cheetah ... ...

Z15: If ?x is a bird Z5: If ?x is a mammal ?x eats meat ?x is a good flyer then ?x is a carnivore then ?x is an albatross ... ... ... ... Tweety is a cheetah Tweety has hair Tweety eats meat Feiten− verzameling Tweety has tawny color Tweety is a mammal Tweety has dark spots Tweety is a carnivore

Top−down inferentie Regel− % Biological class verzameling

% Animal identities

3

Z1: If ?x has hair then ?x is a mammal ... ... % Carnivore or ungulate

2

1

Z9: If ?x is a carnivore ?x has tawny color ?x has dark spots then ?x is a cheetah ... ...

?

Z15: If ?x is a bird Z5: If ?x is a mammal ?x eats meat ?x is a good flyer then ?x is a carnivore then ?x is an albatross ... ... ... ... Tweety is a cheetah Tweety has hair Tweety eats meat Feiten− verzameling Tweety has tawny color Tweety is a mammal Tweety has dark spots Tweety is a carnivore

Top−down versus bottom−up • Het probleem bepaalt de keuze – Is er een duidelijk doel te identificeren? • Zo ja, dan top−down • Zo nee, dan bottom−up

– Top−down met name voor classificatie – Bottom−up met name voor constructie en – compositie

Opdracht Doel

:g

Feiten : {a, f} Regels R1: if b and f then g R2: if g then c R3: if a then b R4: if a then e R5: if b and c then d

• Wat is de uiteindelijke feitenverzameling bij • bottom−up inferentie? Bij top−down inferentie?

Overige redeneer−aspecten (1) • Meta−regels • De conflict−set bestaat uit de regels • welke kunnen "vuren" •

•

Welke regel wordt geselecteerd? • De eerste? De meest specifieke? ...

– Forward chaining • Bottom−up met selectie van de eerste geschikte regel

– Backward chaining • Top−down met selectie van de eerste geschikte regel

Overige redeneer−aspecten (2) • Redeneren met onzekere informatie – Feiten en conclusies hebben een certainty factor – (CF) – Bij het afleiden van nieuwe feiten worden Cfs – gecombineerd If A and B then C (0.80) If C or D then D (0.90)

– Belief Networks

Belief Networks • Grafisch model voor berekenen kansen • P(A = a_1) gegeven bekende informatie • P(B), P(C), P(D), etc. en ook P(B|A) etc.

Trace en uitlegfaciliteiten • Trace – Toont welke feiten getraceerd worden

• Why – Toont waarom een vraag gesteld wordt

• How – Toont hoe een feit afgeleid is

• Why−not – Toont waarom een feit niet afgeleid is – Complementair t.o.v. How

Voorbeelden: Dendral (1) • Domein van de organische chemie • Bepalen van structuurformules van organische • verbindingen a.d.h. Van • massa−spectrometrische gegevens Massaspectrum

Gegeven: C6H13NO 2 Electron beam H Gevraagd: H − C − ??? H

Voorbeelden: Dendral (2) • Naïeve benadering – Genereer alle mogelijke structuren – Genereer voor elke structuur het massaspectrum – Vergelijk deze met het gegeven spectrum

• Heuristische benadering – Gebruik domeinkennis tijdens het genereren van de – mogelijke structuren if there are two peaks x and y such that 1) x + y = M + 28 2) x − 28 is a high peak then there is a ketone (C=O) subgroup

Voorbeelden: Mycin (1) • • • •

Domein van de infectieziekten Diagnose èn therapie Onzekere en onvolledige informatie Evaluatie – 10 willekeurige patiënten gepresenteerd aan Mycin – 10 willekeurige patiënten gepresenteerd aan 9 – specialisten – 100 recepten beoordeeld door 8 beoordelaars

Voorbeelden: Mycin (2)

Persoon% accept.% onacc Medicus 1 50 10 Medicus 2 50 10 Medicus 3 50 10 Medicus 5 4 70 40 0 Medicus 6 50 0 Huisarts 30 10 Medicus 8 10 Student 30 30 0

Voorbeelden: American Express • Advies bij kredietwaardigheid nieuwe klanten • 1/3 minder afwijzingen • Omzetverhoging van $27.000.000,− per jaar • Vraag: bedenk enkele mogelijke regels voor • bovenstaand expert systeem

Knowledge engineering Identificatie Conceptualisering (Kennis acquisitie) Formalisering Implementatie Testen

Knowledge acquisition bottleneck • Het grootste probleem in Knowledge • engineering is om alle kennis in de computer • te zetten. • Dit probleem heet de knowlegde acquisition • bottleneck. • Het kan soms jaren duren voordat een • correct en helder expert systeem gebouwd is.

Trends in expertsystemen • • • • • • •

Schaalvergroting (parallelle systemen) Hybride systemen Zelflerende systemen Kennisacquisitie Eigenschappen kennisrepresentatievormen Redeneren m.b.v. modellen Internet expertsystemen

Internet expertsystemen • Positief – Publiekelijk toegankelijk – Eenvoudige distributie – Platform onafhankelijk – WWW omgeving

• Negatief – Beperkte betrouwbaarheid en performance – Matige beveiliging – Geen standaard voor betalingen

Demonstratie expertsysteem • Harthulp via de ambulancedienst – 112 alarmcentrale – Diagnose van hartklachten – Advies over het sturen van een ambulance – Onzekere en onvolledige informatie – Kritieke toepassing

• http://www.cs.uu.nl/docs/mti

Samenvatting en conclusie • Expertsystemen... – Vormen een belangrijk deelgebied van AI – Zijn er in vele soorten en maten – Zijn zeer succesvol gebleken – Staan volop in de belangstelling – Bestaan meestal uit een grote verzameling causale – (als−dan) regels – Vragen informatie aan de gebruiker en geven deze – advies