机器学习基石

admin 管理员组

文章数量: 1087649

机器学习基石

knitr::opts_chunk$set(echo = TRUE)

1 前文回顾

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

2 Restriction of Break Point

  有些 H H $H$的成长函数很容易找到，例如Part2中的Positive Rays、Positive Intervals等。有些则很难，如2D perceptrons。此时我们不考虑具体的H" role="presentation">HH$H$，只考虑能生成的dichotomy。比如，对于2D perceptrons，如果三点共线，且呈 o、x、o o 、 x 、 o $o、x、o$，则不认为这是一个dichotomy。而如果我们不考虑2D perceptrons这一限制，那么认为这是一种dichotomy。这样的话，如果知道break point时，我们可以 H H $H$作用于D" role="presentation">DD$D$
时，最多最多能产生多少dichotomy吗？相当于我们在寻找 mH(N) m H ( N ) $m_H(N)$的一个上界。
  举例说明，假设不知道某个 H H $H$的成长函数mH(N)" role="presentation">mH(N)mH(N)$m_H(N)$，但是知道最小的break point k=2 k = 2 $k=2$，那么 H H $H$作用与N=3" role="presentation">N=3N=3$N=3$时，最多最多产生多少种dichotomy？

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

2.1 Bounding Function

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

2.2 Part1 Of Bound Function

  关于 B(N,K) B ( N , K ) $B(N,K)$函数的求解分成两部分。首先考虑下面情况:
1. 当 k=1 k = 1 $k=1$时，break point为1，说明任意一个点不可能出现两种类型，因此 allB(N,1)=1 a l l B ( N , 1 ) = 1 $all \; B(N,1)=1$。
2. 当 N<k N < k $N<k$时，由break point的定义知，所有的 N N $N$个点都被shatter,即最多有2N" role="presentation">2N2N$2^N$个dichotomy。所以 B(N,k)=2N B ( N , k ) = 2 N $B(N,k)=2^N$。
3. 当 N=k N = k $N=k$时，说明此时被shatter，即不可能有 2N 2 N $2^N$个dichotomy。所以 B(N,k)=2N−1 B ( N , k ) = 2 N − 1 $B(N,k) = 2^N-1$。
4. 上一节中我们还求得 B(3,2)=4 B ( 3 , 2 ) = 4 $B(3,2)=4$
那么可以得到下面的图：

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

2.3 Part2 Of Bound Function

   N>k N > k $N>k$时， B(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)$能不能和前面这些已知的数据存在某种练习。
首先把 B(4,3) B ( 4 , 3 ) $B(4,3)$的所有情况写出来(Ps:我的程序也可以求)，共有11个dichotomy，记为 all a l l $all$。如果增加再一个dichotomy，会出现三个点被shatter的情况。

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

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

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

-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 ) $$\begin{array}{l} B\left( {4,3} \right) = 2\alpha + \beta \\ \alpha + \beta \le B\left( {3,3} \right)\\ \alpha \le B\left( {3,2} \right)\\\Rightarrow B\left( {4,3} \right) \le B\left( {3,3} \right) + B\left( {3,2} \right) \end{array}$$
根据公式，可以填满表格：

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

B(N,k)≤∑i=0k(Ni) B ( N , k ) ≤ ∑ i = 0 k ( N i ) $$B\left( {N,k} \right) \le \sum\limits_{i = 0}^k {\left( {\begin{array}{*{20}{c}} N\\ i \end{array}} \right)}$$
下面用数学归纳法证明(摘自《learning from data》)：
1. k=1 k = 1 $k=1$时， B(N,k)=1≤(1+N) B ( N , k ) = 1 ≤ ( 1 + N ) $B(N,k)=1 \le (1+N)$，对所有的 N N $N$不等式成立。只需考虑k&gt;1" role="presentation">k>1k>1$k>1$的情形。 N=1 N = 1 $N=1$时，不等式也成立。
2. 假设 N≤No N ≤ N o $N \le N_o$时，对于所有 k k $k$不等式都成立。那么只需证明N=No+1" role="presentation">N=No+1N=No+1$N=N_o+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 ) $$\begin{array}{l} B\left( {{N_o} + 1,k} \right) \le B\left( {{N_o},k} \right) + B\left( {{N_o},k - 1} \right)\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \sum\limits_{i = 0}^{k - 1} {\left( {\begin{array}{*{20}{c}} {{N_o}}\\ i \end{array}} \right)} + \sum\limits_{i = 0}^{k - 2} {\left( {\begin{array}{*{20}{c}} {{N_o}}\\ i \end{array}} \right)} \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left( {\begin{array}{*{20}{c}} {{N_o}}\\ 0 \end{array}} \right) + \sum\limits_{i = 1}^{k - 1} {\left( {\begin{array}{*{20}{c}} {{N_o}}\\ i \end{array}} \right)} + \sum\limits_{i = 1}^{k - 1} {\left( {\begin{array}{*{20}{c}} {{N_o}}\\ {i - 1} \end{array}} \right)} \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 1 + \sum\limits_{i = 1}^{k - 1} {\left\{ {\left( {\begin{array}{*{20}{c}} {{N_o}}\\ i \end{array}} \right) + \left( {\begin{array}{*{20}{c}} {{N_o}}\\ {i - 1} \end{array}} \right)} \right\}} \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 1 + \sum\limits_{i = 1}^{k - 1} {\left( {\begin{array}{*{20}{c}} {{N_o} + 1}\\ i \end{array}} \right)} \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \sum\limits_{i = 0}^{k - 1} {\left( {\begin{array}{*{20}{c}} {{N_o} + 1}\\ i \end{array}} \right)} \end{array}$$
中间合并组合项和公式是用组合数公式的递推公式:
(Nm)=(N−1m)+(N−1m−1) ( N m ) = ( N − 1 m ) + ( N − 1 m − 1 ) $$\left( {\begin{array}{*{20}{c}} N\\ m \end{array}} \right) = \left( {\begin{array}{*{20}{c}} {N - 1}\\ m \end{array}} \right) + \left( {\begin{array}{*{20}{c}} {N - 1}\\ {m - 1} \end{array}} \right)$$
此时不等式成立，至于归纳法，就学过一个变量的证明，凑活看吧。

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

