On the equivalence of Occam algorithms
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916950206054400 |
|---|---|
| author | Keinath-Esmail, Zaman |
| author_facet | Keinath-Esmail, Zaman |
| contents | 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 $δ$-dependent, which is an important limitation. In this paper, we show that their partial converse applies to Occam algorithms with $δ$-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_05906 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the equivalence of Occam algorithms Keinath-Esmail, Zaman Machine Learning Data Structures and Algorithms 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 $δ$-dependent, which is an important limitation. In this paper, we show that their partial converse applies to Occam algorithms with $δ$-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. |
| title | On the equivalence of Occam algorithms |
| topic | Machine Learning Data Structures and Algorithms Information Theory F.1.1; F.4.1 |
| url | https://arxiv.org/abs/2308.05906 |