Effective Concept Classes of PAC and PACi Incomparable Degrees, Joins and Embedding of Degrees

Abstract

The Probably Approximately Correct (PAC) learning is a machine learning model introduced by Leslie Valiant in 1984. The PACi reducibility refers to the PAC reducibility independent of size and computation time. This reducibility in PAC learning resembles the reducibility in Turing computability. The ordering of concept classes under PAC reducibility is nonlinear, even when restricted to particular concrete examples.

Due to the resemblance to Turing Reducibility, we suspected that there could be incomparable PACi and PAC degrees for the PACi and PAC reducibilities as in Turing incomparable degrees. In 1957 Friedberg and in 1956 Muchnik independently solved the Post problem by constructing computably enumerable sets A and B of incomparable degrees using the priority construction method. We adapt this idea to PACi and PAC reducibilities and construct two effective concept classes C and D such that C is not reducible to D and vice versa. When considering PAC reducibility it was necessary to work on the size of an effective concept class, thus we use Kolmogorov complexity to obtain the size. The non-learnability of concept classes in the PAC learning model is explained by the existence of PAC incomparable degrees.

Analogous to the Turing jump, we give a jump operation on effective concept classes for the zero jump. To define the zero jump operator for PACi degrees the join of all the effective concept classes is constructed and proved that it is a greatest element. There are many properties proven for existing degrees. Thus we can explore proving those properties to PACi and PAC degrees. But if we prove an embedding from those degrees to PACi and PAC degrees then those properties will be true for PACi and PAC degrees without explicitly proving them.

Abstract prepared by Dodamgodage Gihnee M. Senadheera and taken directly from the thesis

E-mail: [email protected]

URL: https://www.proquest.com/docview/2717762461/abstract/ACD19F29A8774AF6PQ/1?accountid=13864

The Association for Symbolic Logic publishes abstracts of recent PhD theses in logic. The aim of this activity is to publish abstracts for the majority of recent PhD theses in logic world wide and submitted abstracts will therefore only be edited to ensure that they fall within the general area of logic and are appropriate in terms of length and content. This section willprovide a permanent publicly accessible overview of theses in logic and thus make up for the lack of central repository for the theses themselves. The Thesis Abstracts Section is edited by Sandra Müller. Any abstract should formally be submitted by the thesis advisor though it is expected to usually be prepared by the candidate. For detailed instructions for preparation and submission, including the required TeX template, please consult the link below. https://aslonline.org/journals/the-bulletin-of-symbolic-logic/logic-thesis-abstracts-in-the-bulletin-of-symbolic-logic/.