机器学习基石---Why Can Machines Learn(Part3)

knitr::opts_chunk$set(echo = TRUE)

1 前文回顾

M M 的数值对learning的影响。并且得出如果MM有限，learning可能是可行的，因为此时满足Ein≈Eout E i n ≈ E o u t 。接着试图用成长函数mH(N) m H ( N ) (即dichotomy的个数)去替代M M ，至于替代的合理性，存疑(因为同样dichotomy的不同hypothesis不一定完全重叠)，Part4会有说明。然后提出break point概念，猜测2D perceptrons的成长函数mH(n)mH(n)是多项式O(N4−1) O ( N 4 − 1 ) 。本文主要内容就是探讨这一猜测的正确性。

2 Restriction of Break Point

H

H 的成长函数很容易找到，例如Part2中的Positive Rays、Positive Intervals等。有些则很难，如2D perceptrons。此时我们不考虑具体的HH，只考虑能生成的dichotomy。比如，对于2D perceptrons，如果三点共线，且呈o、x、o o 、 x 、 o ，则不认为这是一个dichotomy。而如果我们不考虑2D perceptrons这一限制，那么认为这是一种dichotomy。这样的话，如果知道break point时，我们可以H H 作用于DD

时，最多最多能产生多少dichotomy吗？相当于我们在寻找mH(N)

m H ( N ) 的一个上界。

举例说明，假设不知道某个H

H 的成长函数mH(N)mH(N)，但是知道最小的break point k=2 k = 2 ，那么H H 作用与N=3N=3时，最多最多产生多少种dichotomy？

成长函数为4，最多有4种dichotomy。N=4 N = 4 时，最多有5种hypothesis。用R写了个函数，放在最后。有兴趣可以瞅瞅~这时，我们发现当N>k N > k 时，break point k k 限制了mH(N)mH(N)的大小，即成长函数与N N 和breakpointbreakpoint有关。如果给定N N ，kk，mH(N) m H ( N ) 有上界，且上界不呈指数增长，最好是多项式，那么我们可以说learning是可行的。

2.1 Bounding Function

B(N,K) B ( N , K ) ，表示当break point 为k时，成长函数mH(N) m H ( N ) 的最大值。即mH(N) m H ( N ) 最多最多有多少种dichotomy。并且此时我们不考虑H H ，只关心成长函数的上界。那么从上一小节知道 B(3,2)=4B(3,2)=4

2.2 Part1 Of Bound Function

B(N,K) B ( N , K ) 函数的求解分成两部分。首先考虑下面情况: 1. 当k=1 k = 1 时，break point为1，说明任意一个点不可能出现两种类型，因此allB(N,1)=1 a l l B ( N , 1 ) = 1 。 2. 当N

那么剩下的空应该怎么填呢？

2.3 Part2 Of Bound Function

N>k N > k 时，B(N,k) B ( N , k ) 的情况较为复杂。推导过程先从B(4,3) B ( 4 , 3 ) 讲起，探索B(4,3) B ( 4 , 3 ) 能不能和前面这些已知的数据存在某种练习。 首先把B(4,3) B ( 4 , 3 ) 的所有情况写出来(Ps:我的程序也可以求)，共有11个dichotomy，记为all a l l 。如果增加再一个dichotomy，会出现三个点被shatter的情况。

对上图中11个dichotomy分组，分组依据为x1-x3是否是完全相同的。把相同标记为orange,不同的标记为purple。得到下图：

把11个dichotomy的x4去掉，orange部分去重得到4个不同dichotomy组合，命名为α α ，purple部分命名为β β 。那么B(4,3)=2α+β B ( 4 , 3 ) = 2 α + β 。 接着我们再关注α α 和β β 部分，因为他们是从all a l l 中取出来的，所以all a l l 满足的性质，α α 也满足。也就是说α α 和β β 这个整体中任意3个点不能够被shatter。那么α+β

另外，如果只看α α 这部分，由于break point是3，所以α α double之后，添加x4 x 4 时，仍满满足break point=3。那么如果α α 这部分存在两个点被shatter，这时double之后添加成对x4 x 4 一列，会出现3个点被shatter。显然不满足break point为3的前提。所以α α 中任意两点不能shatter，即α

-a.png)

综合以上两点：

B(4,3)=2α+βα+β≤B(3,3)α≤B(3,2)⇒B(4,3)≤B(3,3)+B(3,2) B ( 4 , 3 ) = 2 α + β α + β ≤ B ( 3 , 3 ) α ≤ B ( 3 , 2 ) ⇒ B ( 4 , 3 ) ≤ B ( 3 , 3 ) + B ( 3 , 2 )

根据公式，可以填满表格：

进一步推导出B(N,k) B ( N , k ) 满足下列不等式：

B(N,k)≤∑i=0k(Ni) B ( N , k ) ≤ ∑ i = 0 k ( N i )

