标签归档:LDA

PRML读书会第四章 Linear Models for Classification

Deep Learning Specialization on Coursera

PRML读书会第四章 Linear Models for Classification

主讲人 planktonli

planktonli(1027753147) 19:52:28

现在我们就开始讲第四章,第四章的内容是关于 线性分类模型,主要内容有四点:
1) Fisher准则的分类,以及它和最小二乘分类的关系 (Fisher分类是最小二乘分类的特例)
2) 概率生成模型的分类模型
3) 概率判别模型的分类模型
4) 全贝叶斯概率的Laplace近似
需要注意的是,有三种形式的贝叶斯:
1) 全贝叶斯
2) 经验贝叶斯
3) MAP贝叶斯
我们大家熟知的是 MAP贝叶斯
MAP(poor man’s Bayesian):不涉及marginalization,仅是一种按后验概率最大化的point estimate。这里的MAP(poor man’s Bayesian)是属于 点概率估计的。而全贝叶斯可以看作对test样本的所有参数集合的加权平均,PRML说的Bayesian主要还是指Empirical Bayesian: 继续阅读

如何计算两个文档的相似度(二)

Deep Learning Specialization on Coursera

上一节我们介绍了一些背景知识以及gensim , 相信很多同学已经尝试过了。这一节将从gensim最基本的安装讲起,然后举一个非常简单的例子用以说明如何使用gensim,下一节再介绍其在课程图谱上的应用。

二、gensim的安装和使用

1、安装
gensim依赖NumPySciPy这两大Python科学计算工具包,一种简单的安装方法是pip install,但是国内因为网络的缘故常常失败。所以我是下载了gensim的源代码包安装的。gensim的这个官方安装页面很详细的列举了兼容的Python和NumPy, SciPy的版本号以及安装步骤,感兴趣的同学可以直接参考。下面我仅仅说明在Ubuntu和Mac OS下的安装:

1)我的VPS是64位的Ubuntu 12.04,所以安装numpy和scipy比较简单"sudo apt-get install python-numpy python-scipy", 之后解压gensim的安装包,直接“sudo python setup.py install"即可;

2)我的本是macbook pro,在mac os上安装numpy和scipy的源码包废了一下周折,特别是后者,一直提示fortran相关的东西没有,google了一下,发现很多人在mac上安装scipy的时候都遇到了这个问题,最后通过homebrew安装了gfortran才搞定:“brew install gfortran”,之后仍然是“sudo python setpy.py install" numpy 和 scipy即可;

2、使用
gensim的官方tutorial非常详细,英文ok的同学可以直接参考。以下我会按自己的理解举一个例子说明如何使用gensim,这个例子不同于gensim官方的例子,可以作为一个补充。上一节提到了一个文档:Latent Semantic Indexing (LSI) A Fast Track Tutorial , 这个例子的来源就是这个文档所举的3个一句话doc。首先让我们在命令行中打开python,做一些准备工作:

>>> from gensim import corpora, models, similarities
>>> import logging
>>> logging.basicConfig(format='%(asctime)s : %(levelname)s : %(message)s', level=logging.INFO)

然后将上面那个文档中的例子作为文档输入,在Python中用document list表示:

>>> documents = ["Shipment of gold damaged in a fire",
... "Delivery of silver arrived in a silver truck",
... "Shipment of gold arrived in a truck"]

正常情况下,需要对英文文本做一些预处理工作,譬如去停用词,对文本进行tokenize,stemming以及过滤掉低频的词,但是为了说明问题,也是为了和这篇"LSI Fast Track Tutorial"保持一致,以下的预处理仅仅是将英文单词小写化:

>>> texts = [[word for word in document.lower().split()] for document in documents]
>>> print texts
[['shipment', 'of', 'gold', 'damaged', 'in', 'a', 'fire'], ['delivery', 'of', 'silver', 'arrived', 'in', 'a', 'silver', 'truck'], ['shipment', 'of', 'gold', 'arrived', 'in', 'a', 'truck']]

