May 30, 2010

[读书笔记] 游戏测试 Part 2:测试技术

Book:Charles P. Schultz, Robert Bryant, Tim Langdell, Game Testing All in One(周学毛等译, 清华大学出版社), Thomson Learning


  • 测试技术
    在Intellivision平台上有一款曾经的畅销游戏名为Astrosmash,由于程序员在开发时假设没有玩家能得到达到一千万点,因此他并没有编写处理得分溢出情况的代码。而当游戏发布几周后,就有一些顾客开始打电话抱怨,当他们得分超过9999999点时,得分显示的是负数、字母或非数字符号。而事实上,由于该游戏允许玩家以慢动作玩游戏,使其更易于积累到高分数,因而更易触发该缺陷。由此,该游戏的作者约翰·索尔得到了一个深刻的教训:用户总会让你吃惊。
    理想情况下,玩家可能会希望开发者做完所有可能的测试工作,扫清所有可能触发的Bug;但事实上,由于开发周期、成本等因素,使得这成为一个不可能完成的任务,甚至潜在测试集本身的数量也不允许测试团队做完所有的测试。因此,他们创造了一些十分有用的测试设计技术,来帮助减轻测试的压力,以接近完美的测试。

    1)组合测试:
    可选择是游戏的一大魅力所在,如在典型的RPG游戏中,玩家可以选择人物的性别、职业、服装、武器、初始属性值分配和所属战斗阵营等。但是这诸多的可选配置就给测试团队带了一个极为头痛的问题。假设有2种性别(男、女)、2种职业(法师、战士)可供玩家选择,那么需要测试2(2×2)种可能组合;那么,如果额外地提供2种可选的服装(丝绸、皮革),就需要测试8(2×2×2)种可能。完全的组合测试是一个无比庞大的指数级增长,它既不现实也不经济。但其实,只要测试覆盖了足够的功能,就可以将测试集做得小一点。配对组合测试提供了这样一种可能。
    配对组合测试的基本思路是将可选值进行配对,得到测试集必须符合的条件集,那么如果缩小后的测试集满足这些条件,就认为它是正确的。比如上文提到的例子,它的测试集必须符合的条件就如下图(左)所示,而下图(右)则是一个符合要求的测试集表格,但它只有4条测试路径,却涵盖我们所关心的所有可选功能。
                  
    事实上,对于任意的可选参数集,都能通过一些简单可循的步骤创建任意大小的配对表格,生成令人满意的较小的测试集。并且,有一些预先构造好的表格模板可供选择,只需要简单地替换参数名称和值就能生成你想要的测试集;还可以选择组合工具Allpair,自动生成测试集。当然,这些并不重要,重要的是配对组合测试的方法可以节省掉大量的时间,将测试员从重复的冗余的测试中解放出来,而将精力投入到其他更值得关注的地方。
    不过,有时完全的组合测试是必要的,比如对于一些对游戏而言十分重要的特征值,但这通常只占总特征的不到10%。测试团队通常会选择混合的方式,即对关键特征作完全测试,对其他普通特征作配对测试。有时,10%关键特征会用掉80%测试路径,而90%普通特征却只能共享剩余的20%,但这是合理的,因为这些关键特征往往是全新的富有创造性的,同是也是最容易出错的。

    2)测试流程图(TFD):
    与组合测试不同,测试流程图是从游戏者的角度来描绘游戏行为的一种方式。如果多个游戏或特性中有相同的行为,测试员可以重复使用TFD;且只要正确的游戏条件和行为没有改变,TFD就保持不变,由此生成的测试路径就始终有效。
    TFD通常使用专门的开发制图工具处理和分析,它大致包括流程、事件、动作、状态、终结符等要素。一张较完整的TFD如下图所示:
           
    TFD需要配合数据词典才能发挥功效。数据词典对TFD集中每个独特命名的初始元素提供了详细的描述,尤其对于do条目定义了需要执行的操作,对check条目定义了测试员所需检查的目标。如定义check条目DropSound为:检查该项目是否已做丢弃声音。
    那么,TFD上的每一条路径就代表一个测试流程,可以通过简单地复制粘贴数字词典上对应的描述,获得一份详细的测试设计文案。对于测试路径有几种经典的可选策略:
    a. 最小路径:这种策略生成覆盖TFD中所有流程的最小路径,即TFD中的每一个地方至少被经过一次。它的测试次数在众多策略中是最少的,但它带来的问题是由于路径较长,有时直到项目的后期,才能发现一些早就在测试路径中存在的问题。
    b. 基线路径集:基线路径是一条从输入终端到输出终端的直接路径,在不重复或往返循环的情况下经过尽可能多的区域,由此往复直到基线路径集覆盖流程中所有的地方。它比最小路径复杂些,但能避免最小路径的延后发现缺陷的问题,不过,由于不同路径的区别操作可能造成最终发现的Bug成因暧昧。
    c. 专家结构路径:这一路径只是一个基于专业人员的经验制定的测试路径,它不必涵盖流程中的所有地方,但一定一次或多次经过专业人员认为最有可能失败或出现问题的地方。它往往是具有偏见的,但却很经济合算。因此,专家路径经常会联合前两者使用。
    测试流程图的方法对于测试游戏的状态转化、操作流程和其他可重复的功能尤其有效。

    3)净室测试:
    净室测试是从一种被称为“净室软件工程”的软件开发时间中提取出来的技术,其最初目的是在项目中运行软件,以进行平均无故障时间(MTTF)的测量。在游戏测试中,净室测试被用来解决游戏玩家在运行了许多时间后发现官方未公布的缺陷这一问题。它的目的在于发现、根除很有可能会被用户发现的缺陷。这些缺陷通常存在于玩家经常会使用到的游戏功能中,这也就要求测试团队按照一种玩家的方式去运行游戏的测试。
    首先要获得各个游戏功能的使用率。这可能基于测试员研究游戏玩家而得到的实际数据,也可能来自于个人关于这款游戏如何运行的期望,以及游戏生命周期中可能存在的玩法的变化。但,通常有三种定义和获取的方式:
    a. 基于模式:这指游戏的不同模式,如对战、RPG、多人等。不同模式的游戏针对的用户群不同,因此习惯、关注点、所需提供的功能都不尽相同,比如多人游戏的玩家可能会比单机玩家更多地在意玩家间的交互方式。
    b. 基于玩家类别:Richard A. Bartle将多用户玩家分为四类,进取者、冒险者、社交者和杀手。他们所热衷于的游戏功能就很不同,冒险者很关心游戏的艺术特效和美景,而杀手才不在乎,他只要体验杀戮的快感就万事大吉了。当然,还有其他的分类,比如键盘杀手和自定义者,游戏世界和真实世界是一样的,各种鸟都有。
    c. 基于现实:这种方式比较直接和直观,它通过记录玩家的偏好并统计,以用于进一步的测试和改进。
    得到使用率后,就可以利用其去选择测试步骤、数值、细节,且把它们按顺序排好形成能反映出玩家用法的测试情况。比如在使用组合测试时,使用率高的选项就应当在测试集中占有较大的比重;而在使用流程图测试时,使用率高的地方就应当被更频繁地经过。

    4)测试树:
    测试树提供了一种可以很好地反映存在于游戏功能和原理之间的树形关系。通过沿各种不同的从树的定点到树的每一个终点的路径测试,可以检测这些结构的行为方式。在游戏测试中,使用测试树有三种不同的目的。
    a. 测试用例树:它记录了测试用例和游戏特点、原理和功能之间的层次关系。这种测试已经成熟并且文档化了。每一次开发小组给测试者发送一个新版本,测试树就会被使用。测试者根据缺陷补丁或者版本中引进的新功能,决定其影响的范围以及要执行的测试。并且,测试用例树也很好地表型了游戏本身的构造方式。如下图所示,针对一款战役游戏给出了一个粗略的测试用例树。那么,当有关小型战斗游戏模式的代码被改动后,测试者就可以通过查看测试用例树明确地知道,他需要进一步地测试地图、玩家数量、种族、游戏选项和胜利条件等。当然,有时,这种检测可以是向上的,比如一张新地图的加入,就需要执行所有战役模式的测试。
            20105301632013
    b. 特征树:这种树用于反映游戏中的一些逻辑特征,或者说是游戏规则,典型地如RPG中常见的技能树、任务树和升级树等。特征树可以被很方便地翻译成测试文案,测试方法通常是通过替换每一个特征条件直到满足结论成立,这样,就能找到有缺陷的条件。如下图(左),给出了一个十分简单的技能升级的特征树,只有当人物的白魔法能力达到2级,同时黑魔法能力达到3级,才能修习蓝魔法。那么这一规则的测试就如下图(右)所示。
            20105301642134    20105301642333
    c. 设计测试树:这种树可以提高对一个复杂的游戏特征的理解,并且给潜在的混乱职能带来秩序,尤其是在关于与其他游戏规则,原理和职能交互作用的部分。测试员通过它生成测试用例,用以查明狭小范围内的游戏行为方式中潜在的缺陷。比如在RPG中,一种魔法会因为不同的人物、地点、武器和对象,而产生不同的伤害效果。那么,测试者就可以根据这些画出一个针对该魔法的树,修建无效的支路,最后依次执行所有的生成校验该魔法适当行为方式的测试。

    5)随机测试:
    随机测试(Ad Hoc Testing),有时又称综合测试(General Testing),是以一种较为主观的方法来搜索错误。这种方法认为,就算拥有最全面、详尽的测试计划和设计,依然可能会有疏漏;而随机测试,允许测试员作为一个个体,在对游戏执行系列客观测试的过程中,探测那些可能已出现过的调查路径。通俗地说,当测试员想着“如果我做#%&$,会怎么样?”时,随机测试提过了一个回答诸如此类问题的机会。
    随机测试有两种主要形式,自由随机测试(Free Testing)和定向随机测试(Directed Testing)。
    a. 自由随机测试:又称右脑测试,因为其是否直观和主观,是一种有专业游戏测试人员“即时”设计的“可与原始数据分离”的测试。这种测试往往需要锐利的眼光,一种游戏测试员的直觉;要求测试者在混乱中创造秩序,有目标有记录;并且始终保持孤身作战,这是自由测试的一个重要原则,避免集体审议,使得测试员保留个人作为玩家的特征,更容易发现一些违反直觉的游戏缺陷。
    b. 定向随机测试:这种测试方法使得测试者像一个侦探般工作,它通常用于解决某一特定问题或者查找特定解决方案,通常是因为一个或多个测试员报告了游戏中一个“偶然的”死机情况但原因不明后开始的,比如回答“场景切换的时候有时会崩溃”。测试员会先就结果作出假设,再一个个地验证它们。这个过程十分依赖测试员的经验和敏锐的嗅觉。共享信息是必要的,因为这方便地切断一些别人尝试过的假设,帮助更快的解决问题。

    6)性能测试:
    游戏性能测试与上文提到的所有测试技术所关注的焦点均不同。它关注的是“游戏运行得好不好”,而不是“游戏是否能运行”。差别是明显的,并且前者似乎更加重要,而且往往是带有主观特性的。性能测试的大部分是指对游戏平衡性的测试,也就是“游戏会不会太难或者太简单”以及“游戏中的各个可选功能是否均有可选之处”等。测试员所需要做的,是尽量准确地描述游戏的不平衡点,而不是给出过于精确的改善意见。
    还有一些性能测试可以通过外部测试进行,也就是给除了开发团队和测试团队之外的人玩,比如公司的营销部。这也就是我们经常看到的外部Beta测试,它包括封闭的和开放的。封闭测试的测试员经过仔细筛选,而开放测试通常在封闭测试之后进行,面向其他一些感兴趣的人群。外部Beta测试依赖于有效的管理,否则,会带来大量无用的数据。

