多元随机森林估计的渐近正态性

就像命题3一样，我们认为这个要求在应用中似乎更宽松。原因是，它用于给出在L拆分后创建的超矩形v上的以下界限| v |≥ αL.（57）α指数小（即2-五十） 节点的比例是取尽可能小的EL/Lδ>/适当值的结果。3.5将命题3和命题6与等式（33）和（34）相结合，得出本节开头讨论的Vart的对角项的期望界（31）。因此，命题2适用，并建立了随机森林估计的联合正态性。4启发式和模拟前面的部分重点是推导渐近正态性结果-1/2（射频）-u）距离====> N（0，I），其中V=VarRF=snVarT。（58）回顾一下我们的常设大会∈ Rqis随机森林估计值atx，xqandu是它的期望值。根据（9），随机森林的目标函数实际上是ismxEY | XxRFx- mx/√Vdist====> N、 x∈ XVvanish相对于对角线，逐点的结果延续到我们的多元设置，andV-1/2（射频）-m） 距离====> N（0，I），其中m=（m（x），m（xq））。√Vx\'x∈,pare独立于极限n→ ∞,Var（RF（x）+RF（x））=Var（RF（x））+Var（RF（x））+2cov（RF（x）+RF（x））≈ Var（RF（x））+Var（RF（\'x）），（59），因此，可以有效地应用标量情况下的刀切估计，以获得随机森林估计函数的密集带（即，涉及多个点的估计的表达式）。有限样本。在本节中，我们为协方差项提供了一个“封底”，这可能对从业者有用。我们强调，以下计算（主要）是启发式的：如上所示，协方差项取决于asM（x，\'\'x）等量，这在很大程度上取决于基本分裂算法的精确机制。

自从我们的部门。首先，命题3和命题6的证明表明，上界为m（x，`x）+对数的渐近方差vhaso off-对角项∞X`=0p`∞X`=0\'p`= M（x，\'x）+E（L）E（\'L）（60）p`PL≥ `xx`表示\'p`=p（\'L≥ `). 也就是说，Lis是X和X延伸到同一分区之前的拆分数。如果我们用I（resp.\'I）表示x（resp.\'x）的终端节点中的指示符变量，那么事件{I=1}和{L=logs}是相等的，因此e（I | x=x）=P（L=logs）≤E Llog s.（61）E Llog sEI | XX表明协方差项由（对数）E（I | X=X）E（\'I | X=X）限定≈ （对数）M（x，\'x）。（62）备注。粗略地说，这个启发式算法表示，随机森林估计器rf被认为是域x上的函数，是协方差过程（logs）·M（x，’x）的渐近高斯分布。我们强调，这不是我们的理论结果所暗示的，因为我们在那里保持了测试点的数量q固定。为了得到一个有用的启发，我们将考虑相关性的界，而不是协方差。这是一个非常粗糙的上限，因为我们已经降低了数量（α’s）来自有限系列。在我们的符号中，[]下界SM（x，x）（和M（\'x，\'x））的结果，而我们的文章提供了M（x，\'x）上的上界。忽略对数项，我们得到Cov（RF（x），RF（\'x））pVar RF（x）·Var RF（\'x）≈M（x，\'x）pM（x，x）M（\'x，\'x）。（63）回想一下m（x，\'x）=E[E（I|x）E（\'I|x）]，它随着“x”离开x而衰变。使用前面的表达式（注意m（x，x）≈ M（\'x，\'x）由于x和\'x之间的对称性，我们可以从纯粹的几何考虑来限制相关性。

由于被积函数（I | X）E（|I | X）（64）随着X远离X（和| X）而衰减，我们可以想象它的积分m（X，X）=ZxE（I | X=X）dx（65）对点X nearx的贡献最大，比如aL中的点∞-侧边长度为Ddp{y的盒子∈,pkx- yk≤ d/}Mx，\'xd/x\'x近似，这些点的体积{y∈ [0,1]p:kx- yk∞≤ d/2，k\'x- yk≤ d/2}是（d- z） 。（d）- （zp）≈ 数据处理- （z+···+zp）dp-1，式中zi=|xj- 其中，如果| zi |1.除以bydp，后一组的体积比例为1-dkx- \'\'xk，这将导致启发式Cov（RF（x），RF（\'x））pVar RF（x）·Var RF（\'x）≈ 1.- ckx- 对于某些常数c.（67），RHS在nx=\'x时具有正确的标度，即相关性等于1时x- \'\'xk=0。用kx在另一个极端保持正确的比例- \'xk=p，我们应该取c=1/p，这样Cov（RF（x），RF（\'x））pVar RF（x）·Var RF（\'x）= 1.-ppXi=1 | xi- |xi |。（68）当然，这种启发式肯定是错误的，因为它不依赖于；我们的理论结果表明，即使对于非截然相反的点，相关性也降至零→ ∞.因此，另一个建议是使用Cov（RF（x），RF（\'x））pVar RF（x）·Var RF（\'x）= 闵1.-sppXi=1 | xi- \'xi |，0, （69）对一些人来说 >0，其中依赖项源于将M（x，\'x）的衰变视为x从x移动（c.f.证明命题3）。4.1模拟在本节中，我们讨论计算相关结构的模拟结果。在我们的实验中，我们设定P=2，这样协变量X分布在单位平方上。