下面用数学归纳法证明(摘自《learning from data》)：

1. k=1

k = 1 时， B(N,k)=1≤(1+N) B ( N , k ) = 1 ≤ ( 1 + N ) ，对所有的 N N 不等式成立。只需考虑k>1k>1的情形。 N=1 N = 1 时，不等式也成立。

2. 假设N≤No

N ≤ N o 时，对于所有 k k 不等式都成立。那么只需证明N=No+1N=No+1时，不等式也成立即可：

B(No+1,k)≤B(No,k)+B(No,k−1)≤∑i=0k−1(Noi)+∑i=0k−2(Noi)=(No0)+∑i=1k−1(Noi)+∑i=1k−1(Noi−1)=1+∑i=1k−1{(Noi)+(Noi−1)}=1+∑i=1k−1(No+1i)=∑i=0k−1(No+1i) B ( N o + 1 , k ) ≤ B ( N o , k ) + B ( N o , k − 1 ) ≤ ∑ i = 0 k − 1 ( N o i ) + ∑ i = 0 k − 2 ( N o i ) = ( N o 0 ) + ∑ i = 1 k − 1 ( N o i ) + ∑ i = 1 k − 1 ( N o i − 1 ) = 1 + ∑ i = 1 k − 1 { ( N o i ) + ( N o i − 1 ) } = 1 + ∑ i = 1 k − 1 ( N o + 1 i ) = ∑ i = 0 k − 1 ( N o + 1 i )

中间合并组合项和公式是用组合数公式的递推公式:

(Nm)=(N−1m)+(N−1m−1) ( N m ) = ( N − 1 m ) + ( N − 1 m − 1 )

此时不等式成立，至于归纳法，就学过一个变量的证明，凑活看吧。

M M ,后来发现有的成长函数很难寻找，于是用B(N,k)B(N,k)作为成长函数的上界。最终通过上两个小节，我们找到了B(N,k) B ( N , k ) 的上界。也就是找到了mH(N) m H ( N ) 的上界。但是为什么mH(N) m H ( N ) 可以代替M M 呢，如果同一个dichotomy的不同hypothesis，不是完全重叠怎么办？

3 VC Bound

mH(N)mH(N)可以代替M M ，得到HH遇到hypothesis的概率的上界为：

PD[BADD]≤2∗mH(N)∗exp(−2ε2N) P D [ B A D D ] ≤ 2 ∗ m H ( N ) ∗ exp ⁡ ( − 2 ε 2 N )

PD[BADD]

P D [ B A D D ] 表示整个hypothesis set H H 遇到bad data的概率，也就是存在hypothesishh遇到bad data的概率。上面的公式可以改写为：

PD[∃h∈H,s.t.|Ein(g)−Eout(g)|>ε]≤2∗mH(N)∗exp(−2ε2N) P D [ ∃ h ∈ H , s . t . | E i n ( g ) − E o u t ( g ) | > ε ] ≤ 2 ∗ m H ( N ) ∗ exp ⁡ ( − 2 ε 2 N )

mH(N) m H ( N ) 直接代替M M 不合理，因为同一个dichotomy可能对应不同的hypothesis，而这些hypothesis的bad data不一定会完全重叠，所以直接代替不合理。那么从公式本身出发，同一个的dichotomy只能保证EinEin相同，并不能保证Eout E o u t 相同。所以我们可以替换掉Eout E o u t 吗？   推导我是看不懂了，当做定理记住咯！

PD[∃h∈H,s.t.|Ein(g)−Eout(g)|>ε]≤4∗mH(2N)∗exp(−18ε2N) P D [ ∃ h ∈ H , s . t . | E i n ( g ) − E o u t ( g ) | > ε ] ≤ 4 ∗ m H ( 2 N ) ∗ exp ⁡ ( − 1 8 ε 2 N )

4 Summary

mH(N) m H ( N ) 替换M M ,本文先得到了mH(N)mH(N)的上界，即Bound函数，继而找到了这Bound函数的上界。完了，又对不等式右端做了些变化使其可以完全替换掉M M $M$，继而说明了可泛化。

5 Ref

​​[1] Code

