# Computational Learning Theory

Last Updated: 2021-11-19

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

ML:

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

Application:

• 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"

specifies:

• 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}
2^2