在通信约束下从样本中学习分布

本篇是来自Standford CompressionWorkshop 2019的演讲，演讲者是来自斯坦福大学的Leighton Barnes，演讲题目是在通信约束下从样本中学习分布。

首先演讲者介绍了演讲的主题，是在在某种通信约束下进行统计推断，也就是在某种通信受限条件下可以将统计工作做到多好。比如有一群不同的服务器，也就是一群不同的节点，数据分布在这些服务器上，为了某些计算而需要被传输到某地。问题是在传输速率和统计问题中，基本的取舍在于什么。演讲者举了一个例子，用来解释做这项工作的动机。在训练某种深度神经网络时，需要进行分布式的随机梯度下降计算，数据分布在一些节点中。如果是64个节点通过1Gbps的网络连接起来，可以提升30倍的训练速度，而使用10Gbps的网络连接，则可以提升260倍的训练速度。因此，如果使用如此的分布式计算，那么通信将会成为瓶颈，所以需要寻找在通信速率和效果之间的一种比较合理的折中。

接下来演讲者介绍了具体的数学问题。假设有一些从分布P中获得的样本X，他们是独立同分布的，这些数据分布在不同的节点上，并且需要被传输到某个集中的位置。现在的目标就是估计P这个分布。假设每个节点仅能向中心传输K比特，从而问题转化为每个节点的子问题。问题中最基本的情况是需要估计某种离散分布P，即已知种类数为D，要估计每种取值的概率。还可以估计某种非参数分布，即有一些从符合某种光滑的密度函数f的分布中抽取不同的样本，从而估计这个f。还可以估计参数，比如估计高斯分布的均值。

下面演讲者介绍了不同的通信协议，其问题背景如前文所描述。首先是独立协议，也就是每个节点单独决定如何编码产生这k比特，所以这些每个节点的信息都是独立的随机变量，这也是独立协议名字的由来。第二种是顺序协议，这种协议下节点可以进行一定程度上的交互。按照顺序，每个节点广播其k比特信息，排在后面的节点可以收到并使用这些信息，从而决定如何编码自己的信息。第三种协议类似于有一个公共的黑板，所有节点可以看到其他所有节点已经发布的信息，但是每个节点发布的总信息量还是被限制在K比特以内。

然后演讲者介绍了本领域一些已经完成的工作，感兴趣的读者可以去视频中获得这些情况。

接下来演讲者具体介绍了估计离散分布的数学过程，这个过程是最简单的一种情况。此过程的数学描述可以见下图，图中描述了问题的情况，最优化的目标和限制。

注意我们试图同时进行估计和寻找最佳的编码方式。在这种中心化的情况下，如果有一群样本，那么估计分布的一般方法是建立一个直方图，并且样本越多，可信度越高。之后演讲者又介绍了非中心化情况的做法，这种做法比较复杂，读者可以去视频中了解更具体的细节。

下面演讲者阐述了他们的定理及推论如下图。

令人惊讶的是，理论上可以证明这种估计不能做得更好，也就是L2 risk最小的最大值存在一个下界，这下界与所给的比特数和待估计的分布大小有关。推论表明，K只要大于等于logD就可以达到中心化的效果。

下面做一个总结，演讲者说他们的主要贡献是证明了我们不能比上述这种简单的方案做得更好，并且在统计问题上证明了L2 risk的下界。在下界的估计时引出了费雪信息量（Fisher Information），这个量在某种程度上量化了导数项的方差。基本上在估计中能达到的MSE的下界就是费雪信息量的倒数。演讲者研究的主要就是费雪信息量，研究了在量化样本中得到的费雪信息量是什么，还有如果获得了一个压缩的样本，如何量化其费雪信息量，以及与比特率K成哪种关系，这就是他们的主要创新点。

然后演讲者讲了一些应用例子。首先是离散分布的情况，从压缩样本中提取的费雪信息量随k成指数增长，从而解释了估计问题中L2 risk的下界中分母上有2的k次幂。在估计高斯分布的均值时，费雪信息量随k线性增长，从而L2 risk的下界中分母上有k。同样的，在估计高斯分布的方差时，费雪信息量随k平方增长，从而L2 risk的下界中分母上有k平方。

最后演讲者回到了随机梯度下降的例子，这个例子中可以用到他们的理论。有一些潜在的参数是总体期望的真实梯度，有一些数据在一群不同的节点上，这些数据可以被视为满足某种潜在分布的噪声样本，这时每个节点要如何编码k比特并发送给中央处理器，才能获得梯度的最好估计呢？

由于本篇理论味道较浓，帖子难以讲得清楚，感兴趣的读者可以在演讲者Leighton Barnes的两篇论文中了解更具体的研究成果细节，论文标题分别为“Learning Distributions from their Samples under Communication Constraints”和“Fisher Information for Distributed Estimation under a Blackboard Communication Protocol”。