模式分类笔记 -- 统计学习（2）

任意一个拥有n个变量的boolean function可以被一个r（r<n）阶的PTG来实现。具体细节现在不看，不然又扯出来一大堆东西。PTG来解决问题看成是多个LTG的组合，只不过输入被扩展了。

在典型的boolean function的时候，当变量数又比较小，可以用K-map来进行简单有效的分析，挖出可行的LTG组合形式。

 

 

Function Counting Theorem：位于general position的m个点能被线性二分的情况的数目

我们以Points in General Position的概念出发，来对这个问题来进行说明。
在一个d维空间的m个点中，如果不存在d+1个点同处在d-1维的超平面 上，那么我们认为这m个点处在General Position上，此时m>d。例如三点不共线。
如果m<d, 那么就变成没有m-2维的超平面包含这m个点，意义不大，且又没法感受，因为超过了三维空间就没法用立体图形表示了。说到底，回到线性代数的表示方式:也就是（m>n时）。


general position在定理证明里是充要条件，当然它也有表述问题时其优秀的特性，例如m个随机点位于Gerneral position的概率是接近1的：）

现在我们来证明一下这个定理：
设m点集X={x1, x2, ..xm}实数域d维空间，记C(m, d)为完成{X+，X-}分离出来的线性二分的数目，X+表明在分隔超平面正侧。其实我们这里讨论的是没有标记过的点，就如非监督学习一样，只是考察能不能把它们分开，是能够完成可分的任务的所有可行情况的数目。

考虑一个新点，xm+1, 记x‘ = {x1, x2, ..xm,xm+1},这m+1个点同样要满足general position的条件，那么可以存在一些通过xm+1的超平面可以完成对X的划分，记这种划分的数目为D。对于D中的每一种情况，将会有两个新的划分出现，{X+, X- U {Xm+1}}和{X+ U {Xm+1}, X-}。
这是因为对于处于general position的情况下，D中的那个分隔超平面可以移动无限小的距离而不影响到分隔的结果{X+, X-}。因此对于D中每个旧的分隔情况，会增加出一个新的来 ：C(m+1, d)=C(m, d) - D + 2D = C(m, d) + D.

然而D=C(m, d-1),因为限制了超平面必须通过一点 ，其实就使得问题等价于d-1维度的问题 。C(m+1, d) = C(m, d) + C(m, d-1)。
这样的迭代关系 ，我们可以解得
C(1, n) = 2,因为一个点只可能有两种划分情况，既而更加简化，在m<d+1时，更加简单：

一个单独n-input LTG可以完成对处于general position上的m个点划分的概率是：

 

当n->无穷的时候，这个概率的极限是1，限制条件是m<2(n+1) 。LTG不能处理m>3(n+1)的问题，但有这问题的时候我们还可以提高维度。

General Position其实是这个问题的上界，因为在任意点集合，出现不同的线性二分的情况叫少了，数目少了，概率自然就降下来了。
对于属于布尔空间的m个点，能被一个r阶PTG进行二分的概率是多少呢
Function counting的数目上界是 。这里右边的是多项式的自由度，看到最上面写的那个定理么，funciton counting theorem里看得出方程也是随m递增的，2的n次方做为左边的极限带来的就是最大值。

再往下的就不说了。

其实写了这么多更多只是对于Cover theorem的一个佐证 ：The probability that classes are linearly separable increases when the features are nonlinearly mapped to a higher dimensional feature space.

低维空间不可分转换到高维空间有可能线性可分 。

评论

1 楼 doudoulong2002ok 2008-11-29  

有道理！加油！