本文将介绍差分隐私中和熵相关的概念。
Renyi Entropy
熵在密码学中有很多应用,比如说常见的香农熵和Hartley Function,它们都是由Renyi Entropy推广得到的:
Hα(X)=1−α1log(Σi=1npiα), α≥0, α=1
至于说Renyi Entropy是如何得到其他熵的?是不同的α对应不同的熵
如果将p看成向量,括号里的形式实际上可以被看成向量的α范数
Hα(X)=1−α1log(Σi=1npiα)=1−ααlog∥p∥α
Hartley Function or max-entropy
当α=0时,H0(X)实际上就是Hartley熵
Hα(X)=1−01log(Σi=1npi0)=log n
他表示的意思是:如果从有限集合A中均匀随机地选取样本,则已知结果后所揭示的信息由哈特利函数给出。
哈特利使用了以十为底的对数,以这个底数,信息单位被称为哈特利(又名ban或dit)以纪念他。它也称为哈特利熵或最大熵。
Shannon entropy
当α→1时,H1X实际上就是Shannon熵
H1(X)=α→1lim1−α1log(Σi=1npiα)
H1(X)=α→1lim−11Σi=1npiαΣi=1npiαlnpi=−Σi=1npilnpi
Renyi Divergence
Divergence
并不是距离,因为不满足距离定义中的对称性
,但是我们仍然可以用它来衡量两个分布之间的差距,比如常用的KL-Divergence
。而和Renyi Entropy
一样,Renyi Divergence
也是KL-Divergence
和Max-Divergence
的推广。
Dα(p∥Q)=α−11log(Σi=1nqiqiαpiα)
KL Divergece
当α→1
Dα(p∥Q)=α−11log(Σi=1nqiqiαpiα)
D1(p∥Q)=logΣi=1npiqipi
Max Divergence
当α→∞
D∞(p∥Q)=α→∞limα−11log(Σi=1nqiqiαpiα)=logmaxqipi
3 - 差分隐私中的Divergence
从Max-Divergence
可以看到,当对这个Max-Divergence
进行约束之后:
D∞(P∥Q)=logmaxqipi
Pr(A(x′)=t)Pr(A(x)=t)≤exp(ε)