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

2022-4-26 12:08:13

多元随机森林估计器的渐近正态性Technologykkli@mit.edu*2020年12月16日抽象分析。Athey和Wager最近的一篇论文表明，逐点随机森林估计是交感高斯的。在本文中，我们将他们的结果推广到多元情况，并证明在多个点上的估计向量是联合渐近正态的。具体来说，极限正态分布的协方差矩阵是对角的，因此在足够深的树中，任意两点的估计都是独立的。我们证明了o-对角项由与两个给定点属于结果树的同一片叶子的概率有关的量所限定。我们的结果依赖于基础树估计的某些稳定性，并且我们给出了一些分裂规则的例子。我们还提供了一个启发式和数值模拟来测量有限样本中的反对角线项的衰减。1简介树和随机森林是Breiman[]首次引入的非参数估计。Givena feature spaceX Rp和一组数据点{（Xi，Yi）} X×R，树估计器通过沿给定轴重复拆分X，将特征空间递归地划分为轴对齐的不重叠超矩形。树估计在测试点X的预测∈ 然后是一个包含X的超矩形中着陆的目标的集合；如果是连续的，则聚合为样本平均值，该树也称为回归树。树估计器的深度定义为到达终端超矩形前的最大分裂数，控制树估计器的复杂性。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:08:19

有两种常用的方法来控制复杂性：“boosting”方法生长深度较大的树，然后通过修剪树（即，在非末端超矩形处进行预测）或引入decayfactor来降低复杂性；取而代之的是“套袋”方法在数据的不同子集上生长一组浅树，并对这些树进行平均，以进行最终预测。装袋的直觉是，生长在不同亚群上的树并不是完全相关的，因此聚集减少了变异和变异*我要感谢我的顾问阿尔贝托·阿巴迪和维克托·切尔诺朱科夫审阅了本文的多份草稿。此外，Sophie（Liyang）Sun、Ben Deaner、14.386班（2020年春季）研讨会的参与者以及麻省理工学院计量经济学午餐研讨会的参与者提供了非常有用的反馈。我还要感谢Stefan Wager教授帮助我理解随机森林模型中协方差估计的机制。当特征空间X不需要是矩形时，可以将X放大到一个矩形集合X，该集合定义为包含X的所有矩形集合的交点。arXiv:2012.03486v3[econ.EM]2021年1月30日平衡偏差-方差权衡。这种类型的估计器被称为随机森林，它们是本文的重点。自21世纪初引入随机森林以来，由于与竞争模型相比具有多种实用优势，随机森林已成为应用数据分析中越来越重要的工具。首先，高质量的随机林库随时可用，流行的实现可扩展到数百个分布式工作者[，]。此外，树估计器和随机林背后的核心算法足够简单，可以快速原型化定制实现，估计器不受特征异常值的影响，丢失的数据可能很容易合并。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:08:25

首先，它们的结构自然地与大多数应用程序的空间位置一致：也就是说，与轴相关的潜在目标函数是连续的。最后，树模型是可解释的，具有明确的特征重要性概念[6,7]，支持将其用作模型选择工具[8]。影响。在鲁宾的潜在结果框架[]中（见[]以了解概述），根据Whetheria接受治疗的情况，个体（0）Y（1）。统计员可以访问IID观测{Xi，Wi，Yi≤ 我≤ n} 谢维∈ {，}YiY（Wi）iinterest是xτ（x）处的治疗效果：- E（Y（1）- Y（0）|Xi=x）。（1） Y（0）iY（1）iτx假设。一个常见的假设是无依据性，即治疗状态取决于Y（1）和Y（0）是否取决于Xi。在这个假设下，τ（x）=E易Wie（x）-1.- Wi1- e（x）| Xi=x, 其中e（x）=P（Wi=1 | Xi=x）。（2）在这里，关键函数ise（x）被称为倾向评分，是协变量亚群治疗的概率x；参见[]推导和含义。机器学习更重要的是，无依据性还意味着τ（x）=E（Y | W=1，x=x）- E（Y | W=0，X=X），（3），因此可以通过拟合两个模型来估计τ（X），一个是在W=1的样本子集上，另一个是在W=0上。有序的分类特征。外汇→ R（例如，为了测试零假设：f（x）=0）需要了解基本估计量^f（x）的收敛率或渐近分布，其中x是感兴趣的点。然而，目标函数的泛函通常也是令人感兴趣的：例如，两个不同亚群的处理效果（即f=τ）的差异由数量f（x）表示- f（\'x），（4）x'xin与加权处理效应有关，其中一个亚群xis被赋予一个重要权重，建模为密度u（x）。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:08:32

