{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T21:13:37Z","timestamp":1780434817333,"version":"3.54.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2006,3,28]],"date-time":"2006-03-28T00:00:00Z","timestamp":1143504000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2006,5]]},"DOI":"10.1007\/s10994-006-6265-7","type":"journal-article","created":{"date-parts":[[2006,3,28]],"date-time":"2006-03-28T17:23:29Z","timestamp":1143566609000},"page":"161-182","source":"Crossref","is-referenced-by-count":103,"title":["An algorithmic theory of learning: Robust concepts and random projection"],"prefix":"10.1007","volume":"63","author":[{"given":"Rosa I.","family":"Arriaga","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Santosh","family":"Vempala","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2006,3,28]]},"reference":[{"key":"6265_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D. (2001). Database friendly random projections. In Proc. Principles of Database Systems (PODS) (pp. 274\u2013281).","DOI":"10.1145\/375551.375608"},{"issue":"3","key":"6265_CR2","doi-asserted-by":"crossref","first-page":"382","DOI":"10.4153\/CJM-1954-037-2","volume":"6","author":"S. Agmon","year":"1954","unstructured":"Agmon, S. (1954). The relaxation method for linear inequalities. Canadian Journal of Mathematics, 6(3), 382\u2013392.","journal-title":"Canadian Journal of Mathematics"},{"key":"6265_CR3","doi-asserted-by":"crossref","unstructured":"Arriaga, R. I., & Vempala, S. (1999). An algorithmic theory of Learning: Robust concepts and random projection. In Proc. of the 39th IEEE Foundations of Computer Science.","DOI":"10.1109\/SFFCS.1999.814637"},{"key":"6265_CR4","doi-asserted-by":"crossref","unstructured":"Balcan, N., Blum, A., & Vempala, S. (2004). On kernels, margins and low-dimensional mappings. In Proc. of Algorithmic Learning Theory.","DOI":"10.1007\/978-3-540-30215-5_16"},{"key":"6265_CR5","doi-asserted-by":"crossref","unstructured":"Bartlett, P., & Shawe-Taylor, J. (1998). Generalization performance of support vector machines and other pattern classifiers, In B., Schvlkopf, C., Burges, & A.J. Smola, (eds.), Advances in kernel methods\u2014support vector learning. MIT press.","DOI":"10.7551\/mitpress\/1130.003.0007"},{"issue":"1","key":"6265_CR6","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0885-064X(90)90012-3","volume":"6","author":"E. B. Baum","year":"1990","unstructured":"Baum, E. B. (1990). On learning a union of half spaces. journal of Complexity, 6(1), 67\u2013101.","journal-title":"journal of Complexity"},{"key":"6265_CR7","first-page":"441","volume":"3","author":"S. Ben-David","year":"2004","unstructured":"Ben-David, S., Eiron, N., & Simon, H.(2004). Limitations of learning via embeddings in euclidean half spaces. Journal of Machine Learning Research, 3, 441\u2013461.","journal-title":"Journal of Machine Learning Research"},{"key":"6265_CR8","doi-asserted-by":"crossref","unstructured":"Blum, A., Frieze, A. Kannan, R., & Vempala, S. (1996). A polynomial-time algorithm for learning noisy linear threshold functions. In Proc. of the 37th IEEE Foundations of Computer Science.","DOI":"10.1109\/SFCS.1996.548492"},{"key":"6265_CR9","doi-asserted-by":"crossref","unstructured":"Blum, A., & Kannan, R. (1993). Learning an intersection of k halfspaces over a uniform distribution. In Proc. of the 34th IEEE Symposium on the Foundations of Computer Science.","DOI":"10.1109\/SFCS.1993.366856"},{"issue":"4","key":"6265_CR10","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. Journal of ACM, 36(4), 929\u2013965.","journal-title":"Journal of ACM"},{"key":"6265_CR11","doi-asserted-by":"crossref","unstructured":"Bylander, T. (1994). Learning linear threshold functions in the presence of classification noise. In Proc 7th Workshop on Computational Learning Theory.","DOI":"10.1145\/180139.181176"},{"key":"6265_CR12","doi-asserted-by":"crossref","unstructured":"Cohen, E. (1997). Learning noisy perceptrons by a perceptron in polynomial time. In Proc. of the 38th IEEE Foundations of Computer Science.","DOI":"10.1109\/SFCS.1997.646140"},{"key":"6265_CR13","first-page":"273","volume":"20","author":"C. Cortes","year":"1995","unstructured":"Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20, 273\u2013297.","journal-title":"Machine Learning"},{"key":"6265_CR14","unstructured":"Dasgupta, S., & Gupta, A. (1999). An elementary proof of the Johnson-Lindenstrauss Lemma. Tech Rep.U.C. Berkeley."},{"key":"6265_CR15","unstructured":"Feller, W. (1957). An introduction to probability theory and its applications. John Wiley and Sons, Inc."},{"key":"6265_CR16","unstructured":"Frankl, P., & Maehara, H. (1988). The Johnson-Lindenstrauss Lemma and the Sphericity of some graphs, J Comb. Theory, B 44, 355\u2013362."},{"issue":"3","key":"6265_CR17","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1023\/A:1007662407062","volume":"37","author":"Y. Freund","year":"1999","unstructured":"Freund, Y., & Schapire, R. E. (1999). \u201cLarge margin classification using the perceptron algorithm. Machine learning, 37(3), 277\u2013296.","journal-title":"Machine learning"},{"key":"6265_CR18","unstructured":"Garg, A., Har-Peled, S., & Roth, D. (2002). On generalization bounds, projection profile, and margin distribution. ICML, 171\u2013178."},{"key":"6265_CR19","unstructured":"Garg, A., & Roth, D. (2003). Margin distribution and learning. ICML, 210\u2013217."},{"key":"6265_CR20","unstructured":"Glass, A.L., Holyoak, K.J., & Santa J.L. (1979). The structure of categories. In Cognition. Addison-Wesley."},{"key":"6265_CR21","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., & Schrijver, A. (1988). Geometric algorithms and combinatorial optimization, Springer.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"6265_CR22","doi-asserted-by":"crossref","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, 13\u201330.","journal-title":"Journal of the American Statistical Association"},{"key":"6265_CR23","doi-asserted-by":"crossref","unstructured":"Indyk, P., & Motwani, R. (1998). Approximate nearest neighbors: Towards removing the curse of dimensionality. In Procedings of ACM STOC.","DOI":"10.1145\/276698.276876"},{"key":"6265_CR24","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W. B. Johnson","year":"1984","unstructured":"Johnson, W. B., & Lindenstrauss, J.(1984). Extensions of lipshitz mapping into Hilbert space. Contemporary Mathematics, 26, 189\u2013206.","journal-title":"Contemporary Mathematics"},{"issue":"3","key":"6265_CR25","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1016\/S0022-0000(05)80062-5","volume":"48","author":"M.J. Kearns","year":"1994","unstructured":"Kearns, M.J., & Schapire, R.E. (1994). Efficient distribution-free learning of probabilistic concepts. Journal of Computer and System Sciences, 48(3), 464\u2013497.","journal-title":"Journal of Computer and System Sciences"},{"key":"6265_CR26","doi-asserted-by":"crossref","unstructured":"Kearns, M.J., & Vazirani, U. (1994). Introduction to computational learning theory. MIT Press.","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"6265_CR27","doi-asserted-by":"crossref","unstructured":"Kleinberg, J. (1997). Two algorithms for nearest-neighbor search in high dimensions. In Procedings 29th ACM Symposium on Theory of Computing.","DOI":"10.1145\/258533.258653"},{"key":"6265_CR28","doi-asserted-by":"crossref","unstructured":"Klivans, A., & Servedio, R. (2004). Learning intersections of halfspaces with a margin, In Procedings 17th Workshop on Computational Learning Theory.","DOI":"10.1007\/978-3-540-27819-1_24"},{"key":"6265_CR29","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S1364-6613(99)01292-9","volume":"3","author":"B. Knowlton","year":"1999","unstructured":"Knowlton, B. (1999). What can neuropsychology tell us about category learning. Trends in Cognitive Science, 3, 123\u2013124.","journal-title":"Trends in Cognitive Science"},{"key":"6265_CR30","doi-asserted-by":"crossref","unstructured":"Komatsu, L.K. (1992). Recent views on conceptual structure. Psychological Bulletin, 112(3).","DOI":"10.1037\/0033-2909.112.3.500"},{"key":"6265_CR31","doi-asserted-by":"crossref","unstructured":"Linial, N., London, E., & Rabinovich, Y. (1994). The geometry of graphs and some of its algorithmic applications. In Proc. of 35th IEEE Foundations of Computer Science.","DOI":"10.1109\/SFCS.1994.365733"},{"key":"6265_CR32","first-page":"285","volume":"2","author":"N. Littlestone","year":"1987","unstructured":"Littlestone, N. (1987). Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2, 285\u2013318.","journal-title":"Machine Learning"},{"key":"6265_CR33","doi-asserted-by":"crossref","unstructured":"Littlestone, N. (1991). Redundant noisy attributes, attribute errors, and linear threshold learning using winnow. In Proc. 4th workshop on computational learning theory.","DOI":"10.1016\/B978-1-55860-213-7.50017-1"},{"key":"6265_CR34","unstructured":"Mandler, J. M. (2003). Conceptual Categorization, Chapter 5. In D. H., Rakinson, & L. M. Oakes, (eds.), Early category and concept development: Making sense of the blooming, buzzing confusion. Oxford University Press."},{"key":"6265_CR35","unstructured":"Minsky, M., & Papert., S., (1969). Perceptrons: An introduction to computational geometry. The MIT press."},{"key":"6265_CR36","unstructured":"Nosofsky, R., & Zaki, S., (1969). Math modeling, neuropsychology, and category learning: Response to B. Knowlton (1999). Trends in Cognitive Science, 3, 125\u2013126, 1999. Perceptrons: An introduction to computational geometry. The MIT press."},{"key":"6265_CR37","unstructured":"Rakinson, D. H., & Oakes, L. M. (eds.), (2003). Early category and concept development: Making sense of the blooming, buzzing confusion. Oxford University Press."},{"key":"6265_CR38","unstructured":"Reed, S. K. (1982). Categorization, in cognition: Theory and applications. brooks\/cole."},{"key":"6265_CR39","doi-asserted-by":"crossref","unstructured":"Reed, S. K., & Friedman, M. P. (1973). Perceptual vs. conceptual categorization. Memory and Cognition, 1.","DOI":"10.3758\/BF03198087"},{"key":"6265_CR40","unstructured":"Rosch, E. (1978). Principles of categorization. in E., Rosch, & Lloyd, B. B. (eds.), Cognition and categorization Hillsdale."},{"key":"6265_CR41","doi-asserted-by":"crossref","unstructured":"Rosch, E. H., Mervis, C. B., Gray, W. D., Johnson, D. M., & Boyes-Braem, P. (1976). Basic ojects in natural categories. Cognitive Psychology, 8.","DOI":"10.1016\/0010-0285(76)90013-X"},{"key":"6265_CR42","unstructured":"Rosenblatt, F. (1962). Principles of neurodynamics. Spartan Books."},{"issue":"5","key":"6265_CR43","doi-asserted-by":"crossref","first-page":"1651","DOI":"10.1214\/aos\/1024691352","volume":"26","author":"R. E. Schapire","year":"1998","unstructured":"Schapire, R. E., Freund, Y., Bartlett, P. L., & Lee, W. S. (1998). Boosting the margin: A new explanation for the effectiveness of voting methods. Annals of Statistics, 26(5), 1651\u20131686.","journal-title":"Annals of Statistics"},{"issue":"11","key":"6265_CR44","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. G. Valiant","year":"1984","unstructured":"Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27(11), 1134\u20131142.","journal-title":"Communications of the ACM"},{"key":"6265_CR45","doi-asserted-by":"crossref","unstructured":"Valiant, L. G. (1998). A neuroidal architecture for cognitive computation. In Proc. of ICALP.","DOI":"10.1007\/BFb0055091"},{"key":"6265_CR46","doi-asserted-by":"crossref","unstructured":"Vapnik, V. N. (1995). The nature of statistical learning theory. Springer.","DOI":"10.1007\/978-1-4757-2440-0"},{"issue":"2","key":"6265_CR47","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"26","author":"V. N. Vapnik","year":"1971","unstructured":"Vapnik, V. N., & Chervonenkis, A. Ya., (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its applications, 26(2), 264\u2013280.","journal-title":"Theory of Probability and its applications"},{"key":"6265_CR48","doi-asserted-by":"crossref","unstructured":"Vempala, S. (1997). A random sampling based algorithm for learning the Intersection of Half-spaces. In Proc. of the 38th IEEE Foundations of Computer Science.","DOI":"10.1109\/SFCS.1997.646139"},{"key":"6265_CR49","unstructured":"Vempala, S. (2004). The random projection method. 65. DIMACS series, AMS."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-006-6265-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10994-006-6265-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-006-6265-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,6]],"date-time":"2023-05-06T21:50:22Z","timestamp":1683409822000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10994-006-6265-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3,28]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,5]]}},"alternative-id":["6265"],"URL":"https:\/\/doi.org\/10.1007\/s10994-006-6265-7","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3,28]]}}}