6 ms·

Problem solving using Markov chains (2007) [pdf]

301 points by Alifatisk 1y ago

satvikpendem 1y ago
I assume OP watched this excellent Veritasium video about Markov and his chains [0] and posted this article which was referenced in that video. [0] https://youtu.be/KZeIEiBrT_w https://youtu.be/KZeIEiBrT_w
- Alifatisk 1y ago
  You nailed it, I wanted to post the actual article but found that they where behind a paywall, and I don't know if pirated content is allowed to share here but it's definitely worth a read though!
  - danlitt 1y ago
    It is often not piracy to find open copies of papers; the authors often publish them directly (on their personal pages or on arxiv). A commenter further down found a public link: https://math.uchicago.edu/~shmuel/Network-course-readings/Markov_chain_tricks.pdf https://math.uchicago.edu/~shmuel/Network-course-readings/Ma...
    - denverllc 1y ago
      Yeah, most authors are not concerned about their papers being shared because what they care about is citations, not money. It’s the publishing companies that want to put up the paywall (and the ones who would make any money from it anyway).
- mapontosevenths 1y ago
  I assumed he read the Illuminatus! Trilogy and wondered where Markoff Chaney's name originated... There might be something wrong with me, now that I think about it. /s
  - reverendsteveii 1y ago
    That's where I first learned about them. NO SMOKING. NO SPITTING. MGMT
- baxtr 1y ago
  3.4 Mio views in 4 days. Wow…
  - stronglikedan 1y ago
    Veritasium is quality content. Those eyes don't hurt nothing either.
    - tbalsam 1y ago
      They unfortunately recently (last few years) sold out to private equity (which tends to glaze over fundamentals and tries to pump out massive content using previous brand quality to give it credence), so beware of quality in more recent vids: https://youtu.be/hJ-rRXWhElI?si=Zdsj9i_raNLnajzi https://youtu.be/hJ-rRXWhElI?si=Zdsj9i_raNLnajzi
      - fn-mote 1y ago
        Yesterday I was reading comments about how the market could pay for research and avoid the “distorting effects” of public funding. Is there any way to get a better outcome for the public here, or is “do good stuff then sell out” the way it’s always going to be?
        edwardbernays 1y ago
        What distorting effects of public funding? What about the distortionary effects of the market? I'll offer the suggestion that what you read is brainrotting private market propaganda designed to erode the public institutions that make America happier, healthier, and wealthier.
        tomrod 1y ago
        In economics discussions regarding public funding policy, the concern of "crowding out" commercial firms or nonprofits is a real concern. It's definitely an observed, measured, and reported phenomenon. In the end, incentives matter. https://en.wikipedia.org/wiki/Crowding_out_(economics) https://en.wikipedia.org/wiki/Crowding_out_(economics)
- jgalt212 1y ago
  Top comment on the video gave me a chuckle. > I wonder if Markov chains could predict how many times Veritasium changes the thumbnail and title of this video.
  - anitil 1y ago
    I think I remember he did a video explaining that changing the title and thumbnail gives a significant bump in views so that a video can become evergreen. CGP Grey mentioned doing this and hitting 1B total views years earlier than he expected
    - jgalt212 1y ago
      Yeah, I didn't think he was doing it for his health.
- 0xDEAFBEAD 1y ago
  Honestly a pretty bad video by Veritasium standards. Consider the nuclear reaction metaphor. It's clearly not memoryless. Eventually you'll run out of fissile material. The diagram for that example is bad as well. Do arrows correspond to state transitions? Or do they correspond to forks in the process where one neutron results in two?
  - mrlongroots 1y ago
    > Consider the nuclear reaction metaphor. It's clearly not memoryless. Eventually you'll run out of fissile material. I think no real process is memoryless: time passes/machines degrade/human behaviors evolve. It is always an approximation that is found/assumed to hold within the modeled timeframe.
    - 0xDEAFBEAD 1y ago
      Sure but it's still the case that if you treat the reaction as memoryless, your model's predictions will be wildly wrong. It's not a good model in this case.
      - mrlongroots 1y ago
        It seems that most approaches treat neutron diffusion as memoryless (or at least stochastic): https://en.wikipedia.org/wiki/Neutron_transport https://en.wikipedia.org/wiki/Neutron_transport
