差分隱私中敏感度如何計算？

01-23

最近看了很多關於差分隱私的論文，有幾點不明白的地方向各位知友請教。
1.一般說查詢函數的敏感度為1,有的情況下敏感度又要具體算，如何根據給的定義式算敏感度呢？
2.針對大量數據挖掘的演算法都可以用差分進行加噪嗎？

3.看差分隱私的論文，感覺作者是在做一個證明題，似乎解決了一種情況就能發一篇paper，加噪是有固定的套路嗎？

卸腰。

1. 敏感度的計算就是按定義的那樣，對任意一個數據集，你改變數據集中的一項，求這個函數的輸出所發生的變化的最大值。一般這個敏感度是可以根據你的函數推出來的，如果推不出來，起碼也可以求一個上界。比如你的函數如果是有界的 $|f|<M$ ，那你的敏感度最多也就是 $2M$ ，當然你這個上界越緊越好。

2. 我覺得很多人對DP有些誤解。DP關心的永遠只是隱私，如果我設計一個演算法，不管你輸入是什麼，我總是輸出數字0，那這個演算法也是滿足DP的，因為它的輸出跟輸入壓根沒關係，當然不會泄露隱私。大家真正關心的，是如何設計一個好的DP，也就是如何讓一個滿足DP的演算法具有可用性。而且「利用差分來加噪」本身這個說法就是不準確的，應該是反過來「利用雜訊去實現差分隱私」。那麼什麼演算法都可以用加雜訊來實現DP么？答案是：是的，無論你有什麼演算法，你總是可以加足夠多的雜訊（一個極端的例子，讓它只輸出雜訊）讓它滿足差分隱私，但結果可能是你的演算法不再具有可用性，或者可用性非常差。

3. DP作為一個theoretical privacy guarantee，這方面的paper必然會變成一個證明題。這方面的paper思路永遠都是：我設計一個加雜訊的方法，我證明這個方法能讓我的演算法變成DP的，我驗證這樣加雜訊後的演算法依舊有很好的utility。至於加雜訊有沒有套路，要說有也算有，無非就是把別人已有的DP演算法拿過來改造一下。最經典的比如Laplace Mechanism，很多paper都是在這個演算法上設計出來的。為什麼這樣做？因為證明題並不簡單，不是每個人都能無中生有地拿一個演算法並證明它滿足DP的，所以更多的是用別人證好的東西進行改造。如果想要學套路，唯一的方法就是多看paper。

您好，看到更多人在知乎平台關心DP這個領域，表示開森*^_^*。

1.敏感度的定義: $Delta f = max_{x,x$ ，其中 $x acksim x$ 是鄰接集合。你說的敏感度等於1，我猜測指的是DP論文中的經典例子，就是把query $f$ 設為問一個資料庫中有多少個records具有某個性質，那麼這個時候兩個資料庫最多差一行數據自然這個query的返回值至多差一啦～看一下Dwork和Adam Smith大神的經典文章可以解答你的疑惑:

http://www.cs.uml.edu/~ge/pdf/papers_685-2-1/DworkSmith.pdf。

2.許多機器學習演算法都可以加噪，或者說構造一個Mechanism，一個例子是SVM：

http://www.technicolorbayarea.com/papers/2012/RBHT12svm.pdf。

因為大部分分類器都被參數決定，將參數作為Mechanism的response再在上面套用DP的框架是個十分自然的想法。類似的，很多統計的estimator一樣有DP版本，參見第一篇文獻。

同時，很多文章開始討論function release的問題，也就是考慮Mechanism的output是一個函數，如下面這篇文章：

http://www.aaai.org/Conferences/AAAI/2017/PreliminaryPapers/12-Alda-14735.pdf。

基本思想是將返回的函數用Bernstein多項式展開，再在其多項式係數上擾動。由於ML里的classifier都是函數，所以理論上，這個方法可以為一大類ML方法加噪，見文章的preliminaries。

3.加噪沒有固定套路，看具體的應用背景，utility的衡量標準。

如有些考慮data-releasing的文章假設資料庫是有界的，並要求返回的資料庫也落在這個界里，那麼laplace就無法做到了，進而有很多其他方法，如histogram perturbation，但很多時候laplace都有不錯的性質。如樓上聚聚們說的，對一個特定情景，能在限制utility不差的情況下，證明構造的Mechanism滿足DP，自然是一篇paper～

補充：對於機器學習加噪的方式，不同文章的定義不同，下面這個綜述介紹了各式各樣的機器學習加噪：

https://arxiv.org/pdf/1412.7584.pdf。

額，我個人覺得，對於全局敏感度的話，因為是與數據集無關的，所以就可以通過在查詢函數的所有輸入數值的範圍內進行遍歷，找出最大的差值也就是那個曼哈頓距離就行，不過平滑敏感度這樣做就不一定可行了，因為有的函數是難以計算平滑敏感度的，甚至，計算這個平滑敏感度是NP-困難的。

針對數據挖掘的演算法，我目前也就看過2個。。。。。。很慚愧，一個是樸素貝葉斯分類器，通過在分類器的參數上加入滿足拉普拉斯分布的雜訊來實現差分隱私。具體可以看Differentially Private Na¨?ve Bayes Classification這篇論文。另一種方法比較早了，是一種非互動式的差分隱私演算法，基於一個分類樹的方法，對屬性進行泛化，結合指數機制對屬性進行分割，然後加入拉普拉斯雜訊。所以我個人認為，數據挖掘的演算法很多應該是可以加入差分隱私保護機制的。

然後你的第三個問題，其實發paper也不見得非得是解決加入雜訊的問題，當然你在一個已有的演算法上加入了拉普拉斯雜訊也是可以。不過也有例外，2014年usenix上那個獲得最佳論文獎的那篇論文Privacy in Pharmacogenetics: An End-to-End Case Study of Personalized Warfarin Dosing就是分析了差分隱私演算法的一些性能，然後做了些比較。