作者归档:recommender

一文详解深度学习在命名实体识别(NER)中的应用

Deep Learning Specialization on Coursera

近几年来,基于神经网络的深度学习方法在计算机视觉、语音识别等领域取得了巨大成功,另外在自然语言处理领域也取得了不少进展。在NLP的关键性基础任务—命名实体识别(Named Entity Recognition,NER)的研究中,深度学习也获得了不错的效果。最近,笔者阅读了一系列基于深度学习的NER研究的相关论文,并将其应用到达观的NER基础模块中,在此进行一下总结,与大家一起分享学习。

1、NER 简介

NER又称作专名识别,是自然语言处理中的一项基础任务,应用范围非常广泛。命名实体一般指的是文本中具有特定意义或者指代性强的实体,通常包括人名、地名、组织机构名、日期时间、专有名词等。NER系统就是从非结构化的输入文本中抽取出上述实体,并且可以按照业务需求识别出更多类别的实体,比如产品名称、型号、价格等。因此实体这个概念可以很广,只要是业务需要的特殊文本片段都可以称为实体。

学术上NER所涉及的命名实体一般包括3大类(实体类,时间类,数字类)和7小类(人名、地名、组织机构名、时间、日期、货币、百分比)。

实际应用中,NER模型通常只要识别出人名、地名、组织机构名、日期时间即可,一些系统还会给出专有名词结果(比如缩写、会议名、产品名等)。货币、百分比等数字类实体可通过正则搞定。另外,在一些应用场景下会给出特定领域内的实体,如书名、歌曲名、期刊名等。

NER是NLP中一项基础性关键任务。从自然语言处理的流程来看,NER可以看作词法分析中未登录词识别的一种,是未登录词中数量最多、识别难度最大、对分词效果影响最大问题。同时NER也是关系抽取、事件抽取、知识图谱、机器翻译、问答系统等诸多NLP任务的基础。

NER当前并不算是一个大热的研究课题,因为学术界部分学者认为这是一个已经解决的问题。当然也有学者认为这个问题还没有得到很好地解决,原因主要有:命名实体识别只是在有限的文本类型(主要是新闻语料中)和实体类别(主要是人名、地名、组织机构名)中取得了不错的效果;与其他信息检索领域相比,实体命名评测预料较小,容易产生过拟合;命名实体识别更侧重高召回率,但在信息检索领域,高准确率更重要;通用的识别多种类型的命名实体的系统性能很差。

2. 深度学习方法在NER中的应用

NER一直是NLP领域中的研究热点,从早期基于词典和规则的方法,到传统机器学习的方法,到近年来基于深度学习的方法,NER研究进展的大概趋势大致如下图所示。

图1:NER发展趋势

在基于机器学习的方法中,NER被当作序列标注问题。利用大规模语料来学习出标注模型,从而对句子的各个位置进行标注。NER 任务中的常用模型包括生成式模型HMM、判别式模型CRF等。条件随机场(ConditionalRandom Field,CRF)是NER目前的主流模型。它的目标函数不仅考虑输入的状态特征函数,而且还包含了标签转移特征函数。在训练时可以使用SGD学习模型参数。在已知模型时,给输入序列求预测输出序列即求使目标函数最大化的最优序列,是一个动态规划问题,可以使用Viterbi算法解码来得到最优标签序列。CRF的优点在于其为一个位置进行标注的过程中可以利用丰富的内部及上下文特征信息。

图2:一种线性链条件随机场

近年来,随着硬件计算能力的发展以及词的分布式表示(word embedding)的提出,神经网络可以有效处理许多NLP任务。这类方法对于序列标注任务(如CWS、POS、NER)的处理方式是类似的:将token从离散one-hot表示映射到低维空间中成为稠密的embedding,随后将句子的embedding序列输入到RNN中,用神经网络自动提取特征,Softmax来预测每个token的标签。

这种方法使得模型的训练成为一个端到端的过程,而非传统的pipeline,不依赖于特征工程,是一种数据驱动的方法,但网络种类繁多、对参数设置依赖大,模型可解释性差。此外,这种方法的一个缺点是对每个token打标签的过程是独立的进行,不能直接利用上文已经预测的标签(只能靠隐含状态传递上文信息),进而导致预测出的标签序列可能是无效的,例如标签I-PER后面是不可能紧跟着B-PER的,但Softmax不会利用到这个信息。

学界提出了DL-CRF模型做序列标注。在神经网络的输出层接入CRF层(重点是利用标签转移概率)来做句子级别的标签预测,使得标注过程不再是对各个token独立分类。

2.1 BiLSTM-CRF

LongShort Term Memory网络一般叫做LSTM,是RNN的一种特殊类型,可以学习长距离依赖信息。LSTM 由Hochreiter &Schmidhuber (1997)提出,并在近期被Alex Graves进行了改良和推广。在很多问题上,LSTM 都取得了相当巨大的成功,并得到了广泛的使用。LSTM 通过巧妙的设计来解决长距离依赖问题。

所有 RNN 都具有一种重复神经网络单元的链式形式。在标准的RNN中,这个重复的单元只有一个非常简单的结构,例如一个tanh层。

图3:传统RNN结构

LSTM 同样是这样的结构,但是重复的单元拥有一个不同的结构。不同于普通RNN单元,这里是有四个,以一种非常特殊的方式进行交互。

图4:LSTM结构

LSTM通过三个门结构(输入门,遗忘门,输出门),选择性地遗忘部分历史信息,加入部分当前输入信息,最终整合到当前状态并产生输出状态。

图5:LSTM各个门控结构

应用于NER中的biLSTM-CRF模型主要由Embedding层(主要有词向量,字向量以及一些额外特征),双向LSTM层,以及最后的CRF层构成。实验结果表明biLSTM-CRF已经达到或者超过了基于丰富特征的CRF模型,成为目前基于深度学习的NER方法中的最主流模型。在特征方面,该模型继承了深度学习方法的优势,无需特征工程,使用词向量以及字符向量就可以达到很好的效果,如果有高质量的词典特征,能够进一步获得提高。

图6:biLSTM-CRF结构示意图

2.2 IDCNN-CRF

对于序列标注来讲,普通CNN有一个不足,就是卷积之后,末层神经元可能只是得到了原始输入数据中一小块的信息。而对NER来讲,整个输入句子中每个字都有可能对当前位置的标注产生影响,即所谓的长距离依赖问题。为了覆盖到全部的输入信息就需要加入更多的卷积层,导致层数越来越深,参数越来越多。而为了防止过拟合又要加入更多的Dropout之类的正则化,带来更多的超参数,整个模型变得庞大且难以训练。因为CNN这样的劣势,对于大部分序列标注问题人们还是选择biLSTM之类的网络结构,尽可能利用网络的记忆力记住全句的信息来对当前字做标注。

但这又带来另外一个问题,biLSTM本质是一个序列模型,在对GPU并行计算的利用上不如CNN那么强大。如何能够像CNN那样给GPU提供一个火力全开的战场,而又像LSTM这样用简单的结构记住尽可能多的输入信息呢?

Fisher Yu and Vladlen Koltun 2015 提出了dilated CNN模型,意思是“膨胀的”CNN。其想法并不复杂:正常CNN的filter,都是作用在输入矩阵一片连续的区域上,不断sliding做卷积。dilated CNN为这个filter增加了一个dilation width,作用在输入矩阵的时候,会skip所有dilation width中间的输入数据;而filter本身的大小保持不变,这样filter获取到了更广阔的输入矩阵上的数据,看上去就像是“膨胀”了一般。

具体使用时,dilated width会随着层数的增加而指数增加。这样随着层数的增加,参数数量是线性增加的,而receptive field却是指数增加的,可以很快覆盖到全部的输入数据。

图7:idcnn示意图

图7中可见感受域是以指数速率扩大的。原始感受域是位于中心点的1x1区域:

(a)图中经由原始感受域按步长为1向外扩散,得到8个1x1的区域构成新的感受域,大小为3x3;

(b)图中经过步长为2的扩散,上一步3x3的感受域扩展为为7x7;

(c)图中经步长为4的扩散,原7x7的感受域扩大为15x15的感受域。每一层的参数数量是相互独立的。感受域呈指数扩大,但参数数量呈线性增加。

对应在文本上,输入是一个一维的向量,每个元素是一个character embedding:

图8:一个最大膨胀步长为4的idcnn块

IDCNN对输入句子的每一个字生成一个logits,这里就和biLSTM模型输出logits完全一样,加入CRF层,用Viterbi算法解码出标注结果。

在biLSTM或者IDCNN这样的网络模型末端接上CRF层是序列标注的一个很常见的方法。biLSTM或者IDCNN计算出的是每个词的各标签概率,而CRF层引入序列的转移概率,最终计算出loss反馈回网络。

3. 实战应用

3.1 语料准备

Embedding:我们选择中文维基百科语料来训练字向量和词向量。

基础语料:选择人民日报1998年标注语料作为基础训练语料。

附加语料:98语料作为官方语料,其权威性与标注正确率是有保障的。但由于其完全取自人民日报,而且时间久远,所以对实体类型覆盖度比较低。比如新的公司名,外国人名,外国地名。为了提升对新类型实体的识别能力,我们收集了一批标注的新闻语料。主要包括财经、娱乐、体育,而这些正是98语料中比较缺少的。由于标注质量问题,额外语料不能加太多,约98语料的1/4。

3.2 数据增强

