Talen en automaten/2011-12/producten/AILog

definitive

Page Break

Talen en automaten

Erik Barendsen

2011-12
- deelnemers
- instructies
  - dossier
  - werkstuk
- producten
  - AILog
    - test
  - Asterisk
  - Bash
  - BBcode
  - Brainfuck
  - C
  - Chef.
  - Clojure
  - Cow
    - Examples
  - Cplusplus
  - Entropy
  - euphoria
  - Foo
  - GW-BASIC
  - HyperText
  - Iota
  - Java
  - Jug
  - Lang-e-Tape
  - LaTeX
  - Lolcode
  - LUA
  - NXT
  - ObjectiveC
  - Omgrofl
  - Ook!
  - ORK
  - PCTL
  - Piet
  - Popmuziek
  - predicaten logica
  - Prelude
  - Python
  - Rekenmachine
  - Shakespeare
  - Test
  - Whitespace
  - XML

Case Study AILog

Wouter Bulten, Frank Dorssers

Talen en automaten 2011-12

13:30 A

Wouter Bulten^{Bachelor kunstmatige intelligentie}

e-mail

cursuspagina

Frank Dorssers^{Bachelor kunstmatige intelligentie}

e-mail

cursuspagina

Page Break

Inhoud

1 Beschrijving
- 1.1 Gebruik maken van AILog
- 1.2 Gebrek aan documentatie
2 Is AILog regulier?
3 Is AILog contextvrij?

Beschrijving

AILog is een simpele taal om mee te representeren en te redeneren. AILog zelf is redelijk onbekend (er is bijvoorbeeld geen Wikipedia pagina over) maar wordt toch vaak gebruikt, omdat het naast eenvoud ook veel kracht heeft. Het komt dan ook vaak naar voren in AI gerelateerde cursussen om bijvoorbeeld problemen te representeren of te redeneren met Bayesiaanse netwerkmodellen.

Het is ontwikkeld als onderdeel van het boek Artificial Intelligence: foundations of computational agents door David Poole en Alan Mackworth waarbij de eerste ook de ontwikkelaar van AILog is.

Volgens de auteur kan AILog het beste gebruikt worden om 'te representeren in logica' en het toe te passen op domeinen waar logische relaties bekend zijn. Door het domein te beschrijven met behulp van logica kan de gebruiker hieruit afleidingen maken.

Een klein voorbeeld van hoe kennisregels in AILog opgeschreven zijn is te zien in het onderstaande voorbeeld. Deze en andere (uitgebreide) voorbeelden zijn ook te vinden op de website.

away_from_beach <- ~ on_beach.
beach_access <- on_beach & ~ab_beach_access.
swim_at_beach <- beach_access & ~ab_swim_at_beach.
ab_swim_at_beach <- enclosed_bay & big_city & ~ab_no_swimming_near_city.
ab_no_swimming_near_city <- in_BC & ~ab_BC_beaches.

Gebruik maken van AILog

AILog is geschreven in Prolog en moet daar ook in opgestart worden (de door ons gebruikte implementatie is SWI-Prolog). Ondanks dat de basis Prolog is wil de auteur wel benadrukken dat er een groot verschil is:

"Although it has similarities with Prolog, it should not be seen as 'programming in logic', but as 'representing in logic'." (David Poole)

Om te interacteren met AILog is het mogelijk om een bestand in te laden met commando's en kennisregels. Elke kennisregel wordt geanalyseerd en toegevoegd aan de kennisbank. Een voordeel hiervan is dat kansen pas berekend worden als ze nodig zijn. Een kans gerepresenteerd als 1/10000 wordt ook pas uitgerekend als hij nodig is.

Het is echter ook mogelijk om regels één voor één aan te bieden aan de command line interface. Deze manier van invoeren is een stuk interactiever omdat er op veel commando's ook gereageerd kan worden. Hieruit volgt ons eerste probleem:

Probleem 1: Hoe gaan we om met het verschil tussen invoer via de command line interface (CLI) en bestanden?

Wij hebben er voor gekozen om alles te representeren dat zowel via de CLI als via invoer door middel van bestanden wordt geaccepteerd. Via de CLI zijn er in sommige gevallen meer mogelijkheden (vervolg commando's op queries) maar dit hangt af van de verwerking van de kennisbank. Als deze commando's ingevoerd worden in een invoerbestand worden ze genegeerd.

Gebrek aan documentatie

Een van de weinige plekken op internet om informatie te vinden over AILog is de officiële handleiding. Hierin wordt beschreven hoe je informatie kunt representeren en wat daar vervolgens mee gedaan kan worden. Nu is deze handleiding genoeg voor dagelijks gebruik van de taal, echter voor ons doeleinde schoot het tekort. Het vertelt bijvoorbeeld weinig over syntactische eisen.

Probleem 2: Hoe kunnen we AILog representeren in een contextvrije grammatica zonder (complete) kennis over specifieke syntax eisen?

Nu word de situatie verergert doordat AILog in sommige gevallen te veel accepteert en soms te weinig. Een klein voorbeeld kan dit het beste uitleggen:

prob a: 1.
prob b: 2.
prob c: 2*100.
prob f: -2.
prob g: -1 * -1.
prob h: -(-1).

Een prob statement moet een getal tussen de 0 en 1 krijgen, het geeft immers een kans aan. Echter bovenstaande statements worden allemaal geaccepteerd met uitzondering van de laatste. Wanneer de laatste statement aangeboden wordt zal AILog een foutmelding geven:

Probability must be a number or expression in range [0,1]

Dit is vreemd, je zou immers verwachten dat alle kansen met een waarde boven één worden afgewezen. Om hier toch mee om te kunnen gaan hebben wij er voor gekozen om te representeren wat er geaccepteerd wordt, ook al is dat dan niet altijd correct.

Naast dit zijn er nog meer gevallen waar er onverwachte resultaten zijn. Zo mogen bepaalde commando's alleen gegeven worden als reactie op een ander commando. Een voorbeeld hiervan is het more commando wat de volgende verklaring geeft voor een bepaalde observatie. In een tekstbestand mag dit command echter overal staan, het wordt geaccepteerd maar verder genegeerd.

Het voordeel van een gebrek aan documentatie is dat we ook geen contextvrije grammatica of formele specificatie konden vinden. Dit gaf ons de mogelijkheid om deze zelf te schrijven wat natuurlijk ook bijdraagt aan de documentatie omtrent AILog.

Is AILog regulier?

De meeste statements van AILog zijn kort en hebben weinig afhankelijkheden. Om te bewijzen dat AILog niet regulier is moeten we een statement vinden waar deze afhankelijkheid wel in zit. Dit kan bijvoorbeeld met het prob statement. In zijn simpelste vorm bestaat deze uit een variabele en een kans:

prob a: 0.4.

Echter, het is ook mogelijk om berekeningen uit te voeren:

prob a: 0.4 * 0.2.

Om te zorgen dat de volgorde klopt is het ook mogelijk om haakjes toe te voegen, mits er net zoveel 'open'haken als 'sluit'haken zijn:

prob a: ((((0.4)))).

Nu moeten we een woord z vinden van lengte minimaal k. We nemen aan dat AILog regulier is, dit betekent dat z geaccepteerd moet worden door een eindige automaat met maximaal k states. Uit de bovenstaande code fragmenten kunnen we het volgende woord afleiden:

Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Z = prob\ a:\ (^k\ 0\ )^k.}