我们可以通过这些文档抽取一个“词袋(bag-of-words)",将文档的token映射为id:

>>> dictionary = corpora.Dictionary(texts)
>>> print dictionary
Dictionary(11 unique tokens)
>>> print dictionary.token2id
{'a': 0, 'damaged': 1, 'gold': 3, 'fire': 2, 'of': 5, 'delivery': 8, 'arrived': 7, 'shipment': 6, 'in': 4, 'truck': 10, 'silver': 9}

然后就可以将用字符串表示的文档转换为用id表示的文档向量:

>>> corpus = [dictionary.doc2bow(text) for text in texts]
>>> print corpus
[[(0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (6, 1)], [(0, 1), (4, 1), (5, 1), (7, 1), (8, 1), (9, 2), (10, 1)], [(0, 1), (3, 1), (4, 1), (5, 1), (6, 1), (7, 1), (10, 1)]]

例如(9,2)这个元素代表第二篇文档中id为9的单词“silver”出现了2次。

有了这些信息,我们就可以基于这些“训练文档”计算一个TF-IDF“模型”:

>>> tfidf = models.TfidfModel(corpus)
2013-05-27 18:58:15,831 : INFO : collecting document frequencies
2013-05-27 18:58:15,881 : INFO : PROGRESS: processing document #0
2013-05-27 18:58:15,881 : INFO : calculating IDF weights for 3 documents and 11 features (21 matrix non-zeros)

基于这个TF-IDF模型,我们可以将上述用词频表示文档向量表示为一个用tf-idf值表示的文档向量:

>>> corpus_tfidf = tfidf[corpus]
>>> for doc in corpus_tfidf:
... print doc
...
[(1, 0.6633689723434505), (2, 0.6633689723434505), (3, 0.2448297500958463), (6, 0.2448297500958463)]
[(7, 0.16073253746956623), (8, 0.4355066251613605), (9, 0.871013250322721), (10, 0.16073253746956623)]
[(3, 0.5), (6, 0.5), (7, 0.5), (10, 0.5)]

发现一些token貌似丢失了,我们打印一下tfidf模型中的信息:

>>> print tfidf.dfs
{0: 3, 1: 1, 2: 1, 3: 2, 4: 3, 5: 3, 6: 2, 7: 2, 8: 1, 9: 1, 10: 2}
>>> print tfidf.idfs
{0: 0.0, 1: 1.5849625007211563, 2: 1.5849625007211563, 3: 0.5849625007211562, 4: 0.0, 5: 0.0, 6: 0.5849625007211562, 7: 0.5849625007211562, 8: 1.5849625007211563, 9: 1.5849625007211563, 10: 0.5849625007211562}

我们发现由于包含id为0, 4, 5这3个单词的文档数(df)为3,而文档总数也为3,所以idf被计算为0了,看来gensim没有对分子加1,做一个平滑。不过我们同时也发现这3个单词分别为a, in, of这样的介词,完全可以在预处理时作为停用词干掉,这也从另一个方面说明TF-IDF的有效性。

有了tf-idf值表示的文档向量,我们就可以训练一个LSI模型,和Latent Semantic Indexing (LSI) A Fast Track Tutorial中的例子相似,我们设置topic数为2:

>>> lsi = models.LsiModel(corpus_tfidf, id2word=dictionary, num_topics=2)
>>> lsi.print_topics(2)
2013-05-27 19:15:26,467 : INFO : topic #0(1.137): 0.438*"gold" + 0.438*"shipment" + 0.366*"truck" + 0.366*"arrived" + 0.345*"damaged" + 0.345*"fire" + 0.297*"silver" + 0.149*"delivery" + 0.000*"in" + 0.000*"a"
2013-05-27 19:15:26,468 : INFO : topic #1(1.000): 0.728*"silver" + 0.364*"delivery" + -0.364*"fire" + -0.364*"damaged" + 0.134*"truck" + 0.134*"arrived" + -0.134*"shipment" + -0.134*"gold" + -0.000*"a" + -0.000*"in"

lsi的物理意义不太好解释,不过最核心的意义是将训练文档向量组成的矩阵SVD分解,并做了一个秩为2的近似SVD分解,可以参考那篇英文tutorail。有了这个lsi模型,我们就可以将文档映射到一个二维的topic空间中:

>>> corpus_lsi = lsi[corpus_tfidf]
>>> for doc in corpus_lsi:
... print doc
...
[(0, 0.67211468809878649), (1, -0.54880682119355917)]
[(0, 0.44124825208697727), (1, 0.83594920480339041)]
[(0, 0.80401378963792647)]

可以看出,文档1,3和topic1更相关,文档2和topic2更相关;

我们也可以顺手跑一个LDA模型:

>>> lda = models.LdaModel(copurs_tfidf, id2word=dictionary, num_topics=2)
>>> lda.print_topics(2)
2013-05-27 19:44:40,026 : INFO : topic #0: 0.119*silver + 0.107*shipment + 0.104*truck + 0.103*gold + 0.102*fire + 0.101*arrived + 0.097*damaged + 0.085*delivery + 0.061*of + 0.061*in
2013-05-27 19:44:40,026 : INFO : topic #1: 0.110*gold + 0.109*silver + 0.105*shipment + 0.105*damaged + 0.101*arrived + 0.101*fire + 0.098*truck + 0.090*delivery + 0.061*of + 0.061*in

lda模型中的每个主题单词都有概率意义,其加和为1,值越大权重越大,物理意义比较明确,不过反过来再看这三篇文档训练的2个主题的LDA模型太平均了,没有说服力。

好了,我们回到LSI模型,有了LSI模型,我们如何来计算文档直接的相思度,或者换个角度,给定一个查询Query,如何找到最相关的文档?当然首先是建索引了:

>>> index = similarities.MatrixSimilarity(lsi[corpus])
2013-05-27 19:50:30,282 : INFO : scanning corpus to determine the number of features
2013-05-27 19:50:30,282 : INFO : creating matrix for 3 documents and 2 features

还是以这篇英文tutorial中的查询Query为例:gold silver truck。首先将其向量化:

>>> query = "gold silver truck"
>>> query_bow = dictionary.doc2bow(query.lower().split())
>>> print query_bow
[(3, 1), (9, 1), (10, 1)]

再用之前训练好的LSI模型将其映射到二维的topic空间:

>>> query_lsi = lsi[query_bow]
>>> print query_lsi
[(0, 1.1012835748628467), (1, 0.72812283398049593)]

最后就是计算其和index中doc的余弦相似度了:

>>> sims = index[query_lsi]
>>> print list(enumerate(sims))
[(0, 0.40757114), (1, 0.93163693), (2, 0.83416492)]

当然,我们也可以按相似度进行排序:

>>> sort_sims = sorted(enumerate(sims), key=lambda item: -item[1])
>>> print sort_sims
[(1, 0.93163693), (2, 0.83416492), (0, 0.40757114)]

可以看出,这个查询的结果是doc2 > doc3 > doc1,和fast tutorial是一致的,虽然数值上有一些差别:

2dlsi

好了,这个例子就到此为止,下一节我们将主要说明如何基于gensim计算课程图谱上课程之间的主题相似度,同时考虑一些改进方法,包括借助英文的自然语言处理工具包NLTK以及用更大的维基百科的语料来看看效果。

未完待续...

注:原创文章,转载请注明出处“我爱自然语言处理”:www.52nlp.cn

本文链接地址:http://www.52nlp.cn/如何计算两个文档的相似度二

如何计算两个文档的相似度(一)

Deep Learning Specialization on Coursera

前几天,我发布了一个和在线教育相关的网站:课程图谱,这个网站的目的通过对公开课的导航、推荐和点评等功能方便大家找到感兴趣的公开课,特别是目前最火的Coursera,Udacity等公开课平台上的课程。在发布之前,遇到的一个问题是如何找到两个相关的公开课,最早的计划是通过用户对课程的关注和用户对用户的关注来做推荐,譬如“你关注的朋友也关注这些课程”,但是问题是网站发布之前,我还没有积累用户关注的数据。另外一个想法是提前给课程打好标签,通过标签来计算它门之间的相似度,不过这是一个人工标注的过程,需要一定的时间。当然,另一个很自然的想法是通过课程的文本内容来计算课程之间的相似度,公开课相对来说有很多的文本描述信息,从文本分析的角度来处理这种推荐系统的冷启动问题应该不失为一个好的处理方法。通过一些调研和之前的一些工作经验,最终考虑采用Topic model来解决这个问题,其实方案很简单,就是将两个公开课的文本内容映射到topic的维度,然后再计算其相似度。然后的然后就通过google发现了gensim这个强大的Python工具包,它的简介只有一句话:topic modelling for humans, 用过之后,只能由衷的说一句:感谢上帝,感谢Google,感谢开源!

当前课程图谱中所有课程之间的相似度全部基于gensim计算,自己写的调用代码不到一百行,topic模型采用LSI(Latent semantic indexing, 中文译为浅层语义索引),LSI和LSA(Latent semantic analysis,中文译为浅层语义分析)这两个名词常常混在一起,事实上,在维基百科上,有建议将这两个名词合二为一。以下是课程图谱的一个效果图,课程为著名的机器学习专家Andrew Ng教授在Coursera的机器学习公开课,图片显示的是主题模型计算后排名前10的相关课程,Andrew Ng教授同时也是Coursera的创始人之一:

     课程图谱机器学习公开课

最后回到这篇文章的主题,我将会分3个部分介绍,首先介绍一些相关知识点,不过不会详细介绍每个知识点的细节,主要是简要的描述一下同时提供一些互联网上现有的不错的参考资料,如果读者已经很熟悉,可以直接跳过去;第二部分我会介绍gensim的安装和使用,特别是如何计算课程图谱上课程之间的相似度的;第三部分包括如何基于全量的英文维基百科(400多万文章,压缩后9个多G的语料)在一个4g内存的macbook上训练LSI模型和LDA模型,以及如何将其应用到课程图谱上来改进课程之前的相似度的效果,注意课程图谱的课程内容主要是英文,目前的效果还是第二部分的结果,第三部分我们一起来实现。如果你的英文没问题,第二,第三部分可以直接阅读gensim的tutorail,我所做的事情主要是基于这个tutorail在课程图谱上做了一些验证。

一、相关的知识点及参考资料

这篇文章不会写很长,但是涉及的知识点蛮多,所以首先会在这里介绍相关的知识点,了解的同学可以一笑而过,不了解的同学最好能做一些预习,这对于你了解topic model以及gensim更有好处。如果以后时间允许,我可能会基于其中的某几个点写一篇比较详细的介绍性的文章。不过任何知识点首推维基百科,然后才是下面我所罗列的参考资料。

1) TF-IDF,余弦相似度,向量空间模型
这几个知识点在信息检索中是最基本的,入门级的参考资料可以看看吴军老师在《数学之美》中第11章“如何确定网页和查询的相关性”和第14章“余弦定理和新闻的分类”中的通俗介绍或者阮一峰老师写的两篇科普文章“TF-IDF与余弦相似性的应用(一):自动提取关键词”和“TF-IDF与余弦相似性的应用(二):找出相似文章”。

