One sample often both selects an event and measures it. Estimating the event's true probability is then hard, as with test error or the probability of never-seen outcomes.
The authors unify such cases as data-dependent probability estimation. They analyze two classic methods: using sample frequency, and removing one point at a time. The second recovers the Good-Turing estimator, which estimates unseen probability by counting outcomes seen once. Both apply to predictors memorizing exceptions on a base classifier.
They propose a hybrid estimator and find that the base classifier's generalization alone does not guarantee accuracy. Accuracy follows when possible error regions are not too complex, or when selection depends weakly on the sample. This gives practical error estimation for memory-augmented models.