التفاصيل البيبلوغرافية
| العنوان: |
The teaching size: computable teachers and learners for universal languages. |
| المؤلفون: |
Telle, Jan Arne, Hernández-Orallo, José, Ferri, Cèsar |
| المصدر: |
Machine Learning; Sep2019, Vol. 108 Issue 8/9, p1653-1675, 23p |
| مصطلحات موضوعية: |
UNIVERSAL language, CONCEPT learning, TEACHERS, MOBILE learning, PROGRAMMING languages, NEUROLINGUISTICS |
| مستخلص: |
The theoretical hardness of machine teaching has usually been analyzed for a range of concept languages under several variants of the teaching dimension: the minimum number of examples that a teacher needs to figure out so that the learner identifies the concept. However, for languages where concepts have structure (and hence size), such as Turing-complete languages, a low teaching dimension can be achieved at the cost of using very large examples, which are hard to process by the learner. In this paper we introduce the teaching size, a more intuitive way of assessing the theoretical feasibility of teaching concepts for structured languages. In the most general case of universal languages, we show that focusing on the total size of a witness set rather than its cardinality, we can teach all total functions that are computable within some fixed time bound. We complement the theoretical results with a range of experimental results on a simple Turing-complete language, showing how teaching dimension and teaching size differ in practice. Quite remarkably, we found that witness sets are usually smaller than the programs they identify, which is an illuminating justification of why machine teaching from examples makes sense at all. [ABSTRACT FROM AUTHOR] |
|
Copyright of Machine Learning is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
Find this article in full text from Springer Verlag. 
Full Text Finder