所有由rickjin发布的文章

腾讯广点通招聘广告数据分析师

广点通广告数据分析师

岗位职责:

针对特定的广告行业需求,基于大规模用户数据,对用户兴趣、偏好进行数据挖掘和分析,挖掘广告主感兴趣的人群,协助广告主在广点通系统中进行广告定向投放, 并通过数据分析追踪广告投放效果,推动特定广告行业的效果优化。

岗位要求:

  1. 本科以上学历,数学[……]

继续阅读

神奇的伽玛函数(上)

一、开篇

数学爱好者们汇集在网络论坛上的一大乐事就是对各类和数学相关的事物评头论足、论资排辈。如果要评选历史上最伟大的数学家,就会有一大堆的粉丝围绕高斯、黎曼、牛顿、欧拉、阿基米德等一流人物展开口水战;如果要讨论最奇妙的数学常数,$e, \pi, \phi=\frac{\sqrt{5}-1}{[……]

继续阅读

[LDA数学八卦-5]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-dice

LDA模型

[……]

继续阅读

[LDA数学八卦-4]文本建模

4. 文本建模

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

corpus

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

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

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

[……]

继续阅读

[LDA数学八卦-3]MCMC 和 Gibbs Sampling

3.1 随机模拟

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

simulation

随机模拟与计算机

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

[……]

继续阅读

[LDA数学八卦-2]认识Beta/Dirichlet分布

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)}$ 的分布是什么。[……]

继续阅读

[LDA数学八卦-1]神奇的Gamma函数

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 函数发现的历史,要说清楚它需要一定的数学推导,这儿只是简要的说一些主线。

[……]

继续阅读

正态分布的前世今生(下)

6. 开疆拓土,正态分布的进一步发展

19世纪初,随着拉普拉斯中心极限定理的建立与高斯正态误差理论的问世,正态分布开始崭露头角,逐步在近代概率论和数理统计学中大放异彩。在概率论中,由于拉普拉斯的推动,中心极限定理发展成为现代概率论的一块基石。而在数理统计学中,在高斯的大力提倡之下,正态分布开始逐步畅行于天下。

6.1 论剑中心极限定理

先来说说正态分布在概率论中的地位,这个主要是由于中心极限定理的影响。 1776 年,拉普拉斯开始考虑一个天文学中的彗星轨道的倾角的计算问题,最终的问题涉及独立随机变量求和的概率计算,也就是计算如下的概率值
$$ S_n = X_1 + X_2 + \cdots + X_n $$
$$P(a < S_n < b) = ? $$

在这个问题的处理上,拉普拉斯充分展示了其深厚的数学分析功底和高超的概率计算技巧,他首次引入了特征函数(也就是对概率密度函数做傅立叶变换)来处理概率分布的神妙方法,而这一方法经过几代概率学家的发展,在现代概率论里面占有极其重要的位置。基于这一分析方法,拉普拉斯通过近似计算,在他的1812年发表的名著《概率分析理论》中给出了中心极限定理的一般描述:

定理:[拉普拉斯, 1812]  $ e_i (i=1, \cdots n)$ 为独立同分布的测量误差,具有均值$\mu$ 和方差 $\sigma^2$。如果 $\lambda_1, \cdots, \lambda_2$ 为常数, $a>0$, 则有
$$ \displaystyle P\left(\left|\sum_{i=1}^n \lambda_i(e_i – \mu)\right|
\le a \sqrt{\sum_{i=1}^n \lambda_i^2}\right)
\approx \frac{2}{\sqrt{2\pi}\sigma} \int_0^a e^{-\frac{x^2}{2\sigma^2}} dx . $$

这已经是比棣莫弗-拉普拉斯中心极限定理更加深刻的一个结论了,理科专业的本科生学习《概率论与数理统计》这门课程的时候,通常学习的中心极限定理的一般形式如下:

[林德伯格-列维 中心极限定理] 设$X_1,\cdots, X_n$ 独立同分布,且具有有限的均值 $\mu$ 和方差 $\sigma^2$ ,则在 $n \rightarrow \infty$ 时,有
$$ \displaystyle \frac{\sqrt{n}(\overline{X} – \mu)}{\sigma} \rightarrow N(0,1) .$$