# 生成点的全排列 -----------------------------------------------------------------# 生成point_num个点的全排列## 参数说明:point_num点的个数，整数，point_type每个点的选择，字符串组成的向量combination_f <- function(point_num, point_type) { if (point_num == 1) { comb_data <- data.frame(point_type,stringsAsFactors = FALSE) colnames(comb_data) <- paste0("x",1:ncol(comb_data)) return(comb_data) }else{ comb_data <- combination_f(point_num-1,point_type) ## 生成列表长度为point_type个数的列表，其中每个列表都是上一步返回的数据框 ## 用do.call合并这些数据框 comb_data_new <- do.call("rbind",rep(list(comb_data),length(point_type))) ## comb_data_new 相当于复制 comb_data 这个数据框length(point_type)次 ## 只需新增一列，对comb_data_new中的每一个comb_data增加一种point_type即可 comb_data_new$newcol <- rep(point_type,each=nrow(comb_data_new)/length(point_type)) colnames(comb_data_new) <- paste0("x",1:ncol(comb_data_new)) return(comb_data_new) }}# 判断有没有被shatter -----------------------------------------------------------## 判断大小为dichotomy_num的dichotomy组合，在任意break_point个点时会不会被shatter## 参数:最小的break point---break_point；点的个数---point_num；## point_type---每个点的选择，字符串组成的向量；dichotomy_num---dichotomy组合的数量## all_comb_data---所有point_num^length(point_type)种组合 is_shatter_f <- function(break_point,point_num, point_type,dichotomy_num,all_comb_data){ ## 第一步生成dichotomy_num个dichotomy的所有组合 #### 首先point_num个点，总计能生成point_num^length(point_type)中情况，即dichotomy的所有组合。 #### 那么dichotomy_num个dichotomy的所有组合，就是求1:中不重复的选择dichotomy_num个dichotomy ## dichotomy_candidate的每一列数字，对应all_comb_data相应的行， dichotomy_candidate <- data.frame(combn(1:length(point_type)^point_num,dichotomy_num)) ## 下面生成所有break_point的全排列 #### 方便后面检查是不是被shatter shatter_comb_data <- combination_f(break_point, point_type) shatter_point_all_dichotomy_vector <- do.call('paste0',shatter_comb_data) ## 如果最小的break point为k，计算在point_num中所有k个点的组合情况 shatter_point_candidate <- data.frame(combn(1:point_num,break_point)) ## 下面遍历所有的情况，如果有一种情况没有被shatter，则返回True和对应的dichotomy组合 ## 最终返回所有的dichotomy组合 dichotomy_list <- list(result = FALSE) for(i in 1:ncol(dichotomy_candidate)){ ## 取出第i种情况下的dichotomy组合 subset_dichotomy <- all_comb_data[dichotomy_candidate[,i],] for(j in 1:ncol(shatter_point_candidate)){ index <- 1 ## break_point个点组合的第j种情况，拼接成向量 ## 这里有点问题，如果break point是1，do.call里面的就不是数据框了 if (break_point == 1) { break_point_dichotomy_vector <- subset_dichotomy[, shatter_point_candidate[, j]] } else{ break_point_dichotomy_vector <- do.call('paste0', subset_dichotomy[, shatter_point_candidate[, j]]) } ## 判断有没有被shatter if(all(shatter_point_all_dichotomy_vector %in% break_point_dichotomy_vector)){ ## 如果TRUE,说明第i种情况下的dichotomy组合在第j种点的组合下被sahtter ## 跳出这次循环，说明这种dichotomy组合被kill了 index <- 0 break } } ## 检查j和index的值 #### 如果j=ncol(dichotomy_candidate)且index=1 #### 说明所有点的组合都遍历了，且最后一个点的组合没有被shatter if(j==ncol(shatter_point_candidate)&index==1){ ## 只要有一个dichotomy组合成功没有被shatter，result就被标记为TRUE dichotomy_list$result <- TRUE dichotomy_list <- c(dichotomy_list,list(subset_dichotomy)) } } return(dichotomy_list)}# 生成满足break point的dichotomy## 参数break_point，点的个数point_num，点的种类point_type## break point含义对于任意的dichotomy组合，任意两列不能shatter## 即任意两列不能出现point_num=break_point的全排列dichotomy_by_breakpoint_f(break_point = 2,point_num = 4,point_type = c('o','x'))dichotomy_by_breakpoint_f <- function(break_point, point_num, point_type) { ## 第一步生成全排列 all_comb_data <- combination_f(point_num, point_type) ## 查看是否满足break point ## 有两种逻辑： ## 1、先从小到大，取到point_num=break_point时满足条件的dichotomy组合，完了增加一个点就复制length(point_type)份，填上一列，检查即可~ ## 2、先生成全排列，一次检查所有可能排列组合是否满足break point。这样暴力，代码好写，但是效率不高。 ## 先用2试一下 for (i in 1:nrow(all_comb_data)) { ## 检查当dichotomy数为i时，会不会被shatter temp_list <- is_shatter_f( break_point = break_point, point_num = point_num, point_type = point_type, dichotomy_num = i, all_comb_data = all_comb_data ) if (temp_list$result) { ## 没有被shatter，复制temp_list，用于返回结果 temp_list1 <- temp_list } else{ ## 如果出现被shatter的情况，说明第i个dichotomy及大于i个dichotomy都会被shatter break } } return(temp_list1) }

2018-01-24 于杭州

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。