Categories

Calendar

November 2017
M T W T F S S
« Jun    
 12345
6789101112
13141516171819
20212223242526
27282930  

机器学习物语(2):大数定理军团

机器学习理论帝国崛起,大数定理军团功不可没,称之为军团毫不夸张,在前军先锋强大数定理和副将弱大数定理后面,是铠甲上刻着“Concentration of Measure”的古老印记的战士们,不妨暂且忽略他们之间乱七八糟的“血缘”关系,而罗列一些名字:Chebyshev 不等式、 Markov 不等式、 Bernstein 不等式、 Hoeffding 不等式、 McDiarmid 不等式、 Chernoff 不等式……虽然他们之间互相关系微妙,但是在战斗中却是各有千秋,特别是在装备了现代化的“大规模杀伤性武器”——

概率与测度 (4):闲扯大数定理与学习理论

本文属于概率与测度系列。

在本系列的上一篇文章中,我偷偷留了一个问题:为什么具体试验所得到的频率是趋向于该事件的概率的。这个问题似乎是显而易见的,但是仔细想想似乎也并不显然,并不能一下子得出这个结论来。事实上,历史上有以这个性质作为基础来构建概率论的理论体系的尝试,不过在现在的概率论公理化体系下面,这个可以作为一个结论推导出来,具体来说,它是大数定理的一个特殊情况。不过如本文标题所说,这次只是闲扯,因为我们目前的进度还没有到大数定理那里,所以就不仔细介绍众多形式的大数定理了,下面只给一个常见的形式,并且暂时省略证明:

概率与测度 (3):概率模型

本文属于概率与测度系列。

系列的前面两篇大致陈述了一下测度论方面的基础,由于这个学期有去旁听《概率论》这门课,所以主要还是按照课程进度来吧,不定期地把课程里一些有意思的内容抽取出来整理在这里。这次就说概率模型。

先从一个例子开始,比如一个盒子里放了 8 个黑球和 2 个白球,从盒子里随机拿一个球,问它是白球的概率是多少,大家都会不假思索地说,1/5 。的确,这似乎是很显然的,不过,实际上我们是用了一个模型来进行概率分析,但是由于这个情况实在太简单了,我们根本就没有注意到模型的存在性,但是换一个稍微简单的例子,要忽略模型“走捷径”有时候就会一下子想不清楚了。比如两个人各掷一个骰子,问 A 得到的点数比 B 大的概率。这个问题就比刚才那个问题要困难一些了。

最早人们在对这类概率问题进行数学抽象的时候,归纳出来的一种模型,现正称为古典概率模型。该模型包由一个包含有限个(设为 $N$)元素的样本空间 $\Omega$ 组成,$\Omega$ 中的每一个元素称为一个基本事件,$\Omega$ 的任意一个子集是一个事件。所有基本事件的概率是相等的,即 $1/N$ ,而任意事件的概率即为该集合的元素个数乘以 $1/N$ ,换句话说:

\[
P(A) = \frac{|A|}{N}
\]

也就是该事件集合的元素个数除以样本空间的总元素个数。对于第一个例子,我们可以这样建立模型:对每一个球编号,一共 1 到 10 号,设 8 号和 9 号是白球,其他的都是黑球,样本空间 $\Omega$ 为 {抽到的是 1 号球、抽到的是 2 号球、……、抽到的是 10 号球} ,而“抽到白球”这个事件集合即 {抽到的是 9 号球、抽到的是 10 号球} ,简单计算立即得到 1/5 的概率。

对于第二个问题,我们用一个 tuple $(x,y)$ 来记两次掷骰子的结果,则整个样本空间集合为 {$(x,y)$, $x=1,\ldots,6$, $y=1,\ldots,6$} 一共 36 […]

概率与测度 (2):积分与期望

本文属于概率与测度系列。

上一次我们谈到零测集的概念。之所以提出来,一方面是因为它比较好玩,另一方面是它和另一个重要概念息息相关。这个东西就是“几乎处处 (Almost everywhere)”,经常被缩写为“a.e.”。例如,“函数 $f$ 几乎处处等于零”——当我第一次看到这个样子的话的时候,就被深深地雷到了。 =.=bb 当然,我是后来才知道,这个东西是有严格定义的。把一个听起来就模棱两可的词强行加上一个严格的定义,然后直接拿来用,果然搞数学的人好洒脱!

