8 ms·

Markov chains are the original language models

allthatineed 1y ago
I remember playing with megahal eggdrop bots. This was one of my first forays into modifying c code, trying to figure out why 350mb seemed to be the biggest brain size (32 bit memory limits and requiring a contiguous block for the entire brain). I miss the innocence of those days. Just being a teen, tinkering with things i didn't understand.
- foobarian 1y ago
  I'm old now, but thanks to LLMs I can now again tinker with things I don't understand :-)
  - codr7 1y ago
    Are you though? Or is the LLM the target of your tinkering and lack of understanding? Honest question.
  - jcynix 1y ago
    The nice thing about LLMs is that they can explain stuff so you can learn to understand. And they are very patient. For example I'm currently relearning various ImageMagick details and thanks to their explanations now understand things that I cut/copy/pasted a long time ago without always understanding why things worked the way they did.
- vunderba 1y ago
  I remember reading the source of the original MegaHAL program when I was younger - one of the tricks that made it stand out (particularly in the Loebner competitions [1]) was that it used both a backwards and forwards Markov chain to generate responses. [1] https://en.wikipedia.org/wiki/Loebner_Prize https://en.wikipedia.org/wiki/Loebner_Prize
- anthk 1y ago
  Hailo it's still alive under CPAN.
glouwbug 1y ago
The Practice of Programming by Kernighan and Pike had a really elegant Markov: https://github.com/Heatwave/the-practice-of-programming/blob/master/3.3.markov-chain.c https://github.com/Heatwave/the-practice-of-programming/blob...
- jcynix 1y ago
  And Mark V. Shaney was designed by Rob Pike and posted on Usenet, but that happened a long time ago: https://en.wikipedia.org/wiki/Mark_V._Shaney https://en.wikipedia.org/wiki/Mark_V._Shaney
- anthk 1y ago
  This one too: http://c9x.me/cbits/ http://c9x.me/cbits/
- y7r4m 1y ago
  About a decade ago I somehow came across Genudi[0], a markov chain based "AI", and had quite a bit of fun with it. The creator has a blog that makes for an interesting reading session. 0: https://www.genudi.com/about https://www.genudi.com/about
chankstein38 1y ago
I once, probably 4-6 years ago, used exports from Slack conversations to train a Markov Chain to recreate a user that was around a lot and then left for a while. I wrote the whole thing in python and wasn't overly well-versed in the statistics and math side but understood the principle. I made a bot and had it join the Slack instance that I administrate and it would interact if you tagged it or if you said things that person always responded to (hardcoded). Well, the responses were pretty messed up and not accurate but we all got a good chuckle watching the bot sometimes actually sound like the person amidst a mass of random other things that person always said jumbled together :D
- vunderba 1y ago
  I had a similar program designed as my "AWAY" bot that was trained on transcripts of my previous conversations and connected to Skype. At the time (2009) I was living in Taiwan so I would activate it when I went to bed to chat with my friends back in the States given the ~12 hour time difference. Reading back some of the transcripts made it sound like I was on the verge of a psychotic break though.
- emmelaich 1y ago
  I'm sure that Gilfoyle's prank in Silicon Valley had its basis in a true story, like most of SV's episodes. i.e. I'm sure this has been done quite a few times ever since Mark V. Shaney.
taolson 1y ago
If you program a Markov chain to generate based upon a fairly short sequence length (4 - 5 characters), it can create some neat portamenteaus. I remember back in the early 90's I trained one on some typical tech literature and it came up with the word "marketecture".
- ronsor 1y ago
  That sounds like a corporate buzzword generator
ahmedhawas123 1y ago
Random tidbit - 15+ years ago Markov chains were the go to for auto generating text. Google was not as advanced as it is today at flagging spam, so most highly affiliate-marketing dense topics (e.g., certain medications, products) search engine results pages were swamped with Markov chain-created websites that were injected with certain keywords.
- gattilorenz 1y ago
  For auto-generating non-sensical texts and SEO spam; for actual text generation, planners and realizers were the to-go approach (and ~5 years later it was all LTSMs)
AnotherGoodName 1y ago
The problem is the linear nature of markov chains. Sure they can branch but after an observation you are absolutely at a new state. A goes to B goes to C etc. A classic problem to understand why this is an issue is feeding in a 2D bitmap where the patterns are vertical but you’re passing in data left to right which Markov chains can’t handle since they are navigating exclusively on the current left to right inout. They miss the patterns completely. Similar things happen with language. Language is not linear and context from a few sentences ago should change probabilities in the current sequence of characters. The attention mechanism is the best we have for this and Markov chains struggle beyond stringing together a few syllables. I have played with Markov chains a lot. I tried having skip states and such but ultimately you’re always pushed towards doing something similar to the attention mechanism to handle context.
- cuttothechase 1y ago
  Would having a Markov chain of Markov chains help in this situation. One chain does this when 2D bitmap patterns are vertical and another one for left to right?
  - AnotherGoodName 1y ago
    Yes and then you weight between them with a neural network and your vertical predictor catches that every second vertical line is solid (while every other vertical line is static to mess up the horizontal markov chains). Of course then someone passes you video where there’s 3rd dimension. And you need to yet customise again with that consideration. Or maybe the pattern is in 45 degree diagonal lines and not horizontal or vertical. Better have a markov chains for that too. What about 10degree vertical lines? Etc. In the end you’re inputting a millions of ways there could be a pattern, passing all of those into a neural network and weighting the chains that make correct predictions more. You start to realize even with all these ways past context could still influence the current prediction and what you want is a generator for all the ways there could be a pattern. At this point you're getting into the realm of multilayer neural networks and starting to consider the attention mechanism. I don’t want to discourage anyone from learning markov chains here btw. It’s just that they have limitations and those limitations actually make a great learning journey for neural networks as you realize you really need more than an absolute singular state being activated at a time and then you start to think about how all the states activated in the past might influence the current probabilities (essentially you then start thinking about the problem the attention mechanism solves).
cestith 1y ago
I’ve been telling people for years that a reasonably workable initial, simplified mental model of a large language model is a Markov chain generator with an unlimited, weighted corpus trained in. Very few people who know LLMs have said anything to critique that thought more than that it’s a coarse description and downplays the details. Since being simplified is in the initial statement and it’s not meant to capture detail, I say if it walks like a really big duck and it honks instead of quacking then it’s maybe a goose or swan which are both pretty duck-like birds.
- nerdponx 1y ago
  It's not a Markov chain because it doesn't obey the Markov property. What it is, and what I assume you mean, is a next-word prediction model based solely on the previous sequence of words, up to some limit. It literally is that, because it was designed to be that.
  - cestith 1y ago
    What about a language model requires knowledge of previous states to choose the next state based on the current state? Are you asserting that only the last word chosen is the current state? Couldn’t the list of symbols chosen so far be the current state, so long as no data is carried forward about how that list has been generated?
    - coliveira 1y ago
      You're right, the recent memory of the LLM is the state, that's why it needs to be so deep to be effective compared to a traditional MC.
  - qwelfkh 1y ago
    Okay, so we have a function that converts a buffer of tokens to a distribution of next tokens. We give the function a buffer, get back the next-token-distribution, from which we sample to get our next token. We append that to the buffer (and possibly roll off the first token) to obtain a new buffer. If we consider entire buffers to be states (which is a perfectly reasonable thing to do), then we have a stochastic process that moves us from one state to another. How is that not a Markov chain?
