Optimal Prediction of the Number of Unseen Species with Multiplicity Yi Hao
–Neural Information Processing Systems
Based on a sample of size n, we consider estimating the number of symbols that appear at least µ times in an independent sample of size a n, where a is a given parameter. This formulation includes, as a special case, the well-known problem of inferring the number of unseen species introduced by [Fisher et al.] in 1943 and considered by many others. Of considerable interest in this line of works is the largest a for which the quantity can be accurately predicted. We completely resolve this problem by determining the limit of estimation to be a (log n)/µ, with both lower and upper bounds matching up to constant factors. For the particular case of µ = 1, this implies the recent result by [Orlitsky et al.] on the unseen species problem. Experimental evaluations show that the proposed estimator performs exceptionally well in practice. Furthermore, the estimator is a linear combination of symbols' empirical counts, and hence linear-time computable.
Neural Information Processing Systems
Jan-24-2025, 23:30:14 GMT
- Country:
- North America > United States (1.00)
- Industry:
- Government > Regional Government (0.46)
- Technology: