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

Z时代
2024-01-10
分类：技术分享

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

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

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

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

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

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

【Context-Free Bandit】

【Contextual Bandit】

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

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

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

Context-Free Bandit

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

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

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

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

Contextual Bandit

【定理】依照至少为

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

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

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

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

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)

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

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

x 轴：交互轮数

y 轴：累积 regret

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

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

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