The ordering of concept classes under PAC reducibility is nonlinear, even when restricted to particular concrete examples. We construct two effective concept classes of incomparable PAC degrees to show that there exist incomparable PAC degrees, analogous to incomparable Turing degrees. The non-learnability of concept classes in the PAC learning model is explained by the existence of PAC incomparable degrees. It was necessary to deal with the size of an effective concept class thus we propose a method to compute the size of the effective concept class using Kolmogorov complexity. To define the jump operator for PACi degrees the join of effective concept classes is constructed and explores the possibility of embedding known degrees to PACi or PAC degrees. If an embedding exists it will enable proving properties of known degrees for PACi and PAC degrees without explicitly proving them.
| Identifer | oai:union.ndltd.org:siu.edu/oai:opensiuc.lib.siu.edu:dissertations-3061 |
| Date | 01 August 2022 |
| Creators | Senadheera, Dodamgodage Gihanee Madumalika |
| Publisher | OpenSIUC |
| Source Sets | Southern Illinois University Carbondale |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Dissertations |
Page generated in 0.0019 seconds