专业一点的参考资料推荐王斌老师在中科院所授的研究生课程“现代信息检索(Modern Information Retrieval)”的课件,其中“第六讲向量模型及权重计算”和该主题相关。或者更详细的可参考王斌老师翻译的经典的《信息检索导论》第6章或者其它相关的信息检索书籍。

2)SVD和LSI
想了解LSI一定要知道SVD(Singular value decomposition, 中文译为奇异值分解),而SVD的作用不仅仅局限于LSI,在很多地方都能见到其身影,SVD自诞生之后,其应用领域不断被发掘,可以不夸张的说如果学了线性代数而不明白SVD,基本上等于没学。想快速了解或复习SVD的同学可以参考这个英文tutorial: Singular Value Decomposition Tutorial , 当然更推荐MIT教授Gilbert Strang的线性代数公开课和相关书籍,你可以直接在网易公开课看相关章节的视频。

关于LSI,简单说两句,一种情况下我们考察两个词的关系常常考虑的是它们在一个窗口长度(譬如一句话,一段话或一个文章)里的共现情况,在语料库语言学里有个专业点叫法叫Collocation,中文译为搭配或词语搭配。而LSI所做的是挖掘如下这层词语关系:A和C共现,B和C共现,目标是找到A和B的隐含关系,学术一点的叫法是second-order co-ocurrence。以下引用百度空间上一篇介绍相关参考资料时的简要描述:

