月度归档:2018年03月

推荐NLPIR大数据语义智能分析平台

Deep Learning Specialization on Coursera

NLPIR大数据语义智能分析平台由北京理工大学大数据搜索与挖掘实验室( Big Data Search and Mining Lab.BDSM@BIT)张华平博士主导,最近上线了新版,这里做个推荐。张华平博士最广为人知的产品是ICTCLAS中文分词平台,相信这更有助于大家了解NLPIR大数据语义智能分析平台,以下摘自“NLPIR大数据语义智能分析平台新版上线”。

NLPIR大数据语义智能分析平台针对大数据内容采编挖搜的综合需求,融合了网络精准采集、自然语言理解、文本挖掘和语义搜索的最新研究成果,先后历时十八年,服务了全球四十万家机构用户,是大数据时代语义智能分析的一大利器。

NLPIR大数据语义智能挖掘平台,针对大数据内容处理的需要,融合了网络精准采集、自然语言理解、文本挖掘和网络搜索的技术,提供了客户端工具、云服务、二次开发接口。开发平台由多个中间件组成,各个中间件API可以无缝地融合到客户的各类复杂应用系统之中,可兼容Windows,Linux,Android,Maemo5, FreeBSD等不同操作系统平台,可以供Java,C,C#等各类开发语言使用。

NLPIR大数据语义智能分析平台十三大功能:

1、精准采集:对境内外互联网海量信息实时精准采集,有主题采集(按照信息需求的主题采集)与站点采集两种模式(给定网址列表的站内定点采集功能)。

2、文档抽取:对doc、excel、pdf与ppt等多种主流文档格式,进行文本信息抽取,信息抽取准确,效率达到大数据处理的要求。

3、新词发现:从文本中挖掘出新词、新概念,用户可以用于专业词典的编撰,还可以进一步编辑标注,导入分词词典中,提高分词系统的准确度,并适应新的语言变化。

4、批量分词:对原始语料进行分词,自动识别人名地名机构名等未登录词,新词标注以及词性标注。并可在分析过程中,导入用户定义的词典。

5、语言统计:针对切分标注结果,系统可以自动地进行一元词频统计、二元词语转移概率统计。针对常用的术语,会自动给出相应的英文解释。

6、文本聚类:能够从大规模数据中自动分析出热点事件,并提供事件话题的关键特征描述。同时适用于长文本和短信、微博等短文本的热点分析。

7、文本分类:根据规则或训练的方法对大量文本进行分类,可用于新闻分类、简历分类、邮件分类、办公文档分类、区域分类等诸多方面。

8、摘要实体:对单篇或多篇文章,自动提炼出内容摘要,抽取人名、地名、机构名、时间及主题关键词;方便用户快速浏览文本内容。

9、智能过滤:对文本内容的语义智能过滤审查,内置国内最全词库,智能识别多种变种:形变、音变、繁简等多种变形,语义精准排歧。

10、情感分析:针对事先指定的分析对象,系统自动分析海量文档的情感倾向:情感极性及情感值测量,并在原文中给出正负面的得分和句子样例。

11、文档去重:快速准确地判断文件集合或数据库中是否存在相同或相似内容的记录,同时找出所有的重复记录。

12、全文检索:支持文本、数字、日期、字符串等各种数据类型,多字段的高效搜索,支持AND/OR/NOT以及NEAR邻近等查询语法,支持维语、藏语、蒙语、阿拉伯、韩语等多种少数民族语言的检索。

13、编码转换:自动识别内容的编码,并把编码统一转换为其他编码。

欢迎大家下载使用。

NLPIR大数据语义智能分析平台白皮书:

http://www.nlpir.org/NLPIR-Parser-WhitePaper.pdf (约3MB)

NLPIR大数据语义智能分析平台:

http://www.nlpir.org/NLPIR-Parser.zip (约160MB)

推荐系统中的矩阵分解技术(达观数据 周颢钰)

Deep Learning Specialization on Coursera

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

网络中的信息量呈现指数式增长,随之带来了信息过载问题。推荐系统是大数据时代下应运而生的产物,目前已广泛应用于电商、社交、短视频等领域。本文将针对推荐系统中基于隐语义模型的矩阵分解技术来进行讨论。

NO.1
评分矩阵、奇异值分解与Funk-SVD

对于一个推荐系统,其用户数据可以整理成一个user-item矩阵。矩阵中每一行代表一个用户,而每一列则代表一个物品。若用户对物品有过评分,则矩阵中处在用户对应的行与物品对应的列交叉的位置表示用户对物品的评分值。这个user-item矩阵被称为评分矩阵。

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

上图即为评分矩阵的一个例子。其中的?表示用户还没有对物品做出评价,而推荐系统最终的目标就是对于任意一个用户,预测出所有未评分物品的分值,并按分值从高到低的顺序将对应的物品推荐给用户。

说到矩阵分解技术,首先想到的往往是特征值分解(eigendecomposition)奇异值分解(Singular value decomposition,SVD)

对于特征值分解,由于其只能作用于方阵,因此并不适合分解评分矩阵这个场景。

而对于奇异值分解,其具体描述为:假设矩阵M是一个m*n的矩阵,则一定存在一个分解技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术,其中U是m*m的正交矩阵,V是n*n的正交矩阵,Σ是m*n的对角阵,可以说是完美契合分解评分矩阵这个需求。其中,对角阵Σ还有一个特殊的性质,它的所有元素都非负,且依次减小。这个减小也特别快,在很多情况下,前10%的和就占了全部元素之和的99%以上,这就是说我们可以使用最大的k个值和对应大小的U、V矩阵来近似描述原始的评分矩阵。

