- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper introduces Inbetween-Decision, a decision problem motivated by in-between instances (IBIs): objects that exhibit characteristics of multiple clusters. The main result classifies the problem under all choices of which of five parameters are bounded: alphabet size , dimensionality , number of clusters , maximum cluster size , and target-set size . The problem is polynomial-time solvable when the bounded parameters include one of , , or , and is NP-complete in the remaining regimes. The tractable cases admit fixed-parameter algorithms.
Overall, the paper is difficult to understand and I am unconvinced that the formulation captures the notion of in-betweenness used to motivate the work, or that its significance for machine learning has been adequately established. The broad claims about a third machine learning primitive make this gap more pronounced.
Critical strengths
The paper contains a coherent complexity classification for a symbolic covering problem.
Critical weaknesses
-
The paper is difficult to read, particularly the abstract and introduction. Although the introduction mentions aligned symbolic feature vectors, the relationship between this setting and the clustering terminology is not sufficiently clear. The authors should clarify early on how clusters are represented, whether they are given as input, and what structural assumptions, if any, they satisfy. In particular, the question of selecting a bounded number of representatives to “exactly reconstruct a target object” coordinate by coordinate is difficult to interpret without a concrete explanation of the data model and reconstruction rule. Explaining these details upfront, and distinguishing this formulation from Euclidean or graph-based clustering, would substantially improve readability.
-
I am not convinced by the opening claim that unsupervised learning views every object through a binary inlier/outlier distinction, or by the resulting presentation of IBI as a third machine learning primitive. These are much broader claims than the paper’s formal results support. The contribution is a complexity classification for a specific symbolic covering problem, not a demonstration that machine learning requires a new foundational primitive.
-
I found the connection between the introductory motivation and the mathematical formulation difficult to follow. The paper mentions topic-bridging publications and some areas, while acknowledging that these motivating instances are continuous. It then moves to exact reconstruction over aligned symbolic coordinates without sufficiently explaining why this is the appropriate discrete counterpart for those applications.
Questions for authors
See weaknesses.
With the help of the reviews we came to the conclusion that it is best to withdraw this submission, having the chance to substantially improve this work and resubmit it in future. At that point we'd like to thank the reviewer for the feedback. The connection between the motivation and the mathematical formulation is among the core points of improvement. Thank you for pointing that out.