本文正在参加 人工智能创作者扶持计划
6.3 区分机制
一些机器学习办法可看作是将样本空间区分红多个互不相容的区域,然后在各区域中对正例和反例别离计数,以大都的类别作为区域中样本的符号,这被称为区分机制。常见的依据区分机制的机器学习办法包括最近邻、决策树、随机森林等。
具体而言,给定练习集 Dm={(x1,y1),(x2,y2),…,(xm,ym)}\mathcal{D}_m=\{(x_1,y_1),(x_2,y_2),\ldots,(x_m,y_m)\},依据某种区分机制将样本空间 X\mathcal{X} 区分红多个互不相容的区域 1,2,…,n\Omega_1,\Omega_2,\ldots,\Omega_n,然后对每个区域中正例和反例进行计数,按“少数遵守大都”准则确认区域中样本的符号,即有
其间 (x)\Omega(x) 表明样本 xx 地点的区域。
定义 6.3 区分机制一致性
跟着练习数据规划 m→∞m\rightarrow\infty,若依据区分机制的输出函数 hm(x)h_m(x) 满意 R(hm)→R∗R(h_m)\rightarrow R^*,则称该区分机制具有一致性。
直观上看,区分机制具有一致性需求满意两个条件:
- 区分后的区域满足小,然后保证能够捕捉数据的部分信息
- 区分后的区域应包括满足多的练习样本,然后保证“少数遵守大都”办法的有效性
给定区域 \Omega,用 Diam()\text{Diam}(\Omega) 表明区域 \Omega 的直径,即 Diam()=supx,x′∈∥x−x′∥\text{Diam}(\Omega)=\sup_{x,x’\in\Omega}\lVert x-x’\rVert,给定样本 x∈Xx\in\mathcal{X},设 N(x)=∑i=1mI(xi∈(x))N(x)=\sum_{i=1}^m\mathbb{I}(x_i\in\Omega(x)),代表落入区域 (x)\Omega(x) 的样本数
引理 6.4
设 X1,X2,…,XmX_1,X_2,\ldots,X_m 是 mm 个独立同散布的 Bernoulli 随机变量,且满意 Xi∼Bernoulli(p)X_i\sim\text{Bernoulli}(p),则有
证明
依据 Jensen 不等式有
=\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}}
引理得证。
定理 6.4
假定条件概率 (x)\eta(x) 在样本空间 X\mathcal{X} 上连续,若区分后的每个区域满意 : 当 m→∞m\rightarrow\infty 时有 Diam((x))→0\text{Diam}(\Omega(x))\rightarrow0 和 N(x)→∞N(x)\rightarrow\infty 依概率建立,则该区分机制具有一致性。
其间依概率建立 (比极限更弱) 是指 : 对 ∀>0,limm→∞P((Diam()−0)⩾)=0\forall\epsilon>0,\lim_{m\rightarrow\infty}P((\text{Diam}(\Omega)-0)\geqslant)=0,对 ∀N>0,limm→∞P(N(x)>N)=1\forall N>0,\lim_{m\rightarrow\infty}P(N(x)>N)=1
证明
对恣意样本 x∈Xx\in\mathcal{X},设 (x)=∑xi∈(x)I(yi=+1)N(x)\hat{\eta}(x)=\sum_{x_i\in\Omega(x)}\frac{\mathbb
{I}(y_i=+1)}{N(x)},依据区分机制得到分类器 hm(x)=2I((x)⩾12)−1h_m(x)=2\mathbb{I}\left(\hat{\eta}(x)\geqslant\frac{1}{2}\right)-1,由引理 6.2,R(hm)−R∗⩽2E[∣(x)−(x)∣]R(h_m)-R^*\leqslant2\mathbb{E}[\lvert\hat{\eta}(x)-\eta(x)\rvert],设区域 (x)\Omega(x) 的条件概率的期望为 (x)=E[(x′)∣x′∈(x)]\bar{\eta}(x)=\mathbb{E}[\eta(x’)|x’\in\Omega(x)]
利用三角不等式有 E[∣(x)−(x)∣]⩽E[∣(x)−(x)∣]+E[∣(x)−(x)∣]\mathbb{E}[\lvert\hat{\eta}(x)-\eta(x)\rvert]\leqslant\mathbb{E}[\lvert\hat{\eta}(x)-\bar{\eta}(x)\rvert]+\mathbb{E}[\lvert\bar{\eta}(x)-\eta(x)\rvert],依据 (x)\eta(x) 的连续性,以及当 m→∞m\rightarrow\infty 时有 Diam((x))→0\text{Diam}(\Omega(x))\rightarrow0 依概率建立,然后得到 E[∣(x)−(x)∣]→0\mathbb{E}[\lvert\bar{\eta}(x)-\eta(x)\rvert]\rightarrow0。
下面只需证明 E[∣(x)≤−(x)∣]→0\mathbb{E}[\lvert\hat{\eta}(x)\leq-\bar{\eta}(x)\rvert]\rightarrow0
给定 x,x1,…,xmx,x_1,\ldots,x_m,有
& \mathbb{E}\left[\mid \hat{\eta}(x)-\bar{\eta}(x) \| x, x_1, \ldots, x_m\right] \\
=&\mathbb{E}\left[\mid \hat{\eta}(x)-\bar{\eta}(x) \| N(x)=0, x, x_1, \ldots, x_m\right] P(N(x)=0)+ \\
& \mathbb{E}\left[\mid \hat{\eta}(x)-\bar{\eta}(x) \| N(x)>0, x, x_1, \ldots, x_m\right] P(N(x)>0) \\
\leqslant & P\left(N(x)=0 \mid x, x_1, \ldots, 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)} \| N(x)>0, x, x_1, \ldots, x_m\right]\\
\end{aligned}
N(x)(x)N(x)\hat{\eta}(x) 表明区域 (x)\Omega(x) 中正例的个数,其遵守二项散布 B(N(x),(x))\mathcal{B}(N(x),\hat{\eta}(x)),由引理 6.4,有
& \mathbb{E}\left[\mid \sum_{x_i \in \Omega(x)} \frac{\mathbb{I}\left(y_i=+1\right)-\bar{\eta}(x)}{N(x)} \| N(x)>0, x, x_1, \ldots, x_m\right] \\
& \leqslant \mathbb{\mathbb{E}}\left[\sqrt{\frac{\bar{\eta}(x)(1-\bar{\eta}(x))}{N(x)}} \mathbb{I}(N(x)>0) \mid x, x_1, \ldots, x_m\right] \\
& \leqslant \frac{1}{2} P\left(1 \leqslant N(x) \leqslant k \mid x, x_1, \ldots, x_m\right)+\frac{1}{2 \sqrt{k}} P\left(N(x)>k \mid x, x_1, \ldots, x_m\right) \\
& \leqslant \frac{1}{2} P\left(1 \leqslant N(x) \leqslant k \mid x, x_1, \ldots, x_m\right)+\frac{1}{2 \sqrt{k}}
\end{aligned}
结合以上两个不等式,有
& \mathbb{E}\left[|\hat{\eta}(x)-\bar{\eta}(x)| \mid x, x_1, \ldots, x_m\right] \\
& \leqslant P\left(N(x)=0 \mid x, x_1, \ldots, x_m\right)+\frac{1}{2} P\left(1 \leqslant N(x) \leqslant k \mid x, x_1, \ldots, x_m\right)+\frac{1}{2 \sqrt{k}}
\end{aligned}
对 x,x1,…,xmx,x_1,\ldots,x_m 取期望有
取 k=N(x)k=\sqrt{N(x)},依据条件 N(x)→∞N(x)\rightarrow\infty 依概率建立,有 E[∣(x)≤−(x)∣]→0\mathbb{E}[\lvert\hat{\eta}(x)\leq-\bar{\eta}(x)\rvert]\rightarrow0,代入三角不等式定理得证。
随机森林 (Random Forest)
随机森林 (Random Forest) 是一种重要的集成学习办法 (ensemble learning),经过对数据集进行有放回采样 (bootstrap sampling) 产生多个练习集,然后依据每个练习集产生随机决策树,最终经过投票法对随机决策树进行集成,这些随机决策树是在决策树生成过程中,对区分节点、区分特点及区分点引入随机选择而产生的。
对随机决策树,能够引入一个新的随机变量 Z∈ZZ\in\mathcal{Z},用以描写决策树的随机性,即用 hm(x,Z)h_m(x,Z) 表明随机决策树,这里 mm 表明练习集的大小。假定产生 nn 棵随机决策树 hm(x,Z1),hm(x,Z2),…,hm(x,Zn)h_m(x,Z_1),h_m(x,Z_2),\ldots,h_m(x,Z_n),然后依据这些决策树进行投票,然后构成随机森林 hm(x;Z1,…,Zn)\bar{h}_m(x;Z_1,\ldots,Z_n),即
引理 6.5
对随机决策树 hm(x,Z)h_m(x,Z) 和随机森林 hm(x;Z1,…,Zn)\bar{h}_m(x;Z_1,\ldots,Z_n),有
此引理表明,若随机决策树 hm(x,Z)h_m(x,Z) 具有一致性,则由随机决策树构成的随机森林 hm(x;Z1,…,Zn)\bar{h}_m(x;Z_1,\ldots,Z_n) 也具有一致性
证明
依据引理 6.1 可知
\mathbb{E}_Z\left[R\left(h_m(x, Z)\right)\right]-R^* &= \mathbb{E}_{x \sim \mathcal{D}_x}\left[|1-2 \eta(x)| \mathbb{I}\left(h_m(x, Z) \neq h^*(x)\right)\right] \\
&=\mathbb{E}_{x \sim \mathcal{D}_x}\left[(1-2 \eta(x)) \mathbb{I}\left(\eta(x)<\frac{1}{2}\right) P_Z\left(h_m(x, Z)=1\right)\right. \\
&\left.+(2 \eta(x)-1) \mathbb{I}\left(\eta(x)>\frac{1}{2}\right) P_Z\left(h_m(x, Z)=-1\right)\right]
\end{aligned}
进一步得到
&\mathbb{E}_{Z_1, \ldots, Z_n}\left[R\left(\bar{h}_m\left(x ; Z_1, \ldots, Z_n\right)\right)\right]-R^*\\
=\mathbb{E}_{x \sim D_x} & {\left[(1-2 \eta(x)) \mathbb{I}\left(\eta(x)<\frac{1}{2}\right) P_{Z_1, \ldots Z_n}\left(\bar{h}_m\left(x ; Z_1, \ldots, Z_n\right)=1\right)\right.} \\
& \left.+(2 \eta(x)-1) \mathbb{I}\left(\eta(x)>\frac{1}{2}\right) P_{Z_1, \ldots, Z_n}\left(\bar{h}_m\left(x ; Z_1, \ldots, Z_n\right)=-1\right)\right]
\end{aligned}
对恣意样本 x∈Xx\in\mathcal{X},当 (x)<1/2\eta(x)<1/2 时,只需证明 PZ1,…,Zn(hm(x;Z1,…,Zn)=1)⩽2PZ(hm(x,Z)=1)P_{Z_1, \ldots, Z_n}\left(\bar{h}_m\left(x ; Z_1, \ldots, Z_n\right)=1\right) \leqslant 2 P_Z\left(h_m(x, Z)=1\right) 即可
&P_{Z_1, \ldots, Z_n}\left(\bar{h}_m\left(x ; Z_1, \ldots, Z_n\right)=1\right)=P_{Z_1, \ldots, Z_n}\left(\sum_{i=1}^n\mathbb{I}(h_m(x,Z_i)=1)\geqslant\frac{n}{2}\right)\\
&(\text{由 Markov 不等式})\leqslant\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{aligned}
同理可证 (x)⩾1/2\eta(x)\geqslant1/2 的情况,引理得证
定理 6.5
当练习集规划 m→∞m\rightarrow\infty 时,假如每棵随机决策树的迭代轮数 k=k(m)→∞k=k(m)\rightarrow\infty 且 km→0\frac{k}{m}\rightarrow0,则随机森林具有一致性
证明
首要研讨随机决策树的一致性,随机决策树本质上是依据区分机制的一种分类办法。考虑样本空间 X=[0,1]d\mathcal{X}=[0,1]^d,对恣意 x∈Xx\in\mathcal{X},令 (x,Z)\Omega(x,Z) 表明样本 xx 地点的区域,N(x,Z)N(x,Z) 表明落入 (x,Z)\Omega(x,Z) 中的练习样本数,即 N(x,Z)=∑i=1mI(xi∈(x,Z))N(x,Z)=\sum_{i=1}^m\mathbb{I}(x_i\in\Omega(x,Z))
首要证明当 m→∞m\rightarrow\infty 时 N(x,Z)→∞N(x,Z)\rightarrow\infty 依概率简直处处建立。设 1,2,…,k+1\Omega_1,\Omega_2,\ldots,\Omega_{k+1} 为随机决策树经过 kk 轮迭代后得到的 k+1k+1 个区域,且设 N1,N2,…,Nk+1N_1,N_2, \ldots,N_{k+1} 别离为练习集 Dm\mathcal{D}_m 落入这些区域的样本数。给定练习集 Dm\mathcal{D}_m 和随机变量 ZZ,样本 xx 落入区域 i\Omega_i 的概率为 Ni/mN_i/m。
对恣意给定 t>0t>0
\rightarrow 0
其次证明当 k→∞k\rightarrow\infty 时区域 (x,Z)\Omega(x, Z) 的直径 Diam((x,Z))→0\text{Diam}(\Omega(x,Z))\rightarrow 0 依概率简直处处建立。令 TmT_m 表明区域 (x,Z)\Omega(x, Z) 被区分的次数,依据随机决策树的结构可知 Tm=∑i=1kiT_m=\sum_{i=1}^k\xi_i,其间 i∼Bernoulli(1/i)\xi_i\sim\text{Bernoulli}(1/i)。于是有
,代入\mathbb{E}
依据 Chebyshev 不等式可知,当 k→∞k\rightarrow\infty 时有
故 P(Tm⩽E[Tm]2)→0P\left(T_m\leqslant\frac{\mathbb{E}[T_m]}{2}\right)\rightarrow 0,代入 E[Tm]⩾lnk\mathbb{E}[T_m]\geqslant\ln k 可得 P(Tm⩾lnk2)→1P\left(T_m \geqslant\frac{\ln k}{2}\right)\rightarrow 1
令 LjL_j 表明区域 (x,Z)\Omega(x, Z) 中第 jj 个特点的边长,依据随机决策树的结构可知
这里的随机变量 kj∼B(Tm,1/d)k_j\sim\mathcal{B}(T_m,1/d) 表明随机决策树结构中的第 jj 个特点被选用区分的次数,随机变量 Ui∼U(0,1)U_i\sim U(0,1) 表明第 jj 个特点被区分的方位。依据 Ui∼U(0,1)U_i\sim U(0,1) 有
由此可得
再依据 kj∼B(Tm,1/d)k_j\sim\mathcal{B}(T_m,1/d) 有
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}{4 d}\right)^{K_j}\left(1-\frac{1}{d}\right)^{T_m-K_j}\right] \\
& =E\left[\left(1-\frac{1}{d}+\frac{3}{4 d}\right)^{T_m}\right]=E\left[\left(1-\frac{1}{4 d}\right)^{T_m}\right]
\end{aligned}
又由于 P(Tm⩾lnk2)→1P\left(T_m\geqslant\frac{\ln k}{2}\right)\rightarrow 1,当 k→∞k\rightarrow\infty 时有 E[Lj]→0\mathbb{E}[L_j]\rightarrow 0,进而有 E[Diam((x,Z))]→0\mathbb{E}\left[\text{Diam}(\Omega(x,Z))\right]\rightarrow 0
依据 Diam((x,Z))⩾0\text{Diam}(\Omega(x,Z))\geqslant 0 和 EDiam((x,Z))→0\mathbb{E}\text{Diam}(\Omega(x,Z))\rightarrow 0 可知 P((x,Z)⩾)→0P\left(\Omega(x,Z)\geqslant\epsilon\right)\rightarrow 0,即 Diam((x,Z))→0\text{Diam}(\Omega(x,Z))\rightarrow 0 依概率建立
依据定理 6.2 可得随机决策树具有一致性。
再依据引理 6.5 可知由随机决策树集成的随机森林也具有一致性。
定理得证。