تقرير
On the equivalence of Occam algorithms
| العنوان: | On the equivalence of Occam algorithms |
|---|---|
| المؤلفون: | Keinath-Esmail, Zaman |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Machine Learning, Computer Science - Data Structures and Algorithms, Computer Science - Information Theory, F.1.1, F.4.1 |
| الوصف: | Blumer et al. (1987, 1989) showed that any concept class that is learnable by Occam algorithms is PAC learnable. Board and Pitt (1990) showed a partial converse of this theorem: for concept classes that are closed under exception lists, any class that is PAC learnable is learnable by an Occam algorithm. However, their Occam algorithm outputs a hypothesis whose complexity is $\delta$-dependent, which is an important limitation. In this paper, we show that their partial converse applies to Occam algorithms with $\delta$-independent complexities as well. Thus, we provide a posteriori justification of various theoretical results and algorithm design methods which use the partial converse as a basis for their work. Comment: 13 pages, submitted to Information and Computation |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2308.05906 |
| رقم الأكسشن: | edsarx.2308.05906 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |