Shannon提出了简单的离散无记忆信源和信道模型,考虑独立同分布的(independently and identically distributed, i.i.d.)随机变量,采用渐近均分性(asymptotic equipartition property, AEP)给出了可靠通信的充要条件[1];但现实的信息处理过程中,常见的信源和信道是非平稳或有记忆的,Shannon信息论方案并不能直接应用。Han等[2⇓-4]提出信息谱方法(information-spectrum methods)构建了更一般的编码框架,分析非平稳信源的数据压缩或离散有记忆信道的信道编码等问题。Han[4-5]等也运用信息谱思想给出了大偏差概率理论中的假设检验问题,并通过谱散度率给出一般信源(包括非平稳或非遍历信源)第二类误差概率的最佳指数。信息谱方法还应用于通信理论的其他领域,如一般的Gelfand-Pinsker信道的容量问题[6]以及随机数的萃取[7]。文献[8⇓-10]将非独立同分布随机序列假设检验的方法运用到一般量子态序列的假设检验问题。Hayashi和Datta[11-12]各自用不同的方式将谱散度率推广到量子情形中,称之为量子谱散度率。量子谱散度率在量子纠缠度量和平滑熵中有很好的应用[13-14]。量子信息谱在经典-量子信道容量[11]、量子信源编码[15]、带限制边信息的经典-量子信道编码[16]、有限码长的二阶情形[17]等方面应用广泛。
无论是经典还是量子情形下的信息谱方法,均为码长n充分大时的渐近情形。当n充分大时,在实际中由于设备等限制,不可能达到理论预期,必然产生误差。因此,有必要考虑非渐近的情形,即有限码长或者有限次信道使用。在one-shot信息论框架中,一次只使用单一的信源或信道,在允许容忍误差的条件下,讨论信源压缩和信道编码。one-shot情形下的Tomamichel等[18]给出了信息谱相对熵(information-spectrum relative entropy),并给出了信息谱相对熵在i.i.d.情形下的极限形式。特别地,Anshu等[19]给出另一类谱散度率的定义,得到了它与平滑最大信息的关系,并将其应用到态的分离情形。在one-shot情形下,信息谱方法也应用于随机数萃取[18,20]以及具有量子边信息的信源压缩的可达界[21]研究。
信息谱相对熵的本质是概率分布的对数似然比,而相对熵是对数似然比的期望,且用Shannon熵定义的信息度量都完全可以由相对熵来刻画。受此启发,本文考虑用信息谱相对熵来定义信息谱条件熵和信息谱互信息。在Shannon熵的理论框架中,由于Bayes规则,条件熵的链式法则(chain rules)[22]在信源编码和信道编码中有非常重要的应用。目前,关于信息谱应用的研究相对较多,而对于信息谱相对熵本身的研究相对少且不完整,并且没有得到系统的讨论。因此,本文首先给出one-shot情形下的信息谱相对熵定义,并详细讨论了其性质。特别地,讨论信息谱相对熵与假设检验相对熵的关系。研究表明,在误差容忍的情况下,这两个量化是等价的。基于信息谱相对熵刻画了信息谱条件熵和信息谱互信息,得到了一些有意义的性质。由于信息谱互信息存在不同的定义方式,本文重点讨论了不同定义互信息之间的关系,进而给出了它们的链式关系。
1 信息谱相对熵
在Shannon信息论框架中,很多结果都依赖于渐近均分性。若随机变量序列X1,X2,…,Xn服从独立同分布,由大数定律可知,随机变量的函数依概率收敛于Shannon熵,即
log →H(X)。
(X)=inf ,
H(X)=sup 。
熵率的概念在Shannon信息论也是常见的量化,谱熵率在非独立同分布情形下有很好的研究[4]。在独立同分布情形下,相对熵给出渐近情形下非对称假设检验误差概率的最佳指数。类似于Shannon熵,同样可以考虑非独立同分布情形下的相对熵形式。对于非独立同分布情形,对2个分布PX={ 和 如何区分?在信息谱的理论中,随机变量序列对数似然比 log 称为散度密度率,对散度密度率进行概率极限运算得到上谱散度率(spectral sup-divergence rate)和下谱散度率(spectral inf-divergence rate)[4-5]。具体地,对于随机变量序列PX和QX,上、下谱散度率为
(PX‖QX)=inf ,
和
D(PX‖QX)=sup 。
对于上、下谱散度率,一般情形下有D(PX‖QX)≤ (PX‖QX)。谱散度率可用于刻画非平稳无记忆或非遍历的随机变量序列假设检验问题,并给出第二类误差概率和正确检验概率的最佳指数[4]。对于具体信息任务的处理,上、下谱散度率并不能解决一些实际问题,从而一些学者考虑有限码长的情形。Tomamichel等[18]给出了one-shot的下谱散度率,即下信息谱相对熵(information-spectrum inf-relative entropy)。最近,Anshu等[19]给出了one-shot的上谱散度率,即上信息谱相对熵(information-spectrum sup-relative entropy)。
定义1 给定一个概率分布PX及次归一化概率分布QX(概率分布求和小于等于1),对于ε∈[0,1],上、下信息谱相对熵分别定义为
(PX‖QX)=inf ,
和
D (PX‖QX)=sup 。
上、下信息谱相对熵在随机数萃取和具有边信息的信源压缩中有很好的应用。但是,对于这2个量化,只针对具体问题给出了应用,它们本身的性质并没有得到详细研究。比如,经典信息论中,依赖相对熵可给出条件熵、互信息以及信息处理不等式等。本文将详细讨论其性质。
命题1 对2个概率分布PX和QX,且ε∈[0,1],有
1)当ε'≥ε,有
(PX‖QX)≥ (PX‖QX),
D (PX‖QX)≤D (PX‖QX);
2)对于常数c>0,有
(PX‖cQX)= (PX‖QX)-log c,
D (PX‖cQX)=D (PX‖QX)-log c;
3)若存在概率分布Q'≥Q,则有
(PX‖Q'X)≤ (PX‖QX),
D (PX‖Q'X)≤D (PX‖QX)。
证明 由于 (PX‖QX)和D (PX‖QX)运算相似,只考虑上信息谱相对熵的证明。首先考虑不等式(7)。当ε'≥ε时,不妨设 (PX‖QX)=γ,则有
<ε≤ε'。
根据上信息谱相对熵的定义直接可得
(PX‖QX)≤γ= (PX‖QX)。
为了证明等式(9),对于常数c>0,不妨设 (PX‖cQX)=γ,则有
=
<ε。
根据上信息谱相对熵的定义可得
(PX‖QX)≤γ+log c=
(PX‖cQX)+log c。
同理可得,
(PX‖cQX)≤ (PX‖QX)-log c。
最后,给出关系式(11)的证明。不妨设 (PX‖QX)=γ,由于Q'≥Q,结合上信息谱相对熵的定义可得
≤
<ε。
从而可得, (PX‖QX)≥ (PX‖Q'X)。
为了讨论one-shot情形下假设检验相对熵和信息谱相对熵之间的关系,首先给出假设检验相对熵的定义[23]。
定义2 对于概率分布PX和次归一化概率分布QX,对于ε>0,假设检验相对熵定义为
(PX‖QX)=max {-log( {S})|S⊆X, {S}≥1-ε}。
下面给出信息谱相对熵近似等价于假设检验相对熵。
命题2 给定概率分布PX及次归一化概率分布QX,对于δ、η>0,0<ε<1且0<δ+ε<1,则有
(PX‖QX)-η≤ (PX‖QX)≤ (PX‖QX)-log δ,
D (PX‖QX)≤ (PX‖QX)≤D (PX‖QX)-log δ。
证明 首先证明不等式(14)的下界。设γ= (PX‖QX)-η,对于某些任意的η>0可使得集合S= 满足
≥1-ε。
结合 (PX‖QX)的定义可得
≤
2-γ ≤2-γ。
由此可推出
(PX‖QX)≥γ= (PX‖QX)-η。
对于上界,不失一般性,设 (PX‖QX)<∞,取S是满足 (PX‖QX)的最佳概率分布集合, 则
{S}= 。
对于任意实数r,有
1-ε≤ {S}= {S}-2r {S}+2r {S}= (PX(x)-2rQX(x))+ ≤ + 。
取r= (PX‖QX)+ξ,则∀ξ>0,有
≤1-ε-δ。
结合不等式(17)及不等式(18),可得
log δ≤ (PX‖QX)+ξ- (PX‖QX)。
当ξ→0时,不等式得证。
为了证明关系式(15),首先考虑左边不等式。 不妨设γ=D (PX‖QX)-ξ,∀ξ>0,设S= 是满足 (PX‖QX)的一个概率分布集合,有
{S}= ≤
2-γ ≤2-γ。
从而有 (PX‖QX)≥γ。因此,当ξ→0时,得到关系式(15)的左边情形。
为证明右边不等式,不妨设r= (PX‖QX)+log δ,当 (PX‖QX)<∞时,记S为满足 (PX‖QX)的最佳概率分布集合,则
{S}=2-r·δ。
进而有
= PX(x)≥
(PX(x)-2rQX(x))≥
(PX(x)-2rQX(x))=
{S}-2r {S}≥
1-ε-δ。
从而可得D (PX‖QX)≥r,进而完成证明。
在经典信息论中,一对随机变量的两个联合分布PXY和QXY之间的相对熵可以表示为相对熵与条件相对熵的和,通常称之为相对熵的链式关系[22],即
D(PXY‖QXY)=D(PX‖QX)+D(PY|X‖QY|X),
其中D(PY|X‖QY|X)是条件相对熵,且
D(PY|X‖QY|X)= PX(x)D(PY|X(y|X=x)‖QY|X(y|X=x))。
定义3 给定条件概率分布PY|X和QY|X,对于ε∈[0,1],上、下信息谱条件相对熵定义为
(PY|X‖QY|X)=inf { γ∈R 2γ}<ε},
D (PY|X‖QY|X)= sup {γ∈R 2γ}>1-ε}。
由于涉及极限和参数不等式,上、下信息谱条件相对熵并不具有像条件相对熵一样的链式关系,只能给出一个类似的情形,下面给出信息谱相对熵的链式关系。
命题3 2个联合分布PXY和QXY,对于0<ε1+ε2≤1,有
(PXY‖QXY)≤ (PX‖QX)+ (PY|X‖QY|X),
D (PXY‖QXY)≥D (PX‖QX)+D (PY|X‖QY|X),
式中ε=ε1+ε2。
证明 为了证明关系式(23),不妨设a1= (PX‖QX),且S1={(x,y)|PX(x)≥ QX(x)},设a2= (PY|X‖QY|X),且S2={(x,y)|PY|X(y|x)≥ QY|X(y|x)}。进一步有
S2= ,
显然,对(x,y)∈S1∪S2,有PXY(x,y)≥ QXY(x,y)。因此,可得
{S1∪S2}=
{PXY(x,y)≥ QXY(x,y)}≤
{S1}+ {S2}≤ε1+ε2。
根据 (PXY‖QXY)的定义,得到关系式(23)。同理可证关系式(24)。
2 信息谱条件熵和互信息
在Shannon信息论中,Shannon熵、条件熵以及互信息都可以由相对熵表示。结合前面的讨论,本节将考虑使用信息谱相对熵来刻画one-shot情形下的条件熵和互信息,并给出相应的性质。
定义4 给定概率分布PX,对于ε∈(0,1),上、下信息谱熵分别定义为
(X)=-D (PX‖1X)=inf ,
H (X)=- (PX‖1X)=sup ,
式中1X(x)=1,∀x∈X。
显然,这里上信息谱熵和下信息谱熵也是上谱熵率(1)和下谱熵率(2)在one-shot情形下的形式。下面给出one-shot情形的条件熵。
定义5 给定联合概率分布PXY,以及相应的边际概率分布PY,对于ε∈[0,1],上、下信息谱条件熵分别定义为
$\begin{aligned}&\overline{H}_{s}^{\varepsilon}(X\mid Y)=-\underline{D}_{s}^{\varepsilon}(P_{xY}\parallel1_{X}\times P_{Y})= \\&\inf\Big\{\gamma\in\left.\mathbf{R}\right|_{(x,y)\leftarrow P_{XY}}\Big|\frac{P_{XY}(x,y)}{1_{X}(x)\times P_{Y}(y)}> \\&\left.2^{-\gamma}\right\}>\left.1-\varepsilon\right\},& \end{aligned}$
$ \begin{array}{l}\underline{H}_{s}^{\varepsilon}(X \mid Y) \stackrel{\mathrm{d}}{=}-\bar{D}_{s}^{\varepsilon}\left(P_{X Y} \| 1_{X} \times P_{Y}\right)= \\\sup \left\{\gamma \in \mathbf{R} \mid \underset{(x, y) \leftarrow P_{X Y}}{P}\left\{\frac{P_{X Y}(x, y)}{1_{X}(x) \times P_{Y}(y)}>\right.\right. \\\left.\left.2^{-\gamma}\right\}<\varepsilon\right\} 。 \\\end{array}$
由于条件Bayes概率,在Shannon信息论中,有
H(X|Y)=H(XY)-H(Y)。
该等式也称为熵的链式法则。结合定义以及概率不等式,下面给出信息谱条件熵的链式关系。
命题4 对于联合概率分布PXY,及边际概率分布PY,若0<ε1+ε2≤1,则
(X|Y)≤ (XY)-H (Y),
式中ε=ε1+ε2。
证明 不妨取 (XY)=a1,且S1={(x,y)|PXY(x,y)≤ 1XY(x,y)},同时取H (Y)=a2,且S2={(x,y)|PY(y)≥ 1Y(y)},进而对于集合S1∪S2,有
{S1∪S2}=
{PXY(x,y)≤ 1X(x)×
PY(y)}≤ {S1}+ {S2}≤
ε1+ε2。
根据 (X|Y)的定义,进而命题得证。
类似上信息谱条件熵,容易得到下信息谱条件熵的链式关系。
命题5 对于联合概率分布PXY及边际概率分布PY,若0<ε1+ε2≤1, 有
H (X|Y)≥H (XY)- (Y),
式中ε=ε1+ε2。
由于涉及参数与概率不等式,一般情况下很难得到等号成立的关系,目前得到的结果有助于理解不同信息谱熵之间的关系,并期望能在具体信息处理尤其是one-shot情形下的随机数萃、信道编码以及多址接入信道中得到应用。最后,考虑与相对熵相关联的另一个重要量化——互信息。
定义6 给定联合概率分布PXY和相应的边际概率分布PX,对于ε∈[0,1],则上、下信息谱互信息分别定义为
$ \begin{array}{l}\bar{I}_{s}^{\varepsilon}(X: Y) \stackrel{\mathrm{d}}{=} \bar{D}_{s}^{\varepsilon}\left(P_{X Y} \| P_{X} \times P_{Y}\right)= \\\inf \left\{\gamma \in \mathbf{R} \mid \underset{(x, y) \in P_{X Y}}{P}\left\{\frac{P_{X Y}(x, y)}{P_{X}(x) \times P_{Y}(y)}\right\rangle\right. \\\left.\left.2^{\gamma}\right\}<\varepsilon\right\}, \\\end{array}$
$ \begin{array}{l}\underline{I}_{s}^{\varepsilon}(X: Y) \stackrel{\mathrm{d}}{=} \underline{D}_{s}^{\varepsilon}\left(P_{X Y} \| P_{X} \times P_{Y}\right)= \\\sup \left\{\gamma \in \mathbf{R} \mid \underset{(x, y) \in P_{X Y}}{P}\left\{\frac{P_{X Y}(x, y)}{P_{X}(x) \times P_{Y}(y)}>\right.\right. \\\left.\left.2^{\gamma}\right\}>1-\varepsilon\right\} 。 \\\end{array}$
由于信息谱相对熵是非负的,显然,易知信息谱互信息也非负。Shannon相对熵是一个信息距离度量,从而互信息可以看做是给定联合分布到不同乘积分布集合上的最小相对熵。结合相对熵的性质,可以给出互信息的4种等价定义。但是,这种描述在广义熵中并不存在等价定义,比如Renyi相对熵以及量子版本的各类Renyi相对熵。最后,利用信息谱相对熵来讨论互信息的不同定义并建立它们的关系。
定义7 给定联合概率分布PXY、边际分布PX以及次归一化概率分布QX和QY,对于ε∈[0,1],信息谱互信息可定义为
(X:Y)P|Q= (PXY‖PX×QY),
I (X:Y)P|Q= D (PXY‖PX×QY),
(X:Y)Q|Q= (PXY‖QX×QY),
I (X:Y)Q|Q= D (PXY‖QX×QY)。
注意,这里并没有考虑关于随机变量X的最小化定义,显然它们的定义及相关性质与随机变量Y的情形类似。同时,如果最小化在联合概率分布的边际概率上可达,就类似于常见的Shannon互信息。下面给出上述4类互信息的序关系。
命题6 给定联合概率分布PXY、边际分布PX以及次归一化概率分布QX和QY,对于0<ε+δ≤ε+δ+η<1,有
(X:Y)Q|Q≥ (X:Y)P|Q-log ≥ (X:Y)-log -log ,
I (X:Y)Q|Q≥I (X:Y)P|Q-log ≥I (X:Y)-log -log 。
证明 由于上、下信息谱互信息定义相似,故只考虑上信息谱互信息的证明。为了证明关系式(38),首先考虑 (X:Y)Q|Q和 (X:Y)P|Q之间的关系。设 (X:Y)Q|Q=a,且S1={(x,y)|PXY(x,y)≥2aQX(x)QY(y))。令S2={(x,y)|QX(x)> PX(x)},由边际概率分布可知,
{S2}=
=
PX(x)≤δ QX(x)≤δ。
$ \begin{aligned}\underset{(x, y) \leftarrow P_{X Y}}{P} & \left\{S_{1} \cup S_{2}\right\}= \\& \underset{(x, y) \leftarrow P_{X Y}}{P}\left\{P_{X Y}(x, y) \geqslant\right. \\& \left.\frac{2^{a}}{\delta} P_{X}(x) \times Q_{Y}(y)\right\} \leqslant \\& \underset{(x, y) \leftarrow P_{X Y}}{P}\left\{S_{1}\right\}+\underset{(x, y) \leftarrow P_{X Y}}{P}\left\{S_{2}\right\} \leqslant \varepsilon+\delta 。\end{aligned}$
由此可得, (X:Y)Q|Q≥ (X:Y)P|Q-log 。
对于 (X:Y)P|Q和 (X:Y)之间的关系,不妨设 (X:Y)P|Q=b,且S3={(x,y)|PXY(x,y)≥2bPX(x)QY(y)}。假设
S4= ,
可得
{S4}≤η。
对于(x,y)∈S3∪S4,有
{S3∪S4}=
≤
{S3}+ {S4}≤ε+δ+η。
显然, (X:Y)P|Q≥ (X:Y)-log ,进而关系式(38)得证。
该结果说明,由于取优化不同而导致的不同互信息,它们之间依赖于某个参数。在给定参数下,可以看做它们是等价的。有了信息谱熵、信息谱条件熵以及信息谱互信息,自然地可以给出类似于Shannon熵、条件熵以及互信息之间的关系,即
I(X:Y)=H(X)-H(X|Y)。
结合命题4和命题5的证明过程,对于0<ε1+ε2≤1,有
(X:Y)≤ (X)-H (X|Y),I (X:Y)≥H (X)- (X|Y),
式中ε=ε1+ε2。
3 结语
信息谱方法不仅拓展了Shannon信息论和量子信息论的研究领域,而且为信息处理提供了新的理论框架。本文研究了信息谱相对熵的性质,以及信息谱相对熵与假设检验相对熵的关系。特别地,建立了信息谱相对熵的链式关系。基于信息谱相对熵定义了信息谱条件熵和信息谱互信息,分别给出了它们之间的链式关系。信息谱互信息并不同于Shannon互信息的单一形式,它存在不同的定义方式,本文也得到了不同信息谱互信息之间的等价关系。随着量子信息技术的发展,在量子信息处理中也会遇到非独立同分布的情形,但是由于量子态的非对易性,将经典的结论直接推广到量子情形目前还存在困难。虽然前人已经给出量子信息谱相对熵的一些应用,但本文中关于量子信息谱相对熵的链式关系至今没有解决。因此,下一步将考虑量子信息谱相对熵的链式关系。