第三次看论文笔记：Differential Privacy for Collaborative Filtering Recommender Algorithm Xue Zhu
序言
协同过滤通过从用户评价矩阵中学习行为模式向用户推荐。如果得到用户的推荐列表，再加上一定的背景知识，就可以以此推断出关于这个用户的一些消息，隐私遭到了泄露。通过在评价矩阵中加入噪音，提供了理论上的私有保护，但对推荐准确性影响存在不确定性，本文在差分隐私应用到推荐系统当中，本文设计了1，基于抽样的差分隐私项目推荐（DP-IR）和基于抽样的差分私有用户推荐（DP-IR），俩种算法都是基于指数机制的，前者针对项目，后者针对用户
介绍
主要介绍了相似性的重要性，然后说明了在两种算法当中的简单应用
2.1
令居矩阵：对于两个评价矩阵，如中其中只是缺少了一个人的评价记录，那么这两个矩阵称为评价矩阵
差分隐私机制定义：E
灵敏度定义：
2.2指数机制
Definition 4. (Exponential Mechanism) Given a quality function q : (R.squr (|U|×|I|) , I) → R, an input matrix M, ∆q is the sensitivity of the quality function. the exponential mechanism expo(M, I, q,E ) outputs i ∈ I with probability:
以下是算法的另一种解释：
关于指数机制指数机制一般是针对与非数值型的
设算法Ｇ输入为数据集Ｄ，输出为一实体对ｒ∈Ｒａｎｇｅ，ｑ（Ｄ，ｒ）为打分函数，Δｑ为函 数ｑ（Ｄ，ｒ）的敏感度。若算法Ｇ以正 比 于 ｅｘｐ（εｑ（Ｄ，ｒ） ２Δｑ ）的概率从Ｒaｎｇｅ中选择并输出ｒ，那么算法Ｇ 提供ε差分隐私保护。
定义1，隐私组合定理：这个是针对与（E，δ）机制的，组合隐私定理就是说并行时候的结果隐私预算的数学公式
指数机制的精确度：
保护基于项目推荐：
3.1基于项目的推荐系统及推理
Deshpande提供了一种基于条目的top-N推荐算法。给定一个评级矩阵，用户购买记录={u1，u2，u3,......,un}.为每个项目我们先计算他和其他项目之间的相似度。下面这个计算如下：
以下算法1是未进行隐私预算的推荐算法
如何在推荐系统中使用差分隐私达到隐私保护的目的呢？
设计基于差分隐私项目的推荐算法，并在此列表上进行了采样（DP-IR），以解决隐私问题
定理5质量函数和敏感度：给定评价矩阵，一个项目i，一个人i对j的评价将通过以下这个式子给定：
接下来他讲了邻近矩阵的敏感度计算
自从Sij∈[0,1]，对于任意一对相邻矩阵，查询函数的灵敏度为
从上面的讨论中，我们可以看到，当一个用户更新他的购买记录时，相似性变化最多为1
3.3接下来就是在基于项目的推荐算法里面加入差分隐私
带采样的隐私推荐算法(简称DP-IR)。它包括两个步oopp'骤
Step1：对每个人所对应的用户矩阵用概率p（M）进行抽样，得到新的用户矩阵T，然后我们设计一个微分隐私算法
Step2：我们根据步骤1得到的相关列表Li和用户u的购买记录Iu向用户u推荐k个项目，记为R(L, Iu)。
我们将展示整个算法DP-IR
3.3.1差别化隐私相关项目推荐算法
首先给出了相关列表推荐算法的差分隐私算法，
因为用户基数比较大，所以进行抽样计算相似度，然后进行推荐
3.3.2貌似介绍了在该算法处理当中涉及的处理过程之间的关系
3.4前面分析了DP-IR算法，下面介绍了一些定理
引理1：介绍了抽样
定理3：说算法DP-A1’是满足（E，Eδ0/2）
定理4：将两个处理过程合并f o A’，他表明，如果后一个过程不访问矩阵M，而只应用于前一个过程的输出L上，那么它保留不同的私有
定理5：将两个过程中进行隐私预算的计算
以上都分析了该算法的准确性，满足差分隐私，和推荐系统接下来是算法中随机抽样和指数机制中的误差分析
定理6：评价DP+_IR的准确性
对于项目i，算法A1’中记录第t内部推荐的R*,关于这个推荐的错误定义为：
该误差表示的是最终输出和最优输出之间的误差，对于两个参数，要满足下式
引理2：添加 chernoff 噪音
算法的误差对距离进行了评价，得到了最优结果。根据这个定义和引理，我们提出了下面的定理。
定理6：该算法的准确度
3.6讨论质量函数
基于项目的协同过滤的一个关键点是项目相似度的测量。在选择质量函数时应考虑三个方面。首先，一个好的相似度度量应该反映项目相关性的本质，这应该从用户行为中学习。在方程3中，分子反映了这样一个事实，即购买i和j的用户越多，给的评级越高，i和j就越相似。因为在差分隐私法中，精度与函数的灵敏度有关。更多细节可以从定理2中得到。考虑到我们的相似函数，最大的差异只有1/|U|，因为用户数量非常大，所以非常小。第三，随着用户数量的增加，灵敏度预计会下降。还有其他一些常用的度量方法来评估项目相似度[7]。
4基于用户的推荐
基于用户的推荐是另一种具有代表性的算法，可以形式化为两个步骤[7]。对于一些用户u，首先找到k个最相似的用户集Ku = {Uui, Uu2，…根据某些相似度度量(如皮尔逊相关系数或余弦相似度)。用户之间的相似矩阵表示为S，其中每个entry Suv表示用户u和v之间的相似度，对于每个用户u，根据knearest neighbour记录的物品i，判断u对物品i的评级。用户u对项目i的预测得分可以用rui = P Pn K SuvMvi n K Suv来计算。项目根据预测得分按降序排列。
后面假设了一下攻击者的攻击方式，然后我们添加差分隐私算法
假设用户u购买记录Iu = {Iu1, Iu2，…，Iuw}，我们根据u的邻居向u推荐k个条目，首先定义两个用户之间的相似度。用户u向量ru{1,2，…，从评级矩阵中选择R} |I|，其中rui = Mui(如果用户u对项目I进行评级)，则为0。显然，rui{0,1，…,R }。设ru = P i i rui/| i |为u的平均评级;设Iuv = iutiv，计算两个用户u和v之间的相似性为
基于这种相似性，我们引入了用户偏好函数q(M, u, i)，用于评估用户对某项产品的偏好程度
定理7：偏好函数和敏感度
给定一个用户组,一组项目,用户相似度矩阵和评级矩阵M(梅∈{ 0 . .},R∈N对于每一个用户u∈u +),u，第i项目的项m偏好是计算:
接下来就是详细介绍了该算法
由于用户基数太大，所以我们对器经行抽样V，然后对其进行算法5进行隐私保护处理
定理7：算法DP-A2’是满足（E，E*δ0/2）差分隐私的推荐算法
然后接下来讲了对该算法的证明：
5，实验
在该小节说明了数据来源，计算了召回率，还测试了推荐错误和隐私参数和抽样参数之间关系。然后比较不同相似度的计算对实验的印象
网友评论