stevenAthompson 1y ago
Here's a direct link to a PDF. http://math.uchicago.edu/~shmuel/Network-course-readings/Markov_chain_tricks.pdf http://math.uchicago.edu/~shmuel/Network-course-readings/Mar...
- tomhow 1y ago
  Updated, thanks!
tantalor 1y ago
(2007)
- Iwan-Zotow 1y ago
  And? MC didn't change much, did they?
  - taeric 1y ago
    Putting the date is often a good affordance to help people scanning the headlines know if they have seen this one before. It is not, necessarily, meant as a knock against it.
    - gertlex 1y ago
      Especially with academic papers where publish dates are often not easy to find in a super-quick skim. (there's a copyright 2007 at the bottom of the linked page, which isn't explicitly "published in 2007" in my mind)
postit 1y ago
Markov Chains are a gateway drug to more advanced probabilistic graphic models which are worth exploring. I still remember working throughout Koller&Friedman cover to cover as one of the best learning experiences I’ve ever had.
- notrealyme123 1y ago
  Just bought it last week. This book just makes me happy. It feels like bishops pattern recognition but with a clearer tone (and a different field of course)
- roadside_picnic 1y ago
  PGMs are a great topic to explore (and Koller+Friedman is a great book), but, as a word of caution to anyone interested: implementation of any of these more advanced models remains a major challenge. For anyone building production facing models, even if your problem is a pretty good match for the more interesting PGMs, the engineering requirements alone are a good reason not to go too far down that path. The PGM book is also structured very clearly for researchers in PGMs. The book is laid out in 3 major section: the models, inference techniques (the bulk of the book), and learning. Which means, if you follow the logic of the book, you basically have to work through 1000+ pages of content before you can actually start running even toy versions of these models. If you do need to get into the nitty-gritty of particular inference algorithms, I don't believe there is another textbook with nearly the level of scope and detail. Bishop's section on PGMs from Pattern Recognition and Machine Learning is probably a better place to start learning about these more advanced models, and if you become very interested then Koller+Friedman will be an invaluable text. It's worth noting that the PGM course taught by Koller was one of the initial, and still very excellent, Coursera courses. I'm not sure if it's still free, but it was a nice way to get a deep dive into the topic in a reasonably short time frame (I do remember those homeworks as brutal though!)[0]. 0. https://www.coursera.org/specializations/probabilistic-graphical-models https://www.coursera.org/specializations/probabilistic-graph...
  - yanovskishai 1y ago
    Played with Bayesian nets a bit in grad school—Pearl’s causality stuff is still mind-blowing—but I’ve almost never bumped into a PGM in production. A couple things kept biting us: Inference pain. Exact is NP-hard, and the usual hacks (loopy BP, variational, MCMC) need a ton of hand-tuning before they run fast enough. The data never fits the graph. Real-world tables are messy and full of hidden junk, so you either spend weeks arguing over structure or give up the nice causal story. DL stole the mind-share. A transformer is a one-liner with a mature tooling stack; hard to argue with that when deadlines loom. That said, they’re not completely dead - reportedly Microsoft’s TrueSkill (Xbox ranking), a bunch of Google ops/diagnosis pipelines, some healthcare diagnosis tools by IBM Watson built on Infer.NET. Anyone here actually shipped a PGM that beat a neural baseline? Would really love to appreciate your war stories.
mindcrime 1y ago
Heh, somebody watched that same Veritasium video about Markov Chains and Monte Carlo methods. Great video; lots of interesting historical stuff in there that I didn't know (like the feud between Markov and Nekrasov).
- carlmcqueen 1y ago
  For awhile I was working on Monte Carlo sims in my job in finance in my early career. Just re-building a existing archaic excel monster in python to be more flexible to new investment models and implement and allow for more levers. Since I was already working with them daily I begin applying Monte Carlo models to a lot more problems I was thinking about. It truly is a fun tool to play with, especially when you're in the thick of designing them.
