Rephil和MapReduce: 描述长尾数据的数学模型

Google Rephil是Google AdSense背后广告相关性计算的头号秘密武器。但是这个系统没有发表过论文。只是其作者(博士Uri Lerner和工程师Mike Yar)在2002年在湾区举办的几次小规模交流中简要介绍过。所以Kevin Murphy把这些内容写进了他的书《Machine Learning: a Probabilitic Perspecitve》里。在吴军博士的《数学之美》里也提到了Rephil。 Rephil的模型是一个全新的模型,更像一个神经元网络。这个网络的学习过程从Web scale的文本数据中归纳海量的语义——比如“apple”这个词有多个意思:一个公司的名字、一种水果、以及其他。当一个网页里包含”apple”, “stock”, “ipad”等词汇的时候,Rephil可以告诉我们这个网页是关于apple这个公司的,而不是水果。 这个功能按说pLSA和LDA也都能实现。为什么需要一个全新的模型呢? 从2007年至今,国内外很多团队都尝试过并行化pLSA和LDA。心灵手巧的工程师们,成功的开发出能学习数万甚至上十万语义(latent topics)的训练系统。但是不管大家用什么训练数据,都会发现,得到的大部分语义(相关的词的聚类)都是非常类似,或者说“重复”的。如果做一个“去重”处理,几万甚至十万的语义,就只剩下几百几千了。 这是怎么回事?   如果大家尝试着把训练语料中的低频词去掉,会发现训练得到的语义和用全量数据训练得到的差不多。换句话说,pLSA和LDA模型的训练算法没有在意低频数据。 为什么会这样呢?因为pLSA和LDA这类概率模型的主要构造单元都是指数族分布(exponential family)。比如pLSA假设一个文档中的语义的分布是multinomial的,每个语义中的词的分布也是multinomial的。因为multinomial是一种典型的指数族分布,这样整个模型描述的海量数据的分布,不管哪个维度上的marginalization,都是指数族分布。在LDA中也类似——因为LDA假设各个文档中的语义分布的multinomial distributions的参数是符合Dirichlet分布的,并且各个语义中的词的分布的multinomial distributions的参数也是符合Dirichlet分布的,这样整个模型是假设数据是指数族分布的。 可是Internet上的实际数据基本都不是指数族分布的——而是长尾分布的。至于为什么是这样?可以参见2006年纽约时报排名畅销书The Long Tail: Why the Future of Business is Selling Less of More。或者看看其作者Chris Anderson的博客The Long Tail。 长尾分布的形状大致如下图所示: 其中x轴表示数据的类型,y轴是各种类型的频率,少数类型的频率很高(称为大头,图中红色部分),大部分很低,但是大于0(称为长尾,图中黄色部分)。一个典型的例子是文章中词的分布,有个具体的名字Zipf’s law,就是典型的长尾分布。而指数族分布基本就只有大头部分——换句话说,如果我们假设长尾数据是指数族分布的,我们实际上就把尾巴给割掉了。 割掉数据的尾巴——这就是pLSA和LDA这样的模型做的——那条长尾巴覆盖的多种多样的数据类型,就是Internet上的人生百态。理解这样的百态是很重要的。比如百度和Google为什么能如此赚钱?因为互联网广告收益。传统广告行业,只有有钱的大企业才有财力联系广告代理公司,一帮西装革履的高富帅聚在一起讨论,竞争电视或者纸媒体上的广告机会。互联网广告里,任何人都可以登录到一个网站上去投放广告,即使每日广告预算只有几十块人民币。这样一来,刘备这样织席贩屡的小业主,也能推销自己做的席子和鞋子。而搜索引擎用户的兴趣也是百花齐放的——从人人爱戴的陈老师苍老师到各种小众需求包括“红酒木瓜汤”(一种丰胸秘方,应该出丰胸广告)或者“苹果大尺度”(在搜索范冰冰主演的《苹果》电影呢)。把各种需求和各种广告通过智能技术匹配起来,就酝酿了互联网广告的革命性力量。这其中,理解各种小众需求、长尾意图就非常重要了。 实际上,Rephil就是这样一个能理解百态的模型。因为它把Google AdSense的盈利能力大幅提升,最终达到Google收入的一半。两位作者荣获Google的多次大奖,包括Founders’ Award。 而切掉长尾是一个很糟糕的做法。大家还记得小说《1984》里有这样一个情节吗?老大哥要求发布“新话”——一种新的语言,删掉自然英语中大部分词汇,只留下那些主流的词汇。看看小说里的人们生活的世界,让人浑身发毛,咱们就能体会“割尾巴”的恶果了。没有看过《1984》的朋友可以想象一下水木首页上只有“全站十大”,连“分类十大”都删掉之后的样子。 既然如此,为什么这类模型还要假设数据是指数族分布的呢?——实在是不得已。指数族分布是一种数值计算上非常方便的数学元素。拿LDA来说,它利用了Dirichlet和multinomial两种分布的共轭性,使得其计算过程中,模型的参数都被积分给积掉了(integrated out)。这是AD-LDA这样的ad hoc并行算法——在其他模型上都不好使的做法——在LDA上好用的原因之一。换句话说,这是为了计算方便,掩耳盗铃地假设数据是指数族分布的。 实际上,这种掩耳盗铃在机器学习领域很普遍。比如有个兄弟听了上面的故事后说:“那我们就别用概率模型做语义分析了,咱们还用矩阵分解吧?SVD分解怎么样?” 很不好意思的,当我们把SVD分解用在语义分析(称为LSA,latent semantic analysis)上的时候,我们还是引入了指数族分布假设——Gaussian …

Rephil和MapReduce: 描述长尾数据的数学模型 Read More »