As an undergraduate, one of my favorite card games was Mao, named after the infamous chairman. The main rule of the game is that there is only one rule, and it is that no one tells you the rules! You have to discover them for yourself by getting negative feedback whenever you break one. Some might say that you teach yourself. Others might say that you have as many teachers as there are players. The fact is that either way you end up learning the rules.
In recent blog entries, Artem Kaznacheev discusses the problem of trying to minimize and learn Deterministic and Non-Deterministic Finite Automoata (NFA, DFA). To “learn” a DFA or NFA is to determine what regular language it accepts. A DFA is a deterministic process composed of a finite number of states that either accepts or rejects strings of words. Any regular language can be produced by a DFA. And for any language coming from an NFA, there is a DFA that also produces that language. This is what reminded me of Mao, the game in which you strive to determine the overall set of rules by running strings of cards through the machine that is play. If you don’t get penalized, then the move was accepted. So you incrementally learn the rules, which I am likening to the language.
Kaznacheev writes tongue in cheek about the value of a minimal adequate teacher in helping to learn……in this case to learn a DFA. Apparently, a minimal teacher need only provide counterexamples to the students proposals for candidate languages. In other words, the student suggests that a certain set of strings forms the language of the DFA, and the teacher either agrees or shows the student an example of a string in their language that is not accepted by the DFA. Even such a minimal teacher can make the difference between never learning the DFA and learning it in polynomial time! Without the teacher, the only way to determine whether you have the right language is to run every word through the automaton.
So he writes “It was my round-about way of justifying my existence to the students”. This inspired me, because just imagine how useful a marginally better than minimal-adequate teacher is!
Another great post on the concept of “Bounded Rationality” provides an alternative explanation for our irrational decisions. I didn’t decide to stay up all night watching Breaking Bad because of incomplete access to future information OR even due to being in an unfamiliar hotel room as opposed to my cozy house. I did it because there is a limit on my processing power and because different parts of my mind are coming up with conflicting ideas that are not being resolved. Each decision is assigned a complexity and each decision-making part of my mind can handle only certain ranges of complexity.
Take a moment to look through Kaznachev’s algorithmic glasses.