Attention

一. 定义

我们有一个query向量,和一段key向量,这里query可以理解为一个包含比较多信息的全局向量,我们利用这个query对所有key向量进行相似度计算,然后softmax归一化得到attention概率权重,最后我们对每个key所对应的权重和value进行加权求和,得到最终的输出向量然后去做分类或者预测等任务。

本质是(带权)特征筛选

在Transformer中,在encoder self-attention中,QKV都来自encoder的上一层输出;在decoder self-attention中, QKV都来自decoder的上一层输出,但注意mask(在 time_step 为 t 的时刻,我们的解码输出应该只能依赖于 t 时刻之前的输出,而不能依赖 t 之后的输出);在encoder-decoder attention中,Q来自decoder的上一层输出,KV来自encoder的上一层输出。

二. 分类

计算区域

Soft Attention/Global Attention,这是比较常见的Attention方式,对所有key求权重概率,每个key都有一个对应的权重,是一种全局的计算方式。

Local Attention,这种方式其实是以上两种方式的一个折中,对一个窗口区域进行计算。先用Hard方式定位到某个地方,以这个点为中心可以得到一个窗口区域,在这个小区域内用Soft方式来算Attention。

Hard Attention,这种方式是直接精准定位到某个key,其余key就都不管了,相当于这个key的概率是1,其余key的概率全部是0。

三. 相似度计算

点乘,拼接,cos相似度

四. 常见task

  • 1)机器翻译:encoder用于对原文建模,decoder用于生成译文,attention用于连接原文和译文,在每一步翻译的时候关注不同的原文信息。
  • 2)文本分类:一般是对一段句子进行attention,得到一个句向量去做分类。
  • 3)摘要生成:encoder用于对原文建模,decoder用于生成新文本,从形式上和机器翻译都是seq2seq任务,但是从任务特点上看,机器翻译可以具体对齐到某几个词,但这里是由长文本生成短文本,decoder可能需要capture到encoder更多的内容,进行总结。

五.常见问题

  • Attention和全连接层的区别
    • 全连接的作用的是对一个实体进行从一个特征空间到另一个特征空间的映射,而注意力机制是要对来自同一个特征空间的多个实体进行整合。
    • 全连接的权重对应的是一个实体上的每个特征的重要性,而注意力机制的输出结果是各个实体的重要性。
    • 全连接的权重一般与位置有关而且是固定的,而注意力机制与位置无关使得权重与输入有关所以是动态的。
  •  Self-attention(q=k=v) 和 RNN的区别
    • RNN长距离依赖需要经过大量的时间步,训练慢,并且有可能因为梯度消失只能建立短距离依赖,self-attention可以直接计算两个远距离信息之间的依赖关系。
    • Self-attention并没有解决并行问题,并行问题通过Transformer的positional encoding加入位置信息辅助解决。

六. 参考

二叉树路径问题

112. 路径总和

113. 路径总和 II

124. 二叉树中的最大路径和 略难

129. 求根到叶子节点数字之和

257. 二叉树的所有路径

437. 路径总和 III

543. 二叉树的直径

988. 从叶结点开始的最小字符串

return the last

LightGBM

一.概述

LightGBM 由微软提出,主要用于解决 GDBT 在海量数据中遇到的问题,以便其可以更好更快地用于工业实践中。对 XGBoost 具有训练速度快、内存占用低的特点

  • 单边梯度抽样算法;
  • 直方图算法;
  • 互斥特征捆绑算法;
  • 基于最大深度的 Leaf-wise 的垂直生长算法;
  • 类别特征最优分割;
  • 特征并行和数据并行;
  • 缓存优化。

二. 详述

  • 单边梯度抽样算法
    • GBDT 算法的梯度大小可以反应样本的权重,梯度越小说明模型拟合的越好,单边梯度抽样算法(Gradient-based One-Side Sampling, GOSS)利用这一信息对样本进行抽样,减少了大量梯度小的样本,在接下来的计算锅中只需关注梯度高的样本,极大的减少了计算量。GOSS 算法保留了梯度大的样本,并对梯度小的样本进行随机抽样,为了不改变样本的数据分布,在计算增益时为梯度小的样本引入一个常数进行平衡。
  • 直方图算法
    • 直方图算法的基本思想是将连续的特征离散化为 k 个离散特征,同时构造一个宽度为 k 的直方图用于统计信息(含有 k 个 bin)。利用直方图算法我们无需遍历数据,只需要遍历 k 个 bin 即可找到最佳分裂点。
    • 直方图加速:通过父节点的直方图与相邻叶节点的直方图相减的方式构建,从而减少了一半的计算量。
    • XGBoost 在进行预排序时只考虑非零值进行加速,而 LightGBM 也采用类似策略:只用非零特征构建直方图。
  • 互斥特征捆绑算法
    • 将一些特征进行融合绑定,则可以降低特征数量。
  • 带深度限制的 Leaf-wise 算法
    • Level-wise(XGBoost):基于层进行生长,直到达到停止条件;
    • Leaf-wise(LightGBM):每次分裂增益最大的叶子节点,直到达到停止条件。
  • 类别特征最优分割
    • LightGBM 原生支持类别特征,采用 many-vs-many 的切分方式将类别特征分为两个子集,实现类别特征的最优切分

三. 参考

Dialogue system papers

ICSL

Other