基于差分隱私度序列的Thurstone模型中參數(shù)估計(jì)量的漸近性理論

胡軍浩，馬曉慧，羅敬

（中南民族大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院，武漢430074）

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，各種網(wǎng)絡(luò)平臺(tái)收集了大量的用戶信息.例如，網(wǎng)絡(luò)購(gòu)物平臺(tái)，網(wǎng)絡(luò)交流平臺(tái)，醫(yī)療就診信息平臺(tái)等.這些網(wǎng)絡(luò)平臺(tái)的數(shù)據(jù)有助于分析個(gè)人的消費(fèi)行為、購(gòu)買偏好以及過往疾病的有效診斷，能夠有效解決人們?cè)谏钪忻媾R的問題.但是，網(wǎng)絡(luò)數(shù)據(jù)在為生活提供便利的同時(shí)，也帶來了隱私泄露的風(fēng)險(xiǎn).網(wǎng)絡(luò)數(shù)據(jù)通常包含個(gè)人及其關(guān)聯(lián)的敏感信息（例如，性關(guān)系、電子郵件交換）.如果網(wǎng)絡(luò)數(shù)據(jù)在公開前不進(jìn)行任何的保密處理，那么這些敏感信息很容易受到攻擊.因此為了保護(hù)網(wǎng)絡(luò)數(shù)據(jù)所包含的隱私信息，通常情況下先將網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)化成圖結(jié)構(gòu)，然后利用圖中的度序列研究網(wǎng)絡(luò)中可能攜帶的個(gè)人隱私信息［1］.因此，在研究網(wǎng)絡(luò)圖模型的過程中，網(wǎng)絡(luò)節(jié)點(diǎn)的度序列的保護(hù)至關(guān)重要.近年來，在研究網(wǎng)絡(luò)數(shù)據(jù)的隱私保護(hù)方法中，差分隱私方法受到了極大關(guān)注.由于差分隱私是一種隱私標(biāo)準(zhǔn)，限制對(duì)一個(gè)人的數(shù)據(jù)進(jìn)行更改不會(huì)顯著影響隨機(jī)數(shù)據(jù)發(fā)布機(jī)制中的輸出分布［2］，故被廣泛用于發(fā)布網(wǎng)絡(luò)數(shù)據(jù).

基于此，本文利用Thurstone 模型［3］研究成對(duì)比較網(wǎng)絡(luò)數(shù)據(jù)的相關(guān)統(tǒng)計(jì)性質(zhì).目前文獻(xiàn)［4］利用原始網(wǎng)絡(luò)數(shù)據(jù)節(jié)點(diǎn)的度序列信息證明了Thurstone 模型下參數(shù)矩估計(jì)的相合性與漸近正態(tài)性.但考慮到網(wǎng)絡(luò)數(shù)據(jù)節(jié)點(diǎn)度序列的隱私保護(hù)問題，本文在文獻(xiàn)［4］的基礎(chǔ)上研究具有差分隱私度序列的Thurstone模型矩估計(jì)問題.本文主要采用文獻(xiàn)［5］提出的方法.具體地，首先在Thurstone 網(wǎng)絡(luò)圖模型中利用差分隱私度序列替換原始度序列，然后利用矩方程估計(jì)度參數(shù)，最后證明矩估計(jì)量的漸近性質(zhì).據(jù)作者所知，基于差分隱私度序列研究Thurstone 模型中參數(shù)估計(jì)的漸近性質(zhì)目前較少.因此，在Thurstone 模型下基于差分隱私度序列研究參數(shù)估計(jì)的統(tǒng)計(jì)性質(zhì)具有重要的實(shí)際意義和理論價(jià)值.

1 基礎(chǔ)知識(shí)

1.1 Thurstone網(wǎng)絡(luò)圖模型

成對(duì)比較數(shù)據(jù)通?？捎靡粋€(gè)有向加權(quán)圖Gn表示，其中每個(gè)節(jié)點(diǎn)表示一個(gè)個(gè)體，從節(jié)點(diǎn)i到節(jié)點(diǎn)j的加權(quán)有向邊表示個(gè)體i優(yōu)先于個(gè)體j的次數(shù).現(xiàn)考慮具有n+ 1 個(gè)節(jié)點(diǎn)的有向加權(quán)圖Gn，節(jié)點(diǎn)標(biāo)記為0，1，…，n.設(shè)A=(aij)(n+1)×(n+1)為Gn的鄰接矩陣，鄰接矩陣A的元素aij表示節(jié)點(diǎn)i在tij比較總數(shù)中優(yōu)于節(jié)點(diǎn)j的次數(shù)，其中tij∈[1，T]表示i與j比較的次數(shù)，T為正常數(shù).為了便于說明，令T=tij=tji=aij+aji(i≠j)，并設(shè)定aii=tii= 0.記aij(0 ≤i＜j≤n)為服從二項(xiàng)分布的隨機(jī)變量，即aij~Binomial(T；pij)，其中定義為節(jié)點(diǎn)i的度，(d0，d1，…，dn)為網(wǎng)絡(luò)圖Gn的度序列.