jcynix 1y ago
Ah, yes, Markov chains. A long time agoMark V. Shaney https://en.wikipedia.org/wiki/Mark_V._Shaney https://en.wikipedia.org/wiki/Mark_V._Shaney was designed by Rob Pike and posted on Usenet. And Veritasium's video "The Strange Math That Predicts (Almost) Anything" talks in detail about the history of Markov chains: https://youtu.be/KZeIEiBrT_w https://youtu.be/KZeIEiBrT_w
- chilipepperhott 1y ago
  It's a great explainer. Definitely better than mine.
  - proprietario 1y ago
    fwiw, your explanation really made markov chains click for me (unlike other markov chain explanations) i have to admit, that the part where you went from the idea over hashmaps to the matrix representation was a bit dense, but rereading it twice made me under it so thanks for your explanation!
    - chilipepperhott 1y ago
      That's great to hear. Thanks! I'm glad it worked.
- emmelaich 1y ago
  Going way back, I believe https://en.wikipedia.org/wiki/Racter https://en.wikipedia.org/wiki/Racter (1984) used Markov chains. The book "The Policeman's Beard is Half-Constructed" is hilarious, but as noted it was co-written by the author.
benob 1y ago
Like it or not, LLMs are effectively high-order Markov chains
- guluarte 1y ago
  markov chains with limited self correction
- BenoitEssiambre 1y ago
  Exactly. I think of them as Markov Chains in grammar space or in Abstract Syntax Tree space instead of n-gram chain-of-words space. The attention mechanism likely plays a role in identifying the parent in the grammar tree or identifying other types of back references like pronouns or if it's for programming languages, variable back references.
  - benob 1y ago
    There was a time when people would estimate n-gram probabilities with feed-forward neural networks [1,2]. We just improved that with the (multilayer) attention mechanism which allows for better factoring over individual tokens. It also allowed for much larger n. [1] https://jmlr.org/papers/volume3/bengio03a/bengio03a.pdf https://jmlr.org/papers/volume3/bengio03a/bengio03a.pdf [2] https://www.sciencedirect.com/science/article/abs/pii/S0885230806000325 https://www.sciencedirect.com/science/article/abs/pii/S08852...
- krackers 1y ago
  Only in the way that every real-world computer is a finite state machine.
  - bigfishrunning 1y ago
    Every real-world computer is a finite state machine, there's just a lot of states. I guess I'm unsure of the point that you're trying to make here
    - 1y ago
fair_enough 1y ago
On a humorous note OP, you seem like exactly the kind of guy who would get a kick out of this postmodern essay generator that a STEM professor wrote using a Recursive Transition Network in 1996: https://www.elsewhere.org/journal/pomo/ https://www.elsewhere.org/journal/pomo/ Every now and again, I come back to it for a good chuckle. Here's what I got this time (link to the full essay below the excerpt): "If one examines subcultural capitalist theory, one is faced with a choice: either reject subdialectic cultural theory or conclude that the significance of the artist is significant form, but only if culture is interchangeable with art. It could be said that many desituationisms concerning the capitalist paradigm of context exist. The subject is contextualised into a presemanticist deappropriation that includes truth as a totality." https://www.elsewhere.org/journal/pomo/?1298795365 https://www.elsewhere.org/journal/pomo/?1298795365
- chilipepperhott 1y ago
  That essay generator is pretty cool. There are definitely a lot of undergrads whose essays look about the same.
  - fair_enough 1y ago
    There is no dearth of midwittery in the non-STEM fields. I admit this is elitist and downright snobbish, but I am disgusted that somebody else can get a degree from the same university as me in a non-STEM major and piggyback off of prestige they didn't create. In my opinion, it's stolen valor.
    - procaryote 1y ago
      Perhaps you should value knowledge over status?
      - fair_enough 1y ago
        It doesn't matter what I value. The people who wanna hire me for jobs or invest in my fund value status. There's a reason companies hire people they don't need: to make themselves look bigger to investors and in the case of law firms, clients. Analyzing complex systems from first principles and challenging decisions that have no good reason is a noble cause, but it's only useful if you have the authority to make the changes. I'm not dictator of the world, I don't get to dictate how customers, clients, or employers shall make their business and hiring decisions.
jedberg 1y ago
For funsies one of the early reddit engineers wrote a Markov comment generator trained on all the existing comments. It worked surprisingly well. :)
- huseyinkeles 1y ago
  https://www.reddit.com/r/SubredditSimulator https://www.reddit.com/r/SubredditSimulator Seems like it stopped around 5 years ago.
kragen 1y ago
A first-order Markov-chain text generator is not complex at all; it's a one-line shell script, reformatted here onto three lines for clarity: perl -ane 'push@{$m{$a}},$a=$_ for@F;END{ print$a=$m{$a}[rand@{$m{$a}}]," "for 1..100_000 }' <<<'fish fish for fish.' Given the King James Bible instead of "fish fish for fish." as input, this program produces output like this: 25:13 As the hands upon his disciple; but make great matter wisely in their calamity; 1:14 Sanctify unto the arches thereof unto them: 28:14 Happy is our judges ruled, that believe. 19:36 Thus saith the first being one another's feet. This leans pretty hard on Perl DWIM; a Python version is many times longer: import random, sys model, last, word = {None: []}, None, None for word in (word for line in sys.stdin for word in line.split()): model.setdefault(last, []).append(last := word) sys.stdout.writelines(str(word := random.choice(model.get(word) or words)) + " " for words in [list(model.keys())] for i in range(100_000)) (If you write code like that at a job, you might get fired. I would reject your pull request.) It's probably worth mentioning: - Markov-chain states don't have to be words. For text modeling, a common thing to do is to use N-grams (of either words or characters) instead of single words for your states. - It's good to have some nonzero probability to take a transition that hasn't occurred in the training set; this is especially important if you use a larger universe of states, because each state will occur fewer times in the training set. "Laplacian smoothing" is one way to do this. - Usually (and in my code examples above) the probability distribution of transitions we take in our text generator is the probability distribution we inferred from the input. Potter's approach of multiplying his next-state-occupancy vector Ms⃗ by a random diagonal matrix R and then taking the index of the highest value in the resulting vector produces somewhat similar results, but they are not the same; for example sum(random.random() * 0.75 > random.random() * 0.25 for i in range(1_000_000)) is roughly 833000, not roughly 750000. It's 5× as common instead of 3×. But I imagine that it still produces perfectly cromulent text. Interestingly, modern compilers derive from Chomsky's theory of linguistics, which he formulated while working on an AI project in the 01950s in order to demolish the dominant theory of psychology at the time, behaviorism. Behaviorism essentially held that human minds were Markov chains, and Chomsky showed that Markov chains couldn't produce context-free languages.
- chilipepperhott 1y ago
robotnikman 1y ago
I remember creating a chatbot for my minecraft server over a decade ago that used Markov chains. It was funny seeing the crazy things it spat out and the other players enjoyed it.
saylisteins 1y ago
There is an interesting video about this from Veritasium https://www.youtube.com/watch?v=KZeIEiBrT_w https://www.youtube.com/watch?v=KZeIEiBrT_w
pessimizer 1y ago
Loved playing with Babble! when I was a teenager: https://archive.org/details/Babble_1020 https://archive.org/details/Babble_1020 You could load it up with anything, and it would just babble on.
fluxusars 1y ago
Can't believe no one's mentioned this classic yet: https://www.tumblr.com/kingjamesprogramming https://www.tumblr.com/kingjamesprogramming Back in the early days of Slack I wrote a chat bot that logged all the messages people wrote and used that data to make it say random things prompted by certain trigger words. It was hilarious, until the bosses found out that I was basically logging all their conversations. Unsurprisingly they made me turn it off.
- airstrike 1y ago
  LMAO thanks for that link, it's hilarious
