标签： adaboost

adaboost

使用机器学习方法解决问题时，有较多模型可供选择。 一般的思路是先根据数据的特点，快速尝试某种模型，选定某种模型后， 再进行模型参数的选择（当然时间允许的话，可以对模型和参数进行双向选择）
因为不同的模型具有不同的特点， 所以有时也会将多个模型进行组合，以发挥‘三个臭皮匠顶一个诸葛亮的作用’， 这样的思路， 反应在模型中，主要有两种思路： Bagging和Boosting
Bagging
Bagging 可以看成是一种圆桌会议， 或是投票选举的形式，其中的思想是：‘群众的眼光是雪亮的’，可以训练多个模型，之后将这些模型进行加权组合，一般这类方法的效果，都会好于单个模型的效果。 在实践中， 在特征一定的情况下，大家总是使用Bagging的思想去提升效果。 例如kaggle上的问题解决，因为大家获得的数据都是一样的，特别是有些数据已经过预处理。
以下为Data Mining Concepts and Techniques 2nd 中的伪代码
基本的思路比较简单，就是：训练时，使用replacement的sampling方法， sampling一部分训练数据k次并训练k个模型；预测时，使用k个模型，如果为分类，则让k个模型均进行分类并选择出现次数最多的类(每个类出现的次数占比可以视为置信度)；如为回归，则为各类器返回的结果的平均值。
在该处，Bagging算法可以认为每个分类器的权重都一样。
Boosting
在Bagging方法中，我们假设每个训练样本的权重都是一致的； 而Boosting算法则更加关注错分的样本，越是容易错分的样本，约要花更多精力去关注。对应到数据中，就是该数据对模型的权重越大，后续的模型就越要拼命将这些经常分错的样本分正确。 最后训练出来的模型也有不同权重，所以boosting更像是会整，级别高，权威的医师的话语权就重些。
以下为Data Mining Concepts and Techniques 2nd 中adaboost伪代码：
训练时：先初始化每个训练样本的权重相等为1/d  d为样本数量； 之后每次使用一部分训练样本去训练弱分类器，且只保留错误率小于0.5的弱分类器，对于分对的训练样本，将其权重 调整为 error(Mi)/(1-error(Mi)) ，其中error(Mi)为第i个弱分类器的错误率（降低正确分类的样本的权重，相当于增加分错样本的权重）；
与测试：每个弱分类器均给出自己的预测结果，且弱分类器的权重为log(1-error(Mi))/error(Mi) ) 权重最高的类别，即为最终预测结果。
在adaboost中，  弱分类器的个数的设计可以有多种方式，例如最简单的就是使用一维特征的树作为弱分类器。
adaboost在一定弱分类器数量控制下，速度较快，且效果还不错。
我们在实际应用中使用adaboost对输入关键词和推荐候选关键词进行相关性判断。随着新的模型方法的出现， adaboost效果已经稍显逊色，我们在同一数据集下，实验了GBDT和adaboost，在保证召回基本不变的情况下，简单调参后的Random Forest准确率居然比adaboost高5个点以上，效果令人吃惊。。。。
Bagging和Boosting都可以视为比较传统的集成学习思路。 现在常用的Random Forest，GBDT，GBRank其实都是更加精细化，效果更好的方法。 后续会有更加详细的内容专门介绍。
参考内容：
Data Mining Concepts and Techniques 2nd
Soft Margin for Adaboost
也可关注我的微博： weibo.com/dustinsea
或是直接访问： http://semocean.com

分类模型在关键词推荐系统中的应用

