【我們為什麼用高斯機制？】差分隱私程式碼實現系列（七）

作者：由粥少女的擰發條鳥發表于攝影時間：2021-12-07

差分隱私程式碼實現系列（七）

寫在前面的話

書上學來終覺淺，絕知此事要躬行

。

回顧

1、函式的靈敏度反映了函式的輸出在其輸入更改時將更改的量。

2、這種敏感度度稱為"全域性"，因為它獨立於所查詢的實際資料集（它適用於相鄰#FormatImgID_1# 和#FormatImgID_2#的任何選擇）。

3、這個想法在某些情況下很容易形式化（例如，在美國人口普查中，每個人都提交包含其資料的單個響應），但在其他上下文中（例如位置軌跡，社交網路和時間序列資料）極具挑戰性。

4、根據經驗，當被求和屬性的值不存在下限和上限時，求和查詢具有無限的敏感度。

5、具有無限敏感度的查詢無法使用拉普拉斯機制使用差分隱私直接回答。

6、裁剪的基本思想是對屬性值強制實施上限和下限。

7、此外，在裁剪中丟失的資訊量與確保差分隱私所需的噪聲量之間存在權衡。當上下裁剪邊界靠得更近時，靈敏度較低，需要的噪聲更小，以確保差分隱私。但是，激進的剪下通常會從資料中刪除大量資訊。這種資訊丟失往往會導致準確性的損失，這超過了靈敏度降低導致的噪聲改善的程度。根據經驗，請嘗試將剪下邊界設定為包含 100% 的資料集，或儘可能接近。在某些領域（例如，圖查詢，我們稍後將研究）比其他領域更難。

8、請注意，對於最大的裁剪引數，總和會劇烈波動！關鍵是要尋找圖形中相對平滑（意味著低噪聲）且不增加（意味著裁剪邊界足夠）的區域。

鬆弛差分隱私（Approximate Differential Privacy）

鬆弛差分隱私，也稱為

$(\epsilon, \delta)$

-差分隱私，具有以下定義：

