提出高效稳定的多维K-S距离计算方法，支持精确假设检验。
Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance
- 基于正交矩形区域最大化差异，定义新多维K-S距离
- 样本量增大时距离收敛至0，4维内可近线性时间计算
- 适用于高维数据的双样本检验，优于现有其他变体
我们重新审视将概率分布间的Kolmogorov-Smirnov距离推广到多维情形的方法，提出一种新形式：在正交支配矩形区域（R^d中的d面矩形）上最大化差异，该距离为积分概率度量。证明了分布与其样本间的距离随样本量增长趋于0，并给出了收敛速率边界。进一步表明，在4个或更少维度下，可近似线性时间计算该距离，且误差可控。据此构建了具有delta精度的双样本假设检验。最后，证明其他常见变体不满足这些性质。
原文摘要 · Abstract (English)
We revisit extending the Kolmogorov-Smirnov distance between probability distributions to the multi-dimensional setting, and make new arguments about the proper way to approach this generalization. Our proposed formulation maximizes the difference over orthogonal dominating rectangular ranges (d-sided rectangles in R^d), and is an integral probability metric. We also prove that the distance between a distribution and a sample from the distribution converges to 0 as the sample size grows, and bound this rate. Moreover, we show that one can, up to this same approximation error, compute the distance efficiently in 4 or fewer dimensions; specifically, the runtime is near-linear in the size of the sample needed for that error. With this, we derive a delta-precision two-sample hypothesis test using this distance. Finally, we show these metrics and approximation properties do not hold for other popular variants.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。