Skip to main content

Computational learning theory

We've run a learner

Mondrain Composition Colored Vornoi Diagram Nearest 1-NN

Learning theory​

  • Define learning problems
  • Showing specific algorithm work
  • show these problems are fundamentally hard.

Resources in machine learning​

Theory of computing analyzes how algorithms use resources: time, space.

What resources matter in computational learning theory?

Time, space, data/samples

Defining inductive learning​

  1. Probability of successful training
  2. Number of examples to train on
  3. Complexity of hypothesis class
  4. Accuracy to which target concept is approximated
  5. Manners in which training examples presented
  6. Manners in which training examples selected

Selecting training examples​

Learner / Teachers

  1. Learner asks questions of teacher C(X)?
  2. Teacher gives examples to help learner.
    1. Teacher chooses X, tells C(x)
  3. Fixed distribution
    1. x chosen from D by nature
  4. Evil worst distribution.

Teaching via 20 questions​

Reconstructing hypothesis​

  • Show what's irrelevant
  • Show what's relevant