×

Multi-armed bandit for species discovery: a Bayesian nonparametric approach. (English) Zbl 1404.62030

Summary: Let \((P_1,\dots, P_J)\) denote \(J\) populations of animals from distinct regions. A priori, it is unknown which species are present in each region and what are their corresponding frequencies. Species are shared among populations and each species can be present in more than one region with its frequency varying across populations. In this article, we consider the problem of sequentially sampling these populations to observe the greatest number of different species. We adopt a Bayesian nonparametric approach and endow \((P_1,\dots, P_J)\) with a hierarchical Pitman-Yor process prior. As a consequence of the hierarchical structure, the \(J\) unknown discrete probability measures share the same support, that of their common random base measure. Given this prior choice, we propose a sequential rule that, at every time step, given the information available up to that point, selects the population from which to collect the next observation. Rather than picking the population with the highest posterior estimate of producing a new value, the proposed rule includes a Thompson sampling step to better balance the exploration – exploitation trade-off. We also propose an extension of the algorithm to deal with incidence data, where multiple observations are collected in a time period. The performance of the proposed algorithms is assessed through a simulation study and compared to three other strategies. Finally, we compare these algorithms using a dataset of species of trees, collected from different plots in South America.

MSC:

62G05 Nonparametric estimation
62F15 Bayesian inference
62P10 Applications of statistics to biology and medical sciences; meta analysis

References:

[1] Agrawal, S.; Goyal, N., Analysis of Thompson sampling for the multi-armed bandit problem, JMLR: Workshop and Conference Proceedings, 23, 39.1-39.26, (2012)
[2] Auer, P.; Cesa-Bianchi, N.; Fischer, P., Finite-time analysis of the multiarmed bandit problem, Machine Learning, 47, 235-256, (2002) · Zbl 1012.68093
[3] Barger, K.; Bunge, J., Objective Bayesian estimation of the number of species, Bayesian Analysis, 5, 619-639, (2010)
[4] Basu, D., Role of the sufficiency and likelihood principles in sample survey theory, Sankhya, 31, 441-454, (1969) · Zbl 0214.46504
[5] Bubeck, S.; Cesa-Bianchi, N., Regret analysis of stochastic and nonstochastic multi-armed bandit problems, Foundations and Trends in Machine Learning, 5, 1-122, (2012) · Zbl 1281.91051
[6] Bubeck, S.; Ernst, D.; Garivier, A., Optimal discovery with probabilistic expert advice: finite time analysis and macroscopic optimality, Journal of Machine Learning Research, 14, 601-623, (2013) · Zbl 1305.68140
[7] Chao, A., On estimating the probability of discovering a new species, The Annals of Statistics, 9, 1339-1342, (1981) · Zbl 0477.62016
[8] Chao, A.; Lee, S. M., Estimating the number of classes via sample coverage, Journal of the American Statistical Association, 87, 210-217, (1992) · Zbl 0850.62145
[9] Chapelle, O.; Li, L., An empirical evaluation of Thompson sampling, Advances in Neural Information Processing Systems, 24, 1-9, (2011)
[10] Cochran, W. G., Sampling Techniques, (1977), Wiley, New York · Zbl 0353.62011
[11] Condit, R.; Pitman, N.; Leigh, E. G.; Chave, J.; Terborgh, J.; Foster, R. B.; Nunez, P.; Aguilar, S.; Valencia, R.; Villa, G.; Muller-Landau, H. C.; Losos, E.; Hubbell, S. P., Beta-diversity in tropical forest trees, Science, 295, 666-669, (2002)
[12] Duan, J. A.; Guindani, M.; Gelfand, A. E., Generalized spatial Dirichlet process models, Biometrika, 77, 1-11, (2007) · Zbl 1156.62064
[13] Efron, B.; Thisted, R., Estimating the number of unseen species: how many words did shakespeare know?, Biometrika, 63, 435-447, (1976) · Zbl 0344.62088
[14] Favaro, S.; Lijoi, A.; Prünster, I., A new estimator of the discovery probability, Biometrics, 68, 1188-1196, (2012) · Zbl 1259.62110
[15] Ferguson, T. S., A Bayesian analysis of some nonparametric problems, The Annals of Statistics, 1, 209-230, (1973) · Zbl 0255.62037
[16] Fonteneau-Belmudes, F.; Ernst, D.; Druet, P.; Panciatici, P.; Wehenkel, L., Consequence driven decomposition of large-scale power system security analysis, Proceedings of the 2010 IREP Symposium, VIII, 1-8, (2010)
[17] Gelfand, A. E.; Guindani, M.; Petrone, S.; Bernardo, J. M.; Bayarri, M. J.; Berger, J. O.; Dawid, A. P.; Heckerman, D.; Smith, A. F. M.; West, M., Bayesian Statistics, 8, Bayesian nonparametric modeling for spatial data analysis using Dirichlet processes, 1-26, (2007), Oxford University Press, Oxford, UK
[18] Gelfand, A. E.; Kottas, A.; MacEachern, S. N., Bayesian nonparametric spatial modelling with Dirichlet processes mixing, Journal of the American Statistical Association, 100, 1021-1035, (2005) · Zbl 1117.62342
[19] Goldwater, S.; Griffiths, T.; Johnson, M., Advances in Neural Information Processing Systems, 18, Interpolating between types and tokens by estimating power-law generators, 459-466, (2006), MIT Press, Cambridge, MA
[20] Good, I. J., The population frequencies of species and the estimation of population parameters, Biometrika, 40, 237-264, (1953) · Zbl 0051.37103
[21] Good, I. J.; Toulmin, G. H., The number of new species, and the increase in population coverage, when a sample is increased, Biometrika, 43, 45-63, (1956) · Zbl 0070.14403
[22] Granmo, O. C., Solving two-armed Bernoulli bandit problems using a Bayesian learning automaton, International Journal of Intelligent Computing and Cybernetics, 3, 207-234, (2010) · Zbl 1205.68200
[23] Griffin, J. E.; Steel, M. F. J., Order-based dependent Dirichlet processes, Journal of the American Statistical Association, 101, 179-194, (2006) · Zbl 1118.62360
[24] Ionita-Laza, I.; Laird, N. M., On the optimal design of genetic variant discovery studies, Statistical Applications in Genetics and Molecular Biology, 9, 33.1-33.17, (2010) · Zbl 1304.92089
[25] Ionita-Laza, I.; Lange, C.; Laird, N. M., Estimating the number of unseen variants in the human genome, Proceedings of the National Academy of Sciences, 106, 5008-5013, (2009) · Zbl 1202.92059
[26] Kaufmann, E.; Korda, N.; Munos, R., Thompson sampling: an optimal finite-time analysis, Proceedings of the 23rd International Conference on Algorithmic Learning Theory, 199-213, (2012) · Zbl 1386.91055
[27] Lai, T. L.; Robbins, H., Asymptotically efficient adaptive allocation rules, Advances in Applied Mathematics, 6, 4-22, (1985) · Zbl 0568.62074
[28] Lijoi, A.; Mena, R. H.; Prünster, I., Bayesian nonparametric estimation of the probability of discovering new species, Biometrika, 94, 715-740, (2007) · Zbl 1156.62374
[29] MacEachern, S. N., ASA Proceedings of the Section on Bayesian Statistical Science, Dependent nonparametric processes, 50-55, (1999), American Statistical Association, Alexandria, VA
[30] Mao, C. X., Predicting the conditional probability of discovering a new class, Journal of the American Statistical Association, 99, 1108-1118, (2004) · Zbl 1055.62007
[31] Mao, C. X.; Lindsay, B. G., A Poisson model for the coverage problem with a genomic application, Biometrika, 89, 669-681, (2002) · Zbl 1037.62115
[32] May, B. C.; Leslie, D. S., Simulation studies in optimistic Bayesian sampling in contextual-bandit problems, (2011)
[33] Mitzenmacher, M., A brief history of generative models for power law and lognormal distributions, Internet Mathematics, 1, 226-251, (2004) · Zbl 1063.68526
[34] Petrone, S.; Guindani, M.; Gelfand, A. E., Hybrid Dirichlet mixture models for functional data, Journal of the Royal Statistical Society, 71, 755-782, (2009) · Zbl 1248.62079
[35] Pitman, J.; Ferguson, T. S.; Shapley, L. S.; MacQueen, J. B., Statistics, Probability and Game Theory, Some developments of the blackwell-macqueen urn scheme, 245-267, (1996), Institute of Mathematical Statistics, Hayward, CA · Zbl 0996.60500
[36] Pitman, J.; Yor, M., The two parameter Poisson-Dirichlet distribution derived from a stable subordinator, Annals of Probability, 25, 855-900, (1997) · Zbl 0880.60076
[37] Pyke, C. R.; Condit, R.; Aguilar, S.; Lao, S., Floristic composition across a climatic gradient in a neotropical lowland forest, Journal of Vegetation Science, 12, 553-566, (2001)
[38] Reich, B.; Fuentes, M., A multivariate semiparametric Bayesian spatial modeling framework for hurricane surface wind fields, Annals of Applied Statistics, 1, 249-264, (2007) · Zbl 1129.62114
[39] Russo, D.; Van Roy, B., Learning to optimize via posterior sampling, Mathematics of Operations Research, 39, 1221-1243, (2014) · Zbl 1310.93091
[40] An information-theoretic analysis of Thompson sampling, Journal of Machine Learning Research, 17, 1-30, (2016) · Zbl 1360.62030
[41] Scott, S., A modern Bayesian look at the multi-armed bandit, Applied Stochastic Models in Business and Industry, 26, 639-658, (2010)
[42] Steel, M. F. J.; Fuentes, M.; Gelfand, A. E.; Diggle, P. J.; Fuentes, M.; Guttorp, P., Handbook of Spatial Statistics, Non-Gaussian and nonparametric models for continuous spatial data, 149-167, (2010), CRC Press, Boca Raton, FL · Zbl 1188.62284
[43] Teh, Y. W., Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, A hierarchical Bayesian language model based on Pitman Yor processes, 985-992, (2006), Association for Computational Linguistics, Morristown
[44] Teh, Y. W.; Jordan, M.; Hjort, N. L.; Holmes, C.; Müller, P.; Walker, S. G., Bayesian Nonparametrics, Hierarchical Bayesian nonparametric models with applications, 158-207, (2010), Cambridge University Press, Cambridge, UK
[45] Thompson, S. K., Adaptive cluster sampling, Journal of the American Statistical Association, 85, 1050-1059, (1990) · Zbl 1330.62070
[46] Stratified adaptive cluster sampling, Biometrika, 78, 389-397, (1991)
[47] Adaptive cluster sampling: designs with primary and secondary units, Biometrics, 47, 1103-1115, (1991)
[48] An adaptive procedure for sampling animal populations, Biometrics, 48, 1195-1199, (1992)
[49] Sampling, (2002), Wiley, New York · Zbl 1002.62012
[50] Thompson, S. K.; Seber, G. A. F., Adaptive Sampling, (1996), Wiley, New York · Zbl 0860.62008
[51] Thompson, W. R., On the likelihood that one unknown probability exceeds another in view of the evidence of two samples, Biometrika, 25, 285-294, (1933) · JFM 59.1159.03
[52] Whittaker, R. H., Vegetation of the siskiyou mountains, Ecological Monographs, 30, 279-338, (1960)
[53] Zacks, S., Bayes sequential designs of fixed size samples from finite populations, Journal of the American Statistical Association, 64, 1342-1349, (1969) · Zbl 0186.51902
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.