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

注意，超立方体的连续性和紧性的一个结果是，高达三阶的条件矩是有界的。我们的结果不会明确地依赖于X密度的知识：然而，密度会影响我们在整个证明中所携带的隐式常数（c.f.，引理3.2和[12]中的定理3.3]）。3多元U-统计量的高斯性3。1测试点和符号惯例我们在本节中开始研究随机森林估计器。正如模型简介中所讨论的，测试点处的随机森林估计器Rf（x）是一种统计，其中核是Rf的分布，特别是Rf（x）和Rf（\'x）在不同点Sx和\'x）之间的相关结构∈ X.为此，我们将确定一组q测试点X，xq∈ 在编写估计器时，X（13）将忽略它们的显式依赖性。因此，RF（Z，…，Zn）代表Q维估计器，即在x，…，处评估的随机森林，xq，给定观察值{Zi:1≤ 我≤ n} 。作为记法的结果，我们的大多数方程都可以在第k个测试点理解；一个值得注意的例外是，它指的是我们现在描述的哈耶克投影。3.2哈耶克预测我们首先回顾U统计量的霍夫丁分解的性质，也就是阿沙耶克预测；关于单变量病例的教科书处理，请参见[]。Letf（Z，…，Zm）∈ rqq是一种基于观测的广义维统计。哈耶克投影函数定义为f（Z，…，Zm）=mXi=1E[f（Z，…，Zm）| Zi]- （m）- 1） ef（Z，…，Zm）。（14） 也就是说，它是到由{g（Zi）：1形式的函数所跨越的线性空间的坐标投影≤ 我≤ m} 。特别是，当参数和z对称时，Zmis anIID序列，我们有f（Z。

，Zs）∈ Rq。由于第三动量（Y | X=X）被假定为有界的，LindbergCentral极限定理[]的条件很容易遵循，并且应用三角形CLT，我们得到了熟悉的事实V-1/2（RF）- u）距离====> N（0，I），（20），其中0是rqa中的零向量，I是q×q单位矩阵。评论三阶矩有界的条件是不必要的。Lindberg模型是在[24]中开发的，它们的条件也满足我们的案例。RFRF viaV的正常值-1/2（射频）-u）=V-1/2（射频）-RF）+V-1/2（RF）- u). （21）由于RHS上的第二个和是渐近正态的，根据Slutsky定理，V-1/2（射频）-u）是渐近正态的，一旦我们建立收敛V-1/2（射频）-RF）P--→0.策略是表明E=V-1/2（射频）-RF）以平方平均值收敛。我们可以发展它的平方范数（e | e）=e（RF-RF）| V-1（射频）-RF）=E tr V-1（射频）-RF（RF）-RF）|=tr V-1E（射频）-RF（RF）-RF）|=tr V-1/2Var（射频）-RF）V-1/2，（22）其中，我们使用标识符tr（ABC）=tr（BCA）来表示一致性矩阵A、B和C。极限RHS为零是熟悉的条件变量（f）的自然多元推广-Varf→ 0（23）表示单变量U-统计量[22]。在单变量设置中，通过在多变量设置中考虑更高阶的条件来检查之前的条件，如下所示。正如我们将看到的，更实质性的困难在于U统计核的维数，即每棵树的子样本大小随样本大小而增长。根据下面的命题1，我们可以扩展RF-根据H–oe有效分解，检查矩阵V-1、射频-射频=nsXi<jN- 2秒- 2.（T（2）（Zi，Zj）-u）+Xi<j<kN- 3秒- 3.（T（3）（Zi，Zj，Zk）-u) + ···, （24）其中T（2），T（3）等是服从正规方程的二阶和三阶投影- u）V-1（T（k）- u）]=0，对于k6=k。

