- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
Paraphrasing a bit here...
This paper studies "batch active querying". Suppose X is the set of queries and Y is the set of outcomes, this work assumes we have observed some queries: M = {(x1,y1) ... (xm,ym)}. This work decides next batch of queries to issue S_query = {x^1, ... , x^k}. It then goes and get the outcome for those queries, S = {(x^1, y^1), ..., (x^k, y^k)}, and combine the observations SEEN = S \cup M. It then uses SEEN to predict the outcomes for the rest of the queries, and compute some loss on 1) the prediction accuracy itself perhaps, or 2) downstream usage of the predictions.
Generally, computing S_query from M is intractable as it is a combinatorial optimization problem. So the author made some relaxations until submodular happened and the proofs are happy. Empirical results look promising too, but maybe done on too few domain and a bit archaic (like who still do cifar in 2026 lol, but maybe that's beside the point)....
Critical strengths
Good problem statement and logical decomposition into the 3 apprximation steps. Relaxed a whole bunch and actually got to sub-modular surrogate and the proof works out. Nice work.
Although checking the proof is beyond my ability, as I don't work on sub-modular proofs, so I leave it to the other reviewers who can validate the proof itself.
But at the end of the day, the empirical results looked pretty good, and the proposed method seemed very general.
Critical weaknesses
Section 5 in experiment, what are the metrics we're comparing? Is it how well a network can predict patches of the full CIFAR images when observing SEEN ? Or is it how well a network can predict the classification label of the CIFAR image given only SEEN ?
In Section 5 you are also missing a figure visualizing the patches queried for by your algorithm, vs that of baselines, vs that of random. Like show a CIFAR image, show the M, and show the SEEN, for all these baseliens. Something like (https://arxiv.org/pdf/1711.03243 Figure 2) . Because while the performance plot shows your method is good in aggregate, the reader would like to intimately know what your algorithm actually does on a concrete instance. So you want to always have a "gallery" figure, showing specific instances of how your algorithms work on a set of concrete input, so the reader goes "yeah okay I trust you" and then show the plot which demonstrate to the reader that "oh yeah I see the plot, it works on thousands of inputs like the ones you just showed me".
Figure1 you want to also report (approximate) oracle results. If you were to select a large number of subsets (like 1M possible different subsets) for S_query within the budget, and have an oracle pick the best one, you'd get a very good performance right? How far is the proposed method from this oracle? Having random is great as it esbalishes a lower bound, I'd like to see the upper bound too with the oracle.
Have some figures to explain your experiment setup would be nice, as the broader audience would benefit from a more hand-holdy explanation. Like can you have a coverstory of sorts? something like . . . "we're looking for oil, we have drilled into the ocean at these coordinates and taken their readings, and we can send down a submarine to drill at these additional coordinates to see if theres oil" iono some intuitive to understand story, that motivates why observations must be taken in batch, what real-life problems have that flavor, etc. Like what's the point of observing patches of CIFAR ( ? )
Questions for authors
this work reminded me of a prior line of works by Pu.Y that do query selection in the non-batch setting. https://arxiv.org/abs/1704.06131 , https://arxiv.org/pdf/1711.03243 . They also have notion of interpolating (neighborhood of) past observations to make predictions on future queries. See if there's some interesting connections.
another thing, this part: "the predictor f and encoder g are one masked network, trained once per dataset and seed with uniformly random masks and then frozen. "
So the predictor f is trained over uniformly random masks, but at test time, the observations it gets to use is the SEEN set. Now the patches in SEEN is nothing but random no? So this is actually somewhat off-distribution. Have you thought about training "f" alongside a distribution of the SEEN set, and see if performans can be better? I'm just so curious haha
minor:
- maybe we can drop the l(f(x_M),y) term from equation 1, as that's a constant no?
anyways I like the paper and want to champion it, it's a breath of fresh air after all the auto-research slop on my stack . . . but you gotta make it more accessible. It was not easy to read . . .
3 comments
Response to Reviewer 2ur4 (2/2)
Q1: Connection to Pu et al.
Both papers are now cited (Sec. 2). Like HUC, they use past observations to model new ones. Pu et al., UAI 2017 learn a model that predicts the outcome of a candidate observation from the outcomes seen so far. They pick, one at a time, the observation whose outcome is most uncertain. Pu et al., ICML 2018 pick a small set of input-output examples for a program synthesizer. Each time, they add the example their model finds least likely given those already chosen. HUC differs in its goal and in when it commits. An action earns credit by how much it matters for a downstream label predictor under each similar record, not by how uncertain its value is. The whole batch is fixed before any value is seen. In the revision: Sec. 2 cites both papers.
Q2: Training f on the distribution of the SEEN sets.
Yes, on Synthetic it helps, and HUC stays ahead of TOPK by about as much as before. We fine-tuned one copy of the predictor on the feature sets HUC actually acquires and one on TOPK's. The similar records and their utilities stay fixed, so the picks do not change:
| Synthetic, 1,600 new test cases, three training seeds (accuracy points) | 5 features | 10 | 15 | 20 | 25 |
|---|---|---|---|---|---|
| HUC, fine-tuned minus original predictor | +1.1 | +1.6 | +1.2 | +1.3 | +0.9 |
| HUC minus TOPK, original predictors | +15.0 | +16.1 | +7.3 | +1.9 | +0.3 |
| HUC minus TOPK, each fine-tuned on its own feature sets | +15.7 | +16.6 | +7.1 | +1.7 | +0.3 |
In the revision: App. A.8, Table A8.7.
M1: Dropping from Eq. 1.
Yes. The term varies across cases but is constant in for a fixed , so dropping it leaves the best batch unchanged. We keep it so that and reads as the benefit of acquiring . Dropping it would shift the objective and change the form of its multiplicative approximation bound. Sec. 3 now says this after Eq. 1.
Follow-up on the added items
Thank you again for the kind words, and for the concrete suggestions, which made the paper easier to follow. Each item you asked for is already in the revised PDF, and all of them stay in the final version.
- The metric is the class label, now stated in Sec. 5 and the Figure 2 caption.
- Sec. 1 has the clinical cover story and a setup figure (Figure 1), and we rewrote the parts that were hard to follow.
- App. A.8 has the Synthetic and CIFAR-10 galleries (Figures A8.1 and A8.2) and DDXPlus examples (Tables A8.9 and A8.10).
- The hindsight oracle uses the true label to pick the best of many candidate batches (Table A8.6). On DDXPlus and Synthetic, HUC closes more of the gap between the fixed path and this oracle than TOPK and AACO-greedy at every budget. TOPK ranks actions by their average utility, and AACO-greedy re-scores candidate batches with the predictor.
- Fine-tuning the predictor on the acquired sets raises HUC's accuracy on Synthetic by 0.9 to 1.6 points, and its lead over TOPK stays about the same (Table A8.7).
- Sec. 2 cites both papers by Pu et al., and Sec. 3 says why Eq. 1 keeps its first term.
We would be glad to clarify anything before the discussion closes.
Response to Reviewer 2ur4 (1/2)
Thank you for the concrete suggestions and the kind words. We added the galleries, the hindsight oracle, the fine-tuning run, the cover story and the setup figure you asked for. Each is below with its location.
W1: Which metric does Sec. 5 compare?
The class label. On CIFAR, the frozen classifier sees the central patches M plus the acquired patches S, with all other patches masked, and outputs the class. We report its top-1 accuracy, and no patch is ever reconstructed. Every dataset works this way, with the class, the cancer subtype or the diagnosis as the label. Figure 2 plots each method's accuracy minus that of the fixed path, which is the zero line. The fixed path is a baseline that acquires the same patches for every image. Sec. 5 and the Figure 2 caption now say this.
W2: A figure of the patches each method queries.
Added to App. A.8 as Figure A8.2. It shows eight CIFAR-10 test images. Six are drawn at random, and two are chosen among images where HUC is correct and TOPK is wrong, as the caption says. For each image it shows the full image, the initial patches M, and for each method the patches it adds, the visible input and the prediction. The methods are HUC, random selection, the fixed path, TOPK and AACO-greedy. TOPK ranks actions by their average utility, and AACO-greedy re-scores candidate batches with the predictor. App. A.8 also shows four random Synthetic cases, where the generator tells which question carries the class signal. At five features the true class's question is in HUC's batch for 64% of test cases and in TOPK's for 40% (Table A8.8). For DDXPlus, App. A.8 lists the questions each method asks for six random and three chosen patients. One chosen patient is an 82-year-old man with a cough. His similar records point most often to pharyngitis, COPD and upper respiratory tract infection (URTI). TOPK and the fixed path ask three pain questions, which among these three diagnoses concern only pharyngitis and URTI. HUC asks one pain question, one about COPD and one about past asthma attacks. The correct diagnosis is an acute COPD exacerbation, and only HUC gets it right. In the revision: App. A.8, Figures A8.1 and A8.2 and Tables A8.8 to A8.10.
W3: Oracle results.
Added as the hindsight oracle (Table A8.6). On DDXPlus and Synthetic, HUC closes more of the gap between the fixed path and the oracle than TOPK and AACO-greedy at every budget.
For every test case, the oracle uses the true label to pick from a pool of batches the one with which the predictor does best. The pool holds up to 10,000 random batches of the same size and the batches of HUC, TOPK, CS and the fixed path. It is correct for 98 to 100% of DDXPlus patients, against 84 to 95% for HUC, and for every Synthetic case. That is more than the 87% the same predictor reaches on Synthetic with every feature observed, because the label picks a batch on which the predictor happens to be right. The new Table A8.6 in App. A.8 covers all five datasets.
W4: A cover story and a setup figure.
Added. Sec. 1 now names cases where all actions must be chosen at once. A patient fills in an intake questionnaire before a visit, or a clinician orders a panel of laboratory tests at the same time. Every question or test is chosen before any answer arrives. Your oil-survey example has the same structure. The drilling sites are fixed before any reading returns, and the image patches in our CIFAR experiments play the role of sites in a controlled setting. In plain words, HUC looks up similar completed records and notes which questions mattered for each of them. It then picks a set that covers what most of them need, and it gives less credit to a question whose job is already done for a record. The new setup figure (Figure 1) shows this on a small example with three similar records that need different actions. TOPK's three picks serve only two of the records, while HUC's serve all three. Sec. 1 now adds the clinical example and the setup figure (Figure 1).