Aperocky 1y ago
Shameless plug for playing with random markov chain with seed texts: https://aperocky.com/markov/ https://aperocky.com/markov/ Source: https://github.com/Aperocky/weighted-markov-generator https://github.com/Aperocky/weighted-markov-generator
Doch88 1y ago
I remember coding IRC bots with Markov Chains that were repeating random nonsense from the chat, so many memories
mwcz 1y ago
This is great. I use Markov chains to describe to normies how LLMs work. It's very interesting reading what Claude Shannon wrote after producing Markov chains from English sentences. > In an unpublished spoof written a year later, Shannon imagined the damage his methods would do if they fell into the wrong hands. It seems that an evil Nazi scientist, dr. Hagen Krankheit, had escaped Germany with a prototype of his Müllabfuhrwortmaschine, a fearsome weapon of war "anticipated in the work ... of Dr. Claude Shannon." Krankheit's machine used the principles of randomized text to totally automate the propaganda industry. By randomly stitching together agitprop phrases in a way that approximated human language, the Müllabfuhrwortmaschine could produce an endless flood of demoralizing statements. From A Mind at Play. I don't remember the exact year he did that work. I think it was some time before 1950, yet strangely timely in 2025.
- lou1306 1y ago
  This is amazing, in no small part due to the fact that Krankheit literally means "disease" in German.
anthk 1y ago
Also for perl user: curl -L https://cpanmin.us/ -o cpanm ./cpanm -n local::lib ./cpanm -n Hailo ~/perl5/bin/hailo -t file.txt -b file.brn ~/perl5/bin/hailo -b file.brn file.txt must be a text file with one sentence per line.
slashdave 1y ago
I don't think the author understands what a Markov chain is
- jaapz 1y ago
  Be the first to explain it to them properly then
_aobj 1y ago
Great article. I have been hitting on 'High School's levels including 8 dimensional , dual quaternion, Dirac's Eq. Algebra. On my website. Mainly as they give a view of the dynamics of non trivial unitary matrix expansions that can occur in such as Zeta Zero, element nuclei, prime numbers, energy levels. For light elements. For de located electrons in sync, the Markov chains are interesting, as they relate to cellular automata, the taking of limits for (relativity, electrons moving with charge potential).Having not done high school algebra, until latter years. I have learnt to not assume, a particular algebra fits all dynamic non trivial matrix process's. Ie quantum computing, long range sensors, gravity waves, pressurised plasma at phase, ECT. So great article as it shows a practical high school level of applied knowledge, that doesn't revolve around solely unitary matrices. In as much as its potential dynamic (linear expansion)evolved states ! To which the high school level of visualisation can become aware! (I just thought I'd add this on legal probabilities. There is a case involving a SASR trooper 'Schultz' that revolves around shooting a Mulha's spotter. In Australia magistrates seem to judge cases based on 4 dimensional probabilities. And this seems to tie in with Jeffery Epstein's management through cohesion of President Clinton's pattent attorney change from an solely engineer to a lawyer based pattent granting. Epstein's little girl problem wasn't solely sexual, but given stock market prediction dynamics, more like a dynamic non trivial unitary probability problem of visualising size. Something magistrates in Australia seem to have adopted in the determining of complex military cases.). Warren
traes 1y ago
There seems to be a mistake in the "Building the Transition Matrix" section of this article. Instead of showing the diagonal matrix D with the normalization coefficients it instead shows the normalized Markov matrix M, incorrectly claiming it is equal to the unnormalized matrix C.
Nevermark 1y ago
Nice little example. Could add a "stop" token at the end of the fruit example, so when the little model runs it can call its own stop. To generalize to ADHD, create another model that can quietly "Listen" to a speaker (token generator) until its Markov chain predicts a "Stop", and starts its own generating model running, regardless of whether the speaker was done. Then two instances can have time efficient interrupty conversations with each other.
snoopre 1y ago
[dead]
calf 1y ago
So I think this "talking point" of "LLMs are just Markov chains" is as bad, analogously, as "Your amazing invention that passes the Turing Test is justa giant LUT". Or "Your C++ program is justa FSM". It is all technically true, but it is being used subtly to dismiss/delegitimize something, instead of communicate a scientifically insightful idea. How is this different than "Humans are just collections of cells". True except we're are a very interesting type of collection! LLMs are a very interesting type of Markov chain! Haskell/Java/Ruby programs are a very interesting type of FSM! Etc. The talking point by itself is just reductionism, of which we've seen and heard variants of during other scientific revolutions. Also, this Markov chain has size O(T^K), exponential in the token length of the context window, which is a beyond astronomically large object
leecming 1y ago
markov chains are a historical curio for NLP - easy to understand and implement, but just not good enough to do anything useful with. the jump to word vectors (e.g., word2vec) + CNNs/RNNs arguably put the field in a place where you could build useful language tools
- hiddencost 1y ago
  They're used heavily in information retrieval at scale. 3gram counting features especially.
dugmartin 1y ago
If you would like to visually play with a Markov chain model my non-profit research org built a Markov plugin for, CODAP, our data analysis tool: https://codap.concord.org/app/static/dg/en/cert/index.html?di=https://models-resources.concord.org/markov-chain-plugin/ https://codap.concord.org/app/static/dg/en/cert/index.html?d... If you select drawing mode from the first screen shown and then click the "T" icon you can type some text and it will generate a state diagram for you that you can then "play" and examine the output sequences. If you have states that have multiple exit routes you can click on that state and adjust the probabilities of each option.
mangomountain 1y ago
When I first heard about chat gpt I thought it was a markov chain generator and totally dismissed it lol woops
dfsegoat 1y ago
Related: KingJamesProgramming [1] - a mashup of Knuth books [2] and the King James Bible with a Markov chain, is still one of my favorite reads for a laugh. It was also the first place I was really exposed to probabilistic-based methods for generation of novel content. You get gems like: "they smote the city with the edge of the sword. 22:20 And one of his main motivations was the high cost of proprietary software houses." and "37:29 The righteous shall inherit the land, and leave it for an inheritance unto the children of Gad according to the number of steps that is linear in b." [1] https://www.tumblr.com/kingjamesprogramming https://www.tumblr.com/kingjamesprogramming [2] https://en.wikipedia.org/wiki/Donald_Knuth https://en.wikipedia.org/wiki/Donald_Knuth
- foofoo12 1y ago
  The latest post on KingJamesProgramming is hilarious: "then shall they call upon me, but I will not cause any information to be accumulated on the stack."
