0%

绪论

image-20220502141142624.png

基本问题

  1. 强化学习的基本结构是什么?

    ​ 智能体与环境的交互。(当智能体在环境中得到当前时刻的状态后,其会基于此状态 输出一个动作,这个动作会在环境中被执行并输出下一个状态和当前的这个动作得到的奖励。智能体在环 境里存在的目标是最大化期望累积奖励。)

  2. 强化学习相对于监督学习为什么训练过程会更加困难?(与监督学习的不同)

    1. 强化学习处理的大多是序列数据,其很难像监督学习的样本一样满足独立同分布条件。
    2. 强化学习有奖励的延迟,即智能体的动作作用在环境中时,环境对于智能体状态的奖励存在延迟, 使得反馈不实时
    3. 监督学习有正确的标签,模型可以通过标签修正自己的预测来更新模型,而强化学习相当于一个 “试错”的过程,其完全根据环境的“反馈”更新对自己最有利的动作。
  3. 强化学习的基本特征有哪些?

    1. 有试错探索过程
    2. 会从环境中获得延迟奖励
    3. 数据都是时间关联的
    4. 智能体的动作会影响它从环境中得到的反馈
  4. 近几年强化学习发展迅速的原因有哪些?

    算力的提升、深度强化学习端到端训练

  5. 状态和观测有什么关系?

    状态是对环境的完整描述,不会隐藏环境信息。观测是对状态的部分描述,可能会遗漏一些信息。

  6. 一个强化学习智能体由什么组成?

    策略函数、价值函数、模型(智能体对当前环境状态的理解)

  7. 根据强化学习智能体的不同,我们可以将其分为哪几类?

    基于价值的智能体、基于策略的智能体、演员-评论员

  8. 基于策略迭代和基于价值迭代的强化学习方法有什么区别?

    基于策略迭代的强化学习方法,智能体会制定一套动作策略,即确定在给定状态下需要采取何种 动作,并根据该策略进行操作。强化学习算法直接对策略进行优化,使得制定的策略能够获得最大的奖励; 基于价值迭代的强化学习方法,智能体不需要制定显式的策略,它维护一个价值表格或价值函数,并通过 这个价值表格或价值函数来选取价值最大的动作。

    基于价值迭代的方法只能应用在离散的环境下,例如围棋或某些游戏领域,对于行为集合规模庞 大或是动作连续的场景,如机器人控制领域,其很难学习到较好的结果(此时基于策略迭代的方法能够根 据设定的策略来选择连续的动作)。

面试问题

友善的面试官: 看来你对于强化学习还是有一定了解的呀,那么可以用一句话谈一下你对于强化学习的认识吗?

​ 强化学习包含环境、动作和奖励 3 部分,其本质是智能体通过与环境的交互,使其做出的动作对应的决策得到的总奖励最大,或者说是期望最大。

友善的面试官: 请问,你认为强化学习、监督学习和无监督学习三者有什么区别呢?
    1. 强化学习和无监督学习是不需要有标签样本的,而监督学习需要许多有标签样本来进行模型的构建和训练。
    2. 对于强化学习与无监督学习,无监督学习直接基于给定的数据进行建模,寻找数据或特征中隐藏的结构,一般对应聚类问题;强化学习需要通过延迟奖励学习策略来得到模型与目标的距离,这个 距离可以通过奖励函数进行定量判断,这里我们可以将奖励函数视为正确目标的一个稀疏、延迟形式。
    3. 强化学习处理的多是序列数据,样本之间通常具有强相关性,但其很难像监督学习的样本一样满足独 立同分布条件。
友善的面试官: 根据你的理解,你认为强化学习的使用场景有哪些呢?

“多序列决策问题”,或者说是对应的模型未知,需要通过学习逐渐逼近真实模型的 问题。并且当前的动作会影响环境的状态,即具有马尔可夫性的问题。同时应满足所有状态是可重复到达 的条件,即满足可学习条件。

友善的面试官: 请问强化学习中所谓的损失函数与深度学习中的损失函数有什么区别呢?

深度学习中的损失函数的目的是使预测值和真实值之间的差距尽可能小,而强化学习中的损失函数的目的是使总奖励的期望尽可能大。

友善的面试官: 你了解有模型和免模型吗?两者具体有什么区别呢?

是否需要对真实的环境进行建模,免模型方法不需要对环境进行建模,直 接与真实环境进行交互即可,所以其通常需要较多的数据或者采样工作来优化策略,这也使其对于真实环 境具有更好的泛化性能;而有模型方法需要对环境进行建模,同时在真实环境与虚拟环境中进行学习,如 果建模的环境与真实环境的差异较大,那么会限制其泛化性能。

内容:

  • 毕设内容

  • NCE & InfoNCE

下周内容:

  • cs224n 生成模型

NCE

多分类问题

nlp中常常将语言模型当做一个多分类问题,经过softmax后的概率可以被看做给出上下文c,下一个单词w的条件概率分布[公式]

这里进入softmax以前的结果用[公式]表示,那么

[公式]

\(Z(C)\)常被看做”配分函数“或”归一化因子“,单词库大小[公式]常常是很大的,因此该项往往很难直接计算。(如果把配分项看做参数学习,会趋向于零完全失效)

回顾极大似然估计:

[公式]

\(\theta\)求导:

[公式]
NCE对于采样的建模

Noise Contrastive Estimation(噪声对比估计)的核心思想就是通过学习数据分布样本和噪声分布样本之间的区别,从而发现数据中的一些特性,将问题转换成了一个二分类问题,分类器能够对数据样本和噪声样本进行二分类。

假设一个特定上下文 [公式] 的数据分布为 [公式],从该分布采样的样本为正样本,记[公式],另一个与上下文无关的噪声分布为[公式]

,从该分布取出的是负样本,记为 [公式]假设现在取出了若干正负样本组成一个混合分布 [公式]负样本与正样本之比为k(正样本[公式]个,负样本[公式]个),那么有:

[公式]

假设标签 [公式] (属于哪一个分布)为伯努利分布,那么它的对数似然函数(取负值为交叉熵损失):

[公式]

目标函数需要除以正样本数目(利用大数定律可以看做是期望):

[公式]
NCE原理

将目标函数对\(\theta\) 求导:

[公式]

对于上面两项继续求导:

  1. [公式]
  2. [公式]

将上述式子带回目标函数求导结果:

[公式]

此处存在两个细节:

  1. 假设配分项[公式](对于参数很多的神经网络来说,配分项每次求梯度时可看做固定的,我们将 [公式] 固定为 1 对每个 [公式] 仍是有效的)。

    $

    \[\begin{aligned} p_{\theta}(w \mid c) &=\frac{\exp \left(s_{\theta}(w, c)\right)}{\sum_{w^{\prime} \in V} \exp \left(s_{\theta}(w, c)\right)} \\ &=\exp \left(s_{\theta}(w, c)\right)\times \exp \left(\theta_{0}\right)\\ \end{aligned}\]

    $

    上述式子对\(\theta\) 求导只有第一项的内容,因此后面部分看做是1在梯度更新时是有利的。

    如此一来:[公式]

  2. \(k\to \infty\)时,\(\frac{k \times q(w)}{p_{\theta}(w, c)+k \times q(w)}\)的极限为1。

    [公式]
实现

实现时:一般正例采样一次,负例采样k次。

InfoNce  CPC

https://arxiv.org/abs/1807.03748

任务和目的

CPC(对比预测编码) 就是一种通过无监督任务来学习(编码)高维数据的特征表示(representation),而通常采取的无监督策略就是根据上下文预测未来或者缺失的信息(nlp中早有分布式表示的概念)。 [公式] 表示根据当前上下文 [公式] 预测 [公式] 个时刻后的数据 [公式] (假设是像文本、语音中那样的序列数据),可以通过最大化当前上下文 [公式] 和要未来的数据 [公式] 之间的互信息来构建预测任务。

[公式]

其中联合分布本身是intractable的,但是我们可以从[公式]入手,这个比例可以被看做密度比(即贝叶斯中的似然比,给定上下文c第k个单词为\(x_{t+k}\)的概率,比一般群体多了多少),分子 [公式] 就相当于 [公式] ,是我们想得到的目标函数;分母 [公式] 就相当于 [公式] ,是用来进行对比的参考分布(噪声)。因此类似NCE,将问题转化为二分类问题:

  1. 从条件 [公式] 中取出数据称为“正样本”,它是根据上下文 [公式] 所做出的预测数据,将它和这个上下文一起组成“正样本对”,类别标签设为 1。
  2. 将从 [公式] 中取出的样本称为“负样本”,它是与当前上下文 [公式] 没有必然关系的随机数据,将它和这个上下文 [公式] 一起组成“负样本对”,类别标签设为 0。
  3. 正样本也就是与 [公式] 间隔固定步长 [公式] 的数据,根据 NCE 中说明的设定,正样本选取 1 个;因为在 NCE 中证明了噪声分布与数据分布越接近越好,所以负样本就直接在当前序列中随机选取(只要不是那一个正样本就行),负样本数量越多越好。

同样可以按照NCE中的写法:

[公式]

[公式] 是一个 socring function ,输出的分数用来量化 [公式] 在上下文 [公式] 中匹配性(NCE例子中是神经网络), CPC 文章中用余弦相似度来量化,并且将 [公式] 定义为 [公式]

[公式]

写为交叉熵损失,得到:

[公式]
与互信息的关系

对于互信息的利用一般分为两类:

  1. 优化互信息上界(upper bound),一般作为正则项在pretrain使用,优化下游任务(较少)。

    Cheng P, Hao W, Dai S, et al. Club: A contrastive log-ratio upper bound of mutual information[C]//International conference on machine learning. PMLR, 2020: 1779-1788.

  2. 优化lower bound, 互信息本身是intractable,因此转化为优化lower bound

    Poole B, Ozair S, Van Den Oord A, et al. On variational bounds of mutual information[C]//International Conference on Machine Learning. PMLR, 2019: 5171-5180.

InfoNCE是第二种互信息估计,最小化 InfoNCE,也就等价于最大化 [公式][公式] 之间互信息的下限:

[公式]
与MINE关系

这篇论文中作者还将infoNCE与MINE(另一个互信息估计)做了比较,infoNCE比MINE多了个常数。对于复杂任务,两者效果都很好,但对于简单任务MINE会不稳定。

内容:

  • louis philippe morency 《多模态机器学习》 完成

  • kaggle fashion recommendation competition:

    1. 利用swing transformers提取了图片特征
  • 论文阅读:

    1. sequential recommendation
    2. boosting相关

1 sequential recommendation

Session-based recommendations with recurrent neural networks(ICLR 2016)

背景:

GRU4rec是使用神经网络做序列推荐的经典基于会话的推荐方法(基本根据物品推荐,缺少用户侧信息),这篇文章出现前主要有基于物品的协同过滤和基于马尔可夫决策过程的方法。

  • 基于物品的协同过滤,需要维护一张物品的相似度矩阵,当用户在一个session中点击了某一个物品时,基于相似度矩阵得到相似的物品推荐给用户。这种方法简单有效,并被广泛应用,但是这种方法只把用户上一次的点击考虑进去,而没有把前面多次的点击都考虑进去。
  • 基于马尔可夫决策过程(MDP)的推荐方法,其主要学习的是状态转移概率,即点击了物品A之后,下一次点击的物品是B的概率,并基于这个状态转移概率进行推荐。这样的缺陷主要是随着物品的增加,建模所有的可能的点击序列是十分困难的

主要内容:

输入:对于一个Session中的点击序列\(x=[x_1,x_2,x_3...x_{r-1},x_r]\),依次将\(x_1,x_2,x_3...x_{r-1},x_r\)输入到模型中。

模型:序列中的每一个物品xt被转换为one-hot,随后转换成其对应的embedding,经过N层GRU单元后,经过一个全联接层得到下一次每个物品被点击的概率。

loss:

  1. bpr:\({\cal L}_{s}=-\frac{1}{N_{S}}\cdot\sum_{j=1}^{N_{S}}{\sigma}\left(\hat{r}_{s,i}\,-\,\hat{r}_{s,j}\right)\)。经典bpr让正样本和负样本之间得分差尽可能大。
  2. top1:\({\cal L}_{s}=\frac{1}{N_{S}}\cdot\sum_{j=1}^{N_{S}}{\sigma}\left(\hat{r}_{s,j}\,-\,\hat{r}_{s,i}\right)\,+\,\sigma\,\left(\hat{r}_{s,j}^{2}\right)\)第一项让正负样本之间差尽可能大(与bpr稍微有区别),第二项对负样本添加了正则项。

trick:

  1. parallel:为了更好的并行计算,论文采用了 mini-batch 的处理,即把不同的session拼接起来(看纵向)

  2. sampling on output:物品数量如果过多的话,模型输出的维度过多,计算量会十分庞大,因此在实践中一般采取负采样的方法。论文采用了取巧的方法来减少采样需要的计算量,即选取了同一个batch 中其他 sequence 下一个点击的 item作为负样本,用这些正负样本来训练整个神经网络。

Recurrent Neural Networks with Top-k Gains for Session-based Recommendations(CIKM 2018)

背景:

这篇文章从采样和损失函数角度对GRU4rec进行了优化,即很多序列推荐论文中的GRU4rec+对比算法。

主要内容

采样
img

在GRU4rec基础上,除了batch sampling(从batch中快速得到负样本),作者引入了额外的负样本(所有batch共享的)。