amelius 1y ago
If you're holding a hammer every problem looks like a nail ...
- tempodox 1y ago
  Yea, if it were true, then Markov chains on steroids (LLMs) would be super at problem solving, but they can't even reason. And they get worse if you add random facts about cats: https://news.ycombinator.com/item?id=44724238 https://news.ycombinator.com/item?id=44724238
  - CrazyStat 1y ago
    That doesn’t follow at all, but I guess don’t pass up any opportunity to bash LLMs.
  - ducktective 1y ago
    LLMs are Markov Chains on steroids? By the way, does anyone know which model or type of model was used in winning gold in IMO?
    - magicalhippo 1y ago
      > LLMs are Markov Chains on steroids? Might be a reference to this[1] blog post which was posted here[2] a year ago. There has also been some academic work linking the two, like this[3] paper. [1]: https://elijahpotter.dev/articles/markov_chains_are_the_original_language_models https://elijahpotter.dev/articles/markov_chains_are_the_orig... [2]: https://news.ycombinator.com/item?id=39213410 https://news.ycombinator.com/item?id=39213410 [3]: https://arxiv.org/abs/2410.02724 https://arxiv.org/abs/2410.02724
    - roadside_picnic 1y ago
      > LLMs are Markov Chains on steroids? It's not an unreasonable view, at least for decoder-only LLMs (which is what most popular LLMs are). While it may seem they violate the Markov property since they clearly do make use of their history, in practice that entire history is summarized in an embedding passed into the decoder. I.e.just like a Markov chain their entire history is compressed into a single point which leaves them conditionally independent of their past given their present state. It's worth noting that this claim is NOT generally applicable to LLMs since both encoder/decoder and encoder-only LLMs do violate the Markov property and therefore cannot be properly considered Markov chains in a meaningful way. But running inference on decoder only model is, at a high enough level of abstraction, is conceptually the same as running a Markov chain (on steroids).
naasking 1y ago
Unless the problem is "quantum mechanics", then that reduces to non-Markovian processes with unistochastic laws, and ironically, this makes for a causally local QM: https://arxiv.org/abs/2402.16935v1 https://arxiv.org/abs/2402.16935v1
Pamar 1y ago
I am on the move so I cannot check the video (but I did skim the pdf). Is there any chance to see an example of this technique? Just a toy/trivial example would be great, TIA!
- mindcrime 1y ago
  For the Monte Carlo Method stuff in particular[1], I get the sense that the most iconic "Hello, World" example is using MC to calculate the value of pi. I can't explain it in detail from memory, but it's approximately something like this: Define a square of some known size (1x1 should be fine, I think) Inscribe a circle inside the square Generate random points inside the square Look at how many fall inside the square but not the circle, versus the ones that do fall in the circle. From that, using what you know about the area of the square and circle respectively, the ratio of "inside square but not in circle" and "inside circle" points can be used to set up an equation for the value of pi. Somebody who's more familiar with this than me can probably fix the details I got wrong, but I think that's the general spirit of it. For Markov Chains in general, the only thing that jumps to mind for me is generating text for old school IRC bots. :-) [1]: which is probably not the point of this essay. For for muddying the waters, I have both concepts kinda 'top of mind' in my head right now after watching the Veritasium video.
  - ilyakaminsky 1y ago
    TIL, thanks! I asked Claude to generate a simulator [1] based on your comment. I think it came out well. [1] https://claude.ai/public/artifacts/1b921a50-897e-4d9e-8cfa-0b1c32a35704 https://claude.ai/public/artifacts/1b921a50-897e-4d9e-8cfa-0...
    - mindcrime 1y ago
      Righteous!
  - jldugger 1y ago
    > From that, using what you know about the area of the square and circle respectively, the ratio of "inside square but not in circle" and "inside circle" points can be used to set up an equation for the value of pi. Back in like 9th grade, when Wikipedia did not yet exist (but MathWorld and IRC did) I did this with TI-Basic instead of paying attention in geometry class. It's cool, but converges hilariously slowly. The in versus out formula is basically distance from origin > 1, but you end up double sampling a lot using randomness. I told a college roommate about it and he basically invented a calculus approach summing pixels in columns or something as an optimization. You could probably further optimize by finding upper and lower bounds of the "frontier" of the circle, or iteratively splitting rectangle slices in infinitum, but thats probably just reinventing state of the art. And all this skips the cool random sampling the monte carlo algorithm uses.
