Dong Guo's Blog

Expectation Propagation: Theory and Application

| Comments

简介

第一次接触EP是10年在百度实习时,当时组里面正有计划把线上的CTR预估模型改成支持增量更新的版本,读到了微软一篇基于baysian的CTR预估模型的文章(见推荐阅读5),文章中没有给出推导的细节,自己也没有继续研究。今年在PRML中读Approximal inference这章对EP有了一些了解,同时参考了其它相关的一些资料,在这里和大家探讨。

什么是期望传播

期望传播(Expectation Propagation): 基于bayesian的一种近似推断方法,常用于图模型中计算单个节点的边缘分布或者后验分布,属于message passing这一类推断方法。

牛人

首先当然是Thomas Minka, 其在MIT读博期间提出了EP,并将EP作为博士论文课题在2001年发表。Minka毕业之后去了CMU教书,现在和Bishop一起在剑桥微软研究院。

其次是Kevin p. Murphy, 他是我做EP相关文献调研时发现的paper比较多的,我读到的一篇全文基本都是在推导Minka博士论文中一些公式的细节。btw Murphy 2013年出版了一本书,见推荐阅读2。

中英文对照

下面是一些关键词的中英文对应 (由于相关的书籍文献基本都是英文的,有些词没有想到比较好的中文翻译,故保留英文)

截断高斯: Truncated Gaussian

置信传播: Belief Propagation (后面会简称BP)

期望传播: Expectation Propagation (后面会简称为EP)

消息传递: Message passing

背景

EP本身的思想和方法都还是比较简单的,不过会涉及到一些背景知识,这边一并介绍。

高斯、截断高斯

EP的核心思想之一是用指数族分布近似复杂分布,实际应用中通常选择高斯分布,所以多个高斯分布的乘积,相除,积分在EP应用过程中不可避免。

截断高斯是高斯分布在指定区间归一化后的结果,(所以其并不是一个高斯分布),EP本身并不和截断高斯直接相关,但是如果在分类问题中应用EP,对观察样本(0-1)建模方法通常是y=sign(f(x)>t), 和另一个高斯分布相乘之后即为截断高斯分布。(然后就需要计算其的均值方差,原因后面会提到)

我在另一篇文章Gaussian and Truncated Gaussian中介绍了比较多的细节,可以参考。

指数族分布

指数族分布(exponential family distribution)有着非常好的特性,比如其有充分统计量,多个指数族分布的乘积依然是指数族分布,具体的介绍可以参见wikipedia, 介绍的非常全面,也可以参考PRML第2章。

由于指数族的良好特性,其常被拿去近似复杂的概率分布(EP和variance baysian都是)。由于EP中常常选择高斯分布,我们这边强调一下,高斯分布的充分统计量为: (x, x2), 其中x为高斯分布的自变量。

图模型

EP是贝叶斯流派的计算变量后验分布(或者说是边缘分布)的近似推断方法,通常都可以通过一个概率图模型来描述问题的生成过程(generation process),所以可以说图模型是EP的典型应用场景。

图模型在很多地方都有介绍,比如PRML第8章,在这里就不重复了。有1点提一下,一个图模型的联合分布(不管是有向图还是无向图)可以写成若干个因子的乘积,对于有向图每个因子是每个节点的条件分布(条件于其的所有直接相连的父节点),对于无限图每个因子是energy function。 这个特性在后面的置信传播算法会用到。

factor graph

图模型中节点之间的关系通过边来表达,factor graph将这种节点之间的关系通过显式的节点(factor node)来表达,比如对于有向图,每个factor node就代表一个条件概率分布,图中的所有的信息都存在于节点上(variable nodes和factor nodes)。

后面的BP和EP都基于factor graph,可以认为factor graph使得图上的inference方法变得比较直观,另一个好处是factor graph屏蔽了有向图和无向图的差异。(有向图无向图都可以转变为factor graph)

更多了解可以看PRML第8章。

置信传播

