💻 computer science

Positive-First Most Ambiguous: A Simple Active Learning Criterion for Interactive Retrieval of Rare Categories

This paper introduces Positive-First Most Ambiguous (PF-MA), a novel active learning criterion designed to overcome the limitations of conventional methods in imbalanced, low-budget interactive retrieval by prioritizing likely positive samples near the decision boundary to rapidly discover rare fine-grained categories while ensuring diverse class coverage.

Original authors: Kawtar Zaher, Olivier Buisson, Alexis Joly

Published 2026-03-26

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Kawtar Zaher, Olivier Buisson, Alexis Joly

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to find a very specific, rare type of bird hidden in a massive library containing millions of photos of all kinds of animals. You don't have a name for this bird yet; you just have one photo of it as a starting clue. Your goal is to show the computer photos, ask "Is this the bird?", and have the computer get smarter with every answer until it can find all the other photos of that bird.

The problem? The bird is extremely rare. For every one photo of your bird, there might be 1,000 photos of cats, dogs, and squirrels. Also, you (the human) only have a few seconds to look at each batch of photos, and you can only label about 10 photos at a time before you get tired.

This is the challenge the paper tackles. Here is how they solved it, using simple analogies:

The Problem: The "Wrong" Way to Search

Standard computer programs (called Active Learning) usually try to be "fair." They look for photos that are confusing to the computer.

The "Confusion" Strategy (MA): Imagine the computer asks, "Is this a bird?" and gets stuck on a photo of a squirrel that looks a little bit like a bird. It spends all its time asking you about squirrels because they are confusing.
- Result: You get bored because 9 out of 10 photos are irrelevant (squirrels), even though the computer is learning a lot. You might quit before finding the bird.
The "Confidence" Strategy (MP): The computer only shows you photos it is 100% sure are the bird.
- Result: You get happy quickly because you see birds! But, they are all the exact same bird, sitting in the exact same pose. You miss the birds flying, nesting, or standing on rocks. The computer learns nothing new because the photos are too similar.

The Solution: "Positive-First Most Ambiguous" (PF-MA)

The authors created a new strategy called PF-MA. Think of this as a Smart Detective who knows two things:

You need to see the bird first (to stay happy and motivated).
The computer needs to see the tricky ones (to learn the difference between a bird and a squirrel).

How PF-MA works:

The "Positive-First" Rule: The computer looks at the photos it thinks are most likely to be your bird. Even if it's not 100% sure, if it leans toward "Bird," it shows it to you. This keeps your "satisfaction meter" high because you see relevant results immediately.
The "Most Ambiguous" Rule: Among those likely birds, it picks the ones that are on the edge. Maybe it's a bird with a weird angle, or a bird that looks a bit like a squirrel. These are the "tricky" ones that help the computer learn the fine details.
The Balance: It fills your small batch of 10 photos with mostly birds (so you are happy) and a few tricky, confusing ones (so the computer gets smarter).

The "Class Coverage" Metric

The authors also realized that finding more birds isn't enough; you need to find different kinds of birds.

The Analogy: Imagine you are collecting stamps. If you find 30 stamps, but they are all the same picture of a cat, you haven't really collected much. But if you find 30 stamps showing cats sleeping, running, eating, and playing, you have a great collection.
They created a new score called "Class Coverage." It doesn't just count how many birds you found; it checks if you found birds in different poses, backgrounds, and situations. PF-MA is great at this because it doesn't just pick the "safest" bird; it picks the interesting ones.

Why This Matters

In the real world, this is huge for things like:

Biodiversity: Finding a rare, endangered plant in a forest full of common weeds.
Medical Imaging: Finding a rare tumor in a sea of healthy tissue.
Art History: Finding a specific style of painting in a massive museum archive.

The Bottom Line:
Old methods were like a teacher who only asked questions they knew you would get wrong (boring and frustrating). The new method (PF-MA) is like a helpful guide who shows you the things you are most likely to recognize (keeping you engaged) while gently challenging you with the tricky ones to help you learn faster. It finds the rare "needles in the haystack" quickly, keeps you happy, and ensures you find needles of all shapes and sizes.

1. Problem Statement

The paper addresses the challenge of interactive fine-grained visual retrieval in real-world scenarios characterized by severe class imbalance and strict operational constraints.

Context: Users seek to discover a specific, rare, or visually subtle concept (e.g., a rare species) within massive unlabeled collections where the target class may represent less than 0.1% of the data.
Constraints:
- Low Annotation Budget: Users can only label a very small number of samples per iteration (e.g., $b=10$ ).
- Low Latency: The system must provide feedback within seconds, precluding heavy retraining or complex stochastic processes.
- Asymmetric Utility: In this setting, querying a "likely positive" sample provides significantly higher value (user satisfaction) than querying an ambiguous negative, contrary to standard Active Learning (AL) assumptions which treat classes symmetrically.
Limitations of Existing Methods:
- Uncertainty-based (e.g., Most Ambiguous - MA): Selects samples near the decision boundary. In imbalanced settings, these are predominantly negatives, leading to poor user satisfaction and slow discovery of the rare class.
- Confidence-based (e.g., Most Positive - MP): Selects high-confidence positives. While satisfying to the user, these samples are often redundant and fail to refine the decision boundary or capture visual diversity.
- Representativeness-based (e.g., CoreSet, DAL): Aim to match the unlabeled data distribution, which causes them to oversample majority (irrelevant) classes in long-tailed datasets.

