8 ms·
Using a Markov chain to generate readable nonsense with 20 lines of Python
- Pompidou 3y agoI implemented one in R this year and feed it with religious content. Then I text to speech output and post it on youtube. https://youtube.com/playlist?list=PLEB5tND7siCOe7ySYjVOBwR2v9W2efu-r&si=jEkwL39jYBt2ldeZ https://youtube.com/playlist?list=PLEB5tND7siCOe7ySYjVOBwR2v...
- westurner 3y ago>> 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. Next word prediction; vector databases: Vector database: https://en.wikipedia.org/wiki/Vector_database https://en.wikipedia.org/wiki/Vector_database https://news.ycombinator.com/item?id=37812219 https://news.ycombinator.com/item?id=37812219
- raister 3y agoThis was posted 50 days ago - how does it reach first page again? https://news.ycombinator.com/from?site=benhoyt.com https://news.ycombinator.com/from?site=benhoyt.com
- deleted 3y ago[deleted]
- j4yav 3y agoBy people being interested and upvoting it. Not everyone reads the home page all day every day.
- lowbloodsugar 3y agoNever 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.
- not2b 3y agoThis 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'm fine with.
- 082349872349872 3y agoMark V. Shaney?
- not2b 3y agoNo, it was called markov3. Mark V. Shaney was similar but from Bell labs. See https://github.com/cheako/markov3 https://github.com/cheako/markov3 (not coded very well but I got better).
- bugbuddy 3y agoThis 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.
- abetusk 3y agoAs many know and point out, this idea is now very old (40+ years?). The big problem is that it creates "word salad" [0]. In the generative art and procgen community, the term "10,000 bowls of oatmeal" problem has been used [1]. Taking a step back, this is a perennial problem, even with AI old and new. I'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 "word salad" problem, just a few steps removed to become a "logic salad" problem. [0] https://en.wikipedia.org/wiki/Word_salad https://en.wikipedia.org/wiki/Word_salad [1] https://galaxykate0.tumblr.com/post/139774965871/so-you-want-to-build-a-generator https://galaxykate0.tumblr.com/post/139774965871/so-you-want...
- max_ 3y agoI wonder how this would behave if trained on 1 trillion words like the LLMs. 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. There is also an interesting post by Orange duck. [0] [0] https://theorangeduck.com/page/17-line-markov-chain https://theorangeduck.com/page/17-line-markov-chain
- stabbles 3y agoYeah, a century old approach using frequency tables where the next word is generated based just on the previous two words is highly competitive with contemporary neural nets. To produce coherent sentences, do you ever need to remember more than the last two words you said? I doubt it.
- CamperBob2 3y agoNow ask it to render a deepfake of Noam Chomsky waving his hands saying "Nothing to see here."
- gattilorenz 3y agoThe only way to make it sound less like a word salad is to increase the n-gram length (e.g. use the last 10 words to predict the next), but at that point it starts repeating the corpus. I guess technically you can train on a huge corpus like those of NNs to mitigate that, but you’ll end up with more refined word salads then (edit: refined as in “locally coherent but globally still a word salad”)
- sgt101 3y agowell - the lawyers from the NYT called, and they disagree...
- gattilorenz 3y agoI didn’t get the call, so it’s not clear what they disagree on :) I doubt the have anything to say about Markov chains. We’re talking about technical possibilities, not legality of training corpora
- bradrn 3y agoFor a more thorough exploration of Markov text generation, I like this article: https://zompist.com/markov.html https://zompist.com/markov.html
- codethief 3y agoI wouldn't call it "more thorough", as it doesn't do much more than the OP, but it's certainly a nice read. Thanks for the link!
- alejoar 3y agoWe 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. Every message was added to it's knowledge base and it would say random but hilarious stuff made up from all the nonsense we used to talk about. Good times.
- duke_sam 3y agoFor a hack day project someone took our IRC logs to do something similar for employees who had left (one bot per engineer, small company so a handful of bots). This made for a great afternoon until the bots started talking to each other and then started triggering the simple command the ops bot would accept. It quickly got shut down.
- Lukkaroinen 3y agoI wrote one bot like this. It was fun to play around.
- bhattid 3y agoOut of curiosity, was the bot based on the bMotion repository? https://github.com/jamesoff/bmotion https://github.com/jamesoff/bmotion I remember a friend of mine settings up an IRC bot (named Zeta) like that for his sheet music forum many years ago. She was involved in a lot of hilarity - probably my favorite antics were when she randomly decided to courtmatial someone. Good times indeed! :)
- seabass-labrax 3y ago> she randomly decided to courtmatial someone Well, you can't stave off fate - you've got to face the music eventually.
- deleted 3y ago[deleted]
- ZetaH 3y agoI was doing a similar experiment recently to generate random names that sound like names from a specific language. I was breaking the list of names apart into 3 and 2 letter parts, marking which fragments are from the start, middle and end. 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: Spanish Names: Armusa Vantara Modria German Names: Ven Marwar, Ger Naroff, Vort Kraldent, Görn Henter, Urg Wicher, Wan Ehranus, Eck Hayazin, Wert Biewin, Rein Relberid, Catalan: Pallava Ecorus Sangana Ginavari Telamita Exorxió Hungarian cities: Jószög Alszeny Hernafő Garnáza Ragytúr Hidácska Mezécs (edit formatting)
- jokoon 3y agoI remember finding a set of english names generated with a markov chain, I wish I know how to make it, they sounded good.
- pavel_lishin 3y ago> I wish I know how to make it You can learn! I know it's easy to say something is easy to a beginner, but figuring out Markov chains is truly something you can get the basics of over a weekend if you've ever written any software at all.
- weare138 3y agohttps://en.wikipedia.org/wiki/MegaHAL https://en.wikipedia.org/wiki/MegaHAL
- forinti 3y agoI 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: Andam monstros sombrios pela escuridão dos remorsos Pairando acima dos transeuntes Maldito seja o gênero humano Prostituído talvez em desintegrações maravilhosas Source code: https://alquerubim.blogspot.com/2018/01/gerador-de-augusto-dos-anjos.html https://alquerubim.blogspot.com/2018/01/gerador-de-augusto-d...
- Frummy 3y agoWe 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.
- Frummy 3y agoGenuinely curious to hear what’s wrong with what I thought a cool, curious fun time implementing markov chains. We learned a lot about statistics and linear algebra, matrix diagonalisation and exponentiation, I find it very relevant and can answer questions if you don’t understand.
- mebassett 3y agothis 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'm cheating a bit using word2vec here. I might as well just say I'm using the attention mechanism...)
- pona-a 3y agoThat sounds interesting, but still fails to capture long-range dependencies. If I understand correctly, what you're proposing is to replace co-occurrence frequency with word2vec cosine similarity. I suppose it may help improve overall performance, you're still just blindly predicting the next word based on the previous one like a first order Markov chain would. For example, it won't ever fit "2 plus 2 equals 4," because right when we get to equals, we discard all the previous words. Perhaps if we could get the embedding model to consider the full sentence and then produce a set of probability-scored next token predictions it may work, but now we've just reinvented a transformer.
- csmpltn 3y ago> "I suppose it may help improve overall performance, you're still just blindly predicting the next word based on the previous one like a first order Markov chain would." Instead of only taking in the last "token" as context to the function that generates the next token - take the last 15 tokens (ie. the last 2-3 sentences), and predict based on that. And that's your "attention" mechanism.
- terminous 3y agoYeah, that's just attention with extra steps
- kwhitefoot 3y ago> using Lewis Carroll’s Alice in Wonderland as input. The book is more or less nonsense to begin with, Has he ever read Alice?
- ltr_ 3y agoWhen 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, 'what?! I cloud have done that for a living?'. [0] https://www.youtube.com/watch?v=UXyHf_SpUUI https://www.youtube.com/watch?v=UXyHf_SpUUI
- samsquire 3y agoI had an idea. What if you trained a markov chain and got weights of every pair or sequence of pairs for a certain length. Could you also do rotations with this information in vector space? With multiple points of freedom? What if you could do inverse kinematics with markov chains? Like robot planning for a goal?
- dahart 3y agoSee also Mark V Shaney https://en.wikipedia.org/wiki/Mark_V._Shaney https://en.wikipedia.org/wiki/Mark_V._Shaney 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. https://people.eecs.berkeley.edu/~efros/research/EfrosLeung.html https://people.eecs.berkeley.edu/~efros/research/EfrosLeung....
- fluoridation 3y agoThat's amazing! It's a literal uncrop. I'll have to look into this later.
- AndruLuvisi 3y agoThe first edition of Programming Perl had a script that did this called travesty. You can download it from https://resources.oreilly.com/examples/9780937175644 https://resources.oreilly.com/examples/9780937175644 When I was learning Perl in the '90s, I remember having a lot of fun running this on different manual pages.
- chuckadams 3y agoIt’s also built into emacs: I believe it’s called disassociated-press
- heikkilevanto 3y agoI 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.
- mdberkey 3y agoOne 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.
- hermitcrab 3y agoI created a little program in C++/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: https://successfulsoftware.net/2019/04/02/bloviate/ https://successfulsoftware.net/2019/04/02/bloviate/
- qarl 3y agohttps://archive.org/details/ComputerRecreationsMarkovChainer https://archive.org/details/ComputerRecreationsMarkovChainer
- swayvil 3y agoPlausible nonsense of sufficient complexity and consistency as to seem real. It's trivial to generate. It casts every cherished truth into doubt.