Belief Propagation (BP)又叫’sum-product’,是一种计算图模型上节点边缘分布的推断方法,属于消息传递方法的一种,非近似方法(基于其延伸的Loopy Belief propagation为近似推断方法)。 BP的核心为如下3点:

  • 单个variable node边缘分布的计算

(注:上图来之PRML)

前面提到过图模型的联合分布可以分解为若干因子的乘积,每个因子对应一个factor node:

每个variable node的边缘分布为与其直接相连的factor nodes传递过来的message的乘积:

  • 从factor node到variable node的消息传递

(注:上图来之PRML)

从factor node f传递到variable node x的message为:与f直接相连(除了x)的variable nodes传递到f的messages与f本身的乘积的积分(积分变量为与f直接相连的除x之外的所有variable nodes):

  • 从variable node到factor node的消息传递

(注:上图来之PRML)

从variable node x到factor node f的message为:与x直接相连的factor nodes(除f以外)传递到x的messages的乘积:

更多细节请参考PRML

Moment matching

在实际的问题中,要么后验分布本身比较复杂(推荐阅读3中的Clutter example),要么最大化后验的计算比较复杂,要么破坏了具体算法的假设(比如EP要求图中的所有message都是指数族),所以常常会用(有良好性质的)指数族分布近似实际的概率分布。

用一个分布去近似另一个分布的常见方法是最小化KL散度:

我们发现通过最小化KL散度得到的‘最接近’p(x)的q(x)可以简单地通过匹配充分统计量的期望得到。

当q(x)为高斯分布的时候,我们知道其充分统计量u(x)=(x, x2),这时通过KL散度最小化近似分布近似的方法称为moment matching(匹配矩)

为什么称为匹配矩呢,看看矩的定义就知道了:

期望传播方法-理论

EP的思想:在图模型中,用高斯分布近似每一个factors,然后’approximate each factor in turn in the context of all remaining facotrs’.

下面为具体的算法: (注:本算法参考了PRML)

下面通过Minka博士论文中的例子‘clutter problem’来解释:每个观察样本以(1-w)的概率由高斯分布N(x|sita, I)生成,以w的概率由noise生成(同样也是高斯分布N(x|0, aI)),于是:

按照EP的思想,我们用一个单高斯q(sita)去近似混合高斯p(x|sita)

单高斯去近似混合高斯听起来效果一定不好,但实际上,由于EP在近似的时候乘了其他所有factors的高斯近似之后的上下文,考虑到很多个高斯分布相乘之后的方差一般都很小,所有实际上单高斯只需要在很小的区间近似好混合高斯即可。如下图:

(注:上面2张图来之PRML)

其中蓝色曲线为混合高斯(没有画完整),红色曲线为近似的单高斯,绿色曲线为‘其它所有factor的乘积’。

EP怎么应用在message passing中:

在图模型中,所谓的’context of all remaining factors’就是当前节点之外所有节点和messages,所以EP在图模型中的使用方式为:和BP一样的方法计算message和marginal distribution,当某个factor或者marginal distribution不是高斯分布时,用高斯分布近似它。所以Minka认为EP也就是BP+moment matching。

由于每个factor以及variable node的边缘分布都是高斯分布(或被近似为高斯分布),所以EP的计算过程一般并不复杂。

期望传播方法-应用

EP被广泛地应用在图模型的inference上,这边提一下微软的2个应用:Bing的CTR预估,XBOX游戏中player skill的评估。

Bing的CTR预估

详细的推导及实验请参考:Bayesian CTR prediction for Bing paper中称这个model为ad predictor,其在我的数据集上预估效果很不错,训练预测速度快,天然支持增量更新,主要的缺点就是模型不是稀疏的。如果你知道怎么自然地达到稀疏效果,请指教。

和其它算法的比较请参考:Classification Models

XBOX中player skill的评估

图模型和上一篇略有差异,推导过程差不多,paper中没有给出详细的推导过程,不过Murphy的新书中给出了,请参考推荐阅读2。

