作者归档:rickjin

[火光摇曳]神奇的伽玛函数(下)

原文链接: http://www.flickering.cn/?p=203

五、$ \Gamma(n) = (n-1)!$ 还是 $ \Gamma(n) = n! $ ? 

伽玛函数找到了,我们来看看第二个问题,为何伽玛函数被定义为满足 $\Gamma(n)=(n-1)!$? 这看起来挺别扭的,如果我们稍微修正一下,把伽玛函数定义中的 $t^{x-1}$ 替换为 $t^x$
 \Gamma(x) = \int_0^{\infty} t^{x}e^{-t}dt ,
这不就可以使得 $\Gamma(n)=n!$了嘛。估计数学界每年都有学生问这个问题,然而答案却一直有一些争议。

欧拉最早的伽玛函数定义还真是如上所示,选择了$\Gamma(n)=n!$,事实上数学王子高斯在研究伽玛函数的时候, 一直使用的是如下定义:
 \Pi(x)=\int_{0}^\infty t^x e^{-t}\,dt ,
然而这个定义在历史上并没有流传开来。

Legendre

勒让德肖像水彩画

欧拉在伽玛函数的推导中实际上引入了两类积分形式
 \int_0^1 t^{x}(1-t)^{y}dt, \quad \quad \int_0^{\infty} t^{x}e^{-t}dt
现在我们分别称为欧拉一类积分和欧拉二类积分。勒让德追随欧拉的脚步,发表了多篇论文对欧拉积分进行了深入的研究和推广,不过在勒让德的研究中,对积分中的参数做了 $-1$的移位修改,主要定义为
 B(x, y) = \int_0^1 t^{x-1}(1-t)^{y-1}dt

 \Gamma(x) = \int_0^{\infty} t^{x-1}e^{-t}dt .
$B(x,y)$ 现在称为贝塔积分或者贝塔函数。其中$\Gamma(x)$ 的这个定义选择导致了 $ \Gamma(n) = (n-1)!$ 。实际上伽马函数中的$\Gamma$符号历史上就是勒让德首次引入的,而勒让德给出的这个伽玛函数的定义在历史上起了决定作用,该定义被法国的数学家广泛采纳并在世界范围推广,最终使得这个定义在现代数学中成为了既成事实。
继续阅读

[火光摇曳]神奇的伽玛函数(上)

原文链接: http://www.flickering.cn/?p=163

一、开篇

数学爱好者们汇集在网络论坛上的一大乐事就是对各类和数学相关的事物评头论足、论资排辈。如果要评选历史上最伟大的数学家,就会有一大堆的粉丝围绕高斯、黎曼、牛顿、欧拉、阿基米德等一流人物展开口水战;如果要讨论最奇妙的数学常数,$e, \pi, \phi=\frac{\sqrt{5}-1}{2} $ 肯定在候选队列中;如果要推举最美丽的数学公式,欧拉公式 $e^{i\pi} + 1= 0$ 与和式 $ 1 + \frac{1}{2^2} + \frac{1}{3^2} + \frac{1}{4^2} + \cdots = \frac{\pi^2}{6} $ 常常被数学爱好者们提及;如果有人追问最神奇的数学函数是什么? 这个问题自然又会变得极具争议,而我相信如下这个长相有点奇特的伽玛函数
 \Gamma(x)=\int_0^{\infty}t^{x-1}e^{-t}dt
一定会出现在候选队列中。

伽玛函数不是初等函数,而是用积分形式定义的超越函数,怎么看都让人觉得不如初等函数自然亲切。然而伽玛函数也被称为阶乘函数,高等数学会告诉我们一个基本结论:伽玛函数是阶乘的推广。通过分部积分的方法,容易证明这个函数具有如下的递归性质
\Gamma(x+1) = x \Gamma(x)
由此可以推导出,对于任意的自然数$n$
\Gamma(n) = (n-1)! .
由于伽玛函数在整个实数轴上都有定义,于是可以看做阶乘概念在实数集上的延拓。

