今天为大家分享的是由北京师范大学统计学院赵俊龙等人于2024年发表在Annals of Statistics 的文章《Approximation Error from Discretizations and Its Applications》（作者:赵俊龙，刘秀敏,  杜斌和Yufeng Liu）。文章研究随机变量离散化的逼近误差，比较不同离散化方法的近似误差，考虑了几个重要的场景来说明结果的实用性。

1 引言

通过将连续变量的范围进行划分，将连续变量离散化为离散变量是统计学和机器学习中常用的技术。 离散化可以产生更稳健的估计量并简化估计过程，提高计算效率[2]。 由于这些优点，离散化已广泛应用于许多领域，包括但不限于降维、分类以及回归问题[4, 7, 6, 3, 9, etc.]。 尽管文献已有众多的离散化算法，但从理论上讲，离散化的作用尚未完全理解。具体而言，离散化会导致偏差（或近似误差），准确描述偏差有助于更好地理解这些方法。关于这个问题，现有文献通常侧重于特定算法，例如随机森林[5, 8, 1]。在一般框架中分析偏差具有挑战性，因为偏差通常取决于所考虑的问题以及选择分割点的方式。

在本文中，我们开发了一个统一的框架来分析适用于不同算法的偏差，而不是只关注特定算法。结果表明近似误差由两个因素控制：使用和未使用离散化所导出的两个特定分布之间的距离，以及所涉及函数的光滑度。基于上述结果，本文（1）研究了单变量和多变量离散化误差，以及切片逆回归（SIR） 的矩阵近似误差。进而提出了一种适用于 SIR 的自适应响应离散化算法；（2）考虑基于协变量离散化的估计量的非参数回归，针对不同类别的回归函数，推导出均方误差（MSE）的收敛速度；（3）将经典随机森林（RF）与响应的部分离散化相结合，提出了一种改进的随机森林算法。

2 离散化近似误差

为给出离散化近似误差的一般形式，我们以一个回归模型为例进行说明。考虑回归模型，其中 和 都是连续变量， 与 无关，满足 和 。 当维度 中等或较大时，估计 并不容易，而一些现有的使用离散化的方法（例如基于树的算法）由于其良好的性能而广受欢迎。用 表示 的离散版本， 是 的离散版本。近似误差的一个常用度量是 。另一个有用的度量是平方和之差：

受上述例子的启发，我们首先讨论单变量离散化的近似误差，即 和 的误差（即 ，其中 ）。注意到， 和 可以写成统一的形式，如下所示。 令是两个随机变量，可以是连续或离散变量，满足 ；令 是连续变量。 定义。假定，对于离散化方法， 是一个随机区间，其中端点表示为 ， 不依赖于 。假设 有一个分布，其 c.d.f. 表示为 。对于不同的离散化方法，分布不同。令, 其中期望取自 且。 那么离散化近似误差可以表示为。

令 , ; 。 假设导数 存在且连续，在一定条件下近似误差有上界：

注意到当 接近阶梯函数时，接近零，离散化可以有良好的性能。 因此，我们还将结论扩展到了 在某些区间为常数或近似常数的情况，给出改进的近似误差界。 考虑到监督算法可以利用响应信息来自适应地选择的切割点，即在较小的区间内切割较少，而在较大的区间内切割较多。基于此，为了降低EP-方法的偏差，我们提出自适应EP-（AEP）切片方法，其近似误差阶数为 ，其中当函数越接近阶梯函数， 越接近零。

我们进一步将结果推广到多变量情况。多变量离散化的问题更具挑战性，通常是难以得到简洁的结果，这取决于预测变量的相依性结构和用于选择分割点的特定算法（一般情形下公式比较复杂，这里略去）。本文在某些条件下，可以得到简洁的结果。例如，当使用 EP- 切片时，近似误差的上界为 ，揭示了维度 的影响。与单变量情况类似，我们还推导出一些函数类的下界，显示了我们上界的紧性。进一步，我们研究了矩阵情形，得到了相应的误差界。 设 , 其中。令是的离散化版本，  ，则对 满足  ,有

3 应用

为了进一步说明理论结果的实用性，我们将本文结果应用于回归中几个有趣的问题：

（1）我们研究了使用离散化估计量的回归平方和 (RSS) 估计，对 给出了其渐近性质, 证明了：当    ，且 满足     和 ,      ，当时，收敛速度由偏差决定，具有阶数。 此外，根据 的结果，可以得到切片数 对 SIR 中矩阵 的误差影响的结果。基于该结果，我们提出了一种适用于 SIR 的自适应响应离散化算法以及切片数目选择方法，比如 阶数可以取为。

（2）我们研究了基于离散化估计量的非参数回归问题。当回归函数属于 H"older 类 且 时，得到的结果与文献中现有的结果相同。当回归函数接近阶梯函数时，我们得到了改进的收敛速度，证实了离散化在这种情况下的优势。

（3）我们通过将响应的部分离散化与随机森林相结合，提出了一种新的回归问题算法。模拟结果表明，新算法可以显著改善随机森林。