一些小结

  1. EP的通用性比较好,对于实际的问题,画出graph model和factor graph,就可以尝试用EP来进行inference;
  2. 虽然应用EP时的推导过程略长(计算很多个message和marginal distribution),但是最终的整体的更新公式一般都非常简单,所以模型训练时间开销往往较小;
  3. 为了使用EP,只能用高斯分布来建模,比如Bing的CTR预估那篇对每个feature的weight建模,只能假设服从高斯分布,相当于是2范数的正则化,不能达到稀疏模型的效果;
  4. 在我的实验中,通过EP进行inference得到的模型预估效果不错,值得一试;

推荐阅读

  1. 机器学习保留书籍:Pattern recognition and machine learning 第2,8,10章 (第2章看看高斯四则运算,指数族分布特性;第8章了解图模型基础,期望传播算法;第10章了解期望传播算法)

  2. Murphy新书: Machine Learning: A Probabilistic Perspective 第22章 (本书相比PRML更加具体,第22章干脆包含了TrueSkill的详细推导步骤)

  3. Minka的博士论文:A family of algorithms for approximate Bayesian inference (想了解基本思想和理论看完前3节即可)

  4. EP的应用之一:TrueSkill: A Bayesian Skill Rating System (文中并没有给出EP每一步的细节)

  5. EP的应用之二:Web-Scale Bayesian Click-Through Rate Prediction for Sponsored Search Advertising in Microsoft’s Bing Search Engine (CTR预估的应用比较吸引人,文章写得很棒,算法的效果也很好,只是干脆忽略的inference过程,有兴趣的同学可以参看我另一个文章,里面有一步一步推导的过程)

  6. Minka整理的EP学习资料:link (其中的包含了一个videolecture上他做的variance inference的talk值得一看)

  7. 本文的PPT: 墙外, 墙内

Classification Models

| Comments

During my past 3 years in career, following classifiers are often used for classification tasks.

Typcial classifiers comparision

Decision Tree

Decision Tree is not a start-of-art model for classification or regression, and when there are huge features(say millions) it will take a long time for training. But it may perform very well when the number of distinct features are limited, and the classification/regression task is obviously non-linear.

A typical scenario is multi-model fusion: you have trained multiple models for single task, and you want to generate the final prediction result using all these models. Based on my past experiments, Decision Tree can out perform linear model(linear regression, logistic regression and so on) on many datasets.

RDT, random forest, boosting tree

All of these 3 models are ensemble learning method for classification/regression that operate by constructing multiple Decision Tree at training time. For RDT(random decision tree), only part of total samples are used to training each tree. And all features are considered for splitting.

Similar with RDT, random forest also use part of total sampels to construct each tree, but it also only use subset of features/dimisions for splitting. So random forest introduces more ‘random’ factors for training, and it may perform better when there are more noises in training set.

boosting tree is actually forward stagwise additive modeling with decision tree as base learner. And if you choose exponential loss function, then boosting tree becauses Adaboost with decision tree as base learner. Here is one slide about additive model and boosting tree.

Generalized linear model

One of the most popular generalized linear model is logistic regression, which is generalized linear model with inversed sigmoid function as the link function. There are multiple different implementation for logistic regression, and here are some often used by me.

Logistic regression optimized with SGD.

It’s very basic, so I ignore the details here

OWLQN

It was proposed by Microsoft in paper Orthant-Wise Limited-memory Quasi-Newton Optimizer for L1-regularized Objectives of ICML 2007. You can also find the source code and executable runner via this link.

This model is optimized by a method which is similar with L-BFGS, but can achieve sparse model with L1 regularizer. I recommend you try this model and compare with other models you are using in your dataset. Here are four reasons:

  1. It’s fast, especially when the dataset is huge;
  2. It can generate start-of-art prediction results on most dataset;
  3. It’s stable and there are few parameters need to be tried. Actaully, I find only regularization parameters can impact the performance obviously;
  4. It’s sparse, which is very important for big dataset and real product. (Of course, sparse is due to L1 regularizer, instead of the specific optimization method)

