0%

信息熵与统计距离

前面我们了解到比特(bit),也即二进制中的位,是信息的基本度量单位,本文针对这一点做进一步展开。本文受到 Loss Functions Explained By Siraj Raval 启发,主要参考了相关维基词条。

为方便理解,本文公式采用离散形式,但基本都可以无障碍的推广到积分形式

信息量

信息定量化的概念最早是由哈特莱 (Ralph Hartley) 于1928年提出,并选择了系统状态数(假设各状态等概率)的对数作为信息的度量。20年后,1948年信息论奠基人香农 (Claude E. Shannon) ,在其划时代的论文 A mathematical theory of communication中详细讨论了这一问题:

…the actual message is one selected from a set of possible messages. …If the number of messages in the set is finite then this number or any monotonic function of this number can be regarded as a measure of the information produced when one message is chosen from the set, all choices being equally likely. As was pointed out by Hartley the most natural choice is the logarithmic function.

The choice of a logarithmic base corresponds to the choice of a unit for measuring information. If the base 2 is used the resulting units may be called binary digits, or more briefly bits, a word suggested by J. W. Tukey. …

香农在论文中指出,对数底数的选择对应于信息度量单位的选择,并将以2为底数时对应的信息量单位称为比特 (binary digits, bit) ,与二进制系统的信息存储相对应;而以10为底情况称为decimal digits (dit, ban,也被称为Hartley) ;以e为底情况称为natural units(nat)。不同单位间根据对数的性质,相差一个常数倍(换底公式)。

香农认为信息的基本作用是消除人们对事物认知的不确定性。因此能够降低系统不确定性的才是有效信息,其余的则属于冗余信息。有效信息量的大小由信息消除不确定性的程度决定:1比特的信息量对应于系统的不确定性减半。

以前段的世界杯为例,某场球赛双方实力均等,胜率都是50%50\%,则比赛结果所含的有效信息量就是1bit,因为不确定性从概率均等的两种降低为一种。这一信息你可能是通过一篇文章、一个图片或者一段视频获得的,信息量可能是KB或者MB量级,但就比赛结果而言,其有效信息量就是1比特。换句话说,有效信息可以仅通过1比特的信息传达,其余的都是冗余信息。类似的,如果8支球队赢得冠军的概率均等,则比赛结果的有效信息量就是3比特 ( 比赛结果将事件不确定度减半了3次,23=8,log28=32^3=8, \log_2 8=3 )

从上面可以看出,有效信息量就等于系统不确定性降低程度的二进制对数(以2为底的对数)。比如某个随机事件发生的概率为p(x)p(x),事件发生,系统不确定性降低程度可由1/p(x)1/p(x)度量,从而这一结果的所包含的信息量为I(x)=log21p(x)=log2p(x)bit\textcolor{blue}{I(x) = \log_2 \frac{1}{p(x)} = -\log_2 p(x)\textrm{bit}}
由于对数函数的性质,信息量单调、非负、可加:信息量随事件不确定性增加而增加;且两独立随机事件同时发生的信息量为两事件各自发生的信息量相加。

回到前面的例子:对于两只球队情况,一只球队获胜概率为1/21/2,该球队获胜的有效信息量为 log22=1\log_2 2=1bit;对于8只球队情况,一只球队获胜概率为1/81/8,该球队获胜的有效信息为 log28=3\log_2 8=3bit。
有了这一定义,对于概率不等情况也很好处理。假设两队中胜率较小队的胜率为25%25\%,则该队获胜的信息量为log20.25=2-\log_2 0.25 = 2bit;对胜率较大队获胜的信息量可做类似计算 log20.75=0.415-\log_2 0.75 = 0.415bit。

最后,我们再来看一个经典的编码问题——老鼠毒药问题:

1000瓶无色液体中有一瓶毒药,其余为清水,老鼠吃到毒药一天内会死,现要求在一天内检测出有毒药瓶,至少需要几只老鼠?

乍一看可能以为这是一个抽样问题,但其实问题跟概率完全没关系。要用尽量少的老鼠,又限制检测时间为毒发时间,肯定要将液体混着喂,但要怎么混使用老鼠才最少,这其实是个编码问题。我们将问题换个说法就清晰了:1000个不同的状态用二进制编码需要几位?一天后老鼠的状态有生、死两种,因此是二进制编码。

不考虑实际操作,仅从信息编码角度考虑,1000个状态最少需要10位二进制来编码。具体操作:根据瓶子编码,如1001001010,将所有第一位为1的瓶子液体取少量混合喂给第一只老鼠,依次类推,最后根据第二天老鼠生死状态判断有毒瓶子的编码中那几位为1。
从信息论角度应该如何理解这一问题?随机抽样,取到毒药瓶的概率为11000\frac{1}{1000},因此有效信息量为 log21000=9.97\log_2 1000=9.97bit,要编码/存储9.97bit(比特)的有效信息,最少自然需要10bit(位)。
我们把问题扩展一下,1000瓶中有两瓶毒药,其他条件不变,最少需要几只老鼠?随机抽取两瓶水,共C10002C_{1000}^2种状态,二进制编码需要19位;从信息论角度看,抽出两瓶毒药的概率为21000×1999\frac{2}{1000}\times \frac{1}{999},从而有效信息量为log2(500×999)=18.93\log_2 (500\times 999)=18.93bit,因此最少需要19只老鼠。