好游戏取决于有创意的设计、严谨的测试和有力的营销。设计带来亮点,测试巩固亮点,营销贩卖亮点。虽然Bug是挖不尽的,但我们仍希望它是接近完美的。因此,如若没有deadline,测试团队的工作将是无穷无尽的。也因此,使得Time-critical的测试成为一项极为繁重的工作。这迫使业界总在探索更有效的测试技术,如何节约成本,如何避免遗漏,等等。缺陷触发、自动化测试、捕获/回放测试等技术相继诞生。那么,这样一个没有Bug的未来是否值得展望呢?答案犹未可知。

May 29, 2010

[读书笔记] 游戏测试 Part 1:基本概念

Book:Charles P. Schultz, Robert Bryant, Tim Langdell, Game Testing All in One(周学毛等译, 清华大学出版社), Thomson Learning


为着这学期软件工程课8000+字的Term Paper看的这书。前日去图书馆原是想借些正经软工书的,翻了满架子的书竟是本本写得都像畅销书,还真如众人所说的,真水。想看些架构设计的书,竟也没找着。稍有些质感读起来也不太枯燥的,就只有一些游戏方面的书,有图,还有些我知晓的例子。那便看吧。

测试为什么重要呢?因为游戏会出错,出各种各样的错,并且即使经过了漫长的尽可能全面的测试,游戏依旧会出错。但这恰恰说明在发布前的测试是十分必要的,不管是对于游戏出版商,还是对于开发团队而言。一款出色的游戏会得到褒奖,而一款充满Bug频频跳闸的游戏则会给开发团队带来漫天的骂声,销售额和利润也随之蒸发。

