统计距离(statistical Distance)

统计距离(Statistical Distance)

统计距离的定义

在欧式空间,如果要衡量两个 n 维空间中的点 \bold{x}=(x_{1},\cdots,x_{n})\bold{y} = (y_{1}, \cdots, y_{n})\in\mathbb{R}^{n} 之间的距离,通常可以使用 L^{p}- 范数来进行描述,其数学公式是:

d(\bold{x},\bold{y})=(\sum_{i=1}^{n}|x_{i}-y_{i}|^{p})^{1/p}, 1\leq p <+\infty.

d(\bold{x},\bold{y})=\max_{1\leq i\leq n}|x_{i}-y_{i}|, p=+\infty.

在统计学中,如果需要衡量两个统计对象之间的“距离”,在离散的场景下除了可以使用欧式距离之外,还可以使用其他的统计距离来描述这两个统计对象之间的距离。与之对应的,在连续的场景下,同样可以定义出两个统计对象之间的距离。

首先,我们来回顾一下距离的定义;

距离是定义在集合 X 的函数 d:X\times X \rightarrow [0,+\infty), 并且满足以下条件:

  1. d(x,y)\geq 0 对于所有的 x,y\in X 都成立;
  2. d(x,y) = 0 \iff x=y;
  3. d(x,y) = d(y,x) 对于所有的 x,y\in X 都成立;
  4. d(x,y) + d(y,z) \geq d(x,z) 对于所有的 x,y,z\in X 都成立。

而广义的距离会缺少其中一个或者多个条件,例如时间序列领域中的 DTW 距离就不满足三角不等式。

在微积分中,凸函数(convex 函数)f: \mathbb{D}\rightarrow \mathbb{R} 指的是在其定义域内的任意两个点 x_{1},x_{2}\in\mathbb{D}, 满足
\frac{f(x_{1})+f(x_{2})}{2} \geq f\bigg(\frac{x_{1}+x_{2}}{2}\bigg). 换言之,如果凸函数 f(x) 存在二阶连续导数,那么 f'(x) 是增函数,f''(x)\geq 0.

其次,在统计距离中,通常会基于一个函数 f:\mathbb{R}\rightarrow\mathbb{R} 来定义两个概率分布之间的距离。该函数 f 是一个凸函数(convex function),并且满足 f(1)=0. 对于空间 X 中的两个概率分布 PQ 而言,

D_{f}(P||Q)=\int_{X}f\bigg(\frac{dP}{dQ}\bigg)dQ=\int_{X}f\bigg(\frac{p(x)}{q(x)}\bigg)q(x)dx

定义了概率分布 PQf- 散度(f-divergence),其中 p(x),q(x) 分别对应了 P,Q 的概率密度函数。不同的函数 f(x) 对应了不同的散度,常见的散度包括但不限于:

  • KL – 散度(KL – Divergence):f(x)=x\ln(x);
  • Reverse KL -散度(Reverse KL – Divergence):f(x)=-\ln(x);
  • Hellinger 距离(Hellinger Distance):f(x)=(\sqrt{x}-1)^{2} 或者 f(x)=2(1-\sqrt{x});
  • 变分距离(Total Variation Distance):f(x)=|x-1|/2;
  • Pearson \chi^{2} – 散度(Pearson \chi^{2} – Divergence):f(x)=(x-1)^{2} 或者 f(x)=x^{2}-1 或者 f(x)=x^{2}-x;
  • Reverse Pearson \chi^{2} – 散度(Reverse Pearson \chi^{2} – Divergence):f(x)=\frac{1}{x}-1 或者 f(x)=\frac{1}{x}-x;
  • Jensen-Shannon-Divergence:f(x)=\bigg\{(x+1)\ln\bigg(\frac{2}{x+1}\bigg)+x\ln(x)\bigg\}/2;
  • L1 – 范数(L1 – Norm):f(x)=|x-1|;

在这样的定义下,D_{f} 是非负函数,i.e. D_{f}(P||Q)\geq 0. 事实上,

D_{f}(P||Q)=\int_{X} f\bigg(\frac{dP}{dQ}\bigg)dQ\geq f\bigg(\int_{X}\frac{dP}{dQ}dQdx\bigg)=f(1)=0.