- svat 1y ago
  Just stating for clarity: it is a mashup of the King James Bible and the book Structure and Interpretation of Computer Programs, which is not by Knuth (it is by Harold Abelson and Gerald Jay Sussman with Julie Sussman).
  - dfsegoat 1y ago
    Ahh thank you for catching - apologies I didn't see this in time to add a correction.
procaryote 1y ago
Aren't transformers markov chains mathematically? You couldn't practically implement them as naive markov chains as the state space is too big, but the math is the same, isn't it?
- lou1306 1y ago
  Yes, in the sense that they can be formalised as such. Given n tokens t1..tn, a transformer computes the probability p(t') that every token t' has of being the next. Each of these probabilities are arcs from a state t1..tn to another state t1..tn,t' weighted by p(t'). And since the context window is bounded, this is guaranteed to be finite-state, and all states are transient except those where the window is saturated.
Ianjit 1y ago
I am at stage 4 as well. Boredom.
stared 1y ago
Markov models do not extrapolate. If we take intuitions from HMMs and use them in LLMs, we are prone to see nothing besides "stochastic parrots". Anyway, for anyone who wants to go deeper, I recommend Lawrence R. Rabiner, "A tutorial on Hidden Markov Models and selected applications in speech recognition", https://www.cs.cmu.edu/~cga/behavior/rabiner1.pdf https://www.cs.cmu.edu/~cga/behavior/rabiner1.pdf And for a cure example, there is also one in nothin else than Claude Shannon, "A Mathematical Theory of Communication", https://web.archive.org/web/20121108191018/https://www.alcatel-lucent.com/bstj/vol27-1948/articles/bstj27-3-379.pdf https://web.archive.org/web/20121108191018/https://www.alcat...
brador 1y ago
RNG, then Bayesian, then vectors, then markovs, then tensors is the temporal research order of human like sentence generation. Exciting to see what’s next but not much breakthrough remaining in the space.
bjornsing 1y ago
I’d say an LLM is a form of Markov chain, where the state is defined to consist of the entire context window, and each state transition adds one token to that context window.
andai 1y ago
This is most apparent with older models like GPT-2, and more generally base ("text") models like Davinci. They are essentially only trained to predict the next word, based on what they've seen on the internet. So they're a really fun way to try and "sample" the internet, by seeing the kind of outputs they produce. -- A really fun thing I did with GPT-2 with a friend back when it came out, is we fine tuned the model on our WhatsApp conversation together. (The model was small enough to do this on mid range GPU, in a few hours.) So GPT-2 learned to simulate chats between us. It was hilarious, but also weirdly illuminating. My friend mostly talked about art (true), and didn't say much (true), and I rambled about how I finally figured out the One Weird Trick that's finally gonna turn my life around (...also true)... The text itself was largely incoherent, but the "feel" (statistical properties?) were spot on.
- whycombinetor 1y ago
  Modern LLMs are also "essentially only trained to predict the next word, based on what they've seen on the internet."
  - andai 1y ago
    Well, sort of! The new ones all "sound like AI." They're not great for writing, especially in terms of style and tone. I'm not sure exactly how that works, but apparently instruct tuning produces mode collapse, whereas the older models are basically "raw unfiltered internet" (for better and worse). I've been playing around with Davinci and it's remakable how much better the writing is. You have to prompt it right, because all it does is continue the text. (E.g. if you ask it a question, it might respond with more questions.) But I think we really lost something valuable when we started neglecting the base/text models.
  - in-silico 1y ago
    Until they've undergone preference tuning and RL post-training (which is expected to start using more training compute than next-token-prediction pre-training).
lormayna 1y ago
Almost 10 years ago I created couple of Twitter bots that can tweet like the leaders of two populisti Italian party. The quality of the tweets was sometimes not the best, but usually decent. It was impressive how many people starts following them in few weeks.
westurner 1y ago
Markov chain > History: https://en.wikipedia.org/wiki/Markov_chain#History https://en.wikipedia.org/wiki/Markov_chain#History Examples of Markov chains: https://en.wikipedia.org/wiki/Examples_of_Markov_chains https://en.wikipedia.org/wiki/Examples_of_Markov_chains A Hopfield network is an RNN Recurrent Neural Network. Hopfield network: https://en.wikipedia.org/wiki/Hopfield_network https://en.wikipedia.org/wiki/Hopfield_network From "Ask HN: Parameter-free neural network models: Limits, Challenges, Opportunities?" (2024) https://news.ycombinator.com/item?id=41794272 https://news.ycombinator.com/item?id=41794272 re: neural network topologies : > The Asimov Institute > The Neural Network Zoo: https://www.asimovinstitute.org/neural-network-zoo https://www.asimovinstitute.org/neural-network-zoo > PNG: "A mostly complete chart of neural networks" (2019) includes Hopfield nets!" https://www.asimovinstitute.org/wp-content/uploads/2019/04/NeuralNetworkZo19High.png https://www.asimovinstitute.org/wp-content/uploads/2019/04/N... > [ Category:Neural network architectures, Types of artificial neural networks ]
Atatator 1y ago
As my scientific advisor used to say: "Markov has nothing to lose but his chains!"
red_hare 1y ago
I use Markov chains as an example of a "Small Language Model" in teaching LLMs. My favorite thing about them is that you can use them to demonstrate temperature. The math is basically the same, and it has a similar effect of creating more creativity in the response. from math import log, exp from random import choices # Likilihood of transitioning from of curr_word to next_word transitions: dict[dict[str, float]] = {...} def next_word(current_word, temp=1.0): if current_word not in transitions: return random.choice(list(transitions.keys())) probabilities = transitions[current_word] next_words = list(probabilities.keys()) pvals = list(probabilities.values()) logits = [log(p) for p in pvals] scaled_logits = [logit/temp for logit in logits] max_logit = max(scaled_logits) exps = [exp(s - max_logit) for s in scaled_logits] sum_exps = sum(exps) softmax_probs = [exp_val/sum_exps for exp_val in exps] return choices(next_words, weights=softmax_probs)[0] def generate_sequence(start_word, length): sequence = [start_word] current_word = start_word for _ in range(length - 1): current_word = next_word(current_word) sequence.append(current_word) return sequence Some outputs of this when the transitions are trained on a lyrics dataset. > print(" ".join(generate_sequence("When", 20, temp=0.1))) When I know that I know that I was a little thing that I know that I don't know that > print(" ".join(generate_sequence("When", 20, temp=0.5))) When I don't know you know I can do I see And the river to the light in the time > print(" ".join(generate_sequence("When", 20, temp=1.0))) When are melting Little darling, I feel more And if I was very slow (In control) For our troubles And It's a lot more nonsensical than an LLM, but highlights what the logit manipulation is doing.

