[Alg] hoe een "intelligente" gesprekssimulator maken?

[muba]

Ik heb net deze pagina (vooral hoofdstuk 4 - over hoe MegaHAL werkt) gelezen en er reist een grote vraag bij me op.

Op zich snap heel hoofdstuk vier, maar... als dat markov model er een is van de vierde orde, hoe kan het dan dat MegaHAL weet te reageren op zoiets als "yes"? Want dat zijn hooguit drie symbolen - {begin van zin, "yes", eind van zin}. Drie symbolen, en dan moet ik begin-van-zin en eind-van-zin er zelf bij fantaseren, want die pagina rept daar verder niet over.

Dus lijkt het mij onmogelijk om te voorspellen wat voor symbool er na een gegeven reeks van vier symbolen er komt, simpelweg omdat er maar drie symbolen gegeven zijn. Er is gewoon niet genoeg data om mee te werken.

En als je een paar voorbeeldgesprekken ziet (zie ook hier), dan zie je dat MegaHAL af en toe een enkel woord uit de input kiest, dat als keyword gebruikt en daar vervolgens een zin mee maakt.

Maar hoe kan het dat hij vanuit 1 woord, 1 symbool, een hele zin maakt? Want het zijn 4th-order markov modellen, dus hij moet minstens twee woorden ofwel vier symbolen hebben...

Ik kom er niet uit...

Edit: 700e bericht, woohoo

[ Voor 1% gewijzigd door muba op 20-11-2006 03:40 . Reden: 700e bericht! ]

[LauPro]

Volgens mij werkt het iets anders. Op basis van het ene keyword maakt hij honderden zinnen. En daarna wordt door het 4th-order Markov model de meeste aannemelijke uitgekozen. Ik weet niet precies hoe MegaHAL in elkaar zit maar als je aan een willekeurig persoon "yes?" zou vragen dan zal deze waarschijnlijk vrij bijdehand reageren want het is ook (als initiatie van een gesprek) een vrij bijdehandte vraag imo.

[muba]

Maar hoe gaat dat in zijn werk dan, die honderden zinnen maken?

Ik bedoel, ik begrijp hoe je met behulp van een markov model en een aantal beginsymbolen een hele reeks (in dit geval een hele zin) kan maken, maar er is daar volgens mij te weinig input voor.

Dus op welke manier worden die zinnen dan bepaald, in de eerste instantie?
Het enige wat ik kan bedenken is dat er ook nog 1st order markov chains zijn ofzo, maar daar rept die pagina niet over.

[DroogKloot]

Heel simpel, de conditionele waarschijnlijkheid van een woord W_n gegeven k voorgaande woorden is volgens de regel van Bayes gelijk aan:

P(W_n | (W_{n - 1}, W_{n - 2}, ..., W_{n - k})) = P(W_{n - k}, ..., W_{n - 2}, W_{n - 1}, W_n) / P((W_{n - k}, ..., W_{n - 2}, W_{n - 1})

Als je nu niet beschikt over (W_{n - 1}, W_{n - 2}, ..., W_{n - k}), bijvoorbeeld omdat W_n gewoon het eerste woord van de zin is, dan zul je (aangezien je Markov-model alleen is getraind op tri- en quadri-grammen, het zogenaamde out-of-vocabulary probleem) iets moeten bedenken om toch die kans te berekenen, en daar zijn allerlei meer en minder betrouwbare technieken voor. Zoek bv. op Good-Turing smoothing, dat is een vrij rechtlijnige methode om nul-waarschijnlijkheden in je model te voorkomen die redelijk goed werkt voor niet al te kleine ngram-sets.

[muba]

Hmm... ik had niet gedacht dat het zo'n ingewikkeld gedoe zou worden Maar toch bedankt