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:

1. Kennis van elementaire concepten op het gebied van kennissystemen.
2. Kennis en praktische vaardigheid in het voorstellen van, het redeneren over, het verwerven van en het gebruiken van kennis.
3. 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).
2. 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.

• OWL: Uniform Resource Identifier (URI): Generic Syntax, Extensible Markup Language, XML schema, RDF, RDFS, OWL
• Eerste orde logica. Rik van Geldrop, "Bird's-eye view of Logic Programming". Entailment @ Wiki.
2. 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.
• Vladimir Lifshitz "Circumscription", Robert Stärk, "On the existence of
  xpoints in Moore's autoepistemic logic and the non-monotonic logic of McDermott and Doyle"
3. 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.
• Kristian Kersting and Luc De Raedt "Bayesian Logic Programs", Kristian Kersting and Luc De Raedt "Bayesian Logic Programming: Theory and Tool", Judea Pearl "Fusion, Propagation and Structuring in Belief Networks", F. J. Diez "Parameter adjustment in Bayes networks: the generalised noisy OR-gate", Peter Vojtas "Fuzzy logic programming"
4. 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.
• Peter Jackson, "Computing Prime Implicates", Raymond Reiter "A Theory of Diagnosis from First Principles"
• 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.
1. Beschrijvende logica's: Franz Baader, Werner Nutt "Basic Description Logics", Franz Baader "Description Logics Terminology", Description Logics Bibliography
2. 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).
1. Kennisblootlegging: Guus Schreiber, Hans Akkermans, Anjo Anjewierden, Robert de Hoog, Nigel Shadbolt, Walter Van de Velde, Bob Wielinga. "Knoweldge Engineering and Management" (hoofdstuk 8)
6. 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)
7. Het verwerven van kennis: machinaal leren, gesuperviseerd leren, classificatie. Classificatietechnieken: versieruimtes, beslisbomen, lineaire modellen met behulp van de kleinste kwadraten benadering, k dichtsbijzijnde buren.
8. Data mining Gastcollege door Dr. Toon Calders
9. 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).
10. 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)
11. 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 Π^p₂? 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 Π^p₂-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(α|β^*₁Ù … Ùβ^*_n) = F(P(α|β^*₁), …, 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:
• Eiter, Makino, “Generating all abductive explanations from a propositional Horn theory”.
• Denecker, De Schreye, “SLDNFA: an abductive procedure for normal abductive programs”.
• 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):

1. Welke dataset hebben jullie gekozen?
2. Voor welke clusteringtechniek(en) hebben jullie gekozen? Waarom?
3. Welke ongelijkheidsmaat hebben jullie gebruikt?

a) NB: ongelijkheidsmaat moet gebaseerd worden op ten minste twee eigenschappen per voorbeeld

4. Hoe wordt het aantal clusters bepaald?

a) Hoe hebben jullie de bovengrens gekozen voor het aantal clusters (K)?

5. 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?

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