测试为什么对于游戏尤其重要呢?其实测试对于任意一款应用软件都是相当重要的,但是没有一款应用软件像游戏这样拥有庞大、多样、富有压力的客户群。不要指望玩家规规矩矩地按照手册上写的点击菜单,你永远都无法完全预测到每一个玩家所有可能的变态操作——他们可能在物品交易的过程中突发奇想地丢掉正在交易的物品,而导致玩家数据错误。因此,游戏测试是任重而道远的。
 

  • 游戏测试员的任务
    作为一名出色的游戏测试员,需要从一名游戏玩家开始,但绝不仅止于此。游戏测试员需要诀窍来发现问题、记录并报告Bug、报告测试进展和帮助开发者发现并确定Bug具体位置。在游戏发布之前,测试员需要反复地做以下这些事情:
    201052710520821 

    1)Play:游戏测试员的“玩”较普通玩家是少有选择性的,测试方案从一开始就规定了测试的目的和步骤,如查探某一游戏中的地图、检查某个特定的原则是否得到执行、或者寻找某一类特殊的问题。有些测试甚至是十分具体的,比如对游戏界面的测试,就依赖于敏锐的观察和对细节的注意,并且往往需要循环重复一些枯燥的按钮和下拉动作,以确定是否存在某些不合理或错误的操作响应。

    2)Identify:游戏测试有两个目的,一为找到游戏代码或设计中的缺陷,二为说明游戏中的各个部分能否正常运行。当在测试过程中发现了问题,游戏就相对地“失败”了,这时需要测试员详细地描述发生该问题的过程和结果。
    当测试游戏的同一部分时,不是每个测试员都能发现同样的缺陷。心理学上认为这是由人的不同性格造成的,并给出了有效的性格测试工。这个工具可以识别一个人是裁判还是感知者。裁判善于组织和作计划,喜欢井然有序和可预测的测试环境,专注于测试内容的细节,提供详尽的测试报告,适合测试用户手册、脚本;感知者则喜欢采用非常规的游戏玩法,测试多种可能和游戏的真实体验,往往不受计划约束,却能发现一些意想不到的珍贵Bug。这两种人是互补的,因此在一个测试团队中往往需要这两种人。

    3)Amplify:这里的“放大”指的是尽可能地使缺陷在第一次被发现时就完全暴露出来,以减少用在这个问题上的时间和成本,这对开发者通常是有益的。为了达到这个目的,通常需要做到两点。首先,尽可能早地执行测试,如当一些新的人物、关卡、功能或子系统第一次被引入时就应当马上进行测试;第二,当在测试过程中发现某个Bug时,应当检查每一个可能触发该Bug的地方,如代码中所有调用包含缺陷的关卡、功能或子系统的地方。

    4)Notify:当测试人员发现问题且能描述它影响游戏的方式时,就需要记录此信息并就此向开发人员通报。这一过程通常通过缺陷追踪和管理软件实现,如业界常用的DevTrack。一份完整的通报包括以下几个重要部分:

    a. 标题:一个描述性强的标题通常很有用,它帮助开发人员快速地定位此缺陷的大致内容。好的标题通常需要包括一些重要的要素,如事件、人物、方式等。这就和撰写报纸的标题一样,像“杭州地震了”这样的标题是不适用的,它让人产生迷惑。而“5月22日杭州发生里氏8级大地震”这样的标题则合格得多,它恰当地表达了这则新闻的重要性和爆炸性。有时还需要更多的细节,如“造成90人死亡”和“城中30余处房屋倒塌”等。

    b. 描述字段:这里包括测试员能及的所有有帮助的细节,人物(战士)、事件(嵌入到内墙的上部)、地点(训练厅)、时间(拜访符咒训练者后)和方式(跳跃)。有时,如果可以,还会描述问题可能的解决方法等。

    c. 缺陷的优先级:优先级的名称和含义对项目而言可能各不相同,但概念是相同的,都是根据其重要性对缺陷进行划分,从而决定它是否被优先处理。“紧急”的Bug可能导致玩家信息的丢失、终止或异常中断游戏等重大缺陷;一个“高”优先级的Bug通常是导致某些严重后果的缺陷,如提交了请求但不能得到请求的东西;“中等”缺陷导致明显的问题,但不会危及玩家的奖励或关卡;“低”优先级的Bug则是正对非常微小的缺陷而言,如一些不容易发觉的拼写错误。但应当注意的是,Bug的严重性等级和优先级是有所区别的,比如主菜单中的拼写错误并不会导致什么严重的后果,但却是一个急需改正的Bug。因此,大多数游戏公司会在对Bug订正排序时联合使用严重性和优先级。

    d. 缺陷的类型:包括需求修改、文档问题、矛盾报告、进一步增强、微小改进、新特征、第三方错误等,对确定缺陷的路径和处理缺陷而言有重要的意义。通常缺陷管理软件会提供一些可选的分类。

    e. 备注:这确保测试员通过添加文件的形式,提供所有有帮助的内容或信息,包括日志文件、包括Bug的录像、操作系统的弹出窗口和错误代码等。

    5)Testify:游戏测试员的工作只是发现并通报缺陷,而真正区分缺陷的优先级的权利则掌握在变更控制委员会(CCB)手中。CCB监督和促使最要紧的缺陷得以完成修复,从而在项目期限到时能交付一个最符合要求的游戏。其成员一般包括来自发展部门、测试部门和项目管理部门的代表,他们对Bug进行仔细检查,对其优先级打分,再交付修改。值得一提的是,这里涉及到游戏测试中另一个重要的原则——有选择的(Optional),有时因为项目期限的临近,使得许多团队放弃修复一些有难度的缺陷。

    6)Verify:这一步指的是在Bug被修复好之后,有测试人员再次对性测试一次,以确定其是否被完全和有效地改正。
     
     
  • 游戏缺陷的类型
    由IBM公司开发的正交分类(ODC)系统定义了多种软件缺陷的分类方法,其中与游戏较相关的大致有八类。每一种缺陷类型或者是执行结果不正确,或者是缺少代码。

    1)功能(Function):功能错误是一种影响游戏性能及用户体验的错误,可能由提供这一功能的代码丢失或不正确造成,如,在触发某一人物技能后,显示技能停留剩余时间的时间条的缺失。

    2)赋值(Assignment):赋值错误指程序所使用的值被错误地初始化或设置,多数发生在游戏开始、进入一个新关卡或一种游戏模式时,典型地如在策略游戏中,对开始的位置单元和可用资源的初始化。错误的赋值将导致对游戏平衡性的破坏。且有时这种错误是隐藏的,难以有程序员发现的,只有通过测试才能找到。

    3)检查(Checking):当代码在被使用前缺少适当地验证数据时,就可能产生检查类型的缺陷,简单地如边界比较,使用<=代替<。

    4)时间控制(Timing):时间控制缺陷与资源的共享、资源的实时管理相关。良好的时间控制应当在加载某些大型资源时,给出进度条,显示正在进行的操作。通常RPG游戏中在人物启动某项特殊技能的时候会给出一个短小的动画,但往往技能切换完成得会比动画快得多,这时错误或缺失的代码讲导致在动画完成前,技能就被启动,这是违反游戏的世界观原始设定(比如关于念魔咒隐身),这是一个典型的时间控制缺陷。

    5)构造/包装/合并(Build/Package/Merge):这类缺陷是由于配置游戏源代码库系统,变更游戏文件管理,或版本识别和控制引起的错误。良好的版本管理和习惯约定能减少或避免出现这类缺陷。

    6)算法(Algorithm):算法缺陷包括一些计算过程或者选择结构中出现的有关时间复杂度或正确性的问题,主要涉及逻辑控制、AI、数值计算、渲染控制等方面。这类缺陷都大部分涉及到游戏功能,其中一些还是隐藏功能,因此大多会考虑写一个专门针对某一算法缺陷的查找脚本,做连续地测试,而不是一个一个地手动测试。

    7)文档(Documentation):文档缺陷不是由不适宜的代码导致的,而是存在于从文件中重新得到的字节型数据或定义的常量,比如在屏幕上显示的文字、音频或供函数调用的读入参数。这些缺陷只能通过仔细地阅读文本、听音频、检查文件和图形,才能被检测到。

    8)接口(Interface):接口缺陷可能在任何一个信息被转移或交换的地方发生。但通常,它的存在是由于模块之间的调用方式有误,比如被传入的参数与调用例程不匹配,或者在传入时使用前没有做合适的数值范围或类型检测等,都可能导致接口缺陷的产生,而且这些缺陷往往是细小且不容易发现的。
     
     
  • 测试阶段与过程
    虽然游戏的大小不等,开发周期也各不相同,小到只需数周就可完成的手机游戏,大到一些大型的MMORPG或平台游戏,有时需要几年的开发时间,甚至屡屡跳票(如暗黑3)。但不管游戏有多大、生产周期有多长,其测试始终遵循相同的基本结构。

    1)试生产阶段:对测试可能的认知是认为测试是在游戏的一个成功部分被开发之后的某一个时间开始的,但事实上,测试始于项目开始之时。许多发生在项目的早阶段的事情,将会为以后测试的好坏定下基调。最好能在项目一开始,就将较多的努力和技术应用于测试活动来修正错误,而不是后来对其做更多的测试,来努力修正它们。
    在这一阶段,需要制定合理的测试计划,包括:决定测试的范围、任命测试主管、决定阶段验收标准、参与游戏设计检查、建立缺陷追踪数据库(关键)、起草测试计划草稿和测试设计。除此之外,还要对游戏原型作模块测试,并且根据测试要求招募或雇佣额外的团队成员。这一阶段的测试结果往往是不成熟的,但却对未来的测试工作有着深远的影响。

    2)测试的开题阶段:这一阶段分为两个部分,测试员准备和开题会议。测试员准备的步骤和开题的议程都记录在测试开题的清单上,可以看到,测试员需要在开题前通过阅读说明书或文档了解被测试的游戏特征,需要测试所需的设备、文件和程序,最后需要阅读由测试专家书写的测试文案。
    开题会议是一个交互式的会议,每个测试的开题都是改善对测试的理解、测试质量和测试执行的机会。通过会议当中的讨论,能提前发现一些在未来的测试过程中可能遇到的问题,并找到补救措施。有统计表明,开题会议实际上节约了测试时间,开题测试的速率是非开题测试速率的1.4倍。

    3)α测试阶段:在α阶段的游戏是成型的,游戏的特征已经被测试和校订了,各种素材也被整合过了。这是整个游戏第一次完备的测试,因此,这一阶段的测试是最繁忙的,也因此严格坚持测试套件中的内容是十分关键的,它能让整个测试过程井然有序。在α阶段,游戏的所有模块至少应该被测试一次。业界有公认的详细的α阶段测试入口标准,涉及代码的平台TRC通过率、QA要求、软硬件相容指标和美术要求等,只有符合该标准才能进入α测试阶段;类似的,也有β测试入口标准和最终测试入口标准等,这对整个游戏的测试阶段起到良好的规划作用。

    4)β测试阶段:此时,开发团队已经在极大程度上停止创造新代码和新素材,而将关注点转移到如何使游戏更完美,也就是到了识别和修正Bug的时候了。在β测试的早期阶段,会有团队以外的玩家参与测试,但大部分的时间会被花在报告Bug并测试装载上。
    这里有一个值得一提的时间点,称为“设计锁定”。当设计锁定状态被宣布后,游戏大方面的测试都已经结束,平衡问题也得到了最好的解决,团队的关注点变为反复地通过实际测试案例来检验版本。在这一状态到来前,项目组需要作出一些重大的决定,如是否要执行最后时刻的特征强化(引入设计师的新构想)、是否砍掉似乎不那么有趣的关卡、哪些Bug将被忽略(难以决定,但时间是有限的)。

    5)最终测试阶段:进入这一阶段的游戏出于典型的发布状态,所有的已知一级Bug(崩溃、暂停、主要功能失灵)和大多数的二级、三级Bug被修复。游戏被宣布处于“代码锁定”状态,测试员充当游戏者和项目组的最后防护线。测试团队将最后一次,在时间允许的条件下,尽可能多次执行所有测试套件。任何在最后阶段中发现的严重缺陷都将导致候选版本被拒绝,Bug修正后最终测试必须从头再做一次。此时,整个团队都处于极度的疲倦中,但唯有大踏步地前进才是最好的取得胜利的方法。

    6)发布证明阶段:这一阶段的测试通常是由平台制作商(任天堂、索尼)来完成的。其测试游戏的代码是否符合TRC,其功能性和稳定性是否合乎标准。通常,此时还会有一些Bug被发现,然后开发商将会与平台经理的客户就Bug进行讨论,开发团队将被要求修复那些“必须被修复”的Bug。这一过程有时会反复多次,直至候选版本被平台制造商认可,成为“正式版”。

    7)公布后测试阶段:游戏发布后,测试依旧不会停止。这也就是我们通常看到的开发商不断公布补丁的时刻,但并不是所有的补丁都用于修复Bug,有时它们是用来为游戏添加新特征的。这一过程会一直持续到游戏的生命周期结束。
     