对于深度学习方法,一般需要大量标注语料,否则极易出现过拟合,无法达到预期的泛化能力。我们在实验中发现,通过数据增强可以明显提升模型性能。具体地,我们对原语料进行分句,然后随机地对各个句子进行bigram、trigram拼接,最后与原始句子一起作为训练语料。

另外,我们利用收集到的命名实体词典,采用随机替换的方式,用其替换语料中同类型的实体,得到增强语料。

下图给出了BiLSTM-CRF模型的训练曲线,可以看出收敛是很缓慢的。相对而言,IDCNN-CRF模型的收敛则快很多。

图9:BiLSTM-CRF的训练曲线

图10:IDCNN-CRF的训练曲线

3.3 实例

以下是用BiLSTM-CRF模型的一个实例预测结果。

图11:BiLSTM-CRF预测实例

4. 总结

最后进行一下总结,将神经网络与CRF模型相结合的CNN/RNN-CRF成为了目前NER的主流模型。对于CNN与RNN,并没有谁占据绝对优势,各有各的优点。由于RNN有天然的序列结构,所以RNN-CRF使用更为广泛。基于神经网络结构的NER方法,继承了深度学习方法的优点,无需大量人工特征。只需词向量和字向量就能达到主流水平,加入高质量的词典特征能够进一步提升效果。对于少量标注训练集问题,迁移学习,半监督学习应该是未来研究的重点。

ABOUT

88集团赠送38彩金作者

朱耀邦:达观数据NLP算法工程师,负责达观数据NLP基础模块的研究、优化,以及NLP算法在文本挖掘系统中的具体应用。对深度学习、序列标注、实体及关系抽取有浓厚兴趣。

达观数据王子豪:这5个例子,小学生都能秒懂分类算法

Deep Learning Specialization on Coursera
分类算法作为数据挖掘、机器学习中重要的研究领域,在新闻分类、黄反广告识别、情感分析、观点挖掘等应用实践中都有着广泛的应用。如何将朴素贝叶斯、决策树、支持向量机这些常见的分类算法通俗易懂地讲给对人工智能感兴趣的人?达观研究院的这篇分类算法科普文章,以日常生活为例子,让小学生都能秒懂分类算法。

试想,8岁的小明是你刚上小学的儿子,长得可爱,古灵精怪,对世界充满好奇。

这天饭后,刚写完家庭作业的小明看到你在书桌前对着电脑眉头紧锁,便跑了过来问你:“爸爸(妈妈),你在做什么呀?”。

身为算法工程师的你正为公司的一个分类项目忙得焦头烂额,听到小明的问话,你随口而出:“分类!”

“分类是什么?”

听到儿子的追问,你的视线终于离开屏幕,但想说的话还没出口又咽了回去……

分类是什么?

简单来说,分类就是对事物进行区分的过程和方法。

在你眼里乖巧的小明是一个好孩子,同时你也想确保他会在学校做一名“好学生”而不是“坏学生”。这里的区分“好学生”和“坏学生”就是一个分类任务,88集团赠送38彩金这点,达观研究院可以帮你回答小明的疑问。

K最邻近

“别和其他坏学生在一起,否则你也会和他们一样。”        —— 家长

这句话通常来自家长的劝诫,但它透露着不折不扣的近邻思想。在分类算法中,K最近邻是最普通也是最好理解的算法。它的主要思想是通过离待预测样本最近的K个样本的类别来判断当前样本的类别。

家长们希望孩子成为好学生,可能为此不惜重金购买学区房或者上私立学校,一个原因之一是这些优秀的学校里有更多的优秀学生。与其他优秀学生走的更近,从K最近邻算法的角度来看,就是让目标样本与其他正样本距离更近、与其他负样本距离更远,从而使得其近邻中的正样本比例更高,更大概率被判断成正样本。

 

朴素贝叶斯

“根据以往抓获的情况来看,十个坏学生有九个爱打架。”      —— 教导主任

说这句话的训导主任很有可能就是通过朴素贝叶斯算法来区分好、坏学生。

“十个坏学生有九个爱打架”就意味着“坏学生”打架的概率P(打架|坏学生)=0.9,假设根据训导处历史记录坏学生占学生总数P(坏学生)=0.1、打架发生的概率是P(打架)=0.09,那么这时如果发生打架事件,就可以通过贝叶斯公式判断出当事学生是“坏学生”的概率P(坏学生|打架)=P(打架|坏学生)×P(坏学生)÷P(打架)=1.0,即该学生100%是“坏学生”。

朴素贝叶斯算法成立的一个前提是满足特征间条件独立假设。假如教导主任还管学生早恋问题,那么他通过“打架”和“早恋”两种特征来判断学生的前提必须是——在已知学生“好坏”的情况下“打架”和“早恋”之间没有关联。这样的假设可能和实际情况不符合,但让训导主任判断起来更加简单粗暴。

决策树

“先看抽不抽烟,再看染不染头发,最后看讲不讲脏话。”  ——社区大妈

社区大妈经验丰富,有一套自己的判断逻辑。假设“抽烟”、“染发”和“讲脏话”是社区大妈认为的区分“好坏”学生的三项关键特征,那么这样一个有先后次序的判断逻辑就构成一个决策树模型。在决策树中,最能区分类别的特征将作为最先判断的条件,然后依次向下判断各个次优特征。决策树的核心就在于如何选取每个节点的最优判断条件,也即特征选择的过程。

而在每一个判断节点,决策树都会遵循一套IF-THEN的规则:

IF “抽烟” THEN -> “坏学生”

ELSE

IF “染发” THEN -> “坏学生”

ELSE IF “讲脏话” THEN -> “坏学生”

ELSE -> “好学生”

逻辑回归

“上课讲话扣1分,不交作业扣2分,比赛得奖加5分。”   ——纪律委员

班上的纪律委员既勤恳又严格,总是在小本本上记录同学们的每一项行为得分。在完成对每一项行为的评分后,纪律委员根据最终加总得到的总分来判断每位同学的表现好坏。

上述的过程就非常类似于逻辑回归的算法原理。我们称逻辑回归为一种线性分类器,其特征就在于自变量x和因变量y之间存在类似y=ax+b的一阶的、线性的关系。假设“上课讲话”、“不交作业”和“比赛得奖”的次数分别表示为x1、x2、和x3,且每个学生的基础分为0,那么最终得分y=-1*x1-2*x2+5*x3+0。其中-1、-2和5分别就对应于每种行为在“表现好”这一类别下的权重。

Sigmoid函数图像

对于最终得分y,逻辑回归还通过Sigmoid函数将其变换到0-1之间,其含义可以认为是当前样本属于正样本的概率,即得分y越高,属于“表现好”的概率就越大。也就是说,假如纪律委员记录了某位同学分别“上课讲话”、“不交作业”和“比赛得奖”各一次,那么最终得分y=-2-1+5=2,而对2进行Sigmoid变换后约等于0.88,即可知该同学有88%的概率为“好学生”。

支持向量机

“我想个办法把表现差的学生都调到最后一排。”  ——班主任

即使学生们再不情愿,班主任也有一万个理由对他们的座位作出安排。对于“坏学生”,一些班主任的采取的做法是尽量让他们与“好学生”保持距离,即将“坏学生”们都调到教室的最后一排。这样一来,就相当于在学生们之间画了一条清晰的分割界线,一眼就能区分出来。

支持向量机的思想就是如此。支持向量机致力于在正负样本的边界上找到一条分割界线(超平面),使得它能完全区分两类样本的同时,保证划分出的间隔尽量的大。如果一条分割界线无法完全区分(线性不可分),要么加上松弛变量进行适当的容忍,要么通过核函数对样本进行空间上的映射后再进行划分。对于班主任来讲,调换学生们的座位就相当于使用了核函数,让原本散落在教室里的“好”、“坏”学生从线性不可分变得线性可分了。

结束语

分类和分类算法的思想其实无处不在。而在实际工程中,分类算法的应用需要关注的地方还有很多。达观数据在中文文本分类方面拥有丰富的实践经验和心得。想了解这方面的内容,敬请期待下一篇文章《中文文本分类——你需要了解的10项关键内容》。

88集团赠送38彩金作者

王子豪:达观数据高级NLP算法工程师,负责达观数据文本挖掘和NLP算法的开发及应用,在文本分类、观点挖掘和情感分析等领域有丰富实践经验。

达观数据桂洪冠:如何省时省力验证模型效果?达观数据在线分层实验平台给你支招

Deep Learning Specialization on Coursera

背景

随着大数据和人工智能时代的到来,数据的驱动使得企业经营决策和精细化运营的效果指标的量化评估成为可能,企业的决策和运营也越来越离不开数据的支持。尤其是朝夕万变的互联网行业,产品创新和决策都需要快速得到用户反馈的数据去不断的迭代更新。 产品的新特性是否会受到用户的欢迎?新优化的模型和策略的线上效果如何?如何低成本的进行快速且量化的效果验证? 答案是A/B test实验

事实上,一个高效的A/B test在线实验平台已经成为各大互联网公司进行产品迭代和策略优化的标配工具。A/B测试是互联网公司实现数据驱动的基础,Microsoft、Google, Amazon、Facebook都在这方面做了大量的工作,腾讯、阿里、百度等国内主流互联网公司也纷纷各自构建了一套支持产品迭代和策略优化的A/B test在线实验平台。