于是我们马上能得到一个解决方案:对原始评分矩阵M做奇异值分解,得到U、V及Σ,取Σ中较大的k类作为隐含特征,则此时M(m*n)被分解成U(m*k) Σ(k*k)V(k*n),接下来就可以直接使用矩阵乘法来完成对原始评分矩阵的填充。但是实际上,这种方法存在一个致命的缺陷——奇异值分解要求矩阵是稠密的。也就是说SVD不允许待分解矩阵中存在空白的部分,这一开始就与我们的问题所冲突了。

当然,也可以想办法对缺失值先进行简单的填充,例如使用全局平均值。然而,即使有了补全策略,在实际应用场景下,user和item的数目往往是成千上万的,面对这样的规模传统SVD算法O(n^3)的时间复杂度显然是吃不消的。因此,直接使用传统SVD算法并不是一个好的选择。(达观数据周颢钰)

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

既然传统SVD在实际应用场景中面临着稀疏性问题和效率问题,那么有没有办法避开稀疏问题,同时提高运算效率呢?

实际上早在06年,Simon Funk就提出了Funk-SVD算法,其主要思路是将原始评分矩阵M(m*n)分解成两个矩阵P(m*k)和Q(k*n),同时仅考察原始评分矩阵中有评分的项分解结果是否准确,而判别标准则是均方差。

即对于矩阵M(m*n),我们想办法将其分解为P(m*k)、Q(k*n),此时对于原始矩阵中有评分的位置MUI来说,其在分解后矩阵中对应的值就是

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

那么对于整个评分矩阵而言,总的损失就是

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

只要我们能想办法最小化上面的损失SSE,就能以最小的扰动完成对原始评分矩阵的分解,在这之后只需要用计算M’ 的方式来完成对原始评分矩阵的填充即可。(达观数据 周颢钰)

这种方法被称之为隐语义模型(Latent factor model,LFM),其算法意义层面的解释为通过隐含特征(latent factor)将user兴趣与item特征联系起来。

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

对于原始评分矩阵R,我们假定一共有三类隐含特征,于是将矩阵R(3*4)分解成用户特征矩阵P(3*3)与物品特征矩阵Q(3*4)。考察user1对item1的评分,可以认为user1对三类隐含特征class1、class2、class3的感兴趣程度分别为P11、P12、P13,而这三类隐含特征与item1相关程度则分别为Q11、Q21、Q31。

回到上面的式子

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

可以发现用户U对物品I最终的评分就是由各个隐含特征维度下U对I感兴趣程度的和,这里U对I的感兴趣程度则是由U对当前隐含特征的感兴趣程度乘上I与当前隐含特征相关程度来表示的。

于是,现在的问题就变成了如何求出使得SSE最小的矩阵P和Q

 

NO.2
随机梯度下降法

在求解上文中提到的这类无约束最优化问题时,梯度下降法(Gradient Descent)是最常采用的方法之一,其核心思想非常简单,沿梯度下降的方向逐步迭代。梯度是一个向量,表示的是一个函数在该点处沿梯度的方向变化最快,变化率最大,而梯度下降的方向就是指的负梯度方向。

根据梯度下降法的定义,其迭代最终必然会终止于一阶导数(对于多元函数来说则是一阶偏导数)为零的点,即驻点。对于可导函数来说,其极值点一定是驻点,而驻点并不一定是极值点,还可能是鞍点。另一方面,极值点也不一定是最值点。下面举几个简单的例子。

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

上图为函数技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术。从图中可以看出,函数唯一的驻点 (0,0)为其最小值点。

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

上图为函数技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术。其一阶导数为技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术,从而可知其同样有唯一驻点(0,0)。从图中可以看出,函数并没有极值点。

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

上图为函数技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术。从图像中可以看出,函数一共有三个驻点,包括两个极小值点和一个极大值点,其中位于最左边的极小值点是函数的最小值点。

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

上图为函数技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术。其中点 (0,0,0)为其若干个鞍点中的一个。

从上面几幅函数图像中可以看出梯度下降法在求解最小值时具有一定的局限性,用一句话概括就是,目标函数必须是凸函数。关于凸函数的判定,对于一元函数来说,一般是求二阶导数,若其二阶导数非负,就称之为凸函数。对于多元函数来说判定方法类似,只是从判断一元函数的单个二阶导数是否非负,变成了判断所有变量的二阶偏导数构成的黑塞矩阵(Hessian Matrix)是否为半正定矩阵。判断一个矩阵是否半正定可以判断所有特征值是否非负,或者判断所有主子式是否非负。

回到上面funk-svd的最优化问题上来。经过一番紧张刺激的计算之后,可以很遗憾地发现,我们最终的目标函数是非凸的。这就意味着单纯使用梯度下降法可能会找到极大值、极小值或者鞍点。这三类点的稳定性按从小到大排列依次是极大值、鞍点、极小值,考虑实际运算中,浮点数运算都会有一定的误差,因此最终结果很大几率会落入极小值点,同时也有落入鞍点的概率。而对于极大值点,除非初始值就是极大值,否在几乎不可能到达极大值点。

