Estimating the number of unseen species is an important problem in many scientific endeavors. Its most popular formulation, introduced by Fisher et al. [Fisher RA, Corbet AS, Williams CB (1943) J Animal Ecol 12(1):42−58], uses n samples to predict the number U of hitherto unseen species that would be observed if t · n new samples were collected. Of considerable interest is the largest ratio t between the number of new and existing samples for which U can be accurately predicted. In seminal works, Good and Toulmin [Good I, Toulmin G (1956) Biometrika 43(102):45−63] constructed an intriguing estimator that predicts U for all t ≤ 1. Subsequently, Efron and Thisted [Efron B, Thisted R (1976) Biometrika 63(3):435−447] proposed a modification that empirically predicts U even for some t > 1, but without provable guarantees. We derive a class of estimators that provably predict U all of the way up to t ∝ log n. We also show that this range is the best possible and that the estimator's mean-square error is near optimal for any t. Our approach yields a provable guarantee for the Efron−Thisted estimator and, in addition, a variant with stronger theoretical and experimental performance than existing methodologies on a variety of synthetic and real datasets. The estimators are simple, linear, computationally efficient, and scalable to massive datasets. Their performance guarantees hold uniformly for all distributions, and apply to all four standard sampling models commonly used across various scientific disciplines: multinomial, Poisson, hypergeometric, and Bernoulli product. species estimation | extrapolation model | nonparametric statistics S pecies estimation is an important problem in numerous scientific disciplines. Initially used to estimate ecological diversity (1-4), it was subsequently applied to assess vocabulary size (5, 6), database attribute variation (7), and password innovation (8). Recently, it has found a number of bioscience applications, including estimation of bacterial and microbial diversity (9-12), immune receptor diversity (13), complexity of genomic sequencing (14), and unseen genetic variations (15). All approaches to the problem incorporate a statistical model, with the most popular being the "extrapolation model" introduced by Fisher, Corbet, and Williams (16) in 1943. It assumes that n independent samples X n ≜ X 1 , . . . , X n were collected from an unknown distribution p, and calls for estimating the number of hitherto unseen symbols that would be observed if m additional samples X n+m n + 1 ≜ X n+1 , . . . , X n+m were collected from the same distribution. In 1956, Good and Toulmin (17) predicted U by a fascinating estimator that has since intrigued statisticians and a broad range of scientists alike (18). For example, in the Stanford University Statistics Department brochure (19), published in the early 1990s and slightly abbreviated here, Bradley Efron credited the problem and its elegant solution with kindling his interest in statistics. As we shall soon see, Efron, along with Ronald Thisted, went on to make significant contributions to this problem. This example evaluates the Good−Toulmin estimator for the special case where the original and future samples are of equal size, namely m = n. To describe the estimator's general form, we need only a modicum of nomenclature. The prevalence Φ i ≜ Φ i ðX n Þ of an integer i ≥ 0 in X n is the number of symbols appearing i times in X n . For example, for X 7 = bananas, Φ 1 = 2 and Φ 2 = Φ 3 = 1, and, in Corbet's table, Φ 1 = 118 In the early 1940s, naturalist Corbet had spent 2 y trapping butterflies in Malaya. At the end of that time, he constructed a table (see below) to show how many times he had trapped various butterfly species. For example, 118 species were so rare that Corbet had trapped only one specimen of each, 74 species had been trapped twice each, etc. Corbet returned to England with his table, and asked R. A. Fisher, the greatest of all statisticians, how many new species he would see if he returned to Malaya for another 2 y of trapping. This question seems impossible to answer, because it refers to a column of Corbet's table that doesn't exist, the "0" column. Fisher provided an interesting answer that was later improved on [by Good and Toulmin (17)]. The number of new species you can expect to see in 2 y of additional trapping is 118 − 74 + 44 − 24 + . . . − 12 + 6 = 75. Many scientific applications ranging from ecology to genetics use a small sample to estimate the number of distinct elements, known as "species," in a population. Classical results have shown that n samples can be used to estimate the number of species that would be observed if the sample size were doubled to 2n. We obtain a class of simple algorithms that extend the estimate all the way to n log n samples, and we show that this is also the largest possible estimation range. Therefore, statistically speaking, the proverbial bird in the hand is worth log n in the bush. The proposed estimators outperform existing ones on several synthetic and real datasets collected in various disciplines.
Despite there are several estimators for the unseen species problem (for example, the Good-Toulmin estimator and its extensions REF ), the problem tackled here is different in an important aspect.
Optimal prediction of the number of unseen species
Proceedings of the National Academy of Sciences of the United States of America
Proceedings of the National Academy of Sciences of the United States of America
Mathematics Medicine