Simple Definition

A learning algorithm is defined like this:

• Input: Labeled data
• Output: Classifier
  • A classifier is a function that given:
    • Input: Unlabeled data point
    • Outputs: Label (class) of the data point
    • Predicts the class for the data point with error $ϵ$

Because many of learning algorithms are probabilistic (and the labeled data distribution is mostly probabilistic), the learning algorithm does not always output a good classifier. So we also consider the chance of getting a good enough classifier from it: $\delta$

General Definition

Inputs

• $EX(c,D)$: Oracle
  • This can be seen as the labeled-data generator. A function that you can call as many times as you want to give you one labeled datapoint from distribution D.
• $\delta$: Confidence parameter
  • The chance of getting a good enough classifier.
• $ϵ$: Error parameter
  • The error of the classifier
  • The definition of good enough

Output

• With $\delta$ probability: A classifier for c that classifies data points from distribution D with $ϵ$ error or less
  • Creates a good enough classifier
• With $1-\delta$ probability: A classifier for c that classifies data points from distribution D with more than $ϵ$ error
  • Fails to create a good enough classifier