知识库

知识库资源

当前位置:首页>知识库
全部 14 商业 3

蒙特卡罗:丢失确定性之后,怎么办?

时间:2021-04-24   访问量:1048

欢迎来到我的《算法通识课》

上一讲,我们说到了启发式算法策略,因为搜索的空间太大,找到最优解很慢,所以我们得舍弃一点解决问题的质量,而去追求解决问题的效率。

这一讲我们要讲的算法策略,蒙特卡罗方法也有这样的特点。但解决问题的类型不一样。我们来说个例子。

故事的主人公,小文,开了一家小超市。她每天中午会提前准备好寿司和包子两种套餐。她有一个难题:没法估计自己每天该备多少货。

因为超市周围的顾客没个准,有的今天不来,有的明天不来;有的今天想吃包子,明天想吃寿司;有的见着寿司没了,转头就走,有的见着包子没了,倒也愿意用寿司来替代。

小文的难题背后隐藏的问题,就是随机性事件带来的复杂性。那些大型电商的备货方案,选品更多,但本质上和小文的难题是一样的。

我们这一讲要讲的蒙特卡罗法,就是应对这种确定性丢失了的情况的。

1 蒙特卡罗方法:对现实世界进行随机模拟

蒙特卡罗法怎么帮小文解决问题呢?

我们拆解一下这个问题。小文早上备货结束之后,就好像同时出现了好多个平行宇宙。每个平行宇宙当中,顾客的需求都不一样,小文的利润也不一样。

我们不能预先知道小文能挣多少钱。不过,我们可以计算所有平行宇宙当中,利润的平均值。这叫利润的期望。

那这样的平行宇宙有多少个呢?

咱们先随便选一个顾客,张三,来看看他的随机行为。

张三今天可能不来小文的超市,也可能来。如果来,他有可能想吃寿司,也可能想吃包子。如果他想吃寿司,有寿司那就买了,但如果寿司正好没有了,那他可能愿意用包子替换,也可能不愿意。

我算了一下,张三的行为有5种可能性,能生成5个平行宇宙。

如果我们再把李四也加进来。两个人的随机行为就可以生成25个平行宇宙。如果考虑100个顾客,那要考虑的可能性是5的100次方。太多了!准确计算利润的期望,变成了一件不可能完成的任务。

那怎么办?我们可以在所有可能的平行宇宙中,选一些做代表。

怎么选呢?比如张三的5种可能的行为,我们随机抽取一个。李四也一样。依次把所有100个顾客的行为都随机抽取一遍,我们就得到了一个“随机样本”。

对这个样本来说,所有随机性的事件都变成确定的了,所以小文的利润也可以算。

这样的样本取它个100个,咱们就可以算出小文的平均利润了。这就是蒙特卡罗方法。

蒙特卡罗方法是一种模拟算法,每个样本都代表着一次对现实的模拟。我们用有限次的模拟,来替代了所有平行宇宙的可能性。

我们一句话总结一下。蒙特卡罗方法就是对问题中的随机事件进行取样,为有限个样本进行独立计算,最后把样本结果进行统计的策略。

2 蒙特卡罗适用的问题

那是不是说,但凡有随机性的问题,我们都用蒙特卡罗方法来解决呢?

不一定。蒙特卡罗法是可能性太多,我们计算不了的时候用的。如果需要考虑的可能性很少,那直接计算就可以了。

比如说两支足球队,北京国安和广州恒大,他们之间要打两场比赛。我们知道比赛的积分规则,也知道每个队伍打一场获胜的概率,那要估计北京国安两场比赛之后的分数,你可以简单分情况讨论,直接计算就可以。这就是道简单的数学题。

但假如中超联赛中的16支球队都来了,又有分组双循环积分赛,又有多轮淘汰赛,一共要进行160场比赛,请问以国安队的实力,最后最可能的联赛排名是多少呢?

这咱就算不出来了,但蒙特卡罗方法用在这里再合适不过。

我们可以把160场比赛,按照事先规定好的概率,随机生成结果,得到一个样本,看看国安队在这个样本里排名第几。然后依葫芦画瓢,生成许多其他的样本。最后,计算北京国安在这些随机抽取的样本中的平均排名。

听起来思路并不复杂,但蒙特卡罗能解决一些非常重要的问题。我来说一个真实的例子。

第二次世界大战当中,美国原子弹的研制就第一次用到了蒙特卡罗方法。

原子弹的爆炸依赖于裂变时产生的链式反应。在链式反应中,核物质中游离的中子会撞击铀原子,释放出大量的能量,同时释放出来三个新的中子。这些中子如果又能撞击其他铀原子,链式反应就会发生。这样原子弹就能爆炸了。

但释放出来的中子是不是能撞击到其他铀原子,是一个不确定的过程。

