摘要：本文將先簡(jiǎn)單介紹Bandit 問題和本地差分隱私的相關(guān)背景，然后介紹基于本地差分隱私的 Bandit 算法，最后通過一個(gè)簡(jiǎn)單的電影推薦場(chǎng)景來驗(yàn)證 LDP LinUCB 算法。

Bandit問題是強(qiáng)化學(xué)習(xí)中一類重要的問題，由于它定義簡(jiǎn)潔且有大量的理論分析，因此被廣泛應(yīng)用于新聞推薦，醫(yī)學(xué)試驗(yàn)等實(shí)際場(chǎng)景中。隨著人類進(jìn)入大數(shù)據(jù)時(shí)代，用戶對(duì)自身數(shù)據(jù)的隱私性日益重視，這對(duì)機(jī)器學(xué)習(xí)算法的設(shè)計(jì)提出了新的挑戰(zhàn)。為了在保護(hù)隱私的情況下解決 Bandit 這一經(jīng)典問題，北京大學(xué)和華為諾亞方舟實(shí)驗(yàn)室聯(lián)合提出了基于本地差分隱私的 Bandit 算法，論文已被 NeurIPS 2020 錄用，代碼已基于 MindSpore 開源首發(fā)。

本文將先簡(jiǎn)單介紹 Bandit 問題和本地差分隱私的相關(guān)背景，然后介紹基于本地差分隱私的 Bandit 算法，最后通過一個(gè)簡(jiǎn)單的電影推薦場(chǎng)景來驗(yàn)證 LDP LinUCB 算法。

大家都有過這樣的經(jīng)歷，在我們刷微博或是讀新聞的時(shí)候，經(jīng)常會(huì)看到一些系統(tǒng)推薦的內(nèi)容，這些推薦的內(nèi)容是根據(jù)用戶對(duì)過往推薦內(nèi)容的點(diǎn)擊情況以及閱讀時(shí)長(zhǎng)等反饋來產(chǎn)生的。在這個(gè)過程里，系統(tǒng)事先不知道用戶對(duì)各種內(nèi)容的偏好，通過不斷地與用戶進(jìn)行交互（推薦內(nèi)容 — 得到反饋），來慢慢學(xué)習(xí)到用戶的偏好特征，不斷提高推薦的精準(zhǔn)性，從而最大化用戶的價(jià)值，這就是一個(gè)典型的 Bandit 問題。

Bandit 問題有 context-free 和 contextual 兩種常見的設(shè)定，下面給出它們具體的數(shù)學(xué)定義。

【Context-Free Bandit】

【Contextual Bandit】

傳統(tǒng)的差分隱私技術(shù)（Differential Privacy，DP）是將用戶數(shù)據(jù)集中到一個(gè)可信的數(shù)據(jù)中心，在數(shù)據(jù)中心對(duì)用戶數(shù)據(jù)進(jìn)行匿名化使其符合隱私保護(hù)的要求后，再分發(fā)給下游使用，我們將其稱之為中心化差分隱私。但是，一個(gè)絕對(duì)可信的數(shù)據(jù)中心很難找到，因此人們提出了本地差分隱私技術(shù)（Local Differential Privacy，LDP），它直接在客戶端進(jìn)行數(shù)據(jù)的隱私化處理后再提交給數(shù)據(jù)中心，徹底杜絕了數(shù)據(jù)中心泄露用戶隱私的可能。

Context-Free Bandit

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

根據(jù)上述定理，我們只需將任一非隱私保護(hù)的算法按照算法 1 進(jìn)行改造，就立即可以得到對(duì)應(yīng)的隱私保護(hù)版本的算法，且它的累積 regret 的理論上界和非隱私算法只相差一個(gè)

因子，因此算法 1 具有很強(qiáng)的通用性。我們將損失函數(shù)滿足不同凸性和光滑性條件下的 regret 簡(jiǎn)單羅列如下：

上述算法和結(jié)論可以擴(kuò)展到每一輪能觀測(cè)多個(gè)動(dòng)作損失值的情況，感興趣的可以參見論文（https:///abs/2006.00701）。

Contextual Bandit

【定理】 依照至少為

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

上述算法和結(jié)論可以擴(kuò)展到 gg 不是恒等變換的情況，感興趣的可以參見論文（https:///abs/2006.00701）。

MovieLens 是一個(gè)包含多個(gè)用戶對(duì)多部電影評(píng)分的公開數(shù)據(jù)集，我們可以用它來模擬電影推薦。我們通過src/dataset.py 來構(gòu)建環(huán)境：我們從數(shù)據(jù)集中抽取一部分有電影評(píng)分?jǐn)?shù)據(jù)的用戶，然后將評(píng)分矩陣通過 SVD 分解來補(bǔ)全評(píng)分?jǐn)?shù)據(jù)，并將分?jǐn)?shù)歸一化到[?1,+1]。在每次交互的時(shí)候，系統(tǒng)隨機(jī)抽取一個(gè)用戶，推薦算法獲得特征，并選擇一部電影進(jìn)行推薦，MovieLensEnv會(huì)在打分矩陣中查詢?cè)撚脩魧?duì)電影對(duì)評(píng)分并返回，從而模擬用戶給電影打分。

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))

每來一個(gè)用戶，LDP LinUCB 算法根據(jù)用戶和電影的聯(lián)合特征x基于當(dāng)前的模型來選擇最優(yōu)的電影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

系統(tǒng)收到更新量之后，更新模型參數(shù)如下：

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)

我們測(cè)試不同的 \varepsilonε 對(duì)累積 regret 對(duì)影響：

• x 軸：交互輪數(shù)
• y 軸：累積 regret

相關(guān)模型代碼已上線 MindSpore Model Zoo：https:///mindspore/mindspore/tree/master/model_zoo感興趣的可自行體驗(yàn)。

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:///mindspore/mindspore/tree/master/model_zoo/research/rl/ldp_linucb

本文分享自華為云社區(qū)《MindSpore 首發(fā)：隱私保護(hù)的 Bandit 算法，實(shí)現(xiàn)電影推薦》，原文作者：chengxiaoli。