为了从鞍点和极小值点中脱出,在梯度下降法的基础上衍生出了各式各样的改进算法,例如动态调整步长(即学习率),利用上一次结果的动量法,以及随机梯度下降法(Stochastic Gradient Descent, SGD)等等。实际上,这些优化算法在当前最火热的深度学习中也占据着一席之地,例如adagrad、RMSprop,Adam等等。而本文则将主要介绍一下随机梯度下降法。(达观数据 周颢钰)

随机梯度下降法主要是用来解决求和形式的优化问题,与上面需要优化的目标函数一致。其思想也很简单,既然对于求和式中每一项求梯度很麻烦,那么干脆就随机选其中一项计算梯度当作总的梯度来使用好了。

具体应用到上文中的目标函数

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

SSE是关于P和Q的多元函数,当随机选定U和I之后,需要枚举所有的k,并且对技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术,以及技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术求偏导数。整个式子中仅有技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术这一项与之相关,通过链式法则可知

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

在实际的运算中,为了P和Q中所有的值都能得到更新,一般是按照在线学习的方式选择评分矩阵中有分数的点对应的U、I来进行迭代。

值得一提的是,上面所说的各种优化都无法保证一定能找到最优解。有论文指出,单纯判断驻点是否是局部最优解就是一个NPC问题,但是也有论文指出SGD的解能大概率接近局部最优甚至全局最优。

另外,相比于利用了黑塞矩阵的牛顿迭代法,梯度下降法在方向上的选择也不是最优的。牛顿法相当于考虑了梯度的梯度,所以相对更快。而由于其线性逼近的特性,梯度下降法在极值点附近可能出现震荡,相比之下牛顿法就没有这个问题。

但是在实际应用中,计算黑塞矩阵的代价是非常大的,在这里梯度下降法的优势就凸显出来了。因此,牛顿法往往应用于一些较为简单的模型,如逻辑回归。而对于稍微复杂一些的模型,梯度下降法及其各种进化版本则更受青睐。(达观数据 周颢钰)

 

NO.3
基于Funk-SVD的改进算法

到这一步为止,我们已经能通过SGD找到一组分解方案了,然而对于填充矩阵的FunkSVD算法本身而言,目前这个形式是否过于简单了一些呢?

实际上,在Funk-SVD被提出之后,出现了一大批改进算法。本文将介绍其中某些经典的改进思路。

1

正则化

对于所有机器学习算法而言,过拟合一直是需要重视的一个问题,而加入正则化项则是防止过拟合的经典处理方法。对于上面的Funk-SVD算法而言,具体做法就是在损失函数后面加入一个L2正则项,即

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

其中,λ为正则化系数,而整个求解过程依然可以使用随机梯度下降来完成。

2

偏置

考察式子

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

可以发现这个式子表明用户U对物品 I 的评分全部是由U和I之间的联系带来的。然而实际上,有很多性质是用户或者物品所独有的。比如某个用户非常严苛,不论对什么物品给出的分数都很低,这仅仅与用户自身有关。

又比如某个物品非常精美,所有用户都会给出较高的分数,这也仅仅与物品自身有关。因此,只通过用户与物品之间的联系来预测评分是不合理的,同时也需要考虑到用户和物品自身的属性。于是,评分预测的公式也需要进行修正。不妨设整个评分矩阵的平均分为σ,用户U和物品I的偏置分别为技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术,那么此时的评分计算方法就变成了

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

同时,误差E除了由于M‘计算方式带来的变化之外,也同样需要加入U和I偏置的正则项,因此最终的误差函数变成了

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

3

隐式反馈

对于实际的应用场景中,经常有这样一种情况:用户点击查看了某一个物品,但是最终没有给出评分。

实际上,对于用户点击查看物品这个行为,排除误操作的情况,在其余的情况下可以认为用户被物品的描述,例如贴图或者文字描述等所吸引。这些信息我们称之为隐式反馈。事实上,一个推荐系统中有明确评分的数据是很少的,这类隐式数据才占了大头。

可以发现,在我们上面的算法当中,并没有运用到这部分数据。于是对于评分的方法,我们可以在显式兴趣+偏置的基础上再添加隐式兴趣,即

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

其中N(U)表示为用户U提供了隐式反馈的物品的集合。这就是svd++算法。

此时的损失函数也同样需要加上隐式兴趣的正则项,即

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

4

对偶算法

在上面的svd++中,我们是基于用户角度来考虑问题的,很明显我们同样可以基于物品的角度来考虑问题。具体来说就是

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

其中 N(I)表示为物品I提供了隐式反馈的用户的集合。类似地,在损失函数中也需要加上隐式兴趣的正则项。

在实际运用中,可以将原始的svd++得到的结果与对偶算法得到的结果进行融合,使得预测更加准确。然而相比起物品的数目,用户的数目往往是要高出几个量级的,因此对偶算法在储存空间和运算时间的开销上都将远高于原始的svd++,如何在效率和准确度之间找到平衡也是一个需要思考的问题。(达观数据 周颢钰)

 

NO.4
请因子分解机

矩阵分解的思想除了直接应用在分解评分矩阵上之外,其思想也能用在其他地方,接下来介绍的因子分解机(Factorization Machine,FM)就是一个例子。

对于经典的逻辑回归算法,其sigmoid函数中的项实际上是一个线性回归

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

在这里我们认为各个特征之间是相互独立的,而事实上往往有些特征之间是相互关联、相互影响的。因此,就有必要想办法捕捉这些特征之间的相互影响。简单起见,先只捕捉二阶的关系,即特征之间两两之间的相互影响。具体反映到回归公式上,即为

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

