Statistics

统计距离（statistical Distance）

4 Comments

统计距离（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 中的两个概率分布 P 和 Q 而言，

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

定义了概率分布 P 和 Q 的 f- 散度（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}-x 和 g_{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 U 有 m_{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

Advertisement

4 thoughts on “统计距离（statistical Distance）”

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

    Like

    Reply

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

      Like

      Reply

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

      Like

      Reply

Leave a Reply

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

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com 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 )

Cancel

Connecting to %s