如果我们继续再学习一些数学,就会惊奇地发现这个具有神秘气质的伽玛函数真是才华横溢。她栖身于现代数学的各个分支,在微积分、概率论、偏微分方程、组合数学, 甚至是看起来八竿子打不着的数论当中,都起着重要的作用。 并且这个函数绝非数学家们凭空臆想的一个抽象玩具,它具有极高的实用价值,频繁现身于在现代科学尤其是物理学之中。

笔者对数学的涉猎很有限,主要是从概率统计中频繁地接触和学习这个函数,不过这个函数多年来一直都让我心存疑惑:

  • 都说$n!$ 和伽玛函数是近亲,可是从相貌上这两个数学公式都差了十万八千里,历史上数学家们是如何找到这个奇特的函数的?
  •  现代数学对伽玛函数的定义使它满足 $\Gamma(n) = (n-1)!$,既然号称是$n!$ 的推广,为何定义伽玛函数的时候不让它满足$\Gamma(n) = n!$?这看起来不是更加舒服自然吗?
  •  伽玛函数是唯一满足阶乘特性的推广函数吗?
  •  伽玛函数在各种概率分布的密度函数中频繁出现,伽玛函数本身是否有直观的概率解释?

带着这些疑问,笔者翻阅了许多讲解伽马函数历史和应用的资料,发现伽玛函数真是一个来自异族的美女,与生俱来携带着一种神秘的色彩。你要接近她并不难,然而她魅力独特,令你无法看透。从她出生开始,就吸引着众多一流的数学家对她进行解读。 历史上伽玛函数的发现,和数学家们对阶乘、插值以及积分的研究有着紧密的关系,而这最早要从著名的沃利斯公式讲起。
继续阅读

Darts: Double-ARray Trie System 翻译文档

Darts: Double-ARray Trie System

开篇

Darts 是用于构建双数组 Double-Array [Aoe 1989] 的简单的 C++ Template Library . 双数组 (Double-Array) 是用于实现 Trie 的一种数据结构, 比其它的类 Trie 实现方式(Hash-Tree, Digital Trie, Patricia Tree, Suffix Array) 速度更快。 原始的 Double-Array 使能够支持动态添加删除 key, 但是 Darts 只支持把排好序的词典文件转换为静态的 Double-Array.

Darts 既可以像 Hash 一样作为简单的词典使用,也能非常高效的执行分词词典中必须的 Common Prefix Search 操作。

自2003年7月起, 两个开源的日语分词系统 MeCabChaSen 都使用了 Darts .

继续阅读

日文分词器 Mecab 文档

一、日文分词器 MeCab 简介

