Back to Search
Start Over
Learning attribute-efficiently with corrupt oracles
- Source :
- ALT
- Publication Year :
- 2007
- Publisher :
- Elsevier BV, 2007.
-
Abstract
- We study learning in a modified EXACT model, where the oracles are corrupt and only few of the presented attributes are relevant. Both modifications were already studied in the literature [Dana Angluin, Mārtiņš Krikis, Learning with malicious membership queries and exceptions (extended abstract), in: COLT ’94: Proceedings of the Seventh Annual Conference on Computational Learning Theory, ACM Press, 1994, pp. 56–57 [3]; Dana Angluin, Mārtiņš Krikis, Robert H. Sloan, György Turán, Malicious omissions and errors in answers to membership queries, Machine Learning 28 (1997) 211–255; Laurence Bisht, Nader H. Bshouty, Lawrance Khoury, Learning with errors in answers to membership queries (extracted abstract), in: FOCS ’04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS’04, IEEE Computer Society, 2004, pp. 611–620; Nader H. Bshouty, Lisa Hellerstein, Attribute-efficient learning in query and mistake-bound models, J. Comput. System Sci. 56 (3) (1998) 310–319 [12]; Nick Littlestone, Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm, Machine Learning 2 (4) (1988) 285–318; Robert H. Sloan, Gyorgy Turan, Learning with queries but incomplete information (extended abstract), in: COLT ’94: Proceedings of the Seventh Annual Conference on Computational Learning Theory, ACM Press, 1994, pp. 237–245 [5]], and efficient solutions were found to most of their variants. Nonetheless, their reasonable combination is yet to be studied, and integrating the existing solutions either fails or works with a complexity that can be significantly improved. In this paper we prove the equivalence of EXACT learning attribute-efficiently with and without corrupt oracles. For each of the possible scenarios we describe a generic scheme that enables learning in these cases using modifications of the standard learning algorithms. We also generalize and improve previous non-attribute-efficient algorithms for learning with corrupt oracles.
- Subjects :
- Oracles
Monotone theory
Scheme (programming language)
General Computer Science
business.industry
Computer science
Attribute efficient
Queries
Theoretical Computer Science
Computational learning theory
Complete information
EXACT
Learning
Artificial intelligence
business
Corrupt
computer
Equivalence (measure theory)
Learning with errors
Computer Science(all)
computer.programming_language
Subjects
Details
- ISSN :
- 03043975
- Volume :
- 387
- Database :
- OpenAIRE
- Journal :
- Theoretical Computer Science
- Accession number :
- edsair.doi.dedup.....7f653e6d61c8a3bbec213d0dd9cf10b7