5 ms·

when this first hit hn it had an enormous rank of 1070, and the comments are all about the breakthrough importance of markov chains for those who follow.. is t

when this first hit hn it had an enormous rank of 1070, and the comments are all about the breakthrough importance of markov chains for those who follow.. is this still the case? i feel like i hear less and less about markov chains are they still in research and use? is page rank still the most prominent search algo? does page rank still use markov models? i always felt these probabilistic models were a conflation of correlation and causation

kastnerkyle 11y ago
RNNs (recurrent neural networks) can be seen as generalizations of Markov chains - or as I prefer think of it, Markov chains are very limited RNNs. There is an enormous amount of research happening around these sequential models (and differentiable DAGs (directed acyclic graphs) aka neural networks in general) these days. Markov chains have never (in the work I have seen at least) tried to imply causation - purely correlation/probability. There is other recent research on causality (see the work of Pearl), but just because one thing very likely follows another doesn't mean the preceding event "caused" the next one, as both events could be side effects from the same (unobserved) root cause.
- justifier 11y ago
  but the difference between neural nets and markov chains is the probabilistic element of nn is the optimal traversal and could be replaced with a perfect algo if one were found to be computationally feasable whereas markov chains start from a place of probability and require it the construction stage of the markov model agrees with your statement: > just because one thing very likely follows another doesn't mean the preceding event "caused" the next one but when in use the current state is the cause of the following state informed by your model nn can simulate a system whereas an mc can only simulate data from a system
  - kastnerkyle 11y ago
    RNNs are optimizing a probability, at least with standard training to maximize likelihood. As you say, with a different training criterion sure it could do something different - but so could a Markov chain if it was built to optimize a different objective (though it wouldn't be a Markov chain anymore I don't think). Look at reinforcement learning - loads of stuff making the Markov assumption and doing quite well on complex tasks, though once again this is quite different than a Markov chain. In theory (at least my opinion on theory) if we had an infinite size "state" it would be possible to just encode all past information in every state, and use Markov rules. It is just not practical, and much easier to extend lookup to multiple timesteps in the past especially with better understanding of optimizing things like RNNs. Choosing the maximum p(X_t+1 | X_t) does not infer causality in any way in my mind - only saying that given the data when X_t happens, some event at X_t+1 is likely to happen. Classic correlation. I don't see where you are seeing causality in that part. I also don't see a distinction in simulating a system and data from a system - to me it is just that NNs can model much more complex systems than typical Markov chains. In general I agree with you, but I find these two concepts are much, much more similar than they are different.
    - justifier 11y ago
      > but so could a Markov chain if it was built to optimize a different objective (though it wouldn't be a Markov chain anymore I don't think). i wanted to think about this, and i thought maybe you could have a purely markov model if it were a self constructing self similar model a markov fractal at each event the chain reconstructs itself from its new perspective in the fractal but even done elegantly i think it would be more undue overhead to constantly reconstruct the model than just feeding a self similar model constantly reconstructed inputs, which i see a more clear affinity to neural networks or something wholly different than either
sillysaurus3 11y ago
This isn't quite related to your question, but I think Markov chains made their debut in the original information theory paper by Shannon: http://worrydream.com/refs/Shannon%20-%20A%20Mathematical%20Theory%20of%20Communication.pdf http://worrydream.com/refs/Shannon%20-%20A%20Mathematical%20... It doesn't necessarily matter whether they're still in use. All of these tools are worth learning, so that if a problem ever comes up that can be solved by markov chaining, you'll know it right away. Same for all the other tools, though. And there are a lot of them.
- jamessb 11y ago
  This isn't quite related to your question, but I think Markov chains made their debut in the original information theory paper by Shannon What? That paper even says: Stochastic processes of the type described above are known mathematically as discrete Markoff processes and have been extensively studied in the literature; the corresponding footnote says "For a detailed treatment see M. Frechet ... 1938".
  - sillysaurus3 11y ago
    Always happy to be wrong, as it means I've learned. Thanks.