具体来说就是使用 技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术来描述技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术,对于w而言,其中可学习的项就对应了评分矩阵中有分值的项,而其他由于数据稀疏导致难以学习的项就相当于评分矩阵中的未评分项。这样一来,不仅解决了数据稀疏性带来的二阶权重学习问题,同时对于参数规模,也从技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术级别降到了O(kn)级别。

 

NO.5
与DNN的结合

深度学习无疑是近几年来最热门的机器学习技术。注意到隐语义模型中,隐含特征与深度学习中的embedding实际上是一回事,那么是否有可能借助DNN来帮助我们完成矩阵分解的工作呢?

实际上,在YouTube的文章《Deep neural networks for YouTube recommendations》中,就已经有了相关技术的应用。

技术干货丨想写出人见人爱的推荐系统,先了解经典矩阵分解技术

上图是YouTube初排模型的图示。具体的流程为:首先通过nlp技术,如word2vec,预训练出所有物品的向量I表示;然后对于每一条用户对物品的点击,将用户的历史点击、历史搜索、地理位置信息等信息经过各自的embedding操作,拼接起来作为输入,经过MLP训练后得到用户的向量表示U;而最终则是通过 softmax 函数来校验U*I的结果是否准确。

相比于传统的矩阵分解算法,使用DNN能为模型带来非线性的部分,提高拟合能力。另一方面,还可以很方便地加入各式各样的特征,提高模型的准确度。(达观数据 周颢钰)

 

NO.6
矩阵分解的优缺点

矩阵分解有如下优点:

  1. 能将高维的矩阵映射成两个低维矩阵的乘积,很好地解决了数据稀疏的问题;

  2. 具体实现和求解都很简洁,预测的精度也比较好;

  3. 模型的可扩展性也非常优秀,其基本思想也能广泛运用于各种场景中。

相对的,矩阵分解的缺点则有:

  1. 可解释性很差,其隐空间中的维度无法与现实中的概念对应起来;

  2. 训练速度慢,不过可以通过离线训练来弥补这个缺点;

  3. 实际推荐场景中往往只关心topn结果的准确性,此时考察全局的均方差显然是不准确的。

NO.7
总结

矩阵分解作为推荐系统中的经典模型,已经经过了十几年的发展,时至今日依然被广泛应用于推荐系统当中,其基本思想更是在各式各样的模型中发挥出重要作用。但是对于推荐系统来说,仅仅有一个好的模型是远远不够的。影响推荐系统效果的因素非常之多。想要打造一个一流的推荐系统,除了一个强大的算法模型之外,更需要想方设法结合起具体业务,不断进行各种尝试、升级,方能取得最终的胜利。

 

参考文献

【1】Simon Funk, http://sifter.org/~simon/journal/20061211.html

【2】Koren, Yehuda, Robert Bell, and Chris Volinsky. "Matrix factorization techniques for recommender systems." Computer42.8 (2009).

【3】Jahrer, Michael, and Andreas Töscher. "Collaborative filtering ensemble." Proceedings of the 2011 International Conference on KDD Cup 2011-Volume 18. JMLR. org, 2011.

【4】Rendle, Steffen. "Factorization machines." Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 2010.

【5】Covington, Paul, Jay Adams, and Emre Sargin. "Deep neural networks for youtube recommendations." Proceedings of the 10th ACM Conference on Recommender Systems. ACM, 2016.

Coursera上数据结构 & 算法课程(公开课)汇总推荐

Deep Learning Specialization on Coursera

数据结构和算法是基本功,Coursera上有很多数据结构和算法方面的经典课程,这里做个总结。

1. 普林斯顿大学 Sedgewick 教授的 算法1: Algorithms, Part I

这门算法课程已经开过很多轮,好评如潮 ,应该算得上是 Coursera 上的明星算法课程了,感兴趣的同学可以参考课程图谱上的旧版 课程评论,强烈推荐:

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms.

2. 普林斯顿大学 Sedgewick 教授的 算法2: Algorithms, Part II

系列课程,依然强烈推荐,感兴趣的同学可以参考早期课程的评价:http://coursegraph.com/coursera_algs4partII

“Part II较Part I在部分Programming Assignments上增加了timing和memory的难度,API100%不再意味着全部100%,这正是这门课程的精华之处:不是灌输算法知识,而是通过实际操作的过程让学员深入理解数据结构和算法调优在经济上的意义。个人很喜欢论坛上大家在Performance Thread里贴出自己的report然后交流优化心得的过程,很有圆桌会议的架势。这门课的教授Robert Sedgewick师出名门,是Knuth在斯坦福的博士。老爷子年岁已近70,一直活跃在论坛上解答和讨论问题,敬业程度让人赞叹。”

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms.

3. 斯坦福大学的 算法专项课程(Algorithms Specialization)

斯坦福大学的算法专项课程系列(Algorithms Specialization),这个系列包含4门子课程,涵盖基础的算法主题和高级算法主题,此前评价非常高,五颗星推荐,感兴趣的同学可以关注: Learn To Think Like A Computer Scientist-Master the fundamentals of the design and analysis of algorithms.

Algorithms are the heart of computer science, and the subject has countless practical applications as well as intellectual depth. This specialization is an introduction to algorithms for learners with at least a little programming experience. The specialization is rigorous but emphasizes the big picture and conceptual understanding over low-level implementation and mathematical details. After completing this specialization, you will be well-positioned to ace your technical interviews and speak fluently about algorithms with other programmers and computer scientists. About the instructor: Tim Roughgarden has been a professor in the Computer Science Department at Stanford University since 2004. He has taught and published extensively on the subject of algorithms and their applications.

