这次主要debug了一下Gamma函数，原先计算Scaler的时候直接套用Gamma Function的定义计算，容易导致溢出（用Matlab算几个值就知道了），这次改为用log_gamma()进行计算，避开计算Gamma函数的乘积。貌似这次效果要好些，但是应该还是会有bug，以后再慢慢调不着急嘿嘿。
贴个链接：https://www.cs.indiana.edu/~kduan/rsc/2010/lda-ep-0.2.tar
Tuesday, June 8, 2010
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.
标号场为隐随机场，它描述像素的局部相关属性，采用的模型应根据人们对图像的结构与特征的认识程度，具有相当大的灵活性。
空域标号场的先验模型主要有非因果马尔可夫模型和因果马尔可夫模型。
Monday, May 10, 2010
概率图模型一点点总结
1. MCMC (in Bayesian Network Inference)
MCMC的主要步骤：
给定一个贝叶斯网络的query，固定其中的evidence variable，对剩下的non-evidence
variable反复进行如下操作：
1. 随机初始化所有的non-evidence variables
2. 对于某个non-evidence variable，给定其markove blanket对其进行sample
这整个过程是一个markov链，每个状态都对应于query variable的一个sample。将这个过
程进行一段时间后（到达平稳分布），这些所有query variable的取样结果统计一下就可
以得到query variable的近似推理结果。
关于平稳分布（stationary distribution）：
平稳分布要求满足detailed balance的条件(比平稳分布要更强)，即P(X)q(X->X')=P(X')
q(X'->X)。
为了满足detailed balance条件，考虑一个markov chain，其中每个variable的值都是在
给定当钱状态中“所有”其它变量的当前值的情况下进行sample得到的；在贝叶斯网中，这
个条件可以放松到这个variable的markov blanket（在贝叶斯网中，对于一个变量X，X与
其它变量在给定其markov blanket的情况下条件独立）。另外为了处理markov chain的状
态转移，我们可以使用Gibbs Sampling，这可以看成是MCMC的一种特殊情况。
MCMC可以看成是Direct Sampling和Rejection Sampling等近似推理的改进。主要原因是贝
叶斯网络中进行exact inference的计算复杂度代价很高（尤其是当网络结构很复杂的时候
），近似推理可以降低开销并获得很好的效果。
2. Bayesian Network
贝叶斯网是基于贝叶斯规则的一种网络结构（有向无环图），是概率图模型的一种形式。
图的一个节点表示一个状态，图的一条边表示一个因果关系。每一个状态对应一个CPT（条
件概率表），可以用来在贝叶斯网络中进行概率推理。一般来说，条件概率表相对而言都
不大，比联合概率的表示形式要简洁很多，而且一个贝叶斯网可以表达任何一种belief
state，因此贝叶斯网络可以有效地表达很复杂的causal relationship。
上学期学过的概率推理方法有：Variable Elimination和Monte Carlo Sampling以及
likelihood weighting。
3. Stereo Matching with Belief Propagation
这篇文章主要内容有三点：一是利用MRF对Stereo Matching问题建模，二是采用Belief
Propagation对构建好的MRF模型进行概率推理，三是在此基础上增加更多的特征以提高效
果。
MRF也是概率图模型的一种，很适合用于对spatial Constraint进行建模。Markov随机场与
Gibbs Field是等价的，密度P(X) = (1/Z)*exp(-H(X))，Z是一个normalizer，H(X)是
energy function。根据MRF的Markov性质，一个site只和周围临近neighbor相关，我们可
以得到P(X(i)=Y(i)|X(s\i)=x(s\i))=(1/Z(i))exp(-H(y(i)x(s\i)))。当I比较小的时候，
由于X仅在I上进行取值，因此可在合理的时间开销范围内进行求解Z(i)。
在这篇文章中，MRF模型的目的是估算出给定图像以后其真实结构的条件概率。在进行概率
推理的时候，可以采用MCMC的方法，但是本文采用的是Belief Propagation，原因是MCMC
方法的计算开销较大。
Belief Propagation是贝叶斯网中的一种近似推理方法（存在loop的情况下需要迭代）。
BP方法分为Sum Product和Max Product两种，本文采用的是第二种，类似Viterbi算法。
最后，这个MRF模型以constraint的形式综合了其它的特征以提高性能
文章的问题是无法保证得到全局最优解；或许Hidden CRF的效果更好些？不知是否可行？
因为CRF是对序列标注问题的建模，是不是也可以用到这个问题里？它也可以包括进去隐藏
变量（HCRF），CRF得到是全局最优解。
4. Stereo Matching with Color-Weighted Correlation, Hierarchical Belief
Propagation and Occlusion Handling
这篇文章是一种global matching stereo model，主要在于：
(1) 在计算matching cost的时候，采用color weighted correlation；而前一篇文章使用
的是Birchfield and Tomasi像素差进行计算。这样的好处是算法对occlusion boundary不
那么敏感。
(2) Hierarchical Belief Propagation.
(3) Pixel Classification. 这应该是个标记(label)问题
(4) 利用绝对误差来反复迭代优化最后的结果。
MCMC的主要步骤：
给定一个贝叶斯网络的query，固定其中的evidence variable，对剩下的non-evidence
variable反复进行如下操作：
1. 随机初始化所有的non-evidence variables
2. 对于某个non-evidence variable，给定其markove blanket对其进行sample
这整个过程是一个markov链，每个状态都对应于query variable的一个sample。将这个过
程进行一段时间后（到达平稳分布），这些所有query variable的取样结果统计一下就可
以得到query variable的近似推理结果。
关于平稳分布（stationary distribution）：
平稳分布要求满足detailed balance的条件(比平稳分布要更强)，即P(X)q(X->X')=P(X')
q(X'->X)。
为了满足detailed balance条件，考虑一个markov chain，其中每个variable的值都是在
给定当钱状态中“所有”其它变量的当前值的情况下进行sample得到的；在贝叶斯网中，这
个条件可以放松到这个variable的markov blanket（在贝叶斯网中，对于一个变量X，X与
其它变量在给定其markov blanket的情况下条件独立）。另外为了处理markov chain的状
态转移，我们可以使用Gibbs Sampling，这可以看成是MCMC的一种特殊情况。
MCMC可以看成是Direct Sampling和Rejection Sampling等近似推理的改进。主要原因是贝
叶斯网络中进行exact inference的计算复杂度代价很高（尤其是当网络结构很复杂的时候
），近似推理可以降低开销并获得很好的效果。
2. Bayesian Network
贝叶斯网是基于贝叶斯规则的一种网络结构（有向无环图），是概率图模型的一种形式。
图的一个节点表示一个状态，图的一条边表示一个因果关系。每一个状态对应一个CPT（条
件概率表），可以用来在贝叶斯网络中进行概率推理。一般来说，条件概率表相对而言都
不大，比联合概率的表示形式要简洁很多，而且一个贝叶斯网可以表达任何一种belief
state，因此贝叶斯网络可以有效地表达很复杂的causal relationship。
上学期学过的概率推理方法有：Variable Elimination和Monte Carlo Sampling以及
likelihood weighting。
3. Stereo Matching with Belief Propagation
这篇文章主要内容有三点：一是利用MRF对Stereo Matching问题建模，二是采用Belief
Propagation对构建好的MRF模型进行概率推理，三是在此基础上增加更多的特征以提高效
果。
MRF也是概率图模型的一种，很适合用于对spatial Constraint进行建模。Markov随机场与
Gibbs Field是等价的，密度P(X) = (1/Z)*exp(-H(X))，Z是一个normalizer，H(X)是
energy function。根据MRF的Markov性质，一个site只和周围临近neighbor相关，我们可
以得到P(X(i)=Y(i)|X(s\i)=x(s\i))=(1/Z(i))exp(-H(y(i)x(s\i)))。当I比较小的时候，
由于X仅在I上进行取值，因此可在合理的时间开销范围内进行求解Z(i)。
在这篇文章中，MRF模型的目的是估算出给定图像以后其真实结构的条件概率。在进行概率
推理的时候，可以采用MCMC的方法，但是本文采用的是Belief Propagation，原因是MCMC
方法的计算开销较大。
Belief Propagation是贝叶斯网中的一种近似推理方法（存在loop的情况下需要迭代）。
BP方法分为Sum Product和Max Product两种，本文采用的是第二种，类似Viterbi算法。
最后，这个MRF模型以constraint的形式综合了其它的特征以提高性能
文章的问题是无法保证得到全局最优解；或许Hidden CRF的效果更好些？不知是否可行？
因为CRF是对序列标注问题的建模，是不是也可以用到这个问题里？它也可以包括进去隐藏
变量（HCRF），CRF得到是全局最优解。
4. Stereo Matching with Color-Weighted Correlation, Hierarchical Belief
Propagation and Occlusion Handling
这篇文章是一种global matching stereo model，主要在于：
(1) 在计算matching cost的时候，采用color weighted correlation；而前一篇文章使用
的是Birchfield and Tomasi像素差进行计算。这样的好处是算法对occlusion boundary不
那么敏感。
(2) Hierarchical Belief Propagation.
(3) Pixel Classification. 这应该是个标记(label)问题
(4) 利用绝对误差来反复迭代优化最后的结果。
Subscribe to:
Posts (Atom)