DP-指數機制

作者：由 DPer 發表于攝影時間：2019-05-16

我們之前介紹了著名的Laplace機制。在本章節中我們將介紹一下同樣著名的指數機制。

指數機制與Laplace機制

如何實現指數機制

應用案例

指數機制的理論證明

指數機制與Laplace機制

在Laplace機制中，我們首先對資料庫進行查詢，然後再查詢結果之上新增一定的噪聲使其滿足DP的要求。因此，返回的資料通常只是“接近準確”的。那麼差分隱私能否允許我們得到真實的結果呢？在這種情況下，指數機制應運而生。

指數機制（The exponential mechanism）是為我們希望選擇“最佳”響應的情況而設計的，但直接在計算數量上新增噪聲可以完全破壞其價值。例如在拍賣中設定價格，其目標是最大化收益，以及在最優價格上新增少量正噪聲（為了保護投標的隱私）可以大大減少由此產生的收入。為了理解接下來我們舉個例子：

假設我們有大量的南瓜和四個投標人：A，B，C，D，其中A，B，C各自出價1。00美元，D出價3。01美元。如何制定最優出售價格？假如以 3。01美元出售，則收入為3。01美元（只有D買）；以1。00美元出售，收入為3。00美元（ABC購買）；以3。02美元出售，收入為零！

在這個案例中，每個使用者的投標價格是涉及個人隱私的，而對於價格來說，我們自然不希望是加噪聲了的。畢竟誰也不希望本來可以3美元出手的南瓜最後只賣了2美元。

如何實現指數機制

指數機制適用於回答具有任意實用程式（和任意非數字範圍），同時保留差異隱私。給定一些任意範圍

$\mathcal{R}$

，首先我們需要定義一個實用性函式

$\mu$

：

$\mu: \mathbb{N}^{|\mathcal{X}|} \times \mathcal{R} \rightarrow \mathbb{R} \\$

簡單來說，這裡

$\mu$

的作用就是給使用者擁有的資料打個分，分越高，表示這個資料越重要（比如上述案例中的價格，可以直接作為

$\mu$

看待）。因此對於資料集

，我們希望選取的元素有最大效益。

和 Laplace 機制一樣，我們需要知道

$\mu$

最多改變多少，所以我們定義：

$\triangle u = \max \limits_{r \in \mathcal{R}, ||x-y||_1 \le 1} |u(x,r)-u(y,r)|\\$

設計指數機制的出發點即為對於任意的

，按照

$\exp(\epsilon u(x,r)/\triangle \mu)$

的機率選取最優解即可滿足差分隱私要求，因為：

$\ln \frac{\exp(\epsilon \cdot u(x,r)/\triangle u)}{\exp (\epsilon \cdot u(y,r) / \triangle \mu)} = \epsilon [u(x,r)-u(y,r)]/\triangle u \le \epsilon\\$

所以就有了我們的指數機制了：

The Exponential Mechanism： The exponential mechanism

$\mathcal{M}_E(x,u,\mathcal{R})$

selects and outputs an element

$r\in \mathcal{R}$

with probability proportional to

$\exp(\frac{\epsilon\cdot u(x,r)}{2\triangle u})$

翻譯過來就是：設隨機化演算法

輸入為資料集

，輸出為一個實體物件

$r\in\mathcal{R},\mu(X,\mathcal{R})$

為可用性函式，

$\triangle \mu$

為函式

$\mu(x,\mathcal{R})$

的敏感度，若以正比於

$\exp(\frac{\epsilon\cdot u(x,r)}{2\triangle u})$

的機率從輸入中選擇並輸出

，則演算法

是

$\epsilon$

-DP的。

應用案例

假設某基地正在舉辦一場體育比賽，可以選擇的專案有{足球，排球，籃球，網球}四個專案，參與者們對這些專案進行投票，現在要確定一個專案是的整個決策過程滿足$\epsilon$-DP，以每個選項的得票數量作為可用性函式，在給定隱私預算情況下，可以計算選擇各個專案的輸出機率：

上述案例中，當

$\epsilon = 0$

時，提供完全的隱私保護但資料可用性為0，隨著

$\epsilon$

越大，選擇出期望結果的可能性也越大。

指數機制的理論證明

此部分涉及指數機制的理論證明，不感興趣的可以直接跳過。

$\begin{align} \frac{\Pr[\mathcal{M}_E(x,u,\mathcal{R})=r]}{\Pr[\mathcal{M}_E(y,u,\mathcal{R})=r]} &= \frac{(\frac{\exp(\frac{\epsilon u(x,r)}{2\triangle u})}{\sum_{r$