达观数据的算法和工程团队每天都在持续不断地尝试各种算法模型的升级和策略优化,而这些算法模型和策略有的相互独立,有的相互影响。为了对这些模型和策略进行有效的量化效果评估,我们借鉴了谷歌的 ”Overlapping Experiment Infrastructure”中的思想搭建了达观数据在线分层实验平台。该实验平台可以支持同时运行多个并行实验,支持多种分流模式,支持自动灰度发布,支持实验效果的实时反馈和可视化(达观数据桂洪冠)。

分层实验模型

达观数据在线分层实验平台的设计借鉴了谷歌2010年在KDD上公布的分层实验框架,并在其基础上根据我们的应用特点进行了大量的裁剪。谷歌分层实验框架对实验空间进行了纵向横向两个维度的划分,其中纵向的划分是对应的概念,横向的划分对应的概念。是指流量的一个划分(指对一部分流量的独占),是指系统参数的一个子集,而实验是指在一个流量划分上,进行零个或多个参数的修改,并最后改变请求处理的过程。概念还是比较抽象,我们来看一个栗子:

如上图,流量先被分成两个域,左边是一个只有单一层的非重叠域,右边是一个三层的重叠域。在这种情况下,每个请求要么被分到非重叠域要么被分到重叠域。如果请求在非重叠域(上图左侧),那么请求最多在一个实验中(这个实验可以改变参数集合中的任意参数的值),如果请求在重叠域(上图右侧),那么请求可以通过三个实验层总共九个实验中。每个实验层可以根据不同的流量划分策略把流量分配到相应参数集的实验中。

下图是一个更具体的栗子,左侧是非重叠域,右侧分为3层,分别是UI层搜索结果层广告结果层

根据我们的实践经验,一般每一层划定一个批次实验,这个批次试验中有一个是基准实验,其它的属于对比实验,基准实验以及每个对比试验都对应一个试验参数集(达观数据桂洪冠)。

分层实验模型特性

分层实验模型具备如下一些特性:

特性1:纵向域划分,横向层划分。

特性2:相互关联的策略参数位于相同实验层,相互独立的策略参数位于不同实验层。

特性3:流量在不同实验层之间根据不同的分流策略被重新分配,不同层的实验流量是正交的。

特性4:不同实验层之间的实验相互独立。

特性5:模型的发布层(Launch Layers)可以实现实验流量的灰度发布直至全流量发布。

流量分配策略

分层实验模型常见的流量分配策略:

策略1:随机分配

优点是简单自然,缺点是用户的请求会在不同参数集的实验中“穿梭”,造成用户体验上的不一致性。

策略2:按照cookie或用户id取模进行分配

此种流量划分方式可以确保用户的请求被分配到固定的实验中,不会造成用户体验的不一致。

策略3:按照cookie+日期取模进行分配

这种方式是综合了cookie和日期的信息后再取模,采用这种方式的话,一个实验一天内圈定的cookie是固定的,但随着日期的变更会圈定不同的cookie。

策略4:按照业务字段进行分配

这种方式可以满足特定的实验流量要求,比如可以按照用户的地域来源取特定城市的用户流量,或者按照用户年龄取特定年龄段的用户流量。

策略5:hash查询串取模进行分配

这种方式使得相同的查询串请求可以分流到确定的实验上。

为了保证层与层之间实验流量的相互独立,上述基于取模的流量分配策略需要考虑实验所在层layerid的信息, 假设当前层有20个bucket分桶(实验参数),则当前流量在当前层的bucket = (f(cookieid, layerid) % 20),f是某个hash函数。

流量分流条件

在通过上述流量分配策略选择一部分流量后,分流条件(condition)通过仅分配特定条件的流量给实验或域,以达到更高效利用流量的目的。比如,一个实验仅仅改变来自日语的查询,那么实验配置中只抽取日语的流量。我们可以基于地区,语言,浏览器等信息设置流量抽样条件。有了分流条件,一个只使用“日语”流量的实验,和一个只使用英语流量的实验,可以使用相同的cookie取模。

灰度发布策略

灰度发布是一种常用的发布流量控制策略,是指在实验的过程中根据实验的效果逐步加大实验流量同时持续跟踪实验效果直至最终全量一个实验。分层实验模型是如何实现灰度发布策略的呢? 谷歌提出一个发布层的概念(Launch Layers)。在这个架构下,一个特性的评估和发布过程是类似如下过程的:

1)创建一个实验或是一组实验来评估特性。注意配置实验涉及指定分配类型和相关的分配参数(比如:cookie取模),分配条件,和特性相关的参数。

2)评估实验指标。根据实验结果,判断是否要进行新一轮的实验,即通过修改或创建新的实验,或甚至修改代码从根本上改变特性。

3)如果特性可以发布,就进入发布过程:创建一个新的发布层和发布层实验,逐步的放量这个实验,并最终删除发布完的发布层,然后将发布层实验的相关参数设为系统默认参数。

达观分层实验平台架构

达观分层实验平台主要由实验配置管理中心实验分析与展示中心以及在线服务系统三部分组成。

实验配置管理中心

实验人员可以在实验配置管理中心进行实验的创建启动暂停删除等操作。

实验创建:实验数据主要包括(但不限于)实验的名称(比如搜索Reranking实验)、实验的起始时间、实验owner、实验参数集、实验作用模块、流量分配等。其中实验起始时间定义了实验生效发生作用的时间范围,超过此时间实验自动结束并停止。实验参数集定义了需要测试的不同实验参数数据,每个实验参数对应实验的一个bucket分桶(比如rank_strategy=5, rank_strategy=6, rank_strategy=7分别对应实验的三个bucket)。每个实验都有一个唯一的实验ID。

实验流量分配:对实验选择流量划分策略(见前文介绍)。

实验启动:创建好的时间在达到实验设置的开始时间后自动启动,实验人员也可以对暂停的实验重新执行启动操作。

实验暂停:实验人员可以对执行中的实验执行暂停操作。

实验删除:实验人员可以删除已经停止的实验,正在执行的实验无法直接删除(需要先执行停止操作)

实验权限控制:实验的owner(创建者)对实验有启动、暂停、删除等权限,也即只能操作自己创建的实验。实验配置管理中心直接控制线上服务的模型和策略的执行,安全性就显得尤为重要。

实验持久化:实验的数据被存储到MySQL数据库中进行持久化。

实验分析与效果展示中心

实验分析和可视化效果展示是实验平台不可或缺的组成部分。在数据实时采集模块,实验ID以及实验参数数据(比如策略和模型参数)连同系统的业务日志数据一起被记录和采集。在这里可以实时查看到每个执行中实验(实验ID区分)的统计分析和效果对比数据,既可以对一个实验的不同参数集(实验bucket分桶)的结果数据进行横向对比(通常与基准实验作对比),也可以对实验基于时间维度的纵向效果作对比。

上图是达观数据推荐算法和某客户推荐算法时间维度纵向效果(点击率)对比。

在我们的实践中,通过对实验日志数据的实时采集和分析,可以实现对实验效果(比如CTR指标)进行准实时的对比分析和监控。如果发现实验(新算法策略)的效果指标出现异常,可以在实验配置管理中心及时调整实验参数或调整实验流程或停止实验(达观数据桂洪冠)。

在线服务系统(实验执行环境)

在线服务系统是实验执行的环境。在线服务系统加载了一个实验平台客户端组件,该组件主要有2个职责:

职责1:定时从数据库中同步实验数据信息

职责2:实验流量决策。对每个请求流量,根据实验的流量划分策略进行bucket分桶计算,获取对应bucket的实验参数数据(策略和模型参数)。请求携带被分配的实验参数数据流入线上服务模块。

各线上服务模块从请求中获取自己关心的实验参数数据进行相应的实验,并在记录日志时把实验ID和参数数据一同写入。

总结

本文以谷歌2010年发布的分层实验框架为参考,阐述了分层实验模型的域、层、实验等基本概念,进一步分析了分层模型的基本特性、实验流量划分策略、分流条件以及灰度发布方法等内容。然后,重点介绍了达观数据分层实验平台架构的实验配置中心、效果分析与展示中心、在线服务系统(实验执行环境)等主要模块,描述了从实验创建到实验执行再到实验结果分析的全过程。

达观数据分层实验平台同时运行着数十个面向不同客户的多个系统应用的策略和模型迭代优化实验,已经成为公司基础平台体系架构中非常重要的组成部分。

未来展望

未来我们希望把达观数据分层实验平台做成开放的一站式实验服务平台,把我们的平台实验能力输出给更多的客户和合作伙伴,大家基于这个平台相互学习合作共赢。

参考文献

1.Diane Tang, Ashish Agarwal, Deirdre O’Brien, Mike Meyer   Overlapping Experiment Infrastructure: More, Better, Faster Experimentation

2.阿里妈妈大规模在线分层实验实践http://www.infoq.com/cn/articles/alimama-large-scale-online-hierarchical-experiment/

88集团赠送38彩金作者

桂洪冠,达观数据联合创始人,中国计算机学会CCF会员,自然语言处理技术专家。在参与创办达观数据前,曾在腾讯文学、阿里巴巴、新浪微博等知名企业担任数据挖掘高级技术管理工作。桂洪冠在数据技术领域拥有6项国家发明专利,中国科学技术大学计算机硕士学位。在大数据架构与核心算法以及文本智能处理等领域有深厚的积累和丰富的实战经验。

“达人”计划丨达观数据2019届校园招聘正式启动

Deep Learning Specialization on Coursera

一 Who we are

用理解分析情景

用热诚驱动革新

用AI开拓未来

为有志于在人工智能NLP领域发展的同学

提供一条有趣、钱多、目标明确的赛道

为客户提供文本智能处理解决方案

