- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper introduces the problem of priority-aware explainable clustering, where clusters in a reference clustering may have different priorities. The goal is to construct a decision tree that provides strong approximation guarantees for the -medians objective. The setting differs from the traditional one, studied in many papers, because it aims to achieve better guarantees for points assigned to high-priority clusters.
Let be a set of reference centers partitioned into sets , where is the set of centers with the th highest priority. The authors assume that the set of higher-priority centers has fewer centers than the set with smaller priority,
There are two main theoretical results:
-
it is possible to build a randomized decision tree (Theorem 1.1) with at most leaves such that the distance between a point , whose closest center is , and its center is (in expectation) $ O( \log |P| \log s) |x-c_i|_1$. The assumption that implies that points whose closest center has high priority have better theoretical guarantees.
-
a result with the same flavor as the above one, but with different bounds (Theorem 1.2), for the setting in which all centers may have different priorities ( ). The competitive ratio for the point with the th highest priority is and the number of leaves is , for every .
To obtain the results, they employ and adapt the machinery developed for obtaining optimal bounds for explainable clustering via decision trees
Critical strengths
-
The motivation of the proposed problem is reasonable: minimizing the price of explainability for some clusters of higher priority. This is an interesting addition to the literature that studies explainable clustering from a theoretical standpoint.
-
The paper gives a good theoretical characterization for the problem, providing meaningful upper bounds on the competitive ratio and on the number of leaves required by the proposed decision trees (Theorems 1.1 and 1.2. They also show that additional leaves are necessary to improve the competitive ratio, even for a single high-priority center. The presentation is also good, at least for someone acquainted with the field.
Critical weaknesses
When a decision tree has exactly leaves, each cluster can be explained by a single rule (a conjunction of conditions). When more than leaves are allowed, however, interpretability may be substantially reduced, since some clusters (potentially including high-priority ones) may require a disjunction of many rules to be described. The guarantees established in the paper allow leaves (Theorem 1.1) and leaves (Theorem 1.2).
These guarantees alone do not establish that the resulting trees remain interpretable. An experimental evaluation would help assess their practical usefulness, particularly the number and complexity of rules needed to describe individual clusters. While the absence of experiments may be acceptable in a primarily theoretical conference, I believe solid empirical evidence is important to establish the significance of these results for ICLR community.
This concern is the main reason why I consider the paper borderline.
Questions for authors
No question that would affect my assessment
2 comments
Thank you for the discussion!
I think it is a good idea to add this discussion to the final version.
However, this does not change my assessment much. I am keeping my score, as I still consider the paper borderline for the reasons explained in my review.
We thank the reviewer for the thoughtful feedback and for recognizing the theoretical contribution of the paper. We would like to briefly address the concern regarding interpretability when more than k leaves are allowed.
We distinguish between the explanation of an individual assignment and the complexity of describing the entire region assigned to a cluster. In the standard k-leaf setting, these two notions coincide: each cluster corresponds to a single leaf, while every individual assignment is explained by the conjunction of threshold conditions along the corresponding root-to-leaf path.
Our bi-criteria setting preserves the latter property. Even when a center labels multiple leaves, every individual point is still explained by a single root-to-leaf path consisting of simple threshold conditions on individual features. Thus, allowing additional leaves does not turn the explanation of an individual assignment into a disjunction of many rules. Specifically, the height of the PrioriTree output is at most k-s-2, so the size of an explanation of a clustering assignment is still comparable to the number of clusters k and independent of the dimension d, as in the standard explainable clustering model. Therefore, in a medical application, for example, a doctor can still verify a classification of a patient to the cluster of high risk patients by only checking a concise explanation of the form "age >= 65, blood pressure >= 140" and so on.
The reviewer correctly points out that there is additional complexity if one wants to describe the entire region assigned to a center: this region may be a union of several leaf regions. We can quantify this fragmentation for PrioriTree. If Lc denotes the number of final leaves labeled by c∈Pi, then
∑c∈PiLc=k.
Thus, centers in Pi are represented by k/∣Pi∣ leaves on average, while a particular center may appear in at most k leaves.
We will add this discussion to the final version. We will also include experiments reporting the empirical competitive ratio, number of leaves, tree depth, runtime, and the observed fragmentation of individual clusters. This will allow us to evaluate directly the interpretability--accuracy tradeoff introduced by allowing additional leaves.