One problem is it’s more challenge to implement it by yourself, so you need spend some time to make it support incremental update or online learning.

FTRL

It was proposed by Google via paper Ad Click Prediction: a View from the Trenches in 2013. I tried on my dataset, and this implementation can generate similar prediction performance with OWLQN. It’s quicker than OWLQN for training, and it’s also sparse. One advantage is it’s very easy to implement, and it support increamental update naturally. One pain point for me is this model has 3-4 parameters need to be chosen, and most of them impact the prediction performance obviously.

Ad predictor

This paper was also proposed by Microsoft in ICML 2009.

One biggest different with upper 3 implementation is it’s based on bayesian, so it’s generative model. Ad predictor is used to predict CTR of sponsor search ads of Bing, and on my dataset, it could also achieve comparable prediction performance with OWQLN and FTRL. Ad predictor model the weight of each feature with a gaussian distribution, so it natually supports online learning. And the prediction result for each sample is also a gaussian distribution, and it could be used to handle the exploration and exploitation problem. See more details of this model in another post.

Neural Network

ANN is so slow for training, so it’s tried only when the dataset is small of medium. Another disadvantage of ANN is it’s totally blackbox.

SVM

SVM with kernel is also slow for training. You can try it with libsvm.

Gaussian and Truncated Gaussian

| Comments

Everybody knows about Gaussian distribution, and Gaussian is very popular in Bayesian world and even in our life. This article summaries typical operation of Gaussian, and something about Truncated Guassian distribution.

Gaussian

pdf and cdf

Sum/substraction of two independent Gaussian random variables

Please take care upper formula only works when x1 and x2 are independent. And it’s easy to get the distribution for variable x=x1-x2 See here for the detils of inference

Product of two Gaussian pdf

Please take care x is no longer a gaussian distribution. And you can find it’s very elegant to use ‘precision’ and ‘precision adjusted mean’ for Gaussian operation like multiply and division. See here for the detils of inference

Division of two Gaussian pdf

Intergral of the product of two gaussian distribution

Truncated Gaussian

Truncated Gaussian distribution is very simple: it’s just one conditional (Gaussian) distribution. Suppose variable x belongs to Gaussian distribution, then x conditional on x belongs to (a, b) has a truncated Gaussian distribution.

Calculate expectation of Truncated Gaussian

Calculate variance of Truncated Gaussian

Bayesian CTR Prediction of Bing

| Comments

Microsoft published a paper in ICML 2009 named ‘Web-Scale Bayesian Click-Through Rate Prediction for Sponsored Search Advertising in Microsoft’s Bing Search Engine’, which is claimed won the competition of most accurate and scalable CTR predictor across MS. This article shows how to inference this model(let’s call it Ad predictor) step-by-step.

Pros. and Cons.

I like it because it’s totally based on Bayesian, and Bayesian is beautiful. Online learning is naturally supported, and the precition accuracy is comparable with FTRL and OWLQN. And both training and prediction is light-weight and fast. Btw: one shortage of this model is it’s not sparse, which may be a big issue when applied on big dataset with huge amount of features.

Inference using Expectation Propagation step by step

Firstly, following is the factor graph of ad predictor.

For each sample, we can use the formula of step 13 to update the posterior parameter of W, which is very easy to be implemented.

Prediction

After training, we can predict with following formula:

Prediction Accuracy

I compared it with FTRL and OWLQN on one dataset for age&gender prediction. AUC of this model is comparable with OWLQN and FTRL, so I recommend you have a try in your case.

Insights

  1. You can find variance of each feature increases after every exposure, which makes sense.

  2. This model shows samples with more features will have bigger variance, which does not make sense very much. I think the reason is we assume all the features are independent. Any insights from you?

Notes for Distributed System Theory

| Comments

