发表于 | 分类于 ，

词向量之DNN模型
word2vec-Hierarchical Softmax
word2vec-Negative Sampling

词向量之DNN模型

  • 模型
    • 训练方式：CBOW或者Skip-gram
    • 输入：one-hot向量，n*V矩阵（V表示词汇数量，n表示输入词数）
    • Hidden layer：我们想得到的N维词向量
    • Output layer：softmax分类
  • 核心就是采用语言模型，学习Input layer和Hidden layer直接的参数矩阵（词嵌入矩阵）
  • 训练方式：softmax进行多分类，采用交叉熵作为loss，梯度下来求解方法进行训练
  • 缺点：
    • 从input layer到hidden layer
      每次我们只是使用了几个单词进行训练，但是在计算梯度的过程却要对整个参数矩阵进行运算，这样计算效率低下
    • 从hidden layer到output layer
      采用全连接层并用softmax方式，需要对输出层中每个位置求其概率。为了得到输出层的每个位置的概率，我们需要求得所有单词的得分，如果一个词汇表很庞大的话，这是很耗资源的

word2vec-Hierarchical Softmax

参考FastText

  • 霍夫曼树
    参考FastText中的霍夫曼链接，总的来说就是让出现频率大的词在树较浅的层次，频率小的出现在较深层次（最少编码也是这个道理）
  • 网络结构
    • 模型学习方式同样可以是CBOW或者Skip-gram模式
    • Input layer：需要学习的词向量，多个词向量加和平均到映射层
    • Output layer：通过加和平均得到的向量，作为输入，通过
      Hierarchical Softmax进行分类训练
  • 训练过程:
    • 需要通过已经词表构造一颗霍夫曼树（通过频率的计算）
    • 通过$X_w$的输入，就能够通过霍夫曼树确定该输入对应到的叶子节点，同时也就知道了整个路径(类似101001…)
    • 每一个节点的选择都是通过sigmoid进行二分类
    • 最后是通过最大似然模型，梯度提升求解方法进行该路径概率的最大值求解（p(step1)*p(step2)…都是二分类模型）
      • 通过反向传播求梯度后，通过梯度提升，更改权重向量（节点与节点连线）；同时改变input layer词向量（因为$X_w$只是加权求平均）
  • 优点：
    • 舍去了隐藏层，在CBOW模型从输入层到隐藏层的计算改为直接从输入层将几个词的词向量求和平均作为输出
      • 词向量的线性相关性
        • 第一个改进在于去除了隐藏层，Word2vec训练词向量的网络结构严格上来说不算是神经网络的结构，也就去掉了非线性的激活函数，所以就能够表示词向量直接是线性相关的
    • 舍去了隐藏层到输出层的全连接结构，换成了霍夫曼树来代替隐藏层到输出层的映射
      • 不需要计算所有的非叶子结点，只需要计算找寻某个叶子结点时经过的路径上存在的节点，极大的减少了计算量
  • 缺点：
    比如霍夫曼树的结构是基于贪心的思想，这样训练频率很大的词很有效，但是对词频很低的词很不友好，路径很深（二分类比较多，训练的权重也就比较多）

word2vec-Negative Sampling

  • 网络结构
  • 训练网络图
  • 训练过程：
    • 输入：(V,w0)(V,w1)(V,w2)…
      • w0是想预测出来的那个正样本，w1，w2…是跟随随机选取的负样本
      • V是上下文，比如cbow方式就是前后单词的向量求和sum
    • 输出也是用的二分类的方法对正负样本进行概率判断
    • 也是采用的最大似然的方法，对各个正负样本进行概率相乘，使其概率值达最大
      • 通过梯度提升的方法，更新每个样本对应的$\theta$向量，以及输入的词向量
  • Negative Sampling选取负例词原理
    基本就是对词出现的频率进行划分，目的是概率性取到不同频率的负样本
  • 优点：
    Negative Sampling训练生僻词的词向量会更稳定更快些

word2vec整体优缺点

  • Word2vec训练出来的词向量效果挺好，其训练出来的词向量可以衡量不同词之间的相近程度
  • word2vec也存在缺点，因为在使用context（w）中并没有考虑w上下文的词序问题，这就造成了训练时输入层所有的词都是等价的，这样训练出来的词向量归根结底只包含大量语义，语法信息
    • 所以一般想拥有比较好的词向量，还是应该在一个有目标导向的神经网络中训练，比如目标是情感分析，在这样的神经网络中去取得第一层embedding层作为词向量，其表达的的效果应该会比word2vec训练出来的效果好得多，当然一般我们可能不需要精准表达的词向量，所以用word2vec来训练出词向量，也是一种可选择的快速效率的方法

发表于 | 分类于 ，

参考文章：
王者对决：XLNet对比Bert
3分钟了解GPT Bert与XLNet的差异
张俊林-运行机制及和 Bert 的异同比较

自回归语言模型

  • 概念
    在 ELMO / BERT 出来之前，大家通常讲的语言模型其实是根据上文内容预测下一个可能跟随的单词，就是常说的自左向右的语言模型任务，或者反过来也行，就是根据下文预测前面的单词，这种类型的 LM 被称为自回归语言模型
    • ELMO本质上也是自回归LM
      • ELMO 尽管看上去利用了上文，也利用了下文，但是本质上仍然是自回归 LM ，这个跟模型具体怎么实现有关系。
      • ELMO 是做了两个方向 ( 从左到右以及从右到左两个方向的语言模型 ) ，但是是分别有两个方向的自回归 LM ，然后把 LSTM 的两个方向的隐节点状态拼接到一起，来体现双向语言模型这个事情的。所以其实是两个自回归语言模型的拼接，本质上仍然是自回归语言模型
  • 缺点
    自回归语言模型的问题在于它只能使用前向上下文或后向上下文，这意味着它不能同时使用前向和后向上下文，从而限制其对上下文和预测的理解。
    • 当然，貌似 ELMO 这种双向都做，然后拼接看上去能够解决这个问题，因为融合模式过于简单，所以效果其实并不是太好