LSI本质上识别了以文档为单位的second-order co-ocurrence的单词并归入同一个子空间。因此:
1)落在同一子空间的单词不一定是同义词,甚至不一定是在同情景下出现的单词,对于长篇文档尤其如是。
2)LSI根本无法处理一词多义的单词(多义词),多义词会导致LSI效果变差。

A persistent myth in search marketing circles is that LSI grants contextuality; i.e., terms occurring in the same context. This is not always the case. Consider two documents X and Y and three terms A, B and C and wherein:

A and B do not co-occur.
X mentions terms A and C
Y mentions terms B and C.

:. A---C---B

The common denominator is C, so we define this relation as an in-transit co-occurrence since both A and B occur while in transit with C. This is called second-order co-occurrence and is a special case of high-order co-occurrence.

其实我也推荐国外这篇由Dr. E. Garcia所写的SVD与LSI的通俗教程,这个系列最早是微博上有朋友推荐,不过发现英文原始网站上内容已经被其主人下架了,原因不得而知。幸好还有Google,在CSDN上我找到了这个系列“SVD与LSI教程系列”,不过很可惜很多图片都看不见了,如果哪位同学发现更好的版本或有原始的完整版本,可以告诉我,不甚感激!

不过幸好原文作者写了两个简要的PDF Tutorial版本:

Singular Value Decomposition (SVD)- A Fast Track Tutorial

Latent Semantic Indexing (LSI) A Fast Track Tutorial

这两个简明版本主要是通过简单的例子直观告诉你什么是SVD,什么是LSI,非常不错。

这几个版本的pdf文件我在微盘上上传了一个打包文件,也可以从这里下载:svd-lsi-doc.tar.gz

3) LDA
这个啥也不说了,隆重推荐我曾经在腾讯工作时的leader rickjin的"LDA数学八卦"系列,通俗易懂,娓娓道来,另外rick的其他系列也是非常值得一读的。

未完待续...

注:原创文章,转载请注明出处“我爱自然语言处理”:www.52nlp.cn

本文链接地址:http://www.52nlp.cn/如何计算两个文档的相似度一

LDA-math-认识Beta/Dirichlet分布(3)

Deep Learning Specialization on Coursera

2. LDA-math-认识Beta/Dirichlet分布(3)
2.3 Dirichlet-Multinomial 共轭

对于魔鬼变本加厉的新的游戏规则,数学形式化如下:

  1. $X_1,X_2,\cdots,X_n {\stackrel{\mathrm{iid}} {\sim}}Uniform(0,1)$,
  2. 排序后对应的顺序统计量 $X_{(1)},X_{(2)},\cdots, X_{(n)}$,
  3. 问 $(X_{(k_1)}, X_{(k_1+k_2)})$的联合分布是什么;

游戏3