可参考老版课程评论:Algorithms: Design and Analysis, Part 1Algorithms: Design and Analysis, Part 2

3.1 Divide and Conquer, Sorting and Searching, and Randomized Algorithms

The primary topics in this part of the specialization are: asymptotic ("Big-oh") notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).

3.2 Graph Search, Shortest Paths, and Data Structures

The primary topics in this part of the specialization are: data structures (heaps, balanced search trees, hash tables, bloom filters), graph primitives (applications of breadth-first and depth-first search, connectivity, shortest paths), and their applications (ranging from deduplication to social network analysis).

3.3 Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

3.4 Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

The primary topics in this part of the specialization are: shortest paths (Bellman-Ford, Floyd-Warshall, Johnson), NP-completeness and what it means for the algorithm designer, and strategies for coping with computationally intractable problems (analysis of heuristics, local search).

4. 北京大学的 程序设计与算法专项课程系列

据说是国内学生选择最多的中文程序设计课程,这个系列包含7门子课程,分别是计算导论与C语言基础, C程序设计进阶 ,C++程序设计, 算法基础, 数据结构基础, 高级数据结构与算法, 程序开发项目实践,最后一个项目实践课程联合腾讯公司设计一个实际的应用问题:搜索引擎设计。感兴趣的同学可以关注:

本专项课程旨在系统培养你的程序设计与编写能力。系列课程从计算机的基础知识讲起,无论你来自任何学科和行业背景,都能快速理解;同时我们又系统性地介绍了C程序设计,C++程序设计,算法基础,数据结构与算法相关的内容,各门课之间联系紧密,循序渐进,能够帮你奠定坚实的程序开发基础;课程全部配套在线编程测试,将有效地训练和提升你编写程序的实际动手能力。并通过结业实践项目为你提供应用程序设计解决复杂现实问题的锻炼,从而积累实际开发的经验。因此,我们希望本专项课程能够帮助你完成从仅了解基本的计算机知识到能够利用高质量的程序解决实际问题的转变。

5. 加州大学圣地亚哥分校的 数据结构与算法专项课程系列(Data Structures and Algorithms Specialization)

这个系列包含5门子课程和1门毕业项目课程,包括算法工具箱,数据结构 ,图算法,字符串算法 ,高级算法与算法复杂度,算法毕业项目 等,感兴趣的同学可以关注: Master Algorithmic Programming Techniques-Learn algorithms through programming and advance your software engineering or data science career

This specialization is a mix of theory and practice: you will learn algorithmic techniques for solving various computational problems and will implement about 100 algorithmic coding problems in a programming language of your choice. No other online course in Algorithms even comes close to offering you a wealth of programming challenges that you may face at your next job interview. To prepare you, we invested over 3000 hours into designing our challenges as an alternative to multiple choice questions that you usually find in MOOCs. Sorry, we do not believe in multiple choice questions when it comes to learning algorithms...or anything else in computer science! For each algorithm you develop and implement, we designed multiple tests to check its correctness and running time — you will have to debug your programs without even knowing what these tests are! It may sound difficult, but we believe it is the only way to truly understand how the algorithms work and to master the art of programming. The specialization contains two real-world projects: Big Networks and Genome Assembly. You will analyze both road networks and social networks and will learn how to compute the shortest route between New York and San Francisco (1000 times faster than the standard shortest path algorithms!) Afterwards, you will learn how to assemble genomes from millions of short fragments of DNA and how assembly algorithms fuel recent developments in personalized medicine.

注:本文首发“课程图谱博客”:http://blog.coursegraph.com ,同步发布到这里, 本文链接地址:http://blog.coursegraph.com/coursera上数据结构-算法课程-算法公开课-汇总推荐 http://blog.coursegraph.com/?p=736

A/B测试的数学原理与深入理解(达观数据 陈运文)

Deep Learning Specialization on Coursera

当面对众多选择时,如何选才能最大化收益(或者说最小化我们的开销)?比如,怎么选择最优的上班的路线才能使途中花费的时间最少?假设每天上下班路线是确定的,我们便可以在账本中记下往返路线的长度。

A/B测试便是基于数据来进行优选的常用方法,在记录多次上班路线长度后,我们便会从数据中发现到一些模式(例如路线A比路线B花的时间更少),然后最终一致选择某条路线。

当A/B测试遇到非简单情况时(如分组不够随机时,或用户量不够大到可以忽略组间差异,或不希望大规模A/B测试长期影响一部分用户的收益),该怎样通过掌握理论知识来更好的指导实践呢?本文尝试通过由浅入深的介绍,希望能够帮助大家对A/B测试有更加深入的理解。

NO.1
为什么需要A/B测试

任何问题,只要它的每个选项能够被多次进行测试,并且每个选项在被测试时都能返回固定的结果,那么它就能使用A/B测试技术来进行优化。在上述例子中,每天的上下班路线是确定的,所以我们能够在账本中记下往返路线的长度。

那么什么样的路线对于用户来说才是一个好的方案呢?是考虑路线A还是B?什么时候用户才有充分的数据去确定哪条线路是最好的?测试线路好与不好的最优策略又是什么?图1用形式化概括定义了问题。

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

图1 形式化定义的问题

在这个场景中,参与的用户正面临一个选择,根据他的决策会生成一个结果,而这个结果会对应一份给参与者的反馈。假设用户持续地暴露于这个决策,他应该怎么制定获得最大收益(或等效地说,最小成本)的策略?