接下来,问题再复杂点:还是一瓶毒药,要求在两天内检测出有毒药瓶,至少需要几只老鼠?
最简单的想法:把药瓶均分,拿同样几只老鼠,每天检测500瓶,最少需要log2500=8.97\log_2 500=8.97,即9只老鼠,比之前少了一只,但这是最少了吗?答案是否定的。
沿着之前的思路:之前的问题中,一天后,老鼠的状态有生、死两种,因此是二进制编码问题;而现在的问题中,两天后,老鼠的状态有死、生死、生生三种,因此是一个三进制编码问题。从信息论的角度看,信息量没变,但是信息量的单位变成了trit(三进制位),最少需要log31000=6.29\log_3 1000=6.29trit,即只需要7只老鼠。或者我们这样理解:问题的信息量是log21000\log_2 1000bit,而每只老鼠两天后能提供log23\log_2 3bit的信息量,从而需要 log21000log23=log31000=6.29\frac{log_2 1000}{\log_2 3}= \log_3 1000=6.29只老鼠。结果是一致的,因为正如本文开始所说,对数底数的选择是对信息量单位的选择。

具体要如何操作呢?稍微有点复杂,但基本思路与之前相同:

  • 第一天,取所有三进制编码第一位是2的瓶子液体少许,混合后喂给第一只老鼠,依次类推;
  • 第一天结束,根据老鼠生死状态判断有毒瓶子编码中哪几位为2(死老鼠对应的位),这些位上编码不是2的瓶子直接筛除;
  • 对于其余位,对应的老鼠都没死。在第二天,取这些位中编码是1的瓶子液体取少量,混合后喂给相应位对应的老鼠;
  • 第二天结束,根据老鼠状态判断有毒瓶子编码中哪几位为1,并最终确定毒药瓶三进制编码。

不借助信息编码视角,应该很难想到这一“最优”方案。

关于信息编码还有一个经典的称球问题NN个球中有一个和其他的质量不同,用天平最少几次一定能找出次品球?或者反过来:用天平称kk次最多能从多少球中找出次唯一的品球。这一问题又可分为已知次品球偏轻(重)以及不知偏向等情况。
最直接的想法是二分法,但并非最优方案。天平有平衡、左重、右重三种状态,这也是一个三进制编码问题。最简单的,已知8个球中一个比其他球略重,只需称2次就可以确定次品球了。更多讨论可参考这篇文章,这里直接给出结论(⌈⌉为向上取整,⌊⌋为向下取整):

  • 已知次品球偏轻(重):最少称重次数log3N\lceil\log_3 N\rceil;最多区分球数3k3^k
  • 不知次品球重量偏向:最少称重次数log32N\lceil\log_3 2N\rceil;最多区分球数3k2=3k12\displaystyle\lfloor\frac{3^k}{2}\rfloor=\frac{3^k-1}{2}
  • 找出次品球重量偏向:最少称重次数log32(N+1)\lceil\log_3 2(N+1)\rceil;最多区分球数3k21=3k32\displaystyle\lfloor\frac{3^k}{2}\rfloor-1=\frac{3^k-3}{2}
    :后两种情况的公式跟维基不一致,虽然不影响取整后结果,但本质上的信息量是不同的,我还没想清信息量到底是多少😖,存疑。

NN个球中有两个和其他的质量不同,…

信息熵

从前面两只球队的例子可以看到,当两队胜率不一样时,每只球队获胜所包含的信息量(不确定性的降低程度)是不一样的。那么我们随机获得一个比赛结果(抽取一个样本),系统不确定性降低程度的期望,或者说我们能获得信息量的期望应为0.25×2+0.75×0.415=0.810.25 \times 2 + 0.75 \times 0.415 = 0.81

香农将这一期望值称为系统的信息熵(Entropy),用以表征随机抽取一个样本所预期获得的信息量:

H(p)=ipilog2 pi=E(log2p)H(p) = -\sum_{i} p_i \log_2~p_i = E(-\log_2 p)

其中符号HH来自玻尔兹曼的H定理(本质上就是统计物理中的熵):

The form of HH will be recognized as that of entropy as defined in certain formulations of statistical mechanics where pip_i is the probability of a system being in cell ii of its phase space. HH is then, for example, the HH in Boltzmann’s famous HH theorem.

作为对比,统计物理中的熵(Entropy)

