Active Probabilistic Clustering

Thank you for your and the other reviewers' valuable feedback. Taking into consideration the concerns raised regarding terminology, problem definitions, and algorithmic details, we have diligently revised the corresponding sections and added a flowchart illustrating how APC operates. We hope our response and the updated manuscript address your concerns and related issues about the paper. We answer your questions as follows:

<Weakness 1, Question 1> The problem formulation is not clearly described. Please clarify and motivate the objective (metrics) for the problem.

Thanks for your advice. Firstly, we study the Active Constrained Clustering (ACC) problem, which is formally defined in Section 2 Definition of ACC. ACC belongs to the scope of semi-supervised clustering, and it utilizes the actively queried pairwise constraints as supervisory information to strengthen the original unsupervised clustering result.

Secondly, the objective of APC is to maximize the improvement of Normalized Mutual Information (NMI) with as few human queries as possible. This objective is motivated by the observed challenges in previous ACC works, specifically the "Accumulation Plane" problem encountered with complex datasets. In the revised version, we provide a detailed and clear explanation of our motivation for selecting this objective and using the NMI metric. This information is presented in Section 2.

<Weakness 2, Question 3> Considering that $w_i$ and $w_j$ are two random variables, the LHS of equation (2) has to be either 1 or 0, while the RHS of (2) does not. The same for equation (3) and (4). Please Clarify the probability space and random variables.

Thank you for your feedback. It's crucial to note that in Equation (2), $w_i$ and $w_j$ are not random variables. For the conditional merge probability expressions $P(w_i=w_j|w_i,w_j)$, the condition $w_i$ implies that the samples within this cluster share a common class, and the same interpretation applies to the condition $w_j$. $w_i=w_j$ signifies that the classes of the two clusters are identical. Note that the relationship between the classes of $w_i$ and $w_j$ remains unknown unless observed by human annotators. Therefore, we derive equations (2), (3) and (4) to estimate the probability of the event $w_i=w_j$ occurring.

Common clustering algorithms are based on either the distance or the similarity between two samples. Similarly, the basic event (i.e., random variable) in probabilistic clustering is whether two samples belong to the same class or not: $e_{ij}\in \{1,0\}$, and its probability is defined as $P(e_{ij}=1)\in [0,1]$. More complex events like $(w_i=w_j|w_i,w_j)$ are the combinations of these basic events, and their probability is derived based on $P(e_{ij}=1)$.

We have refined the explanation of these equations and added the discussion about probability space and random variables to minimize potential confusion in the revision.

<Question 2> Clarify the terminology of "splitting" and "clustering" in Theorem 2.

Thanks for your detailed review. In Theorem 2, the terms "clustering" and "splitting" convey the same concept. To eliminate potential confusion associated with the term "splitting,", we have changed the "splitting" to "clustering" in the Theorem in the revision.

<Question 4> Clarify the notation of $w_j$, entropy and mutual information.

$w_j$ first appears in Theorem 2, where it denotes a cluster that contains some samples. In Equation (2), $w_j$ as a condition means the event that all samples in this cluster have the same class. We have added the definition of entropy and mutual information in Definition 2.2 in the revision.

Thank you for your and the other reviewers' valuable feedback. Taking into consideration the concerns raised regarding terminology, problem definitions, and algorithmic details, we have diligently revised the corresponding sections and added a flowchart illustrating how APC operates. We hope our response and the updated manuscript address your concerns and related issues about the paper. We answer your questions as follows:

<Weakness 1> Description of the main algorithm: Algorithms 2 and 3 are deferred to the Appendix without giving the intuition regarding what they do. What does "Implement Human Test on w_1 and w_2" mean?

Thanks for your advice. We placed Algorithms 2 and 3 in the main write-up instead of in the appendix in the revision. The intuition regarding them has been discussed in Section 3.3, and we rephrase them to help with your understanding in the revision.

The "Human Test" consists of two parts: Purity Test and comparison of central samples. To avoid ambiguity in "Implement Human Test on w_1 and w_2", we have changed it to "Implement Purity Test on w_1 and w_2".

<Weakness 2> Can conditions in Theorem 2 hold in natural clustering settings? Do these conditions continue to hold after a sequence of fusion operations?

The conditions hold in some real scenarios such as face clustering and person re-identification, where FPC algorithm can provide a good initial clustering result and is widely applied in the real world [1]. We agree that it may not hold in some challenging tasks where the initial NMI is bad. However, it is challenging for a clustering algorithm to fit all datasets. Concerning the cases where the initial NMI is bad (e.g., 0.1), there are related works such as Active Deep clustering [2] aiming to solve it.

