中间结果文件造成的组合爆炸问题及解决方法

（一）广告点击率的预测

竞争性广告是商业搜索引擎公司的主要收入来源，当搜索引擎用户发布搜索关键词时，广告商提供创意和关键词竞价，从而触发关键供应商广告的购买。对于多个触发广告，存在着广告创意排名的问题，即需要确定哪些广告应该显示，哪些广告应该按顺序显示。

CTR表示广告的点击率，通常由点击次数和显示数量之间的比率计算。CTR越高，广告排名越高。一个直观的想法，如何估计CTR，是基于历史点击率信息的广告。对于一个查询术语，假设广告A在1000种显示器中被点击10次，它的CTR可以估计为0.01。这个想法可能看起来很简单，但不可行，主要是因为使用历史数据M不足以估计一个可信的值。因此，有必要运用一定的技术手段，合理估计广告的CTR。一般的做法是根据轮询和广告的特点，使用逻辑回归等机器学习模型来估计CTR。

Alimama负责阿里巴巴的广告业务，他们希望提高CTR估算的准确性，但面临两大挑战：第一，数据规模，涉及数百亿条记录；第二，数据每天更新，这就要求该模型具有更高的性能。目前，基于ODPS机器学习框架，通过逻辑回归算法实现模型训练，然后将训练结果输出到在线服务的广告引擎中来提高CTR估算的准确性。

（二）平行随机梯度下降

平行随机梯度下降是雅虎提出了一种简单的数据并行随机梯度下降算法。

假设训练数据用CI表示，Wi表示第二次迭代的特征权重向量。假设有k台随机梯度下降（SGD）机器可以并发运行，执行逻辑如下：首先，主控制程序将所有连续数据分配给k个服务器。每个服务器获取完整的训练数据，然后每个服务器可以并行执行单机SGD任务。从所有训练数据中随机抽取单机SGD任务，并根据其梯度的逆方向作为目标函数的降维方向。每一次用n步大小更新特征权重向量。这样，每个服务器的单个SGD任务就可以得到产量模型参数，然后主控程序从每台服务器上收集它们的模型，并取平均值得到最终的模型参数。

虽然该方法看起来非常简单，但本书作者证明了该算法的收敛性。

（三）自然语言处理：文件相似度的计算

在语言处理环境中，计算文档集合中任意两个文档的相似性是一个非常常见的应用场景。计算任意两个文档间相似性的计算复杂度为0。如果文档集很小，则可以在一台机器上进行处理。但是，如果文档集合很大，例如百万级别，则只能考虑与多台计算机并行计算。这是一个典型的非迭代批处理任务，所以使用Map Reduce来解决它是一个很好的选择。

一种简单、粗糙的方法是根据公式计算任意两个文档，但实际上可以优化公式。优化的基本思想是：对任意两个文档，考虑任何一个单词t对相似度计算的影响，很明显，如果t不出现在任何文档中，那么它对两个文档的相似度的贡献率为0，即只有两个文档包含t这个词，那么单词t对两者之间的相似性有影响。如果查看单词t，可以记录哪些文档包含单词t并形成一个集合。因此，对于单词t来说，它只会导致集合中文档的两两相似性。(www.xing528.com)

如果文档集合很大，请考虑使用两个连续的MR任务来完成上述计算过程。第一个任务是建立单词索引的过程。任务的输入是文档希尔地图阶段的输出键是单词t值，作为包含单词和单词权重的文档ID。减少阶段总结包含单词t的文档，并将倒排索引写入磁盘。使用一个单词的倒排索引，MR任务的第二阶段计算文档的相似度。总之，Map阶段在其倒排索引文档集合中计算，单词对任意两个文档相似性的贡献。如果倒排索引包含Map，则需要执行（m-1）计算。此阶段的关键输出是文档，其值为约简阶段累加同一文档对的所有值，即累加不同词对计算两个文档相似度的贡献，从而得到两个文档的全局相似度。

这样，可以对大规模文本计算集进行相似度计算。实验结果表明，文档大小随计算时间的增加呈线性增长，是一种可扩展的计算方法，但也存在一些问题。在计算文档相似度的第二阶段MR任务时，Map工作台的输出存在组合爆炸问题，会产生大量的中间结果文件，占用了大量的磁盘空间，降低了计算效率。为了减少中间文件的数量，可以使用DF-cm的优化方法，即过滤一些停止词或普通单词，从而大大减少中间结果文件的大小和减少阶段的计算量。而且由于一个词的df值大往往意味着信息含量较少，即使经过过滤，也不会对相似度计算的结果产生很大的影响。

（四）ALI云PAI和ET

阿里云PAI是阿里巴巴集团的智能平台，旨在加快整个创新过程，提高工作效率。该平台是一个基于ALI云的云计算平台。它具有处理大规模数据的能力和分布式存储能力。同时，整个模型支持非常大规模的建模和GPU计算。此外，该平台还具有社区特色：实验结果可以共享，社区团队共同工作。智能平台主要分为三层：第一层是WebU 1接口，第二层是IDST算法层，最后一层是Max Compute平台层。

PAI的主要特点是适合大数据分析、分布式计算体系结构、大量先进算法的集成、完备的数据挖掘功能和良好的图形界面。

该平台通过交互界面降低了技术门槛，用户无须过多的经验就可以轻松地实现数据挖掘的工作。其次，ALI对其嵌入式算法进行了多年的改进，提高了算法的性能和精度。最后，在数据智能化方面，平台提供了从元数据到模型部署的完整流程，通过提供基本组件，用户可以构建各种垂直场景下的解决方案。

其客户主要包括以下几类：一类是传统的大型企业和政府部门，如中石化、中石油、气象局；另一类是中小型企业，主要是公共云启动用户；以及一些个人用户，如数据科学家、研究人员等。

PAI的底层是基础设施层，包括CPU和GPU集群，顶层是ALI提供的计算框架，包括Map Reduce、SQL、MPI等。中间层是模型算法层，包括数据预处理、特征工程、机器学习算法等基本组件，帮助用户完成简单的工作。平台产品层主要是项目管理、算法模型共享等一些具体需求；顶层是应用层，ALI内部搜索、推荐、蚂蚁金融服务集团等项目的数据挖掘工作都依赖于PAI平台产品。

ALI云ET是基于ALI人工智能平台开发的，其特点是基于强大的云计算和大数据处理能力，目前，E-Work具有语音识别、图像/视频识别、交通预测、情感分析等技能，并向大数据人工智能方向发展。ET的前身是阿里·云·小AI，它在湖南卫视的“我是歌手”节目中准确地预测了这位进入决赛的歌手属于李健，这是人工智能技术在理解人类情感方面向前迈出的重要一步。