Clausius Entropy:   dS=(dQT)可逆过程Boltzmann Entropy:   S=kBlnΩGibbs Entropy:   S=kBipiln pi\begin{aligned} \text{Clausius Entropy:}~~~ dS &= \left(\frac{dQ}{T}\right)_{\text{可逆过程}} \\ \text{Boltzmann Entropy:}~~~ S &= k_B\ln\Omega\\ \text{Gibbs Entropy:}~~~ S &= -k_B\sum_{i} p_i \ln~p_i \end{aligned}

其中kBk_B为玻尔兹曼常数,Ω\Omega为特定宏观状态下系统的微观状态数,pip_i为系统处于微观态ii的概率。
可以看到信息熵在形式上与第三式完全一致。统计物理中熵有三种表述:克劳修斯熵、玻尔兹曼熵和吉布斯熵。三者在本质上是相同的,前者是对熵的宏观描述,后两者则是微观统计描述。考虑到统计物理的基本假设——等先验概率假设 (equal a priori probability postulate: 对于给定能量和组分的孤立系统,没有其他信息情况下,系统处于各微观状态的概率均等),便可由吉布斯熵得到玻尔兹曼熵。

通过研究卡诺热机,克劳修斯于1850年首次明确指出热力学第二定律(熵增定律)的基本概念,并于1865年引入了熵的概念,作为描述系统“能量退化”的状态参数。此时熵作为一个宏观观测量,其本质尚不清楚。玻尔兹曼在1866年开始使用ρlnρ\textcolor{orange}{\rho ln \rho}的形式表述熵,但他将ρ\rho解释为相空间的态密度,而没有提及概率,但其实态密度本身就是概率密度;吉布斯则在1878年给出了明确的概率解释[wiki]。几十年后(1948年),香农又从新的角度赋予上述公式了更一般的诠释,即信息熵。

信息熵与物理熵的关系Information is Physical

1867年,麦克斯韦针对热力学第二定律,提出了著名的思想实验麦克斯韦妖
为了解决这一问题,1929年物理学家Szilard引入一个简化版的麦克斯韦妖——单分子热机模型,并首次将信息的概念引入到热力学循环。Szilard认为麦克斯韦妖在获取分子状态信息过程中会消耗能量,从而导致整个系统的熵增。

直到香农建立信息熵之后,Landauer于1960年
于1961年提出了兰道尔原理( Landauer’s principle ),指出擦除1bit的信息最少需要消耗kTln2kT \ln 2的能量
建立起信息熵与热力学熵真实的联系。

2011年,物理学学家发现,虽然信息擦除必定增加熵,但却不一定消耗能量,而可以消耗其他守恒量,如角动量;2012年,物理学家测到了擦除1bit数据时所产生的热量。

1982年,Bennett

In 1960, Rolf Landauer raised an exception to this argument.

Landauer’s principle demonstrates the reality of this by stating the minimum energy E required (and therefore heat Q generated) by an ideally efficient memory change or logic operation by irreversibly erasing or merging N h bits of information will be S times the temperature which is

E = Q = T k B ln ⁡ ( 2 ) N h {\displaystyle E=Q=Tk_{\mathrm {B} }\ln(2)Nh} {\displaystyle E=Q=Tk_{\mathrm {B} }\ln(2)Nh}