在这种情况下，f的相应函数为∈Xf（x）du，其中u不一定是x（5）的密度，并且积分在域x.ff（x）上，而且是不同点的估计值sf（x）和f（`x）之间的相关性。作为一个具体例子，考虑函数τ（x）和简单差τ（x）- τ（`x）。我们有τ（x）- τ（x）=[E（Y | W=1，x=x）- E（Y | W=1，X=\'X）]- [E（Y | W=0，X=X）- E（Y | W=0，X=\'X）]=:A- B.（6）Ab如上所述，wi=1和wi=0的数据集的两个“一半”。因此，估算值^A和^b是独立的，因此VaR（^A-^B）=Var^A+Var^B。然后，方差^A和^B取决于它们各自在x和^x处的随机森林估计的协方差。本文研究了一类随机森林模型的相关结构，其渐近分布在[]中首次得到。我们找到了充分的条件，在此条件下，不同点的随机森林估计的渐近协方差相对于各自的方差消失；此外，我们还提供了基于计算的有限样本启发法。据我们所知，这是关于随机森林估计器相关结构的第一组结果。本文基于并扩展了[]中的结果，后者又基于Related，后者通过结合矩条件的知识，将本文考虑的随机森林模型扩展到更广泛的目标函数类。本文建立的稳定性结果已出现在[]，他们研究了随机森林和逻辑回归的算法稳定性概念，并得出了推广误差保证。与本文密切相关的还有[]和【】在这种背景下，我们的论文为将有限样本统计理论应用于随机森林提供了一个垫脚石，其中协方差矩阵的边界起着核心作用。本文的结构如下。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:08:40

在第2节中，我们介绍了随机森林模型，并陈述了我们的结果所需的假设；第三部分是我们的主要理论贡献；第4节以第3节为基础，讨论了在有限样本设置中有用的启发式方法；第5节总结。所有证据见附录。2模型设置和假设2。1.树估计概述本文的目的是研究随机森林估计的渐近高斯逼近。自始至终，我们假设一个随机样本{Zi=（Xi，Yi）：1≤ 我≤ n} 给定X×Ris，其中每个xi是属于子集X的特征或协变量的向量 p-dimensionalYi的Rpof∈ rxix特征空间或特征域。给定数据集{Zi}ni=1，树估计器通过进行轴对齐拆分递归地划分特征空间。具体来说，轴对齐的拆分是一对（j，t），其中j∈ {，…，p}是分裂坐标，t∈ Ris分裂指数；给定一个子集十、分裂（j，t）分成左右两半{X∈ R:xj<t}和{x∈ R:xj>t}，（7）xjjxX{Zi≤ 我≤ n} 例如，当目标为连续时，常用的选择是（j，t）=arg minj，~tXi:Xi∈L（易）- uL）+Xi:Xi∈R（易）- uR）（8）式中，L=L（~j，~t）和R=R（~j，~t）是由分割（~j，~t）得到的X的两半，其中uLanduR分别是对应特征Land inLandR的targets的平均值。xlrlr分别指通过使用满足特征sillcriterion的数据子集计算的分割forLis。当每个节点满足停止标准时，该过程完成；在它之前是一个超矩形与X的交点。这个序列以自然的方式响应一棵树；我们将在拆分过程中出现的半空间称为节点，以及最终分区终端节点的元素。根据（7），我们排除了点位于矩形“边”上的边情况。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

点击查看更多内容…

2022-4-26 12:08:53

，n}，内部期望用ξs<nasuming thats表示~ nβ对于某些β非常接近于1；具体地说，我们假设自始至终选择子样本大小是为了满足[]定理3的假设，因此目标函数x7的估计量→ E（Y | X=X）（见上文讨论）。为了与符号[]保持一致，我们将编写（x；Z，…，Zs）来表示（x；ξ，Z，…，Zs）对ξ的期望。有了这个符号，随机森林（atx）估计器（10）是带有大小核（Z，…，Zs）7的统计估计→ T（x，Z，…，Zs）。我们将在第3.2.3节模型假设的讨论中更详细地讨论RF的U统计表示。由于我们的结果将是[]中结果的延伸，我们将研究相同的随机森林模型，并采用一组类似的假设。关于树估计量的假设是有标准的（例如，参见[18]中的第7章和第9章）。第一个也是最定制的假设是，树算法是诚实的。直觉上，honestytree会在功能固定时进行估计。假设1。i分裂指数）独立于Xi。具体地说，我们需要使用（Yi | Xi，S）=dist（Yi | Xi），（11）iyis树算法。（由于独立观察，第二个等式是自动的。）有几种方法可以满足这个假设。第一种方法是仅根据特征计算分割。这排除了（8）中给出的示例拆分规则，因此我们可以使用其在特征空间（j，t）=arg minj，~tXi:Xi中的模拟∈LkXi- uLk+Xi:Xi∈RkXi- uRk，（12）其中uLanduRd表示每个半空间中xi的平均值（即质心）。在这种情况下，分割的选择本质上是一种聚类算法，它可以找到最佳分割。基于目标的计算分割是使用样本分割。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:08:59