自编码语言模型

与AR语言模型不同，BERT使用自动编码器(AE)语言模型。AE语言模型旨在从损坏的输入重建原始数据。
在BERT中，通过添加[MASK]来破坏预训练输入数据。例如，’Goa has the most beautiful beaches in India’将成为‘Goa has the most beautiful [MASK] in India’，该模型的目标是根据上下文词预测[MASK]词。自动编码器语言模型的优点是，它可以看到前向和后向的上下文。但是，由于在输入数据中添加[MASK]引入了微调模型的差异

bert的问题

  • [MASK]标记导致实际和预训练不一致
    训练BERT以预测用特殊[MASK]标记替换的标记。问题是在下游任务中微调BERT时，[MASK]标记永远不会出现。在大多数情况下，BERT只是将非掩码标记复制到输出中。
  • 预测的标记彼此独立
    Bert 在第一个预训练阶段，假设句子中多个单词被 Mask 掉，这些被 Mask 掉的单词之间没有任何关系，是条件独立的，而有时候这些单词之间是有关系的，XLNet 则考虑了这种关系
    • 例如：
      Whenever she goes to the [MASK] [MASK] she buys a lot of [MASK]
      三个[MASK]是并行训练，它们三个直接的关系bert是没有考虑的

XLNet

  • 背景：
    能不能结合自编码(bert)从左向右学习，和自回归模型(elmo)能够同时学习上下文，也能够避免bert的缺陷呢？
  • 排列语言建模思想：
    看上去仍然是个自回归的从左到右的语言模型，但是其实通过对句子中单词排列组合，把一部分 Ti 下文的单词排到 Ti 的上文位置中，于是，就看到了上文和下文，但是形式上看上去仍然是从左到右在预测后一个单词
    • 这样从左往右也能看见原始Ti的上下文了

发表于 | 分类于 ，

参考：
CF,FM,WDL,DeePFM算法对比总结
CTR模型演进

xDeepFM

  • 背景
    • 由上面的DCN网络可以看出：时间cross网络的每一层是上一层的乘以一个标量得到，并没有做到vector-wise的特征多阶交叉
    • 特征交叉还是以deep部分的bit-wise的方式构建的

CIN网络(Compressed Interaction Network)

能够做到vector-wise基本的多阶特征交叉(outer product & 多阶：RNN网络思想)，同时还能够进行维度控制(CNN网络中的池化思想)

  • 概览

  • 步骤1：

    • 输入是所有field的embedding向量构成的矩阵$x^0 \in R^{m*D}$
      • 该矩阵的第i行对应第个field的embedding向量，假设共有i个field，每个field的embedding向量的维度为D
    • 输出：第k层的输出也是一个矩阵，记为$x^k \in R^{H_k*D}$
      • 该矩阵的行数为$H_k$，表示第k层共有$H_k$个特征（embedding）向量，其中$H_0=m$，其他层不一定和m相等
      • 第k层的输出$x^k$由第k-1层的输出$x^{k-1}$和$x_0$经过复杂（outer product）计算得到,具体的，矩阵$x^k$中的第h行的计算公式：
        • 其中，0表示哈达玛积，即两个矩阵或向量对应元素相乘得到相同大小的矩阵或向量

  • 步骤二：
    将步骤一种的多维m$H_k$D采用池化方法压缩成$H_k$*m维度向量，避免维度灾难

    • $z^{k+1}$可以被看作是一个宽度为m、高度为$H_k$、通道数为 D 的图像，在这个虚拟的图像上施加一些卷积操作即得到$x^{k+1}$。$w^{k,h}$是其中一个卷积核，总共有$H_{k+1}$个不同的卷积核

  • 步骤三：
    $H_k$个feature再通过sum pooling，进行cat操作，连接得到不同交叉特征作为CIN的输出，这里也进行的降维

  • CIN宏观

    CIN的宏观框架如下图所示，它的特点是，最终学习出的特征交互的阶数是由网络的层数决定的，每一层隐层都通过一个池化操作连接到输出层，从而保证了输出单元可以见到不同阶数的特征交互模式。同时不难看出，CIN的结构与循环神经网络RNN是很类似的，即每一层的状态是由前一层隐层的值与一个额外的输入数据计算所得

    • 不同的是，CIN中不同层的参数是不一样的，而在RNN中是相同的；RNN中每次额外的输入数据是不一样的，而CIN中额外的输入数据是固定的，始终是$x_0$

xDeepFM模型整体

借鉴Wide&Deep和DeepFM等模型的设计，将CIN与线性回归单元、全连接神经网络单元组合在一起，得到最终的模型并命名为极深因子分解机xDeepFM

  • 特点:
    既有线下模型的记忆能力，也集成了多维特征的显示交叉，同时也兼顾了DNN网络隐式特征交叉和泛华能力，在CIN网络也采用池化计算进行降维，有效的避免了维度爆炸的情况
    • CIN：集成显示的高阶特征交叉
    • DNN：集成隐式的高阶特征交叉，并兼顾泛华能力
    • 线下模型：集成线下模型有助于记忆功能

发表于 | 分类于 ，

相关文章

