4 ms·

Is there a standard way to build markov chains with deeper memory than just the current state? For example in the rainy sunny markov chain our rainy probability

by rtkwe 8y ago

Is there a standard way to build markov chains with deeper memory than just the current state? For example in the rainy sunny markov chain our rainy probability should/could decrease as the number of rainy days in a row increases. In a pure state machine this would require an infinite number of states for SS...SSS and RR...RRR.

stochastic_monk 8y ago
You’d need some kind of higher structure of computing. One method for longer-term dependence is simply expanding the transition matrix and state space, but that’s not unbounded in any meaningful sense. A recurrent neural network approximates unbounded long-term information for general tasks, but I think what you’re looking for in particular is a push-down automaton, while a Markov chain is a finite-state automaton.
- tree_of_item 8y ago
  See [0] for a way to make recurrent neural nets in to pushdown nets. [0]: https://arxiv.org/abs/1506.02516 https://arxiv.org/abs/1506.02516
  - stochastic_monk 8y ago
    I’m not an expert in nlp or these augmented models. Could you perhaps compare this to Dyer’s Stack LSTM?
    - tree_of_item 8y ago
      I'm not sure how Dyer's thing works, but I can describe the paper I linked to: A "stack" is a stack of (vector, scalar) pairs (a vector and its "weight"). At each time step, the stack has three inputs: the vector to push, the weight to push it with, and the weight to pop off the stack. Its output is the top 1.0 weight of the stack. The stack's behavior on a time step is divided in to three parts: 1. First, that pop weight is removed from the stack. For example, if you want to remove 0.6 from a stack like [(a, 0.4), (b, 0.4)], you'd remove all of a leaving you with 0.2 to remove from b, so the final stack would be [(b, 0.2)]. 2. The pushed vector is placed on the stack with the given push weight. 3. The top 1.0 of the stack is blended together and returned. For example, a stack like [(a, 0.4), (b, 0.4), (c, 0.8)] would take 0.4 of a, 0.4 of b, and 0.2 of c. This process is differentiable, and you can combine this with the usual recurrent loops to make a recurrent stack machine.
      - stochastic_monk 8y ago
        Thank you so much! That makes the paper a lot easier to understand.
S4M 8y ago
By definition, a Markov chain only depends of the current state. That said, I can think of a way to make something depending on the past as well: if you have two states (S for sunny, R for Rainy), with two days of state you now have four states: SS, SR, RS, RR, which gives you a transition probabilities matrix - of course you will have some restriction, for example from SS you can only go to SS and SR.
bena 8y ago
I think one of the features/requirements of Markov chains is that they be stateless. Previous states cannot influence the current probability. It really depends on how granular you want to cut it. You could make 10 rainy states, each with an increased probability of sunny, equal chance to stay or go to a lower probability, and no chance of going to a state with a higher probability. So R90 could be S = 10%, R90 = 45%, and R80 = 45%. R80 could be S = 20%, R80 = 40%, and R70% = 40%. And so on. That way you don't need to track how many days it's been raining, it will naturally filter down to lower rainy percentages until it inevitably goes back to sunny.
gimagon 8y ago
The definition of the Markov property is that the process is memoryless - the probability distribution of the next state only depends on the previous state. This makes them an easy tool to use for mathematical analysis, but limits the amount of things they can model completely. One simple way to add memory is to make states more complex. For example, instead of recording the weather each day as a state, you could record the weather for two day tuples. This allows more complex dynamics, but the number of states quickly increases. Hierarchical Markov Models are another way to achieve this. In a HMM, there is a probability matrix for different types of weather (winter vs summer) and a probability matrix that governs transitions between each of these types.
ColinWright 8y ago
Lots of other commentators are saying that the property of MCs is that they are memory-less, but in fact it's trivial to make a MC have deeper memory: Use tuples. So if you have observations A, B, C, B, C, A, D, A, ... then you form pairs: (A,B), (B,C), (C,B), (B,C), (C,A), (A,D), (D,A), ... Each node in the MC is one of these pairs, and (X,Y) -> (Y,Z) if Z is the new state that appears. The number of states grows very quickly, but if you make the system dynamic then it works fine. This is what you use to randomly generate text using the previous 3 words as a predictor for the next. Then (w0,w1,w2) predicts w3, and your next "state" is (w1,w2,w3). And so on.
- throwawayjava 8y ago
  As a confused undergrad first learning about random dynamical systems on my own (outside of any classes), this really bothered me. How could the Markov assumption be so powerful when it's clearly trivial to add memory and retain the Markov property?! After reading through theorems and proofs for dynamical systems theory, and especially considering applications of that theory, I came up with basically two practical take-aways: 1. Complexity matters and the curse of dimensionality is real. 2. All those nice theorems (stability, convergence, splitting, invariance, bifurcations, ...) are stated with respect to a state space and make assumptions about the dynamics on that state space. So if you code up a state space representation that is history-aware with respect to the dynamics you really care about, then: a) you might lose some theorems that hold for the original process, and b) you sometimes realize the theorems lose a lot of power when they're telling you something about a tuple of things you care about instead of the actual thing you care about. If I ever teach people about random dynamical systems, this explanation will come immediately after the definition of a Markov process and I'll continually remind my audience throughout the course. Understanding what goes wrong when a system is "technically" Markovian is probably the best way to obtain a deep intuition. Or at least, it was very helpful to me.