数据被划分为两部分SIANDI；印度和印度的观察∈ Imay可以在拆分过程中自由使用，而Yi∈ i用于确定终端节点值。在这种情况下，需要（11）中的等式∈ 我{Wi}。在分裂阶段（“模型拟合”），分裂的计算就好像响应变量是WI；例如，（8）用uLandurb表示{Wi}的平均值。一旦树长满，预测（“模型推理”）就会像往常一样使用Yi的预测。在时间序列预测中，使用这种追踪目标的做法尤其流行，在拟合和推断步骤中使用不同的视界（c.f.，[21]）。xit术语“推断”用于表示计算现有模型的预测，这与描述数据管道无关：参见[19,20]的文档。扩展到所有三个方案。我们的下一个假设将确保每一个轴都被选为分裂坐标，其概率从下到下是有界的。假设2。δ头，选择第一个坐标作为分割坐标；第二次，选择第二个坐标，以此类推，第J次硬币落地时，（p mod J）+第1个坐标基于观察结果。这是对[]中随机分裂假设的修正，其中在[]中研究并由[]等流行库实现的每个轴δpδpAnother方法都使用随机化每轮中可用分裂轴的数量。具体来说，泊松随机变量Q的强度与√首次实现的合格中介机构（每轮独立实现的合格中介机构）。然后，统一选择min（Q，p）多个轴作为该轮分裂的潜在候选轴。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:09:07

显然，这也导致了每个协调1被选择的概率的下限≤ J≤ p、上述两种方法中的每一种都涉及两轮独立的随机化：第一轮是随机化，第二轮是确定分裂轴。直观地说，我们的循环分裂假设被简化了。重要的是，方差只取决于δ，而不取决于onp，我们将在证明中利用onp。假设3α，kα∈,/mαmthan 2k- 部分k得1分。该关键假设从[]继承而来，包含两个要求。第一个要求是，任何分割都不会产生包含太少观测值的半空间，即当通过观测值计数进行测量时，两个半空间都较大。如[]所示，这意味着在互补概率指数小的情况下，分裂轴收缩了一个介于α和1之间的因子- α、所以这两个半空间在欧几里得体积上也很大（概率很高）。假设的后半部分对观测值的区间节点数设定了上限。在这种假设下生长的树必然会更深，因为[12]中的样本大小，在我们的边界中出现的常数可能会在方案2中发生变化。我们采用mJ mod J=0的约定，因此表示为（p mod J）加1。如果Q=0，该节点的拆分将停止。（因此，子样本大小=nβ）增加。特别是，叶节点处的预测平均观测值将是有限个项的平均值。一个重要的结果是，树估计的方差（在任何测试点X）有界于（c.f.，Var的分布假设（Y | X=X））。假设4（预先确定的分割）。每个节点上考虑的候选拆分不依赖于数据{Zi}，因此它们会提前确定。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:09:14

