机器学习方法解决信息论中多年开放问题？基于核方法的渐进最优单样本和双样本检验_华为云大赛技术圈

华为诺亚方舟实验室网络大脑和因果研究团队基于在机器学习和信息论研究方面的积累，利用核均值嵌入方法（kernel mean embedding）和大偏差理论中的Sanov’s定理，第一次从理论上证明了在非有限样本空间上的单样本检验的全局最优性质，（基本）解决了信息论和统计中的一个长期开放的问题（追溯到W. Hoeffding在1965年的工作）。同时建立了扩展的Sanov’s定理，从而证明了一般情况下的双样本检验的全局最优性。

该工作“Asymptotically Optimal One- and Two-Sample Testing with Kernels”经过近一年半的评审，已被IEEE顶刊IEEE Transactions on Information Theory接收。

论文地址为：

https://arxiv.org/abs/1908.10037（单栏），

http://dx.doi.org/10.1109/TIT.2021.3059267（双栏）。

背景

我们考虑统计假设检验中两个基础问题：单样本和双样本检验。在单样本问题（one-sample or goodness-of-fit testing）中，我们会给定某个分布P（例如高斯分布）和样本
，目标是判断
是否由该分布产生。我们用Q来表示
对应的真实但是未知的分布，该问题可转化为一个假设检验问题：
。双样本问题（two-sample or homogeneity testing）中，给定样本
和
，目标是判断
和
是否由同一个分布产生。如果我们用P和Q分别表示样本的潜在分布，那我们同样考虑一个假设检验问题：
。

单样本和双样本问题有很长的历史，在实际中也有非常广泛的应用。异常检测中，异常样本通常认为是来自和正常分布不同的分布。在变化点检测中，变化点之前的样本分布与变化前的分布不一样。通过将观察的样本与随机打乱的版本进行比较，可以将双样本检验应用于（条件）独立性测试，这对因果发现中一大类的方法（constraint-based methods）会很有帮助。其他的例子包括认知无线电中的频谱感知，生成模型中判别构造样本和实际样本的相似度，以及衡量MCMC方法生成的样本的质量等。

我们考虑非参数检验场景，并且假设没有关于未知分布（单样本问题中的Q，双样本问题中的P和Q）的先验知识。在这种情况下，通常的方法是基于一定的概率距离度量：只有两个分布相同时概率距离才为0，因此基于样本估计的统计量越大则表明P和Q越倾向于不同，即
更倾向成立。已有的例子包括最早的Kolmogorov-Smirnov distance，total variation，Wasserstein distance，Kullback-Leibler divergence（KLD），以及近些年提出的maximum mean discrepancy（MMD）和kernel Stein discrepancy （KSD）等基于核方法的概率距离度量。

目前存在很多单样本和双样本检验，一个自然的问题是如何从衡量一个方法的好坏，更进一步的是找到或者设计最优的检测。在单样本问题上，W. Hoeffding在1965年的一个工作里提出了一种衡量准则。假设样本是i.i.d.的，在简单假设检验问题中（即假设P和Q已知，判断样本是由哪个分布产生），似然比检验（likelihood ratio test）可以在给定第一类错误概率的约束取得最小的第二类错误概率。Chernoff-Stein引理进一步证明了第二类错误概率可以随着样本数量的增长而指数衰减到0，并且最优的指数速率为P和Q之间的KLD，记为
。因此，Hoeffding提出了一个最优的标准：是否存在这样一个单样本检验，在满足第一类错误概率的约束下，对于任意真实的Q（只要
），都可以实现和简单假设检验问题中同样的最优指数速率
？上述问题在信息论中被称为universal hypothesis testing。Hoeffding证明了似然比检验在此条件下的全局最优性，但是该结果只有当概率分布的样本空间为有限集的时候才成立。Hoeffding的结果吸引了很多后续的工作（如下[2]-[6]），尝试将上述结果扩展到更一般的样本空间（例如实数集），但是已有的工作通常是考虑某种弱化的标准或者假设检验问题，并且所提出的方法在实际中很难使用。如何在非有限样本空间上达到同样的全局最优性仍然是个开放的问题。值得注意的是，在非有限样本空间上，即便是存在性（achievability），即是否存在这样一个全局最优的单样本检验，也是个未知的问题。

[1] W. Hoeffding, “Asymptotically optimal tests for multinomial distributions,” The Annals of Mathematical Statistics, 1965.

[2] G. Tusnady, “On asymptotically optimal tests,” The Annals ofStatistics, 1977.

[3] O. Zeitouni and M. Gutman, “On universal hypothesis testing vialarge deviations,” IEEE Trans. Inf. Theory, 1991.

[4] M. Feder and N. Merhav, “Universal composite hypothesis testing:A competitive minimax approach,” IEEE Trans. Inf. Theory, 2002.

[5] J. Unnikrishnan, D. Huang, S. P. Meyn, A. Surana, and V. V.Veeravalli, “Universal and composite hypothesis testing via mismatched divergence,” IEEE Trans. Inf. Theory, 2011.

