集成学习常用方法与DSTC7实战

2019 年 1 月 4 日 微信AI

前言

集成学习(ensemble learning)是学术竞赛中经常用到的多模型融合技术。无论是在图像分类、视频理解或是自然语言理解领域，它都能通过集成已有多个基础模型，带来一定的性能提升；因此获得了非常广泛的应用。本文将介绍四种类型的集成学习方法，包括bagging、boosting、stacking和blending。然后，结合DSTC7 track1 challenge任务，构建适用于句子选择(sentence selection)场景下的集成学习模型。

Bagging

Bagging的思想是随机地从训练集合中采样出多个子集合(sub-dataset)，然后针对每一个子集合，训练相应的基础模型。最终，通过投票或者平均的方法将这些基础模型进行输出结果的融合。

图1.Bagging流程图

Boosting

GBDT是最常用的boosting工具。它是基于梯度下降方法(Gradient Descend Method)推演出的集成模型；通过对目标函数进行一阶泰勒展开，迭代寻找最优模型的过程变成了寻找一个合适的来使得损失最小化；的设置如下图所示时，能够保证迭代后损失下降。
而近些年比较火的XGBoost是通过牛顿方法(Newton’s Method)进行最优的寻找。通过牛顿方法，可以将损失函数展开为下方的表达式。通过求解第二、第三项的和值，获得的零点就是最优的。

整个XGBoost的算法流程如下：

XGBoost输出加权了多棵树的输出；具体到每棵树的实现上，它将样本x映射到叶子节点的索引，并根据此索引从叶子节点分布中获取分数。
在损失函数中引入了正则化项，用于惩罚所有树上的叶子节点数以及叶子节点分布的L2范数。
近似优化目标函数。在第t轮迭代中，；通过贪心策略需要去优化的第t轮目标函数为：

通过牛顿方法展开目标函数，并进行函数项合并后，可以获得如下表达式：
最优的权重与数值可通过最小化目标函数获得。其中标红部分称为打分函数(scoring function)。
要使得损失函数的数值最小化，就需要寻找使打分函数最小的树结构。由于树的结构无穷无尽，在进行左右子树划分(Splitting）的过程中，需要遵循下方的增益值(Gain)表达式来选择树结构:
树的划分寻找算法，包含暴力搜索法与百分率搜索法。两个算法如下所示。

下图给出了一个进行暴力搜索的例子。通过排序、遍历的方式来获得最优的划分点；最终获得的树结构见右侧。

图2.

LightGBM作为最新的boosting工具包，它在训练速度与内存使用上都有了明显的优化。其与XGBoost的对比如下。

Stacking

首先将整个训练数据划分为K折。通过K-1折训练，1折测试的方式获得K个模型。最终合并所有模型的输出结果进行集成模型学习，用此模型在测试集合上进行最终的预测。这个方法的缺点是需要训练的模型数目与折数成正比。在数据量很大的比赛中，往往需要花费很多的时间与机器资源。

Blending

整个训练过程分为两个步骤。第一步，将全部数据划分为训练集合与验证数据集合，然后用前者训练多种基础模型。第二步，用已有的基础模型，在验证集合上进行预测输出，再利用监督方法基于多种输出结果进行集成模型的学习。

实战：DSTC7 track1 challenge

DSTC是对话系统领域比较重要的一个赛事。从2013年至今，一共举办了7届比赛。本次比赛中的track1是进行句子选择(sentence selection)：在给定一个问题时，从100个候选中找到最优的一个回答。主办方提供的数据集合包含了两个部分：外部知识库以及带有上下文的对话数据。整个训练集合大约有几十万条，开发集合为500条。

通过尝试不同的训练集合划分、网络结构变形以及损失的变化，一共训练出了200多个基础模型。我们采用了Blending+Hard sampling+XGBoost的策略进行模型的融合。

集成方法

对于所有M个基础模型，在切分的开发子集合上预测输出分数。
将100选1的多分类问题假设为独立的二分类问题，因此原始的每个样本会形成100个新的样本x(只有目标类别的label=1，其他类别的label=0)。每个x是一个特征维度是M的样本。
将所有样本x根据M维特征的平均值进行排序，剔除不在[0.001,0.95]范围之内的样本；这么做的目的是让模型在融合时能够更加专注在“难”样本上。
采用XGBoost在难样本数据上进行模型学习。通过调节树深度、树数目以及优化目标获得最优的融合模型。
在测试时，对所有候选回答进行打分和排序，采用分数最高的回答作为最终输出。

图5.

结果对比

下方给出了ensemble模型与最优单模型的性能对比，采用Recall@10与MRR作为评测指标。在此次比赛中，ensemble策略在所有任务上都带来了性能的提升。

总结

本文介绍了常用的集成学习方法，包括Bagging、Boosting、Stacking和Blending。然后详细分析的XGBoost的基本原理。最后结合在DSTC7比赛中的经历，给出了在句子选择任务上采用的集成学习方法。与此比赛相关的文章《End-to-end Gated Self-attentive Memory Network for Dialog ResponseSelection》已经投稿到AAAI-2018 workshop上。

参考文献：

[1] Tianqi Chen and Carlos Guestrin.XGBoost: A Scalable Tree Boosting System. In 22nd SIGKDD Conference onKnowledge Discovery and Data Mining, 2016.

[2] Guolin Ke, Qi Meng, Thomas Finley,Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, Tie-Yan Liu. "LightGBM: AHighly Efficient Gradient Boosting Decision Tree". Advances in NeuralInformation Processing Systems 30 (NIPS 2017), pp. 3149-3157.