组合数学中的采样(Sample)问题 (一):基本概念和两种形式

前面的一系列帖子介绍了组合数学中的分配问题。另一个组合数学的基本模型是采样模型,很多排列组合问题都可以从这个模型开始思考。

采样问题有两种基本形式,第一种是可以重复采样的,比如所有长度为10个字母的英文单词,可以看做该单词的每个字母都从26个英文字母中挑选一个,这样的挑选重复10次。很明显,所有可能的单词总数是:

(1)   \begin{equation*} 26^{10} \end{equation*}

第二种是不能重复采样的,比如假定我们有 n 个人,需要从其中挑出 r 个样本。很明显第一个人有 n 种选择,第二个人就只有 n-1 中选择了。所有可能的样本总数是:

(2)   \begin{equation*} n \times (n-1) \times (n-2) \times ... \times (n-r+1) = P_n^r \end{equation*}

今天很开心,对于工作中纠结了快三个月的模型终于有了深刻的认识

更新现在这个模型已经快三个月了,现在终于有了深刻的认识:

  • 训练数据的问题想要通过模型来修正,那是很困难的,如果能够消除这些不正确的数据,那么一切都会顺利很多。消除的办法可以是简单的 Rule 过滤,也可以是加上权重。
  • 把多Label 标注的问题转化成为一个简单的 Binary Classifier 掩盖了很多实际的问题,但是通过检查模型在每一个 Label 上的表现,可以更好地发现到底是哪里的训练数据有问题。

最后吐槽一下,互联网上的图片,女人的衣服占得比例实在是太多啦!

组合数学中的分配问题(五):桥牌发牌

最近迷上了和孩子们打桥牌,顺便看到 William Feller 的书,提到桥牌四家牌的总共可能的分布一共接近 {10}^{30},鉴于这个老爷爷在他的书中一开始就犯了一个简单的错误,这类数字我也是不敢盲目相信了,还是自己验算一下吧。

桥牌的52张牌都是不同的,四个玩家东南西北也是不同的,所以这是一个可以区分的对象分配到可以区分的组中的问题,不过这个问题和我们在 组合数学中的分配问题(一):可以区分的对象和组 中讨论的有所不同,每一家拿到的牌的数量是一样的,都是13张。 对于这类问题有一个简单的思路: 从52张牌中挑选13张牌发到第一家的所有可能组合是:

(1)   \begin{equation*} \begin{split} &{52 \choose 13} \\ &= \frac{52 \times 51 \times 50 \times ... \times 42 \times 41 \times 40}{13 \times 12 \times 11 \times ... \times 3 \times 2 \times 1} \\ &= \frac{52 \times 51 \times 50 \times ... \times 42 \times 41 \times 40}{13!} \end{split} \end{equation*}

然后从剩下的39张牌中继续挑出13张牌发给第二家的所有可能组合是:

(2)   \begin{equation*} \begin{split} &{39 \choose 13} \\ &= \frac{39 \times 38 \times 37 \times ... \times 29 \times 28 \times 27}{13 \times 12 \times 11 \times ... \times 3 \times 2 \times 1} \\ &= \frac{39 \times 38 \times 37 \times ... \times 29 \times 28 \times 27}{13!} \end{split} \end{equation*}

综合起来,发给这两家牌的总共可能方案是:

(3)   \begin{equation*} \frac{52 \times 51 \times 50 \times ... \times 29 \times 28 \times 27}{13! \times 13!} \end{equation*}

以此类推下去,发给四家牌的所有总共可能方案是:

(4)   \begin{equation*} \begin{split} &\frac{52!}{13! \times 13! \times 13! \times 13!} \\ &= 53,644,737,765,488,792,839,237,440,000 \\ &\approx 5.3 \times 10^{28}  \\ &\approx 10^{30} \end{split} \end{equation*}

看来老爷爷这次又搞对了。 🙂