完全类似于第一个游戏的推导过程,我们可以进行如下的概率计算(为了数学公式的简洁对称,我们取$x_3$满足$x_1+x_2+x_3 = 1$,但只有$x_1,x_2$是变量)
继续阅读

LDA-math-认识Beta/Dirichlet分布(2)

Deep Learning Specialization on Coursera

2. LDA-math-认识Beta/Dirichlet分布(2)
2.2 Beta-Binomial 共轭

魔鬼的第二个题目,数学上形式化一下,就是

  1. $X_1,X_2,\cdots,X_n {\stackrel{\mathrm{iid}}{\sim}}Uniform(0,1)$,对应的顺序统计量是 $X_{(1)},X_{(2)},\cdots, X_{(n)}$, 我们要猜测 $p=X_{(k)}$;
  2. $Y_1,Y_2,\cdots,Y_m {\stackrel{\mathrm{iid}}{\sim}}Uniform(0,1)$, $Y_i$中有$m_1$个比$p$小,$m_2$个比$p$大;
  3. 问 $P(p|Y_1,Y_2,\cdots,Y_m)$ 的分布是什么。

由于$p=X_{(k)}$在 $X_1,X_2,\cdots,X_n $中是第$k$大的,利用$Y_i$的信息,我们容易推理得到 $p=X_{(k)}$ 在$X_1,X_2,\cdots,X_n,Y_1,Y_2,\cdots,Y_m {\stackrel{\mathrm{iid}}{\sim}} Uniform(0,1)$ 这$(m+n)$个独立随机变量中是第 $k+m_1$大的,于是按照上一个小节的推理,此时$p=X_{(k)}$ 的概率密度函数是 $Beta(p|k+m_1,n-k+1+m_2)$。按照贝叶斯推理的逻辑,我们把以上过程整理如下:

  1. $p=X_{(k)}$是我们要猜测的参数,我们推导出 $p$ 的分布为 $f(p) = Beta(p|k,n-k+1)$,称为 $p$ 的先验分布;
  2. 数据$Y_i$中有$m_1$个比$p$小,$m_2$个比$p$大,$Y_i$相当于是做了$m$次贝努利实验,所以$m_1$ 服从二项分布 $B(m,p)$;
  3. 在给定了来自数据提供的$(m_1,m_2)$的知识后,$p$ 的后验分布变为 $f(p|m_1,m_2)=Beta(p|k+m_1,n-k+1+m_2)$

coin-toss贝努利实验

继续阅读

LDA-math-认识Beta/Dirichlet分布(1)

Deep Learning Specialization on Coursera

2. 认识Beta/Dirichlet分布
2.1 魔鬼的游戏---认识Beta 分布

统计学就是猜测上帝的游戏,当然我们不总是有机会猜测上帝,运气不好的时候就得揣度魔鬼的心思。有一天你被魔鬼撒旦抓走了,撒旦说:”你们人类很聪明,而我是很仁慈的,和你玩一个游戏,赢了就可以走,否则把灵魂出卖给我。游戏的规则很简单,我有一个魔盒,上面有一个按钮,你每按一下按钮,就均匀的输出一个[0,1]之间的随机数,我现在按10下,我手上有10个数,你猜第7大的数是什么,偏离不超过0.01就算对。“ 你应该怎么猜呢?

从数学的角度抽象一下,上面这个游戏其实是在说随机变量$X_1,X_2,\cdots,X_n {\stackrel{\mathrm{iid}}{\sim}} Uniform(0,1)$,把这$n$ 个随机变量排序后得到顺序统计量 $X_{(1)},X_{(2)},\cdots, X_{(n)}$, 然后问 $X_{(k)}$ 的分布是什么。

对于不喜欢数学的同学而言,估计每个概率分布都是一个恶魔,那在概率统计学中,均匀分布应该算得上是潘多拉魔盒,几乎所有重要的概率分布都可以从均匀分布$Uniform(0,1)$中生成出来;尤其是在统计模拟中,所有统计分布的随机样本都是通过均匀分布产生的。

