2L340: Kennissystemen
Kennissystemen zijn softwaresystemen,
die kennis verwerven, op een expliciete manier voorstellen, over deze kennis
redeneren en gebruiken om een opdracht uit te voeren. Het vak Kennissystemen
bestaat uit hoorcolleges die de belangrijke onderwerpen presenteren uit het
gebied van de kennissystemen. In Blok E worden de kennisvoorstelling en het
redeneren besproken, in blok F - het verwerven van kennis en het gebruiken
ervan.
Leerdoelen:
- Kennis van elementaire concepten op het
gebied van kennissystemen.
- Kennis en praktische vaardigheid in het
voorstellen van, het redeneren over, het verwerven van en het gebruiken
van kennis.
- Praktische vaardigheid in het
implementeren van kennissystemen.
Docent: Dr. Alexander
Serebrenik
Les: Dinsdag, 1-2 lesuur (8.45-10.30)
Beoordeling:
·
Eindcijfer
= 0.1*Opdracht0 + 0.4*Opdracht1 + 0.2*Opdracht2 + 0.3*Opdracht3 + Bonuspunten
·
Bonuspunten worden toegekend alleen voor het
huiswerk die voldoende (zes of meer)
heeft gekregen:
Woordenboek.
Datum
|
Onderwerp
|
Transparanten
|
Aanbevolen
lectuur
|
Huiswerk/opdracht
|
27 maart
|
Inleiding
|
Transparanten
|
|
Opdracht 0
|
|
Voorstellen van kennis
|
Transparanten
|
|
|
3 april
|
Kennisvoorstelling en
basisredeneren
|
Transparanten
|
Lectuur
|
Opdracht 1, Huiswerk: 0, 1, 2
|
10 april
|
Niet-monotoon redeneren
|
Transparanten
|
Lectuur
|
Huiswerk: 3, 4,
5, 6
|
17 april
|
Redeneren met onzekerheid
|
Transparanten
|
Lectuur
|
Huiswerk: 7, 8,
9
|
24 april
|
Diagnose en uitleg
|
Transparanten
|
Lectuur
|
Huiswerk: 10, 11
|
1 mei
|
Efficiënt
redeneren. Het verwerven van kennis: kennisblootlegging
en clustering.
|
Transparanten
|
Lectuur
|
Huiswerk: 12, 13
|
8 mei
|
Tentamenweek, geen les
|
|
|
|
15 mei
|
Clustering
|
Transparanten
|
Lectuur
|
Opdracht 2, Huiswerk: 14
|
22 mei
|
Classification
|
Transparanten
|
Lectuur
|
Huiswerk: 15, 16
|
29 mei
|
Data mining
|
gastcollege door Dr. Toon Calders
|
|
|
5 juni
|
Planning
|
Transparanten
|
Lectuur
|
Opdracht 3, Huiswerk: 17, 18
|
12 juni
|
Roosters
|
Transparanten
|
Lectuur
|
Huiswerk: 19, 20, 21.
|
19 juni
|
Genetische
algoritmen
|
Transparanten
|
|
|
|
Industriële
toepassingen van kennissystemen.
|
Mevr. Iulia Dobai (Philips
Applied Technologies)
|
|
|
Dhr.
Bob Huisman (NedTrain)
|
|
|
Lessenplan
-
- Motivering (welke voordelen
bieden kennissystemen ten opzichte van klassieke software). Vier
basistaken van kennissystemen: kennis voorstellen, erover redeneren, hem
verwerven en gebruiken. Wel of geen kennissysteem? Rollen in het
totstandkomen van het systeem. Architectuur.
- Kennisvoorstellen. Welke
vragen moet een kennisingenieur stellen? Wat verwachten we van een
formalisme voor kennisvoorstelling? Ondubbelzinnigheid, expressiviteit,
compositionaliteit, leesbaarheid voor mens en machine. Kandidaten: natuurlijke taal,
logica’s, XML. Voor- en nadelen (kort).
- Twee belangrijke
kennisvoorstellingsformalismen: OWL en eerste-orde logica. De OWL-toren:
URI, XML, RDF, RDFS, OWL. Eerste-orde logica: feiten, regels.
Basisredeneren in eerste-orde logica: semantisch gevolg en bewijsbaarheid.
Top-down vs. bottom-up. Breedte-eerst vs. diepte-eerst.
- Niet-monotoon redeneren. Tekortkomingen
van het klassiek redeneren ten opzichte van uitzonderingen en gewoontes.
Verschillende manieren om niet-monotoon redeneren te formaliseren: aanname
van een gesloten wereld, negatie als falen, circumscriptie, verstekregels,
autoepistemische logica.
- Onzekerheid en vaagheid. Tekortkomingen
van het klassiek redeneren ten opzichte van onzekere en vage stellingen.
Onzekerheid: modelleren met behulp van geloofsnetwerken. Combinatie van
geloofsnetwerken en logische programma’s: Bayesiaans logisch programmeren.
Vaagheid: manieren om
met vage stellingen om te gaan. Relatie tussen onzekerheid en vaagheid.
- Diagnose en uitleg. Nood aan diagnose
en uitleg in kennissystemen. Abductieve uitleg. Het berekenen van een
abductieve uitleg. Consistentiegebaseerde uitleg. Het berekenen van een
consistentiegebaseerde uitleg. Relatie tussen abductieve en
consistentiegebaseerde uitleg.
-
- Deel 1: Efficiënt redeneren. Verschillende
complexiteitsklassen. Hoe moeilijk is het redeneren in eerste orde logica?
Begrip van een beschrijvende logica. Relatie tussen SHIF, SHOIN en SROIQ,
en de OWL-talen. “Hoe expressiever de taal, hoe complexer het redeneren”:
voorbeelden van verschillende beschrijvende logica’s en complexiteit van
het redeneren in deze logica’s. Combinaties van beschrijvende logica’s
met eerder besprokene uitbreidingen: niet-monotoon redeneren,
onzekerheid, vaagheid, uitleg.
- Beschrijvende
logica's: Franz
Baader, Werner Nutt "Basic Description Logics", Franz
Baader "Description Logics Terminology", Description
Logics Bibliography
- Utbreidingen: Franz Baader,
Bernhard Hollunder "Embedding Defaults into Terminological
Knowledge Representation Formalisms", Piero
Bonatti, Carsten Lutz, Frank Wolter "Description Logics with
Circumscription", "Resolution
Based Explanations for Reasoning in the Descri[tion Logics ALC",
Daphne
Koller, Alon Levy, Avi Pfeffer "P-CLASSIC: A tractable
probabilistic description logic", Umberto
Straccia "Reasoning within Fuzzy Description Logics", Umberto
Straccia "A Fuzzy Description Logic for the Semantic Web"
- Deel 2: Het verwerven van kennis:
machinaal leren, informatie-retrieval en kennisblootlegging. Technieken
voor kennisblootlegging: intervieuws, het bouwen van ladders, repertory
grid. Drie vormen van machinaal leren. Clustering als voorbeeld van niet
gesuperviseerd leren. Hiërarchisch en scheidend clustering (inleding).
- Kennisblootlegging: Guus Schreiber, Hans
Akkermans, Anjo Anjewierden, Robert de Hoog, Nigel Shadbolt, Walter Van
de Velde, Bob Wielinga. "Knoweldge Engineering and Management"
(hoofdstuk 8)
- Het verwerven van kennis: machinaal
leren, niet gesuperviseerd leren, clustering. Scheidend clustering met
behulp van grafentheorie (minimaal opspannende boom, max cut) en
statistiek (k gemiddelde, k centroïden, vage k
gemiddelde; aantal clusters bepalen).
- Trevor
Hastie, Robert Tibshirami, Jerome Friedman. "The Elements of Statistical
Learning" (Hoofdstuk 14.3)
- Het verwerven van kennis: machinaal
leren, gesuperviseerd leren, classificatie. Classificatietechnieken:
versieruimtes, beslisbomen, lineaire modellen met behulp van de kleinste
kwadraten benadering, k dichtsbijzijnde buren.
- Data mining Gastcollege door Dr.
Toon Calders
- Het gebruiken van kennis: planning. Klassieke planning: aannames,
oplossingen (voorwaarts zoeken, achterwaarts zoeken, STRIPS). Reductie
naar SAT. Het oplossen van SAT (Davis-Putnam, stochastisch).
- Malik Ghallab, Dana Nau, Paolo Traverso. “Automated
planning” (Hoofdstukken 2-4, 8).
- Roosteren. Wat is een roosteringprobleem? Welke
parameters zijn van belang bij het omschrijven van een dergelijk probleem?
Voorbeelden van roosteringproblemen. Onderbreekbare en niet onderbreekbare
opdrachten. Benaderingsalgoritmen.
- Peter Brucker, “Scheduling algorithms”
(Hoofdstukken 1, 4.2, 5.1)
- Genetische algoritmen. Wat zijn genetische algoritmen? Hoe
kan je genetische algoritmen gebruiken om NP-volledige problemen op te lossen?
Huiswerk (aanbevolen)
- Huiswerk 0. Kies en bespreek één van de volgende
kennisvoorstellingsformalismen: semantic networks, frames and scripts,
UML, production rules. Wat zijn de sterke en de zwakke kanten? In te
dienen tot 17 april 2007, 12 uur 's middags in Alexander z'n
brievenbus (naast HG 5.91).
- Huiswerk 1. XPath is een andere manier om naar delen van een
XML document te verwijzen. Aanbevolen: een paper van Maarten Marx. Schrijf een rapportje over XPath.
Hoe zou je XPath gebruiken bij het bouwen van een kennissysteem? In te
dienen tot 17 april 2007, 12 uur 's middags in Alexander z'n
brievenbus (naast HG 5.91).
- Huiswerk 2. Schrijf een rapportje over de heuristische
zoekalgoritmen. Wat is een heuristisch zoekalgoritme? Wat zijn de aannames
om die toe te passen? Hoe kunnen we dat op de SLD-bomen toepassen?
Sleutelwoorden: informed search, heuristic search, iterative diepening,
A*, Hill Climbing Vervolgvak: 2IN40 - Heuristic search. In te dienen tot
17 april 2007, 12 uur 's middags in Alexander z'n brievenbus (naast HG
5.91).
- Huiswerk 3. Soms wordt het beweerd dat Prolog met de
aannname van een gesloten wereld werkt. Dat is niet het geval: Prolog
werkt met negatie als eindig falen (negation as finite failure).
Zoek uit wat het verschil is tussen de twee, besprek de voor- en de
nadelen. In te dienen tot 24 april 2007, 12 uur 's middags in
Alexander z'n brievenbus (naast HG 5.91).
- Huiswerk 4. Hoe moeilijk is het berekenen van CIRC?
Bespreek de complexiteit van de prepositionele circumscriptie. Beantwoord
de volgende vragen: wat is een prepositionele circumscriptie? Wat is Πp2? Over welke dichotomie gaat het? In te dienen tot 24 april
2007, 12 uur 's middags in Alexander z'n brievenbus (naast HG 5.91). Lectuur:
- Th. Eiter, G.
Gottlob: Propositional Circumscription and Extended Closed-World
Reasoning are Πp2-Complete. Theor. Comput.
Sci. 114(2): 231-245 (1993)
- L. M. Kirousis, Ph.
G. Kolaitis: A Dichotomy in the Complexity of Propositional
Circumscription. Theory Comput. Syst. 37(6): 695-715
- Huiswerk 5. Er zijn veel verschillende varianten van
verstekregels Kies er één van, bestudeer en vat samen! Zoek
bijvoorbeeld: priorities, quasi-default, cautious semantics, justified
semantics, cumulative default logics, … In te dienen tot
24 april 2007, 12 uur 's middags in Alexander z'n brievenbus (naast HG
5.91).
- Huiswerk 6. []p wordt ook gebruikt als “altijd p” of
als “het is verplicht dat p”. Lees over modale logica’s. Voorbeelden van
modale logica's: temporele, deontische logica’s. Kies een van de twee.
Schrijf een verslag: modale logica’s in het algemeen, voorbeeld van een
temporele/deontische logica, axioma’s die ervoor van toepassing zijn. In
te dienen tot 24 april 2007, 12 uur 's middags in Alexander z'n
brievenbus (naast HG 5.91).
- Huiswerk 7. Combinatieregel F: P(α|β*1Ù … Ùβ*n) = F(P(α|β*1), …, P(α|β*n)). Deterministische combinatieregels:
logische (Ù, Ú, Ø), numerieke (min, max, avg), “Noisy-OR”.
Maak een overzicht van verschillende combinatieregels. In te dienen
tot 1 mei 2007, 12 uur 's middags in Alexander z'n brievenbus (naast HG
5.91).
- Huiswerk 8. Balios is een onderdeel van Profile-suite. Bespreek Balios met nadruk op
uitdrukkingskracht vs. efficiëntie; bijkomende eigenschappen; sterke en
zwakke punten. In te dienen tot 1 mei 2007, 12 uur 's middags in
Alexander z'n brievenbus (naast HG 5.91).
- Huiswerk 9. Redeneren met vaagheid. In de les hebben we
een mogelijke combinatie regel en een manier om de graden van het hoofd te
berekenen besproken. Bespreek ten minste een andere combinatieregel en een
andere manier om de graden van het hoofd te berekenen. In te dienen
tot 1 mei 2007, 12 uur 's middags in Alexander z'n brievenbus (naast HG
5.91).
- Huiswerk 10. Kies een van de
bestaande technieken voor het berekenen van een abductieve uitleg. Wat de
techniek samen. Wat is de complexiteit van het algoritme? Sterke en zwakke
punten? In te dienen tot 8 mei 2007, 12 uur 's middags in
Alexander z'n brievenbus (naast HG 5.91). Aanbevolen:
- Huiswerk 11. Lees het artikel
van Reiter. Bespreek de relatie tussen consistentiegebaseerde
uitleg en verstekregels. In te dienen tot 8 mei 2007, 12
uur 's middags in Alexander z'n brievenbus (naast HG 5.91).
- Huiswerk 12. ALC kan verder beperkt worden: schrijf een
verslag over beschrijvende logica’s die minder expressief zijn dan ALC. Wat zijn ze? Hoe complex is het
redeneren? In te dienen tot 15 mei 2007, 12 uur 's middags in
Alexander z'n brievenbus (naast HG 5.91).
- Huiswerk 13. Er zijn ook andere
kennisblootleggingtechnieken behalve diegene die we tijdens de les
besproken hebben: bijvoorbeeld, regelinductie en protocolanalyse.
Schrijf een verslag over een (aantal) van deze technieken. Vergelijk ze met interviews,
het bouwen van ladders en reportory grid. Wat zijn hun voor-
en nadelen? Wanneer zal je deze technieken toepassen? In te dienen
tot 15 mei 2007, 12 uur 's middags in Alexander z'n brievenbus (naast HG
5.91).
- Huiswerk 14. Een belangrijk probleem is het clusteren van
XML documenten. Welke technieken zou je ervoor gebruiken? Aanbevolen
lectuur: “Clustering
XML documents by structure” van Theodore Dalamagas, Tao Cheng, Klaas-Jan
Winkel, and Timos Sellis. In te dienen tot 29 mei 2007, 12 uur
's middags in Alexander z'n brievenbus (naast HG 5.91).
- Huiswerk 15. ID3 kan verbeterd worden, de verbeterde
versies heten C4.5 en C5.0. Bespreek de optimalisaties van C4.5 en/of
C5.0. Geef een voorbeeld die de voordelen van C4.5/C5.0 ten opzichte van
ID3 aantoont. In te dienen tot 5 juni 2007, 12 uur 's middags in
Alexander z'n brievenbus (naast HG 5.91).
- Huiswerk 16. Een andere “lineaire model” aanpak is Linear
Discriminant Analysis (LDA). Wat is LDA? Hoe wordt die berekend?
Voorbelden van succesvolle toepassingen In te dienen tot 5
juni 2007, 12 uur 's middags in Alexander z'n brievenbus (naast HG
5.91).
- Huiswerk 17. De behoefte om “torentjes af te breken”, maw
inefficiency is niet het enige probleem van STRIPS. Wat zal STRIPS doen met het “twee
variabelen” voorbeeld? Waarom? In te dienen tot 19 juni 2007, 12 uur 's middags in Alexander z'n brievenbus
(naast HG 5.91).
- Huiswerk 18. In plaats van reductie naar SAT, kunnen we constraints
satisfaction problems (CSP) gebruiken. Wat is een constraints
satisfaction problem? Hoe stel je een planningprobleem als CSP? Hoe los je
een CSP op? Geef voorbeeld van een planningprobleem en toon aan hoe je die
1) naar CSP vertaald, 2) oplost en 3) een plan extraheert. In te dienen tot 19 juni 2007, 12 uur 's middags in
Alexander z'n brievenbus (naast HG 5.91).
- Huiswerk 19. Gonzalez en
Sahni hebben een betere techniek voorgesteld om het besproken probleem
van gelijkaardige machines op te lossen. Hun algoritme is efficiënter
(O(n+m log n)) en creërt minder onderbrekingen. Bespreek het artikel. Kies
een voorbeeld en toon aan dat er inderdaad minder onderbrekingen worden
aangemaakt. In te dienen tot 26 juni 2007, 12 uur 's middags in
Alexander z'n brievenbus (naast HG 5.91).
- Huiswerk 20. Belangrijke problemen in het roosteren
hebben vaak te maken met de zo genaamde “shops”: Wat zijn de general/open/flow/job
shop problemen? Geef voorbeelden en bespreek een van de bijbehorende
algoritmen. Wat is de complexiteit ervan? In te dienen tot 26
juni 2007, 12 uur 's middags in Alexander z'n brievenbus (naast HG
5.91).
- Huiswerk 21. Analyseer het algoritme voor parallelle machines, onderbreekbare
opdachten en zo klein mogelijke doorlooptijd, dat we tijdens de les
besproken hebben (Transparanten 58-62).
Bewijs dat het algoritme inderdaad een optimale rooster oplevert (denk aan
Jackson!). Wat is het maximale aantal onderbrekingen als functie van het
aantal machines en het aantal opdrachten? In te dienen tot 26
juni 2007, 12 uur 's middags in Alexander z'n brievenbus (naast HG
5.91).
Opdrachten (verplicht)
- Opdracht 0. Kies een KS beschikbaar
on-line. Welke opdrachten voert het KS uit? Hoe wordt kennis voorgesteld,
verworven, beredeneert en gebruikt? Was, volgens je, KS een geschikte
oplossing voor het probleem? Waarom? Sleutelwoorden: expert system,
knowledge-based system, decision support, planning, scheduling,
classification. In te
dienen tot 10
april 2007, 12 uur 's middags in Alexander z'n brievenbus (naast HG 5.91).
- Opdracht 1. Redeneren. Zie een apart document. Ik raad ten zeerste aan om zo
vroeg mogelijk aan deze opdracht te beginnen en iedere week een stapje
verder te zetten. In te dienen tot 22 mei 2007, 12 uur 's middags
in Alexander z'n brievenbus (naast HG 5.91).
- Opdracht 2. Clustering. Kies een
van de volgende datasets (geboorte- en sterfcijfers per land (doc
– ter informatie, tsv – tab
separated values), metrieken van objecten in een software systeem (doc, tsv),
astronomische karakteristieken van sterrenbeelden (doc,
tsv);
als jullie een andere dataset willen gebruiken, bespreek het met mij
eerst). Jullie doel is het onderscheiden van groepjes (clusters) gerelateerde landen,
objecten en sterrenbeelden door scheidend clustering te gebruiken. In te dienen: implementatie van het
gekozen algoritme en het bijbehorende verslag.
Implementatie:
a) Moet met een willekeurige
tab-separated bestand kunnen werken. Het eerste colom bevat namen van de
objecten, alle andere – verschillende eigenschappen (reële getallen).
b) Moet op mijn laptop draaien (zorg indien nodig voor de installatiegids)
c) Ik ben wel bereid om een kwartiertje
te wachten op een clusteringprogramma maar zeker geen uur!
De volgende punten moeten in het verslag toegelicht worden (ik gebruik
een dataset van chemische
elementen als voorbeeld):
- Welke dataset hebben jullie gekozen?
- Voor welke
clusteringtechniek(en) hebben jullie gekozen? Waarom?
- Welke ongelijkheidsmaat hebben jullie
gebruikt?
a)
NB: ongelijkheidsmaat moet gebaseerd worden op ten
minste twee eigenschappen per voorbeeld
- Hoe wordt het aantal clusters bepaald?
a)
Hoe
hebben jullie de bovengrens gekozen voor het aantal clusters (K)?
- Wat zijn de resultaten van de clustering?
a)
Welke
landen, objecten of sterrenbeelden horen samen?
b)
Kunnen
jullie de clusters omschrijven in termen van de eigenschappen (bijv. het aantal
isotopen is lager dan… en het smelttemperatuur is hoger dan…)
c)
Wat
is de verschilmaat van de clusterverdeling (W)?
d)
Kunnen
jullie in deze clusters bepaalde bekende groepen herkennen, bijv., metalen?
- Bespreek het ontwerp en de implementatie.
In te
dienen tot 5 juni
2007, 12 uur 's middags in Alexander z'n brievenbus (naast HG 5.91).
- Opdracht 3. Procesmining. Het doel van procesmining bestaat in
het ontdekken van een procesmodel
gegeven een log. In het kader
van deze opdracht is een log een
XML document en een procesmodel bestaat
uit een reeks MINEPI regels van de volgende vorm: “Als een episode a plaatsvond tijdens een tijdsinterval
van lengte w1, dan zal in v% van
gevallen een episode b plaatsvinden op een verlenging van het
tijdsinterval tot lengte w2”. Lees meer...
Het artikel
van Manilla, Toivonen, Verkamo.
Voorzie voldoende tijd voor het schrijven van het verslag!
Drie voorbeelden van logs:
1. KBS-log0.xml Log uit het artikel van Manilla, Toivonen
en Verkamo.
2. KBS-log1.xml. Nog steeds dezelfde log, deze keer
ingedeeld in drie verschillende procesinstances.
3. KBS-logReviews.xml. Beoordelen van wetenschappelijke
publicaties.
Update 10
juli 2007:
1.
Op verzoek van Johan en Stef: zip met de bijkomende ProM documentatie (JavaDoc
inbegrepen). Let op! Documentatie is misschien niet echt up-to-date.
2.
numSimilarInstances
is het aantal identieke ProcesInstances.
In te
dienen verslag en
de implementatie. Deadline: 18 juli 2007, 12 uur 's middags elektronisch naar
a.serebrenik @ tue.nl (naast HG 5.91).
NB: Deadline
is strikt omwille van de sluiting van het onderwijssecretariaat.