I remember playing with megahal eggdrop bots. This was one of my first forays into modifying c code, trying to figure out why 350mb seemed to be the biggest brain size (32 bit memory limits and requiring a contiguous block for the entire brain). I miss the innocence of those days. Just being a teen, tinkering with things i didn't understand.

foobarian 1y ago
I'm old now, but thanks to LLMs I can now again tinker with things I don't understand :-)
- codr7 1y ago
  Are you though? Or is the LLM the target of your tinkering and lack of understanding? Honest question.
- jcynix 1y ago
  The nice thing about LLMs is that they can explain stuff so you can learn to understand. And they are very patient. For example I'm currently relearning various ImageMagick details and thanks to their explanations now understand things that I cut/copy/pasted a long time ago without always understanding why things worked the way they did.
vunderba 1y ago
I remember reading the source of the original MegaHAL program when I was younger - one of the tricks that made it stand out (particularly in the Loebner competitions [1]) was that it used both a backwards and forwards Markov chain to generate responses. [1] https://en.wikipedia.org/wiki/Loebner_Prize https://en.wikipedia.org/wiki/Loebner_Prize
anthk 1y ago
Hailo it's still alive under CPAN.

glouwbug 1y ago

The Practice of Programming by Kernighan and Pike had a really elegant Markov: https://github.com/Heatwave/the-practice-of-programming/blob/master/3.3.markov-chain.c https://github.com/Heatwave/the-practice-of-programming/blob...

jcynix 1y ago
And Mark V. Shaney was designed by Rob Pike and posted on Usenet, but that happened a long time ago: https://en.wikipedia.org/wiki/Mark_V._Shaney https://en.wikipedia.org/wiki/Mark_V._Shaney
anthk 1y ago
This one too: http://c9x.me/cbits/ http://c9x.me/cbits/
y7r4m 1y ago
About a decade ago I somehow came across Genudi[0], a markov chain based "AI", and had quite a bit of fun with it. The creator has a blog that makes for an interesting reading session. 0: https://www.genudi.com/about https://www.genudi.com/about

chankstein38 1y ago

I once, probably 4-6 years ago, used exports from Slack conversations to train a Markov Chain to recreate a user that was around a lot and then left for a while. I wrote the whole thing in python and wasn't overly well-versed in the statistics and math side but understood the principle. I made a bot and had it join the Slack instance that I administrate and it would interact if you tagged it or if you said things that person always responded to (hardcoded). Well, the responses were pretty messed up and not accurate but we all got a good chuckle watching the bot sometimes actually sound like the person amidst a mass of random other things that person always said jumbled together :D

vunderba 1y ago
I had a similar program designed as my "AWAY" bot that was trained on transcripts of my previous conversations and connected to Skype. At the time (2009) I was living in Taiwan so I would activate it when I went to bed to chat with my friends back in the States given the ~12 hour time difference. Reading back some of the transcripts made it sound like I was on the verge of a psychotic break though.
emmelaich 1y ago
I'm sure that Gilfoyle's prank in Silicon Valley had its basis in a true story, like most of SV's episodes. i.e. I'm sure this has been done quite a few times ever since Mark V. Shaney.

taolson 1y ago

If you program a Markov chain to generate based upon a fairly short sequence length (4 - 5 characters), it can create some neat portamenteaus. I remember back in the early 90's I trained one on some typical tech literature and it came up with the word "marketecture".

ronsor 1y ago
That sounds like a corporate buzzword generator

ahmedhawas123 1y ago

Random tidbit - 15+ years ago Markov chains were the go to for auto generating text. Google was not as advanced as it is today at flagging spam, so most highly affiliate-marketing dense topics (e.g., certain medications, products) search engine results pages were swamped with Markov chain-created websites that were injected with certain keywords.

gattilorenz 1y ago
For auto-generating non-sensical texts and SEO spam; for actual text generation, planners and realizers were the to-go approach (and ~5 years later it was all LTSMs)

AnotherGoodName 1y ago

The problem is the linear nature of markov chains. Sure they can branch but after an observation you are absolutely at a new state. A goes to B goes to C etc. A classic problem to understand why this is an issue is feeding in a 2D bitmap where the patterns are vertical but you’re passing in data left to right which Markov chains can’t handle since they are navigating exclusively on the current left to right inout. They miss the patterns completely. Similar things happen with language. Language is not linear and context from a few sentences ago should change probabilities in the current sequence of characters. The attention mechanism is the best we have for this and Markov chains struggle beyond stringing together a few syllables. I have played with Markov chains a lot. I tried having skip states and such but ultimately you’re always pushed towards doing something similar to the attention mechanism to handle context.

cuttothechase 1y ago
Would having a Markov chain of Markov chains help in this situation. One chain does this when 2D bitmap patterns are vertical and another one for left to right?
- AnotherGoodName 1y ago
  Yes and then you weight between them with a neural network and your vertical predictor catches that every second vertical line is solid (while every other vertical line is static to mess up the horizontal markov chains). Of course then someone passes you video where there’s 3rd dimension. And you need to yet customise again with that consideration. Or maybe the pattern is in 45 degree diagonal lines and not horizontal or vertical. Better have a markov chains for that too. What about 10degree vertical lines? Etc. In the end you’re inputting a millions of ways there could be a pattern, passing all of those into a neural network and weighting the chains that make correct predictions more. You start to realize even with all these ways past context could still influence the current prediction and what you want is a generator for all the ways there could be a pattern. At this point you're getting into the realm of multilayer neural networks and starting to consider the attention mechanism. I don’t want to discourage anyone from learning markov chains here btw. It’s just that they have limitations and those limitations actually make a great learning journey for neural networks as you realize you really need more than an absolute singular state being activated at a time and then you start to think about how all the states activated in the past might influence the current probabilities (essentially you then start thinking about the problem the attention mechanism solves).

cestith 1y ago

I’ve been telling people for years that a reasonably workable initial, simplified mental model of a large language model is a Markov chain generator with an unlimited, weighted corpus trained in. Very few people who know LLMs have said anything to critique that thought more than that it’s a coarse description and downplays the details. Since being simplified is in the initial statement and it’s not meant to capture detail, I say if it walks like a really big duck and it honks instead of quacking then it’s maybe a goose or swan which are both pretty duck-like birds.

nerdponx 1y ago
It's not a Markov chain because it doesn't obey the Markov property. What it is, and what I assume you mean, is a next-word prediction model based solely on the previous sequence of words, up to some limit. It literally is that, because it was designed to be that.
- cestith 1y ago
  What about a language model requires knowledge of previous states to choose the next state based on the current state? Are you asserting that only the last word chosen is the current state? Couldn’t the list of symbols chosen so far be the current state, so long as no data is carried forward about how that list has been generated?
  - coliveira 1y ago
    You're right, the recent memory of the LLM is the state, that's why it needs to be so deep to be effective compared to a traditional MC.
