KDD 2019 | 自动探求特点组合，第四范式提出新方式AutoCross

　　KDD 2019 | 自动探求特点组合，第四范式提出新方式AutoCross

　　机器之心专栏

　　作者：罗远飞、王梦硕、周浩、姚权铭

　　涂威威、陈雨强、杨强、戴文渊

　　特征组合是提升模型疗效的重要手段，但借助专家自动探求和试错成本过低且过分冗长。于是，第四范式提出了一种新型特点组合方式 AutoCross，该方式可在实际应用中手动实现表数据的特点组合，提高机器学习算法的预测能力，并提高效率和有效性。目前，该论文已被数据挖掘领域顶会 KDD 2019 接收。

　　论文简介

　　论文：AutoCross: Automatic Feature Crossing for Tabular Data in Real-World Applications

　　

　　论文链接：

　　本文提出了一种在实际应用中手动实现表数据特点组合的方式 AutoCross。该方式可以获得特点之间有用的相互作用，并提升机器学习算法的预测能力。该方式借助集束搜索策略（beam search strategy）构建有效的组合特点，其中收录仍未被现有工作覆盖的高阶（两个以上）特征组合，弥补了此前工作的不足。

　　此外，该研究提出了连续小批量梯度增长和多细度离散化，以进一步提升效率和有效性，同时确保简单，无需机器学习专业知识或繁琐的超参数调整。这些算法致力增加分布式估算中涉及的估算、传输和储存成本。在基准数据集和真实业务数据集上的实验结果表明，AutoCross 可以明显提升线性模型和深度模型对表数据的学习能力和性能，优于其他基于搜索和深度学习的特点生成方式，进一步证明了其有效性和效率。

　　背景介绍

　　近年来，机器学习似乎已在推荐系统、在线广告、金融市场剖析等众多领域取得了好多成功，但在这种成功的应用中，人类专家参与了机器学习的所有阶段，包括：定义问题、采集数据、特征工程、调整模型超参数，模型评估等。

　　而这种任务的复杂性常常超出了非机器学习专家的能力范围。机器学习技术使用门槛高、专家成本昂贵等问题成为了阻碍 AI 普及的关键诱因。因此，AutoML 的出现被视为提升机器学习易用性的一种最有效方式，通过技术手段减低对人类专家的依赖，让更多的人应用 AI，获得更大的社会和商业效益。

　　众所周知，机器学习的性能很大程度上取决于特点的质量。由于原创特点极少形成令人满意的结果，因此一般要对特点进行组合，以更好地表示数据并提升学习性能。例如在新闻推荐中，若只有新闻类型、用户 ID 两类特点，模型只能分别预测不同新闻类型或不同用户 ID 对点击率的影响。通过加入新闻类型 x 用户 ID 组合特点，模型就可学习到一个用户对不同新闻的偏好。再加入时间等特点进行高阶组合，模型就可对一个用户在不同时间对不同新闻的偏好进行预测，提升模型的个性化预测能力。

　　特征组合作为提升模型疗效的重要手段，以往大多须要建立庞大的数据科学家团队，依靠她们的经验进行探求和试错，但冗长、低效的过程令科学家非常苦闷，且并非所有企业都能承受昂贵的成本。

　　第四范式从很早便开始关注并精耕 AutoML 领域，从解决顾客业务核心下降的角度出发，构建了反欺诈、个性化推荐等业务场景下的 AutoML，并将其赋能给企业的普通开发人员，取得了接近甚至超过数据科学家的业务疗效。其中，AutoCross 发挥了重要的作用。

　　痛点

　　特征组合是对从数据中提取的海量原创特点进行组合的过程，采用稀疏特点叉乘得出组合特点。在线性模型如 LR 只能描画特点间的线性关系、表达能力受限，而非线性模型如 GBDT 不能应用于*敏*感*词*离散特点场景的情况下，特征组合就能降低数据的非线性，从而提升性能。

　　但枚举所有组合特点，理论上很难做到，因为可能的组合特点数是指数级的，同时暴力添加特点可能会造成学习性能增长，因为它们可能是无关的或冗余的特点，从而降低学习难度。

　　虽然深度神经网络可手动建立高阶特点 (generate high-order features)，但面对大多数以表方式呈现的业务数据，最先进的基于深度学习的方式难以有效囊括所有高阶组合特点，且存在可解释性差、计算成本高等恶果。该论文投稿时，最先进的深度学习方法是 xDeepFM [1]。这篇论文证明了 xDeepFM 可生成的特点是 AutoCross 可生成特点嵌入（embedding）的子集。

　　AutoCross 的优势

　　实现过程

　　给定训练数据 ，并将其界定为训练集 和验证集 。我们可以用一个特点集合 S 来表示 ，并用学习算法 L 训练一个模型 。之后，用验证集和同一个特点集合 S 计算一个须要被最大化的指标 。特征组合搜索问题可以定义为搜索一个最优子特点集的问题：