（25）当然，作为T的投影的高阶项T（k）也满足[（T（k）- u）V-1（T（k）- u)] ≤ E[（T- u）V-1（T）- u)]. （26）这两个关系与（19）和（22）连用，表示e（e | e）≤sntr（VarT-1Var T）。（27）本节剩余部分的中心是证明RHS上的量收敛为零。为了进行比较，[]的一个中心结果（使用我们的符号）是对角元素的界。正态方程是命题1的主要内容。VarT-1和变量T。具体而言，作者获得（Var T）kk（VarT）kk≤ c（对数s）p，对于每个k=1，q、 （28）对于一些康斯坦茨。正如我们将在下一节中看到的，跟踪上所需的界限将随后发展VarT的反对角线元素的界限，即不同测试点随机森林估计值之间的协方差界限（见命题2之后的讨论）。命题1（多变量统计的H-O效应分解）。修正一个积极的定义矩阵。Letf（x，…，xn）∈ Rpbe是一个向量值函数，它的参数是对称的，Xnbe一个随机样本，使得f（X，…，Xn）具有有限的方差。然后存在函数f，f，fn使得f（X，…，Xn）=E（f）+nXi=1f（X）+Xi<jf（Xi，Xj）+···+fn（X，…，Xn）（29），其中fk是k个参数的函数，使得E fk（X，…，Xk）=0和E[fk（X，…，Xk）|Mf`（X，…，Xl。（30）证据。（所有证据见附录。）3.4协方差界本节的目的是建立theVarT的反对角线元素的渐近界。为了满足适当的稳定性条件，我们有渐近行为（VarT）k，l=o（s-) 所有人1≤ k6=l≤ q和一些 > 0

（31）在继续之前，我们首先表明，这个界限，加上对对角线项（28）的控制，有助于建立（27）中的迹界限消失。提议2。Var-Tare的项是有界的，它的对角线项是有界的，远离零。此外，当VarT满足（31）中的条件时，sntr（VarT-1Var（T）→ 0.（32）备注。命题的第一部分，关于VaR T的条目，是我们关于{Zi}的（α，k）-正则性假设和分布假设的结果。正如在假设部分中所讨论的，由于叶节点中的观测数在上面有界，树估计量atxis的（逐点）方差在上面有（一个常数倍）Var（Y | X=X）的界，我们假设Y | Xxwe呈现给boundVarT也可以用于boundVar T；事实上，（Var T）k，l→对于k6=l，尽管我们在本文中将不再进一步讨论。命题2将Tas确立为中心研究对象。回想一下，这是一棵树，而是它的哈耶克投影；换句话说，Var不是树估计的协方差矩阵。然而，我们的结果将证明渐近正态性-1（射频）-u），其中v，RFVarT（19）版本的正是对随机林进行推理所需的对象。尤其是，（28）（31）Vartrf对角占优（即倾向于极限中的对角矩阵）。我们可能总是重新标记索引，这样树就可以在观测点上生长，Zs。要确定界限32，从定义T开始- u=sXi=1E（T | Zi），因此由于独立性，VarT=s Var（E（T | Z））。（33）为了在RHS上发展术语，使用条件期望Var E（T | Z）=Var[E（T | Z）的正交条件- E（T | X）]+Var[E（T | X）]。

（34）由于树算法是诚实的，差异（T | Z）- E（T | X）简单化，因此对于每个≤ K≤ q、 E（Tk|Z）- E（Tk | X）=E（Ik | X）（Y- E（Y | Ik=1，X）），（35）其中tk是树的估计值atxk，以及X和xk是否延伸到样本节点的指示符。因此，在Var[E（T | Z）的（k，l）处的o fff-对角线输入- E（T | X）]等于E（Ik | X）E（Il | X）（Y- E（Y | X，Ik=1）（Y- E（Y | X，Il=1）]。（36）如果我们展开被积函数中的项，对于某些次数最多为两次的多项式，每个项的形状（Ik | X）E（Il | X）·p（Y，E（Y | X，Ik=1），E（Y | X，Il=1））（37）。由于我们假设E（Y | X=X）和E（Y | X=X）是连续的，因此是有界的，所以E（p | X=X）也是有界的。然后，使用迭代期望定律来计算（36），结果表明它是由一个常数timesE[E（Ik | X）E（Ij | X）]限定的。（38）备注。直接应用Cauchy-Schwarz不等式，仅使用E（Y | X=X）有界的事实，将产生较弱的界[E（Ik | X）E（Ij | X）]≤qE[E（Ik | X）E（Ij | X）]（39）直到一个乘法常数。回想一下，Ikandilar指标变量分别表示Xbelong是否与Xkandxl属于同一个超立方体。因此，E（Ik | X）是第一次观测用于预测atxk的概率，同样也是前（Il | X）。直观地说，这种情况只发生在xisNearxk（分别是xl）的时候：因为xk=xl，xc不能同时靠近两者，这意味着产品（Ik | X）E（Il | X）很小。提议3。对于两个点x和¨x∈ X=[0,1]p，定义（X，\'X）=E[E（I|X）E（\'I|X）]，（40）I|X|xIfδ>1/2和X 6=\'X，M（X，\'X）=o（s-(1+)) 对一些人来说 > 0.（41）备注。在前面的显示VSUSM（x，x）中考虑边界是有指导意义的。从定义中可以清楚地看出，M（x，x）≥ M（x，\'x）表示所有的\'x。此外，M（x，x）=E（E（I | x））≤E（E（I | X））=E（I）。根据对称性，EI=1/s（直到常数），因为在X的终端节点有大量的观测。

因此，这个命题所能保证的就是当nx 6=`x时，数量M（x，`x）小于“平凡”界1/s。这个命题表明var[E（T | Z）的贡献- E（T | X）]var E（T | Z）的互协方差很小，特别是小于所需的界（logps·s）-1.δ>/2的要求虽然需要证明，但在实践中几乎肯定不需要。原因是我们的证明使用δ>/2推导出量子化（Ik | X）E（Il | X），（42）上的一致界，而命题要求其期望上的界。事实上，在极端情况下，x=0和¨x=（1，…，1）|，很容易看出，即使δ≤/2.此外，我们的证明与基本树学习所使用的精确分裂规则无关，并且在推导所需的边界时仅使用“随机分裂”（c.f.，假设2）。根据特定的分配规则（例如，（8））和特定的数据分布，预期M（x，`x）将比（41）预测的小。有鉴于此，我们的循环分裂假设的另一种选择是toboundM（x，\'\'x）=ologps·s. （43）3.4.1定界变量E（T | X）我们接下来讨论定界对角项因瓦[E（T | X）]。如命题3中所述，稍微更改符号是很方便的。我们有一个≤ k6=l≤ q、 并使用符号X 7→ xk，`x7→ xl，x等于x的值。本节的目标是建立边界向量[E（T | X）]kl=E（E（T | X=X）- u）（E（\'T|X=X）- \'（u））=ologpss. （44）其中，树的估计值为x和x，u和u是对T和T的（无条件）期望值。

（请注意，我们还对符号进行了轻微更改；之前，它是所有点估计的Q维度向量；对于本节，它是x=xk时的逐点估计。）数量e（T | X=X）-u=E（T | X=X）-E（T）测量单个观测点X的位置为树atx的输出所携带的“信息”的程度。直观地说，当X接近X时，X对包含X的叶节的影响更明显，我们预期（T | X=X）- u ≈ E（Y | X=X）- u. 相反，当x远离x时，其对包含x的叶节位置的影响减小，e（T | x=x）- u ≈ 0.使上述直觉精确的关键是跟踪X=X保留包含X的中间分区，其中“中间分区”指的是创建的DXX分离的节点，其对预测的影响降低。为此，fi xxx和∏表示包含x的终端节点；π是由轴对齐分裂产生的

因此，π只具有无穷多个可能值，我们可以写出（T）=XπP（π=π）π和E（T | X=X）=XπP（π=π| X=X）π（45），其中π=E（T |π=π）和π=E（T |π=π，X=X）。超矩形∏由用于生长树的递归分裂程序确定，并且（45）和在[0,1]p处进行的每一潜在分裂之间存在自然对应关系，有一条指向新顶点的有向边，其中顶点是X∏，那么该顶点是DAG中的一片叶子，没有输出边；对于该节点上的每个潜在拆分，其他顶点都有一个扩展边，每个边都指向另一个顶点，该顶点又是一个包含x的超矩形。之前的定义递归地确定DAG：DAG中的每个顶点都是一个包含x的节点，终端顶点对应于终端节点。对于每个端子顶点，我们关联值F（v）：- π如（45）所示。此外，每个边=（v→ w） 对应于节点v处产生v的半空间w的拆分；与此边关联的“转移概率”p（e）：- P（s）选择在v |当前节点为v）=：P（w | v）。（46）FVf公式（v）：-Xe:v→wP（w | v）f（w）。（47）我们称f为v处的延拓值，通过构造我们得到e（T）=f（“根”）=f（[0，1]p）。（48）或者，如果我们将值SF（v）=uv分配给每个终端顶点，并使用过渡概率P（e）=P（s在v处选择，当前节点为v，X=X）=P（w | v），（49），那么我们在以与f相同的方式扩展后恢复（T | X=X）=f（[0,1]P）。在otherET | Xx中- ETcontinuation值。我们需要假设p（e）≈ p（e）；也就是说，对单个观察的条件作用将不会发生变化（节点）。

这是一个自然的假设，因为最佳分割是使用特定节点中的所有观测值来计算的，因此对单个观测值的条件作用应该相对较小。这将取决于用于构造树的拆分算法的具体情况，以及满足以下假设的规则，即“稳定拆分规则”假设（分裂稳定性）。对于任何nodev，分布{p（e）}e:v之间的总变化距离→wand{p（e）}e:v→wis以V的体积为界。具体来说，确实存在 > 0，使所有v，TV（p，p）≤s|v|1+（达到常数）。（50）这里，|v |表示v处超矩形的体积，即|v |=pYj=1（aj，bj）=pYj=1 | bj- aj |。（51）备注。Sincepandpare离散概率分布：因此，如果pandpare写为概率质量的向量，那么总变异距离就是两个向量之间的形式。Xbound表明，样本点的数量invis在bys | v |的上方和下方有界，而/s是所需的界（logps·s）-1.我们可以将（50）中的| v |解释为|v |中的样本数，而不丧失一般性。与此相关的是，[]的引理12（另见[]中引理2的证明）扩展到了这一事实，即在节点之间是一致的。稳定性假设对用于选择最优分割的程序进行了限制：即，如果决策基于多个点，则对任意一个点进行条件调整，以m为界的概率改变最优分割-(1+). 在实践中，大多数拆分过程都满足一个更强的界限。下面的命题给出了一组充分条件。提议4。假设根据数量f（u，…，uQ），…，选择节点v处的最佳分割，fP（u，…，uQ）（52）对于某些Q≥ 1，其中。

，uQare被分割点的样本平均值uk=nvXi:Xi∈vmk（Xi）（53），其中总和超过v中的点，nv表示这些点的数量。具体来说，假设最优分割是基于哪个分割得到最大值，即arg maxifi（u）值来决定的。Iff，fPare Lipschitz和functionsm，如果Mk（X）为1次指数，则满足分裂稳定性假设。由于Xiare有界，Mk（X）是次指数的要求允许使用（8）来计算最优分割。一般来说，命题4中的条件足以保证指数有界，而不是（50）中的多项式有界。因此，命题4应该被简单地视为提供了一个似是而非的论点，即在实践中通常会遇到稳定的分割规则。下一个命题表明，分裂概率的界自动意味着延拓值的相关界。提议5。假设分裂概率满足一般界（·）在那个电视里（p，p）≤（s | v |）log sat每个节点v.（54）例如，（z） =z-(1+). 对于任何包含x但不包含x的节点v，|f（v）- f（v）|≤ C（s | v |）（55）对于不依赖于v的常数C。例如，二项随机变量b（n，p）偏离np超过√对于某些常数C，n小于C/sfo。分裂稳定性假设规定：（z） =z-(1+), 因素在哪里允许我们忽略额外的对数。在这种情况下，我们可以把界设为v（p，p）和| f- f |在变量E（T | X）上建立所需的界限。提议6。假设分裂规则是稳定的，如（50）所示，δ>-α. Forx 6=x，| E（T | x=x）- E（T）|=os1+（56）对一些人来说 >0.特别是，Var E（T | X）的反对角线条目是-(1+)) 至少x和‘x的音调与x不同。δ>/α</那δ>- 命题6中的α更具限制性。