卡方技术在企业搜索引擎角色信息分析中的运用论文
对于少于 1 000 人的企业单位，60% 的员工认为在企业信息化平台中找到自己想要的数据是非常困难的。
而在公司人数超过 1 000 人的情况下，认为获取不到自己想要数据的员工竟然达到公司人数的 77%.因此，企业的规模越大，企业的人数越多，企业信息化平台中产生的数据量就越多，员工查找信息就更加困难。根据调查显示，对于少于 1 000 人的企业里，有 67% 的员工认为找到所需的信息对企业的发展是有影响的，而对于多于 1 000 人的企业中，这个数字竟然高达 89%.在大中型企业中，每天有 70% 的员工耗费 1 ~ 2 小时来查找所需要的信息，加大了企业的成本，尤其是用户想要查看已经离职员工之前记录的信息，由于人员已经离开，想要查找对应信息的难度加大，搜索耗费的时间就更长。
传统企业搜索引擎虽然在一定程度上已经解决该问题。然而，不同角色的用户有着不同的需求，例如，财务角色的用户和销售角色的用户对于相同的查询词会有不同的需求。本文提出采用卡方的方法进行角色信息的分析，使不同角色的用户虽采用相同的查询词，但得到与其角色更相关的信息。
1 基于卡方的角色分析理论
企业内部每个用户在不同系统中的职位不一样，对于相同角色下的用户，偏好可能相同，如角色 A 下的用户关注财务信息，经常搜索和点击财务方面的数据。当角色 A 下的其他用户搜索时，如果查询词跟 A 输入的查询词相关时，根据 LUCENE,获取文档应排在后面，但根据角色信息，角色 A 下的用户点击过多的.文档应排在前面，这样就隐含地为用户推送了相关文档。针对这个可能性，进行角色分析。【1】
其中，N 是一个定值，系统的数据条目数；A 代表在某角色中文档包含该词的篇数；B 代表在该角色中文档没有包含该词的篇数；C 代表的是不在该角色下有多少篇文档包含该词；D 代表的是不在该角色下有多少篇文档没有包含该词；而 A+C 是一个定值，B+D 也是一个定值，因此公式（1）可以简化，如下所示：【2】
2 基于卡方的角色分析理论算法过程
因为企业中有多个系统，分系统考虑，统计一个系统下所有角色对应的特征词。
第一步获取某系统下的所有数据，获取文档对应的用户以及角色，并对正文部分进行分词。
第二步获取角色 A 在该系统下的所有数据并分词。
第三步对角色 A 下的每个词 T,统计词 T 在该角色下出现的样本频率，获取词 T 在该角色中没有出现的样本频率，获取词 T 不在该角色下出现的样本频率，获取词 T 不在该角色下没有出现的样本频率。
第四步，根据公式（2）计算该系统下角色 A 中词T 的权重；获取每个系统下的每个角色对应的特征词，并保存。
第五步获取用户所能访问系统中角色对应的特征词，并根据特征词进行全文检索，获取排名前300的文档。
当获取某系统下角色 A 权重最大的 10 个词时，需考虑特征词在该系统下所有角色中出现的次数，如果次数大于角色个数的一个比值时，则这样的词排除掉，因为这样的词不具有特性。
当用户查询时，根据输入查询词，得到搜索结果，分析前 300 篇文档中是否包含该文档，如果包含，则将文档的分数提高。
3 结 语
针对目前企业搜索中存在的问题，不同角色的用户有着不同的需求，本文提出基于卡方的角色分析方法，使不同角色的用户虽采用相同的查询词，但得到与其角色更相关的信息。该方法已经应用在实际平台中，进一步证明了该方法的有效性。
参考文献
[1] 吴庆涛 . 个性化搜索引擎中的用户兴趣模型分析与研究 [J]. 研究与开发 ,2010（10）。
[2] 李绍华 , 高文宇 . 搜索引擎页面排序算法研究综述 [J]. 计算机应用研究 ,2007（24）。
在计算广告和推荐系统中，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预估中的应用
PNN，全称为Product-based Neural Network，认为在embedding输入到MLP之后学习的交叉特征表达并不充分，提出了一种product layer的思想，既基于乘法的运算来体现体征交叉的DNN网络结构，如下图：
按照论文的思路，我们也从上往下来看这个网络结构：
输出层
输出层很简单，将上一层的网络输出通过一个全链接层，经过sigmoid函数转换后映射到(0,1)的区间中，得到我们的点击率的预测值：
l2层
根据l1层的输出，经一个全链接层 ，并使用relu进行激活，得到我们l2的输出结果：
l1层
l1层的输出由如下的公式计算：
重点马上就要来了，我们可以看到在得到l1层输出时，我们输入了三部分，分别是lz，lp 和 b1，b1是我们的偏置项，这里可以先不管。lz和lp的计算就是PNN的精华所在了。我们慢慢道来:
Product Layer
product思想来源于，在ctr预估中，认为特征之间的关系更多是一种and“且”的关系，而非add"加”的关系。例如，性别为男且喜欢游戏的人群，比起性别男和喜欢游戏的人群，前者的组合比后者更能体现特征交叉的意义。
product layer可以分成两个部分，一部分是线性部分lz，一部分是非线性部分lp。二者的形式如下：
在这里，我们要使用到论文中所定义的一种运算方式，其实就是矩阵的点乘啦：
Embedding Layer
Embedding Layer跟DeepFM中相同，将每一个field的特征转换成同样长度的向量，这里用f来表示。
损失函数
使用和逻辑回归同样的损失函数，如下：
前面提到了，product layer可以分成两个部分，一部分是线性部分lz，一部分是非线性部分lp。看product layer的公式，我们首先需要知道z和p，这都是由我们的embedding层得到的，其中z是线性信号向量，因此我们直接用embedding层得到：
论文中使用的等号加一个三角形，其实就是相等的意思，你可以认为z就是embedding层的复制。
对于p来说，这里需要一个公式进行映射：
不同的g的选择使得我们有了两种PNN的计算方法，一种叫做Inner PNN，简称IPNN，一种叫做Outer PNN，简称OPNN。
接下来，我们分别来具体介绍这两种形式的PNN模型，由于涉及到复杂度的分析，所以我们这里先定义Embedding的大小为M，field的大小为N，而lz和lp的长度为D1。
IPNN的示意图如下：
IPNN中p的计算方式如下，即使用内积来代表 ：
所以， 其实是一个数，得到一个 的时间复杂度为M，p的大小为N*N，因此计算得到p的时间复杂度为N*N*M。而再由p得到lp的时间复杂度是N*N*D1。因此 对于IPNN来说，总的时间复杂度为N*N(D1+M)。文章对这一结构进行了优化，可以看到，我们的p是一个对称矩阵，因此我们的权重也可以是一个对称矩阵，对称矩阵就可以进行如下的分解：
因此：
因此：
从而得到：
可以看到，我们的权重只需要D1 * N就可以了，时间复杂度也变为了D1*M*N。
2.2 OPNN
OPNN的示意图如下：
OPNN中p的计算方式如下：
此时 为M*M的矩阵，计算一个 的时间复杂度为M*M，而p是N*N*M*M的矩阵，因此计算p的事件复杂度为N*N*M*M。从而计算lp的时间复杂度变为D1 * N*N*M*M。这个显然代价很高的。为了减少负责度，论文使用了叠加的思想，它重新定义了p矩阵：
这里计算p的时间复杂度变为了D1*M*(M+N)
论文： Product-based Neural Networks for User Response Prediction
推荐系统中使用ctr排序的f(x)的设计-dnn篇之PNN模型
推荐系统遇上深度学习(六)--PNN模型理论和实践
推荐好文： 深度学习在CTR预估中的应用
对于今天排序技术的探索可以追溯到19世纪，美国人口统计局的Herman Hollerith发明了第一批具有排序装置的制表机，成功地应用到1890年的美国人口普查。关于Hollerith及其制表机的故事，Leon E. Truesdell曾在【The Development of Punch Card Tabulation（Washington: U. S. Bureau of the Census, 1965）】中进行了有趣而详尽地描述。
排序例程曾经是为存储程序式计算机编写的第一个程序，因为它集中体现了计算机潜在的非数值应用。冯·诺伊曼在1954年为了检验EDVAC计算机指令代码的适用性以及评价他所建议的计算机组织的优点，编写了内部归并排序程序，Knuth在【Computing Surveys 2(1970), 247~260】中描述了这个发展细节。
在德国，K. Zuse于1945年独立编写了用于直接插入排序的程序，作为他的Plankalkul语言中线性表操作的例子之一，这一开创性的工作推迟了近30年才发表。
1946年在穆尔学校举行的有关计算的专题讨论会上，John Mauchly作了“排序和整理”的演讲，是第一个公开发表的关于计算机排序的讨论，包括直接插入排序和折半插入排序。
到1952年左右，内部排序的许多方法已在程序设计领域广为流传，但理论上的研究却相对很少。Daniel Goldenberg用Whirlwind计算机编写了5个不同方法的排序程序，分别就最好情况和最坏情况进行了分析。
由Howard B. Demuth于1956年撰写的博士论文【Electronic Data Sorting. Stanford University, 1956】可以说是一篇非常值得关注的论文，因为这篇论文有助于奠定计算复杂性理论的基础。论文利用循环的、线性的以及随机的存储器，考虑了排序问题的3个抽象模型，并对每个模型提出了最优（或接近最优）的方法。Demuth的论文建立了如何把理论同实践相联系的重要思想。
事实上，计算的大多数早期历史都出现在比较难以得到的报告中，因为那时仅有少数人同计算机打交道。有关排序文献的第一次付印是在1955年，用的是三篇重要的综述性文章。第一篇文章是由J. C. Hosken撰写的【Proc. Eastern Joint Computer Conference 8(1955), 39~55】，综述了在计算机上进行排序的方法，以及所有可利用的专用设备，文中的54项参考文献大多数是以厂家的手册为基础的。第二篇文章是由E. H. Friend撰写的【Sorting on Electronic Computer Systems. Journal of the ACM 3(1956), 134~168】是排序技术发展史的一个重要里程碑，Friend对相当多的内部和外部排序算法给出了细致的描述。第三篇文章是由D. W. Davies撰写的【Proc. Inst. Elec. Engineers 103B, Supplement 1(1956), 87~93】。
1962年11月ACM主持召开了一次关于排序的研讨会，在会上宣读的大多数论文都发表在COMMUNICATIONS OF THE ACM1963年5月的刊物上，这些论文是当时技术发展水平的很好代表。
靠，这就给5分。自己找吧给500刀还差不多