nyeah 1y ago
I mean, often, sure. Also problem solving is often a matter of making a spreadsheet full of +, -, *, / operations. Problem solving is often a matter of counting permutations and combinations. It's often a matter of setting up the right system of ordinary differential equations. It's often a matter of setting up the right linear algebra problem. It's often a matter of asking the right person what technique works. It's often a matter of making a measurement before getting lost in the math. It's often a matter of finding the right paper in the literature.
theturtletalks 1y ago
The Veritasium video brought up an interesting point about how LLMs, if trained too much on their own content, will fall victim to the Markov Chain and just repeat the same thing over and over. Is this still possible with the latest models being trained on synthetic data? And if it possible, what would that one phrase be?
- roadside_picnic 1y ago
  That original model collapse paper has largely been misunderstood and in practice, this is only true if you're not curating the generated data at all. The original paper even specifies (emphasis mine): > We find that indiscriminate use of model-generated content in training causes irreversible defects in the resulting models, in which tails of the original content distribution disappear. [0] In practice nobody is "indiscriminately" using model output to fine-tune models since that doesn't even make sense. Even if you're harvesting web data generated by LLMs, that data has in fact been curated by it's acceptance on whatever platform you found it on is a form of curation. There was a very recent paper Supervised Fine Tuning on Curated Data is Reinforcement Learning (and can be improved) [1] whose content is pretty well summarized by the title. So long as the data is curated in some way, you are providing more information to the model and the results should improve somewhat. 0. https://www.nature.com/articles/s41586-024-07566-y https://www.nature.com/articles/s41586-024-07566-y 1. https://www.arxiv.org/pdf/2507.12856 https://www.arxiv.org/pdf/2507.12856 edit: updated based on cooksnoot's comment
  - cootsnuck 1y ago
    There's multiple papers on model collapse. Being able to avoid model collapse is different from it "being disproven". If you just mean its risk has been over exaggerated and/or over simplified then yea, you'd have a point.
    - roadside_picnic 1y ago
      Fair point, I've updated the post to highlight that even the original paper specifics "indiscriminate" use of model outputs. Having spent quite a bit of time diving into many questionable "research" papers (the original model collapse paper is not actually one of these, it's a solid paper), there's a very common pattern of showing that something does or does not work under special conditions but casually making generalized claims about those results. It's so easy with LLMs to find a way to get the result you want that there are far too many papers out there that people quickly take as fact when the claims are much, much weaker than the papers let on. So I tend to get a bit reactionary when addressing many of these "facts" about LLMs. But you are correct that with the model collapse paper this is much more the public misunderstanding the claims of the original paper than any fault with that paper itself.
AnotherGoodName 1y ago
I feel like we need a video on Dynamic Markov Chains. It's a method to create a markov chain from data. It's used in all the highest compression winners in the Hutter Prize (a competition to compress data the most).
- jadbox 1y ago
  Make your own video then :)
- atiedebee 1y ago
  You mean the algorithm used in hook[0]? These are not really top performers anymore. PPM has generally performed better and nowadays it's LLMs and context mixers that are at the top of text compression[1] [0]: https://mattmahoney.net/dc/dce.html#Section_421 https://mattmahoney.net/dc/dce.html#Section_421 [1]: https://mattmahoney.net/dc/text.html https://mattmahoney.net/dc/text.html
  - AnotherGoodName 1y ago
    DMC is used in pretty much all of these, just not alone (that alg column is too small to capture this). As in go into the first open source entry which is #2 in this list, cmix, unzip the files, go into paq8.cpp and search for DMC. See "Model using DMC (Dynamic Markov Compression)" and associated code. In these cases DMC is one model mixed in with others and the best model for the current context is used. Hook exclusively uses DMC for outstanding results but the others use DMC as one of the prediction models.
1vuio0pswjnm7 1y ago
Note to file: No one is complaining about the absence of [PDF] from the title. Possible that time of submission is a factor. For example, https://news.ycombinator.com/item?id=44574033 https://news.ycombinator.com/item?id=44574033
- gnabgib 1y ago
  Wasn't the submitted URL: https://news.ycombinator.com/item?id=44734162 https://news.ycombinator.com/item?id=44734162