在数学中有如下定理:如果 f 是凸函数,那么 g(x,t)=tf(x/t) 在定义域 \{(x,t)|x/t\in Dom(f),t>0\} 也是凸函数。

根据以上定理,可以得到:对于 \forall 0\leq \lambda\leq 1,

D_{f}(\lambda P_{1}+(1-\lambda)P_{2} ||\lambda Q_{1}+(1-\lambda)Q_{2})\leq \lambda D_{f}(P_{1}||Q_{1}) + (1-\lambda)D_{f}(P_{2}||Q_{2}).

除了 f- 散度之外,直接使用 L^{p}- 范数也可以定义两个概率空间的距离,特别地,当 p=1,2,\infty 时,其距离公式是:

||P-Q||_{1}=\int_{X}|p(x)-q(x)|dx,

||P-Q||_{2}=\sqrt{\int_{X}|p(x)-q(x)|^{2}dx},

||P-Q||_{\infty}=\sup_{x\in X}|p(x)-q(x)|.

统计距离的函数分析

事实上,对于 KL 散度和 Reverse KL 散度而言,令 f_{1}(x)=x\ln(x), f_{2}(x)=-\ln(x),

\text{KL}_{f_{1}}(P||Q)=\int_{X}f_{1}\bigg(\frac{p(x)}{q(x)}\bigg)q(x)dx=\int_{X}p(x)\ln\frac{p(x)}{q(x)}dx

=\int_{X}-p(x)\ln\frac{q(x)}{p(x)}dx=\int_{X}f_{2}\bigg(\frac{q(x)}{p(x)}\bigg)p(x)dx

=\text{Reverse KL}_{f_{2}}(Q||P),

这就是函数 f_{1}, f_{2} 分别对应着 KL-散度和 Reverse KL-散度相应函数的原因。

类似地,对于函数 f_{3}(x)=x^{2}-1, f_{4}(x)=x^{2}-xg_{3}(x)=\frac{1}{x}-x, g_{4}(x)=\frac{1}{x}-1 而言,可以直接证明得到:

\text{Pearson}_{f_{3}}(P||Q)=\int_{X}\bigg(\bigg(\frac{p(x)}{q(x)}\bigg)^{2}-1\bigg)q(x)dx

=\int_{X}\bigg(\frac{p(x)}{q(x)}-\frac{q(x)}{p(x)}\bigg)p(x)dx=\int_{X}g_{3}\bigg(\frac{q(x)}{p(x)}\bigg)p(x)dx

=\text{Reverse Pearson}_{g_{3}}(Q||P),

\text{Pearson}_{f_{4}}(P||Q)=\int_{X}\bigg(\bigg(\frac{p(x)}{q(x)}\bigg)^{2}-\frac{p(x)}{q(x)}\bigg)q(x)dx

=\int_{X}\bigg(\frac{p(x)}{q(x)}-1\bigg)p(x)dx=\int_{X}g_{4}\bigg(\frac{q(x)}{p(x)}\bigg)p(x)dx

=\text{Reverse Pearson}_{g_{4}}(Q||P).

对于 Jensen-Shannon Divergence(简写为 JSD)而言,f(x)=\frac{1}{2}\bigg\{(x+1)\ln\bigg(\frac{2}{x+1}\bigg)+x\ln(x)\bigg\},

\text{JSD}_{f}(P||Q)=\frac{1}{2}\int_{X}f\bigg(\frac{p(x)}{q(x)}\bigg)q(x)dx

=\frac{1}{2}\int_{X}\bigg\{\bigg(\frac{p(x)}{q(x)}+1\bigg)\ln\bigg(\frac{2q(x)}{p(x)+q(x)}\bigg)+\frac{p(x)}{q(x)}\ln\bigg(\frac{p(x)}{q(x)}\bigg)q(x)\bigg\}dx

=\frac{1}{2}\int_{X}\bigg\{p(x)\ln\frac{2p(x)}{p(x)+q(x)}+q(x)\ln\frac{2q(x)}{p(x)+q(x)}\bigg\}dx

=\frac{1}{2}\text{KL}(P||M)+\frac{1}{2}\text{KL}(Q||M),

其中 M=(P+Q)/2, i.e. m(x)=(p(x)+q(x))/2.

