《机器学习理论导引》笔记目录

• 第一章 : 预备知识
  • 第一章 : 预备知识(上)
  • 第一章 : 预备知识(下)
• 第二章 : 可学性
• 第三章 : 复杂度
• 第四章 : 泛化界
  • 第四章 : 泛化界(上)
  • 第四章 : 泛化界(中)
  • 第四章 : 泛化界(下)
• 第五章 : 稳定性
• 第六章 : 一致性
  • 第六章 : 一致性(上)
  • 第六章 : 一致性(下)
• 第七章 : 收敛率
  • 第七章 : 收敛率(上)
  • 第七章 : 收敛率(下)
• 第八章 : 遗憾界
  • 第八章 : 遗憾界(上)
  • 第八章 : 遗憾界(下)

6.3 划分机制

  一些机器学习方法可看作是将样本空间𝒳划分成多个互不相容的区域，然后在各区域中对正例和反例分别计数，以多数的类别作为区域中样本的标记，这被称为划分机制。常见的基于划分机制的机器学习方法包括最近邻、决策树、随机森林等。

  具体而言，给定训练集 ${\mathcal{D}}_m=\{(x_1,y_1),(x_2,y_2),\dots ,(x_m,y_m)\}$，基于某种划分机制将样本空间 $\mathcal{X}$ 划分成多个互不相容的区域 ${\Omega }_1,{\Omega }_2,\dots ,{\Omega }_n$，然后对每个区域中正例和反例进行计数，按“少数服从多数”原则确定区域中样本的标记，即有

