Find your next learning step
A greedy audit policy is appealing: after every new label, select the scene with the largest expected gain per unit cost. That rule has a rigorous near-optimal guarantee only when the audit objective is adaptively monotone and adaptively submodular under the stated observation model. The conditions matter as much as the algorithm.
Open the chapter contents · Remote Sensing root · Gold Standard of Education · How X Works
Chapter contents
Choose the route closest to the decision, or read from Chapter 1. The chapters remain open; these grouped routes are a navigable index.
Route 1 · Define the decision
Route 2 · Work the ledgers
Route 3 · Transfer the method
Route 4 · Check limits and evidence
Route 5 · Ask and continue
CHAPTER 1 OF 12 · DEFINE THE DECISION
1. Adaptive value depends on what has been observed
Before collection, an audit has outcomes such as correct label, reference error or unexpected class. After each result, the policy updates its partial realisation and recomputes the conditional expected marginal gain of remaining scenes.
Adaptive submodularity is a diminishing-returns property: observing more cannot increase a candidate scene’s conditional marginal gain under the required model. Adaptive monotonicity says an additional observation has non-negative expected benefit.
CHAPTER 2 OF 12 · DEFINE THE DECISION
2. State the utility before invoking a guarantee
Useful objectives include covered error modes, entropy reduction or decision-risk reduction. A guarantee for one utility does not transfer automatically to another.
Specify item states, prior distribution, observation noise, costs and stopping rule. If labels are spatially dependent or an audit changes later measurement quality, prove or test whether diminishing returns still holds.
CHAPTER 3 OF 12 · WORK THE LEDGERS
3. A conditional marginal-gain ledger
A map team considers four audit strata. Values are expected error modes resolved per unit cost under two information states.
| Candidate stratum | Gain before labels | Gain after two diverse labels | Diminishing? |
|---|---|---|---|
| Cloud edge | 0.32 | 0.18 | Yes |
| Mountain shadow | 0.27 | 0.16 | Yes |
| Urban boundary | 0.22 | 0.21 | Nearly flat |
| Sensor seam | 0.19 | 0.26 | No: complementarity appears |
Do not average away the violating branch. A single plausible complementarity can invalidate the standard greedy guarantee even if most marginal gains decline.
CHAPTER 4 OF 12 · WORK THE LEDGERS
4. Worked greedy audit sequence
Assume the first three strata satisfy the conditions and the budget permits two equal-cost audits.
| Step | Current marginal gains | Greedy choice | Cumulative expected utility |
|---|---|---|---|
| 1 | 0.32, 0.27, 0.22 | Cloud edge | 0.32 |
| 2 after result | 0.14, 0.20, 0.17 | Mountain shadow | 0.52 |
| Alternative fixed pair | Cloud edge + urban boundary | — | 0.47 |
The numerical example demonstrates the rule, not the theorem. The approximation factor applies only after the objective and observation distribution meet the formal assumptions.
CHAPTER 5 OF 12 · WORK THE LEDGERS
5. Greedy guarantees are conditional and comparative
Under a cardinality constraint and adaptive monotone submodular utility, adaptive greedy is competitive with the optimal adaptive policy. Other constraints, approximate marginal gains and coverage objectives have different factors and technical conditions.
The benchmark is the best policy under the same prior, state model, utility and budget. It is not the unknowable best audit system under every possible scene process.
CHAPTER 6 OF 12 · TRANSFER THE METHOD
6. Handle costs, quotas and robust objectives explicitly
With unequal costs, rank expected marginal gain per cost only when the relevant result supports that rule. Biome quotas, travel paths and laboratory batches can create matroid, knapsack or routing constraints.
A robust objective across seasons or classifiers may remain submodular in special constructions, but max–min operations can break simple guarantees. Keep the robustness proof separate from the field rationale.
CHAPTER 7 OF 12 · TRANSFER THE METHOD
7. Changed-context transfer: flood-damage mapping
Transfer the method to flood-damage reference collection. Early labels across water depth, building type and sensor angle may reduce the value of similar scenes, supporting diminishing returns.
A rare industrial site may instead become more valuable only after a hazardous-material cue appears. Treat that complementarity as a branch for lookahead planning rather than forcing it into a greedy theorem.
CHAPTER 8 OF 12 · TRANSFER THE METHOD
8. Connect the audit-planning branch
The lookahead-policy guide values enabling observations and short rollouts. The sequential-audit guide develops decision-focused marginal value.
Use the robust-value guide when dependence assumptions dominate the audit ranking.
CHAPTER 9 OF 12 · CHECK LIMITS AND EVIDENCE
9. Limits and common misconceptions
Ordinary submodularity of a batch objective does not by itself prove adaptive submodularity after outcomes are observed. The conditional distribution is part of the property.
Diminishing returns does not mean every second audit has less absolute value than the first. It compares the same candidate under nested information states.
CHAPTER 10 OF 12 · CHECK LIMITS AND EVIDENCE
10. Practical evidence checklist
Archive the utility, item states, prior, observation model, cost structure, conditional marginal calculations, constraint family, approximate-gain error and stopping rule.
Search specifically for complementarity, label-dependent costs and model updates that increase marginal gain. Compare greedy with rollout or exact solutions on small instances before relying on the guarantee.
CHAPTER 11 OF 12 · ASK AND CONTINUE
11. Frequently asked questions
Can I test adaptive submodularity empirically?
You can look for violations across simulated and observed partial realisations, but absence of observed violations is not a mathematical proof.
Is greedy still useful without a guarantee?
Yes, as a transparent heuristic, provided it is compared with stronger baselines and not presented as near-optimal by theorem.
Why use lookahead when diminishing returns holds?
Lookahead can still improve practical choices under approximation, constraints or model mismatch, although its extra computation may not be necessary.
CHAPTER 12 OF 12 · ASK AND CONTINUE
12. Sources and next reading
Golovin and Krause introduce adaptive submodularity and adaptive greedy guarantees. Krause, Singh and Guestrin develop submodular mutual-information sensor placement. Krause and colleagues study robust submodular observation selection. The remote-sensing ledgers above are original teaching examples.
Continue through the Remote Sensing root, the Gold Standard of Education and How X Works.
Top · Contents · Previous · How X Works