转载于：MindSpore
作者： MindSpore
老虎机（Bandit）问题是强化学习中一类重要的问题，由于它定义简洁且有大量的理论分析，因此被广泛应用于新闻推荐，医学试验等实际场景中。随着人类进入大数据时代，用户对自身数据的隐私性日益重视，这对机器学习算法的设计提出了新的挑战。为了在保护隐私的情况下解决 Bandit 这一经典问题，北京大学和华为诺亚方舟实验室联合提出了基于本地差分隐私的 Bandit 算法，论文已被 NeurIPS 2020 录用，代码已基于 MindSpore 开源首发。
本文将先简单介绍 Bandit 问题和本地差分隐私的相关背景，然后介绍基于本地差分隐私的 Bandit 算法，最后通过一个简单的电影推荐场景来验证 LDP LinUCB 算法。
老虎机（Bandit） 问题
大家都有过这样的经历，在我们刷微博或是读新闻的时候，经常会看到一些系统推荐的内容，这些推荐的内容是根据用户对过往推荐内容的点击情况以及阅读时长等反馈来产生的。在这个过程里，系统事先不知道用户对各种内容的偏好，通过不断地与用户进行交互（推荐内容 — 得到反馈），来慢慢学习到用户的偏好特征，不断提高推荐的精准性，从而最大化用户的价值，这就是一个典型的 Bandit 问题。
Bandit 问题有 context-free 和 contextual 两种常见的设定，下面给出它们具体的数学定义。
【Context-Free Bandit】
【Contextual Bandit】
本地差分隐私（LDP）
传统的差分隐私技术（Differential Privacy，DP）是将用户数据集中到一个可信的数据中心，在数据中心对用户数据进行匿名化使其符合隐私保护的要求后，再分发给下游使用，我们将其称之为中心化差分隐私。但是，一个绝对可信的数据中心很难找到，因此人们提出了本地差分隐私技术（Local Differential Privacy，LDP），它直接在客户端进行数据的隐私化处理后再提交给数据中心，彻底杜绝了数据中心泄露用户隐私的可能。
隐私保护的 Bandit 算法
Context-Free Bandit
我们可以证明，上述算法有如下的性能：
上述算法和结论可以扩展到每一轮能观测多个动作损失值的情况，感兴趣的可以参见论文（https://arxiv.org/abs/2006.00...
Contextual Bandit
上述算法和结论可以扩展到 gg 不是恒等变换的情况，感兴趣的可以参见论文（https://arxiv.org/abs/2006.00...
场景模拟：电影推荐
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])
LDP LinUCB 的算法位于src/linucb.py，参数如下，分别对应算法中的 :
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))`
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/m...\_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/m...\_zoo/research/rl/ldp\_linucb
MindSpore官方资料
GitHub : https://github.com/mindspore-...
Gitee:https : //gitee.com/mindspore/mindspore
官方QQ群 : 871543426
推荐阅读
更多嵌入式AI技术干货请关注嵌入式AI专栏。