301 points by Alifatisk 1y ago

I assume OP watched this excellent Veritasium video about Markov and his chains [0] and posted this article which was referenced in that video. [0] https://youtu.be/KZeIEiBrT_w https://youtu.be/KZeIEiBrT_w

Alifatisk 1y ago
You nailed it, I wanted to post the actual article but found that they where behind a paywall, and I don't know if pirated content is allowed to share here but it's definitely worth a read though!
- danlitt 1y ago
  It is often not piracy to find open copies of papers; the authors often publish them directly (on their personal pages or on arxiv). A commenter further down found a public link: https://math.uchicago.edu/~shmuel/Network-course-readings/Markov_chain_tricks.pdf https://math.uchicago.edu/~shmuel/Network-course-readings/Ma...
  - denverllc 1y ago
    Yeah, most authors are not concerned about their papers being shared because what they care about is citations, not money. It’s the publishing companies that want to put up the paywall (and the ones who would make any money from it anyway).
mapontosevenths 1y ago
I assumed he read the Illuminatus! Trilogy and wondered where Markoff Chaney's name originated... There might be something wrong with me, now that I think about it. /s
- reverendsteveii 1y ago
  That's where I first learned about them. NO SMOKING. NO SPITTING. MGMT
baxtr 1y ago
3.4 Mio views in 4 days. Wow…
- stronglikedan 1y ago
  Veritasium is quality content. Those eyes don't hurt nothing either.
  - tbalsam 1y ago
    They unfortunately recently (last few years) sold out to private equity (which tends to glaze over fundamentals and tries to pump out massive content using previous brand quality to give it credence), so beware of quality in more recent vids: https://youtu.be/hJ-rRXWhElI?si=Zdsj9i_raNLnajzi https://youtu.be/hJ-rRXWhElI?si=Zdsj9i_raNLnajzi
    - fn-mote 1y ago
      Yesterday I was reading comments about how the market could pay for research and avoid the “distorting effects” of public funding. Is there any way to get a better outcome for the public here, or is “do good stuff then sell out” the way it’s always going to be?
      - edwardbernays 1y ago
        What distorting effects of public funding? What about the distortionary effects of the market? I'll offer the suggestion that what you read is brainrotting private market propaganda designed to erode the public institutions that make America happier, healthier, and wealthier.
        tomrod 1y ago
        In economics discussions regarding public funding policy, the concern of "crowding out" commercial firms or nonprofits is a real concern. It's definitely an observed, measured, and reported phenomenon. In the end, incentives matter. https://en.wikipedia.org/wiki/Crowding_out_(economics) https://en.wikipedia.org/wiki/Crowding_out_(economics)
jgalt212 1y ago
Top comment on the video gave me a chuckle. > I wonder if Markov chains could predict how many times Veritasium changes the thumbnail and title of this video.
- anitil 1y ago
  I think I remember he did a video explaining that changing the title and thumbnail gives a significant bump in views so that a video can become evergreen. CGP Grey mentioned doing this and hitting 1B total views years earlier than he expected
  - jgalt212 1y ago
    Yeah, I didn't think he was doing it for his health.
0xDEAFBEAD 1y ago
Honestly a pretty bad video by Veritasium standards. Consider the nuclear reaction metaphor. It's clearly not memoryless. Eventually you'll run out of fissile material. The diagram for that example is bad as well. Do arrows correspond to state transitions? Or do they correspond to forks in the process where one neutron results in two?
- mrlongroots 1y ago
  > Consider the nuclear reaction metaphor. It's clearly not memoryless. Eventually you'll run out of fissile material. I think no real process is memoryless: time passes/machines degrade/human behaviors evolve. It is always an approximation that is found/assumed to hold within the modeled timeframe.
  - 0xDEAFBEAD 1y ago
    Sure but it's still the case that if you treat the reaction as memoryless, your model's predictions will be wildly wrong. It's not a good model in this case.
    - mrlongroots 1y ago
      It seems that most approaches treat neutron diffusion as memoryless (or at least stochastic): https://en.wikipedia.org/wiki/Neutron_transport https://en.wikipedia.org/wiki/Neutron_transport