[6] P. Yang and B. Chen, “Robust Kullback-Leibler divergence anduniversal hypothesis testing for continuous distributions,” IEEE Trans. Inf.Theory, 2019.

问题描述

我们主要以单样本检验为例。考虑概率分布的样本空间为Polish空间（例如

），给定某个分布

和样本

，目标是判断

是否由该分布产生。我们用

来表示

对应的真实但是未知的分布，该问题可转化为一个假设检验问题：

。我们可以将一个单样本检验表示为

，当

成立时，则判断

成立。对于一个给定的单样本检验，我们考虑两类错误：当真实的分布满足

、但检验判别为

，此类错误被称为第一类错误（type-Ierror or false positive）；第二类错误（type-II error or false negative）发生是

为真但判别为。我们将两类错误的概率分别表示为：

注意这里的第二类错误概率依赖真实的但是未知的分布Q。

通常第一类和第二类错误概率不能同时最小化，一个常用的策略是Neyman-Person准则，即给定第一类错误概率约束条件

，目标最小化第二类错误概率。如上述介绍，这里我们关心的是指数收敛速率：

上述极限也被称为错误指数（error exponent），经常用在信息论中信源编码和信道编码等问题中，并且和其他两个渐进统计指标，Chernoff index和Bahadur slope有很强的联系。在Hoeffding全局最优的结果上，我们的目标是寻找一个单样本检验，对于任意一个潜在的分布

，都满足如下条件：

主要贡献

我们首先利用大偏差理论中的Sanov’s定理和KLD的下半连续性，得到满足全局最优的一个充分条件：

这里表示样本的经验概率测量（empiricalmeasure），条件a)是第一类错误的约束，条件b)需要一个弱收敛的概率距离。目前大部分的概率距离测量例如KLD，total variation distance都不满足b)，而Wasserstein distance，Levy metric等距离尽管具有弱收敛性，但是他们的样本估计通常不好计算，并且很难找到一个合适的阈值使得条件a)成立。显然，上述充分条件的关键是寻找一个合适的概率距离。

与此同时，机器学习领域中一个广泛研究的方向是基于核方法的概率距离，例如MMD和KSD等，然而目前的统计刻画结果通常依赖于具体的核函数，因此并非最优。基于上述定理和已有对这些概率距离的研究结果，我们第一次从理论上证明了在非有限样本空间上单样本检验的全局最优性。

基于MMD的插入单样本检验(plug-in test)

我们首先考虑直接带入观测样本的MMD统计量。假设样本空间为Polish, locally compact and Hausdorff（包括），并且核函数满足有界、连续和characteristic的性质。那么以下单样本检验的第一类错误概率满足约束条件，并且达到最优的第二类错误指数：

这里

，核函数

可以为高斯或者拉帕拉斯核函数。虽然该检验的构造比较直接和简单，但实际中需要计算关于

的积分

。如果

是非高斯的，显式表达式可能不太容易得到，下一个单样本检验方法则不需要计算这些积分。

基于双样本检验的单样本检验

我们从给定的分布

中抽样得到

个i.i.d.样本

，考虑如下检验：

我们证明了只要样本数量

随着

，满足

，那么以上检验也可以实现单样本检验的全局最优性。

基于KSD的单样本检验

当给定的概率分布比较复杂的时候，获得i.i.d.样本同样可能不太容易。KSD（kernel Steindiscrepancy）是近年提出的基于Stein变换再生核希尔伯特空间（RKHS）函数构建的统计量。KSD在
下的期望值为零，并且不需要计算积分或样本抽样。在放松第一类错误的约束（只需要渐进满足给定的约束）的条件下，我们证明了基于KSD的单样本检验同样可以达到最优的第二类错误指数。但是该结果需要关于概率分布和核函数更强的假设，具体细节请参见文章。

双样本检验

我们将全局最优性准则扩展到双样本检验的问题中。和单样本问题不同的是，现有的研究并没有建立双样本问题下的最优第二类错误指数。因此，我们首先证明了在第一类错误概率约束下的最优的第二类错误指数为：

这里

, ，并且假设

。然而，单样本问题下全局最优的充分条件并不适用，因为Sanov’s定理只适用于一个概率分布的情况。为此，我们建立了扩展的Sanov’s定理，从而证明了一般情况下基于MMD的双样本检验的全局最优性。细节请参见文章。

结语

我们第一次从理论上证明了单样本检验在非有限样本空间（具体的，Polish, locally compact and Hausdorff space）上的全局最优性，（基本）解决了信息论和统计中的一个长期开放的问题。同时建立了扩展的Sanov’s定理，证明了一般情况下的双样本检验的全局最优性。未来的一个工作是将现在的结果扩展到Polish空间。目前我们的证明框架和Sanov’s定理在Polish空间上也是适用的，如果能够找到一个合适的概率距离，我们相信全局最优结果在Polish样本空间会同样成立。

我们团队目前主要从事因果推理和发现相关的基础研究和应用（例如推荐、根因发现、解耦表征、RL等），欢迎有兴趣加入我们的同学发送简历至zhushengyu@huawei.com。

[技术干货] 机器学习方法解决信息论中多年开放问题？基于核方法的渐进最优单样本和双样本检验