以一流文本挖掘技赋能企业转型

AI趋势中一起破浪前行!

二 招聘岗位

AI算法工程师
自然语言处理,搜索算法,推荐算法,计算机视觉。
软件开发工程师
python后端开发、java后端、大数据开发方向;docker、k8s、自动化运维方向。
前端开发工程师
开发公司官网、移动端产品,实现业务功能和交互效果,向全栈工程师发展。
AI行业研究员
对相关行业和上市公司进行持续地跟踪和深入研究,把握行业走向和周期运行趋势。
产品经理(B端)
需求收集、产品设计、文档撰写、竞品分析,持续优化产品的用户体验,推进产品市场化。

三 培养计划

大牛带教

1V1导师制,入职不孤单,搬砖不迷茫
学无止境

达观大讲堂(内部达人、外部大咖每周分享,干货满满or趣味与脑洞向topic,工作生活两不误)
神秘组织

达模院(季度之星、最佳新人、最佳成长等季度奖项,等你来pick)
打怪升级

每年两次公开透明的晋升机会,9级职级体系,不断进阶
生活保障走心的生日礼物和节日福利,实用派or文艺派,兼容个性化需求;跨组团建基金、聚餐经费,每季度请花完预算,随你到处浪;补充医疗保险、年终多薪、项目奖金、出差补贴、兴趣club、人生大事红包
一夜暴富

优秀达人的股票期权计划

达观风采

四 招聘流程

空中宣讲        10月最后一周简历投递  2018.10-2018.12笔试面试  2018.10-2019.01

录用通知  2018.11-2019.02

实习阶段  2019.01-毕业日期

正式入职      以毕业时间为准

2018年10月,空中宣讲会将登陆直播平台,关注达观数据官网、微信公众号、知乎专栏,获取具体时间与直播链接,

参与互动,

更有干货满满的人工智能礼包相送~

五 投递渠道

快来51job、智联招聘、BOSS直聘、实习僧、大街网搜索 达观数据 投递校招类岗位或直接发送简历至hr@datagrand.com

邮件标题:姓名-投递岗位-学校-专业-毕业年月

加入官方校招qq群:931328675

HR小姐姐们会尽快联系大家~

达观数据曾彦能:如何用深度学习做好长文本分类与法律文书智能化处理

Deep Learning Specialization on Coursera

在NLP领域中,文本分类舆情分析等任务相较于文本抽取,和摘要等任务更容易获得大量标注数据。因此在文本分类领域中深度学习相较于传统方法更容易获得比较好的效果。正是有了文本分类模型的快速演进,海量的法律文书可以通过智能化处理来极大地提高效率。我们今天就来分析一下当前state of art的文本分类模型以及他们在法律文书智能化中的应用。

文本分类领域走过路过不可错过的深度学习模型主要有FastText,TextCNN,HAN,DPCNN。本文试图在实践之后总结一下这些这些分类模型的理论框架,把这些模型相互联系起来,让大家在选择模型与调参的时候能有一些直觉与灵感。在深度学习这个实践为王的领域常有人质疑理论理论无用,我个人的感受是理论首先在根据数据特征筛选模型的时候非常有用,其次在调参的过程中也能大幅提升效率,更重要的是调不出结果的时候,往往脑海里的那一句“这个模型不应该是这样的结果”,以及“这不科学”提供了坚持方向信心。

一、文本分类模型详解

1. FastText

其中FastText结构特别简单,对于速度要求特别高场合适用,他把一篇文章中所有的词向量(还可以加上N-gram向量)直接相加求均值,然后过一个单层神经网络来得出最后的分类结果。很显然,这样的做法对于复杂的文本分类任务来说丢失了太多的信息。FastText的一种简单的增强模型是DAN,改变在于在词向量平均完成后多叠了几层全连接神经网络。对应地,FastText也可以看成是DAN全连接神经网络层数为1的的一种特例。

图1 2层DAN网络

需要特别注意的是,对于不加n-gram向量的FastText模型,他不可能去分辨否定词的位置,看下面的两句话:

我不喜欢这类电影,但是喜欢这一个。

我喜欢这类电影,但是不喜欢这一个。

这样的两句句子经过词向量平均以后已经送入单层神经网络的时候已经完全一模一样了,分类器不可能分辨出这两句话的区别,只有添加n-gram特征以后才可能有区别。因此,在实际应用的时候需要对你的数据有足够的了解。

2. TextCNN

TextCNN相较于fastText模型的结构会复杂一些,在2014年提出,他使用了卷积 + 最大池化这两个在图像领域非常成功的好基友组合。我们先看一下他的结构。如下图所示,示意图中第一层输入为7*5的词向量矩阵,其中词向量维度为5,句子长度为7,然后第二层使用了3组宽度分别为2、3、4的卷积核,图中每种宽度的卷积核使用了两个。

其中每个卷积核在整个句子长度上滑动,得到n个激活值,图中卷积核滑动的过程中没有使用padding,因此宽度为4的卷积核在长度为7的句子上滑动得到4个特征值。然后出场的就是卷积的好基友全局池化了,每一个卷积核输出的特征值列向量通过在整个句子长度上取最大值得到了6个特征值组成的feature map来供后级分类器作为分类的依据。

图2 TextCNN结构

我们知道图像处理中卷积的作用是在整幅图像中计算各个局部区域与卷积核的相似度,一般前几层的卷积核是可以很方便地做可视化的,可视化的结果是前几层的卷积核是在原始输入图像中寻找一些简单的线条。NLP中的卷积核没法做可视化,那么是不是就不能理解他在做什么了呢,其实可以通过模型的结构来来推断他的作用。因为TextCNN中卷积过后直接就是全局max pooling,那么它只能是在卷积的过程中计算与某些关键词的相似度,然后通过max pooling层来得出模型关注那些关键词是否在整个输入文本中出现,以及最相似的关键词与卷积核的相似度最大有多大。我们假设中文输出为字向量,理想情况下一个卷积核代表一个关键词,如下图所示:

图3 TextCNN卷积核的意义示意图

比如说一个2分类舆情分析任务中,如果把整个模型当成一个黑箱,那么去检测他的输出结果,会发现这个模型对于输入文本中是否含有“喜欢”,“热爱”这样的词特别敏感,那么他是怎么做到的呢?整个模型中能够做到遍历整个句子去计算关键词相似度的只有卷积的部分,因为后面直接是对整个句子长度的max pooling。但是因为模型面对的是字向量,并不是字,所以他一个卷积核可能是只学了半个关键词词向量,然后还有另外的卷积核学了另外半个关键词词向量,最后在分类器的地方这些特征值被累加得到了最终的结果。

TextCNN模型最大的问题也是这个全局的max pooling丢失了结构信息,因此很难去发现文本中的转折关系等复杂模式,TextCNN只能知道哪些关键词是否在文本中出现了,以及相似度强度分布,而不可能知道哪些关键词出现了几次以及出现这些关键词出现顺序。假想一下如果把这个中间结果给人来判断,人类也很难得到对于复杂文本的分类结果,所以机器显然也做不到。针对这个问题,可以尝试k-max pooling做一些优化,k-max pooling针对每个卷积核都不只保留最大的值,他保留前k个最大值,并且保留这些值出现的顺序,也即按照文本中的位置顺序来排列这k个最大值。在某些比较复杂的文本上相对于1-max pooling会有提升。

3. HAN(Hierarchy Attention Network)

相较于TextCNN,HAN最大的进步在于完全保留了文章的结构信息,并且特别难能可贵的是,基于attention结构有很强的解释性。

他的结构如下图所示:

图4 HAN结构

输入词向量序列后,通过词级别的Bi-GRU后,每个词都会有一个对应的Bi-GRU输出的隐向量h,再通过uw向量与每个时间步的h向量点积得到attention权重,然后把h序列做一个根据attention权重的加权和,得到句子summary向量s2,每个句子再通过同样的Bi-GRU结构再加attention得到最终输出的文档特征向量v向量,然后v向量通过后级dense层再加分类器得到最终的文本分类结果。模型结构非常符合人的从词->句子->再到篇章的理解过程。

最重要的是该模型在提供了更好的分类精度的情况下,可视化效果非常好。同时在调参过程中,我们发现attention部分对于模型的表达能力影响非常大,整个模型在所有位置调整L2-Loss对模型表达能力带来的影响远不如在两处attention的地方大,这同时也能解释为什么可视化效果比较好,因为attention对于模型的输出贡献很大,而attention又恰恰是可以可视化的。

下面我们来看一下他在法律领域罪名预测任务上的可视化效果。下面的可视化的结果并不是找了极少数效果好的,而是大部分情况下模型的可视化能够解释他的输出。需要注意的是,此处为了让不太重要句子中相对重要的词并不完全不可见,词的亮度=sqrt(句子权重)*词权重。

在非常长的文本中,HAN觉得中间那些完全是废话,不如那句“公诉机关认为”有用,就放弃了。

图5 HAN attention可视化1

如下图所示,模型虽然在文本第二行中看到了窃取的字样,但是他认为这个案件中主要的事件是抢劫,这就是保留文本结构的好处。

图6 HAN attention可视化2

可以看到并不是所有的深度学习模型都是不可以理解的,这种可解释性也会给实际应用带来很多帮助。

4 DPCNN

上面的几个模型,论神经网络的层数,都不深,大致就只有2~3层左右。大家都知道何凯明大神的ResNet是CV中的里程碑,15年参加ImageNet的时候top-5误差率相较于上一年的冠军GoogleNet直接降低了将近一半,证明了网络的深度是非常重要的。