stevenAthompson 1y ago

Here's a direct link to a PDF. http://math.uchicago.edu/~shmuel/Network-course-readings/Markov_chain_tricks.pdf http://math.uchicago.edu/~shmuel/Network-course-readings/Mar...

tomhow 1y ago
Updated, thanks!

tantalor 1y ago

(2007)

Iwan-Zotow 1y ago
And? MC didn't change much, did they?
- taeric 1y ago
  Putting the date is often a good affordance to help people scanning the headlines know if they have seen this one before. It is not, necessarily, meant as a knock against it.
  - gertlex 1y ago
    Especially with academic papers where publish dates are often not easy to find in a super-quick skim. (there's a copyright 2007 at the bottom of the linked page, which isn't explicitly "published in 2007" in my mind)

postit 1y ago

Markov Chains are a gateway drug to more advanced probabilistic graphic models which are worth exploring. I still remember working throughout Koller&Friedman cover to cover as one of the best learning experiences I’ve ever had.

notrealyme123 1y ago
Just bought it last week. This book just makes me happy. It feels like bishops pattern recognition but with a clearer tone (and a different field of course)
roadside_picnic 1y ago
PGMs are a great topic to explore (and Koller+Friedman is a great book), but, as a word of caution to anyone interested: implementation of any of these more advanced models remains a major challenge. For anyone building production facing models, even if your problem is a pretty good match for the more interesting PGMs, the engineering requirements alone are a good reason not to go too far down that path. The PGM book is also structured very clearly for researchers in PGMs. The book is laid out in 3 major section: the models, inference techniques (the bulk of the book), and learning. Which means, if you follow the logic of the book, you basically have to work through 1000+ pages of content before you can actually start running even toy versions of these models. If you do need to get into the nitty-gritty of particular inference algorithms, I don't believe there is another textbook with nearly the level of scope and detail. Bishop's section on PGMs from Pattern Recognition and Machine Learning is probably a better place to start learning about these more advanced models, and if you become very interested then Koller+Friedman will be an invaluable text. It's worth noting that the PGM course taught by Koller was one of the initial, and still very excellent, Coursera courses. I'm not sure if it's still free, but it was a nice way to get a deep dive into the topic in a reasonably short time frame (I do remember those homeworks as brutal though!)[0]. 0. https://www.coursera.org/specializations/probabilistic-graphical-models https://www.coursera.org/specializations/probabilistic-graph...
- yanovskishai 1y ago
  Played with Bayesian nets a bit in grad school—Pearl’s causality stuff is still mind-blowing—but I’ve almost never bumped into a PGM in production. A couple things kept biting us: Inference pain. Exact is NP-hard, and the usual hacks (loopy BP, variational, MCMC) need a ton of hand-tuning before they run fast enough. The data never fits the graph. Real-world tables are messy and full of hidden junk, so you either spend weeks arguing over structure or give up the nice causal story. DL stole the mind-share. A transformer is a one-liner with a mature tooling stack; hard to argue with that when deadlines loom. That said, they’re not completely dead - reportedly Microsoft’s TrueSkill (Xbox ranking), a bunch of Google ops/diagnosis pipelines, some healthcare diagnosis tools by IBM Watson built on Infer.NET. Anyone here actually shipped a PGM that beat a neural baseline? Would really love to appreciate your war stories.

mindcrime 1y ago

Heh, somebody watched that same Veritasium video about Markov Chains and Monte Carlo methods. Great video; lots of interesting historical stuff in there that I didn't know (like the feud between Markov and Nekrasov).

carlmcqueen 1y ago
For awhile I was working on Monte Carlo sims in my job in finance in my early career. Just re-building a existing archaic excel monster in python to be more flexible to new investment models and implement and allow for more levers. Since I was already working with them daily I begin applying Monte Carlo models to a lot more problems I was thinking about. It truly is a fun tool to play with, especially when you're in the thick of designing them.

amelius 1y ago

If you're holding a hammer every problem looks like a nail ...

