MindSpore:基于本地差分隐私的 Bandit 算法

摘要:本文将先简单介绍Bandit 问题和本地差分隐私的相关背景,然后介绍基于本地差分隐私的 Bandit 算法,最后通过一个简单的电影推荐场景来验证 LDP LinUCB 算法。

Bandit问题是强化学习中一类重要的问题,由于它定义简洁且有大量的理论分析,因此被广泛应用于新闻推荐,医学试验等实际场景中。随着人类进入大数据时代,用户对自身数据的隐私性日益重视,这对机器学习算法的设计提出了新的挑战。为了在保护隐私的情况下解决 Bandit 这一经典问题,北京大学和华为诺亚方舟实验室联合提出了基于本地差分隐私的 Bandit 算法,论文已被 NeurIPS 2020 录用,代码已基于 MindSpore 开源首发

本文将先简单介绍 Bandit 问题和本地差分隐私的相关背景,然后介绍基于本地差分隐私的 Bandit 算法,最后通过一个简单的电影推荐场景来验证 LDP LinUCB 算法。

大家都有过这样的经历,在我们刷微博或是读新闻的时候,经常会看到一些系统推荐的内容,这些推荐的内容是根据用户对过往推荐内容的点击情况以及阅读时长等反馈来产生的。在这个过程里,系统事先不知道用户对各种内容的偏好,通过不断地与用户进行交互(推荐内容 — 得到反馈),来慢慢学习到用户的偏好特征,不断提高推荐的精准性,从而最大化用户的价值,这就是一个典型的 Bandit 问题。

Bandit 问题有 context-free 和 contextual 两种常见的设定,下面给出它们具体的数学定义。

【Context-Free Bandit】

【Contextual Bandit】

传统的差分隐私技术(Differential Privacy,DP)是将用户数据集中到一个可信的数据中心,在数据中心对用户数据进行匿名化使其符合隐私保护的要求后,再分发给下游使用,我们将其称之为中心化差分隐私。但是,一个绝对可信的数据中心很难找到,因此人们提出了本地差分隐私技术(Local Differential Privacy,LDP),它直接在客户端进行数据的隐私化处理后再提交给数据中心,彻底杜绝了数据中心泄露用户隐私的可能。

Context-Free Bandit

我们可以证明,上述算法有如下的性能:

根据上述定理,我们只需将任一非隐私保护的算法按照算法 1 进行改造,就立即可以得到对应的隐私保护版本的算法,且它的累积 regret 的理论上界和非隐私算法只相差一个

因子,因此算法 1 具有很强的通用性。我们将损失函数满足不同凸性和光滑性条件下的 regret 简单罗列如下:

上述算法和结论可以扩展到每一轮能观测多个动作损失值的情况,感兴趣的可以参见论文(https://arxiv.org/abs/2006.00701)。

Contextual Bandit

【定理】 依照至少为

的概率,LDP LinUCB 算法的 regret 满足如

上述算法和结论可以扩展到 gg 不是恒等变换的情况,感兴趣的可以参见论文(https://arxiv.org/abs/2006.00701)。

MovieLens 是一个包含多个用户对多部电影评分的公开数据集,我们可以用它来模拟电影推荐。我们通过src/dataset.py 来构建环境:我们从数据集中抽取一部分有电影评分数据的用户,然后将评分矩阵通过 SVD 分解来补全评分数据,并将分数归一化到[−1,+1]。在每次交互的时候,系统随机抽取一个用户,推荐算法获得特征,并选择一部电影进行推荐,MovieLensEnv会在打分矩阵中查询该用户对电影对评分并返回,从而模拟用户给电影打分。

class MovieLensEnv:    def observation(self):        """random select a user and return its feature."""        sampled_user = random.randint(0, self._data_matrix.shape[0] - 1)        self._current_user = sampled_user        return Tensor(self._feature[sampled_user])    def current_rewards(self):        """rewards for current user."""        return Tensor(self._approx_ratings_matrix[self._current_user])

import mindspore.nn as nn
class LinUCB(nn.Cell):    def __init__(self, context_dim, epsilon=100, delta=0.1, alpha=0.1, T=1e5):    ...        # Parameters        self._V = Tensor(np.zeros((context_dim, context_dim), dtype=np.float32))        self._u = Tensor(np.zeros((context_dim,), dtype=np.float32))        self._theta = Tensor(np.zeros((context_dim,), dtype=np.float32))

每来一个用户,LDP LinUCB 算法根据用户和电影的联合特征x基于当前的模型来选择最优的电影a_max做推荐,并传输带噪声的更新量:

import mindspore.nn as nn
class LinUCB(nn.Cell):...    def construct(self, x, rewards):        """compute the perturbed gradients for parameters."""        # Choose optimal action        x_transpose = self.transpose(x, (1, 0))        scores_a = self.squeeze(self.matmul(x, self.expand_dims(self._theta, 1)))        scores_b = x_transpose * self.matmul(self._Vc_inv, x_transpose)        scores_b = self.reduce_sum(scores_b, 0)        scores = scores_a + self._beta * scores_b        max_a = self.argmax(scores)        xa = x[max_a]        xaxat = self.matmul(self.expand_dims(xa, -1), self.expand_dims(xa, 0))        y = rewards[max_a]        y_max = self.reduce_max(rewards)        y_diff = y_max - y        self._current_regret = float(y_diff.asnumpy())        self._regret += self._current_regret
 # Prepare noise        B = np.random.normal(0, self._sigma, size=xaxat.shape)        B = np.triu(B)        B += B.transpose() - np.diag(B.diagonal())        B = Tensor(B.astype(np.float32))        Xi = np.random.normal(0, self._sigma, size=xa.shape)        Xi = Tensor(Xi.astype(np.float32))
 # Add noise and update parameters        return xaxat + B, xa * y + Xi, max_a

系统收到更新量之后,更新模型参数如下:

import mindspore.nn as nn
class LinUCB(nn.Cell):...    def server_update(self, xaxat, xay):        """update parameters with perturbed gradients."""        self._V += xaxat        self._u += xay        self.inverse_matrix()        theta = self.matmul(self._Vc_inv, self.expand_dims(self._u, 1))        self._theta = self.squeeze(theta)

我们测试不同的 \varepsilonε 对累积 regret 对影响:

  • x 轴:交互轮数
  • y 轴:累积 regret

相关模型代码已上线 MindSpore Model Zoo:https://gitee.com/mindspore/mindspore/tree/master/model_zoo感兴趣的可自行体验。

1. Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, Liwei Wang. “Locally Differentially Private (Contextual) Bandits Learning.” Advances in Neural Information Processing Systems. 2020.

2. LDP LinUCB 代码:

https://gitee.com/mindspore/mindspore/tree/master/model_zoo/research/rl/ldp_linucb

本文分享自华为云社区《MindSpore 首发:隐私保护的 Bandit 算法,实现电影推荐》,原文作者:chengxiaoli。

 

点击关注,第一时间了解华为云新鲜技术~

给TA买糖
共{{data.count}}人
人已赞赏
经验教程

趣谈 DHCP 协议,有点意思。

2021-3-9 10:39:00

经验教程

使用egg.js开发后端API接口系统

2021-3-9 11:28:00

⚠️
免责声明:根据《计算机软件保护条例》第十七条规定“为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬。”您需知晓本站所有内容资源均来源于网络,仅供用户交流学习与研究使用,版权归属原版权方所有,版权争议与本站无关,用户本人下载后不能用作商业或非法用途,需在24个小时之内从您的电脑中彻底删除上述内容,否则后果均由用户承担责任;如果您访问和下载此文件,表示您同意只将此文件用于参考、学习而非其他用途,否则一切后果请您自行承担,如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。 本站为个人博客非盈利性站点,所有软件信息均来自网络,所有资源仅供学习参考研究目的,并不贩卖软件,不存在任何商业目的及用途,网站会员捐赠是您喜欢本站而产生的赞助支持行为,仅为维持服务器的开支与维护,全凭自愿无任何强求。本站部份代码及教程来源于互联网,仅供网友学习交流,若您喜欢本文可附上原文链接随意转载。
无意侵害您的权益,请发送邮件至 momeis6@qq.com 或点击右侧 私信:momeis 反馈,我们将尽快处理。
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索