由于篇幅限制，这里我们以结果（3）为例展示理论结果的应用，其他结果见论文。我们利用了AEP 离散化思想，提出了以下用于回归问题的算法。 作为示例，我们考虑模型 ，其中 ，， 独立于 ，均值为零，方差为 。为简单起见，我们假设 。 使用离散化的理想情况是 是阶梯函数，即对于某个较小的 ，其中 构成 范围的不相交分割， 是不同的常数。 观察到 服从 个正态分布的混合分布，，即 ， 。 用 表示 的 观测， 那么 响应变量观测 之间存在组效应，我们可以对其聚类并估计聚类均值 。如果 估计得很好，则用估计的聚类均值 替换响应将降低回归分析中估计的误差。 因为连续函数可以用分段常数函数来近似，这个想法适用于一般的连续函数，促使我们提出如下响应的部分离散化方法。

我们应用聚类算法将 分成 个组 。用 分别表示 中 的样本均值和样本标准差， 表示包含 中响应的最小区间，。 %正确识别的类应该具有相对较小的样本方差（其中，上例中的总体版本为 ），而混合在一起且难以清楚分割的类应该具有较大的样本方差。 将 的值排序。 表示前 个具有较小的样本方差的区间（），其对应回归函数的值被认为是常数，可以通过 来 估计。 定义离散化响应： 如果 且其中 ，则令 ；否则 。 从而我们得到调整后的样本 。 这里是一个调整参数，控制偏差和方差的平衡，可以通过验证集进行选择。 基于调整后的样本，我们提出对调整后的样本应用基于树的算法，如算法1所示。基于树的算法将预测变量离散化，而算法 1 对预测变量和响应都使用离散化。 对响应进行部分离散化能够减少对回归函数在近似常数的区域进行分割，从而减少估计函数的方差。

我们通过模拟来说明算法 1 的有效性。当算法 1 的步骤 3 中应用经典的随机森林(RF)时，将该算法命名为响应离散化辅助随机森林 (RDRF)。假设 是 来自以下模型的观测其中，，，  来自 ，且 ，其中 是常数，使得 。

在以下模拟中，我们比较RF 和 RDRF。对于 ，我们设置训练数据 样本量为 ; 验证集样本量为，其中 ; 测试数据 样本量为。 对于RF 算法，我们使用 作为训练集来拟合回归函数并计算 上的测试误差。对于 RDRF，给定训练数据 和验证数据 ，我们实现算法 1 来构建估计量并计算 上的测试误差。 模拟结果总结为三个方面：预测误差、树数量的影响和计算成本，其中对每个设置重复该过程 200 次以报告平均值。

我们报告了 RDRF 测试误差相对于 RF 的改进率，定义为 )/，其中 E 和 E 分别表示 RF 和 RDRF 的测试误差。显然， 意味着 RDRF 优于 RF，而 表示 RF 优于 RDRF。 RF 和 RDRF 中的树数取 。模拟结果如图1所示。可以看出，当较小（例如）时，RDRF总是优于RF。然而，当时，RDRF可能比RF更差，特别是当很大时。这是可以理解的，可能有两个原因：（1）RDRF的训练集只有大小，而RF的训练集大小为；（2）随着的增加，RF的误差减小，改进率变小。

为了考察当RF中的树数量很大时RDRF是否仍然有优势，我们在RF中设置，对RDRF取和。模拟结果如图2所示，虚线表示 RDRF 的结果。可以看出，RF 的预测误差随着 的增加而趋于稳定，但比 RDRF 的预测误差要大。

4 结论

本文研究了离散化的近似误差，结果表明，近似误差取决于两个因素：有无离散化导出的两个分布之间的距离以及所研究函数的平滑度。此外，对于在某些区域为常数的函数，自适应切片方法可获得改进的结果。 最后，我们考虑了三个重要的应用，研究了 SIR 中切片数选择的影响，建立了非参数回归问题中离散化估计量的 MSE，并提出了一种改进的随机森林版本。 理论结果和模拟证实了使用离散化的作用。

References

[1] Susan Athey, Julie Tibshirani, and Stefan Wager. Generalized random forests. The Annals of Statistics, 47(2):1148–1178, 2019.

[2] S. Carc´ıa, J. Luengo, J.A. S´aez, V. L´opez, and F. Herrera. A survey of discretization techniques: taxonomy and empirical analysis in supervised learning. IEEE Transactions on Knowledge and Data Engineering, 25(4):734–750, 2013.

[3] B. Jiang, C. Ye, and J.S. Liu. Nonparametric k-sample tests via dynamic slicing. Journal of the American Statistical Association, 110(510):642–653, 2015.

[4] K.-C. Li. Sliced inverse regression for dimension reduction. Journal of the American Statistical Association, 86(414):316–327, 1991.

[5] Yi Lin and Yongho Jeon. Random forests and adaptive nearest neighbors. Publications of the American Statal Association, 101(474):578–590, 2006.

[6] H. Liu, F. Hussain, C. Lim, and M. Dash. Discretization: an enabling technique. Data Mining and Knowledge Discovery, 6(4):393–423, 2002.

[7] H. Liu and R. Setiono. Feature selection and discretization. IEEE Transactios on Knowledge and Data Engineering, 9:1– 4, 1997.

[8] Erwan Scornet. Random forests and kernel methods. IEEE Transactions on Information Theory, 62(3):1485–1500, 2016.

[9] Y. Sheena. Estimation of a continuous distribution on the real line by discretization methods. Metrika, 82:339–360, 2019.