Find your next learning step
A remote-sensing audit may violate exact adaptive diminishing returns yet remain close enough for greedy selection to be useful. The adaptive submodularity ratio quantifies that gap in a model. Empirical lower-bound diagnostics can reveal where the ratio collapses, but they must not be presented as universal theorems beyond the states and histories actually checked.
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. The ratio measures distance from the ideal property
Exact adaptive submodularity requires every candidate’s conditional marginal gain to decrease as the observation history grows. A ratio-based analysis compares aggregate gains with the value available to a competing policy.
A ratio near one supports a strong diminishing-return structure in the analysed model. A small ratio warns that complementarity can make greedy choices substantially less reliable.
CHAPTER 2 OF 12 · DEFINE THE DECISION
2. State the domain before quoting a bound
Define the utility, prior over scene states, observation model, audit budget, feasible actions and partial histories. The ratio belongs to that complete specification, not to the satellite sensor in isolation.
Changing cloud handling, label noise or the operational value of rare detections can change the ratio even when the imagery is identical.
CHAPTER 3 OF 12 · WORK THE LEDGERS
3. An empirical ratio ledger
A stratified diagnostic enumerates or samples histories and computes conservative ratios after accounting for Monte Carlo error.
| Stratum | Histories checked | Lower diagnostic | Main cause |
|---|---|---|---|
| Clear agricultural | 1,200 | 0.82 | Mostly redundant scenes |
| Cloud-edge forest | 900 | 0.46 | Optical–thermal complementarity |
| Urban change | 1,100 | 0.68 | Temporal dependence |
| Rare flood onset | 420 | 0.21 | Enabling observations |
The rare flood stratum controls the weakest observed behaviour even though it contains fewer histories. Averaging the four values would conceal the branch where a guarantee matters most.
CHAPTER 4 OF 12 · WORK THE LEDGERS
4. Worked approximate-guarantee translation
For a monotone budgeted model, suppose the applicable theorem gives a greedy factor of 1 minus exp of negative gamma. Insert each conservative diagnostic only as a model-based benchmark.
| Gamma diagnostic | Benchmark factor | Meaning |
|---|---|---|
| 1.00 | 0.632 | Exact adaptive-submodular reference |
| 0.82 | 0.560 | Strong approximate structure |
| 0.46 | 0.369 | Material guarantee loss |
| 0.21 | 0.189 | Weak protection |
A benchmark factor is not a forecast of realised accuracy. It compares model utility with an optimal policy under stated conditions.
CHAPTER 5 OF 12 · WORK THE LEDGERS
5. Lower-bound diagnostics need error bars
Conditional gains estimated by simulation have uncertainty. Use common random numbers, repeated runs and one-sided adjustments so numerical noise does not inflate the apparent lower bound.
Search adaptively for bad histories, but evaluate the final reported diagnostic on a held-out set of histories or with a valid correction. Otherwise the minimum can be a tuning artefact.
CHAPTER 6 OF 12 · TRANSFER THE METHOD
6. Route weak strata to richer policies
A low ratio need not force a complex policy everywhere. Keep greedy selection in clear strata and route cloud-edge, rare-event or enabling-history branches to rollout, paired audits or expert review.
Record the routing rule before deployment and monitor how often it activates. Local simplicity is valuable only when the gate itself is reliable.
CHAPTER 7 OF 12 · TRANSFER THE METHOD
7. Changed-context transfer: coastal algal bloom audits
Transfer the workflow to algal bloom confirmation using ocean colour, thermal data and in-situ sampling. A colour anomaly can raise the marginal value of a thermal or field observation, lowering the ratio.
The transfer check rebuilds the prior, utilities and missingness model. It verifies whether the weakest ratio occurs during cloud cover, river discharge events or the early onset that decision-makers care about most.
CHAPTER 8 OF 12 · TRANSFER THE METHOD
8. Connect the guarantee and stress-test branches
The adaptive-submodularity guide gives the exact positive case. The stress-test guide finds explicit violations.
Use the lookahead audit guide when ratio diagnostics identify enabling observations that greedy choice undervalues.
CHAPTER 9 OF 12 · CHECK LIMITS AND EVIDENCE
9. Limits and common misconceptions
The minimum ratio observed in a simulation is not automatically a mathematical lower bound over unvisited histories. Call it an empirical diagnostic unless coverage is proven.
A good global ratio can still hide unacceptable performance on a protected rare-event stratum. Governance may require a stratum-specific floor or a separate safety rule.
CHAPTER 10 OF 12 · CHECK LIMITS AND EVIDENCE
10. Practical evidence checklist
Archive the utility, prior, observation model, feasible policy class, history sampler, conditional-gain estimator, numerical tolerances, uncertainty adjustments and stratum results.
Report both the weakest reproducible history and the distribution of diagnostics. State exactly which theorem is invoked, which assumptions were checked and where only empirical evidence is available.
CHAPTER 11 OF 12 · ASK AND CONTINUE
11. Frequently asked questions
Can a ratio exceed one?
Definitions differ, and many analyses cap or normalise the ratio. Use the exact definition from the applicable result and do not mix conventions.
Is the smallest sampled value too pessimistic?
It may be noisy, but a decision-relevant bad history should be investigated rather than averaged away. Replicate and bound its numerical error.
Does a low ratio prove greedy will fail?
No. It weakens the available worst-case guarantee; empirical policy evaluation is still needed.
CHAPTER 12 OF 12 · ASK AND CONTINUE
12. Sources and next reading
Golovin and Krause introduce adaptive submodularity and greedy guarantees. Fujii and Sakaue develop the adaptive submodularity ratio and broader approximation results. Bian and colleagues analyse greedy guarantees using submodularity ratio and curvature in the non-adaptive setting. The remote-sensing diagnostics 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