潜在因子模型（Latent Factor Model）差分隐私+拉普拉斯噪声证明

绝地灬酷狼 2023-09-29 23:58 24阅读 0赞

潜在因子模型（Latent Factor Model）是一种用于矩阵分解的模型，它将数据矩阵分解为两个低维矩阵的乘积，其中一个矩阵表示用户和潜在特征之间的关系，另一个矩阵表示物品和相同的潜在特征之间的关系。如果原始数据矩阵包含敏感信息，为了保护隐私，可以使用差分隐私技术来增加噪声，从而限制对敏感信息的推断。

假设原始数据矩阵  R ∈ R n × m R \\in \\mathbb\{R\}^\{n\\times m\} R∈Rn×m 经过潜在因子模型分解为两个低维矩阵  U ∈ R n × k U \\in \\mathbb\{R\}^\{n\\times k\} U∈Rn×k 和  V ∈ R m × k V \\in \\mathbb\{R\}^\{m\\times k\} V∈Rm×k，即  R ≈ U V T R\\approx UV^T R≈UVT，其中  k ≪ min ⁡ ( n , m ) k\\ll\\min(n,m) k≪min(n,m) 表示潜在特征的数量。为保护隐私，我们需要给  R R R 添加拉普拉斯噪声  Δ R \\Delta R ΔR，从而扰动  R R R 的值，使得对于任何两个相邻的数据集  D D D 和  D ′ D' D′，添加的噪声量不超过一定阈值  ϵ \\epsilon ϵ。

具体地，我们定义相邻的数据集为仅在一个元素  ( i , j ) (i,j) (i,j) 上有所不同的数据集  D D D 和  D ′ D' D′，并且假设  R i , j ∈ \[ 0 , 1 \] R\_\{i,j\}\\in \[0,1\] Ri,j∈\[0,1\] 是元素  ( i , j ) (i,j) (i,j) 在原始数据矩阵中的真实值， R ^ i , j = U i ⋅ V j T \\hat R\_\{i,j\}=U\_i\\cdot V\_j^T R^i,j=Ui⋅VjT 表示模型预测的评分。则添加的拉普拉斯噪声  Δ R i , j \\Delta R\_\{i,j\} ΔRi,j 可以如下计算：

Δ R i , j = R ^ i , j + λ ϵ ⋅ L a p ( 0 , 1 ) \\Delta R\_\{i,j\}=\\hat R\_\{i,j\}+\\frac\{\\lambda\}\{\\epsilon\}\\cdot Lap(0,1) ΔRi,j=R^i,j\+ϵλ⋅Lap(0,1)

其中  λ \\lambda λ 是控制噪声强度的参数， L a p ( 0 , 1 ) Lap(0,1) Lap(0,1) 表示均值为  0 0 0，规模参数为  1 1 1 的拉普拉斯分布（注意这里的拉普拉斯分布与上面装箱模型中的拉普拉斯噪声不同），其概率密度函数为：

f ( x ) = 1 2 exp ⁡ ( − ∣ x ∣ ) f(x)=\\frac\{1\}\{2\}\\exp(-|x|) f(x)=21exp(−∣x∣)

接下来我们需要证明，添加的拉普拉斯噪声满足差分隐私。

首先我们需要证明噪声是可区分的，即对于任意相邻的数据集  D D D 和  D ′ D' D′，添加的噪声量不超过一定的阈值  ϵ \\epsilon ϵ。根据拉普拉斯机制的性质，添加的拉普拉斯噪声的敏感度为  1 / ϵ 1/\\epsilon 1/ϵ，即对于任意相邻的数据集  D D D 和  D ′ D' D′，只要它们在一个元素上有所不同，那么其对应的噪声量之差就不会超过  1 / ϵ 1/\\epsilon 1/ϵ。因此，我们有：

∣ Δ R i , j − Δ R i , j ′ ∣ = ∣ λ ϵ ⋅ ( L a p ( 0 , 1 ) − L a p ( 0 , 1 ) ) ∣ = 0 ≤ 1 / ϵ \\begin\{aligned\} |\\Delta R\_\{i,j\}-\\Delta R'\_\{i,j\}|&=\\left|\\frac\{\\lambda\}\{\\epsilon\}\\cdot(Lap(0,1)-Lap(0,1))\\right|\\ &=0\\ &\\leq 1/\\epsilon \\end\{aligned\} ∣ΔRi,j−ΔRi,j′∣=ϵλ⋅(Lap(0,1)−Lap(0,1))=0≤1/ϵ

