{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,4]],"date-time":"2024-07-04T10:36:06Z","timestamp":1720089366298},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2019,6,18]],"date-time":"2019-06-18T00:00:00Z","timestamp":1560816000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,18]],"date-time":"2019-06-18T00:00:00Z","timestamp":1560816000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1007\/s10994-019-05814-1","type":"journal-article","created":{"date-parts":[[2019,6,18]],"date-time":"2019-06-18T21:17:30Z","timestamp":1560892650000},"page":"2087-2111","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Speculate-correct error bounds for k-nearest neighbor classifiers"],"prefix":"10.1007","volume":"108","author":[{"given":"Eric","family":"Bax","sequence":"first","affiliation":[]},{"given":"Lingjie","family":"Weng","sequence":"additional","affiliation":[]},{"given":"Xu","family":"Tian","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,18]]},"reference":[{"key":"5814_CR1","unstructured":"Audibert, J. -Y. (2004). PAC-Bayesian Statistical Learning Theory. Ph.D. thesis, Laboratoire de Probabilities et Modeles Aleatoires, Universites Paris 6 and Paris 7. \n                    http:\/\/cermis.enpc.fr\/~audibert\/ThesePack.zip\n                    \n                  ."},{"key":"5814_CR2","first-page":"1741","volume":"9","author":"E Bax","year":"2008","unstructured":"Bax, E. (2008). Nearly uniform validation improves compression-based error bounds. Journal of Machine Learning Research, 9, 1741\u20131755.","journal-title":"Journal of Machine Learning Research"},{"issue":"5","key":"5814_CR3","doi-asserted-by":"crossref","first-page":"3225","DOI":"10.1109\/TIT.2011.2180887","volume":"58","author":"E Bax","year":"2012","unstructured":"Bax, E. (2012). Validation of $$k$$-nearest neighbor classifiers. IEEE Transactions on Information Theory, 58(5), 3225\u20133234.","journal-title":"IEEE Transactions on Information Theory"},{"key":"5814_CR4","first-page":"581","volume":"9","author":"E Bax","year":"2008","unstructured":"Bax, E., & Callejas, A. (2008). An error bound based on a worst likely assignment. Journal of Machine Learning Research, 9, 581\u2013613.","journal-title":"Journal of Machine Learning Research"},{"key":"5814_CR5","unstructured":"Bax, E., Li, J., Sonmez, A., & Cataltepe, Z. (2013). Validating collective classification using cohorts. In NIPS workshop on frontiers of network analysis: methods, models, and applications."},{"key":"5814_CR6","unstructured":"Bax, E., & Kooti, F. (2016). Ensemble validation: Selectivity has a price, but variety is free (pg. 3, Inequalities 8 and 9). Baylearn 2016. \n                    https:\/\/arxiv.org\/pdf\/1610.01234.pdf\n                    \n                  ."},{"issue":"297","key":"5814_CR7","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1080\/01621459.1962.10482149","volume":"57","author":"G Bennett","year":"1962","unstructured":"Bennett, G. (1962). Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association, 57(297), 33\u201345.","journal-title":"Journal of the American Statistical Association"},{"key":"5814_CR8","doi-asserted-by":"crossref","unstructured":"Blum, A., & Langford, J. (2003) PAC-MDL bounds. In Proceedings of the 16th annual conference on computational learning theory (COLT) (pp. 344\u2013357).","DOI":"10.1007\/978-3-540-45167-9_26"},{"issue":"3","key":"5814_CR9","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0012-365X(79)90084-0","volume":"25","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V. (1979). The tail of the hypergeometric distribution. Discrete Mathematics, 25(3), 285\u2013287.","journal-title":"Discrete Mathematics"},{"key":"5814_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801389","volume-title":"An introduction to support vector machines and other Kernel-based learning methods","author":"N Cristianini","year":"2000","unstructured":"Cristianini, N., & Shawe-Taylor, J. (2000). An introduction to support vector machines and other Kernel-based learning methods. Cambridge: Cambridge University Press."},{"key":"5814_CR11","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1109\/TIT.1979.1056032","volume":"25","author":"L Devroye","year":"1979","unstructured":"Devroye, L., & Wagner, T. (1979). Distribution-free inequalities for the deleted and holdout estimates. IEEE Transactions on Information Theory, 25, 202\u2013207.","journal-title":"IEEE Transactions on Information Theory"},{"key":"5814_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0711-5","volume-title":"A probabilistic theory of pattern recognition","author":"L Devroye","year":"1996","unstructured":"Devroye, L., Gy\u00f6rfi, L., & Lugosi, G. (1996). A probabilistic theory of pattern recognition. Berlin: Springer."},{"key":"5814_CR13","volume-title":"Pattern classification","author":"RO Duda","year":"2001","unstructured":"Duda, R. O., Hart, P. E., & Stork, D. G. (2001). Pattern classification. New York: Wiley."},{"issue":"3","key":"5814_CR14","first-page":"1","volume":"21","author":"S Floyd","year":"1995","unstructured":"Floyd, S., & Warmuth, M. (1995). Sample compression, learnability, and the Vapnik\u2013Chervonenkis dimension. Machine Learning, 21(3), 1\u201336.","journal-title":"Machine Learning"},{"key":"5814_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-84858-7","volume-title":"The elements of statistical learning: Data mining, inference, and prediction","author":"T Hastie","year":"2009","unstructured":"Hastie, T., Tibshirani, R., & Friedman, J. (2009). The elements of statistical learning: Data mining, inference, and prediction (2nd ed.). Berlin: Springer.","edition":"2"},{"issue":"301","key":"5814_CR16","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301), 13\u201330.","journal-title":"Journal of the American Statistical Association"},{"key":"5814_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0907-3","volume-title":"Learning to classify text using support vector machines","author":"T Joachims","year":"2002","unstructured":"Joachims, T. (2002). Learning to classify text using support vector machines. London: Kluwer Academic Publishers."},{"key":"5814_CR18","unstructured":"Kedem, D., Tyree, S., Sha, F., Lanckriet, G.\u00a0R. & Weinberger, K.\u00a0Q. (2012). Non-linear metric learning. In Pereira, F., Burges, C. J. C., Bottou, L., & Weinberger, K. Q. (Eds.), Advances in neural information processing systems (Vol. 25, pp. 2573\u20132581). Curran Associates, Inc. \n                    http:\/\/papers.nips.cc\/paper\/4840-non-linear-metric-learning.pdf\n                    \n                  ."},{"key":"5814_CR19","first-page":"273","volume":"6","author":"J Langford","year":"2005","unstructured":"Langford, J. (2005). Tutorial on practical prediction theory for classification. Journal of Machine Learning Research, 6, 273\u2013306.","journal-title":"Journal of Machine Learning Research"},{"key":"5814_CR20","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/978-3-642-34166-3_49","volume":"7626","author":"J Li","year":"2012","unstructured":"Li, J., Sonmez, A., Cataltepe, Z., & Bax, E. (2012). Validation of network classifiers. Structural, Syntactic, and Statistical Pattern Recognition Lecture Notes in Computer Science, 7626, 448\u2013457.","journal-title":"Structural, Syntactic, and Statistical Pattern Recognition Lecture Notes in Computer Science"},{"key":"5814_CR21","unstructured":"Littlestone, N., & Warmuth, M. (1986). Relating data compression and learnability. Unpublished manuscript, University of California, Santa Cruz."},{"key":"5814_CR22","unstructured":"London, B., Huang, B., & Getoor, L. (2012). Improved generalization bounds for large-scale structured prediction. In NIPS workshop on algorithmic and statistical approaches for large social networks."},{"key":"5814_CR23","first-page":"935","volume":"8","author":"SA Macskassy","year":"2007","unstructured":"Macskassy, S. A., & Provost, F. (2007). Classification in networked data: A toolkit and a univariate case study. Journal of Machine Learning Research, 8, 935\u2013983.","journal-title":"Journal of Machine Learning Research"},{"key":"5814_CR24","unstructured":"Marchand, M., & Shawe-Taylor, J. (2001). Learning with the set covering machine. In Proceedings of the eighteenth international conference on machine learning (ICML 2001) (pp. 345\u2013352)."},{"key":"5814_CR25","unstructured":"Maurer, A., & Pontil, M. (2009). Empirical Bernstein bounds and sample-variance penalization. In 22nd annual conference on learning theory (COLT). \n                    http:\/\/www0.cs.ucl.ac.uk\/staff\/M.Pontil\/reading\/svp-final.pdf\n                    \n                  ."},{"key":"5814_CR26","unstructured":"Mullin, M., & Sukthankar, R. (2000). Complete cross-validation for nearest neighbor classifiers. In Proceedings of the seventeenth international conference on machine learning (pp. 639\u2013646)."},{"issue":"3","key":"5814_CR27","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1609\/aimag.v29i3.2157","volume":"29","author":"P Sen","year":"2008","unstructured":"Sen, P., Namata, G., Bilgic, M., Getoor, L., Gallagher, B., & Eliassi-Rad, T. (2008). Collective classification in network data. AI Magazine, 29(3), 93\u2013106.","journal-title":"AI Magazine"},{"key":"5814_CR28","unstructured":"Skala, M. (2013). Hypergeometric tail inequalities: Ending the insanity. arXiv \n                    arXiv:1311.5939v1\n                    \n                  . \n                    https:\/\/arxiv.org\/abs\/1311.5939v1\n                    \n                  ."},{"issue":"11","key":"5814_CR29","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27(11), 1134\u20131142. \n                    https:\/\/doi.org\/10.1145\/1968.1972\n                    \n                  . (ISSN: 0001-0782).","journal-title":"Communications of the ACM"},{"key":"5814_CR30","volume-title":"Statistical learning theory","author":"V Vapnik","year":"1998","unstructured":"Vapnik, V. (1998). Statistical learning theory. New York: Wiley."},{"key":"5814_CR31","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V Vapnik","year":"1971","unstructured":"Vapnik, V., & Chervonenkis, A. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16, 264\u2013280.","journal-title":"Theory of Probability and its Applications"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-019-05814-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10994-019-05814-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-019-05814-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,18]],"date-time":"2020-06-18T00:11:18Z","timestamp":1592439078000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10994-019-05814-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,18]]},"references-count":31,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["5814"],"URL":"https:\/\/doi.org\/10.1007\/s10994-019-05814-1","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,18]]},"assertion":[{"value":"22 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}