Paper Info
Title
Complexity of Teaching by a Restricted Number of Examples
Abstract
Teaching is inextricably linked to learning, and there are many studies on the complexity of teaching as well as learning in computational learning theory. In this paper, we study the complexity of teach- ing in the situation that the number of examples is restricted, especially less than its teaching dimen- sion. We formulate a model of teaching by a re- stricted number of examples, where the complex- ity is measured by the maximum error to a target concept. We call a concept class is optimally in- crementally teachableif the teacher can optimally teach it to the learner whenever teaching is termi- nated. We study the complexity of the three concept classes of monotone monomials, monomials without the empty concept, and monomials in our model. We show that the boundary of optimally incremental teachability is different from that of polynomial teachability in the classical model. We also show that inconsistent examples help to reduce the max- imum error in our model.
Year
Venue
Keywords
2009
COLT
computational learning theory
Field
DocType
Citations 
Quantum complexity theory,Asymptotic computational complexity,Teaching dimension,Stability (learning theory),Concept class,Computer science,Descriptive complexity theory,Artificial intelligence,Computational learning theory,Machine learning,Sample exclusion dimension
Conference
10
PageRank 
References 
Authors
0.87
12
2
Name
Order
Citations
PageRank
Hayato Kobayashi1214.69
Ayumi Shinohara293688.28