图7 ImageNet历年冠军

那么问题来了,在文本分类领域网络深度提升会带来分类精度的大幅提升吗?我们在一些比较复杂的任务中,以及数据量比较大(百万级)的情况下有提升,但不是ResNet那种决定性的提升。

DPCNN的主要结构如下图所示:

图8 DPCNN结构

从词向量开始(本文的重点在于模型的大结构,因此不去详解文中的region embedding部分,直接将整个部分认为是一种词向量的输出。)先做了两次宽度为3,filter数量为250个的卷积,然后开始做两两相邻的max-pooling,假设输入句子长度padding到1024个词,那么在头两个卷积完成以后句子长度仍然为1024。在block 1的pooling位置,max pooling的width=3,stride=2,也即序列中相邻的3个时间步中每一维feature map取这三个位置中最大的一个留下,也即位置0,1,2中取一个最大值,然后,移动2个时间步,在2,3,4时间步中取一次max,那么pooling输出的序列长度就是511。

后面以此类推,序列长度是呈指数级下降的,这也是文章名字Deep Pyramid的由来。然后通过两个卷积的非线性变换,提取更深层次的特征,再在输出的地方叠加上未经过两次卷积的quick connection通路(ResNet中使得深层网络更容易训练的关键)。因为每个block中的max pooling只是相邻的两个位置做max-pooling,所以每次丢失的结构信息很少,后面的卷积层又能提取更加抽象的特征出来。所以最终模型可以在不丢失太多结构信息的情况下,同时又做了比较深层的非线性变换。

我们实际测试中在非线性度要求比较高的分类任务中DPCNN会比HAN精度高,并且由于他是基于CNN的,训练速度比基于GRU的HAN也要快很多。

二、法律文书智能化应用

达观数据在法律文书智能化处理中也应用了上面的几个模型,并在此基础上做法律行业针对性的优化。在刚刚结束的“法研杯”法律人工智能大赛中达观数据代表队取得了单项三等奖的成绩。

以裁判文书智能化处理为例,达观数据可以通过上述的文本分类器根据一段犯罪事实来向法律工作者推荐与描述的犯罪事实相关的罪名,法律条文,甚至是刑期的预测等。

下面以裁判文书网的一篇裁判文书为例,我们截取其中的犯罪事实部分文字,输入模型。模型会根据输入的文字判断此段分类事实对应的罪名,并且高亮出犯罪事实中的关键内容。

截取裁判文书网中的犯罪事实部分:

图9 裁判文书样例

输入模型:

“公诉机关指控:2017年6月30日22时左右,被告人耿艳峰醉酒驾驶冀T×××××号比亚迪小型轿车沿东孙庄村东水泥路由西向东行驶,行至事发处,与对向被告人孙汉斌无证醉酒驾驶无牌二轮摩托车发生碰撞。造成两车不同程度损坏,孙汉斌受伤的道路交通事故。经衡水市公安局物证鉴定所检验:耿艳峰血液酒精含量为283.11mg/lOOmL;孙汉斌血液酒精含量为95.75mg/mL。经武强县交通警察大队认定:耿艳峰、孙汉斌均负此事故的同等责任。”

得到结果:

图10 模型输出结果

模型会输出预测的罪名以及相关法条的推荐结果,能够极大地提高律师的效率。并且模型还能将关键的句子以及词高亮出来给律师进一步仔细审阅提供方便。

目前在刑法相关的大量样本上罪名预测与相关法条推荐的准确率在90%左右。刑期由于存在不同年代不同地区存在一些差异,目前模型的输出结果还不能特别直观地给出评估。

三、总结

目前state of the art的深度学习文本发分类模型在十万~百万级以上的数据上已经能取得相当不错的效果,并且也有一些可解释性非常强的模型可用。要在实际业务中把文本分类模型用好,除了像文中深入分析理论以外,在大量的业务实践中总结经验也是必不可少的。达观在裁判文书处理等实际任务上实测输出结果也非常不错,并且达观的深度学习文本分类技术也会在各个业务应用中不断优化升级,希望能为法律行业的智能化以及效率优化作出一些贡献。

参考文献:

1.Joulin, Armand, et al. "Bag of Tricks forEfficient Text Classification." Proceedings of the 15th Conferenceof the European Chapter of the Association for Computational Linguistics:Volume 2, Short Papers. Vol. 2. 2017.

2.Iyyer, Mohit, et al. "Deep unorderedcomposition rivals syntactic methods for text classification." Proceedingsof the 53rd Annual Meeting of the Association for Computational Linguistics andthe 7th International Joint Conference on Natural Language Processing (Volume1: Long Papers). Vol. 1. 2015.

3.Kim, Yoon. "Convolutional Neural Networksfor Sentence Classification." Proceedings of the 2014 Conferenceon Empirical Methods in Natural Language Processing (EMNLP). 2014.

4.Yang, Zichao, et al. "Hierarchicalattention networks for document classification." Proceedings of the2016 Conference of the North American Chapter of the Association forComputational Linguistics: Human Language Technologies. 2016.

5.Johnson, Rie, and Tong Zhang. "Deeppyramid convolutional neural networks for text categorization." Proceedingsof the 55th Annual Meeting of the Association for Computational Linguistics(Volume 1: Long Papers). Vol. 1. 2017.

88集团赠送38彩金作者

曾彦能:达观数据NLP算法工程师,负责达观数据NLP深度学习算法的研究、优化,以及在文本挖掘系统中的具体应用。对文本分类,序列标注模型有深入的研究。曾作为主要成员之一代表达观数据参加2018中国"法研杯" 法律智能挑战赛获得单项三等奖。

受限玻尔兹曼机原理及在推荐系统中的应用(达观数据于敬)

Deep Learning Specialization on Coursera

深度学习相关技术近年来在工程界可谓是风生水起,在自然语言处理、图像和视频识别等领域得到极其广泛的应用,并且在效果上更是碾压传统的机器学习。一方面相对传统的机器学习,深度学习使用更多的数据可以进行更好的扩展,并且具有非常优异的自动提取抽象特征的能力。

另外得益于GPU、SSD存储、大容量RAM以及大数据分布式计算平台等的快速发展,海量数据的处理能力大幅度提升。同时,“千人千面”的个性化推荐系统已经融入到我们的日常生活的方方面面,并且给企业带来了巨大的收益。智能推荐系统本质上是对原始的用户行为数据进行深入地分析和挖掘,得到用户的兴趣偏好,进行精准推荐。所以,将深度学习和推荐系统相结合也成为了工业界的研究热点,Google、Facebook、Netflix等公司很早就开始研究基于深度学习的推荐系统,并且取得了显著的效果提升。(达观数据 于敬)

达观数据目前服务的公司有几百家,所提供的个性化推荐服务,不仅给企业带来了巨大的经济收益,同时大大提升了用户的粘性和活跃度,为企业的长远发展提供持续且高质量的技术支撑。当然这背后离不开达观数据多年来在个性化推荐算法上的持续打磨和对技术的精益求精,离不开在推荐效果优化上积累的丰富宝贵经验。本文选取了达观推荐系统众多推荐算法的其中之一:受限玻尔兹曼机(Restricted Boltzmann Machine,RBM),进行详细介绍。主要包括三部分:RBM介绍、RBM的数学原理、RBM在推荐系统中的应用。

一、RBM介绍

RBM和Netflix

提到基于RBM的推荐系统,不得不提Netflix竞赛。2006年,Netflix公司为了提升推荐效果,悬赏百万美元组织了一场竞赛,让大家穷尽所能以使其推荐算法的效果能够提升10%以上。在竞赛的后半程,RBM异军突起。当时以SVD++为核心的各种模型几乎已经陷入了僵局,很多人在此基础上加了pLSA、LDA、神经元网络算法、马尔可夫链、决策树等等,但效果提升并不明显,各个参赛队伍基本上进入到了比拼trick与融合模型数据的体力活阶段了。

但是,RBM的出现,把整个竞赛推进到了一个新的台阶。最终在2009年,“鸡尾酒”团队将上百个模型进行融合以10.05%的结果获得了此次竞赛的终极大奖。但是Netflix后来的线上系统并没有采用如此复杂的全套算法,而是仅仅应用了最核心的两个算法,其中就有受限玻尔兹曼机,另外一个就是耳熟能详的奇异值分解。

RBM的层次结构

RBM是一种可用随机神经网络来解释的概率图模型,主要用于协同过滤、降维、分类、回归、特征学习和主题建模。RBM包括两层,第一个层称为可见层,第二个层称为隐藏层。

图 1 RBM两层结构

如图1所示,每个圆圈称为节点,代表一个与神经元相似的单元,而运算就在这些节点中进行。每一个神经元是一个二值单元,也就是每一个神经元的取值只能等于0或1。节点之间的连接具有如下特点:层内无连接,层间全连接。

RBM和BM的不同之处就在于:BM允许层内节点连接,而RBM不允许。这就是受限玻尔兹曼机中受限二字的本意。每一个节点对输入数据进行处理,同时随机地决定是否继续传输输入数据,这里的“随机”是指改变输入数据的系数是随机初始化的。每个可见层的节点表示有待学习数据集合中一个物品的一个低层次特征。

图 2 输入数据通过节点的过程

接下来看一下单个输入x是如何通过这个两层网络的,如图2所示。在隐藏层的节点中,x和一个权重w相乘,再和所谓的偏差b相加。这两步的结果输入到一个激活函数中,进而得到节点的输出,也就是对于给定输入x,最终通过节点后的信号强度。如果用公式表示的话,即:

sigmoid函数是神经网络中常用的激活函数之一,其定义为:

接下来看看多项输入节点是如何整合到隐藏节点中的,如图4所示。每个输入x分别与各自的权重w相乘,再将结果求和后与偏差b想加,得到结果后输入到激活函数中,最后得到节点的输出值a。

图 4 多个输入通过一个隐藏节点的过程

由于可见层的所有节点的输入都会被传送到隐藏层中的每个节点,所以RBM可以被定义成一种对称二分图。如图5所示,当多个输入通过多个隐藏节点时,在隐藏层的每个节点中,都会有 x和权重w相乘,有4个输入,而每个输入x会有三个权重,最终就有12个权重,从而可以形成一个行数等于输入节点数、列数等于输出节点数的权重矩阵。隐藏层的每个节点接收4个可见层的输入与各自权重相乘后的输入值,乘积之和与偏差值b相加,再经过激活运算后得到隐藏层每个节点的输出a。

图 5 多个输入通过多个隐藏节点的过程

图 5 多个输入通过多个隐藏节点的过程

再进一步,如果是想构建一个二层的深度神经网络,如6所示,将第一隐藏层的输出作为第二隐藏层的输入,然后再通过不定数量的隐藏层,最终就可以到达分类层。(达观数据 于敬)

图 6 多隐藏层的处理过程

图 6 多隐藏层的处理过程

RBM的重构

这里介绍下RBM在无监督情况下如何重构数据的,其实就是在可见层和第一隐藏层之间多次进行正向和反向传递,但并不涉及更深的网络结构。在重构阶段,第一隐藏层的激活值作为反向传递的输入。这些输入值和相应的权重相乘,然后对这些乘积求和后再与偏差相加,得到的结果就是重构值,也就是原始输入x的近似值。

图 7 RBM重构过程

由于RBM的初始权重是随机初始化的,所以重构值与原始输入之间的差别往往很大。r值与输入值之差定义为重构误差,经由反向传递来不断修正RBM的权重,经过不断迭代,可以使得重构误差达到最小。

RBM在正向传递过程中根据输入值来计算节点的激活值,也就是对输入x进行加权后得到输出为a的概率p(a|x;w)。 而在反向传递时,激活值则变成输入,输出值变成了原始数据的重构值,也就是RBM在估计激活值为a时而输入值为x的概率p(x|a;w),激活值的权重w和正向传递中的一样。最终两个过程相结合,得到输入 为x 和激活值为 a 的联合概率分布p(x, a)。

重构不同于平时所说的回归、分类。重构是在预测原始输入数据的概率分布,同时预测许多不同点的值,这就是生成学习。RBM用KL(Kullback Leibler)散度来衡量预测的概率分布与基准分布之间的距离。

KL散度衡量的是两条曲线下方不重叠区域的面积,RBM的优化算法就是要最小化这个面积,从而使得权重在与第一隐藏层的激活值相乘后,可以得到与原始输入尽可能近似的结果。如图7所示,左半边是一组原始输入的概率分布曲线p,另外一个是重构值的概率分布曲线q,右半边的图则显示了两条曲线之间的差异。

图 8 RBM重构过程中误差表示

在整个重构过程中,RBM会根据重构误差反复的迭代计算,以尽可能准确地学习出原始值,最终看上去两条概率分布曲线会尽可能地逼近,如图8所示。

图 9 RBM概率密度曲线的逼近

利用RBM的堆叠可以构造出深层的神经网络模型——深度置信网络(Deep Belief Net, DBN),感兴趣的话可以查阅相关资料深入了解。在处理无监督学习问题时,使用一定的数据集合来训练网络,设置下可见层节点的值匹配下数据集合中的值。然后使用训练好的网络,对未知数据进行计算就可以进行分类。(达观数据 于敬)

二、RBM的数学原理

在RBM中,有如下性质:当给定可见层节点的状态时,隐藏层各节点之间是否激活是条件独立的;反之当给定隐藏层节点的状态时,可见层各节点之间是否激活也是条件成立的。

图 10 RBM的网络结构

图10是一个RBM的网络结构示意图,其中:

:分别表示可见层和隐藏层的神经元数量;

:可见层的状态向量,表示可见层中第个神经元的状态;

:可见层的状态向量,表示隐藏层中第个神经元的状态;

:可见层的偏置向量,表示可见层中第个神经元的偏置;

隐藏层的偏置向量,表示隐藏层中第个神经元的偏置;

:隐藏层和可见层之间的权重矩阵,表示隐藏层中第个神经元与可见层中第个神经元之间的连接权重

对于RBM,其参数主要是可见层和隐藏层之间的权重、可见层的偏置和隐藏层的偏置,记为,可将其看作是W、a、b中所有分量拼接起来的到的长向量。

RBM是一个基于能量的模型,对于给定的状态(v, h),可以定义能量函数

进而可以的到(v, h)的联合概率分布

其中

为归一化因子

于是,可以定义边缘概率分布

结合联合概率分布、边缘概率分布和sigmoid函数,可以得到:

在给定可见层状态时,隐藏层上某个神经元被激活的概率

给定隐藏层状态时,可见层上某个神经元被激活的概率

给定训练样本后,训练RBM也就是调整参数,使得RBM表示的概率分布尽可能与训练数据保持一致。

给定训练集:

是训练样本的数量,,则训练RBM的目标就是最大化似然函数:

进一步取log函数:

使用梯度上升法进行上述最优化问题的求解,梯度上升法的形式是:

为学习率,最终可以得到:

Hinton给出了高效寻来呢RBM的算法——对比散度(Contrastive Divergence,简称CD)算法。

,取初始值:,然后执行k步Gibbs抽样,其中第t步先后执行:

  • 利用采样出
  • 利用采样出

最后,88集团赠送38彩金RBM的评估方法,由于本身算法的限制,一般采用近似方法进行评估,重构误差就是其中之一。重构误差以训练样本作为初始状态,经过RBM的分布进行一次Gibbs转移后与原数据的差异量。重构误差在一定程度上反映了RBM对训练样本的似然度,虽然不完全可靠,但计算简单,在实践中非常有用。(达观数据 于敬)

三、如何将RBM应用到推荐系统中

本质上来说,RBM是一个编码解码器:将原始输入数据从可见层映射到隐藏层,并且得到原始输入数据的隐含因子,对应的是编码过程;然后利用得到的隐藏层向量在映射回可见层,得到新的可见层数据,对应的是解码过程。而优化目标是希望让解码后的数据和原始输入数据尽可能的接近。在推荐场景中,可以获取到用户对物品的评分矩阵,进过RBM的编码-解码过程处理后,不仅得到了已有评分对应的新评分,同时对未评分的物品进行预测,并将预测分数从高到低排序就可以生成推荐列表。换句话说,就是将RBM应用到协同过滤中。

但是这个推荐过程需要解决两个问题:

1)RBM中的节点都是二元变量, 如果用这些二元变量来对用户评分进行建模?

2)实际业务场景中,用户只会对很少的物品评分,用户评分行为矩阵都是非常稀疏的,那么如何处理这些缺失的评分?

Ruslan Salakhutdinov等人首次提出了使用RBM求解Netflix竞赛中的协同过滤问题。对传统的RBM进行改进:可见层使用Softmax神经元;用户只对部分物品评分,而对于没有评分的物品使用一种特殊的神经元表示,这种神经元不与任何隐藏层神经元连接。具体结构如图11所示。

图 11 RBM处理推荐问题

从图11中可以看到,Softmax神经元是一个长度为K的向量(图中K为5),并且这个向量每次只有一个分量为1,而且第i个单元为1仅当用户对该物品打分为i是才会置为1,其余为0。从而可以得到可见层单元和隐藏层单元被激活的概率:

使用前面提到的CD算法,各个参数的学习过程如下:

RBM经过学习以后,可以得到整个网络的全部参数。给定一个用户u和一个物品i,预测评分R(u, i)过程如下:

1)  将用户u的所有评分作为RBM的softmax单元的输入

2)  对于所有的隐藏单元j计算激活概率

3)对于所有的k=1,2,…,K, 计算

4)取期望值作为预测结果,比如

以上RBM只用到用户对物品的评分,忽略了很重要的信息:用户浏览过哪些物品,但是并没有评的情况。条件RBM (Conditional Restricted Boltzmann Machine)对这种信息可以进行建模。

图 12 条件RBM处理推荐过程

 

其中r是m维的向量,为1的话,表示用户对浏览过第i个电影,加入r之后的条件概率:

权重D的学习过程:

经过前面的分析,对RBM的内部算法原理、编码和解码过程以及在推荐中的应用等有了基本的了解。在推荐业务场景中,一般有两种使用方式:

一是进行离线计算,也就是对大量用户都批量计算推荐结果,当然计算量往往很乏;二是将训练号的模型保存下来,然后实时生成推荐结果,也就是排序的过程。在达观推荐架构中,RBM是以第二种方式进行应用中。这种方式避免了大量复杂的离线计算,可以对多种单一离线结果进行融合排序,应用上更加灵活。

图 13 达观推荐架构图

其实深度学习的很多模型都可以应用于推荐系统,方式也非常多。达观数据精于技术,对于推荐系统和深度学习相结合以持续优化推荐效果的探索也从未停止,后续也会不断地分享相关成果,敬请期待。

88集团赠送38彩金作者