pandora潘多拉魔盒Uniform(0,1)

继续阅读

LDA-math-神奇的Gamma函数(3)

Deep Learning Specialization on Coursera

1. 神奇的Gamma函数
1.3 从二项分布到Gamma 分布

Gamma 函数在概率统计中频繁现身,众多的统计分布,包括常见的统计学三大分布($t$ 分布,$\chi^2$ 分布,$F$ 分布)、Beta分布、 Dirichlet 分布的密度公式中都有 Gamma 函数的身影;当然发生最直接联系的概率分布是直接由 Gamma 函数变换得到的 Gamma 分布。对Gamma 函数的定义做一个变形,就可以得到如下式子
 \int_0^{\infty} \frac{x^{\alpha-1}e^{-x}}{\Gamma(\alpha)}dx = 1
于是,取积分中的函数作为概率密度,就得到一个形式最简单的Gamma 分布的密度函数
Gamma(x|\alpha) = \frac{x^{\alpha-1}e^{-x}}{\Gamma(\alpha)}
如果做一个变换 $x=\beta t$, 就得到Gamma 分布的更一般的形式
Gamma(t|\alpha, \beta) = \frac{\beta^\alpha t^{\alpha-1}e^{-\beta t}}{\Gamma(\alpha)}
其中 $\alpha$ 称为 shape parameter, 主要决定了分布曲线的形状;而$\beta$ 称为 rate parameter 或者inverse scale parameter ($\frac{1}{\beta}$ 称为scale parameter),主要决定曲线有多陡。

gamma-distribution$Gamma(t|\alpha,\beta)$分布图像

Gamma 分布在概率统计领域也是一个万人迷,众多统计分布和它有密切关系。指数分布和$\chi^2$ 分布都是特殊的Gamma 分布。另外Gamma 分布作为先验分布是很强大的,在贝叶斯统计分析中被广泛的用作其它分布的先验。如果把统计分布中的共轭关系类比为人类生活中的情侣关系的话,那指数分布、Poission分布、正态分布、对数正态分布都可以是 Gamma 分布的情人。接下来的内容中中我们主要关注$\beta = 1$的简单形式的 Gamma 分布。
继续阅读

LDA-math-神奇的Gamma函数(2)

Deep Learning Specialization on Coursera

1. 神奇的Gamma函数
1.2 Gamma 函数欣赏

Each generation has found something of interest to say about the gamma function. Perhaps the next generation will also. 
---Philip J.Davis

Gamma 函数从它诞生开始就被许多数学家进行研究,包括高斯、勒让德、威尔斯特拉斯、柳维尔等等。这个函数在现代数学分析中被深入研究,在概率论中也是无处不在,很多统计分布都和这个函数相关。Gamma 函数作为阶乘的推广,首先它也有和 Stirling 公式类似的一个结论
 \Gamma(x) \sim \sqrt{2\pi}e^{-x}x^{x-\frac{1}{2}}
另外, Gamma 函数不仅可以定义在实数集上,还可以延拓到整个复平面上。

gamma-complex复平面上的Gamma 函数

Gamma 函数有很多妙用,它不但使得 (1/2)! 的计算有意义,还能扩展很多其他的数学概念。比如导数,我们原来只能定义一阶、二阶等整数阶导数,有了Gamma 函数我们可以把函数导数的定义延拓到实数集,从而可以计算 1/2 阶导数,同样的积分作为导数的逆运算也可以有分数阶。我们先考虑一下 $x^n$ 的各阶导数

derivatives由于k阶导数可以用阶乘表达,于是我们用Gamma 函数表达为
 \frac{\Gamma{(n+1)}}{\Gamma{(n-k+1)}} x^{n-k}