图1中假定了用户多次处于需要进行选择的场景中,每一次进行决策都会达成一项结果,而这个结果会关联相应的反馈。在上下班这个例子中,假定他每天都需要上下班,而且他每次上下班都必须进行线路的选择,产出的结果是这次上下班中所有因素的结合体,反馈就是从这些因素中构建出来的(陈运文 达观数据)。

这是个浅显的例子,在互联网产品研发时,有大量类似的场景需要做出各种正确的选择,例如:

1

着陆页优化(Landing-page optimization)

在用户点击去往的页面(着陆页),如何获得最大的转化率(常用计算方法为有购买行为或深度网页交互行为的用户数占网站访问总用户数的比率)。决策要考虑到着陆页的形式和内容(要从可能已有的3或4个备选方案中做出选择),希望能够从候选集合中选出最好的着陆页,以能够吸引来访的用户,并让深度交互或者购买行为的概率最大化。

2

广告创意优化(Ad creative optimization)

在线广告提出了许多适合机器学习技术应用的挑战,其中之一就是如何选择广告的形式和内容。当我们决定将要进行广告展示,以及确定了广告的价格后,在这个广告位上选择放置什么广告呢?我们需要对大量的决策进行测试,选出正确的广告创意组合。

NO.2
什么是A/B测试

经常遇到的问题是,我们应该怎么评估各不相同的决策,以及应该采用哪些策略来测试我们的产出? A/B测试(A/B testing)就是其中之一的方法。A/B测试近年来很受欢迎,但大部分产品经理也许会简单地认为它只不过是一种包含两个组的实验,其实背后有更为复杂的数学统计理论知识。

具体细节
当进行A/B测试时,通常会采用两个(或多个)组:A组和B组。第一个组是对照组,第二个组会改变其中一些因素。就以着陆页优化为例,A组会展示现有的着陆页,B组会展示一个内容或者内容作了某些修改的新着陆页。A/B测试的目的就是尝试了解新的布局是否在统计上显著地改变了转化率。

特别值得注意的是,将用户分配到对应的组需要经过深思熟虑。对于A/B测试,我们可以高效地进行随机分组。当用户数量较大时,各组间用户行为可以假设是相同的(即组间没有偏差)。但是,这里有三个非常重要的关键点,是大家有必要进一步理解其数学理论原理的原因:

1
问题1
怎样验证两个组的用户的行为是无偏差、完全相同的
2
问题2

当两个组的用户行为不完全相同时(例如分组不够随机或者组内用户数量较小时),该如何设计AB测试以实现期望的验证结果

3
问题3

当用户基础行为受其他因素影响发生整体变化了呢?例如季节、时间波动、热度等因素影响下,怎样更好的剔除干扰来评估结果

NO.3
AB测试的统计理论

假设我们已经构建了两组数目较大的用户组,这些用户组的区别仅在于他们到达的着陆页。我们现在希望能测试两组间的转化率在统计上是否存在明显差异。由于样本量大,我们可以采用双样本单尾z-检验(two-sample, one-tailed z-test)。另外,对于较小的样本集合,我们可以依赖于t-检验。

z检验(z-test)是在数据是正态分布和随机抽样的假设下运行的,目的是验证测试集(B组)是否与该对照集(A组)有显著不同,但是如何执行这个测试呢?

假设有来自A组和B组中的每一组的5,000个样本。我们需要一个数学公式来说明我们的零假设(null hypothesis)——两组群体的转化率没有显著的正差异,和备择假设(或称对立假设,alternative hypothesis)——不同人群间的转化率确实存在着正差异。

我们可将采样转化率视为一个正态分布的随机变量,也就是说,采样的转化率是在正态分布下对转化率的一个观测。要了解这一点,请考虑从同一组中提取多个样本进行实验将导致略有不同的转化率。每当对某组进行抽样时,可获得群体转化率的估计,对于A组和B组都是如此。为此我们提出一个新的正态随机变量,它是A和B组的随机变量的组合,是差值的分布。让我们用X来表示这个新的随机变量,定义为:

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

其中,Xe表示实验组的转化率的随机变量,Xn表示对照组的转化率的随机变量。现在我们可以写出零假设和备择假设。零假设可以表示为:

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

这表示实验组和对照组是相同的。两个随机变量Xe和Xn分布在相同的群体平均值周围,所以我们的新随机变量X应该分布在0左右。我们的备择假设可以表示如下:

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

实验组的随机变量的期望值大于对照组的期望值;该群体的平均值较高。

我们可以在零假设的前提下,对X的分布执行单尾z检验,以确定是否有证据支持备择假设。为了达到这个目的,我们对X进行采样,计算标准分,并测试已知的显著性水平。

X的采样等效于运行两个实验,确定它们各自的转化率,并将对照组和实验组的转化率相减。按照标准分的定义,可以写作:

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

其中,P_experiment是实验组的转化率,P_control 是对照组的转化率,SE是转化率差值的标准差。

为确定标准误差,注意到转化过程是符合二项分布的,因此访问该网站可以被看作单次伯努利试验(single Bernoulli trial),而积极结果(完成转化)的可能性是未知的。

假设样本数量足够大,我们可以使用广泛采用的Wald方法(参考Lawrence D. Brown, T. Tony Cai, and Anirban DasGupta, “Confidence Intervals for a Binomial Proportion and Asymptotic Expansions,” The Annals of Statistics 30, no. 1 (2002): 160–201.)将该分布近似为正态分布。为了捕获特定转化率的不确定性,我们可以将标准误差(SE)写入实验组和对照组,其中p是转化的可能性,n是样本数量,具体如下:

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

