Let us modelize a riddle:
We have a finite set of elements E and some subsets A_i.
For the riddle, an unknown element e is chosen in E and the player asks a sequence of questions " is e in A_i ?" An oracle answers yes or no. The goal is to find e.
The strategy of the player is modelized by a binary tree of questions (each node is labeled by a subset A_i with two branches (e is in A_i) or (e is not in A_i)). Notice that A_i can appear several times in the tree. Such a tree is said to be discriminatory if it allows you to find any element of e.
The problem is: build the discriminative tree of minimal height (we can consider the height as an average or the maximal one).
In fact, our goal is to have an algorithm that takes the A_i and builds the decision tree of minimal height.
This problem has probably been investigated for a long time. In which framework ? (data base, game theory, information theory?). If you know anything about this problem, please let me know because I didn't find anything on the web.
Sounds like an application of the ID3 method.
http://en.wikipedia.org/wiki/ID3_algorithm
Regards,
Joachim
It becomes more clear now. The keyword is decision tree. I was not familiar with this concept and field. My problem belongs clearly to this framework. The problem of building a decision tree of given height is NP-hard. http://www.ise.bgu.ac.il/faculty/liorr/hbchap9.pdf
It means that it is not possible to build the smallest decision tree (in some sens) in a polynomial time (up to P=NP). The wikipedia page gives for instance some heuristics. ID3 is one of them -at each step, it uses the set with the smalles entropy- and there exists many others.
Thanbks a lot for your answer Joachim.
This is very similar to some of the riddles I've heard. I can't remember from which book or source online, though. But the gist of it was dividing your uncertainties into as equal parts as possible, for the next step. I think it was one of the information theory sources, though. And it doesn't have to be only binary, also characterizing such as tree may not be easy.
The whole strategy was if you want to find e in E, and you are given N tries, use the tries such that your posterior uncertainties after each step are managable, it's like minimum depth, tree in a way, where you want the depth to be less than or equal to N.
Example 1: choose a No, between 1 and 100, have your friend guess the number using Yes/No question answers. ex. Is it higher than x? Turns out it's best to always stick to the middle number, so the best solution would be to ask if it is higher than 50, then upon answer, choose the middle number again. what you are doing mathematically is maximizing entropy of the answer. H(ask if it is higher than 50|between 1 and 100)>H(ask if it is higher than n|between 1 and 100) for any n.
Entropy speaking, you need to ask at least lg[100] questions, and in base 2.
Example 2> you have 12 balls which are either equal weight or one is heavier than others or one is lighter. you have a scale that you can weigh them it gives you 3 outcomes [equal, higher, lower]. here you have 25 uncertainties to start with and have a device that can potentially give you 3 outcomes. so you need at least log[25] in base 3 tries. turns out with the right strategy you can use the scale 3 times at most to solve riddle, though the strategy itself is more complicated than example 1.
Example 3, if you ever played mastermind (white and black flags for color choices, that game). you can use same approach of maximizing entropy by asking the right colors from user. I did a Matlab implementation of this and used some baysian formulation, most of the time 3 guesses was sufficient but then some cases required 4 quesses. The point here is that it is not Alsways possible to find the answer, and there are interdependencies,
Overalle rule:
to find e in E using any decision tree (binary or other) you need at least N=log[E] tries. you can't go lower than that, and in fact, as the problem gets more complicated, the sufficient tries may be higher than this. as in example 3, it turns out that every guess can narrow down the next step but does not guarantee the narrowing down of the next two steps.
Are you thinking of something like group testing? [http://en.wikipedia.org/wiki/Group_testing]
Thanks a lot for your interesting answers. ID3 was the kind of things that I had in mind. The keywords for my question was "decision tree":
- see for instance slideshow http://www.comp.dit.ie/jkelleher/ai2lectures/Information-Theory-and-Decision-Trees.pdf
- or nice book chapter for a survey on the question http://www.ise.bgu.ac.il/faculty/liorr/hbchap9.pdf .
- or wikipedia http://en.wikipedia.org/wiki/Decision_tree_learning
The question that I had in mind was exactly: give an algorithm to build a decision tree of minimal height . Nevertheless, the problem is NP-hard (Naumov 91 and other references are cited in the book chapter I mentionned) and the book chapter gives an overview of the work in this field.
- Badges
- Science topic