对于 Hellinger Distance 而言,f_{1}(x)=(\sqrt{x}-1)^{2}, f_{2}(x)=2(1-\sqrt{x}). 其实这两个函数是等价的,因为

\text{Hellinger Distance}_{f_{1}}(P||Q)=\int_{X}\bigg(\sqrt{\frac{p(x)}{q(x)}}-1\bigg)^{2}q(x)dx

=\int_{X}\bigg(p(x)+q(x)-2\sqrt{p(x)q(x)}\bigg)dx

=2-2\int_{X}\sqrt{p(x)q(x)}dx

=\int_{X}2\bigg(1-\sqrt{\frac{p(x)}{q(x)}}\bigg)q(x)dx

=\text{Hellinger Distance}_{f_{2}}(P||Q).

其中 BC(P,Q)=\int_{X}p(x)q(x)dx 被称为 Bhattacharyya 系数(Bhattacharyya Coefficient),Bhattacharyya 距离则定义为

D_{B}(P||Q)=-\ln(BC(P,Q))=-\ln\bigg(\int_{X}p(x)q(x)dx\bigg).

统计距离的上下界分析

对于以上函数而言,由于凸函数 f(1)=0, 因此当 P=Q 时,D_{f}(P||Q)=0.

KL 散度是没有上界的,但是 Jensen Shannon Divergence 是具有上界的。事实上,如果 M=(P+Q)/2, 则有

KL(P||M)=\int_{X}p(x)\ln\frac{2p(x)}{p(x)+q(x)}dx\leq\int_{X}p(x)\ln 2 dx=\ln2,

同样地,KL(Q||M)\leq \ln2, 所以可以得到 JSD(P||Q)\leq \ln2.

根据 Hellinger 距离的公式,可以得到:\text{Hellinger Distance}(P||Q)=2-\int_{X}\sqrt{p(x)q(x)}dx\leq 2. 同时,Bhattacharyya 距离 D_{B}(P||Q)=-\ln(BC(P||Q)) 是没有上界的,因为 BC(P||Q) 可以取值到零。

考虑 L^{p}- 范数中 p=1,2,\infty 三种情况:

||P-Q||_{1}=\int_{X}|p(x)-q(x)|dx\leq\int_{X}(p(x)+q(x))dx=2, 并且上界 2 是可以取到的。

||P-Q||_{2}=\sqrt{\int_{X}(p(x)-q(x))^{2}}=\sqrt{\int_{X}((p(x))^{2}-2p(x)q(x)+(q(x))^{2})dx}

\leq\sqrt{\int_{X}((p(x))^{2}+(q(x))^{2})dx}

\leq\sqrt{\int_{X}(p(x)+q(x))dx}=\sqrt{2}.

||P-Q||_{\infty}=\sup_{X}|p(x)-q(x)|dx\leq 1.

证明以上不等式使用了性质 0\leq p(x),q(x)\leq 1, \int_{X}p(x)dx=\int_{X}q(x)dx=1.

多重集合

多重集合的定义与性质

在数学中,集合(set)中不能够包含重复的元素,但一个多重集合(multiset)中则可以包含重复的元素,并且计算了元素的重数。例如,

  1. a\neq b 时,\{a,b\} 可以看成集合,也可以看成重数为 1 的多重集合,可以记为 \{a^{1},b^{1}\} 或者 \{1/a,1/b\}.
  2. 在多重集合 \{a,a,b\} 中,a 的重数是 2,b 的重数是 1,可以记为 \{a^{2},b^{1}\} 或者 \{2/a,1/b\}.
  3. 在多重集合 \{a,a,a,b,b,b\} 中,a,b 的重数都是 3。

对于一个有限集合 \{a_{1},\cdots,a_{n}\} 而言,其多重集合可以记为 \{a_{1}^{m(a_{1})},\cdots,a_{n}^{m(a_{n})}\} 或者 \{m(a_{1})/a_{1},\cdots,m(a_{n})/a_{n}), 其中 m(a_{i}) 表示元素 a_{i} 的重数。多重集合的一个典型例子就是质因数分解,例如:100=2^{2}\cdot 5^{2}.