Volgens het pomplemma zouden we dit moeten kunnen schrijven als Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Z = uvw} waarbij:

Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u = prob\ a:\ (^p,\qquad v = (^q,\qquad w = (^{k-p-q} 0\ )^k.}

Nu moet elk woord van de vorm Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Z' = uv^iw} ook geaccepteerd worden voor elke Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i >= 0} . Stel we nemen:

Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Z' = uv^2w = prob\ a:\ (^p (^{2q} (^{k-p-q} 0\ )^k. = prob\ a:\ (^{k+q} 0\ )^k.}

Bij Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Z'} zijn het aantal begin- en sluithaken niet gelijk wat betekent dat Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Z'} niet door de taal geaccepteerd wordt. Dit zou volgens het pomplemma wel moeten en dit is daarom in tegenspraak met onze aanname dat de taal regulier is. AILog is dus geen reguliere taal.

Is AILog contextvrij?

Context-free grammar of AILog
This grammar accepts all rules that are syntactically accepted by the AILog system.

Start → <Input> . | <Output> . | <Basic-commands> .

Input commands

Input →: create_nogoods; | <unobserve>; | <prob_threshold>; | tell <clause>; | cd <directory>; | load <filename>; | prload <filename>; | prob <prob-sequence>; | assumable <atom-sequence>

unobserve →: unobserve; | unobserve all

prob_threshold →: prob_threshold; | prob_threshold <chance>

Output commands

Output →: probs; | worlds; | observations; | explanations; | assumables; | nogoods; | ask <body>; | whynot <body>; | observe <body>; | predict <body>

Basic commands

Basic-commands →: quit; | check; | prolog; | askables; | stats runtime; | <help>; | <clear>; | <listing>; | allow <atom>; | bound <number>; | askable <atom>

listing →: listing; | listing <atom>

clear →: clear; | clear <atom>

help →: help; | help prob; | help abduction

Low level

body →: <atom>; | ~<body>; | <body>&<body>

atom →: <name>; | <name> ( <terms> )

atom-sequence →: <atom>; | <atom> , <atom-sequence>

prob-sequence →: <atom> : <operation>; | <atom> : <operation>, <prob>

terms →: <term>; | <term> , <terms>

term →: <variable>; | <constant>

variable →: <uppercase>; | <uppercase><restname>

constant →: <lowercase>; | ' <restname> '; | <double>; | <lowercase><restname>

name →: <lowercase>; | <lowercase><restname>

restname →: <alphanum>; | <alphanum><restname>

filename →: <alphanum-special>; | <alphanum-special> <filename>

directory →: <foldername>; | ' <foldername-space> '; | <foldername> / <directory>; | ' <foldername-space> ' / <directory>

Basic

operation →: <operation> * <operation>; | <operation> + <operation>; | <operation> - <operation>; | <operation> / <operation>; | ( <operation> ); | - ( <operation> ); | - <double>; | <double>

double →: <number>.<number>; | <number>

number →: 0<number> | 1<number> | ... | 9<number>; | 0 | 1 | ... | 9

chance →: 0; | 1; | 0. <number>

lowercase →: a | b | ... | z

uppercase →: A | B | ... | Z

alphanum-special →: a | b | ... | z; | A | B | ... | Z; | 0 | 1 | ... | 9; | _ | ( | ) | + | - | ? | > | < | "

alphanum →: a | b | ... | z; | A | B | ... | Z; | 0 | 1 | ... | 9; | _

foldername →: <alphanum>; | <alphanum> <foldername>

foldername-spec →: <alphanum-special>; | <alphanum-special> <alphanum-spec>

foldername-space →: <foldername-spec>; | <foldername-spec> <space> <foldername-space>

space →: | <space>

Knowledge rules

clause →: <atom> <- <expression>

expression →: <atom>; | ~ <expression>; | <expression> & <expression>

Talen en automaten/2011-12/producten/AILog

Inhoud

Beschrijving

Gebruik maken van AILog

Gebrek aan documentatie

Is AILog regulier?

Is AILog contextvrij?

Input commands

Output commands

Basic commands

Low level

Basic

Knowledge rules

Navigatiemenu

Persoonlijke instellingen

Naamruimten

Varianten

Weergaven

Meer

zoek

Afdrukken/exporteren

Hulpmiddelen