loss
  1. cross-entropy:

    L_{xe} = -log,s_i = -log, 当存在一个 r_k >> r_i 时,s_i 趋近于 0log,0 未定义,造成结果不稳定。针对这个问题论文提出了2种代替 -log,s_i 的计算方式:

    • -log(s_i + ),其中 = 10^{-24}
    • 去掉\(r_i\)对应的log,降低其为0情况-r_i + log,_{j=1}^{N} e^{r_j}
  2. ranking losses:

    • TOP1 L_{top1} =  {j=1}^{N_s} (r{j} - r_{i}) + (r_{j} ^2)
    • BPR [L_{bpr} =- _{j=1}^{N_s} log((r_i - r_j))](https://math.jianshu.com/math?formula=L_%7Bbpr%7D%20%3D-%20%5Cfrac%7B1%7D%7BN_s%7D%20%5Csum_%7Bj%3D1%7D%5E%7BN_s%7D%20log(%5Csigma%20(r_i%20-%20r_j))

    其中,N_s 为负样本量大小,r_k 为 item k 的分数,i 代表正样本,j 代表负样本。

    这两种损失函数主要缺点是会发生梯度消失的现象,如当 r_{j} << r_i 时,(r_{j} - r_{i})1-(r_i - r_j) 都会趋近于 0,从而导致梯度消失(负样本得分远小于正样本);同时对负样本取平均值会加速这种梯度消失的现象(样本量越多,平均值越小)。

    [ = - {j=1}^{N_s} (r{j} - r_{i}) (1- (r_{j} - r_{i}))](https://math.jianshu.com/math?formula=%5Cfrac%7B%5Cpartial%20L_%7Btop1%7D%7D%7B%5Cpartial%20r_i%7D%20%3D%20-%20%5Cfrac%20%7B1%7D%7BN_s%7D%20%5Csum_%7Bj%3D1%7D%5E%7BN_s%7D%20%5Csigma%20(r_%7Bj%7D%20-%20r_%7Bi%7D)%20(1-%20%5Csigma%20(r_%7Bj%7D%20-%20r_%7Bi%7D))

    [ =- _{j=1}^{N_s} (1-(r_i - r_j))](https://math.jianshu.com/math?formula=%5Cfrac%7B%5Cpartial%20L_%7Bbpr%7D%7D%7B%5Cpartial%20r_i%7D%20%3D-%20%5Cfrac%7B1%7D%7BN_s%7D%20%5Csum_%7Bj%3D1%7D%5E%7BN_s%7D%20(1-%5Csigma%20(r_i%20-%20r_j))

  3. ranking-max losses:

    为了克服梯度消失的情况,作者提出了ranking-max的loss框架:

    \({\cal L}_{\mathrm{pairwise-max}}\left(r_{i},\{r_{j}\}_{j=1}^{N_{S}}\right)={\cal L}_{\mathrm{pairwise}}(r_{i},{\bf m}_{\mathrm{ax}}\,r_{j})\)

  • TOP1-max [L_{top1-max} = {j=1}^{N_s} s_j((r{j} - r_{i}) + (r_{j} ^2))](https://math.jianshu.com/math?formula=L_%7Btop1-max%7D%20%3D%20%5Csum_%7Bj%3D1%7D%5E%7BN_s%7D%20s_j(%5Csigma%20(r_%7Bj%7D%20-%20r_%7Bi%7D)%20%2B%20%5Csigma%20(r_%7Bj%7D%20%5E2))

[ = - {j=1}^{N_s}s_j (r{j} - r_{i}) (1- (r_{j} - r_{i}))](https://math.jianshu.com/math?formula=%5Cfrac%7B%5Cpartial%20L_%7Btop1-max%7D%7D%7B%5Cpartial%20r_i%7D%20%3D%20-%20%5Csum_%7Bj%3D1%7D%5E%7BN_s%7Ds_j%20%5Csigma%20(r_%7Bj%7D%20-%20r_%7Bi%7D)%20(1-%20%5Csigma%20(r_%7Bj%7D%20-%20r_%7Bi%7D)) 其中 maxsoft score s_j 相当于权重(对每个负样本加权重,sj和为1),当 r_j 较小时,s_j 也会较小(趋近于 0),样本 j 类似于被忽略,所以不会减少整体的梯度。

  • BPR-max L_{bpr-max} =- log _{j=1}^{N_s} s_j (r_i - r_j) \({\frac{\partial{\cal L}_{\mathrm{bpr}-\mathrm{max}}}{\partial r_{k}}}=s_{k}-{\frac{s_{k}\sigma^{2}(r_{i}-r_{k})}{\sum_{j=1}^{N_{S}}s_{j}\sigma(r_{i}-r_{j})}}\) 这里的梯度信息可以看做是单个梯度的加权平均值,s_j (r_i - r_j) 相当于权重。当 r_i 较小时,权重分布较为均匀,实际得分高的将会得到更多关注;当 r_i 较大时,得分高的才会产生较大的权重,从而得到更多关注。这有利于模型的训练。

TOP1-maxBPR-max 的梯度信息均和 softmax score 成比例,这意味着只有 score 较大的 item 会被更新,这样的好处在于模型训练过程中会一直推动 target 往排序列表的顶部前进,而常规的 TOP1 和 BPR 在 target 快接近顶部的时候,平均梯度信息更小了,更新几乎停滞,这样很难将 target 推至顶部。

  • BPR-max with score regularization 受 TOP1 添加正则项的启发,对 BPR 添加正则项,同样能提高模型的表现。 L_{bpr-max} =- log {j=1}^{N_s} s_j (r_i - r_j) + {j=1}^{N_s} s_j r_j^2 其中, 为正则项参数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# 传统bpr
class BPRLoss(nn.Module):
def __init__(self):
super(BPRLoss, self).__init__()

def forward(self, logit):
"""
Args:
logit (BxB): Variable that stores the logits for the items in the mini-batch
The first dimension corresponds to the batches, and the second
dimension corresponds to sampled number of items to evaluate
B,N
"""
# differences between the item scores
diff = logit.diag().view(-1, 1).expand_as(logit) - logit
# final loss
loss = -torch.mean(F.logsigmoid(diff))
return loss


class BPR_max(nn.Module):
def __init__(self):
super(BPR_max, self).__init__()
def forward(self, logit):
# 通过softmax表示sj
logit_softmax = F.softmax(logit, dim=1)
diff = logit.diag().view(-1, 1).expand_as(logit) - logit
loss = -torch.log(torch.mean(logit_softmax * torch.sigmoid(diff)))
return loss
# top1loss

class TOP1Loss(nn.Module):
def __init__(self):
super(TOP1Loss, self).__init__()
def forward(self, logit):
"""
Args:
logit (BxB): Variable that stores the logits for the items in the mini-batch
The first dimension corresponds to the batches, and the second
dimension corresponds to sampled number of items to evaluate
"""
diff = -(logit.diag().view(-1, 1).expand_as(logit) - logit)
loss = torch.sigmoid(diff).mean() + torch.sigmoid(logit ** 2).mean()
return loss


class TOP1_max(nn.Module):
def __init__(self):
super(TOP1_max, self).__init__()

def forward(self, logit):
logit_softmax = F.softmax(logit, dim=1)
diff = -(logit.diag().view(-1, 1).expand_as(logit) - logit)
loss = torch.mean(logit_softmax * (torch.sigmoid(diff) + torch.sigmoid(logit ** 2)))
return loss

基于注意力的方法& transformer-based methods:

SASRec: Self-Attentive Sequential Recommendation(ICDM 2018)

背景:

之前的序列建模方法:

  • 基于MC的方法,通过一个简单的假设,进行信息的状态转移。在高稀疏数据下表现好,但在更复杂的场景中很难捕捉到有用的信息,文章实验也证明了这点;
  • 基于RNN的方法有很强的表达能力,但是训练需要大量的数据,在密集型数据集下表现得更好,且因为每一个隐藏状态都必须依赖于前一个,运行效率较低;

注意力机制背后的思想是连续的输出都依赖于某个输入的“相关”部分,而模型应该连续地关注这些输入,在推荐领域,AFM、DIN模型已经得到了很好的应用,详见基于注意力的方法

主要内容:

图片
  1. Postional embedding(PE):即transformer中的位置编码表示先后顺序。对于稀疏数据集可不加pe,因为用户没有太多的记录,因此购买顺序没有太大关系。
[公式]
  1. Self-Attention层

    原transformer中self-attention(K=V):

    [公式]

    在本文中对应的是[公式]

    此时K!=V,作者认为这样可以让模型更加灵活,比如对于<query q, key k>以及< key k, query q>就可以有不同的表示。

    此外, 考虑到不同维度隐藏特征的非线性交互,本文与Transformer一样,在self-attention之后,采取两层的前馈网络:

  2. stack transformer

    一般而言叠加多个自注意力机制层能够学习更复杂的特征转换,但会存在一些问题:

    1. 模型更容易过拟合;

    2. 训练过程不稳定(梯度消失问题等);

    3. 模型需要学习更多的参数以及需要更长的时间训练;

      因此,作者在自注意力机制层和前馈网络「加入残差连接、Layer Normalization、Dropout」来抑制模型的过拟合。(依旧按照transformer设置)

    [公式]
  3. prediction(与训练好的item embeddings做点积,实际实现时用的都是同一个item embedding)

    [公式]

    作者还尝试通过引入user embedding,但是没有提高性能:

    [公式]

对比BST(KDD2019)

Behavior Sequence Transformer for E-commerce Recommendation in Alibaba这篇论文同样是使用了transformer应用在序列推荐中,但是BST面向排序阶段(SAS面向召回阶段),把序列推荐看成一个CTR任务, 引入了(other features: 用户基本特征、物品基本特征、上下文信息等),模型结构:

img

FDSA: Feature-level Deeper Self-Attention Network for Sequential Recommendation(IJCAI 2019)

背景:

SAS只考虑物品之间的顺序模式,而忽略了有助于捕获用户细粒度兴趣偏好的特征之间的顺序模式。 事实上,我们的日常item-item关系是十分重要的。例如,用户在买了衣服之后更可能买鞋子,显示出了下一个产品的类别与当前产品的类别具有高度的相关性。

作者将用户对结构化属性(例如类别)不断变化的需求称为显式的特征转换。此外,物品还可能包含一些非结构化属性,如描述文本或图像,这些属性表示物品的更多细节。因此,作者希望从这些非结构化属性中挖掘用户潜在的特征级别模式,称之为隐式特征转换。

因此FDSA通过对物品序列和特征序列分别应用不同的自注意块,对显式和隐式特征转换进行建模。为了获得隐式的特征转换,增加了一种vanilla注意机制,以帮助基于特征的自注意力块自适应地从各种物品属性中选择重要的特征。

主要工作:
在这里插入图片描述

FDSA由5部分组成,Embedding layer, Vanilla attention layer, Item-based self-attention block, Feature-based self-attention block, 以及FFN。

  1. 首先将稀疏的物品以及物品的离散属性映射到低维稠密向量(embedding)。对物品的文本属性,利用主题模型提取关键词,然后利用word2vec获得关键词的文本向量表示。

  2. 物品的特征通常是异构的,利用传统注意力从物品的各种特征中选择重要的特征。

    在这里插入图片描述

    $ vec(c_i), vec(b_i) \(为物品类别和品牌的稠密向量表示,\) vec(item_i^{text}) $ 表示文本i的文本特征表示。

    注意力得分为:在这里插入图片描述

  3. 物品级和序列级特征分别输入transformer,最后拼接在一起得到最后预测结果。

BERT4Rec: Sequential Recommendation with Bidirectional Encoder Representations from Transformer(CIKM 2019)

将Bert应用到推荐,完全相同的模型(没有next sentence prediction,因为无意义)。

img

S3-Rec: Self-Supervised Learning for Sequential Recommendation with MIM(CIKM2020)

背景:
  1. 现有的神经网络模型利用预测损失来学习模型参数或者嵌入表征,但是这样的训练受限于数据稀疏问题。

  2. 各类数据之间的关系没有被充分挖掘出来——上下文数据和序列数据之间的关联或融合一直不太好捕捉并用于序列推荐(pretrain对于提高性能有影响,说明直接单一目标函数训练是不够的)。

主要内容:

S3-rec利用原有数据的相关性来构建自监督信号,并通过预训练方法来增强数据表示,以改善序列推荐。它利用互信息最大化(MIM)原理来学习属性,物品,子序列和序列之间的相关性。

互信息最大化

互信息:信息论中,互信息是不确定性减少的度量。让互信息最大化,就是让不确定性尽可能降低,充分挖掘数据之间的关系。

img
img

互信息(KL(p(x,y)||p(x)p(y)))一般通过NCE实现(NCE来自NLP,是互信息的下限https://arxiv.org/pdf/1807.03748.pdf):

[公式]

https://zhuanlan.zhihu.com/p/334772391

https://zhuanlan.zhihu.com/p/413681189

img
模型
在这里插入图片描述
  1. Modeling Item-Attribute Correlation:最大化物品和属性间的互信息。img

    对于每个物品,属性都提供其细粒度信息。 因此通过对物品-属性相关性进行建模来融合物品和属性级别的信息。以这种方式,期望将有用的属性信息融入到物品表示中。

    用双线性模型建模属性向量之间相关性:

    img

    NCEloss:

    img
  2. Modeling Sequence-Item Correlation

    img

    和bert4rec, 一样在每个训练步骤中,随机掩盖输入序列中的一部分物品(即,将它们替换为特殊标记“ [mask]”)。 然后,基于两个方向上的上下文从原始序列中预测被mask的物品。

    对应loss(F代表mask位置预测的embedding):

    img
    img
  3. Modeling Sequence-Attribute Correlation

    img

    融合序列上下文和物品属性信息(现有方法很少这样关联的):

    img
    img
  4. Modeling Sequence-Segment Correlation

    img

    物品序列与单词序列之间的主要区别在于单个物品项目可能与周围环境没有高度关联。例如,用户仅仅因为某些产品就在购买中而购买了它们,严格的上下文信息并不是决定因素。因此作者还考虑了子序列(序列模式,不是考虑严格位置关系,考虑相对位置关系)。

    img
    img
训练

模型训练包括预训练和微调两个阶段,预训练过程中利用上面的4个Loss即4个子任务通过无掩码的自注意力机制进行训练,得到高质量的物品表征和属性表征

微调阶段再来使用pairwise loss训练:

img

2 BOOSTING

GB

梯度提升(Gradient Boost)核心思想是,用多个弱分类器(比如生成的子树)来构建一个强分类器(最终集成出来的树)。每一棵树(以回归树为例)学习的是之前所有树结论和的残差,这个残差就是一个加预测值后能得真实值的累加量。

[公式]

GBT

梯度提升树(GBT)的一个核心思想是利用损失函数的负梯度在当前模型的值作为残差的近似值,本质上是对损失函数进行一阶泰勒展开,从而拟合一个回归树。

一阶泰勒:[公式]

对应损失函数展开:

[公式]
[公式]

其中对于平方或指数损失函数,就是通常意义上的残差。对于其他普通函数,残差是导数的近似值。用于回归模型时,是梯度提升回归树GBRT;梯度提升树用于分类模型时,是梯度提升决策树GBDT;二者的区别主要是损失函数不同。

XGBoost

算法

目标函数:
[公式]
[公式]

相比GBDT引入了正则项, [公式] 表示给定一颗树的叶节点数,决策树定义为 [公式][公式] 为某一样本,这里的 [公式] 表示该样本所在的叶子结点,[公式] 为叶子结点权重 [公式],所以得出 [公式] 为每个样本的取值 [公式](即预测值)。所以 [公式] 表示每颗树叶节点上的输出分数的平方(相当于L2正则)

在通常的模型中针对这类目标函数可以使用梯度下降的方式进行优化,但注意到 [公式] 表示的是一颗树,而非一个数值型的向量,所以不能使用梯度下降的方式去优化该目标函数。在此作者提出了使用 前向分步算法(additive manner)。

目标函数为: [公式]

其中第 i 个样本在第 t 颗树的预测值 ([公式])等于样本 i 在前 t-1 棵树的预测值( [公式] ) 加当前第 t 颗树预测值( [公式] ) 公式表达为: [公式]

对于该函数的优化,在 XGBoost 中使用了泰勒展开式,与 GDBT 不同的是 XGBoost 使用了泰勒二次展开式。

[公式]

使 [公式]

这里是针对 [公式] 的求导,所以可以将 [公式] 部分看成常数去掉。

得出简化后的损失函数:

[公式]

如果确定了树的结构,为了使目标函数最小,可以令其导数为0,解得每个叶节点\(j\)的最优预测分数为:

[公式]

[公式] 代入简化后的目标函数得到最小损失为:[公式]

[公式] 则有:[公式]

直观上看,判断一棵树的好坏,就可以根据上面的\(L^{(t)}\)进行判断,loss越小(注意loss中的负号),代表树的结构越好。

作者在划分时用了贪心算法。假设在某节点分裂了左 [公式] ,右节点 [公式] 且满足 如果确定了树的结构(即q(x)确定),为了使目标函数最小,可以令其导数为0,解得每个叶节点的最有预测分数为:[公式] ,

那么分裂后增益 可以表示为: [公式]

该值越大,说明分裂后能使目标函数减少越多,就越好。此方法被用于 XGBoost 判断最优特征以及最优切分点。

Shrinkage & 列降采样
  • Shrinkage 策略(权重衰减,类似 LSTM)。比如把整个训练过程看作一个时间序列,离当前树时间点越靠前的权重对当前权重的累加影响越小,这个衰减就是论文里的参数 [公式] 控制的。(时间做平滑)
  • 特征降采样的方法来避免过拟合,只是这里的降采样使用的是列降采样(与随机森林做法一样每次的输入特征不是全部特征,不仅能降低过拟合,还能减少计算),它的另外一个好处是可以方便加速并行化
分裂点

每个树生成的问题都要考虑到两个问题是:1)按照哪个维度 / 顺序组合切 2)如何判断*最佳切分点*

  1. 贪心算法

    从树的根节点开始,对每个叶节点枚举所有的可用特征。此处文中指出:对该节下的数据需令其按特征值进行排序,这样做可以使计算分裂收益值更加高效,*分裂收益值* 计算如下:

    [公式]

    然后选择该轮最大收益值作为*最佳分裂点* ,使在该节点行分裂出左右两个新的叶节点,并重新分配新节点上的样本。至此一个循环结束,继续按同样流程递归迭代直至满足条件停止。在特征维度较大的时候,内存会不够。

  2. 近似值

    作者提出将连续特征变量按照特征值分布进行分桶操作的方法,这样只需要计算每个桶中的统计信息就可以求出最佳分裂点的最佳分裂收益值。

    在确定分裂点时作者提出了两种方法:Global、Local。

    Global 表示在生成树之前进行候选切分点(candidate splits)的计算,且在整个计算过程中只做一次操作。在以后的节点划分时都使用已经提前计算好的候选切分点;Local 则是在每次节点划分时才进行候选切分点的计算。Global 适合在取大量切分点下使用; Local 更适用于深度较大的树结构。

LightGBM

https://zhuanlan.zhihu.com/p/99069186

对xgboost的优化:

  • 基于Histogram的决策树算法。

    直方图方式进行分桶, 将特征离散化(与xgboost一样仅考虑非零特征)。

    CSDN图标

    Histogram(直方图)做差加速。一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到,在速度上可以提升一倍。

  • 单边梯度采样 Gradient-based One-Side Sampling(GOSS):使用GOSS可以减少大量只具有小梯度的数据实例,这样在计算信息增益的时候只利用剩下的具有高梯度的数据就可以了,相比XGBoost遍历所有特征值节省了不少时间和空间上的开销。

    GOSS排除大部分小梯度的样本,仅用剩下的样本计算信息增益,它是一种在减少数据量和保证精度上平衡的算法。

  • 互斥特征捆绑 Exclusive Feature Bundling(EFB):使用EFB可以将许多互斥的特征绑定为一个特征,这样达到了降维的目的。

  • 带深度限制的Leaf-wise的叶子生长策略:大多数GBDT工具使用低效的按层生长 (level-wise) 的决策树生长策略,因为它不加区分的对待同一层的叶子,带来了很多没必要的开销。实际上很多叶子的分裂增益较低,没必要进行搜索和分裂。LightGBM使用了带有深度限制的按叶子生长 (leaf-wise) 算法:

    该策略每次从当前所有叶子中,找到分裂增益最大的一个叶子,然后分裂,如此循环。因此同Level-wise相比,Leaf-wise的优点是:在分裂次数相同的情况下,Leaf-wise可以降低更多的误差,得到更好的精度;Leaf-wise的缺点是:可能会长出比较深的决策树,产生过拟合。因此LightGBM会在Leaf-wise之上增加了一个最大深度的限制,在保证高效率的同时防止过拟合。

  • 直接支持类别特征(Categorical Feature)

  • 支持高效并行

  • Cache命中率优化

week 10 内容:

  • louis philippe morency 《多模态机器学习》 90%

  • kaggle fashion recommendation competition:

    1. 完成EDA、数据预处理
    2. 用流行度、item相关性、最近购买的item三种方法,进行了提交(baseline)
  • 论文阅读:

    1. BGSP、BKM聚类
    2. fashion recommendation相关
    3. boosting相关(待完善)

1 Co-clustering

Bipartite spectral graph partition(BGSP)-SpectralCoclustering(2001)

https://scikit-learn.org/stable/modules/biclustering.html#spectral-biclustering

共同聚类,也称为双聚类,该方法在数据矩阵中同时聚类样本集和特征集。由于同时利用了样本类群和特征类群之间的关系,该方法相比传统聚类性能更优异。受互联网技术发展的影响,共聚类已成为近年来数据挖掘领域的一个研究热点。从分类角度,共聚类有两种类型:

  1. 棋盘格形式的共聚类:如下图,聚类完成后矩阵呈现棋盘格形式,该方法假设数据矩阵中每一个元素都属于一个共聚类簇。

  2. 对角共聚类:如下图,聚类完成后类簇位于矩阵对角线上,该方法仅考虑数据中的部分数据形成共聚类簇。

对于很多有着稀疏矩阵的应用来说,对角共聚类往往是更好的选择。一方面,对于棋盘格式的共聚类而言,稀疏矩阵中大部分的条目是为0的,对于共聚类没有贡献。另一方面,在实际的应用中,数据矩阵往往掺杂着许多噪声,这些噪声极大第降低了共聚性能。

在基于对角的共聚类方法中,最著名的是二部谱图划分(BSGP)方法(较快)。然而,由于BSGP在求解过程中涉及奇异值分解,因此在计算上无法用于大型数据集,这严重限制了BSGP在实际应用中的范围。此外,BSGP基于谱图的双分区Ncuts。在处理多分区问题时,首先需要将原离散问题放宽为一个连续问题,然后使用k-means算法输出离散结果。在这种离散-连续-离散变换过程中,最终得到的优化问题与BSGP的原始目标问题有很大的偏差,会损害BSGP的性能。

BSGP(Bipartite spectrum graph partitioning)共聚类,首先构建二部图\(G=\{V, A\}\),V是点集, 设\(X\in{R}^{d \times n}\)

\(\boldsymbol{A}=\left[\begin{array}{cc} \boldsymbol{0} & \boldsymbol{X} \\ \boldsymbol{X}^{T} & \boldsymbol{0} \end{array}\right]\)

feature cluster: \(\boldsymbol{P}=\left[\boldsymbol{p}_{1 \cdot}^{T}, \cdots, \boldsymbol{p}_{d \cdot}^{T}\right]^{T} \in\{0,1\}^{d \times c}\)

sample cluster: \(\boldsymbol{Q}=\left[\boldsymbol{q}_{1 \cdot}^{T}, \cdots, \boldsymbol{q}_{d \cdot}^{T}\right]^{T} \in\{0,1\}^{n \times c}\)

对聚类完成后的cluser定义(保证cluster中的元素比其他划分方法更好):

feature cluster:

\(\Omega_{l}=\{x_{i\cdot}:\sum_{j\in\Theta_{l}}X_{i j}\geq\sum_{i\in\Theta_{k}}X_{i j},\forall k=1,\cdot\cdot\cdot,c\}\)

sample cluster:

\(\Theta_{l}=\{x_j:\sum_{i\in\Omega,}X_{i j}\geq\sum_{i\in\Omega_{i}}X_{i j},\forall k=1,\cdot\cdot\cdot,c\}\)

很容易看出\(\Omega_l\)\(\theta_l\)之间存在递归关系,同时这也决定了BSGP基与diagonal co-cluster。

二划分的优化:

BGSP为了找到G最小的ncuts,优化如下的问题:

\(\min _{\boldsymbol{y}} \frac{\boldsymbol{y}^{T} \boldsymbol{L} \boldsymbol{y}}{\boldsymbol{y}^{T} \boldsymbol{D} \boldsymbol{y}}, \text { s.t. } \boldsymbol{y} \in\{-1,1\}^{(d+n) \times 1}\)

其中,\(D\)是度矩阵\(D_{ii} = \textstyle\sum_{k}A_{i k}\)

拉普拉斯矩阵: \(L = D - A\)

partition :

\(y=[p^{T},q^{T}]^{T},p\in\{1,-1\}^{d\times1},q\in\{1,-1\}^{n\times1}\) 是indicator vector

由于上述优化目标是NP-complete problem,进行松弛:

\(\operatorname*{min}_{q\neq0}{\frac{q^{T}L q}{q^{T}D q}},s.t.q^{T}D e=0\)

其中\(e\)\((d + n) \times 1\)全1的向量,考虑到数据矩阵A的结构,可使用SVD计算\(D_1^{-1/2}XD_2^{-1/2}\)的第二小奇异值对应的向量来求解。\(D1, D2\)满足:

\(\boldsymbol{D}=\left[\begin{array}{ll} \boldsymbol{D}_{1} & \\ & \boldsymbol{D}_{2} \end{array}\right]\)

多个类群的扩展:

对于含有c个类群的情况,需要计算\(l = log_2(c)\)个left vectors U和right vectors V

构成一个L维度的数据集:

\(\boldsymbol{Z}=\left[\begin{array}{l} \boldsymbol{D}_{1}^{-1 / 2} \boldsymbol{U} \\ \boldsymbol{D}_{2}^{-1 / 2} \boldsymbol{V} \end{array}\right]\)

最后,需要用k-means算法对新的数据集Z进行聚类,其中Z的前d个结果对应X的特征聚类结果,后n个结果对应样本聚类结果。

BGSP中的问题:

  1. 需要一个后处理步骤来输出聚类结果
  2. 涉及奇异值分解(SVD),其复杂度大于\(O(n^2d)\)

Bilateral k-Means Algorithm for Fast Co-Clustering(IJCAI 2017)

优化目标

BGSP中多类群的优化目标为:

\(\operatorname*{min}_{Y}\sum_{k=1}^{c}\frac{y_{k}^{T}L y_{k}}{y_{k}^{T}D y_{k}},s.t.{\cal Y}\in\Phi_{(d+n)\times c}\)

由于\(y_k^{T}Dy_k = Y^TDY\),因此优化目标转化为:

\(\operatorname*{min}_{Y}Tr(Y^{I}LY\{Y^{I}D Y)^{-1}),s.t.Y\in\Phi_{(m+n)\chi c}\)

由于\(Y^{T}=[P^{T},Q^{T}]\),因此可以把A拆为X,即\(T r(I-Y^{T}A Y(Y^{T}D Y)^{-1}) = T r(I-2P^{T}X Q(Y^{T}D Y)^{-1})\)

优化目标转变为:

\(\operatorname*{min}_{P.Q}T r(-P^{T}X Q(Y^{T}D Y)^{-1})\)

\(s.t.P\in\Phi_{d\times c},Q\in\Phi_{n\times c}\)

为了得到二范数,添加\(T r((Y^{T}D Y)^{-1}P^{T}P(Y^{T}D Y)^{-1}Q^{I}Q)\)以及\(T r(X^{T}X)\)两项,得到优化目标:

\(\operatorname*{min}_{P.Q}\|X-P(Y^{T}D Y)^{-1}Q^{T}\|_{F}^{2}\)

\(s.t.P\in\Phi_{d\times c},Q\in\Phi_{n\times c}\)

\((Y^{T}D Y)^{-1}\)是对角阵,求逆矩阵的开销很大,为了简化,用对角阵S代替,S也是待优化的参数:

\(\operatorname*{min}_{P,O_{S}}\|X-P S Q^{T}\|_{F}^{2}\)

\(s.t.P\in\Phi_{d\times c},Q\in\Phi_{n\times c},\;S\in d i a g\)

优化方法

使用两个命题来简化目标:

\(J_{1}=||X-P S Q^{T}||_{F}^{2} =T r(X^{T}X)-2T r(Q^{T}X^{T}P S) +T r(S P^{T}P S Q^{T}Q)\)

由于P和Q是indicator matrix, 所以\(P^{T}P\)以及\(Q^{T}Q\)是对角阵,

由第一个命题:

\(T r(Q^{T}X^{T}P S)=f({\cal S})^{T}f(P^{T}X Q)\)

由第二个命题可知:

\(T_{r}(S P^{T}P S Q^{T}Q)=T r(S P^{T}P Q^{T}Q S)=f(S)^{T}(P^{T}P Q^{T}Q)f(S)\)

\(H\)表示\(P^T PQ^T Q\), \(s\)表示\(f(s)\) \(r\)表示\(f(P^T XQ)\),那么有:

\(J_{1}=T r(X^{T}X)-2{\bf r}^{T}{\bf s}+{\bf s}^{T}{H}s\)

  1. 求解s:

\({\frac{\partial J_{1}}{\partial s}}=2(H s-r)=0\)

\(s=H^{-1}r\)

由于H是对角阵,求逆很方便。

  1. 固定P、S,求Q:

    \(R = PS\)

    对每个sample进行如下优化:

    \(\operatorname*{min}_{Q}\|x_{\cdot i}-R q_{i\cdot}^{T}\|_{F}^{2}\)

    由于q是indicator,只会有一个1,那么就根据如下方式得出(\(r_k\)\(R\)的第k列):

    img
  2. 固定Q S,求P:

    \(L=SQ^T\)

    \(\operatorname*{min}_{p}||x_{j}.-p^{T}_{j}L||_{F}^{2}\)

img

\(l_k\)代表了L的第k行

2 Fasion recommendation

回顾《A Survey on Neural Recommendation: From Collaborative Filtering to Information-rich Recommendation》中,fashion recommendation是对Image information建模的代表任务,其目的在于增强可解释性。

DeepStyle: Learning User Preferences for Visual Recommendation(SIGIR 2017)

这篇文章将图片信息经过预训练好的cnn的到视觉embedding,聚类后发现相同类别的服装被聚类在一起(比如鞋子),而这与推荐任务不太符合,因为相似风格的商品往往会被同一个人同时购买(皮鞋配西装),但在视觉特征空间中却并不相似,这就为提升推荐效果带来了难度。因此作者提出一个商品(item)由风格(style)和类别(category)组成,即item = style + cate. 因此如上图,作者从商品的视觉特征向量中减除了该商品对应类别的隐含表达(类别的平均向量),进而得到了商品的风格特征向量.随后将向量输入到BPR框架中进行训练(对每个user采样正负商品样本对(正样本表示实际购买了的商品,负样本表示没有购买过的商品)),取得了很好的推荐效果。

Aesthetic-based Clothing Recommendation(www 2018)

传统的方法只考虑 CNN 抽取的图像特征;而本文考虑了图片中的美学特征对于推荐的影响;作者利用 BDN 从图片中学习美学特征,然后将其融合到 DCF 中,增强用户-产品,产品-时间矩阵,从而提高了推荐效果。

3 Boosting

回顾CART:

算法 支持模型 树结构 特征选择 连续值处理 缺失值处理 剪枝
ID3 分类 多叉树 信息增益 不支持 不支持 不支持
C4.5 分类 多叉树 信息增益比 支持 支持 支持
CART 分类回归 二叉树 基尼系数 均方差 支持 支持 支持

C4.5决策树用较为复杂的熵(信息增益比)来度量,使用了相对较为复杂的多叉树,只能处理分类不能处理回归。CART(Classification And Regression Tree)做了改进,可以处理分类,也可以处理回归。

信息度量

ID3中使用了信息增益选择特征,增益大优先选择。C4.5中,采用信息增益比选择特征,减少因特征值多导致信息增益大的问题。CART分类树算法使用基尼系数来代替信息增益比,基尼系数代表了模型的不纯度,基尼系数越小,不纯度越低,特征越好。这和信息增益(比)相反。

  假设K个类别,第k个类别的概率为\(p_k\),概率分布的基尼系数表达式:

img

  如果是二分类问题,第一个样本输出概率为p,概率分布的基尼系数表达式为:

img

  对于样本D,个数为\(|D|\),假设K个类别,第k个类别的数量为\(|C_k|\),则样本D的基尼系数表达式:

img

  对于样本D,个数为\(|D|\),根据特征A的某个值\(a\),把D分成\(|D1|\)\(|D2|\),则在特征A的条件下,样本D的基尼系数表达式为:

img

  比较基尼系数和熵模型的表达式,二次运算比对数简单很多。尤其是二分类问题,更加简单。

对于二类分类,基尼系数和熵之半的曲线如下:

img

  基尼系数和熵之半的曲线非常接近,因此,基尼系数可以做为熵模型的一个近似替代。

  CART分类树算法每次仅对某个特征的值进行二分,而不是多分,这样CART分类树算法建立起来的是二叉树,而不是多叉树。

特征处理

对于连续的特征:

同C4.5一样将连续特征离散化,从小到大选相邻两样本值的平均数作为划分点,找基尼系数最小的划分。但与ID3、C4.5不同的是它后面还可以参与子节点的划分过程。

对于离散的特征:

ID3、C4.5,特征A被选取建立决策树节点,如果它有3个类别A1,A2,A3,我们会在决策树上建立一个三叉点,这样决策树是多叉树。CART采用的是不停的二分。会考虑把特征A分成{A1}和{A2,A3}、{A2}和{A1,A3}、{A3}和{A1,A2}三种情况,找到基尼系数最小的组合,比如{A2}和{A1,A3},然后建立二叉树节点,一个节点是A2对应的样本,另一个节点是{A1,A3}对应的样本。由于这次没有把特征A的取值完全分开,后面还有机会对子节点继续选择特征A划分A1和A3。这和ID3、C4.5不同,在ID3或C4.5的一颗子树中,离散特征只会参与一次节点的建立。

流程
  1. 分类

    输入:训练集D,基尼系数的阈值,样本个数阈值。

    输出:决策树T。

    递归建立CART分类树:

      (1)、对于当前节点的数据集为D,如果样本个数小于阈值或没有特征,则返回决策子树,当前节点停止递归。

      (2)、计算样本集D的基尼系数,如果基尼系数小于阈值,则返回决策树子树,当前节点停止递归。

      (3)、计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数,对于离散值和连续值的处理方法和基尼系数的计算见第二节。缺失值的处理方法和C4.5算法里描述的相同。

      (4)、在计算出来的各个特征的各个特征值对数据集D的基尼系数中,选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值,把数据集划分成两部分D1和D2,同时建立当前节点的左右节点,做节点的数据集D为D1,右节点的数据集D为D2。

      (5)、对左右的子节点递归的调用1-4步,生成决策树。

      对生成的决策树做预测的时候,假如测试集里的样本A落到了某个叶子节点,而节点里有多个训练样本。则对于A的类别预测采用的是这个叶子节点里概率最大的类别。

  2. 回归

    与分类树不同:

    不同。

      (1)、分类树与回归树的区别在样本的输出,如果样本输出是离散值,这是分类树;样本输出是连续值,这是回归树。分类树的输出是样本的类别,回归树的输出是一个实数。

      (2)、连续值的处理方法不同。

      (3)、决策树建立后做预测的方式不同。

      分类模型:采用基尼系数的大小度量特征各个划分点的优劣。

      回归模型:采用和方差度量,度量目标是对于划分特征A,对应划分点s两边的数据集D1和D2,求出使D1和D2各自集合的均方差最小,同时D1和D2的均方差之和最小。

    img

    表达式为:

    img

    其中,c1为D1的样本输出均值,c2为D2的样本输出均值。

      对于决策树建立后做预测的方式,CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。回归树输出不是类别,采用叶子节点的均值或者中位数来预测输出结果。

boosting

bagging和boosting是集成学习的两种代表性范式,bagging的个体弱学习器的训练集是通过随机采样得到的,学习器之间没有强依赖关系。boosting相反,每次训练都期望纠正之前的错误,学习器之间存在强依赖关系。Boosting主要关注降低偏差,因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成;Bagging主要关注降低方差,因此它在不剪枝的决策树、神经网络等学习器上效用更为明显。

工作机制

boosting方法的工作机制是首先从训练集用初始权重训练出一个弱学习器1,根据弱学习的学习误差率表现来更新训练样本的权重,使得之前弱学习器1学习误差率高的训练样本点的权重变高,使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.,如此重复进行,直到弱学习器数达到事先指定的数目T,最终将这T个弱学习器通过集合策略进行整合,得到最终的强学习器。  

img

boosting家族算法一般需要解决:

​ 1)如何计算学习误差率e?

​ 2)如何得到弱学习器权重系数\(α\)?

 3)如何更新样本权重D?

​ 4)使用何种结合策略?