- qwelfkh 1y ago
  Okay, so we have a function that converts a buffer of tokens to a distribution of next tokens. We give the function a buffer, get back the next-token-distribution, from which we sample to get our next token. We append that to the buffer (and possibly roll off the first token) to obtain a new buffer. If we consider entire buffers to be states (which is a perfectly reasonable thing to do), then we have a stochastic process that moves us from one state to another. How is that not a Markov chain?

jcynix 1y ago

Ah, yes, Markov chains. A long time agoMark V. Shaney https://en.wikipedia.org/wiki/Mark_V._Shaney https://en.wikipedia.org/wiki/Mark_V._Shaney was designed by Rob Pike and posted on Usenet. And Veritasium's video "The Strange Math That Predicts (Almost) Anything" talks in detail about the history of Markov chains: https://youtu.be/KZeIEiBrT_w https://youtu.be/KZeIEiBrT_w

chilipepperhott 1y ago
It's a great explainer. Definitely better than mine.
- proprietario 1y ago
  fwiw, your explanation really made markov chains click for me (unlike other markov chain explanations) i have to admit, that the part where you went from the idea over hashmaps to the matrix representation was a bit dense, but rereading it twice made me under it so thanks for your explanation!
  - chilipepperhott 1y ago
    That's great to hear. Thanks! I'm glad it worked.
emmelaich 1y ago
Going way back, I believe https://en.wikipedia.org/wiki/Racter https://en.wikipedia.org/wiki/Racter (1984) used Markov chains. The book "The Policeman's Beard is Half-Constructed" is hilarious, but as noted it was co-written by the author.

benob 1y ago

Like it or not, LLMs are effectively high-order Markov chains

guluarte 1y ago
markov chains with limited self correction
BenoitEssiambre 1y ago
Exactly. I think of them as Markov Chains in grammar space or in Abstract Syntax Tree space instead of n-gram chain-of-words space. The attention mechanism likely plays a role in identifying the parent in the grammar tree or identifying other types of back references like pronouns or if it's for programming languages, variable back references.
- benob 1y ago
  There was a time when people would estimate n-gram probabilities with feed-forward neural networks [1,2]. We just improved that with the (multilayer) attention mechanism which allows for better factoring over individual tokens. It also allowed for much larger n. [1] https://jmlr.org/papers/volume3/bengio03a/bengio03a.pdf https://jmlr.org/papers/volume3/bengio03a/bengio03a.pdf [2] https://www.sciencedirect.com/science/article/abs/pii/S0885230806000325 https://www.sciencedirect.com/science/article/abs/pii/S08852...
krackers 1y ago
Only in the way that every real-world computer is a finite state machine.
- bigfishrunning 1y ago
  Every real-world computer is a finite state machine, there's just a lot of states. I guess I'm unsure of the point that you're trying to make here
  - 1y ago

fair_enough 1y ago

On a humorous note OP, you seem like exactly the kind of guy who would get a kick out of this postmodern essay generator that a STEM professor wrote using a Recursive Transition Network in 1996: https://www.elsewhere.org/journal/pomo/ https://www.elsewhere.org/journal/pomo/ Every now and again, I come back to it for a good chuckle. Here's what I got this time (link to the full essay below the excerpt): "If one examines subcultural capitalist theory, one is faced with a choice: either reject subdialectic cultural theory or conclude that the significance of the artist is significant form, but only if culture is interchangeable with art. It could be said that many desituationisms concerning the capitalist paradigm of context exist. The subject is contextualised into a presemanticist deappropriation that includes truth as a totality." https://www.elsewhere.org/journal/pomo/?1298795365 https://www.elsewhere.org/journal/pomo/?1298795365

chilipepperhott 1y ago
That essay generator is pretty cool. There are definitely a lot of undergrads whose essays look about the same.
- fair_enough 1y ago
  There is no dearth of midwittery in the non-STEM fields. I admit this is elitist and downright snobbish, but I am disgusted that somebody else can get a degree from the same university as me in a non-STEM major and piggyback off of prestige they didn't create. In my opinion, it's stolen valor.
  - procaryote 1y ago
    Perhaps you should value knowledge over status?
    - fair_enough 1y ago
      It doesn't matter what I value. The people who wanna hire me for jobs or invest in my fund value status. There's a reason companies hire people they don't need: to make themselves look bigger to investors and in the case of law firms, clients. Analyzing complex systems from first principles and challenging decisions that have no good reason is a noble cause, but it's only useful if you have the authority to make the changes. I'm not dictator of the world, I don't get to dictate how customers, clients, or employers shall make their business and hiring decisions.

jedberg 1y ago

For funsies one of the early reddit engineers wrote a Markov comment generator trained on all the existing comments. It worked surprisingly well. :)

huseyinkeles 1y ago
https://www.reddit.com/r/SubredditSimulator https://www.reddit.com/r/SubredditSimulator Seems like it stopped around 5 years ago.

kragen 1y ago

A first-order Markov-chain text generator is not complex at all; it's a one-line shell script, reformatted here onto three lines for clarity: perl -ane 'push@{$m{$a}},$a=$_ for@F;END{ print$a=$m{$a}[rand@{$m{$a}}]," "for 1..100_000 }' <<<'fish fish for fish.' Given the King James Bible instead of "fish fish for fish." as input, this program produces output like this: 25:13 As the hands upon his disciple; but make great matter wisely in their calamity; 1:14 Sanctify unto the arches thereof unto them: 28:14 Happy is our judges ruled, that believe. 19:36 Thus saith the first being one another's feet. This leans pretty hard on Perl DWIM; a Python version is many times longer: import random, sys model, last, word = {None: []}, None, None for word in (word for line in sys.stdin for word in line.split()): model.setdefault(last, []).append(last := word) sys.stdout.writelines(str(word := random.choice(model.get(word) or words)) + " " for words in [list(model.keys())] for i in range(100_000)) (If you write code like that at a job, you might get fired. I would reject your pull request.) It's probably worth mentioning: - Markov-chain states don't have to be words. For text modeling, a common thing to do is to use N-grams (of either words or characters) instead of single words for your states. - It's good to have some nonzero probability to take a transition that hasn't occurred in the training set; this is especially important if you use a larger universe of states, because each state will occur fewer times in the training set. "Laplacian smoothing" is one way to do this. - Usually (and in my code examples above) the probability distribution of transitions we take in our text generator is the probability distribution we inferred from the input. Potter's approach of multiplying his next-state-occupancy vector Ms⃗ by a random diagonal matrix R and then taking the index of the highest value in the resulting vector produces somewhat similar results, but they are not the same; for example sum(random.random() * 0.75 > random.random() * 0.25 for i in range(1_000_000)) is roughly 833000, not roughly 750000. It's 5× as common instead of 3×. But I imagine that it still produces perfectly cromulent text. Interestingly, modern compilers derive from Chomsky's theory of linguistics, which he formulated while working on an AI project in the 01950s in order to demolish the dominant theory of psychology at the time, behaviorism. Behaviorism essentially held that human minds were Markov chains, and Chomsky showed that Markov chains couldn't produce context-free languages.

chilipepperhott 1y ago

robotnikman 1y ago

