机器学习基石---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小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~