Effective Concept Classes of PACi/PAC Incomparable Degrees and Jump Structure

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. In 1957 Friedberg and 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/PAC reducibilities and construct two the effective concept classes $C_0$ and $C_1$ such that $C_0$ is not reducible to $C_1$ 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. Analogous to Turing jump, we give a jump structure on effective concept classes. As the future work, we begin to explore an embedding of structures from PAC degrees to 1-1 degrees or Turing degrees.

machine learningcomputer science theorylogic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic