I just realized that the previously mentioned game Eleksius is a very difficult form of active learning. This thought was triggered by the ICML 2009 tutorial on active learning from John Langford’s blog article.  Active learning is a machine learning technique where the machine actively chooses which query to ask to the oracle. This is particularly useful in combination with costly experiments. When one has a black box that has input and output, and want to find out the relation between input and output, but to obtain an output, one needs time and/or money; ffor example such as DNA microarray, drug discovery, space, high energy experiments, or even computer simulations. Active learning can be thought of as a clever way of designing experiments that depend on the previous experimental results. The key is to search the plausible hypothesis space efficiently through probing the best spots.

In other games such as Eleusis and some sequence puzzles, one also searches the hypothesis space of logical and mathematical rules, and one needs to find a “simple” solution, however, are not active learning problem since the player does not have the choice of next item.

Let X be the set of all objects, and Q be the set of all hypotheses. Each hypothesis (or question) q in Q is a binary function from X to {‘yes’, ‘no.’}. In Twenty questions, the player tries to find an unknown element x in X by using a few (less than or equal to twenty) questions as possible. The goal of Eleksius is to find the unknown q by using as few number of objects as possible.

The set of all possible binary functions on X has the cardinality $2^X$ (fancy way of saying the number of elements). Hence, in principle, finding Q should be more difficult just because of the size of the set. However, this is not entirely true. Arbitrary binary function on X is meaningless. Also, the function must be balanced, there are many objects corresponding to yes, and same for no. However, the most important factor is human perception and natural language. The question in god’s mind is some simple concept that can be clearly expressed in a few words at most. Therefore there is a structure in this space Q, some are preferred and some are not. How can we measure this? Is there a natural algorithm that a human or computer player can use to solve Eleksius?