从二项分布(np(1-p))的方差得到分子,而分母表示当采用更多的样本时,转化率的误差会随之下降。请注意正面结果的概率等同于转化率,并且因为两个变量的标准误差可以通过相加来合并,得到如下结果:

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

通过替换,可获得如下的z检验公式,这是一个符合二项分布的Wald(或正态)区间的公式:

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

z的值越大,反对零假设的证据就越多。为了获得单尾测试的90%置信区间,我们的z值将需要大于1.28。这实际上这是指在零假设(A组和B组的人口平均值是相同的)的条件下,等于或大于这个转化率差值的偶然发生的概率小于10%。

换句话说,在对照组和实验组的转化率来自具有相同平均值的分布的假设前提下,如果运行相同的实验100次,只会有10次具有这样的极端值。我们可以通过95%的置信区间,更严格的边界和更多的证据来反对零假设,这时需要将z值增加到1.65。

研究影响z大小的因素会带来很多有用的帮助。很显然,如果在一个给定的时间点从一个实验集和一个对照集中提取两个转化率,转化率的差值越大将导致z分数越大。因此就有了更多的证据表明两个集合分别来自不同的人群,而且这些人群带有不同的均值。然而样品的数量也很重要,如你所见,大量样本将导致总体较小的标准误差。这表明运行实验的时间越长,转化率的估算越准确。

NO.4
评估效果的代码实现

设想你在负责大型零售网站,设计团队刚刚修改了着陆页。每周有约20,000用户,并可以量化用户的转化率:即购买产品的百分比。设计团队向你保证新网站将带来更多的客户。但你不太确定,希望运行A / B测试来看看效果是否真的会提高。

用户在第一次访问网站时被随机分配到A组或B组,并在实验期间始终保留在该组中,实验结束时评估两组用户的平均转化率。统计结果是,新着陆页的平均转化率是0.002,而原先的着陆页的平均转化率是0.001。在着陆页永久更改为新设计之前,你需要知道这一增长是否足够明确。下面这段代码帮你回答这个问题。

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

这段代码获取实验中z的值,在上述参数条件下z值为1.827,超过了92%置信区间,但不在95%的区间内。可以说,从控制分布中抽取数据的概率小于0.08。因此在该区间内数据提升是显著的。我们应该否定零假设,接受备择假设,即组之间有差异,第二组具有较高的转化率。如果我们控制了用户组的所有其他方面,就意味着网站的新设计产生了积极的效果。

你应该能够从代码中看到转化率分布的标准误差对返回的z值有直接影响。 对给定的常数值p_experiment和p_control,两个组的SE越高,z的数值越小,结果就越不显著。还注意到由于SE的定义,z的数值与样本的数量具有直接关系,对于给定的转换概率也同样如此。图2展示了这种关系。

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

图2

图2 展示了A / B组的固定转化率,以及A / B组中的用户数量和z值之间的关系。 假设转化率不会随着我们收集更多数据而改变,我们需要每个组中大约3,000个用户达到70%的置信区间。 要达到80%的置信区间时需要每组约5000个用户,达到90%时需要 7500个用户,达到95%时需要12000个用户。

图2中可见对于两个组的给定转化率,测试组中的用户越多,备择假设的证据就越充分。直观上来看这很容易理解:当收集的数据越多,我们对结果越自信!我们也可以绘制一张类似的图,保持用户数量不变,改变组之间的差异。但必须注意,对正在关注的应用,不应该期望效果的大幅度变化。

 

NO.5
A/B测试方法的副作用和处理办法

对于非常小的效果变化,往往都需要创建相当大的对照组和测试组来实现AB测试,这个的代价往往是很大的。设想下在零售商场中,每天观察到的用户数量,往往需要很久的时间才能得出明显的结论。在实际业务应用中,会遇到的问题是:当你运行测试时整体运行的效果是受到很大影响的,因为必须有一半的用户处于效果不佳的实验组,或者有一半的用户处于效果不佳的对照组,而且你必须等待测试完成才能停止这种局面。

这是被称为探索利用难题(explore-exploit conundrum)的一个经典问题。我们需要运行次优方法,以探索空间,并找到效果更好的解决方案,而一旦找到了更好的解决方案,我们还需要尽快利用它们来实现效果提升。能否可以更快地利用新的解决方案,而不必等待测试完全完成呢?答案是肯定的。下面简单介绍下多臂赌博机(multi-armed bandit,MAB)的概念。

1

多臂赌博机的定义

多臂赌博机(multi-armed bandit,MAB)的名字来源于著名的赌博游戏角子赌博机(one-armed bandit)。对那些从没去过赌场的人,我们来做下解释:角子机(又称老虎机)是一个需要你拉杠杆(或摇臂)的赌博机器,根据机器展示的数值,你可能会得到一笔奖励,也可能(更大几率)得不到任何东西。和你想的一样,这些机器的设置都对庄家有利,所以能获的奖励的几率是非常非常小的。

多臂赌博机(理论上的)扩展了这种形式,想象你面对的是一堆角子赌博机,每个赌博机都被分配按照一个独立的概率进行奖励。作为一个玩家,你不知道在这些机器后的获奖概率,你唯一可以找到获奖概率的方法是进行游戏。你的任务是通过玩这些机器,最大限度地提高所获的奖励。那么你应该使用什么策略呢?