这些中子运动的方向,携带的能量都是随机的。如果整个核物质的质量太小,很有可能中子被释放出来之后,直接离开了核物质,没撞击到任何铀原子,那链式反应就不会发生,原子弹就爆炸不了。

在核物理中有一个概念,叫“临界质量”,是让链式反应能够发生的最小质量。而这个临界质量,就是对各个中子运动中的随机变量进行取样,通过蒙特卡罗模拟算法计算得到的。

3 使用蒙特卡罗的注意事项

蒙特卡罗方法是算法工程师在解决问题时常用的算法策略。知道它做不到什么,哪里更容易出问题,能帮我们更好地利用它。所以在最后,我们还要跟你说说在使用它的时候,几个非常值得注意的地方。

第一,蒙特卡罗方法是对问题的估算,而不是精确计算。

比如说国安队在联赛中的最终排名,你只进行了一次模拟,发现北京国安得了第四名。这能代表国安队最可能得到的名次吗?

不能。这只能说明国安可能分数比较靠前。从第一到第七,这个区间中的任何名次都有可能。

要想把这个区间缩小,我们就得多模拟,多取样。也许模拟10次之后,这个区间就缩小到第一名到第五名。模拟100次,这个区间变成第二名到第四名。但这样就需要很多很多次模拟,计算量变大,效率就降低了。

对国安队名次的预测精确性差点不是什么问题。但如果我们预测的是核弹的爆炸,飓风运行的轨迹,对最后结果精确度的要求就会很高。这就是为什么算法学家会费很多力气去研究更聪明的方法,用尽量少的样本来获得尽量高的精确度。

第二,蒙特卡罗方法的成功,非常依赖参数和模型的正确。

还拿国安队的名次来举例。我们相信蒙特卡罗方法的结果,需要我们正确估计,或者至少大致正确估计每两支队伍比赛的胜负概率。

好比说,我是北京国安的狂热球迷,认为国安打哪支球队的胜率都是90%。结果其他球队这一年都引入了特厉害的外援,实力大增。不对这些信息进行考虑,修正国安90%的胜率,那随机模拟的结果就是不可信的。模拟次数再多,也没用。

这还有个真实的例子。

2016年美国总统大选之前,各个机构都不断对大选结果进行预测。很多这样的预测都是基于蒙特卡罗方法的。开票之前,几乎所有的机构都预测希拉里会以接近100%的概率获胜。没想到,特朗普最终当上了总统。

之所以预测出错,就是因为模拟的参数错了。

哪个候选人能获选,是他们在每个州的胜负情况加权得到的,就像要打很多场积分不同的比赛一样。而这些预测机构,把那些重点摇摆州的胜负概率估算错了,所以导致最后的预测结果也错了。

第三,蒙特卡罗方法,会减小我们发现问题本质的机会。

什么意思呢?比如小文用蒙特卡罗方法,算出了准备50份寿司和50份包子带来的利润。但这两个数到底是多少,她的利润能最大呢?

蒙特卡罗方法不能直接告诉她。小文只能改变一下这两个数字,对每个组合都使用蒙特卡罗模拟来计算收益,看看什么组合能让收益最大。

这样做可以吗?可以,但这样我们就放弃了对问题本质的认识。

小文遇到的问题本质,是对多备货带来的浪费成本和少备货带来的顾客流失成本之间的平衡。

比如她意识到,包子的利润率低,那可以少备货,比顾客平均需求低也不太影响收入;寿司利润率高,就多备货,尽可能地保证顾客的需求。这是能让利润最大化的关键认识。

这样的认识,可能已经足够为小文提供一个好的解决方案了,并不需要蒙特卡罗方法。如果什么问题都用它解决,小文就对备货问题就不会有更深入的认识。

 划重点

1 对问题中的随机事件进行取样,为有限个样本进行独立计算,最后把每个样本结果进行统计的策略叫蒙特卡罗方法。

2 蒙特卡罗方法最适用于随机变量多,计算逻辑复杂的问题。

3 随机模拟不是万能的。它会占用大量计算资源,依赖于参数的正确性,并且对揭示问题本质没有太大帮助。

最后,给你留一道思考题。你生活中有没有遇到哪个问题,觉得应该用随机模拟的方法去解决呢?请在留言区,分享你的思考。

到这里,我们讲算法策略的模块就结束了。下一讲,我们来看看算法领域最前沿的部分,机器学习。


上一篇:启发式:放弃最优解之后,怎么办?

下一篇:机器学习:机器到底在学什么?

发表评论:

评论记录:

未查询到任何数据!
点击这里给我发消息

在线咨询

咨询专员 点击这里给我发消息

点击这里给我发消息 售后服务专员

在线咨询

免费通话

24小时免费咨询

请输入您的联系电话,座机请加区号

免费通话

微信扫一扫

微信联系
返回顶部