2. Methodology

A. Positive-First Most Ambiguous (PF-MA)

The core contribution is a novel AL selection criterion designed to balance user satisfaction (retrieving relevant positives) with classifier informativeness (refining the boundary).

Logic: PF-MA explicitly breaks the symmetry of standard uncertainty sampling. It prioritizes samples that are:
1. Likely Positive: The model predicts a probability $f(x_i) \geq 0.5$ .
2. Ambiguous: Among the likely positives, it favors those near the decision boundary (where $f(x_i) \approx 0.5$ ) to maximize learning.
3. Fallback: Only if the annotation budget is not filled by positives does it include ambiguous negatives.
Mathematical Formulation:
The score for a sample $x_i$ is calculated as:
$PF\text{-}MA(x_i) = (1 - |0.5 - f(x_i)|) \times \mathbb{1}(f(x_i) \geq 0.5) + f(x_i) \times \mathbb{1}(f(x_i) < 0.5)$
- Interpretation: If $f(x_i) \geq 0.5$ , the score is the "ambiguity" (distance from 0.5). If $f(x_i) < 0.5$ , the score is simply the probability itself (ranking negatives by how close they are to being positive, but strictly lower priority than positives).

B. Class Coverage Metric

To evaluate retrieval quality beyond simple accuracy, the authors propose a Class Coverage Metric ( $cov^C_t$ ) that measures visual diversity.

Mechanism:
1. Perform offline K-means clustering ( $K=32$ ) on the ground truth class to define visual modes (clusters).
2. Assign retrieved positive samples to these clusters.
3. Calculate the fraction of clusters covered by at least one retrieved positive.
Significance: This metric penalizes systems that retrieve many redundant samples from a single visual mode (e.g., birds only on one type of branch) and rewards systems that span the full visual manifold of the class.

C. Experimental Setup

Datasets: Long-tailed datasets including CIFAR100-LT, ImageNet-LT, and PlantNet300K (fine-grained botanical data).
Descriptors: Pre-trained ViT-L14 models via CLIP (language-supervised) and DINOv2 (self-supervised).
Classifier: Lightweight linear SVM (to meet low-latency constraints).
Budget: $b=10$ samples per iteration over $T=25$ iterations.
Baselines: Random, MA (Most Ambiguous), MP (Most Positive), DAL, CoreSet, ALAMP, and diversity-enhanced variants (MA-S, MP-D, etc.).

3. Key Results

Superior Coverage: PF-MA consistently outperforms all baselines in Class Coverage across all datasets and descriptors. For example, on ImageNet-LT with DINOv2, PF-MA achieved 0.954 coverage vs. 0.899 for MA and 0.877 for MP.
Early Retrieval Performance: PF-MA shows a pronounced advantage in the first few iterations. It rapidly discovers relevant samples, allowing users to stop the process earlier without sacrificing quality.
Robustness to Class Size:
- MP works well for very small classes but fails as class size increases (due to redundancy).
- MA works better for large classes but fails to satisfy users early on.
- PF-MA maintains consistent performance across all class sizes, eliminating the need for prior knowledge of the target class frequency.
Positive Ratio: PF-MA maintains a high proportion of positive samples in selected batches (often >80% on CIFAR/ImageNet), whereas MA returns mostly negatives. This directly correlates with higher user satisfaction.
Classifier Performance: Despite prioritizing positives, PF-MA achieves high F1-scores, proving that selecting boundary-adjacent positives is sufficient for training an effective classifier without needing excessive negative samples.

4. Key Contributions

PF-MA Criterion: A simple, computationally efficient AL strategy that explicitly addresses the asymmetric utility of interactive retrieval by prioritizing ambiguous positives over ambiguous negatives.
Class Coverage Metric: A new evaluation metric that quantifies the diversity of retrieved samples relative to the underlying visual manifold, addressing the limitation of standard metrics like mAP or F1-score in fine-grained retrieval.
Empirical Validation: Comprehensive experiments demonstrating that PF-MA outperforms state-of-the-art AL methods (including deep AL and diversity-based methods) in long-tailed, low-budget, and low-latency settings.

5. Significance

This work bridges the gap between theoretical Active Learning and practical Human-in-the-Loop (HITL) systems for rare category discovery.

User-Centric Design: It shifts the optimization goal from "global model accuracy" to "rapid discovery of the user's specific concept," acknowledging that in interactive settings, user fatigue and satisfaction are critical constraints.
Practical Applicability: The method is lightweight (linear SVM, simple scoring) and robust, making it suitable for real-world applications like biodiversity monitoring, where users need to find rare species quickly without extensive prior knowledge of the dataset distribution.
Paradigm Shift: It challenges the conventional wisdom that uncertainty sampling (selecting the most ambiguous samples regardless of class) is optimal, demonstrating that in imbalanced retrieval, biased sampling toward the target class is necessary for success.