Using a Markov chain to generate readable nonsense with 20 lines of Python

See also Mark V Shaney <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Mark_V._Shaney" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Mark_V._Shaney</a><p>This was a class assignment in college, we had a lot of fun with it, and one of my classmates, the brilliant Alyosha Efros, decided to apply the exact same technique to images instead of text. It turned into a paper that revitalized texture synthesis in the Siggraph community. The most interesting part about it (in my opinion) is that he ran it on images of text, and it produces images of readable text nonsense! With the right window size, perhaps there’s a nonzero possibility of being able to produce the same text either way. This always struck me as very meta and makes me wonder if there are ways we could go in reverse with image processing (or other types of data); if there’s a latent underlying representation for the information contained in image content that is much smaller and more efficient to work with. Neural networks might or might not be providing evidence.<p><a href="https:&#x2F;&#x2F;people.eecs.berkeley.edu&#x2F;~efros&#x2F;research&#x2F;EfrosLeung.html" rel="nofollow">https:&#x2F;&#x2F;people.eecs.berkeley.edu&#x2F;~efros&#x2F;research&#x2F;EfrosLeung....</a>

As many know and point out, this idea is now very old (40+ years?). The big problem is that it creates &quot;word salad&quot; [0]. In the generative art and procgen community, the term &quot;10,000 bowls of oatmeal&quot; problem has been used [1].<p>Taking a step back, this is a perennial problem, even with AI old and new. I&#x27;ve heard that the early (good) chess bots, after Deep Blue, had a problem of only being locally context sensitive and being easily fooled by longer range attack planning. We even see it, to a certain extent, in LLMs where they forget or contradict themselves with what was just said. I have no doubt that LLMs will just keep getting better but, as a snapshot of right now, you can see shades of this &quot;word salad&quot; problem, just a few steps removed to become a &quot;logic salad&quot; problem.<p>[0] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Word_salad" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Word_salad</a><p>[1] <a href="https:&#x2F;&#x2F;galaxykate0.tumblr.com&#x2F;post&#x2F;139774965871&#x2F;so-you-want-to-build-a-generator" rel="nofollow">https:&#x2F;&#x2F;galaxykate0.tumblr.com&#x2F;post&#x2F;139774965871&#x2F;so-you-want...</a>

&gt;&gt; <i>Making the prefix shorter tends to produce less coherent prose; making it longer tends to reproduce the input text verbatim. For English text, using two words to select a third is a good compromise; it seems to recreate the flavor of the input while adding its own whimsical touch.</i><p>Next word prediction; vector databases:<p>Vector database: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Vector_database" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Vector_database</a><p><a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=37812219">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=37812219</a>

I was doing a similar experiment recently to generate random names that sound like names from a specific language.<p>I was breaking the list of names apart into 3 and 2 letter parts, marking which fragments are from the start, middle and end.<p>To generate the words I started from a random one from the start fragments, then continued with a random one from the middle fragments that starts with the latter that the previous one ended with, and similarly ended it with one from the end fragments. Some examples:<p>Spanish Names:<p>Armusa Vantara Modria<p>German Names:<p>Ven Marwar, Ger Naroff, Vort Kraldent, Görn Henter, Urg Wicher, Wan Ehranus, Eck Hayazin, Wert Biewin, Rein Relberid,<p>Catalan:<p>Pallava Ecorus Sangana Ginavari Telamita Exorxió<p>Hungarian cities:<p>Jószög Alszeny Hernafő Garnáza Ragytúr Hidácska Mezécs<p>(edit formatting)

We had a bot that would randomly say things in our IRC channel 15 years ago that worked like this. You could also mention it to prompt it to reply.<p>Every message was added to it&#x27;s knowledge base and it would say random but hilarious stuff made up from all the nonsense we used to talk about.<p>Good times.

When I read about Markov Chains and hallucination of LLMs, the first thing that comes to my mind is Reggie watts [0] performances, also remind me i used to do the same thing when i was bored in the classroom, but on my paper notebooks,just nonsense that seems plausible, it was kind of entering in a meditative state, it felt good. when i discovered watts i thought to my self, &#x27;what?! I cloud have done that for a living?&#x27;.<p>[0] <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=UXyHf_SpUUI" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=UXyHf_SpUUI</a>

For a more thorough exploration of Markov text generation, I like this article: <a href="https:&#x2F;&#x2F;zompist.com&#x2F;markov.html" rel="nofollow">https:&#x2F;&#x2F;zompist.com&#x2F;markov.html</a>

I did this once with Perl and a book called Eu by the Brazilian poet Augusto dos Anjos. It spat out verses and I joined a few to create this little thing:<p>Andam monstros sombrios pela escuridão dos remorsos<p>Pairando acima dos transeuntes<p>Maldito seja o gênero humano<p>Prostituído talvez em desintegrações maravilhosas<p>Source code: <a href="https:&#x2F;&#x2F;alquerubim.blogspot.com&#x2F;2018&#x2F;01&#x2F;gerador-de-augusto-dos-anjos.html" rel="nofollow">https:&#x2F;&#x2F;alquerubim.blogspot.com&#x2F;2018&#x2F;01&#x2F;gerador-de-augusto-d...</a>