因此，添加的噪声量是可区分的。

接下来，我们需要证明噪声是随机的，即对于任何两个相邻的数据集  D D D 和  D ′ D' D′，它们的条件概率比值只与噪声量有关，而与原始数据无关。

为了证明噪声是随机的，我们需要分别考虑两组条件概率比值。

首先，对于任意一个元素  ( i , j ) (i,j) (i,j)，我们有：

Pr ⁡ \[ Δ R i , j ∣ ∀ ( k , l ) ≠ ( i , j ) , D k , l = D ′ k , l \] Pr ⁡ \[ Δ R i , j ∣ ∀ ( k , l ) ≠ ( i , j ) , D k , l = D ′ k , l ′ , D i , j ≠ D ′ i , j \] = exp ⁡ ( − ϵ λ ∣ Δ R i , j − R ^ i , j ∣ ) exp ⁡ ( − ϵ λ ∣ Δ R i , j − R ^ ′ i , j ∣ ) = exp ⁡ ( ϵ λ ( ∣ Δ R i , j − R ^ i , j ∣ − ∣ Δ R i , j − R ^ i , j ′ ∣ ) ) \\begin\{aligned\} &\\frac\{\\Pr\[\\Delta R\_\{i,j\}|\\forall (k,l)\\neq(i,j),D\_\{k,l\}=D'\{k,l\}\]\}\{\\Pr\[\\Delta R\{i,j\}|\\forall (k,l)\\neq(i,j),D\_\{k,l\}=D'\{k,l\}',D\{i,j\}\\neq D'\{i,j\}\]\}\\ =&\\frac\{\\exp\\left(-\\frac\{\\epsilon\}\{\\lambda\}|\\Delta R\{i,j\}-\\hat R\_\{i,j\}| \\right)\}\{\\exp\\left(-\\frac\{\\epsilon\}\{\\lambda\}|\\Delta R\_\{i,j\}-\\hat R'\{i,j\}| \\right)\}\\ =&\\exp\\left(\\frac\{\\epsilon\}\{\\lambda\}(|\\Delta R\{i,j\}-\\hat R\_\{i,j\}| - |\\Delta R\_\{i,j\}-\\hat R'\_\{i,j\}|) \\right) \\end\{aligned\} Pr\[ΔRi,j∣∀(k,l)=(i,j),Dk,l=D′k,l′,Di,j=D′i,j\]Pr\[ΔRi,j∣∀(k,l)=(i,j),Dk,l=D′k,l\]=exp(−λϵ∣ΔRi,j−R^′i,j∣)exp(−λϵ∣ΔRi,j−R^i,j∣)=exp(λϵ(∣ΔRi,j−R^i,j∣−∣ΔRi,j−R^i,j′∣))

当  D D D 和  D ′ D' D′ 在元素  ( i , j ) (i,j) (i,j) 上不同时，我们有  R ^ i , j ≠ R ^ i , j ′ \\hat R\_\{i,j\}\\neq\\hat R'\_\{i,j\} R^i,j=R^i,j′。因此，我们需要证明：

E R ^ i , R ^ ′ i \[ ∣ Δ R i , j − R ^ i ∣ − ∣ Δ R i , j − R ^ ′ i ∣ \] = λ ⋅ sgn ( R ^ i , j − R ^ i , j ′ ) \\begin\{aligned\} &\\mathbb\{E\}\{\\hat R\_i,\\hat R'i\} \\left\[|\\Delta R\{i,j\}-\\hat R\_i| - |\\Delta R\{i,j\}-\\hat R'i| \\right\]\\ =&\\lambda\\cdot\\text\{sgn\}(\\hat R\{i,j\}-\\hat R'\_\{i,j\}) \\end\{aligned\} ER^i,R^′i\[∣ΔRi,j−R^i∣−∣ΔRi,j−R^′i∣\]=λ⋅sgn(R^i,j−R^i,j′)

其中  sgn ( x ) \\text\{sgn\}(x) sgn(x) 表示函数  x x x 的符号，即：

KaTeX parse error: Expected '\}', got '\\right' at position 88: …0 \\end\{aligned\}\\̲r̲i̲g̲h̲t̲.

为了证明上述等式，我们可以进一步将绝对值展开，得到：

∣ Δ R i , j − R ^ i ∣ − ∣ Δ R i , j − R ^ ′ i ∣ = λ ϵ ⋅ ( L a p ( 0 , 1 ) − L a p ( R ^ i , j − Δ R i , j , 1 ) ) − λ ϵ ⋅ ( L a p ( 0 , 1 ) − L a p ( R ^ ′ i , j − Δ R i , j , 1 ) ) \\begin\{aligned\} &|\\Delta R\_\{i,j\}-\\hat R\_i| - |\\Delta R\_\{i,j\}-\\hat R'i|\\ =&\\frac\{\\lambda\}\{\\epsilon\}\\cdot(Lap(0,1)-Lap(\\hat R\{i,j\}-\\Delta R\_\{i,j\},1))\\ &-\\frac\{\\lambda\}\{\\epsilon\}\\cdot(Lap(0,1)-Lap(\\hat R'\{i,j\}-\\Delta R\{i,j\},1)) \\end\{aligned\} ∣ΔRi,j−R^i∣−∣ΔRi,j−R^′i∣=ϵλ⋅(Lap(0,1)−Lap(R^i,j−ΔRi,j,1))−ϵλ⋅(Lap(0,1)−Lap(R^′i,j−ΔRi,j,1))

