Mathematical framework
The goal of PAC learning is to use few examples as possible, and as little computation as possible to pick a hypothesis concept which is a close approximation to the target concept.
Define a concept to be a boolean mapping . X is the input space. c(x)=1 indicates x is a positive example , i.e. the service provider can offer the ìcorrectî service for challenge x.
Now define the error between the target concept c and the hypothesis h as .