差分隐私（二）

本文将介绍差分隐私中和熵相关的概念。

Renyi Entropy

熵在密码学中有很多应用，比如说常见的香农熵和Hartley Function，它们都是由Renyi Entropy推广得到的：

$H_{\alpha}(X)=\frac{1}{1-\alpha}log(\Sigma_{i=1}^np_i^{\alpha}),\ \alpha \ge0,\ \alpha\ne1$

至于说Renyi Entropy是如何得到其他熵的？是不同的$\alpha$对应不同的熵

如果将$p$看成向量，括号里的形式实际上可以被看成向量的$\alpha$范数

$H_{\alpha}(X)=\frac{1}{1-\alpha}log(\Sigma_{i=1}^np_i^{\alpha})=\frac{\alpha}{1-\alpha}log\| p \| _{\alpha}$

Hartley Function or max-entropy

当$\alpha=0$时，$H_0(X)$实际上就是Hartley熵

$H_{\alpha}(X)=\frac{1}{1-0}log(\Sigma_{i=1}^np_i^{0})=log\ n$

他表示的意思是：如果从有限集合A中均匀随机地选取样本，则已知结果后所揭示的信息由哈特利函数给出。

哈特利使用了以十为底的对数，以这个底数，信息单位被称为哈特利（又名ban或dit）以纪念他。它也称为哈特利熵或最大熵。

Shannon entropy

当$\alpha \rarr 1$时，$H_1{X}$实际上就是Shannon熵

$H_1(X)=\lim_{\alpha \rarr 1} \frac{1}{1-\alpha}log(\Sigma_{i=1}^np_i^{\alpha})$

$H_1(X)=\lim_{\alpha \rarr 1} \frac{1}{-1} \frac{\Sigma_{i=1}^n p_i^{\alpha}\ln p_i}{\Sigma_{i=1}^np_i^{\alpha}}=-\Sigma_{i=1}^n p_i \ln p_i$

Renyi Divergence

Divergence并不是距离，因为不满足距离定义中的对称性，但是我们仍然可以用它来衡量两个分布之间的差距，比如常用的KL-Divergence。而和Renyi Entropy一样，Renyi Divergence也是KL-Divergence和Max-Divergence的推广。

$D_{\alpha}(p\| Q)=\frac{1}{\alpha-1}\log (\Sigma_{i=1}^n q_i \frac {p_i^{\alpha}}{q_i^{\alpha}})$

KL Divergece

当$\alpha \rarr 1$

$D_{\alpha}(p\| Q)=\frac{1}{\alpha-1}\log (\Sigma_{i=1}^n q_i \frac {p_i^{\alpha}}{q_i^{\alpha}})$

$D_{1}(p\| Q)=\log \Sigma_{i=1}^n p_i \frac {p_i}{q_i}$

Max Divergence

当$\alpha \rarr \infty$

$D_{\infty}(p\| Q)=\lim_{\alpha \rarr \infty}\frac{1}{\alpha-1}\log (\Sigma_{i=1}^n q_i \frac {p_i^{\alpha}}{q_i^{\alpha}})=\log \max \frac{p_i}{q_i}$

3 - 差分隐私中的Divergence

从Max-Divergence可以看到，当对这个Max-Divergence进行约束之后：

$D_{\infty}(P\| Q)=\log \max \frac{p_i}{q_i}$

$\frac {Pr(A(x)=t)}{Pr(A(x^\prime)=t)} \le exp(\varepsilon)$