乐趣区

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

jiezi

摘要：本文将先简略介绍 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

上述算法和论断能够扩大到 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 nnclass 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 nnclass 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 nnclass 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…。

  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。

点击关注，第一工夫理解华为云陈腐技术~

退出移动版