jamessb 11y ago
the breakthrough importance of markov chains i feel like i hear less and less about markov chains are they still in research and use? Markov chains will always be important, because they are a fairly fundamental concept (going back to the early 20th century). They idea is certainly still widely used: two major classes of applications are Hidden Markov Models (where you attempt to infer the hidden state of a system from observations that depend on the state) [1], and Markov-Chain Monte Carlo (MCMC) [2] (where you sample from a probability distribution function by constructing a markov chain whose equilibrium distibution is that distribution). is page rank still the most prominent search algo? PageRank is really a ranking algorithm, rather than a search algorithm. It's been applied to many things other than web searching, and has many variants (e.g. see the review article "PageRank Beyond the Web" [3). That said, Google rankings depend on many things other than PageRank. i always felt these probabilistic models were a conflation of correlation and causation What do you mean? [1]: https://en.wikipedia.org/wiki/Hidden_Markov_model#Applications https://en.wikipedia.org/wiki/Hidden_Markov_model#Applicatio... [2]: https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo [3]: http://epubs.siam.org/doi/10.1137/140976649 http://epubs.siam.org/doi/10.1137/140976649
- justifier 11y ago
  > i always felt these probabilistic models were a conflation of correlation and causation > What do you mean? the example from the post of weather events is a simplified version of what i mean the collected data expresses that there is a probability of 50/50 rain versus shine the first string of possible outputs is scattered and more random than the real data, so weights are introduced to nuance to the output and the second string is more closely representative of the data but this introduces a relative psuedo causation, what the author refers to as stickyness it's reminiscent of the monty hall problem(o) altering the state of the model causes its probability to change relative to a specific potential, but only within the limited scope of the probable space choosing one door causes the probabilities associated with the state to change but the system itself is unchanged by the choice and what you see with the weather is a simulation of the collected data stead the underlying system, which i feel conflates correlation with causation (o) https://en.wikipedia.org/wiki/Monty_Hall_problem https://en.wikipedia.org/wiki/Monty_Hall_problem
smac8 11y ago
Just to add a comment on page rank, from what I've heard that is a actually a very small contributor to the overall google algorithm. That is - at least in the way it was originally conceived by Larry Page - PageRank is now only a minuscule tuner amongst 100's of other tuners in the overall search algorithm now, but because it was the first and core part of the google algorithm, people still continue to assume it is the predominant one.
thaw13579 11y ago
They're widely used for error correcting codes and MCMC and are generally important for modeling any kind of discrete sequential process. I guess the theory is well understood though, so deep learning etc. gets more attention.

kastnerkyle 11y ago

RNNs (recurrent neural networks) can be seen as generalizations of Markov chains - or as I prefer think of it, Markov chains are very limited RNNs. There is an enormous amount of research happening around these sequential models (and differentiable DAGs (directed acyclic graphs) aka neural networks in general) these days. Markov chains have never (in the work I have seen at least) tried to imply causation - purely correlation/probability. There is other recent research on causality (see the work of Pearl), but just because one thing very likely follows another doesn't mean the preceding event "caused" the next one, as both events could be side effects from the same (unobserved) root cause.

justifier 11y ago
but the difference between neural nets and markov chains is the probabilistic element of nn is the optimal traversal and could be replaced with a perfect algo if one were found to be computationally feasable whereas markov chains start from a place of probability and require it the construction stage of the markov model agrees with your statement: > just because one thing very likely follows another doesn't mean the preceding event "caused" the next one but when in use the current state is the cause of the following state informed by your model nn can simulate a system whereas an mc can only simulate data from a system
- kastnerkyle 11y ago
  RNNs are optimizing a probability, at least with standard training to maximize likelihood. As you say, with a different training criterion sure it could do something different - but so could a Markov chain if it was built to optimize a different objective (though it wouldn't be a Markov chain anymore I don't think). Look at reinforcement learning - loads of stuff making the Markov assumption and doing quite well on complex tasks, though once again this is quite different than a Markov chain. In theory (at least my opinion on theory) if we had an infinite size "state" it would be possible to just encode all past information in every state, and use Markov rules. It is just not practical, and much easier to extend lookup to multiple timesteps in the past especially with better understanding of optimizing things like RNNs. Choosing the maximum p(X_t+1 | X_t) does not infer causality in any way in my mind - only saying that given the data when X_t happens, some event at X_t+1 is likely to happen. Classic correlation. I don't see where you are seeing causality in that part. I also don't see a distinction in simulating a system and data from a system - to me it is just that NNs can model much more complex systems than typical Markov chains. In general I agree with you, but I find these two concepts are much, much more similar than they are different.
  - justifier 11y ago
    > but so could a Markov chain if it was built to optimize a different objective (though it wouldn't be a Markov chain anymore I don't think). i wanted to think about this, and i thought maybe you could have a purely markov model if it were a self constructing self similar model a markov fractal at each event the chain reconstructs itself from its new perspective in the fractal but even done elegantly i think it would be more undue overhead to constantly reconstruct the model than just feeding a self similar model constantly reconstructed inputs, which i see a more clear affinity to neural networks or something wholly different than either