CTR数据特点

  • 图像中会有大量的像素与周围的像素比较类似；文本数据中语言会受到语法规则的限制。CNN对于空间特征有很好的学习能力，正如RNN对于时序特征有强大的表示能力一样
  • 在Web-scale的搜索、推荐和广告系统中，特征数据具有高维、稀疏、多类别的特点，一般情况下缺少类图像、语音、文本领域的时空关联性

深度CTR、CVR预估模型发展演化的三条主线

  • 1.第一条主脉络是以FM家族为代表的深度模型，它们的共同特点是自动学习从原始特征交叉组合新的高阶特征。
  • 2.第二条主脉络是一类使用attention机制处理时序特征的深度模型，以DIN、DIEN等模型为代表
    • attention机制是不是可以在某种程度上理解为一种特殊形式的组合特征，和第一条主线雷同
  • 3.第三条主脉络是以迁移学习、多任务学习为基础的联合训练模型或pre-train机制，以ESMM
    • 属于流程或框架层面的创建

FM家族的交叉特征组合

背景

交叉组合原始特征构成新的特征是一种常用且有效的特征构建方法。哪些特征需要被交叉组合以便生成新的有效特征？需要多少阶的交叉组合？这些问题在深度学习流行之前需要算法工程师依靠经验来解决。人工构建组合特征特别耗时耗力，在样本数据生成的速度和数量巨大的互联网时代，依靠人的经验和技能识别出所有潜在有效的特征组合模式几乎是不可能的。一些有效的组合特征甚至没有在样本数据中出现过。

GBDT+LR

  • 特点：将特征工程和目标拟合分为两个模型，能够组合些高阶的特征，但是比较麻烦

FM

  • 特点：
    • 模型是第一个从原始特征出发，端到端学习的例子
    • FM提出了一种很好的自动学习交叉组合特征的思路，随后融入FM模型思路的深度学习模型便如雨后春笋般应运而生，典型的代表有FNN、PNN、DeepFM、DCN、xDeepFM等
  • 问题：
    • FM毕竟还是一个浅层模型，经典的FM模型只能做二阶的特征交叉，模型学习复杂组合特征的能力偏弱

FNN

  • 背景：
    FNN模型最先提出了一种增强FM模型的思路，就是用FM模型学习到的隐向量初始化深度神经网络模型（MLP），再由MLP完成最终学习
  • 特点:
    • MLP（plain-DNN）因其特殊的结构天然就具有学习高阶特征组合的能力，它可以在一定的条件下以任意精度逼近任意函数
    • 可以看出plain-DNN的高阶特征交互建模是元素级的（bit-wise），也就是说同一个域对应的embedding向量中的元素也会相互影响
  • 不足：
    • plain-DNN以一种隐式的方式建模特征之间的交互关系，我们无法确定它学习到了多少阶的交叉关系
    • 虽然两种建模交叉特征的方式(bit-wise和vectiro-wise)有一些区别，但两者并不是相互排斥的，如果能把两者集合起来，便会相得益彰

PNN

  • 背景：
    PNN模型最先提出了一种融合bit-wise和vector-wise交叉特征的方法，其通过在网络的embedding层与全连接层之间加了一层Product Layer来完成特征组合
  • 不足：
    舍弃了低阶特征：PNN与FM相比，舍弃了低阶特征，也就是线性的部分，这在一定程度上使得模型不太容易记住一些数据中的规律

WDL

  • 特点：WDL（Wide & Deep Learning）模型混合了宽度模型与深度模型，其宽度部分保留了低价特征，偏重记忆；深度部分引入了bit-wise的特征交叉能力
  • 不足：
    宽度部分的输入依旧依赖于大量的人工特征工程
    • 能不能在融合bit-wise和vector-wise交叉特征的基础上，同时还能保留低阶特征(linear part)呢？

DeepFm

  • 背景：
    能不能在融合bit-wise和vector-wise交叉特征的基础上，同时还能保留低阶特征(linear part)呢（优化WDL问题）
  • 特点：
    • DeepFM模型融合了FM和WDL模型，其FM部分实现了低阶特征和vector-wise的二阶交叉特征建模，其Deep部分使模型具有了bit-wise的高阶交叉特征建模的能力
  • 不足：
    FM、DeepFM和Inner-PNN都是通过原始特征隐向量的内积来构建vector-wise的二阶交叉特征，有下面问题：
    • 必须要穷举出所有的特征对，即任意两个field之间都会形成特征组合关系，而过多的组合关系可能会引入无效的交叉特征，给模型引入过多的噪音，从而导致性能下降
    • 二阶交叉特征有时候是不够的，好的特征可能需要更高阶的组合。虽然DNN部分可以部分弥补这个不足，但bit-wise的交叉关系是晦涩难懂、不确定并且不容易学习的
    • 所以：有没有可能引入更高阶的vector-wise的交叉特征，同时又能控制模型的复杂度，避免产生过多的无效交叉特征呢

DCN

DCN模型以一个嵌入和堆叠层(embedding and stacking layer)开始，接着并列连一个cross network和一个deep network，接着通过一个combination layer将两个network的输出进行组合。交叉网络（cross network）的核心思想是以有效的方式应用显式特征交叉

  • 不足： 因此Cross Network的输出就相当于不断乘以一个数，当然这个数是和$x_0$高度相关的
    • CrossNet的输出被限定在一种特殊的形式上
    • 特征交叉还是以bit-wise的方式构建的

