71人工智能

人工智能04－05春季陈昱北大计算机研究所chenyu◎icst.pku.edu.cn825299988-52762基本信息周四10－12节，电教239先修课程：计算机科学中涉及编程、数据结构和算法分析的课程；高等数学，包括微积分、线性代数和概率统计。课程网页:教材:人工智能—一种现代方法(第二版)作者:StuartRussellandPeterNorvig译者:姜哲等出版商:人民邮电出版社教材网页:助教:李佳静，82529988－5772，[e-mail]考核方式：平常作业40％，期末考试60％。3课程基本内容覆盖教材中1－11，13－21，23和26章。问题求解知识与推理规划不确定知识与推理学习4第一章、序论什么是人工智能（AI）人工智能的基础人工智能的历史回顾和展望5什么是AIAI是普遍的研究领域和人类智能活动的所有范畴都潜在相关人vs.理性人：经验科学，涉及许多假设和实验证实理性：数学和工程相结合。一个系统如果能够在它所知的范围内“正确行事”，它就是理性的。像人一样思考的系统像人一样行动的系统理性地思考的系统理性地行动的系统6像人一样行动:图灵测试图灵预测，2000年之前计算机有30%的概率蒙骗一个普通人达5分钟。然而，AI研究者相信研究智能的根本原则远比复制样本更重要。Source:lecturenotesbyDr.HweeTouNg,Singapore7图灵测试对计算机的要求自然语言处理知识表示自动推理机器学习完全图灵测试计算机视觉机器人技术8像人一样思考：认知模型方法确定人是怎样思考的通过内省通过心理测试（blackbox）通过计算机程序来表达关于思维的结论比较计算机输入/输出以及timingbehavior和人类行为，例子：GeneralProblemSolverbyNewell&Simon。认知科学：把AI的计算机模型和心理学的实验相结合，试图创立一种精确且可检验的人类思维工作方式理论。9理性地思考：“思维法则”方法“正确思考”是不能辩驳的推理过程（Aristotle）三段论：前提正确结论正确描述世界上一切事物及其彼此之间关系的精确的命题符号（19世纪）求解任何用逻辑符号描述的可解问题的程序（1965）逻辑的方法的两个障碍：难以获得非形式化的知识并得到逻辑符号表示所需的形式化表达，尤其当知识不可靠时。“原则上”可以解决一个问题与实际解决问题这两者之间存在巨大的差异：如果推理步骤不合适，会耗尽计算机的资源。10理性地行动：理性智能体方法智能体是某种能够行动的东西，区别于简单“程序”自主控制的操作感知环境持续能力适应变化有能力承担其它智能体的目标通过自己的行动获得最佳结果做出正确的推论是理性智能体的部分功能，但不是理性的全部内容。图灵测试中需要的所有技能都是为了做出理性行为11把AI的研究看成理性智能体的设计的好处比“思维法则”方法更为通用正确的推论只是实现理性的几种可能机制之一比建立在人类行为或思维基础上的方法更经得起科学发展的检验理性的标准有着清楚而普遍的定义人类的行为可以很好地适应特定的环境，而且部分地取决于未知的进化过程。12本课程的着眼点理性智能体的通用原则构造理性智能体所需的组成部分在很长时间内实现完美的理性在复杂的环境下是不可行的，但它是研究问题的出发点。有限理性：在没有足够的计算时间前提下采取正确的行动。13第一章、序论什么是人工智能（AI）人工智能的基础人工智能的历史回顾和展望14AI的基础:为AI贡献想法、观点和技术的学科的简史哲学（公元前428年至今）数学（约800年至今）经济学（1776年至今）神经科学（1861年至今）心理学（1879年至今）计算机工程（1940年至今）控制论（1948年至今）语言学（1957年至今）15哲学形式化规则能用来抽取合理的结论吗？Aristotle的三段论：在初始前提的条件下机械地推导出结论。用机械装置进行推理RamonLull,LeonardodaVinci,WilhelmSchickard精神的意识是如何从物质的大脑产生出来？Descartes给出了第一个关于意识和物质之间的区别及由此引起的问题的清晰讨论：二元论vs.唯物主义描述意识的形式化、理性的部分16二元论vs.唯物主义二元论意识的一部分是超脱于自然之外的，不受物理定律影响。动物不拥有这种二元属性，可以被当作机器看待。唯物主义大脑依照物理定律运转而构成意识自由意志是对出现在选择过程中的可能选择的感受方式17哲学（2）：知识从哪里来？Bacon“NovumOrganum”开启经验主义运动：“无物非先感而后知”Hume“ATreatiseofHumanNature”提出归纳原理:一般规则是通过揭示形成规则的元素之间的重复关联而获得逻辑实证主义学说所有的知识都可以用最终与（对应于传感器输入的）观察语句相联系的逻辑理论来刻画Carnap“TheLogicalStructureoftheWorld”定义一个用于从基本实验中抽取知识的计算过程18哲学（3）：知识是如何导致行动的？对AI来说是至关重要的Aristotle:行动是通过目标与关于行动结果的知识之间的逻辑联系来判定的。2300年后Newell&Simon在GPS程序中实现Aristotle的算法（回归规划系统）当多个行动可以达到目标时或根本无法到达目标时，如何行事？Arnauld正确地表述了一个定量规则（17世纪）JohnMill“Utilitarianism”把理性决策规范的思想发扬推广到人类行为的各个层面(19世纪）19哲学家们标志出了AI的大部分思想，但实现成为一门规范科学的飞跃就要求在三个基础领域完成一定程度的数学形式化：逻辑、计算和概率。20数学什么是抽取合理结论的形式化规则？Boole逻辑（接近命题逻辑）Frege扩展了Boole逻辑，使其包含对象和关系，创建了一阶逻辑（当今最基本的知识表示系统）代表作“Begriffschrift”（概念符号），1879Tarski引入一种参考理论，可以表示如何将逻辑对象和现实世界的对象联系起来。21数学（2）：逻辑和计算的极限Euclid的计算最大公约数的算法是第一个不可忽视的算法把一般的数学推理形式化为逻辑演绎的努力（始于19世纪晚期）Hilbert著名的“23个问题”的最后一个问题是：是否存在一个算法可以判定任何涉及自然数的逻辑命题的真实性。Godel证明了确实存在真实的局限（不完备性定理，1931）在任何表达能力足以描述自然数的语言中，在不能通过任何算法建立它们的真值意义下，存在不可判定的真值语句。22逻辑和计算的极限（2）Turning试图精确地刻画哪些函数是能够被计算的但，计算或有效过程的概念是无法给出形式化定义的。如果解决一个问题需要的时间随实例的规模成指数级增长，该问题称为不可操作的。NP-完全理论为认识不可操作问题提供一种方法任何NP-完全问题类可归约而成的问题类很可能是不可操作的23数学（3）：概率概率起源于对赌博问题可能结果的描述，成为所有需要定量的科学的无价之宝，帮助对付不确定的测量和不完备的理论。（Cardano，16世纪）Bayes提出了根据新证据更新概率的法则（18世纪）Bayes分析形成了大多数AI系统中不确定推理的现代方法的基础24经济学我们如何决策以获得最大效益？AdamSmith是第一个把经济学当作科学来看待，认为经济是个人代理之间的协调过程，这些代理追求自己的经济利益的最大化。对于“偏好的结果”（效用）的数学处理，由Walras完成形式化。决策理论把概率和效用结合起来，为在不确定条件下进行决策提供了形式化和完整的框架。（适用于“宏观”经济）“微观”经济则更像博奕游戏在他人不合作情况下如何获得最大效益？25经济学（２）当行动的收益不是立即体现的，而是一些按顺序采用的行动的结果时，如何制定理性的决策？属于运筹学问题的形式化马尔可夫决策过程基于满意度的模型制定“足够好”的决策，而不是艰苦计算得到最优化决策，能更好地描述人类行为。（Simon,1947)26神经科学：大脑是如何处理信息的？大脑的神经元27心理学：人类和动物是如何思考的？研究方法：内省vs.心理测量行为主义者只研究对动物的感知和它所引发的行动的度量，排斥精神的结构，包括知识、信念、目标和推理步骤。认知心理学把大脑当作信息处理装置。基于知识的智能体的三个步骤：把刺激翻译成内部表示表示经过认知过程处理→新的表示表示被翻译回到行动计算机模型的发展导致认知科学的创建普遍的观点：“认知理论就应该像计算机程序”28计算机工程：如何制造能干的计算机？AI需要智能和人工制品，即计算机。AI对主流计算机科学的影响分时技术交互式翻译器使用窗口和鼠标的个人计算机面向对象的编程…29控制论：人工制品怎样才能在自己控制下运转现代控制论和AI的共同点：设计出能随时间变化使目标函数最大化的系统。控制论的主要工具是微积分和线性代数其主要研究对象是用固定的连续变量集描述的（线性）系统AI的部分起因是寻求摆脱控制论的数学方法局限性的途径不同的工具：逻辑推理和计算不同的问题：语言、视觉、规划…30语言学：语言和思维是怎样联系起来的？现代语言学的诞生：Chomsky理论形式化，可以编程实现。知识表示的许多早期工作和语言紧密联系31总结哲学：标出了AI的大部分重要思想数学：使AI成为一门规范科学经济学：决策理论神经科学：网络，并行处理…心理学：认知理论计算机工程：AI的“载体”控制论：反馈的思想语言学：知识表示、语法32为什么AI有必要成为一个单独的领域？和控制论、运筹学、决策理论的目标类似为什么不是数学的一个分支？AI从一开始就承载着复制人的才能的思想方法论的不同AI属于计算机科学的分支AI试图建造在复杂和变化的环境中自动发挥功能的机器33第一章、序论什么是人工智能（AI）人工智能的基础人工智能的历史回顾和展望34孕育期（1943－1955）McCulloch&Pitts提出人工神经元模型基础生理学知识和脑神经元的功能对命题逻辑的形式化分析Turing的计算理论Turing第一个清晰地描绘出AI的完整图景在“ComputingMachineryandIntelligence”中提出了图灵测试、机器学习、遗传算法和增量学习。35诞生：DartmouthCollege，1956Dartmouthworkshop，1956夏天与会者的背景：自动机、神经网络和智能研究Impact：在随后的20年中，AI被与会者和他们在MIT、CMU、Stanford及IBM的学生和同事所统治。36Look,Ma,nohand!(1952-69)GPS可能是第一个实现了“像人一样思考”方法的程序Samuel‘scheckersprogram，通过学习达到了业余高手的级别，反驳了认为计算机只能做人让它做的事的观念。（通过“强化学习”）McCarthy“ProgramswithCommonSense”描述了一个假设程序，AdviceTaker。它可被看作是第一个完整的AI系统，不同于其它的系统，它包含了世界的一般知识。SRI的Shakey机器人项目，第一次演示了逻辑推理和物理行为的完整集成。37现实的困难：1966－1973早期的程序很少包含或不包含关于它们的主题信息AI试图解决的许多问题不可操作在计算复杂性理论发展起来之前，广泛认为由“微问题”到“大问题”只是需要更快的硬件和更大容量的内存。但，程序原