Adaboost

基本思路

训练样本:

\(T=\{(x_,y_1),(x_2,y_2), ...(x_m,y_m)\}\)

训练集的在第k个弱学习器的输出权重为(第一个权重1/m,后面逐渐调整)

\(D(k) = (w_{k1}, w_{k2}, ...w_{km}) ;\;\; w_{1i}=\frac{1}{m};\;\; i =1,2...m\)

  1. 分类问题

    多元分类是二元分类的推广,这里首先考虑二分类,输出为{-1,1}

    1)第k个弱分类器\(G_k(x)\)在训练集上的加权误差率为

    \(e_k = P(G_k(x_i) \neq y_i) = \sum\limits_{i=1}^{m}w_{ki}I(G_k(x_i) \neq y_i)\)

    2)第k个弱分类器\(G_k(x)\)权重系数为:

    \(\alpha_k = \frac{1}{2}log\frac{1-e_k}{e_k}\)

    从上式可以看出,如果分类误差率\(ek\)越大,则对应的弱分类器权重系数\(αk\)越小。也就是说,误差率小的弱分类器权重系数越大。

    3)样本权重D:假设第k个弱分类器的样本集权重系数为\(D(k) = (w_{k1}, w_{k2}, ...w_{km})\),则对应的第k+1个弱分类器的样本集权重系数为:

    \(w_{k+1,i} = \frac{w_{ki}}{Z_K}exp(-\alpha_ky_iG_k(x_i))\)

    其中规范化因子\(Z_k = \sum\limits_{i=1}^{m}w_{ki}exp(-\alpha_ky_iG_k(x_i))\)

    计算公式可以看出,如果第i个样本分类错误,则\(y_iG_k(x_i) < 0\),导致样本的权重在第k+1个弱分类器中增大,如果分类正确,则权重在第k+1个弱分类器中减少.

    4)集成策略:加权表决法

    \(f(x) = sign(\sum\limits_{k=1}^{K}\alpha_kG_k(x))\)

    对于Adaboost多元分类算法,其实原理和二元分类类似,最主要区别在弱分类器的系数上。比如Adaboost SAMME算法,它的弱分类器的系数:

    \(\alpha_k = \frac{1}{2}log\frac{1-e_k}{e_k} + log(R-1)\)

    其中R为类别数

  2. 回归问题(Adaboost R2)

    数据权重: \(D(1) = (w_{11}, w_{12}, ...w_{1m}) ;\;\; w_{1i}=\frac{1}{m};\;\; i =1,2...m\)

    1) 对于弱学习器:计算最大误差\(E_k= max|y_i - G_k(x_i)|\;i=1,2...m\)

    2)计算每个样本的相对误差:

    线性:\(e_{ki}= \frac{|y_i - G_k(x_i)|}{E_k}\)

    平方:\(e_{ki}= \frac{(y_i - G_k(x_i))^2}{E_k^2}\)

    指数:\(e_{ki}= 1 - exp(\frac{-|y_i -G_k(x_i)|}{E_k})\)

    3)回归误差率为:\(e_k = \sum\limits_{i=1}^{m}w_{ki}e_{ki}\)

    4)弱学习器的系数:\(\alpha_k =\frac{e_k}{1-e_k}\)

    5)新的数据权重:\(w_{k+1,i} = \frac{w_{ki}}{Z_k}\alpha_k^{1-e_{ki}}\),\(Z_k = \sum\limits_{i=1}^{m}w_{ki}\alpha_k^{1-e_{ki}}\)

    6)最终的集成学习器:\(f(x) =G_{k^*}(x)\), \(G_{k^*}(x)=G_k(x)ln\frac{1}{\alpha_k} , k=1,2,....K\)

损失函数以及各权重推导

从分类器角度,adaboost是多个分类器叠加:

第k-1轮的强学习器为:\(f_{k-1}(x) = \sum\limits_{i=1}^{k-1}\alpha_iG_{i}(x)\)

第k轮:\(f_{k}(x) = \sum\limits_{i=1}^{k}\alpha_iG_{i}(x)\)

因此可以得到迭代关系:\(f_{k}(x) = f_{k-1}(x) + \alpha_kG_k(x)\)

adaboost的损失函数为指数函数:

\(\underbrace{arg\;min\;}_{\alpha, G} \sum\limits_{i=1}^{m}exp(-y_if_{k}(x))\)