xDeepFM

  • 背景
    • 由上面的DCN网络可以看出：时间cross网络的每一层是上一层的乘以一个标量得到，并没有做到vector-wise的特征多阶交叉
    • 特征交叉还是以deep部分的bit-wise的方式构建的
  • 特点
    既有线下模型的记忆能力，也集成了多维特征的显示交叉，同时也兼顾了DNN网络隐式特征交叉和泛华能力，在CIN网络也采用池化计算进行降维，有效的避免了维度爆炸的情况
    • CIN：集成显示的高阶特征交叉
    • DNN：集成隐式的高阶特征交叉，并兼顾泛华能力
    • 线下模型：集成线下模型有助于记忆功能

总结

特征交叉组合作为一种常用的特征工程方法，可以有效地提升模型的效果。特征交叉组合从人工方式开始，经历了模型辅助的阶段，最后发展到各种端到端模型的阶段。端到端模型从建模二阶交叉关系向构建高阶交叉关系的方向发展，同时建模方式也从bit-wise向vector-wise发展。

  • 本文总结了FM家族的一系列深度学习模型，这些模型有一个共同的强制要求：所有field的embedding向量的维数是相同的。这个要求是合理的吗？我们知道不同的field对应的值空间大小是不一样的，比如淘宝商品ID的量级在十亿级，类目的量级在万级，用户年龄段的量级在十级，在如此巨大的差异的情况下，embedding向量的维数只能取得尽可能的大，这大大增加了模型的参数量级和网络的收敛时间。所以作者认为本文提及的FM家族模型有两个主要缺点：
    • 强制要求所有field的embedding向量的维数，增加了网络复杂度；
    • 对连续值特征不友好

发表于 | 分类于 ，

CVR预估的新思路：完整空间多任务模型

背景

传统CVR预估模型有样本选择偏差（sample selection bias）和训练数据过于稀疏（data sparsity ）的问题

  • 以电子商务平台为例，用户在观察到系统展现的推荐商品列表后，可能会点击自己感兴趣的商品，进而产生购买行为。换句话说，用户行为遵循一定的顺序决策模式：impression → click → conversion：即p(CVR) = p(conversion|click,impression)

样本选择偏差

  • 对应图中的阴影区域，传统的CVR模型就是用此集合中的样本来训练的，同时训练好的模型又需要在整个样本空间做预测推断。由于点击事件相对于展现事件来说要少很多，只是全局的一个很小的子集。
    • 违背了机器学习算法之所以有效的前提：独立同分布
    • 样本选择偏差会伤害学到的模型的泛化性能

数据过于稀疏

  • 对应图中的阴影区域，传统的CVR模型就是用此集合中的样本来训练的，数据量太少

ESMM模型

概念

  • CTCVR
    • x是高维稀疏多域的特征向量，y和z的取值为0或1，分别表示是否点击和是否购买
    • CVR模型的目标是预估条件概率pCVR ，与其相关的两个概率为点击率pCTR 和点击且转换率 pCTCVR ，它们之间的关系如下：

模型架构

  • 在整个样本空间建模，而不像传统CVR预估模型那样只在点击样本空间建模
  • 共享特征表示
    由于CTR任务的训练样本量要大大超过CVR任务的训练样本量，ESMM模型中特征表示共享的机制能够使得CVR子任务也能够从只有展现没有点击的样本中学习，从而能够极大地有利于缓解训练数据稀疏性问题
  • 损失函数由两部分组成
    • 其中，$\theta _{ctr}$ 和$\theta _{cvr}$分别是CTR网络和CVR网络的参数，l(.)是交叉熵损失函数。在CTR任务中，有点击行为的展现事件构成的样本标记为正样本，没有点击行为发生的展现事件标记为负样本；在CTCVR任务中，同时有点击和购买行为的展现事件标记为正样本，否则标记为负样本

总结

  • ESMM模型是一个新颖的CVR预估方法，其首创了利用用户行为序列数据在完整样本空间建模，避免了传统CVR模型经常遭遇的样本选择偏差和训练数据稀疏的问题，取得了显著的效果
  • ESMM模型的贡献在于其提出的利用学习CTR和CTCVR的辅助任务，迂回地学习CVR的思路。ESMM模型中的BASE子网络可以替换为任意的学习模型，因此ESMM的框架可以非常容易地和其他学习模型集成，从而吸收其他学习模型的优势，进一步提升学习效果，想象空间巨大

发表于 | 分类于 ，

fastText原理及实践-我爱自然语言处理
fastText原理-csdn

softmax回归

  • Softmax回归（Softmax Regression）又被称作多项逻辑回归（multinomial logistic regression），它是逻辑回归在处理多类别任务上的推广
    • 代价函数上推导出它们的一致性
  • softmax函数常在神经网络输出层充当激活函数，目的就是将输出层的值归一化到0-1区间，将神经元输出构造成概率分布，主要就是起到将神经元输出值进行归一化的作用

FastText特点:分层softmax

  • 背景：标准的Softmax回归中，要计算y=j时的Softmax概率，我们需要对所有的K个概率做归一化，这在|y|很大时非常耗时。于是，分层Softmax诞生了，它的基本思想是使用树的层级结构替代扁平化的标准Softmax。这样大大节省了时间空间
  • 霍夫曼树理解
    • 给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为霍夫曼树
  • 构造霍夫曼树方法：根据类标的频数构造的霍夫曼树
    • 表示出现最频繁的类，路径最短
  • 使用：当我们知道了目标类别(或者单词)x，之后，我们只需要计算root节点，到该词的路径累乘，即可. 不需要去遍历所有的节点信息，时间复杂度变为O(log2(V))
  • 单词预测举例

