13066158880
当前位置:首页 / 新闻动态

通俗解释爬山法、模拟退火、遗传算法、贝叶斯算法

admin 2022-08-08 新闻动态

1爬山法

 

成本函数抽象成了一座山(想象一下一个2维坐标系,横轴为变量,纵轴为成本函数,成本函数随着横轴的递增而上下起伏绵延不绝,好似一座山),某人可在山中一任意位置左右移动(取该函数中的一点),因此,随着某人水平方向的变化(变量的变化),这哥们的海拔高度也在变化(成本函数随着变量的变化而变化)。

 

可惜,这哥们一心想去山的最底处。所以他总喜欢走下坡路,一旦发现各个方向再走都是上坡的时候,那这哥们认为他终于走到了山的最底处,他不再走了并返回此时他的位置。(该例子的成本函数仅和一个变量有关,但现实生活中,成本函数是和多个变量有关。道理也是一样,就好像这个哥们每次走路的时候有N个方向供他选择(N个变量))

 

明眼的人都能看出来,这哥们非常容易的会把局部最小值当成全局最小值。以为山的小凹谷就是整座山的最低处了(这座山绵延不绝,并不是两头连接大地的那种,是长度无限长的那种),too navie。

 

有什么办法呢?就是随机重复爬山法,让你每次初始位置都随机的多试几次。说不定还真能蒙到正确结果。

 

2模拟退火算法

 

这哥们突然变聪明了,认为有时候退一步海阔天空,我有的时候稍微走点上坡路,指不定后面会有一个大下坡等着我呢,于是这哥们开始只要上坡路不是上升的特别离谱,他都会试着去尝试一下,走走看。不过,随着时间的流逝,这哥们开始越来越不愿意走上坡路,一开始可能这是上坡路还会去尝试着走一下呢。到后来,越来越不愿意去尝试。这个愿不愿意去尝试走上坡路的心态就跟刚出炉放在空气中的铁一样,随着时间的流逝而渐渐降温,渐渐冷却,渐渐退火。

 

公式表示就是这样:,如果新的成本函数降低了,当然欣然接受一开始,不多说。但是如果新的成本函数增高了,那么就开始考虑要不要试一下要不要走,一开始的时候,温度很高,高低成本之差显得很小,除了个温度接近为0,这个P值接近为1,一般程序当中都是用一个0和1之间的随机数与P值比较,如果比P小那么就尝试,如果比P大那么不尝试。所以很明显,一开始肯定是乐意尝试的,后来随着时间的增加,温度的下降,P值越来越小接近于0。因此,更加不愿意去尝试上坡路了

 

这个方法的问题和爬山法其实差不多,每次结果可能都会不同,尝试着每次改下参数(初始温度和温度下降的速度)来试试。

 

3遗传算法

 

这时候,想象成人类吧。人类的生存环境十分的残酷,只有优秀的一拨人才能活下来(优秀的人意为成本函数小的最优解),一代一代,每代之中会有变异(对既有解进行微小的,简单的,随机的改变)也会有交叉(选取最优解中的两个解,然后将他们按照某种方式进行结合)。

 

很显然,变异和交叉会产生新的种群(会对成本函数产生或增或减的影响)。同样,这些新的种群有的能适应这个世界而存活下去,有的就消失在人类的进化长河里。正所谓物竞天择适者生存。真是残酷。

 


 4  贝叶斯法

 

250 年前,贝叶斯牧师就很重视小数据预测问题,他来自英国迷人的温泉城镇坦布里奇韦尔斯,是一位长老会的牧师。

 

贝叶斯设想,如果我们买10 张新的、不熟悉的抽奖彩票,其中有5 张中奖,那么要估计中奖概率就似乎相对容易:5/10,或50%。

 

但是,如果我们只买了一张彩票,并赢得奖品呢?

 

我们真的认为中奖的概率就是1/1,或是100%的?这似乎过于乐观,不是吗?

 

如果是这样的话,那中奖概率应该是多少?我们应该猜多少呢?

 

对于那些曾在不确定性推理历史上产生如此重大影响的人来说,贝叶斯自己的故事也具有讽刺的不确定性

 

他出生于1701年或者1702年,出生地是英国的赫特福德郡,或是伦敦。

 

1746年,或1748年,或1747年,抑或是1749年,他写了一篇在数学界最具影响力的论文,他却未将它发表,并继续做其他事情。

 

在这两个事件之间我们有了更多的把握。作为牧师的儿子,贝叶斯去爱丁堡大学学习神学,并像他父亲一样被任命为牧师。

 

他对数学和神学感兴趣,并在1736年为牛顿全新的 “微积分”理论写了一篇慷慨激昂的辩护书,以回应乔治伯克利主教对牛顿的攻击。

 

这使他在1742年当选为皇家学会的成员,并被赞誉为“擅长几何、数学和哲学学习的绅士”。

 

1761年贝叶斯去世后,他的朋友理查德·普莱斯被要求整理他的数学论文,看是否有可发布的内容。

 

一篇文章引起了他的兴趣,并令他特别兴奋——他说这篇文章“极为出色,值得保存”。

 

这篇论文就论述了本文所讨论的彩票问题:让我们想象一个人在抽奖的时候,对会不会中奖完全不知道,也不知道中奖和无奖的比例如何。

 

让我们进一步假设,他要从他之前了解到的无奖的数量来推测相对的中奖数量,并询问他在这些情况下能做出什么合理的结论。

 