假设多重集合 A,B 的元素都属于集合 U,

  1. 子集:如果对于所有的 x\in Um_{A}(x)\leq m_{B}(x), 则称多重集合 A 是多重集合 B 的子集;
  2. 交集:如果 \forall x\in U,m_{C}(x)=\min(m_{A}(x),m_{B}(x)), 则称多重集合 C 是多重集合 A,B 的交集,记为 C=A\cap B;
  3. 并集:如果 \forall x\in U,m_{C}(x)=\max(m_{A}(x),m_{B}(x)), 则称多重集合 C 是多重集合 A,B 的并集,记为 C=A\cup B;
  4. 求和:如果 \forall x\in U, m_{C}(x)=m_{A}(x)+m_{B}(x), 则称多重集合 C 是多重集合 A,B 的和,记为 C=A\oplus B;
  5. 求差:如果 \forall x\in U, m_{C}(x)=\max(0,m_{A}(x)-m_{B}(x)), 则称多重集合 C 是多重集合 A,B 的差,记为 C=A\ominus B.

假设 A=\{x^{2},y^{1},z^{3}\}, B=\{x^{1},y^{4},w^{3}\}, 那么

A\oplus B=\{x^{3},y^{5},z^{3},w^{3}\},

A\ominus B=\{x^{1},z^{3}\},

A\cap B=\{x^{1},y^{1}\},

A\cup B=\{x^{2},y^{4},z^{3},w^{3}\}.

多重集合的相似度和距离

由于已经定义了多重集合的交集和并集,因此集合相似度中的 Jaccard 相似度,Overlap 相似度都可以应用到多重集合中。

对于多重集合 A=\{a_{1}^{m(a_{1})},\cdots,a_{n}^{m(a_{n})}\} 而言,令 p_{i}=m(a_{i})/\sum_{i=1}^{n}m(a_{i}), 1\leq i\leq n. 因此,多重集合 A 对应了一个离散的概率分布 \{p_{1},\cdots,p_{n}\}. 于是,可以使用以上的统计距离(Statistical Distance)来计算两个多重集合之间的距离。

参考资料

  1. 统计距离:https://en.wikipedia.org/wiki/Statistical_distance
  2. f – divergence:https://en.wikipedia.org/wiki/F-divergence:包括了 KL 散度的其余变形方式。
  3. Bregman distance:https://en.wikipedia.org/wiki/Bregman_divergence
  4. Jensen Shannon Divergence:https://en.wikipedia.org/wiki/Jensen%E2%80%93Shannon_divergence
  5. KL Divergence:https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence
  6. Bhattacharyya distance:https://en.wikipedia.org/wiki/Bhattacharyya_distance
  7. Wasserstein metric:https://en.wikipedia.org/wiki/Wasserstein_metric
  8. 多重集合:multiset:https://en.wikipedia.org/wiki/Multiset

4 thoughts on “统计距离(statistical Distance)”

  1. 张博士,
    您好!
    我现在是一个在读的能源专业博士生,我一直在关注你的blog,感叹于自己数学方面的不足,在你的这里学到了非常多的东西。
    在看了你这篇统计距离和上一篇相似度的文章后,我把其中的数学模型用在了能源分析上。在翻看了你的reference之后,我还是有一些疑问,希望能烦劳你帮忙解答一下。
    我把Jaccard, overlap, dice 和 Pearson都用在了我的风电场发电数据分析上,希望能找到相关发电机组的相似性。但是我发现4个处理出来的结果,有一些结果的差异非常大。我翻看我专业的文章里面,大多数都是pearson,也就是matlab里面常用的corrcoef。
    我想咨询一下的就是,这四个不同的处理方式,我如何能从中找到他们之间的相似结论,也即,我希望通过4个不同的处理,找到运行结果类似的风场模型。
    非常感谢!
    此致
    敬礼
    杨士辰

    Like

    1. 风场数据我暂时不太了解。Jaccard / Overlap /Dice 主要是为了处理集合类型的数据,Pearson 可以处理序列型的数据。在不同的场景下,应该是需要使用不同的相似度指标来进行计算。在不同的时候,需要的相似度是不一样的。
      可以根据具体的场景来进行选择。

      Like

    2. 个人感觉四种相似度算法,得到的差异性较大应该是合理的,毕竟四种相似度算法描述的“相似度”是不一样的。选择一个最合适的即可。

      Like

Leave a Reply to shichen Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s