Seminar
| Parent Program: | |
|---|---|
| Location: | SLMath: Online/Virtual |
To participate in this seminar, please register here: https://www.msri.org/seminars/25206
The seminar will feature research talks by the six postdoctoral scholars appointed to the Fall 2020 DDC program, along with talks by students and other pre-tenure researchers associated with this program. Since seminar attendees will have disparate backgrounds, we plan that these talks will not be too advanced, nor will they assume substantial background knowledge. Our postdocs include number theorists, model theorists, and computable structure theorists, and talks can be expected to span all of these areas.
Two Effective Concept Classes Of PACi Incomparable Degrees
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.
 |
Slides
|
Two Effective Concept Classes Of PACi Incomparable Degrees
| H.264 Video | 25156_28654_8597_Two_Effective_Concept_Classes_of_PACi_Incomparable_Degrees.mp4 |