Return to search

EFFECTIVE CONCEPT CLASSES OF PAC AND PACi INCOMPARABLE DEGREES, JOINS AND EMBEDDING OF DEGREES

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.

Identiferoai:union.ndltd.org:siu.edu/oai:opensiuc.lib.siu.edu:dissertations-3061
Date01 August 2022
CreatorsSenadheera, Dodamgodage Gihanee Madumalika
PublisherOpenSIUC
Source SetsSouthern Illinois University Carbondale
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceDissertations

Page generated in 0.0015 seconds