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

网友投稿 607 2022-09-02

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

机器学习基石---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 ,继而说明了可泛化。

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小时内删除侵权内容。

上一篇:用PHP如何实现解析抖音无水印视频(php仿抖音短视频源码)
下一篇:PHP基于Token的身份验证的方法,可参考学习下
相关文章

 发表评论

暂时没有评论,来抢沙发吧~