March 30, 2010

清明将至,雨断断续续地纷纷

近脱产地准备iBT已半月有余,每天做2小时的反复听力现在总算跟得上iBT的语速了。顺便背着单词,拿词汇书啃实在痛苦了些,就把一些阅读里听力里的词和句子记在Excel里然后每天看看,至于为啥要写在Excel里呢,因为这样排布起来比较好看~ 700字的阅读最近看起来也不太吃力了,虽然长句读起来还是有些卡时间有时也会超,我发现我比较喜欢看地理和心理类的文章。

作文就只做了些翻译和句型的练习,看到题目还是没有清晰的头绪,接下去得看些范文再模仿着写下。口语基本没准备,前几日试着录了下,发现自己说中文都很含糊> <,难道你们一直听到我口齿不清啊,我要去画圈圈。。

四个部分里准备地最开心的是听力,因为lecture的内容还是比较有实质的,偶尔还可以收获些谈资,更重要的是可以以此为名看美剧和电影。最辛苦的应该是口语吧,所以迟迟都没有开始,说出第一句话还是很困难的,小时候花了几年,现在长大了心智成熟了但怎么着也要酝酿个几个星期吧。

看多了英语,最近觉得听到中文讲话,偶尔听听日语歌还有一丝不挂都是十分美妙的事情,有种回家的感觉。

