精华内容
下载资源
问答
  • 大数据背后的神秘公式:贝叶斯公式

    万次阅读 多人点赞 2016-07-29 08:56:08
    答案是,它们都会用到同一个数学公式——贝叶斯公式。它虽然看起来很简单、很不起眼,但却有着深刻的内涵。那么贝叶斯公式是如何从默默无闻到现在广泛应用、无所不能的呢?一 什么是贝叶斯公式18世纪英国业余数学家...

    大数据、人工智能、海难搜救、生物医学、邮件过滤,这些看起来彼此不相关的领域之间有什么联系?答案是,它们都会用到同一个数学公式——贝叶斯公式。它虽然看起来很简单、很不起眼,但却有着深刻的内涵。那么贝叶斯公式是如何从默默无闻到现在广泛应用、无所不能的呢?

    一 什么是贝叶斯公式

    18世纪英国业余数学家托马斯·贝叶斯(Thomas Bayes,1702~1761)提出过一种看上去似乎显而易见的观点:“用客观的新信息更新我们最初关于某个事物的信念后,我们就会得到一个新的、改进了的信念。” 这个研究成果,因为简单而显得平淡无奇,直到他死后的两年才于1763年由他的朋友理查德·普莱斯帮助发表。它的数学原理很容易理解,简单说就是,如果你看到一个人总是做一些好事,则会推断那个人多半会是一个好人。这就是说,当你不能准确知悉一个事物的本质时,你可以依靠与事物特定本质相关的事件出现的多少去判断其本质属性的概率。用数学语言表达就是:支持某项属性的事件发生得愈多,则该属性成立的可能性就愈大。与其他统计学方法不同,贝叶斯方法建立在主观判断的基础上,你可以先估计一个值,然后根据客观事实不断修正。

    1774年,法国数学家皮埃尔-西蒙·拉普拉斯(Pierre-Simon Laplace,1749-1827)独立地再次发现了贝叶斯公式。拉普拉斯关心的问题是:当存在着大量数据,但数据又可能有各种各样的错误和遗漏的时候,我们如何才能从中找到真实的规律。拉普拉斯研究了男孩和女孩的生育比例。有人观察到,似乎男孩的出生数量比女孩更高。这一假说到底成立不成立呢?拉普拉斯不断地搜集新增的出生记录,并用之推断原有的概率是否准确。每一个新的记录都减少了不确定性的范围。拉普拉斯给出了我们现在所用的贝叶斯公式的表达:

    P(A/B)=P(B/A)*P(A)/P(B),

    该公式表示在B事件发生的条件下A事件发生的条件概率,等于A事件发生条件下B事件发生的条件概率乘以A事件的概率,再除以B事件发生的概率。公式中,P(A)也叫做先验概率,P(A/B)叫做后验概率。严格地讲,贝叶斯公式至少应被称为“贝叶斯-拉普拉斯公式”。

    二 默默无闻200年

    贝叶斯公式现在已经非常流行,甚至在热门美剧《生活大爆炸》中谢耳朵也秀了一下。但它真正得到重视和广泛应用却是最近二三十年的事,其间被埋没了200多年。这是为什么呢?原因在于我们有另外一种数学工具——经典统计学,或者叫频率主义统计学(我们在学校学的主要是这种统计学),它在200多年的时间里一直表现不错。从理论上讲,它可以揭示一切现象产生的原因,既不需要构建模型,也不需要默认条件,只要进行足够多次的测量,隐藏在数据背后的原因就会自动揭开面纱。

    在经典统计学看来,科学是关于客观事实的研究,我们只要反复观察一个可重复的现象,直到积累了足够多的数据,就能从中推断出有意义的规律。而贝叶斯方法却要求科学家像算命先生一样,从主观猜测出发,这显然不符合科学精神。就连拉普拉斯后来也放弃了贝叶斯方法这一思路,转向经典统计学。因为他发现,如果数据量足够大,人们完全可以通过直接研究这些样本来推断总体的规律。

    打个比方来帮助我们理解这两种统计学方法的区别。假如我们想知道某个区域里海拔最低的地方,经典统计学的方法是首先进行观测,取得区域内不同地方的海拔数据,然后从中找出最低点。这个数据量必须足够多,以反映区域内地形全貌的特征,这样我们才能相信找到的就是实际上的最低点。而贝叶斯方法是我不管哪里最低,就凭感觉在区域内随便选个地方开始走,每一步都往下走,虽然中间可能有一些曲折,但相信这样走早晚能够到达最低点。可以看出,贝叶斯方法的关键问题是这个最终到达的低点可能不是真正的最低点,而是某个相对低点,它可能对该区域的地形(碗型、马鞍形等)和最初我们主观选择的出发点有依赖性。如果问题域是碗型的,我们到达的就是最低点;但如果是马鞍形或者其他复杂曲面,那么我们到达的可能是多个相对低点(极点)中的一个,而不是真正的最低点。这是贝叶斯方法最受经典统计学方法诟病的原因,也是它在过去的200多年被雪藏的原因所在。

    贝叶斯方法原理示意图:
    这里写图片描述

    三 初显威力

    长期以来,贝叶斯方法虽然没有得到主流学界的认可,但其实我们经常会不自觉地应用它来进行决策,而且还非常有效。比如炮兵在射击时会使用贝叶斯方法进行瞄准。炮弹与子弹不同,它的飞行轨迹是抛物线,瞄准的难度更大,因此他们会先根据计算和经验把炮管调整到一个可能命中的瞄准角度(先验概率),然后再根据炮弹的实际落点进行调整(后验概率),这样在经过2-3次射击和调整后炮弹就能够命中目标了。

    在日常生活中,我们也常使用贝叶斯方法进行决策。比如在一个陌生的地方找餐馆吃饭,因为之前不了解哪家餐馆好,似乎只能随机选择,但实际上并非如此,我们会根据贝叶斯方法,利用以往积累的经验来提供判断的线索。经验告诉我们,通常那些坐满了客人的餐馆的食物要更美味些,而那些客人寥寥的餐馆,食物可能不怎么样而且可能会被宰。这样,我们就往往通过观察餐厅的上座率来选择餐馆就餐。这就是我们根据先验知识进行的主观判断。在吃过以后我们对这个餐馆有了更多实际的了解,以后再选择时就更加容易了。所以说,在我们认识事物不全面的情况下,贝叶斯方法是一种很好的利用经验帮助作出更合理判断的方法。

    而两个标志性的事件在让学术界开始重视贝叶斯方法上起到了重要作用。

    1.联邦党人文集作者公案

    1787年5月,美国各州(当时为13个)代表在费城召开制宪会议;1787年9月,美国的宪法草案被分发到各州进行讨论。一批反对派以“反联邦主义者”为笔名,发表了大量文章对该草案提出批评。宪法起草人之一亚历山大·汉密尔顿着急了,他找到曾任外交国务秘书(即后来的国务卿)的约翰·杰伊,以及纽约市国会议员麦迪逊,一同以普布利乌斯(Publius)的笔名发表文章,向公众解释为什么美国需要一部宪法。他们走笔如飞,通常在一周之内就会发表3-4篇新的评论。1788年,他们所写的85篇文章结集出版,这就是美国历史上著名的《联邦党人文集》。

    《联邦党人文集》出版的时候,汉密尔顿坚持匿名发表,于是,这些文章到底出自谁人之手,成了一桩公案。1810年,汉密尔顿接受了一个政敌的决斗挑战,但出于基督徒的宗教信仰,他决意不向对方开枪。在决斗之前数日,汉密尔顿自知时日不多,他列出了一份《联邦党人文集》的作者名单。1818年,麦迪逊又提出了另一份作者名单。这两份名单并不一致。在85篇文章中,有73篇文章的作者身份较为明确,其余12篇存在争议。

    1955年,哈佛大学统计学教授Fredrick Mosteller找到芝加哥大学的年轻统计学家David Wallance,建议他跟自己一起做一个小课题,他想用统计学的方法,鉴定出《联邦党人文集》的作者身份。

    但这根本就不是一个小课题。汉密尔顿和麦迪逊都是文章高手,他们的文风非常接近。从已经确定作者身份的那部分文本来看,汉密尔顿写了9.4万字,麦迪逊写了11.4万字。汉密尔顿每个句子的平均长度是34.55字,而麦迪逊是34.59字。就写作风格而论,汉密尔顿和麦迪逊简直就是一对双胞胎。汉密尔顿和麦迪逊写这些文章,用了大约一年的时间,而Mosteller和Wallance甄别出作者的身份花了10多年的时间。

    如何分辨两人写作风格的细微差别,并据此判断每篇文章的作者就是问题的关键。他们所采用的方法就是以贝叶斯公式为核心的包含两个类别的分类算法。先挑选一些能够反映作者写作风格的词汇,在已经确定了作者的文本中,对这些特征词汇的出现频率进行统计,然后再统计这些词汇在那些不确定作者的文本中的出现频率,从而根据词频的差别推断其作者归属。这其实和我们现在使用的垃圾邮件过滤器的原理是一样的。

    他们是在没有计算机帮助的条件下用手工处理“大数据”,这一工程的耗时耗力是可想而知的。将近100个哈佛大学的学生帮助他们处理数据。学生们用最原始的方式,用打字机把《联邦党人文集》的文本打出来,然后把每个单词剪下来,按照字母表的顺序,把这些单词分门别类地汇集在一起。有个学生干得累了,伸了个懒腰,长长地呼了一口气。他这一口气用力太猛,一下子把刚刚归置好的单词条吹得如柳絮纷飞,一屋子学生瞬间石化,估计很多人连灭了他的心都有。而这只是手工大数据时代的日常。

    Mosteller和Wallance这是要在干草垛里找绣花针。他们首先剔除掉用不上的词汇。比如,《联邦党人文集》里经常谈到“战争”、“立法权”、“行政权”等,这些词汇是因主题而出现,并不反映不同作者的写作风格。只有像“in”,“an”,“of”,“upon”这些介词、连词等才能显示出作者风格的微妙差异。一位历史学家好心地告诉他们,有一篇1916年的论文提到,汉密尔顿总是用“while”,而麦迪逊则总是用“whilst”。但仅仅有这一个线索是不够的。“while”和“whilst”在这12篇作者身份待定的文章里出现的次数不够多。况且,汉密尔顿和麦迪逊有时候会合写一篇文章,也保不齐他们会互相改文章,要是汉密尔顿把麦迪逊的“whilst”都改成了“while”呢?

    当学生们把每个单词的小纸条归类、粘好之后,他们发现,汉密尔顿的文章里平均每一页纸会出现两次“upon”,而麦迪逊几乎一次也不用。汉密尔顿更喜欢用“enough”,麦迪逊则很少用。其它一些有用的词汇包括:“there”、“on”等等。1964年,Mosteller和Wallance发表了他们的研究成果。他们的结论是,这12篇文章的作者很可能都是麦迪逊。他们最拿不准的是第55篇,麦迪逊是作者的概率是240:1。

    这个研究引起了极大的轰动,但最受震撼的不是宪法研究者,而是统计学家。Mosteller和Wallance的研究,把贝叶斯公式这个被统计学界禁锢了200年的幽灵从瓶子中释放了出来。

    2.天蝎号核潜艇搜救

    2014年初马航MH370航班失联,所有人都密切关注搜救的进展情况。那么我们是用什么方法在茫茫大海中寻找失联的飞机或者船只的呢?这要从天蝎号核潜艇说起。

    1968年5月,美国海军的天蝎号核潜艇在大西洋亚速海海域突然失踪,潜艇和艇上的99名海军官兵全部杳无音信。按照事后调查报告的说法,罪魁祸首是这艘潜艇上的一枚奇怪的鱼雷,发射出去后竟然敌我不分,扭头射向自己,让潜艇中弹爆炸。

    为了寻找天蝎号的位置,美国政府从国内调集了包括多位专家的搜索部队前往现场,其中包括一位名叫John Craven的数学家,他的头衔是“美国海军特别计划部首席科学家”。在搜寻潜艇的问题上,Craven提出的方案使用了上面提到的贝叶斯公式。他召集了数学家、潜艇专家、海事搜救等各个领域的专家。每个专家都有自己擅长的领域,但并非通才,没有专家能准确估计到在出事前后潜艇到底发生了什么。有趣的是,Craven并不是按照惯常的思路要求团队成员互相协商寻求一个共识,而是让各位专家编写了各种可能的“剧本”,让他们按照自己的知识和经验对于情况会向哪一个方向发展进行猜测,并评估每种情境出现的可能性。据说,为了给枯燥的工作增加一些趣味,Craven还准备了威士忌酒作为“投注”正确的奖品。

    因为在Craven的方案中,结果很多是这些专家以猜测、投票甚至可以说赌博的形式得到的,不可能保证所有结果的准确性,他的这一做法受到了很多同行的质疑。可是因为搜索潜艇的任务紧迫,没有时间进行精确的实验、建立完整可靠的理论,Craven的办法不失为一个可行的办法。

    由于失事时潜艇航行的速度快慢、行驶方向、爆炸冲击力的大小、爆炸时潜艇方向舵的指向都是未知量,即使知道潜艇在哪里爆炸,也很难确定潜艇残骸最后被海水冲到哪里。Craven粗略估计了一下,半径20英里的圆圈内的数千英尺深的海底,都是天蝎号核潜艇可能沉睡的地方,要在这么大的范围,这么深的海底找到潜艇几乎成了不可能完成的任务。
    这里写图片描述

    贝叶斯Craven把各位专家的意见综合到一起,得到了一张20英里海域的概率图。整个海域被划分成了很多个小格子,每个小格子有两个概率值p和q,p是潜艇躺在这个格子里的概率,q是如果潜艇在这个格子里,它被搜索到的概率。按照经验,第二个概率值主要跟海域的水深有关,在深海区域搜索失事潜艇的“漏网”可能性会更大。如果一个格子被搜索后,没有发现潜艇的踪迹,那么按照贝叶斯公式,这个格子潜艇存在的概率就会降低:

    这里写图片描述
    格子潜艇存在的概率由于所有格子概率的总和是1,这时其他格子潜艇存在的概率值就会上升:
    这里写图片描述

    格子潜艇存在的概率每次寻找时,先挑选整个区域内潜艇存在概率值最高的一个格子进行搜索,如果没有发现,概率分布图会被“洗牌”一次,搜寻船只就会驶向新的“最可疑格子”进行搜索,这样一直下去,直到找到天蝎号为止。

    最初开始搜救时,海军人员对Craven和其团队的建议嗤之以鼻,他们凭经验估计潜艇是在爆炸点的东侧海底。但几个月的搜索一无所获,他们才不得不听从了Craven的建议,按照概率图在爆炸点的西侧寻找。经过几次搜索,潜艇果然在爆炸点西南方的海底被找到了。

    由于这种基于贝叶斯公式的方法在后来多次搜救实践中被成功应用,现在已经成为海难空难搜救的通行做法。

    2009年法航空难搜救的后验概率分布图:
    这里写图片描述

    2009年法航空难搜救的后验概率分布图2014马航MH370失联搜索区域:
    这里写图片描述

    2014马航MH370失联搜索区域与计算机的结合使贝叶斯公式巨大的实用价值进一步体现出来,它不但为我们提供了一条全新的问题解决路径,带来工具和理念的革命,而且甚至可能是人类大脑本身的认知和构建方式。

    贝叶斯公式在联邦党人文集作者公案和天蝎号核潜艇搜救中大显身手后(详见大数据背后的神秘公式(上):贝叶斯公式),开始引起学术界的注意和重视,而其上世纪八十年代在自然语言处理领域的成功,向我们展示了一条全新的问题解决路径。计算能力的不断提高和大数据的出现使它的威力日益显现,一场轰轰烈烈的“贝叶斯革命”正在发生。

    一 真正的突破

    自然语言处理就是让计算机代替人来翻译语言、识别语音、认识文字和进行海量文献的自动检索。但是人类的语言可以说是信息里最复杂最动态的一部分。人们最初想到的方法是语言学方法,让计算机学习人类的语法、分析语句等等。尤其是在乔姆斯基(有史以来最伟大的语言学家)提出 “形式语言” 以后,人们更坚定了利用语法规则的办法进行文字处理的信念。遗憾的是,几十年过去了,在计算机语言处理领域,基于这个语法规则的方法几乎毫无突破。

    其实早在几十年前,数学家兼信息论的祖师爷香农 (Claude Shannon)就提出了用数学方法处理自然语言的想法。遗憾的是当时的计算机根本无法满足大量信息处理的需要,所以他的这一想法并没有引起重视。

    率先成功利用数学方法解决自然语言处理问题的是语音和语言处理大师贾里尼克 (Fred J他引入一个全新的视角,认为语音识别就是根据接收到的一个信号序列推测说话人实际发出的信号序列(说的话)和要表达的意思。这就把语音识别问题转化为一个通信问题,而且进一步可以简化为用贝叶斯公式处理的数学问题。

    一般情况下,一个句子中的每个字符都跟它前面的所有字符相关,这样公式中的条件概率计算就非常复杂,难以实现。为了简化问题,他做了两个假设:

    1、 说话人说的句子是一个马尔科夫链,也就是说,句子中的每个字符都只由它前一个字符决定;

    2、 独立输入假设,就是每个接受的字符信号只由对应的发送字符决定。

    这样的简化看起来有点简单粗暴,每个字符在语义上都是和文章的其他部分相关的,怎么可能只跟它前一个字符相关呢?很多人不相信用这么简单的数学模型能解决复杂的语音识别、机器翻译等问题。其实不光是一般人,就连很多语言学家都曾质疑过这种方法的有效性。但事实证明,这个基于贝叶斯公式的统计语言模型比任何当时已知的借助某种规则的解决方法都有效。贾里尼克和贝克夫妇在七十年代分别独立提出用这个模型进行语音识别,八十年代微软公司用这个模型成功开发出第一个大词汇量连续语音识别系统。现在我们手机上的语音识别和语音输入功能都已经非常成熟而且好用了。

    更加可贵的是,这种语音识别系统不但能够识别静态的词库,而且对词汇的动态变化具有很好的适应性,即使是新出现的词汇,只要这个词已经被大家高频使用,用于训练的数据量足够多,系统就能正确地识别。这反映出贝叶斯公式对现实变化的高度敏感,对增量信息有非常好的适应能力。

    自然语言处理方面的成功开辟了一条全新的问题解决路径:

    1、原来看起来非常复杂的问题可以用贝叶斯公式转化为简单的数学问题;

    2、可以把贝叶斯公式和马尔科夫链结合以简化问题,使计算机能够方便求解;虽然我们不完全了解为什么这种看似粗暴的简化并不影响我们的研究过程,但从实践看来它非常有效;

    3、将大量观测数据输入模型进行迭代——也就是对模型进行训练,我们就可以得到希望的结果。

    随着计算能力的不断提高、大数据技术的发展,原来手工条件下看起来不可思议的进行模型训练的巨大工作量变得很容易实现,它们使贝叶斯公式巨大的实用价值体现出来。

    二 经典统计学的困难和贝叶斯革命

    1 经典统计学的困难

    当贝叶斯方法在实际应用中不断证明自己的同时,经典统计学却遇到了困境。经典统计学比较适合于解决小型的问题,同时该方法要求我们获得足够多的样本数据,而且要求这些样本能够代表数据的整体特征。在处理涉及几个参数的问题时,它可以得心应手。但如果相对于问题的复杂程度,我们只掌握少量的信息时,经典统计学就显得力不从心了,原因就是数据的稀疏性问题。

    都大数据时代了,还存在数据稀疏性问题吗?答案是肯定的。具体来说,一个取决于n个参数,并且每个参数只有两种表现(0或者1)的系统,共有2的n次方种现象。如果某类癌症的产生过程中有100个基因参与(这其实很保守了,人类总共有几万个基因),那么它有2的100次方种可能的基因图谱;根据采样定理进行估算,采用经典统计学方法至少需要获得1%-10%的样本才能确定其病因,也就是需要制作出数万亿亿亿个患有该疾病的病人的基因图谱!这不具备可操作性。所以用经典统计学方法无法解释由相互联系、错综复杂的原因(相关参数)所导致的现象。

    2 贝叶斯网络带来工具革命
    而目前的情况是,相对简单的问题已经解决得差不多了,剩下的都非常复杂。龙卷风的形成、星系的起源、致病基因、大脑的运作机制等,要揭示隐藏在这些问题背后的规律,就必须理解它们的成因网络,把错综复杂的事件梳理清楚。由于经典统计学失效,科学家别无选择,他们必须从众多可能奏效的法则中选择一些可以信任的,并以此为基础建立理论模型。为了能做出这样的选择,为了能在众多可能性中确定他们认为最为匹配的,过去,科学家多少是依靠直觉来弥补数据上的缺失和空白。而贝叶斯公式正好以严谨的数学形式帮他们实现了这一点。科学家把所有假设与已有知识、观测数据一起代入贝叶斯公式,就能得到明确的概率值。而要破译某种现象的成因网络,只需将公式本身也结成网络,即贝叶斯网络,它是贝叶斯公式和图论结合的产物。

    网络化想法的提出也不是一帆风顺的。直到上世纪80年代,美国数学家朱迪亚·珀尔才证明,使用贝叶斯网络应该可以揭示复杂现象背后的成因。操作原理是这样的:如果我们不清楚一个现象的成因,首先根据我们认为最有可能的原因来建立一个模型;然后把每个可能的原因作为网络中的节点连接起来,根据已有的知识、我们的预判或者专家意见给每个连接分配一个概率值。接下来只需要向这个模型代入观测数据,通过网络节点间的贝叶斯公式重新计算出概率值。为每个新数据、每个连接重复这种计算,直到形成一个网络图,任意两个原因之间的连接都得到精确的概率值为止,就大功告成了。即使实验数据存在空白或者充斥噪声和干扰信息,不懈追寻各种现象发生原因的贝叶斯网络依然能够构建出各种复杂现象的模型。贝叶斯公式的价值在于,当观测数据不充分时,它可以将专家意见和原始数据进行综合,以弥补测量中的不足。我们的认知缺陷越大,贝叶斯公式的价值就越大。
    这里写图片描述

    心血管疾病成因的贝叶斯网络

    和前面提到的马尔可夫链类似,我们可以假设贝叶斯网络中每个节点的状态值取决于其前面的有限个状态。不同的是,贝叶斯网络比马尔可夫链灵活,它不受马尔可夫链的链状结构的约束,因此可以更准确地描述事件之间的相关性。可以说,马尔可夫链是贝叶斯网络的特例,而贝叶斯网络是马尔可夫链的推广,它给复杂问题提供了一个普适性的解决框架。

    为了确定各个节点之间的相关性,需要用已知数据对贝叶斯网络进行迭代和训练。由于网络结构比较复杂,理论上,用现有的计算机是不可计算的(基于冯·诺依曼结构的计算机无法解决这种NP复杂度的问题,NP(Non-deterministic Polynomial)指用非确定机在多项式时间内可以解决的问题类)。但对于一些具体的应用,可以根据实际情况对网络结构(采用网络拓扑的图同构技术)和训练过程进行简化,使它在计算上可行。如果量子计算机开发成功,将能够完全解决其计算问题。这样,贝叶斯公式为科学家开辟的新路就完全打通了。

    今天一场轰轰烈烈的“贝叶斯革命”正在发生:生物学家用贝叶斯公式研究基因的致病机制;基金经理用贝叶斯公式找到投资策略;互联网公司用贝叶斯公式改进搜索功能,帮助用户过滤垃圾邮件;大数据、人工智能和自然语言处理中都大量用到贝叶斯公式。既然在手工时代,我们无法预测到今天贝叶斯公式与计算机结合的威力,那么我们怎么能忽视贝叶斯网络与量子计算机结合可能蕴藏的巨大潜力呢?

    3 人类大脑的构建方式?

    贝叶斯公式不仅在自然科学领域掀起革命,它的应用范围也延伸到了关于人类行为和人类大脑活动的研究领域。教育学家突然意识到,学生的学习过程其实就是贝叶斯公式的运用;心理学家证明贝叶斯方法是儿童运用的唯一思考方法,其他方法他们似乎完全不会。进一步,心理学研究的成果使科学家思考人类的大脑结构是否就是一个贝叶斯网络。这个公式不仅是研究人类思维的工具,它可能就是大脑本身的构建方式。这个观点十分大胆,但获得越来越广泛的认可。因为贝叶斯公式是我们在没有充分或准确信息时最优的推理结构,为了提高生存效率,进化会向这个模式演进。贝叶斯公式突然渗透到一切科学领域,提供了通用的研究框架,这是十分罕见的事情。

    人工智能近年来取得了长足的进步,但目前的人工智能通常需要从大量的数据中进行学习,而人类具有“仅从少量案例就形成概念”的能力,两者之间存在巨大差距。比如,尽管你这辈子只见过一个菠萝,但你一眼就能看出菠萝的特征,很快就能从一堆水果中认出菠萝来,甚至还能在纸上画出菠萝的简笔画,而目前的人工智能算法得看成千上万张菠萝的图片才能做到。

    不过,这种情况或许已经开始改变了。2015年底,一篇人工智能论文登上了《 科学 》杂志的封面,为人们带来了人工智能领域的一个重大突破: 三名分别来自麻省理工学院、纽约大学和多伦多大学的研究者开发了一个“只看一眼就会写字”的计算机系统。只需向这个系统展示一个来自陌生文字系统的字符,它就能很快学到精髓,像人一样写出来,甚至还能写出其他类似的文字——更有甚者,它还通过了图灵测试,我们很难区分下图中的字符是人类还是机器的作品。这个系统采用的方法就是贝叶斯程序学习(Bayesian Program Learning)——一种基于贝叶斯公式的方法。这不但是人工智能领域的重大突破,而且为我们认识人脑的学习机制提供了重要参考。
    这里写图片描述

    三 理念的革命

    这不仅仅是一场科学的革命,同样也是一场理念的革命。当科学不断强调其对世界认识的客观性时,贝叶斯公式却融入了主观性因素:它并不向我们表述世界,而是表述我们所掌握的知识和经验。这些带有观察者个人因素的知识是脱离研究现象本身的;而它在向我们描述外部现实世界的同时,也描述了观察者对现实的认知的缺陷。更重要的,它迫使我们认识到,科学理论和科学模型反映的是现实的心理意象,而不是现实本身。而现实为我们提供数据,以保证对现实的意象不会离现实本身太远。在寻找各种现象原因的同时,它也在规范着我们的思想。

    四 贝叶斯公式这么牛,与我何干?

    我们经常需要在信息不充分或者不准确的情况下进行判断和决策,一条街上哪个饭馆最靠谱?在自习室惊鸿一瞥的女神有没有男朋友?老公的公文包里发现一只口红,他有没有出轨?新开发的App应该等做得尽善尽美再发布,还是应该尽早发布,用互联网的力量帮助它完善?我应该选择哪个工作offer或者还是考公务员才能使自己的收益最大化?

    贝叶斯公式为我们提供了一些决策原则:

    •平时注意观察和思考,建立自己的思维框架,这样在面临选择时就容易形成一个接近实际情况的先验概率,这样经过少量的试错和纠错的迭代循环就可能得到理想的结果;在经过很多次选择和实践的历练后就能够形成自己的直觉,在面对陌生情况时,根据自己的经验和少量信息就能够快速地做出比较准确的判断。

    •大数据时代获得信息的成本越来越低,社会也变得更加开放和包容,初始状态(先验概率)的重要性下降了,即使最初选择不理想,只要根据新情况不断进行调整,仍然可以取得成功。所以如果当下觉得很难做出选择,那就倾听内心的声音,让直觉来选择,这有利于治疗选择恐惧症。

    以开发App的例子来说,先按照自己的想法弄个可用的原型出来,然后充分利用互联网的力量,让活跃的用户社区帮助它快速迭代,逐渐使它的功能和体验越来越好。

    •对新鲜事物保持开放的心态,愿意根据新信息对自己的策略和行为进行调整。

    “大胆假设,小心求证”,“不断试错,快速迭代”,这些都可以看成贝叶斯公式的不同表述。英国哲学家以赛亚·伯林(Isaish Berlin)曾经援引古希腊诗人的断简残片“狐狸多知而刺猬有一大知”,将人的策略分为狐狸和刺猬两类。刺猬用一个宏大的概念解释所有现象,而狐狸知道很多事情,用多元化的视角看待问题,它也愿意包容新的证据以使得自己的模型与之相适应。在这个快速变化的时代,固守一个不变的信条的刺猬很难适应环境的变化,而使用贝叶斯公式的灵活的狐狸才更容易生存。

    参考文献

    [1] 《新发现》杂志2013年2月:解密世界的方程式

    [2] 吴军:《数学之美》

    [3] 何帆:《先放一把火》

    [4] 科学松鼠会:死理性派是怎么判断漂亮女孩是不是单身的?

    [5] 统计之都创作小组:失联搜救中的统计数据分析

    [6] 机器之心:《科学》封面重磅论文:人工智能终于能像人类一样学习

    展开全文
  • 线程池最优大小计算公式

    千次阅读 2020-03-16 22:37:53
    线程数量=cpu的数量*cpu期望利用*(1 + 任务等待时间/任务处理时间)。 比如一个8核CPU,希望这部分工作的CPU使用20%,任务等待时间允许200ms,每个任务执行10ms。 那么线程数量=8*0.2*(1+200/10)= 33 ...

    java并发编程实战中提到一个计算线程池最优大小的公式


    线程数量=cpu的数量*cpu期望利用率*(1 + wait time / service time)。

    wait time 等待io完成时间

    service time CPU忙处理任务的时间(不包含阻塞等待的时间),例如 处理io返回完成时间 

    wait time / service time 称为阻塞系数,对于CPU密集型任务 阻塞系数为0,cpu核的数量就是线程数,拥有更多的线程数也是用处不大的。


    比如一个8核CPU,希望这部分工作的CPU使用率20%,任务等待io完成50ms,任务执行io返回5ms。
    那么线程数量=8*0.2*(1+50/5)=16

    展开全文
  • BP神经网络公式推导及实现(MNIST)

    万次阅读 热门讨论 2015-12-26 11:32:40
    BP神经网络公式推导及实现(MNIST)

    BP神经网络的基础介绍见:http://blog.csdn.net/fengbingchun/article/details/50274471,这里主要以公式推导为主。

    BP神经网络又称为误差反向传播网络,其结构如下图。这种网络实质是一种前向无反馈网络,具有结构清晰、易实现、计算功能强大等特点。

     

    BP神经网络有一个输入层,一个输出层,一个或多个隐含层。每一层上包含了若干个节点,每个节点代表一个神经元,同一层上各节点之间无任何耦合连接关系,层间各神经元之间实现全连接,即后一层(如输入层)的每一个神经元与前一层(如隐含层)的每一个神经元实现全连接。网络按照监督学习的方式学习,当信息被输入网络后神经元受到刺激,激活值从输入层依次经过各隐含层节点,最后在输出层的各节点获得网络的输入响应。

    BP神经网络的基本思想:BP神经网络的学习采用误差反向传播算法,BP算法是一种有监督的学习方法,其主要思想是把整个学习过程分为正向传播、反向(逆向)传播和记忆训练三个部分。正向传播时,输入样本从输入层输入,经各隐含层处理后传向输出层,每一层神经元的状态只影响下一层神经元的状态。如果在输出层得不到期望的输出,则转入误差的反向传播阶段,将输出误差以某种形式通过隐含层向输入层反传,并将误差分摊给各层的所有单元,从而获得各层单元的误差信号并将其作为修正各单元权值的依据。这种网络的信号正向传播与误差反向传播是反复交替进行的,权值的不断调整就是网络的记忆训练过程。网络的记忆训练过程一直进行到网络趋向收敛,即输出误差达到要求的标准。

    三层BP神经网络的学习算法:为了使BP网络具有某种功能,完成某项任务,必须调整层间连接权值和节点阈值,使所有样品的实际输出和期望输出之间的误差稳定在一个较小的值之内。三层BP网络学习过程主要由四部分组成:(1)、输入模式顺传播(输入模式由输入层经隐含层向输出层传播计算);(2)、输出误差逆传播(输出的误差由输出层经隐含层传向输入层);(3)、循环记忆训练(模式顺传播与误差逆传播的计算过程反复交替循环进行);(4)、学习结果判别(判定全局误差是否趋向极小值或是否已达到设定的最大迭代次数)。

    (1)、输入模式顺传播:这一过程主要是利用输入模式求出它所对应的实际输出。

    确定输入向量Xk


    式中,k=1,2,…,m;m是学习模式对数(训练模式对数);n是输入层单元数。

    确定期望输出向量Yk


    式中,k=1,2,…,m;m是学习模式对数(训练模式对数);q为输出层单元数。

    计算隐含层各神经元的激活值sj


    式中,n是输入层单元数;wij是输入层至隐含层的连接权值;θj是隐含层单元的阈值;j=1,2…p,p是隐含层单元数。

    激活函数采用s型函数:


    计算隐含层j单元的输出值:将上面的激活值即公式(3)代入激活函数即公式(4)中可得隐含层j单元的输出值:


    阈值θj在学习过程中与权值wij一样也不断地被修正。

    计算输出层第t个单元的激活值ot


    计算输出层第t个单元的实际输出值ct


    式中,wjt是隐含层至输出层的权值;θt是输出层单元阈值;j=1,2…p,p是隐含层单元数;xj为隐含层第j个节点的输出值;f是s型激活函数,t=1,2…,q,q为输出层单元数。

    利用以上各公式就可以计算出一个输入模式的顺传播过程。

    (2)、输出误差的逆传播:在第一步的模式顺传播计算中得到了网络的实际输出值,当这些实际的输出值与希望的输出值不一样或者误差大于所限定的数值时,就要对网络进行校正。

    这里的校正是从前往后进行的,所以叫做误差逆传播,计算时是从输出层到隐含层,再从隐含层到输入层。

    输出层的校正误差:


    式中,t=1,2,…,q,q是输出层单元数;k=1,2,…,m,m是训练(学习)模式对数;ytk是希望输出;ctk是实际输出;f(.)是对输出函数的导数。

    隐含层各单元的校正误差:


    式中,t=1,2,…,q,q是输出层单元数;j=1,2,…,p; p是隐含层单元数;k=1,2,…,m,m是训练(学习)模式对数。

    对于输出层至隐含层连接权和输出层阈值的校正量:


    式中,bjk是隐含层j单元的输出;dtk是输出层的校正误差;j=1,2…,p;t=1,2,…,q;k=1,2,…,m; α>0(输出层至隐含层学习率)。

    隐含层至输入层的校正量:


    式中,ejk是隐含层j单元的校正误差;xik是标准输入,i=1,2,…,n ,n是输入层单元数;0<β<1(隐含层至输入层学习率)。

    (3)、循环记忆训练:为使网络的输出误差趋向于极小值,对于BP网输入的每一组训练模式,一般要经过数百次甚至上万次的循环记忆训练,才能使网络记住这一模式。这种循环记忆实际上就是反复重复上面介绍的输入模式顺传播和输出误差逆传播。

    (4)、学习结果的判别:当每次循环记忆训练结束后,都要进行学习结果的判别。判别的目的主要是检查输出误差是否已经小到可以允许的程度。如果小到可以允许的程度,就可以结束整个学习过程,否则还要继续进行循环训练。

    确定隐含层节点数:一般有3个经验公式:


    式中,m为要设置的隐含层节点数;n为输入层节点数;l为输出层节点数;α为1至10之间的常数。

    以下按照上面的公式实现的BP,通过MNIST库测试,识别率可以达到96.5%以上。

    BP.hpp:

    #ifndef _BP_HPP_
    #define _BP_HPP_
    
    namespace ANN {
    
    #define num_node_input_BP	784 //输入层节点数
    #define width_image_BP		28 //归一化图像宽
    #define height_image_BP		28 //归一化图像高
    #define num_node_hidden_BP	120 //隐含层节点数
    #define num_node_output_BP	10 //输出层节点数
    #define alpha_learning_BP	0.8 //输出层至隐含层学习率
    #define beta_learning_BP	0.6 //隐含层至输入层学习率
    #define patterns_train_BP	60000 //训练模式对数(总数)
    #define patterns_test_BP	10000 //测试模式对数(总数)
    #define iterations_BP		10000 //最大训练次数
    #define accuracy_rate_BP	0.965 //要求达到的准确率
    
    class BP {
    public:
    	BP();
    	~BP();
    
    	void init(); //初始化,分配空间
    	bool train(); //训练
    	int predict(const int* data, int width, int height); //预测
    	bool readModelFile(const char* name); //读取已训练好的BP model
    
    protected:
    	void release(); //释放申请的空间
    	bool saveModelFile(const char* name); //将训练好的model保存起来,包括各层的节点数,权值和阈值
    	bool initWeightThreshold(); //初始化,产生[-1, 1]之间的随机小数
    	bool getSrcData(); //读取MNIST数据
    	void calcHiddenLayer(const int* data); //计算隐含层输出
    	void calcOutputLayer(); //计算输出层输出
    	void calcAdjuctOutputLayer(const int* data); //计算输出层校正误差
    	void calcAdjuctHiddenLayer(); //计算隐含层校正误差
    	float calcActivationFunction(float x); //计算激活函数,对数S形函数
    	void updateWeightThresholdOutputLayer(); //更新输出层至隐含层权值和阈值
    	void updateWeightThresholdHiddenLayer(const int* data); //更新隐含层至输入层权值和阈值
    	float test(); //训练完一次计算一次准确率
    
    private:
    	float weight1[num_node_input_BP][num_node_hidden_BP]; //输入层至隐含层连接权值
    	float weight2[num_node_hidden_BP][num_node_output_BP]; //隐含层至输出层连接权值
    	float threshold1[num_node_hidden_BP]; //隐含层阈值
    	float threshold2[num_node_output_BP]; //输出层阈值
    	float output_hiddenLayer[num_node_hidden_BP]; //顺传播,隐含层输出值
    	float output_outputLayer[num_node_output_BP]; //顺传播,输出层输出值
    	float adjust_error_outputLayer[num_node_output_BP]; //逆传播,输出层校正误差
    	float adjust_error_hiddenLayer[num_node_hidden_BP]; //逆传播,隐含层校正误差
    
    	int* data_input_train; //原始标准输入数据,训练
    	int* data_output_train; //原始标准期望结果,训练
    	int* data_input_test; //原始标准输入数据,测试
    	int* data_output_test; //原始标准期望结果,测试
    };
    
    }
    
    #endif //_BP_HPP_
    BP.cpp:

    #include <assert.h>
    #include <time.h>
    #include <iostream>
    #include <fstream>
    #include <algorithm>
    #include <windows.h>
    
    #include "BP.hpp"
    
    namespace ANN {
    
    BP::BP()
    {
    	data_input_train = NULL;
    	data_output_train = NULL;
    	data_input_test = NULL;
    	data_output_test = NULL;
    }
    
    BP::~BP()
    {
    	release();
    }
    
    void BP::release()
    {
    	if (data_input_train) {
    		delete[] data_input_train;
    	}
    	if (data_output_train) {
    		delete[] data_output_train;
    	}
    	if (data_input_test) {
    		delete[] data_input_test;
    	}
    	if (data_output_test) {
    		delete[] data_output_test;
    	}
    }
    
    bool BP::initWeightThreshold()
    {
    	srand(time(0) + rand());
    
    	for (int i = 0; i < num_node_input_BP; i++) {
    		for (int j = 0; j < num_node_hidden_BP; j++) {
    			weight1[i][j] = -1 + 2 * ((float)rand()) / RAND_MAX; //[-1, 1]
    		}
    	}
    
    	for (int i = 0; i < num_node_hidden_BP; i++) {
    		for (int j = 0; j < num_node_output_BP; j++) {
    			weight2[i][j] = -1 + 2 * ((float)rand()) / RAND_MAX;
    		}
    	}
    
    	for (int i = 0; i < num_node_hidden_BP; i++) {
    		threshold1[i] = -1 + 2 * ((float)rand()) / RAND_MAX;
    	}
    
    	for (int i = 0; i < num_node_output_BP; i++) {
    		threshold2[i] = -1 + 2 * ((float)rand()) / RAND_MAX;
    	}
    
    	return true;
    }
    
    static int reverseInt(int i)
    {
    	unsigned char ch1, ch2, ch3, ch4;
    	ch1 = i & 255;
    	ch2 = (i >> 8) & 255;
    	ch3 = (i >> 16) & 255;
    	ch4 = (i >> 24) & 255;
    	return((int)ch1 << 24) + ((int)ch2 << 16) + ((int)ch3 << 8) + ch4;
    }
    
    static void readMnistImages(std::string filename, int* data_dst, int num_image)
    {
    	std::ifstream file(filename, std::ios::binary);
    	assert(file.is_open());
    
    	int magic_number = 0;
    	int number_of_images = 0;
    	int n_rows = 0;
    	int n_cols = 0;
    	file.read((char*)&magic_number, sizeof(magic_number));
    	magic_number = reverseInt(magic_number);
    	file.read((char*)&number_of_images, sizeof(number_of_images));
    	number_of_images = reverseInt(number_of_images);
    	assert(number_of_images == num_image);
    	file.read((char*)&n_rows, sizeof(n_rows));
    	n_rows = reverseInt(n_rows);
    	file.read((char*)&n_cols, sizeof(n_cols));
    	n_cols = reverseInt(n_cols);
    	assert(n_rows == height_image_BP && n_cols == width_image_BP);
    
    	for (int i = 0; i < number_of_images; ++i) {
    		for (int r = 0; r < n_rows; ++r) {
    			for (int c = 0; c < n_cols; ++c) {
    				unsigned char temp = 0;
    				file.read((char*)&temp, sizeof(temp));
    				//data_dst[i * num_node_input_BP + r * n_cols + c] = (int)temp; //formula[1]
    				if (temp > 128) {
    					data_dst[i * num_node_input_BP + r * n_cols + c] = 1;
    				} else {
    					data_dst[i * num_node_input_BP + r * n_cols + c] = 0;
    				}
    			}
    		}
    	}
    }
    
    static void readMnistLabels(std::string filename, int* data_dst, int num_image)
    {
    	std::ifstream file(filename, std::ios::binary);
    	assert(file.is_open());
    
    	int magic_number = 0;
    	int number_of_images = 0;
    	file.read((char*)&magic_number, sizeof(magic_number));
    	magic_number = reverseInt(magic_number);
    	file.read((char*)&number_of_images, sizeof(number_of_images));
    	number_of_images = reverseInt(number_of_images);
    	assert(number_of_images == num_image);
    
    	for (int i = 0; i < number_of_images; ++i) {
    		unsigned char temp = 0;
    		file.read((char*)&temp, sizeof(temp));
    		data_dst[i * num_node_output_BP + temp] = 1; //formula[2]
    	}
    }
    
    bool BP::getSrcData()
    {
    	assert(data_input_train && data_output_train && data_input_test && data_output_test);
    
    	std::string filename_train_images = "D:/Download/MNIST/train-images.idx3-ubyte";
    	std::string filename_train_labels = "D:/Download/MNIST/train-labels.idx1-ubyte";
    	readMnistImages(filename_train_images, data_input_train, patterns_train_BP);
    	/*unsigned char* p = new unsigned char[784];
    	memset(p, 0, sizeof(unsigned char) * 784);
    	for (int j = 0, i = 59998 * 784; j< 784; j++, i++) {
    		p[j] = (unsigned char)data_input_train[i];
    	}
    	delete[] p;*/
    	readMnistLabels(filename_train_labels, data_output_train, patterns_train_BP);
    	/*int* q = new int[10];
    	memset(q, 0, sizeof(int) * 10);
    	for (int j = 0, i = 59998 * 10; j < 10; j++, i++) {
    		q[j] = data_output_train[i];
    	}
    	delete[] q;*/
    
    	std::string filename_test_images = "D:/Download/MNIST/t10k-images.idx3-ubyte";
    	std::string filename_test_labels = "D:/Download/MNIST/t10k-labels.idx1-ubyte";
    	readMnistImages(filename_test_images, data_input_test, patterns_test_BP);
    	readMnistLabels(filename_test_labels, data_output_test, patterns_test_BP);
    
    	return true;
    }
    
    void BP::init()
    {
    	data_input_train = new int[patterns_train_BP * num_node_input_BP];
    	memset(data_input_train, 0, sizeof(int) * patterns_train_BP * num_node_input_BP);
    	data_output_train = new int[patterns_train_BP * num_node_output_BP];
    	memset(data_output_train, 0, sizeof(int) * patterns_train_BP * num_node_output_BP);
    	data_input_test = new int[patterns_test_BP * num_node_input_BP];
    	memset(data_input_test, 0, sizeof(int) * patterns_test_BP * num_node_input_BP);
    	data_output_test = new int[patterns_test_BP * num_node_output_BP];
    	memset(data_output_test, 0, sizeof(int) * patterns_test_BP * num_node_output_BP);
    
    	initWeightThreshold();
    	getSrcData();
    }
    
    float BP::calcActivationFunction(float x)
    {
    	return 1.0 / (1.0 + exp(-x)); //formula[4] formula[5] formula[7]
    }
    
    void BP::calcHiddenLayer(const int* data)
    {
    	for (int i = 0; i < num_node_hidden_BP; i++) {
    		float tmp = 0;
    		for (int j = 0; j < num_node_input_BP; j++) {
    			tmp += data[j] * weight1[j][i];
    		}
    
    		tmp -= threshold1[i]; //formula[3]
    		output_hiddenLayer[i] = calcActivationFunction(tmp);
    	}
    }
    
    void BP::calcOutputLayer()
    {
    	for (int i = 0; i < num_node_output_BP; i++) {
    		float tmp = 0;
    		for (int j = 0; j < num_node_hidden_BP; j++) {
    			tmp += output_hiddenLayer[j] * weight2[j][i];
    		}
    
    		tmp -= threshold2[i]; //formula[6]
    		output_outputLayer[i] = calcActivationFunction(tmp);
    	}
    }
    
    void BP::calcAdjuctOutputLayer(const int* data)
    {
    	for (int i = 0; i < num_node_output_BP; i++) {
    		adjust_error_outputLayer[i] = (data[i] - output_outputLayer[i]) *
    			output_outputLayer[i] * (1.0 - output_outputLayer[i]); //formula[8], f'(x)= f(x)*(1. - f(x))
    	}
    }
    
    void BP::calcAdjuctHiddenLayer()
    {
    	for (int i = 0; i < num_node_hidden_BP; i++) {
    		float tmp = 0;
    		for (int j = 0; j < num_node_output_BP; j++) {
    			tmp += weight2[i][j] * adjust_error_outputLayer[j];
    		}
    
    		adjust_error_hiddenLayer[i] = tmp * (output_hiddenLayer[i] * (1.0 - output_hiddenLayer[i])); //formula[9]
    	}
    }
    
    void BP::updateWeightThresholdOutputLayer()
    {
    	for (int i = 0; i < num_node_output_BP; i++) {
    		for (int j = 0; j < num_node_hidden_BP; j++) {
    			weight2[j][i] += (alpha_learning_BP * adjust_error_outputLayer[i] * output_hiddenLayer[j]); //formula[10]
    		}
    
    		threshold2[i] += (alpha_learning_BP * adjust_error_outputLayer[i]); //formula[11]
    	}
    }
    
    void BP::updateWeightThresholdHiddenLayer(const int* data)
    {
    	for (int i = 0; i < num_node_hidden_BP; i++) {
    		for (int j = 0; j < num_node_input_BP; j++) {
    			weight1[j][i] += (beta_learning_BP * adjust_error_hiddenLayer[i] * data[j]); //formula[12]
    		}
    
    		threshold1[i] += (beta_learning_BP * adjust_error_hiddenLayer[i]); //formula[13]
    	}
    }
    
    float BP::test()
    {
    	int count_accuracy = 0;
    
    	for (int num = 0; num < patterns_test_BP; num++) {
    		int* p1 = data_input_test + num * num_node_input_BP;
    		calcHiddenLayer(p1);
    		calcOutputLayer();
    
    		float max_value = -9999;
    		int pos = -1;
    
    		for (int i = 0; i < num_node_output_BP; i++) {
    			if (output_outputLayer[i] > max_value) {
    				max_value = output_outputLayer[i];
    				pos = i;
    			}
    		}
    
    		int* p2 = data_output_test + num * num_node_output_BP;
    		if (p2[pos] == 1) {
    			count_accuracy++;
    		}
    		Sleep(1);
    	}
    
    	return (count_accuracy * 1.0 / patterns_test_BP);
    }
    
    bool BP::saveModelFile(const char* name)
    {
    	FILE* fp = fopen(name, "wb");
    	if (fp == NULL) {
    		return false;
    	}
    
    	int num_node_input = num_node_input_BP;
    	int num_node_hidden = num_node_hidden_BP;
    	int num_node_output = num_node_output_BP;
    	fwrite(&num_node_input, sizeof(int), 1, fp);
    	fwrite(&num_node_hidden, sizeof(int), 1, fp);
    	fwrite(&num_node_output, sizeof(int), 1, fp);
    	fwrite(weight1, sizeof(weight1), 1, fp);
    	fwrite(threshold1, sizeof(threshold1), 1, fp);
    	fwrite(weight2, sizeof(weight2), 1, fp);
    	fwrite(threshold2, sizeof(threshold2), 1, fp);
    
    	fflush(fp);
    	fclose(fp);
    
    	return true;
    }
    
    bool BP::readModelFile(const char* name)
    {
    	FILE* fp = fopen(name, "rb");
    	if (fp == NULL) {
    		return false;
    	}
    
    	int num_node_input, num_node_hidden, num_node_output;
    
    	fread(&num_node_input, sizeof(int), 1, fp);
    	assert(num_node_input == num_node_input_BP);
    	fread(&num_node_hidden, sizeof(int), 1, fp);
    	assert(num_node_hidden == num_node_hidden_BP);
    	fread(&num_node_output, sizeof(int), 1, fp);
    	assert(num_node_output == num_node_output_BP);
    	fread(weight1, sizeof(weight1), 1, fp);
    	fread(threshold1, sizeof(threshold1), 1, fp);
    	fread(weight2, sizeof(weight2), 1, fp);
    	fread(threshold2, sizeof(threshold2), 1, fp);
    
    	fflush(fp);
    	fclose(fp);
    
    	return true;
    }
    
    int BP::predict(const int* data, int width, int height)
    {
    	assert(data && width == width_image_BP && height == height_image_BP);
    
    	const int* p = data;
    	calcHiddenLayer(p);
    	calcOutputLayer();
    
    	float max_value = -9999;
    	int ret = -1;
    
    	for (int i = 0; i < num_node_output_BP; i++) {
    		if (output_outputLayer[i] > max_value) {
    			max_value = output_outputLayer[i];
    			ret = i;
    		}
    	}
    
    	return ret;
    }
    
    bool BP::train()
    {
    	int i = 0;
    	for (i = 0; i < iterations_BP; i++) {
    		std::cout << "iterations : " << i;
    
    		float accuracyRate = test();
    		std::cout << ",    accuray rate: " << accuracyRate << std::endl;
    		if (accuracyRate > accuracy_rate_BP) {
    			saveModelFile("bp.model");
    			std::cout << "generate bp model" << std::endl;
    			break;
    		}
    
    		for (int j = 0; j < patterns_train_BP; j++) {
    			int* p1 = data_input_train + j * num_node_input_BP;
    			calcHiddenLayer(p1);
    			calcOutputLayer();
    
    			int* p2 = data_output_train + j * num_node_output_BP;
    			calcAdjuctOutputLayer(p2);
    			calcAdjuctHiddenLayer();
    
    			updateWeightThresholdOutputLayer();
    			int* p3 = data_input_train + j * num_node_input_BP;
    			updateWeightThresholdHiddenLayer(p3);
    		}
    	}
    
    	if (i == iterations_BP) {
    		saveModelFile("bp.model");
    		std::cout << "generate bp model" << std::endl;
    	}
    
    	return true;
    }
    
    }
    
    test.cpp:

    #include <iostream>
    #include "BP.hpp"
    #include <opencv2/opencv.hpp>
    
    int test_BP();
    
    int main()
    {
    	test_BP();
    	std::cout << "ok!" << std::endl;
    }
    
    int test_BP()
    {
    	//1. bp train
    	ANN::BP bp1;
    	bp1.init();
    	bp1.train();
    
    	//2. bp predict
    	ANN::BP bp2;
    	bool flag = bp2.readModelFile("bp.model");
    	if (!flag) {
    		std::cout << "read bp model error" << std::endl;
    		return -1;
    	}
    
    	int target[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    	std::string path_images = "../../../../test-images/";
    
    	int* data_image = new int[width_image_BP * height_image_BP];
    
    	for (int i = 0; i < 10; i++) {
    		char ch[15];
    		sprintf(ch, "%d", i);
    		std::string str;
    		str = std::string(ch);
    		str += ".jpg";
    		str = path_images + str;
    
    		cv::Mat mat = cv::imread(str, 2 | 4);
    		if (!mat.data) {
    			std::cout << "read image error" << std::endl;
    			return -1;
    		}
    
    		if (mat.channels() == 3) {
    			cv::cvtColor(mat, mat, cv::COLOR_BGR2GRAY);
    		}
    
    		if (mat.cols != width_image_BP || mat.rows != height_image_BP) {
    			cv::resize(mat, mat, cv::Size(width_image_BP, height_image_BP));
    		}
    
    		memset(data_image, 0, sizeof(int) * (width_image_BP * height_image_BP));
    
    		for (int h = 0; h < mat.rows; h++) {
    			uchar* p = mat.ptr(h);
    			for (int w = 0; w < mat.cols; w++) {
    				if (p[w] > 128) {
    					data_image[h* mat.cols + w] = 1;
    				}
    			}
    		}
    
    		int ret = bp2.predict(data_image, mat.cols, mat.rows);
    		std::cout << "correct result: " << i << ",    actual result: " << ret << std::endl;
    	}
    
    	delete[] data_image;
    
    	return 0;
    }
    

    train结果如下图所示:



    predict结果如下图所示,测试图像是从MNIST test集合中选取的:


    GitHub:https://github.com/fengbingchun/NN

    展开全文
  • 带你彻彻底底搞懂朴素贝叶斯公式

    万次阅读 多人点赞 2018-03-10 17:29:50
    本文参考了该博客的实例,但该博客中的朴素贝叶斯公式计算错误,评论中的也不对,所以,重新写一篇。一. 朴素贝叶斯 朴素贝叶斯中的朴素一词的来源就是假设各...就相当于完成了我们的任务。 则,朴素贝特斯公式...

    本文参考了该博客的实例,但该博客中的朴素贝叶斯公式计算错误,评论中的也不对,所以,重新写一篇。

    一. 朴素贝叶斯

          朴素贝叶斯中的朴素一词的来源就是假设各特征之间相互独立。这一假设使得朴素贝叶斯算法变得简单,但有时会牺牲一定的分类准确率

        首先给出贝叶斯公式:
        换成分类任务的表达式:
         我们最终求的p(类别|特征)即可!就相当于完成了我们的任务。
         则,朴素贝特斯公式为:
    . 实例解析

    首先,给出数据如下:


    现在给我们的问题是,如果一对男女朋友,男生想女生求婚,男生的四个特点分别是不帅,性格不好,身高矮,不上进,请你判断一下女生是还是不嫁

    这是典型的二分类问题,按照朴素贝叶斯的求解,转换为P(嫁|不帅、性格不好、矮、不上进)和P(不嫁|不帅、性格不好、矮、不上进)的概率,最终选择嫁与不嫁的答案。

    这里我们根据贝特斯公式:

    由此,我们将(嫁|不帅、性格不好、矮、不上进)转换成三个可求的P(嫁)、P(不帅、性格不好、矮、不上进|嫁)、P(不帅、性格不好、矮、不上进)。进一步分解可以得:
    P(不帅、性格不好、矮、不上进)=P()P(不帅|嫁)P(性格不好|嫁)P(矮|嫁)P(不上进|嫁)+P(不)P(不帅|不嫁)P(性格不好|不嫁)P(矮|不嫁)P(不上进|不嫁)。

    P(不帅、性格不好、矮、不上进|嫁)=P(不帅|嫁)P(性格不好|嫁)P(矮|嫁)P(不上进|嫁)

    将上面的公式整理一下可得:


     P()=1/2、P(不帅|嫁)=1/2、P(性格不好|嫁)=1/6、P(矮|嫁)=1/6、P(不上进|嫁)=1/6。
     P(不嫁)=1/2、P(不帅|不嫁)=1/3、P(性格不好|不嫁)=1/2、P(矮|不嫁)=1、P(不上进|不嫁)=2/3
     但是由贝叶斯公式可得:对于目标求解为不同的类别,贝叶斯公式的分母总是相同的。所以,只求解分子即可:

    于是,对于类别“嫁”的贝叶斯分子为:P(嫁)P(不帅|嫁)P(性格不好|嫁)P(矮|嫁)P(不上进|嫁)=1/2 * 1/2 * 1/6 * 1/6 * 1/6=1/864     
    对于类别“不嫁”的贝叶斯分子为:P(不)P(不帅|不嫁)P(性格不好|不嫁)P(矮|不嫁)P(不上进|不嫁)=1/2 * 1/3 * 1/2 * 1* 2/3=1/18。
    经代入贝叶斯公式可得:P(嫁|不帅、性格不好、矮、不上进)=(1/864) / (1/864+1/18)=1/49=2.04%
    P(不嫁|不帅、性格不好、矮、不上进)=(1/18) / (1/864+1/18)=48/49=97.96%
    P(不嫁|不帅、性格不好、矮、不上进) > P(嫁|不帅、性格不好、矮、不上进),则该女子选择不嫁!

    . 朴素贝叶斯的优缺点

    优点:
      (1) 算法逻辑简单,易于实现(算法思路很简单,只要使用贝叶斯公式转化即可!
    (2)分类过程中时空开销小(假设特征相互独立,只会涉及到二维存储
    缺点:
          朴素贝叶斯假设属性之间相互独立,这种假设在实际过程中往往是不成立的。在属性之间相关性越大,分类误差也就越大。

    四. 朴素贝叶斯实战

        sklearn中有3种不同类型的朴素贝叶斯:

    • 高斯分布型:用于classification问题,假定属性/特征服从正态分布的。
    • 多项式型:用于离散值模型里。比如文本分类问题里面我们提到过,我们不光看词语是否在文本中出现,也得看出现次数。如果总词数为n,出现词数为m的话,有点像掷骰子n次出现m次这个词的场景。
    • 伯努利型:最后得到的特征只有0(没出现)和1(出现过)。
      4.1  我们使用iris数据集进行分类
    from sklearn.naive_bayes import GaussianNB
    from sklearn.model_selection import cross_val_score
    from sklearn import datasets
    iris = datasets.load_iris()
    gnb = GaussianNB()
    scores=cross_val_score(gnb, iris.data, iris.target, cv=10)
    print("Accuracy:%.3f"%scores.mean())
        输出: Accuracy:0.953
     

      4.2 Kaggle比赛之“旧金山犯罪分类预测”

           题目数据:第一种获取方式:Kaggle网站上;第二种获取方式:百度网盘

            题目背景:『水深火热』的大米国,在旧金山这个地方,一度犯罪率还挺高的,然后很多人都经历过大到暴力案件,小到东西被偷,车被划的事情。当地警方也是努力地去总结和想办法降低犯罪率,一个挑战是在给出犯罪的地点和时间的之后,要第一时间确定这可能是一个什么样的犯罪类型,以确定警力等等。后来干脆一不做二不休,直接把12年内旧金山城内的犯罪报告都丢带Kaggle上,说『大家折腾折腾吧,看看谁能帮忙第一时间预测一下犯罪类型』。犯罪报告里面包括日期描述星期几所属警区处理结果地址GPS定位等信息。当然,分类问题有很多分类器可以选择,我们既然刚讲过朴素贝叶斯,刚好就拿来练练手好了。

         (1) 首先我们来看一下数据

    import pandas as pd  
    import numpy as np  
    from sklearn import preprocessing  
    from sklearn.metrics import log_loss  
    from sklearn.cross_validation import train_test_split
    train = pd.read_csv('/Users/liuming/projects/Python/ML数据/Kaggle旧金山犯罪类型分类/train.csv', parse_dates = ['Dates'])  
    test = pd.read_csv('/Users/liuming/projects/Python/ML数据/Kaggle旧金山犯罪类型分类/test.csv', parse_dates = ['Dates'])  
    train  

     我们依次解释一下每一列的含义:

    • Date: 日期
    • Category: 犯罪类型,比如 Larceny/盗窃罪 等.
    • Descript: 对于犯罪更详细的描述
    • DayOfWeek: 星期几
    • PdDistrict: 所属警区
    • Resolution: 处理结果,比如说『逮捕』『逃了』
    • Address: 发生街区位置
    • X and Y: GPS坐标

            train.csv中的数据时间跨度为12年,包含了将近90w的记录。另外,这部分数据,大家从上图上也可以看出来,大部分都是『类别』型,比如犯罪类型,比如星期几。

        (2)特征预处理

           sklearn.preprocessing模块中的 LabelEncoder函数可以对类别做编号,我们用它对犯罪类型做编号;pandas中的get_dummies( )可以将变量进行二值化01向量,我们用它对”街区“、”星期几“、”时间点“进行因子化。

    #对犯罪类别:Category; 用LabelEncoder进行编号  
    leCrime = preprocessing.LabelEncoder()  
    crime = leCrime.fit_transform(train.Category)   #39种犯罪类型  
    #用get_dummies因子化星期几、街区、小时等特征  
    days=pd.get_dummies(train.DayOfWeek)  
    district = pd.get_dummies(train.PdDistrict)  
    hour = train.Dates.dt.hour  
    hour = pd.get_dummies(hour)  
    #组合特征  
    trainData = pd.concat([hour, days, district], axis = 1)  #将特征进行横向组合  
    trainData['crime'] = crime   #追加'crime'列  
    days = pd.get_dummies(test.DayOfWeek)  
    district = pd.get_dummies(test.PdDistrict)  
    hour = test.Dates.dt.hour  
    hour = pd.get_dummies(hour)  
    testData = pd.concat([hour, days, district], axis=1)  
    trainData 
    

        特征预处理后,训练集feature,如下图所示:

       (3) 建模

    from sklearn.naive_bayes import BernoulliNB
    import time
    features=['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday', 'BAYVIEW', 'CENTRAL', 'INGLESIDE', 'MISSION',  
     'NORTHERN', 'PARK', 'RICHMOND', 'SOUTHERN', 'TARAVAL', 'TENDERLOIN']  
    X_train, X_test, y_train, y_test = train_test_split(trainData[features], trainData['crime'], train_size=0.6)  
    NB = BernoulliNB()  
    nbStart = time.time()  
    NB.fit(X_train, y_train)  
    nbCostTime = time.time() - nbStart  
    #print(X_test.shape)  
    propa = NB.predict_proba(X_test)   #X_test为263415*17; 那么该行就是将263415分到39种犯罪类型中,每个样本被分到每一种的概率  
    print("朴素贝叶斯建模%.2f秒"%(nbCostTime))  
    predicted = np.array(propa)  
    logLoss=log_loss(y_test, predicted)  
    print("朴素贝叶斯的log损失为:%.6f"%logLoss)  
    
    输出:
    朴素贝叶斯建模0.55秒
    朴素贝叶斯的log损失为:2.582561

    展开全文
  • PMP计算公式

    千次阅读 2015-05-19 11:27:10
    名称 ...公式 所在章节 PERT (P+4M+O)/6 时间(或成本) 标准差 (P-O)/6 时间(或成本) 总浮动时间 LS-ES 或 LF-EF 时间 成本偏差(CV) EV-AC
  • 应用服务器配置测算及计算公式

    万次阅读 2019-01-15 10:06:27
    应用服务器配置测算及计算公式 1 术语和定义 1.1 信息系统 由计算机、通信设备、处理设备、控制设备及其相关的配套设施构成,按照一定的应用目的和规则,对信息进行采集、加工、存储、传输、检索等处理的人机系统。...
  • 股市公式编辑器

    千次阅读 2017-03-01 16:34:44
    通达信公式教程 公式入门 我们大多数的用户并不是完全了解“公式编辑器”的意义,简单地,我们可以从以下几个角度进行理解: 一、指标分析: “公式编辑器”好比是一个工作母床,通过这个工作母床可以制造出所...
  • 答案是,它们都会用到同一个数学公式——贝叶斯公式。它虽然看起来很简单、很不起眼,但却有着深刻的内涵。那么贝叶斯公式是如何从默默无闻到现在广泛应用、无所不能的呢? 18世纪英国业余数学家托马斯·贝叶斯...
  • Mathpix(全名Mathpix Snipping Tool)是一款跨平台(Windows、macOS、Linux)的公式提取软件,其底层使用机器学习算法进行识别,准确相当之高。目前,最新版的Mathpix需要注册登录才能使用,注册地址点击右侧链接...
  • 上一篇文章(点击链接:【Linux进程、线程、任务调度】二)讲了: fork vfork clone 的含义 写时拷贝技术 Linux线程的实现本质 ...吞吐 vs. 响应 SCHED_FIFO算法 与 SCHED_RR算法 SCHED_NORMAL...
  • 我们要完成三项任务: 使用随机森林算法完成基本建模任务 基本任务需要我们处理数据,观察特征,完成建模并进行可视化展示分析 观察数据量与特征个数对结果影响 在保证算法一致的前提下, 加大数据个数,观察结果变换...
  • 计算机网络常用公式

    千次阅读 2019-05-30 11:04:26
    流水线吞吐=任务数/完成时间 流水线加速比=不采用流水线的执行时间/采用流水线的执行时间 流水线的总时间=(指令总数+2) 周期值 七、存储器计算 存储器带宽:每秒能访问的位数 单位ns=10-9秒 存储器带宽=1秒...
  • μC/OS Ⅱ中的空闲任务与统计任务 空闲任务 先上一段转自他人博客的一段关于空闲任务为什么存在的一段描述: uc/os-II操作系统关于空闲任务是这样描述的:  1、系统任务并且不能被删除;  2、优先级别最低而且...
  • Mathpix Snip--图片中识别公式

    万次阅读 2019-05-06 10:49:29
    title: 数学公式神器Mathpix Snip—妈妈再也不用担心我不会写数学公式了! 数学公式神器Mathpix Snip 本文转载自机器之心—《最好用的文字与公式编辑器,这套数学笔记神器送给你》,原文链接点击这儿。 在平时写博客...
  • 大智慧公式编写---初学者入门指南

    千次阅读 2009-12-25 18:33:00
    参考网址:http://www.55188.com/viewthread.php?tid=511351 公式入门我们大多数的用户并不是完全了解“公式编辑器”的意义,简单地,我们可以从以下几个角度进行理解:一、指标分析:“公式编辑器”好比是一个工作...
  • 大智慧公式编写教程

    万次阅读 2007-07-29 19:44:00
    大智慧公式编写教程 公式入门我们大多数的用户并不是完全了解“公式编辑器”的意义,简单地,我们可以从以下几个角度进行理解:一、指标分析:“公式编辑器”好比是一个工作母床,通过这个工作母床可以制造出所需要...
  • BP——反向传播算法公式推导及代码

    千次阅读 多人点赞 2019-03-14 23:51:19
    BP——反向传播算法计算过程详解人工神经网络的结构前向传播激活函数反向传播梯度下降具体计算过程 本文主要参考吴恩达和李宏毅的深度学习视频,...(注:Markdown敲公式对我来说太困难,后面的公式都用图片的形式展...
  • 朱明放1,2,叶飞跃1,2,丁小未2  (1.... ...2.江苏理工学院计算机学院,江苏常州,213001) ...摘要:任务指派问题是典型的组合优化问题,得到了广泛的...结合人力资源任务分配的实例进行了实验分析和研究,获得了人员与岗
  • 在多任务优化的情景下,如果任务之间存在潜在关系,那么高质量的解在这些任务之间的转移可以显著提高算法的性能。然而有的时候缺乏关于任务间协同作用的任何先验知识(黑盒优化),主要是负迁移导致算法的性能受损,...
  • 提高带宽利用!为什么要Pacing?

    千次阅读 2018-10-17 22:44:11
    这注定单条TCP的带宽利用极低,因此HTTP协议一般会采用多条TCP流捆绑的方式来传输Web服务器的数据以增加带宽,然而多TCP连接意味着连接管理的开销会增大,同时数据同步的开销也会增加,这导致了人们倾向于使用单独...
  • 线程池 核心线程数设定公式

    千次阅读 2020-03-22 17:21:18
    0.8,CPU核数为4 则核心线程数为20 注:阻塞系数公式 Blocking Coefficient(阻塞系数) = 阻塞时间/(阻塞时间+使用CPU的时间) CPU密集型: CPU密集型也叫计算密集型,指的是系统的硬盘、内存性能相对CPU要好很多,...
  • 1.公式: 响应时间(RT)是指系统对请求作出响应的时间。 吞吐量(Throughput)是指系统在单位时间内处理请求的数量。 并发用户数(Maximum concurrent user)是指系统可以同时承载的正常使用系统功能的用户的数量。 ...
  • 【word2vec】算法原理 公式推导

    万次阅读 多人点赞 2018-10-10 09:17:24
    使用word2vec模型学习的单词的向量表示已经被证明能够携带语义信息,且在各种NLP任务中都是有用的。越来越多的研究人员希望尝试使用word2vec,但我注意到对于word2vec参数学习过程目前还缺乏一个全面解释的资料,...
  • 任务、进程和线程

    千次阅读 2007-09-17 16:48:00
     在Win 32(95/NT)中,每一个进程可以同时执行多个线程,这意味着一个程序可以同时完成多个任务。对于象通信程序这样既要进行耗时的工作,又要保持对用户输入响应的应用来说,使用多线程是最佳选择。当进程使用多个...
  • 本文要介绍的就是人工智能背后的简单原理——贝叶斯公式。人工智能、无人驾驶、语音图片识别与大数据有什么关系?海难空难如何搜救?垃圾短信、垃圾邮件如何识别?这些看起来彼此不相关的领域之间会有什么联系吗?...
  • 任务学习通常通过隐藏层的 Hard 或 Soft 参数共享来完成。 共享 Hard 参数是神经网络 MTL 最常用的方法,可以追溯1993年Caruana所发表的论文。在实际应用中,通常通过在所有任务之间共享隐藏层,同时保留几个特定...
  • 计算linux服务器CPU利用

    万次阅读 2019-06-20 15:25:00
    文章目录一 通过top查看cpu各类占用信息二 通过/proc/stat文件查看cpu信息三 cpu占用计算公式四 代码实现 一 通过top查看cpu各类占用信息 如下图所示: us User time 用户时间 表示CPU 执行用户...
  • LDA模型学习之贝叶斯公式

    千次阅读 2013-10-18 10:58:32
     通常使用回归测试来评估分类器的准确,最简单的方法是用构造完成的分类器对训练数据进行分类,然后根据结果给出正确评估。但这不是一个好方法,因为使用训练数据作为检测数据有可能因为过分拟合而导致结果过于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,012
精华内容 15,204
关键字:

任务完成率公式