{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:35:24Z","timestamp":1725471324053},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540352945"},{"type":"electronic","value":"9783540352969"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11776420_17","type":"book-chapter","created":{"date-parts":[[2006,9,28]],"date-time":"2006-09-28T14:49:15Z","timestamp":1159454955000},"page":"199-213","source":"Crossref","is-referenced-by-count":0,"title":["Exact Learning Composed Classes with a Small Number of Mistakes"],"prefix":"10.1007","author":[{"given":"Nader H.","family":"Bshouty","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hanna","family":"Mazzawi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_CR1","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D.: Queries and Concept Learning. Machine Learning\u00a02, 319\u2013342 (1988)","journal-title":"Machine Learning"},{"key":"17_CR2","unstructured":"Auer, P., Kwek, S., Maass, W., Warmuth, M.K.: Learning of Depth Two Neural Networks with Constant Fan-in at the Hidden Nodes. Electronic Colloquium on Computational Complexity (ECCC)\u00a07(55) (2000)"},{"issue":"4","key":"17_CR3","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0020-0190(92)90237-P","volume":"42","author":"A. Blum","year":"1992","unstructured":"Blum, A.: Rank-r Decision Trees are a Subclass of r-Decision Lists. Inf. Process. Lett.\u00a042(4), 183\u2013185 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"17_CR4","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0020-0190(96)00077-4","volume":"59","author":"N.H. Bshouty","year":"1996","unstructured":"Bshouty, N.H.: A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries. Inf. Process. Lett.\u00a059(1), 37\u201339 (1996)","journal-title":"Inf. Process. Lett."},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Bshouty, N.H.: A new Composition Theorem for Learning Algorithms. In: Proceedings of the 30th annual ACM Symposium on Theory of Computing (STOC), pp. 583\u2013589 (1998)","DOI":"10.1145\/276698.276873"},{"issue":"3","key":"17_CR6","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0890-5401(89)90001-1","volume":"82","author":"A. Ehrenfeucht","year":"1989","unstructured":"Ehrenfeucht, A., Haussler, D.: Learning Decision Trees from Random Examples. Inf. Comput.\u00a082(3), 231\u2013246 (1989)","journal-title":"Inf. Comput."},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Kearns, M., Li, M., Pitt, L., Valiant, L.: On the learnability of boolean formulae. In: In Proceeding of the 19th ACM Symposium on the Theory of Computing, pp. 285\u2013294 (1987)","DOI":"10.1145\/28395.28426"},{"issue":"2","key":"17_CR8","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/j.jcss.2003.07.007","volume":"68","author":"A.R. Klivans","year":"2004","unstructured":"Klivans, A.R., Servedio, R.A.: Learning DNF in time \n                    \n                      \n                    \n                    $2^{\\tilde O( n^{1\/3})}$\n                  . J. Comput. Syst. Sci.\u00a068(2), 303\u2013318 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR9","first-page":"285","volume":"2","author":"N. Littlestone","year":"1988","unstructured":"Littlestone, N.: Learning when irrelevant attributes abound. A new linear-threshold algorithm. Machine Learning\u00a02, 285\u2013318 (1988)","journal-title":"Machine Learning"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/inco.1997.2686","volume":"141","author":"W. Maass","year":"1998","unstructured":"Maass, W., Warmuth, M.K.: Efficienct Learning with Virtual Threshold Gates. Information and Computation\u00a0141, 66\u201383 (1998)","journal-title":"Information and Computation"},{"issue":"3","key":"17_CR11","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/0022-0000(90)90028-J","volume":"41","author":"L. Pitt","year":"1990","unstructured":"Pitt, L., Warmuth, M.K.: Prediction-preserving reducibility. Journal of Computer and System Science\u00a041(3), 430\u2013467 (1990)","journal-title":"Journal of Computer and System Science"},{"key":"17_CR12","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N. Sauer","year":"1972","unstructured":"Sauer, N.: On the dencity of families of sets. J. Combinatorial Theory, Ser. A\u00a013, 145\u2013147 (1972)","journal-title":"J. Combinatorial Theory, Ser. A"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Tarui, J., Tsukiji, T.: Learning DNF by Approximating Inclusion-Exclusion Formulae. In: IEEE Conference on Computational Complexity, pp. 215\u2013220 (1999)","DOI":"10.1109\/CCC.1999.766279"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: A theory of the learnable. Communication of the ACM\u00a027(11) (1984)","DOI":"10.1145\/1968.1972"}],"container-title":["Lecture Notes in Computer Science","Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11776420_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:15:31Z","timestamp":1619507731000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11776420_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540352945","9783540352969"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11776420_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}