　　其中 F 是 的原创特点集合，收录 F 所有原创特点以及基于 F 可生成的所有组合特点。

　　但是，假设原创特点数为 d，则上述问题中所有可能解的数目是 ，搜索空间巨大。为了提升搜索效率，AutoCross 将搜索最优子特点集的问题转换为用贪婪策略逐渐建立较优解的问题。首先，AutoCross 考虑一个树结构的搜索空间 （图 3），其中每一个节点表示一个子特点集。之后，用集束搜索策略在 上搜索较优解。通过这些方式，AutoCross 只须要访问 个候选解，极大地提升了搜索效率。AutoCross 的整体算法如算法 1 所示。

　　

　　

　　算法 1 中的一个关键步骤是评估候选特征集。最直接的方式是用每位候选特征集训练模型并评估其性能，但是这些方式估算代价巨大，难以在搜索过程中反复执行。为了提升特征集评估的效率，AutoCross 提出了逐域对数概率回归（field-wise logistic regression）和连续批训练梯度增长（successive mini-batch gradient descent）方法。

　　为了提升特征集评估效率，逐域对数概率回归做出两种近似。首先，用特点集在对数概率回归模型上的表现近似最终将使用这个特点集的模型上的表现；其次，在考虑 中一个节点的子节点时，不改变该节点收录特点对应的权重（weight），仅训练子节点新增特点的权重。

　　图 4 说明了怎样将逐域对数概率回归布署在参数服务器构架上。逐域对数概率回归与参数服务器的结合可以提升特征集评估的储存效率、传输效率和估算效率。在逐域对数概率回归训练结束后，AutoCross 计算训练得模型的指标，并借此方式来评估每一个候选特征集。

　　

　　AutoCross 采用连续批训练梯度增长方式进一步提升特征集评估的效率。该方式借鉴 successive halving 算法 [2]，认为每一个候选特征集是 multi-arm bandit 问题中的一个 arm，对一个特点集用一个数据块进行权重更新相当于拉了一次对应的 arm，其回报为该次训练后的验证集 AUC。

　　具体算法见算法 2，算法 2 中惟一的参数是数据块的数目 N。N 可以按照数据的大小和估算环境自适应地确定。在使用连续批训练梯度增长时，用户不需要象使用传统的 subsampling 方法一样调整 mini-batch 的规格和采样率。

　　

　　为了支持数值特点与离散特点的组合，AutoCross 在预处理时将数值特点离散化为离散特点。AutoCross 提出了多细度离散化（multi-granularity discretization）方法，使得用户不需要反复调整离散化的细度。多细度离散化思想简单：将每一个数值特点，根据不同细度界定为多个离散特点。然后采用逐域对数概率回归选购出最优的离散特点。多个界定细度既可以由用户指定，也可以由 AutoCross 根据数据大小和估算环境来自适应地选择，从而增加了用户的使用难度。

　　实验结果

　　该论文在十个数据集（五个公开、五个实际业务）上进行了实验。比较的方式包括：

　　效果比较：如下表 3 所示，AC+LR 和 AC+W&D 在大部分数据集上的排行都在前两位。这彰显了 AutoCross 产生的特点除了可以提高 LR 模型，也可以用于增强深度学习模型的性能，并且 AC+LR 和 AC+W&D 的疗效都优于 xDeepFM。如之前所说，xDeepFM 所生成的特点不能完全收录 AutoCross 生成的特点。这些结果彰显出显式生成高阶组合特点的疗效优势。

　　

　　高阶特点的作用：见表 5 和图 6。从中可以得出，高阶组合特点可以有效提升模型性能。

　　

　　时间消耗：见表 6、图 7（主要做展示用）。

　　

　　

　　推断延后：见表 7。从中可以得出：AC+LR 的推测速率比 AC+W&D、Deep、xDeepFM 快几个数量级。这说明 AutoCross 不仅可以提升模型表现，同时保证了太低的推论延后。

　　参考文献

　　[1] J. Lian, X. Zhou, F. Zhang, Z. Chen, X. Xie, and G. Sun. 2018. xDeepFM: Com- bining Explicit and Implicit Feature Interactions for Recommender Systems. In International Conference on Knowledge Discovery & Data Mining.

　　[2] K. Jamieson and A. Talwalkar. 2016. Non-stochastic best arm identification and hyperparameter optimization. In Artificial Intelligence and Statistics. 240–248.

　　[3] O. Chapelle, E. Manavoglu, and R. Rosales. 2015. Simple and scalable response prediction for display advertising. ACM Transactions on Intelligent Systems and Technology (TIST) 5, 4 (2015), 61.

　　------------------------------------------------

　　加入机器之心（全职记者 / 实习生）：

　　投稿或寻求报导：