  It might seem counter-intuitive at first: We find that, in expectation, the
proportion of data points in an unknown population-that belong to classes that
do not appear in the training data-is almost entirely determined by the number
$f_k$ of classes that do appear in the training data the same number of times.
While in theory we show that the difference of the induced estimator decays
exponentially in the size of the sample, in practice the high variance prevents
us from using it directly for an estimator of the sample coverage. However, our
precise characterization of the dependency between $f_k$'s induces a large
search space of different representations of the expected value, which can be
deterministically instantiated as estimators. Hence, we turn to optimization
and develop a genetic algorithm that, given only the sample, searches for an
estimator with minimal mean-squared error (MSE). In our experiments, our
genetic algorithm discovers estimators that have a substantially smaller MSE
than the state-of-the-art Good-Turing estimator. This holds for over 96% of
runs when there are at least as many samples as classes. Our estimators' MSE is
roughly 80% of the Good-Turing estimator's.