Thurstone 模型是研究成對(duì)比較數(shù)據(jù)的模型之一.在該模型下，個(gè)體i優(yōu)于個(gè)體j的隨機(jī)變量aij滿足以下概率分布：

其中θi表示個(gè)體i的能力水平參數(shù).根據(jù)文獻(xiàn)［5］的分析，為了保證解的可識(shí)別性，設(shè)θ0= 0.

故 待 估 參 數(shù)θ=(θ1，…，θn)，其中θ∈Rn，R為實(shí)數(shù).

1.2 差分隱私

差分隱私是基于臨近數(shù)據(jù)集概念定義的.設(shè)兩個(gè)數(shù)據(jù)集D1和D2具有相同的屬性結(jié)構(gòu)，兩者的對(duì)稱差記為D1ΔD2，|D1ΔD2|表示D1ΔD2中記錄的數(shù)量.若|D1ΔD2| = 1，則稱D2和D1為臨近數(shù)據(jù)集.下面給出差分隱私嚴(yán)格的數(shù)學(xué)定義：

定義1［6］設(shè)有隨機(jī)算法A，PA為算法A所有可能的輸出構(gòu)成的集合.對(duì)于任意兩個(gè)臨近數(shù)據(jù)集D2和D1（相差一條記錄）以及PA的任何子集SA，若算法A滿足：

則算法A提供ε—差分隱私保護(hù)，其中隱私參數(shù)ε＞0.

隱私參數(shù)ε由管理隱私政策的數(shù)據(jù)管理員選擇，控制著隱私和效用之間的平衡.ε越小表示隱私保護(hù)水平越高［6］.在現(xiàn)有的研究中，圖結(jié)構(gòu)一般采取兩種常用的差分隱私保護(hù)標(biāo)準(zhǔn)，分別為節(jié)點(diǎn)差分隱私和邊差分隱私［7］.參考文獻(xiàn)［7］，本文使用邊差分隱私進(jìn)行研究.邊差分隱私的定義如下：

定義2［8］設(shè)D1和D2是任意兩個(gè)只有一條邊不同的相鄰圖，取ε＞0為隱私參數(shù).如果算法A滿足：

則稱算法A滿足ε—邊差分隱私.其中G是n個(gè)節(jié)點(diǎn)上感興趣的所有有向圖的集合.

一般情況下，實(shí)現(xiàn)邊差分隱私是利用Laplace機(jī)制（數(shù)值型）和指數(shù)機(jī)制（離散型）的噪聲對(duì)數(shù)據(jù)進(jìn)行加噪，從而實(shí)現(xiàn)數(shù)據(jù)的隱私保護(hù).由于兩種機(jī)制都依靠全局敏感度，故先給出全局敏感度的定義.

定義3［8］（全局敏感度） 給定查詢函數(shù)f：G→Rk，G為輸入數(shù)據(jù)集，Rk為輸出數(shù)據(jù)集.在任意一對(duì)臨近數(shù)據(jù)集D1和D2上，函數(shù)f的全局敏感度定義為：

其中‖f(D1)-f(D2)‖1是f(D1)和f(D2)間的一階距離.全局敏感度度量了當(dāng)輸入數(shù)據(jù)集變化時(shí)，對(duì)相應(yīng)輸出結(jié)果的影響.

本文考慮利用Laplace機(jī)制實(shí)現(xiàn)邊差分隱私.由文獻(xiàn)［8］中的結(jié)論可知，當(dāng)f(G)為整數(shù)時(shí)，可以使用一個(gè)離散的Laplace隨機(jī)變量作為隨機(jī)擾動(dòng)，并且隨機(jī)擾動(dòng)服從以下分布：

其中x= -Δ(f)logλ.下面給出關(guān)于Laplace 機(jī)制的相關(guān)敏感度定義.

定義4［8］給定查詢函數(shù)f：G→Rk.e1，…，ek相互獨(dú)立，且服從參數(shù)為λ的離散Laplace 分布.離散Laplace 機(jī)制的輸出f(D1)+(e1，…，ek)滿足ε—邊緣差分隱私，其中ε= -Δ(f)logλ，并且：

1.3 相關(guān)引理

引 理 1［4］設(shè)A=(aij)(n+1)×(n+1)，aij~Binomial(T；pij)，其 中TΦ(||θ*||∞)[1 - Φ(||θ*||∞)]，θ*∈Rn為 參 數(shù) 真 值.若則當(dāng)n→∞時(shí)，S{d-E(d)}的前k個(gè)元素組成的向量服從均值為0、協(xié)方差矩陣為B=(bij)k×k的漸近正態(tài)分布，這里：

引 理2［9］若 矩 陣V=(vij) 滿 足vij=vji，vij＜且V的 近 似逆矩陣為為Kronecker delta 函數(shù)，則：

其 中

引 理3［10］F：D?X→Y為Fréchet 可 微.若x0∈D時(shí)，F(xiàn)"(x0)可逆，且滿足：

