精华内容
下载资源
问答
  • 数据库完整性实验报告

    千次阅读 2019-12-03 13:43:39
    (1)实现数据完整性的概念及实施数据完整性的重要性。 (2)掌握数据完整性的分类。 (3)掌握完整性约束的添加、删除方法。 (4)掌握通用默认值的创建、实施与删除方法。 (5)掌握规则的创建、实施与删除...

    实验六 数据库完整性

    一、实验学时

    2学时

    二、实验目的

    (1)实现数据完整性的概念及实施数据完整性的重要性。
    (2)掌握数据完整性的分类。
    (3)掌握完整性约束的添加、删除方法。
    (4)掌握通用默认值的创建、实施与删除方法。
    (5)掌握规则的创建、实施与删除方法。
    (6)掌握级联删除、级联修改方法。

    三、实验要求

    (1)硬件设备:奔腾II或奔腾II以上计算机,局域网。
    (2)软件环境:WINDOWS 9X/NT、WINDOWS SERVER、WINDOWS XP、WINDOWS 7、SQL SERVER 2000/2005/2008中文版企业版或标准版。
    (3)实验课前预习,课后及时完成实验内容。
    (4)实验过程及记录按题目格式要求填写代码清单。
    四、实验内容
    数据完整性是指数据的正确性、完备性和一致性,是衡量数据库质量好坏的重要标准。
    数据完整性分为以下三类:
    实体完整性:是指保证表中所有的行惟一。由主键约束来实现。
    参照完整性:也叫引用完整性。参照完整性总是保证主关键字(被引用表)和外部关键字(引用表)之间的参照关系。它涉及两个或两个以上表数据的一致性维护。由外键约束来实现。
    用户自定义完整性:是指用户针对某一具体关系数据库的数据必须满足的语义要求。通常由Check约束来实现。
    1.完整性约束的添加、删除
    约束是强制数据完整性的首选方法。约束有6种类型:非空约束、默认值约束、Check约束、主键约束、外键约束、唯一性约束。
    (1)使用企业管理器实施约束
    1)为表Student的Sdept字段即所在系字段,设置默认值约束,默认值取‘CS’。
    添加默认约束的操作步骤:

    删除默认约束的操作步骤:

    2)(若原有约束,请在企业管理器中删除Student表的主键约束)在企业管理器中将Sno重设为主键。(会操作即可,操作步骤可略)
    3)为Student表的Sname字段添加唯一性约束。
    添加唯一性约束操作步骤:

    删除唯一性约束操作步骤:

    4)(若原有约束,请在企业管理器中删除原有的外键约束)在企业管理器中删除SC原有的外键约束,在企业管理器中对Sno,Cno字段设置外键约束,约束名自己取。并允许级联删除与级联更新。
    添加外键约束的操作步骤:

    删除外键约束的操作步骤:

    (2)使用T-SQL语句添加、删除约束(约束名自取,并自行添加或修改某些字段值检验有效性)
    1)为Student表的Sno字段添加一个check约束,使学号满足如下条件:
    a. 学号前四位为2002。
    b. 学号后五位为数字字符。
    T-SQL语句为:
    create table Student
    (Sno char(9) check(Sno like’[2002][0-9][0-9][0-9][0-9][0-9]’));

    2)(若原有约束,请在企业管理器中删除SC表主键约束及外键约束)将SC表中的Sno,Cno字段设置为主键。
    T-SQL语句为:
    alter table SC
    add constraint PK_SC primary key(Sno,Cno)

    3)为SC表中的Sno,Cno添加外键约束,约束名自取;并允许级联删除与级联更新。
    添加外键约束T-SQL语句为:

    alter table SC
    add constraint FK_Sno foreign key(Sno) references Student(Sno)
    on delete cascade on update cascade;
    alter table SC
    add constraint FK_Cno foreign key(Cno) references Course(Cno)
    on delete cascade on update cascade

    验证级联删除与级联更新T-SQL语句:
    (测试实例自编)
    **select from Student
    where Sno=‘200200002’
    select from SC
    where Sno=‘200200001’
    delete from Student
    where Sno=‘200200001’
    select from Student
    where Sno=‘200200001’
    select
    from SC
    where Sno=‘200200001’

    2.通用默认值的实施
    (1)使用企业管理器实现
    1)使用企业管理器中为数据库Stu_Course创建一个默认的年龄,名称自取,值为:19。
    具体步骤如下:

    2)将该默认值绑定到Student表中的Sage列。
    具体步骤如下:

    3)将Sage列上的绑定解除,并在企业管理器中删除该默认值。
    具体步骤如下:

    若未解除绑定,能否删除默认值?

    (2)使用T-SQL语句实施默认值
    1)为数据库Stu_Course创建一个关于性别的默认值,名称自取,值为“女”。
    T-SQL语句为:
    create default about_sex as '女’

    2)将该默认值绑定到Student表中的Ssex字段(原有的约束请删除)
    T-SQL语句:
    sp_bindefault about_sex ,"Student.Ssex"

    3)解除表Student的Ssex列的默认值绑定,并删除该默认值。
    T-SQL语句:
    sp_unbindefault ‘Student.Ssex’
    drop default about_sex

    3.规则的实施
    (1)使用企业管理器实现
    1)使用企业管理器为数据库Stu_Course创建一个关于性别的取值规则,规则名自取,要求字段的取值仅能为‘男’或‘女’。
    具体步骤如下:

    2)将该规则绑定到Student表的Ssex字段上。
    具体步骤如下:

    3)解除Student表的Ssex列上的绑定,并删除该规则。
    具体步骤如下:

    (2)使用T-SQL实施规则
    1)为数据库Stu_Course创建一个关于学号的规则,名称自取,学号的具体取值规则为:
    a.学号前四位为2002。
    b.学号后五位为数字字符。
    T-SQL语句为:
    create rule rule_Sno
    as @range like’2002[0-9][0-9][0-9][0-9][0-9]'

    2)将该规则绑定到表Student表、SC表的Sno列上。
    T-SQL语句为:
    exec sp_bindrule ‘rule_Sno’,‘Student.Sno’
    exec sp_bindrule ‘rule_Sno’,'SC.Sno’

    3)解除所有的绑定,并删除该规则。
    T-SQL语句为:
    exec sp_unbindrule ‘Student.Sno’
    exec sp_unbindrule 'SC.Sno’

    展开全文
  • 算法的重要性

    万次阅读 2013-07-22 17:57:13
    今天看了一篇关于算法的文章,是李开复老师写的,很不错,在整个计算机系统里,算法无疑是非常重要的!   算法的力量 算法是计算机科学领域最重要的基石之一,但却受到了国内一些程序员的冷落。许多...
    今天看了一篇关于算法的文章,是李开复老师写的,很不错,在整个计算机系统里,算法无疑是非常重要的!
     
    算法的力量

    算法是计算机科学领域最重要的基石之一,但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解,认为学计算机就是学各种编程语言,或者认为,学习最新的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。编程语言虽然该学,但是学习计算机算法和理论更重要,因为计算机算法和理论更重要,因为计算机语言和开发平台日新月异,但万变不离其宗的是那些算法和理论,例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。在“开复学生网”上,有位同学生动地把这些基础课程比拟为“内功”,把新的语言、技术、标准比拟为“外功”。整天赶时髦的人最后只懂得招式,没有功力,是不可能成为高手的。


    算法与我

    当我在1980年转入计算机科学系时,还没有多少人的专业方向是计算机科学。有许多其他系的人嘲笑我们说:“知道为什么只有你们系要加一个‘科学’,而没有‘物理科学系’或‘化学科学系’吗?因为人家是真的科学,不需要画蛇添足,而你们自己心虚,生怕不‘科学’,才这样欲盖弥彰。”其实,这点他们彻底弄错了。真正学懂计算机的人(不只是“编程匠”)都对数学有相当的造诣,既能用科学家的严谨思维来求证,也能用工程师的务实手段来解决问题——而这种思维和手段的最佳演绎就是“算法”。

    记得我读博时写的Othello对弈软件获得了世界冠军。当时,得第二名的人认为我是靠侥幸才打赢他,不服气地问我的程序平均每秒能搜索多少步棋,当他发现我的软件在搜索效率上比他快60多倍时,才彻底服输。为什么在同样的机器上,我可以多做60倍的工作呢?这是因为我用了一个最新的算法,能够把一个指数函数转换成四个近似的表,只要用常数时间就可得到近似的答案。在这个例子中,是否用对算法才是能否赢得世界冠军的关键。

    还记得1988年贝尔实验室副总裁亲自来访问我的学校,目的就是为了想了解为什么他们的语音识别系统比我开发的慢几十倍,而且,在扩大至大词汇系统后,速度差异更有几百倍之多。他们虽然买了几台超级计算机,勉强让系统跑了起来,但这么贵的计算资源让他们的产品部门很反感,因为“昂贵”的技术是没有应用前景的。在与他们探讨的过程中,我惊讶地发现一个O(n*m)的动态规划(dynamic programming)居然被他们做成了O(n*n*m)。更惊讶的是,他们还为此发表了不少文章,甚至为自己的算法起了一个很特别的名字,并将算法提名到一个科学会议里,希望能得到大奖。当时,贝尔实验室的研究员当然绝顶聪明,但他们全都是学数学、物理或电机出身,从未学过计算机科学或算法,才犯了这么基本的错误。我想那些人以后再也不会嘲笑学计算机科学的人了吧!


    网络时代的算法

    有人也许会说:“今天计算机这么快,算法还重要吗?”其实永远不会有太快的计算机,因为我们总会想出新的应用。虽然在摩尔定律的作用下,计算机的计算能力每年都在飞快增长,价格也在不断下降。可我们不要忘记,需要处理的信息量更是呈指数级的增长。现在每人每天都会创造出大量数据(照片,视频,语音,文本等等)。日益先进的纪录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。在科学研究方面,随着研究手段的进步,数据量更是达到了前所未有的程度。无论是三维图形、海量数据处理、机器学习、语音识别,都需要极大的计算量。在网络时代,越来越多的挑战需要靠卓越的算法来解决。

    再举另一个网络时代的例子。在互联网和手机搜索,如果要找附近的咖啡店,那么搜索引擎该怎么处理这个请求呢?最简单的办法就是把整个城市的咖啡馆都找出来,然后计算出它们的所在位置与你之间的距离,再进行排序,然后返回最近的结果。但该如何计算距离呢?图论里有不少算法可以解决这个问题。

    这么做也许是最直观的,但绝对不是最迅速的。如果一个城市只有为数不多的咖啡馆,那么这么做应该没什么问题,反正计算量不大。但如果一个城市里有很多咖啡馆,又有很多用户都需要类似的搜索,那么服务器所承受的压力就大多了。在这种情况下,我们该怎样优化算法呢?

    首先,我们可以把整个城市的咖啡馆做一次“预处理”。比如,把一个城市分成若干个“格子(grid)”,然后根据用户所在的位置把他放到某一个格子里,只对格子里的咖啡馆进行距离排序。

    问题又来了,如果格子大小一样,那么绝大多数结果都可能出现在市中心的一个格子里,而郊区的格子里只有极少的结果。在这种情况下,我们应该把市中心多分出几个格子。更进一步,格子应该是一个“树结构”,最顶层是一个大格——整个城市,然后逐层下降,格子越来越小,这样有利于用户进行精确搜索——如果在最底层的格子里搜索结果不多,用户可以逐级上升,放大搜索范围。

    上述算法对咖啡馆的例子很实用,但是它具有通用性吗?答案是否定的。把咖啡馆抽象一下,它是一个“点”,如果要搜索一个“面”该怎么办呢?比如,用户想去一个水库玩,而一个水库有好几个入口,那么哪一个离用户最近呢?这个时候,上述“树结构”就要改成“r-tree”,因为树中间的每一个节点都是一个范围,一个有边界的范围(参考:http://www.cs.umd.edu/~hjs/rtrees/index.html)。

    通过这个小例子,我们看到,应用程序的要求千变万化,很多时候需要把一个复杂的问题分解成若干简单的小问题,然后再选用合适的算法和数据结构。


    并行算法:Google的核心优势

    上面的例子在Google里就要算是小case了!每天Google的网站要处理十亿个以上的搜索,GMail要储存几千万用户的2G邮箱,Google Earth要让数十万用户同时在整个地球上遨游,并将合适的图片经过互联网提交给每个用户。如果没有好的算法,这些应用都无法成为现实。

    在这些的应用中,哪怕是最基本的问题都会给传统的计算带来很大的挑战。例如,每天都有十亿以上的用户访问Google的网站,使用Google的服务,也产生很多很多的日志(Log)。因为Log每份每秒都在飞速增加,我们必须有聪明的办法来进行处理。我曾经在面试中问过关于如何对Log进行一些分析处理的问题,有很多面试者的回答虽然在逻辑上正确,但是实际应用中是几乎不可行的。按照它们的算法,即便用上几万台机器,我们的处理速度都根不上数据产生的速度。

    那么Google是如何解决这些问题的?

    首先,在网络时代,就算有最好的算法,也要能在并行计算的环境下执行。在Google的数据中心,我们使用的是超大的并行计算机。但传统的并行算法运行时,效率会在增加机器数量后迅速降低,也就是说,十台机器如果有五倍的效果,增加到一千台时也许就只有几十倍的效果。这种事半功倍的代价是没有哪家公司可以负担得起的。而且,在许多并行算法中,只要一个结点犯错误,所有计算都会前功尽弃。

    那么Google是如何开发出既有效率又能容错的并行计算的呢?

    Google最资深的计算机科学家Jeff Dean认识到,Google所需的绝大部分数据处理都可以归结为一个简单的并行算法:Map and Reduce(http://labs.google.com/papers/mapreduce.html)。这个算法能够在很多种计算中达到相当高的效率,而且是可扩展的(也就是说,一千台机器就算不能达到一千倍的效果,至少也可以达到几百倍的效果)。Map and Reduce的另外一大特色是它可以利用大批廉价的机器组成功能强大的server farm。最后,它的容错性能异常出色,就算一个server farm宕掉一半,整个fram依然能够运行。正是因为这个天才的认识,才有了Map and Reduce算法。借助该算法,Google几乎能无限地增加计算量,与日新月异的互联网应用一同成长。


    算法并不局限于计算机和网络

    举一个计算机领域外的例子:在高能物理研究方面,很多实验每秒钟都能几个TB的数据量。但因为处理能力和存储能力的不足,科学家不得不把绝大部分未经处理的数据丢弃掉。可大家要知道,新元素的信息很有可能就藏在我们来不及处理的数据里面。同样的,在其他任何领域里,算法可以改变人类的生活。例如人类基因的研究,就可能因为算法而发明新的医疗方式。在国家安全领域,有效的算法可能避免下一个911的发生。在气象方面,算法可以更好地预测未来天灾的发生,以拯救生命。

    所以,如果你把计算机的发展放到应用和数据飞速增长的大环境下,你一定会发现;算法的重要性不是在日益减小,而是在日益加强。

    展开全文
  • 蒙特卡罗和重要性采样

    万次阅读 2014-10-08 22:08:20
    重要性采样是非常有意思的一个方法。我们首先需要明确,这个方法是基于采样的,也就是基于所谓的蒙特卡洛法(Monte Carlo)。蒙特卡洛法,本身是一个利用随机采样对一个目标函数近似。例如求一个稀奇古怪的形状的...

    重要性采样是非常有意思的一个方法。我们首先需要明确,这个方法是基于采样的,也就是基于所谓的蒙特卡洛法(Monte Carlo)。蒙特卡洛法,本身是一个利用随机采样对一个目标函数做近似。例如求一个稀奇古怪的形状的面积,如果我们没有一个解析的表达方法,那么怎么做呢?蒙特卡洛法告诉我们,你只要均匀的在一个包裹了这个形状的范围内随机撒点,并统计点在图形内的个数,那么当你撒的点很多的时候,面积可以近似为=(在图形内的点的个数/总的点个数),当你撒的点足够多的时候,这个值就是面积。 这里假设我们总有办法(至少要比找解析的面积公式简单)求出一个点是否在图形内。另一个例子,如果你要求一个稀奇古怪的积分,没有解析办法怎么办?蒙特卡洛法告诉你,同样,随机撒点,你一定可以知道f(xi)的值,那么这个积分的解可以表示为=(b-a)/点的个数*sigma[f(xi)],其中b,a为积分的上下限。

    好了,知道了蒙特卡洛法,下面来说重要性采样的前提一些内容。

    很多问题里,我们需要知道一个随机变量的期望E(X),更多时候,我们甚至需要知道关于X的某一个函数f(X)的期望E[f(X)]。问题来了,如果这个X的概率分布超级特么的复杂,你准备怎么做呢?积分么?逐点求和么?听上去挺不现实的。这时蒙特卡洛法跑出来告诉你,来来来,咱只要按照你这个概率分布,随机的取一些样本点,再sigma(p(xi)*f(xi))不就可以近似这个期望了么。但问题又来了,你怎么”按照这个概率分布“去撒点呢?

    经典蒙特卡洛法是这么做的,首先把这个概率分布写成累计概率分布的形式,就是从pdf写成cdf,然后在[0,1]上均匀取随机数(因为计算机只能取均匀随机数),假如我们取到了0.3,那么在cdf上cdf(x0)=0.3的点x0就是我们依据上述概率分布取得的随机点。

    举个具体例子吧,例如我想按照标准正态分布N(0,1)取10个随机数,那么我首先在[0,1]上按照均匀分布取10个点

    0.4505    0.0838    0.2290    0.9133    0.1524    0.8258    0.5383    0.9961    0.0782    0.4427

    然后,我去找这些值在cdf上对应的x0,如下

    -0.1243   -1.3798   -0.7422    1.3616   -1.0263    0.9378    0.0963    2.6636   -1.4175   -0.1442

    那么上述这些点,就是我按照正态分布取得的10个随机数。

    OK,你按照上述方法去找cdf吧。

    我如果这么说,你肯定会疯掉。因为,如果概率分布都超级特么的复杂,累计概率分布岂不是会更特么不知道怎么求了!

     

    然后,我们开始了重要性采样的介绍。

    让我们回顾一下期望的求法E(f(x))=sum( p(x) * f(x) ) dx。那么,现在我们引入另一个概率分布s(x),相比于p(x),s(x)是非常简单能找到cdf的。那么我们变形一下E(f(x)) = sum( p(x) * f(x) / s(x) * s(x) ) dx ,再仔细看看,这个求f(x)的期望变成了,求在s(x)分布下,p(x)*f(x)/s(x)的期望。

    重要性采样的关键就在这里,把对f(x)不好求的期望,变成了一个在另一个分布下相对好求的期望。

    这样,s(x)能找到cdf,那么就用上面提到的那个方法去采样,然后对应的,求出h(x0)=p(x0)*f(x0)/s(x0)的值,最后再sigma(s(xi)*h(xi))就可以近似E(f(x))了。

    举个例子:就上面那个求积分的问题,用重要性采样解释还可以有很好玩儿的内容。上面求积分时,我们是用的均匀采样的方法,注意这个时候自变量X已经被我们弄成了随机变量,f(X)就是这个随机变量的函数。但是,大家可能会注意到这个问题:如果这个f(x)长的比较特别,例如是个高斯函数N(a,b^2),只不过它的方差b特别的小,但是自变量范围特别大。这时的均匀采样,大多数点都会落在了概率很低的地方,落在a附近的点很少。这样,均匀随机采样法得到的期望很有可能会和真实值差得非常远。(唉,这个问题想不明白的画图,还想不明白的做实验)。那么,此时,如果我们换一个概率,不用均匀采样法,用,例如说N(a,b^2)分布,用上述方法重要性采样一下。那么落在a附近的点会超级的多,这样,得到的期望会很好的近似真实值。

    当然,上面那个分布是我随口说的,大家都希望那个重要性采样的概率函数可以无限的逼近真实分布。但既然能表示真实分布,我们就知道cdf了,谁还需要重要性采样呢?所以这只是理论情况。实际上,一般大家用的方法都会根据具体的情况选择。我所见到的,大多都是利用某一种距离/相似度度量函数,然后把这些距离利用某种方法变换成概率分布。这么说还是太抽象,举例吧:

    我有一个特定人的模板,我希望在一个给定的区域内寻找这个人。那么粒子的状态就是位置坐标(x, y)和大小(w,h),每个粒子的权重:

    首先,求这个粒子的直方图,再和模板求一个距离,巴式距离啦,EMD啦,随你选。假设这个值为x。

    然后,计算K*exp^(-alpha*x)。这个方法被称为likelihood map,就是说分数越小则概率越高,分数越大概率越低。反正K和alpha积分从0到正无穷的和是1就可以了。这样每个点都有了一个概率值。

    且慢,现在还不是概率值。所有粒子的和不是1,所以只能叫权重值。然后再归一化一下,就成为了概率值。

    最后这个值就是我们要找的s(x)。p(x),f(x),s(x)都有了,这样我们就可以比较轻易的利用s(x)的分布撒点,求期望了。

     

    当然,在很多文章里这些概率都是带着条件概率的,有的利用马尔科夫性,只和前一帧的状态以及观测相关,有的则写成和以前全部状态相关。但是原理基本是一致的。s(x)的选取也各不相同,具体问题具体分析了。

    展开全文
  • 粒子滤波与重要性采样

    万次阅读 多人点赞 2016-06-02 22:52:48
    现在我们明白了,粒子滤波的结构实际上是加了一层重要性采样的思想在里面的蒙特卡洛方法。 现在我们要解决的就是如何估计这个相似程度的问题。粒子滤波在这里了很牛逼的一件事。我们不知道这个东西原本的分布是...

    最近又复习粒子滤波,感觉实际代码和推导总是有那么一些差距那一理解,主要是好好的分布为什么一转就变成特征似然程度了。这个东西让我们理一遍

    之前理解粒子的思想可能是有一些问题的,对于一个未知分布来说的话,我们想要知道这个分布的期望,好,现在我们均匀的去撒粒子吧,其实蒙特卡洛方法来说,我们只要对大量的粒子求平均就可以知道我们想要分布的期望了。但是在粒子滤波的问题里面,我们偏偏对每一个粒子反馈的情报加上了一个权,这个权代表我们-是不是很信任这个分布。再看这个权的分布形式,实际上就是它和目标的相似程度。现在我们明白了,粒子滤波的结构实际上是加了一层重要性采样的思想在里面的蒙特卡洛方法。

    现在我们要解决的就是如何估计这个相似程度的问题。粒子滤波在这里做了很牛逼的一件事。我们不知道这个东西原本的分布是什么,,但是我们可以观察某一个特征啊,如果这个特征的分布能够代表原来的分布的话,我们是不是可以近似这样来理解!!!!!!!

    让我们一步一步理解这个思路:
    蒙特卡洛方法是什么,就是试验,用大量的样本去替代概率。
    比如说,我们想要知道一个骰子投出点数的期望,我们就不断去投这个骰子,把每一次的结果平均取来,就可以知道这个筛子的期望了。
    在这个过程之中,有一个非常重要的点:为什么我们通过简单的平均就能够推算出这个骰子的期望呢?原因在于每一次单独实验的概率分布都是符合骰子本来的概率分布的。对于蒙特卡洛方法来说,样本的分布和要求取期望的分布一致至关重要。

    蒙特卡洛方法应用的另一个常用的例子是使用计算面积。
    就是这个玩意:
    这里写图片描述
    我们用维基百科蒙特卡洛方法词条的这个图来说明。如果我想要知道这个四分之一圆的面积,一种方法当然是测量半径,然后用圆面积公式 4πr2 来算。但是假设我们回到古代,并不知道 π 的具体数值。就没有办法算圆的面积了么?这时候我们可以用蒙特卡洛方法解决,在一个矩形空间均匀撒下粒子,然后计算落在圆面积里面的粒子和撒下所有粒子的比值,这个比值刚好就是圆面积和这个矩形空间面积的比值。于是,圆的面积就可以被反推回来了。
    这个例子实际上是由一定误导性的,原因在于:这不是最朴素的蒙特卡洛方法!!为什么呢?试问:每一个粒子遵从的是什么分布?为了让求值正确,我们投放粒子的时候是在整个空间均匀分布的。但是,属于圆的部分在这个矩形空间并非是均匀分布的。换而言之,这两个分布,不一样啊,那还算什么蒙特卡洛方法呢。那么这套算法究竟是经历了什么,让它又歪打正着算出正确的结果了呢,这就是我们要重点讨论的问题:重要性采样。

    在此之前,我们还需要绕个圈子,好更好的引出我们的问题。蒙特卡洛方法其实核心就在于解决一个分布的期望问题,而且,这个分布的概率分布还他妈必须是已知的!(或者你能够确信我们的样本一定一定是和要求期望的分布时一致的)
    比如,一个变量 x 的概率分布是p(x),我们要求它的期望怎么求?按照定义

    E(x)=xp(x)dx

    很好,现在我告诉你,这个 p(x) 形式巨复杂巨难算,臣妾根本积不出来(在高维的情况下尤甚)。那好,我就们不得不祭出蒙特卡洛了,蒙特卡洛告诉你,想知道期望,按照这个分布得到一些样本,平均就好了嘛。问题又来了,我们该怎么按照这个分布生成样本呢。
    比如,我们想要按照正态分布生成一些样本,继而通过这些样本获取它的期望。但是,就计算机的角度来说,我们只能够得到均匀分布的随机数如何从均匀分布的随机数得到高斯分布的随机数呢?概率累计!

    这里我们使用:http://blog.csdn.net/tudouniurou/article/details/6277526 的一个例子
    例如我想按照标准正态分布N(0,1)取10个随机数,那么我首先在[0,1]上按照均匀分布取10个点

    0.4505 0.0838 0.2290 0.9133 0.1524 0.8258 0.5383 0.9961 0.0782 0.4427

    然后,我去找这些值在cdf上对应的x0,如下

    -0.1243 -1.3798 -0.7422 1.3616 -1.0263 0.9378 0.0963 2.6636 -1.4175 -0.1442

    用画图来表述的话,是这样的:

    可是问题在这里:本来这个分布我就积不出来,你还要我积分,有啥用呢。重点来了!积不出来,我可以试着用其他方法啊,让我们改变一下求期望积分的形式:

    E(x)=xp(x)q(x)q(x)dx

    对,我们把这个积分项目上下乘以了一个q(x),这是我们已知的一个分布,并且这个分布在数学上来说是可以随意设定的。那么,这个式子其实可以理解为:现在我们求取的是 xp(x)q(x) 的期望,这个变量是按照 q(x) 分布的。看不太明白?让我们来看一个例子,这个例子出自
    Udacity的机器人人工智能教程-CS373 Artificial Intelligence for Robotics Programming a Robotic Car:
    这里写图片描述

    绿色的点是一个机器人,看色的线代表激光发出的测量线,现在它被随机放在了地图的一个位置,它想要知道自己到底在哪里,于是,它就开始猜测:由于没有任何的先验信息,所以一开始,它可能存在与房间的任何一个角落,每一个红色的点即代表机器人对自己所处位置的一个猜想,这就是我们在蒙特卡洛方法里面所提到的样本。而猜测(红色点)的分布是均匀的,也就是之前式子里面的 q(x) 分布。当然,每一个猜测有好有坏,不然我们简单的把所有粒子一平均,机器人对自己位置的猜想肯定一直会处于整个房间的最中心了。 p(x)q(x) 这部分我们称之为权值,就是为了衡量每个猜测的好坏,也就是衡量我们随意决定的分布和真实分布之间的相似度。
    在这里其实还有一个小问题的,我们应该如何去衡量 p(x)q(x) ,在机器人定位问题里面, p(x) 我们根本不知道!不知道的东西怎么去衡量啊,粒子滤波在这里有很牛逼的一招:这个不知道,我们可以抓特征啊。在这个问题里面,由于机器人知道整个房间的地图,又能探测到自己周边环境的样子,所以它可以把 p(x)q(x) 转换为计算当前猜测点的特和探测器感知的周围环境的似然程度!粒子滤波器牛逼的地方就在这里:我不知道真实情况怎么分布的,但是我可以追踪你的一个特征,并且我假设:这个特征的分布期望和原始目标的分布期望是一致的。这就好像是老师叫你去操场上找人,但是你并不知道要找的人会在操场哪里出现,而且最关键的是你还不认识那个人。这时候老师说,不知道不认识不要紧,你只要找那个穿着红衣服的人就可以了。然后你就去操场一看,哟,红衣服在这里,虽然你不认识他,但是你认为红衣服是他在这个状态空间的唯一特征,所以你还是准确找到了这个人。
    这样, p(x)q(x) 在实际计算中实际上就近似于计算特征的相似程度了。在这个问题里面,就是比较猜测位置姿态所应该得到的环境信息和实际得到的环境信息之间的差异。
    当然,为了更好的性能,我们还是希望 p(x)q(x) 尽可能接近于1,也就是 q(x) 尽可能接近于原始 p(x) 的分布的,这个问题我们可以通过粒子重采样解决。在这里我们不深入讨论,只给出重采样迭代之后的效果:
    这里写图片描述
    这里写图片描述
    这里写图片描述
    这里写图片描述
    这里写图片描述
    这里写图片描述
    可以看到,在移动过程中,机器人的猜测渐渐全部收敛到机器人的真实位置了!
    真他妈好玩。

    最后回到之前我们提到的算面积那个问题,它实际上也是采用了重要性采样的思想,而权重分布变成了0-1分布,所以得到了之前的结果。
    均匀的撒粒子只是一种折中的方法。在不知道原始分布是什么样子的情况下,均匀分布的粒子最具有适应性,为了提升性能,我们在做重采样的时候,依然会不断优化粒子,使其趋近于原来的概率分布。这样使其不断接近真实分布,从而完成整个蒙特卡洛的思路。

    展开全文
  • 经验的重要性

    千次阅读 2016-09-26 14:05:39
    2. 物理课上的实验 3. MBA课中的案例分析 为什么要学习案例: 1. 人类的逻辑推理能力并没有那么好,掌握了理论,也不能很好的应用实际生活中。 2. 人类更擅长总结规律,以及经验复制。并将环境和理论映射关联,在...
  • 论“事前-事中-事后”的重要性

    万次阅读 2018-09-08 17:33:31
    所谓事前,就是事情之前应该有统筹的规划,考虑可能出现的问题和困难,最好提前做实验验证下,以保证在真实现场不出问题,或者即使出现问题也有应对方案,不至于手忙脚乱、大动干戈。 所谓事中,就是事情的过程...
  • 为什么以这个为主题写.是因为最近在一个购物网,需求没有做好,导致前台的时候商品与图片是1对1的关系,后台添加的时候有很...而且需求要的到位,需求的思维严禁程度至关重要.. (下面为转载)  一、
  • 论机器学习中数据的重要性

    千次阅读 多人点赞 2020-06-13 15:51:50
    ​ 现如今,机器学习在越来越多的领域中凸显出其不可替代的重要性,人们开始从各领域渗透机器学习的典型案例,希望其大规模投入使用,而好的训练结果与坏的训练结果的区别并不在于你的模型好坏,而往往是取决于你...
  • 论互联网安全的重要性

    千次阅读 2015-06-14 20:17:31
    论互联网安全的重要性 当今,计算机领域什么最火?当属人工智能了,纵观各大IT巨头google,facebook,apple,Baidu都有自己的人工智能实验室,google有谷歌大脑,其主要计划是研究当今最顶级的技术,比如无人驾驶汽车...
  • 建模的重要性及意义

    万次阅读 2018-06-07 17:40:15
    建模的重要性? 如果你想搭一个狗窝,你备好木料、钉子和一些基本工具(如锤子、锯和卷尺) ,就可以开始工作。从制定一点初步的计划到完成一个满足适当功能的狗窝,你 可能不用别人帮助,在几个小时内就能够实现...
  • XGBoost输出特征重要性以及筛选特征 1,梯度提升算法是如何计算特征重要性的? 使用梯度提升算法的好处是在提升树被创建后,可以相对直接地得到每个属性的重要性得分。一般来说,重要性分数,衡量了特征在模型中的...
  • 在打比赛的时候一直贯穿的思考,大概就是判别各个特征的重要性。 在建立模型之前,特征重要性能够帮助训练模型,防止过拟合,提升模型的RUC效果。 建立模型之后,特征重要性能够增强模型(集成模型 非深度学习模型...
  • 研究算法的重要性

    千次阅读 多人点赞 2017-04-29 22:28:06
    借用李开复老师的一篇阐述算法的文章,解释算法的重要性。 算法的力量,李开复聊算法的重要性 算法的力量 算法是计算机科学领域最重要的基石之一,但却受到了国内一些程序员的冷落。许多学生看到一些...
  • 谈谈工作总结的重要性

    千次阅读 2013-05-29 17:28:41
    去年刚接触地图,工作中主要是学习阶段,有太多的IDEA,空余时间也过很多的实验、尝试,当时我的mentor一直强调我一定有输出。那个时候这句话确实听进去了,不管什么都会写个文档,当然了文档主要是记录了很多...
  • 其中一些方法基于特定的模型,例如线性回归模型中的回归系数、基于树的模型中的增益重要性或神经网络中的批处理范数参数(批处理参数通常用于NN pruning,即神经网络剪枝压缩)。其他一些方法是“通用的”,它们几乎...
  • 前天用clementine 试了一次生成决策树,结果粗来只有一个根节点,如下图。 ...我不用假数据也能交毕业论文啦!!! 我还没了解修剪严重的含义,写此贴帮助那些遇此问题一筹莫展的童鞋
  • python实现RF,并计算特征重要性

    千次阅读 2018-02-24 20:42:55
    随机森林模型的训练以及特征重要性import xlrd import csv import numpy as np import pandas as pd import matplotlib.pyplot as plt from scipy.interpolate import spline #设置路径 path='/Users/kqq/Documents...
  • 电磁兼容的重要性

    千次阅读 2013-12-06 22:19:22
    电磁兼容达标认证已由一个国家范围向全球地区发展,使电磁兼容与安全、环境适应处于同等重要地位。 例如,欧共体将产品的电磁兼容要求纳入技术法规,强制执行89/336/EEC指令,规定从1996年1月1日起...
  • 这篇文章主要讲述Navicat for Oracle设置唯一约束和设置某字段为递增序列。文章主要以图文为主,虽然都是非常简单基础的文章,但还是希望对你有所帮助。主键是所有组成主键的列都不能包含空值,而如果唯一约束由...
  • 国外十大高校人工智能实验室及其代表人物一览
  • CSAPP 六个重要实验 lab5

    千次阅读 2014-10-10 02:02:18
    然后看看对block的探测学习 http://blog.csdn.net/cinmyheart/article/details/38174421  The only file you will modify and turn in is mm.c.  Your dynamic storage ...
  • 1. 麻省理工学院计算机科学与人工智能实验室(CSAIL) 2. 卡耐基梅隆大学机器人学院(Robotics Academy) 3. 斯坦福大学的人工智能实验室(SAIL) 二、国外市场派 1. 谷歌DeepMind人工智能实验室 2. 微软Microsoft ...
  • 一个例子说明FPGA中PLL的重要性

    万次阅读 多人点赞 2012-05-02 11:11:51
    PLL的重要性 PLL,即锁相环。是FPGA中的重要资源。由于一个复杂的FPGA系统往往需要多个不同频率,相位的时钟信号。所以,一个FPGA芯片中PLL的数量是衡量FPGA芯片能力的重要指标。 今天,我结合一个例子,来活生生...
  • 在一个大系统中,需要针对每个用例分析模型吗?这一点在你的书中没有提到呀,也许是我看的不认真吧。 (青润) 17:11:10这一点,我的书中写了。 (青润) 17:11:44不过,不够明确,这也是另外一个朋友三个月前提出来的...
  • 实验三 数据库系统设计综合实验 1、实验目的 通过实验,使学生掌握数据库系统设计和开发的一般方法,能够设计并实现简单的数据库系统。 2、实验要求 熟悉实验实验环境,掌握实验预备知识,了解实验中故障排除的...
  • 互联网时代个人信息安全的重要性

    万次阅读 2017-10-18 16:09:20
    社会工程学常常被人说成是一门艺术,很多人可能都认为自己没有艺术细胞,因为大家对艺术的理解就是诸如绘画、摄影、诗歌等领域,其实社会工程学也可以被归为艺术的一类,只要你能把一个项目或者说工程的精致,那...
  • 如何理解 重要性采样(importance sampling)

    万次阅读 多人点赞 2011-03-25 13:22:00
    重要性采样是非常有意 思的一个方法。我们首先需要明确,这个方法是基于采样的,也就是基于所谓的蒙特卡洛法(Monte Carlo)。蒙特卡洛法,本身是一个利用随机采样对一个目标函数近似。例如求一个稀奇古怪...
  • 计算机组成原理实验:微程序控制实验

    千次阅读 多人点赞 2021-02-07 15:20:32
    学生实验报告 实验课名称:计算机组成原理 实验项目名称:微程序控制实验 一、实验名称: 微程序控制实验 二、实验目的: (1)掌握微程序控制器的组成原理。 (2)掌握微程序的编制、写入,观察微程序的运行过程。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 328,177
精华内容 131,270
关键字:

做实验的重要性