Paper: Privacy-preserving bandits
安全计算Secure computation
General idea: there is a function on all of data as the union of each owner’s data. Each owner doesn’t need to share or send his data to a common place to run the function but still can get the result from the function.
大家都不用把确切数据告诉别人（或曰：真实数据从未离开过自己），最后仍然能得到联合计算的结果。
安全计算适用于： 凡是一个计算任务需要用到来自多个参与者的数据，但各个参与者又不想（或不被允许）交换或公开数据。
计算方法
基于噪音的：基本思想：让原始数据淹没在噪音中，使别有用心者无法从得到的结果反推原始数据
噪音的增加方法：
- 对输入数据加噪音
- 对模型参数加噪音
- 对输出加噪音
评价：效率高，会伤害模型质量
- 会不会伤害模型的质量？会的。
不基于噪音的：基本思想：通过密码学方法将数据编码或加密，得到一些奇怪的数字。这些数字保持了原始数据的某些关系。在源头上对数据加密或编码，计算操作方法看到的都是密文。主要包括三种方法
-
- RSA：支持的是同态乘法
评价：不会对计算过程加干扰。缺点：使用了很多密码学方法，计算量通讯量庞大。对于复杂的任务，短时间内可能无法完成。
差分隐私Differential Privacy
保护的是数据源中一点微小的改动导致的隐私泄露问题。比如有一群人出去聚餐，那么其中某人是否是单身狗就属于差分隐私。
定义
相邻数据集
现给定两个数据集D和D’, 若它们有且仅有一条数据不一样，那我们就称此二者为相邻数据集。
算法能达到差分隐私的效果
- 对于一个随机化算法 $A$
- 所谓随机化算法，是指对于特定输入，该算法的输出不是固定值，而是服从某一分布
- 其分别作用于两个相邻数据集
- 得到的两个输出分布难以区分：得到一个特定输出的概率差不多。$\Pr[A(D)=O]\leq e^\epsilon \Pr[A(D’)=O]$
放松版定义
有delta：$\Pr[A(D)=O]\leq e^\epsilon \Pr[A(D’)=O] + \delta$
方法
- 加噪音
- 拉普拉斯噪音：由于拉普拉斯分布的数学性质正好与差分隐私的定义相契合
- 高斯噪音：针对于放松版的差分隐私。
Bandit
定义
多臂赌博机问题：一个赌徒，要去摇老虎机，走进赌场一看，一排老虎机，外表一模一样，但是每个老虎机吐钱的概率可不一样，他不知道每个老虎机吐钱的概率分布是什么，那么想最大化收益该怎么整？
在计算广告和推荐系统领域，针对这个问题，还有个说法叫做EE问题：exploit－explore问题。
exploit意思就是：比较确定的兴趣，当然要用啊。好比说我们已经挣到的钱，当然要花啊；
explore意思就是：不断探索用户新的兴趣才行，不然很快就会出现一模一样的反复推荐。就好比我们虽然有一点钱可以花了，但是还得继续搬砖挣钱啊，不然花完了喝西北风啊。
评价标准
累积遗憾：
$$
R_T=\sum_{i=1}^T (w_{opt}-w_{B(i)})
$$
算法
Thompson sampling：每次选择臂的方式是：用每个臂现有的beta分布产生一个随机数b，选择所有臂产生的随机数中最大的那个臂去摇。
UCB算法（全称是Upper Confidence Bound（置信区间上界））：就是以收益（bonus）均值的置信区间上限代表对该arm未来收益的预估值。
置信区间可以简单地理解为不确定性的程度，区间越宽，越不确定，反之亦反之。
每个item的回报均值都有个置信区间，随着试验次数增加，置信区间会变窄（逐渐确定了到底回报丰厚还是可怜）。
每次选择前，都根据已经试验的结果重新估计每个item的均值及置信区间。
选择置信区间上限最大的那个item。
做法：每次先对每一个臂都试一遍，然后选择以下值最大的那个臂：
$$
\bar{x}j (t) + \sqrt{ \frac{2 \ln t}{T{j,t} } }
$$- $x_j(t)$：这个臂$j$到目前的收益均值，即对臂$j$期望收益的预估
- $t$：截止到目前总的试验次数
- $T_{j,t}$: 臂$j$被试到的次数
诠释：
- 前一项触发exploitation机制，均值（期望收益）越高，被选中的概率越大
- 后一项触发exploration机制，累积被选中的次数越少，之后被选中的概率越大
Epsilon-greedy算法：
做法：选一个(0,1)之间较小的数epsilon ，每次以概率epsilon（产生一个[0,1]之间的随机数，比epsilon小）做一件事：所有臂中随机选一个。否则，选择截止当前，平均收益最大的那个臂。
epsilon的值可以控制对Exploit和Explore的偏好程度。越接近0，越保守。
完全朴素的算法：先试几次，每个臂都有了均值之后，一直选均值最大那个臂。这个算法是我们人类在实际中最常采用的。
LinUCB: zhihu3
- 启发：UCB这样的context-free类算法，没有充分利用推荐场景的上下文信息，为所有用户的选择展现商品的策略都是相同的，忽略了用户作为一个个活生生的个体本身的兴趣点、偏好、购买力等因素都是不同的，因而，同一个商品在不同的用户、不同的情景下接受程度是不同的。
- 特点：
- 加入了用户和物品的特征，即context。
- 收益是特征的线性函数：Lin(linear): $\mathbb{E}[r_{a,t}|x_{a,t}]=x_{a,t}^\top \theta_a$
- $x_{a,t}$是每个老虎机的特征
- $\theta$ 是模型的参数，每个老虎机维护一个$\theta$
- 使用每个老虎机的前$m$个特征向量$x$和遗憾值$r$，用岭回归的方法，可以求解$\theta$
算法分类：
- context-free:Thompson sampling, UCB, Epsilon-greedy, naive
- contextual: LinUCB
应用
推荐系统冷启动问题：
用分类或者Topic来表示每个用户兴趣，我们可以通过几次试验，来刻画出新用户心目中对每个topic的感兴趣概率。
这里，如果用户对某个topic感兴趣，就表示我们得到了收益，如果推给了它不感兴趣的topic，推荐系统就表示很遗憾(regret)了。
当一个用户来了，针对这个用户，我们用Thompson算法为每一个topic采样一个随机数，排序后，输出采样值top N 的推荐item。注意，这里略有改动，原始多臂问题每次只摇一个臂，我们这里一次摇N个臂。
获取用户的反馈，比如点击。没有反馈则更新对应topic的lose值，点击了则更新对应topic的wins值。