FastText特点:n-gram特征

  • 在文本特征提取中，常常能看到n-gram的身影。它是一种基于语言模型的算法，基本思想是将文本内容按照字节顺序进行大小为N的滑动窗口操作，最终形成长度为N的字节片段序列
    • 分字粒度和词粒度
  • n-gram产生的特征只是作为文本特征的候选集，你后面可能会采用信息熵、卡方统计、IDF等文本特征选择方式筛选出比较重要特征
  • 优势：
    • 对于低频词生成的词向量效果会更好。因为它们的n-gram可以和其它词共享。
    • 对于训练词库之外的单词，仍然可以构建它们的词向量。我们可以叠加它们的字符级n-gram向量。

word2vec:cbow

  • 背景:word2vec主要有两种模型：skip-gram 模型和CBOW模型,CBOW模型架构和fastText模型非常相似
  • CBOW:
    • CBOW模型的基本思路是：用上下文预测目标词汇
    • 架构图如下所示：
    • 神经网络模型：
      重点就是学习输入层到隐藏层，隐藏层到输出层的权重矩阵
      • 输入层：输入层由目标词汇y的上下文单词{${x_1,x_2…x_c}$}组成，$x_i$是被onehot编码过的V维向量，其中V是词汇量
      • 隐含层：隐含层是N维向量h
      • 输出层：输出层是被onehot编码过的目标词y
        因为词库V往往非常大，使用标准的softmax计算相当耗时，于是CBOW的输出层采用的正是上文提到过的分层Softmax

FastText

  • 使用fastText进行文本分类的同时也会产生词的embedding，即embedding是fastText分类的产物。除非你决定使用预训练的embedding来训练fastText分类模型

对word2vec的改进

  • 背景：
    word2vec把语料库中的每个单词当成原子的，它会为每个单词生成一个向量。这忽略了单词内部的形态特征，比如：“apple” 和“apples”，“达观数据”和“达观”，这两个例子中，两个单词都有较多公共字符，即它们的内部形态类似，但是在传统的word2vec中，这种单词内部形态信息因为它们被转换成不同的id丢失了
  • fasttext方法不同与word2vec方法，引入了两类特征并进行embedding。其中n-gram颗粒度是词与词之间，n-char是单个词之间
    • n-char:
      对于单词“apple”，假设n的取值为3，则它的trigram有:
      “<ap”, “app”, “ppl”, “ple”, “le>”
      其中，<表示前缀，>表示后缀。于是，我们可以用这些trigram来表示“apple”这个单词，进一步
    • 我们可以用这5个trigram的向量叠加来表示“apple”的词向量

模型架构

  • 不同点1：输入
    • CBOW的输入是目标单词的上下文，fastText的输入是多个单词及其n-gram或者n-char特征，这些特征用来表示单个文档
    • CBOW的输入单词被onehot编码过，fastText的输入特征是被embedding过
  • 不同点2：输出
    • CBOW的输出是目标词汇，fastText的输出是文档对应的类标
    • fastText采用了分层Softmax，大大降低了模型训练时间

核心思想：

  • 仔细观察模型的后半部分，即从隐含层输出到输出层输出，会发现它就是一个softmax线性多类别分类器，分类器的输入是一个用来表征当前文档的向量；模型的前半部分，即从输入层输入到隐含层输出部分，主要在做一件事情：生成用来表征文档的向量。那么它是如何做的呢？叠加构成这篇文档的所有词及n-gram的词向量，然后取平均。叠加词向量背后的思想就是传统的词袋法，即将文档看成一个由词构成的集合
    • 将整篇文档的词及n-gram向量叠加平均得到文档向量，然后使用文档向量做softmax多分类
      - 这中间涉及到两个技巧：字符级n-gram特征的引入以及分层Softmax分类

发表于 | 分类于 ，

聚类总结

模块度

社区划分的标准–模块度
社区划分的标准–模块度2

  • 概念
    模块度（Modularity）用来衡量一个社区的划分是不是相对比较好的结果。一个相对好的结果在社区内部的节点相似度较高，而在社区外部节点的相似度较低
  • 定义
    社区内部的总边数和网络中总边数的比例减去一个期望值，该期望值是将网络设定为随机网络时同样的社区分配所形成的社区内部的总边数和网络中总边数的比例的大小
    • 公式一:
    • $k_v*k_w$,及随机网络的理解，可以参考
    • 公式二:
    • 举例：
      • 第一项是三项合在一起

Louvain算法

参考文章

  • Louvain算法是由底向上的层次聚类算法的一种，目的是优化提升模块度
  • 步骤
    • 1.将图中的每个节点看成一个独立的社区，次数社区的数目与节点个数相同；
    • 2.对每个节点i，依次尝试把节点i分配到其每个邻居节点所在的社区，计算分配前与分配后的模块度变化ΔQ，并记录ΔQ最大的那个邻居节点，如果maxΔQ>0，则把节点i分配ΔQ最大的那个邻居节点所在的社区，否则保持不变；
    • 3.重复2），直到所有节点的所属社区不再变化；
    • 4.对图进行压缩，将所有在同一个社区的节点压缩成一个新节点，社区内节点之间的边的权重转化为新节点的环的权重，社区间的边权重转化为新节点间的边权重；
    • 5.重复1）直到整个图的模块度不再发生变化

发表于 | 分类于 ，

LightGBM优缺点比较

直方图

直方图优化算法深入理解

  • 和xgboost的pre-order比较
    xgboost 采用了预排序的方法来处理节点分裂，这样计算的分裂点比较精确。但是，时间空间上都造成了很大的时间开销(但这个也是当时相比GBDT的重要提升点)。为了解决这个问题，Lightgbm 选择了基于 histogram 的决策树算法。相比于 pre-sorted算法，histogram 在内存消耗和计算代价上都有不少优势
  • LightGBM和最近的FastBDT都采取了提前histogram binning再在bin好的数据上面进行搜索。并在pre-bin之后的histogram的求和用了一个非常巧妙的减法trick(histogram加速)，省了一半的时间