- dminor 8y ago
  Exactly - even if your process is conceptually a Markov chain, your code doesn't have to explicitly enumerate all of the states. I used a similar scheme to your example, but with letters for generating a word for http://password.supply http://password.supply
abhgh 8y ago
The Markov chains we normally we hear of are first order Markov chains. The general notion being d-order chains. These are hard to compute (too many model parameters) but there has been quite some research on an interesting middle ground: variable length Markov chains.
cosmic_ape 8y ago
The particular behavior you mention can be modeled by a Semi-Markov Model. In these, the time you stay at a given state can be an arbitrary fixed distribution. In a regular chain this time is geometric, so memoryless. But other distributions, with Gaussian like tails or power law tails would produce the effect you want.

by rtkwe 8y ago

stochastic_monk 8y ago

You’d need some kind of higher structure of computing. One method for longer-term dependence is simply expanding the transition matrix and state space, but that’s not unbounded in any meaningful sense. A recurrent neural network approximates unbounded long-term information for general tasks, but I think what you’re looking for in particular is a push-down automaton, while a Markov chain is a finite-state automaton.

tree_of_item 8y ago
See [0] for a way to make recurrent neural nets in to pushdown nets. [0]: https://arxiv.org/abs/1506.02516 https://arxiv.org/abs/1506.02516
- stochastic_monk 8y ago
  I’m not an expert in nlp or these augmented models. Could you perhaps compare this to Dyer’s Stack LSTM?
  - tree_of_item 8y ago
    I'm not sure how Dyer's thing works, but I can describe the paper I linked to: A "stack" is a stack of (vector, scalar) pairs (a vector and its "weight"). At each time step, the stack has three inputs: the vector to push, the weight to push it with, and the weight to pop off the stack. Its output is the top 1.0 weight of the stack. The stack's behavior on a time step is divided in to three parts: 1. First, that pop weight is removed from the stack. For example, if you want to remove 0.6 from a stack like [(a, 0.4), (b, 0.4)], you'd remove all of a leaving you with 0.2 to remove from b, so the final stack would be [(b, 0.2)]. 2. The pushed vector is placed on the stack with the given push weight. 3. The top 1.0 of the stack is blended together and returned. For example, a stack like [(a, 0.4), (b, 0.4), (c, 0.8)] would take 0.4 of a, 0.4 of b, and 0.2 of c. This process is differentiable, and you can combine this with the usual recurrent loops to make a recurrent stack machine.
    - stochastic_monk 8y ago
      Thank you so much! That makes the paper a lot easier to understand.

