用matlab二分法代码Sauer-Lemma验证
验证凸假设集的Sauer引理
凸集
这里考虑的假设集是凸集。
该集合包含2D空间h：R
^
2->
{-1，+1}中的所有假设，这些假设在某个凸集内为正，而在其他凸集内为负。
为了创建凸集，沿着随机圆的圆周随机选择N个点。
我们考虑这些点的任何二分法，分配+/-
1的任意模式。
理论
对于凸集，其增长函数为m（N）=
2
^
N。
增长函数只与假设集的m（N）的上限有关，对于凸集，我们可以通过沿圆的周长取N个点来轻松地创建该上限。
由于m（N）=
2
^
N，这意味着我们的假设集H（凸集）可以破坏任何N个点集。
这意味着断点=
k
=无穷大，而VC尺寸=
d
=无穷大。
如果B（N，k）是N个点上的最大二分法数，因此N个点的大小k的子集不能被这些二分法粉碎，则，
现在，根据绍尔的引理，
因此，
对于凸集的情况，由于k->无穷大，我们可以将求和的上限设为N而不是k-1
运行代码
在MATLAB命令终端中输入以下命令sauermain.m
输入N的值（要获取的点数）
观察
如果我们将+1点与一个多边形相连，则由多边形的封闭内部（将始终是凸
评论0