[alg] Dynamisch gebruik van oneindige graaf

[MicroWhale]

Dit is een theorem over het dynamisch gebruik van de oneindige boom. Het doel is om deze boom zodanig te gebruiken dat, met behulp van een aantal nog te definieren methoden, een zekere mate intelligentie te simuleren is.

Bij een oneindige boom kan elk element met elk element gekoppeld worden. Voor het gemak laten we de mogelijkheid dat een element met zichzelf gekoppeld wordt vervallen.

Zo kunnen door koppelingen relaties aangegeven worden. Wat deze relaties inhouden voor de boom en wat de elementen van deze boom bevatten is op zich niet van belang.

Een voorbeeld maakt eea wellicht duidelijk:

De elementen in de boom zijn:
• blauw
• is
• kleur
• joe zijn auto

de relaties zijn als volgt:

blauw->is->kleur
"joe zijn auto"->is->blauw

Aan de hand van de vraag "wat is de kleur van joe zijn auto?" zou het, nog te definieren, algoritme op het element "blauw" uit moeten komen. En dus ook als de boom veel meer elementen bevat als hierboven aangegeven is.

Dat is dus het idee.

Nu is aan jullie de vraag:
• is het mogelijk?
• zie ik iets essentieels over het hoofd?
• is er misschien een betere/slimmere manier waarop ik dit kan doen?
• hoe laat ik de boom snel / correct groeien?
• op welke manieren kan dit concept nog meer toegepast worden?

Alvast dank

[ Voor 5% gewijzigd door MicroWhale op 11-07-2003 12:06 ]

[Alarmnummer]

Ik denk dat je even moet kijken naar semantische netwerken en frames.

Je zou trouwens ook perfect met prolog hiermee kunnen experimenteren als je er behoefte aan hebt (hierin kan je ook met frames en semantische netwerken werken):

fijn boek:
Prolog Programming for Artificial Intelligence by Ivan Bratko
hierin staat ook uitleg over semantische netwerken en frames.

[ Voor 19% gewijzigd door Alarmnummer op 11-07-2003 12:19 ]

[Soultaker]

Volgens mij bedoel jij een graaf, en niet een boom. In een boom kunnen per definitie geen cykels voorkomen (en kunnen dus niet alle elementen "gekoppeld" worden). Een oneindige graaf wordt ook als basis gebruikt bij de ontwikkelingen rond het Semantische Web van het W3C, al vormt het daar slechts een basis. Zij geven trouwens de verbindingen in de graaf ook een naam, waardoor je dus dit soort relaties krijgt:

code:

blauw ---type---> kleur
fiets ---kleur---> blauw
fiets ---eigenaar---> Soultaker

Voor het semantische web is dit natuurlijk pas interessant wanneer alle gebruikte identifiers ook een goedgedefinieerde betekenis hebben, maar daar gaat jou nu waarschijnlijk niet om. Waar ik echter heen wilde is dat daar ook een querytaal bij ontwikkeld waarmee het mogelijk moet zijn om informatie over een zekere knoop in de graaf te verzamelen. Misschien kun je daar eens naar kijken wat ideeën opdoen over de mogelijkheden.

[MicroWhale]

Dank voor de links, weer wat nuttig leesvoer

Het is inderdaad een graaf en niet een boom.

De uitdaging zit hem erin om met zo weinig mogelijk definitie (buiten de boom zelf) van de elementen zelf, een graaf te krijgen waaruit een algoritme een voor de gebruiker "zinnig" antwoord kan genereren.

De querytaal zal in dit geval dan "geschreven taal" worden. Maar ook hier heb ik mezelf als uitdaging gesteld dat het algoritme dat hiervoor gebruikt wordt, zo generiek mogelijk moet worden.

[Soultaker]