于是基于上式,我们可以把导数的阶从整数延拓到实数集。例如,取$n=1, k=\frac{1}{2}$我们可以计算 $x$ 的 $\frac{1}{2}$阶导数为
 \frac{\Gamma{(1+1)}}{\Gamma{(1-1/2+1)}} x^{1-1/2} = \frac{2\sqrt{x}}{\sqrt{\pi}}
继续阅读

LDA-math-神奇的Gamma函数(1)

Deep Learning Specialization on Coursera

1. 神奇的Gamma函数
1.1 Gamma 函数诞生记
学高等数学的时候,我们都学习过如下一个长相有点奇特的Gamma函数
 \Gamma(x)=\int_0^{\infty}t^{x-1}e^{-t}dt
通过分部积分的方法,可以推导出这个函数有如下的递归性质
\Gamma(x+1) = x \Gamma(x)
于是很容易证明,$\Gamma(x)$ 函数可以当成是阶乘在实数集上的延拓,具有如下性质
\Gamma(n) = (n-1)!

学习了Gamma 函数之后,多年以来我一直有两个疑问:

  • 这个长得这么怪异的一个函数,数学家是如何找到的;
  • 为何定义 $\Gamma$ 函数的时候,不使得这个函数的定义满足$\Gamma(n) = n! $ 而是 $\Gamma(n) = (n-1)! $

最近翻了一些资料,发现有不少文献资料介绍 Gamma 函数发现的历史,要说清楚它需要一定的数学推导,这儿只是简要的说一些主线。

1728年,哥德巴赫在考虑数列插值的问题,通俗的说就是把数列的通项公式定义从整数集合延拓到实数集合,例如数列 $1,4,9,16,\cdots$ 可以用通项公式 $n^2$ 自然的表达,即便 $n$ 为实数的时候,这个通项公式也是良好定义的。直观的说也就是可以找到一条平滑的曲线$y=x^2$通过所有的整数点$(n,n^2)$,从而可以把定义在整数集上的公式延拓到实数集合。一天哥德巴赫开始处理阶乘序列 $1,2,6,24,120,720,\cdots$,我们可以计算 $2!,3!$, 是否可以计算 $2.5!$呢?我们把最初的一些 $(n,n!)$的点画在坐标轴上,确实可以看到,容易画出一条通过这些点的平滑曲线。


factorial
factorial-curve

但是哥德巴赫无法解决阶乘往实数集上延拓的这个问题,于是写信请教尼古拉斯.贝努利和他的弟弟丹尼尔.贝努利,由于欧拉当时和丹尼尔.贝努利在一块,他也因此得知了这个问题。而欧拉于1729 年完美的解决了这个问题,由此导致了$\Gamma$ 函数的诞生,当时欧拉只有22岁。
继续阅读

概率语言模型及其变形系列-PLSA及EM算法

Deep Learning Specialization on Coursera

本系列博文介绍常见概率语言模型及其变形模型,主要总结PLSA、LDA及LDA的变形模型及参数Inference方法。初步计划内容如下

第一篇:PLSA及EM算法

第二篇:LDA及Gibbs Samping

第三篇:LDA变形模型-Twitter LDA,TimeUserLDA,ATM,Labeled-LDA,MaxEnt-LDA等

第四篇:基于变形LDA的paper分类总结

第五篇:LDA Gibbs Sampling 的JAVA实现

第一篇 PLSA及EM算法

[Update 2012/12/21 为了解决部分朋友反映的网页图片无法显示的问题,更新PDF版本

下载地址 PLSA及EM算法-yangliuy]

前言:本文主要介绍PLSA及EM算法,首先给出LSA(隐性语义分析)的早期方法SVD,然后引入基于概率的PLSA模型,其参数学习采用EM算法。接着我们分析如何运用EM算法估计一个简单的mixture unigram 语言模型和混合高斯模型GMM的参数,最后总结EM算法的一般形式及运用关键点。对于改进PLSA,引入hyperparameter的LDA模型及其Gibbs Sampling参数估计方法放在本系列后面的文章LDA及Gibbs Samping介绍。
继续阅读