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:
- developing computational models of learning.
- 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