leaf-wise替代level-wise

在 histogram 算法之上， LightGBM 进行进一步的优化。首先它抛弃了大多数 GBDT 工具使用的按层生长
(level-wise) 的决策树生长策略，而使用了带有深度限制的按叶子生长 (leaf-wise) 算法

  • 在 histogram 算法之上， LightGBM 进行进一步的优化。首先它抛弃了大多数 GBDT 工具使用的按层生长(level-wise) 的决策树生长策略，而使用了带有深度限制的按叶子生长 (leaf-wise) 算法。 level-wise 过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，不容易过拟合。但实际上level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销。因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

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

  • Level wise方式：
    Level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂

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

Gradient-based One-Side Sampling(GOSS)

在机器学习当中，我们面对大数据量时候都会使用采样的方式（根据样本权值）来提高训练速度。又或者在训练的时候赋予样本权值来关于于某一类样本（如Adaboost）。LightGBM利用了GOSS来做采样算法。

    1. 选取前a%个较大梯度的值作为大梯度值的训练样本
    1. 从剩余的1 - a%个较小梯度的值中，我们随机选取其中的b%个作为小梯度值的训练样本
    1. 对于较小梯度的样本，也就是b% * #samples，我们在计算信息增益时将其放大(1 - a) / b倍

总的来说就是a% #samples + b% #samples个样本作为训练样本。 而这样的构造是为了尽可能保持与总的数据分布一致，并且保证小梯度值的样本得到训练。

Exclusive Feature Bundling(EFB)

EFB中文名叫独立特征合并，顾名思义它就是将若干个特征合并在一起。使用这个算法的原因是因为我们要解决数据稀疏的问题。在很多时候，数据通常都是几千万维的稀疏数据。因此我们对不同维度的数据合并一齐使得一个稀疏矩阵变成一个稠密矩阵

发表于 | 分类于 ，

XGBoost论文阅读及其原理
XGBoost很棒的原理解读
https://blog.csdn.net/guoxinian/article/details/79243307
https://blog.csdn.net/matrix_zzl/article/details/78635221#2-xgboost%E5%8E%9F%E7%90%86%E6%8E%A8%E5%AF%BC

boosting集成框架

  • boosting集成是后一个模型是对前一个模型产生误差信息进行矫正
  • gradient boost更具体，新模型的引入是为了减少上个模型的残差(residual)，我们可以在残差减少的梯度(Gradient)方向上建立一个新的模型
  • 框架算法：
    • 1.设定函数初始值F0，为一个恒值函数，论文中基于变量优化出恒值，实际上也可以给定任意值或者直接为0
    • 2.泛函优化
      根据参数MM，进行MM次迭代，不断将当前函数$F_{m−1}$往最优函数F∗空间上逼近，逼近方向就是当前函数下的函数负梯度方向-$\delta L(y,F)$,由于优化函数，而非变量，本质上属于泛函优化
    • 3.每次迭代计算出函数负梯度，基于训练数据构建模型来拟合负梯度。原则上可以选择任何模型：树模型，线性模型或者神经网络等等，很少框架支持神经网络，推测：神经网络容易过拟合，后续函数负梯度恒为0就无法继续迭代优化下去。如果用树模型进行拟合，就是我们熟悉的CART建树过程
  • 泛函优化与变量优化
  • 和bagging比较并行性
    谈到集成学习，不得不说bagging集成，比如随机森林
    • 1）建树前对样本随机抽样（行采样）
    • 2）每个特征分裂随机采样生成特征候选集（列采样）
    • 3）根据增益公式选取最优分裂特征和对应特征分裂值建树。
      • 建树过程完全独立，不像boosting训练中下一颗树需要依赖前一颗树训练构建完成，因此能够完全并行化。Python机器学习包sklearn中随机森林RF能完全并行训练
      • 而GBDT算法不行，训练过程还是单线程，无法利用多核导致速度慢。希望后续优化实现并行，Boosting并行不是同时构造N颗树，而是单颗树构建中遍历最优特征时的并行，类似XGBoost实现过程。随机森林中行采样与列采样有效抑制模型过拟合，XGBoost也支持这2种特性，此外其还支持Dropout抗过拟合。

XGboost改进(算法)-Loss方程

  • Loss进行泰勒二阶展开并且加入了惩罚项

    • 目标函数只依赖于每个数据点的在误差函数上的一阶导数和二阶导数

    • 目标函数通过二阶泰勒展开式做近似。传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。注：支持自定义代价函数，只要函数可一阶和二阶求导

      • 泰勒展开理解
        • 如何让两个人运动轨迹一样？
          就是让两个人的速度，加速度，加速度的加速度…都一致。那么翻译成数学语言，也就是两条曲线想要一样，那么在某一点的一阶导数，二阶导数，三阶导数，四阶导数….n阶导数也相同，就说这两条曲线是相同的。也就是泰勒展开式的核心思想

    • 定义了树的复杂度，即xgboost在代价函数里加入了正则项，用于控制模型的复杂度，正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。代替了剪枝。

  • obj fucntion的形式已经非常漂亮，是一个典型的二次函数。可是问题在于，loss是sample wise的，而正则项则关注tree structure，两者尚不能统一，仍然不能直接得到一个直观的结果
    • 我们希望的obj function的形式是易于计算的，所以下一步我们要将training loss从sample-wise转化成tree-structure-wise
    • $I_j$为所有对应到叶子节点j的样本的集合
      $I_j={i|q(x_i)=j}$
    • 我们就可以顺利地将样本group by叶子，实现统一obj function的关注目标
      • 它只关注tree structure相关信息，没有其他杂质
      • 它的形式依然是一个简单的二次函数的形式，其极值是直接可求得的，换句话说，对于每一棵树，其最佳参数可以在O(1)的时间内求出数值解。这使得XGBoost相对于传统GBDT的个求解速度大大提升
      • 简单求解一下这个二次函数的极值，我们有，在给定的tree structure下，最佳的参数取值$w_j$和loss:
        • 同样loss值只和样本的一阶和二阶梯度有关
        • 梯度就和具体的$h_{\theta}(x)$，以及具体的loss方程有关系了

