type
status
date
slug
summary
tags
category
icon
password
本笔记是learning theory教材 ”Understanding Machine Learning: From Theory to Algorithms” 第二章的读书笔记
📝 The Statistical Learning Framework
- Empirical Risk Minimization (ERM) learner
Formally, the learner should choose in advance (before seeing the data) a set of predictors. This set is called a hypothesis class and is denoted by H. Each h ∈ H is a function mapping from X to Y. For a given class H, and a training sample, S, the ERMH learner uses the ERM rule to choose a predictor h ∈ H, with the lowest possible error over S
Learner choose an from according to Learning rule (ERM) in the training set (sampled i.i.d. from distribution ).
🤗 Finite hypothesis class PAC learnability
- Realizability assumption
证明思路:
Goal: 找到一个足够大的m使得，在全域上的error L 小于 的同时，在训练集 S 上的 error 为0，发生这样的事件的概率小于
即要证明:
- 设置L
- realizability assumption
- S 全部分类正确
- union bound
- 反代算出m的下界
结论: 所有在有限假设空间中的算法模型，满足 S 的 size m大于一定的值，通过ERM学到的h是满足PAC条件的，也就是所有的有限假设空间都是PAC可学的(在本书中PAC learnable是默认满足realizability assumption的，否则就是agnostic PAC)
📎 参考文章
- 西瓜书 12.3.1
- Author:FlowerMouse
- URL:https://tangly1024.com/article/uml-chap2
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
