Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

benhoyt.com

Post reply on HN
Print view View original

71–77 of 77 posts

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

#71

Post by [deleted] »

microtonal wrote: post #45
YeGoblynQueenne wrote: post #40

Earlier quoted context omitted.

The output is "word salad" because the probabilities of the model are uniform, albeit implicitly- eyballing the python, it selects the next n-gram uniformly at random. A better n-gram model would calculate the probability of an n-gram following another n-gram according to their frequency in the training corpus. With a larger corpus and better training techniques (some smoothing for one thing) you'd get much more cohe…

The output is "word salad" because the probabilities of the model are uniform, albeit implicitly- eyballing the python, it selects the next n-gram uniformly at random. From a quick look, it doesn't seem to sample uniformly. w3 is added to a list for the context w1, w2, not a set. So, say word A occurs twice as often in a particular context as B, it will be in the list twice as often. So, even though a uniform choice…

[deleted]

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

#72

Post by YeGoblynQueenne »

microtonal wrote: post #45
YeGoblynQueenne wrote: post #40

Earlier quoted context omitted.

The output is "word salad" because the probabilities of the model are uniform, albeit implicitly- eyballing the python, it selects the next n-gram uniformly at random. A better n-gram model would calculate the probability of an n-gram following another n-gram according to their frequency in the training corpus. With a larger corpus and better training techniques (some smoothing for one thing) you'd get much more cohe…

The output is "word salad" because the probabilities of the model are uniform, albeit implicitly- eyballing the python, it selects the next n-gram uniformly at random. From a quick look, it doesn't seem to sample uniformly. w3 is added to a list for the context w1, w2, not a set. So, say word A occurs twice as often in a particular context as B, it will be in the list twice as often. So, even though a uniform choice…

>> From a quick look, it doesn't seem to sample uniformly. w3 is added to a list for the context w1, w2, not a set. So, say word A occurs twice as often in a particular context as B, it will be in the list twice as often. So, even though a uniform choice function is used, the probability of A getting samples is twice as high.

Yeah, you're right. I had to squint a bit but it's like you say, the code is sampling uniformly from a list with possible multiples. Don't make me squint man! I'll get wrinkles :P

Squinting a bit more, that's not the way I know how to build n-grams. If you gave me the string (the cat sat on the bat) I'd give you bi-grams ($s the), (the cat), (cat sat), (sat on), (on the), (the bat), (bat $e). That way, after the first bigram, the next word only depends on the second word in the last bigram, because every bigram (w1 w2) is only ever followed by a bigram (w2 w3). So you're sliding a window of length 2 over the corpus, guided by the probability of the next word.

>> You get a word salad because a trigram model has to little context to do anything else. This is a well-known issue with Markov and hidden Markov models.

Yes, it's the Markov property that makes for word salad, ultimately, but you get less salad-y output if you can calculate better probabilities, and if you do it in the way I say above. And you can always build a string by selecting the next bigram that maximises the probability of the entire string. That's how I've always done it. I guess that's not Markovian any more but gives you reasonable output especially for small-ish corpora with not huge variance.

>> (Fun fact: some hidden Markov model taggers switch to a different trigram distribution for V2 languages after seeing the finite verb, otherwise they often fail catastrophically in the verb cluster due to the limited context.)

Thanks, I didn't know that.

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

#73

Post by codethief »

bradrn wrote: post #11

For a more thorough exploration of Markov text generation, I like this article: https://zompist.com/markov.html

I 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!

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

#74

Post by YeGoblynQueenne »

shawnz wrote: post #42
YeGoblynQueenne wrote: post #40

Earlier quoted context omitted.

The output is "word salad" because the probabilities of the model are uniform, albeit implicitly- eyballing the python, it selects the next n-gram uniformly at random. A better n-gram model would calculate the probability of an n-gram following another n-gram according to their frequency in the training corpus. With a larger corpus and better training techniques (some smoothing for one thing) you'd get much more cohe…

> A better n-gram model would calculate the probability of an n-gram following another n-gram according to their frequency in the training corpus. With a larger corpus and better training techniques (some smoothing for one thing) you'd get much more coherent output. I don't understand what you mean here, isn't that exactly what an n-gram model is already designed to achieve where n > 1? Since this is a 2-gram model i…

That's right, but a bi-gram model is just a big table of bi-grams and their probabilities (which are really their frequencies in a corpus normalised over the number of all bigrams in the corpus). You can use those probabilities in two ways: to calculate the probability of a string, by taking the bigrams in the string and multiplying their probabilities together; or by starting with some bigram (e.g. a search term entered by a user) and then selecting the next bigram according to its probability (i.e. its frequency in the corpus), or according to the probability of the entire string so-far (which you get by multiplying the probabilities of the bigrams so far); and repeat until you reach some maximum string-length.

So you're right that my comment is a bit confusing: I refer to the way you sample from a bi-gram model, so as to generate a string. Sorry!

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

#75

Post by java_beyb »

tahnyall wrote: post #39
echelon wrote: post #33

Earlier quoted context omitted.

Which languages are harder for LLMs? Is there any writeup or analysis of this?

If I had to guess, from my time working with ASR (Advanced Speech Recognition) languages and its difficulty with the Indian (country of) accent; I'd guess Indian languages.

what's advanced speech recognition?

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

#77

Post by chuckadams »

nurettin wrote: post #64
chuckadams wrote: post #57

Earlier quoted context omitted.

I recall one site way back that used a Markov chain generator to mash up Karl Marx and Ayn Rand. Was fairly plausible reading, actually.

I imagine that's like mixing different kinds of salad.

It definitely gives you some whiplash, but most of the time it's just righteous ranting about ... whatever. The whole site was a trove of comedy, featuring quizzes like "Porn Star or My Little Pony?". I couldn't remember its name until I started typing this reply: lileks.com.
Post reply on HN