XGboost改进-tree structure原理

  • 不同的决策树算法有不同的度量（information gain, gini, etc.），用来评价新划分对模型的loss有多少影响。
    因为XGBoost已经有了一个需要minimize的object function，XGBoost的score/gain的度量方式就可以简单选取新划分的loss和划分之前的loss的差值，如果新划分让loss变小，换言之，划分前的loss比划分后的loss大，那么就说明划分是有用的
  • 有了这个前提，才有下面的find best split
    • 现有的boosted tree基本基于贪心的思想，即“每次仅考虑对当前层次/树效果最好的结点作为分裂节点
      • 时间复杂度$o(m*n^2)$(m是特征数量，n是样本数量)
        • 相当于对每个特征，又需要两重的for循环，以每个样本的该特征的值作为分割点进行整体收益计算，比它大的放左边，比它小的放右边（因为没有排序，所以只能两重for循环，就是$o(n^2)$）

XGboost改进-特征树分割点选择(精确法)

  • XGBoost在单机默认是exact greedy，搜索所有的可能分割点。分布式是dynamic histogram
  • 精确算法由于需要遍历特征的所有取值，计算效率低，适合单机小数据，对于大数据、分布式场景并不适合
  • 时间复杂度$o(m*n^2)$(m是特征数量，n是样本数量),因为进行pre-sort
    • 相当于只需要消耗排序的时间$O(n*log(n))$
    • 排好序后直接将自己的左右的样本划分到左右子树就好

XGboost改进-特征树分割点选择(近似法)(Weighted Quantile Sketch)

(近似方法Approximate Algorithm)（分布式加权直方图算法）

  • 核心思想：分位数
    • 既然样本数量太大，我们可不可以按比例来选择，从n个样本中抽取k个样本来进行计算，取k个样本中的最优值作为split value，这样就大大减少了运算数量。这就是k分位点选取的思想，即quantile sketch
    • 要如何抽取k个样本？我们要均分的是loss，而不是单纯的对样本，而每个样本对loss的贡献可能是不一样的，按样本均分会导致loss分布不均匀，取到的分位点会有偏差
    • 近似方法采用的分桶原理正是这个：按照二阶梯度来进行rank
  • 对特征k,构造数据集$D_k=(x_{1k},h_1),(x_{2k},h_2),…(x_{nk},h_n)$(就不用pre-sort)
    • h是$x_{ik}$对损失函数的二阶梯度
  • rank 排序定义
    • 对某一个特征上，样本特征值小于z的二阶梯度除以所有的二阶梯度总和。其实就是对样本的二阶梯度进行累加求和
    • 就是代表特征k上，特征值小于z的样本的权重(二阶梯度)累积
  • 选择分割点$s_{k1},s_{k2}…s_{kl}$：相邻两个分割点的rank值不超过$\epsilon$
  • 直方图理解
  • 所以$\epsilon$越小，那么桶个数$\frac{1}{\epsilon}$越多，越精细
  • 离散化两种方式(global&local)
    • glocal:是在建立第k棵树的时候利用样本的二阶梯度对样本进行离散化，每一维的特征都建立buckets。在建树的过程中，我们就重复利用这些buckets去做
      • m个buckets就相当于只有m个样本
    • local:每次进行分支时，我们都重新计算每个样本的二阶梯度并重新构建buckets，再进行分支判断
      • 显然局部选择的编码复杂度更高，但是实验当中效果极其的好，甚至与Exact Greedy Algorithm一样
  • 没有理解分桶后，按照每个同为节点，如何进行树的划分，而且每个特征都有不同的分桶

对缺失值的处理

  • 对于稀疏性的离散特征，在寻找split point的时候，不会对该特征为missing的样本进行遍历统计
    • 通过这个工程技巧来减少了为稀疏离散特征寻找split point的时间开销
  • 在逻辑实现上，为了保证完备性，会处理将缺失样本分配到左右子树节点两种方案，或者指定默认的分支，大大提升了效率

XGboost改进-并行化

支持并行化处理。xgboost的并行是在特征粒度上的，在训练之前，预先对特征进行了排序(pre-sort)，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行，即在不同的特征属性上采用多线程并行方式寻找最佳分割点。

XGboost改进（工程上）

  • 缓存
    结合工程上数据存储技巧：比如block概念等
    • 对于有大量数据或者说分布式系统来说，我们不可能将所有的数据都放进内存里面。因此我们都需要将其放在外存上或者分布式存储。但是这有一个问题，这样做每次都要从外存上读取数据到内存，这将会是十分耗时的操作。因此我们使用预读取（prefetching）将下一块将要读取的数据预先放进内存里面。其实就是多开一个线程，该线程与训练的线程独立并负责数据读取。此外，我还要考虑block的大小问题。如果我们设置最大的block来存储所有样本在k特征上的值和梯度的话，cache未必能一次性处理如此多的梯度做统计。如果我们设置过少block size，这样不能充分利用的多线程的优势，也就是训练线程已经训练完数据，但是prefetching thread还没把数据放入内存或者cache中
  • 对数据进行压缩存在外存
    • 一种是对数据进行压缩存于外存中，到内存中需要训练时再解压，这样来增加系统的吞吐率，尽管消耗了一些时间来做编码和解码但还是值得的
    • 多外存存储，其实本质上就是分布式存储。这样说有多个线程对分布式结构管理，吞吐率自然高

