{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T00:52:54Z","timestamp":1768524774402,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1999,12,1]],"date-time":"1999-12-01T00:00:00Z","timestamp":944006400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1999,12,1]],"date-time":"1999-12-01T00:00:00Z","timestamp":944006400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Machine Learning"],"published-print":{"date-parts":[[1999,12]]},"DOI":"10.1023\/a:1007666507971","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T05:54:50Z","timestamp":1040536490000},"page":"337-354","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["The Complexity of Learning According to Two Models of a Drifting Environment"],"prefix":"10.1007","volume":"37","author":[{"given":"Philip M.","family":"Long","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"241753_CR1","doi-asserted-by":"crossref","unstructured":"Anthony, M. Biggs, N., & Shawe-Taylor, J. (1990). The learnability of formal concepts. Proceedings of the 1990 Workshop on Computational Learning Theory (pp. 246\u2013257).","DOI":"10.1016\/B978-1-55860-146-8.50022-9"},{"key":"241753_CR2","doi-asserted-by":"crossref","unstructured":"Auer P., & Warmuth, M.K. (1995). Tracking the best disjunction. Proceedings of the 36th Annual Symposium on the Foundations of Computer Science.","DOI":"10.1109\/SFCS.1995.492487"},{"key":"241753_CR3","doi-asserted-by":"crossref","unstructured":"Bartlett, P.L. (1992). Learning with a slowly changing distribution. Proceedings of the 1992 Workshop on Computational Learning Theory (pp. 243\u2013252).","DOI":"10.1145\/130385.130412"},{"key":"241753_CR4","doi-asserted-by":"crossref","unstructured":"Bartlett, P.L., Ben-David, S., & Kulkarni, S.R. (1996). Learning changing concepts by exploiting the structure of change. Proceedings of the 1996 Conference on Computational Learning Theory (pp. 131\u2013139).","DOI":"10.1145\/238061.238080"},{"key":"241753_CR5","unstructured":"Bartlett, P.L., & Helmbold, D.P. (1995). Manuscript."},{"issue":"2","key":"241753_CR6","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1006\/inco.1997.2656","volume":"138","author":"R.D. Barve","year":"1997","unstructured":"Barve, R.D., & Long, P.M. (1997). On the complexity of learning from drifting distributions. Information and Computation, 138(2), 101\u2013123.","journal-title":"Information and Computation"},{"key":"241753_CR7","doi-asserted-by":"crossref","unstructured":"Blum, A., & Chalasani, P. (1992). Learning switching concepts. Proceedings of the Fifth Annual Workshop on Computational Learning Theory (pp. 231\u2013242).","DOI":"10.1145\/130385.130411"},{"issue":"4","key":"241753_CR8","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M.K. (1989). Learnability and the Vapnik-Chervonenkis dimension. JACM, 36(4), 929\u2013965.","journal-title":"JACM"},{"key":"241753_CR9","doi-asserted-by":"crossref","unstructured":"Freund, Y., & Mansour, Y. (1997). Learning under persistent drift. Proceedings of the 1997 European Conference on Computational Learning Theory.","DOI":"10.1007\/3-540-62685-9_10"},{"key":"241753_CR10","doi-asserted-by":"crossref","unstructured":"Freund, Y., & Ron, D. (1995). Learning to model sequences generated by switching distributions. Proceedings of the 1995 Conference on Computational Learning Theory (pp. 41\u201350).","DOI":"10.1145\/225298.225303"},{"issue":"1","key":"241753_CR11","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/0890-5401(92)90010-D","volume":"100","author":"D. Haussler","year":"1992","unstructured":"Haussler, D. (1992). Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1), 78\u2013150.","journal-title":"Information and Computation"},{"issue":"2","key":"241753_CR12","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0097-3165(95)90052-7","volume":"69","author":"D. Haussler","year":"1995","unstructured":"Haussler, D. (1995). Sphere packing numbers for subsets of the boolean n-cube with bounded Vapnik-Chervonenkis dimension. Journal of Combinatorial Theory, Series A, 69(2), 217\u2013232.","journal-title":"Journal of Combinatorial Theory, Series A"},{"issue":"2","key":"241753_CR13","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1006\/inco.1994.1097","volume":"115","author":"D. Haussler","year":"1994","unstructured":"Haussler, D., Littlestone, N., & Warmuth, M.K. (1994). Predicting {0; 1}-functions on randomly drawn points. Information and Computation, 115(2), 129\u2013161.","journal-title":"Information and Computation"},{"issue":"1","key":"241753_CR14","first-page":"27","volume":"14","author":"D.P. Helmbold","year":"1994","unstructured":"Helmbold, D.P., & Long, P.M. (1994).Tracking drifting concepts by minimizing disagreements. Machine Learning, 14(1), 27\u201346.","journal-title":"Machine Learning"},{"key":"241753_CR15","unstructured":"Herbster, M., & Warmuth, M.K. (1995). Tracking the best expert. Proceedings of of the Twelvth International Conference on Machine Learning."},{"key":"241753_CR16","doi-asserted-by":"crossref","unstructured":"Herbster, M., & Warmuth, M.K. (1998). Tracking the best regressor. Proceedings of the 1998 Conference on Computational Learning Theory.","DOI":"10.1145\/279943.279949"},{"key":"241753_CR17","first-page":"115","volume":"17","author":"M.J. Kearns","year":"1994","unstructured":"Kearns, M.J., Schapire, R.E., & Sellie, L.M. (1994). Toward efficient agnostic learning. Machine Learning, 17, 115\u2013141.","journal-title":"Machine Learning"},{"key":"241753_CR18","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1090\/trans2\/017\/10","volume":"17","author":"A.N. Kolmogorov","year":"1961","unstructured":"Kolmogorov, A.N., & Tihomirov, V.M. (1961). \n$$\\varepsilon $$\n-entropy and \n$$\\varepsilon $$\n-capacity of sets in functional spaces. American Mathematical Society Translations (Ser. 2), 17, 277\u2013364.","journal-title":"American Mathematical Society Translations (Ser. 2)"},{"issue":"3","key":"241753_CR19","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1109\/78.558480","volume":"45","author":"A. Kuh","year":"1997","unstructured":"Kuh, A. (1997). Comparison of tracking algorithms for single layer threshold networks in the presence of random drift. IEEE Trans. on Signal Processing, 45(3), 640\u2013650.","journal-title":"IEEE Trans. on Signal Processing"},{"key":"241753_CR20","unstructured":"Kuh, A., Petsche, T., & Rivest, R. (1990). Learning time varying concepts. In NIPS 3. Morgan Kaufmann."},{"key":"241753_CR21","unstructured":"Kuh, A., Petsche, T., & Rivest, R. (1991). Mistake bounds of incremental learners when concepts drift with applications to feedforward networks. In NIPS 4. Morgan Kaufmann."},{"key":"241753_CR22","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1006\/inco.1994.1009","volume":"108","author":"N. Littlestone","year":"1994","unstructured":"Littlestone, N., & Warmuth, M.K. (1994). The weighted majority algorithm. Information and Computation, 108, 212\u2013261.","journal-title":"Information and Computation"},{"key":"241753_CR23","doi-asserted-by":"crossref","unstructured":"Pollard, D. (1984). Convergence of Stochastic Processes. Springer Verlag.","DOI":"10.1007\/978-1-4612-5254-2"},{"key":"241753_CR24","doi-asserted-by":"crossref","unstructured":"Pollard, D. (1990). Empirical Processes: Theory and Applications, volume 2 of NSF-CBMS Regional Conference Series in Probability and Statistics. Institute of Math. Stat. and Am. Stat. Assoc.","DOI":"10.1214\/cbms\/1462061091"},{"key":"241753_CR25","doi-asserted-by":"crossref","unstructured":"Roy, S. (1991). Semantic complexity of relational queries and data independent data partitioning. Proceedings of the ACM SIGACT-SIGART-SIGMOD Annual Symposium on Principles of Database Systems.","DOI":"10.1145\/113413.113437"},{"key":"241753_CR26","unstructured":"Royden, H.L. (1963). Real Analysis. Macmillan."},{"key":"241753_CR27","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N. Sauer","year":"1972","unstructured":"Sauer, N. (1972). On the density of families of sets. J. Combinatorial Theory (A), 13, 145\u2013147.","journal-title":"J. Combinatorial Theory (A)"},{"key":"241753_CR28","doi-asserted-by":"crossref","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S. Shelah","year":"1972","unstructured":"Shelah, S. (1972). A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math., 41, 247\u2013261.","journal-title":"Pacific J. Math."},{"issue":"2","key":"241753_CR29","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1006\/jcss.1996.0019","volume":"52","author":"H.U. Simon","year":"1996","unstructured":"Simon, H.U. (1996). General lower bounds on the number of examples needed for learning probabilistic concepts. Journal of Computer and System Sciences, 52(2), 239\u2013254.","journal-title":"Journal of Computer and System Sciences"},{"key":"241753_CR30","first-page":"28","volume":"22","author":"M. Talagrand","year":"1994","unstructured":"Talagrand, M. (1994). Sharper bounds for Gaussian and empirical processes. Annals of Probability, 22, 28\u201376.","journal-title":"Annals of Probability"},{"issue":"5","key":"241753_CR31","doi-asserted-by":"crossref","first-page":"897","DOI":"10.1016\/S0893-6080(96)00118-9","volume":"10","author":"X. Tian","year":"1997","unstructured":"Tian, X., & Kuh, A. (1997). Performance bounds for single layer threshold networks when tracking a drifting adversary. Neural Networks, 10(5), 897\u2013906.","journal-title":"Neural Networks"},{"issue":"2","key":"241753_CR32","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V.N. Vapnik","year":"1971","unstructured":"Vapnik, V.N., & Chervonenkis, A.Y. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2), 264\u2013280","journal-title":"Theory of Probability and its Applications"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1007666507971.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1007666507971\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1007666507971.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T11:33:15Z","timestamp":1752147195000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1007666507971"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,12]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1999,12]]}},"alternative-id":["241753"],"URL":"https:\/\/doi.org\/10.1023\/a:1007666507971","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,12]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}