一般来说,把 n 个可以区分的对象分配到 r 个可以区分的组中,其中每个组的数量分别是 m_1 + m_2 + m_3 + ... + m_r = n ,总共的分配方案一共是:

(5)   \begin{equation*} \dfrac{n!}{m_1! \times m_2! \times m_3! \times ... \times m_r!} \end{equation*}

顺便提一下,从 n 个可以区分的对象中取出 m 的对象的组合数公式是上面公式的特例。想象我们需要把这n个对象分为两组,一组是 m个,另外一组是n-m个,那么按照上面的公式,我们有:

(6)   \begin{equation*} \dfrac{n!}{m!  \times (n-m)!} \end{equation*}

这刚好和组合数公式一模一样。

顺便再深入一下,在所有这 {10}^{30} 的可能分布中,每一家都有一个 Ace 的可能性是多大呢?

把4个Ace 发到四家手中,而且保证每人有一个的方案总共是:

(7)   \begin{equation*} \dfrac{4!}{1! \times 1! \times 1! \times 1!} = 4! \end{equation*}

把剩下的48张牌发到四家手中,而且保证每人有12张的方案总共是:

(8)   \begin{equation*} \dfrac{48!}{12! \times 12! \times 12! \times 12!} \end{equation*}

所以每一家都有一个 Ace 的可能性就是上面的方案总数除以所有的方案总数,即:

(9)   \begin{equation*} \dfrac{\dfrac{48!}{12! \times 12! \times 12! \times 12!} \times 4!}{\dfrac{52!}{13! \times 13! \times 13! \times 13!}} \approx 0.105 \end{equation*}

