{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:32Z","timestamp":1763468012879},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540222828"},{"type":"electronic","value":"9783540278191"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27819-1_12","type":"book-chapter","created":{"date-parts":[[2010,9,14]],"date-time":"2010-09-14T06:05:39Z","timestamp":1284444339000},"page":"170-185","source":"Crossref","is-referenced-by-count":6,"title":["Concentration Bounds for Unigrams Language Model"],"prefix":"10.1007","author":[{"given":"Evgeny","family":"Drukh","sequence":"first","affiliation":[]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D. Angluin","year":"1979","unstructured":"Angluin, D., Valiant, L.G.: Fast Probabilistic Algorithms for Hamiltonian Circuits and matchings. Journal of Computer and System Sciences\u00a018, 155\u2013193 (1979)","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR2","unstructured":"Chen, S.F.: Building Probabilistic Models for Natural Language. Ph.D. Thesis, Harvard University (1996)"},{"key":"12_CR3","unstructured":"Chen, S.F., Goodman, J.: An Empirical Study of Smoothing Techniques for Language Modeling. Technical Report TR-10-98, Harvard University (1998)"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0885-2308(91)90016-J","volume":"5","author":"K.W. Church","year":"1991","unstructured":"Church, K.W., Gale, W.A.: A Comparison of the Enhanced Good-Turing and Deleted Estimation Methods for Estimating Probabilities of English Bigrams. Computer Speech and Language\u00a05, 19\u201354 (1991)","journal-title":"Computer Speech and Language"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Curran, J.R., Osborne, M.: A Very Very Large Corpus Doesn\u2019t Always Yield Reliable Estimates. In: Proceedings of the Sixth Conference on Natural Language Learning, pp. 126\u2013131 (2002)","DOI":"10.3115\/1118853.1118861"},{"key":"12_CR6","doi-asserted-by":"crossref","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.: A Probabilistic Theory of Pattern Recognition. Springer, New York (1996)"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Drukh, E.: Concentration Bounds for Unigrams Language Model, M.Sc. Thesis, Tel. Aviv. University (2004)","DOI":"10.1007\/978-3-540-27819-1_12"},{"issue":"2","key":"12_CR8","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M","volume":"13","author":"D.P. Dubhashi","year":"1998","unstructured":"Dubhashi, D.P., Ranjan, D.: Balls and Bins: A Study in Negative Dependence. Random Structures and Algorithms\u00a013(2), 99\u2013124 (1998)","journal-title":"Random Structures and Algorithms"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1080\/09296179508590051","volume":"2","author":"W. Gale","year":"1995","unstructured":"Gale, W.: Good-Turing Smoothing Without Tears. Journal of Quantitative Linguistics\u00a02, 217\u2013237 (1995)","journal-title":"Journal of Quantitative Linguistics"},{"issue":"16","key":"12_CR10","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1093\/biomet\/40.3-4.237","volume":"40","author":"I.J. Good","year":"1953","unstructured":"Good, I.J.: The Population Frequencies of Species and the Estimation of Population Parameters. Biometrika\u00a040(16), 237\u2013264 (1953)","journal-title":"Biometrika"},{"issue":"2","key":"12_CR11","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1080\/00949650008812016","volume":"66","author":"I.J. Good","year":"2000","unstructured":"Good, I.J.: Turing\u2019s Anticipation of Empirical Bayes in Connection with the Cryptanalysis of the Naval Enigma. Journal of Statistical Computation and Simulation\u00a066(2), 101\u2013112 (2000)","journal-title":"Journal of Statistical Computation and Simulation"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1214\/aoms\/1177728178","volume":"27","author":"W. Hoeffding","year":"1956","unstructured":"Hoeffding, W.: On the Distribution of the Number of Successes in Independent Trials. Annals of Mathematical Statistics\u00a027, 713\u2013721 (1956)","journal-title":"Annals of Mathematical Statistics"},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"13","DOI":"10.2307\/2282952","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association\u00a058, 13\u201330 (1963)","journal-title":"Journal of the American Statistical Association"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Holden, S.B.: PAC-like Upper Bounds for the Sample Complexity of Leave-One- Out Cross-Validation. In: Proceesings of the Ninth Annual ACM Workshop on Computational Learning Theory, pp. 41\u201350 (1996)","DOI":"10.1145\/238061.238067"},{"issue":"3","key":"12_CR15","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1109\/TASSP.1987.1165125","volume":"35","author":"S.M. Katz","year":"1987","unstructured":"Katz, S.M.: Estimation of Probabilities from Sparse Data for the Language Model Component of a Speech Recognizer. IEEE Transactions on Acoustics, Speech and Signal Processing\u00a035(3), 400\u2013401 (1987)","journal-title":"IEEE Transactions on Acoustics, Speech and Signal Processing"},{"issue":"6","key":"12_CR16","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1162\/089976699300016304","volume":"11","author":"M. Kearns","year":"1999","unstructured":"Kearns, M., Ron, D.: Algorithmic Stability and Sanity-Check Bounds for Leave- One-Out Cross-Validation. Neural Computation\u00a011(6), 1427\u20131453 (1999)","journal-title":"Neural Computation"},{"key":"12_CR17","unstructured":"Kutin, S.: Algorithmic Stability and Ensemble-Based Learning, Ph.D. Thesis, University of Chicago (2002)"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1162\/1532443041424292","volume":"4","author":"D. McAllester","year":"2003","unstructured":"McAllester, D., Ortiz, L.: Concentration Inequalities for the Missing Mass and for Histogram Rule Error. Journal of Machine Learning Research, Special Issue on Learning Theory\u00a04, 895\u2013911 (2003)","journal-title":"Journal of Machine Learning Research, Special Issue on Learning Theory"},{"key":"12_CR19","unstructured":"McAllester, D., Schapire, R.E.: On the Convergence Rate of Good-Turing Estimators. In: Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, pp. 1\u20136 (2000)"},{"key":"12_CR20","unstructured":"McAllester, D., Schapire, R.E.: Learning Theory and Language Modeling. In: Seventeenth International Joint Conference on Artificial Intelligence (2001)"},{"key":"12_CR21","first-page":"148","volume-title":"Surveys in Combinatorics","author":"C. McDiarmid","year":"1989","unstructured":"McDiarmid, C.: On the Method of Bounded Differences. In: Surveys in Combinatorics, pp. 148\u2013188. Cambridge University Press, Cambridge (1989)"},{"issue":"Oct","key":"12_CR22","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1126\/science.1088284","volume":"302","author":"A. Orlitsky","year":"2003","unstructured":"Orlitsky, A., Santhanam, N.P., Zhang, J.: Always Good Turing: Asymptotically Optimal Probability Estimation. Science\u00a0302(Oct), 427\u2013431 (2003) (in Reports)","journal-title":"Science"}],"container-title":["Lecture Notes in Computer Science","Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27819-1_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:22:54Z","timestamp":1605759774000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27819-1_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540222828","9783540278191"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27819-1_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}