I have a problem in mind and I am sure this is likely an area of active research, but am at a loss as to the correct terminology and thus unable to find any reference literature. It is best explained by example:

Say I have several objects, for example mahogany chairs. For each of these chairs I know a number of attributes about them such as their weight, texture, colour, age, etc.

If you contact me inquiring about one of my chairs and tell me some incomplete information, e.g. "dark brown, 60's era chair" I want to decide optimally what further information (if any) do I require from you to identiy the chair of interest, i.e. what questions do I need to ask to obtain the required attribute information. Additionally, in the likely case that there are many questions I will need to ask you, how can I optimise the questions I ask you. Optimisation could mean minimising the expected number of quesitons I need to ask you, or asking questions I think you are most likely to be able to answer.

So I would appreciate some information or references for this kind of problem. It's worth noting I am interested in implementing this computationally (hence posting here) as opposed to a purely abstract problem.


A while back, Ross Quinlan designed two algorithms (along with implementations available online) called IDE3 and C4.5 for building decision trees from data. The book:

  • Quinlan, J.R.: C4.5: Programs for Machine Learning, Morgan Kauffman, 1993

is the core reference 2 decades ago. Such an algorithm will be giving data along with its classifications in different dimensions to learn a decision tree. The algorithms aim for optimal trees, and further possibilities exist for improving the resulting.

Recent refinements of the approach include using genetic algorithms:

A more general keyword to look for is classification. Check out a recent book on Machine Learning. (Or perhaps ask your question at http://metaoptimize.com/).


On the one hand, what you're asking sounds like binary search. On the other hand, the adaptivity makes it feel more like active learning: think of the "thing you're trying to learn" as a hypothesis and the "queries" as being labels of objects. Since this question is primarily about finding the right terminology, do look at the active learning literature and see if it captures the spirit of what you want.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.