I remember creating a chatbot for my minecraft server over a decade ago that used Markov chains. It was funny seeing the crazy things it spat out and the other players enjoyed it.

saylisteins 1y ago

There is an interesting video about this from Veritasium https://www.youtube.com/watch?v=KZeIEiBrT_w https://www.youtube.com/watch?v=KZeIEiBrT_w

pessimizer 1y ago

Loved playing with Babble! when I was a teenager: https://archive.org/details/Babble_1020 https://archive.org/details/Babble_1020 You could load it up with anything, and it would just babble on.

fluxusars 1y ago

Can't believe no one's mentioned this classic yet: https://www.tumblr.com/kingjamesprogramming https://www.tumblr.com/kingjamesprogramming Back in the early days of Slack I wrote a chat bot that logged all the messages people wrote and used that data to make it say random things prompted by certain trigger words. It was hilarious, until the bosses found out that I was basically logging all their conversations. Unsurprisingly they made me turn it off.

airstrike 1y ago
LMAO thanks for that link, it's hilarious

Aperocky 1y ago

Shameless plug for playing with random markov chain with seed texts: https://aperocky.com/markov/ https://aperocky.com/markov/ Source: https://github.com/Aperocky/weighted-markov-generator https://github.com/Aperocky/weighted-markov-generator

Doch88 1y ago

I remember coding IRC bots with Markov Chains that were repeating random nonsense from the chat, so many memories

mwcz 1y ago

This is great. I use Markov chains to describe to normies how LLMs work. It's very interesting reading what Claude Shannon wrote after producing Markov chains from English sentences. > In an unpublished spoof written a year later, Shannon imagined the damage his methods would do if they fell into the wrong hands. It seems that an evil Nazi scientist, dr. Hagen Krankheit, had escaped Germany with a prototype of his Müllabfuhrwortmaschine, a fearsome weapon of war "anticipated in the work ... of Dr. Claude Shannon." Krankheit's machine used the principles of randomized text to totally automate the propaganda industry. By randomly stitching together agitprop phrases in a way that approximated human language, the Müllabfuhrwortmaschine could produce an endless flood of demoralizing statements. From A Mind at Play. I don't remember the exact year he did that work. I think it was some time before 1950, yet strangely timely in 2025.

lou1306 1y ago
This is amazing, in no small part due to the fact that Krankheit literally means "disease" in German.

anthk 1y ago

Also for perl user: curl -L https://cpanmin.us/ -o cpanm ./cpanm -n local::lib ./cpanm -n Hailo ~/perl5/bin/hailo -t file.txt -b file.brn ~/perl5/bin/hailo -b file.brn file.txt must be a text file with one sentence per line.

slashdave 1y ago

I don't think the author understands what a Markov chain is

jaapz 1y ago
Be the first to explain it to them properly then

_aobj 1y ago

Great article. I have been hitting on 'High School's levels including 8 dimensional , dual quaternion, Dirac's Eq. Algebra. On my website. Mainly as they give a view of the dynamics of non trivial unitary matrix expansions that can occur in such as Zeta Zero, element nuclei, prime numbers, energy levels. For light elements. For de located electrons in sync, the Markov chains are interesting, as they relate to cellular automata, the taking of limits for (relativity, electrons moving with charge potential).Having not done high school algebra, until latter years. I have learnt to not assume, a particular algebra fits all dynamic non trivial matrix process's. Ie quantum computing, long range sensors, gravity waves, pressurised plasma at phase, ECT. So great article as it shows a practical high school level of applied knowledge, that doesn't revolve around solely unitary matrices. In as much as its potential dynamic (linear expansion)evolved states ! To which the high school level of visualisation can become aware! (I just thought I'd add this on legal probabilities. There is a case involving a SASR trooper 'Schultz' that revolves around shooting a Mulha's spotter. In Australia magistrates seem to judge cases based on 4 dimensional probabilities. And this seems to tie in with Jeffery Epstein's management through cohesion of President Clinton's pattent attorney change from an solely engineer to a lawyer based pattent granting. Epstein's little girl problem wasn't solely sexual, but given stock market prediction dynamics, more like a dynamic non trivial unitary probability problem of visualising size. Something magistrates in Australia seem to have adopted in the determining of complex military cases.). Warren

traes 1y ago

There seems to be a mistake in the "Building the Transition Matrix" section of this article. Instead of showing the diagonal matrix D with the normalization coefficients it instead shows the normalized Markov matrix M, incorrectly claiming it is equal to the unnormalized matrix C.

Nevermark 1y ago

Nice little example. Could add a "stop" token at the end of the fruit example, so when the little model runs it can call its own stop. To generalize to ADHD, create another model that can quietly "Listen" to a speaker (token generator) until its Markov chain predicts a "Stop", and starts its own generating model running, regardless of whether the speaker was done. Then two instances can have time efficient interrupty conversations with each other.

snoopre 1y ago

[dead]

calf 1y ago

So I think this "talking point" of "LLMs are just Markov chains" is as bad, analogously, as "Your amazing invention that passes the Turing Test is justa giant LUT". Or "Your C++ program is justa FSM". It is all technically true, but it is being used subtly to dismiss/delegitimize something, instead of communicate a scientifically insightful idea. How is this different than "Humans are just collections of cells". True except we're are a very interesting type of collection! LLMs are a very interesting type of Markov chain! Haskell/Java/Ruby programs are a very interesting type of FSM! Etc. The talking point by itself is just reductionism, of which we've seen and heard variants of during other scientific revolutions. Also, this Markov chain has size O(T^K), exponential in the token length of the context window, which is a beyond astronomically large object

leecming 1y ago

markov chains are a historical curio for NLP - easy to understand and implement, but just not good enough to do anything useful with. the jump to word vectors (e.g., word2vec) + CNNs/RNNs arguably put the field in a place where you could build useful language tools

hiddencost 1y ago
They're used heavily in information retrieval at scale. 3gram counting features especially.

dugmartin 1y ago

If you would like to visually play with a Markov chain model my non-profit research org built a Markov plugin for, CODAP, our data analysis tool: https://codap.concord.org/app/static/dg/en/cert/index.html?di=https://models-resources.concord.org/markov-chain-plugin/ https://codap.concord.org/app/static/dg/en/cert/index.html?d... If you select drawing mode from the first screen shown and then click the "T" icon you can type some text and it will generate a state diagram for you that you can then "play" and examine the output sequences. If you have states that have multiple exit routes you can click on that state and adjust the probabilities of each option.

mangomountain 1y ago

When I first heard about chat gpt I thought it was a markov chain generator and totally dismissed it lol woops

dfsegoat 1y ago

Related: KingJamesProgramming [1] - a mashup of Knuth books [2] and the King James Bible with a Markov chain, is still one of my favorite reads for a laugh. It was also the first place I was really exposed to probabilistic-based methods for generation of novel content. You get gems like: "they smote the city with the edge of the sword. 22:20 And one of his main motivations was the high cost of proprietary software houses." and "37:29 The righteous shall inherit the land, and leave it for an inheritance unto the children of Gad according to the number of steps that is linear in b." [1] https://www.tumblr.com/kingjamesprogramming https://www.tumblr.com/kingjamesprogramming [2] https://en.wikipedia.org/wiki/Donald_Knuth https://en.wikipedia.org/wiki/Donald_Knuth

