算法心经:数学的应用:概率的应用(上)

 

  终于写到重头戏了，如果说前面的微分积分还属于基础理论，而与我们日常的算法设计距离有点远的话，那么后面的概率、矩阵、空间立体几何，可就是和应用息息相关了。

  为什么要有概率
  概率是个数学概念，但它在计算机软件设计上有很多应用，数学概念是留给数学系的人讨论的事情，我们这里侧重的它的应用。那么为什么会在应用中用到概率，概率真正体现的是什么呢？我个人理解，概率的本质是体现了一种模糊的思想，既可以是A、又可以是B，甚至本身概率的值就是模糊的，因为没有人知道真正的概率是什么，我会在后面解释这句让人晕的话。
  理解了概率要表达模糊的思想后，我们会发现世界上绝对的事太少，甚至就是0、1写入都存在微小的写错概率，说不好的事情太多，也就决定了概率绝对是大有用处。

  概率的内容
  目前市面本科的概率书的标题一般为“概率和数理统计”，表明了概率实际分为两部分内容：概率和统计。统计是在概率分布的基础上，而单纯的概率统计不是这里要讲的重点，所以下面主要把概率理论部分分成了两块，“概率的计算”和“概率的分布”。
 
  概率的计算
  概率的求解绝对是数学的东西，这里不讨论，什么全概率、独立时间、贝叶斯公式，书上都有。这里举几个实际的例子，首先概率在算法设计分析时会碰到，就像我们在积分那节举的例子，计算出的公式几乎都基于vector里面的对象分布完全随机的，也就是每个对象在各个位置的概率都一样导出的，如果概率不一样呢？结果当然会不一样，有关计算不详加讨论。谈到了分布的概率，TAOCP《计算机程序设计艺术》在动态分配内存那章的课后题专门有一题讨论了，最佳匹配分配内存的一个最大弱点，最后的结果就是分配完空间的出现概率不平均。再有，BM字符串匹配比KMP算法的一个重要改进，就是假设字符串比较时，从后位首先出现不一样的概率比从头起出现字符不一样的概率大。甚至在搜索引擎里，pagerank的那个0.85都是模拟了用户从浏览器直接跳转的概率（尽管客观上起到了，避免矩阵奇异的效果）。
  概率计算很多都是基于经典的模型（后面会说明模型的思想在概率起到重要作用），高中数学排列组合上让我记忆犹新的一个模型就是问什么人排成一队，怎么分法时，会想象每人之间一个空格，然后对空格取组合运算。值得一提的计算模型是生日模型，由此引申的计算可以应用到判断hash的冲突的概率，比如做人机博弈时，每次alpha beta剪枝搜索（也可以不同次）需要对棋盘做hash，然后在每次再对棋局评估时，利用hash值看该棋局是否已经被评估过。应用概率，我们可以设计合理的hash code长度，然后利用生日模型，估算出该hash code长度下，棋盘的冲突概率，然后把概率限制在可接受的范围内。 因为这个计算模型太重要了，所以写一下，将M个球，放入到N个(N>M)桶时，每个桶的冲突概率是：1-N*(N-1)*(N-2)....(N-M+1)/power(N,M)，可以看出，当N个足够大时，冲突概率几乎为0。
  最后说一个曾经让我犯晕的小题，看你完全理解概率计算没？
 
  题一：打雷后下雨的概率是80%，而打闪电后下雨的概率是70%，那么即打雷又打闪电后下雨的概率是多少？不会计算没关系，直觉告诉我们肯定比80%高，恩，没错，把这题改一改变成另外一题
 
  题二：打雷后下雨的概率是80%，但是没打闪电后下雨的概率是20%，那么打雷了但没打闪电后下雨的概率是多少？不会计算没关系，直觉告诉我们肯定位于80%和20%之间。

  哦？？？晕了，怎么两个题产生的效果不一样，一个是比最高的高，一个是两个概率之间，我们的直觉错了吗，还是忽略什么重要的东西，请独立思考1分钟再看答案。
 
  相信直觉没错的，看第一题怎么解：
  解=1-又打雷又闪电但没下雨的概率= 1 - 0.2 *0.3 = 94%
  第二题：
  解=0.8 *0.2 /( 0.8 *0.2 +(1-0.8)*(1-0.2) )= 0.16/0.32= 50%
  与直觉一样，相当于大家互相拖了一下后腿，而大家的力量一样，所以扯平了，哈哈，我故意没写第二题解的说明，你是否明白了呢？
 
  其实真正忽悠人的地方在于对独立事件的理解，题一中的打雷下雨是独立事件，类似于我踢一脚门塌的概率是80%，你踢一脚的概率是70%，我们同踢时门塌的概率是94%，但是如果我不踢，对你踢有影响吗？没影响，所以结果相当于一个合力。
  题二里的事件，并不是独立事件，相当于考虑利益去做某事的概率是80%，考虑危险去做该事的概率是20%，两个是互相影响的，隐含了这个条件，你考虑了利益决定不去做这事而又考虑了危险，这时去做该事的概率是0!!!同理，你考虑了危险决定不去做这事，但是你又考虑了利益，但结果仍然去做该事的概率是0!!!实际上是一个类似单票否决的机制，最后的概率只由两部分构成，考虑了利益考虑了危险做的概率和考虑了利益又考虑了风险但不做的概率，那么做的概率就是做的概率比这两个加起来的概率的值。
  题二的关键我们的潜意识在作崇，类似于认为厂长就是男的那种，所以这题也有脑筋急转弯的类型。
  BTW：这道题的思考来源网上的一篇著名的文章“贝叶斯过滤垃圾邮件”，该文章中有一个类似的公式，但啥都没说明直接就说叫联合概率公式，后来我查书发现没这个公式，所以才反复思考这个公式是怎么出来的。

  概率的分布
  前面提过，概率的分布是另一个大部分，而且是极其庞大的部分，总体上可以分为连续变量分布和离散变量分布，对计算机应用来说，离散研究得更多一些，不过由于理论深度太高，我的水平不允许我在这里推导公式，所以建议大家去看书，这里只提一提正态分布，随机变量合符合正态分布，这是一个极为有用的结论。用浏览器浏览页面，可以有前进和后退，那么在N次浏览后，应该是按照初始的URL呈正态分布，那么多维的正态分布怎样呢，比如前进到页面里的URL每个的概率是1/N,那么浏览和后退N次后，呈现的分布是什么呢？是不是预示某些阅读习惯呢？我也不知道，留做思考吧：）

  （非常）+重要的定理：大数定理
  这里采用正则语法，表明再怎么重要也不过分。前面提到过一句话，就是概率本身的值表达的意思是个模糊的含义，甚至该值都是模糊的。现在作出解释，事实上一个事件的概率，我们根本不知道，Miller投中一个三分的概率是什么？没人知道，也没法测量，所以说所谓的概率都是近似值，因为真值不存在，这好象是讲哲学了。不管你接受不接受这样的观点，大数定理是同样为我们解决这个问题来准备的。
  大数定理说明：当事件发生足够多次时，它的发生频率就是它单次发生的概率。
  不用去管它怎么证明，我们还是要惊呼，这个看似常识的定理为宇宙把概率模型和统计模型两大世界联系了起来!!!让我们知道了对概率的分析可以用统计的方法去解决，这个定理，就是搭起统计和概率的桥梁。Miller的三分命中率终于可以算了，让他投1000个，看他进了几个:)


  还有一个公式，也可以起到桥梁作用，那就是贝叶斯公式，P(A/B)=P(B/A)*p(A)/P(B)，这个公式太深奥，以至都创立了两大学术派，我只有用的份，不敢多作半点解释，那么这唯一半点解释就是建立正推反推的模型，我们会在后面的三维概率模型中用到它。

