组合数学中的采样(Sample)问题 (三):组合分析计算概率的关键是所有基本事件的概率应该相等

组合分析是概率论的基础。特别的,在利用组合分析计算某个事件的概率时,我们需要确保所有基本事件的概率是相等的。这一点在我刚刚开始学习概率组合分析的时候并不明显,现在经过 William Feller 老爷爷的一番教育,终于开窍了。下面试举两例。 扔一个6面的骰子,每一面出现的概率都是 ,而且这些基本事件的概率是相等的。从这个基础出发,我们可以计算很多与掷骰子有关的概率问题。 桥牌中5张红心在两个敌手之间有三种可能的组合:0-5,1-4 和 2-3。虽然 Partition Number With k-Part Constraint  可以告诉我们总共可能的组合有三种,但是这三种结果的概率并不相同,所以在这里组合分析必须依赖 可以区分的对象和可以区分的组 一文中的技术,否则将会误入歧途。 问题一:6个骰子出现至少一个1点和12个骰子出现至少两个1点,哪个概率大? 六个骰子的所有可能的结果是 种,1点从不出现的所有可能的结果是 ,所以至少出现一个1点的概率是: (1)   十二个骰子的所有可能的结果是 种,1点从不出现的所有可能的结果是,1点出现一次的概率是 ,(第一个因子12 表示从12个骰子中挑出一个,让它的结果是1点,这一共有12种可能。第二个因子 表示剩下的11个骰子每一个都可以从 2、3、4、5、6 这5个数字中任意选择),所以至少出现两个1点的概率是: (2)   6个骰子出现至少一个1点的概率要大一些,虽然直觉告诉我们这两种相等。 🙁 问题二:桥牌中5张红心在两个敌手之间三种可能的组合:0-5,1-4 和 2-3 的概率分别是多大? 正如前面我们所说的,我们把这5张红心当作不同的牌,两个敌手也当作可以区分的对象,那么总共可能的分配是:0-5, 1-4, 2-3, 3-2, 4-1, 5-0 这么六种,0-5 和5-0 分配的总共可能方案是: (3)   类似的,1-4 和 4-1 分配的总共可能方案是: (4)   而 […]

组合数学中的采样(Sample)问题 (二):一个人被选中的概率

很多排列组合的题目都需要一个合适的思路用来描述选择的过程,一旦这个过程确定下来,又容易用基本的排列组合方式去描述,那么解决题目就容易的多了。下面就是一个典型的例子:反向思考要比正向思考容易很多。 假定我们要从 个中选出 个人编为一个排列,这个排列中包含某个固定的人 的概率是多少呢? 在上一个帖子中我们已经讲到过基本采样问题的计算方法,这里的问题需要更进一步从反向去思考,如果我们需要的这个排列不包含的话,那么总共可供挑选的人数就是 ,从中选出人的总共可能的排列就是: (1)   而从 个中选出 个人编为一个排列的总共可能性是: (2)   所以从 个中选出 个人编为一个排列,这个排列中不包含某个固定的人 的概率是: (3)   那么相应的,从 个中选出 个人编为一个排列,这个排列中包含某个固定的人 的概率就是1减去上面的概率: (4)   如果正向去思考,过程要麻烦一些,可以参考下面的思路:假定我们第一个人就选取,然后剩下的个人从剩下的个人中选取,总共可能的排列是: (5)   同理,如果我们第二个人选取,然后剩下的个人从剩下的个人中选取,总共可能的排列也是 。考虑到我们一共需要选取 个人,所以总共包含 的可能的排列就是: (6)   那么相应的,从 个中选出 个人编为一个排列,这个排列中包含某个固定的人 的概率是: (7)   上面的过程是针对选择对象不能重复(No replacement)的情况,所以正向和反向的分析复杂程度差不太多,如果是对象可以重复(With Replacement),反向分析的思路还是差不多: 从 个人中选取 个人的总共排列是: (8)   如果排除某个固定的人 ,从剩下的 个人中选取 个人的总共排列是: (9)   […]

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

前面的一系列帖子介绍了组合数学中的分配问题。另一个组合数学的基本模型是采样模型,很多排列组合问题都可以从这个模型开始思考。 采样问题有两种基本形式,第一种是可以重复采样的,比如所有长度为10个字母的英文单词,可以看做该单词的每个字母都从26个英文字母中挑选一个,这样的挑选重复10次。很明显,所有可能的单词总数是: (1)   第二种是不能重复采样的,比如假定我们有 个人,需要从其中挑出 个样本。很明显第一个人有 种选择,第二个人就只有 中选择了。所有可能的样本总数是: (2)  

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