I implemented one in R this year and feed it with religious content. Then I text to speech output and post it on youtube. <a href="https:&#x2F;&#x2F;youtube.com&#x2F;playlist?list=PLEB5tND7siCOe7ySYjVOBwR2v9W2efu-r&amp;si=jEkwL39jYBt2ldeZ" rel="nofollow">https:&#x2F;&#x2F;youtube.com&#x2F;playlist?list=PLEB5tND7siCOe7ySYjVOBwR2v...</a>

I created a little program in C++&#x2F;Qt for using Markov chains to re-write text. But it works on character sequences, rather than words. There are examples and binaries for Windows and Mac:<p><a href="https:&#x2F;&#x2F;successfulsoftware.net&#x2F;2019&#x2F;04&#x2F;02&#x2F;bloviate&#x2F;" rel="nofollow">https:&#x2F;&#x2F;successfulsoftware.net&#x2F;2019&#x2F;04&#x2F;02&#x2F;bloviate&#x2F;</a>

This is exactly the approach I used back in the late 80s; I published a Markov chain text generator on comp.sources.games that digested Usenet posts, built tables and used the previous two words to generate the next word. It was mildly amusing at the time. Someone resurrected it and put on GitHub, which I&#x27;m fine with.

this is old tech - but it had me thinking. Markov chains are picking the next token from a random set and they are giving approximately all possible tokens (from the training set) an equal probability. What if it weighted the probability - say using the inverse vector distance or cosine similarity of the neighbors as a proxy for probability, where the vector embedding came from word2vec...how close would the performance be to a transformer model or even something like lstm rnns ? (I suppose I&#x27;m cheating a bit using word2vec here. I might as well just say I&#x27;m using the attention mechanism...)

We uh as a group project did markov chains with some custom algorithmic adjustments, scraped reddit via api, and academic torrent (this data required a lot of cleaning and was orders of magnitude bigger, ran separately), to simulate posts and comments. In same group project we also implemented Variable Length Markov Chain, tree-based custom context-length, although a team member did the matrix based implementation custom context-length as well through some matrix magic.

I remember as a school boy I heard about Markov Chains, and played a bit with them. Instead of building big n-gram tables, I found a simpler way. Start with one n-gram, then scan the source text until you find the next occurrence of it, and take the next letter after it. Output it, and append it to your n-gram, dropping its first letter, and repeat until you have sufficient amount of nonsense text.

I wonder how this would behave if trained on 1 trillion words like the LLMs.<p>Also, Is training a Markov cheaper that training neural nets? It would be a great way to cut AI costs if they could be made as effective as neural nets.<p>There is also an interesting post by Orange duck. [0]<p>[0] <a href="https:&#x2F;&#x2F;theorangeduck.com&#x2F;page&#x2F;17-line-markov-chain" rel="nofollow">https:&#x2F;&#x2F;theorangeduck.com&#x2F;page&#x2F;17-line-markov-chain</a>

The first edition of Programming Perl had a script that did this called travesty. You can download it from <a href="https:&#x2F;&#x2F;resources.oreilly.com&#x2F;examples&#x2F;9780937175644" rel="nofollow">https:&#x2F;&#x2F;resources.oreilly.com&#x2F;examples&#x2F;9780937175644</a><p>When I was learning Perl in the &#x27;90s, I remember having a lot of fun running this on different manual pages.

<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;MegaHAL" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;MegaHAL</a>

I had an idea.<p>What if you trained a markov chain and got weights of every pair or sequence of pairs for a certain length.<p>Could you also do rotations with this information in vector space? With multiple points of freedom?<p>What if you could do inverse kinematics with markov chains?<p>Like robot planning for a goal?

<a href="https:&#x2F;&#x2F;archive.org&#x2F;details&#x2F;ComputerRecreationsMarkovChainer" rel="nofollow">https:&#x2F;&#x2F;archive.org&#x2F;details&#x2F;ComputerRecreationsMarkovChainer</a>

One of my first personal projects was making 2 discord bots that would have an infinite “conversation” using Markov chains. Feeding them text from Reddit produced some hilarious results.

&gt; using Lewis Carroll’s Alice in Wonderland as input. The book is more or less nonsense to begin with,<p>Has he ever read Alice?

Plausible nonsense of sufficient complexity and consistency as to seem real. It&#x27;s trivial to generate.<p>It casts every cherished truth into doubt.

Never forget a mate implemented a markov chainer in Lambda MOO, and named it “Cute Ickle Baby”. Left it in the Living Room, listening to what people said, and randomly saying things. Sometimes it said the funniest shit and had us all pissing ourselves laughing.

This works pretty well for languages that use a space as word separator. Now do this for those languages that don’t and have no clear and easy rules for word separation.

This was posted 50 days ago - how does it reach first page again? <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;from?site=benhoyt.com">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;from?site=benhoyt.com</a>