于敬:达观数据联合创始人,中国计算机学会(CCF)会员,第23届ACM CIKM Competition竞赛国际冠军,达观数据个性化推荐组总负责人,负责达观数据智能推荐系统的架构设计和开发、推荐效果优化等。同济大学计算机应用技术专业硕士,曾先后在盛大创新院、盛大文学和腾讯文学数据中心从事用户行为建模、个性化推荐、大数据处理、数据挖掘和机器学习相关工作,对智能推荐、机器学习、大数据技术和分布式系统有较深入的理解和多年实践经验。

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

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)为其若干个鞍点中的一个。

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

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

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

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

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

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

SSE是88集团赠送38彩金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.

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个赌博机具有更高的平均值和更小的方差。

可以看到88集团赠送38彩金赌博机的获奖概率分布的信息被编码为三个分布。每个分布具有递增的平均值和递减的方差。因此,我们不太确定奖励期望值为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测试的统计理论基础。

fastText原理及实践(达观数据王江)

Deep Learning Specialization on Coursera

王江题图

本文首先会介绍一些预备知识,比如softmax、ngram等,然后简单介绍word2vec原理,之后来讲解fastText的原理,并着手使用keras搭建一个简单的fastText分类器,最后,我们会介绍fastText在达观数据的应用。

 

NO.1
预备知识
Softmax回归

 

Softmax回归(Softmax Regression)又被称作多项逻辑回归(multinomial logistic regression),它是逻辑回归在处理多类别任务上的推广。

在逻辑回归中, 我们有m个被标注的样本:技术干货丨fastText原理及实践其中技术干货丨fastText原理及实践。因为类标是二元的,所以我们有技术干货丨fastText原理及实践。我们的假设(hypothesis)有如下形式:

技术干货丨fastText原理及实践

代价函数(cost function)如下:

技术干货丨fastText原理及实践

在Softmax回归中,类标是大于2的,因此在我们的训练集技术干货丨fastText原理及实践

中,技术干货丨fastText原理及实践。给定一个测试输入x,我们的假设应该输出一个K维的向量,向量内每个元素的值表示x属于当前类别的概率。具体地,假设技术干货丨fastText原理及实践形式如下:

技术干货丨fastText原理及实践

代价函数如下:

技术干货丨fastText原理及实践

 

其中1{·}是指示函数,即1=1,1=0

既然我们说Softmax回归是逻辑回归的推广,那我们是否能够在代价函数上推导出它们的一致性呢?当然可以,于是:

技术干货丨fastText原理及实践

可以看到,逻辑回归是softmax回归在K=2时的特例。

分层Softmax

 

你可能也发现了,标准的Softmax回归中,要计算y=j时的Softmax概率:技术干货丨fastText原理及实践,我们需要对所有的K个概率做归一化,这在|y|很大时非常耗时。于是,分层Softmax诞生了,它的基本思想是使用树的层级结构替代扁平化的标准Softmax,使得在计算技术干货丨fastText原理及实践时,只需计算一条路径上的所有节点的概率值,无需在意其它的节点。

下图是一个分层Softmax示例:

11

树的结构是根据类标的频数构造的霍夫曼树。K个不同的类标组成所有的叶子节点,K-1个内部节点作为内部参数,从根节点到某个叶子节点经过的节点和边形成一条路径,路径长度被表示为技术干货丨fastText原理及实践。于是,技术干货丨fastText原理及实践就可以被写成:

技术干货丨fastText原理及实践

其中:

技术干货丨fastText原理及实践表示sigmoid函数;

技术干货丨fastText原理及实践表示n节点的左孩子;

技术干货丨fastText原理及实践是一个特殊的函数,被定义为:

技术干货丨fastText原理及实践

技术干货丨fastText原理及实践是中间节点技术干货丨fastText原理及实践的参数;X是Softmax层的输入。

上图中,高亮的节点和边是从根节点到 技术干货丨fastText原理及实践 的路径,路径长度技术干货丨fastText原理及实践

可以被表示为:

技术干货丨fastText原理及实践

于是,从根节点走到叶子节点技术干货丨fastText原理及实践,实际上是在做了3次二分类的逻辑回归。

通过分层的Softmax,计算复杂度一下从|K|降低到log|K|。

 

n-gram特征

 

在文本特征提取中,常常能看到n-gram的身影。它是一种基于语言模型的算法,基本思想是将文本内容按照字节顺序进行大小为N的滑动窗口操作,最终形成长度为N的字节片段序列。看下面的例子:

我来到达观数据参观

相应的bigram特征为:我来 来到 到达 达观 观数 数据 据参 参观

相应的trigram特征为:我来到 来到达 到达观 达观数 观数据 数据参 据参观

 

注意一点:n-gram中的gram根据粒度不同,有不同的含义。它可以是字粒度,也可以是词粒度的。上面所举的例子属于字粒度的n-gram,词粒度的n-gram看下面例子:

 

我 来到 达观数据 参观
 
相应的bigram特征为:我/来到 来到/达观数据 达观数据/参观
相应的trigram特征为:我/来到/达观数据 来到/达观数据/参观 

n-gram产生的特征只是作为文本特征的候选集,你后面可能会采用信息熵、卡方统计、IDF等文本特征选择方式筛选出比较重要特征。

 

NO.2

Word2vec

你可能要问,这篇文章不是介绍fastText的么,怎么开始介绍起了word2vec?

最主要的原因是word2vec的CBOW模型架构和fastText模型非常相似。于是,你看到facebook开源的fastText工具不仅实现了fastText文本分类工具,还实现了快速词向量训练工具。word2vec主要有两种模型:skip-gram 模型和CBOW模型,这里只介绍CBOW模型,有关skip-gram模型的内容请参考达观另一篇技术文章:

漫谈Word2vec之skip-gram模型

模型架构

CBOW模型的基本思路是:用上下文预测目标词汇。架构图如下所示:

技术干货丨fastText原理及实践

输入层由目标词汇y的上下文单词 技术干货丨fastText原理及实践 组成, 技术干货丨fastText原理及实践 是被onehot编码过的V维向量,其中V是词汇量;隐含层是N维向量h;输出层是被onehot编码过的目标词y。输入向量通过 技术干货丨fastText原理及实践维的权重矩阵W连接到隐含层;隐含层通过 技术干货丨fastText原理及实践 维的权重矩阵 技术干货丨fastText原理及实践 连接到输出层。因为词库V往往非常大,使用标准的softmax计算相当耗时,于是CBOW的输出层采用的正是上文提到过的分层Softmax。

前向传播

输入是如何计算而获得输出呢?先假设我们已经获得了权重矩阵技术干货丨fastText原理及实践技术干货丨fastText原理及实践(具体的推导见第3节),隐含层h的输出的计算公式:

技术干货丨fastText原理及实践

即:隐含层的输出是C个上下文单词向量的加权平均,权重为W

接着我们计算输出层的每个节点:

技术干货丨fastText原理及实践

这里技术干货丨fastText原理及实践是矩阵技术干货丨fastText原理及实践的第j列,最后,将技术干货丨fastText原理及实践作为softmax函数的输入,得到技术干货丨fastText原理及实践

技术干货丨fastText原理及实践

反向传播学习权重矩阵

在学习权重矩阵和过程中,我们首先随机产生初始值,然后feed训练样本到我们的模型,并观测我们期望输出和真实输出的误差。接着,我们计算误差88集团赠送38彩金权重矩阵的梯度,并在梯度的方向纠正它们。

首先定义损失函数,objective是最大化给定输入上下文,target单词的条件概率。因此,损失函数为:

技术干货丨fastText原理及实践

这里,技术干货丨fastText原理及实践表示目标单词在词库V中的索引。

如何更新权重技术干货丨fastText原理及实践?

我们先对E88集团赠送38彩金技术干货丨fastText原理及实践求导:

技术干货丨fastText原理及实践

技术干货丨fastText原理及实践函数表示:

技术干货丨fastText原理及实践

于是,技术干货丨fastText原理及实践的更新公式:

技术干货丨fastText原理及实践

如何更新权重W

我们首先计算E88集团赠送38彩金隐含层节点的导数:

技术干货丨fastText原理及实践

然后,E88集团赠送38彩金权重的导数为:

技术干货丨fastText原理及实践

于是,技术干货丨fastText原理及实践的更新公式:

技术干货丨fastText原理及实践

 

NO.3

fastText分类

终于到我们的fastText出场了。这里有一点需要特别注意,一般情况下,使用fastText进行文本分类的同时也会产生词的embedding,即embedding是fastText分类的产物。除非你决定使用预训练的embedding来训练fastText分类模型,这另当别论。

字符级别的n-gram

word2vec把语料库中的每个单词当成原子的,它会为每个单词生成一个向量。这忽略了单词内部的形态特征,比如:“apple” 和“apples”,“达观数据”和“达观”,这两个例子中,两个单词都有较多公共字符,即它们的内部形态类似,但是在传统的word2vec中,这种单词内部形态信息因为它们被转换成不同的id丢失了。

 

为了克服这个问题,fastText使用了字符级别的n-grams来表示一个单词。对于单词“apple”,假设n的取值为3,则它的trigram有:

“<ap”,  “app”,  “ppl”,  “ple”, “le>”

其中,<表示前缀,>表示后缀。于是,我们可以用这些trigram来表示“apple”这个单词,进一步,我们可以用这5个trigram的向量叠加来表示“apple”的词向量。

这带来两点好处

1. 对于低频词生成的词向量效果会更好。因为它们的n-gram可以和其它词共享。

