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

<ul>
<li>Quinlan, J.R.: C4.5: Programs for Machine Learning,   Morgan Kauffman, 1993</li>
</ul>

<p>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.</p>

<p>Recent refinements of the approach include using genetic algorithms:</p>

<ul>
<li><a href="http://www.jprr.org/index.php/jprr/article/viewFile/44/25" rel="nofollow">A Genetic Algorithm for Constructing Compact Binary Decision Trees</a> by Sung-Hyuk Cha and Charles Tappert.</li>
</ul>

<p>A more general keyword to look for is <strong>classification</strong>. Check out a recent book on Machine Learning. (Or perhaps ask your question at <a href="http://metaoptimize.com/" rel="nofollow">http://metaoptimize.com/</a>).</p>

CC BY-SA 2.5
2011-04-02T06:51:48.167Z
2011-04-03T08:45:53.240Z
2011-04-03T08:45:53.240Z
Dave Clarke
<p>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. </p>

CC BY-SA 2.5
2011-04-02T05:00:38.470Z
2011-04-02T05:00:38.470Z
Suresh Venkat
<p>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: </p>

<p>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.</p>

<p>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 <strong>decide optimally what further information (if any) do I require from you to identiy the chair of interest</strong>, 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, <strong>how can I optimise the questions I ask you.</strong>  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.</p>

<p>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.</p>

<advice-request><optimization><terminology>
Asking optimal questions to differentiate object in set
zenna
# Asking optimal questions to differentiate object in set

(Asked by: username_0 on 2011-04-02)

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.

**Tags:** advice-request, optimization, terminology


---

## 2 answers

### Answer by username_1 on 2011-04-02. Score: 0 | Accepted answer

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 Genetic Algorithm for Constructing Compact Binary Decision Trees](http://www.jprr.org/index.php/jprr/article/viewFile/44/25) by Sung-Hyuk Cha and Charles Tappert.

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/>).


---

### Answer by username_2 on 2011-04-02. Score: 1

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.


---

