{"id":"fbdd140b-3c9e-4bd4-a9de-9b2b52227116","arxiv_id":"2412.02310","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"GAL selects images for user labeling by the estimated impact of each candidate on the retrieval classifier, using a greedy batch scheme, and reports improved retrieval accuracy over prior active learning methods on four benchmarks.","lead":"An active learning method called GAL chooses which unlabeled images a user should label next in an interactive image retrieval system, by estimating how much each candidate image would shift the retrieval classifier. It outperformed several existing active learning baselines on four retrieval benchmarks, and the paper introduces a new object-level benchmark for this task.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The (1-1/e) guarantee in §4.2.1 is unsupported: Eq. (15) does not meet the Nemhauser conditions, and submodularity of the max term is asserted without proof, so the paper's stated theoretical contribution is not established.","rationale":"The paper's central empirical claim is that GAL outperforms AL baselines on IIR benchmarks; the reader found this plausible but requested variance information and queried the theory. I agree with that conditional posture. The single most load-bearing issue I see is the formal guarantee, because it is a stated contribution and the proof in §4.2.1 has a concrete gap: the acquisition function (15) is not shown to be nonnegative and submodular, and the max term is not covered by the cited Das & Kempe result. This is an internal correctness problem, not a disagreement with a field consensus. I do not choose the pseudo-label proxy as the primary concern because the paper provides some empirical evidence for it (Fig. 11b reports pseudo-label accuracy on FSOD), and the final labels are supplied by the oracle at the end of each cycle. Still, a direct oracle comparison would strengthen the empirical section. A conditional verdict is therefore appropriate: the theoretical guarantee should be corrected or withdrawn, and the experiments should report variance or significance; the rest of the contribution can stand pending those checks.","tokens_in":22970,"tokens_out":13741,"duration_ms":153686,"concrete_test":"Run a randomized search over small GP instances (e.g., 3 test points, 4 candidate train points, SE kernel with a range of γ values) and for every subset A compute r_A(x) = (Σ21 Σ11(A)^{-1} Σ12)[x,x] and h(A) = max_{x∈Xc} r_A(x). Check the diminishing-returns inequality h(S∪{x}) - h(S) ≥ h(T∪{x}) - h(T) for all S⊆T⊆Xc and x∉T. One violation falsifies the claimed submodularity of the normalized acquisition function in §4.2.1; if none appears, the proof still needs an explicit argument for the max term.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.2.1 claims that F(A) = -(Σ_{x∈Xc} σ²_A(x) + α max_{x∈Xc} σ²_A(x)) satisfies the conditions of the Nemhauser et al. (1978) theorem and therefore that greedy batch selection attains a (1-1/e) approximation. This is not established. First, for the SE kernel in Eq. (10), σ²_∅(x)=K(x,x)=1, so F(∅)=-(|Xc|+α)<0, violating the nonnegativity condition as stated; a constant shift would restore nonnegativity, but the paper does not perform that shift. Second, the submodularity argument cites Das & Kempe (2008) for variance reduction and the closure of submodular functions under non-negative linear combinations, but Eq. (15) contains a negative sign and a max term. Writing σ²_A(x)=1-r_A(x), the normalized objective is Σ_x r_A(x) + α max_x r_A(x). The sum is monotone submodular, but max_x r_A(x) is a maximum of monotone submodular functions; maxima of submodular functions are not submodular in general, and no property specific to GP variance reduction is shown. Thus the (1-1/e) bound is unproven. This does not refute the empirical comparisons, but it invalidates a stated central contribution.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes GAL, a batch-mode active learning framework for interactive content-based image retrieval. The main idea is to select samples by their estimated impact on the classifier: for SVM and MLP classifiers this impact is the change in the decision boundary under a pseudo-label chosen to minimize that change (Eqs. 3-6), while for Gaussian processes it is the reduction of global predictive variance, with a greedy batch construction that adds each pseudo-labeled selection to the training set before choosing the next sample. The paper reports experiments on Paris-6K, Places365, a new FSOD-IR object-level benchmark, and MIRFLICKR-25K, comparing against random selection, RBMAL, COD, MaxiMin, Kmeans++, Coreset, ITAL, and Kapoor et al. A theoretical claim is made that greedy GP-based selection satisfies a (1-1/e) approximation guarantee via the Nemhauser et al. theorem. Code is available online.","tokens_in":23259,"tokens_out":4959,"duration_ms":59377,"significance":"If the empirical claims hold, GAL is a useful contribution to interactive image retrieval active learning: it addresses cold-start, open-set, and class-imbalance conditions with a unified acquisition framework, introduces a new object-level benchmark (FSOD-IR), and provides code. The breadth of the evaluation (three classifier families, four datasets, several baselines, and a batch-mode ablation) is a clear strength. However, the theoretical guarantee stated as contribution 3 is not established by the current proof, and the pseudo-label proxy underlying the SVM/MLP acquisition functions is not validated on real data. The empirical comparison would be stronger with variance reporting or significance tests.","major_comments":[{"comment":"The claimed (1-1/e) guarantee is not established. For the squared-exponential kernel in Eq. (10), σ²_∅(x)=K(x,x)=1, so F(∅)=-(|Xc|+α)<0, violating the non-negativity condition of the Nemhauser et al. theorem. More importantly, the submodularity argument is not valid as written: Eq. (15) contains a negative sign and a max term, and while the sum Σ_x σ²_A(x) is monotone submodular by Das & Kempe (2008), a maximum of monotone submodular functions is not submodular in general, and no GP-specific property is shown for the max term. A constant shift would restore non-negativity but would not fix the submodularity issue. Therefore contribution 3, as stated, is unsupported.","section":"§4.2.1, Eq. (15)"},{"comment":"The pseudo-label proxy is load-bearing for the SVM and MLP acquisition functions: Eq. (3) assumes the true label produces a smaller decision-boundary shift than the false label, so the argmin label approximates the true label. The paper motivates this only with a 2D Gaussian toy example (Fig. 2), and the pseudo-label accuracy reported in Fig. 11b covers only FSOD-IR with B=1 and one candidate size. Since Algorithm 1 inserts each selected sample with its pseudo-label into the training set before choosing the next sample, incorrect pseudo-labels can systematically steer within-batch selections. Please validate this assumption on the real datasets, e.g., by reporting pseudo-label accuracy per dataset/cycle or by ablating with oracle labels during greedy selection.","section":"§3, Eq. (3)"},{"comment":"The empirical comparisons are averaged over only five random queries, but no standard deviations, confidence intervals, or significance tests are reported. Some observed margins are small (e.g., Table 2, Paris K=200: GAL 0.960 vs Random 0.942; Table 3, Paris K=100: GAL 0.946 vs Kmeans++ 0.922), and with N=5 these differences may not be reliable. The \"superiority\" claim would be much stronger with per-query variability or paired statistical tests over the same query set.","section":"Tables 2-6 and Figs. 8-14"}],"minor_comments":[{"comment":"For the GP acquisition function, the pseudo-label returned by Next is Null, but Algorithm 1 still performs Yl ← Yl ∪ {l*}, which would insert Null into the label set used for subsequent training; the algorithm should make explicit that GP selection does not update Yl with pseudo-labels.","section":"Algorithm 1"},{"comment":"There is an overloaded use of F: Eq. (13) defines Fgp as a function of a candidate point xi, while Eq. (15) defines F(A) as a set function over a batch A; please use distinct symbols or clarify the relationship.","section":"§4.2"},{"comment":"Eq. (7) defines Fmlp as a norm but does not specify whether it is the L2 norm or a squared norm; the SVM version in Eq. (1) uses squared L2, so the MLP definition should be made consistent.","section":"§4.1, Eq. (7)"},{"comment":"There are several typos, e.g., \"aqcusition function\" in §4.2, \"lake size\" in §5.1, and \"Kappor et al.\" in Table 6; these should be corrected.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper has a solid empirical core and a useful new benchmark, but the theoretical contribution is currently overstated. If the (1-1/e) proof cannot be repaired, the authors should either remove the guarantee from the contribution list or substantially weaken it to an empirical observation. The pseudo-label assumption deserves validation even if the theoretical claim is dropped. The lack of variance reporting is common in this literature but worth insisting on here given the small number of queries."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the empirical contribution of GAL is real and worth sending to reviewers; the (1-1/e) guarantee in §4.2.1 is not proved and should be cut or fixed.\n\nWhat's actually new: the minimal-shift pseudo-label acquisition for SVM/MLP, the greedy batch construction that retrains with pseudo-labels within the batch, and a GP acquisition that minimizes pooled variance plus a max term. The FSOD-IR benchmark is a useful addition. Code is claimed and the runtime analysis is honest. The empirical story is broad: four datasets, three classifiers, several baselines, and the reported gains are consistent. GAL (batch) vs GAL greedy shows a small but sensible improvement, and the pseudo-label accuracy plot in Fig. 11b is a direct attempt to validate the core assumption. The paper earns credit for that.\n\nSoft spots, in order. The theory section is the load-bearing problem. Eq. (15) is non-positive: at A=∅ with the SE kernel, σ²_∅(x)=1, so F(∅)=-(|Xc|+α)<0, which already violates the Nemhauser nonnegativity condition. The submodularity argument is also unsound as written: it cites closure under non-negative linear combinations, but (15) has a negative sign and a max term. A maximum of submodular functions is not submodular in general, and no GP-specific property is shown. So the (1-1/e) statement is unsupported. I don't think this refutes the empirical comparisons, but it is a central claimed contribution, and the authors should either provide a correct proof or drop the guarantee. The experiments are otherwise decent, but 5 query runs with no error bars makes the 5-10% gaps hard to judge; the paper needs variance or per-query spread. The pseudo-label proxy is the main idea and is only demonstrated on a 2D toy plus one accuracy curve; an ablation against, say, treating all pseudo-labels as positive or using classifier confidence would make the mechanism credible.\n\nWho this is for: people working on active learning for retrieval and cold-start AL generally. It is a serious empirical paper with a broken theory claim. My recommendation: send it to peer review, but the reviewers should insist on fixing or removing the guarantee and adding error bars. If the authors do that, it is a solid contribution.","headline":"Solid empirical paper on active learning for interactive image retrieval with a genuine theory flaw: the (1-1/e) guarantee in §4.2.1 is unsupported and should be fixed or removed before publication.","tokens_in":23808,"tokens_out":2102,"would_cite":true,"duration_ms":23759,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"GAL is a batch-mode active learning method for interactive image retrieval that selects samples by measuring their impact on the classifier's decision boundary, outperforming existing baselines on four benchmarks and carrying a (1-1/e)…","keywords":["active learning","interactive image retrieval","batch-mode active learning","greedy selection","classifier impact","Gaussian process","cold start","content-based image retrieval"],"falsifier":"Measure how often GAL's pseudo-labels match the actual user labels for the images it selects over the first few active-learning cycles on a real retrieval dataset. If that agreement is near chance (50%) while GAL still beats random and diversity baselines, then the minimal-shift pseudo-label mechanism is not the source of the gains, and the paper's explanation of its own success fails.","tokens_in":22718,"feed_emoji":"🖼️","tokens_out":12412,"duration_ms":113814,"temperature":0.7,"pith_summary":"The paper introduces GAL, a batch-mode active-learning framework for interactive image retrieval, where each round the system shows a user a small set of images and learns from their relevance feedback. GAL's selection rule scores each unlabeled candidate by how much adding it to the training set would change the classifier, with the candidate's label guessed by the smaller of the two class-conditional changes (the pseudo-label). A greedy loop adds each chosen image to the training set before picking the next, so later choices must bring new information rather than duplicate the previous one. On four retrieval benchmarks with SVM, MLP, and Gaussian Process classifiers, GAL reports higher retrieval accuracy per labeled sample than random selection, uncertainty, diversity, and several hybrid baselines. For the Gaussian Process case the paper proves a (1-1/e) approximation guarantee for the greedy batch selection.","feed_headline":"Greedy impact scores cut labeling effort in image search","feed_subtitle":"New GAL method picks the most boundary-changing images per round and beats baselines on four retrieval benchmarks.","key_machinery":"The key machinery is a MaxMin acquisition function built on classifier impact. For SVM, each candidate $x_i$ is added to the training set once with label $+1$ and once with $-1$; the impact score is $S_i = \\min_{l\\in\\{+1,-1\\}} \\|W(x_i,l) - W_0\\|^2$, where $W_0$ is the current hyperplane and $W(x_i,l)$ is the hyperplane retrained with the candidate added (the minimizing label is the pseudo-label). For the MLP, the same idea applies to the vector of all network weights. For the Gaussian Process, the acquisition function is $F_{\\rm gp}(x_i) = -\\big(\\sum_{x\\in X_c} \\sigma^2_{A\\cup\\{x_i\\}}(x) + \\alpha \\max_{x\\in X_c} \\sigma^2_{A\\cup\\{x_i\\}}(x)\\big)$, i.e., the negative total and worst-case predictive variance after adding the candidate to the training set $A$; for the GP the variance reduction is label-independent, so no pseudo-label is needed. The greedy Algorithm 1 then inserts each selected point (with its pseudo-label) into the training set before selecting the next, which yields a conditioned diversity: nearby points have low impact once a similar point is in the batch, while boundary points remain attractive.","core_discovery":"The core claim is that in the cold-start, open-set, class-imbalanced setting of interactive image retrieval, the most useful unlabeled samples are those that would most strongly reshape the classifier's decision boundary, and that this can be estimated without oracle labels. For SVM and MLP classifiers, GAL tentatively labels each candidate as positive and as negative, computes the resulting change in the decision boundary (or in all network weights for the MLP), and treats the label producing the smaller change as the pseudo-label, since a wrong label would move the boundary more. The impact score of the candidate is that smaller change, and the algorithm selects the candidate with the largest score. For Gaussian Processes, the acquisition function instead measures how much adding the candidate would reduce the total and worst-case predictive variance over the candidate pool. The greedy loop then iterates: after a point is selected it is added to the training set with its pseudo-label, so the next pick cannot simply echo the information already gained. The paper shows this mechanism outperforms existing active-learning baselines across Paris, Places, FSOD-IR, and MIRFLICKR, and proves that the GP acquisition function is monotone submodular, so greedy batch selection inherits the classical (1-1/e) approximation bound.","pith_inferences":["The minimal-shift pseudo-label heuristic could transfer to other severely imbalanced binary active-learning settings, such as defect detection or medical triage; there it could be tested by comparing pseudo-label accuracy with oracle labels on real workloads.","The paper's evidence that a small top-K pool beats the full pool suggests that the optimal pool size depends on feature-space geometry; a natural follow-up is to measure how K should scale with database size and class rarity.","The (1 - 1/e) guarantee covers only the GP acquisition function; for SVM and MLP the greedy scheme has no formal bound, so an open question is whether a submodular relaxation or a different proof route could extend the guarantee to those settings.","Because the pseudo-label accuracy is initially modest (the paper reports it hovering around chance-to-60% at the start on FSOD), combining GAL with a first cycle of random or diversity-based selection could improve cold-start robustness even further."],"forward_implications":["An interactive retrieval system can reach a target mean average precision with fewer user-labeled images per round, since GAL selects images that most quickly sharpen the classifier.","The greedy construction makes larger batch sizes usable in cold-start settings; the paper's experiments show GAL stays ahead of baselines even when the batch budget grows from 3 to 7 after the first cycles.","For Gaussian-Process retrieval, the selected batch is provably near-optimal with respect to uncertainty reduction, by the (1 - 1/e) submodular maximization guarantee.","Restricting the selection pool to the top-K ranked candidates (e.g., K=200) improves both accuracy and runtime, so the method scales to databases where scoring every image each round is too slow.","The newly introduced FSOD-IR benchmark offers an object-level interactive retrieval testbed where queries are objects inside images, which is more challenging than image-level retrieval."],"supporting_citations":[{"why":"Provides the MaxiMin selection paradigm that GAL extends to multiple classifiers and batch budgets, and serves as a primary baseline.","marker":"Karzand & Nowak (2020)"},{"why":"Introduces the ITAL Gaussian-process active learning method and the MIRFLICKR evaluation protocol that GAL is compared against.","marker":"Barz et al. (2018)"},{"why":"Gives the (1 - 1/e) approximation theorem for greedy submodular maximization, which grounds GAL's GP guarantee.","marker":"Nemhauser et al. (1978)"},{"why":"Proves that GP variance reduction is increasing, monotone, and submodular, a premise for the approximation guarantee.","marker":"Das & Kempe (2008)"},{"why":"Provides the closure properties for submodular functions used to show the GP acquisition function is submodular and monotone.","marker":"Fujishige (2005)"},{"why":"Documents the cold-start phenomenon and the strength of random and diversity baselines, which motivates the GAL design and explains the comparisons.","marker":"Hacohen et al. (2022)"},{"why":"Supplies the Coreset diversity baseline that GAL is compared against in batch-mode experiments.","marker":"Sener & Savarese (2018)"},{"why":"Supplies the Paris-6K benchmark protocol used for instance-level interactive retrieval evaluation.","marker":"Radenović et al. (2018)"},{"why":"Supplies the FSOD dataset that the paper turns into a new object-level interactive retrieval benchmark (FSOD-IR).","marker":"Fan et al. (2020)"},{"why":"Provides the MIRFLICKR-25K dataset and protocol used for the GP-based comparisons with ITAL.","marker":"Huiskes & Lew (2008)"}],"fun_headline_variants":["Greedy impact scores pick boundary-shifting images","Impact-based active learning cuts labeling for image retrieval","AL via classifier impact: greedy selection beats baselines","Which images to label? The ones that move the boundary most","Greedy impact metric reduces annotation cost in image search"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method's sample selection only works if, for each candidate image, the label that causes the smallest change in the trained classifier is usually the correct label—the pseudo-label—because the impact scores and the whole greedy batch construction are built on those guessed labels.","fun_headline_variants_meta":{"raw":{"variants":["Greedy impact scores pick boundary-shifting images","Impact-based active learning cuts labeling for image retrieval","AL via classifier impact: greedy selection beats baselines","Which images to label? The ones that move the boundary most","Greedy impact metric reduces annotation cost in image search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000196,"raw_usage":{"total_tokens":1383,"prompt_tokens":991,"completion_tokens":392,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":607,"completion_tokens_details":{"reasoning_tokens":314}},"tokens_in":607,"tokens_out":392,"duration_ms":4638,"temperature":1.0,"reasoning_tokens":314,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:36:24.645764+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure how often GAL's pseudo-labels match the actual user labels for the images it selects over the first few active-learning cycles on a real retrieval dataset. If that agreement is near chance (50%) while GAL still beats random and diversity baselines, then the minimal-shift pseudo-label mechanism is not the source of the gains, and the paper's explanation of its own success fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the MaxiMin selection paradigm that GAL extends to multiple classifiers and batch budgets, and serves as a primary baseline."},{"cited_title":"o rn Barz, Christoph K \\","cited_arxiv_id":null,"evidence_quote":"Introduces the ITAL Gaussian-process active learning method and the MIRFLICKR evaluation protocol that GAL is compared against."},{"cited_title":"Submodular Functions and Optimization","cited_arxiv_id":null,"evidence_quote":"Provides the closure properties for submodular functions used to show the GP acquisition function is submodular and monotone."},{"cited_title":"Active learning for convolutional neural networks: A Core-Set approach","cited_arxiv_id":null,"evidence_quote":"Supplies the Coreset diversity baseline that GAL is compared against in batch-mode experiments."},{"cited_title":"Few-Shot Object Detection with Attention-RPN and Multi-Relation Detector","cited_arxiv_id":null,"evidence_quote":"Supplies the FSOD dataset that the paper turns into a new object-level interactive retrieval benchmark (FSOD-IR)."},{"cited_title":"The MIRFLICKR retrieval evaluation","cited_arxiv_id":null,"evidence_quote":"Provides the MIRFLICKR-25K dataset and protocol used for the GP-based comparisons with ITAL."}],"review_version":1}