3 VC Bound

  我们假设mH(N)" role="presentation">mH(N)mH(N)$m_H(N)$可以代替 M M $M$，得到H" role="presentation">HH$H$遇到hypothesis的概率的上界为：

PD[BADD]≤2∗mH(N)∗exp(−2ε2N) P D [ B A D D ] ≤ 2 ∗ m H ( N ) ∗ exp ⁡ ( − 2 ε 2 N ) $${P_D}\left[ {BAD\;D} \right] \le 2 * {m_H}\left( N \right) * \exp \left( { - 2{\varepsilon ^2}N} \right)$$
   PD[BADD] P D [ B A D D ] ${P_D}\left[ {BAD\;D} \right]$表示整个hypothesis set H H $H$遇到bad data的概率，也就是存在hypothesish" role="presentation">hh$h$遇到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 ) $${P_D}\left[ {\exists \;h \in H,\;s.t.\;\left| {{E_{in}}\left( g \right) - {E_{out}}\left( g \right)} \right| > \varepsilon } \right] \le 2 * {m_H}\left( N \right) * \exp \left( { - 2{\varepsilon ^2}N} \right)$$

  上一小节末提到用 mH(N) m H ( N ) $m_H(N)$直接代替 M M $M$不合理，因为同一个dichotomy可能对应不同的hypothesis，而这些hypothesis的bad data不一定会完全重叠，所以直接代替不合理。那么从公式本身出发，同一个的dichotomy只能保证Ein" role="presentation">EinEin$E_{in}$相同，并不能保证 Eout E o u t $E_{out}$相同。所以我们可以替换掉 Eout E o u t $E_{out}$吗？
  推导我是看不懂了，当做定理记住咯！

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 ) $${P_D}\left[ {\exists \;h \in H,\;s.t.\;\left| {{E_{in}}\left( g \right) - {E_{out}}\left( g \right)} \right| > \varepsilon } \right] \le 4 * {m_H}\left( 2N \right) * \exp \left( { - \frac{1}{8}{\varepsilon ^2}N} \right)$$

4 Summary

  前文我们试图用 mH(N) m H ( N ) $m_H(N)$替换 M M $M$,本文先得到了mH(N)" role="presentation">mH(N)mH(N)$m_H(N)$的上界，即Bound函数，继而找到了这Bound函数的上界。完了，又对不等式右端做了些变化使其可以完全替换掉 M M <script type="math/tex" id="MathJax-Element-104">M</script>，继而说明了可泛化。

5 Ref

[1] .html
[2]

6 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]])}## 判断有没有被shatterif(all(shatter_point_all_dichotomy_vector %in% break_point_dichotomy_vector)){## 如果TRUE,说明第i种情况下的dichotomy组合在第j种点的组合下被sahtter## 跳出这次循环，说明这种dichotomy组合被kill了index <- 0break}}## 检查j和index的值#### 如果j=ncol(dichotomy_candidate)且index=1#### 说明所有点的组合都遍历了，且最后一个点的组合没有被shatterif(j==ncol(shatter_point_candidate)&index==1){## 只要有一个dichotomy组合成功没有被shatter，result就被标记为TRUEdichotomy_list$result <- TRUEdichotomy_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时，会不会被shattertemp_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都会被shatterbreak}}return(temp_list1)}

                                        2018-01-24 于杭州

本文标签： 机器学习基石