将迭代关系代入:\(L(\alpha_k, G_k(x)) = \underbrace{arg\;min\;}_{\alpha, G}\sum\limits_{i=1}^{m}exp[(-y_i) (f_{k-1}(x) + \alpha G(x))]\)

\(w_{ki}^{’} = exp(-y_if_{k-1}(x))\), 可知该值与\(\alpha 、G\)无关,仅与\(f_{k-1}\)有关:\(L(\alpha_k, G_k(x)) = \underbrace{arg\;min\;}_{\alpha, G}\sum\limits_{i=1}^{m}w_{ki}^{’}exp[-y_i\alpha G(x)]\)

  1. \(G_k(x)\)

    \(\begin{align} \sum\limits_{i=1}^mw_{ki}^{'}exp(-y_i\alpha G(x_i)) &= \sum\limits_{y_i =G_k(x_i)}w_{ki}^{'}e^{-\alpha} + \sum\limits_{y_i \ne G_k(x_i)}w_{ki}^{'}e^{\alpha} \\& = (e^{\alpha} - e^{-\alpha})\sum\limits_{i=1}^mw_{ki}^{'}I(y_i \ne G_k(x_i)) + e^{-\alpha}\sum\limits_{i=1}^mw_{ki}^{'} \end{align}\)

    得:\(G_k(x) = \underbrace{arg\;min\;}_{G}\sum\limits_{i=1}^{m}w_{ki}^{’}I(y_i \neq G(x_i))\)

  2. \(\alpha\):G代入损失函数\(L\),并对$\(求导,令其为零:\)_k = log$

    \(e_k = \frac{\sum\limits_{i=1}^{m}w_{ki}^{’}I(y_i \neq G(x_i))}{\sum\limits_{i=1}^{m}w_{ki}^{’}} = \sum\limits_{i=1}^{m}w_{ki}I(y_i \neq G(x_i))\)

  3. 利用迭代关系以及\(w_{ki}^{’} = exp(-y_if_{k-1}(x))\)得到w迭代公式:

    \(w_{k+1,i}^{’} = w_{ki}^{’}exp[-y_i\alpha_kG_k(x)]\)

正则化项

对学习器迭代添加正则项:\(f_{k}(x) = f_{k-1}(x) + \nu\alpha_kG_k(x)\)\(\nu\)的取值范围为\(\nu \in [0,1]\)。对于同样的训练集学习效果,较小的$$意味着我们需要更多的弱学习器的迭代次数。

总结

最广泛的Adaboost弱学习器是决策树和神经网络。对于决策树,Adaboost分类用了CART分类树,而Adaboost回归用了CART回归树。

    Adaboost的主要优点有:

    1)Adaboost作为分类器时,分类精度很高

    2)在Adaboost的框架下,可以使用各种回归分类模型来构建弱学习器,非常灵活。

    3)作为简单的二元分类器时,构造简单,结果可理解。

    4)不容易发生过拟合

    Adaboost的主要缺点有:

    1)对异常样本敏感,异常样本在迭代中可能会获得较高的权重,影响最终的强学习器的预测准确性。

GBDT

https://zhuanlan.zhihu.com/p/89572181

GBDT(Gradient Boosting Decision Tree) 又叫 MART(Multiple Additive Regression Tree),是一种迭代的决策树算法,GBDT中的树是回归树(不是分类树),GBDT用来做回归预测,调整后也可以用于分类。

回顾:

  1. 回归树(用最小均方误差来进行划分):img

  2. 提升树:迭代多颗树共同决策,每一棵树是之前的所有树的结论和残差。

    需要解决: 1)如何计算学习误差率e?(残差)

    ​ 2)如何得到弱学习器权重系数\(α\)?(这一棵树的权重)

     3)如何更新样本权重D?(下一棵树的学习)

    ​ 4)使用何种结合策略?(决策)

GDBT关注了如何学习残差的问题,当损失函数时平方损失和指数损失函数时,每一步的优化很简单(如adaboost),但是对于更一般的损失函数,每一步的优化就不容易了。

针对这一问题,Freidman提出了梯度提升算法:利用最速下降的近似方法,即利用损失函数的负梯度在当前模型的值,作为回归问题中提升树算法的残差的近似值,拟合一个回归树:

img
  1. 初始化:f0仅仅是只有一个根节点的树,\(\gamma\)是划分值,让loss最小

  2. 循环部分:

    1. 对每一个样本计算负梯度(样本权重)

    2. 利用(x, r)拟合cart回归树,对应的叶子节点区域是\(R_{jm}\),j是叶子结点个数

    c.对叶子节点计算最佳的拟合值(学习残差)

    d.更新强学习器\(f_{m}(x)=f_{m-1}(x)+\sum_{j=1}^{J_{m}} \gamma_{j m} I\left(x \in R_{j m}\right)\)

  3. 汇总:\(f(x)=f_{0}(x)+\sum_{m=1}^{M}\sum_{j=1}^{J_{m}} \gamma_{j m} I\left(x \in R_{j m}\right)\)

调参时的问题:

树的深度很少就能达到很高的精度(6,对于普通决策树和随机森林需要15+)。泛化误差可以分解为两部分,偏差(bias)和方差(variance)。boosting关注偏差,bagging关注方差。因此对boosting而言,弱学习器的拟合能力不能太强(方差小),不然会导致过拟合。而bagging采样不同的数据来进行弱分类器的训练,因此不容易过拟合。

XGBoost——GDBT的更快实现1(待补充)

https://www.cnblogs.com/mantch/p/11164221.html

https://zhuanlan.zhihu.com/p/86816771

LightGBM——GDBT的更快实现2(待补充)

https://zhuanlan.zhihu.com/p/99069186

week 9 内容:

  • louis philippe morency 《多模态机器学习》 80%

  • 论文阅读:

    1. A Survey of Clustering With Deep Learning: From the Perspective of Network Architecture
    2. EM、GMM
    3. SpectralCoclustering

A Survey of Clustering With Deep Learning: From the Perspective of Network Architecture

近些年来很多研究几种在使用深度神经网络学习更好的表示来提高聚类性能。这篇综述从网络框架的角度进行了研究,他们首先介绍了领域相关知识,然后提出了深度学习进行聚类的相关分类方法(taxonomy),最后提出未来发展的方向并做了总结。

Intorduction

数据聚类是机器学习、模式识别、计算机视觉、数据压缩等领域的一个基本问题。聚类的目标是根据一些相似度量(如欧几里德距离)将相似数据分类成一个聚类传统的聚类方法对高维数据的聚类性能通常很差,这是由于这些方法使用的相似度进行度量的效率较低。此外,这些方法在大规模数据集上通常具有较高的计算复杂度。因此,人们广泛研究降维和特征转换方法,将原始数据映射到一个新的特征空间中,生成的数据更容易被现有的分类器分离。一般来说,现有的数据变换方法包括线性变换如主成分分析(PCA)和等非线性变换如核方法、谱方法等。然而,潜在结构高度复杂的数据仍挑战着现有的聚类方法。深度神经网络(DNNs)由于其固有的高度非线性变换特性,可以将数据转换为更有利于聚类的表示形式。

##### 传统聚类方法分类

  1. 基于划分的方法(partition-based)

  2. 基于密度的方法(density-based)

  3. 层次的方法(hierarchical)

  4. 其他

由于深度学习聚类的本质是学习面向聚类的表示,本文基于网络结构进行了分类

深度学习的聚类方法
  1. 基于autoencoder:训练解码器和编码器,解码器是训练时候重建回原始数据,编码器是训练的mapping function(降维、非线性表示)
  2. ClusterDNN: 通过特定聚类loss进行约束训练的前馈神经网络
  3. 基于GAN和VAE:它们不仅可以执行聚类任务,还可以从获得的聚类中生成新的样本

PRELIMINARIES

结构:

  1. MLP:对聚类任务,好的初始化是必要的,避免训练陷入局部最优
  2. CNN:不需要特定初始化,但良好的初始化能显著提高性能。

clustering loss:

  1. 主聚类损失 Principal Clustering Loss:这类聚类损失函数包括样本的聚类中心(cluster centroids)和聚类分配(cluster assignment)。在聚类损耗引导下对网络进行训练后,可以直接得到聚类。
  2. 辅助性损失 Auxiliary Clustering Loss:第二类只起到引导网络学习更可行的聚类表示的作用,不能直接输出聚类。这意味着只有辅助聚类损失的深层聚类方法需要在训练完网络后运行一种聚类方法才能得到聚类。

metrics:

  1. 聚类准确率:

\[A C C=\operatorname*{max}_{m}{\frac{\int_{i=1}^{n}\sum\{y_{i}=m(c_{i})\}}{n}}\]

c是聚类分配,y是ground truth, m是mapping function

  1. Normalized Mutual Information(NMI)

I是互信息,H是信息熵

深度聚类方法

深度聚类方法的损失函数(优化目标)通常由网络损失Ln和聚类损失Lc两部分组成:

\[{\cal L}=\lambda L_{n}+(1-\lambda)L_{c}\]

Ln:网络损失可以是自动编码器(AE)的重构损失、变分自编码器(VAE)的变分损失或生成式对抗网络(GAN)的对抗损失。

Lc:群体之间特征区分更明显

  1. AE based

    reconstruction loss:

    \(\operatorname*{min}_{\phi,\theta}{\cal L}_{r e c}=\operatorname*{min}_{\bigl|n\bigr|}\sum_{i=1}^{n}\left|\left|\,x_{i}-g_{\theta}(f_{\phi}(x_{i})\right\gt \right|^{2}\)

    total loss:

    \(L=\lambda L_{r e c}+(1-\lambda)L_{t}\)

    提升性能:

    1. 结构:对于含有空间不变性的数据可加入pooling
    2. 鲁棒性:为了避免过拟合和提高鲁棒性,在输入中加入噪声
    3. 引入特征限制,如正则化
    4. 把各层的重构损失都加入到loss中

    例子:

    1. DCN:它结合了自动编码器和k-means算法。首先进行预训练AE,然后联合优化重建损失和k-means损失。
  2. CDNN-Based

    没有了reconstruction loss,基于cdn的算法存在获取损坏特征空间的风险,当所有的数据点被简单地映射到紧凑的聚类上时,导致聚类损失值很小,但没有意义。因此,需要仔细设计聚类loss,对于一定的聚类loss,网络初始化很重要。因此,基于cdn的深度聚类算法按照网络初始化的方式分为三类,即无监督预训练、有监督预训练和随机初始化。

    1. unsupervised

      这些算法首先以无监督的方式训练RBM或自动编码器,然后通过聚类loss对网络(仅对自动编码器的编码器部分)进行微调。

    2. supervised

      复杂的图像数据中提取可行的特征(domain pretrain)

    3. non pretrain

      在精心设计的聚类损失的指导下,网络也可以训练提取判别特征

  3. VAE-BASED

    与传统的聚类方法相比,基于ae和cdn的深度聚类方法有了显著的改进。然而,它们是专门为聚类而设计的,不能揭示数据的真正底层结构,这就妨碍了它们扩展到聚类之外的其他任务,例如生成样本。VAE可以被认为是AE的生成变体,因为它强制AE的潜在代码遵循预定义的分布。VAE将变分贝叶斯方法与神经网络的灵活性和可扩展性相结合。

  4. GAN-BASED

FUTURE OPPORTUNITIES

  1. future opportunities
  1. 目前还没有理论分析解释深度学习聚类工作原理以及如何进一步提高聚类性能
  2. 其他网络架构与聚类相结合
  3. 引入tricks降低训练难度,提高鲁棒性
  4. 引入其他任务如多任务学习、迁移学习

EM 算法

EM算法是一种迭代算法,1977年Dempster等人总结,用于含有隐变量的概率模型极大似然估计,或者最大后验估计。有两步,E步求期望,M步求极大。

Q函数:完全对数似然在给定观测数据Y以及当前\(\theta^{(i)}\)的情况下对Z的期望。

\(Q(\theta, \theta^{(i)}) = E_Z [\log P(Y,Z|\theta)|Y,\theta^{(i)}]\)

\(\sum_{z(i)}Q^{i}(z^{(i)}) = 1\)

\(Q^{i}(z^{(i)})\geq0\)

步骤

分为E步和M步,即求Q函数,极大化Q函数。

输入:观测数据Y,隐变量数据Z,联合分布,条件分布

输出:模型参数

  1. 选取参数的初始值在\(\theta^{(0)}\)(可任意选择,但是算法对初始值敏感);开始迭代;

  2. E步:计算

  3. M步:最大化\(Q(\theta, \theta^{(i)})\),得到\(\theta^{(i+1)}\)

    ^{(i+1)}=Q(, ^{(i)})
  4. 重复2. 3.,直到收敛

    停止迭代的条件:

导出

给定观测数据Y,目标是极大化观测数据(不完全数据)Y关于参数的对数似然函数,即

L()=P(Y|)=_{Z}P(Y,Z|)={ _Z P(Y|Z,) P(Z|)}

其中表示在模型参数为时,观测数据Y的概率分布。

\(\begin{align*} P(Y|\theta)&=\sum_Z P(Y,Z|\theta)=\sum_Z P(Z|\theta)P(Y|Z,\theta)\\ \end{align*}\)

EM算法通过逐步迭代来逐步近似极大化。假设第i次迭代后的估计值为。下一轮的估计值要使。故

L()-L(^{(i)} )={ _Z P(Y|Z,)P(Z|) }-P(Y|^{(i)} )

利用Jensen不等式(这里用的是\(log{\bigl(}\sum_{i=1}^{M}\lambda_{i}x_{i}{\bigr)}\leq\sum_{i=1}^{M}\lambda_{i}log{\bigl(}x_{i}{\bigr)}\))得到下界:

\[\begin{align*} L(\theta)-L(\theta^{(i)} ) &=\log \left\{ \sum_Z P(Y|Z,\theta^{(i)} ) \frac{P(Y|Z,\theta) P(Z|\theta)}{P(Y|Z,\theta^{(i)} )} \right \} - \log P(Y|\theta^{(i)} ) \\ &\geq \sum_Z P(Z|Y,\theta^{(i)} )\log \frac{P(Y|Z,\theta) P(Z|\theta)}{P(Z|Y,\theta^{(i)})} - \log P(Y|\theta^{(i)})\\ &= \sum_Z P(Z|Y,\theta^{(i)} )\log \frac{P(Y|Z,\theta) P(Z|\theta)}{P(Z|Y,\theta^{(i)})} - \sum_ZP(Z|Y,\theta^{(i)} ) \log P(Y|\theta^{(i)}) \\ &= \sum_Z P(Z|Y,\theta^{(i)} )\log \frac{P(Y|Z,\theta) P(Z|\theta)}{P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})} \\ \end{align*}\]

B(, {(i)})=L({(i)})+_Z P(Z|Y,^{(i)} )

的一个下界。任何可使增大的,都可以使增加。选择能使当前极大的作为新的值。

\[\begin{align*} \theta^{(i+1)} &=\arg \max (L(\theta^{(i)})+\sum_Z P(Z|Y,\theta^{(i)} )\log \frac{P(Y|Z,\theta) P(Z|\theta)}{P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})}) \\ &=\arg \max (\sum_Z P(Z|Y,\theta^{(i)}))\log (P(Y|Z,\theta)P(Z|\theta))\\ &=\arg \max (\sum_Z P(Z|Y,\theta^{(i)})\log(P(Y,Z|\theta))) \\ &=\arg \max Q(\theta, \theta^{(i)}) \end{align*}\]

所以EM算法就是通过迭代不断求Q函数,并将之极大化,直至收敛。下图为EM算法的直观解释,的一个下界。

img

我们首先初始化模型的参数,我们基于这个参数对每一个隐变量进行分类,此时相当于我们观测到了隐变量。有了隐变量的观测值之后,原来含有隐变量的模型变成了不含隐变量的模型(以上是E步),因此我们可以直接使用极大似然估计来更新模型的参数(M步),再基于新的参数开始新一轮的迭代,直到参数收敛。

收敛性

定理一:为观测数据的似然函数,是EM算法得到的参数估计序列,是对应的似然函数序列,则是单调递增的。

定理二:是观测数据的对数似然函数,是EM算法得到的参数估计序列,是对应的对数似然函数序列。如果有上界,则收敛到某一值;在函数满足一定条件下,EM算法得到的参数估计序列的收敛值的稳定点。

GMM混合高斯

模型定义:

\(p(x)=\sum_{k=1}^{K}\alpha_{k}\mathcal{N}(x|\mu_{k},\Sigma_{k})\)

\(\sum_{k=1}^{K}\alpha_{k}=1\)

  1. 多个高斯模型的加权平均;(单个表达能力不够)
  2. 混合:隐变量->属于哪一个高斯分布
参数学习