X的分布被选为“四模态”X~概率为1/4的N（u，I）概率为1/4的N（u，I）概率为1/4的N（u，I）概率为1/4的N（u，I）概率为1/4的N（u，I）概率为1/4的u=（0.3,0.3）|u=（0.3,0.7）|u=（0.7,0.3）|u=（0.7,0.7）|（70）|单位平方上的有界密度，在u处有四个峰值，u. 条件在X=（X，X）上的分布是y~x+x+N（0,1）。（71）随机分裂概率为δ=1/2，正则性参数为α=0.01和k=1，因此树的生长达到最大程度（即终端节点可能包含一个观测值），每个终端节点位于单位平方的101×101网格上。对于每一个样本大小，种植了几百棵树，并对估计值进行汇总以计算相关性。图1绘制了估算值在X和¨X之间的相关性，作为KX的函数- “xk。xThounds trees）as“x”在每个细胞上的范围：相关性与tLNORMKx相关- “xk。然后，通过改变参考点x和相关性atkx来重复该过程- “-xkis是观察到的相关性的平均值。该图表明，前一节中给出的线性启发法（69）是保守的：很明显，随着x和¨x分离，相关性呈超线性下降。图2以对数标度绘制了相关性，这表明相关性在单位附近呈指数衰减。

换言之，模拟表明，正确的启发式是这样的形状Cov（RF（x），RF（\'x））pVar RF（x）·Var RF（\'x）≈ E-λkx-对于合适的λ，xk（72）。也就是说，`N（u，∑）表示x的条件分布~ 事件x上的N（u，∑）∈ [0,1].0.000.250.500.751.000.0 0.5 1.0 1.5L1标准相关性1002003004005006007008000001000200040005000600070000009000000200000300004000050006000000700000800001000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000。-10-7.5-5-2.50.00.0.1 0.2 0.3L1 NormLog（相关）N10020030040050060070080090010000002000000060008000900020000030000400005000600070000070000080000100000000000000020000000000000400000000060000007000000000000000008000000000000000000000000000000000000000000000000000000000000000010000001500000Log具有不同样本大小和L1 NormLog的对数相关图2：作为样本大小和Lnorm函数的相关对数。5结论随机森林和基于树的方法是应用数据分析工具包的重要组成部分。在本文中，我们研究了几个点上随机森林估计之间的协方差。我们开发了一种新的有向无环图结构，当已知一个点的知识时（命题5和命题6），它可以跟踪分裂概率。作为证明的一部分，我们建立了一类分裂规则的稳定性（见命题4）。我们还确定（命题3）M（x，`x），它（粗略地）捕获了属于同一终端节点的两点的可能性，作为控制多元随机森林协方差矩阵的反对角项的关键量。通过这种方式，本文为在特征空间的多个点上对目标函数进行推理提供了理论基础。具体而言，我们表明协方差是有限样本。最后，我们讨论了未来研究的几个途径。

