数据率失真理论（Rate distortion theory）或称信息率-失真理论（information rate-distortion theory）是信息论的主要分支，其的基本问题可以归结如下：对于一个给定的信源（source, input signal）分布与失真度量，在特定的码率下能达到的最小期望失真是多少；或者为了满足一定的失真限制，可允许的最大码率为何，$D$ 定义为失真的符号。

要完全避免失真几乎不可能。处理信号时必须允许有限度的失真﹐可减小所必需的信息率。1959年﹐Claude Shannon 首先发表《逼真度准则下的离散信源编码定理》一文，提出了率失真函数的概念。

我们通常都通过一个失真度量（distortion measure）来衡量一个随机变量以及它的表示（representation）之间的距离。下面以一个例子为开始，介绍具体的率失真理论中的一些定义与定理。

---

1. 一个例子

假设一个随机变量$X$，其一个表示定义为$\hat{X}(X)$，若我们使用$R$个比特（bit）来表示$X$，每个比特的数值为$0$或$1$，那么函数$\hat{X}$可以有$2^R$中不同取值，那么我们现在的问题是找到一个$\hat{X}$的最优值集（称为再生点（reproduction points）或码点（code points）），而目的是通过最小化定义的一个失真度量得到。

现在我们假设$X\sim \mathcal{N}\left(0,{\sigma }^2\right)$，同时假设一个平方误差的失真度量。目的则要通过最小化$E(X-\hat{X}(X){)}^2$从$2^R$个不同值中找到最优的$\hat{X}$。举一个简单的例子，假设我们现在只能用一个比特来表示，那么$\hat{X}$可以有两个不同的取值。由于分布是关于$0$对称的，因此我们将是否$X>0$作为两种不同取值的划分标准。为使平方误差达到最小，函数$\hat{X}$应该取其所在区域上$X$的条件均值。将正态分布截断的分布称为半正态分布（Half-normal distribution），其期望为：$\sqrt{2/\pi }\sigma$，因此有：
$$\hat{X}(x)=\{\begin{array}{ll}\sqrt{\frac{2}{\pi }}\sigma & \text{ if }x\ge 0,\\ -\sqrt{\frac{2}{\pi }}\sigma & \text{ if }x<0.\end{array}$$
而当比特数提升到两个甚至更多之后，区域的划分方法就不再这么简单了，需要将实轴划分为多个区域。但这些区域该如何划分，再生点应该怎样选取？为此，引入关于最优区域划分和再生点选取的两个性质：

• 给定一个再生点的集合 { X ^ ( w ) } \{\hat{X}(w)\} {X^(w)}，通过将源随机变量$X$映射到最接近它的表示$\hat{X}(w)$来最小化失真。由这个映射定义的$X$的区域集称为由再生点定义的Voronoi或Dirichlet划分（partition）。
• 再生点应该在各自划分到的区域上使条件期望失真最小化。

由上述两个性质可以得到一个简单算法：

1. 首先从某个再生点集合开始，找到最优的再生区域集（在失真度量下的最邻近的区域）；
2. 再确定出这些区域的相应最优再生点。

迭代重复上述两个步骤，直到算法收敛于失真的一个局部极小值。

---

2. 一些定义

前面的例子中假设需要量化的是单个随机变量，而通常实际情况中，我们通常假设$n$个独立同分布的随机变量集合，共需要$nR$比特来表示。

假设某信号源产生的序列（信源序列） $X_1,X_2,\cdots ,X_n\stackrel{i.i.d.}{\sim }p(x)$，信源序列$X^n$的编码用$f_n\left(X^n\right)\in \left\{1,2,\dots ,2^{nR}\right\}$进行表示，$X^n$的译码则用估计形式${\hat{X}}^n$表示。具体如下图所示：

失真函数/度量： 失真函数（distortion function）或失真度量（distortion measure）指从信源空间与再生空间的乘积空间到非负实数集上的映射：
$$d:\mathcal{X}\times \hat{\mathcal{X}}\to {\mathcal{R}}^{+}$$
失真函数$d(x,\hat{x})$是用来刻画使用$\hat{x}$表示$x$时的代价度量。

常用的失真函数

1. 汉明（Hamming）失真
   $$d(x,\hat{x})=\{\begin{array}{ll}0& \text{ 当 }x=\hat{x}\\ 1& \text{ 当 }x\ne \hat{x},\end{array}$$
   其期望$Ed(x,\hat{x})=\text{Pr}(X\ne \hat{X})$。直观上来理解，就是我们只关注原始字母与恢复字母是否相等，若相等，则失真为$0$，若不相等，则失真为$1$（无论多不相等均为$1$）。

2. 绝对值失真
   $$d(x,\hat{x})=\left|x-\hat{x}\right|$$

3. 平方误差失真
   $$d(x,\hat{x})=(x-\hat{x}{)}^2$$
   平方误差失真为最常用的一种失真函数（前面简单例子中所使用的度量）。其优点在于简单，且与最小二乘法联系紧密。但在某些如图像或语音编码等应用中，其并非是一个合适的度量，例如在很多图像与语音的编码中，两个图像或者语音人工看起来是一致的，但实际的平方误差相差会比较大。

序列失真： 序列$x^n$到${\hat{x}}^n$的失真定义为：
$$d\left(x^n,{\hat{x}}^n\right)=\frac{1}{n}\sum _{i=1}^{n}d\left(x_i,{\hat{x}}_i\right)$$
这种定义是一种平均值的定义，此外也可以定义为每个字符失真的最大值。

操作意义下信源的率失真码：一个$(2^{nR},n)$率失真码（rate distortion code）包括一个编码函数：
$$f_n:{\mathcal{X}}^n\to \left\{1,2,\dots ,2^{nR}\right\}$$
和一个译码（再生）函数：
$$g_n:\left\{1,2,\dots ,2^{nR}\right\}\to {\hat{\chi }}^n$$
这个$(2^{nR},n)$码的失真定义为
$$D=Ed\left(X^n,g_n\left(f_n\left(X^n\right)\right)\right)$$
其中所取的期望是针对$X$的概率分布而言，有：
$$D=\sum _{x^n}p\left(x^n\right)d\left(x^n,g_n\left(f_n\left(x^n\right)\right)\right)$$
将$n$元组 $g_n(1),g_n(2),\dots ,g_n\left(2^{nR}\right)$ 定义为 ${\hat{X}}^n(1),\dots ,{\hat{X}}^n(2^{nR})$，称为码簿（codebook），$f_n^{-1}(1),\dots ,f_n^{-1}\left(2^{nR}\right)$为分配区域（assignment regions），

下面为了刻画如何尽可能优的进行传输，提出了几个概念：

• 若存在一组率失真编码$(2^{nR},n)$，使得
  $$\underset{n\to \infty }{\lim }Ed\left(X^n,g_n\left(f_n\left(X^n\right)\right)\right)⩽D$$
  则称率失真对$(R,D)$是可达的。

• 信源的率失真区域是所有可达率失真对$(R,D)$的闭包（Closure）。

• 率失真函数（rate distortion function）：对于给定的一个失真度$D$，率失真函数$R(D)$定义为：
  R ( D ) = inf ⁡ { R : ( R , D ) ∈  率失真区域  } , R(D)=\inf \{R:(R, D) \in \text { 率失真区域 }\}, R(D)=inf{R:(R,D)∈ 率失真区域 },
  直观上理解就是在信源序列与再生序列的失真不超过$D$的前提下，最小可能的码率（信源最大可能的压缩率）。

• 失真率函数（distortion rate function）：给定一个码率$R$，定义失真率函数$D(R)$为：
  D ( R ) = inf ⁡ { D : ( R , D ) ∈  率失真区域  } , D(R)=\inf \{D:(R, D) \in \text { 率失真区域 }\}, D(R)=inf{D:(R,D)∈ 率失真区域 },
  含义为：在给定码率（压缩率）$R$条件下所能达到的最小失真。

---

下面我们通过引入互信息的概念，给出一种可计算形式的表达。互信息$I(X;\hat{X})$的含义是$\hat{x}$究竟代表了多少$x$中的信息，定义如下：
$$I(X;\hat{X})=\sum _{x\in \mathcal{X},\hat{x}\in \hat{\mathcal{X}}}p(x,\hat{x})\log \left(\frac{p(x,\hat{x})}{p(x)p(\hat{x})}\right)$$

而后我们将编码器与解码器看做一个整体，称为熵压缩编码器（类似信道的设置），其转移概率记为$q(\hat{x}|x)$，对一个给定的信源随机变量$X$，服从概率分布$p(x)$，此时输入与输出的平均失真可以记为
$$Ed(X,\hat{X})=\sum _{x\in \mathcal{X},\hat{x}\in \hat{\mathcal{X}}}p(x,\hat{x})d(x,\hat{x})=\sum _{x\in \mathcal{X},\hat{x}\in \hat{\mathcal{X}}}p(x)q(\hat{x}|x)d(x,\hat{x})⩽D$$
其中$p(x,\hat{x})$为$x$与$\hat{x}$的联合概率分布。

在分析信道容量的时候，是希望最大化$I(X;\hat{X})$，而在这里，我们是希望最小化$I(X;\hat{X})$，这样就可以使得通过熵压缩编码器的信息量尽可能小，以此来实现所需要使用的比特数尽可能的低。但是有一个前提约束，就是限制失真度量的最大值，而后再最小化这个互信息才有意义（不然$\hat{X}$会为一个常数）。

下面给出信息论意义下的率失真函数的定义（一个数学上的最优值）：
$$R^{(I)}(D)=\underset{q(\hat{x}\mid x):{\sum }_{(x,\hat{x})}p(x)q(\hat{x}\mid x)d(x,\hat{x})\le D}{\min }I(X;\hat{X})$$
需要注意信源压缩编码理论里面的一个基本设置是：信源的密度函数$p(x)$是给定的，而一般我们能够调整的是$q(\hat{x}\mid x)$。

---

率失真编码定理（Shannon第三定理）：
给定具有独立同分布$p(x)$的信源$X$和有界的失真度量$d(x,\hat{x})$，操作意义下的率失真函数等于信息论意义下的率失真函数，即：
$$R(D)=R^{(I)}(D)=\underset{q(\hat{x}\mid x):{\sum }_{(x,\hat{x})}p(x)q(\hat{x}\mid x)d(x,\hat{x})\le D}{\min }I(X;\hat{X})$$
是在失真约束$D$下可以达到的最小信息传输速率。

---

3. 率失真函数的性质

• $R^{(I)}(D)$是非增函数。当我们能够容忍的失真度逐渐增加时，率失真函数也就是传输的信息会逐步减小（或不变）。

• $R^{(I)}(D)$的定义域为$(D_{min},+\infty )$，且存在$D_{max}$，当$D\ge D_{max}$时，$R^{(I)}(D)=0$。也就是说，当我们能够容忍的失真到达一个程度后，就可以什么都不需要传了。

• $R(D)$是$D$的下凸函数。本质上是$I(p,q)$在$q$上是下凸的性质。

---

4. 率失真函数的两个常见例子

• $Bernoulli(p)$信源在汉明失真度量下的率失真函数为：
  R ( D ) = { H ( p ) − H ( D ) , 0 ⩽ D ⩽ min ⁡ { p , 1 − p } 0 , D > min ⁡ { p , 1 − p ∣ R(D)= \begin{cases}H(p)-H(D), & 0 \leqslant D \leqslant \min \{p, 1-p\} \\ 0, & D>\min \{p, 1-p \mid\end{cases} R(D)={H(p)−H(D),0,​0⩽D⩽min{p,1−p}D>min{p,1−p∣​

• 一个$\mathcal{N}\left(0,{\sigma }^2\right)$高斯信源在平方误差失真度量下的率失真函数为：
  $$R(D)=\{\begin{array}{ll}\frac{1}{2}\log \frac{{\sigma }^2}{D},& 0⩽D⩽{\sigma }^2\\ 0,& D>{\sigma }^2\end{array}$$

针对高斯信源，我们先将$R(D)$写成$D(R)$，
则$R(D)=\frac{1}{2}\log \frac{{\sigma }^2}{D}$可变为$D(R)={\sigma }^2{2}^{-2R}$。（注意，这里的$\log$均是以$2$为底的）。那么$1$比特的失真为$0.25{\sigma }^2$

这是有一个非常有趣的观察：在最开始的第一个例子，我们用$1$比特量化$\mathcal{N}\left(0,{\sigma }^2\right)$高斯分布的连续随机变量时，平均失真为$D={\int }_{-\infty }^{\infty }{\left(x-\hat{X}(x)\right)}^{2}p(x)dx=\frac{\pi -2}{\pi }{\sigma }^2\approx 0.3633{\sigma }^2$，这并不是最优的。因此，这表明我们如果将几个失真的问题结合在一起考虑，则可获得比单个分开考虑时更低的失真。（即使我们量化的是独立随机变量）

---

参考

1. Wiki: Rate–distortion theory
2. Thomas M. Cover, Joy A. Thomas (2006). Elements of Information Theory. John Wiley & Sons, New York.
3. 信息论基础（2017），叶中行