tempodox 1y ago
Yea, if it were true, then Markov chains on steroids (LLMs) would be super at problem solving, but they can't even reason. And they get worse if you add random facts about cats: https://news.ycombinator.com/item?id=44724238 https://news.ycombinator.com/item?id=44724238
- CrazyStat 1y ago
  That doesn’t follow at all, but I guess don’t pass up any opportunity to bash LLMs.
- ducktective 1y ago
  LLMs are Markov Chains on steroids? By the way, does anyone know which model or type of model was used in winning gold in IMO?
  - magicalhippo 1y ago
    > LLMs are Markov Chains on steroids? Might be a reference to this[1] blog post which was posted here[2] a year ago. There has also been some academic work linking the two, like this[3] paper. [1]: https://elijahpotter.dev/articles/markov_chains_are_the_original_language_models https://elijahpotter.dev/articles/markov_chains_are_the_orig... [2]: https://news.ycombinator.com/item?id=39213410 https://news.ycombinator.com/item?id=39213410 [3]: https://arxiv.org/abs/2410.02724 https://arxiv.org/abs/2410.02724
  - roadside_picnic 1y ago
    > LLMs are Markov Chains on steroids? It's not an unreasonable view, at least for decoder-only LLMs (which is what most popular LLMs are). While it may seem they violate the Markov property since they clearly do make use of their history, in practice that entire history is summarized in an embedding passed into the decoder. I.e.just like a Markov chain their entire history is compressed into a single point which leaves them conditionally independent of their past given their present state. It's worth noting that this claim is NOT generally applicable to LLMs since both encoder/decoder and encoder-only LLMs do violate the Markov property and therefore cannot be properly considered Markov chains in a meaningful way. But running inference on decoder only model is, at a high enough level of abstraction, is conceptually the same as running a Markov chain (on steroids).

naasking 1y ago

Unless the problem is "quantum mechanics", then that reduces to non-Markovian processes with unistochastic laws, and ironically, this makes for a causally local QM: https://arxiv.org/abs/2402.16935v1 https://arxiv.org/abs/2402.16935v1

Pamar 1y ago

I am on the move so I cannot check the video (but I did skim the pdf). Is there any chance to see an example of this technique? Just a toy/trivial example would be great, TIA!

mindcrime 1y ago
For the Monte Carlo Method stuff in particular[1], I get the sense that the most iconic "Hello, World" example is using MC to calculate the value of pi. I can't explain it in detail from memory, but it's approximately something like this: Define a square of some known size (1x1 should be fine, I think) Inscribe a circle inside the square Generate random points inside the square Look at how many fall inside the square but not the circle, versus the ones that do fall in the circle. From that, using what you know about the area of the square and circle respectively, the ratio of "inside square but not in circle" and "inside circle" points can be used to set up an equation for the value of pi. Somebody who's more familiar with this than me can probably fix the details I got wrong, but I think that's the general spirit of it. For Markov Chains in general, the only thing that jumps to mind for me is generating text for old school IRC bots. :-) [1]: which is probably not the point of this essay. For for muddying the waters, I have both concepts kinda 'top of mind' in my head right now after watching the Veritasium video.
- ilyakaminsky 1y ago
  TIL, thanks! I asked Claude to generate a simulator [1] based on your comment. I think it came out well. [1] https://claude.ai/public/artifacts/1b921a50-897e-4d9e-8cfa-0b1c32a35704 https://claude.ai/public/artifacts/1b921a50-897e-4d9e-8cfa-0...
  - mindcrime 1y ago
    Righteous!
- jldugger 1y ago
  > From that, using what you know about the area of the square and circle respectively, the ratio of "inside square but not in circle" and "inside circle" points can be used to set up an equation for the value of pi. Back in like 9th grade, when Wikipedia did not yet exist (but MathWorld and IRC did) I did this with TI-Basic instead of paying attention in geometry class. It's cool, but converges hilariously slowly. The in versus out formula is basically distance from origin > 1, but you end up double sampling a lot using randomness. I told a college roommate about it and he basically invented a calculus approach summing pixels in columns or something as an optimization. You could probably further optimize by finding upper and lower bounds of the "frontier" of the circle, or iteratively splitting rectangle slices in infinitum, but thats probably just reinventing state of the art. And all this skips the cool random sampling the monte carlo algorithm uses.

