排序算法毕业论文

在计算广告和推荐系统中，CTR预估(click-through rate)是非常重要的一个环节，判断一个商品的是否进行推荐需要根据CTR预估的点击率来进行。在进行CTR预估时，除了单特征外，往往要对特征进行组合。对于特征组合来说，业界常用的方法有人工特征工程 + LR（Logistic Regression）、GBDT（Gradient Boosting Decision Tree） + LR、FM（Factorization Machine）和FFM（Field-aware Factorization Machine）模型。最近几年也出现了很多基于FM改进的方法，如deepFM，FNN，PNN，DCN，xDeepFM等。 FM(Factorization Machine)主要是为了解决数据稀疏的情况下，特征怎样组合的问题。已一个广告分类的问题为例，根据用户与广告位的一些特征，来预测用户是否会点击广告。数据如下：(本例来自美团技术团队分享的paper) clicked是分类值，表明用户有没有点击该广告。1表示点击，0表示未点击。而country,day,ad_type则是对应的特征。对于这种categorical特征，一般都是进行one-hot编码处理。 将上面的数据进行one-hot编码以后，就变成了下面这样 ： 因为是categorical特征，所以经过one-hot编码以后，不可避免的样本的数据就变得很稀疏。举个非常简单的例子，假设淘宝或者京东上的item为100万，如果对item这个维度进行one-hot编码，光这一个维度数据的稀疏度就是百万分之一。由此可见， 数据的稀疏性 ，是我们在实际应用场景中面临的一个非常常见的挑战与问题。 one-hot编码带来的另一个问题是 特征空间变大 。同样以上面淘宝上的item为例，将item进行one-hot编码以后，样本空间有一个categorical变为了百万维的数值特征，特征空间一下子暴增一百万。所以大厂动不动上亿维度，就是这么来的。 普通的线性模型，我们都是将各个特征独立考虑的，并没有考虑到特征与特征之间的相互关系。但实际上，大量的特征之间是有关联的。最简单的以电商为例，一般女性用户看化妆品服装之类的广告比较多，而男性更青睐各种球类装备。那很明显，女性这个特征与化妆品类服装类商品有很大的关联性，男性这个特征与球类装备的关联性更为密切。如果我们能将这些有关联的特征找出来，显然是很有意义的。 一般的线性模型为：                       从上面的式子很容易看出，一般的线性模型压根没有考虑特征间的关联。为了表述特征间的相关性，我们采用多项式模型。在多项式模型中，特征 与 的组合用 表示。为了简单起见，我们讨论二阶多项式模型。具体的模型表达式如下： 为了简单起见，我们只考虑二阶交叉的情况，具体的模型如下：                       式中， 表示样本的特征数量, 表示第 个特征，与线性模型相比，FM的模型就多了后面特征组合的部分。 从FM公式可以看出，组合特征的参数一共有 n(n−1)/2个，任意两个参数都是独立的。然而，在数据稀疏性普遍存在的实际应用场景中，二次项参数的训练是很困难的。其原因是，每个参数 的训练需要大量 和 都非零的样本；由于样本数据本来就比较稀疏，满足 和 都非零”的样本将会非常少。训练样本的不足，很容易导致参数  不准确，最终将严重影响模型的性能。 那么，如何解决二次项参数的训练问题呢？矩阵分解提供了一种解决思路。在model-based的协同过滤中，一个rating矩阵可以分解为user矩阵和item矩阵，每个user和item都可以采用一个隐向量表示。比如在下图中的例子中，我们把每个user表示成一个二维向量，同时把每个item表示成一个二维向量，两个向量的点积就是矩阵中user对item的打分。 类似地，所有二次项参数 可以组成一个对称阵 （为了方便说明FM的由来，对角元素可以设置为正实数），那么这个矩阵就可以分解为 ， 的第 列便是第 维特征的隐向量。换句话说，每个参数 ，这就是FM模型的核心思想。因此，FM的模型方程为（本文不讨论FM的高阶形式）                      其中， 是第 维特征的隐向量， 代表向量点积。隐向量的长度为 ，二次项的参数数量减少为 个，远少于多项式模型的参数数量。另外，参数因子化使得 的参数和 的参数不再是相互独立的，因此我们可以在样本稀疏的情况下相对合理地估计FM的二次项参数。具体来说， 和 的系数分别为 和 ，它们之间有共同项 。也就是说，所有包含“ 的非零组合特征”（存在某个 ，使得 ）的样本都可以用来学习隐向量 vivi，这很大程度上避免了数据稀疏性造成的影响。而在多项式模型中， 和 是相互独立的。 显而易见，FM的模型公式是一个通用的拟合方程，可以采用不同的损失函数用于解决回归、二元分类等问题，比如可以采用MSE（Mean Square Error）损失函数来求解回归问题，也可以采用Hinge/Cross-Entropy损失来求解分类问题。当然，在进行二元分类时，FM的输出需要经过sigmoid变换，这与Logistic回归是一样的。直观上看，FM的复杂度是 。但是，通过下面的等式，FM的二次项可以化简，其复杂度可以优化到  。由此可见，FM可以在线性时间对新样本作出预测。                              我们再来看一下FM的训练复杂度，利用SGD（Stochastic Gradient Descent）训练模型。模型各个参数的梯度如下： 其中， 是隐向量 的第 个元素。由于 只与 有关，而与 无关，在每次迭代过程中，只需计算一次所有 的 ，就能够方便地得到所有 的梯度。显然，计算所有 的 的复杂度是 ；已知 时，计算每个参数梯度的复杂度是 ；得到梯度后，更新每个参数的复杂度是 ；模型参数一共有 个。因此，FM参数训练的复杂度也是 。综上可知，FM可以在线性时间训练和预测，是一种非常高效的模型。 libFM 论文： Factorization Machines 论文： Factorization Machines with Follow-The-Regularized-Leader for CTR prediction in Display Advertising 推荐系统遇上深度学习(一)--FM模型理论和实践 FM（Factorization Machines）的理论与实践 深入FFM原理与实践-美团 推荐好文：  深度学习在CTR预估中的应用