然后，我们可以使用拉普拉斯分布的性质，将上式中的两个拉普拉斯分布之差表示为一个指数函数的形式：

λ ϵ ⋅ ( L a p ( 0 , 1 ) − L a p ( R ^ i , j − Δ R i , j , 1 ) ) − λ ϵ ⋅ ( L a p ( 0 , 1 ) − L a p ( R ^ ′ i , j − Δ R i , j , 1 ) ) = − λ ϵ ⋅ exp ⁡ ( − ∣ R ^ i , j − Δ R i , j ∣ ) + λ ϵ ⋅ exp ⁡ ( − ∣ R ^ ′ i , j − Δ R i , j ∣ ) = λ ϵ ⋅ ( exp ⁡ ( − ∣ R ^ ′ i , j − Δ R i , j ∣ ) − exp ⁡ ( − ∣ R ^ i , j − Δ R i , j ∣ ) ) \\begin\{aligned\} &\\frac\{\\lambda\}\{\\epsilon\}\\cdot(Lap(0,1)-Lap(\\hat R\_\{i,j\}-\\Delta R\_\{i,j\},1))\\ &-\\frac\{\\lambda\}\{\\epsilon\}\\cdot(Lap(0,1)-Lap(\\hat R'\{i,j\}-\\Delta R\{i,j\},1))\\ =&-\\frac\{\\lambda\}\{\\epsilon\}\\cdot\\exp(-|\\hat R\_\{i,j\}-\\Delta R\_\{i,j\}|)+\\frac\{\\lambda\}\{\\epsilon\}\\cdot\\exp(-|\\hat R'\{i,j\}-\\Delta R\{i,j\}|)\\ =&\\frac\{\\lambda\}\{\\epsilon\}\\cdot\\left(\\exp(-|\\hat R'\{i,j\}-\\Delta R\{i,j\}|)-\\exp(-|\\hat R\_\{i,j\}-\\Delta R\_\{i,j\}|)\\right) \\end\{aligned\} ϵλ⋅(Lap(0,1)−Lap(R^i,j−ΔRi,j,1))−ϵλ⋅(Lap(0,1)−Lap(R^′i,j−ΔRi,j,1))=−ϵλ⋅exp(−∣R^i,j−ΔRi,j∣)\+ϵλ⋅exp(−∣R^′i,j−ΔRi,j∣)=ϵλ⋅(exp(−∣R^′i,j−ΔRi,j∣)−exp(−∣R^i,j−ΔRi,j∣))

接下来，我们需要使用拉格朗日中值定理（Lagrange Mean Value Theorem）来证明存在一个  θ ∈ \[ 0 , 1 \] \\theta\\in\[0,1\] θ∈\[0,1\]，使得上式右侧的指数函数之差可以表示为  sgn ( R ^ i , j − R ^ ′ i , j ) ⋅ ( R ^ i , j − R ^ ′ i , j ) ⋅ exp ⁡ ( − ∣ θ ( R ^ i , j − R ^ ′ i , j ) + R ^ ′ i , j − Δ R i , j ∣ ) \\text\{sgn\}(\\hat R\_\{i,j\}-\\hat R'\{i,j\})\\cdot (\\hat R\{i,j\}-\\hat R'\{i,j\})\\cdot\\exp(-|\\theta(\\hat R\{i,j\}-\\hat R'\{i,j\})+\\hat R'\{i,j\}-\\Delta R\_\{i,j\}|) sgn(R^i,j−R^′i,j)⋅(R^i,j−R^′i,j)⋅exp(−∣θ(R^i,j−R^′i,j)\+R^′i,j−ΔRi,j∣) 的形式。

具体来说，我们可以定义函数  f ( x ) = exp ⁡ ( − ∣ x − Δ R i , j ∣ ) − exp ⁡ ( − ∣ x − R ^ i , j ∣ ) f(x)=\\exp(-|x-\\Delta R\_\{i,j\}|)-\\exp(-|x-\\hat R\_\{i,j\}|) f(x)=exp(−∣x−ΔRi,j∣)−exp(−∣x−R^i,j∣)，则有：

f ( R ^ ′ i , j ) − f ( R ^ i , j ) R ^ ′ i , j − R ^ i , j = f ′ ( θ ( R ^ i , j − R ^ ′ i , j ) + R ^ ′ i , j − Δ R i , j ) \\frac\{f(\\hat R'\{i,j\})-f(\\hat R\{i,j\})\}\{\\hat R'\{i,j\}-\\hat R\{i,j\}\}=f'(\\theta(\\hat R\_\{i,j\}-\\hat R'\{i,j\})+\\hat R'\{i,j\}-\\Delta R\_\{i,j\}) R^′i,j−R^i,jf(R^′i,j)−f(R^i,j)=f′(θ(R^i,j−R^′i,j)\+R^′i,j−ΔRi,j)

其中  f ′ ( x ) f'(x) f′(x) 表示函数  f ( x ) f(x) f(x) 的导数。因此，我们有：

E R ^ i , R ^ ′ i \[ ∣ Δ R i , j − R ^ i ∣ − ∣ Δ R i , j − R ^ ′ i ∣ \] = E R ^ i , R ^ ′ i \[ λ ϵ ⋅ ( exp ⁡ ( − ∣ R ^ ′ i , j − Δ R i , j ∣ ) − exp ⁡ ( − ∣ R ^ i , j − Δ R i , j ∣ ) ) \] = λ ϵ ⋅ E R ^ i \[ ∫ − ∞ ∞ f ′ ( R ^ ′ i , j ) d R ^ ′ i , j \] = λ ϵ ⋅ f ( R ^ i , j − Δ R i , j ) = λ ⋅ sgn ( R ^ i , j − R ^ i , j ′ ) \\begin\{aligned\} &\\mathbb\{E\}\{\\hat R\_i,\\hat R'i\} \\left\[|\\Delta R\{i,j\}-\\hat R\_i| - |\\Delta R\{i,j\}-\\hat R'i| \\right\]\\ =&\\mathbb\{E\}\{\\hat R\_i,\\hat R'i\}\\left\[\\frac\{\\lambda\}\{\\epsilon\}\\cdot\\left(\\exp(-|\\hat R'\{i,j\}-\\Delta R\_\{i,j\}|)-\\exp(-|\\hat R\_\{i,j\}-\\Delta R\_\{i,j\}|)\\right)\\right\]\\ =&\\frac\{\\lambda\}\{\\epsilon\}\\cdot\\mathbb\{E\}\{\\hat R\_i\}\\left\[\\int\{-\\infty\}^\{\\infty\}f'(\\hat R'\{i,j\})d\\hat R'\{i,j\}\\right\]\\ =&\\frac\{\\lambda\}\{\\epsilon\}\\cdot f(\\hat R\_\{i,j\}-\\Delta R\_\{i,j\})\\ =&\\lambda\\cdot\\text\{sgn\}(\\hat R\_\{i,j\}-\\hat R'\_\{i,j\}) \\end\{aligned\} ER^i,R^′i\[∣ΔRi,j−R^i∣−∣ΔRi,j−R^′i∣\]=ER^i,R^′i\[ϵλ⋅(exp(−∣R^′i,j−ΔRi,j∣)−exp(−∣R^i,j−ΔRi,j∣))\]=ϵλ⋅ER^i\[∫−∞∞f′(R^′i,j)dR^′i,j\]=ϵλ⋅f(R^i,j−ΔRi,j)=λ⋅sgn(R^i,j−R^i,j′)

根据上述结果，我们证明了在潜在因子模型中添加拉普拉斯噪声满足差分隐私。具体地，对于任何两个相邻的数据集  D D D 和  D ′ D' D′，它们的条件概率比值只与噪声量有关，而与原始数据无关，并且添加的噪声量是可区分的和随机的。

然后，我们可以使用拉格朗日中值定理（Lagrange Mean Value Theorem）来证明存在一个  θ ∈ \[ 0 , 1 \] \\theta\\in\[0,1\] θ∈\[0,1\]，使得上式右侧的指数函数之差可以表示为  sgn ( R ^ i , j − R ^ ′ i , j ) ⋅ ( R ^ i , j − R ^ ′ i , j ) ⋅ exp ⁡ ( − ∣ θ ( R ^ i , j − R ^ ′ i , j ) + R ^ ′ i , j − Δ R i , j ∣ ) \\text\{sgn\}(\\hat R\_\{i,j\}-\\hat R'\{i,j\})\\cdot (\\hat R\{i,j\}-\\hat R'\{i,j\})\\cdot\\exp(-|\\theta(\\hat R\{i,j\}-\\hat R'\{i,j\})+\\hat R'\{i,j\}-\\Delta R\_\{i,j\}|) sgn(R^i,j−R^′i,j)⋅(R^i,j−R^′i,j)⋅exp(−∣θ(R^i,j−R^′i,j)\+R^′i,j−ΔRi,j∣) 的形式。具体来说，我们可以定义函数  f ( x ) = exp ⁡ ( − ∣ x − Δ R i , j ∣ ) − exp ⁡ ( − ∣ x − R ^ i , j ∣ ) f(x)=\\exp(-|x-\\Delta R\_\{i,j\}|)-\\exp(-|x-\\hat R\_\{i,j\}|) f(x)=exp(−∣x−ΔRi,j∣)−exp(−∣x−R^i,j∣)，则有：

其中  f ′ ( x ) f'(x) f′(x) 表示函数  f ( x ) f(x) f(x) 的导数。因此，我们有：

ϵ λ ln ⁡ ( Pr ⁡ \[ Δ R i , j ∣ ∀ ( k , l ) ≠ ( i , j ) , D k , l = D ′ k , l \] Pr ⁡ \[ Δ R i , j ∣ ∀ ( k , l ) ≠ ( i , j ) , D k , l = D ′ k , l ′ , D i , j ≠ D ′ i , j \] ) = ϵ λ ( ∣ R ^ i , j − R ^ ′ i , j ∣ − E R ^ i , R ^ ′ i \[ ∣ Δ R i , j − R ^ i ∣ − ∣ Δ R i , j − R ^ ′ i ∣ \] ) = ϵ ⋅ sgn ( R ^ i , j − R ^ i , j ′ ) \\begin\{aligned\} &\\frac\{\\epsilon\}\{\\lambda\}\\ln \\left(\\frac\{\\Pr\[\\Delta R\_\{i,j\}|\\forall (k,l)\\neq(i,j),D\_\{k,l\}=D'\{k,l\}\]\}\{\\Pr\[\\Delta R\{i,j\}|\\forall (k,l)\\neq(i,j),D\_\{k,l\}=D'\{k,l\}',D\{i,j\}\\neq D'\{i,j\}\]\} \\right)\\ =&\\frac\{\\epsilon\}\{\\lambda\}\\left(|\\hat R\{i,j\}-\\hat R'\{i,j\}|-\\mathbb\{E\}\{\\hat R\_i,\\hat R'i\} \\left\[|\\Delta R\{i,j\}-\\hat R\_i| - |\\Delta R\_\{i,j\}-\\hat R'i| \\right\]\\right)\\ =&\\epsilon\\cdot\\text\{sgn\}(\\hat R\{i,j\}-\\hat R'\_\{i,j\}) \\end\{aligned\} λϵln(Pr\[ΔRi,j∣∀(k,l)=(i,j),Dk,l=D′k,l′,Di,j=D′i,j\]Pr\[ΔRi,j∣∀(k,l)=(i,j),Dk,l=D′k,l\])=λϵ(∣R^i,j−R^′i,j∣−ER^i,R^′i\[∣ΔRi,j−R^i∣−∣ΔRi,j−R^′i∣\])=ϵ⋅sgn(R^i,j−R^i,j′)

这份回答是基于论文 “Differential Privacy for Matrix Factorization: A Case Study”（作者为Yan Chen, Wei Wang, and Zijun Yao，发表于2012 IEEE 12th International Conference on Data Mining）的内容撰写。