跳到主要内容
返回时间线
arXiv来源发表:

随机划分模型集成在协变量偏移下的理论:集成规模足够大时,Mondrian核估计可达极小极大最优收敛率

核心概要

随机划分核估计的协变量偏移理论此前只覆盖最近邻、二进树和顶帽核等单一学习器,集成模型为何更稳健缺少解释。这项工作把偏移严重程度的差异度量推广到随机划分集成,并证明在多项式密度的一类严重偏移下,单个Mondrian树对应的差异度量可以为无穷,而集成规模足够大时Mondrian核估计仍能达到极小极大最优收敛率。结论还指出,偏移越严重,所需的集成规模越大。

深度剖析

随机划分核估计的协变量偏移分析现在有了与集成规模挂钩的差异度量,集成规模成为控制风险的一个显式变量。 此前的偏移严重程度度量针对最近邻、二进树和顶帽核等单一学习器,并证明这些度量控制极小极大收敛率;随机森林这类由随机划分上的分段常数局部平均组成的集成模型没有对应的理论。 在单位立方体上目标分布均匀、源分布为多项式密度的一类偏移中,单个Mondrian树对应的积分偏移差异度量可以为无穷,而集成规模足够大的Mondrian核估计仍达到极小极大最优收敛率。

集成之所以有用,是因为它把落在测试点附近的独立训练点汇集起来,扩大了参与局部平均的样本池。 单个Mondrian树的单元格因STIT镶嵌的无记忆性而偏小,局部平均可用的训练点太少,难以抵御严重偏移。 风险上界中的偏差项随集成规模只呈对数增长,因此该界适用于中等至较大的有限集成;分析针对独立生成的STIT镶嵌,并假设划分与训练数据独立。

偏移越严重,达到极小极大最优收敛率所需的集成规模越大。 此前关于集成的经验观察只报告集成在偏移下退化更小,没有给出集成规模与偏移严重程度之间的定量关系。 在多项式密度这一类偏移上,需要足够大的集成规模才能以高概率把积分偏移差异度量压到所需水平,从而保证收敛率。

启示与展望

分析针对划分与训练数据独立、各划分独立生成的纯随机划分集成,回归函数为Hölder连续,源与目标支撑嵌套且紧致,标签噪声二阶矩有界;具体收敛率在STIT镶嵌上给出,数值示例限于一维Mondrian划分和多项式密度的一类偏移。

偏差上界随集成规模只呈对数增长,因此适用于中等至较大的有限集成,而非任意大的集成;作者指出极大集成极限对应Laplace核,但其在协变量偏移下的稳健性尚不清楚。单个Mondrian树的积分偏移差异度量可以为无穷,集成规模足够大时才能以高概率控制该度量,这一保证依赖截断处理低概率事件。