foofoo12 1y ago
The latest post on KingJamesProgramming is hilarious: "then shall they call upon me, but I will not cause any information to be accumulated on the stack."
svat 1y ago
Just stating for clarity: it is a mashup of the King James Bible and the book Structure and Interpretation of Computer Programs, which is not by Knuth (it is by Harold Abelson and Gerald Jay Sussman with Julie Sussman).
- dfsegoat 1y ago
  Ahh thank you for catching - apologies I didn't see this in time to add a correction.

procaryote 1y ago

Aren't transformers markov chains mathematically? You couldn't practically implement them as naive markov chains as the state space is too big, but the math is the same, isn't it?

lou1306 1y ago
Yes, in the sense that they can be formalised as such. Given n tokens t1..tn, a transformer computes the probability p(t') that every token t' has of being the next. Each of these probabilities are arcs from a state t1..tn to another state t1..tn,t' weighted by p(t'). And since the context window is bounded, this is guaranteed to be finite-state, and all states are transient except those where the window is saturated.

Ianjit 1y ago

I am at stage 4 as well. Boredom.

stared 1y ago

Markov models do not extrapolate. If we take intuitions from HMMs and use them in LLMs, we are prone to see nothing besides "stochastic parrots". Anyway, for anyone who wants to go deeper, I recommend Lawrence R. Rabiner, "A tutorial on Hidden Markov Models and selected applications in speech recognition", https://www.cs.cmu.edu/~cga/behavior/rabiner1.pdf https://www.cs.cmu.edu/~cga/behavior/rabiner1.pdf And for a cure example, there is also one in nothin else than Claude Shannon, "A Mathematical Theory of Communication", https://web.archive.org/web/20121108191018/https://www.alcatel-lucent.com/bstj/vol27-1948/articles/bstj27-3-379.pdf https://web.archive.org/web/20121108191018/https://www.alcat...

brador 1y ago

RNG, then Bayesian, then vectors, then markovs, then tensors is the temporal research order of human like sentence generation. Exciting to see what’s next but not much breakthrough remaining in the space.

bjornsing 1y ago

I’d say an LLM is a form of Markov chain, where the state is defined to consist of the entire context window, and each state transition adds one token to that context window.

andai 1y ago

This is most apparent with older models like GPT-2, and more generally base ("text") models like Davinci. They are essentially only trained to predict the next word, based on what they've seen on the internet. So they're a really fun way to try and "sample" the internet, by seeing the kind of outputs they produce. -- A really fun thing I did with GPT-2 with a friend back when it came out, is we fine tuned the model on our WhatsApp conversation together. (The model was small enough to do this on mid range GPU, in a few hours.) So GPT-2 learned to simulate chats between us. It was hilarious, but also weirdly illuminating. My friend mostly talked about art (true), and didn't say much (true), and I rambled about how I finally figured out the One Weird Trick that's finally gonna turn my life around (...also true)... The text itself was largely incoherent, but the "feel" (statistical properties?) were spot on.

whycombinetor 1y ago
Modern LLMs are also "essentially only trained to predict the next word, based on what they've seen on the internet."
- andai 1y ago
  Well, sort of! The new ones all "sound like AI." They're not great for writing, especially in terms of style and tone. I'm not sure exactly how that works, but apparently instruct tuning produces mode collapse, whereas the older models are basically "raw unfiltered internet" (for better and worse). I've been playing around with Davinci and it's remakable how much better the writing is. You have to prompt it right, because all it does is continue the text. (E.g. if you ask it a question, it might respond with more questions.) But I think we really lost something valuable when we started neglecting the base/text models.
- in-silico 1y ago
  Until they've undergone preference tuning and RL post-training (which is expected to start using more training compute than next-token-prediction pre-training).

lormayna 1y ago

Almost 10 years ago I created couple of Twitter bots that can tweet like the leaders of two populisti Italian party. The quality of the tweets was sometimes not the best, but usually decent. It was impressive how many people starts following them in few weeks.

westurner 1y ago

Markov chain > History: https://en.wikipedia.org/wiki/Markov_chain#History https://en.wikipedia.org/wiki/Markov_chain#History Examples of Markov chains: https://en.wikipedia.org/wiki/Examples_of_Markov_chains https://en.wikipedia.org/wiki/Examples_of_Markov_chains A Hopfield network is an RNN Recurrent Neural Network. Hopfield network: https://en.wikipedia.org/wiki/Hopfield_network https://en.wikipedia.org/wiki/Hopfield_network From "Ask HN: Parameter-free neural network models: Limits, Challenges, Opportunities?" (2024) https://news.ycombinator.com/item?id=41794272 https://news.ycombinator.com/item?id=41794272 re: neural network topologies : > The Asimov Institute > The Neural Network Zoo: https://www.asimovinstitute.org/neural-network-zoo https://www.asimovinstitute.org/neural-network-zoo > PNG: "A mostly complete chart of neural networks" (2019) includes Hopfield nets!" https://www.asimovinstitute.org/wp-content/uploads/2019/04/NeuralNetworkZo19High.png https://www.asimovinstitute.org/wp-content/uploads/2019/04/N... > [ Category:Neural network architectures, Types of artificial neural networks ]

Atatator 1y ago

As my scientific advisor used to say: "Markov has nothing to lose but his chains!"

red_hare 1y ago

I use Markov chains as an example of a "Small Language Model" in teaching LLMs. My favorite thing about them is that you can use them to demonstrate temperature. The math is basically the same, and it has a similar effect of creating more creativity in the response. from math import log, exp from random import choices # Likilihood of transitioning from of curr_word to next_word transitions: dict[dict[str, float]] = {...} def next_word(current_word, temp=1.0): if current_word not in transitions: return random.choice(list(transitions.keys())) probabilities = transitions[current_word] next_words = list(probabilities.keys()) pvals = list(probabilities.values()) logits = [log(p) for p in pvals] scaled_logits = [logit/temp for logit in logits] max_logit = max(scaled_logits) exps = [exp(s - max_logit) for s in scaled_logits] sum_exps = sum(exps) softmax_probs = [exp_val/sum_exps for exp_val in exps] return choices(next_words, weights=softmax_probs)[0] def generate_sequence(start_word, length): sequence = [start_word] current_word = start_word for _ in range(length - 1): current_word = next_word(current_word) sequence.append(current_word) return sequence Some outputs of this when the transitions are trained on a lyrics dataset. > print(" ".join(generate_sequence("When", 20, temp=0.1))) When I know that I know that I was a little thing that I know that I don't know that > print(" ".join(generate_sequence("When", 20, temp=0.5))) When I don't know you know I can do I see And the river to the light in the time > print(" ".join(generate_sequence("When", 20, temp=1.0))) When are melting Little darling, I feel more And if I was very slow (In control) For our troubles And It's a lot more nonsensical than an LLM, but highlights what the logit manipulation is doing.