- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper focuses on a framework where a first classifier identifies a subset of candidate labels before using a larger model or human expert to consider this subset only afterwards. The authors remain in a specific setup where only the class-specific summary, top-1 accuracy are available. They show that two classifiers having identical top-1 accuracy and per class summaries can yield different top-k accuracy. Thus, they aim to obtain bounds on the top-k accuracy when both top-1 accuracy and each class marginal distribution are known. This bound then allows them to identify how many labels should be kept at a given quality (expressed using coverage, i.e., top-k accuracy) threshold. The authors first work under an idealized framework where the probabilities given by the classifier provide the exact probabilities of the true label. They also work in a more practical scenario without this assumption, where they instead rely on programming techniques to obtain the minimal value and maximal values of these bounds across the set of plausible joint distributions of probability scores and labels.
Critical strengths
- The paper introduces theoretical bounds that are, according to the authors and to the best of my knowledge, novel
- The paper aims to use these bounds to provide budget guarantees
Critical weaknesses
- [W1] The practical relevance of the problem is insufficiently justified. As noted by the authors, performing a new evaluation report containing a true-label rank histogram would determine every top-k coverage and shortlist budget exactly.
- [W2] The paper only considers a mix of toy datasets with a small number of classes. They do not evaluate their certification on tasks with large label spaces, where shortlist selection would be more useful.
- [W3] The paper considers coarse probability score grids. The authors considered 5 neighbors, 5 votes (line 369) or rounded the probability scores to multiples of 1 / 5 (line 464) in the main body of the paper. The method becomes overly expensive when trying to reach finer evaluation. For instance, none of the tested settings with and managed to work according to their experiments (line 465, table 18). This constrains the use of their certificates in practice.
- [W4] The top-1 accuracy is high in this work. I have concerns about the interest of the paper considering the tradeoff between the small increases of coverage induced by adding a new label with respect with the associated cost to be considered by the expert classifier. The work would have benefited from having a thorough analysis of the time (time to optimize + time to process an additional label) and resources needed to obtain a specific top-k coverage on each dataset.
- [W5] The writing should be improved.
- A) The paper does not sufficiently guide the reader through the main results. The progression between the paragraph “Pooled marginals and what the report fixes” and the start of section 4.1 would gain from clearer explanations and less reliance on supplementary material. There is not enough explanation on how to use or eq. 11 to build certificates without exploring the supplementary material. The connection between eq13 and eq14 could also be made clearer. Some concepts are not clearly introduced. For instance, the paper talks about columns (line 81) or row links (178) without clearly explaining which table or row/column it is talking about. Moreover, the paper sends the reader very often to the supplementary material to understand derivations, but it does not necessarily help the understanding as its structure is not linear and it can require navigating across many different sections. For example, section A relies upon theorems in section B whose proof requires section C/D.
- B) The paper relies on a large number of notations that are not thoroughly introduced, can take different meanings across the manuscript, and make the argument difficult to follow. For instance, while the Law operator is used in eq.2, its meaning only comes at line 195; nothing is explained about (eq.13) besides stating it describes a “1D potential determined by the report”(line 292) and providing its expression, in the main body of the paper; the meaning of and (eq 14) has to be inferred by the reader; and (line 464) is unclear. especially has different meanings: it represents the score-grid denominator in line 464 and the number of samples in line 172. is also used with different meanings: it is a probability score in eq. 4 or eq. 18 but represents the summary in most of the paper (line 205)
- C) The paper is not self-contained. As identified with different examples above, the main text relies too heavily on the supplementary material to understand the argument. Moreover, line 149-150 directly sends the reader to the supplementary material to assess a statement that the authors claim to show. There are references to tables from the supplementary material in lines 377-378 and 453.
- [W6] Some results are not explained thoroughly. For instance, the authors do not explain the decrease in ambiguous reports identified in Figure 2
Questions for authors
- Considering you are only dealing with at most 10 possible recommended labels in the experiments of this work, why not directly give them all to the expert classifier ? Would this be really that expensive in time and resources ?
- The paper focuses on a specific framework where only top-1 accuracy and summaries of each individual class are available. I have never encountered such a framework, nor my colleagues. Which scientific community relies solely on these kinds of “reports” ? Why not change the evaluation protocol directly ?
- In Fig.1, could you explain why the part between the k=1 and k=2 is filled with colors, while your work should only consider $ k\geq 2$? I was also wondering why you got rid of the “7” and “9” in the x-axis.
- Can you explain what is the difference between the top-k coverage and the top-k accuracy in your work ?
- Can you explain the difference between (eq1), (eq 2), (line 165), (line 165) and (line 205). I do get that one is used to refer to summaries and the others for probability scores but I still am not sure about the notations in eq 18 ?
- Can you explain why you used x as dummy variables in different variables such as line 201, eq 11 ? Similarly to your use of and for the scores, I was expecting to use and for the ground-truth label as in line 164. However, in the integrals, should take values across [0, 1]. Would it be more consistent to use instead there ?
- Are you stating that the top-k coverage is the Bayes risk in line 191 ?
2 comments
I appreciate the efforts the authors have made to improve the paper. However, despite these efforts, the paper remains difficult to read at places. For instance lines 314-328 partly describe a mathematical demonstration whose presence does not bring much besides confusion. Moreover, the paper has many statements or links to tables that are in the appendix. This keeps breaking the reading and introduces questions that may not be necessary to understand the paper. All these writing choices make the paper more complicated to read.
I would also advise the authors to take into consideration if it is possible to decompose your 72-page-long submissions into different articles to gain clarity.
On top of that I still think the paper would gain from more realistic experiments. A first step would be to show that, on top of having the theory that is working on any number of classes, we can still apply it on datasets with more than 10 classes.
Therefore, I maintain my rating.
Thank you for the detailed reading. The revised PDF addresses the presentation points, later version would further refine it.
W1: Who uses such reports? Why not change the protocol? We agree the protocol should change. When list sizing is expected, evaluators should report the true-label rank histogram (N numbers). The revision says so, and no longer suggests that any community relies only on these reports (§1, §6). Our contribution is to show exactly what is lost otherwise, and which statistics avoid the loss.
W2: Large label spaces. The theory holds for any number of classes. Our exact experiments cover at most ten classes, which we now state (§6). The simple bounds discussed with Reviewer nGYN work at any size.
W3: Coarse scores. We added an experiment on the original, unrounded RepVGG scores. It will be reported in later revision (see the general response).
W4: High accuracy; why not pass all labels? For ten classes, passing all labels is feasible, and the paper says so. We have no timing study and do not claim time savings. The revision adds a simple accounting instead (§5; App. I, Table 17), assuming second-stage cost grows with list size:
High top-1 accuracy moves the problem to strict targets; it does not remove it.
W5: Writing. Fixed in the revision:
Renaming the report symbol s touches many appendix proofs, so we will do it in the final version.
W6: The decrease in Fig. 2. Near 100%, every compatible batch needs the same larger list, so the ambiguity disappears. The caption now explains this.
Questions.