sillysaurus3 11y ago

This isn't quite related to your question, but I think Markov chains made their debut in the original information theory paper by Shannon: http://worrydream.com/refs/Shannon%20-%20A%20Mathematical%20Theory%20of%20Communication.pdf http://worrydream.com/refs/Shannon%20-%20A%20Mathematical%20... It doesn't necessarily matter whether they're still in use. All of these tools are worth learning, so that if a problem ever comes up that can be solved by markov chaining, you'll know it right away. Same for all the other tools, though. And there are a lot of them.

jamessb 11y ago
This isn't quite related to your question, but I think Markov chains made their debut in the original information theory paper by Shannon What? That paper even says: Stochastic processes of the type described above are known mathematically as discrete Markoff processes and have been extensively studied in the literature; the corresponding footnote says "For a detailed treatment see M. Frechet ... 1938".
- sillysaurus3 11y ago
  Always happy to be wrong, as it means I've learned. Thanks.

jamessb 11y ago

the breakthrough importance of markov chains i feel like i hear less and less about markov chains are they still in research and use? Markov chains will always be important, because they are a fairly fundamental concept (going back to the early 20th century). They idea is certainly still widely used: two major classes of applications are Hidden Markov Models (where you attempt to infer the hidden state of a system from observations that depend on the state) [1], and Markov-Chain Monte Carlo (MCMC) [2] (where you sample from a probability distribution function by constructing a markov chain whose equilibrium distibution is that distribution). is page rank still the most prominent search algo? PageRank is really a ranking algorithm, rather than a search algorithm. It's been applied to many things other than web searching, and has many variants (e.g. see the review article "PageRank Beyond the Web" [3). That said, Google rankings depend on many things other than PageRank. i always felt these probabilistic models were a conflation of correlation and causation What do you mean? [1]: https://en.wikipedia.org/wiki/Hidden_Markov_model#Applications https://en.wikipedia.org/wiki/Hidden_Markov_model#Applicatio... [2]: https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo [3]: http://epubs.siam.org/doi/10.1137/140976649 http://epubs.siam.org/doi/10.1137/140976649

justifier 11y ago
> i always felt these probabilistic models were a conflation of correlation and causation > What do you mean? the example from the post of weather events is a simplified version of what i mean the collected data expresses that there is a probability of 50/50 rain versus shine the first string of possible outputs is scattered and more random than the real data, so weights are introduced to nuance to the output and the second string is more closely representative of the data but this introduces a relative psuedo causation, what the author refers to as stickyness it's reminiscent of the monty hall problem(o) altering the state of the model causes its probability to change relative to a specific potential, but only within the limited scope of the probable space choosing one door causes the probabilities associated with the state to change but the system itself is unchanged by the choice and what you see with the weather is a simulation of the collected data stead the underlying system, which i feel conflates correlation with causation (o) https://en.wikipedia.org/wiki/Monty_Hall_problem https://en.wikipedia.org/wiki/Monty_Hall_problem

smac8 11y ago

Just to add a comment on page rank, from what I've heard that is a actually a very small contributor to the overall google algorithm. That is - at least in the way it was originally conceived by Larry Page - PageRank is now only a minuscule tuner amongst 100's of other tuners in the overall search algorithm now, but because it was the first and core part of the google algorithm, people still continue to assume it is the predominant one.

thaw13579 11y ago

They're widely used for error correcting codes and MCMC and are generally important for modeling any kind of discrete sequential process. I guess the theory is well understood though, so deep learning etc. gets more attention.