2

多臂赌博机策略

为了更严格地定义问题,我们通过数学形式化来表达,假设现在有k个赌博机,可观察到的每台的获奖概率等于p_k。假设一次只能拉动一个摇臂,并且赌博机只会按照它关联的概率机型奖励。这是一个设置了限定局数的有限次的游戏。在游戏期间任意时间点时,水平线H被定义为允许的剩余游戏的数量。

对所有机器用户会尝试最大化的获奖回报。在游戏中的任一时间点,我们都可以通过使用称为遗憾值(regret)来度量用户的表现。遗憾值的意思是,假设用户能在每一步选择最优的赌博机,得到的奖励和目前获得的实际奖励的差值。遗憾值的数学定义为:

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

其中T表示我们到目前为止进行过的步数,r_t表示在第t步获得的奖励,u_opt表示每一局从最优赌博机返回来的期望奖励。遗憾值的数值越低,策略越优。但因为这个度量值会受到偶然性的影响(奖励可能会被从最优赌博机选择中获得的期望奖励更高),我们可以选择使用遗憾值的期望值代替,定义为:

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

其中μ_t是在第t步从赌博机中获得的平均奖励(不可观测的)。因为第二项是来自所选策略的期望奖励,所以它将小于或等于来自最优策略(每一步都选择最优的赌博机)的期望奖励。

3

Epsilon优先方法

Epsilon优先(Epsilon first)是MAB策略中最简单的一种方式,它被认为和事先执行A/B测试方法具有同等意义。给定ε,执行探索空间操作的次数为(1 – ε) × N,其中N是游戏中总共的局数,剩余的次数都是执行后续探索的局数。

update_best_bandit算法会持续统计记录每一个赌博机的奖励收入和游戏局数。变best_bandit会在每一局结束进行更新,记录当前具有最高获奖概率的赌博机的编号,流程如下:

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

4

Epsilon贪婪

Epsilon贪婪(epsilon-greedy)策略中,ε表示我们进行探索空间的概率,和进行利用已知最优摇臂的事件互斥

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

该方法的特点:不需要等到探索阶段完成,才能开始利用有关赌博机的奖励表现的知识。但要小心,该算法不会考虑效果数据的统计意义。因此可能发生这样的情况:个别赌博机的奖励峰值导致后续的所有局游戏都错误地选择了这个赌博机(陈运文 达观数据)。

5

Epsilon递减

Epsilon递减(epsilon-decreasing)策略在实验开始阶段,会有一个很高的ε值,所以探索空间的可能性很高。ε值会随着水平线H上升而不断递减,致使利用似然知识的可能性更高。

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

需要注意这里有几种方法去来选择一个最优的速率来更新ε值,具体取决于赌博机的数量,以及他们各自进行奖励的权重。

6

贝叶斯赌博机

与A / B测试类似,贝叶斯赌博机(Bayesian bandits)假设每个赌博机的获奖概率被建模为获奖概率的分布。当我们开始实验时,每个赌博机都有一个通用的先验概率(任意赌博机的奖励比率初始都是同等的)。

在某一个赌博机上进行的局数越多,我们对它的奖励信息就了解越多,所以基于可能的奖励概率更新其获奖概率分布。当需要选择玩哪一个赌博机的时候,从获奖概率分布中采样,并选择对应样本中具有最高奖励比率的赌博机。图3提供了在给定时间内对三个赌博机所含信息的图形化表示。

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

图3

使用贝叶斯赌博机策略对三个赌博机的获奖概率信息进行建模。第1、2和3个赌博机的平均获奖率分别为0.1、0.3和0.4。 第1个赌博机具有较低的平均值而且方差也比较大,第2个赌博机具有较高的平均值和较小的方差,第3个赌博机具有更高的平均值和更小的方差。

可以看到关于赌博机的获奖概率分布的信息被编码为三个分布。每个分布具有递增的平均值和递减的方差。因此,我们不太确定奖励期望值为0.1的真实奖励率,最可靠的是奖励期望值为0.4的赌博机。因为赌博机的选择是通过对分布进行抽样来进行的,所以分布期望值是0.1的赌博机的摇臂也可能被拉动。这个事件会发生在第2个赌博机和第3个赌博机的采样样本奖励值异常小,而且第1个赌博机的采样样本异常大时,相应代码如下(陈运文 达观数据):

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

NO.6
总结

A/B测试和贝叶斯赌博机的各自的优点和局限是:两者有各自适用的场景,也验证的变量数量也各不相同,具体如下表。

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

此外,两个方法的收敛速度也很不一样。在A/B测试中是指获得统计意义,在贝叶斯赌博机中是指累积遗憾值不再增加。以本章最开始的网站优化为例,首先请注意,任何行为的改变可能是微小的(<0.01),而我们已经知道贝叶斯赌博机相比大的改变提升,需要更多的收敛时间。如果加了多种选择,在同一个实验中测试多种登陆页面,将更加会影响收敛速度。假如用户变化导致的底层分布变的比模型收敛更快呢?比如,季节趋势,销售或者其他因素可能会影响。

技术干货 | 如何选择上班路线最省时间?从A/B测试数学原理说起

显然,收集的数据越多,对效果的潜在变化的把握度就越高。当2个组划分本身就存在统计差异时,通过多臂赌博机而不是A/B测试的方法可以从概率上修正我们选择的分布。本文还重点介绍了z检验(z-test)的数学知识,因为其构成了A/B测试的统计理论基础。