mecab (http://mecab.sourceforge.net/) 是奈良先端科学技術大学院的工藤拓开发的日文分词系统, 该作者写过多个 machine learning 方面的软件包, 最有名的就是 CRF++, 目前该作者在 google@Japan 工作。

mecab 是基于CRF 的一个日文分词系统,代码使用 c++ 实现, 基本上内嵌了 CRF++ 的代码, 同时提供了多种脚本语言调用的接口(python, perl, ruby 等).整个系统的架构采用通用泛化的设计, 用户可以通过配置文件定制CRF训练中需要使用的特征模板。 甚至, 如果你有中文的分词语料作为训练语料,可以在该架构下按照其配置文件的规范定制一个中文的分词系统。

日文NLP 界有几个有名的开源分词系统, Juman, Chasen, Mecab.   Juman 和 Chasen 都是比较老的系统了, Mecab 系统比较新, 在很多方面都优于 Juman 和 Chasen, mecab 目前开发也比较活跃。 Mecab 虽然使用 CRF 实现, 但是解析效率上确相当高效, 据作者的介绍, Mecab 比基于 HMM 的 Chasen 的解析速度要快。 笔者在一台 Linux 机器上粗略测试过其速度,将近达到 2MB/s, 完全达到了工程应用的需求, 该系统目前在日文 NLP 界被广泛使用。

中文和日文的有着类似的分词需求,因此mecab 对于中文处理来说有着很好的借鉴价值, 由于mecab 的内部模块化得很清晰,如果能读懂其文档的话,是比较容易能看懂整套代码的。 可惜目前中文的资料很少, 而其自带的文档又都是日文的, 所以了解它的中国人不多。

笔者把 mecab 自带的文档从日文翻译成中文, 希望mecab对于中文分词有兴趣的读者能有借鉴价值。日语水平很烂, 大家凑合着看吧。 对于自由的文档翻译,有一句话: Document is like sex. If it's good, it's very very good. If it's bad, it's better than nothing.

二、关于 MeCab (和布蕪)

Mecab 是京都大学情报学研究科-日本电信电话股份有限公司通信科学基础研究所通过 Unit Project 的合作研究共同开发的词法分析引擎。其设计的基本方针是不依赖于具体的语言,词典,语料库, 采用 Conditional Random Fields (CRF) 模型进行参数估计, 性能优于使用隐马模型的 ChaSen 。同时, 平均解析速度高于 ChaSenJumanKAKASI 这些日文词法分析器. 顺便说一下, Mecab (和布蕪, めかぶ), 是作者最喜欢的食物.

目录

继续阅读

LDA-math-LDA 文本建模

5. LDA 文本建模

5.1 游戏规则

对于上述的 PLSA 模型,贝叶斯学派显然是有意见的,doc-topic 骰子$\overrightarrow{\theta}_m$和 topic-word 骰子$\overrightarrow{\varphi}_k$都是模型中的参数,参数都是随机变量,怎么能没有先验分布呢?于是,类似于对 Unigram Model 的贝叶斯改造, 我们也可以如下在两个骰子参数前加上先验分布从而把 PLSA 对应的游戏过程改造为一个贝叶斯的游戏过程。由于 $\overrightarrow{\varphi}_k$和$\overrightarrow{\theta}_m$都对应到多项分布,所以先验分布的一个好的选择就是Drichlet 分布,于是我们就得到了 LDA(Latent Dirichlet Allocation)模型。

lda-diceLDA模型

在 LDA 模型中, 上帝是按照如下的规则玩文档生成的游戏的

game-lda-1

继续阅读

LDA-math-文本建模

4. 文本建模

我们日常生活中总是产生大量的文本,如果每一个文本存储为一篇文档,那每篇文档从人的观察来说就是有序的词的序列 $d=(w_1, w_2, \cdots, w_n)$。

corpus
包含$M$ 篇文档的语料库

统计文本建模的目的就是追问这些观察到语料库中的的词序列是如何生成的。统计学被人们描述为猜测上帝的游戏,人类产生的所有的语料文本我们都可以看成是一个伟大的上帝在天堂中抛掷骰子生成的,我们观察到的只是上帝玩这个游戏的结果 ------ 词序列构成的语料,而上帝玩这个游戏的过程对我们是个黑盒子。所以在统计文本建模中,我们希望猜测出上帝是如何玩这个游戏的,具体一点,最核心的两个问题是

  • 上帝都有什么样的骰子;
  • 上帝是如何抛掷这些骰子的;

第一个问题就是表示模型中都有哪些参数,骰子的每一个面的概率都对应于模型中的参数;第二个问题就表示游戏规则是什么,上帝可能有各种不同类型的骰子,上帝可以按照一定的规则抛掷这些骰子从而产生词序列。

dice-all god-throw-dice

上帝掷骰子

4.1 Unigram Model

假设我们的词典中一共有 $V$ 个词 $v_1, v_2, \cdots v_V$,那么最简单的 Unigram Model 就是认为上帝是按照如下的游戏规则产生文本的。

game-unigram-model

上帝的这个唯一的骰子各个面的概率记为 $\overrightarrow{p} = (p_1, p_2, \cdots, p_V)$, 所以每次投掷骰子类似于一个抛钢镚时候的贝努利实验, 记为 $w\sim Mult(w|\overrightarrow{p}) $。

unigram-model上帝投掷$V$ 个面的骰子

继续阅读

LDA-math-MCMC 和 Gibbs Sampling(2)

3 LDA-math-MCMC 和 Gibbs Sampling(2)
3.2 Markov Chain Monte Carlo

对于给定的概率分布$p(x)$,我们希望能有便捷的方式生成它对应的样本。由于马氏链能收敛到平稳分布, 于是一个很的漂亮想法是:如果我们能构造一个转移矩阵为$P$的马氏链,使得该马氏链的平稳分布恰好是$p(x)$, 那么我们从任何一个初始状态$x_0$出发沿着马氏链转移, 得到一个转移序列 $x_0, x_1, x_2, \cdots x_n, x_{n+1}\cdots,$, 如果马氏链在第$n$步已经收敛了,于是我们就得到了 $\pi(x)$ 的样本$x_n, x_{n+1}\cdots$。

这个绝妙的想法在1953年被 Metropolis想到了,为了研究粒子系统的平稳性质, Metropolis 考虑了物理学中常见的波尔兹曼分布的采样问题,首次提出了基于马氏链的蒙特卡罗方法,即Metropolis算法,并在最早的计算机上编程实现。Metropolis 算法是首个普适的采样方法,并启发了一系列 MCMC方法,所以人们把它视为随机模拟技术腾飞的起点。 Metropolis的这篇论文被收录在《统计学中的重大突破》中, Metropolis算法也被遴选为二十世纪的十个最重要的算法之一。

我们接下来介绍的MCMC 算法是 Metropolis 算法的一个改进变种,即常用的 Metropolis-Hastings 算法。由上一节的例子和定理我们看到了,马氏链的收敛性质主要由转移矩阵$P$ 决定, 所以基于马氏链做采样的关键问题是如何构造转移矩阵$P$,使得平稳分布恰好是我们要的分布$p(x)$。如何能做到这一点呢?我们主要使用如下的定理。
继续阅读

LDA-math-MCMC 和 Gibbs Sampling(1)

3  LDA-math-MCMC 和 Gibbs Sampling
3.1 随机模拟

随机模拟(或者统计模拟)方法有一个很酷的别名是蒙特卡罗方法(Monte Carlo Simulation)。这个方法的发展始于20世纪40年代,和原子弹制造的曼哈顿计划密切相关,当时的几个大牛,包括乌拉姆、冯.诺依曼、费米、费曼、Nicholas Metropolis, 在美国洛斯阿拉莫斯国家实验室研究裂变物质的中子连锁反应的时候,开始使用统计模拟的方法,并在最早的计算机上进行编程实现。

simulation随机模拟与计算机

现代的统计模拟方法最早由数学家乌拉姆提出,被Metropolis命名为蒙特卡罗方法,蒙特卡罗是著名的赌场,赌博总是和统计密切关联的,所以这个命名风趣而贴切,很快被大家广泛接受。被不过据说费米之前就已经在实验中使用了,但是没有发表。说起蒙特卡罗方法的源头,可以追溯到18世纪,布丰当年用于计算$\pi$的著名的投针实验就是蒙特卡罗模拟实验。统计采样的方法其实数学家们很早就知道,但是在计算机出现以前,随机数生成的成本很高,所以该方法也没有实用价值。随着计算机技术在二十世纪后半叶的迅猛发展,随机模拟技术很快进入实用阶段。对那些用确定算法不可行或不可能解决的问题,蒙特卡罗方法常常为人们带来希望。

monte-carlo-simulation蒙特卡罗方法

继续阅读

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

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$是变量)
继续阅读