Computational Learning Theory

Last Updated: 2021-11-19

CLT: "machine learning from Theoretical Computer Science P.O.V."


  • programs that automatically self-improve
  • extracting useful knowledge/info from raw data


  • auto classification clustering of text, objects, etc
  • prediction weather, finance, etc
  • developing complicated software. play chess, drive car

CLT's 2 parts:

  1. developing computational models of learning.
  2. proving things about the model.

model= "rules of the game"


  • what is being learned? - skill: ride a bike - subject: CLT - environment: NYC - language - This course: learning (boolean) classification rules i.e. Boolean functions f:X->{0,1}
  • How is information obtained? Many possibility, learners access to info. - random examples(passive) - asking questions(active); (different types of) queries; - experiments, exploring
  • What type of data is available? - incomplete - noisy
  • What prior info/assumptions can learner make? - usually assume the Bool func being learned has some structure
  • Constraints on learner. - Our learners, efficient algorithm: programs that run in "small" tim/space/data examples
  • Success criterion: what should algorithm successfully do? - online vs offline - hypoth. representation f(fact): "target concept" | h: hypothesis for f - accuracy/error

Some learning models we'll discuss

  • Online mistake-bond model
  • Probably Approx. Correct model(KV)
  • Statistical Queries
  • Exact learning

Within these models, we'll:

  • Look at specific algorithms.
  • General techniques for designing learning algs
  • Sample complexity
  • Computational barriers to learning.
  • Learning from noisy data.
  • Boosting accuracy.
  • Compare different models

Basic Notions/Terminology

X=domain for function to be learned(input domain)

X={all cars} f:X->{0,1}