贝叶斯的关键见解是,试图使用我们看到的中奖和未中奖彩票来分析彩票来源于整体彩票池的方法,本质上是在倒推。

 

他说,要做到这一点,我们需要先用假设向前推理

 

换句话说,我们首先需要确定,如果各种可能场景都成真的情况下,我们中奖的可能性有多少。

 

这个被现代统计学家称为“可能性”的概率,给了我们解决问题所需要的信息。

 

例如,假设我们买了三张彩票,三张都中奖了。现在,如果这种彩票中奖率特别高,所有彩票都能中奖,那我们的买三中三的中奖率就肯定会一直发生,在这种情况下就是100% 的概率。

 

但如果只有一半的彩票能中奖,那我们三张彩票的中奖率就是1/2×1/2×1/2, 也就是1/8。

 

如果1000 张彩票只有一张能中奖,那么我们的中奖率将是1/1000×1/1000×1/1000,也就是1×10–9

 

贝叶斯认为,因此我们应该判断如何能让所有彩票都尽可能中奖而不是一半能中奖,或者尽可能使一半的彩票中奖而不是1/1000。

 

也许我们生来便拥有这种直觉,但贝叶斯的逻辑思维却给我们提供了为这种直觉定量的方法。

 

在同等条件下,我们应该想象成所有彩票都中奖的概率比一半中奖的概率要高8 倍,因为我们在这种情况下买的彩票正好是8 倍多的中奖概率(100% 与1/8)。

 

同样的,一半的彩票中奖的概率正好是1000 张中一张中奖的1.25 亿倍,我们已经通过比较1/8 和1×10–9 而得知其中的原因。

 

这是贝叶斯论证的关键所在:从假设的过去向前推理,并奠定了理论基础,让我们可以向后找到最大的可能性

 

这是一个巧妙和创新的方法,但它对抽奖问题没能提供一个完整的答案。

 

普莱斯在向皇家学会提交贝叶斯的研究结果时,他能够确定,如果你买了一张彩票并中奖了,那么至少有一半的彩票都能中奖的概率是75%。

 

但是,考虑概率的概率问题会让人有点儿头晕。更重要的是,如果有人在催促我们:“好吧,但是你认为彩票的中奖率到底是多少?”我们仍然不知道该说什么。

 

如何将所有可能的假设提取到单一的期望值,这一问题将在短短几年后,由法国数学家皮埃尔·西蒙·拉普拉斯Pierre Simon laplace)解答。

 

  拉普拉斯定理  

 

1749年,拉普拉斯生于诺曼底,他父亲送他到一所天主教学校,并希望他成为神职人员。

 

拉普拉斯继续在卡昂大学学习神学,他不像贝叶斯那样一生都能平衡对神学和科学的奉献,因此他最终放弃了做牧师,而专攻数学。

 

1774年,在完全不知道贝叶斯以前做的工作的情况下,拉普拉斯发表了一篇雄心勃勃的论文,名为“事件原因的概率论”。

 

在这篇论文中,拉普拉斯终于解决了如何从观察到的效果向后推理并找出可能的原因这一问题。

 

如我们所见,贝叶斯找到了一种比较两种假设的相对可能性的方法。但是在彩票这一问题上,这里的假设几乎就是无穷的——每一个中奖彩票可能的比例。

 

利用微积分这一曾备受争议却受到贝叶斯坚决拥护的数学学科,拉普拉斯能够证明这个巨大范围的可能性,这可以提取成一个单一的预估值和一个非常简洁的数字。

 

他表示,如果我们提前真的不知道彩票的情况,然后当我们第一次买的三张彩票中的一张彩票中奖了,我们可以推测奖池里彩票的总中奖比例为2 / 3。

 

如果我们买三张彩票,都中奖了,那我们可以推测总中奖比例正好是4/5。

 

事实上,如果买n 张彩票共w 张中奖,那么中奖率就是中奖数加1,除以所购买的数目加2,即(w+1)/(n+2)。

 

这种令人难以置信的简单方法,估计概率的简单方法被称为拉普拉斯定律,它很容易就能适用于任何你需要通过历史事件来评估概率的情况。

 

如果你做了10 次尝试,其中有5 次成功,拉普拉斯定律估计你的整体成功概率是6/12 或50%,这符合我们的直觉。

 

如果你只试一次便取得成功,拉普拉斯给的估计是2/3,这比假设你每次都赢更合理,也比普莱斯的观点更具可操作性。(它告诉我们,50% 或更大的成功概率有75% 的元概率。)

 

拉普拉斯继续将他的统计方法应用到广泛的时间问题上,包括评估男孩和女孩的出生率是否真正平均。(他发现,男婴其实比女婴的出生率稍高。)

 

他还写了关于概率的哲学论文,可以说这是给大众读者的第一本关于概率的书,也是最好的概率书之一,此书奠定了他的理论基础并讲述了这些理论在法律、科学与日常生活上的应用。

 

拉普拉斯定律为我们在现实世界中,面对小数据时提供了第一种简单的经验法则。

 

即使我们只进行了一些或一次观察,它也都能给予我们实际指导。想知道你的车晚点的概率吗?你的垒球队会赢吗?数一数过去已经发生的数量再加一,然后除以可能的机会数再加2。

 

拉普拉斯定律的精髓就在于无论我们有一个单独的数据点,或数以百万计的数据,它都同样适用。

 

相信太阳明天会升起是有道理的,这句话告诉我们:地球已经连续看到太阳上升约1.6 万亿天,在下一次的“尝试”中看见太阳不升起来的机会,几乎没有可能。

 


推荐新闻