第一个是扩展我们的框架，以涵盖分类或离散值特征。在这里，需要新的假设来保证节点大小“不太小”第二，我们对随机森林协方差矩阵的潜在改进后的边界可与[，]的重新集中结果一起使用，以提供有限样本高斯近似。这将为我们的启发法提供理论基础，并增加本文对实践者的有用性。命题1的证明。对于Rq中的随机向量，定义内积Hx，Y i：- E（X | MY）。（73）对于每个子集A {1，…，n}，设HAbe为formg（Xi:i）的平方可积随机向量集∈ A） ，其中g是| A |参数的函数，满足条件e（g（Xi:i∈ A） |{Xi:我∈ B} ）=0（74）B（AHAAsubsets{，…，n}。通过归纳，onr=|A |，直接sumLBAHBis等于{Xi:i的函数的所有统计量的集合∈ A} 。特别是，LAHAis是基于{X，…，Xn}{X，…，Xn}HA | A |的所有统计数据的集合，存在函数sh，H，Hn，其中hk是k元函数的集合，例如hHatha={g（Xi:i）∈ A） ：g∈ H | A |}。（75）根据（73）中给出的内积，将f投影到HK上，证明就完成了。命题2的证明。我们将证明一个更一般的说法，即ifa和bn是两个具有有界项的方阵序列，对于所有n和Aii，对于某些δ，bii>δ≥biilogn（76）andAij=o（1/logn），然后tr（A）-1B）→为了证明这一点，从行列式APπ开始-sgnπQqi=1aiπiπ{，…，n}sgnπAijAii，我们有| det A |~QAii，符号A在哪里~ b C|b|的标准≤ |a|≤ c | b |对于康斯坦茨和cnot，取决于n。接下来，回想一下克拉默规则（A）-1） ii=数据A-i/det A，（77）A-Iaiit | det A-我|~Qj6=iAjj，从何处（A-1） 二,~好吧。