\(\gamma_{j k}\)代表第j个观测来源于k个分模型(01随机变量)---------这里的隐变量

  1. 写出完全对数似然

    \(\begin{aligned} P(y, \gamma \mid \theta) &=\prod_{j=1}^{N} P\left(y_{j}, \gamma_{j 1}, \gamma_{j 2}, \cdots, \gamma_{j K} \mid \theta\right) \\ &=\prod_{k=1}^{K} \prod_{j=1}^{N}\left[\alpha_{k} \phi\left(y_{j} \mid \theta_{k}\right)\right]^{\gamma_{k}} \\ &=\prod_{k=1}^{K} \alpha_{k}^{n_{k}} \prod_{j=1}^{N}\left[\phi\left(y_{j} \mid \theta_{k}\right)\right]^{\gamma_{k}} \\ &=\prod_{k=1}^{K} \alpha_{k}^{n_{k}} \prod_{j=1}^{N}\left[\frac{1}{\sqrt{2 \pi} \sigma_{k}} \exp \left(-\frac{\left(y_{j}-\mu_{k}\right)^{2}}{2 \sigma_{k}^{2}}\right)\right]^{\gamma_{k t}} \end{aligned}\)

    对数似然:

    \(\log P(y,\gamma\vert\theta)=\sum_{k=1}^{K}[n_{k}\log\alpha_{k}+\sum_{j=1}^{N}\gamma_{k}\biggl[\log(\frac{1}{\sqrt{2\pi}})-\log\sigma_{k}-\frac{1}{2\sigma_{k}^{2}}(y_{j}-\mu_{k})^{2}\biggr]]\)

    其中:\(n_k = \sum_{j=1}^{N}\gamma_{jk}\), \(\sum_{k=1}^{K}n_{k}=N\) (Q函数推导的时候代入)

  2. 确定Q函数

    \(\begin{aligned} Q\left(\theta, \theta^{(i)}\right) &=E\left[\log P(y, \gamma \mid \theta) \mid y, \theta^{(i)}\right] \\ &=E\left\{\sum_{k=1}^{K} [n_{k} \log \alpha_{k}+\sum_{j=1}^{N} \gamma_{j k}\left[\log \left(\frac{1}{\sqrt{2 \pi}}\right)-\log \sigma_{k}-\frac{1}{2 \sigma_{k}^{2}}\left(y_{j}-\mu_{k}\right)^{2}\right]]\right\} \\ &=\sum_{k=1}^{K}\left\{\sum_{j=1}^{N}[\left(E \gamma_{j k}\right) \log \alpha_{k}+\sum_{j=1}^{N}\left(E \gamma_{j k}\right)\left[\log \left(\frac{1}{\sqrt{2 \pi}}\right)-\log \sigma_{k}-\frac{1}{2 \sigma_{k}^{2}}\left(y_{j}-\mu_{k}\right)^{2}\right]]\right\} \end{aligned}\)

    需要计算期望\(E (\gamma_{j k}|y, \theta)\)

    \(\hat{\gamma}_{j k} &=E\left(\gamma_{j k} \mid y, \theta\right)=P\left(\gamma_{j k}=1 \mid y, \theta\right) \\ &=\frac{P\left(\gamma_{j k}=1, y_{j} \mid \theta\right)}{\sum_{k=1}^{K} P\left(\gamma_{j k}=1, y_{j} \mid \theta\right)}&=\frac{P\left(y_{j} \mid \gamma_{j k}=1, \theta\right) P\left(\gamma_{j k}=1 \mid \theta\right)}{\sum_{k=1}^{K} P\left(y_{j} \mid \gamma_{j k}=1, \theta\right) P\left(\gamma_{j k}=1 \mid \theta\right)} &=\frac{\alpha_{k} \phi\left(y_{j} \mid \theta_{k}\right)}{\sum_{k=1}^{K} \alpha_{k} \phi\left(y_{j} \mid \theta_{k}\right)}, \quad j=1,2, \cdots, N ; \quad k=1,2, \cdots, K\)

    Q函数为:

    \(Q\left(\theta, \theta^{(i)}\right)=\sum_{k=1}^{K} [n_{k} \log \alpha_{k}+\sum_{k=1}^{N} \hat{\gamma}_{j k}\left[\log \left(\frac{1}{\sqrt{2 \pi}}\right)-\log \sigma_{k}-\frac{1}{2 \sigma_{k}^{2}}\left(y_{j}-\mu_{k}\right)^{2}\right]]\)

  3. 确定M步

    这一步求Q函数对\(\theta\)的极大值,分别对\(\mu \space \sigma \space \alpha\)求偏导等于零(\(\alpha\)需要在满足和为1,所以除个N)解得

    \({\hat{\mu}}_{k}={\frac{\sum_{j=1}^{N}{\hat{\gamma}}_{k}y_{j}}{\sum_{j=1}^{N}{\hat{\gamma}}_{k}}}\)

    \(\hat{\sigma}_{k}^{2}=\frac{\sum_{j=1}^{N} \hat{\gamma}_{j k}\left(y_{j}-\mu_{k}\right)^{2}}{\sum_{j=1}^{N} \hat{\gamma}_{j k}}\)

    \(\hat{\alpha}_{k}=\frac{n_{k}}{N}=\frac{\sum_{j=1}^{N} \hat{\gamma}_{j k}}{N}\)

week 8 内容:

  • louis philippe morency 《多模态机器学习》 70%
  • 论文阅读:
    1. Variational Autoencoders for Collaborative Filtering
    2. A Survey on Curriculum Learning(TPAMI 2021)
    3. sampling
    4. VI、EM算法、GMM

Variational Autoencoders for Collaborative Filtering(WWW 2018)

主要工作

该文作者把变分自编码器拓展应用于基于隐式反馈的协同过滤推荐任务,希望通过非线性概率模型克服线性因子模型的局限。该文提出了基于变分自编码器(Variational Autoencoder)的生成模型VAE_CF,并针对变分自编码器的正则参数和概率模型选取做了适当调整(使用了多项式分布),使其在当时推荐任务中取得SOTA结果。

模型

如上图所示,虚线代表了采样操作,a是传统AE,b是denoising AE(论文中使用了多项式分布的Mult-dae), c代表vae(论文中是mult-vae)。

\(\mathbf{z}_u \sim \mathcal{N}(0, \mathbf{I}_K), \pi(\mathbf{z}_u) \propto \exp\{f_\theta (\mathbf{z}_u\},\mathbf{x}_u \sim \mathrm{Mult}(N_u, \pi(\mathbf{z}_u))\)

该模型根据标准高斯分布抽取K维隐变量 [公式] ,然后根据非线性函数 [公式] 生成用户 [公式] 点击所有物品的概率分布 [公式] ,最后根据多项式分布 [公式] 重构用户点击历史(隐式反馈的用户-物品评价矩阵对应行)。

Multi-DAE目标函数(对数似然):

\(\mathcal{L}_u(\theta, \phi) = \log p_\theta(\mathbf{x}_u | g_\phi(\mathbf{x}_u))\)

Multi-VAE目标函数(ELBO):

\(\mathcal{L}_u(\theta, \phi) = \mathbb{E}_{q_\phi(z_u | x_u)}[\log p_\theta(x_u | z_u)] - \beta \cdot KL(q_\phi(z_u | x_u) \| p(z_u))\)

VAE_CF模型较标准的变分自编码器做了如下调整:

1、将正则参数调至0.2(低于常规值1,具体来说使用了annealing来逐步增大beta),称其为部分正则化(partially regularized),实际上是$-vae $在推荐上的应用。

2、使用了多项式分布进行重建而非高斯分布。

  • 多项式似然非常适合于隐式反馈数据的建模,并且更接近 rank loss;
  • 无论数据的稀缺性如何,采用principled Bayesian方法都更加稳健。

使用SGD进行优化:

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
class MultiVAE(nn.Module):
"""
Container module for Multi-VAE.

Multi-VAE : Variational Autoencoder with Multinomial Likelihood
See Variational Autoencoders for Collaborative Filtering
https://arxiv.org/abs/1802.05814
"""

def __init__(self, p_dims, q_dims=None, dropout=0.5):
# p_dims = [200, 600, n_items]
super(MultiVAE, self).__init__()
# q -> encoder | p-> decoder
self.p_dims = p_dims
# 确定维度
if q_dims:
assert q_dims[0] == p_dims[-1], "In and Out dimensions must equal to each other"
assert q_dims[-1] == p_dims[0], "Latent dimension for p- and q- network mismatches."
self.q_dims = q_dims
else:
self.q_dims = p_dims[::-1] # [n_items, 600, 200]

# Last dimension of q- network is for mean and variance
temp_q_dims = self.q_dims[:-1] + [self.q_dims[-1] * 2] # [ n_items, 600, 400] ]
# encoder
# in:[ n_items, 600]
# out:[600, 400]
self.q_layers = nn.ModuleList([nn.Linear(d_in, d_out) for
d_in, d_out in zip(temp_q_dims[:-1], temp_q_dims[1:])])
# decoder
# in:[200, 600,]
# out:[600, n_items]
self.p_layers = nn.ModuleList([nn.Linear(d_in, d_out) for
d_in, d_out in zip(self.p_dims[:-1], self.p_dims[1:])])

self.drop = nn.Dropout(dropout)
self.init_weights()

def forward(self, input):
mu, logvar = self.encode(input)
z = self.reparameterize(mu, logvar)
return self.decode(z), mu, logvar

def encode(self, input):
h = F.normalize(input)
h = self.drop(h)

for i, layer in enumerate(self.q_layers):
h = layer(h)
if i != len(self.q_layers) - 1:
h = F.tanh(h)
else:
# 最后一层分均值和方差
mu = h[:, :self.q_dims[-1]]
logvar = h[:, self.q_dims[-1]:]
return mu, logvar

def reparameterize(self, mu, logvar):
# 重参数化技巧
if self.training:
std = torch.exp(0.5 * logvar)
eps = torch.randn_like(std)
return eps.mul(std).add_(mu)
else:
return mu

def decode(self, z):
# 解码
h = z
for i, layer in enumerate(self.p_layers):
h = layer(h)
if i != len(self.p_layers) - 1:
h = F.tanh(h)
return h

def init_weights(self):
for layer in self.q_layers:
# Xavier Initialization for weights
size = layer.weight.size()
fan_out = size[0]
fan_in = size[1]
std = np.sqrt(2.0/(fan_in + fan_out))
layer.weight.data.normal_(0.0, std)

# Normal Initialization for Biases
layer.bias.data.normal_(0.0, 0.001)

for layer in self.p_layers:
# Xavier Initialization for weights
size = layer.weight.size()
fan_out = size[0]
fan_in = size[1]
std = np.sqrt(2.0/(fan_in + fan_out))
layer.weight.data.normal_(0.0, std)

# Normal Initialization for Biases
layer.bias.data.normal_(0.0, 0.001)

def loss_function(recon_x, x, mu, logvar, anneal=1.0):
# BCE = F.binary_cross_entropy(recon_x, x)
BCE = -torch.mean(torch.sum(F.log_softmax(recon_x, 1) * x, -1))
KLD = -0.5 * torch.mean(torch.sum(1 + logvar - mu.pow(2) - logvar.exp(), dim=1))

return BCE + anneal * KLD

A Survey on Curriculum Learning (TPAMI 2021)

主要工作

课程学习 (Curriculum learning, CL) 是近几年逐渐热门的一个前沿方向。Bengio 首先提出了课程学习(Curriculum learning,CL)的概念,它是一种训练策略,模仿人类的学习过程,主张让模型先从容易的样本开始学习,并逐渐进阶到复杂的样本和知识(从易到难)。CL策略在计算机视觉和自然语言处理等多种场景下,在提高各种模型的泛化能力和收敛率方面表现出了强大的能力。这篇综述一共调研了147篇文献,从问题定义有效性分析方法总结未来研究方向等几大方面进行了详细的概括和总结。

问题定义:

  1. 原始的课程学习

课程式学习是在 [公式] 个训练步骤上的训练标准序列 [公式] , 每个准则 [公式] 是目标训练分布 [公式] 的权重。该准则包括数据/任务、模型容量、学习目标等。满足的准则:

熵增(harder)、权重增加、最后的目标训练分布达到[公式]

  1. 从数据层面泛化的课程学习(data level)

    在T步内对于training target分布赋权学习。

  2. 更加泛化的课程学习(criteria )

    存在“hard to easy”效果更好的examples,为了让课程学习定义更加泛化。提出课程学习是在每一个[公式]利用机器学习的所有元素进行训练的设计,比如data、目标函数等。

有效性分析:

1. 模型优化角度

CL可以看成是一种特殊的 continuation 方法continuation method是一种思想,就是不能一口吃个胖子,一步一步的解决问题。)。这种方法首先优化比较smooth的问题,然后逐渐优化到不够smooth的问题。如下图所示,continuation 方法提供了一个优化目标序列,从一个比较平滑的目标开始,很容易找到全局最小值,并在整个训练过程中跟踪局部最小值。另外,从更容易的目标中学习到的局部最小值具有更好的泛化能力,更有可能近似于全局最小值。

2. 数据分布角度(降噪denoising)

训练分布和测试分布之间存在着由噪声/错误标注的训练数据引起的偏差。直观地讲,训练分布和目标(测试)分布有一个共同的大密度高置信度标注区域,这对应于CL中比较容易的样本。如下图所示,波峰附近的数据代表高置信度的数据即干净的数据,两边(尾部)代表的是低置信度的数据即噪声数据。左图看出,训练数据 [公式] 比目标数据 [公式] 噪声更多(其分布尾巴更翘);右图看出,CL通过加权,一开始分配给噪声数据较小的权重,后面慢慢才给这些数据增加权重。通过这种方式,CL就可以减少来自负样本的影响。

另外,CL本质上是将目标分布下的预期风险上界最小化,这个上界表明,我们可以通过CL的核心思想来处理将 [公式] 上的预期风险最小化的任务:根据课程设置逐步抽取相对容易的样本,并将这些样本的经验风险最小化。

左图为数据分布图;右图为加权后的数据分布图

应用场景

从动机上看,主要分为的是指导训练和降噪。

  1. 指导训练:让训练可行/更好。应用:sparse reward RL, multi-task learning, GAN training, NAS(提高效率);domain adaption, imbalanced classification(让训练可行)

  2. denoise:加速训练、让训练更泛化和鲁棒(针对噪声多的或是异质数据)。应用:weakly-supervised or unsupervised learning, NLP tasks (neural machine translation, natural language understanding, etc.)

方法总结:

课程学习的核心问题是得到一个ranking function,该函数能够对每条数据/每个任务给出其learning priority (学习优先程度)。这个则由难度测量器(Difficulty Measurer)实现。另外,我们什么时候把 Hard data 输入训练 以及 每次放多少呢? 这个则由训练调度器 (Training Scheduler)决定。因此,目前大多数CL都是基于"难度测量器+训练调度器 "的框架设计。根据这两个是否自动设计可以将CL分成两个大类即 Predefined CLAutomatic CL

Predifined CL 的难度测量器和训练调度器都是利用人类先验先验知识由人类专家去设计;而Automatic CL是以数据驱动的方式设计。

1. Predefined CL

1.1 预定义的难度测量器

complexity:structural complexity (如句子的长度等)

diversity :分布的多样性(例如用信息熵来衡量)

noise:噪声角度(如直接从网上爬下的照片噪声就会多)

domain:domain knowledge

IR例子:

  1. [18]Continuation Methods and Curriculum Learning for Learning to Rank(CIKM 2018)

    提出了CM和CL两种策略来提升λ-MART的性能。

    CM:先针对MSE训练回归森林,然后进行λ-MART训练

    CL:需要从训练数据采样。第一种策略根据相关性来划分数据、第二种根据难度进行划分。

  2. [82]Curriculum Learning Strategies for IR An Empirical Study on Conversation Response Ranking (ecir 2020)

1.2 预定义的训练调度器

训练调度器可以分为离散调度器连续调度器。两者的区别在于:离散型调度器是在每一个固定的次数(>1)后调整训练数据子集,或者在当前数据子集上收敛,而连续型调度器则是在每一个epoch调整训练数据子集。

例子:

离散调度器:

Baby step:排序后分buckets,训练过程逐步引入。

One-Pass :直接使用下一个bucket,不是引入了。

连续调度器:

设计function\(\lambda(t)\)得到引入的porpotion。

linear(像linear lr scheduler):

root function:

为了让新加入的samples能够被充分学习,需要让加入的速率降低。

1.3 predifined CL存在的问题

  1. 很难预定义CL的方法找到测量器和调度器两者最优的组合。

  2. 不够灵活,没有考虑模型自身的反馈在训练过程中。

  3. 需要专家知识,代价较高。

  4. 人类认为容易的样本对模型来说就不一定容易。(人和机器模型的决策边界不一定一致)

2. Automatic CL

与predifined CL对比:

自动CL的方法论分为四类,即Self-paced LearningTransfer TeacherRL Teacher其他自动CL

Automatic CL的分类

2.1 Self-paced Learning

Self-paced Learning 让学生自己充当老师,根据其对实例的损失来衡量训练实例的难度。这种策略类似于学生自学:根据自己的现状决定自己的学习进度。主要利用基于loss的difficulty measurer,有很强的泛化能力。

原始loss,总共N个样本:

\(\operatorname*{min}_{w}\mathbb{E}(w;\lambda)\sum_{i=1}^{\mathcal{N}}l_{i}+R(w)\)

SPL引入了spl-regularization,v是一系列的weights:

\(\operatorname*{min}_{w;v\in[0,1]^{N}}\mathbb{S}\bigl(w,v;\lambda\bigr)\sum_{i=1}v_{i}l_{i}+g\bigl(v;\lambda\bigr).\)

SPL原始的l1正则项:

\(g(v;\lambda)=-\lambda\sum_{i=1}^{N}v_{i}.\)

固定w,我们可以得到最优的v(Eq.9):

\(v_{i}^{\star}=\arg\operatorname*{min}_{v_{i}\in[0,1]}v_{i}l_{i}^{\bigtriangledown}+g(v_{i};\lambda),\quad i=1,2,\cdot\cdot\cdot\cdot,n\)

同样固定v,可以优化w(Eq.10):

\(w^{*}=\arg\operatorname*{min}_{w}\sum_{i=1}^{N}v_{i}^{*}l_{i}.\)

常见的regularizer:

2.2 Transfer Teacher

SPL在学习初期,学生网络可能是不够成熟的,所以会影响到后面的训练

Transfer Teacher 则通过1个强势的教师模型来充当教师,根据教师对实例的表现来衡量训练实例的难度。教师模型经过预训练,并将其知识转移到测量学生模型训练的例子难度上。

2.3 RL Teacher

RL Teacher 采用强化学习(RL)模式,教师根据学生的反馈,实现数据动态选择。这种策略是人类教育中最理想的场景,教师和学生通过良性互动共同提高:学生根据教师选择的量身定做的学习材料取得最大的进步,而教师也有效地调整自己的教学策略,更好地进行教学。

2.4 其他自动 CL

除上述方法外,其他自动CL方法包括各种自动CL策略。如采取不同的优化技术来自动寻找模型训练的最佳课程,包括贝叶斯优化、元学习、hypernetworks等。

未来研究方向:

  1. 评价数据集和指标

虽然各种CL方法已经被提出并被证明是有效的,但很少有工作用通用基准来评估它们。在现有的文献中,数据集和指标在不同的应用中是多样化的。

2. 更完善的理论分析

现有的理论分析为理解CL提供了不同的角度。尽管如此,我们还需要更多的理论来帮助我们揭示为什么典型的CL是有效的。

3. 更多的CL算法以及应用

自动CL为CL在更广泛的研究领域提供了潜在的应用价值,已经成为一个前沿方向。因此,一个很有前途的方向是设计更多的自动CL方法,这些方法可具有不同的优化方式(如:bandit 算法、元学习、超参数优化等)和不同的目标(如:数据选择/加权、寻找最佳损失函数或假设空间等)。除了方法之外,还应该探索CL在更多领域中的应用。

总结:

这篇主要做了以下三项工作:

  1. 总结了现有的基于 "难度测量器+训练调度器 "总体框架的CL设计,并进一步将自动CL的方法论分为四类,即Self-paced LearningTransfer TeacherRL Teacher其他自动CL
  2. 分析了选择不同CL设计的原则,以利于实际应用。
  3. 对连接CL和其他机器学习概念(包括转移学习、元学习、持续学习和主动学习等)的关系的见解,然后指出CL的挑战以及未来潜在的研究方向,值得进一步研究。

Sampling

mote carlo integration:求定积分

Inverse Transform Sampling :

利用cdf:\(F(x) = P(X \le x)\)

算法:

Ancestral sampling(祖先采样)得到联合概率:

拒绝采样(rejection sampling):

利用比较容易采样的分布,罩住需要采样分布;

重要性采样(importance sampling):

不是采样方法,而是快速得到函数期望。依然从容易采样的Q入手,通过权重进行调整。

可以利用重要性采样的w进行重采样:

如果使用拒绝采样、重要性采样,尽量保证proposal distribution是heavy tail的,如果Q密度为0时,P还有密度,那么基本上采样效率会很低(找相近的分布采样效率会高)。

EM and GMM

https://blog.csdn.net/weixin_43661031/article/details/91358990

EM 算法

EM算法是一种迭代算法,1977年Dempster等人总结,用于含有因变量的概率模型极大似然估计,或者最大后验估计。有两步,E步求期望,M步求极大。

Q函数:完全对数似然在给定观测数据Y以及当前\(\theta^{(i)}\)的情况下对Z的期望。

\(Q(\theta, \theta^{(i)}) = E_Z [\log P(Y,Z|\theta)|Y,\theta^{(i)}]\)

$_{z(i)}Q{i}(z{(i)})=1 $

\(Q^{i}(z^{(i)})\geq0\)

步骤

分为E步和M步,即求Q函数,极大化Q函数。

输入:观测数据Y,隐变量数据Z,联合分布,条件分布

输出:模型参数

  1. 选取参数的初始值在\(\theta^{(0)}\)(可任意选择,但是算法对初始值敏感);开始迭代;

  2. E步:计算

  3. M步:最大化\(Q(\theta, \theta^{(i)})\),得到\(\theta^{(i+1)}\)

    ^{(i+1)}=Q(, ^{(i)})
  4. 重复2. 3.,直到收敛

    停止迭代的条件:

导出

给定观测数据Y,目标是极大化观测数据(不完全数据)Y关于参数的对数似然函数,即

L()=P(Y|)=_{Z}P(Y,Z|)={ _Z P(Y|Z,) P(Z|)}

其中表示在模型参数为时,观测数据Y的概率分布。

\(\begin{align*} P(Y|\theta)&=\sum_Z P(Y,Z|\theta)=\sum_Z P(Z|\theta)P(Y|Z,\theta)\\ \end{align*}\)

EM算法通过逐步迭代来逐步近似极大化。假设第i次迭代后的估计值为。下一轮的估计值要使。故

L()-L(^{(i)} )={ _Z P(Y|Z,)P(Z|) }-P(Y|^{(i)} )

利用Jensen不等式(这里用的是\(log{\bigl(}\sum_{i=1}^{M}\lambda_{i}x_{i}{\bigr)}\leq\sum_{i=1}^{M}\lambda_{i}log{\bigl(}x_{i}{\bigr)}\))得到下界:

\[\begin{align*} L(\theta)-L(\theta^{(i)} ) &=\log \left\{ \sum_Z P(Y|Z,\theta^{(i)} ) \frac{P(Y|Z,\theta) P(Z|\theta)}{P(Y|Z,\theta^{(i)} )} \right \} - \log P(Y|\theta^{(i)} ) \\ &\geq \sum_Z P(Z|Y,\theta^{(i)} )\log \frac{P(Y|Z,\theta) P(Z|\theta)}{P(Z|Y,\theta^{(i)})} - \log P(Y|\theta^{(i)})\\ &= \sum_Z P(Z|Y,\theta^{(i)} )\log \frac{P(Y|Z,\theta) P(Z|\theta)}{P(Z|Y,\theta^{(i)})} - \sum_ZP(Z|Y,\theta^{(i)} ) \log P(Y|\theta^{(i)}) \\ &= \sum_Z P(Z|Y,\theta^{(i)} )\log \frac{P(Y|Z,\theta) P(Z|\theta)}{P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})} \\ \end{align*}\]

B(, {(i)})=L({(i)})+_Z P(Z|Y,^{(i)} )

的一个下界。任何可使增大的,都可以使增加。选择能使当前极大的作为新的值。

\[\begin{align*} \theta^{(i+1)} &=\arg \max (L(\theta^{(i)})+\sum_Z P(Z|Y,\theta^{(i)} )\log \frac{P(Y|Z,\theta) P(Z|\theta)}{P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})}) \\ &=\arg \max (\sum_Z P(Z|Y,\theta^{(i)}))\log (P(Y|Z,\theta)P(Z|\theta))\\ &=\arg \max (\sum_Z P(Z|Y,\theta^{(i)})\log(P(Y,Z|\theta))) \\ &=\arg \max Q(\theta, \theta^{(i)}) \end{align*}\]

所以EM算法就是通过迭代不断求Q函数,并将之极大化,直至收敛。下图为EM算法的直观解释,的一个下界。

img

我们首先初始化模型的参数,我们基于这个参数对每一个隐变量进行分类,此时相当于我们观测到了隐变量。有了隐变量的观测值之后,原来含有隐变量的模型变成了不含隐变量的模型(以上是E步),因此我们可以直接使用极大似然估计来更新模型的参数(M步),再基于新的参数开始新一轮的迭代,直到参数收敛。

收敛性

定理一:为观测数据的似然函数,是EM算法得到的参数估计序列,是对应的似然函数序列,则是单调递增的。

定理二:是观测数据的对数似然函数,是EM算法得到的参数估计序列,是对应的对数似然函数序列。如果有上界,则收敛到某一值;在函数满足一定条件下,EM算法得到的参数估计序列的收敛值的稳定点。

GMM混合高斯

模型定义:

\(p(x)=\sum_{k=1}^{K}\alpha_{k}\mathcal{N}(x|\mu_{k},\Sigma_{k})\)

\(\sum_{k=1}^{K}\alpha_{k}=1\)

  1. 多个高斯模型的加权平均;(单个表达能力不够)
  2. 混合:隐变量->属于哪一个高斯分布
参数学习

\(\gamma_{j k}\)代表第j个观测来源于k个分模型(01随机变量)---------这里的隐变量

  1. 写出完全对数似然

    \(\begin{aligned} P(y, \gamma \mid \theta) &=\prod_{j=1}^{N} P\left(y_{j}, \gamma_{j 1}, \gamma_{j 2}, \cdots, \gamma_{j K} \mid \theta\right) \\ &=\prod_{k=1}^{K} \prod_{j=1}^{N}\left[\alpha_{k} \phi\left(y_{j} \mid \theta_{k}\right)\right]^{\gamma_{k}} \\ &=\prod_{k=1}^{K} \alpha_{k}^{n_{k}} \prod_{j=1}^{N}\left[\phi\left(y_{j} \mid \theta_{k}\right)\right]^{\gamma_{k}} \\ &=\prod_{k=1}^{K} \alpha_{k}^{n_{k}} \prod_{j=1}^{N}\left[\frac{1}{\sqrt{2 \pi} \sigma_{k}} \exp \left(-\frac{\left(y_{j}-\mu_{k}\right)^{2}}{2 \sigma_{k}^{2}}\right)\right]^{\gamma_{k t}} \end{aligned}\)

    对数似然:

    \(\log P(y,\gamma\vert\theta)=\sum_{k=1}^{K}[n_{k}\log\alpha_{k}+\sum_{j=1}^{N}\gamma_{k}\biggl[\log(\frac{1}{\sqrt{2\pi}})-\log\sigma_{k}-\frac{1}{2\sigma_{k}^{2}}(y_{j}-\mu_{k})^{2}\biggr]]\)

    其中:\(n_k = \sum_{j=1}^{N}\gamma_{jk}\), \(\sum_{k=1}^{K}n_{k}=N\) (Q函数推导的时候代入)

  2. 确定Q函数

    \(\begin{aligned} Q\left(\theta, \theta^{(i)}\right) &=E\left[\log P(y, \gamma \mid \theta) \mid y, \theta^{(i)}\right] \\ &=E\left\{\sum_{k=1}^{K} [n_{k} \log \alpha_{k}+\sum_{j=1}^{N} \gamma_{j k}\left[\log \left(\frac{1}{\sqrt{2 \pi}}\right)-\log \sigma_{k}-\frac{1}{2 \sigma_{k}^{2}}\left(y_{j}-\mu_{k}\right)^{2}\right]]\right\} \\ &=\sum_{k=1}^{K}\left\{\sum_{j=1}^{N}[\left(E \gamma_{j k}\right) \log \alpha_{k}+\sum_{j=1}^{N}\left(E \gamma_{j k}\right)\left[\log \left(\frac{1}{\sqrt{2 \pi}}\right)-\log \sigma_{k}-\frac{1}{2 \sigma_{k}^{2}}\left(y_{j}-\mu_{k}\right)^{2}\right]]\right\} \end{aligned}\)

    需要计算期望\(E (\gamma_{j k}|y, \theta)\)

    \(\hat{\gamma}_{j k} &=E\left(\gamma_{j k} \mid y, \theta\right)=P\left(\gamma_{j k}=1 \mid y, \theta\right) \\ &=\frac{P\left(\gamma_{j k}=1, y_{j} \mid \theta\right)}{\sum_{k=1}^{K} P\left(\gamma_{j k}=1, y_{j} \mid \theta\right)}&=\frac{P\left(y_{j} \mid \gamma_{j k}=1, \theta\right) P\left(\gamma_{j k}=1 \mid \theta\right)}{\sum_{k=1}^{K} P\left(y_{j} \mid \gamma_{j k}=1, \theta\right) P\left(\gamma_{j k}=1 \mid \theta\right)} &=\frac{\alpha_{k} \phi\left(y_{j} \mid \theta_{k}\right)}{\sum_{k=1}^{K} \alpha_{k} \phi\left(y_{j} \mid \theta_{k}\right)}, \quad j=1,2, \cdots, N ; \quad k=1,2, \cdots, K\)

    Q函数为:

    \(Q\left(\theta, \theta^{(i)}\right)=\sum_{k=1}^{K} [n_{k} \log \alpha_{k}+\sum_{k=1}^{N} \hat{\gamma}_{j k}\left[\log \left(\frac{1}{\sqrt{2 \pi}}\right)-\log \sigma_{k}-\frac{1}{2 \sigma_{k}^{2}}\left(y_{j}-\mu_{k}\right)^{2}\right]]\)

  3. 确定M步

    这一步求Q函数对\(\theta\)的极大值,分别对\(\mu \space \sigma \space \alpha\)求偏导等于零(\(\alpha\)需要在满足和为1,所以除个N)解得

    \({\hat{\mu}}_{k}={\frac{\sum_{j=1}^{N}{\hat{\gamma}}_{k}y_{j}}{\sum_{j=1}^{N}{\hat{\gamma}}_{k}}}\)

    \(\hat{\sigma}_{k}^{2}=\frac{\sum_{j=1}^{N} \hat{\gamma}_{j k}\left(y_{j}-\mu_{k}\right)^{2}}{\sum_{j=1}^{N} \hat{\gamma}_{j k}}\)

    \(\hat{\alpha}_{k}=\frac{n_{k}}{N}=\frac{\sum_{j=1}^{N} \hat{\gamma}_{j k}}{N}\)

整体算法:

VI与EM算法关系

https://zhuanlan.zhihu.com/p/97284299

Variational inference (变分推断,以下简称VI)和Expectation maximization(期望极大化,以下简称EM)这两种算法实际上是密切相关的。实际上我们可以将EM看作VI的特殊形式。

对于 [公式] ,我们有 [公式]如果我们想根据 [公式] 推测隐变量 [公式] 的概率,我们就需要计算如下的积分: [公式] 。然而 [公式] 有时难以计算,尤其是对于高维的系统,因为高维系统里面的积分复杂度很高。因此我们需要发展一种更加方便的方法来近似表达 [公式] 。VI就是用函数 [公式] 来近似表达 [公式]

Jensen's inequality

对于任何的凸函数(convex function) [公式] ,我们都有 [公式] 。Fig 1是一个直观的特例,当自变量 [公式] 的分布是在 [公式] 两点的均匀分布的时候,从图中可以明显看出 [公式] 。Jensen's inequality [公式] 取等号的条件是 [公式] ,即 [公式] 是一个常数。

imgFig 1. 一个凸函数以及E[(f(X))]和f[E(X)]的取值比较,这里X的分布是在a和b两点的均匀分布 (图片来自于Andrew Ng的讲义,见Reference &amp;amp;amp;amp;amp;amp;amp;amp;amp; Acknowledgement)

由于 [公式] 是一个凹函数,即 [公式] 是一个凸函数,所以满足 [公式] ,取等号的条件是自变量 [公式] 是一个常数。之后我们要用到有关 [公式] 的这些性质。

KL divergence & ELBO

先证明一个数学结论:对于任意的概率 [公式][公式] 是变量, [公式] 是参数), [公式] (这里 [公式] 是某个关于 [公式] 的概率密度函数),我们有

[公式]

其中的不等号来自于Jensen's inequality应用在凹函数 [公式] 上的结论。由此我们知道,对于上面的式子取等号的条件是 [公式] (也就是说在给定 [公式] 的情况下二者的比例是一个常数,无论 [公式] 取什么值),所以取等号的时候 [公式] (这是由于 [公式] 是概率密度,因此满足归一化条件)。由此我们可以定义KL divergence(记为 [公式] )和Evidence Lower BOund(简称为ELBO,记为 [公式] ):

[公式]
[公式]

由此可见KL divergence一定非负,而ELBO是 [公式] 的下界。KL divergence最小的时候等于0,此时 [公式] ,这是根据Jensen不等式取等号的条件得出的。并且KL divergence越小, [公式] 越接近 [公式] 。减小KL divergence等价于增大ELBO,因为我们要优化的目标函数是 [公式] ,而 [公式] 可以看作给定的量。

由此我们得到一个重要的结论:优化 [公式] 来增大ELBO等价于优化 [公式] 来逼近 [公式]

以下我们通过极大化ELBO,从而训练得到一个好的函数 [公式] 来近似表达 [公式]我们可以将ELBO的形式等价变换一下,得到另一种等价形式:

[公式]

其中 [公式] 是著名的Gibbs entropy。

Variational Inference

在实际操作中,首先我们有已经观察到的 [公式] 个数据点 [公式] ,我们需要通过优化 [公式] 来极大化ELBO,即对于每个数据点 [公式] ,我们希望得到函数 [公式] 。每个 [公式] 对应的ELBO是

[公式]

我们的目标是极大化 [公式]

[公式]

注意到对于不同的 [公式] ,我们选取的函数形式 [公式] 不同,因为 [公式][公式] 不同的时候是不同的关于 [公式] 的函数。一般来说,通过选取合适的、简单的 [公式] 的形式,例如exponential family,[公式] 可以解析地计算出来;对于 [公式] 则需要用stochastic optimization进行极大化,从而优化函数 [公式] (也就是优化函数 [公式] 的表达式里面包含的参数)。总结一下,VI就是通过选取一些形式简单的、具有良好性质的函数 [公式] 来近似表达 [公式] ,具体的操作方法是极大化ELBO。

Expectation Maximization

EM实际上可以看作一个简化的VI(通过一定的适用条件和一个类似于“作弊”的方法来简化计算)。EM的适用条件是函数 [公式] 的形式不太复杂,我们可以显式地表达出 [公式] 的时候。从适用条件上来看EM就是VI的一个特例。回忆第1节Motivation中我们说过,有时候 [公式] 难以计算,所以难以直接写出 [公式] 的具体形式。而EM就是适用于 [公式] 不难计算的情况,此时我们可以直接写出 [公式] 的具体形式。

当函数 [公式] 的形式不太复杂的时候,我们自然会选择 [公式] 来训练,因此我们可以说,EM就是选取[公式]的VI,这和EM的适用条件是自洽的。以下首先写出EM的算法,然后指出其中关键的“作弊”一步在哪里。

EM Algorithm

BEGIN

我们有 [公式] 个数据点 [公式] ,并且我们有函数 [公式][公式] 的表达式。

Step 0,初始化:初始随机猜测参数 [公式]

Step 1, E-step:在第 [公式] 步的时候 [公式] ,计算 [公式]

Step2, M-step: 按照如下规则得到新的参数 [公式]

[公式]

Step3, 重复 Step 1 & 2(迭代)直到收敛。

END

其中关键的“作弊”步骤是Step2,因为*严格来说我们应该这样计算* [公式]

[公式]

也就是将 [公式] 替换成 [公式] 后maximize ELBO。但是*实际上这个算法却是这么做的*

[公式]

也就是将ELBO表达式中的某几个 [公式] 固定在了 [公式] 的值(其中 [公式] 是第 [公式] 次优化得到的参数),只优化其余位置的 [公式] 值,从而使得极大化算法更加简便同时通过迭代方法确保最后能收敛到一个local maximum。由于 [公式] 相当于常数,因此 [公式] 相当于常数项,在极大化的时候可以去掉,由此我们可以得到

[公式]

并且通过迭代求解找到 local maximum。

week 7 内容:

  • louis philippe morency 《多模态机器学习》 50%
  • 论文阅读:
    1. Collaborative Denoising Auto-Encoders for Top-N Recommender Systems
    2. Semantic Image Synthesis with Spatially-Adaptive Normalization
    3. DAGAN: Dual Attention GANs for Semantic Image Synthesis

Collaborative Denoising Auto-Encoders for Top-N Recommender Systems(WSDM 2016)

主要工作

top-N推荐任务具有较多应用场景。该文作者基于降噪自编码器(Denoising Autoencoder)提出了系统过滤推荐模型CDAE,用于完成基于用户偏好的top-N推荐任务。CDAE模型在特定情况下可对多种经典协同过滤模型做泛化,具有较强的可解释性。 ##### 模型

img