2. 对于训练词库之外的单词,仍然可以构建它们的词向量。我们可以叠加它们的字符级n-gram向量。

模型架构

之前提到过,fastText模型架构和word2vec的CBOW模型架构非常相似。下面是fastText模型架构图:

技术干货丨fastText原理及实践

注意:此架构图没有展示词向量的训练过程。可以看到,和CBOW一样,fastText模型也只有三层:输入层、隐含层、输出层(Hierarchical Softmax),输入都是多个经向量表示的单词,输出都是一个特定的target,隐含层都是对多个词向量的叠加平均。

不同的是,CBOW的输入是目标单词的上下文,fastText的输入是多个单词及其n-gram特征,这些特征用来表示单个文档;CBOW的输入单词被onehot编码过,fastText的输入特征是被embedding过;CBOW的输出是目标词汇,fastText的输出是文档对应的类标。

值得注意的是,fastText在输入时,将单词的字符级别的n-gram向量作为额外的特征;在输出时,fastText采用了分层Softmax,大大降低了模型训练时间。这两个知识点在前文中已经讲过,这里不再赘述。

fastText相关公式的推导和CBOW非常类似,这里也不展开了。

核心思想

现在抛开那些不是很讨人喜欢的公式推导,来想一想fastText文本分类的核心思想是什么?

仔细观察模型的后半部分,即从隐含层输出到输出层输出,会发现它就是一个softmax线性多类别分类器,分类器的输入是一个用来表征当前文档的向量;模型的前半部分,即从输入层输入到隐含层输出部分,主要在做一件事情:生成用来表征文档的向量。那么它是如何做的呢?叠加构成这篇文档的所有词及n-gram的词向量,然后取平均。叠加词向量背后的思想就是传统的词袋法,即将文档看成一个由词构成的集合。

于是fastText的核心思想就是:将整篇文档的词及n-gram向量叠加平均得到文档向量,然后使用文档向量做softmax多分类。这中间涉及到两个技巧:字符级n-gram特征的引入以及分层Softmax分类。

88集团赠送38彩金分类效果

还有个问题,就是为何fastText的分类效果常常不输于传统的非线性分类器?

假设我们有两段文本:

我 来到 达观数据

俺 去了 达而观信息科技

这两段文本意思几乎一模一样,如果要分类,肯定要分到同一个类中去。但在传统的分类器中,用来表征这两段文本的向量可能差距非常大。传统的文本分类中,你需要计算出每个词的权重,比如tfidf值, “我”和“俺” 算出的tfidf值相差可能会比较大,其它词类似,于是,VSM(向量空间模型)中用来表征这两段文本的文本向量差别可能比较大。

 

但是fastText就不一样了,它是用单词的embedding叠加获得的文档向量,词向量的重要特点就是向量的距离可以用来衡量单词间的语义相似程度,于是,在fastText模型中,这两段文本的向量应该是非常相似的,于是,它们很大概率会被分到同一个类中。

使用词embedding而非词本身作为特征,这是fastText效果好的一个原因;另一个原因就是字符级n-gram特征的引入对分类效果会有一些提升 。

 

NO.4

手写一个fastText

keras是一个抽象层次很高的神经网络API,由python编写,底层可以基于Tensorflow、Theano或者CNTK。它的优点在于:用户友好、模块性好、易扩展等。所以下面我会用keras简单搭一个fastText的demo版,生产可用的fastText请移步https://github.com/facebookresearch/fastText

如果你弄懂了上面所讲的它的原理,下面的demo对你来讲应该是非常明了的。

为了简化我们的任务:

1. 训练词向量时,我们使用正常的word2vec方法,而真实的fastText还附加了字符级别的n-gram作为特征输入;

2. 我们的输出层使用简单的softmax分类,而真实的fastText使用的是Hierarchical Softmax。

首先定义几个常量:

VOCAB_SIZE = 2000

EMBEDDING_DIM =100

MAX_WORDS = 500

CLASS_NUM = 5

VOCAB_SIZE表示词汇表大小,这里简单设置为2000;

EMBEDDING_DIM表示经过embedding层输出,每个词被分布式表示的向量的维度,这里设置为100。比如对于“达观”这个词,会被一个长度为100的类似于[ 0.97860014, 5.93589592, 0.22342691, -3.83102846, -0.23053935, …]的实值向量来表示;

MAX_WORDS表示一篇文档最多使用的词个数,因为文档可能长短不一(即词数不同),为了能feed到一个固定维度的神经网络,我们需要设置一个最大词数,对于词数少于这个阈值的文档,我们需要用“未知词”去填充。比如可以设置词汇表中索引为0的词为“未知词”,用0去填充少于阈值的部分;

CLASS_NUM表示类别数,多分类问题,这里简单设置为5。

模型搭建遵循以下步骤

1. 添加输入层(embedding层)。Embedding层的输入是一批文档,每个文档由一个词汇索引序列构成。例如:[10, 30, 80, 1000] 可能表示“我 昨天 来到 达观数据”这个短文本,其中“我”、“昨天”、“来到”、“达观数据”在词汇表中的索引分别是10、30、80、1000;Embedding层将每个单词映射成EMBEDDING_DIM维的向量。于是:input_shape=(BATCH_SIZE, MAX_WORDS), output_shape=(BATCH_SIZE,MAX_WORDS, EMBEDDING_DIM);

2. 添加隐含层(投影层)。投影层对一个文档中所有单词的向量进行叠加平均。keras提供的GlobalAveragePooling1D类可以帮我们实现这个功能。这层的input_shape是Embedding层的output_shape,这层的output_shape=( BATCH_SIZE, EMBEDDING_DIM);

3. 添加输出层(softmax层)。真实的fastText这层是Hierarchical Softmax,因为keras原生并没有支持Hierarchical Softmax,所以这里用Softmax代替。这层指定了CLASS_NUM,对于一篇文档,输出层会产生CLASS_NUM个概率值,分别表示此文档属于当前类的可能性。这层的output_shape=(BATCH_SIZE, CLASS_NUM)

4. 指定损失函数、优化器类型、评价指标,编译模型。损失函数我们设置为categorical_crossentropy,它就是我们上面所说的softmax回归的损失函数;优化器我们设置为SGD,表示随机梯度下降优化器;评价指标选择accuracy,表示精度。

用训练数据feed模型时,你需要:

1. 将文档分好词,构建词汇表。词汇表中每个词用一个整数(索引)来代替,并预留“未知词”索引,假设为0;

2. 对类标进行onehot化。假设我们文本数据总共有3个类别,对应的类标分别是1、2、3,那么这三个类标对应的onehot向量分别是[1, 0,
0]、[0, 1, 0]、[0, 0, 1];

3. 对一批文本,将每个文本转化为词索引序列,每个类标转化为onehot向量。就像之前的例子,“我 昨天 来到 达观数据”可能被转化为[10, 30,
80, 1000];它属于类别1,它的类标就是[1, 0, 0]。由于我们设置了MAX_WORDS=500,这个短文本向量后面就需要补496个0,即[10, 30, 80, 1000, 0, 0, 0, …, 0]。因此,batch_xs的 维度为( BATCH_SIZE,MAX_WORDS),batch_ys的维度为(BATCH_SIZE, CLASS_NUM)。

下面是构建模型的代码,数据处理、feed数据到模型的代码比较繁琐,这里不展示。

技术干货丨fastText原理及实践

 

NO.5

fastText原理及实践

fastText在达观数据的应用

fastText作为诞生不久的词向量训练、文本分类工具,在达观得到了比较深入的应用。主要被用在以下两个系统:

1. 同近义词挖掘。Facebook开源的fastText工具也实现了词向量的训练,达观基于各种垂直领域的语料,使用其挖掘出一批同近义词;

2. 文本分类系统。在类标数、数据量都比较大时,达观会选择fastText 来做文本分类,以实现快速训练预测、节省内存的目的。

达观数据搜索引擎的Query自动纠错技术和架构详解

Deep Learning Specialization on Coursera

1 背景

如今,搜索引擎是人们的获取信息最重要的方式之一,在搜索页面小小的输入框中,只需输入几个关键字,就能找到你感兴趣问题的相关网页。搜索巨头Google,甚至已经使Google这个创造出来的单词成为动词,有问题Google一下就可以。在国内,百度也同样成为一个动词。除了通用搜索需求外,很多垂直细分领域的搜索需求也很旺盛,比如电商网站的产品搜索,文学网站的小说搜索等。面对这些需求,达观数据(www.datagrand.com)作为国内提供中文云搜索服务的高科技公司,为合作伙伴提供高质量的搜索技术服务,并进行搜索服务的统计分析等功能。(达观数据联合创始人高翔)

搜索引擎系统最基本最核心的功能是信息检索,找到含有关键字的网页或文档,然后按照一定排序将结果给出。在此基础之上,搜索引擎能够提供更多更复杂的功能来提升用户体验。对于一个成熟的搜索引擎系统,用户看似简单的搜索过程,需要在系统中经过多个环节,多个模块协同工作,才能提供一个让人满意的搜索结果。其中拼写纠错(Error Correction,以下简称EC)是用户比较容易感知的一个功能,比如百度的纠错功能如下图所示:

图片 1

图 1:百度纠错功能示例

EC其实是属于Query Rewrite(以下简称QR)模块中的一个功能,QR模块包括拼写纠错,同义改写,关联query等多个功能。QR模块对于提升用户体验有着巨大的帮助,对于搜索质量不佳的query进行改写后能返回更好的搜索结果。QR模块内容较多,以下着重介绍EC功能。
继续阅读