type
status
date
slug
summary
tags
category
icon
password
本博客是知名 Learning Theory 教材 ”Understanding Machine Learning: From Theory to Algorithms” 第五章的读书笔记
📝 The Bias-Complexity Tradeoff
🗺️ Big Picture
本章主要探讨 Prior Knowledge 在学习算法中的体现形式。
No-Free-Lunch theorem 表明如果没有任何先验知识，任何学习算法都会失败。
因此，可以通过两种途径来利用先验知识：
- 对于分布 来说，可以知道哪些分布的相关性质
- 对于假设类 通过预定义一个确定的类来进行约束
而对于第二点，有两个指标来度量选择的假设类 :
- approximating error:
- estimation error:
the error due to overfitting, which depends on the size or the complexity of the class
No-Free-Lunch Theorem
证明思路为取一个大小为2m的subset，然后取一个大小为m的sample S作为训练集，运行算法A，证明在分布D上的L的期望是大于1/4的。
这一步需要先证明对于一个不在S中的 来说，对于所有T种sample的选择，预测错误的平均值等于 1/2.
然后通过书中的转换即可得到1/4的结论
至此之后，再通过Markov不等式的推论（在appendix B.1中）可以得到
推论
Let X be an infinite domain set and let H be the set of all functions from X to {0, 1}. Then, H is not PAC learnable.
如果对假设类H不加限制，那么一定不是PAC可学的。
因此解决方法为 约束假设类
Error Decomposition
realizability assumption表述的就是
因此，在减小total Loss的时候面临一个tradeoff，如果H过于复杂，estimation error会增加，容易造成overfitting；而如果H过于简单，approximation error会增加，造成underfitting.
Learning theory studies how rich we can make H while still maintaining reasonable estimation error.
🤗 Summary
The No-Free-Lunch theorem states that there is no universal learner. Every learner has to be specified to some task, and use some prior knowledge about that task, in order to succeed.
📎 参考文章
- Understanding Machine Learning: From Theory to Algorithms
- Author:FlowerMouse
- URL:https://tangly1024.com/article/uml-chap5
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
