資訊專欄INFORMATION COLUMN
摘要：基本思想上圖給出了差分隱私的一般性方法。定義一給出了差分隱私的數學表達。從定義可以看出差分隱私技術限制了任意一條記錄對算法輸出結果的影響。而基于不同噪音機制且滿足差分隱私的算法所需噪音大小與全局敏感性密切相關。
1. 蘋果、微軟、谷歌與差分隱私的愛恨糾葛
在2016 年6 月份的蘋果 WWDC 大會上蘋果公司負責軟件工程的高級副總裁克雷格?費德里希(Craig Federighi)在WWDC上滿臉傲驕地說「We believe you should havegreat features and great privacy」，那個瞬間特別像一個小孩子，自信滿滿地向世界宣告「我們就是能站著把錢賺了」。就這樣，差分隱私從研究論文一躍成為科技新聞頭條。其實 Google 也有嘗試過類似的事情，在 GitHub 上開源了一個名為RAPPOR(Randomized Aggregatable Privacy-Preserving Ordinal Response)的項目，從原理上來說，也是向數據中注入可控的噪音元素的方式來保護用戶隱私，早在2014 年Google就以這項技術來收集用戶使用Chrome瀏覽器時的資料。不過DP主要是由微軟研究院的C. Dwork提出及發展，微軟也已經在這個領域申請了不少的專利。遺憾的是，一如蘋果宣稱的，蘋果是唯一一家將Differential Privacy作為標準大規模部署的公司。
2. 重大用戶隱私泄露事件過去幾十年，互聯網的發展徹底改變了我們的生活。網絡逐漸成為人們生活的中心——網購、聊天、看新聞、查股票??，無不通過網絡進行。日常生活的網絡化塑造了一個網絡時代和一大批與我們息息相關的互聯網公司。這些公司往往提供優質而免費的服務，并擁有巨量用戶。不過，為了提供更好的服務，或者出于其他商業目的，幾乎所有的互聯網公司都在盡可能地記錄用戶的行為。這些用戶數據對互聯網公司來說是珍貴的資源，因為他們可以通過機器學習和數據挖掘從中獲得大量有用的信息。與此同時，用戶數據亦是危險的“潘多拉之盒”：數據一旦泄漏，用戶的隱私將被侵犯，同時對公司的信譽也帶來莫大的傷害。近年來，我們已經目睹了多起用戶隱私泄漏事件，幾家大公司深陷其中；而這些事件全都是由于數據擁有者分享數據不當引起的。
20 世紀最著名的用戶隱私泄漏事件發生在美國馬薩諸塞州。90 年代中葉，該州團體保險委員會(Group Insurance Commis-sion)決定發布州政府雇員的“經過匿名化處理的”醫療數據，以助公共醫學研究。在數據發布之前，委員會對潛在的隱私問題已有所認識，因此刪除了數據中所有的敏感信息，例如姓名、住址和社會安全號碼(social security number)。然而 1997 年，麻省理工學院博士生拉坦婭?斯威尼(Latanya Sweeney)(現任哈佛大學教授)成功破解了這份匿名數據，并找到了時任馬薩諸塞州州長威廉?威爾德(William Weld)的醫療記錄，還將該記錄直接寄給了州長本人。
2006 年8月4日，美國在線公司的研究部門在互聯網上發布了超過65萬用戶在過去三個月的搜索關鍵字，以供公眾對搜索技術進行研究。該公司對發布的數據進行了匿名化處理，但僅僅是把用戶的賬號用一個隨機號碼代替，并沒有對用戶所提交的搜索關鍵字進行任何處理。隨后，《紐約時報》成功將部分數據去匿名化，并在經過當事人同意后，公開了其中一位搜索用戶的真實身份。這起隱私泄漏事件引起了人們的廣泛關注，并導致美國在線公司首席技術官辭職。隨后，美國在線公司因為此事件在北加州地方法院被起訴。
網飛公司 (Netflix) 也曾深陷數據隱私泄漏的丑聞中。2006 年，網飛公司投資100萬美元舉辦了一個為期三年的推薦系統算法競賽，并發布了一些用戶的影評數據供參賽者測試。出于隱私保護，網飛公司在發布數據前將所有用戶的個人信息移除，僅保留了每個用戶對各個電影的評分以及評分的時間戳。然而，來自德州大學奧斯汀分校的兩位研究人員利用網飛用戶影評數據與公開的互聯網電影數據庫(IMDB)用戶影評數據之間的相關性，將網飛公司的一部分匿名用戶與公開的IMDB用戶進行了一一對應，由此獲得了IMDB用戶在網飛公司網站上的全部電影瀏覽信息（包括涉及敏感題材的電影）。為此，2009年，網飛公司遭到了4 位用戶的起訴，也不得不取消了原定于2010年舉行的第二屆算法競賽。
3. 隱私保護研究的目的隱私保護研究的目標在于提出用以修改隱私數據的技術，使得修改后的數據可以安全發布(以供第三方進行研究)，而不會遭受去匿名化等隱私攻擊。同時，修改后的數據要在保護隱私的前提下最大限度地保留原數據的整體信息，否則被發布的數據將毫無研究價值。具體來說，當前的研究熱點主要集中在兩個方面：
(1)隱私保護技術能提供何種強度的保護，或者說能夠抵御何種強度的攻擊；
(2)如何在保護隱私的同時，最大限度地保留原數據中的有用信息。
針對層出不窮的隱私攻擊方式和現有隱私保護機制的缺陷，來自微軟研究院的德沃柯(Dwork) 等人于2006年提出了差分隱私模型。差分隱私具有兩個最重要的優點：(1)差分隱私嚴格定義了攻擊者的背景知識：除了某一條記錄，攻擊者知曉原數據中的所有信息——這樣的攻擊者幾乎是最強大的，而差分隱私在這種情況下依然能有效保護隱私信息；(2)差分隱私擁有嚴謹的統計學模型，極大地方便了數學工具的使用以及定量分析和證明。正是由于差分隱私的諸多優勢，使其一出現便迅速取代了之前的隱私模型，成為隱私研究的核心，并引起理論計算機科學、數據庫與數據挖掘、機器學習等多個領域的關注。
上圖給出了差分隱私的一般性方法。當用戶(也可能是潛藏的攻擊者)向數據提供者提交一個查詢請求時，如果數據提供者直接發布準確的查詢結果，則可能導致隱私泄漏，因為用戶可能會通過查詢結果來反推出隱私信息。為了避免這一問題，差分隱私系統要求從數據庫中提煉出一個中間件，用特別設計的隨機算法對中間件注入適量的噪音，得到一個帶噪中間件；再由帶噪中間件推導出一個帶噪的查詢結果，并返回給用戶。這樣，即使攻擊者能夠從帶噪的結果反推得到帶噪中間件，他也不可能準確推斷出無噪中間件，更不可能對原數據庫進行推理，從而達到了保護隱私的目的。
差分隱私的定義是建立在對隨機算法的約束之上的。約束的根本目的在于限制攻擊者在得到帶噪中間件后，對原數據庫的推導能力。定義一給出了差分隱私的數學表達。
隱私是指個人、組織機構等實體不愿意被外部知曉的信息。例如，個人的薪資、醫療記錄等。雖然出現了多種基于 -匿名和劃分隱私保護框架的保護方法，而差分隱私保護技術被公認為比較嚴格和強健的保護模型。該保護模型的基本思想是對原始數據、對原始數據的轉換或者是對統計結果添加噪音來達到隱私保護效果。 該保護方法可以確保在某一數據集中插入或者刪除一條記錄的操作不會影響任何計算的輸出結果。另外，該保護模型不關心攻擊者所具有的背景知識，即使攻擊者已經掌握除某一條記錄之外的所有記錄的信息，該記錄的隱私也無法被披露。差分隱私的形式化定義如下。
定義1:
給定數據集和，二者互相之間至多相差一條記錄，即。給定一個隱私算法，為的取值范圍，若算法在數據集和上任意輸出結果滿足下列不等式，則 滿足-差分隱私。
其中，概率由算法的隨機性控制，也表示隱私被披露的風險；隱私預算參數表示隱私保護程度， 越小隱私保護程度越高。從定義1可以看出差分隱私技術限制了任意一條記錄對算法輸出結果的影響。該定義是從理論角度確保算法滿足-差分隱私，而要實現差分隱私保護需要噪音機制的介入。
噪音機制是實現差分隱私保護的主要技術，常用的噪音添加機制分別為拉普拉斯機制與指數機制。而基于不同噪音機制且滿足差分隱私的算法所需噪音大小與全局敏感性(Global Sensitive)密切相關。
定義2:
對于任意一個函數，函數的全局敏感性為。其中，和至多相差一條記錄，表示所映射的實數空間，表示函數的查詢維度，表示度量使用的距離，通常使用來度量 。
該機制過拉普拉斯分布產生的噪音擾動真實輸出值來實現差分隱私保護。
定理1：
對于任一個函數，若算法的輸出結果滿足下列等式，則滿足-差分隱私。
其中，是相互獨立的拉普拉斯變量，噪音量大小與成正比，與成反比。算法的全局敏感性越大，所需噪音越大 。從上式可知，中第個元素由拉普拉斯噪音引起的標準絕對誤差與方差分別為
該機制主要是處理一些輸出結果為非數值型的算法，例如，分類操作中分裂屬性的選擇問題。該機制的關鍵技術是如何設計打分函數，其中表示從輸出域中所選擇的輸出項。
定理2：
給定一個打分函數，若算法
滿足下列等式，則滿足-差分隱私。
其中，為打分函數的全局敏感性。由上式可知，打分越高，被選擇輸出的概率越大。
差分隱私保護技術本身蘊含著序列組合性與并行組合性兩種重要的組合性質。
性質1.
給定數據庫與個隨機算法，且滿足-隱私，則在上的序列組合滿足-差分隱私，。
性質2.
設為一個隱私數據庫，被劃分成個不相交的子集，,設為任一個隨機算法滿足-差分隱私。則算法在上的系列操作滿足-差分隱私。
這兩種性質在證明算法是否滿足差分隱私以及在隱私預算分配過程中起著重要作用。
滿足差分隱私的保護算法需要在保護隱私的同時，又要兼顧保護后數據的可用性以及隱私預算的分配策略是否合理。通常包括3個方面對隱私保護算法進行度量。
(1)算法誤差。
常用的應用型誤差度量方法包括相對誤差、絕對誤差、誤差的方差以及歐式距離等。此外，數據依賴情況下的操作，必須考慮信息缺損帶來的誤差。
(2)算法性能。
一般利用時間復雜度與漸近噪音誤差邊界對算法的性能進行評估。
(3)的合理分配。
隱私預算代表著數據隱私保護程度。 一旦耗盡，將破壞差分隱私，算法本身也就失去了意義。因此，合理的預算分配策略要盡可能使的生命周期持續長一些。常用的分配策略包括線性分配、均勻分配、指數分配、自適用性分配以及混合策略分配等。
參考文獻
張嘯劍, 孟小峰. 面向數據發布和分析的差分隱私保護[J]. 計算機學報, 2014(4):927-949.
數據分享中的差分隱私保護 張俊
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/11299.html
摘要：摘要隱私數據與機器學習看似矛盾，其實不然。在每個分區上訓練機器學習模型，將其稱為教師模型。差分隱私能夠很好地與機器學習的任務相一致，比如在學習過程中，記住像病例這樣的特殊訓練實例是侵犯隱私的行為，也是一種過擬合現象，降低了模型泛化能力。 摘要： 隱私數據與機器學習看似矛盾，其實不然。如何有效保護機器學習訓練中的隱私數據？谷歌專家給出了答案——PATE框架，就算你不太懂隱私保護的知識，也...
摘要：作者天瓊，數據游戲優勝隊伍成員介紹本文整理記錄了參與的一次小型數據分析競賽數據游戲，競賽目標是預測年月日股閉市時招商銀行的股價。日發現的數據有錯誤，需要手工矯正日該數據恢復正常。而函數，是對樣本外的數據進行預測。 作者：天瓊，「數據游戲」優勝隊伍成員 介紹 本文整理記錄了參與的一次小型數據分析競賽「數據游戲」，競賽目標是預測2019年5月15日A股閉市時招商銀行600036的股價。 主...
摘要：作者天瓊，數據游戲優勝隊伍成員介紹本文整理記錄了參與的一次小型數據分析競賽數據游戲，競賽目標是預測年月日股閉市時招商銀行的股價。日發現的數據有錯誤，需要手工矯正日該數據恢復正常。而函數，是對樣本外的數據進行預測。 作者：天瓊，「數據游戲」優勝隊伍成員 介紹 本文整理記錄了參與的一次小型數據分析競賽「數據游戲」，競賽目標是預測2019年5月15日A股閉市時招商銀行600036的股價。 主...
摘要：是世界上最重要的研究者之一，他在谷歌大腦的競爭對手，由和創立工作過不長的一段時間，今年月重返，建立了一個探索生成模型的新研究團隊。機器學習系統可以在這些假的而非真實的醫療記錄進行訓練。今年月在推特上表示是的，我在月底離開，并回到谷歌大腦。 理查德·費曼去世后，他教室的黑板上留下這樣一句話：我不能創造的東西，我就不理解。（What I cannot create, I do not under...
摘要：以此來實現硬件不換，功能迭代升級的目的。這樣如何使用最低成本高效的升級則成了物聯網設備的一個重要課題。 1、背景 隨著網絡環境日益便利，物聯網速成長期，物聯網設備跟隨產品定位不同導致的碎片化特別嚴重，但他們都有一個共同點就是都需要迭代更新，產品多樣且復雜，那么必然導致升級類型和樣式多，不是...
閱讀 1441·2023-04-25 19:00
閱讀 4135·2021-11-17 17:00
閱讀 1753·2021-11-11 16:55
閱讀 1510·2021-10-14 09:43
閱讀 3108·2021-09-30 09:58
閱讀 850·2021-09-02 15:11
閱讀 2118·2019-08-30 12:56
閱讀 1399·2019-08-30 11:12
