Sample Complexity.md

有多少训练样例可以足够用于学习目标概念?

Version Space

![[Pasted image 20240601165833.png]]

样本复杂度

![[Pasted image 20240601174730.png]]

样例产生方式1

![[Pasted image 20240601174811.png]]

样例产生方式2

![[Pasted image 20240601175529.png]]

样例产生方式3

![[Pasted image 20240601175735.png]]

学习问题的样本复杂度

![[Pasted image 20240601180102.png]]

Version Space的 $\varepsilon$ 详尽化

![[Pasted image 20240601180141.png]]

需要多少训练样例可使得 $VS_{H,D}$ 是 $\varepsilon$-详尽的?

![[Pasted image 20240601180809.png]]

有限假设空间的样本复杂度: 一致学习器

![[Pasted image 20240601181041.png]]![[Pasted image 20240601182245.png]]

有限假设空间的样本复杂度: 不可知学习和不一致假设

![[Pasted image 20240601182524.png]] ![[Pasted image 20240601182605.png]]

无限假设空间

![[Pasted image 20240601183032.png]]

无限假设空间的样本复杂度: 实例集合的打散

![[Pasted image 20240601183101.png]]

Vapnik-Chervonenkis Dimension

![[Pasted image 20240601191323.png]]![[Pasted image 20240601191524.png]]![[Pasted image 20240601191844.png]]![[Pasted image 20240601192047.png]] ![[Pasted image 20240601192117.png]]

无限假设空间的样本复杂度

![[Pasted image 20240601192148.png]] ![[Pasted image 20240601192157.png]]

总结

![[Pasted image 20240601192211.png]]