看来均贫富的概率只有十分之一啊。:-(

An Introduction to Probability – Theory and its Applications 学习笔记 (二):组合数学是概率论的基础

自己在看了这本概率论教材之后才认识到原来组合数学是概率论的基础,难怪这本书一开始就花了好几章来讲组合数学,下面讲讲书中的两个基本的例子。

一、如果把 r 个球放到 n 个盒子中,一共有多少种分配方法?

这个问题本身很简单,我在 组合数学中的分配问题(一):可以区分的对象和组 中有过详细的介绍,答案就是 n^r。搞笑的是,作者在这个问题上却犯了个错:假定有 4 个球 放到 3 个 盒子里,总共的分配方法应该是 3^4 = 81 种,书中却搞成了 4 ^ 3 = 64 种,让人大惊失色,难道这么经典的教材还会在这个简单的问题上犯错吗?那书里教的东西大家还信得过吗? 🙁  详细讨论参见 Math Exchange的这个帖子

二、随机采样100个人,按照是否抽烟和男女性别两个属性把这100个人分为4组:

  • 男性抽烟
  • 男性不抽烟
  • 女性抽烟
  • 女性不抽烟

总共可能的分组数目是多少呢?

这个问题也是分配问题的一种,具体来讲,分成的每个组是可以区分的,比如(20, 20, 20, 40)和(20, 20, 40, 20) 是两种不同的分组方式。但是分配对象本身是不可区分的,我们只关心每个组中有多少人,所以它属于 组合数学中的分配问题(二):不能区分的对象和可以区分的组 中介绍的那类问题。因为每一组的人数都有可能为0,所以总共的分组方案是:

(1)   \begin{equation*} {(100 + 4 - 1) \choose 3} = {103 \choose 3} = 176,851 \end{equation*}

这次 William Feller 老先生在书中终于把答案搞对了。 🙂

An Introduction to Probability – Theory and its Applications 学习笔记 (一):基本概念

下面是书中的几个基本概念:

  • Experiment:  Throw a dice; Sample 100 people from all populations of USA; Assign 4 balls into 3 cells; Throw  5 dices at the same time; etc.
  • Event: The result of an experiment, this really depends on the way you want to measure. For example, suppose the experiment is to throw a dice:
    1.  The dice gives 5, this is an event.
    2. The dice gives a number larger than 4, this is also an event.
  • Simple Event:  For the event like “The dice gives a number larger than 4”, it could be that the dice gives 5 or the dice give 6. In this sense, “The dice gives 5” is a simple event, but “The dice gives a number larger than 4” is a compound event. A compound event is an aggregation of certain simple events.
  • Sample Space: To define an experiment without ambiguity, we must agree on all the possible simple events. In this strict term, one simple event is also called a sample point, the aggregation of all the simple events is call sample space.

简单的决策树(Decision Tree)

最近做的一个项目用到了 Boosted/Bagged Decision Tree,趁这个机会顺便补习了一下基本的决策树的知识,这篇文章来说一说。

决策树(Decision Tree)是一种有监督机器学习的基本方法,它比较适合结果分类不是很多的场合,其优点是得到的模型能够很容易解释,因此可以帮助人们理解各个输入信号与最终预测目标的关系。在很多场合,这一目的甚至比能够准确地进行预测还要重要。比如某些数据的收集过程需要花费很多时间和精力,如果通过决策树建模发现这个数据对于最终模型的贡献不大,我们就可以从最终模型中去掉这个输入数据,从而节约时间和精力。

假定我们需要预测某一个网站的用户会不会订阅付费服务,为此我们收集了一组用户的数据以及他们是否最终订阅了付费服务,数据如下:

Referrer Location Daily View Device Subscribe Payed Service
Google US 50 Mac OS Yes
Google French 75 Windows Yes
Slashdot US 93 Ubuntu No

决策树模型正如其名,模型是一个树状结构。除开叶子节点以外,其他每一个节点都是一个条件判断,用来决定下一步是选择左子树还是右子树,叶子节点就是分类的结果。下图就是一个模型的示例:

这样的树是怎么构建出来的呢?最简单的决策树的训练方法被称为 CART (Classification and Regression Tree Analysis),本质是一个递归的过程。为了理解这个过程,我们首先要回到一个基本的概念:信息熵

对于一个离散型的随机变量X,假定它有 N 个可能的结果,每一个结果出现的概率是 p(x_i) ,那么该随机变量X 的信息熵定义如下:

(1)   \begin{equation*} H(x) = \sum_{i=1}^{N} p(x_i) \cdot \log \dfrac {1}{p(x_i)} \end{equation*}

这里我们的随机变量就是 用户是否会订阅我们的收费服务,可能的取值有 Yes 和 No 两种,而每一种结果的概率,就是数据中该结果的数目除以总共的数据数目。

在引入了上面的的信息熵的定义之后,针对每一组数据,我们就可以计算它的熵。决策树模型的训练过程最基本的目标就是不断的减少分组中数据的熵。具体来讲,针对每一组数据,我们可以遍历所有的输入信号的所有可能取值,每一对(Signal, Value) 可以作为一个判断条件,把当前的数据分为两组。下来我们计算这两组数据的熵,并把它们的和与当前的数据的熵进行比较,得出熵减少的数量。在遍历了所有的(Signal, Value)以后,我们就可以找到一对 (Signal, Value) ,当使用它作为判断条件的时候,熵减少最大,这就是我们要对当前数据创建的判断条件。 把上述的过程递归的应用于两个新生成的组,最终我们就可以得到一棵完整的决策树。

决策树的训练过程还有很多细节,比如在比较当前数据的熵和两个新组的熵之和时,我们通常要把两个新组的大小作为权重来考虑。再比如实际创建决策树的时候,为了防止 Overfitting,子节点可以不是只有一个明确的答案,而是给出好几种答案以及它们各自的概率。另外按照上面的算法生成好决策树以后,我们也可以对于模型进行裁剪,这些细节在这里就不展开了。

Yeti Math Bloggie 34: Alina’s Cookies :P

Yo peeps, Yeti here! As a lover of cookies 😛 I shall put a math related cookie problem in this post, because I merely feel like it. We start with the problem itself:

When Alina was hungry she ate c cookies, which was 30% of all the cookies she had. How many cookies did she have in the beginning?

You sees, there are 3 numbers the problem:

  • The total number of cookies: x
  • The number of cookies she ate: c
  • % of the cookies she ate: 30%

There is a word in this problem that can help us with solving it: of                       This word means to multiply the #’s in front on behind the word. More can be found out in post #17 X of Y, of this series. “… 30% of all the cookies she had. …” basically means, we get that (assuming x is the total number of cookies) c is 30% of x.

Translating that into an algebraic equation gets you:

(1)   \begin{equation*} x \times \dfrac{3}{10} = c \end{equation*}

Solving for x gets you

(2)   \begin{equation*} x = \dfrac{10c}{3} \end{equation*}

Yeeto Yeets!

衡量分类器效果的一些指标 (3) – AUC/ROC 曲线

这个系列的 第一篇文章 讲述了衡量分类器效果的一些基本概念,第二篇文章 讲述了 PR 曲线一些特定的知识,今天这篇文章讲一讲 AUC/ROC 曲线,以下简称 ROC 曲线。

ROC 曲线也是使用Confusion Matrix 中的数据来衡量分类器的性能。同样,在选定了特定的阈值以后,对于一组已经标定好的数据,我们可以计算它的 True Positive, False Positive, False Negative, True Negative。在这四个数据算好以后,我们有以下两个新的定义:

True Positive Rate (TPR)

(1)   \begin{equation*} \text{ TPR } = \frac{TP}{TP + FN} \end{equation*}

直观来讲,TPR 反映的就是模型标定为正例的那些正例占总共数据中的所有正例的比例。在讨论 Precision/Recall 的背景下,这个东西其实就是Recall。但是在 ROC的背景下,TPR 这个名字更有意义一些,以便和下面的 FPR 对应。

False Positive Rate (FPR)

(2)   \begin{equation*} \text{ FPR } = \frac{FP}{FP + TN} \end{equation*}

直观来讲,FPR 反映的就是模型错误的标定为正例的那些负例占总共数据中的所有负例的比例。

很明显,在阈值(Threshold)增加的时候,模型标定的正例(Postive)会减少,因为标定的正例包含了 True Positive 和 False Positive,因此 TPR 和 FPR 都会下降。同样在 阈值(Threshold)减少的时候 TPR 和 FPR 都会上升。极端的情况下,如果我们选取阈值为1,那么所有的数据都被模型预言为反例,则True Positive 和 False Positive 都为 0,那么TPR 和 FPR都是0。而当我们选取阈值为0的话,所有的数据都被模型预言为正例,那么 True Negative 和 False Negative 都是 0,这样 TPR 和 FPR 都是 1。

在有了 TPR 和 FPR 的定义以后,我们就可以画出 ROC 曲线了。ROC 曲线就是对于一个特定的模型和一组标定好的数据,我们从0到1遍历所有可能的阈值,然后计算每个阈值对应的TPR 和 FPR,在把 FPR 作为横坐标,TPR 作为纵坐标,把计算出来的(TPR, FPR)标在图上,就形成了 ROC 曲线。下图是一个典型的 ROC 曲线。

根据前面的分析可以看出,ROC 曲线总是要通过 (0,0) 和 (1,1) 这两个点。那么曲线上其他的点有什么特征呢?这要从分类模型本身说起。

分类模型的作用是给每个数据点输出一个从0到1的分数来表示该数据点属于正例的概率。在最理想的情况下,假定正例的分数全部大于负例,比如正例的分数是从0.6 到 1.0,而负例的分数是从 0 到 0.4,如下图所示。

在这个模型的输出中,如果我们把阈值从0.0开始逐步增加到1.0,在刚开始的一段范围内,False Negative 一直都是0,所以TPR 一直都是1,而同时 False Positive 的数量一直在减少,而 True Negative 的数量一直在增加,因此 FPR 一直在减少,等到阈值来到0.4 到0.6这个区间,False Negative 和 False Positive 都变成了0,因此 TPR 等于1 而 FPR 等于0。 等到阈值跨过了0.6以后,False Positive 保持为0 而 False Negative 开始增加,这个时候 FPR 保持为 0 而 TPR 开始减少,直到最后到达(0,0)这个点。在这种理想情况下的 ROC 曲线如下图所示:

如果分类器的输出没有那么理想,正例和负例的分数范围有重叠(如下图所示),这种时候的ROC曲线就不再是上图那样方方正正,而是向上弯曲,但是无法到达 (FPR=0, TPR=1)这个点。就像我们本文开始时列出的那个图一样。

在使用ROC曲线的时候,我们通常并不关心曲线上的某个特定点,而是使用曲线包围的面积(Area Under Curve, AUC)作为衡量模型整体性能的一个重要指标。这个曲线下的面积有一个重要的物理意义,它表示在测试数据中随机选取一个正例和一个反例,分类模型对正例打分比负例打分更高的概率,很明显,曲线下的面积越大,模型的总体性能就越好,而且这一结论和具体的阈值无关。这一结论的证明如下(摘自 Wikipedia):

假定我们有一个二分类模型,该模型对于所有正例的打分的概率分布(也就是概率密度函数)是:f_1(x),其中x 代表某个正例的分数。同样我们可以假定该模型对于反例打分的概率分布是:f_0(x)。有了这样的概率密度函数定义之后,在某个阈值T下,TRP 和 FPR 可以分别表达如下:

(3)   \begin{equation*} TPR(T) = \int_{T}^{+ \infty} f_1(x) dx \end{equation*}

(4)   \begin{equation*} FPR(T) = \int_{T}^{+ \infty} f_0(x) dx \end{equation*}

ROC 曲线下的面积可以表达为如下积分:

(5)   \begin{equation*} \text{Area} = \int_{0}^{1} \text{TPR }  \text{ dFPR} \end{equation*}

上面积分的自变量是 FPR,因为上面定义的 TPR 和 FPR 的自变量都是 T,所以我们需要把这个积分的自变量替换成为 T 以便求值。注意到函数FPR的定义是一个对于 T 的积分,我们很容易得到:

(6)   \begin{equation*} \frac{dFPR}{dT} = f_0(T) \end{equation*}

将上式代入面积的积分,我们有:

(7)   \begin{equation*} \text{Area} = \int_{0}^{1} \text{TPR }  \text{ dFPR} = \int_{- \infty}^{+ \infty} TPR(T) \cdot f_0(T) dT \end{equation*}

注意到 TPR 本身的定义也是一个积分,将TPR 的定义代入上面的面积公式,我们就得到了如下的二重积分(对于 TPR 我们使用一个新的自变量符号 T ^{\prime} ):

(8)   \begin{equation*} \begin{split} &\text{Area} \\ &= \int_{- \infty}^{+ \infty} TPR(T) \cdot f_0(T) dT \\ &= \int_{- \infty}^{+ \infty} \int_{T}^{+ \infty} f_1(T^{\prime}) \cdot f_0(T)  dT^{\prime} dT \end{split} \end{equation*}

上面的公式推导看似让人眼花缭乱,实际并不复杂,关键是上式最后一行的意义。考虑从测试数据中随机取出一个正例和一个负例,模型给正例打某个分值x的概率是是 f_1(x)dx,模型给负例打某个分值y的概率是是 f_0(y)dy,那么如果我们要求 x>y,那么这一条件成立的概率就是:

(9)   \begin{equation*} P(x>y) = \int_{- \infty}^{+ \infty} \int_{y}^{+ \infty} f_1(x) \cdot f_0(y)  dx dy \end{equation*}

比较 89 两个公式,除了符号不同,我们可以看到它们是完全一样的,这就证明了:

(10)   \begin{equation*} P(x>y) = \text{Area of ROC} \end{equation*}

与 PR 曲线相比,ROC 曲线在什么场合比较适用呢?这是一个很好的问题,一般认为,ROC 曲线综合考虑了测试数据中的正例和反例,因此如果我们有几种建立模型的方法(比如 人工神经网络 vs Random Forest),我们需要比较这几种方法的优劣,AUC/ROC 就是一个比较合适的方法。相反,如果我们需要估计模型在实际问题的表现,并且测试数据的正例和负例不平衡的情况下,Precision/Recall 会更准确一些。

 

分布式Top N 算法引出的数学问题

假定我们需要从 1 Billion 个数中找出 1000 个最大的数,在一台机器上算当然太慢了,一个有效的分布式算法是把这 1 Billion 个数分成 1000 份,每一份就有 1 Million 个数。然后在每一份中用一个机器找到最大的 1000 个数,然后把每一份中最大的1000 个数合起来,总共有 1000 \times 1000 = 1 \text{Million} 个数,然后再用一台机器从这最后的 1 Million 个数中找到最大的 1000 个数即可。 这样的分布式算法使用 1000台机器,大概要比只使用一台机器快 1000 倍。

一般来说,对于 N 个数,如果要找出 M 个最大的数,如果要分成 K 份进行分布式计算,那么最优的 K 值是多少呢? 很明显,分为K 份以后,每一份中有 \dfrac{N}{K} 个数字,因为是并行计算,所以我们假定我们总是能够找到足够的机器,这样这个阶段计算需要处理的数字就是 \dfrac{N}{K} 个,在最后汇总阶段需要处理的数有 K \times M 个,只能在一台机器上处理,所以总的处理时间就是正比于下面的函数:

(1)   \begin{equation*} f = \dfrac{N}{K} + K \times M \end{equation*}

应用基本的微积分求函数极值的知识我们就有:

(2)   \begin{equation*} \dfrac{df}{dK} = M - \dfrac{N}{K^2} \end{equation*}

\dfrac{df}{dK}=0,很容易得到:

(3)   \begin{equation*} K = \sqrt{\dfrac{N}{M}} \end{equation*}

对于我们上面的问题:

(4)   \begin{equation*} K = \sqrt{\dfrac{N}{M}} = \sqrt{\dfrac{1,000,000,000}{1,000}} = 1000 \end{equation*}

所以分成1000份刚好就是最佳答案。

现在我们考虑如何再改进上面的算法。考虑到第二个阶段我们需要处理 K \times M 个数,而且这个阶段只能在一台机器上进行,我们可以在这个方面想想办法。我们可以很快注意到下面一个事实:我们总共需要找到 M 个数,但是为了避免遗漏,在把数据分为 K 份以后,在每一份数据中我们都需要找到 M 个数,实际上只有在最坏的情况下,也就是所有最大的 M 个数不幸的都分到了同一份中,这样做才有意义。那么所有 M 个最大的数刚好都分到同一组中的概率有多大呢?这刚好是我们前面讲到的组合数学分组问题。

因为我们这里需要计算的是一个概率问题,需要考虑到实际的分配过程,因此这里的组和分配对象都是可以区分的。对于把M 个可以区分的对象分配到 K 个可以区分的组,刚好这 M 个数全部分到同一个组里的情况一共有 K 种,而把这 M 个数分配到K 个组中一共的分配方法有 (参见 组合数学中的分配问题(一):可以区分的对象和组K^M 种,因此所有 M 个最大的数刚好都分到同一组中的概率是:

(5)   \begin{equation*} \dfrac{K}{K^M} = \dfrac{1}{K^{M-1}} \end{equation*}

在我们设定的条件 K=1000, M=1000时,上面的概率是一个极其微小的数字。因此如果我们还需要进一步提高程序的效率,那么在每一组中找到 M-1 个数字,然后再把各组的结果合并起来,绝对可以保证我们依然能够找到所有 M 个最大的数字。 🙂