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

「爱情、让人受尽委屈。」 2023-09-29 23:58 3阅读 0赞

潜在因子模型（Latent Factor Model）是一种常见的数据降维技术，可以将高维数据表示为低维特征空间中的因子分解形式。假设我们有  n n n 个用户和  m m m 个物品，每个用户对某些物品有评分行为，那么可以用潜在因子模型来表示这些评分：

r i j = μ + u i T v j + ϵ i j r\_\{ij\} = \\mu + u\_i^Tv\_j + \\epsilon\_\{ij\} rij=μ\+uiTvj\+ϵij

其中  r i j r\_\{ij\} rij 表示用户  i i i 对物品  j j j 的评分， μ \\mu μ 表示全局平均值， u i u\_i ui 和  v j v\_j vj 分别表示用户  i i i 和物品  j j j 的潜在向量（或者说“因子”）， ϵ i j \\epsilon\_\{ij\} ϵij 是一个随机噪声项，通常假设  ϵ i j \\epsilon\_\{ij\} ϵij 独立同分布于某个已知的概率分布，比如高斯分布。

为了满足差分隐私，我们需要保证相邻的数据集只有微小的变化会导致输出的概率分布变化也很小。具体地，考虑两个相邻的数据集  D D D 和  D ′ D' D′，它们只相差一个用户  i i i 对物品  j j j 的评分，我们要保证通过概率分布  M ( D ) \\mathcal\{M\}(D) M(D) 和  M ( D ′ ) \\mathcal\{M\}(D') M(D′) 计算出的条件概率比值  M ( D ) M ( D ′ ) \\frac\{\\mathcal\{M\}(D)\}\{\\mathcal\{M\}(D')\} M(D′)M(D) 不会太大。这里  M \\mathcal\{M\} M 是模型的输出结果，即用户  i i i 对物品  j j j 的预测评分。

为了方便计算，我们假设噪声项  ϵ i j \\epsilon\_\{ij\} ϵij 服从标准正态分布，即  ϵ i j ∼ N ( 0 , 1 ) \\epsilon\_\{ij\} \\sim \\mathcal\{N\}(0,1) ϵij∼N(0,1)。这时，模型的训练过程可以看成是最小化观测数据和模型预测之间的均方误差（MSE）加上一个正则化项：

min ⁡ u , v ∑ ( i , j ) ∈ D ( r i j − μ − u i T v j ) 2 + λ ( ∣ ∣ u i ∣ ∣ 2 + ∣ ∣ v j ∣ ∣ 2 ) \\min\_\{u,v\}\\sum\_\{(i,j)\\in D\}(r\_\{ij\} - \\mu - u\_i^Tv\_j)^2 + \\lambda(||u\_i||^2 + ||v\_j||^2) u,vmin(i,j)∈D∑(rij−μ−uiTvj)2\+λ(∣∣ui∣∣2\+∣∣vj∣∣2)

其中  λ \\lambda λ 是正则项的系数，保证模型不会过拟合。

接下来，我们考虑如何加入噪声使得这个模型满足差分隐私。为了简化推导，我们假设每个用户只对少量物品进行评分，且每个物品也只被少数用户评分，这样数据矩阵是非常稀疏的。此时，我们可以将每个元素  ( i , j ) (i,j) (i,j) 分别视为一个独立的查询，然后对每个查询都加入独立同分布的噪声  N ( 0 , σ 2 ϵ ) \\mathcal\{N\}(0,\\frac\{\\sigma^2\}\{\\epsilon\}) N(0,ϵσ2)，其中  σ \\sigma σ 是一个与查询结果范围相关的参数， ϵ \\epsilon ϵ 是差分隐私的隐私参数。注意到加入的噪声是与查询无关的，因此对于每个查询，模型预测的结果就变成了：

r ^ i j = μ + u i T v j + N ( 0 , σ 2 ϵ ) \\hat\{r\}\_\{ij\} = \\mu + u\_i^Tv\_j + \\mathcal\{N\}(0,\\frac\{\\sigma^2\}\{\\epsilon\}) r^ij=μ\+uiTvj\+N(0,ϵσ2)

于是，我们可以得到不加噪声和加噪声的模型预测之间的条件概率比值：

M ( D ) M ( D ′ ) = ∏ ( i , j ) ∈ D △ D ′ exp ⁡ ( − ( r i j − r ^ i j ) 2 2 σ 2 ) exp ⁡ ( − ( r i j − r ^ i j ′ ) 2 2 σ 2 ) \\frac\{\\mathcal\{M\}(D)\}\{\\mathcal\{M\}(D')\} = \\prod\_\{(i,j)\\in D\\bigtriangleup D'\}\\frac\{\\exp(-\\frac\{(r\_\{ij\}-\\hat\{r\}\{ij\})^2\}\{2\\sigma^2\})\}\{\\exp(-\\frac\{(r\{ij\}-\\hat\{r\}'\_\{ij\})^2\}\{2\\sigma^2\})\} M(D′)M(D)=(i,j)∈D△D′∏exp(−2σ2(rij−r^ij′)2)exp(−2σ2(rij−r^ij)2)

其中， M ( D ) \\mathcal\{M\}(D) M(D) 是在不加噪声时的条件概率， M ( D ′ ) \\mathcal\{M\}(D') M(D′) 是在加噪声时的条件概率， D D D 是原始数据集， D ′ D' D′ 是添加了拉普拉斯噪声的数据集， r ^ i j \\hat\{r\}\_\{ij\} r^ij 是模型对  ( i , j ) (i,j) (i,j) 的预测评分， σ \\sigma σ 是控制隐私保护和查询精度之间的权衡参数。  △ \\bigtriangleup △ 表示两个集合的对称差集。此公式用于计算矩阵分解任务中差分隐私机制的参数  ϵ \\epsilon ϵ。

其中  D △ D ′ D\\bigtriangleup D' D△D′ 表示两个数据集的对称差分，即只包含在其中一个数据集中的元素。注意到噪声的方差是与隐私参数  ϵ \\epsilon ϵ 相关的，因此我们可以将上式改写为：

M ( D ) M ( D ′ ) = exp ⁡ ( ϵ 2 ∑ ( i , j ) ∈ D △ D ′ ( r i j − r ^ i j ) 2 − ( r i j − r ^ i j ′ ) 2 2 σ 2 ) \\frac\{\\mathcal\{M\}(D)\}\{\\mathcal\{M\}(D')\} = \\exp(\\frac\{\\epsilon\}\{2\}\\sum\_\{(i,j)\\in D\\bigtriangleup D'\}\\frac\{(r\_\{ij\}-\\hat\{r\}\{ij\})^2-(r\{ij\}-\\hat\{r\}'\_\{ij\})^2\}\{2\\sigma^2\}) M(D′)M(D)=exp(2ϵ(i,j)∈D△D′∑2σ2(rij−r^ij)2−(rij−r^ij′)2)

接下来，我们需要计算上式中指数部分的值。注意到：

( r i j − r ^ i j ) 2 − ( r i j − r ^ ′ i j ) 2 = ( r ^ ′ i j − r ^ i j ) ( 2 r i j − r ^ i j − r ^ ′ i j ) (r\_\{ij\}-\\hat\{r\}\{ij\})^2-(r\{ij\}-\\hat\{r\}'\{ij\})^2 = (\\hat\{r\}'\{ij\}-\\hat\{r\}\{ij\})(2r\{ij\}-\\hat\{r\}\{ij\}-\\hat\{r\}'\{ij\}) (rij−r^ij)2−(rij−r^′ij)2=(r^′ij−r^ij)(2rij−r^ij−r^′ij)

因此，我们可以进一步得到：

M ( D ) M ( D ′ ) = exp ⁡ ( ϵ 2 σ 2 ∑ ( i , j ) ∈ D △ D ′ ( r ^ ′ i j − r ^ i j ) ( 2 r i j − r ^ i j − r ^ ′ i j ) ) \\frac\{\\mathcal\{M\}(D)\}\{\\mathcal\{M\}(D')\} = \\exp(\\frac\{\\epsilon\}\{2\\sigma^2\}\\sum\_\{(i,j)\\in D\\bigtriangleup D'\}(\\hat\{r\}'\{ij\}-\\hat\{r\}\{ij\})(2r\_\{ij\}-\\hat\{r\}\{ij\}-\\hat\{r\}'\{ij\})) M(D′)M(D)=exp(2σ2ϵ(i,j)∈D△D′∑(r^′ij−r^ij)(2rij−r^ij−r^′ij))

现在的问题是如何计算  r ^ i j \\hat\{r\}\{ij\} r^ij 和  r ^ ′ i j \\hat\{r\}'\{ij\} r^′ij 的值。由于加入的噪声是独立同分布的，因此对于每个查询  ( i , j ) (i,j) (i,j)，我们可以独立地生成两个噪声  ϵ i j \\epsilon\_\{ij\} ϵij 和  ϵ ′ i j \\epsilon'\{ij\} ϵ′ij，然后计算出对应的预测结果  r ^ i j = μ + u i T v j + ϵ i j \\hat\{r\}\{ij\} = \\mu + u\_i^Tv\_j + \\epsilon\_\{ij\} r^ij=μ\+uiTvj\+ϵij 和  r ^ ′ i j = μ + u i T v j + ϵ ′ i j \\hat\{r\}'\{ij\} = \\mu + u\_i^Tv\_j + \\epsilon'\{ij\} r^′ij=μ\+uiTvj\+ϵ′ij。这样，我们就可以将上式进一步转化为：

M ( D ) M ( D ′ ) = exp ⁡ ( ϵ 2 σ 2 ∑ ( i , j ) ∈ D △ D ′ ( ϵ ′ i j − ϵ i j ) ( 2 r i j − μ − u i T v j − ϵ i j − u i T v j − ϵ i j ′ ) ) \\frac\{\\mathcal\{M\}(D)\}\{\\mathcal\{M\}(D')\} = \\exp(\\frac\{\\epsilon\}\{2\\sigma^2\}\\sum\_\{(i,j)\\in D\\bigtriangleup D'\}(\\epsilon'\{ij\}-\\epsilon\{ij\})(2r\_\{ij\}-\\mu-u\_i^Tv\_j-\\epsilon\_\{ij\}-u\_i^Tv\_j-\\epsilon'\_\{ij\})) M(D′)M(D)=exp(2σ2ϵ(i,j)∈D△D′∑(ϵ′ij−ϵij)(2rij−μ−uiTvj−ϵij−uiTvj−ϵij′))

化简一下可以得到：

M ( D ) M ( D ′ ) = exp ⁡ ( − ϵ 2 σ 2 ∑ ( i , j ) ∈ D △ D ′ ( ϵ ′ i j − ϵ i j ) 2 2 u i T v j ) \\frac\{\\mathcal\{M\}(D)\}\{\\mathcal\{M\}(D')\} = \\exp(-\\frac\{\\epsilon\}\{2\\sigma^2\}\\sum\_\{(i,j)\\in D\\bigtriangleup D'\}\\frac\{(\\epsilon'\{ij\}-\\epsilon\{ij\})^2\}\{2\}u\_i^Tv\_j) M(D′)M(D)=exp(−2σ2ϵ(i,j)∈D△D′∑2(ϵ′ij−ϵij)2uiTvj)

现在的问题是如何计算  ∑ ( i , j ) ∈ D △ D ′ u i T v j \\sum\_\{(i,j)\\in D\\bigtriangleup D'\}u\_i^Tv\_j ∑(i,j)∈D△D′uiTvj 的值。注意到这个值可以看成是两个低维向量空间的内积，因此可以用矩阵乘法来实现。具体地，我们可以构造两个矩阵  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，其中  k k k 是潜在因子的维度，然后令  U i , : = u i U\_\{i,:\}=u\_i Ui,:=ui 和  V j , : = v j V\_\{j,:\}=v\_j Vj,:=vj。这样， ∑ ( i , j ) ∈ D △ D ′ u i T v j \\sum\_\{(i,j)\\in D\\bigtriangleup D'\}u\_i^Tv\_j ∑(i,j)∈D△D′uiTvj 就可以表示为  U T ( V − V ′ ) U^T(V-V') UT(V−V′)。于是，我们就可以将条件概率比值进一步转化为：

M ( D ) M ( D ′ ) = exp ⁡ ( − ϵ 2 σ 2 ∣ ∣ U T ( V − V ′ ) ∣ ∣ F 2 ) \\frac\{\\mathcal\{M\}(D)\}\{\\mathcal\{M\}(D')\} = \\exp(-\\frac\{\\epsilon\}\{2\\sigma^2\}||U^T(V-V')||\_F^2) M(D′)M(D)=exp(−2σ2ϵ∣∣UT(V−V′)∣∣F2)

这里  ∣ ∣ ⋅ ∣ ∣ F ||\\cdot||\_F ∣∣⋅∣∣F 表示 Frobenius 范数，即矩阵所有元素的平方和的平方根。注意到这里用到了矩阵  U U U 和  V V V 的乘法，因此我们需要保证这个乘法满足差分隐私。

为了达到这个目的，我们可以对每个用户的潜在向量  u i u\_i ui 加入独立同分布的噪声  N ( 0 , k σ ϵ ) \\mathcal\{N\}(0,\\frac\{\\sqrt\{k\}\\sigma\}\{\\epsilon\}) N(0,ϵkσ)，对每个物品的潜在向量  v j v\_j vj 加入独立同分布的噪声  N ( 0 , k σ ϵ ) \\mathcal\{N\}(0,\\frac\{\\sqrt\{k\}\\sigma\}\{\\epsilon\}) N(0,ϵkσ)。这样，对于不同的数据集  D D D 和  D ′ D' D′，我们可以得到两个带噪声的矩阵  U ~ \\tilde\{U\} U~ 和  V ~ \\tilde\{V\} V~，它们的元素都服从概率分布  N ( 0 , k σ 2 ϵ 2 ) \\mathcal\{N\}(0,\\frac\{k\\sigma^2\}\{\\epsilon^2\}) N(0,ϵ2kσ2)。然后，我们可以将矩阵  U U U 和  V V V 分别替换为  U ~ \\tilde\{U\} U~ 和  V ~ \\tilde\{V\} V~，得到带噪声的乘积矩阵  U ~ T V ~ \\tilde\{U\}^T\\tilde\{V\} U~TV~。由于加入的噪声是独立同分布的，因此对于任意的两个查询  ( i , j ) (i,j) (i,j) 和  ( i ′ , j ′ ) (i',j') (i′,j′)，它们生成的噪声是独立的，因此它们对应的乘积矩阵元素也是独立的。这意味着，整个矩阵  U ~ T V ~ \\tilde\{U\}^T\\tilde\{V\} U~TV~ 满足  ( ϵ , δ ) (\\epsilon,\\delta) (ϵ,δ)\-差分隐私，其中  δ \\delta δ 是一个非常小的常数，可以忽略不计。

综上所述，我们证明了在潜在因子模型中加入独立同分布的噪声可以满足差分隐私。具体地，对于每个查询  ( i , j ) (i,j) (i,j)，我们生成两个独立的噪声  ϵ i j \\epsilon\_\{ij\} ϵij 和  ϵ ′ i j \\epsilon'\{ij\} ϵ′ij，然后计算  r ^ i j = μ + u i T v j + ϵ i j \\hat\{r\}\{ij\} = \\mu + u\_i^Tv\_j + \\epsilon\_\{ij\} r^ij=μ\+uiTvj\+ϵij 和  r ^ ′ i j = μ + u i T v j + ϵ ′ i j \\hat\{r\}'\{ij\} = \\mu + u\_i^Tv\_j + \\epsilon'\{ij\} r^′ij=μ\+uiTvj\+ϵ′ij。接下来，我们使用  r ^ i j \\hat\{r\}\{ij\} r^ij 和  r ^ ′ i j \\hat\{r\}'\{ij\} r^′ij 计算条件概率比值，得到：

为了保证乘法  U T ( V − V ′ ) U^T(V-V') UT(V−V′) 满足差分隐私，我们对矩阵  U U U 和  V V V 加入独立同分布的噪声，得到带噪声的矩阵  U ~ \\tilde\{U\} U~ 和  V ~ \\tilde\{V\} V~，然后将它们替换成原来的矩阵，在加噪声的乘积矩阵  U ~ T V ~ \\tilde\{U\}^T\\tilde\{V\} U~TV~ 中进行乘法运算。最终，整个过程都满足  ( ϵ , δ ) (\\epsilon,\\delta) (ϵ,δ)\-差分隐私，其中  δ \\delta δ 是一个非常小的常数，可以忽略不计。

上述内容是基于原始的“Differential Privacy for Matrix Factorization”论文进行阐述的。该论文由McSherry等人撰写，发表在ACM Conference on Computer and Communications Security (CCS) 2009上。