# Which, When, and How: Hierarchical Clustering with Human-Machine Cooperation
## 4 \"Which\", \"When\", and \"How\"
### The \"When\" Problem  
In this subsection, we focus on the \"when\" problem. If the machine asks questions in the early clustering stage, then it benefits from getting a good start (or foundation) as a trade-off on the risk: it may not reserve enough question operations for very hard decisions that may appear in the later clustering stage. The benefit of asking a question can be estimated through the current machine's certainty. The risk means that the machine has used up its questions, and then encounters a low certainty case in the later clustering stage.  
We want to _maximize the minimum purity_ during the cluster-building process. The total number of questions (denoted by \(Q\)) is limited, since human computations are relatively costly. One may think that the minimum purity monotonously decreases when the hierarchy of the clustering moves up, and thus the machine should ask questions when it encounters a significant certainty reduction. However, the machine is likely to encounter numerous certainty reductions during the cluster-building process, while the available question operations may not be enough. Moreover, how could the machine determine whether a certainty reduction is significant or not? This is very challenging, and can be data-sensitive. The key observation is that the minimum purity may increase, as shown in Figure 4(a). In the left part of Figure 4(a), the purity of these two clusters are \(\frac{6}{7}\) (black circle dominates) and \(\frac{1}{2}\) (a tie), respectively. Hence, the minimum purity is \(\min(\frac{6}{7},\frac{1}{2})=\frac{1}{2}\). In the right part of Figure 4(a), the purity (and the minimum purity) is \(\frac{9}{13}\) (black circle dominates). When the machine merges a cluster with a high purity and a cluster with the lowest purity, the minimum purity may increase. Therefore, during the cluster-building process, the minimum purity may decrease with some oscillations, i.e., _local minimums exist_. These local minimums indicate the time for the machine to ask questions. This is because increased minimum purity means _error propagation_, where a cluster with a high purity is contaminated by a dirty one. Error propagations should be controlled.  
Now, let us go back to the trade-off between a good start and the risk. The existence of error propagations make us consider a higher priority of the risk. Errors made by the machine are inevitable,  
Figure 5: The minimum purity and the “when” problem.  
so the machine should save the limited questions on preventing error propagations, which appear rarely, but are disastrous. Therefore, our solution for the \"when\" problem is that the machine asks a question whenever (1) it encounters a certainty gain and (2) it has available questions to ask, as shown in Figure 5b. Instead of receiving an incorrect certainty gain that may result in error propagations, the machine actively asks questions to verify the correctness. This strategy will maximally restrict the error propagations. If the machine goes to the end of the clustering-building process with unspent questions, it will ask those questions at the end.