S4M 8y ago

By definition, a Markov chain only depends of the current state. That said, I can think of a way to make something depending on the past as well: if you have two states (S for sunny, R for Rainy), with two days of state you now have four states: SS, SR, RS, RR, which gives you a transition probabilities matrix - of course you will have some restriction, for example from SS you can only go to SS and SR.

bena 8y ago

I think one of the features/requirements of Markov chains is that they be stateless. Previous states cannot influence the current probability. It really depends on how granular you want to cut it. You could make 10 rainy states, each with an increased probability of sunny, equal chance to stay or go to a lower probability, and no chance of going to a state with a higher probability. So R90 could be S = 10%, R90 = 45%, and R80 = 45%. R80 could be S = 20%, R80 = 40%, and R70% = 40%. And so on. That way you don't need to track how many days it's been raining, it will naturally filter down to lower rainy percentages until it inevitably goes back to sunny.

gimagon 8y ago

The definition of the Markov property is that the process is memoryless - the probability distribution of the next state only depends on the previous state. This makes them an easy tool to use for mathematical analysis, but limits the amount of things they can model completely. One simple way to add memory is to make states more complex. For example, instead of recording the weather each day as a state, you could record the weather for two day tuples. This allows more complex dynamics, but the number of states quickly increases. Hierarchical Markov Models are another way to achieve this. In a HMM, there is a probability matrix for different types of weather (winter vs summer) and a probability matrix that governs transitions between each of these types.

ColinWright 8y ago

Lots of other commentators are saying that the property of MCs is that they are memory-less, but in fact it's trivial to make a MC have deeper memory: Use tuples. So if you have observations A, B, C, B, C, A, D, A, ... then you form pairs: (A,B), (B,C), (C,B), (B,C), (C,A), (A,D), (D,A), ... Each node in the MC is one of these pairs, and (X,Y) -> (Y,Z) if Z is the new state that appears. The number of states grows very quickly, but if you make the system dynamic then it works fine. This is what you use to randomly generate text using the previous 3 words as a predictor for the next. Then (w0,w1,w2) predicts w3, and your next "state" is (w1,w2,w3). And so on.

throwawayjava 8y ago
As a confused undergrad first learning about random dynamical systems on my own (outside of any classes), this really bothered me. How could the Markov assumption be so powerful when it's clearly trivial to add memory and retain the Markov property?! After reading through theorems and proofs for dynamical systems theory, and especially considering applications of that theory, I came up with basically two practical take-aways: 1. Complexity matters and the curse of dimensionality is real. 2. All those nice theorems (stability, convergence, splitting, invariance, bifurcations, ...) are stated with respect to a state space and make assumptions about the dynamics on that state space. So if you code up a state space representation that is history-aware with respect to the dynamics you really care about, then: a) you might lose some theorems that hold for the original process, and b) you sometimes realize the theorems lose a lot of power when they're telling you something about a tuple of things you care about instead of the actual thing you care about. If I ever teach people about random dynamical systems, this explanation will come immediately after the definition of a Markov process and I'll continually remind my audience throughout the course. Understanding what goes wrong when a system is "technically" Markovian is probably the best way to obtain a deep intuition. Or at least, it was very helpful to me.
dminor 8y ago
Exactly - even if your process is conceptually a Markov chain, your code doesn't have to explicitly enumerate all of the states. I used a similar scheme to your example, but with letters for generating a word for http://password.supply http://password.supply

abhgh 8y ago

The Markov chains we normally we hear of are first order Markov chains. The general notion being d-order chains. These are hard to compute (too many model parameters) but there has been quite some research on an interesting middle ground: variable length Markov chains.

cosmic_ape 8y ago

The particular behavior you mention can be modeled by a Semi-Markov Model. In these, the time you stay at a given state can be an arbitrary fixed distribution. In a regular chain this time is geometric, so memoryless. But other distributions, with Gaussian like tails or power law tails would produce the effect you want.