One of my sabbatical projects is MegaHAL.10, an entirely new version of the mildly popular chatterbot that I wrote and put online fifteen years ago. I’ve been writing it in Google’s Go programming language, and I recently started getting some exciting results.
MegaHAL.10 generates sentences using a second-order Markov model. That means they tend to be random walks; you start out with a blank slate, and you never know where you’ll end up. The only guarantee is that any sequence of three symbols will have previously been observed by the model.
These kinds of random generations may be quite amusing, but they’re not too useful when you’re trying to simulate a conversation, which requires that each generation adheres to the current context. What would be much better is if you could force the model to generate a sentence that has the desired Markovian properties, but which contains pre-determined keywords.
With the original MegaHAL I did this by starting at the keyword and using two Markov models to generate the sentence, one proceeding from the keywords forwards to the end of the sentence, and the other going in the opposite direction. That was a bit of a hack, and could only guarantee that the sentence contains a single keyword.
For MegaHAL.10 I’ve been experimenting with other strategies, including a Fractal slot-filling model and a family of Markov models, each of which generates towards a specified target symbol. Both of these took a template sentence as input, which specified the keywords and their order, and both suffered from several problems, such as the fact that it may be impossible to complete the template, and that the local grammaticalness condition may need to be violated to make the keywords join up.
Recently I had a brainwave: what if we generated with the standard Markov model, but weighted the generations based on another model that specified the distance to the desired keyword. We could then generate a directed random walk, similar to an A* pathfinding algorithm. We may not be able to guarantee that the resulting sentence contains the keywords we want, but chances are it will contain at least a few.
Some bugs still need to be ironed out (and some wrinkles squished), but my tests so far indicate that this method may be the missing link. I trained MegaHAL.10 on the entire collection of Sherlock Holmes stories, and then I asked it to generate a random sentence, specifying these ten keywords in advance:
adventure foot wild scandal street twenty death finger villain rock
This is the sentence I got (I’ve highlighted the keywords):
“Twenty had changed their position, and the street by the death of the adventure of the ROCK OF GIBRALTAR. From the dead scientist. His wild flight to escape from her finger into the garden. Perhaps the villain was able to take counsel how far we can hardly put my foot over the case of this question. I saw that a very remarkable man, that was this William doing there is to avoid scandal.”
To me that’s completely amazing. “Give me a sentence containing these ten words”, I said, “making sure that each sequence of three words in your sentence appears somewhere in the collected Sherlock Holmes stories.” And MegaHAL.10 delivered.
Just to prove it wasn’t a fluke, here are a few more, using the same keywords:
“Twenty or thirty, I have seen death in the street by a strong family resemblance about misdeeds, and if you know now and so I dipped my finger on the ledge above the other hand had dropped his mask of his foot than might at any time before he was wild, wayward, and to our young companion looked at the young diplomatist’s window. There was this dark business which had been in the young lady.”
“Villain! Scoundrel!” cried the old quarters. At the foot of the death of the street. Holmes looked eagerly round for it was twenty before her in the dead scientist. His wild eyes, stained cheeks and He put a triumphant conclusion.
“Death from some little distance down the street by a very simple chain: 1. You had a wild thrill as this was at the foot of the rock on each side of the adventure as a great scandal threatened to raise a scandal may well be cleared along those lines. Mr. Douglas has spent a large coil from under the three strips. No finger impressions–no! Well, he is not here as I was at the other night.”
I’m planning to spend next week improving this algorithm, fixing various bugs, and optimising for memory and speed. I’ll then set to work creating a web version of MegaHAL.10, which will hopefully be going live before the end of the month.
Continuing work on this, fixing bugs and improving performance. In all of the Sherlock Holmes stories, the word “thong” appears twice, and the word “telephone” appears twice, and they never appear in the same sentence together. But we can ask MegaHAL.10 to generate a sentence that contains them both…
“That is precisely what do you conceal yourselves behind those. Then when you see the grim and gray eyes, while she is a huge ledger upon the road, and telephone to make a careful examination of the others, because the thong is commonly passed between them and that she was very happy to advance, but began to amuse you in a most strange and dramatic character, but the facts in my family.”
Noice.
Pingback: The Magic Pantry › TTM: Time To MegaHAL
I’ve always looked at MegaHal with a wild interest, because it was so simple, fast effective and quick! Probably Markov models are not true AI (but also neural nets, genetic algos or reinforcement learning are not really AI); nonetheless they prove to work and be able to learn without having to write specific rules, such as in the AIML chat bots.
I’ve experimented with an old MegaHal code from an old MegaHal site; I suppose Lloyd Kranzky == Jason Hutchens but I’m not sure because I could not find a clear connections between links on MegaHal page and this site…
However, I (too!) have modified an old MegaHal code to test some new functions, etc. I was not interest in IRC and so on and I worked with the original C code released to experiment things like changing Markov Model order, changing the way entropy is computed and so on.
To summarize, I’ve changed lot of things to allow:
- Use any text file (for instance any book such as the holy bible) with any formatting as TRN file, striping/replacing chars and automatically split sentences. For instance I’m trying a huge TRN file with contains the holy bible plus other books (it’s 23 Mbytes, 5 times larger than the entire holy bible…)
- Ability to learn from both TRN and BRN files: allows to learn and incrementally increase brain with different Train files
- Some Uppercase/Lowercase detection and punctuations add/removal to improve formatting; spaces are not considered as words and are automatically added to output.
– Add new parameters to change model order, word hits, entropy computation, etc (from command or from a parameters file). They are mostly experimental…
- Remove the original limitation of MegaHal of 65536 words: now the limit is billions words, branches (but I ensure it will never be reached, while I reached the old limit in my tests). I’ve especially found a very annoying bug that caused memory reallocation failure over 512 Mbytes (in windows, at least): now it’s solved and I’ve checked it can be effectively compiled also for Win64 and allocate more than 2G RAM if required.
- Ability to write some additional information for debug (debug level) to log file.
The input files are not changed, while the output (DIC and BRN) are changed; but obviously only BRN is important. The code compiles and works in Windows with both mingw32-gcc (also the 64 bit version) and VisualStudio; I’ve checked it with warning all pedantic options and with the good CppCheck opensource tool.
If you want to peek into the mess I’ve done, drop me a line. Not such a good code but maybe new ideas can come out for megaHal 10…
Great work, and sorry you had to struggle with all of that old horrible code :)
Im looking forward for MegaHAL.10. You can call me a retard but I only came to know about this piece of software one day ago and I am trying to do something cool with it.
Mate, your algorithm can’t make machines to think, but the way you taught the software enables us to do something.
You created rules for MegaHAL to learn and rules of how he would reply. Knowing that rules and speaking in a language MegaHAL can manage, you could even teach math to it. Real math.
I loved it, it is awesome. I am just having problems with the .swp file, because in here it didn’t create it automatically and the one i handcrafted made the program crash – fragmentation issues…
I used a tab to separate the two words to be swapped in each line but dunno if i did it right. No clues in the web and no clues in your help file.
If you can spare a couple of secs to help someone whos fan of your program – people call it a game but I had an Anonymous member who warned me: do what you want but keep your bot out of the internet…. Your program can even drive people to hysteria, hahaha
You rock.
Congrats for the nice ideas and keep up the good job
From your friend and fan
From Brazil
Emir Starshyne