Als ik zo'n systeem zou moeten implementeren, zou ik het liefst beginnen met een simpele en flexibele basis, waar de gegevens in opgeslagen staan. Bekijk dus de verschillende manieren waarop je toegang wilt krijgen tot de inhoud en welke datarepresentaties en bijbehorende algoritmen daar het meest geschikt voor zijn. Moet je graag dynamisch bijgewerkt kunnen worden of is 'ie in principe statisch (waarbij je 'm natuurlijk wel in het geheel opnieuw kan opbouwen)?

Vervolgens zou ik een querytaal weer op een laag nivo (met een beperkt aantal commando's) implementeren en los daarvan een "vertaler" ontwikkelen om de queries in natuurlijke taal om te zetten in de simpele variant. Op die manier kun je het systeem decomposeren in verschillende overzichtelijke onderdelen en de complexiteit van het geheel drastisch beperken. Uiteraard is het hierbij de truc om top-down vanuit het uiteindelijke gebruiksdoel te redeneren. Stel dus eerst vast welke functionaliteit je wilt aanbieden en daarna pas hoe je die gaat implementeren; als je het andersom doet is de kans groot dat je eerst een basis ontwikkeld, waar je je eigenlijke doel niet goed mee kunt bereiken.

Maar goed, dat zijn natuurlijk alleen mijn ideeën. Waarschijnlijk had je er zelf ook al over nagedacht?

[Alarmnummer]

Ik denk dat je ook moet kijken naar pattern-mathing. Hiermee kan je ook eenvoudig op bepaalde pattronen in die boom gaan zoeken. En laat het nou zou dan prolog ook pattern matching heeft

[MicroWhale]

Alarmnummer schreef op 11 July 2003 @ 13:14:
Ik denk dat je ook moet kijken naar pattern-mathing. Hiermee kan je ook eenvoudig op bepaalde pattronen in die boom gaan zoeken. En laat het nou zou dan prolog ook pattern matching heeft

haha... beetje pro-prolog meneer?!?!

Ik wilde als basis vanuit alle elementen uit de zin, die in de graaf voorkomen, het algoritme laten "redeneren". Dit houdt in dat het vanuit elk element in de zin gaat lopen richting de andere elementen om zo het verband tussen de elementen te leggen. Op deze manier hoop ik de behoefte aan ontwikkeling van een query-taal te vermijden. Het moet dus lekker abstract blijven. (de graaf wordt de script-taal)

Hoe dit zou moeten gebeuren is vooralsnog vrij vaag. Dit komt voornamelijk omdat het (met opzet!) allemaal heel abstract gehouden moet worden.

De taal is trouwens Delphi. Ik heb een object ontworpen waarmee een oneindige graaf gemaakt kan worden, met bijbehorende onderhoud-functies. De boom kan geladen worden en weggeschreven. Verschillende bomen kunnen samengevoegd worden tot één geheel. Dit buiten de basis-funties van het toevoegen, veranderen, verplaatsen en verwijderen van elementen.
Visuele representatie geschied nu middels een aantal Tlistbox. Op een later moment zou er voor een visuele representatie gekozen kunnen worden. Functies hiervoor zijn reeds aanwezig.

[Glimi]

_{Een titelverandering naar [alg] Dynamisch gebruik van oneindige graaf dus?}

[MicroWhale]

Glimi schreef op 11 July 2003 @ 13:34:
_{Een titelverandering naar [alg] Dynamisch gebruik van oneindige graaf dus?}

graag

[Soultaker]

Door het huidige ontwerp van je graaf al als gegeven te stellen, beperk je je mogelijkheden (en je kansen op een solide ontwerp) nogal. Maar goed, dat terzijde, is het misschien een goed idee om wat concreter te formuleren wat je je bij "redeneren" voorstelt. Wat moet je systeem precies kunnen afleiden; welke beperkingen zijn acceptabel?

offtopic:
Overigens betwijfel ik ten zeerste of Prolog een zinnige implementatietaal is voor deze toepassing (of welke toepassing dan ook) aangezien je nogal beperkt wordt tot een klein aantal taalconstructies en (in alle implementaties die ik ken) een waardeloos typesysteem. Voor de kenmerken van de beschikbare constructies (in termen van efficiëntie bijvoorbeeld) ben je totaal overgeleverd aan de grillen van de implementatie. Als je implementatie niet schaalbaar blijkt te zijn, heb je waarschijnlijk gewoon pech. Mede hierdoor (maar ook door de grote verschillen in typesystemen) maakt het nogal veel uit welke Prolog-implementatie je gebruikt.

[MicroWhale]

Soultaker schreef op 11 juli 2003 @ 13:49:
Door het huidige ontwerp van je graaf al als gegeven te stellen, beperk je je mogelijkheden (en je kansen op een solide ontwerp) nogal. Maar goed, dat terzijde, is het misschien een goed idee om wat concreter te formuleren wat je je bij "redeneren" voorstelt. Wat moet je systeem precies kunnen afleiden; welke beperkingen zijn acceptabel?

Volgens de conventionele methode die wij hanteren/aanleren voor het maken van een model zoals dit, heb je helemaal gelijk. In het ontwerp zitten heel bewust keuzes die het moeilijker maken om direct een concreet algoritme te definiëren. Hiervan ben ik mij volledig bewust en het zou er inderdaad toe kunnen leiden dat al dit werk het niet resultaat oplevert dat ik aan het eind verwacht. Het is een onderzoek naar of dit mogelijk is. Vandaar ook mijn "Theorem" in de openings-post.

Ik zou graag je vraag willen beantwoorden over hoe ik het "redeneren" in dat algoritme zie, maar ik kan even de mogelijkheid niet vinden om dit in woorden op te schrijven. Het is veel makkelijker deze in woord en beeld (white-board) uit te leggen/tekenen. Deze houd je nog van me tegoed... ik ga even zoeken naar een makkelijke manier om het uit te leggen.

[Alarmnummer]

Soultaker schreef op 11 July 2003 @ 13:49:
[offtopic]Overigens betwijfel ik ten zeerste of Prolog een zinnige implementatietaal is voor deze toepassing (of welke toepassing dan ook) aangezien je nogal beperkt wordt tot een klein aantal taalconstructies

Maar het is wel handig om hiermee te experimenteren.

en (in alle implementaties die ik ken) een waardeloos typesysteem.

welk typesysteem?

Voor de kenmerken van de beschikbare constructies (in termen van efficiëntie bijvoorbeeld) ben je totaal overgeleverd aan de grillen van de implementatie.

Je gaat er dan meteen vanuit dat het allemaal snel en efficient moet. Je ziet dat hij nog een beeld probeerd te vormen van wat hij precies bedoelt, en zich nog lang niet druk hoeft te maken over zaken zoals efficientie.

Prolog is imho uitstekend geschikt om hier mee te experimenteren,

[MicroWhale]

Men zou er voor kunnen kiezen om het algoritme het volgende te laten doen.

Hiervoor zijn nodig:
• basis-elementen in de boom

Aanname: Een basis-element in een boom wordt bijvoorbeeld weergegeven door een * voor zijn naam.
Bijvoorbeeld (zeer vereenvoudigd):
Elementen:
• steen
• is
• hard
• *object
• *werkwoord
• *eigenschap
• wat

Boom:

steen->is->hard
steen->is->*object
is->is->*werkwoord
hard->is->*eigenschap
wat->is->*object

Dus.... als het algoritme de vraag "Wat is hard?" krijgt, kan vanuit het element "wat" via het basis-element "*object" gezocht worden naar de *eigenschap "hard".

Dit is in ieder geval wat ik het wil laten doen.

Het algoritme zou dan in staat moeten zijn om alle *objecten (of andere *-klassen die aan "wat" zijn verbonden) met de *eigenschap "hard" te vinden.

[MicroWhale]

Aanvulling:
Het enige dat het algoritme dan hoeft te weten is dat vanuit alles met een * gezocht kan gaan worden (iteratief/recursief/etc.)... Algoritme blijft dom, flexibiliteit hoog, antwoorden (hopelijk) goed.

[Alarmnummer]

Logos schreef op 11 July 2003 @ 13:32:
[...]
haha... beetje pro-prolog meneer?!?!

De laatste tijd ben ik weer veel aan het lezen over Prolog en ik ben weer gecharmeerd van deze taal.

Ik wilde als basis vanuit alle elementen uit de zin, die in de graaf voorkomen, het algoritme laten "redeneren". Dit houdt in dat het vanuit elk element in de zin gaat lopen richting de andere elementen om zo het verband tussen de elementen te leggen. Op deze manier hoop ik de behoefte aan ontwikkeling van een query-taal te vermijden. Het moet dus lekker abstract blijven. (de graaf wordt de script-taal)

Het kan soms wel erg handig zijn om toch een domeintaal te gaan maken. Allerlei akelige problemen zoals geheugen reserveren, pointers en transacties (om maar wat dingen op te noemen) die blijven achterwege. Je hoeft je dan alleen te concentreren op de problemen van dat domein, in jouw geval zal dat dus graven zijn.

Hoe dit zou moeten gebeuren is vooralsnog vrij vaag. Dit komt voornamelijk omdat het (met opzet!) allemaal heel abstract gehouden moet worden.

Is het een schoolopdracht? een thuis-knutsel project? of voor je werk?

Visuele representatie geschied nu middels een aantal Tlistbox. Op een later moment zou er voor een visuele representatie gekozen kunnen worden. Functies hiervoor zijn reeds aanwezig

Je bent op de hoogte van MVC (Model View Controller)?


.[/quote]

[MicroWhale]

Antwoorden in bold:

Alarmnummer schreef op 11 July 2003 @ 14:20:
[...]

De laatste tijd ben ik weer veel aan het lezen over Prolog en ik ben weer gecharmeerd van deze taal.

het is te merken
[...]

Het kan soms wel erg handig zijn om toch een domeintaal te gaan maken. Allerlei akelige problemen zoals geheugen reserveren, pointers en transacties (om maar wat dingen op te noemen) die blijven achterwege. Je hoeft je dan alleen te concentreren op de problemen van dat domein, in jouw geval zal dat dus graven zijn.

Het object-model van Delphi biedt ruimschoots voldoende mogelijkheden zodat je je niet bezig hoeft te houden low-level functies
[...]

Is het een schoolopdracht? een thuis-knutsel project? of voor je werk?

thuis-hobby. met de benodigde aspiraties natuurlijk
[...]

Je bent op de hoogte van MVC (Model View Controller)?
ja? maar dat is een manier van programmeren/implementeren. Het huidige model staat volledig los van enig interface, dus dat is geen probleem.

[Alarmnummer]

Het kan soms wel erg handig zijn om toch een domeintaal te gaan maken. Allerlei akelige problemen zoals geheugen reserveren, pointers en transacties (om maar wat dingen op te noemen) die blijven achterwege. Je hoeft je dan alleen te concentreren op de problemen van dat domein, in jouw geval zal dat dus graven zijn.

Het object-model van Delphi biedt ruimschoots voldoende mogelijkheden zodat je je niet bezig hoeft te houden low-level functies

Heb je ervaring met prolog? Als je er een keer mee gaat spelen krijg je toch een hele andere kijk op zaken. Delphi heeft bv geen pattern matching, en dat is typisch iets dat je perfect kan gebruiken om kennis te achterhalen. En verder is het rule-mechanisme echt iets heel bijzonders. Een rule kan je zien als een functie als je alle argumenten invult, maar als je er niets invult (dus een variable declareerd), dan krijg je er een waarde uit.

vb:

//dit zijn de gegevens (facts) die in mijn systeem aanwezig zijn
parent(tom,pat)
parent(pat,chris)

en nu ga ik vragen:
parent(tom,pat)

Dit is zo, want tom is een parent van tom.

maar je kan ook vragen:
parent(tom,X)

Dan krijg je voor X de waarde pat.

Prolog heeft een declaratieve manier van werken, en hierdoor ben je zelf van een hele lading problemen verlost. Verder zie je meestal ook beter wat je algoritme doet. Verder heeft prolog oa ook ingebouwde backtracking, zie het onderstaande voorbeeld:


voorouder(X,Y)
= ouder(X,Y) of ( ouder(X,Z) en voorouder(Z,Y));

Denk hier maar eens over na en probeer het maar eens met delphi na te maken. Ik probeer trouwens geen 'prolog is de oplossing' verhaal te houden, maar prolog zorgt ervoor dat je op een andere manier leert denken, en dit kan je perfect weer gebruiken in een taal zoals Delphi.

Is het een schoolopdracht? een thuis-knutsel project? of voor je werk?

thuis-hobby. met de benodigde aspiraties natuurlijk

Er is niet zo fijn als een thuis-knutsel-project. Geen druk, en doen wat je leuk vind

Je bent op de hoogte van MVC (Model View Controller)?
ja? maar dat is een manier van programmeren/implementeren. Het huidige model staat volledig los van enig interface, dus dat is geen probleem.

Ik kwam hierop omdat je het had over meerdere views over 1 stuk data heen. Hiervoor is MVC gewoon uitermate geschikt. Als je hierin al thuis bent, dan heb ik niets gezegd.

[ Voor 3% gewijzigd door Alarmnummer op 12-07-2003 13:58 ]

[wacco]

Pas je een beetje op met wat je allemaal uitvind?! Ik ben met deze methode een kunstmatige intelligentie aan het bouwen en wil wel de eerste zijn die het werkend heeft (die dus op deze manier z'n zinnen kan opbouwen en kan redeneren)
Al ben jij niet echt bezig met de algoritmes daarvoor, het lijkt wel verdomd veel op m'n theorie this far. Maar ik wil em dus op deze manier echt gaan laten zoeken naar verbanden en hem ook aanleren verbanden te zien. Alles moet bij mij zo dynamisch mogelijk worden (dus dat er ook foutcorrectie kan plaatsvinden)

[Alarmnummer]

wacco schreef op 12 July 2003 @ 19:39:
Pas je een beetje op met wat je allemaal uitvind?! Ik ben met deze methode een kunstmatige intelligentie aan het bouwen en wil wel de eerste zijn die het werkend heeft (die dus op deze manier z'n zinnen kan opbouwen en kan redeneren)

Zoals ik hierboven al vermeld heb lijkt dit enorm veel op semantische netwerken. Aangezien hier echt een enorme lading onderzoek naar gedaan is, zal hier ook wel een enorme lading software mee en voor zijn ontwikkeld.

Al ben jij niet echt bezig met de algoritmes daarvoor, het lijkt wel verdomd veel op m'n theorie this far. Maar ik wil em dus op deze manier echt gaan laten zoeken naar verbanden en hem ook aanleren verbanden te zien.

Als je veel met patterns gaat werken moet je even kijken naar het Rete algoritme.

Alles moet bij mij zo dynamisch mogelijk worden (dus dat er ook foutcorrectie kan plaatsvinden)

Wat bedoel je met foutcorrectie? Dat je een bepaald fact weer gaat terugnemen? Als je dat bedoelt moet je kijken naar default-logica en niet monotone logica.

[wacco]

Met foutcorrectie bedoel ik dat hij aannames maakt, maar dus ook waarschijnlijk foute aannames in z'n database krijgt. En dat door simpelweg tegen hem aan te blijven kletsen dat hij vanzelf ervan 'overtuigd' is dat wat in z'n database staat fout is. Ik wil daarvoor het volgende gaan gebruiken;
1) dat hij door zelf te redeneren met de informatie in z'n database (tijdens een gesprek) tegen 'conflicten' aanloopt hij dat als onderwerp van de discussie wilt gaan nemen (aansturen) om te kijken of dat nou eenmaal zo is, of dat er iets niet klopt
2) Tijdens een discussie niet direct te zeggen FALSE! maar proberen te kijken of hij danwel de persoon achter het toetsenbord het fout heeft. Hij lult je er dus uit als je onzin tikt en wordt overtuigd als je erg sterke argumenten weet aan te dragen, daarmee is er ook weer een grote kans dat ie tegen conflicten aanloopt (1 dus) of nieuwe informatie voorgeschoteld krijgt (weer wat nieuws leert).

Van je fouten leer je!
En eentje van mezelf; In spreekwoorden schuild meer kennis dan je op het eerste gezicht verwacht. Ben namelijk met het uitwerken van die theorieen nogal eens tegen een spreekwoord aangeknalt. (nog eentje? bijvoorbeeld; 'je ritme vinden' heeft een hoop te maken met melodie en idd ritme, wat weer verwijst naar waarom we dansen en muziek als 'prettig' ervaren, het is gewoon droogoefenen voor het echte werk, en over prettig ervaren hebben we zelfs eens een draadje gehad in w&l)

[Alarmnummer]

wacco schreef op 12 July 2003 @ 20:50:
Met foutcorrectie bedoel ik dat hij aannames maakt, maar dus ook waarschijnlijk foute aannames in z'n database krijgt. En dat door simpelweg tegen hem aan te blijven kletsen dat hij vanzelf ervan 'overtuigd' is dat wat in z'n database staat fout is. Ik wil daarvoor het volgende gaan gebruiken

Ik ben zelf een tijdje bezig geweest met niet monotone logica (althans met een soort 'nepvariant' ervan. Maar met niet monotone logica kan je dus werken met allerlei contradicties.

vb:

alle vogels kunnen vliegen
alle pinguings zijn vogels
pinguins vliegen niet

Als je nu de vraag gaat stellen of harry de pinguin kan vliegen dan kom je op ja en nee uit. Hij kan vliegen omdat hij een vogel is, maar hij kan niet vliegen omdat hij een pinguin is.

aardig boek:
Default Reasoning : Causal and Conditional Theories van Hector Geffner

[wacco]

Het idee van m'n algoritme is dus dat hij dan gewoon het gesprek aan gaat en zo meer informatie vergaard, dat pinguings (k*twoord btw) wel onder de categorie vogels valt, maar niet kunnen vliegen. Net zoals struisvogels. Het zijn gewoon uitzonderingen.
Zo zijn er ook een paar vage regels met vissen != zoogdier maar walvissen/dolfijnen weer wel (oid... ben geen oceanoloog)