回到 a.e. ,它的定义其实很简单,我们说某个性质“几乎处处”成立,严格地来说,就是在讲它除了在一个零测集上不成立之外,在其他地方都成立。例如,传说中的 Dirichlet function $\chi_\mathbb{Q}$,它在有理数上取值为 1 ,在无理数上取值为 0 (题外话:这个玩意它还是一个处处不连续的函数)。注意到 $\mathbb{Q}$ 的 (Lebesgue) 测度为零的,因此 $\chi_\mathbb{Q}$ 除了在一个零测集上之外,其他地方都取值为零,那么我们就说它“几乎处处为零”。

和这个对应的概率论里常用的还有一个看起来更雷人的概念,叫做 almost surely (或者叫做 almost certain 、almost always) ,说某件事情 almost surely 成立,就是说这件事情在一个“满测度”集合上成立。所谓“满测度”集就是说它的补集的测度为零,而并不一定要求补集是空集。不过零测集和空集之间的关系,如果不严加定义的话,仅用文字描述起来很难搅清楚,而用上了 almost surely 这样的看起来很模糊的词,就更加雪上加霜了。也许,都是那些数学工作者的错——选了一些表面上看起来很混淆的用词,结果导致一些人在并不知道真正严格含义的情况下纠缠在字面上的意思,最终沦落为民科啊……

当然,抛开用词不说,a.e. 的引入在实分析中是必要的——而并不只是简单的把原来的一些“处处成立”的定理推广为“几乎处处成立”这样一个看上去无关痛痒的扩展。可以想像一下,应该是某个定理在条件中不是 a.e. ,但是结论只能得到 a.e. ,所以说如果去掉 a.e. 这个概念的话,整条路就走不通了。不过,这里暂时还没法详细说这个问题。于是下面以一幅 6 格漫画结束开场白,正式进入这次的主题——“积分”吧!

概率与测度 (1):关于测度

本文属于概率与测度系列。

我又来挖坑了。因为打算抽时间(比如下学期或者下下学期)来学一下概率论,所以学习过程中的一些感想或者笔记什么的应该会不定期地整理出来。这算一个开头吧。

其实概率论似乎经常处于一个比较尴尬的地位,在历史上一度被认为并不属于数学的一部分,直到将测度论引入以建立起严格的公理体系之后,才被数学界所承认。当然,说它“不是数学”,仅仅就是字面上的意思,并没有说什么东西不是数学就一定是不好的。事实上,在被严格化之前,概率统计作为一种工具就已经被广泛应用到各个领域中了,当然,在严格的理论体系建立之后,不论从理论上还是应用上,都得到了爆炸性的发展。然而,仅从大学的教育来看,概率论似乎仍然处境尴尬。

比如在 ZJU 本科,似乎概率论是像 C 语言一样的全校必修的一门课(我从来没有搞清楚过学校的选课规则,以前选课大致都是跟风室友的),足见其用途之广泛。然而除了理学院的一些专业之外,其他专业的概率论教学并没有得到近代概率论的严格化所带来的好处。或者说,这样的东西在这样的上下文下原本就是不需要的吧,毕竟对于工科甚至文科的学生来说,概率就是一种工具而已。其实大部分时候都没有什么问题,但是一些模糊的没有良好定义的概念,有时候会带来问题,看看网络上各种流行的概率相关的趣味问题,比如好像有一个问题是说,有三扇门,其中一个后面有奖励,让你任选一扇门,然后主持人打开剩下的两扇中的其中一扇给你看后面没有奖励,然后问你要不要放弃最开始的选择,而选剩下的那一扇门。类似的问题经常会引发大量的争论,大家各执一词,互不相让,许多情况下引起争议的根源都来自于其中有一些“看起来很明显”但是其实并没有经过严格定义的术语的理解的偏差。

另一方面,虽然数学系的概率论课程确实从严格的角度来教授了,但是听我身边认识的数学系的人说来,他们专业的好多人其实都并不对概率论这门课很有兴趣。因为大家选了两门课“概率论”和“实变函数”,然后发现两门课讲的东西差不多是一样的。实分析课上讲测度论,而概率差不多就是一个归一化了的测度,于是大家都有一种“被坑了”的感觉。 ^_^bb