{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:22:57Z","timestamp":1725664977531},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540626855"},{"type":"electronic","value":"9783540684312"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-62685-9_5","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:47:47Z","timestamp":1330296467000},"page":"38-50","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Learning from incomplete boundary queries using split graphs and hypergraphs"],"prefix":"10.1007","author":[{"given":"Robert H.","family":"Sloan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gy\u00f6rgy","family":"Tur\u00e1n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"issue":"4","key":"5_CR1","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"D. Angluin. Queries and concept learning. Machine Learning, 2(4):319\u2013342, Apr. 1988.","journal-title":"Machine Learning"},{"key":"5_CR2","first-page":"57","volume-title":"Learning with malicious membership queries and exceptions","author":"D. Angluin","year":"1994","unstructured":"D. Angluin and M. Kri\u0137is. Learning with malicious membership queries and exceptions. In Proc. 7th Annu. ACM Workshop on Comput. Learning Theory, pages 57\u201366. ACM Press, New York, NY, 1994."},{"key":"5_CR3","unstructured":"D. Angluin, M. Kri\u0137is, R. H. Sloan, and G. Tur\u00e1n. Malicious omissions and errors in answers to membership queries. Machine Learning. To appear."},{"issue":"4","key":"5_CR4","first-page":"343","volume":"2","author":"D. Angluin","year":"1988","unstructured":"D. Angluin and P. Laird. Learning from noisy examples. Machine Learning, 2(4):343\u2013370, 1988.","journal-title":"Machine Learning"},{"issue":"1","key":"5_CR5","first-page":"7","volume":"14","author":"D. Angluin","year":"1994","unstructured":"D. Angluin and D. K. Slonim. Randomly fallible teachers: learning monotone DNF with an incomplete membership oracle. Machine Learning, 14(1):7\u201326, 1994.","journal-title":"Machine Learning"},{"key":"5_CR6","first-page":"311","volume-title":"On exact specification by examples","author":"M. Anthony","year":"1992","unstructured":"M. Anthony, G. Brightwell, D. Cohen, and J. Shawe-Taylor. On exact specification by examples. In Proc. 5th Annu. Workshop on Comput. Learning Theory, pages 311\u2013318. ACM Press, New York, NY, 1992."},{"key":"5_CR7","first-page":"98","volume-title":"Learning with unreliable boundary queries","author":"A. Blum","year":"1995","unstructured":"A. Blum, P. Chalasani, S. A. Goldman, and D. K. Slonim. Learning with unreliable boundary queries. In Proc. 8th Annu. Conf. on Comput. Learning Theory, pages 98\u2013107. ACM Press, New York, NY, 1995."},{"key":"5_CR8","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/BF01205054","volume":"4","author":"N. Bshouty","year":"1994","unstructured":"N. Bshouty, T. Hancock, L. Hellerstein, and M. Karpinski. An algorithm to learn read-once threshold formulas, and transformations between learning models. Computational Complexity, 4:37\u201361, 1994.","journal-title":"Computational Complexity"},{"key":"5_CR9","first-page":"311","volume":"19","author":"S. F\u00f6ldes","year":"1977","unstructured":"S. F\u00f6ldes and P. L. Hammer. Split graphs. Congressus Numerantium, 19:311\u2013315, 1977.","journal-title":"Congressus Numerantium"},{"key":"5_CR10","first-page":"77","volume-title":"Learning k-term DNF formulas with an incomplete membership oracle","author":"S. A. Goldman","year":"1992","unstructured":"S. A. Goldman and H. D. Mathias. Learning k-term DNF formulas with an incomplete membership oracle. In Proc. 5th Annu. Workshop on Comput. Learning Theory, pages 77\u201384. ACM Press, New York, NY, 1992."},{"key":"5_CR11","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1007\/BF01300374","volume":"14","author":"S. A. Goldman","year":"1995","unstructured":"S. A. Goldman and R. H. Sloan. Can PAC learning algorithms tolerate random attribute noise? Algorithmica, 14:70\u201384, 1995.","journal-title":"Algorithmica"},{"key":"5_CR12","volume-title":"Computer Science and Applied Mathematics","author":"M. C. Golumbic","year":"1980","unstructured":"M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Computer Science and Applied Mathematics. Academic Press, New York, 1980."},{"key":"5_CR13","first-page":"587","volume":"21","author":"Q. P. Gu","year":"1992","unstructured":"Q. P. Gu and A. Maruoka. Learning monotone boolean functions by uniformly distributed examples. SIAM J. Comput., 21:587\u2013599, 1992.","journal-title":"SIAM J. Comput."},{"key":"5_CR14","first-page":"69","volume-title":"Computational Learning Theory: Eurocolt '93, volume New Series Number 53 of The Institute of Mathematics and its Applications Conference Series","author":"T. Heged\u00fcs","year":"1994","unstructured":"T. Heged\u00fcs. On training simple neural networks and small-weight neurons. In Computational Learning Theory: Eurocolt '93, volume New Series Number 53 of The Institute of Mathematics and its Applications Conference Series, pages 69\u201382, Oxford, 1994. Oxford University Press."},{"key":"5_CR15","unstructured":"K. J. Lang and E. B. Baum. Query learning can work poorly when a human oracle is used. In International Joint Conference on Neural Networks, Beijing, 1992."},{"key":"5_CR16","first-page":"285","volume":"2","author":"N. Littlestone","year":"1988","unstructured":"N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285\u2013318, 1988.","journal-title":"Machine Learning"},{"key":"5_CR17","volume-title":"Annals of Discrete Mathematics","author":"N. V. R. Mahadev","year":"1995","unstructured":"N. V. R. Mahadev and U. N. Peled. Threshold Graphs and Related Topics, volume 56 of Annals of Discrete Mathematics. Elsevier Science B.V., Amsterdam, The Netherlands, 1995."},{"key":"5_CR18","unstructured":"U. Peled. Personal Communication."},{"key":"5_CR19","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"L. Pitt and L. Valiant. Computational limitations on learning from examples. J. ACM, 35:965\u2013984, 1988.","journal-title":"J. ACM"},{"key":"5_CR20","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0020-0190(91)90220-C","volume":"37","author":"Y. Sakakibara","year":"1991","unstructured":"Y. Sakakibara. On learning from queries and counterexamples in the presence of noise. Inform. Proc. Lett., 37:279\u2013284, 1991.","journal-title":"Inform. Proc. Lett."},{"key":"5_CR21","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0020-0190(95)00016-6","volume":"54","author":"R. H. Sloan","year":"1995","unstructured":"R. H. Sloan. Four types of noise in data for PAC learning. Inform. Proc. Lett., 54:157\u2013162, 1995.","journal-title":"Inform. Proc. Lett."},{"key":"5_CR22","first-page":"237","volume-title":"Learning with queries but incomplete information","author":"R. H. Sloan","year":"1994","unstructured":"R. H. Sloan and G. Tur\u00e1n. Learning with queries but incomplete information. In Proc. 7th Annu. ACM Workshop on Comput. Learning Theory, pages 237\u2013245. ACM Press, New York, NY, 1994."},{"key":"5_CR23","first-page":"560","volume-title":"Learning disjunctions of conjunctions","author":"L. G. Valiant","year":"1985","unstructured":"L. G. Valiant. Learning disjunctions of conjunctions. In Proceedings of the 9th International Joint Conference on Artificial Intelligence, vol. 1, pages 560\u2013566, Los Angeles, California, 1985. International Joint Committee for Artificial Intelligence."}],"container-title":["Lecture Notes in Computer Science","Computational Learning Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-62685-9_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T00:13:45Z","timestamp":1578528825000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-62685-9_5"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540626855","9783540684312"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-62685-9_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"3 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}