則有：（1）牛頓迭代公式xn+1=xn-F"(xn)F(xn)中的xn(n≥0) 在中，并 且xn(n≥0) 收 斂 于F(x0)= 0的解x*；

2 主要結(jié)果及證明

首先考慮度序列包含著網(wǎng)絡(luò)數(shù)據(jù)節(jié)點(diǎn)的隱私信息.由定義4，設(shè)f：Gn→d，Δ(f) = 2.定義為服從參數(shù)λ的離散Laplace 分布，則添加噪聲后的輸出結(jié)果滿足ε—邊差分隱私.本文主要在差分隱私度序列基礎(chǔ)上，利用矩估計(jì)方程估計(jì)度參數(shù).為了得到參數(shù)估計(jì)的漸近性質(zhì)，需定義以下函數(shù)：

記V=(vij)：=F"(θ)，根據(jù)函數(shù)的單調(diào)性可知：結(jié) 合 引 理2 結(jié) 論 可 知：m=的近似逆S：

定 理 1設(shè)A=(aij)(n+1)×(n+1)，aij~Binomial(T；pij)，其 中若ε(1 +(nlogn)1/2)≥4logn，且τ＜1/12，則n→∞時(shí)，參數(shù)θ*的估計(jì)值存在且：

證明

由函數(shù)xexp(-x2/2)的單調(diào)性可知，結(jié)合向量值函數(shù)的平均值定理［11］：

下面分別證明（1）式中的兩部分：

隨著媒體融合時(shí)代的到來，新聞編輯要想更好地適應(yīng)這一新環(huán)境下的要求，就必須對(duì)這一時(shí)代下的新聞編輯素養(yǎng)重新進(jìn)行思考。

故：

下 面 繼 續(xù) 計(jì) 算η，||F"(θ(0))-1F(θ(0))||∞≤||SF(θ(0))||∞+||WF(θ(0))||∞，

當(dāng)i= 1，…，n時(shí)，通過泰勒展式得到：

若e3(||θ*||∞)2=ο(n1/2)，根據(jù)切比雪夫不等式可知：

結(jié)合引理1和切比雪夫不等式：

3 數(shù)值模擬

在本節(jié)中，通過數(shù)值模擬驗(yàn)證得到的理論結(jié)果.首先參考文獻(xiàn)［4］的模擬研究，設(shè)參數(shù)=iL/n，i=0，1，…，n.針對(duì)n= 100，200兩種情況，考慮L的4個(gè)值，分別為0、0.2*logn、0.5*logn、0.8*logn.基于上述參數(shù)設(shè)定，本文模擬了3 個(gè)不同的ε，分別為2、log(n)/n1/4、log(n)/n1/2.為了驗(yàn)證定理2 中的漸近性質(zhì)，取是bii中θ*替換為后的值；然后使用QQ圖評(píng)估ξij的漸近正態(tài)性；最后給出了θ*i-θ*j的95%置信區(qū)間，-的覆蓋率和置信區(qū)間的長(zhǎng)度以及矩估計(jì)不存在的概率為0.

根據(jù)圖1 可以觀察到，ε= 2 時(shí)經(jīng)驗(yàn)分位數(shù)與標(biāo)準(zhǔn)正態(tài)性分位數(shù)吻合很好.

圖1 QQ圖（ε=2，t=100）Fig.1 The QQ plot（ε=2，t=100）

根據(jù)表1觀察到，與預(yù)期的一樣，置信區(qū)間的長(zhǎng)度隨著L的增加而增加，隨著t的增加而減少.當(dāng)ε=2 時(shí)，大多數(shù)估計(jì)的模擬覆蓋率接近目標(biāo)水平.ε= log(t)/t1/4的結(jié)果也表現(xiàn)出類似的現(xiàn)象；而ε=log(t)/t1/2時(shí)，模擬結(jié)果明顯低于目標(biāo)水平.

表1 （θi*-θj*）對(duì)（i，j）的覆蓋率與置信區(qū)間長(zhǎng)度Tab.1 Estimated coverage probabilities of（θi*-θj*）for pair（i，j）as well as the length of confidence intervals

4 結(jié)論

（1）在忽略加噪過程的情況下，利用差分隱私度序列=di+ei替換度序列di得到矩估計(jì)方程，進(jìn)一步利用矩估計(jì)方程證明了基于差分隱私度序列參數(shù)的矩估計(jì)量的相合性與漸近正態(tài)性；

（2）結(jié)合數(shù)值模擬進(jìn)一步說明理論結(jié)果，結(jié)果表明差分隱私度序列可以直接用于統(tǒng)計(jì)推斷；

（3）本文研究的成對(duì)比較是稠密的，而在許多應(yīng)用中，成對(duì)比較可能是稀疏的［12］.如何分析當(dāng)實(shí)驗(yàn)個(gè)體數(shù)量趨于無窮大且成對(duì)比較稀疏時(shí)模型的漸近性質(zhì)，值得探索和研究.從數(shù)值模擬結(jié)果中還可以看出，對(duì)||θ*||∞的限制條件可能是寬松的，以后將繼續(xù)研究這個(gè)問題.