如上图所示,CDAE模型以用户-物品评价矩阵的行作为输入( [公式] 式模型),通过一层神经网络编码得到用户的隐藏表示,再通过一层神经网络还原用户的交互行为(隐式反馈)。与最简单的 [公式] 模型不同,CDAE模型在编码得到隐藏表示时加入了对用户特征的考量,语义更丰富。为了使模型更具鲁棒性,CDAE模型对输入特征做了噪声处理(通过dropout或者加入高斯噪声实现)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class CDAE(nn.Module):
def __init__(self, nb_item, nb_user, nb_hidden, drop_rate=0.3):
'''
:param nb_item: 项目的数量
https://github.com/stormDL/CDAE_with_Pytorch
'''
super(CDAE, self).__init__()
self.item2hidden = nn.Sequential(
nn.Linear(nb_item, nb_hidden),
nn.Dropout(drop_rate)
)
self.id2hidden = nn.Embedding(nb_user, nb_hidden)
self.hidden2out = nn.Linear(nb_hidden, nb_item)
self.sigmoid = nn.Sigmoid()

def forward(self, uid, purchase_vec):
# 加入了用户特征
hidden = self.sigmoid(self.id2hidden(uid).squeeze(dim=1)+self.item2hidden(purchase_vec))
out = self.hidden2out(hidden)
out = self.sigmoid(out)
return out
img

Semantic Image Synthesis with Spatially-Adaptive Normalization(CVPR 2019 Oral)

这篇文章提出了新的归一化层,从而让生成效果更好。由于相同语义像素的值趋同,分割图经过传统normalization往往会变为0((x-u)/v),因此输入不同的语义信息,BN等传统normalization会“wash away”语义信息。这篇文章通过提出SPADE结构来保留语义信息。

Network

GauGan整体结构使用了上图所示SPADE ResBlk代替pix2pixHD中的resnetblock结构(SPADE替换了InstanceNorm)

Structure
image-20220113192316739

$\(和\) $代表着feature map上每个点的斜率和偏移量, 他们是通过两个卷积操作得到的;除此之外,剩下的就是按照每个通道做normalization。

DAGAN: Dual Attention GANs for Semantic Image Synthesis(ACM MM 2020)

Intro

这篇文章关心的问题在于通过语义分割图生成真实图像(phot-realistic images),该任务是conditional gan的一个延伸。现在相关的迁移工作都没有利用足够的语义信息限制生成过程,同时忽略了空间和通道的结构相关性(structure correlation),导致生成的照片大多缺乏细节同时生成痕迹明显(涂抹等)。

Network

这篇文章backbone network使用的是和GauGan相同的特征提取结构, 即backbone B。在Gaugan基础上引入空间注意力(SAM结构)和通道注意力(CAM结构)。

SAM将B的输出特征作为输入,输出空间相关特征图(语义模块在空间上的联系);CAM将B的每层特征作为输入,输出特征为通道相关特征图。通过元素加整合后输入卷积,得到fake image;对判别器D,它需要输入真实pair和假的pair,实现过程中将photo和语义分割图concat即可。

SAM:

backbone输出语义特征图首先分别进行max和avg pooling,将结果concate后输入卷积层和Sigmoid层,得到As是attention的weight,将As与Fb进行元素积,得到的Fs中相同label的pixel就有了联系(mutual gain), 这样生成的图片就可以有着语义上的持续性(一个object内的pixel应该是同样类别)

CAM:

对于同样的objects,不同尺度的特征应该有联系。因此CAM将backbone中不同特征图做channel wised attention,有利于捕获这样的信息。实现中作者只用了上采样过程中的一个特征图(倒数第二个加conv),和输出做channel-wised concatnation(所以是2C x H x W)。Fb通过AdaptiveAvgPool再经过两个卷积层得到Cx1x1的

channel weights。最后的输出Fc通过两个部分元素加得到,即赋权后的\(F_b^l\)以及\(F_b^{l-1}\)

loss:

  1. 实现角度,gen loss

    判别器:

    使用hinge loss衡量判别器效果,这样限制判别器去找最优的超平面。

    生成器:

    \(L_{FM}\)代表discriminator feature matching loss,它讲判别器的每层特征图抽出,确保real和fake特征图相近,借此优化G(discriminator部分使用detach(),确保更新G时D不动)

    \(L_P\)为perceptual loss,它使用一个pretrain 的VGG进行特征提取,同样,确保fake和real的特征相近。(感觉这个是站在自然图像角度,确保两个pair)

  2. 整体看,实际上loss是分为了conditional adversarial loss,discriminator feature matching loss,perceptual loss

Variational Autoencoders for Collaborative Filtering(WWW 2018)

主要工作

该文作者把变分自编码器拓展应用于基于隐式反馈的协同过滤推荐任务,希望通过非线性概率模型克服线性因子模型的局限。该文提出了基于变分自编码器(Variational Autoencoder)的生成模型VAE_CF,并针对变分自编码器的正则参数和概率模型选取做了适当调整(使用了多项式分布),使其在当时推荐任务中取得SOTA结果。

模型

如上图所示,虚线代表了采样操作,a是传统AE,b是denoising AE, c代表论文提出的vae。该模型根据标准高斯分布抽取K维隐藏因子 [公式] ,然后根据非线性函数 [公式] 生成用户 [公式] 点击所有物品的概率分布 [公式] ,最后根据多项式分布 [公式] 重构用户点击历史(隐式反馈的用户-物品评价矩阵对应行)。

其目标函数(ELBO):

img

VAE_CF模型较标准的变分自编码器做了如下调整:

1、将正则参数调至0.2(低于常规值1),称其为部分正则化(partially regularized)

2、使用了多项式分布而非高斯分布。

  • 多项式似然非常适合于隐式反馈数据的建模,并且更接近 rank loss;
  • 无论数据的稀缺性如何,采用principled Bayesian方法都更加稳健。

使用SGD进行优化:

week 6 内容:

  • louis philippe morency 《多模态机器学习》 35%

  • 论文阅读:

    1. DeepCoclustering
    2. AutoRec: Autoencoders Meet Collaborative Filtering
    3. AugGAN:Cross Domain Adaptation with GAN based DataAugmentation

DeepCoclustering(SDM 2019)

主要内容

framework

这篇文章提出了一种深度学习框架下的共聚类(co-clustering)方法,在聚类精度上超过了其他传统方法。

其中X代表instance(行,对应user), Y代表features(列,对应item), 分别进入Autoencoders进行降维(先进行pretrain 1000 epoch,然后利用encoder接入后面network进行端到端训练),将结果输入inference network(一个multi-layer neural network), 利用GMM框架进行cluster assignment。

优化目标

cluster assignment

参数和概率表示:

inference network:\(\eta_{r}\)\(\eta_{c}\) ——》 \(Q_{\eta_{r}}(k|h_i)\) \(Q_{\eta_{c}}(k|v_j)\) (cluster assignment distributions)

GMM:\(\phi_{r}\)\(\phi_{c}\) ——》\(P_{\phi_{r}}(k|h_i)\) \(P_{\phi_{c}}(k|v_j)\) (cluster assignment posterior)

对于AE输出的隐变量\(z_i\), 进入inference network中的MLN,得到\(h_i\):

\(\mathbf{h}_{i}=\operatorname{Softmax}\left(M L N\left(\mathbf{z}_{i} ; \eta_{r}\right)\right)\)

而后GMM第k个参数:\(\phi_{r}=\left\{\pi_{r}^{k}, \mu_{r}^{k}, \Sigma_{r}^{k}\right\}\),可以被表示为:

\(\begin{array}{l} \pi_{r}^{k}=N_{r}^{k} / N_{r}, \quad \mu_{r}^{k}=\frac{1}{N_{r}^{k}} \sum_{i=1}^{N_{r}^{k}} h_{i k} \mathbf{h}_{i} \\ \Sigma_{r}^{k}=\frac{1}{N_{r}^{k}} \sum_{i=1}^{N_{r}} h_{i k}\left(\mathbf{h}_{i}-\mu_{r}^{k}\right)\left(\mathbf{h}_{i}-\mu_{r}^{k}\right)^{T} \end{array}\)

其中\(N_{r}\)是instance的数目(即user),\(N_{r}^{k}\)是所有instance对应 \(h_i\)的 k-dim的和,这样第i个instance分配给第k个cluster的概率可以表示为:

\(\gamma_{r(i)}^{k}=\frac{\pi_{r}^{k} \mathcal{N}\left(\mathbf{h}_{i} \mid \mu_{r}^{k}, \Sigma_{r}^{k}\right)}{\sum_{k^{\prime}=1}^{g} \pi_{r}^{k^{\prime}} \mathcal{N}\left(\mathbf{h}_{i} \mid \mu_{r}^{k^{\prime}}, \Sigma_{r}^{k^{\prime}}\right)}\)

似然函数(取\(\gamma_{r(i)}^{k}\)上边求和):

\(\log \left\{\prod_{i=1}^{N_{r}} P_{\phi_{r}}\left(\mathbf{h}_{i}\right)\right\}=\sum_{i=1}^{N_{r}} \log P_{\phi_{r}}\left(\mathbf{h}_{i}\right)=\sum_{i=1}^{N_{r}} \log \left\{\sum_{k=1}^{K} \pi_{r}^{k} \mathcal{N}\left(\mathbf{h}_{i} \mid \mu_{r}^{k}, \Sigma_{r}^{k}\right)\right\}\)

DeepCC并没有直接进行MLE,而是最大化变分lower bound,有两点优势:

  1. 通过最小化Q P之间的KL散度,让GMM更准确

  2. 与对数似然绑定,让训练过程更加effective

    lower bound:

\(\begin{array}{l} \sum_{i=1}^{N_{r}} \log P\left(\mathbf{h}_{i}\right)=\sum_{i=1}^{N_{r}} \log \int_{k} P\left(k, \mathbf{h}_{i}\right) \\ =\sum_{i=1}^{N_{r}} \log \int_{k} \frac{P\left(k, \mathbf{h}_{i}\right)}{Q\left(k \mid \mathbf{h}_{i}\right)} Q\left(k \mid \mathbf{h}_{i}\right) \\ =\sum_{i=1}^{N_{r}} \log \left(E_{Q}\left[\frac{P\left(k, \mathbf{h}_{i}\right)}{Q\left(k \mid \mathbf{h}_{i}\right)}\right]\right) \\ \geq \sum_{i=1}^{N_{r}} E_{Q}\left[\log \frac{P\left(k, \mathbf{h}_{i}\right)}{Q\left(k \mid \mathbf{h}_{i}\right)}\right] \\ =\sum_{i=1}^{N_{r}}\left\{E_{Q}\left[\log P\left(k, \mathbf{h}_{i}\right)\right]+H\left(k \mid \mathbf{h}_{i}\right)\right\} \\ =\mathcal{L}_{r} \end{array}\)

中间把log拿入期望使用了jensen ‘s inequality

更进一步,可以得到Q与P之间KL散度与lower bound关系(第二步减了一个\(logP(h_i)\),又加了一个):

\(\begin{array}{l} \mathcal{L}_{r}=\sum_{i=1}^{N_{r}}\left\{E_{Q}\left[\log P\left(k, \mathbf{h}_{i}\right)\right]-E_{Q}\left(\log Q\left(k \mid \mathbf{h}_{i}\right)\right)\right\} \\ =\sum_{i=1}^{N_{r}}\left\{\int_{k} Q\left(k \mid \mathbf{h}_{i}\right) \log \frac{P\left(k, \mathbf{h}_{i}\right)}{Q\left(k \mid \mathbf{h}_{i}\right)}-\right. \left.\int_{k} Q\left(k \mid \mathbf{h}_{i}\right) \log P\left(\mathbf{h}_{i}\right)+\log P\left(\mathbf{h}_{i}\right)\right\} \\ =\sum_{i=1}^{N_{r}}\left\{\int_{k} Q\left(k \mid \mathbf{h}_{i}\right) \log \frac{P\left(k, \mathbf{h}_{i}\right)}{Q\left(k \mid \mathbf{h}_{i}\right) P\left(\mathbf{h}_{i}\right)}+\log P\left(\mathbf{h}_{i}\right)\right\} \\ =\sum_{i=1}^{N_{r}}\left\{\int_{k} Q\left(k \mid \mathbf{h}_{i}\right) \log \frac{P\left(k \mid \mathbf{h}_{i}\right)}{Q\left(k \mid \mathbf{h}_{i}\right)}+\log P\left(\mathbf{h}_{i}\right)\right\} \\ =\sum_{i=1}^{N_{r}}\left\{-K L\left(Q\left(k \mid \mathbf{h}_{i}\right) \| P\left(k \mid \mathbf{h}_{i}\right)\right)+\log P\left(\mathbf{h}_{i}\right)\right\} \end{array}\)

对应可以得到feature的assignment loss:

\(\mathcal{L}_{c}=\sum_{j=1}^{N_{c}}\left\{E_{Q}\left[\log P\left(k, \mathbf{v}_{j}\right)\right]-E_{Q}\left(\log Q\left(k \mid \mathbf{v}_{j}\right)\right)\right\}\)

Instance-Feature Cross Loss

对联合概率\(P(X,Y)\)设计loss进行优化

assignment到cluster的概率:

instance: \(\gamma_{r(i)}=\left(\gamma_{r(i)}^{1}, \cdots, \gamma_{r(i)}^{g}\right)^{T}\)

feature:\(\gamma_{c(i)}=\left(\gamma_{c(i)}^{1}, \cdots, \gamma_{c(i)}^{g}\right)^{T}\)

第i个instance和第j个instance的联合概率(划分前)表示为:

\(p\left(\mathbf{x}_{i}, \mathbf{y}_{j}\right)=\mathcal{J}\left(\boldsymbol{\gamma}_{r(i)}, \boldsymbol{\gamma}_{c(j)}\right)\)

第s个instance cluster和第t个feature cluster的联合概率(划分后)为:

\(p\left(\hat{\mathbf{x}}_{s}, \hat{\mathbf{y}}_{t}\right)=\sum\left\{p\left(\mathbf{x}_{i}, \mathbf{y}_{j}\right) \mid \mathbf{x}_{i} \in \hat{\mathbf{x}}_{s}, \mathbf{y}_{j} \in \hat{\mathbf{y}}_{t}\right\}\)

在论文中,作者使用点积来表示\(\mathcal{J}\),其实是可以尝试改变的。这样做的原因有两点:

  1. 大部分co-cluster, instance cluster以及feature cluster 数量是相等的
  2. 相近的instance 有着相似的 feature

各自的互信息:

\(I(X ; Y)=\sum_{\mathbf{x}_{i}} \sum_{\mathbf{y}_{j}} p\left(\mathbf{x}_{i}, \mathbf{y}_{j}\right) \log \frac{p\left(\mathbf{x}_{i}, \mathbf{y}_{j}\right)}{p\left(\mathbf{x}_{i}\right) p\left(\mathbf{y}_{j}\right)}\)

\(I(\hat{X} ; \hat{Y})=\sum_{\hat{\mathbf{x}}_{s}} \sum_{\hat{\mathbf{y}}_{t}} p\left(\hat{\mathbf{x}}_{s}, \hat{\mathbf{y}}_{t}\right) \log \frac{p\left(\hat{\mathbf{x}}_{s}, \hat{\mathbf{y}}_{t}\right)}{p\left(\hat{\mathbf{x}}_{s}\right), p\left(\hat{\mathbf{y}}_{t}\right)}\)

互信息之间的差:\(I(X ; Y)-I(\hat{X} ; \hat{Y})\)

\(\begin{array}{l} =\sum_{\hat{\mathbf{x}}_{s}} \sum_{\hat{\mathbf{y}}_{t}} \sum_{\mathbf{x}_{i} \in \hat{\mathbf{x}}_{s}} \sum_{\mathbf{y}_{j} \in \hat{\mathbf{y}}_{t}} p\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) \log \frac{p\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)}{p\left(\mathbf{x}_{i}\right) p\left(\mathbf{x}_{j}\right)} \\ -\sum_{\hat{\mathbf{x}}_{s}} \sum_{\hat{\mathbf{y}}_{t}}\left(\sum_{\mathbf{x}_{i} \in \hat{\mathbf{x}}_{s}} \sum_{\mathbf{y}_{j} \in \hat{\mathbf{y}}_{t}} p\left(\mathbf{x}_{i}, \mathbf{y}_{j}\right)\right) \log \frac{p\left(\hat{\mathbf{x}}_{s}, \hat{\mathbf{y}}_{t}\right)}{p\left(\hat{\mathbf{x}}_{s}\right) p\left(\hat{\mathbf{y}}_{t}\right)} \\ =\sum_{\hat{\mathbf{x}}_{s}} \sum_{\hat{\mathbf{y}}_{t}} \sum_{\mathbf{x}_{i} \in \hat{\mathbf{x}}_{s}} \sum_{\mathbf{y}_{j} \in \hat{\mathbf{y}}_{t}} p\left(\mathbf{x}_{i}, \mathbf{y}_{j}\right) \log \frac{p\left(\mathbf{x}_{i}, \mathbf{y}_{j}\right)}{q\left(\mathbf{x}_{i}, \mathbf{y}_{j}\right)} \\ =K L(p(X, Y) \| q(X, Y)) \\ \geq 0 \end{array}\)

因此为了让差最小化(划分后损失最少),设计loss为:

\(1-\frac{I(\hat{X} ; \hat{Y})}{I(X ; Y)}\)

整体loss

综合上述loss:

\(\begin{array}{c} \quad \min _{\theta_{r}, \theta_{c}, \eta_{r}, \eta_{c}} J=J_{1}+J_{2}+J_{3} \\ J_{1}=\frac{\lambda_{1}}{n} \sum_{i=1}^{n} l\left(\mathbf{x}_{i}, g_{r}\left(\mathbf{z}_{i}\right)\right)+\lambda_{2} P_{a e}\left(\theta_{r}\right)+\lambda_{3}\left(-\mathcal{L}_{r}\right)+P_{i n f}\left(\Sigma_{r}\right) \\ J_{2}=\frac{\lambda_{1}}{d} \sum_{j=1}^{i} l\left(\mathbf{y}_{j}, g_{c}\left(\mathbf{w}_{j}\right)\right)+\lambda_{2} P_{a e}\left(\theta_{c}\right)+\lambda_{3}\left(-\mathcal{L}_{c}\right)+P_{\text {inf }}\left(\Sigma_{c}\right) \\ J_{3}=\lambda_{4}\left(1-\frac{I(\hat{X} ; \hat{Y})}{I(X ; X)}\right) \end{array}\)

AutoRec: Autoencoders Meet Collaborative Filtering(WWW 2015)

1、写作动机

