Logic Seminar April 10

Speaker: Wesley Calvert, Southern Illinois University

http://lagrange.math.siu.edu/Calvert/

Abstract: In the Probably Approximately Correct (PAC) notion of machine learning, a computer has the task of finding some concept which, with high probability, will be very close to a pre-specified target. We would like to characterize when this is possible, and to do so in an optimal way. In the present talk, we compute exactly the degree of unsolvability of the problem of determining whether a concept class is PAC learnable. The model of concept class used, a uniform set of Pi-0-1 classes, is a natural one, frequently used in computability, and is rich enough to include most natural examples.