过去三年参与的广告相关的项目都基于各种各样的分布式存储和计算系统,比如hdfs, hbase, cassandra cluster, memcached cluster, Druid, hadoop和spark。最近在研究各个系统的原理,周末浏览了一本电子书《分布式系统原理介绍》,介绍了很多重要的基础知识,推荐浏览。

Key words:

数据存储方式,consistent hashing,数据副本,副本控制协议,Lease机制,Quorum机制,日志技术,Paxos协议,CAP理论

consistent hashing: 分布式数据存取的经典方案

  1. 背景:数据的分布式存储的一种简单方式为hash, 这种方法简单,无需纪录数据存放在哪台node上。但是当集群需要拓展(或者减少)机器时,由于hash结果一般和机器数目有关,数据需要重新迁移;
  2. Consistent hashing将key组织成一个环,每个node负责一段连续的子环,当增加一个node时,只需要将临近的一个node上的部分数据copy到新node,不停机的情况下,对hit rate的影响明显减小;
  3. 需要额外存储的元数据只有node在环上的顺序,数据量小;
  4. 有一个缺点是:每次加入一个node,只能减轻现有的一个node的压力。且如果是随即分配node在环上的顺序,将很难保证在每个node的’负载均衡’;
  5. 一个较好的解决方案是引入’virtual nodes’: 首先假设有比真实nodes个数明显多的virtual nodes。这个个数是固定的,所以可以预先将其均匀地分布到环上。通过元数据将每个real node关联上多个virtual nodes,注意不是连续的,一般选在环上分隔较远的virtual nodes。这样的话,每加入一个real node,将会将属于其他real nodes的几个virtual nodes分配给新加入的real node,分担了多个real nodes的压力。反之,当一个real node失败,可以有多个real nodes来分担压力。

数据副本: 分布式系统提供高容错高用可行的重要手段

  1. 有2种最常见的数据副本存储方案,一种是以机器为粒度,一种是以数据块为粒度。
  2. 以机器为粒度的缺点:
    • 一旦某台机器数据丢失,数据恢复的效率不高,因为一般需要从非常有限台机器copy数据。而且会比较消耗copy from机器的资源,往往需要让一台机器下线,或者限制copy的速度;
    • 一旦某台机器宕机,压力被有限的几台副本机器分担(若3台机器互为副本,则剩余机器的数据访问压力提高50%)
    • 增加一台机器无法扩容,必须一下增加若干台机器(互为副本)
  3. 以数据块为粒度的好处:(相对应)
    • 一旦某台机器数据丢失,可以从剩余的所有机器上copy数据,数据恢复的效率高
    • 一台机器宕机,不会给任何单台机器增加明显压力;
    • 扩容容易

副本控制协议: 控制各副本数据读写行为,使得副本满足一定可用性和一致性

  1. 中心化副本控制协议:中心结点负责数据的更新,并发控制,协调副本一致性;单点故障
    • primary node在将更新同步到各个secondary nodes时,限于primary node的压力,往往只同步给有限几个secondary nodes,后续采用接力的方式
    • 同步过程的中间状态,包括同步失败的处理,以及access状态的返回,决定了系统的数据一致性
    • primary node宕机由于需要时间来发现(比如10s),在这段时间内无法更新数据
  2. 去中心化副本控制协议
  3. 实例 (大部分分布式数据存储系统都使用primary-secondary副本控制协议)
    • GFS: primary-secondary
    • PUNTS(yahoo!的分布式数据存储平台): 使用primary-secondary协议
    • Dynamo/Cassandra: 使用去中心化副本控制协议
    • Zookeeper: 使用去中心化协议选出primary node,之后就转变为中心化的副本控制协议