Theorem 2 assures that the NMI value continues to increase after the lawful fusion operations (both conditions are satisfied), and the purity constraints are always tested before each fusion operation. Therefore, these conditions will continue to hold in APC.

<Weakness 3> Q1: Does FPC use any queries?

A1: FPC is an unsupervised clustering algorithm, and does not use human queries.

Q2: Is there some reason to believe that the initial clustering has some correlation with the target clustering? If so, what is the correlation, and how does this impact the number of queries?

A2: We contend that the clustering outcome of the common clustering method will exhibit a positive correlation with the target clustering, indicating accurate clustering for the majority of samples. For the specific scenarios in which the initial clustering does not correlate with the target clustering, we remark that the initial clustering is of low quality (low NMI and ARI value), and both FPC and APC are not proposed for such cases.

The impact of the correlation is that the number of queries will decrease when the correlation is stronger. This is because a stronger correlation indicates a better initial clustering: clusters with high purity and clustering result with low category fission rate.

[1] Liu etc. Mpc: Multi-view probabilistic clustering. CVPR (2022).

[2] Bicheng Sun, Peng Zhou, etc. (2022). Active deep image clustering. Knowledge-Based Systems.

Thank you for your and the other reviewers' valuable feedback. Taking into consideration the concerns raised regarding terminology, problem definitions, and algorithmic details, we have diligently revised the corresponding sections and added a flowchart illustrating how APC operates. We hope our response and the updated manuscript address your concerns and related issues about the paper. We answer your questions as follows:

<Weakness 1> The terminology like dominant class and purity is not clearly defined.

Assuming that the clustering of $N$ samples is $\Omega=\{w_1,\cdots,w_k\}$, and the ground truth clustering is $C=\{c_1,\cdots,c_K\}$. Then we define the dominant class of a cluster $w_i$ as $\arg \max_j |w_i\cap c_j|$, and the purity of $w_i$ as $\max_j \frac{|w_i\cap c_j|}{|w_i|}$. We have added the formal definition in Theorem 1 in the revision.

<Weakness 2> What exactly is the human answering in the Human Test?

In APC, the answer of the human query is either "must-link: the two samples belong to the same class" or "cannot-link: the two samples belong to different classes".

<Weakness 3, Question 2> What's the application of APC? What information does the algorithm have access to? Does it have access to the ground truth information which causes its good performance?

APC finds application in open-ended tasks like face clustering and person re-identification, where the number of classes is large and unknown. Evaluating the clustering quality and obtaining a reliable dataset in such contexts necessitates the input of human annotators. Their judgment becomes crucial in determining whether certain clusters genuinely represent the same person and warrant merging for an accurate and meaningful dataset.

The APC algorithm has access to three pieces of information: 1) the clustering result of FPC; 2) the pairwise probability matrix $P_{N\times N}$; and 3) Human queries. We argue that APC does not require any ground truth information and its success is owing to two reasons: First, the FPC algorithm isolates noise samples into outlier clusters, leading to high purity in the remaining clusters. Second, APC can alleviate the category fission problem in FPC very fast.

<Question 1> Why is an NMI of 0.95 enough? Is it possible in some applications that we would want say NMI of 1.0? Why not extend the results?

Reaching an NMI of 1.0 with ACC methods proves challenging due to the difficulty in accurately classifying all noise samples. Our goal, however, is to significantly improve clustering quality with a practical and manageable number of human queries. Very few previous ACC methods extend it to 1.0, and it is beyond our problem setting.

<Question 3> Should the term clustering be used instead of cluster in Definition 2.1 and throughout the rest of the paper?

Thanks for pointing out this. We have revised it in the revision.

<Question 4> What is the clustering algorithm used? The authors state that they use FPC, but how does this algorithm work?

As outlined in Algorithm 1 (APC), FPC serves to produce the initial clustering result which is employed as APC's input. To better motivate the use of FPC, We added the description of FPC in the last paragraph of Section 3 in the revision.

<Question 5> How are the constraints enforced by APC?

We propose a relabeling strategy in Section 3.3, which directly adjusts the sample labels in the recalled cluster pair according to the constraints.

[1] Mpc: Multi-view probabilistic clustering. CVPR 2022. Liu etc.

Thank you for your response. We have conducted a comprehensive revision, as outlined in our general response. Any additional specific suggestions you may have regarding the writing and communication would be greatly appreciated. We would be grateful if you could reconsider the assigned score. Your reconsideration would be highly valued.