这段时间杭州的天气着实奇怪,周一阴周二三雨周四五阴周末晴,循环往复。于是每天起床头一件事就是头疼今天穿什么才不至于热死或冷死。panda抱怨是三峡害的,他小时候杭州的天气绝对是四季分明。自辩老师也抱怨三峡导致了西南干旱。我觉得他们都在理,三峡断了我再游长江的美梦,所以,赶快炸了去吧。

刚又去教五调程序了,原本一直跑得挺好动作识别得也挺好,末了老耿至了,soso竟鬼使神差地首次砸到天花板上的日光灯,接着识别结果就开始紊乱了。小魏说这叫蝴蝶效应。我汗,怎么总这样,真是佛曰不可说啊。

March 14, 2010

两本童话

今晚在UME看的原声《波西·杰克逊和神火之盗》,原本是早早地奔去买记忆中今晚首映的爱丽丝的票的,结果被告知上映日期为3月26,今日上映的是神火之盗。售票小姐一脸疲倦地问我,看否?许是今天UME的人真的很多或者她有隐情。我心想看吧,都远远地跑来了,总不至于只纠结了下近来的记忆力就又坐半小时公交晃回去。


原来是本童话。和哈利波特差不多的海报,和哈利波特差不多的基调和色彩,和哈利波特差不多的养眼少年男主角,以及和哈利波特差不多的出身,我是说电影的出身。也是同样的三人小组,两男一女,一个精明一个忠诚一个万能。不过它比哈利波特好些,至少我看得懂。这片子几乎没什么出彩的地方,但它告诉了我们一些事情:
1. 具象化的美杜莎真是恶心,然后知道如何打败美杜莎吗?诀窍是iPhone。
2. 旅行中一定要随身携带Mac,和远方的伙伴保持通信了解法宝的使用方法,因为出发时太急促来不及说。
3. 美杜莎的头是个好武器,但赢了之后千万别高兴得亲她,这太恶心了。
4. 不要吃免费的食物!
5. 拿跑车做奖品的话,就不要把车钥匙放在车里,更不要给车加满油。
6. 最后我觉得,如果宙斯用闪电火和波塞冬打架的话,他会输的,因为水导电。
7. 最后的最后,他们怎么处理美杜莎的头了?扔垃圾桶里了?


回来的时候路过IFE,外带了杯摩卡,回到寝室看完了剩下一半的《了不起的狐狸爸爸》。也是一本童话。狐设是细长细长的身材,小小的脚尖走起来像跳芭蕾舞,通篇发光两次呈国旗色彩的皮毛,甚得我心。几首插曲都很美妙,尤其那首开篇歌词一胖一矮一瘦的童谣,还有那首一群农场工人围在一起唱的中间大段字幕组都没有翻译的小调。


剧情按着上头们的想法该是又不健康又不向上太不着调了,不过按着我的想法,导演绝对有才,他将狐狸偷鸡偷鸭偷苹果酒的传统演绎得真是有如是白的人(C,用一下你的冷笑话)拯救心上人一般波澜壮阔又富有幽默感,就连三个讨厌的农场主疯狂捣毁狐狸爸爸的大树狐狸一家子挖洞逃命的线路和节奏都极具美感,直至最后的营救战役Ash跑出的奥林匹克优美弧线以及最后的Nice Hit砸开门后冲出的得了狂犬病的Spitz犬(噢,我讨厌这个设定,干吗不挑其他的,癞皮狗吉娃娃什么的不是滑稽的多嘛。。)。最后,我真以为它抢着了尾巴领带会突然神智清灵把尾巴还给狐狸爸爸,可它竟然嘶哑咧嘴甩头扭腰地把尾巴上的毛全弄没了,导演,你也太狠了!好在,导演还是很明显地站在野生动物这边的,末了胜利归途中突然出现的不会讲英语也不会讲拉丁语朝狐狸爸爸举了举爪子又消失在林中的狼,我其实没太明白它和他的意图,但仍旧觉得感动。至少这是本快乐的可以笑着看完的片子,虽然狐狸一家从地洞里搬到了有黄色底和小花的墙纸的树屋里最后又搬到了下水道里,不过好在,狐狸爸爸的尾巴失而复得而且可以随意插拔,他们也可以每天吃超市里的免费食品,并且狐狸妈妈又怀孕了。
这可以是一本环保片,也可以是一本针对中产阶级的讽刺片,但我觉得重要的是它有一个美妙多彩的HAPPY ENDING. And I do love happy ending.

February 12, 2010

[读书笔记] 人工智能中的不确定知识与推理 PART 2:关于时间的概率推理

BOOK:Stuart Russell, Peter Norvig, Artifical Intelligence: A Modern Approach(中译第二版,姜哲等), Pearson


