样本统计梳理

样本统计梳理

摘录于

和

1. 最大后验概率估计（MAP）

• 概率是已知模型和参数（生成数据的过程），推数据（结果）。
• 统计是已知数据（结果），推模型和参数（生成数据的过程）。

1.1 贝叶斯理论(Bayes’ Theorem)

贝叶斯统计：参数是未知且不确定，作为随机变量，参数本身也是一个分布，同时，根据已有的信息可以得到参数θ的先验概率，根据先验概率来推断θ的后验概率。贝叶斯如下式：

贝叶斯公式就是你有多大把握能相信一件证据 ；做判断的时候，要考虑所有的因素。

 1.2 似然函数(likelihood function)

对于函数P(x|θ)，x表示某一个具体的数据，θ 表示模型的参数 

• 概率函数：如果θ 是已知确定的，x 是变量，P(x|θ)是对于不同的样本点x ，其出现概率是多少。
• 似然函数：x是已知确定的，θ 是变量，P(x|θ)是对于不同的模型参数，出现x 样本点的概率是多少。
• 同一个数学形式，从不同的变量角度观察，可以有不同的名字。

1.3 最大后验概率估计（MAP）

• 极大似然估计（MLE）中，我们求参数θ，使得似然函数p ( X ∣ θ )最大
• 最大后验概率估计是想求θ ，使P ( X ∣ θ ) P(θ)最大，求得的θ 不单单让似然函数大，θ 自己出现的先验概率也得大
• 虽然MAP=MLE*P（θ），但是MLE将θ视为一个确定未知的值，MAP将θ视为随机变量

2. Wasserstein距离(Wasserstein distance)

2.1 KL散度 

 KL散度（又称相对熵），是信息散度，信息增益。KL散度是两个概率分布P 和Q 差别的非对称性的度量。 典型情况下，P 表示数据的真实分布，Q 表示数据的理论分布、模型分布，或P 的近似分布。

对数函数是凸函数，所以KL散度的值为非负数。

• KL散度不是对称的；
• KL散度不满足三角不等式

2.2 JS散度

JS散度(Jensen-Shannon)度量了两个概率分布的相似度，基于KL散度的变体，解决了KL散度非对称的问题。一般地，JS散度是对称的，其取值是0到1之间。

KL散度和JS散度度量时有一个问题：如果两个分配P , Q离得很远，完全没有重叠，KL散度值是没有意义的，而JS散度值是一个常数。

2.3 Wasserstein距离

Wasserstein距离度量两个概率分布之间的距离，定义如下：

式中， 是P1和P2分布组合起来的所有可能联合分布的集合。

1）对于每一个可能的联合分布γ ，可以从中采样( x , y ) ∼ γ等到一个样本 x和y，并计算出这对样本的距离||x-y||；

2）计算联合分布γ 下，样本对距离的期望值E ( x , y ) ∼ γ [ || x − y || ] ;

3）在所有可能的联合分布中能够对这个期望值取到的下界,就是Wasserstein距离。

 也可以把E ( x , y ) ∼ γ [ || x − y || ] 理解为在γ 这个路径规划下把P1 挪到P2所需要的消耗。而Wasserstein距离就是在最优路径规划下的最小消耗。所以Wesserstein距离又叫Earth-Mover距离。相比KL散度和JS散度，Wassertein距离优势在于：即使两个分布的支撑集没有重叠或者重叠非常少，仍然能反映两个分布的远近。而JS散度在此情况下是常量，KL散度可能无意义。

 

3. 最优传输-Sinkhorn算法

3.1 最优传输问题

最优传输(Optimal Transport)关键的一点是，要考虑怎样把多个数据点同时从一个空间映射到另一个空间上去，而不是只考虑一个数据点。

3.2 Kantorovich relaxation

Kantorovich relaxation可以说是蒙日（Monge）问题的一个松弛版本。

蒙日问题是找出从一个 measure到另一个measure的映射，使得所有c ( x i , y j ) 和最小。c 是个cost function，根据具体应用定义。

问题：一个measure中的每个元素都要对应到另一个measure的一个元素上，导致这个定义只能用来分析同等大小的measure （也就是说只能比较和最优化permutation）。同时，蒙日问题的约束条件，T α = β ，要求对于measure α 里的每一个元素，都对应到measure β 里一个质量完全相等的元素上。这个约束条件并不是线性的，于是蒙日问题很难求解。
kantorovich relaxation将原来的要求松弛，允许每个元素的质量分给目的分布里的多个元素，而不是蒙日问题里的一对一传输。

这样，约束就变为以下公式： 

 这个约束不要求measure α , β 里的元素一 一对应，只需保证α 里每个元素的质量完全传走，β 里每个元素也都收到正确的总质量就足够了。这个简化的约束条件变为线性，相比原本蒙日问题求解难度大幅降低，这也是之后主要都用Kantorovich的重要原因。

 kantorovich 的传输可以用一个矩阵来表示，P i , j 代表a i  到b j 的质量传输大小每个传输仍然需要保证质量守恒。
于是，给出了最优传输问题用kantorovich的定义：​    

 

 这里U 是从a 到b 的所有可能传输P 的集合，而P 就是当前的传输矩阵，C仍然是cost matrix。

3.3 熵正则化

在大型数据集上进行最优传输时 ，时间复杂度是个非常重要的因素。在大部分应用情况下，求标准Kantorovich解是不必要的。利用正则化，改求近似解，那么最优传输的计算代价就大幅降低了。正则化的最优传输是用一系列矩阵乘法求解。这意味着最优传输可以充分享受GPU的矩阵加速效果，实用价值明显提升；同时，正则化后的最优传输距离对输入的概率分布是完全连续的，并且能够系统式求导，在WGAN等方向上这点卓有成效。
正则化定义如下式：

 H(P)即为正则化的代价函数，是整个概念的核心。那么加上正则化的最优传输问题则变为

 式中，ε （epsilon）是个正则化系数，它的大小决定正则化作用的强度，和神经网络里的正则化系数是完全一样的。

同样一个单位的质量转移，如果分布在少数的上，每个取值较大，那么代价会大于将质量分布在多个   上，每个 取值很小。换句话说，正则化鼓励利用多数小流量路径的传输，而惩罚稀疏的，利用少数大流量路径的传输，由此达到减少计算复杂度的目的。

 在ε取值很小时，传输集中使用少数路径；当ε 取值变大，正则化传输的最优解变得更加“扁平”，使用更多的路径进行传输。

 3.4 Sinkhorn算法

 熵正则化仍然是一个概念，需要一个有效的算法，才能够释放它的潜力。

 正则化后的Kantorovich问题的解可以写为以下形式

 加入最优传输的质量守恒条件，得到以下两个条件

 式中是矢量的哈达马积（Hadamard product），也就是元素对应的乘积。这一对等式已经属于一类叫做matrix scaling的数学问题，于是可以通过迭代方式求解。

 每一步先更新u满足左侧等式，再更新v满足右侧等式，最终迭代收敛，两侧等式同时满足，我们就得到了最优解。

 基本Sinkhorn算法的初始化也十分简单：，是将v中每个元素都设为1