基于主题模型和随机游走的标签技术研究--《北京邮电大学》2013年博士论文
基于主题模型和随机游走的标签技术研究
【摘要】：随着互联网的发展,尤其是Web2.0的发展,标签技术在各种网站中得到广泛的应用,给网络资源打上简短的文字标签能极大方便人们对海量数据的存取。由于大量的网络资源还没有标签,而人工打标签费时费力,因此,为网络资源自动打上高质量标签成为近年来学术界以及企业界的一个关注焦点。其中,基于资源内容自动抽取关键短语标签和基于已有的社会化标签集推荐标签是两种主要的自动标签方式。
虽然已经开展了大量的工作,也出现了一些关键短语抽取和社会化标签推荐的算法和应用系统。但是目前的自动标签技术还存在着一些问题,其中包括：在关键短语抽取中,主要考察词语的局部统计特性或局部的词间相关信息,而没有考虑词语-文档-主题三者间的全局关系；在社会化标签推荐中,没有同时考虑标签粒度和噪声标签的主题模型,也没有考虑标签-文档-主题三者间的全局关系；在融合关键短语抽取和社会化标签推荐结果的研究中,主要采用线性融合,该方法的参数需要人为指定,且没有充分考虑关键短语和社会化标签之间的关系。本论文针对这些问题展开工作,并取得了如下的成果：
一、提出了一种基于全局随机游走的关键短语排序算法GlobalRank。该算法在考虑词语本身的TFIDF权值、词语间的局部关系以及词语和文档与主题的关系的同时,通过引入在词语-文档-主题相关图上的全局随机游走,得到关键短语相对于当前文档的全局相关性,GlobalRank综合利用这些信息进行关键短语的排序。为了验证排序算法的性能,将其应用于关键短语抽取任务。在三个数据集上的实验表明,在候选短语相同的条件下,和前人局限于当前文本的局部特征的算法相比,本文提出的关键短语排序算法能生成更加准确的关键短语有序列表。
二、逐步深入地提出了一系列社会化标签推荐模型和算法。首先提出了TG-LDA (Tag-granularity LDA)模型,该模型对网络实际数据中广泛存在的文档主题和标签主题具有不同描述颗粒度的现象进行建模；然后,在TG-LDA模型的基础上,提出了能同时建模多粒度主题和噪声标签的TN-LDA (Tag-granularity and Noise-aware LDA)模型,最后,在TN-LDA的基础上,提出了一个结合了全局随机游走的标签推荐算法。实验表明,本文提出的TN-LDA模型,能在对有标签文档进行更好建模的同时,有效提高标签推荐的性能。而结合全局随机游走的标签推荐算法不仅考虑了网页内容的隐含主题和社会化标签的相互影响,还综合了词粒度标签和主题粒度标签,并将这些关系统一在随机游走的框架下,获取全局相关性。实验表明,该算法的标签推荐结合了主题模型和词特征方法的优点,具有更好的标签推荐性能。
同时,求解随机游走的稳定态,还可以优化文档的主题分布,从而根据其分布对文档聚类。通过实验表明,其聚类性能要优于主题模型的方法。
三、提出了一种综合考虑关键短语和标签自身权重及其相互关系的融合算法LabelRank。该算法利用偏置PageRank算法,得到候选关键短语和标签的显著性权重,并根据其权重,统一对关键短语和标签进行排序并输出。在Delicious数据上的实验表明,LabelRank算法较好地结合了关键短语和社会化标签的优点,其标签推荐性能明显优于单纯的关键短语抽取和社会化标签推荐算法方法,也优于未全局考虑关键短语和社会化标签相关性的线性融合方法。而且,LabelRank受调节参数影响较小,体现出较高的鲁棒性。
最后,结合关键短语抽取和社会化标签推荐算法,实现了一个针对文档的自动标签演示系统,该系统可返回输入文档的关键短语、社会化标签及其融合结果,同时允许用户对系统返回的标签进行判断或自行输入标签,作为训练语料存入训练集。
【关键词】：
【学位授予单位】：北京邮电大学【学位级别】：博士【学位授予年份】：2013【分类号】：TP391.1【目录】：
摘要4-6ABSTRACT6-11第—章 绪论11-33 1.1 研究背景及意义11-14 1.2 国内外研究现状及分析14-23
1.2.1 关键短语抽取14-17
1.2.2 基于内容的社会化标签推荐问题17-21
1.2.3 关键短语和社会化标签的融合方法21-23 1.3 本文的研究内容及安排23-27 参考文献27-33第二章 研究基础及相关问题33-57 2.1 社会化标签系统33-35
2.1.1 Delicious33-34
2.1.2 Bibsonomy和CiteUlike34
2.1.3 豆瓣34-35
2.1.4 新浪微博35 2.2 隐含主题模型35-41
2.2.1 LDA35-36
2.2.2 Tag-LDA36-37
2.2.3 Corr-LDA37-38
2.2.4 PTC38-40
2.2.5 CRM40-41 2.3 无监督关键短语抽取41-49
2.3.1 基于LDA的方法41
2.3.2 基于图排序的方法41-46
2.3.3 基于词聚类的方法46-49 2.4 基于内容的社会化标签推荐49-53
2.4.1 基于词层的方法49-51
2.4.2 基于主题模型的方法51-53 参考文献53-57第三章 全局关键短语排序57-81 3.1 引言57-58 3.2 重置随机游走58 3.3 全局关键短语排序58-60
3.3.1 相关图及转移概率初始化构造59-60
3.3.2 稳定态求解60 3.4 实验结果与分析60-77
3.4.1 关键短语排序输出60-61
3.4.2 实验所需标准语料及预处理61-63
3.4.3 主题模型训练63-64
3.4.4 评测标准64
3.4.5 内部初始化和参数实验64-66
3.4.6 对比方法及参数设置66-67
3.4.7 对比实验及分析67-75
3.4.8 样例分析75-77 3.5 本章小结77-79 参考文献79-81第四章 结合主题模型和随机游走的自动标签推荐81-109 4.1 引言81-82 4.2 基于标签粒度的主题模型82-89
4.2.1 TG-LDA模型82-83
4.2.2 基于吉布斯抽样的模型参数估计83-84
4.2.3 实验数据准备84-86
4.2.4 评测标准86-87
4.2.5 实验结果和分析87-89 4.3 基于标签粒度及噪声标签的主题模型89-94
4.3.1 TN-LDA模型89-91
4.3.2 基于吉布斯抽样的模型参数估计91
4.3.3 实验结果和分析91-93
4.3.4 噪声分析93-94 4.4 结合主题和词特征的标签推荐94-101
4.4.1 相关图及转移概率初始化95-96
4.4.2 标签推荐96
4.4.3 标签推荐对比方法96-97
4.4.4 标签推荐评测97-99
4.4.5 标签粒度分析99-101 4.5 结合主题和词特征的文档聚类101-105
4.5.1 文档聚类101-102
4.5.2 数据准备102-103
4.5.3 聚类评测标准103-104
4.5.4 聚类评测实验104-105 4.6 本章小结105-107 参考文献107-109第五章 融合关键短语和社会化标签109-123 5.1 引言109 5.2 关键短语和社会标签融合算法109-112
5.2.1 相关图及转移概率初始化构造110-112
5.2.2 基于LabelRank的融合算法112 5.3 实验结果与分析112-116
5.3.1 标签来源分析113
5.3.2 内部参数比较113-114
5.3.3 对比方法及参数设置114-115
5.3.4 对比实验与分析115-116 5.4 文档自动标签演示系统116-120 5.5 本章小结120-121 参考文献121-123第六章 工作总结与展望123-127 6.1 工作总结123-124 6.2 工作展望124-127
6.2.1 在线推荐及评测方法124-125
6.2.2 结合用户信息125
6.2.3 结合语义本体125-127致谢127-129攻读博士学位期间发表的论文129
欢迎：、、)
支持CAJ、PDF文件格式
【参考文献】
中国期刊全文数据库
靳延安;李瑞轩;文坤梅;辜希武;卢正鼎;段东圣;;[J];中文信息学报;2010年04期
中国博士学位论文全文数据库
靳延安;[D];华中科技大学;2011年
【共引文献】
中国期刊全文数据库
范忆慧;;[J];重庆理工大学学报(自然科学);2012年07期
黄丹;盛小平;;[J];图书与情报;2012年05期
庄科君;贺宝勋;;[J];福建电脑;2013年02期
文坤梅;徐帅;李瑞轩;辜希武;李玉华;;[J];中文信息学报;2012年06期
余春;;[J];图书馆建设;2012年04期
吴丹;林若楠;冯倩然;陈欢;;[J];图书馆论坛;2012年01期
吴丹;王艳妮;;[J];图书馆;2012年01期
武慧娟;徐宝祥;;[J];情报科学;2012年10期
董永梅;;[J];图书馆建设;2012年09期
李宏言;范利春;高鹏;徐波;;[J];清华大学学报(自然科学版);2013年06期
中国博士学位论文全文数据库
靳延安;[D];华中科技大学;2011年
熊回香;[D];华中师范大学;2011年
孙珂;[D];哈尔滨工业大学;2011年
陈根浪;[D];浙江大学;2012年
中国硕士学位论文全文数据库
于辉;[D];大连理工大学;2012年
周桂清;[D];华南理工大学;2012年
王小蕾;[D];华北电力大学;2012年
江莉莉;[D];南京航空航天大学;2012年
王贤兵;[D];华中科技大学;2012年
潘宇彬;[D];西安电子科技大学;2013年
胡蓉;[D];华中师范大学;2013年
【二级参考文献】
中国期刊全文数据库
金澎;吴云芳;俞士汶;;[J];中文信息学报;2008年03期
靳延安;李瑞轩;文坤梅;辜希武;卢正鼎;段东圣;;[J];中文信息学报;2010年04期
张玫;张晓林;;[J];现代图书情报技术;2007年07期
窦玉萌;赵丹群;;[J];现代图书情报技术;2009年02期
【相似文献】
中国期刊全文数据库
刘玲玲;梁颖红;张永刚;韩艳;姚建民;;[J];江南大学学报(自然科学版);2010年01期
刘华;;[J];中文信息学报;2007年04期
吉翔华;陈超;邵正荣;俞能海;;[J];小型微型计算机系统;2007年12期
王翠英;;[J];现代图书情报技术;2008年05期
程慧荣;黄国彬;张永杰;;[J];图书馆杂志;2008年11期
李枫林;张景;;[J];情报理论与实践;2010年10期
蒋翠清;张玉;丁勇;;[J];现代图书情报技术;2010年10期
顾复;陈芨熙;;[J];成组技术与生产现代化;2007年02期
王翠英;;[J];现代情报;2008年02期
陈远浩;张本宇;张宏江;;[J];小型微型计算机系统;2009年07期
中国重要会议论文全文数据库
任竹;贾珈;蔡莲红;;[A];第七届和谐人机环境联合学术会议（HHME2011)论文集【poster】[C];2011年
韩敏;唐常杰;段磊;李川;巩杰;;[A];第26届中国数据库学术会议论文集（A辑）[C];2009年
房冠南;袁彩霞;王小捷;李江;宋占江;;[A];中国计算语言学研究前沿进展（）[C];2011年
李静;林鸿飞;;[A];第六届全国信息检索学术会议论文集[C];2010年
何莉;林鸿飞;;[A];2009年全国开放式分布与并行计算机学术会议论文集(下册)[C];2009年
吴继媛;孙淳;侯敏;;[A];第五届全国青年计算语言学研讨会论文集[C];2010年
王琦;唐世渭;杨冬青;王腾蛟;;[A];第二十一届中国数据库学术会议论文集（研究报告篇）[C];2004年
冯少卿;都云程;施水才;;[A];第三届全国信息检索与内容安全学术会议论文集[C];2007年
黄天航;;[A];规划创新：2010中国城市规划年会论文集[C];2010年
李志云;周国祥;;[A];全国第20届计算机技术与应用学术会议(CACIS·2009)暨全国第1届安全关键技术与应用学术会议论文集（下册）[C];2009年
中国重要报纸全文数据库
李彩霞;[N];中国包装报;2007年
刘世昌;[N];中国新闻出版报;2007年
辽宁中期 时 岩;[N];证券日报;2005年
英特尔Dialogic分部计算机通信部营销总监Carl R.S[N];网络世界;2001年
;[N];计算机世界;2005年
吴悦;[N];中国经营报;2007年
游峰?杜建民;[N];东莞日报;2008年
张建琛?通讯员
许长水;[N];科技日报;2007年
南京工程学院仿真部
施建强;[N];计算机世界;2002年
刘英赫;[N];中国电子报;2000年
中国博士学位论文全文数据库
孙甲申;[D];北京邮电大学;2013年
靳延安;[D];华中科技大学;2011年
吴超;[D];浙江大学;2010年
吴永辉;[D];哈尔滨工业大学;2010年
宣云干;[D];南京大学;2011年
王萍;[D];华东师范大学;2010年
熊回香;[D];华中师范大学;2011年
栗华;[D];山东大学;2011年
刘名扬;[D];吉林大学;2013年
张智;[D];浙江大学;2012年
中国硕士学位论文全文数据库
姜舟;[D];哈尔滨工业大学;2010年
张永刚;[D];苏州大学;2010年
徐晓明;[D];东北大学;2011年
张超;[D];电子科技大学;2010年
高飞航;[D];东北大学;2011年
胡蓉;[D];华中师范大学;2013年
葛艳艳;[D];大连理工大学;2011年
朱运;[D];复旦大学;2012年
李研;[D];长春理工大学;2009年
王婍犇;[D];华东师范大学;2006年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 大众知识服务
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号Peacock:大规模主题模型及其在腾讯业务中的应用微信公众号-Peacock:大规模主题模型及其在腾讯业务中的应用微信应用号--8081微导航推荐
关注微信号
Peacock：大规模主题模型及其在腾讯业务中的应用
媒体神经认知计算
Peacock：大规模主题模型及其在腾讯业务中的应用作者：赵学敏 王莉峰 王流斌 孙振龙 严浩 靳志辉 王益摘要如果用户最近搜索了“红酒木瓜汤”，那么应该展示什么样的广告呢？从字面上理解，可能应该返回酒水或者水果类广告。可是你知道吗？“红酒木瓜汤”其实是一个民间丰胸秘方。如果机器能理解这个隐含语义，就能展示丰胸或者美容广告——这样点击率一定很高。在广告、搜索和推荐中，最重要的问题之一就是理解用户兴趣以及页面、广告、商品等的隐含语义。让机器能自动学习和理解人类语言中近百万种语义，以及从海量用户行为数据中归纳用户兴趣，是一个已经持续了20年的研究方向，称为主题建模（Latent Topic Modeling）。目前业界的各种系统中最为突出的是Google Rephil，在Google AdSense广告系统中发挥了重要作用。追随Google的脚步，腾讯SNG效果广告平台部（广点通）的同学们成功的研发了Peacock大规模主题模型机器学习系统，通过并行计算可以高效地对10亿x1亿级别的大规模矩阵进行分解，从而从海量样本数据中学习10万到100万量级的隐含语义。我们把Peacock系统应用到了腾讯业务中，包括文本语义理解、QQ群的推荐、用户商业兴趣挖掘、相似用户扩展、广告点击率转化率预估等，均取得了不错的效果。一、为什么我们要开发大规模主题模型训练系统Peacock？1.1 短文本相关性在自然语言处理和信息检索中，我们常常会遇到如下问题：给定查询词，计算查询词和文档之间的相关性。比如表1给出了2个具体例子，此时我们需要计算短文本之间的相关性。常用的计算方法就是不考虑词的相对顺序，使用BOW（Bag-Of-Words）模型把文档表示为词向量，然后计算文本之间的相似度。如果直接采用文档中词的TF-IDF构建文档特征向量，通过计算查询词特征向量和文档特征向量的余弦夹角，我们会发现Q1与D1、D2都相关，而Q2与D1、D2都不相关。显然，这与人对自然语言的理解并不相符：Q1和D2比较相关，都关于“苹果”这种水果；而Q2和D1比较相关，都关于“苹果”公司。表1 短文本相关性之所以会出现这种差异，是因为上述文档特征向量构建方法没有“理解”文档的具体语义信息，单纯的将文档中的词表示为一个ID而已。通过主题模型，文档可以表示为一个隐含语义空间上的概率分布向量（主题向量），文档主题向量之间的余弦夹角就可以一定程度上反映文档间的语义相似度了。1.2 推荐系统图1 用户-物品矩阵主题模型的另一个主要应用场景是推荐系统。不管是电商网站的商品推荐，还是各大视频网站的视频推荐等，都可以简化为如下问题：给定用户-物品矩阵（图1，矩阵中用户u和物品i对应的值表示u对i的偏好，根据用户行为数据，矩阵会得到部分“初始”值），如何“填满”矩阵中没有值的部分。图2 物品聚类在各种眼花缭乱的推荐算法中，直接利用用户-物品矩阵进行推荐是最有效的方式（没有长年的用户、物品内容分析技术积累也一样可以快速做出效果），而这其中的两类主要算法都与主题模型有关系：协同过滤[1]。以基于用户的协同过滤为例，就是要向用户推荐与之相似的用户喜欢的物品，包含两个主要步骤：计算用户相似度和向用户推荐与自己最相似的用户喜欢的物品，难点在于计算用户相似度。如果不引入外部数据，最简单的计算用户u和v相似度的方法可以直接利用用户-物品矩阵的u行和v行，比如计算它们的余弦夹角。然而，真实的互联网数据中，用户-物品矩阵通常都非常稀疏，直接计算不能得到准确的结果。此时，常见的做法是对用户（或物品）进行聚类或者将矩阵投影到更低维的隐空间（图2、3），在隐空间计算用户相似度可以更加准确。主题模型可以用来将用户-物品矩阵投影到隐空间。隐含语义模型 (Latent Factor Model, LFM)[2]。该类方法本质上和主题模型是一致的，直观的理解是将用户-物品矩阵分解为用户-隐含语义（主题）矩阵和隐含语义（主题）-物品矩阵（图3），通过更低维度的上述两个矩阵，来重构原始用户-物品矩阵，重构得到的矩阵将不再稀疏，可以直接用于推荐。具体例子可以参看“QQ群推荐”应用。图3 用户-物品矩阵分解实际上，从以上的讨论中我们容易发现，当使用BOW模型处理文本，把文档数据表示成文档-词（Doc-Word）矩阵的时候，其表示结构和用户-物品（User-Item）矩阵结构是完全一致的。因此这两类数据可以使用同样的算法进行处理。使用隐含主题模型处理文档-词矩阵的时候，可以理解为把词聚类为主题，并计算各个文档和词聚类之间的权重。类似地，处理用户-物品矩阵的时候，可以理解为把物品聚类为主题，然后计算每个用户和各个聚类之间的权重。图2是这个过程的一个形象描述，而这个过程如图3所示，可以理解为把原始矩阵分解为两个较小的矩阵：左下的Topic-Item矩阵描述了物品聚类，每行一个主题（Topic）表示一个聚类；而右侧的User-Topic矩阵每一行为主题权重向量，表示每个用户和每个主题的紧密关系。1.3 Peacock是什么？从上面两个小节我们已经看到，主题模型在互联网产业中具有非常重要的应用。而Peacock系统着手开发时（2012年11月），一些开源以及学术界的主题模型训练系统[5,6,7,8]，要么只能处理小规模的训练语料得到“小模型”，要么模型质量不佳。基于这种状况，我们设计并开发了Peacock系统（更多有关Peacock系统的设计哲学和开发进程，可以参考王益的博客[3]和图灵访谈文章[4]）。Peacock是一个大规模主题模型训练系统，它既可以从数十亿的网络语料中学习出百万级别的隐含语义（主题），也可以对数十亿乘以几亿规模的矩阵进行“分解”。我们的工作总结成论文“Peacock: Learning Long-Tail Topic Features for Industrial Applications”发表在ACM Transaction on Intelligent System and Technology (2015)[15]。图4 Peacock文档语义推断系统Demo图5 Peacock文档语义推断示例1：“苹果”图6 Peacock文档语义推断示例2：“苹果 梨子”图7 Peacock文档语义推断示例3：“苹果大尺度”下面我们分别给定一些具体的例子，让大家对Peacock有一些直观上的认识：自然语言处理的例子。图4给出了Peacock在线推断系统Demo的主要界面，手动输入文档以后，点击“submit”就可以看到Peacock对输入文档的理解。这个例子中，我们利用训练好的Peacock模型，在线推断给定的输入文档的主题分布P(topic|doc)。每一行打印出一个语义主题，并给出主题的权重。具体的主题由一组相关的词组成，每个词都有权重。而第二部分 P(word|doc) 则给出了和该文档相关的权重最高的词。在Demo的例子中，我们可以看到 Peacock 对“红酒木瓜汤”这个检索串最重要的语义理解是“丰胸、产品、减肥、木瓜、效果”，非常符合人的语义理解。图5、6、7演示了典型的多义词“苹果”在不同语境下Peacock对其的不同理解，可以看到“苹果”这个检索串在 Peacock 中被处理成了如下三种语义：“苹果公司及其产品”、“水果”、“范冰冰《苹果》电影”。而“苹果、梨子”主要语义被理解为“水果”，“苹果大尺度”的主要语义被理解为“范冰冰《苹果》电影”。可以看到Peacock可以比较准确的理解不同文档的具体含义，这将有助于我们完成一系列自然语言处理和信息检索的任务。用户-物品矩阵分解的例子。这个例子中，“用户”（相当于“文档”）为QQ，“物品”（相当于“词”）为这部分用户加入的QQ兴趣群（在数据预处理中，我们会将QQ群分为关系群、兴趣群等，兴趣群可以比较好的反映用户的兴趣）。取非常活跃的5亿用户和非常活跃的1亿QQ兴趣群，得到一个5亿x1亿的矩阵，使用Peacock分解该矩阵后获得Topic-Item矩阵（即主题-QQ群矩阵），图8、9、10分别给出了该矩阵中的三个主题（只显示权重最高的主要QQ群）。为了方便理解，同时将QQ群的描述信息显示在群ID之后。可以看到，Peacock学习得到的主题含义比较明确，一定程度上可以反映出Peacock在处理用户-物品矩阵上的有效性。图8 基于QQ-QQ群Peacock矩阵分解示例：炒股类主题图9 基于QQ-QQ群Peacock矩阵分解示例：塔防三国游戏类主题图10 基于QQ-QQ群Peacock矩阵分解示例：济南母婴类主题通过一些具体的例子直观的介绍了主题模型之后，接下来第二章将主要从算法的角度来回答“什么是主题模型”这个问题，第三章介绍对主题模型并行化的一些思考以及Peacock的具体做法，最后第四章介绍主题模型在腾讯业务中的具体应用。二、什么是主题模型？下面以文档建模为例，简单介绍一下主题模型。2.1 主题模型的“三个过程”主题模型一般包含了三个重要的过程：生成过程、训练过程以及在线推断。生成过程定义了模型的假设以及具体的物理含义，训练过程定义了怎样由训练数据学习得出模型，在线推断定义了怎样应用模型。下面分别进行简要介绍。一般来说，主题模型是一种生成模型（生成模型可以直观的理解为给定模型，可以生成训练样本）。给定模型，其生成过程如图11：模型有2个主题，主题1关于银行（主要的词为loan、bank、money等），主题2关于河流（主要的词为river、stream、bank等）。文档1内容100%关于主题1，主题向量为&1.0, 0.0&，文档中每一个词的生成过程如下：以100%的概率选择主题1，再从主题1中以一定的概率挑选词。文档2内容50%关于主题1，50%关于主题2，主题向量为&0.5, 0.5&，文档中每一个词的生成过程如下：以均等的概率选择主题1和2，再从选中的主题中以一定的概率挑选词。文档3内容100%关于主题2，主题向量为&0.0, 1.0&，文档中每一个词的生成过程如下：以100%的概率选择主题2，再从主题2中以一定的概率挑选词。图11 主题模型的生成过程[9]现实的情况是我们没有模型，只有海量的互联网文档数据，此时我们希望有机器学习算法可以自动的从训练文档数据中归纳出主题模型（如图12），即得到每个主题在词表上的具体分布。通常来说，训练过程还会得到一个副产品——每篇训练文档的主题向量。图12 主题模型的训练过程[9]有了主题模型，给定新的文档，通过在线推断，我们就可以得到文档的主题向量（如图13）。图5、6、7给出了一些具体的例子。图13 主题模型的在线推断三个过程中，训练过程是难点，后文将进行重点介绍。2.2 LDA模型及其训练算法LDA（Latent Dirichlet Allocation）[10]作为一种重要的主题模型，自发表以来就引起了学术界和产业界的极大关注，相关论文层出不穷。LDA的训练算法也多种多样，下面以吉布斯采样[11,12]为例，进行简要介绍。图14 LDA训练过程跳过复杂的数学推导，基于吉布斯采样的LDA训练过程如图14所示（每个词用w表示，每个词对应的主题用z表示，图中节点z的不同颜色表示不同的主题）：Step1: 初始时，随机的给训练语料中的每一个词w赋值一个主题z，并统计两个频率计数矩阵：Doc-Topic计数矩阵Ntd，描述每个文档中的主题频率分布；Word-Topic计数矩阵Nwt，表示每个主题下词的频率分布。如图15所示，两个矩阵分别对应于图中的边上的频率计数。Step2: 遍历训练语料，按照概率重新采样其中每一个词w对应的主题z，同步更新Nwt和Ntd。Step3: 重复 step2，直到Nwt收敛。Step2中重新采样词w对应主题z时，采样公式为P(z=t|w,*)=N?wt+βN?t+βV?N?td+αtLd–1+∑tαt∝N?wt+βN?t+βV(N?td+αt)(1)其中αt和β是超参数，分别表示对Ntd和Nwt中的频率计数进行概率平滑；V为词表大小，Ld表示文档d长度，Nwt表示训练语料中主题t中词w的出现次数，Nt表示训练语料中主题t的出现次数，Ntd表示文档d中主题t的出现次数，上角标?表示剔除当前采样词w的影响（比如N?td表示减去当前采样词对应的主题后，文档d中主题t的出现次数）。图15 文档d1中词w主题重新采样事实上，以上对文档d中词w的主题z进行重新采样的公式有非常明确的物理意义，表示P(w|z)P(z|d)，可以如图15直观的表示为一个“路径选择”的过程：对当前文档d中的当前词w（图15中黑体表示），词w的“旧”主题z给出了d-z-w的一条路径（图15（1）虚线）；剔除词w对应的“旧”主题z，更新在Nwt和Ntd中的计数（图15（1）在旧路径对应的两条边上做 “-1”操作）；计算d-z-w的每一条可能路径的概率，d-z-w路径的概率等于d-z和z-w两部分路径概率的乘积即P(z|d)P(w|z)，P(z|d)和Ntd有关，P(w|z)和Nwt有关（图15（1））；依据概率对d-z-w路径进行采样，得到词w的“新”主题z（图15（2）虚线）；增加词w对应的“新”主题z，更新在Nwt和Ntd中的计数（图15（2）在新路径对应的两条边上做“+1”操作）。图16 单机版LDA训练过程在训练模型时，为了包含尽可能多的隐含语义（主题）同时保证效果，通常会使用海量的训练语料。这些互联网原始文档语料经过切词、停用词过滤、文档过滤（长度）等预处理步骤后（通常会分块进行存储），就可以作为LDA训练器的输入了。图14描述的LDA训练过程，在更大范围的训练语料上来看，如图16所示：训练语料数据块中会保存文档中的词和对应的主题(W,T)，以及文档对应的主题直方图Ntd；训练器内存中保存一份Nwt；训练器依次加载训练语料数据块，并对其中的所有词W的主题T进行采样，采样的同时会更新Nwt、Ntd和文档中词W的主题T；采样完成一个数据块后，训练器将更新后的(W,T)和Ntd序列化到磁盘上，供下一个迭代加载采样；所有迭代结束，Nwt收敛，训练器根据Nwt计算出模型并输出。基于吉布斯采样的LDA在线推断过程与训练过程（图14）类似：给定文档，采样更新其中每一个词w对应的主题z（采样公式同上，采样过程中可以保持模型Nwt不变）；重复上述过程，直到文档主题直方图Ntd收敛，使用αt对其进行简单平滑即为文档主题向量。三、十亿文档、百万词汇、百万主题？从上一个小节的算法描述中，我们可以看到LDA 的训练算法貌似并不复杂，主要的工作就是在维护两个频率计数矩阵Nwt和Ntd。然而在这个时代，我们要面对的是互联网的海量数据，想象一下，如果在图15中，左边的文档节点是十亿、中间的主题个数是百万、右边不同的词的个数也是百万，我们将需要处理一张多大的图！！！在实际应用中，我们希望使用更多的数据训练更大的模型，这包含了两重意思： “更多的数据”，我们希望训练器能处理海量的训练数据，因为更多的数据蕴含着更加丰富的隐含语义，同时模型也更加准确，效果更好。上一小节提到单机版LDA训练器显然是处理不了海量数据的，使用它训练模型，我们估计要等到天荒地老了。“更大的模型”，我们希望训练器能归纳出更多更具体更长尾的隐含语义，比如一百万主题。抛开标准LDA算法本身的问题，更大的模型意味着矩阵Nwt规模更大。Nwt的大小为VxK，V表示词表大小，K表示主题个数。取V=1,000,000且K=1,000,000，Nwt需要消耗3000G以上内存（假设int型密集存储，因为模型随机初始化并不稀疏），显然单机内存是无法满足需求的，必须对模型进行切分。下面分别从数据并行和模型并行两个方面来介绍怎样解决上述两个问题。“数据并行”和“模型并行“是Google大神Jeff Dean在深度学习训练系统DistBelief[13]中新提出的两个概念，尽管Peacock系统开发的时候，DistBelief还没有真正对外公布。随着深度学习的持续升温，大家现在已经逐渐熟悉了这两个形象的名词，此处请允许我们借用一下这两个概念。3.1 数据并行——处理更多的数据“数据并行”通俗的理解：通过多任务（每个任务都包含一份完整的模型）并行的处理数据训练模型，任务之间的模型或同步或异步的进行融合。借用王益[3]的说法，“如果一个算法可以做数据并行，很可能就是可扩展的了”。幸运的是，David Newman团队发现基于吉布斯采样的LDA训练算法可以“数据并行”，并给这个算法取了一个名字叫AD-LDA[14]。注意，AD-LDA算法是吉布斯采样的近似算法，因为严格的吉布斯采样要求串行采样，不能并行。直观的理解就是语料中前一个词w1采样更新后的Nwt和Nt应该应用于后一个词w2的采样，而不是w1和w2的采样都基于相同状态的Nwt和Nt。AD-LDA算法会使得LDA的训练收敛速度变慢，但在多几轮迭代后，AD-LDA算法可以收敛到与串行吉布斯采样相同的点。图17 AD-LDA算法图17给出了AD-LDA算法的示意图：假设我们有三个可执行单元，每个都启动一个采样任务，每个任务中都有一个完整的“本地”模型LNwt；任务并行的处理训练语料数据块(W,T)和Ntd，更新模型LNwt，同时序列化更新后的训练语料数据块(W,T)和Ntd到磁盘；在迭代结束或任务处理训练语料数据块过程中，任务之间或同步或异步的融合模型。模型融合的方式可以类似MPI中的AllReduce，也可以借助全局的参数服务器GNwt。AD-LDA算法的整个过程和MapReduce的执行过程非常一致，所以早期有非常多的团队使用MapReduce来实现AD-LDA算法[5]：MapReduce的一个Job进行AD-LDA算法的一个迭代；训练语料数据块(W,T)和Ntd作为Job输入，Mapper加载上个迭代生成的GNwt作为LNwt，对数据块中的词进行主题采样；Reducer融合各个LNwt，生成下一个迭代需要加载的GNwt。因为MapReduce使用磁盘进行数据交换，同时整个训练任务需要调度几百个Jobs，所以基于MapReduce的AD-LDA实现是非常低效的。3.2 模型并行——训练更大的模型上文提到，训练大模型时，Nwt太大而无法整体放入任务的内存，直观的解决方法如图18所示，将Nwt沿词的维度进行分片，每个采样任务只加载一个模型分片N(i)wt。相应的，语料数据块也需要做对应的词维度切分，因为单个任务i只能采样N(i)wt包含的词w。细心的童鞋可能已经发现，图18所示的模型并行方式在Ntd上采用了类似AD-LDA算法的近似，LNtd间的融合与LNwt间的融合类似，相应的算法也会减缓收敛（因为Nwt是所有训练语料上的聚合结果，而Ntd只和具体文档d有关，后者变化比前者更加“快速”， Ntd的并行近似采样更加“危险”，很容易造成训练不收敛）。图18 模型并行1有没有办法不进行Ntd的并行近似采样，同时保持上述的模型切片方式呢？Peacock系统设计了图19所示的并行采样方式：加载了不同N(i)wt切片的任务并行的沿对角线方向对训练语料数据块(W,T)进行采样，一条对角线采样完成后，依次进行下一条对角线。这样在对同一个文档的不同数据块间的词进行采样时，仍然保持了“串行性”，应用了之前数据块中的词对Ntd的更新。图19的模型并行采样方式收敛性同AD-LDA是一致的。图19 模型并行23.3 大规模主题模型训练系统Peacock为了“利用更多的数据训练更大的模型”，Peacock系统结合了上述的“数据并行”和“模型并行”（图20）：多组“模型并行”任务之间采用“数据并行”的方式工作，“模型并行”任务组内部，依然保持图19所示的并行采样方式；在迭代结束或任务处理训练语料数据块过程中，不同“模型并行”任务组之间或同步或异步的融合模型分片LNiwt。模型融合的方式可以类似MPI中的AllReduce，也可以借助全局的参数服务器GNiwt。图20 Peacock中的数据并行和模型并行同上一小节“模型并行”的分析类似，Peacock系统的采样方式收敛性同AD-LDA是一致的。Max Welling团队提出的Async-LDA[6]证明了异步融合LNiwt方式的收敛性。当Peacock采用异步方式融合LNiwt时，相当于同时结合了AD-LDA和Async-LDA算法，实践证明收敛性是没有问题的。当然，Peacock系统在具体实现上除了上述的主要设计思想，还有很多的实用技巧，比如：数据传输和文档采样之间的流水线。图19所示的模型并行方式在每条对角线并行采样结束后都需要同步，怎样去掉这种同步？怎样的模型Nwt分片方式，能尽可能的保证采样服务器之间的负载均衡？我们是否需要每个迭代都重采样所有词的主题？怎样快速的计算对数似然度？怎样将模型的超参数αt和β优化融入Peacock系统？除了标准的吉布斯采样，是否有更加快速的采样算法？主题数K从100到1,000,000，系统的内部数据结构都保持不变么？在我们的论文[15]中，部分的解答了上述问题，更详细的Peacock解密请关注我们的博客“火光摇曳”[16]^_^。四、Peacock在腾讯都有哪些应用？4.1 文本语义分析为了理解互联网上海量、多样化、非结构化的自然语言描述的文本，我们通常会从词法、句法、语义等维度进行分析。受限于文本字面信息量小，存在歧义现象，词法和句法分析容易遭遇 Vocabulary Gap的问题，从海量文本数据中归纳 “知识”，从语义角度帮助理解文本，是一种非常重要的途径。图21 文本分析示例例如，对于输入文本 “红酒木瓜汤效果怎么样？”，根据人的背景知识，很容易猜到这是一位女性用户在询问丰胸产品“红酒木瓜靓汤”的效果。对于机器而言，通常会先进行词法分析，对原始文本做切词、词性标注、命名实体识别等，然后使用词袋模型（Bag of Words，BOW）或提取关键词来表示文本。不难发现，从字面抽取的信息，很容易理解成“红酒”、“木瓜”等餐饮类语义，并非原始文本真实的意思。当然，我们可以对关键词做扩展，给出一些相似的词条，但是，更好的是直接理解语义。一种常见的方法是文本分类，由于对标注语料库的依赖，类别规模一般不会太大，粒度较粗。还有一种方法就是文本聚类，挖掘语义主题标签，更细粒度的理解文本意思，隐含语义分析技术逐渐发展成为常用的解决方案。能够从十亿级别的文档中归纳上百万语义的Peacock系统更是在腾讯广点通广告系统扮演着核心角色。这些不同维度的文本分析模块，包括词袋、关键词提取、关键词扩展、文本分类和Peacock等（图21），整合在一起构成了我们理解语言的基础文本分析平台TextMiner（图22）。图22 文本分析平台TextMiner4.1.1 文本分类器文本分类是一个典型的有监督的机器学习任务，我们在做在线广告系统过程中遇到的任务就有许多，包括网页分类、广告分类、QQ群分类、用户兴趣分类等。在使用相同的标注数据集和机器学习算法情况下，如何找到有区分力的特征无疑是最为关键的。以QQ群分类为例，使用群名称、群简介、群公告等文本描述，类别体系是二级层次结构，共100+节点，标注训练数据80,000。以BOW作为基础特征，新增Peacock主题特征后，一级行业准确率和召回率均有显著提升，达5%左右，二级行业在召回率降低不到1%的情况下，准确率提升达3.86%，达到了实际应用的需求。具体数据如图23所示。图23 QQ群分类器效果4.1.2 相关性计算对给定的查询语句，搜索引擎会将检索到的网页进行排序，把相关性好的排在前面。同样的，在线广告系统应该保证展示给用户的广告与页面内容、用户兴趣相关，以尽量不影响用户体验。这里都涉及到一个共同的任务：排序学习。此问题通常被形式化为有监督的学习问题，我们会将查询、网页、用户、广告表示成语义特征向量，从而在语义空间里比较用户意图（查询、网页内容、用户历史行为）和网页、广告的相关性。Peacock已成功应用在腾讯搜索广告和情境广告中，用于分析文本数据，归纳自然语言的语义，从而更好地匹配查询词和广告，以及页面内容和广告。在情境广告 Learning To Rank 相关性计算框架下，增加Peacock语义特征后，NDCG@5提升达8.92%，线上A/B Test实验 AdCTR 提升 8.82%。相关性评估效果图24所示。图24 情境广告相关性（相关性标注样本包括4,000 查询，200,000对(查询, 广告)，标注0~3四档打分）4.2 广告CTR预估广告点击率预估是预测给定场景下一个广告被点击的概率：P(click=1|ad,user,context)，user表示当前用户，context表示当前的环境信息，譬如当前所在的网页。点击率预估是在线广告系统最核心的技术之一，它决定着广告的排序和计价。业界一般做法是将广告展示、点击日志作为训练数据，抽取特征，通过机器学习方法拟合训练数据得到预估模型，进而做在线点击率预估。选取有效的特征对得到一个精准的点击率预估模型起着至关重要的作用。Peacock是我们理解广告语义的关键技术，被引入到广告点击率预估模型中提升效果。具体的，与KDD Cup 2012 Track2的数据集产生过程类似，我们使用了腾讯情境广告系统的广告展示、点击日志，使用L1范数正则的逻辑回归训练预估模型，通过AUC评估模型精度。Baseline使用一些基础特征，优化实验分别在baseline特征集合的基础上引入主题规模为和100,000的Peacock Top-N语义特征。图25 pCTR增加不同粒度topic特征模型AUC的提升从图25可以看出，加入Peacock语义特征后AUC得到了显著提升，尤其当增加topic规模为100,000的Peacock语义特征时，AUC提升最大，约为1.8%，线上A/B Test实验AdCTR有8.82%的提升。4.3 精准广告定向在腾讯效果广告平台广点通系统里，Peacock被用于理解用户行为数据，从中归纳用户兴趣，提供广告精准定向技术。腾讯丰富的产品线拥有中国互联网公司最多的用户，有着海量、丰富的用户关系和行为数据，如QQ好友关系，QQ 群关系，电商浏览、交易，新闻浏览，查询 Query，UGC 内容（如微博、说说等），移动App 安装，微信公众号文章阅读和广告点击行为等。通过用户行为数据的挖掘可以帮助我们更好的了解用户，以推送精准的广告。而这些数据都可以形式化为用户-物品矩阵，如用户-用户、QQ-QQ群，用户-应用（Apps），用户-搜索词（或搜索Session），用户-URLs等。我们利用Peacock系统对上述用户-物品做矩阵分解（如图3），从不同数据来源，多视角理解用户兴趣，进而挖掘相似用户，提供给广告主丰富的定向策略，如用户商业兴趣定向、关键词定向和Look-Alike定向等。同时，获取到的用户特征，也可以作为广告CTR、CVR预估系统的重要特征。4.4 QQ群推荐图26 QQ群推荐根据用户已加QQ群社交关系数据，利用Peacock对QQ-QQ群做矩阵分解，我们发现语义相近的QQ群被比较好的归到了相同的主题下，如图8、9、10所示。非常直观的，我们将Peacock 模型应用在QQ群消息面板推荐产品中（如图26），相比基于QQ好友关系链的推荐算法，推荐群的点击率和转化率（即点击后是否加入了该群）均有2~3倍的提升（图27）。P(QQGroup│user)=∑topicP(QQGroup|topic)?P(topic|user)(2)图27 QQ群推荐效果后记LDA是一个简洁、优雅、实用的隐含主题模型，腾讯效果广告平台部（广点通）的工程师们为了应对互联网的大数据处理，开发了大规模隐含主题模型建模系统，并在腾讯的多个业务数据中得到了应用。本文由赵学敏、王莉峰、王流斌执笔，靳志辉、孙振龙等修订，相关工作由腾讯SNG效果广告平台部（广点通）质量研发中心Peacock团队王益、赵学敏、孙振龙、严浩、王莉峰、靳志辉、王流斌为主完成，苏州大学曾嘉教授、实习生高阳，香港科技大学杨强教授等持续大力支持，是多人合作的结果。参考文献[1] Greg Linden, Brent Smith, and Jeremy York.
Recommendations: Item-to-Item Collaborative Filtering. IEEE Internet Computing, 2003.[2] Simon Funk. Netflix Update: Try This at Home. http://sifter.org/~simon/journal/.html.[3] 分布式机器学习的故事. http://cxwangyi.github.io//distributed-machine-learning/.[4] LinkedIn高级分析师王益: 大数据时代的理想主义和现实主义(图灵访谈). .cn/article/75445.[5] PLDA and PLDA+. /p/plda/.[6] Arthur Asuncion, Padhraic Smyth, and MaxWelling. Asynchronous Distributed Learning of Topic Models. NIPS’2008.[7] Yahoo_LDA. /shravanmn/Yahoo_LDA.[8] MALLET. http://mallet.cs.umass.edu/.[9] Mark Steyvers, and Tom Griffiths. Probabilistic topic models. In T. Landauer, D McNamara, S. Dennis, and W. Kintsch (eds), Latent Semantic Analysis: A Road to Meaning. Laurence Erlbaum, 2006.[10] D. Blei, A. Ng, and M. Jordan. Latent Dirichlet allocation. JMLR’2003.[11] Thomas L. Griffiths, and Mark Steyvers. Finding scientific topics.PNAS’2004.[12] Gregor Heinrich. Parameter estimation for text analysis. Technical Report, 2009.[13] Jeffrey Dean, Greg S. Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Quoc V. Le, Mark Z. Mao, Marc’Aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, Andrew Y. Ng. Large Scale Distributed Deep Networks. NIPS’2012.[14] David Newman, Arthur Asuncion, Padhraic Smyth, and MaxWelling.Distributed Algorithms for Topic Models. JMLR’2009.[15] Yi Wang, Xuemin Zhao, Zhenlong Sun, Hao Yan, Lifeng Wang, Zhihui Jin, Liubin Wang, Yang Gao, Ching Law, and Jia Zeng. Peacock: Learning Long-Tail Topic Features for Industrial Applications. TIST’2015.[16] 火光摇曳. /.本文链接：Peacock：大规模主题模型及其在腾讯业务中的应用
您可能感兴趣的微信公众号文章
微信扫一扫关注该公众号
版权声明：本站非腾讯微信官方网站,本站收录微信公众号和微信文章内容全部来自于网络,如果有侵犯您的知识产权的内容，请与我们联系，我们会及时修改或删除。
Copyright (C)
, All Rights Reserved
技术支持：厦门指间互联信息科技有限公司
闽ICP备号-2