$$h_m(x)=\{\begin{array}{ll}+1& \text{ 如果 }{\sum }_{x_i\in \Omega (x)}\mathbb{I}\left(y_i=+1\right)\ge {\sum }_{x_i\in \Omega (x)}\mathbb{I}\left(y_i=-1\right)\\ -1& \text{ 如果 }{\sum }_{x_i\in \Omega (x)}\mathbb{I}\left(y_i=+1\right)<{\sum }_{x_i\in \Omega (x)}\mathbb{I}\left(y_i=-1\right)\end{array}$$

  其中 $\Omega (x)$ 表示样本 $x$ 所在的区域。

定义 6.3 划分机制一致性

  随着训练数据规模 $m\to \infty$，若基于划分机制的输出函数 $h_m(x)$ 满足 $R(h_m)\to R^{\ast }$，则称该划分机制具有一致性。

  直观上看，划分机制具有一致性需要满足两个条件:

• 划分后的区域足够小，从而保证能够捕捉数据的局部信息
• 划分后的区域应包含足够多的训练样本，从而确保“少数服从多数”方法的有效性

  给定区域 $\Omega$，用 $\text{Diam}(\Omega )$ 表示区域 $\Omega$ 的直径，即 $\text{Diam}(\Omega )={\sup }_{x,x^{\prime }\in \Omega }\Vert x-x^{\prime }\Vert$，给定样本 $x\in \mathcal{X}$，设 $N(x)={\sum }_{i=1}^m\mathbb{I}(x_i\in \Omega (x))$，代表落入区域 $\Omega (x)$ 的样本数

引理 6.4

  设 $X_1,X_2,\dots ,X_m$ 是 $m$ 个独立同分布的 Bernoulli 随机变量，且满足 $X_i\sim \text{Bernoulli}(p)$，则有

$$\mathbb{E}\left[\left|\frac{1}{m}\sum _{i=1}^m{X}_i-\mathbb{E}[X_i]\right|\right]⩽\sqrt{\frac{p(1-p)}{m}}$$

证明

  根据 Jensen 不等式有

$$\begin{gathered} \mathbb{E}\left[\frac{1}{m}\sum _{i=1}^m{X}_i-\mathbb{E}\left[X_i\right]\right]⩽\sqrt{\mathbb{E}{\left[\frac{1}{m}\sum _{i=1}^m{X}_i-\mathbb{E}\left[X_i\right]\right]}^2} \\ =\sqrt{\frac{1}{m^2}\sum _{i=1}^m\mathbb{E}{\left[X_i-\mathbb{E}\left[X_i\right]\right]}^2}=\sqrt{\frac{v\left(X_1\right)}{m}}=\sqrt{\frac{p(1-p)}{m}} \end{gathered}$$

  引理得证。

定理 6.4

  假设条件概率 $\eta (x)$ 在样本空间 $\mathcal{X}$ 上连续，若划分后的每个区域满足 : 当 $m\to \infty$ 时有 $\text{Diam}(\Omega (x))\to 0$ 和 $N(x)\to \infty$ 依概率成立，则该划分机制具有一致性。

  其中依概率成立 (比极限更弱) 是指 : 对 $\forall ϵ>0,{\lim }_{m\to \infty }P((\text{Diam}(\Omega )-0)⩾)=0$，对 $\forall N>0,{\lim }_{m\to \infty }P(N(x)>N)=1$

证明

  对任意样本 $x\in \mathcal{X}$，设 $\hat{\eta }(x)={\sum }_{x_i\in \Omega (x)}\frac{\mathbb{I}(y_i=+1)}{N(x)}$，根据划分机制得到分类器 $h_m(x)=2\mathbb{I}\left(\hat{\eta }(x)⩾\frac{1}{2}\right)-1$，由引理 6.2，$R(h_m)-R^{\ast }⩽2\mathbb{E}[|\hat{\eta }(x)-\eta (x)|]$，设区域 $\Omega (x)$ 的条件概率的期望为 $\bar{\eta }(x)=\mathbb{E}[\eta (x^{\prime })|x^{\prime }\in \Omega (x)]$

  利用三角不等式有 $\mathbb{E}[|\hat{\eta }(x)-\eta (x)|]⩽\mathbb{E}[|\hat{\eta }(x)-\bar{\eta }(x)|]+\mathbb{E}[|\bar{\eta }(x)-\eta (x)|]$，根据 $\eta (x)$ 的连续性，以及当 $m\to \infty$ 时有 $\text{Diam}(\Omega (x))\to 0$ 依概率成立，从而得到 $\mathbb{E}[|\bar{\eta }(x)-\eta (x)|]\to 0$。

  下面只需证明 $\mathbb{E}[|\hat{\eta }(x)\le -\bar{\eta }(x)|]\to 0$

  给定 $x,x_1,\dots ,x_m$，有

$$\begin{array}{rl}& \mathbb{E}\left[\mid \hat{\eta }(x)-\bar{\eta }(x)\Vert x,x_1,\dots ,x_m\right]\\ =& \mathbb{E}\left[\mid \hat{\eta }(x)-\bar{\eta }(x)\Vert N(x)=0,x,x_1,\dots ,x_m\right]P(N(x)=0)+\\ & \mathbb{E}\left[\mid \hat{\eta }(x)-\bar{\eta }(x)\Vert N(x)>0,x,x_1,\dots ,x_m\right]P(N(x)>0)\\ ⩽& P\left(N(x)=0\mid x,x_1,\dots ,x_m\right)\\ +& \mathbb{E}\left[\mid \sum _{x_i\in \Omega (x)}\frac{\mathbb{I}\left(y_i=+1\right)-\bar{\eta }(x)}{N(x)}\Vert N(x)>0,x,x_1,\dots ,x_m\right]\end{array}$$

  $N(x)\hat{\eta }(x)$ 表示区域 $\Omega (x)$ 中正例的个数，其服从二项分布 $\mathcal{B}(N(x),\hat{\eta }(x))$，由引理 6.4，有

$$\begin{array}{rl}& \mathbb{E}\left[\mid \sum _{x_i\in \Omega (x)}\frac{\mathbb{I}\left(y_i=+1\right)-\bar{\eta }(x)}{N(x)}\Vert N(x)>0,x,x_1,\dots ,x_m\right]\\ & ⩽\mathbb{E}\left[\sqrt{\frac{\bar{\eta }(x)(1-\bar{\eta }(x))}{N(x)}}\mathbb{I}(N(x)>0)\mid x,x_1,\dots ,x_m\right]\\ & ⩽\frac{1}{2}P\left(1⩽N(x)⩽k\mid x,x_1,\dots ,x_m\right)+\frac{1}{2\sqrt{k}}P\left(N(x)>k\mid x,x_1,\dots ,x_m\right)\\ & ⩽\frac{1}{2}P\left(1⩽N(x)⩽k\mid x,x_1,\dots ,x_m\right)+\frac{1}{2\sqrt{k}}\end{array}$$

  结合以上两个不等式，有

$$\begin{array}{rl}& \mathbb{E}\left[|\hat{\eta }(x)-\bar{\eta }(x)|\mid x,x_1,\dots ,x_m\right]\\ & ⩽P\left(N(x)=0\mid x,x_1,\dots ,x_m\right)+\frac{1}{2}P\left(1⩽N(x)⩽k\mid x,x_1,\dots ,x_m\right)+\frac{1}{2\sqrt{k}}\end{array}$$

  对 $x,x_1,\dots ,x_m$ 取期望有

$$\mathbb{E}[|\hat{\eta }(x)-\bar{\eta }(x)|]⩽P(N(x)=0)+\frac{1}{2}P(1⩽N(x)⩽sk)+\frac{1}{2\sqrt{k}}$$

  取 $k=\sqrt{N(x)}$，根据条件 $N(x)\to \infty$ 依概率成立，有 $\mathbb{E}[|\hat{\eta }(x)\le -\bar{\eta }(x)|]\to 0$，代入三角不等式定理得证。

随机森林 (Random Forest)

  随机森林 (Random Forest) 是一种重要的集成学习方法 (ensemble learning)，通过对数据集进行有放回采样 (bootstrap sampling) 产生多个训练集，然后基于每个训练集产生随机决策树，最后通过投票法对随机决策树进行集成，这些随机决策树是在决策树生成过程中，对划分节点、划分属性及划分点引入随机选择而产生的。

  对随机决策树，可以引入一个新的随机变量 $Z\in \mathcal{Z}$，用以刻画决策树的随机性，即用 $h_m(x,Z)$ 表示随机决策树，这里 $m$ 表示训练集的大小。假设产生 $n$ 棵随机决策树 $h_m(x,Z_1),h_m(x,Z_2),\dots ,h_m(x,Z_n)$，然后根据这些决策树进行投票，从而构成随机森林 ${\bar{h}}_m(x;Z_1,\dots ,Z_n)$，即

$${\bar{h}}_m\left(x;Z_1,\dots ,Z_n\right)=\{\begin{array}{ll}+1& \text{ 如果 }{\sum }_{i=1}^n{h}_m\left(x,Z_i\right)\ge 0\\ -1& \text{ 如果 }{\sum }_{i=1}^n{h}_m\left(x,Z_i\right)<0\end{array}$$

引理 6.5

  对随机决策树 $h_m(x,Z)$ 和随机森林 ${\bar{h}}_m(x;Z_1,\dots ,Z_n)$，有

$$E_{Z_1,\dots ,Z_n}\left[R\left({\bar{h}}_m\left(x;Z_1,\dots ,Z_n\right)\right)\right]-{\mathrm{R}}^{\ast }\le 2\left(E_Z\left[R\left(h_m(x,Z)\right)\right]-R^{\ast }\right)$$

  此引理表明，若随机决策树 $h_m(x,Z)$ 具有一致性，则由随机决策树构成的随机森林 ${\bar{h}}_m(x;Z_1,\dots ,Z_n)$ 也具有一致性

证明

  根据引理 6.1 可知

$$\begin{array}{rl}{\mathbb{E}}_Z\left[R\left(h_m(x,Z)\right)\right]-R^{\ast }& ={\mathbb{E}}_{x\sim {\mathcal{D}}_x}\left[|1-2\eta (x)|\mathbb{I}\left(h_m(x,Z)\ne h^{\ast }(x)\right)\right]\\ & ={\mathbb{E}}_{x\sim {\mathcal{D}}_x}[(1-2\eta (x))\mathbb{I}\left(\eta (x)<\frac{1}{2}\right)P_Z\left(h_m(x,Z)=1\right)\\ & +(2\eta (x)-1)\mathbb{I}\left(\eta (x)>\frac{1}{2}\right)P_Z\left(h_m(x,Z)=-1\right)]\end{array}$$

  进一步得到

$$\begin{array}{rl}& {\mathbb{E}}_{Z_1,\dots ,Z_n}\left[R\left({\bar{h}}_m\left(x;Z_1,\dots ,Z_n\right)\right)\right]-R^{\ast }\\ ={\mathbb{E}}_{x\sim D_x}& [(1-2\eta (x))\mathbb{I}\left(\eta (x)<\frac{1}{2}\right)P_{Z_1,\dots Z_n}\left({\bar{h}}_m\left(x;Z_1,\dots ,Z_n\right)=1\right)\\ & +(2\eta (x)-1)\mathbb{I}\left(\eta (x)>\frac{1}{2}\right)P_{Z_1,\dots ,Z_n}\left({\bar{h}}_m\left(x;Z_1,\dots ,Z_n\right)=-1\right)]\end{array}$$

  对任意样本 $x\in \mathcal{X}$，当 $\eta (x)<1/2$ 时，只需证明 $P_{Z_1,\dots ,Z_n}\left({\bar{h}}_m\left(x;Z_1,\dots ,Z_n\right)=1\right)⩽2P_Z\left(h_m(x,Z)=1\right)$ 即可

$$\begin{array}{rl}& P_{Z_1,\dots ,Z_n}\left({\bar{h}}_m\left(x;Z_1,\dots ,Z_n\right)=1\right)=P_{Z_1,\dots ,Z_n}\left(\sum _{i=1}^n\mathbb{I}(h_m(x,Z_i)=1)⩾\frac{n}{2}\right)\\ & (\text{由 Markov 不等式})⩽\frac{2}{n}\sum _{i=1}^n\mathbb{E}[\mathbb{I}(h_m(x,Z_i)=1)]=2P(h_m(x,Z_i)=1)\end{array}$$

  同理可证 $\eta (x)⩾1/2$ 的情况，引理得证

定理 6.5

  当训练集规模 $m\to \infty$ 时，如果每棵随机决策树的迭代轮数 $k=k(m)\to \infty$ 且 $\frac{k}{m}\to 0$，则随机森林具有一致性

证明

  首先研究随机决策树的一致性，随机决策树本质上是基于划分机制的一种分类方法。考虑样本空间 $\mathcal{X}=[0,1{]}^d$，对任意 $x\in \mathcal{X}$，令 $\Omega (x,Z)$ 表示样本 $x$ 所在的区域，$N(x,Z)$ 表示落入 $\Omega (x,Z)$ 中的训练样本数，即 $N(x,Z)={\sum }_{i=1}^m\mathbb{I}(x_i\in \Omega (x,Z))$

  首先证明当 $m\to \infty$ 时 $N(x,Z)\to \infty$ 依概率几乎处处成立。设 ${\Omega }_1,{\Omega }_2,\dots ,{\Omega }_{k+1}$ 为随机决策树通过 $k$ 轮迭代后得到的 $k+1$ 个区域，且设 $N_1,N_2,\dots ,N_{k+1}$ 分别为训练集 ${\mathcal{D}}_m$ 落入这些区域的样本数。给定训练集 ${\mathcal{D}}_m$ 和随机变量 $Z$，样本 $x$ 落入区域 ${\Omega }_i$ 的概率为 $N_i/m$。

  对任意给定 $t>0$

$$P(N(x,Z)<t)=\mathbb{E}[P(N(x,Z)<t|D_m,Z)]=\mathbb{E}\left[\sum _{i:N_i<t}\frac{N_i}{m}\right]⩽(t-1)\frac{k+1}{m}\to 0$$

  其次证明当 $k\to \infty$ 时区域 $\Omega (x,Z)$ 的直径 $\text{Diam}(\Omega (x,Z))\to 0$ 依概率几乎处处成立。令 $T_m$ 表示区域 $\Omega (x,Z)$ 被划分的次数，根据随机决策树的构造可知 $T_m={\sum }_{i=1}^k{\xi }_i$，其中 ${\xi }_i\sim \text{Bernoulli}(1/i)$。于是有
，代入mathbb{E}

$$\mathbb{E}\left[T_m\right]=\sum _{i=1}^k\frac{1}{i}\ge \ln k,V\left(T_m\right)=\sum _{i=1}^k\frac{1}{i}\left(1-\frac{1}{i}\right)\le \ln k+1$$

  根据 Chebyshev 不等式可知，当 $k\to \infty$ 时有

$$P\left(\left|T_m-\mathbb{E}\left[T_m\right]\right|\ge \frac{\mathbb{E}\left[T_m\right]}{2}\right)\le 4\frac{V\left(T_m\right)}{\mathbb{E}{\left[T_m\right]}^2}\le 4\frac{\ln k+1}{{\ln }^{2}k}\to 0$$

  故 $P\left(T_m⩽\frac{\mathbb{E}[T_m]}{2}\right)\to 0$，代入 $\mathbb{E}[T_m]⩾\ln k$ 可得 $P\left(T_m⩾\frac{\ln k}{2}\right)\to 1$

  令 $L_j$ 表示区域 $\Omega (x,Z)$ 中第 $j$ 个属性的边长，根据随机决策树的构造可知

$$\mathbb{E}\left[L_j\right]\le \mathbb{E}\left[\mathbb{E}\left[\prod _{i=1}^{K_j}\max \left(U_i,1-U_i\right)\mid K_j\right]\right]$$

  这里的随机变量 $k_j\sim \mathcal{B}(T_m,1/d)$ 表示随机决策树构造中的第 $j$ 个属性被选用划分的次数，随机变量 $U_i\sim U(0,1)$ 表示第 $j$ 个属性被划分的位置。根据 $U_i\sim U(0,1)$ 有

$$\mathbb{E}\left[\max \left(U_i,1-U_i\right)\right]=2{\int }_{1/2}^1{U}_{i}d{U}_i=\frac{3}{4}$$

由此可得

$$\mathbb{E}\left(L_j\right)=\mathbb{E}\left[\mathbb{E}\left[{\Pi }_{i=1}^{K_j}\max \left(U_i,1-U_i\right)\mid K_j\right]\right]=\mathbb{E}\left[{\left(\frac{3}{4}\right)}^{K_j}\right]$$

  再根据 $k_j\sim \mathcal{B}(T_m,1/d)$ 有

$$\begin{array}{rl}E\left[L_j\right]=E\left[{\left(\frac{3}{4}\right)}^{K_j}\right]& =E\left[\sum _{k_{j=0}=0}^{T_m}{\left(\frac{3}{4}\right)}^{K_j}\left(T_{k_m}^{K_j}\right){\left(\frac{1}{a}\right)}^{K_j}{\left(1-\frac{1}{d}\right)}^{T_m-K_j}\right]\\ & =E\left[\sum _{k_{j=}=0}^{T_{T_m}}\left(T_m\right){\left(\frac{3}{4d}\right)}^{K_j}{\left(1-\frac{1}{d}\right)}^{T_m-K_j}\right]\\ & =E\left[{\left(1-\frac{1}{d}+\frac{3}{4d}\right)}^{T_m}\right]=E\left[{\left(1-\frac{1}{4d}\right)}^{T_m}\right]\end{array}$$

  又因为 $P\left(T_m⩾\frac{\ln k}{2}\right)\to 1$，当 $k\to \infty$ 时有 $\mathbb{E}[L_j]\to 0$，进而有 $\mathbb{E}\left[\text{Diam}(\Omega (x,Z))\right]\to 0$

  根据 $\text{Diam}(\Omega (x,Z))⩾0$ 和 $\mathbb{E}\text{Diam}(\Omega (x,Z))\to 0$ 可知 $P\left(\Omega (x,Z)⩾ϵ\right)\to 0$，即 $\text{Diam}(\Omega (x,Z))\to 0$ 依概率成立

  根据定理 6.2 可得随机决策树具有一致性。

  再根据引理 6.5 可知由随机决策树集成的随机森林也具有一致性。

  定理得证。