To participate in this seminar, please register here: https://www.msri.org/seminars/25206

Abstract:

The Probably Approximately Correct (PAC) learning is a ma chine 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 learn ing 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 in comparable degrees using the priority construction method. We adapt this idea to PACi reducibility and construct two the ef fective concept class C0 and C1 such that C0 is not reducible to C1 and vice versa. In future, we could incorporate the size and time complexity to this reducibility and show that there exist PAC incomparable degrees.