（78）尤其是矩阵A的第i个对角线条目-1B由（A）给出-1B）ii=（A）-1） iiBii+Xj6=i（A-1） 伊比吉~比亚伊≤ 对数n，（79），其中最终关系是由于（A-1） ij本身是一个多项式，由a（即a的辅因子矩阵）除以行列式。因此，一个-1按对数n的顺序排列，因为每个矩阵的维数q×qo是固定的。使用子样本大小=nβ，因此S/n=n-(1-β） 完成证明。命题3的证明。回想一下，分裂算法在第j轴上分裂的概率δ。由于每个终端节点包含恒定数量的点，因此终端节点到达的终端数量以logs/K=logs/K（其中K=2k）为界（由一个常数）-1是叶子的最大尺寸。由于x 6=\'x，我们有0<kx- \'\'xk∞≤ kx- xk∞+ k\'x- xk∞（80）对于allx∈ 特别是，在给定的条件下∈ {，…，p}和|xj的常数β- x1j |>β| xj- 前一个案子成立。当然，x=xto属于大于β的同一叶节点asx{I}的一个必要条件。Letcj（x）表示指向包含x的终端节点的拆分序列中的拆分数量。根据我们的随机化假设，每个分裂至少有一个被选择的独立机会δ，并且由于我们循环通过每个坐标（c.f.，假设2），cj（x）PBlogsK，δ哪里 代表随机优势。（81）根据假设4，沿着第j轴的每一个分裂将其长度减少至少（1）倍- α). 因为分裂是从单位超立方体开始的- α） c（x）≥ β ==> c（x）≤logβlog（1- α)=:ρ. （82）由于{I=1}要求第一个轴的长度超过β（一个常数），这证明了（I | X=X）≤ PBlogsK，δ≤ pρ. （83）由于pρ是常数，我们可以得出BlogsK，δ≤ pρ≤ (1 - δ+o（1））对数s/K=s日志1-δ+o（1）。（84）最后，由于树是二进制的，所以对数的基数是2。

因此，如果我们选择δ>1/2，指数超过1，证明就完成了。命题4的证明。最简单的情况是根节点[0,1]p中的拆分决策，因此我们从那里开始。我们通过在X=xS=arg maxifi上引入带和不带条件的分裂决策之间的耦合来证明这个结果ssXi=1m（Xi），ssXi=1mQ（Xi）=:fiS=arg maxifism（x）+sXi=2m（Xi）, . . . ,smQ（x）+sXi=2mQ（Xi）=:菲。这里是sampleX上的裂缝，X是在选择的样本条件XX上进行的拆分，因为在该事件上拆分概率非常相等。显然，s6=1的一个必要条件是存在一对1≤ i 6=j≤ P表示fi>fjbut fj>fi。（86）假设Lipschitz及其参数是次指数的，则数量F和FJ集中在各自的极限F（E m，…，E mQ）和Fj（E m，…，E mQ）周围；因此，每当fi（em，…，emq）>fj（em，…，emq）时，我们就会有fi- fj>开关概率至少为1- O（e）-cs）对于某些常数c.（87）fi/ssthe | m（x）- m（X）|/s.根据Lipschitz连续性，变元中的1/s改变函数值成比例，当- fj>/s。接下来（fi>fj，fj>fi）以概率出现在mostO（e-cs），最后我们注意到P成对（i，j）。[0，1]p的结果将被称为基本情况。注意，以上事实证明了一个更强大的东西，即对于每个分裂τ，P（s6=S | S=τ）<e-Csp（S6=s | s=τ）<e-反恐精英。（88）可以看出，对于任何τ，（X，…，Xs | S=τ）和（X，…，Xs | S=τ）之间的总变化距离最大-反恐精英。要看到这一点，请注意，sands是xionly的函数，因此这两种分布的密度分别是p（x）=1（S（x）=τ）p（x）p（S=τ）和p（x）=1（S（x）=τ）p（x）p（S=τ）（89）。

我们可以假定p（S=τ）不失一般性≥ P（S=τ），所以总的变化是z | P（x）- p（x）|=ZS=τp（x）- p（x）+ZS6=τ，S=τp（x）=1-P（S=τ，S=τ）P（S=τ）+P（S=τ，s6=τ）P（S=τ）=2p（s6=τ| S=τ）<e-反恐精英。（90）X……的分布差异，当条件onS=τ与条件onS=τ时，支付成本O（e-cs）。现在考虑下一次分裂时分裂概率的差异（S=S | S=τ）- P（S=S | S=τ，X=X）。（91）同样，策略是找到这样的耦合~ （S | S=τ）和S~ （S | S=τ，X=X）（92）TVS，S≤ E-由τ导出的s | v | v |。由于x的分布，Xsons=τ通过一个数量与其非条件分布不同-在总变化距离中，我们可以使用以下耦合=arg max finvXXi∈vm（Xi），s | v | XXi∈vmQ（Xi）S=arg max finvXXi∈vm（Xi），s | v | XXi∈vmQ（Xi）（93）式中，xi遵循（X，…，Xs）条件on=τ的分布，xi遵循τXxSτSτ，增加总变化量e-通过三角不等式。现在，剩下的证明与基本情况相同，注意到在高概率情况下，invis的点数等于| v |直到一个乘法常数（1）- η） 有可能-sη。在DAG的每一个深度递归应用前面的边界。在depthl，weincur从总变化距离中得出“近似成本”-|v | s.Sinces |v |≥ αl，l≤ 奥洛格s | v |洛洛格s | v | e-c | v | severything一起，我们已经证明了电视（p，p）≤ O（log（|v|s）·e-c | v | s）≤ os|v|1+对一些人来说 > 0.（94）命题5的证明。通过选择适当的常数，ifvis aterminal node的说法基本正确。因此，fix非终端节点v/∈ v和letX=Xv={Xi:Xi∈ v} （95）表示落在v中的一组点，因此k：- |X|∈ {1, . . .

N- 1}.回想一下，f=f（v）和f=f（v）分别是树估计器atx的期望值，当分裂序列与当前的xcontainingx子集相比较时，fbeingcomputed conditional onX=x。因此，根据概率和p，fandf是其x分布的函数。我们会证明这一点∈ {，…，n-}, （X | | X |=k，π=v）和（X | X |=k，π=v，X=X）（96）的总变化距离以（对数s）为界·（s | v |）。这将有助于约束| f- f |通过总变化距离tV（p，p）=sup | g的变化定义|≤1 | EA~pg（A）- 每个~pg（A）|。（97）自塞克斯以来/∈ v、 Xis不是x的元素，所以x和x是独立的。因为分裂∏是根据X=X时的分裂概率分布的，所以我们有dist（X | | X |=k，π=v，X=X）=dist（X | | X |=k，π=v）。（98）vlogsP≥-logss | v |稳定性假设logs多次使用并集界限。由（98）可知，（96）中分布的总变化距离由P（6=2）决定，结果如下。6号提案的穷人。其思想是根据有向无环图递归扩展公式化TandE（T | X）。我们从| et开始- E（T | X=X）|=Xvp（e）f（e）-Xvp（e）f（e）≤Xv | p（e）- p（e）| f（e）+Xvp（e）（f（e）- f（e））,（99）在第一次拆分后，总和超过节点Va，即[0,1]p→ v、 第二个夏天和五月∈ vx/∈ vfunction, 然后命题5允许我们约束第二项，这样| E T- E（T | X=X）|≤Xv | p（e）- p（e）| f（e）+Xvp（e）（f（e）- f（e））≤ （αs）+（对数s）（αs）+Xx∈副总裁（e）| f（e）- f（e）|，（100）其中使用了|v|≥ α. 现在，每项| f（e）- f（e）|可以由（αs）+log（s）（αs）+Px∈w（···）。继续这样下去，我们有| E T- E（T | X=X）|≤ 日志(（s） +p（αs）+p（αs）+…）=原木∞X`=0p`（α′s），（101）p′xx``我们假设L是x和x分开后的分裂数，然后p`=p（L）≥ `).