Lease机制:保证secondary nodes和primary node的一致性

  1. primary node在向cache nodes同步数据时,还会附带一个时间戳表达这份数据的有效期。在有效期内primary node保证不修改数据,cache nodes可以放心使用数据。
  2. 带来的cost是:若某个cache node提高修改元数据请求,primary node需要阻塞所有cache nodes对该份数据的读写请求,并等待到该份数据的lease超时才修改元数据。
  3. 所以lease的时长比较关键:太长会导致availability下降,太短会导致cache nodes频繁同步primary node;常使用10s
  4. lease机制用于primary node的选择:primary node的更改主要由于结点宕机,而传统的Heartbeat的方法不能有效监控结点状态(存在网络失败,监控机器本身性能问题导致的延时等),故每当nodes给监控机器发heartbeat时,返回一个lease,若primary node心跳失败,则等待lease过期后,监控结点更换primary node
  5. lease机制应用的实例
    • GFS中用于master挑选primary node
    • Chubby(google的分布式文件系统) 有2处使用了lease机制 a). secondary nodes承诺在一段时间内不重新选举primary node; b). primary node用于监控secondary nodes的状态
    • Zookeeper: primary node向client颁发lease

Quorum机制: 可用性和一致性的权衡

  1. 在存在N个副本的情况下,对于更新操作,只要在W在副本上更新成功,则算该更新成功(“成功提交的更新操作”)。当读取R个副本时(限制R+W>N),就可以保证可以读到更新之后的数据。
  2. 注意:仅依赖quorum机制无法知道最新成功提交的版本号,故无法保证强一致性(系统应该始终返回最新的成功提交的数据),需要通过其他方式获取系统最新成功提交的数据;
  3. Quorum机制体现了CAP理论中的availability(update时只需要更新了W个副本,read时只需要读取R个副本)和consistent(由于update或者read只需要在部分副本上成功即可,导致了仅follow Quorum机制不能保证强一致性)的权衡:

更高效地工作学习

| Comments

周末浏览了一本书《小强升职记》,介绍了工作中事情管理的很多经验,个人觉得帮助挺大,在这边分享一下。

  1. 将事情按照重要性、紧急性2个维度分成4个象限。

    1. 第一象限(重要且紧急):立马去做;思考“这些事情真的都是重要且紧急的吗?”,“为什么这些事情会进入这个象限?”;
    2. 第二象限(重要但不紧急):尽量开始去做,没时间的话第一时间进行任务分解,制定时间表;
    3. 第三象限(不重要但紧急):注意紧急和重要一点关系没有;思考“如何尽力减少这类事情?”
    4. 第四象限(不重要且不紧急):尽量别做
  2. 走出第三象限(不重要但紧急):Monkey theory 甩掉自己身上的猴子,将猴子放回到主人身上 (书中这段举的例子很有意思) 比如:“朋友问:这周六咱们去游泳吧;你答:好啊,到时候你提前给我打电话,有时间的话,我一定去”。 比如“新来的同事问:你好,能不能给我讲讲pre-demo这个项目;你答:好啊,能不能你先看一下咱们wiki上的文档,你总结问题之后咱们一起讨论?” 另外,第三象限中的事情可以想办法delegate给别人去做

  3. 第二象限是精力分配的重点 有2个原因:这些事是重要的;这些事安排处理好了,进入第一象限的事情也会明显变少; 目标描述和任务分解:让自己清晰地自己有哪些细分的是要做,每个时段的任务是什么,明确地知道该任务是否拖延;有利于减轻自己的压力;

  4. 时段工作法:将待做的事情分配到各个小时,每个小时或者任务完成后勾掉任务,给自己增加压力,督促自己提高效率; 这种方法还可以让自己了解自己的高效、低效时段在哪

  5. 每周(天)开始前将要做的事情分到4个象限; 优先做(或者在自己效率最高的时段)做第一第二象限的事情;同时按照时段工作法进行

  6. 一些tips 尽量午休 做一件事情的时候尽量不让自己给打断(如果同事来讨论问题,可以说一会去找他,同时记录下这件事情),专注心如止水地做事 关掉outlook的邮件提醒,绝大部分邮件都不需要立即响应,每半天主动检查一次邮件即可; 安排计划前提前考虑已经被预约掉的时间; 保持办公环境,特别是办公桌的整洁有序; 刚到公司或者吃完饭回到公司,先给水杯打满水再工作;