在CTR预估中，为了解决稀疏特征的问题，学者们提出了FM模型来建模特征之间的交互关系。但是FM模型只能表达特征之间两两组合之间的关系，无法建模两个特征之间深层次的关系或者说多个特征之间的交互关系，因此学者们通过Deep Network来建模更高阶的特征之间的关系。因此 FM和深度网络DNN的结合也就成为了CTR预估问题中主流的方法。有关FM和DNN的结合有两种主流的方法，并行结构和串行结构。两种结构的理解以及实现如下表所示： 今天介绍的NFM模型(Neural Factorization Machine)，便是串行结构中一种较为简单的网络模型。 我们首先来回顾一下FM模型，FM模型用n个隐变量来刻画特征之间的交互关系。这里要强调的一点是，n是特征的总数，是one-hot展开之后的，比如有三组特征，两个连续特征，一个离散特征有5个取值，那么n=7而不是n=3.                      可以看到，不考虑最外层的求和，我们可以得到一个K维的向量。对于NFM模型，目标值的预测公式变为：                      其中，f(x)是用来建模特征之间交互关系的多层前馈神经网络模块，架构图如下所示： mbedding Layer 和我们之间几个网络是一样的，embedding 得到的vector其实就是我们在FM中要学习的隐变量v。 Bi-Interaction Layer 名字挺高大上的，Bi是Bi-linear的缩写，这一层其实是一个pooling层操作，它把很多个向量转换成一个向量，，其实它就是计算FM中的二次项的过程，因此得到的向量维度就是我们的Embedding的维度。最终的结果是：                      Hidden Layers就是我们的DNN部分，将Bi-Interaction Layer得到的结果接入多层的神经网络进行训练，从而捕捉到特征之间复杂的非线性关系。 在进行多层训练之后，将最后一层的输出求和同时加上一次项和偏置项，就得到了我们的预测输出：                      NFM模型将FM与神经网络结合以提升FM捕捉特征间多阶交互信息的能力。根据论文中实验结果，NFM的预测准确度相较FM有明显提升，并且与现有的并行神经网络模型相比，复杂度更低。 NFM本质上还是基于FM，FM会让一个特征固定一个特定的向量，当这个特征与其他特征做交叉时，都是用同样的向量去做计算。这个是很不合理的，因为不同的特征之间的交叉，重要程度是不一样的。因此，学者们提出了AFM模型（Attentional factorization machines），将attention机制加入到我们的模型中。 论文： Neural Factorization Machines for Sparse Predictive Analytics

Abstract: sorting is the important foundation of computer programming, is one of the most important technology of computer application, computer will produce many of the output is according to certain rules and orderly output. Here we from the Angle of data structure, a simple analysis of the insertion sort, partition, quick sorting and so on several common sort algorithm realization principle and the algorithm, the algorithm of time and efficiency, and the object oriented language Java some algorithms of code and simple example, through the example program operation and the analysis, some aspects from the different sort algorithm, the properties of our learning algorithm and the actual programming have helped.