2015年前后,深度神经网络在视觉(vision)和对话(speech)数据建模方面取得了显著的突破,该文作者由此产生了把深度神经网络应用到协同过滤模型的想法。该文基于自编码器提出了协同过滤模型AutoRec,并通过实验证明了该模型较此前的基于神经网络的协同过滤模型具有更强的表示能力和更高的计算效率。

2、问题定义

给定用户集合 [公式] 、物品集合[公式] 、部分用户-物品评分记录构成的用户-物品评价矩阵[公式],对未知用户-物品评价行为做评分预测,根据均方根误差(RMSE)做评估。

其模型也可以写成重建函数形式:

[公式] (1)

其中 [公式][公式] 分别为输出层和隐藏层的激活函数,参数集 [公式] , [公式] , [公式] , [公式] , [公式] . 对应 [公式] 个用户和 [公式] 个条目, [公式] 维隐藏层。

跟AutoEncoder类似地,其损失函数为

[公式]

不过考虑到对模型参数的限制,比如加入L2正则,损失函数变化为:

[公式]

其中 [公式] 为Frobenius范数.

3、具体模型

img

如上图所示,该文提出的AutoRec模型采取了最简单的自编码器结构,通过一层神经网络编码输入特征得到隐藏层表示,再通过一层神经网络表示对隐藏层表示做解码还原输入特征。根据输入特征的不同,该模型可分为 [公式][公式] :输入特征为用户-物品评价矩阵的行,则为基于物品特征学习的自编码器 [公式] ;输入特征为用户-物品评价矩阵的列,则为基于用户特征学习的自编码器 [公式]

CycleGAN( ICCV 2017)

pix2pix使用了pair的data进行训练,然而现实中往往是unpaired-data,CycleGAN就是希望能够在目标域和源域之间,不用建立一对一的映射,就可以完成迁移的训练。

img

做到这一点:

  1. 需要有两个判别器, 分别判断X到Y与Y到X的生成,以及Y到X的生成。

  2. cycle-consistency loss ,生成器可能会直接生成一张目标域的图像而无视源域图像,因此需要保证能够映射回X

    img

AugGAN:基于GAN的图像数据增强(ECCV 2018)

主要内容

augGan利用语义分割的结构意识(structure-aware)进行数据域的迁移。与cycleGan等进行风格迁移的image2image translation不同,这篇文章利用结构意识强调生成照片的真实性而非艺术性。

AugGAN的训练数据包含:1. 分割mask;2,不同领域的图像(春天和冬天,白天和黑夜)。

img

主要结构:

img

AugGan结构如上图:

  1. 整体迁移是有方向的,X代表源域图像,Y代表目标域图像。$ E_x, E_y\(分别代表X和Y的encoder,将图像降维后会得到特征域Z,Z会对接两个decoder,分别输出预测的分割图\){},{}\(,以及生成的fake image\) {X},{Y}$。
  2. augGan使用了cycleGan类似的循环结构,保证循环一致性,\(\bar{Y}\)经过\(E_y,G_y\)得到重构后的$ X_{rec}\(,对\){X}$同理。
  3. 有两个判别器\(D_x,D_y\)
  4. augGan对于decoder中的残差结构使用了hard-share权重共享,对于上采样的结构使用soft-share

loss 设计

总体loss:

\(\begin{aligned} \mathcal{L}_{\text {full }} &=\mathcal{L}_{G A N}\left(E_{x}, G_{x}, D_{x}, X, Y\right)+\mathcal{L}_{G A N}\left(E_{y}, G_{y}, D_{y}, Y, X\right) \\ &+\lambda_{\text {cyc }} * \mathcal{L}_{\text {cyc }}\left(E_{x}, G_{x}, E_{y}, G_{y}, X, Y\right) \\ &+\lambda_{\text {seg }} *\left(\mathcal{L}_{\text {seg }}\left(E_{x}, P_{x}, X, \hat{X}\right)+\mathcal{L}_{\text {seg }}\left(E_{y}, P_{y}, Y, \hat{Y}\right)\right) \\ &+\lambda_{\omega} *\left(\mathcal{L}_{\omega_{x}}\left(\omega_{G_{x}}, \omega_{P_{x}}\right)+\mathcal{L}_{\omega_{y}}\left(\omega_{G_{y}}, \omega_{P_{y}}\right)\right) \end{aligned}\)

  1. 结构意识(structure-aware)

    在转换图像的时候,让模型明白不同位置是什么样的背景(语义特征)有利于迁移,AugGan使用分割的标签来实现。

    \(\begin{aligned} \mathcal{L}_{\text {seg }-x}\left(P_{x}, E_{x}, X, \hat{X}\right) &=\lambda_{\text {seg-L1 }} \mathbb{E}_{x \sim p_{\text {data }(x)}}\left[\left\|P_{x}\left(E_{x}(x)\right)-\hat{x}\right\|_{1}\right] \\ &+\lambda_{\text {seg-crossentropy }} \mathbb{E}_{x \sim p_{\text {data }(x)}}\left[\left\|\log \left(P_{x}\left(E_{x}(x)\right)-\hat{x}\right)\right\|_{1}\right] \end{aligned}\)

    L1loss以及交叉熵损失

  2. 权值共享

    hard-sharing: 完全共享一样的权值

    soft-sharing:通过loss进行约束

    $ {}({G}, {P})=-(({G_{x}} {P{x}} /|{G{x}}|{2}|{P_{x}}|_{2})^{2}) $

  3. 循环一致性(Cycle consistency)

    生成的图片经过重新编码解码能够还原回原来的图片,这样可以保证P(z|X)不会退化为P(z)(不会随机生成目标域的图像)。

    \(\begin{aligned} \mathcal{L}_{c y c}\left(E_{x}, G_{x}, E_{y}, G_{y}, X, Y\right) &=\mathbb{E}_{x \sim p_{\text {data }(x)}}\left[\left\|G_{y}\left(E_{y}\left(G_{x}\left(E_{x}(x)\right)\right)\right)-\mathrm{x}\right\|_{1}\right] \\ &+\mathbb{E}_{y \sim p_{\text {data }(y)}}\left[\left\|G_{x}\left(E_{x}\left(G_{y}\left(E_{y}(y)\right)\right)\right)-y\right\|_{1}\right] \end{aligned}\)

  4. 对抗训练

​ 论文中对抗训练使用了原始的GanLoss:

\(\begin{aligned} \mathcal{L}_{G A N_{1}}\left(E_{x}, G_{x}, D_{x}, X, Y\right) &=\mathbb{E}_{y \sim p_{\text {data }(y)}}\left[\log D_{x}(y)\right] \\ &+\mathbb{E}_{x \sim p_{\text {data }(x)}}\left[\log \left(1-D_{x}\left(G_{x}\left(E_{x}(x)\right)\right)\right)\right] \end{aligned}\)

迁移效果

img

2022/6/3 829. 连续整数求和

type:数学

image-20220628142602227.png
image-20220628142629543.png

2022/6/4 929. 独特的电子邮件地址

type:模拟、字符串

image-20220628142802950.png

https://www.runoob.com/java/java-string.html

2022/6/5 478. 在圆内随机生成点

type:数学、采样

  1. 拒绝采样, 过滤红色部分的点
  2. 从pdf到cdf推导
image-20220628143039943.png
image-20220628143102635.png
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
Random random;
double xc, yc, r;

public Solution(double radius, double x_center, double y_center) {
random = new Random();
xc = x_center;
yc = y_center;
r = radius;
}

public double[] randPoint() {
double u = random.nextDouble();
double theta = random.nextDouble() * 2 * Math.PI;
double r = Math.sqrt(u);
return new double[]{xc + r * Math.cos(theta) * this.r, yc + r * Math.sin(theta) * this.r};
}
}

2022/6/6 732. 我的日程安排表 III

type: 差分数组、线段树

image-20220628143224257.png
image-20220628143241743.png

2022/6/7 875. 爱吃香蕉的珂珂

type: 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int l_speed = 1, r_speed = 0;
for(int pile: piles){
r_speed = Math.max(r_speed, pile);
}
int k = r_speed;
while(l_speed < r_speed){
int speed = (r_speed - l_speed) / 2 + l_speed;
// calculate time consumpution
long time = 0;
for (int pile: piles){
//(pile + speed - 1) / speed;
int tmp = (int)Math.ceil((double)pile / speed);
time += tmp;
}

if(time <= h){
k = speed;
r_speed = speed;
}else{
l_speed = speed + 1;
}
}
return k;
}
}

2022/6/9 497. 非重叠矩形中的随机点

type:数学、采样

先随机使用哪个矩形,再随机该矩形内的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
int[][] rs;
int[] sum;
int size;
Random random = new Random();
public Solution(int[][] rects) {
rs = rects;
size = rs.length;
sum = new int [size+1];
// 构建前缀和数组
for(int i=1;i<=size;++i){
int area = (rs[i - 1][2] - rs[i - 1][0] + 1) * (rs[i - 1][3] - rs[i - 1][1] + 1);
sum[i] = sum[i-1] + area;
}

}

public int[] pick() {
int val = random.nextInt(sum[size]) + 1;
int l = 0, r = size;
// 二分找第一个使得面积小于val的矩形
while(l < r){
int mid = l + (r-l) / 2;
if(sum[mid] >= val) r=mid;
else l = mid + 1;
}
int [] cur = rs[r-1];
// nextInt的取值是[0,n) ,不包括n
int x = random.nextInt(cur[2] - cur[0] + 1) + cur[0];
int y = random.nextInt(cur[3] - cur[1] + 1) + cur[1];
return new int [] {x, y};
}
}

2022/6/14 498. 对角线遍历

type: 矩阵、找规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
每层的索引和相等:
1. 假设矩阵无限大;
2. 索引和为{偶}数,向上遍历,{横}索引值递减,遍历值依次是(x,0),(x-1,1),(x-2,2),...,(0,x)
3. 索引和为{奇}数,向下遍历,{纵}索引值递减,遍历值依次是(0,y),(1,y-1),(2,y-2),...,(y,0)

每层的索引和:
0: (00)
1: (01)(10)
2: (20)(11)(02)
3: (03)(12)(21)(30)
4: (40)(31)(22)(13)(04)
5: (05)(14)(23)(32)(41)(50)
6: (60)(51)................(06)

按照“层次”遍历,依次append在索引边界内的值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public int[] findDiagonalOrder(int[][] mat) {
if (mat == null || mat.length == 0) {
return new int[]{};
}
int m = mat.length, n = mat[0].length;
int[] res = new int[m * n];
int sum = 0, idx = 0;
while(sum < m+n){
if(sum % 2 == 0){
// 向上遍历
int r = sum<m?sum:(m-1);
int c = sum - r;
while(r>=0 && c>=0 && r<m && c<n){
res[idx++] = mat[r][c];
r--;c++;
}
}else{
// 向下遍历
int c = sum<n?sum:(n-1);
int r = sum - c;
while(r>=0 && c>=0 && r<m && c<n){
res[idx++] = mat[r][c];
r++;c--;
}
}
sum++;
}
return res;
}
}

2022/6/22 513. 找树左下角的值

type: 二叉树

  1. DFS

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    int max_depth, res;
    public int findBottomLeftValue(TreeNode root) {
    dfs(root, 1);
    return res;
    }
    void dfs(TreeNode node, int depth){
    if(node == null){
    return;
    }
    if(depth>max_depth){
    // 保证每个depth存的都是最左边的结点
    max_depth = depth;
    res = node.val;
    }
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
    }
    }
  2. BFS

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    int max_depth, res;
    public int findBottomLeftValue(TreeNode root) {
    Deque<TreeNode> q = new ArrayDeque<>();
    q.addLast(root);
    int res = 0;
    while(!q.isEmpty()){
    int num = q.size();
    res = q.peek().val;
    while(num>0){
    TreeNode now = q.pollFirst();
    if(now.left != null) q.addLast(now.left);
    if(now.right != null) q.addLast(now.right);
    num--;
    }
    }
    return res;
    }
    }

week 2 内容:

  • Jure leskovec cs224w 课程进度80%(作业进度60%)

  • 论文阅读:FM、NGCF、light-gcn、cluster-GCN

  • 毕设准备

GNN

GCN

就像"卷积"这个名字所指代的那样,这个想法来自于图像,之后引进到图(Graphs)中。然而,图像有固定的结构时,而图(Graphs)就复杂得多,结构不定。

img

computation_graph_for_a

两个步骤:

  1. propagation(message passing)

  2. aggregation

\[ h_v^{(l)} = W_l\cdot h_v^{(l-1)} + W_r \cdot AGG(\{h_u^{(l-1)}, \forall u \in N(v) \}) \]

\[ AGG(\{h_u^{(l-1)}, \forall u \in N(v) \}) = \frac{1}{|N(v)|} \sum_{u\in N(v)} h_u^{(l-1)} \]

在这里插入图片描述
GQNyxe.png

GraphSage

  • 在 aggregate 的形式上做了进一步扩展—GraphSAGE的想法是采用一个通用的aggregation函数来表示黑箱的运算,可以采用不同的方法聚合其邻居,然后再将其与自身特征拼接

  • 除了 mean,其实任意的将多个 embedding 映射到一个 embedding 的函数都可以用来做聚合,例如 pool,例如 LSTM,

    在这里插入图片描述

cluster-GCN

https://blog.csdn.net/sinat_26811377/article/details/97810302

聚类总结

metis

目前基于SGD的gcn算法,大规模GCN的训练面临问题:

1)面临随着gcn层数增长,计算复杂度呈指数增长;

2)需要保存整个Graph和每个node的embedding,存储量巨大。

Cluster-GCN通过graph聚类算法来筛选联系紧密的sub-graph,从而在sub-graph中的一组node进行采样,并且限制该sub-graph中的邻居搜索,可以显著提高搜索效率。

在这里插入图片描述
  1. metis和graclus谱聚类
  2. for循环,每次随机选一个cluster(without replacement,不放回)计算subgraph的梯度进行更新
  3. 直至优化完成

GNN在推荐(协同过滤)领域应用

Neural Collaborative Filtering

CF发展

NCF不如MF?

img

研究点:

  • 关于推荐系统的深度学习研究不多;

  • 对user和item的交互行为(interaction)的建模大多使用MF,对user和item的隐特征使用内积计算,而这是一种线性方式。而通过引入user/item偏置,提高MF效果也说明内积不足以捕捉到用户交互数据中的复杂结构信息

模型框架:

【导读】Neural Collaborative Filtering

这里关注的问题:

并没有把user和item的交互信息本身编码进 embedding 中,而NGCF希望显式建模User-Item 之间的高阶连接性来提升 embedding

图神经网络应用

NGCF(SIGIR 2019)

在这里插入图片描述

推荐领域的user-item交互可以被看做是一个二部图。

High-order Connectivity 解释高阶连通性如上图,图1左边为一般CF中user-item交互的二部图,双圆圈表示此时需要预测的用户u1,对于u1我们可以把有关他的连接扩展成右图的树形结构,l是能到达的路径长度(或者可以叫跳数),l=1表明能一步到达u1的item,此时可以看到最外层的跳数相同的i4跟i5相比(l都为3),用户u1对i4的兴趣可能要比i5高,因为i4->u2->i2->u1、i4->u3->i3->u1有两条路径,而i5->u2->i2->u1只有一条,所以i4的相似性会更高。所以如果能扩展成这样的路径连通性来解释用户的兴趣,就是高阶连通性。

完整模型:

在这里插入图片描述

NGCF的完整模型如下图,可以分为三个部分来看:

Embeddings:对user和item的嵌入向量,普通的用id来嵌入就可以了 Embedding Propagation Layers:挖掘高阶连通性关系来捕捉交互以细化Embedding的多个嵌入传播层 Prediction Layer:用更新之后带有交互信息的 user 和 item Embedding来进行预测

message passing:

$ m_{u i}=(W_{1} e_{i}+W_{2}(e_{i} e_{u})) $

使用embedding后的user,item的特征$ e_u $ 、\(e_i\) 作为输入,然后两者计算内积相似度来控制邻域的信息,再加回到item上,用权重W控制权重,最后的N是u和i的度用来归一化系数,可以看做是折扣系数,随着传播路径长度的增大,信息慢慢衰减。

aggregation:

\(e_{u}^{(1)}=\operatorname{LeakyReLU}\left(m_{u \leftarrow u}+\sum_{i \in N_{u}} m_{u \leftarrow i}\right)\)

3-hop计算图:

在这里插入图片描述

\(E^{(l)}=\sigma\left((L+I) E^{(l-1)} W_{1}^{(l)}+L E^{(l-1)} \odot E^{(l-1)} W_{2}^{(l)}\right)\)

light-GCN(SIGIR 2020)

在这里插入图片描述

NGCF主要遵循标准GCN变形得到,包括使用非线性激活函数和特征变换矩阵w1和W2。然而作者认为实际上这两种操作对于CF并没什么0用,理由在于不管是user还是item,他们的输入都只是ID嵌入得到的,即根本没有具体的语义(一般在GCN的应用场景中每个节点会带有很多的其他属性),所以在这种情况下,执行多个非线性转换不会有助于学习更好的特性;更糟糕的是,它可能会增加训练的困难,降低推荐的结果。

\(\begin{aligned} e_{u}^{(k+1)} &=\sum_{i \in N_{u}} \frac{1}{\sqrt{\left|N_{u}\right|} \sqrt{\left|N_{i}\right|}} e_{i}^{(k)} \\ e_{i}^{(k+1)} &=\sum_{u \in N_{i}} \frac{1}{\sqrt{\left|N_{i}\right|} \sqrt{\left|N_{u}\right|}} e_{u}^{(k)} \end{aligned}\)

只聚合连接的邻居,连自连接都没有。最后的K层就直接组合在每个层上获得的嵌入,以形成用户(项)的最终表示:

\(\begin{array}{c} e_{u}=\sum_{k=0}^{K} \alpha_{k} e_{u}^{(k)} \\ e_{i}=\sum_{k=0}^{K} \alpha_{k} e_{i}^{(k)} \end{array}\)

其中\[ α_k=1 / (k+1) \]

为什么要组合所有层?

  • GCN随着层数的增加会过平滑,直接用最后一层不合理
  • 不同层的嵌入捕获不同的语义,而且更高层能捕获更高阶的信息,结合起来更加全面
  • 将不同层的嵌入与加权和结合起来,可以捕获具有自连接的图卷积的效果,这是GCNs中的一个重要技巧