此外，每个节点上的候选拆分数量是有限的，每个候选拆分都会将其拆分轴的长度缩短至mosta因子α。预先确定的拆分假设适用于我们的论文。考虑到每个节点都是数据独立的候选拆分“几乎”没有失去通用性，因为特征空间是固定的。例如，随机林的实现通常使用32位浮点数作为其拆分索引，因此该假设自动满足。此外，我们注意到，该假设允许候选拆分依赖于节点，因此拆分过程仍然是数据驱动的，因为通向节点的拆分序列依赖于观察结果。所有特征都是连续的，且x=[0,1]p，所有候选拆分的形式（j，k/m）为某些整数1≤ J≤ pand 0≤ k<m，其中m≥1是一个固定整数。如果一个分裂规则（8）{bmXijc≤ 我≤ N≤ J≤ p} 而不是{Xij}。前一个集合的每个成员都是{，…，m中的整数-}因此可以用MBits来表示。特别是，对于2=256的网格分辨率，即使是iXibyte，也要有一个精细的网格。由于现代CPU和图形处理器以四或八字节存储浮点数，这允许大幅减少，允许计算能力扩展到更大的数据集。以这种方式进行编码的过程被称为量化，这是一个受支持的选项。乍一看，这似乎是限制性的，它使我们的模型与实践更紧密地一致。假设5（关于（X，Y）的DGP的分布假设）。该特性在单位立方上得到了支持，=[0,1]p密度远离零且不完整。此外，函数X7→ E（Y | X=X），x7→ E（Y | X=X）和X 7→ E（Y | X=X）是统一的| Xxi。e、，infx∈XVar（Y | X=X）>0。连续性和方差界假设是标准的。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:09:20

注意，超立方体的连续性和紧性的一个结果是，高达三阶的条件矩是有界的。我们的结果不会明确地依赖于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。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:09:31

，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。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

能者818

2022-4-26 12:09:39

（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

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:09:45

（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）]。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:09:51

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:09:58

因此，这个命题所能保证的就是当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的（无条件）期望值。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:10:04

（请注意，我们还对符号进行了轻微更改；之前，它是所有点估计的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的终端节点；π是由轴对齐分裂产生的

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:10:10

因此，π只具有无穷多个可能值，我们可以写出（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）；也就是说，对单个观察的条件作用将不会发生变化（节点）。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:10:16

这是一个自然的假设，因为最佳分割是使用特定节点中的所有观测值来计算的，因此对单个观测值的条件作用应该相对较小。这将取决于用于构造树的拆分算法的具体情况，以及满足以下假设的规则，即“稳定拆分规则”假设（分裂稳定性）。对于任何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，其中。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

大多数88

2022-4-26 12:10:23

，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中的α更具限制性。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:10:29

就像命题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）等量，这在很大程度上取决于基本分裂算法的精确机制。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:10:35

自从我们的部门。首先，命题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之间的对称性，我们可以从纯粹的几何考虑来限制相关性。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:10:43

由于被积函数（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分布在单位平方上。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

大多数88

2022-4-26 12:10:49

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以对数标度绘制了相关性，这表明相关性在单位附近呈指数衰减。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:10:55

换言之，模拟表明，正确的启发式是这样的形状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），它（粗略地）捕获了属于同一终端节点的两点的可能性，作为控制多元随机森林协方差矩阵的反对角项的关键量。通过这种方式，本文为在特征空间的多个点上对目标函数进行推理提供了理论基础。具体而言，我们表明协方差是有限样本。最后，我们讨论了未来研究的几个途径。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

能者818

2022-4-26 12:11:01

第一个是扩展我们的框架，以涵盖分类或离散值特征。在这里，需要新的假设来保证节点大小“不太小”第二，我们对随机森林协方差矩阵的潜在改进后的边界可与[，]的重新集中结果一起使用，以提供有限样本高斯近似。这将为我们的启发法提供理论基础，并增加本文对实践者的有用性。命题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）二,~好吧。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:11:07

（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。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:11:13

因此，如果我们选择δ>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）。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-26 12:11:20

我们可以假定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, . . .

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