where h is in informational bits and E and Q are in physical Joules. This has been experimentally confirmed.[

信息熵度量了我们能够从一个随机系统的样本中所能获得的平均信息量(期望);也表征了一个随机系统不可预测的程度:系统随机性越大,越混乱,信息熵就越大。前面的信息量反映的是一个具体事件发生所带来的信息;而信息熵表示的则是在结果出来之前,对于所能获得信息量的预期,即信息量的期望值。信息熵有以下性质:

  • 信息熵非负,且只有当系统没有不确定性时才为0;
  • log\log为凹函数,由Jensen不等式H(x)=E(log21p(x))log2E(1p(x))=log2nH(x) = E\left(\log_2 \frac{1}{p(x)}\right) \le \log_2 E\left(\frac{1}{p(x)}\right) = \log_2 n
    对于总状态数为nn的系统,信息熵最大为log2n\log_2 n,在系统各状态概率均等时取得;
    任何使系统趋向于各状态概率均等的变化都将增加系统的信息熵;
  • 联合熵 H(x,y)H(x)+H(y)H(x,y) \le H(x) + H(y),当且仅当XXYY相互独立取等号:
    XXYY联合事件的信息熵不超过各自信息熵之和,XXYY相互独立时两者相等;
  • 条件熵 H(yx)=0H(y∣x)=0 当且仅当YY完全由XX决定,即p(yx)p(y∣x) 只取0或1
  • H(x,y)=H(x)+H(yx)=H(y)+H(xy)H(x,y) = H(x) + H(y|x) = H(y) + H(x|y)
    XXYY联合事件的不确定度(熵)是XX的不确定度与XX已知条件下YY不确定度之和;
  • 结合前者有H(yx)H(y)H(y|x) \le H(y),当且仅当XXYY相互独立取等号:
    任何额外信息都不会增加系统的信息熵(不确定度); p.s.废话😄
  • H(yx)=H(xy)+H(y)H(x)H(y|x) = H(x|y) + H(y) - H(x) 贝叶斯公式的信息熵表达;
  • f,H(f(x)x)=0,H(xf(x))0\forall f, H(f(x)|x) =0 , H(x|f(x)) \ge 0,从而H(f(x))H(x)H(f(x)) \le H(x)
    随机变量函数的不确定度不会超过其自身的不确定度; p.s.有意思🤔

最后,我们回到两只球队的例子:不确定性最大(最随机)的情况便是两队胜率均等,此时系统信息熵为 0.5×1+0.5×1=10.5\times 1 + 0.5\times 1 = 1;其他情况下信息熵都低于该值,比如前面的75%/25%的情况,信息熵为0.81;而当某一队100%获胜时,系统不确定消失,比赛结果也就不会提供新信息,信息熵为0。其信息熵随某一队获胜概率变化的曲线如下:
entropy

联合熵(Joint Entropy),即联合分布p(x,y)p(x,y)的熵:

H(x,y)=x,yp(x,y)log2 p(x,y)H(x,y) = -\sum_{x,y} p(x,y) \log_2~p(x,y)

条件熵(Conditional Entropy),即条件概率p(yx)p(y|x)的熵:

H(yx)=xp(x)yp(yx)log2 p(yx)=x,yp(x,y)log2 p(yx)=x,yp(x,y)log2 p(x)p(x,y)\begin{aligned}H(y|x) &= -\sum_{x} p(x) \sum_{y} p(y|x) \log_2~p(y|x)\\ &= -\sum_{x,y} p(x,y) \log_2~p(y|x)\\ &= \sum_{x,y} p(x,y) \log_2~\frac{p(x)}{p(x,y)}\end{aligned}

互信息(Mutual Information):

I(x;y)=x,yp(x,y)log2 p(x,y)p(x)p(y)I(x;y) = \sum_{x,y} p(x,y) \log_2~\frac{p(x,y)}{p(x)p(y)}

由Jensen不等式,I(x;y)0I(x;y) \ge 0I(x;y)=0I(x;y)=0当且仅当XXYY独立
互信息是对称的I(x;y)=I(y;x)I(x;y)=I(y;x),且I(x;y)H(X),I(x;y)H(y)I(x;y) \le H(X), I(x;y) \le H(y)
互信息度量了XXYY共享的信息量,与H(x),H(y),H(xy),H(yx),H(x,y)H(x), H(y), H(x|y), H(y|x), H(x,y)的关系可由文氏图(Venn)直观表示

I(x;y)=H(x)H(xy)=H(y)H(yx)=H(x)+H(y)H(x,y)=H(x,y)H(xy)H(yx)\begin{aligned}I(x;y) &= H(x) - H(x|y)\\ &= H(y) - H(y|x)\\ &= H(x) + H(y) - H(x,y)\\ &= H(x,y) - H(x|y) - H(y|x)\\\end{aligned}

entropy-veen

由互信息可引出一种随机变量相似度的距离度量(variation of information):

VI(x;y)=H(xy)+H(yx)=H(x,y)I(x;y)=H(x)+H(y)2I(x;y)\begin{aligned}VI(x;y) &= H(x|y) + H(y|x)\\ &= H(x,y) - I(x;y)\\ &= H(x) + H(y) - 2I(x;y)\end{aligned}

统计距离

由信息熵可自然引出几个度量随机分布相似度的统计量,即所谓的统计距离( Statistical Distance ),比如上面提到的VI(x;y)VI(x;y),这里介绍其他几个常见的(以下换用自然对数)。作为“距离”通常要求:

  • 对称d(x,y)=d(y,x)d(x,y)=d(y,x)
  • 非负d(x,y)0d(x,y) \ge 0,等号当且仅当x=yx=y时成立;
  • 满足三角不等式d(x,z)d(x,y)+d(y,z)d(x,z) \le d(x,y)+d(y,z)

其中非负是最基本的要求,但对称性及三角不等式,统计学中的距离度量却不一定满足,因此并不是严格意义上的Metric(距离):两者都不满足的一般称为Divergence(散度);满足对称性但不满足三角不等式的则会被称为Distance(距离);但又有一些两者都满足的也会被称为Distance,有点乱。p.s. 反正汉语也没法区分😋

统计距离通常用于概率密度(分布)函数,但也有用于样本的情况,注意符号上的区别:

  • pip_i指(离散)随机变量状态ii概率xix_i是随机变量样本中的第ii样本
  • pip_i是一个标量的概率值,而xix_i作为一个随机变量的样本则可以是多维矢量

本文讨论的统计距离大部分都是应用于概率分布的,因此出现的都是pip_ip(x)p(x);但也有用于样本的,比如马氏距离、最大均值差异MMD。

  • 交叉熵

交叉熵(Cross Entropy)

H(p,q)=ipilnqi=Ep(lnq)H(p,\textcolor{blue}{q}) = -\sum_{i} p_i \ln \textcolor{blue}{q_i} = E_p(-\ln \textcolor{blue}{q})

交叉熵用来衡量在给定的真实分布下,使用非真实分布所指定的策略消除系统的不确定性所需要付出的努力的大小。

实例:由极大似然估计可以得到Logistic回归的损失函数为交叉熵H(y,y^)H(y,\hat y),其中yy取0或1, y^=sigmoid(θTx+b)=p(y=1x)\hat y = \operatorname{sigmoid}(\theta^Tx+b) = p(y=1|x)

吉布斯不等式H(p,q)H(p)H(p,q) \ge H(p),等号当且仅当分布ppqq完全一致时成立
由吉布斯不等式,交叉熵大于等于信息熵,因此两者间差值便可以作为距离的度量,被称为相对熵;对吉布斯不等式的证明可以参考以下对相对熵非负性的证明。

  • 相对熵

相对熵(Relative Entropy)常被称为K-L散度(Kullback–Leibler Divergence)或信息增益(Information Gain),其形式为:

H(pq)=ipiln(qipi)=Ep(lnplnq)=H(p,q)H(p)H(p||q) =-\sum_{i} p_i \ln \left(\frac{q_i}{p_i}\right) = E_p(\ln p - \ln q) = H(p,q) - H(p)

或公式推导时更常见的积分形式(连续型随机变量):

H(pq)=p(x)lnq(x)p(x)dx=p(x)lnp(x)q(x)dxH(p||q) = -\int p(x) \ln\frac{q(x)}{p(x)} dx= \int p(x) \ln\frac{p(x)}{q(x)} dx

由Jensen不等式可以证明K-L散度非负:ln-\ln为凸函数,由Jensen不等式,

Ep(lnqp)lnEp(qp)=ln1=0E_p\left(-\ln\frac{q}{p}\right) \ge -\ln E_p\left(\frac{q}{p}\right) = -\ln1 = 0

由于K-L散度非负,且H(pq)=0    q=pH(p||q)=0 \iff q=p,因此在统计学/机器学习中常被作为一种“距离”度量 DKL(pq)D_{KL}(p||q)。但这一度量不具有对称性DKL(pq)DKL(qp)D_{KL}(p||q) \neq D_{KL}(q||p),也不满足三角不等式。

在贝叶斯推断领域,DKL(pq)D_{KL}(p||q)度量了观测者的认知由先验分布q(x)q(x)过渡到后验分布p(x)p(x)所获得的信息增益。而在编码理论中,DKL(pq)D_{KL}(p||q)则代表了使用基于q(x)q(x)的编码来编码来自p(x)p(x)的样本,平均所需的额外的比特数(位数)。
而在实际应用,如机器学习领域,通常用p(x)p(x)代表真实分布或观测数据,而q(x)q(x)代表近似分布或理论模型,即用q(x)q(x)去近似p(x)p(x)。通过最小化K-L散度可以得到最接近真实分布/最符合观测数据的近似分布/理论模型。但由于K-L散度的非对称性,DKL(pq)D_{KL}(p||q)DKL(qp)D_{KL}(q||p)在使用中产生的效果并不相同:

  • 最小化DKL(pq)D_{KL}(p||q),会使得p(x)p(x)不为0处q(x)q(x)也尽量不为0(否则p(x)q(x)\frac{p(x)}{q(x)}会很大),从而会得到比较宽(矮胖)的分布曲线;
  • 最小化DKL(qp)D_{KL}(q||p),会使得p(x)p(x)为0处q(x)q(x)也尽量为0(否则q(x)p(x)\frac{q(x)}{p(x)}会很大),从而会得到比较窄(瘦高)的分布曲线。

两者是一致的,但效果却不完全相同,比如用高斯分布q(x)q(x)去近似双高斯分布p(x)p(x):使用前者时,会尽量同时拟合两个峰,最终其峰值可能没太大意义;而使用后者则会尽量拟合到其中一个峰上,峰值更有意义。
D_{KL}

最后,DKL(pq)D_{KL}(p||q)的黑塞(Hessian)矩阵是Fisher信息矩阵。

为了克服相对熵作为“距离”的缺点,人们又引入了JS散度,用于生成对抗网络(GAN)

  • JS散度

JS散度(Jensen–Shannon Divergence):

DJS(pq)=12[DKL(pm)+DKL(qm)],m=12(p+q)D_{JS}(p||q) = \frac{1}{2}[D_{KL}(p||m) + D_{KL}(q||m)], m=\frac{1}{2}(p+q)

如果两个分配P,Q离得很远,完全没有重叠的时候,那么KL散度值是没有意义的,而JS散度值是一个常数。这在学习算法中是比较致命的,这就意味这这一点的梯度为0。梯度消失了。

  • f 散度

K-L散度其实是更一般的ff散度(ff-divergence)的一种:

Df(pq)=q(x)f(p(x)q(x))dxD_f(p||q) = \int q(x)f\left(\frac{p(x)}{q(x)}\right) dx

其中函数f\bm{f}p(x)q(x)\bm{\frac{p(x)}{q(x)}}的凸函数,且f(1)=0\bm{f(1)=0}。由Jensen不等式,E(f(t))f(E(t))E(f(t)) \ge f(E(t))

Df(pq)=q(x)f(p(x)q(x))dxf(q(x)p(x)q(x))dx=f(1)=0D_f(p||q) = \int q(x)f\left(\frac{p(x)}{q(x)}\right) dx \ge f\left(\int q(x) \frac{p(x)}{q(x)}\right) dx = f(1) = 0

ff散度非负,其中等号也当且仅当p=qp=q成立。常见的ff散度及相应的ff形式有:

名称 f(t)f(t) 具体形式
K-L散度 t logtt~\log t DKL(pq)=p(x)lnp(x)q(x)dxD_{KL}(p\|q) = \displaystyle\int p(x) \ln\frac{p(x)}{q(x)} dx
总变差距离 12t1\frac{1}{2} \vert t-1\vert δ(p,q)=12p(x)q(x)dx\delta(p,q) = \displaystyle\frac{1}{2} \displaystyle\int \vert p(x)-q(x)\vert dx
χ2\chi^2散度 (t1)2, t21(t-1)^2,~ t^2-1 χ2(pq)=(p(x)q(x))2q(x)dx\chi^2(p\|q) = \displaystyle\int \frac{(p(x)-q(x))^2}{q(x)} dx
Hellinger距离 12(t1)2, 1t\frac{1}{2} (\sqrt{t}-1)^2,~ 1-\sqrt{t} H2(p,q)=12(p(x)q(x))2dxH^2(p,q) = \displaystyle\frac{1}{2} \int\left(\sqrt{p(x)}-\sqrt{q(x)}\right)^2 dx

其中K-L散度及χ2\chi^2散度非对称,而总变分距离及Hellinger距离对称。

  • 总变差距离(Total Variation Distance)/the Statistical Distance
    总变差距离是针对σ\sigma代数上的概率测度定义的:δ(p,q)=supAFp(A)q(A),sup\delta(p,q)=\displaystyle\sup_{A\in \mathcal{F}}|p(A)-q(A)|, \sup为上确界。具体到概率分布,就对应于两分布差异的1-范数(的一半):

δ(p,q)=12ipiqi=12pq\delta(p,q) = \frac{1}{2}\sum_i |p_i-q_i| =\frac{1}{2}||p-q||

Pinsker不等式   δ(p,q)12DKL(pq), p(x),q(x)2DKL(pq)\textrm{\small Pinsker不等式}~~~\delta(p,q) \le \sqrt{\frac{1}{2} D_{KL}(p||q)},~||p(x),q(x)|| \le \sqrt{2 D_{KL}(p||q)}

              ~~~~~~~~~~~~~~注意:上述不等式中,DKL(pq)D_{KL}(p||q)取以10为底的对数(单位为nat)

  • χ2\chi^2检验(Pearson’s Chi-squared Test)

    χ2=Nin(piqi)2qi\chi^2 = N \sum_i^n\frac{(p_i-q_i)^2}{q_i}

    其中NN为样本数据总数,nn为数据的类别数;假设模型的自由参量(自变量+协变量)数为pp,则χ2\chi^2自由度为npn-p

    χ2\chi^2检验主要用于分类数据
    卡方检验方法可以根据样本数据,推断总体分布与期望分布或某一理论分布是否存在显著差异,是一种吻合性检验,通常适于对有多项分类值的总体分布的分析。它的原假设是:样本来自的总体分布与期望分布或某一理论分布无差异。

约化的χ2\chi^2

  • 海林格距离(Hellinger Distance)

    H2(p,q)=12i(piqi)2=1ipiqiH^2(p,q) = \frac{1}{2}\sum_{i}\left(\sqrt{p_i} - \sqrt{q_i}\right)^2 = 1 - \sum_i \sqrt{p_iq_i}

    ipiqi0\sum_i \sqrt{p_iq_i} \ge 0,从而H2(p,q)1H^2(p,q) \le 1,再结合ff散度性质有:0H2(p,q)10 \le H^2(p,q) \le 1
    海林距离可以表示为2-范数H(p,q)=12pq2H(p,q) = \frac{1}{\sqrt{2}}||\sqrt{p} - \sqrt{q}||_2

    H2(P,Q)δ(P,Q)2H(P,Q)H^{2}(P,Q) \le \delta (P,Q) \le {\sqrt {2}}H(P,Q)

  • 其他度量:

    • 闵氏距离(Minkowski Distance)

d(x,y)=xyp=(ixiyip)1/p,pRd(x,y) = ||x-y||_p = \left(\sum_i|x_i - y_i|^p\right)^{1/p}, p\in \mathbb{R}

闵氏距离即向量范数,是最常见的距离定义。几个常见的特殊情况:

  • 1-范数:曼哈顿距离          d(x,y)=xy=ixiyi~~~~~~~~~~d(x,y) = ||x-y|| = \sum_i|x_i - y_i|
  • 2-范数:欧氏距离             d(x,y)=xy2=i(xiyi)2~~~~~~~~~~~~~d(x,y) = ||x-y||_2 = \sqrt{\sum_i(x_i - y_i)^2}
  • 无穷范数:切比雪夫距离   d(x,y)=xy=maxixiyi~~~d(x,y) = ||x-y||_\infty = \displaystyle\max_i|x_i - y_i|

闵氏距离对称,且当p1p \ge 1时,满足三角不等式。其定义跟统计学没有关系,但可以应用于统计学,比如前面的总变差距离本质上就是1-范数。将闵氏距离应用于统计学,可分为用于概率分布和用于样本集两种情况:

  • 应用于分布,判断分布相似性,即统计距离:
    • 总变差距离:1-范数应用于概率密度函数
    • ?距离:2-范数应用于概率密度函数,没找到,χ2\chi^2检验、海林格距离都似是而非
    • K-S检验:无穷范数应用于经验(累积)分布函数*
      *其他地方未看到过这个说法,存疑😋但仅从公式看是这样的。
  • 应用于样本集,衡量样本与预测之间的偏差(预测误差):
    • 直接使用:如最小二乘法中的欧氏距离​yy^2=in(yif(xi))2||y-\hat y||_2 = \sum_i^n (y_i - f(x_i))^2
    • 均方误差(MSE):MSE=1nyy^2=1nin(yiy^i)2\operatorname{MSE} = \frac{1}{n} ||y-\hat y||_2 = \frac{1}{n} \sum_i^n(y_i-\hat y_i)^2
      问题:(1)当指数p>1p>1,会放大偏差较大异常值的权重,随着pp增加,效应愈加明显。(2)将闵氏距离应用于样本集时,通常需要先对数据进行标准化,以避免不同维度上数据权重不一。但有时候这种做法又不合适,如两个维度数据可能线性相关,各自进行标准化是不合理的(椭圆不是正的,长短轴与坐标轴(变量)不平行,需要做坐标旋转)。

为了克服闵氏距离,尤其是最常用的欧氏距离,应用于样本集时的缺陷,统计学家引入了马氏距离。

  • 马氏距离(Mahalanobis Distance)

DM(x,y)=(xy)TΣ1(xy), Σ为样本协方差矩阵D_M(x,y) = \sqrt{ (x-y)^T \Sigma^{-1} (x-y)},~\Sigma \small\text{为样本协方差矩阵}

马氏距离由印度统计学家马哈拉诺比斯(P. C. Mahalanobis)提出,用于(分布未知的)样本集间相似度的度量。相比欧氏距离,马氏距离多了中间的协方差矩阵逆矩阵项,从而排除了特性间相关性的影响,且与尺度无关(方差归一化),不受量纲影响。
其缺点是要求样本的协方差矩阵矩阵的逆矩阵存在,实际中并不一定现实;且会夸大变化微小的变量的作用。

  • 巴氏距离(Bhattacharyya Distance)

DB(p,q)=ln(ipiqi)=lnBC(p,q)D_{B}(p,q) = -\ln \left(\textstyle\sum_{i} \sqrt{p_iq_i}\right) = -\ln BC(p,q)

BC(p,q)=ipiqiBC(p,q)=\textstyle\sum_{i} \sqrt{p_iq_i}被称为巴氏系数,与海林格距离密切相关H2(p,q)=1BC(p,q)H^2(p,q) = 1-BC(p,q)
巴氏距离对称但不满足三角不等式。

  • Wasserstein距离(Wasserstein Metric / Earth Mover’s Distance)

Wp(μ,ν):=(infγΓ(μ,ν)M×Md(x,y)pdγ(x,y))1/p=infE[d(X,Y)p]W_{p}(\mu ,\nu):=\left(\inf_{\gamma \in \Gamma (\mu ,\nu)}\int_{M\times M}d(x,y)^{p}\,\mathrm{d}\gamma(x,y)\right)^{1/p} = \inf{E} \left[ d(X,Y)^p \right]

Wasserstein距离对称且满足三角不等式。
Wasserstein距离是可以定义两个support不重合,甚至一点交集都没有的分布之间的距离的,而KL在这种情况并不适用。

  • K-S检验(Kolmogorov–Smirnov Test)

Dn=supxFn(x)F(x)D_n = \sup_x |F_n(x) - F(x)|

Dn,m=supxF1,n(x)F2,m(x)D_{n,m} = \sup_x |F_{1,n}(x) - F_{2,m}(x)|

其中F(x)F(x)为累积分布函数,Fn(x), Fm(x)F_n(x),~F_m(x)为经验分布函数,n, mn,~m分别为两个样本的样本数。

K-S检验方法能够利用样本数据推断样本来自的总体是否服从某一理论分布,是一种拟合优度的检验方法,适用于探索连续型随机变量的分布。单样本K-S检验的原假设是:样本来自的总体与指定的理论分布无显著差异。

原假设下,nn\to \infty时,nDn\sqrt{n} D_n趋于分布Kolmogorov分布(K=supt[0,1]B(t),B(t)K=\displaystyle\sup_{t\in [0,1]}|B(t)|, B(t)为布朗桥):

nDnnsuptB(F(t))\sqrt{n} D_n \xrightarrow {n\to \infty } \sup_{t}|B(F(t))|

Kolmogorov分布的累计分布形式为:

Pr(Kx)=12k=1(1)k1e2k2x2=2πxk=1e(2k1)2π2/(8x2)\Pr (K\leq x)=1-2\sum_{k=1}^{\infty }(-1)^{k-1}e^{-2k^{2}x^{2}}={\frac{\sqrt {2\pi }}{x}}\sum_{k=1}^{\infty }e^{-(2k-1)^{2}\pi^{2}/(8x^{2})}

可由Kolmogorov分布获得判断拟合好坏的临界值。
对于拟合,nDn>Kα\sqrt{n} D_{n}>K_{\alpha }则在α\alpha水平上拒绝原假设。其中KαK_{\alpha}Pr(KKα)=1α\Pr (K\leq K_{\alpha })=1-\alpha确定。

对于两个样本,Dn,m>c(α)n+mnmD_{n,m}>c(\alpha) \sqrt{\frac{n+m}{nm}}则在α\alpha水平上拒绝原假设,其中c(α)=12ln(α2)c\left(\alpha \right)= \sqrt{-{\frac{1}{2}}\ln \left({\frac{\alpha}{2}}\right)}

χ2\chi^2检验及KS检验都是统计学中常见的非参数检验方法,用于检验两个分布(数据与模型或数据与数据)的近似程度,χ2\chi^2检验判据来自χ2\chi^2分布,而KS检验判据则来自Kolmogorov分布。χ2\chi^2检验多用于分类数据,而KS检验多用于数值数据。

  • 最大均值差异(Maximum Mean Discrepancy, MMD)

MMD(p,q):=supfF(Ep[f(x)]Eq[f(y)])\operatorname{MMD}(p,q) := \sup_{f \in \mathcal{F}}(E_p [f(x)] - E_q [f(y)])

F\mathcal{F}表示一个在样本空间上的连续函数集
F=C0(X)\mathcal{F}=C^0(\mathcal{X})is the space of continuous, bounded, functions on X\mathcal{X}

MMD(X,Y)=supfF(1mimf(xi)1ninf(yi))\operatorname{MMD}(X,Y)=\sup_{f \in \mathcal{F}}( \frac{1}{m} \sum_i^m f(x_i) - \frac{1}{n} \sum_i^n f(y_i))

MMD(X,Y)=i=1n1f(xi)j=1n2f(yj)H2\operatorname{MMD}(X,Y)=\left \Vert \sum_{i=1}^{n_1} f(x_i)- \sum_{j=1}^{n_2} f(y_j) \right \Vert^2_\mathcal{H}

最大均值差异是应用于样本而非分布函数,其基本想法为:如果两个分布的随机样本对任意的函数ff均值都相等,则可以认为两个分布是相同的。

主要用于迁移学习,稍微有点复杂,为了真正理解上述公式,需要首先了解再生核希尔伯特空间(RKHS),可以参考这篇文章

均方误差(MSE)在参数估计中也存在,但文中与此处不同:假设未知参数θ\theta的估计值为θ^\hat\theta,则该估计的均方误差MSE(θ^)=Varθ^(θ^)+Baisθ^(θ^,θ)2MSE(\hat\theta) = \operatorname{Var}_{\hat\theta}(\hat\theta) + \operatorname{Bais}_{\hat\theta}(\hat\theta, \theta)^2
此时将估计量θ^\hat\theta视为随机变量,当估计量为样本统计量时,对估计量求期望就是对样本求期望。
对于参数估计的方均误差有MSE(x)=E[(xxt)2]=σx+(xˉx)2MSE(x) = E[(x-x_t)^2] = \sigma_{x} + (\bar{x}-x)^2,我们可以得出,对于无偏估计,估计量的MSE是方差。

:统计中常见的数据可分为分类数据 ( Categorical Variable ) 和数值数据 ( Numerical Variable ) ,大致可理解为定性(qualitative)和定量(quantitative)数据。其中分类数据又可分有序(Ordinal)和无序(Nominal);数值数据可分离散(Discrete)和连续(Continuous)。
在做运算时,分类数据通常需要转化为离散型数值数据(编码),比如将四个类别分别对应于1,2,3,4四个数字或者(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)四个向量。

扩展阅读:
评分卡系列(三):分类学习器的评估

Donate if you enjoy this content.