概率的三维空间模型：
  这是我写的概率应用的重点，重在应用举例，首先说明一点，为什么要用三维空间模型呢，是因为我考虑任何问题都爱往矩阵上靠，一想到矩阵自然而然就联想到了空间模型，如果你不接受这个观点，没关系，看看有没有空间的味道。

概率一维空间模型的应用：
  从概率点说起。空间模型里最低级的就是一个点, 那么在概率世界里，点就是一个概率值，不管概率怎么得出的，反正有个23%的概率，那么它就是一个点了，它可以代表任何东西，数或者一个事件的概率，甚至一系列的事件的概率，总之，只要你想把它看成一个封装的点，它就是点。
  有了点，自然需要线，也就是一维概率模型的内容：线。一个点到另一个点有一个概率，那么把这样的一些点连起来，就形成了一条线。A推B，B推C，C推D....，那A能不能推C呢？当然可以了，但是推了，就不是一维模型了，我们会在后面的二维模型里讲。这样依此串成串后，会发现和一个大名鼎鼎的名字能联系一起，那就是马尔可夫链，没错，这就是马尔可夫链了。
  马尔可夫链有什么用？哇塞，用处太多了，按照书上的理论，可以做个简单的聊天机器人，完全基于统计模型。利用大数定理，建立统计频率等于概率的思想，我们统计上万篇文章，按语素分词（如何按语素分词？不是我要讲的重点），例如“今吃了吗？”分成“今”和“吃了吗”两部分，然后我们发现在这上万篇文章里，”今吃了吗“后面跟的最多就是“吃了”和“没吃”，那么我们取最多的发生频率的回答随机做出回答，比如回答“没吃”。接下来，语素变成了“吃了吗”和“没吃”，然后再在上万篇里发现“吃了吗-没吃”后面跟的“没吃回家吃去吧”最多，那么我们就把这句话选成回答。呼呼，好简单，是地，这就是模型的威力，有了模型，万事不难。

  上面的例子是经典书籍的例子，我再举一个我真实解决的例子。
  研二的时候，我的上铺去给一家手机游戏公司兼职，我对做手机游戏也很有兴趣，不免时常和他探讨一下。他做的街头对打游戏，双缓冲呀切图啊这些自然不在话下，不过在测试阶段遇到一个问题，游戏里面的NPC太傻。NPC和PC有很多动作，比如跑，跳，横拳，下蹲，防，下防等等，他设计是基础是随机出招，然后会根据NPC与PC的距离调整一个好斗值，当然这个好斗值也会跟血有关，当NPC的血快没时，它会过多采用进攻动作。而在时间快结束，如果NPC发现自己的血多于PC时会降低好斗值，反之增加，而好斗值直接关系它发招的进攻招的比例。但这么设计有个很重要的弱点，当PC用些固定招术取胜时，NPC就会变得像傻子一样，比如PC跳起落下再扫堂腿，NPC就挂，结果PC反复使这招，结果NPC反复挂。如此的现象，让我不得不想起曾经的FC游戏，魂斗罗啊，赤色要素啊，我每次遇到大BOSS的时候，BOSS发子弹时，我都会躲到一个固定角落猫起来，每次都打不到我，此时多自豪自己为人类啊。
  为了影响玩家感受的自豪感，游戏NPC必须克服这个缺点，那怎么办呢？概率一维模型coming!!!
  我们为PC动作建立4元组马尔可夫链，比如对动作A,B,C,D,E建立两个四元组(A,B,C,D)和(B,C,D,E)，以此类推。在游戏中维护该一堆四元组，随着游戏的进行，就会出现一些重复项了，比如B到C到D到E的出现次数很多，也就是从B到C到D到E的概率很高，OK，我们记下，那么也会随着游戏的进程，各种各样的四元组越来越多，那么就把频率（概率）的小的删除，始终把四元组们维持在一个在手机内存里可接受的范围内，（怎么存储四元组来使存取最快，与我谈的主线无关）。哈哈，我们达到目的了，我们可以记录下游戏中NPC的一些习惯了，那么下一步呢？那就是预测呗，如前假设，B到C到D到E的概率很高，当PC再次在游戏中打出B+C+D的连招时，NPC提前可以预测出PC的下一招极有可能是E，于是就采用对E的防御招术。NPC终于智慧了，好兴奋啊，试试吧，把代码一往原程序一加，效果确实比原来好多了。
  一维概率模型是这么厉害啊!!