XGboost改进-其他

  • 自定义损失函数
  • 列抽样（特征子采样）（column subsampling）[传统GBDT没有]xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性
  • Shrinkage(缩减)
    • 相当于学习速率(xgboost中的eta)[传统GBDT也有]
    • 权值收缩也就是对叶子节点的权值乘上收缩因子，该收缩因子是人为设定的参数。其作用是为了给后面的迭代保留优化空间。大家想想假如一棵树把损失函数降得很低很低，那么后续的优化空间就少了，训练的样本和特征也就少了，最后也就overfitting
  • 传统GBDT以CART作为基分类器，xgboost还支持线性分类器

总结

  • Loss上的优化，引入泰勒二阶，对自定义loss方法比较好；精度也比较高（二阶梯度）；同时推导出来是二阶函数(极致只和一阶二阶梯度有关系)，计算上快很多O(1)负责度；同时加上了以树复杂度相关的正则项
  • 算法对树的分裂上面：精准分裂用了pre-sort技巧。近似分裂大大提高了效率
  • 工程上：比如缓存(block)的考虑，数据压缩存储，树内多特征分化并行等

发表于 | 分类于 ，

参考文章

MLR(混合逻辑回归)

MLR算法是alibaba在2012年提出并使用的广告点击率预估模型，2017年发表出来。MLR模型是对线性LR模型的推广，它利用分片线性方式对数据进行拟合。基本思路是采用分而治之的策略：如果分类空间本身是非线性的，则按照合适的方式把空间分为多个区域，每个区域里面可以用线性的方式进行拟合，最后MLR的输出就变为了多个子区域预测值的加权平均。如下图(C)所示，就是使用4个分片的MLR模型学到的结果

  • MLR模型在大规模稀疏数据上探索和实现了非线性拟合能力，在分片数足够多时，有较强的非线性能力；
  • 同时模型复杂度可控，有较好泛化能力；同时保留了LR模型的自动特征选择能力。

MLR模型的思路非常简单，难点和挑战在于MLR模型的目标函数是非凸非光滑的，使得传统的梯度下降算法并不适用

  • 上式即为MLR的目标函数，其中m为分片数（当m=1时，MLR退化为LR模型）
  • $\pi _i(x,\mu)$是聚类参数，决定分片空间的划分，即某个样本属于某个特定分片的概率
    • softmax也是这样做分类
  • $\eta _i(x,w)$是分类参数，决定分片空间内的预测

  • $\mu$和w都是待学习的参数。最终模型的预测值为所有分片对应的子模型的预测值的期望

  • 神经网络思路
    另一方面，MLR模型可以看作带有一个隐层的神经网络。如下图，是大规模的稀疏输入数据，MLR模型第一步是做了一个Embedding操作，分为两个部分，一种叫聚类Embedding（绿色），另一种是分类Embedding（红色）。两个投影都投到低维的空间，维度为，是MLR模型中的分片数。完成投影之后，通过很简单的内积（Inner Product）操作便可以进行预测，得到输出

FNN (Factorization-machine supported Neural Network)

  • 思路类似于LR+GBDT,两个阶段：
    • 第一个阶段先用一个模型做特征工程
      除了神经网络模型，FM模型也可以用来学习到特征的隐向量（embedding表示），因此一个自然的想法就是先用FM模型学习到特征的embedding表示
    • 第二个阶段用第一个阶段学习到新特征训练最终的模型

PNN（Product-based Neural Networks）

  • 背景
    MLP中的节点add操作可能不能有效探索到不同类别数据之间的交互关系，虽然MLP理论上可以以任意精度逼近任意函数，但越泛化的表达，拟合到具体数据的特定模式越不容易
  • PNN主要是在深度学习网络中增加了一个inner/outer product layer，用来建模特征之间的关系
  • Product Layer的节点分为两部分，一部分是z向量，另一部分是p向量。z向量的维数与输入层的Field个数（N）相同，$z=(f_1,f_2,…f_N)$。p向量的每个元素的值由embedding层的feature向量两两成对并经过Product操作之后生成,$p={g(f_i,f_j)}$i=1…N,j=1…N，因此p向量的维度为N*(N-1)
  • Product操作有两种：内积和外积；对应的网络结构分别为IPNN和OPNN

总结

  • 主流的CTR预估模型已经从传统的宽度模型向深度模型转变，与之相应的人工特征工程的工作量也逐渐减少
  • 上文提到的深度学习模型，除了DIN对输入数据的处理比较特殊之外，其他几个模型还是比较类似的，它们之间的区别主要在于网络结构的不同
  • 这四种深度学习模型的比较见下表
  • 综上，深度学习技术主要有三点优势
    • 个人觉得在是否都能包含高低维特征，特征是否需要工程化上面很重要,并且也在向这个方向发展
    • 模型设计组件化
      组件化是指在构建模型时，可以更多的关注idea和motivation本身，在真正数学化实现时可以像搭积木一样进行网络结构的设计和搭建。
    • 深度学习可以帮助我们实现设计与优化的解耦，将设计和优化分阶段进行
      • 对于工业界的同学来说，可以更加关注从问题本身出发，抽象和拟合领域知识。然后用一些标准的优化方法和框架来进行求解