多么奇妙的性质,随意的一个概率分布中生成的随机变量,在序列和(或者等价的求算术平均)的操作之下,表现出如此一致的行为,统一的规约到正态分布。

central_limit_theorem

中心极限定理

概率学家们进一步的研究结果更加令人惊讶,序列求和最终要导出正态分布的条件并不需要这么苛刻,即便 $X_1,\cdots, X_n$ 并不独立,也不具有相同的概率分布形式,很多时候他们求和的最终的归宿仍然是正态分布。一切的纷繁芜杂都在神秘的正态曲线下被消解,这不禁令人浮想联翩。中心极限定理恐怕是概率论中最具有宗教神秘色彩的定理,如果有一位牧师拿着一本圣经向我证明上帝的存在,我是丝毫不会买账;可是如果他向我展示中心极限定理并且声称那是神迹,我可能会有点犹豫,从而乐意倾听他的布道。如果我能坐着时光机穿越到一个原始部落中,我也一定带上中心极限定理,并劝说部落的酋长把正态分布作为他们的图腾。

[……]

继续阅读

正态分布的前世今生(上)

神说,要有正态分布,就有了正态分布。
神看正态分布是好的,就让随机误差服从了正态分布。
创世纪—数理统计

1. 正态分布,熟悉的陌生人

学过基础统计学的同学大都对正态分布非常熟悉。这个钟形的分布曲线不但形状优雅,它对应的密度函数写成数学表达式
$$ \displaystyle f(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{{(x-\mu})^2}{2\sigma^2}} $$
也非常具有数学的美感。其标准化后的概率密度函数
$$ \displaystyle f(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}} $$
更加的简洁漂亮,两个最重要的数学常量 $\pi$、$e$ 都出现在这公式之中。在我个人的审美之中,它也属于 top-N 的最美丽的数学公式之一,如果有人问我数理统计领域哪个公式最能让人感觉到上帝的存在,那我一定投正态分布的票。因为这个分布戴着神秘的面纱,在自然界中无处不在,让你在纷繁芜杂的数据背后看到隐隐的秩序。

normal_curve

正态分布曲线

正态分布又通常被称为高斯分布,在科学领域,冠名权那是一个很高的荣誉。2002年以前去过德国的兄弟们还会发现,德国1991年至2001年间发行的的一款10马克的纸币上印着高斯(Carl Friedrich Gauss, 1777-1855)的头像和正态密度曲线,而1977年东德发行的20马克的可流通纪念钢镚上,也印着正态分布曲线和高斯的名字。正态分布被冠名高斯分布,我们也容易认为是高斯发现了正态分布,其实不然,不过高斯对于正态分布的历史地位的确立是起到了决定性的作用。

10dm_with_gauss_curve 10dm_with_gauss_curve_detail   20-mark-gauss
德国马克和纪念币上的高斯头像和正态分布曲线

正态曲线虽然看上去很美,却不是一拍脑袋就能想到的。我们在本科学习数理统计的时候,课本一上来介绍正态分布就给出分布密度函数,却从来不说明这个密度函数是通过什么原理推导出来的。所以我一直搞不明白数学家当年是怎么找到这个概率分布曲线的,又是怎么发现随机误差服从这个奇妙的分布的。我们在实践中大量的使用正态分布,却对这个分布的来龙去脉知之甚少,正态分布真是让人感觉既熟悉又陌生。直到我读研究生的时候,我的导师给我介绍了陈希儒院士的《数理统计学简史》这本书,看了之后才了解了正态分布曲线从发现到被人们重视进而广泛应用,也是经过了几百年的历史。

正态分布的这段历史是很精彩的,我们通过讲一系列的故事来揭开她的神秘面纱。

[……]

继续阅读

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 (和布蕪, めかぶ), 是作者最喜欢的食物.

目录

UTF8_EXCERPT_H[……]

继续阅读