更新现在这个模型已经快三个月了,现在终于有了深刻的认识: 训练数据的问题想要通过模型来修正,那是很困难的,如果能够消除这些不正确的数据,那么一切都会顺利很多。消除的办法可以是简单的 Rule 过滤,也可以是加上权重。 把多Label 标注的问题转化成为一个简单的 Binary Classifier 掩盖了很多实际的问题,但是通过检查模型在每一个 Label 上的表现,可以更好地发现到底是哪里的训练数据有问题。 最后吐槽一下,互联网上的图片,女人的衣服占得比例实在是太多啦!

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

最近迷上了和孩子们打桥牌,顺便看到 William Feller 的书,提到桥牌四家牌的总共可能的分布一共接近 ,鉴于这个老爷爷在他的书中一开始就犯了一个简单的错误,这类数字我也是不敢盲目相信了,还是自己验算一下吧。 桥牌的52张牌都是不同的,四个玩家东南西北也是不同的,所以这是一个可以区分的对象分配到可以区分的组中的问题,不过这个问题和我们在 组合数学中的分配问题(一):可以区分的对象和组 中讨论的有所不同,每一家拿到的牌的数量是一样的,都是13张。 对于这类问题有一个简单的思路: 从52张牌中挑选13张牌发到第一家的所有可能组合是: (1)   然后从剩下的39张牌中继续挑出13张牌发给第二家的所有可能组合是: (2)   综合起来,发给这两家牌的总共可能方案是: (3)   以此类推下去,发给四家牌的所有总共可能方案是: (4)   看来老爷爷这次又搞对了。 🙂 一般来说,把 个可以区分的对象分配到 个可以区分的组中,其中每个组的数量分别是 ,总共的分配方案一共是: (5)   顺便提一下,从 个可以区分的对象中取出 的对象的组合数公式是上面公式的特例。想象我们需要把这个对象分为两组,一组是 个,另外一组是个,那么按照上面的公式,我们有: (6)   这刚好和组合数公式一模一样。 顺便再深入一下,在所有这 的可能分布中,每一家都有一个 Ace 的可能性是多大呢? 把4个Ace 发到四家手中,而且保证每人有一个的方案总共是: (7)   把剩下的48张牌发到四家手中,而且保证每人有12张的方案总共是: (8)   所以每一家都有一个 Ace 的可能性就是上面的方案总数除以所有的方案总数,即: (9)   看来均贫富的概率只有十分之一啊。:-(

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

自己在看了这本概率论教材之后才认识到原来组合数学是概率论的基础,难怪这本书一开始就花了好几章来讲组合数学,下面讲讲书中的两个基本的例子。 一、如果把 个球放到 个盒子中,一共有多少种分配方法? 这个问题本身很简单,我在 组合数学中的分配问题(一):可以区分的对象和组 中有过详细的介绍,答案就是 。搞笑的是,作者在这个问题上却犯了个错:假定有 4 个球 放到 3 个 盒子里,总共的分配方法应该是 种,书中却搞成了 种,让人大惊失色,难道这么经典的教材还会在这个简单的问题上犯错吗?那书里教的东西大家还信得过吗? 🙁  详细讨论参见 Math Exchange的这个帖子。 二、随机采样100个人,按照是否抽烟和男女性别两个属性把这100个人分为4组: 男性抽烟 男性不抽烟 女性抽烟 女性不抽烟 总共可能的分组数目是多少呢? 这个问题也是分配问题的一种,具体来讲,分成的每个组是可以区分的,比如(20, 20, 20, 40)和(20, 20, 40, 20) 是两种不同的分组方式。但是分配对象本身是不可区分的,我们只关心每个组中有多少人,所以它属于 组合数学中的分配问题(二):不能区分的对象和可以区分的组 中介绍的那类问题。因为每一组的人数都有可能为0,所以总共的分组方案是: (1)   这次 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:  The dice […]

简单的决策树(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),本质是一个递归的过程。为了理解这个过程,我们首先要回到一个基本的概念:信息熵。 对于一个离散型的随机变量,假定它有 个可能的结果,每一个结果出现的概率是 ,那么该随机变量 的信息熵定义如下: (1)   这里我们的随机变量就是 用户是否会订阅我们的收费服务,可能的取值有 Yes 和 No […]