单个H扩展到多个H时,机器学习的保证

1.差的数据集的概念BAD D

单个H,在抽出的样本(数据集上),满足

$P(|E_{in}-E_{out}|>epsilon)leq 2e^{-2epsilon^2N}$

考虑以下情况,如果抽出的都是绿球(数据集D),此时$E_{in} =0 $,而实际上和$E_{out}$差别很大,
此时称此数据集为差的数据集
单个H碰到差的数据集时,$|E_{in}-E_{out}|>epsilon$
碰到差的数据集的概率为
$P(BAD~D~for~H) leq 2e^{-2epsilon^2N}$

 
2.面临hypothesis set(有M个H)

此时如果有一个H的碰到BAD D,则学习会不靠谱
$P(BAD~D~for~H_1~OR~BAD~D~for~H_2~OR~...BAD~D~for~H_M)\ leq P(BAD~D~for~H_1)+P(BAD~D~for~H_2)...+P(BAD~D~for~H_M) \ leq 2Me^{-2epsilon^2N}$

如果M有限,N足够大,可以保证learning可行



原文地址:https://www.cnblogs.com/porco/p/4605621.html