发帖
雷达卡
《机器学习导论》2nd Edition ---（土耳其）Ethem Alpaydin 著 范明 昝（zan）红英 牛常勇译 ----机械Press-2014.3
2.3 概率逼近正确学习（Probably Approximately Correct，PAC）
使用最紧凑的矩形S作为假设，希望找出我们需要多少实例。
（希望我们的假设是近似正确的，即误差概率不超过某个值）
在概率逼近正确（Praobably Approximately Correct, PAC）学习中，给定类C和从未知但具有确定概率分布P（x）中抽取样本，我们希望找出样本数N，使得对于任意的δ<=1/2 和 ε>0，假设h的误差至多为ε的概率至少为1-δ
P{C△h ≤ ε} ≥ 1-δ
其中，C△h是C与h不同的区域。
在这种情况下，因为S是最紧凑的可能的矩形，C与h=S之间的误差区域是四个矩形条带之和。
我们希望确保正例落在该区域（导致错误）的概率最多为ε
对于任何这样的条带，如果我们能够确保其概率上届为ε/4，则误差最多为4（ε/4）=ε
注意，我们将矩形角部的重叠部分计算了两次，并且这种情况下总的实际误差小于4（ε/4）。随机抽取的样本不在此条带中的概率是1-ε/4。
所有N个独立抽取的样本不在此条带中的概率为（1- ε/4）ⁿ，我们希望其最大值为δ。有不等式
（ 1 - x ） ≤ exp[ - x ]
如果选定 N 和 δ 满足 4 exp [ - εN/4] ≤ δ
则我们有 4（1 - ε/4 ）ⁿ ≤ δ ，不等式两边同时除以4，再取自然对数，并重新排列各项，可以得到：
N ≥ （4/ε）log（4/δ） （式2-7）
因此，只要我们至少从C中取（4/ε）log（4/δ）个独立样本，并使用紧凑矩形作为我们的假设h，则在置信概率（confidence probability）至少为 1-δ的情况下，一个给定点被误分类的错误概率最多为 ε 。
减少δ我们可以有任意大的置信度，而减少ε我们可以有任意小的误差，且我们在不等式（2-7）中看到，样本的数量是分别随1/ε和1/δ呈线性和对数缓慢增长的函数。
京公网安备 11010802022788号