nyeah 1y ago

I mean, often, sure. Also problem solving is often a matter of making a spreadsheet full of +, -, *, / operations. Problem solving is often a matter of counting permutations and combinations. It's often a matter of setting up the right system of ordinary differential equations. It's often a matter of setting up the right linear algebra problem. It's often a matter of asking the right person what technique works. It's often a matter of making a measurement before getting lost in the math. It's often a matter of finding the right paper in the literature.

theturtletalks 1y ago

The Veritasium video brought up an interesting point about how LLMs, if trained too much on their own content, will fall victim to the Markov Chain and just repeat the same thing over and over. Is this still possible with the latest models being trained on synthetic data? And if it possible, what would that one phrase be?

roadside_picnic 1y ago
That original model collapse paper has largely been misunderstood and in practice, this is only true if you're not curating the generated data at all. The original paper even specifies (emphasis mine): > We find that indiscriminate use of model-generated content in training causes irreversible defects in the resulting models, in which tails of the original content distribution disappear. [0] In practice nobody is "indiscriminately" using model output to fine-tune models since that doesn't even make sense. Even if you're harvesting web data generated by LLMs, that data has in fact been curated by it's acceptance on whatever platform you found it on is a form of curation. There was a very recent paper Supervised Fine Tuning on Curated Data is Reinforcement Learning (and can be improved) [1] whose content is pretty well summarized by the title. So long as the data is curated in some way, you are providing more information to the model and the results should improve somewhat. 0. https://www.nature.com/articles/s41586-024-07566-y https://www.nature.com/articles/s41586-024-07566-y 1. https://www.arxiv.org/pdf/2507.12856 https://www.arxiv.org/pdf/2507.12856 edit: updated based on cooksnoot's comment
- cootsnuck 1y ago
  There's multiple papers on model collapse. Being able to avoid model collapse is different from it "being disproven". If you just mean its risk has been over exaggerated and/or over simplified then yea, you'd have a point.
  - roadside_picnic 1y ago
    Fair point, I've updated the post to highlight that even the original paper specifics "indiscriminate" use of model outputs. Having spent quite a bit of time diving into many questionable "research" papers (the original model collapse paper is not actually one of these, it's a solid paper), there's a very common pattern of showing that something does or does not work under special conditions but casually making generalized claims about those results. It's so easy with LLMs to find a way to get the result you want that there are far too many papers out there that people quickly take as fact when the claims are much, much weaker than the papers let on. So I tend to get a bit reactionary when addressing many of these "facts" about LLMs. But you are correct that with the model collapse paper this is much more the public misunderstanding the claims of the original paper than any fault with that paper itself.

AnotherGoodName 1y ago

I feel like we need a video on Dynamic Markov Chains. It's a method to create a markov chain from data. It's used in all the highest compression winners in the Hutter Prize (a competition to compress data the most).

jadbox 1y ago
Make your own video then :)
atiedebee 1y ago
You mean the algorithm used in hook[0]? These are not really top performers anymore. PPM has generally performed better and nowadays it's LLMs and context mixers that are at the top of text compression[1] [0]: https://mattmahoney.net/dc/dce.html#Section_421 https://mattmahoney.net/dc/dce.html#Section_421 [1]: https://mattmahoney.net/dc/text.html https://mattmahoney.net/dc/text.html
- AnotherGoodName 1y ago
  DMC is used in pretty much all of these, just not alone (that alg column is too small to capture this). As in go into the first open source entry which is #2 in this list, cmix, unzip the files, go into paq8.cpp and search for DMC. See "Model using DMC (Dynamic Markov Compression)" and associated code. In these cases DMC is one model mixed in with others and the best model for the current context is used. Hook exclusively uses DMC for outstanding results but the others use DMC as one of the prediction models.

1vuio0pswjnm7 1y ago

Note to file: No one is complaining about the absence of [PDF] from the title. Possible that time of submission is a factor. For example, https://news.ycombinator.com/item?id=44574033 https://news.ycombinator.com/item?id=44574033

gnabgib 1y ago
Wasn't the submitted URL: https://news.ycombinator.com/item?id=44734162 https://news.ycombinator.com/item?id=44734162