在静态世界中,每一个随机变量的取值都是唯一固定的;而有时问题是动态的,环境状态会随时间不断变化,比如考虑病情的发展,因此有必要对时间上的不确定性建模。我们将状态的改变过程描述为一系列快照,每一个快照(或时间片)都描述了世界在某个特定时刻的状态,包含一个随机变量集合,其中一部分是可观察的,如证据变量Effect,另一部分是不可观察的,如Cause。为了方便标记,一般假设时间片间有一个固定的有限时间间隔,以整数标记。符号U1:3对应变量U1,U2,U3。

  • 马尔可夫假设
    马尔可夫假设认为,当前状态值只依赖于过去“有限的”已出现状态历史。这一假设使我们得以避免指定数目无界的条件假设表(过去的历史是无限的)。满足这一假设的过程被称为马尔可夫过程或者马尔可夫链,最简单的也应用最广的是一阶马尔可夫过程,即当前状态只依赖于相邻的前一个状态,与更早的状态无关:
          clause53    | 转移模型
    另外,也假设时刻t的证据变量只取决于当前状态:
          clause63    | 传感器模型
    一阶马尔可夫的假设在大多数情况下都只是一种近似,而且往往是太不精确的,有两种可能的弥补方法:1)提高马尔可夫过程的阶数;2)扩大状态变量集合。但是可以证明,提高阶数,总能够通过增加状态变量的个数重新形式化,以保持阶数不变。
  • 基本推理任务
    1)滤波和预测(Forward)
    滤波指在到目前为止所有已知的证据下,计算“当前”状态的后验概率分布,即已知直到时刻t的滤波结果,根据新的证据clause11 计算t+1时刻的滤波结果。滤波的过程可分为两步:首先,将当前状态分布由时刻t向前投影到时刻t+1;然后,通过新的证据进行更新。
           clause1211
    式子的第一部分是传感器模型,第二部分是一个求和式中,其中第一个因子是转移模型,第二个因子是时刻t状态分布。求和式完成滤波的第一步,总式子完成第二步。并且,可以认为因子2是沿着变量序列向前传递的“消息”f1:t,在每次转移时得到修正,并根据新的证据进行更新,也就是前向递归:
           clause1320
    预测指计算“未来”某个状态的后验概率分布,可以认为是没有增加新证据的条件下的滤波:
           clause148
    这也是一个前向递归,并且这个计算只涉及转移模型而与传感器模型无关。可以证明,预测结果分布会在将来收敛到一个不动点,之后一直保持不变,即稳态分布。收敛的时间称为混合时间,转移模型中的不确定性越多,混合时间就越短,未来也就越模糊。

    2)平滑(Backward)
    平滑指在到目前为止所有已知的证据下,计算“过去”状态的后验概率分布,也可分为两步:时刻1到k的前向递归和时刻k+1到t的后向递归。
            clause1514
    这个求和式中的因子1是传感器模型,因子3是转移模型,因子2是后向传递“消息”:
           clause1610  
    后向递归和前向递归复杂度相同,每次更新所需的空间和时间都是常量,与时间t无关,而是取决于状态空间的大小以及问题所需的特定时序模型。我们可以通过记录整个序列进行前向滤波的每步结果,来降低全序列平滑的时间复杂度为线性,这也就是Forward-Backward算法,先从时刻1到t前向滤波,再从时刻t到1后向平滑。这个基本算法有两个主要缺点:它提高了算法的空间复杂度;它需要修改才能工作在联机环境下,即对于不断新加入的证据,平滑以前的时间片。

    3)寻找最可能序列
    寻找最可能序列指给定一系列观察结果,找到最可能生成这些观察结果的状态序列。应当注意到,平滑计算得到的是“单个”时间片上的后验概率分布,而寻找最可能序列,需要考虑所有时间步上的“联合”概率分布,即
           clause913
    典型地,考虑动态规划的思想,寻找一条以每个时间片上的可能状态为节点最大化后验概率的路径,路径上的状态就组成了最可能序列。在一次前向的遍历中,计算并记录到达每一个状态的最可能路径的概率(通过其父节点上的最可能路径概率记录),并标记产生该概率的父节点。遍历结束后,通过标记就可以回溯到这条最大化概率的最可能路径。这就是经典的Viterbi算法,其空间和时间复杂度都是O(t)。
     
  • 隐马尔可夫模型Hidden Markov Model
    HMM指用“单一离散”随机变量描述过程状态的时序概率模型。该模型的可能取值就是世界的可能状态。多个状态变量可以组合成一个单一的“大变量”,以单个变量取值构成的所有可能元组为取值范围,来保持HMM框架。
    HMM使得所有的基本算法有一种非常简单而优雅的矩阵实现(优雅这词用的,作者太有爱了)。令状态变量用整数1,…,S表示,其中S为可能状态的数目,那么,转移模型就可表示为一个S×S的矩阵T,Tij表示从状态i转移到状态j的概率;对每个时间片t,传感器模型就可表示为一个对角型矩阵Ot(证据取值已知,因此为对角型),Oii表示当状态为i时生成证据et的概率;前向消息和后向消息用列向量表示:
           clause177 
    矩阵的形式化还揭示了改进算法的机会(值得借鉴的一句话)。
    我们可以通过取逆的方式调换等式位置,将前向消息修改为后向传递。那么Forward-Backward算法就可以被修改为:先执行标准的前向过程计算f t:1,但抛弃中间过程,然后b和f同时执行后向计算,得到平滑估计。这种修改降低了算法存储空间的需求,但它要求转移矩阵必须是可逆的,传感器矩阵也是可逆的,即所有观察值在每个状态下都是可能的。类似的,还可以修改平滑算法使之支持固定延时的联机平滑(Fixed-Lag-Smoothing算法)。
    HMM被广泛地应用于语音识别、动作手势识别等领域。
     
  • 卡尔曼滤波器Kalman Filter
    卡尔曼滤波用一些“连续”变量来描述系统的状态(可以是多元的),然后选用合适的条件概率密度“函数”来表示转移模型和传感器模型,典型地,如线性高斯分布。假设位置X由速度和前一时间点的位置决定:
           clause18[6]
    那么如果增加一个高斯噪声,就得到一个线性高斯转移模型:
           clause19[14]
    并且,其给出的单步预测分布也是高斯的,对给定新证据进行条件化后得到的更新分布也是高斯的。一个d元高斯分布的卡尔曼滤波公式传递的“消息”是一个d元均值向量和一个d×d协方差矩阵,其与通用滤波公式或HMM模型的滤波公式的功能是相同的,但由于高斯分布的特殊本质,附加了一些有趣的性质,比如方差值的更新与观察值无关,并且其会很快收敛到一个固定的值而大大简化后续的计算过程。
    卡尔曼滤波最常见的应用是物体运动轨迹的跟踪,甚者能够应用于任何通过连续状态变量和噪声测量来刻画的系统。但是注意,这些系统必须是“光滑的、表现良好”的,并且允许追踪者保持和更新一个合理近似于真实后验概率分布的高斯状态分布。这是因为卡尔曼率滤波器将高斯均值附近的状态Xt当作局部线性的,而“不光滑、表现不良”的系统是高度非线性的,比如Xt+1的取值会因Xt与环境中某值间的相对关系而改变,参考书中鸟撞树干的例子。这种情况下,就需要考虑使用切换卡尔曼滤波器,并行多个卡尔曼滤波器,再根据每个滤波器对当前数据的适合程度,对预测结果取加权和。
     
  • 动态贝叶斯网络Dynamic Bayesian Network
    DBN中的每个时间片都具有任意数量的状态变量和证据变量,HMM和卡尔曼滤波都是DBN的特殊形式。DBN通过将复杂系统的状态分解成一些组成变量,充分利用时序概率模型中的稀疏性,使得其比纯马尔可夫模型更适合大规模系统。DBN需要指定状态变量的先验概率、转移模型和传感器模型,后两者还需要指定相继时间片之间、状态变量与证据变量之间的链接关系的拓扑结构,如左下图所示。
             clause19[22]       graph5[4]
    DBN仍然是贝叶斯网络,因此变量消元、似然加权等推理方法仍然适用。但是DBN的精确推理是不适用的,随着规模的扩大(序列过长),变量消元的因子增长将是指数级的。近似推理中的似然加权也不是很好的选择,与真实的事件序列保持相当接近的样本比例将随着观察序列长度t的增加而呈指数级下降,举个极端的例子,以老板是否带伞来判断是否下雨的DBN,即使老板天天带伞,也仍然会产生有无尽的晴天的幻觉。
    一种比较有效的算法族是粒子滤波,它的工作机理是:首先根据时刻0的先验分布进行采样得到N个样本构成的总体,然后对接下去的每个时间片,对于每个样本通过转移模型使之向前传播,再赋予新证据的似然值进行加权,最后对总样本进行重采样,某个样本被选中的概率与其权值成正比,如右上图所示。例子滤波是高效的,它通过常数数目的样本维持对真实后验概率的良好近似,并且由于它是一个采样算法,能够很容易在混合的和连续的DBN中使用,被广泛应用于复杂的运动模式跟踪以及市场预测。
     

