如果当我24岁时，
我们还在一起，
我们牵手去见彼此的家人，
获取他们的认同
如果当我26岁时，
我们还在一起，
我会挽起留了很久的长发，
做你最美的新娘
如果当我28岁时，
我们还在一起，
我们一起期待着迎接那个加入我们小家庭的新生命的降临
如果当我29岁时，
我们还在一起，
我们一起用心经营我们的家，
每天听着宝宝稚嫩的声音叫我们“爸爸”、“妈妈”
如果当我33岁时，
我们还在一起，
不管周围的人如何分分和和，
我们一起携手坚定的走过那3年之痛、7年之痒，
继续着我们的幸福
如果当我40岁时，
我们还在一起，
就算最初的激情已被现实的生活打磨殆尽，
一切归于平淡，
但彼此的目光仍然会追逐着对方的身影，
相视一笑也会觉得安心
如果当我50岁时，
我们还在一起，
孩子离开我们去追寻他的幸福，
虽然想念宝宝，
依然还有你陪在我的身边，
每天傍晚手牵手一起散步
如果当我60岁时，
我们还在一起，
我们都已该休息，
有了大把的时间一起去做彼此曾经想做而没做的事，
去想去而没去过的地方
如果当我70岁时，
我们还在一起，
身边的孩子们都已经称呼我们“爷爷”、“奶奶”，
你还是当我是个不会照顾自己的孩子，
呵护着你眼中的“孩子”
如果当我76岁时，
我们还在一起，
我们要通知所以认识的人，
邀请所有的人来参加我们的金婚纪念日，
分享我们的幸福快乐
如果当我80岁时，
我们还在一起，
我们会每天躺在摇椅上一起晒太阳，
虽然不知道生命会持续到哪一天，
因为身边有彼此的陪伴，
不再恐惧死亡，
享受生命中的每一天
如果当我走到生命的最后一天时，
我希望身边有你陪伴，
我不要做那个留下来的人，
请允许我自私的先离开这个世界，
又或者你坚持不了了，我愿意陪你一同远去...
因为，
没有你的世界是冰冷的，
所以，
亲爱的，
如果到了那一天，
请让我先走，或带上我一起，
因为，
曾经属于
两个人共享的幸福我一个人收纳不了......
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
死生契阔 与子相悦 执子之手 与子偕老 才是幸福
Thursday, July 1, 2010
Tuesday, June 8, 2010
EP-LDA 0.2 更正版！！！
这次主要debug了一下Gamma函数，原先计算Scaler的时候直接套用Gamma Function的定义计算，容易导致溢出（用Matlab算几个值就知道了），这次改为用log_gamma()进行计算，避开计算Gamma函数的乘积。貌似这次效果要好些，但是应该还是会有bug，以后再慢慢调不着急嘿嘿。
贴个链接：https://www.cs.indiana.edu/~kduan/rsc/2010/lda-ep-0.2.tar
贴个链接：https://www.cs.indiana.edu/~kduan/rsc/2010/lda-ep-0.2.tar
Monday, June 7, 2010
EP-LDA!!!
从开始看LDA到最后初步写完了基于EP的LDA算法！前前后后花了将近三周？忘了，反正很长。。。刚开始时候看LDA的那叫个一头雾水啊。。看到最后才发现，好像不是因为很难，而是自己懂的东西太少了。。Blei的那篇文章从头到尾看下来，发现要是不好好学一下Graphical Model和Machine Learning的话那是基本上在这个方向发展无望的，当然还有最优化相关的知识吧。。。Anyway，今天整理了下代码，感觉还不错嘿嘿。。（狞笑）
废话少说，贴出来几个很有用的reference，算是又一个reading list吧。。。
1. http://research.microsoft.com/en-us/um/people/minka/papers/ep/
这个是Minka所有关于EP的paper list，怎么说的，非常想感慨的一下是，这样的人之所以能有这样好的idea，可能和美国对孩子的教育方式是很有关系的，中国的孩子学习能力超强的，但是又有什么用呢，总是会被别人牵着鼻子走，很难会有很创新的idea。。想到刚刚发布的iphone 4和大陆那么多代工工厂，不禁汗一下，难道中国人生来就是“任劳任怨”的么。。。好像扯淡扯远了，let's make idea!!!
2. http://www.cs.princeton.edu/~blei/.../BleiNgJordan2003.pdf
LDA的开篇之作，没啥可说的，自己写了一个learning notes也一并贴出来，当然写的很简陋，仅仅是这篇paper里边我感觉比较难的地方的推导过程（又一个只会学习的！）请见这里：https://www.cs.indiana.edu/~kduan/rsc/2010/lda-report.pdf
3. http://chasen.org/~daiti-m/dist/lda/
代码框架借鉴的是这位大神，这个是用variational inference也就是原始paper里边的推理方法。代码写的相对来说比较容易懂，所以就没有用Blei自己release的代码，那个应该是写的很完美的，可是比较难理解，对本人这样的菜鸟还是留着以后慢慢研究，哈哈
废话少说，贴出来几个很有用的reference，算是又一个reading list吧。。。
1. http://research.microsoft.com/en-us/um/people/minka/papers/ep/
这个是Minka所有关于EP的paper list，怎么说的，非常想感慨的一下是，这样的人之所以能有这样好的idea，可能和美国对孩子的教育方式是很有关系的，中国的孩子学习能力超强的，但是又有什么用呢，总是会被别人牵着鼻子走，很难会有很创新的idea。。想到刚刚发布的iphone 4和大陆那么多代工工厂，不禁汗一下，难道中国人生来就是“任劳任怨”的么。。。好像扯淡扯远了，let's make idea!!!
2. http://www.cs.princeton.edu/~blei/.../BleiNgJordan2003.pdf
LDA的开篇之作，没啥可说的，自己写了一个learning notes也一并贴出来，当然写的很简陋，仅仅是这篇paper里边我感觉比较难的地方的推导过程（又一个只会学习的！）请见这里：https://www.cs.indiana.edu/~kduan/rsc/2010/lda-report.pdf
3. http://chasen.org/~daiti-m/dist/lda/
代码框架借鉴的是这位大神，这个是用variational inference也就是原始paper里边的推理方法。代码写的相对来说比较容易懂，所以就没有用Blei自己release的代码，那个应该是写的很完美的，可是比较难理解，对本人这样的菜鸟还是留着以后慢慢研究，哈哈
Friday, May 28, 2010
Bias-Variance Tradeoff
Bias(偏差)是指真正的均值和预测值之间的差值;Variance(方差)是指这个预测值作为随机变量的方差(在所有可能的训练样本上平均). 如果用公式表示,就是:
Bias(f^(x_0))=E(f^(x_0))-f(x_0)
Var(f^(x_0))=E[f^(x_0)-E[f^(x_0)]]^2
举个例子,k-NN的方差随着k的上升而下降。这表示了k-NN估计的"稳定性"随着k的上升而提高;而k越高,取的邻域就越大,用这个大邻域中的均值去估计f(x0),偏差就会增大。Bias表示预测的"准确程度";而Variance表示预测的"稳定性".
下边是一个经典的关于Bias-Variance的曲线图:
(model complexity可以理解成这个分类器输入的维度,k-NN中,k越大,复杂度就越低,即分类越粗糙;k越小,复杂度越
高,即分类越细腻)
Bias(f^(x_0))=E(f^(x_0))-f(x_0)
Var(f^(x_0))=E[f^(x_0)-E[f^(x_0)]]^2
举个例子,k-NN的方差随着k的上升而下降。这表示了k-NN估计的"稳定性"随着k的上升而提高;而k越高,取的邻域就越大,用这个大邻域中的均值去估计f(x0),偏差就会增大。Bias表示预测的"准确程度";而Variance表示预测的"稳定性".
下边是一个经典的关于Bias-Variance的曲线图:
(model complexity可以理解成这个分类器输入的维度,k-NN中,k越大,复杂度就越低,即分类越粗糙;k越小,复杂度越
高,即分类越细腻)
Tuesday, May 25, 2010
国史大纲 前言
凡读本书请先具下列诸信念：
一、当信任何一国之国民，尤其是自称知识在水平线以上之国民，对其本国已往历史，应该略有所知。(否则最多只算一有知识的人，不能算一有知识的国民。)
二、所谓对其本国已往历史略有所知者，尤必附随一种对其本国已往历史之温情与敬意。(否则只算知道了一些外国史，不得云对本国史有知识。)
三、所谓对其本国已往历史有一种温情与敬意者，至少不会对其本国历史抱一种偏激的虚无主义，(即视本国已往历史为无一点有价值，亦无一处足以使彼满意。) 亦至少不会感到现在我们是站在已往历史最高之顶点，(此乃一种浅薄狂妄的进化观。)而将我们当身种种罪恶与弱点，一切诿卸于古人。(此乃一种似是而非之文化自谴。)
四、当信每一国家必待其国民具备上列诸条件者比较渐多，其国家乃再有向前发展之希望。(否则其所改进，等于一个被征服国或次殖民地之改进，对其自身国家不发生关系。换言之，此种改进，无异是一种变相的文化征服，乃其文化自身之萎缩与消灭，并非其文化自身之转变与发皇。)
一、当信任何一国之国民，尤其是自称知识在水平线以上之国民，对其本国已往历史，应该略有所知。(否则最多只算一有知识的人，不能算一有知识的国民。)
二、所谓对其本国已往历史略有所知者，尤必附随一种对其本国已往历史之温情与敬意。(否则只算知道了一些外国史，不得云对本国史有知识。)
三、所谓对其本国已往历史有一种温情与敬意者，至少不会对其本国历史抱一种偏激的虚无主义，(即视本国已往历史为无一点有价值，亦无一处足以使彼满意。) 亦至少不会感到现在我们是站在已往历史最高之顶点，(此乃一种浅薄狂妄的进化观。)而将我们当身种种罪恶与弱点，一切诿卸于古人。(此乃一种似是而非之文化自谴。)
四、当信每一国家必待其国民具备上列诸条件者比较渐多，其国家乃再有向前发展之希望。(否则其所改进，等于一个被征服国或次殖民地之改进，对其自身国家不发生关系。换言之，此种改进，无异是一种变相的文化征服，乃其文化自身之萎缩与消灭，并非其文化自身之转变与发皇。)
Friday, May 14, 2010
这几天准备的Reading List
1. Classical Probabilistic Models and Conditional Random Field, K. Roman et al,
http://www.scai.fraunhofer.de/fileadmin/images/bio/data_mining/paper/crf_klinger_tomanek.pdf
2. A Tutorial Introduction to Belief Propagation (crv09), James Coughlan
http://computerrobotvision.org/2009/tutorial_day/crv09_belief_propagation_v2.pdf
3. Understanding Belief Propagation and its Generalizations, Weiss,
http://portal.acm.org/citation.cfm?id=779352
4. Efficient Belief Propagation for Early Vision, PEDRO F. FELZENSZWALB and DANIEL P. HUTTENLOCHER,
http://www.cs.cornell.edu/~dph/papers/bp-cvpr.pdf
5. Fractional Belief Propagation (NIPS02), W. Wiegerinck et al.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.8426
6. Nonparametric Belief Propagation, Erik B. Sudderth et al.
http://ssg.mit.edu/~esuddert/papers/cvpr03.pdf
7. Data Driven Mean-Shift Belief Propagation For non-Gaussian MRFs(CVPR10), Minwoo Park et al.
http://vision.cse.psu.edu/paper/CVPR2010DDMSBP0291.pdf
8. A Constant-Space Belief Propagation Algorithm for Stereo Matching(CVPR10), Qingxiong Yang et al.
http://vision.ai.uiuc.edu/~qyang6/publications/cvpr-10-qingxiong-yang-csbp.pdf
9. Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing(UAI06), G Elidan et al.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.129.1828
这两天读完了前三篇，对BP和Graphical Model的理解比原来更清楚了，我简单写了一点总结。以下：
第一篇是一个Techinical Report，主要介绍了Graphical Model的一般概念，以及四种常见的Graphical Model和它们之间的相互关系。这几种Model分别为Naive Bayes Model, HMM Model, Maximum Entropy Model, Conditional Random Field. HMM是序列化的Naive Bayes，它们都属于Generative Model；而条件随机场则是序列化的最大熵模型，它们都属于判别模型（Discriminate Model）。生成模型和判别模型之间的区别在这里也有介绍。文章详细介绍了前三种模型的推导过程。在推导最大熵模型的时候，本文仅给出了最大熵模型对应的最优条件概率分布，但是没有指明Feature Function的权值lambda如何求。其实在这一点上，最大熵模型的求解非常类似SVM的最优话Margin的过程，在参数估计的时候用到的都是拉格朗日对偶式（Lagrange Duality）和凸优化的知识，具体参数求解过程可参考SVM的推导过程（Stanford CS229课程讲义）。
然后本文介绍了Graphical Model的分类（Undirected和Directed）。很显然NB和HMM属于有向图，而 Undirected Graphical Model我理解其实就是Markov Random Field。另外Factor Graph在文章中也有介绍，但是更详细的如何构造Factor Graph以及如何在Factor Graph和Bayes Network或MRF之间转换则在第三篇文章中有论述。还有一点，MRF也是表征一个Joint Distribution，CRF对应的是表征一个Conditional Distribution；MRF我理解其实是一个二维的HMM，CRF则是一个二维的Linear CRF。。。是不是很别扭。。不过应该是这样的。
本文的后半部分集中讨论了CRF，主要是Linear CRF的构造，训练，和推理。Linear CRF (L-CRF)的构造表征的是，给定一组Observation之后的一个隐藏变量序列的概率。L-CRF与HMM的区别是，L-CRF是对一个条件概率建模，而 HMM是对一个联合概率建模；而且HMM要求当前的Observation只和当前的Hidden Variable相关，而与其它Hidden Variabl是条件独立的，即别的时刻的隐藏变量不影响我当前的观测结果。但是L-CRF 放松了这一要求，允许更多的dependency出现，模型更加灵活。构建模型之前，L-CRF被转换成Factor Graph，每一个Factor都是一组特征函数的线性组合之后的指数形式，这一点与最大熵模型类似。本文讨论的训练L-CRF模型的方法是MAP方法，与MLE的区别是增加了一个关于参数lambda的先验分布，用来避免 overfitting的情况。而在进行推理时，本文采用的是与HMM中相同的Viterbi算法，用于求出给定 Observation后最可能的一个隐藏序列。其实我感觉BP算法的max-product版本和Viterbi算法非常类似。
第二篇是BP算法的一个Tutorial，主要重点如下：
第一，对于Factor的理解。在一个Bayes Network或者HMM等Directed Graphical Model中，Factor可以理解成各个变量节点的条件概率分布，我认为在这里可以理解成，一个factor对应于一个节点的CPT（条件概率表）；但是在MRF等Undirected Graphical Model中，节点之间没有明确的条件概率关系，这时候Factor就可以理解成是一个关于若干变量的Compatibility Function，可以理解成描述节点之间的相互作用或者节点本身的特性。比如在MRF中，我的理解是，每个节点都是被两种因素影响，一个是和周围neighbor节点们的相互作用，另一个是节点本身的“势能”，也即Hidden Variable和对应Observed Variable之间的相互关系，因为观测值是已知的，所以可以把它们之间的相互关系类比成一种“势能”。
第二，明确了研究MRF或者Bayes Nets的目的，即求隐藏变量的Marginalized Probability和求使一个联合分布最大化的一组隐藏变量的取值。
第三，介绍的BP的基本形式，是一种Messsage Passing算法，本质即是通过不断地迭代求局部最佳值来最终获得全局的一组变量取值。如果图结构中不存在环（loop），则 BP算法是确定推理；若存在环结构，则BP算法成为一种近似推理。我对此的理解是，如果不存在环，则这张图一定存在若干“入口”（比如Bayes Nets的Root节点们），可先从这些“入口”节点入手，求出这些节点对应的Belief，然后将这些Belief 顺次传递message给其它节点；但是如果图结构中有环，则必须首先随机初始化所有message，然后通过迭代的方法求出最终解。那么这样看的话，BP算法和其它很多Gradient Descent算法（如EM，Hill Climbing算法等）共同的问题就是无法保证一定会获得全局最优解，而且这些迭代算法本身需要的迭代时间也会比较长。所以这样就有两个BP算法的研究方向，一个是如何保证或者尽量求得全局最优解，一个是如何减少迭代计算的开销。
具体的Belief计算方法和Message更新算法我省略掉，可以参考原文，实现起来应该不是太复杂。本文最后给出的一个例子就是利用BP算法解决Stereo Matching，以及若干改进建议。
第三篇文章是Weiss的一个technical report，引用次数很高。这篇文章侧重于揭示BP算法的本质，用热力学中的模型和概率图模型进行类比，说明了BP算法的物理意义。本文的讨论主要基于Pairwise Markov Random Field，由一个stereo matching的例子引出了其基本模型。这篇文章详细说明了如何将Pairwise MRF、Bayes Nets和Factor Graph之间的相互转换，并最终在MRF上对BP算法进行讨论，这样的好处是，MRF是无向的，而且Message Upadate只有一种形式（与Factor Graph不同）。
一个节点的Belief由以下因素决定：节点本身的Local Evidence（即该节点和对应的观测变量之间的关系，用Compatibility Function表示）；该节点的neighbor节点向这个节点传送的message的乘积。Message的更新函数也类似：由节点i向节点j传送的message由不包括j的和节点i相邻的节点向节点i发送的message之积，节点i本身的特性（Local Evidence），以及节点i和节点j之间的相互关系共同决定。文章稍后给出了更一般的形式，即message的更新其实是节点belief的marginalization的过程，即bi = sigma(j)bij。更一般地，文章还给出了多节点Belief的形式及其message如何更新，这个是后面文章所讲的GBP（Generalized Belief Propagation）的基础。
这篇文章另一个重点是讨论了热力学的几个能量模型及它们和BP/GBP算法之间的对应关系。文章首先介绍了玻尔兹曼定律，即系统的均衡分布由系统的能量状态和温度共同决定。接下来，根据不同的assumption，作者讨论了两种形式的自由能，即Mean-Field Free Energy和Bethe Free Energy。其中，后者假定Gibbs自由能下的Belief满足Normalization Condition以及Marginalization Condition，因而BP算法和Bethe Approximation是等价的。
最后，本文讨论了Generalized Belief Propagation。这是与物理学中Kikuchi Approximation等价的，可以看作是Bethe Approximation的一种扩展形式。具体细节参见原文，其主要思想是，将一个graph分成不同的region以及它们的sub-region，并由这些cluster构造一个新的graph，在这个新构造的graph上进行BP算法（用到之前介绍的多节点的BP形式），这样做的好处是，推理过程中图的节点数量变少了，而且多节点的Belief形式比单个节点的Belief表达信息要多，所以效果应该会更好。
http://www.scai.fraunhofer.de/fileadmin/images/bio/data_mining/paper/crf_klinger_tomanek.pdf
2. A Tutorial Introduction to Belief Propagation (crv09), James Coughlan
http://computerrobotvision.org/2009/tutorial_day/crv09_belief_propagation_v2.pdf
3. Understanding Belief Propagation and its Generalizations, Weiss,
http://portal.acm.org/citation.cfm?id=779352
4. Efficient Belief Propagation for Early Vision, PEDRO F. FELZENSZWALB and DANIEL P. HUTTENLOCHER,
http://www.cs.cornell.edu/~dph/papers/bp-cvpr.pdf
5. Fractional Belief Propagation (NIPS02), W. Wiegerinck et al.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.8426
6. Nonparametric Belief Propagation, Erik B. Sudderth et al.
http://ssg.mit.edu/~esuddert/papers/cvpr03.pdf
7. Data Driven Mean-Shift Belief Propagation For non-Gaussian MRFs(CVPR10), Minwoo Park et al.
http://vision.cse.psu.edu/paper/CVPR2010DDMSBP0291.pdf
8. A Constant-Space Belief Propagation Algorithm for Stereo Matching(CVPR10), Qingxiong Yang et al.
http://vision.ai.uiuc.edu/~qyang6/publications/cvpr-10-qingxiong-yang-csbp.pdf
9. Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing(UAI06), G Elidan et al.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.129.1828
这两天读完了前三篇，对BP和Graphical Model的理解比原来更清楚了，我简单写了一点总结。以下：
第一篇是一个Techinical Report，主要介绍了Graphical Model的一般概念，以及四种常见的Graphical Model和它们之间的相互关系。这几种Model分别为Naive Bayes Model, HMM Model, Maximum Entropy Model, Conditional Random Field. HMM是序列化的Naive Bayes，它们都属于Generative Model；而条件随机场则是序列化的最大熵模型，它们都属于判别模型（Discriminate Model）。生成模型和判别模型之间的区别在这里也有介绍。文章详细介绍了前三种模型的推导过程。在推导最大熵模型的时候，本文仅给出了最大熵模型对应的最优条件概率分布，但是没有指明Feature Function的权值lambda如何求。其实在这一点上，最大熵模型的求解非常类似SVM的最优话Margin的过程，在参数估计的时候用到的都是拉格朗日对偶式（Lagrange Duality）和凸优化的知识，具体参数求解过程可参考SVM的推导过程（Stanford CS229课程讲义）。
然后本文介绍了Graphical Model的分类（Undirected和Directed）。很显然NB和HMM属于有向图，而 Undirected Graphical Model我理解其实就是Markov Random Field。另外Factor Graph在文章中也有介绍，但是更详细的如何构造Factor Graph以及如何在Factor Graph和Bayes Network或MRF之间转换则在第三篇文章中有论述。还有一点，MRF也是表征一个Joint Distribution，CRF对应的是表征一个Conditional Distribution；MRF我理解其实是一个二维的HMM，CRF则是一个二维的Linear CRF。。。是不是很别扭。。不过应该是这样的。
本文的后半部分集中讨论了CRF，主要是Linear CRF的构造，训练，和推理。Linear CRF (L-CRF)的构造表征的是，给定一组Observation之后的一个隐藏变量序列的概率。L-CRF与HMM的区别是，L-CRF是对一个条件概率建模，而 HMM是对一个联合概率建模；而且HMM要求当前的Observation只和当前的Hidden Variable相关，而与其它Hidden Variabl是条件独立的，即别的时刻的隐藏变量不影响我当前的观测结果。但是L-CRF 放松了这一要求，允许更多的dependency出现，模型更加灵活。构建模型之前，L-CRF被转换成Factor Graph，每一个Factor都是一组特征函数的线性组合之后的指数形式，这一点与最大熵模型类似。本文讨论的训练L-CRF模型的方法是MAP方法，与MLE的区别是增加了一个关于参数lambda的先验分布，用来避免 overfitting的情况。而在进行推理时，本文采用的是与HMM中相同的Viterbi算法，用于求出给定 Observation后最可能的一个隐藏序列。其实我感觉BP算法的max-product版本和Viterbi算法非常类似。
第二篇是BP算法的一个Tutorial，主要重点如下：
第一，对于Factor的理解。在一个Bayes Network或者HMM等Directed Graphical Model中，Factor可以理解成各个变量节点的条件概率分布，我认为在这里可以理解成，一个factor对应于一个节点的CPT（条件概率表）；但是在MRF等Undirected Graphical Model中，节点之间没有明确的条件概率关系，这时候Factor就可以理解成是一个关于若干变量的Compatibility Function，可以理解成描述节点之间的相互作用或者节点本身的特性。比如在MRF中，我的理解是，每个节点都是被两种因素影响，一个是和周围neighbor节点们的相互作用，另一个是节点本身的“势能”，也即Hidden Variable和对应Observed Variable之间的相互关系，因为观测值是已知的，所以可以把它们之间的相互关系类比成一种“势能”。
第二，明确了研究MRF或者Bayes Nets的目的，即求隐藏变量的Marginalized Probability和求使一个联合分布最大化的一组隐藏变量的取值。
第三，介绍的BP的基本形式，是一种Messsage Passing算法，本质即是通过不断地迭代求局部最佳值来最终获得全局的一组变量取值。如果图结构中不存在环（loop），则 BP算法是确定推理；若存在环结构，则BP算法成为一种近似推理。我对此的理解是，如果不存在环，则这张图一定存在若干“入口”（比如Bayes Nets的Root节点们），可先从这些“入口”节点入手，求出这些节点对应的Belief，然后将这些Belief 顺次传递message给其它节点；但是如果图结构中有环，则必须首先随机初始化所有message，然后通过迭代的方法求出最终解。那么这样看的话，BP算法和其它很多Gradient Descent算法（如EM，Hill Climbing算法等）共同的问题就是无法保证一定会获得全局最优解，而且这些迭代算法本身需要的迭代时间也会比较长。所以这样就有两个BP算法的研究方向，一个是如何保证或者尽量求得全局最优解，一个是如何减少迭代计算的开销。
具体的Belief计算方法和Message更新算法我省略掉，可以参考原文，实现起来应该不是太复杂。本文最后给出的一个例子就是利用BP算法解决Stereo Matching，以及若干改进建议。
第三篇文章是Weiss的一个technical report，引用次数很高。这篇文章侧重于揭示BP算法的本质，用热力学中的模型和概率图模型进行类比，说明了BP算法的物理意义。本文的讨论主要基于Pairwise Markov Random Field，由一个stereo matching的例子引出了其基本模型。这篇文章详细说明了如何将Pairwise MRF、Bayes Nets和Factor Graph之间的相互转换，并最终在MRF上对BP算法进行讨论，这样的好处是，MRF是无向的，而且Message Upadate只有一种形式（与Factor Graph不同）。
一个节点的Belief由以下因素决定：节点本身的Local Evidence（即该节点和对应的观测变量之间的关系，用Compatibility Function表示）；该节点的neighbor节点向这个节点传送的message的乘积。Message的更新函数也类似：由节点i向节点j传送的message由不包括j的和节点i相邻的节点向节点i发送的message之积，节点i本身的特性（Local Evidence），以及节点i和节点j之间的相互关系共同决定。文章稍后给出了更一般的形式，即message的更新其实是节点belief的marginalization的过程，即bi = sigma(j)bij。更一般地，文章还给出了多节点Belief的形式及其message如何更新，这个是后面文章所讲的GBP（Generalized Belief Propagation）的基础。
这篇文章另一个重点是讨论了热力学的几个能量模型及它们和BP/GBP算法之间的对应关系。文章首先介绍了玻尔兹曼定律，即系统的均衡分布由系统的能量状态和温度共同决定。接下来，根据不同的assumption，作者讨论了两种形式的自由能，即Mean-Field Free Energy和Bethe Free Energy。其中，后者假定Gibbs自由能下的Belief满足Normalization Condition以及Marginalization Condition，因而BP算法和Bethe Approximation是等价的。
最后，本文讨论了Generalized Belief Propagation。这是与物理学中Kikuchi Approximation等价的，可以看作是Bethe Approximation的一种扩展形式。具体细节参见原文，其主要思想是，将一个graph分成不同的region以及它们的sub-region，并由这些cluster构造一个新的graph，在这个新构造的graph上进行BP算法（用到之前介绍的多节点的BP形式），这样做的好处是，推理过程中图的节点数量变少了，而且多节点的Belief形式比单个节点的Belief表达信息要多，所以效果应该会更好。
Tuesday, May 11, 2010
概率图模型一点点总结(2)
判别模型 和 生成模型
【摘要】
- 生成模型：无穷样本==》概率密度模型 = 产生模型==》预测
- 判别模型：有限样本==》判别函数 = 预测模型==》预测
【简介】
简单的说，假设o是观察值，q是模型。
如果对P(o|q)建模，就是Generative模型。其基本思想是首先建立样本的概率密度模型，再利用模型进行推理预测。要求已知样本无穷或尽可能的大限制。
这种方法一般建立在统计力学和bayes理论的基础之上。
如果对条件概率(后验概率) P(q|o)建模，就是Discrminative模型。基本思想是有限样本条件下建立判别函数，不考虑样本的产生模型，直接研究预测模型。代表性理论为统计学习理论。
这两种方法目前交叉较多。
【判别模型Discriminative Model】——inter-class probabilistic description
又可以称为条件模型，或条件概率模型。估计的是条件概率分布 (conditional distribution)， p(class|context)。
利用正负例和分类标签，focus在判别模型的边缘分布。目标函数直接对应于分类准确率。
- 主要特点：
寻找不同类别之间的最优分类面，反映的是异类数据之间的差异。
- 优点:
分类边界更灵活，比使用纯概率方法或生产模型得到的更高级。
能清晰的分辨出多类或某一类与其他类之间的差异特征
在聚类、viewpoint changes, partial occlusion and scale variations中的效果较好
适用于较多类别的识别
判别模型的性能比生成模型要简单，比较容易学习
- 缺点：
不能反映训练数据本身的特性。能力有限，可以告诉你的是1还是2，但没有办法把整个场景描述出来。
Lack elegance of generative: Priors, 结构, 不确定性
Alternative notions of penalty functions, regularization, 核函数
黑盒操作: 变量间的关系不清楚，不可视
- 常见的主要有：
logistic regression
SVMs
traditional neural networks
Nearest neighbor
Conditional random fields(CRF): 目前最新提出的热门模型，从NLP领域产生的，正在向ASR和CV上发展。
- 主要应用：
Image and document classification
Biosequence analysis
Time series prediction
【生成模型Generative Model】——intra-class probabilistic description
又叫产生式模型。估计的是联合概率分布（joint probability distribution），p(class, context)=p(class|context)*p(context)。
用于随机生成的观察值建模，特别是在给定某些隐藏参数情况下。在机器学习中，或用于直接对数据建模（用概率密度函数对观察到的draw建模），或作为生成条件概率密度函数的中间步骤。通过使用贝叶斯rule可以从生成模型中得到条件分布。
如果观察到的数据是完全由生成模型所生成的，那么就可以 fitting生成模型的参数，从而仅可能的增加数据相似度。但数据很少能由生成模型完全得到，所以比较准确的方式是直接对条件密度函数建模，即使用分类或回归分析。
与描述模型的不同是，描述模型中所有变量都是直接测量得到。
- 主要特点：
一般主要是对后验概率建模，从统计的角度表示数据的分布情况，能够反映同类数据本身的相似度。
只关注自己的inclass本身（即点左下角区域内的概率），不关心到底 decision boundary在哪。
- 优点:
实际上带的信息要比判别模型丰富，
研究单类问题比判别模型灵活性强
模型可以通过增量学习得到
能用于数据不完整（missing data）情况
modular construction of composed solutions to complex problems
prior knowledge can be easily taken into account
robust to partial occlusion and viewpoint changes
can tolerate significant intra-class variation of object appearance
- 缺点：
tend to produce a significant number of false positives. This is particularly true for object classes which share a high visual similarity such as horses and cows
学习和计算过程比较复杂
- 常见的主要有：
Gaussians, Naive Bayes, Mixtures of multinomials
Mixtures of Gaussians, Mixtures of experts, HMMs
Sigmoidal belief networks, Bayesian networks
Markov random fields
所列举的Generative model也可以用disriminative方法来训练，比如GMM或HMM，训练的方法有EBW(Extended Baum Welch),或最近Fei Sha提出的Large Margin方法。
- 主要应用：
NLP:
Traditional rule-based or Boolean logic systems (Dialog and Lexis-Nexis) are giving way to statistical approaches (Markov models and stochastic context grammars)
Medical Diagnosis:
QMR knowledge base, initially a heuristic expert systems for reasoning about diseases and symptoms been augmented with decision theoretic formulation Genomics and Bioinformatics
Sequences represented as generative HMMs
【两者之间的关系】
由生成模型可以得到判别模型，但由判别模型得不到生成模型。
Can performance of SVMs be combined elegantly with flexible Bayesian statistics?
Maximum Entropy Discrimination marries both methods: Solve over a distribution of parameters (a distribution over solutions)
【参考网址】
http://prfans.com/forum/viewthread.php?tid=80
http://hi.baidu.com/cat_ng/blog/item/5e59c3cea730270593457e1d.html
http://en.wikipedia.org/wiki/Generative_model
http://blog.csdn.net/yangleecool/archive/2009/04/05/4051029.aspx
==================
比较三种模型：HMMs and MRF and CRF
http://blog.sina.com.cn/s/blog_4cdaefce010082rm.html
HMMs(隐马尔科夫模型):
状态序列不能直接被观测到(hidden)；
每一个观测被认为是状态序列的随机函数；
状态转移矩阵是随机函数，根据转移概率矩阵来改变状态。
HMMs与MRF的区别是只包含标号场变量，不包括观测场变量。
MRF(马尔科夫随机场)
将图像模拟成一个随机变量组成的网格。
其中的每一个变量具有明确的对由其自身之外的随机变量组成的近邻的依赖性(马尔科夫性)。
CRF(条件随机场),又称为马尔可夫随机域
一种用于标注和切分有序数据的条件概率模型。
从形式上来说CRF可以看做是一种无向图模型，考察给定输入序列的标注序列的条件概率。
在视觉问题的应用：
HMMs:图像去噪、图像纹理分割、模糊图像复原、纹理图像检索、自动目标识别等
MRF: 图像恢复、图像分割、边缘检测、纹理分析、目标匹配和识别等
CRF: 目标检测、识别、序列图像中的目标分割
P.S.
标号场为隐随机场，它描述像素的局部相关属性，采用的模型应根据人们对图像的结构与特征的认识程度，具有相当大的灵活性。
空域标号场的先验模型主要有非因果马尔可夫模型和因果马尔可夫模型。
【摘要】
- 生成模型：无穷样本==》概率密度模型 = 产生模型==》预测
- 判别模型：有限样本==》判别函数 = 预测模型==》预测
【简介】
简单的说，假设o是观察值，q是模型。
如果对P(o|q)建模，就是Generative模型。其基本思想是首先建立样本的概率密度模型，再利用模型进行推理预测。要求已知样本无穷或尽可能的大限制。
这种方法一般建立在统计力学和bayes理论的基础之上。
如果对条件概率(后验概率) P(q|o)建模，就是Discrminative模型。基本思想是有限样本条件下建立判别函数，不考虑样本的产生模型，直接研究预测模型。代表性理论为统计学习理论。
这两种方法目前交叉较多。
【判别模型Discriminative Model】——inter-class probabilistic description
又可以称为条件模型，或条件概率模型。估计的是条件概率分布 (conditional distribution)， p(class|context)。
利用正负例和分类标签，focus在判别模型的边缘分布。目标函数直接对应于分类准确率。
- 主要特点：
寻找不同类别之间的最优分类面，反映的是异类数据之间的差异。
- 优点:
分类边界更灵活，比使用纯概率方法或生产模型得到的更高级。
能清晰的分辨出多类或某一类与其他类之间的差异特征
在聚类、viewpoint changes, partial occlusion and scale variations中的效果较好
适用于较多类别的识别
判别模型的性能比生成模型要简单，比较容易学习
- 缺点：
不能反映训练数据本身的特性。能力有限，可以告诉你的是1还是2，但没有办法把整个场景描述出来。
Lack elegance of generative: Priors, 结构, 不确定性
Alternative notions of penalty functions, regularization, 核函数
黑盒操作: 变量间的关系不清楚，不可视
- 常见的主要有：
logistic regression
SVMs
traditional neural networks
Nearest neighbor
Conditional random fields(CRF): 目前最新提出的热门模型，从NLP领域产生的，正在向ASR和CV上发展。
- 主要应用：
Image and document classification
Biosequence analysis
Time series prediction
【生成模型Generative Model】——intra-class probabilistic description
又叫产生式模型。估计的是联合概率分布（joint probability distribution），p(class, context)=p(class|context)*p(context)。
用于随机生成的观察值建模，特别是在给定某些隐藏参数情况下。在机器学习中，或用于直接对数据建模（用概率密度函数对观察到的draw建模），或作为生成条件概率密度函数的中间步骤。通过使用贝叶斯rule可以从生成模型中得到条件分布。
如果观察到的数据是完全由生成模型所生成的，那么就可以 fitting生成模型的参数，从而仅可能的增加数据相似度。但数据很少能由生成模型完全得到，所以比较准确的方式是直接对条件密度函数建模，即使用分类或回归分析。
与描述模型的不同是，描述模型中所有变量都是直接测量得到。
- 主要特点：
一般主要是对后验概率建模，从统计的角度表示数据的分布情况，能够反映同类数据本身的相似度。
只关注自己的inclass本身（即点左下角区域内的概率），不关心到底 decision boundary在哪。
- 优点:
实际上带的信息要比判别模型丰富，
研究单类问题比判别模型灵活性强
模型可以通过增量学习得到
能用于数据不完整（missing data）情况
modular construction of composed solutions to complex problems
prior knowledge can be easily taken into account
robust to partial occlusion and viewpoint changes
can tolerate significant intra-class variation of object appearance
- 缺点：
tend to produce a significant number of false positives. This is particularly true for object classes which share a high visual similarity such as horses and cows
学习和计算过程比较复杂
- 常见的主要有：
Gaussians, Naive Bayes, Mixtures of multinomials
Mixtures of Gaussians, Mixtures of experts, HMMs
Sigmoidal belief networks, Bayesian networks
Markov random fields
所列举的Generative model也可以用disriminative方法来训练，比如GMM或HMM，训练的方法有EBW(Extended Baum Welch),或最近Fei Sha提出的Large Margin方法。
- 主要应用：
NLP:
Traditional rule-based or Boolean logic systems (Dialog and Lexis-Nexis) are giving way to statistical approaches (Markov models and stochastic context grammars)
Medical Diagnosis:
QMR knowledge base, initially a heuristic expert systems for reasoning about diseases and symptoms been augmented with decision theoretic formulation Genomics and Bioinformatics
Sequences represented as generative HMMs
【两者之间的关系】
由生成模型可以得到判别模型，但由判别模型得不到生成模型。
Can performance of SVMs be combined elegantly with flexible Bayesian statistics?
Maximum Entropy Discrimination marries both methods: Solve over a distribution of parameters (a distribution over solutions)
【参考网址】
http://prfans.com/forum/viewthread.php?tid=80
http://hi.baidu.com/cat_ng/blog/item/5e59c3cea730270593457e1d.html
http://en.wikipedia.org/wiki/Generative_model
http://blog.csdn.net/yangleecool/archive/2009/04/05/4051029.aspx
==================
比较三种模型：HMMs and MRF and CRF
http://blog.sina.com.cn/s/blog_4cdaefce010082rm.html
HMMs(隐马尔科夫模型):
状态序列不能直接被观测到(hidden)；
每一个观测被认为是状态序列的随机函数；
状态转移矩阵是随机函数，根据转移概率矩阵来改变状态。
HMMs与MRF的区别是只包含标号场变量，不包括观测场变量。
MRF(马尔科夫随机场)
将图像模拟成一个随机变量组成的网格。
其中的每一个变量具有明确的对由其自身之外的随机变量组成的近邻的依赖性(马尔科夫性)。
CRF(条件随机场),又称为马尔可夫随机域
一种用于标注和切分有序数据的条件概率模型。
从形式上来说CRF可以看做是一种无向图模型，考察给定输入序列的标注序列的条件概率。
在视觉问题的应用：
HMMs:图像去噪、图像纹理分割、模糊图像复原、纹理图像检索、自动目标识别等
MRF: 图像恢复、图像分割、边缘检测、纹理分析、目标匹配和识别等
CRF: 目标检测、识别、序列图像中的目标分割
P.S.
标号场为隐随机场，它描述像素的局部相关属性，采用的模型应根据人们对图像的结构与特征的认识程度，具有相当大的灵活性。
空域标号场的先验模型主要有非因果马尔可夫模型和因果马尔可夫模型。
Subscribe to:
Posts (Atom)