Estimating Hypothesis Accuracy

• Estimating the accuracy with which it will classify future instances - also probable error of this accuracy estimate
• A space of possible instances . Different instances in may be encountered with different frequencies which is modeled by some unknown probability distribution . Notice says nothing about whether is a positive or negative example. The learning task is to learn the target concept, , by considering a space of possible hypothesis. Training examples of the target function are provided to the learner by a trainer who draws each instance independently, according to the distribution and who then forwards the instance along with the correct target value to the learner.
• Are instances ever really drawn independently?
• Sample error - the fraction of instances in some sample that it misclassifies - , where is the number of samples in , and is 1 if , and 0 otherwise
• True error - probability it will misclassify a single randomly drawn instance from the distribution - , where denotes that the probability is taken over the instance distribution .
• Really want but can only get
• How good an estimate of is provided by ?