February 6, 2010

[读书笔记] 人工智能中的不确定知识与推理 PART 1:概率推理

BOOK:Stuart Russell, Peter Norvig, Artifical Intelligence: A Modern Approach(中译第二版,姜哲等), Pearson


不确定性的研究来源于一个不幸的事实:智能体几乎从来无法了解关于其环境的全部事实, 因此对其行动的可行程度构造一个完备而正确的描述是几乎不可能的。书中概括规则不确定性的来源为三个方面:1)惰性,对所有相关规则的一一罗列着实过于繁杂;2)理论的无知,现代科学在大多数领域都无法掌握完备的规则;3)实践的无知,即使掌握所有规则,我们也无法对其一一验证。

题外话:书中第一章绪论提到一种观点“要解决一个难题,你必须已经差不多知道答案”,这里的解决指的是AI方法的解决,直白地说,人类无法通过人工智能来解决连自己都找不到头绪的问题。这种观点缠绕着AI由古至今,数学的上限决定了AI发展的上限,学者们能做的只是不断逼近却无法超越(也许),这是哲学与数学产生的基础所决定的可悲事实。

因此,我们只能期待智能体在给定所拥有的环境信息下,在可以执行的规划中选择性能度量达到最大的一个,即理性决策(期望效用最大化)。理性决策是概率理论和效用理论的结合,前者提供一种方法以概括不确定性,后者对智能体的偏好进行表示和推理使其选择能产生最高期望效用的行动。
那么,作为一种合格的不确定性推理模型,首先要合理地表示各种不确定的规则,而后对于给定的观察事实(证据)能够给出各种规划的效用分布情况,最后针对效用分布作出理性决策。这样的推理模型有很多,其中一种最基础也是已经得到成熟发展的不确定知识表示方法,就是贝叶斯网络。

  • 朴素贝叶斯模型Naive Bayesian Model
    这来源于概率论中著名的贝叶斯法则Bayes' Rule:P(a|b) = P(b|a)·P(b) / P(a)(书中有句话说,这个简单的公式是几乎所有概率推理的现代人工智能系统的基础,在此表示同意)。通过合并条件的方式,我们得到如下的概率分布,即朴素贝叶斯模型(Cause指原因,Effect指各种受其影响的结果):
              clause111
    NBM的成立以条件的独立性假设为前提,也就是说,每一个Effect变量取值都由Cause导致,但是它们彼此之间没有直接影响。条件独立断言对全联合概率分布作了理想式的简化,使得概率系统能够进行规模扩展(将一张大的概率表分割成很多小的概率表来处理,复杂度由O(2^n) 降至O(n) )。并且,其相较绝对独立性断言更加普遍容易获得。虽然条件独立性假设在大多数情况下都不成立,但是NBM比纯粹的逻辑智能体要好得多。
     
  • 贝叶斯网络Bayesian Network
    贝叶斯网络为任意的全联合概率分布提供了一种简便的规范,它是一个有向无环图,每个节点都标注了定量概率信息,用于表示变量之间的依赖关系。如下图所示,箭头由父节点指向子节点,节点Xi 有一个条件概率分布P(Xi | Parent(Xi)) 量化父节点对其的影响,没有连线的变量间相互独立。BN是一种局部结构化系统,具有紧致性,假设系统有n个随机布尔变量,每个变量受到至多k个其他随机变量的影响,那么整个BN可以由不超过n·2^k个数据完全描述,而全联合概率分布则需要2^n个。
             graph122
    BN节点的正确添加次序是:首先添加“根本原因”节点,然后加入受它们影响的变量,直到叶子;错误的添加次序将带来糟糕的网络和额外不必要的需指定的数据,但是尽管如此,它们都表示完全相同的全联合概率分布。
    全联合概率分布中的每个条目都可以通过BN的信息计算出来,有公式
             clause210
    这是BN的数值语义,另外还有与之等价的拓扑语义,其有两种描述,指出图中条件独立的节点:1) 给定父节点,一个节点与它的非后代节点是条件独立的;2) 给定一个节点的父节点、子节点以及子节点的父节点,那么这个节点与网络中的其他节点是条件独立的(又称马尔可夫覆盖Markov Blanket,第一次正式在教科书中与Markov 碰面,幸会幸会~)。
    另,混合贝叶斯网络Hybrid Bayesian Network,指的是同时包含离散随机变量和连续随机变量(比如,概率是高斯分布的)的网络。
     
  • 基于贝叶斯网络的概率推理
    对于任意一种概率推理系统,其最基本的任务是:在给定某些证据(如诸多Effect )后,计算一组查询变量(如Cause )的后验概率分布。

    1)精确推理。
    既然贝叶斯网络给出了全联合概率分布的完备表示,那么查询P(X | e) 就根据网络写成条件概率乘积的形式,然后通过枚举网络中的所有变量并把条件概率表中的对应条目乘起来后求和的方式来回答查询(Enumeraton-Ask)。对X的每一取值x,其计算过程可以用一棵树来表达,如下图左。算法对这棵树作深度优先递归,对每条路径求积,在分支节点处求和,不断递归得到x的后验概率。
           graph2_thumb23           graph3_thumb3
    这种算法是对全联合查询的简单修改,其对全联合分布求和但不显式地构造它。可以看到,它重复计算了很多子表达式,对于一个有n个布尔变量的网络,时间复杂度始终都是O(2^n)。
    那么很自然地,我们能想到对这些子式只进行一次计算,并保存计算结果以备将来使用,来降低时间复杂度。典型地,有变量消元算法(Variable Elimination)。算法在查询求值之前,先剪除所有即非查询变量亦非证据变量祖先的节点,然后从右到左计算表达式。表达式中的所有计算因子都用概率分布来表达,因其变量个数有些写作二元向量,有些写作矩阵。因子间的相乘,以概率分布的点积来代替,使得所有的中间结果被保留下来。这种点积不是矩阵乘法,而是两个具有同一些因子的概率分布的消元联合,如f1(A, B)·f2(B, C) = f3(A, B, C),若有f1(T, T) = 0.3,f2(T, F) = 0.6,那么就有f3(T, T, F) = 0.18。最后,通过不断的消元点积,得到查询所需的分布。
    变量消元算法的时间和空间需求取决于算法运行过程中构造的最大因子,而后者又进一步取决于变量消元次序和网络结构。对于单连通的网络(如上图左),其与网络复杂度成线性关系;但对于多连通的网络(如上图右),书中称这种情况下将有指数级的时间和空间复杂度,并其与计算逻辑命题的布尔满足赋值个数问题难度相当(归约方法证明),是一个#P问题,严格地难于NPC问题。团算法(Clustering)可将这种图中的单独节点联合,形成团节点,最终使得网络结构是一个单连通图,但这种构造也是NPC的(计算理论无处不在XD)。

    2)近似推理。
    由于大规模多连通网络中的精确推理是不可操作的,就有必要考虑近似的推理方法。
    最Naive的,我们通过直接采样的方法,按照拓扑次序依次对每个变量进行采样,被采样变量值的概率分布依赖于其父节点的赋值,再按概率随机对其赋值,多次重复得到大量样本后,就可以计算查询在样本集中的概率分布。显然,此概率分布在极限情况下能过收敛到查询的真实值,且准确度与采样个数有关。直接采样方法有两种衍生算法,用于计算条件概率:拒绝采样(Rejection Sampling),直接采样后剔除证据与查询不同的样本,再归一化概率分布;似然加权(Likelyhood Weighting),这种方法只生成与证据一致的样本,但在生成样本的过程中计算似然权值w补偿真实采样分布与期望采样分布之间的差距,w是每个证据变量在给定其父节点条件下的取值概率的乘积。容易察觉到,前者的可用样本总是很少因此效率低下,而后者的效率虽然较前者要高,但当证据变量个数增加时,大多数样本的权值都将变得非常低,性能将大受影响。
    比较普适地,近似推理有三族主流的方法,分别为变分近似(Variational Approximation)、信度传播(Belief Propagation)以及马尔可夫链蒙特卡洛(Markov Chain Monte Carlo,MCMC)方法。
    MCMC方法:通过对前一个样本进行随机改变而生成下一个样本,在每一步采样循环中,对某个非证据变量Xi 进行采样,其转移方向取决于Xi 的马尔可夫覆盖中变量的当前值。MCMC方法认为采样过程最终会进入一种“动态平衡”,处于这样的情况下,长期来看在每个状态上花费的时间都与其后验概率成正比,也就是稳态分布(Stationary Distribution):
             clause3_thumb11
    其中,π(x) 为状态x的概率,q(x'→x)为状态x转移到x'的概率。
    有性质称为细致平衡(Detailed Balance),意味着任何两种状态之间的期望流量相等:
            clause4_thumb7
    吉布斯采样器(Gibbs Sample)是MCMC方法的一个简单变体,容易证明其满足与真实厚颜概率一致的细致平衡。
    变分近似方法:其基本思想是提出一个原问题的易于处理的简化版本,并通过调整变分参数,使简化问题与原问题之间的距离函数最小化,以保证其与原问题尽可能地相似。
    信度传播方法:又称环传播(Loop Propagation),由Judea Pearl在1982年提出,现被应用于超大规模和非常高连通度的贝叶斯网络,是一种以局部的信度传递代替全局积分的算法,虽然有时会不正确或不收敛,但在绝大多数情况下其结果与真实值是非常接近的。
     
  • 不确定推理的其它方法
    缺省推理(Default Reasoning):它不是把结论当作“在某种程度上相信”,而是“相信,除非找到相信其它事物的更好理由”。在这种体系下,推理总是选择相信缺省值,除非出现某种更特定的值,将缺省值覆盖,如我们相信“张三有两条腿”,除非有信息“张三只有一条腿”。
    基于规则(Rule-Based):这种方法建立在基于规则的逻辑系统之上,对每条规则增加某种“伪因子”以容纳不确定性,曾被广泛应用于专家系统。但由于其无法很好地适应规则集的膨胀和新规则的不断加入,这种方法现在已不被推荐使用。
    无知问题Dempster-Shafer理论:这一理论的存在是为了处理不确定性与无知性的区别,它使用区间值信度来表示智能体对命题概率的知识,允许我们通过信度的变化程度对“无知性”进行表达。比如抛硬币的问题,当硬币均匀时,我们知道正反面出现的概率各为0.5,但是我们对硬币是否均匀却是无知的,此时,该理论认为正反面出现的概率均为[0, 1],那么如果有专家作出检测硬币是均匀的概率是0.9,那么该理论认为,正反面出现的概率就均为[0.45, 0.55]。
    模糊集与模糊逻辑:模糊集理论对命题的定义十分接近自然语言,模糊谓词的真值是介于0和1之间的一个数值,这就意味着,模糊集是一个没有清晰边界的集合,比如我们描述一个人是否高,这就可以用模糊集理论来表述。模糊集理论和基于其的模糊逻辑通常被应用于构造控制系统,但是它和基于规则的推理方法一样,都具有真值函数性,这是说,复合语句的真值通过其各组成部分的真值来计算。而除非存在非常强的独立性假设,这种概率组合是行不通的。这使得模糊集理论在处理复杂网络的问题上,将带来灾难性的不正确信度。
     

February 2, 2010

寒假始

1日,抱着大大的一束百合,打了两次的,才找到莹妞说的新开的高级会所附近的某新开的酒店,末了上楼还被当成送花的小妹= =,酒店经理义正言辞地对俺说“怎也不知道带个花瓶来!”。离被告知的时间已过半小时又一刻,主角们竟都还没到,在场的全是三姑六婆或者花白头发的叔爷们,么有一人认识俺的><,所幸俺临危不惧才不致酿成惨剧。

许是订婚请的人本不多,又是中午能来的更少(俺也是头一遭参加,说是订婚酒女方中午男方晚上),一顿饭吃下来除了主人家,只认识三颗人,两颗是我初中同学一颗是我小学同学T T。真是有史以来最寂寞的一顿酒席。不过见到久违的同学还是开心的,另加兄愈发惊艳,安小妹则愈发讨喜,笑问何时办喜酒,两人竟均答“如果一个人也行,那便可以办了”。我对八卦真是迟钝吧,记忆中两人都是花草有主的。

算来离家已近8年,和家乡已经有些脱节了,逢人说话讲方言要先思考半拍关于如何表达,不识得新开的酒店餐厅、新造的街道小区、其实是南边大片新造和东面大片改造的所有。这个地方和我的记忆愈发不像了,初中时在江滨闲逛可从来不会遇到黑不溜秋的黑人。希望那些好吃的小食店别拆别搬别换老板最重要别变味道最好别加价!