以下内容均基于百度关键词推荐系统进行讨论
本文内容主要集中在使用机器学习方法判断两个短文本的相关性为基础构建商业关键词推荐系统。 为方便读者理解， 会先介绍该技术的具体应用背景及场景。
广告主在百度或google上进行广告投放时， 需要选择关键词， 以向搜索引擎表述自己想要覆盖的有商业价值的网民搜索流量。 在选择关键词后， 还需要设定具体的关键词匹配模式， 以告诉搜索引擎选择的关键词以何种方式去匹配网民的搜索。 举个例子： 网民在百度上搜索 ‘鲜花快送’， 假设商家A是卖花的， 搞鲜花速递业务的， 则A可以在百度凤巢系统中选择‘鲜花快送’这个关键词，同时设定匹配模式为精确匹配(即网民搜索和A在凤巢系统中选择的关键词完全一致时才出A的广告， 更多细节参见：http://yingxiao.baidu.com/)， 假设B在凤巢中未选择‘鲜花快递’， 但选择了‘鲜花速递’， 假设B选择了广泛匹配（语义近似即匹配，具体参见http://yingxiao.baidu.com/）， 则B的广告也会被触发（具体是否会展现， 还和出价， 质量度等诸多因素有关）
此时会面临一个问题： 广告主在凤巢系统中选择关键词时， 仅凭自己去想， 很难完全想到所有符合自己需求的关键词（网民的搜索query千奇百怪）， 故需要提供工具， 帮助凤巢客户快速找到和自己推广意图一致或相近的关键词，即： 关键词推荐工具。
从交互上来看，可以将关键词工具看成一个搜索引擎，凤巢客户输入一个种子词(种子query)，返回一个和种子query意图相近的推荐词list。
当然作为推荐系统， 其中还会包括属性披露， 推荐理由， 关键词行业分类， 关键词自动分组等支持， 这些内容会在接下来的其他博文进行介绍。
整个推荐流程大致如下
整个推荐流程， 大致分为5步：
  1. 基础日志，数据清洗即预处理
  2. 候选词触发： 根据输入种子query触发得到系统性能支持的最大关键词候选（供后续流程进行筛选过滤及排序），当然为保证性能， 该过程中会保留触发关键词的各种基础属性，例如PV， 行业， 主题等； 一般业界的检索，推荐系统会有较多触发逻辑逻辑，故触发出的关键词会比较多
  3. 相关性过滤：因为触发出的推荐关键词较多，故需要判断推荐关键词与种子query的相关性；既要保证召回，又需要保证准确性。
  4. ranking
  5. 使用业务，商业规则对最终结果进行排序调整及过滤（最经典的， 黄赌毒必须过滤删除）
对于相关性过滤，很早以前我们也是使用规则进行过滤，但随着规则数量的急剧增加，一方面导致系统架构性能下降，另外一方面也使系统策略越难约维护，故最终决定使用机器学习方法进行相关性过滤。
涉及到机器学习方法解决问题， 就会涉及到3方面的问题： 用哪些数据，准备哪些数据，如何处理数据？ 使用哪些特征？ 选用何种model ？
数据
一般来说，如果数据选择有问题， 那基本可以说后边无论再做多少努力， 这些努力都会付诸东流， 公司里这样的机器学习相关的项目也不少见： 几个人全情投入几个月或是1年多，效果总提不上去，回过头来发现数据就有问题，哭都没有眼泪。
所以一开始我们选择数据就比较慎重，还好关键词推荐工具隐性和显性反馈数据都还算比较丰富（推荐系统中都需要有这些信息， 将整个数据流形成完整的迭代闭环）： 我们可以认为用户输入一个query并选择了这个query返回的某个候选推荐词的pair，就是一个正例（即模型是判断是否相关，相关为正例，不相关为），而输入一个query后，用户将返回的某个词放入垃圾箱（关键词工具交互上支持该操作），则query及被放入垃圾箱的关键词组成的pair，即为负例。
获得数据后， 很快就发现一个问题： 客户操作得到的正例， 就是毫无疑问的正例；但用户的负反馈（用户使用种子query搜索得到返回结果后，被扔入垃圾箱的的case）很多时候并不一定和query不相关， 甚至是很相关，只是因为用户个性化的原因导致客户认为这个case 不适合自己。
比如： 一个客户主要卖各种花茶， 像菊花茶， 桂花茶等，但他不卖茉莉花茶，此时如果用户输入花茶， 从相关性来说， 推荐‘菊花茶’，‘茉莉花茶’， ‘桂花茶’其实都是OK的，但用户将‘茉莉花茶’放入垃圾箱，因为他不卖该产品。其实并不能说明花茶和茉莉花茶不相关。
为了消除因个性化带来的负例不准的情况，我们人工标注了1.5W非个性化的负例。 并进行随机sampling， 使正负例数量基本相当。
最终使用1/10数据作为测试样本，9/10作为训练样本。
特征
数据准备就绪后，下一步就是如何选择合适的特征了。 因为整个关键词推荐系统所能触发的关键词各式各样， 各种类型千奇百怪， 所以如果直接使用各种地位特征（例如字面，或是ID类）的话，会导致特征空间较大而数据比较稀疏，导致完成分类基本上变成不可能完成的任务； 所以我们不能直接使用字面， ID作为特征进行分类，而是要使用更加泛化，高维的特征。
在特征选择过程中，我们也充分贯彻了站在巨人的肩膀上远眺的方式，充分利用手头的资源，例如短串核心判断，同意变化扩展等基础工具进行特征设计。更详细的特征此处不便于列出，仅列出两个有代表性的特征供大家参考。
  1. 推荐词与种子query经过切词后的相同term的长度之和与种子query经过切词后的term的长度之和的比值；类型为double类型。
  2. 推荐词基本切词后切词顺序包含 query, 特征值为1，默认值为0；类型为double类型。
  3. 推荐词，种子query的topic向量相似度。
  4. 。。。。更多高维特征。。。。。
利用多个类似的高维特征，就能很好地覆盖推荐词与种子query； 当然特征的设计会直接影响关键词推荐中相关性的定义，例如如果字面（重合）相关特征较多， 则推荐主要表现为字面相关，如特征主要为语义特征， 则推荐结果反映为语义相关。如果特征中有用户的历史行为信息特征（例如用户已经选择的关键词），则可以认为相关性模型就已经实现了个性化处理。
 模型
很多项目因为周期比较赶， 所以小步快跑的起步阶段并没有太多时间去做模型和参数的双向搜索，所以综合效率和时间的代价，选择了部分模型及在经验参数下的效果，进行模型的初选。
最终综合考虑性能，准确性和召回诸多因素下，选择了adaboost，在adaboost ratio 和 弱分类器数量上进行了参数实验。 准确性/召回 效果如下：
具体adaboost算法参见： adaboost介绍
WLRatio 300 500 1000 1500
0 0.87/0.89 0.87/0.91 0.87/0.9 0.86/0.91
-0.1 0.81/0.95 0.79/0.96 0.8/0.96 0.8/0.97
-0.2 0.74/0.98 0.73/0.98 0.73/0.98 0.73/0.98
-0.3 0.66/0.99 0.64/1 0.65/1 0.64/1
评估
以上内容均属于线下模型优化部分，所有的指标均可以线下获得， 但最终需要用线上的效果说话， 最后说服力的， 还是线上A/B Test， 因为是后台策略的升级， 故这样的实验在成熟的A/B test框架下比较容易做； 线上实验的最终效果也比较符合预期， 保证准确性的情况下召回大为提升（此处就不贴具体数值）
后文：后来将adaboost直接替换为Random Forest，在未改变模型的基础上效果立刻提升非常多，可见模型选择也较为重要。
参考文献：
百度凤巢关键词工具： www2.baidu.com
Data.Mining.Concepts.and.Techniques.2nd.Ed
也可关注微博： weibo.com
或是直接访问： http://semocean.com