5 ms·
I used to write Markov-based chat bots. Something I thought I observed, but tried and failed to show mathematically, is the possibility of well-connected neigh
by phaedrus 6y ago
I used to write Markov-based chat bots. Something I thought I observed, but tried and failed to show mathematically, is the possibility of well-connected neighborhoods of the graph (cliques?) leading to some outputs being more likely than their a priori likelihood in the input.
For example, once a simple Markov bot learns the input phrase "had had" it will also start to generate output phrases a human would assign 0% probability to like "had had had" and "had had had had". This in itself isn't a violation of the principles behind the model (it would have to look at more words to distinguish these).
The question is whether more complicated loops among related words can create "thickets" where the output generation can get "tangled up" and generate improbable output at a slightly higher rate than the formal analysis says a Markov model of that order should do for given input frequencies. An example of such a thicket would be something like, "have to have had had to have had".
Essentially, I'm hypothesizing that the percentage values of the weighted probabilities of transitions does not tell the whole story, because the high-level structure of the graph has an add-on effect. A weaker hypothesis is that the state-space of Markov models contains such pathological examples, but that these states are not reachable by normal learning.
Unfortunately I lacked the mathematical chops / expertise to formalize these ideas myself, nor do I personally know anyone who could help me explore these ideas.
- ben_w 6y agoI have observed the same phenomena with both simple Markov chains and whatever Apple used for autosuggest on the iPhone. That said, your specific example reminded me of a specific joke sentence: https://en.m.wikipedia.org/wiki/James_while_John_had_had_had_had_had_had_had_had_had_had_had_a_better_effect_on_the_teacher https://en.m.wikipedia.org/wiki/James_while_John_had_had_had...
- phaedrus 6y agoI actually hadn't seen that one (I did know of the "Buffalo buffalo" family of sentences). Regarding observation of the phenomenon, in a way I first observed the inverse of it. My first proofs of concept didn't learn probabilities, only structure. (One might say all edges had the same probability.) Yet aesthetically they performed just as well as versions which included probability in the algorithm.
- phreeza 6y agoSo basically to calculate the stationary distribution (distribution over a long time of evaluation) of a markov chain, you have to calculate the eigenvectors of the transition matrix. And these take into account the graph structure, so I think the stationary distribution will be exactly what is calculated this way, there isn't really any space for anything beyond that. Incidentally, this is very similar to the original pagerank algorithm. The rank roughly corresponds to the probability you will be on any given page if you randomly follow links.
- staticautomatic 6y agoThere's a non-zero probability of transitioning from "had" to "had", but I don't understand how there could be a non-zero probability of "had" following "had had" or of "had had" following "had had" unless the model is being trained on its own output.
- ninjanomnom 6y agoTraditionally only the last output is known by a markov chain and when it comes to chat bot generation the output is usually one word at a time. The bot doesn't track that the last 2+ words it output are the same, all it knows is that the last word it said is 'had', so what next? There are countless markov chain chat bots made though and plenty bend the rules, to some extent though they are all susceptible to this. In an old irc chat of mine we had a lot of fun abusing one such bot to get it stuck in these kinds of loops, in our case it was the word 'fuck'. You'll have to forgive our teenager sense of humor.
- JHonaker 6y agoIt's perfectly fine, theoretically for the Markov chain to depend on more than the previous token. When you start to do that though, unless you can write down a function (or approximation, like an NN) the number of states in your state space that you have to enumerate explodes very quickly. This is the simple motivation behind stuff like GPT or neural reinforcement learning.