$\mathsf{Pr}[F(x) = S] \leq e^\epsilon \mathsf{Pr}[F(x$

新的隱私引數

$\delta$

表示定義的“失敗機率”。

有了機率

$1-\delta$

，我們將得到與純差分隱私相同的保證；對於機率

$\delta$

，我們得不到保證。

換句話說：機率

$1-\delta$

下，

$\frac{\mathsf{Pr}[F(x) = S]}{\mathsf{Pr}[F(x$

。

對於機率

$\delta$

，我們根本得不到保證。

這個定義應該看起來有點嚇人！有了機率

$\delta$

，任何事情都可能發生。包括整個敏感資料集的釋出！

因此，我們通常要求

$\delta$

非常小，通常為

$\frac{1}{n^2}$

或更小，其中

是資料集的大小。

此外，我們還將看到，實踐使用中的

$(\epsilon, \delta)$

差分私有機制不會像定義所允許的那樣災難性地失敗。相反，它們會優雅地失敗，並且不會執行諸如釋放整個資料集之類的可怕事情。

那麼滿足鬆弛差分隱私的機制存在嗎？高斯來了~

高斯機制（The Gaussian Mechanism）

高斯機制是拉普拉斯機制的替代方案，不同在於加的是高斯噪聲而不是拉普拉斯噪聲。

高斯機制不滿足純

$\epsilon$

-差分隱私，但滿足

$(\epsilon, \delta)$

-差分隱私。

根據高斯機制，對於返回數字的函式

，以下

定義滿足

$(\epsilon, \delta)$

-差分隱私：

$F(x) = f(x) + \mathcal{N}(\sigma^2)\\ \text{where } \sigma^2 = \frac{2s^2 \log(1.25/\delta)}{\epsilon^2}$

其中

是

的敏感度，而

$\mathcal{N}(\sigma^2)$

表示從中心為 0 且方差

$\sigma^2$

的高斯（正態）分佈抽樣。

請注意，對於實值函式

$f : D \rightarrow \mathbb{R}$

，我們可以與拉普拉斯機制完全相同的方式使用高斯機制，並且很容易比較在給定值

$\epsilon$

的兩種機制下發生的情況。

說起來可能不直觀，直接上程式碼！

matplotlib

inline

import

matplotlib。pyplot

plt

。

style

。

use

（

‘seaborn-whitegrid’

）

import

pandas

import

numpy

epsilon

vals_laplace

［

。

random

。

laplace

（

loc

，

scale

epsilon

）

for

range

（

100000

）］

delta

10e-5

sigma

。

sqrt

（

。

log

（

1。25

delta

））

epsilon

vals_gauss

［

。

random

。

normal

（

loc

，

scale

sigma

）

for

range

（

100000

）］

plt

。

hist

（

vals_laplace

，

bins

，

label

‘Laplace’

）

plt

。

hist

（

vals_gauss

，

bins

，

alpha

=。

，

label

‘Gaussian’

）；

plt

。

legend

（）；

在這裡插入圖片描述

在這裡，我們繪製了

$\epsilon = 1$

的拉普拉斯和高斯機制的經驗機率密度函式，以及高斯機制的

$\delta = 10^{-5}$

。

與拉普拉斯機制相比，高斯機制的圖看起來“被擠壓”了。與拉普拉斯機制相比，使用高斯機制得到其他答案的可能性要大得多，而拉普拉斯機制則更貼近真實答案的差分私有輸出（相比之下，拉普拉斯機制看起來非常“尖銳”）。

因此，高斯機制有兩個主要缺點，它需要使用寬鬆的

$(\epsilon, \delta)$

差分隱私定義，並且它不如拉普拉斯機制準確。我們為什麼要使用它？

向量值函式及其靈敏度（Vector-Valued Functions and their Sensitivities）

到目前為止，我們只考慮了實值函式（即函式的輸出始終是單個實數）。這些函式的形式為

$f : D \rightarrow \mathbb{R}$

。

然而，拉普拉斯和高斯機制都可以擴充套件到

$f : D \rightarrow \mathbb{R}^k$

形式的向量值函式，它們返回實數的向量。

我們可以將直方圖視為向量值函式，它返回一個向量，其元素由直方圖條柱計陣列成。

我們之前看到函式的靈敏度是：

$GS(f) = \max_{d(x,x$

我們如何定義向量值函式的靈敏度？

考慮表示式

。如果

是一個向量值函式，則此表示式表示兩個向量之間的差異，這可以計算為它們對應元素之間的差異（因此，兩個長度 -

向量的差值是一個新的長度 -

向量）。這個新向量是

和

之間的距離，表示為向量。

此向量的大小是

的靈敏度。有幾種方法可以計算向量的大小；我們將使用其中兩個：

範數和

範數。

L1 和 L2 規範（L1 and L2 Norms）

長度為

的向量

的

範數定義為

$\lVert V \rVert_1 = \sum_{i=1}^k \lvert V_i \rvert$

（即它是向量元素的總和）。在二維空間中，兩個向量之間差的

範數產生它們之間的“曼哈頓距離”。

長度為

的向量

的

範數定義為

$\lVert V \rVert_2 = \sqrt{\sum_{i=1}^k V_i^2}$

（即平方和的平方根）。

在二維空間中，這是"歐氏距離"，並且它總是小於或等於#FormatImgID_54#距離

。

L1 和 L2 靈敏度（L1 and L2 Sensitivities）

向量值函式

的

靈敏度為：

$GS(f) = \max_{d(x,x$

這等於按元素靈敏度的總和。例如，如果我們定義一個向量值函式

返回 1 個敏感結果的長度

向量，

則#FormatImgID_60# 的#FormatImgID_61#敏感度為#FormatImgID_62#

。

類似地，向量值函式

的

靈敏度為：

$GS_2(f) = \max_{d(x,x$

使用與上面相同的示例，返回長度

向量的 1 個敏感結果的向量值函式

的敏感度為

。對於長向量，

靈敏度顯然會遠低於

靈敏度！對於某些應用程式，如機器學習演算法（有時返回具有數千個元素的向量），

#FormatImgID_71#靈敏度明顯低於#FormatImgID_72#靈敏度

。

在 L1 和 L2 之間進行選擇（Choosing Between L1 and L2）

如前所述，拉普拉斯和高斯機制都可以擴充套件到向量值函式。但是，這兩個擴充套件之間存在一個關鍵區別：

向量值拉普拉斯機制需要使用#FormatImgID_73#靈敏度，而向量值高斯機制允許使用#FormatImgID_74#或#FormatImgID_75#靈敏度

。這是高斯機制的一個

主要優勢

。

對於#FormatImgID_76#靈敏度遠低於#FormatImgID_77#靈敏度的應用，高斯機制允許新增更少的噪聲

。

向量值拉普拉斯機制釋放

$f(x) + (Y_1, \dots, Y_k)$

，其中

是從拉普拉斯分佈中得出的 i。i。d，其尺度為

$\frac{s}{\epsilon}$

和

是

的

敏感性。

向量值高斯機制釋放

$f(x) + (Y_1, \dots, Y_k)$

，其中

從高斯分佈中得出 i。i。d。與

$\sigma^2 = \frac{2s^2 \log(1.25/\delta)}{\epsilon^2}$

和

是

的

敏感性。

災難機制（The Catastrophe Mechanism）

$(\epsilon, \delta)$

-差分隱私的定義表明，滿足定義的機制必須“表現良好”，機率為

$1-\delta$

。這意味著對於機率

$\delta$

，該機制可以做任何事情。這種“失敗機率”令人擔憂，因為滿足寬鬆定義的機制可能（機率較低）導致非常糟糕的結果。

考慮以下機制，我們稱之為災難機制：

在這裡插入圖片描述

對於機率

$1-\delta$

，災難機制滿足

$\epsilon$

-差分隱私。對於機率

$\delta$

，它會釋放整個資料集，沒有噪聲。

這種機制滿足了鬆弛差分隱私的定義，但我們可能不希望在實踐中使用它。

幸運的是，大多數

$(\epsilon, \delta)$

差分私有機制都沒有這種災難性的故障模式。

例如，高斯機制永遠不會釋放整個資料集。

相反，對於機率

$\delta$

，高斯機制不能完全滿足

$\epsilon$

-差分隱私，它滿足

$c\epsilon$

-差分隱私，而是對於某個值

。

因此，高斯機制優雅地失敗了，而不是災難性的，所以對高斯機制比對災難機制更有信心是合理的。

稍後，我們將看到對差分隱私定義的替代放寬，這些放寬區分了優雅失敗的機制（如高斯機制）和災難性失敗的機制（如災難機制）。

高階組合（Advanced Composition）

我們已經看到了兩種結合差分私有機制的方法：順序組合和平行組合。事實證明，差分隱私引入了一種分析差分私有機制順序組成的新方法，這可以降低隱私成本。

高階組合定理通常用機制來表示，這些機制是

-fold 自適應組合的例項。

-fold 自適應組合是一系列機制

$m_1, \dots, m_k$

，使得：

每個機制

都可以根據所有先前機制的輸出來選擇

$m_1, \dots, m_{i-1}$

（因此自適應）。

每個機制

的輸入既是私有資料集，也是以前機制的所有輸出（因此組成）。

迭代程式（即迴圈或遞迴函式）幾乎總是

-fold自適應組合的例項。例如，執行 1000 次迭代的

for

迴圈是 1000 倍的自適應合成。作為更具體的例子，平均攻擊是

-fold自適應組合。

# works for sensitivity-1 queries

def

avg_attack

（

query

，

epsilon

，

）：

results

［

query

。

random

。

laplace

（

loc

，

scale

epsilon

）

for

range

（

）］

return

。

mean

（

results

）

avg_attack

（

，

500

）

在這裡插入圖片描述

在此示例中，機制序列是預先固定的（我們每次都使用相同的機制），並且

。

標準順序組合定理說：

該機制的總隱私成本為

$k\epsilon$

（在本例中為

$500 \epsilon$

）。

高階組合定理說：

如果

-fold自適應組合

$m_1, \dots, m_k$

中的每個機制

都滿足

$\epsilon$

-差分隱私

然後對於任何

$\delta \geq 0$

，整個

-fold 自適應組合滿足

$(\epsilon$

-差分隱私，其中：

$\epsilon$

從上面的示例中插入

$\epsilon = 1$

，並設定

$\delta$

，我們得到：

$\epsilon$

因此，對於相同的機制，高階組合在

$\epsilon$

上派生出比順序組合低得多的界。

這是什麼意思？

這意味著順序組合給出的邊界是鬆散的，它們不會嚴格約束計算的實際隱私成本。

事實上，高階組合也給出了鬆散的邊界，它們只是比順序合成給出的邊界稍微緊緻一些。

請務必注意，這兩個邊界在技術上是無法比較的，因為高階組合引入了

$\delta$

。但是，當

$\delta$

較小時，我們通常會比較這兩種方法給出的

$\epsilon$

。

那麼，我們應該總是使用高階組合嗎？事實證明，我們不應該。讓我們嘗試上面的實驗，瞭解

的不同值，並繪製順序組合和高階組合下的總隱私成本圖。

epsilon

delta

10e-5

def

adv_comp

（

）：

return

epsilon

。

sqrt

（

。

log

（

delta

））

def

seq_comp

（

）：

return

epsilon

plt

。

plot

（［

seq_comp

（

）

for

range

（

100

）］，

label

‘Sequential Composition’

）

plt

。

plot

（［

adv_comp

（

）

for

range

（

100

）］，

label

‘Advanced Composition’

）

plt

。

legend

（）；

在這裡插入圖片描述

事實證明，標準的順序合成擊敗了小於約70的

的高階合成。因此，高階組合只有在

較大（例如超過 100）時才真正有用。但是，當

非常大時，高階組合可以產生很大的不同。

plt

。

plot

（［

seq_comp

（

）

for

range

（

10000

）］，

label

‘Sequential Composition’

）

plt

。

plot

（［

adv_comp

（

）

for

range

（

10000

）］，

label

‘Advanced Composition’

）

plt

。

legend

（）；

在這裡插入圖片描述

用於鬆弛差分隱私的高階組合（Advanced Composition for Approximate Differential Privacy）

上面對高階組合的描述要求組合的各個機制滿足純

$\epsilon$

-差分隱私。

但是，如果它們滿足

$(\epsilon, \delta)$

-差分隱私，則該定理也適用。高階組合定理的更一般的陳述如下：

如果

-fold自適應組合

$m_1, \dots, m_k$

中的每個機制

滿足

$(\epsilon, \delta)$

-差分隱私

然後對於任何

$\delta$

，整個

-fold 自適應組合滿足

$(\epsilon$

-差分隱私，其中：

$\epsilon$

唯一的區別在於組合機制的失敗引數

$\delta$

，其中我們有一個額外的

$k\delta$

項。當正在組成的機制滿足純

$\epsilon$

-差分隱私時，則

$\delta = k\delta = 0$

，我們得到與上述語句相同的結果。

總結

1、通常要求#FormatImgID_153#非常小，通常為#FormatImgID_154#或更小，其中#FormatImgID_155#是資料集的大小。

2、高斯機制有兩個主要缺點，它需要使用寬鬆的#FormatImgID_156#差分隱私定義，並且它不如拉普拉斯機制準確。

3、在二維空間中，#FormatImgID_157#距離總是小於或等於#FormatImgID_158#距離。

4、#FormatImgID_159#靈敏度明顯低於#FormatImgID_160#靈敏度。

5、向量值拉普拉斯機制需要使用#FormatImgID_161#靈敏度，而向量值高斯機制允許使用#FormatImgID_162#或#FormatImgID_163#靈敏度。這是高斯機制的一個主要優勢。對於#FormatImgID_164#靈敏度遠低於#FormatImgID_165#靈敏度的應用，高斯機制允許新增更少的噪聲。

6、高階組合也給出了鬆散的邊界，它們只是比順序合成給出的邊界稍微緊緻一些。

7、事實證明，標準的順序合成擊敗了小於約70的#FormatImgID_166#的高階合成。因此，高階組合只有在#FormatImgID_167#較大（例如超過 100）時才真正有用。但是，當#FormatImgID_168#非常大時，高階組合可以產生很大的不同。

本文使用 Zhihu On VSCode 創作併發布

標簽：機制差分 FormatImgID 隱私高斯

上一篇:我該繼續和雙子女走下去嗎?

下一篇：教你如何寫出直擊人心的“朋友圈招生文案”