Skip to main content

Computational Learning Theory

  • Defining learning problem
  • Show specific algorithms work
  • show these problems are fundamentally hard

Inductive Learning​

  • Probability of successful training
  • Number of samples to learn
  • Complexity of hypothesis class
  • Accuracy to which target concept is approximated
  • Manner in which training examples presented - Batch/online
  • Manner in which training examples selected

Selecting training examples​

Teacher can ask 1 question to get the answer.

Learners need to eliminate as many as I can as a learner

Steps​

  1. Show what's irrelavant.
  2. Show what's relevant.

Learn with Constrained Queries​

Learn with mistake bounds​