《人工智能导论：模型与算法》全套课件

古代哲人对智能的思考智能发谋信能赏罚仁能服众勇能果断严能立威五德皆备，然后可以为大将孙武（约公元前545年—约公元前470年）知（通智）者不惑仁者不忧勇者不惧孔子（公元前551年―公元前479年）孟子公元前372年-公元前289年恻隐之心，仁之端也羞恶之心，义之端也辞让之心，礼之端也是非之心，智之端也荀子的智能观：《荀子.正名》知之在人者谓之知知觉：人所固有认识外界客观事物本能，如视觉、听觉和触觉等能力知有所合谓之智智慧：知觉对外界事物的认知所以能之在人者为之能本能：人身上所具用来处置事物能力能有所合谓之能智能：对外界所产生的认知和决策

荀子

战国末期赵国人

(约公元前313年－公元前238年)从感知、到理解、到认知、到决策与行动

计算的诞生结绳计数上古结绳而治，后世圣人易之以书契，百官以治，万民以察。——《周易·系辞》《清明上河图》中赵太丞家药铺柜中的算盘

计算的诞生：从可计算到不可计算20世纪初，人们发现有许多问题无法找到解决的方法。于是开始怀疑，是否对这些问题来说，根本就不存在算法，即不可计算。从费马猜想到费马定理

费马（PierredeFermat）：法国人，律师，业余数学家（1601-1665）1621年出版的《算数(DiophantiAlexandriniArithmeticorumLibriSex)》，大约在1637年费马用拉丁文在本书右侧空白写下：篇幅不足难以写下证明过程计算之力从何而来MathematicalProblems(23个数学问题)LecturedeliveredbeforetheInternationalCongressofMathematiciansatParisin1900工欲善其事，必先利其器：智能之器从何而来DavidHilbert(1862-1943)德国著名数学家

问题2：

证明算术公理的相容性(thecompatibilityofthearithmeticalaxioms)完备性：所有能够从该形式化系统推导出来的命题，都可以从这个形式化系统推导出来。一致性：一个命题不可能同时为真或为假可判定性：算法在有限步内判定命题的真伪如何证明（计算）这一问题？可用怎样的“计算载体”来实现？KurtFriedrichGödel(1906-1978)哥德尔不完全性定理(1931年）任何表达力足够强的(递归可枚举)形式系统都不可能同时具有一致性和完备性《论数学原理及有关系统中不可判定命题》(OnFormallyUndecidablePropositionsofPrincipiaMathematicaandRelatedSystems)工欲善其事，必先利其器：智能之器从何而来计算之力从何而来OnComputableNumbers,withanApplicationtotheEntscheidungsproblem,1937

《论数字计算在决断难题中的应用》图灵机模型计算“gcd(24,16)*10+17”示意AlanTuring(1912-1954)工欲善其事，必先利其器：智能之器从何而来“判定性问题”是无法解决的，即有些数学问题是不可求解的(图灵不可停机的)计算之力从何而来人工智能：以机器为载体的人类智能或生物智能工欲善其事，必先利其器：智能之器从何而来图灵论题：凡是可计算的函数都可以用图灵机计算邱奇论题：任何计算，如果存在一个有效过程，它就能被图灵机实现

邱奇－图灵论题(Church–Turingthesis,computabilitythesis)计算载体提出学者计算角度原始递归函数哥德尔Godel数学的形式丘奇Church数理逻辑的形式图灵机图灵Turing机械的形式图灵奖：计算机界最高奖（1966年设立）AlanTuring(1912-1954)二战提前五年结束的解码器Enigma图灵机模型使得人类得以迈入自动计算时代对智能的测试：图灵测试摩尔定律支撑自动计算时代快速发展：

摩尔定律（计算机速度1年半增长1倍），亿级晶体管、千亿指令/秒人工智能的诞生ResearchProjectonArtificialIntelligence,August31,1955,

Dartmouth当年提出AI概念的建议书AI概念提出50年后，建议人合影四位学者在1955年提出了人工智能这一术语及研究范畴JohnMcCarthy（时任Dartmouth数学系助理教授，1971年度图灵奖获得者）MarvinLeeMinsky（时任哈佛大学数学系和神经学系JuniorFellow，1969年度图灵奖获得者)ClaudeShannon（BellLab,信息理论之父）NathanielRochester（IBM,第一代通用计算机701主设计师)让机器能像人那样认知、思考和学习,即用计算机模拟人的智能。人工智能的诞生达特茅斯会议合影(1956年)报告列举了ArtificialIntelligence值得关注七个问题

AutomaticComputersHowCanaComputerbeProgrammedtoUseaLanguageNeuronNetsTheoryoftheSizeofaCalculationSelf-improvement：自我学习与提高Abstractions：归纳与演绎RandomnessandCreativity

人工智能（ArtificialIntelligence）是以机器为载体所展示的人类智能，因此人工智能也被称为机器智能（MachineIntelligence）计算机课程体系的历史发展：从EE到CSTheTechnischeUniversitätDarmstadt（德国达姆施塔特工业大学）

foundedtheworld'sfirstdepartmentofelectricalengineeringin1882.In1885,thefirstDepartmentofElectricalEngineeringatCornellandthefirstDepartmentofElectricalinUniversityCollegeLondon.The

firstDepartment

of

ComputerSciences

intheUnitedStateswasestablishedat

Purdue

UniversityinOctober1962.

M.S.andPh.D.programsinComputerSciencestarted.FreshmenDeclaringComputerScienceastheirMajorfrom1969-1995at

Purdue

UniversityEdsgerW.Dijkstra,CommunicationwithanAutomaticComputer,PhDthesis,UniversityofAmsterdam,1959.1957年，Dijkstra结婚时填报职业信息时，其填写programmer。但是，官方拒绝这一表述，因为荷兰在那个时候没有这个职业。Thefirst

Ph.D.sinComputerScienceinUnitedStates?ThefirstPh.D.sdesignatedas"ComputerScience"wereawardedbytheUniversityofPennsylvania:RichardWexelblat(December,1965),AndriesvanDam(May,1966).Inmay1965,SisterMaryKennethKelleristhefirstwomantoearnaPh.D.theComputerSciencesDepartmentattheUniversityofWisconsin(thesistitle:InductiveInferenceonComputerGeneratedPatterns)andatthesamedayIrvingC.TangearnedaD.Sc.fromtheAppliedMathematicsandComputerScienceDepartmentatWashingtonUniversityinSt.Louis.计算机课程体系的历史发展：从EE到CS为了规范计算机课程的教学，美国计算机学会（AssociationforComputingMachinery,ACM)于1968年和1978年发布了计算机科学（ComputerScience,CS)教程体系Curriculum68和Curriculum78。

Curriculum68Curriculum78

ComputerscienceMathComputerscienceMath

基础核心课程计算导论、计算机和程序设计、离散数学、数值计算微积分、数学分析、线性代数程序设计1、程序设计2；计算机体系、计算机结构组成、计算机文件系统与处理

微积分、数学分析、线性代数、概率论、离散结构（与逻辑推理有关）中间连接课程数据结构、Prolog语言、计算机组成、系统编程、电路交换理论、数值分析等概率论数学分析II、概率与统计计算机课程体系的演变计算机课程体系的演变人工智能内容在早期计算机课程体系中已经出现，如1968年中“A9AI,heuristicprogramming”和1978年中“CS12AI”。

Curriculum68Curriculum78

ComputerscienceMathComputerscienceMath

前沿课程formallanguages（形式化语言);advancedcomputerorganization(先进计算机结构);analogandhybridcomputing(模拟与混合计算);systemssimulation(系统仿真);informationretrieval(信息检索);computergraphics(计算机图形学);

theoryofcomputability(可计算理论);large-scaleinformationsystems(大型信息系统);

AI,heuristicprogramming(人工智能与启发式规划)

adv.Calculus(高级微积分)*；alg.Structures(算法结构)*;probability&staistics(概率论与统计)*computersandsociety(计算机与社会)；OSandcomputerarchitectureII(操作系统与计算机体系结构)；databasemanagementsystems(数据库管理系统)；AI(人工智能)；algorithms(算法)；softwaredesign(软件设计)；programminglanguagetheory(编程语言理论);automata.Languages,computability(自动机、语言和可计算理论);numericalanalysis(数值分析);numericalmath(数值计算):linearalgebra(线性代数)CS17numericalmath:analysisCS18numericalmath:linearalgebra*twoeachofCSandmathrequired

计算机课程体系的演变1985年，ACM和IEEE计算机协会（IEEE-CS）联合成立了一个工作组，来制定计算机课程体系，这个工作组认为计算机专业是研究信息描述和转换的系统性算法过程，包括理论、分析、设计、效率、执行和应用。同时，工作组提出计算科学的根本问题是，“什么可以（有效地）自动化？（whatcanbeefficientlyautomated）”。1991年，这个工作组发布了计算机课程体系computingcurricula1991。SubjectArea（11个知识领域）TagAlgorithmsandDataStructures（算法与数据结构）ALArchitecture（计算机体系）ARArtificialIntelligenceandRobotics（人工智能与机器人）AIDatabaseandInformationRetrieval（数据库和信息检索）DBHuman-ComputerCommunication（人机交互）HUNumericalandSymbolicComputation（数字和符号计算）NUOperatingSystems（操作系统）OSProgrammingLanguages（编程语言）PLIntroductiontoaProgrammingLanguage(optional)（编程语言导论）PRSoftwareMethodologyandEngineering（软件方法学和工程）SESocial,Ethical,andProfessionalIssues（社会、伦理和专业实践）SPACM和IEEE-CS发布的1991版计算机课程体系计算机课程体系分为11个知识领域，其中将人工智能内容单列为“ArtificialIntelligenceandRobotics（AI）。计算机课程体系的演变2001年，ACM和IEEE-CS联合工作组发布了计算机课程体系ComputingCurricula2001。ComputingCurricula2001将计算机课程体系分为14个知识领域，其中将人工智能内容单列为“IntelligentSystem（AI）。AI的相关内容被分为13个分支，分别为智能系统基础、搜索与优化、知识表达和推理、学习、智能体、计算机视觉、自然语言处理、模式识别、先进机器学习、机器人、知识系统、神经网络和遗传算法。Discretestructures

(离散数学，DS)

IS1:Fundamentalissuesinintelligentsystems(智能系统基础)Human-ComputerInteraction(人机交互，HC)IS2:Searchandoptimizationmethods(搜索与优化)ProgrammingFundamentals(编程基础，PF)IS3:Knowledgerepresentationandreasoning(知识表达和推理)GraphicsandVisualComputing(图形学与可视计算，GV)AlgorithmsandComplexity(算法与复杂性，AL)IS4:Learning（学习）IS5:Agents（智能体）IntelligentSystems(智能系统，IS)IS6:Computervision（计算机视觉）ArchitectureandOrganization(体系与组织，AR)

IS7:Naturallanguageprocessing（自然语言处理）InformationManagement(信息管理，IM)IS8:Patternrecognition（模式识别）OperatingSystems(操作系统，OS)IS9:Advancedmachinelearning（先进机器学习）SocialandProfessionalIssues(社会问题与专业实践，SP)IS10:Robotics（机器人）Net-CentricComputing(网络计算，NC)IS11:Knowledge-basedsystems（知识系统）SoftwareEngineering(软件工程，SE)IS12:Neuralnetworks（神经网络）ProgrammingLanguages(编程语言，PL)IS13:Geneticalgorithms（遗传算法）ComputationalScience(计算科学，CN)14个知识领域AI的13个分支计算机课程体系的演变2013年，ACM和IEEE-CS联合工作组发布了计算机课程体系ComputingCurricula2013。在ComputingCurricula2013中，计算机课程体系被称为为一个“大篷”（bigtent），其知识领域被拓展为18个。在这个课程体系中，人工智能“IntelligentSystem（AI）”相关内容被分为12个分支。AL-AlgorithmsandComplexity(算法与复杂度)

Fundamentalissues(智能基本问题)AR-ArchitectureandOrganization

(计算机结构体系与组织)CN-ComputationalScience(计算科学)BasicSearchStrategies(搜索策略基础)DS-DiscreteStructures（离散数学）BasicKnowledgeBasedReasoning(知识表示和推理基础)GV-GraphicsandVisualization（图形与可视化）HCI-Human-ComputerInteraction（人机交互）BasicMachineLearning（机器学习基础）IAS-InformationAssuranceandSecurity（信息保障与安全）IM-InformationManagement（信息管理）AdvancedSearch（高级搜索）IS-IntelligentSystems（智能系统）AdvancedRepresentationandReasoning(高级知识表达和推理)

NC-NetworkingandCommunications（网络与通讯）

ReasoningUnderUncertainty（不确定下推理）OS-OperatingSystems（操作系统）PDB-Platform-basedDevelopment（基于平台的开发）Agents（智能体）PD-ParallelandDistributedComputing（并行与分布式计算）NaturalLanguageProcessing（自然语言处理）PL-Programminglanguages（程序设计语言）SDF-SoftwareDevelopmentFundamentals（软件开发基本原理）

AdvancedMachineLearning（高级机器学习）SE-softwareEngineering（软件工程）SF-SystemsFundamental（系统基本原理）Robotics（机器人）SP-SocialIssuesandProfessionalPractice（社会问题与专业实践）PerceptionandComputerVision（感知与机器视觉）18个知识领域AI的12个分支计算机课程体系的演变从2008年和2013年计算机课程体系可以看出：计算机课程体系这个“大篷”随时间不断扩展，如基于平台的开发、并行与分布式计算、系统基本原理等是2013年中新增加内容。人工智能知识点逐渐变得明晰，在2013年计算机课程体系中明确指出人工智能是一门研究难以通过传统方法去解决实际问题的学问之道，其通过非传统方法解决问题需要利用常识或领域知识的表达机制、解决问题的能力以及学习技巧。为此，需要研究感知(如语音识别、自然语言理解、计算机视觉)、问题求解（如搜索和规划）、行动（如机器人）以及支持任务完成的体系架构（如智能体和多智能体）。从1968年计算机课程体系到2013年计算机课程体系可看出，人工智能知识体系的着重点走过了从强调程序设计（programming）、到算法研究（model）以及功能实现（function）的不同历史阶段。汇报提纲二、课程内容概要一、人工智能历史与课程体系中国人工智能人才培养载体人才培养载体设置情况人工智能交叉学科目前浙江大学、武汉大学和华中科技大学三所高校设立了人工智能交叉学科人工智能本科专业目前215所高校设立了人工智能本科专业世界一流大学建设36所高校（A类）中有28所高校开设了人工智能本科专业世界一流大学建设6所高校（B类）中有1所高校开设了人工智能本科专业世界一流学科建设95所高校中有34所高校开设了人工智能本科专业中国迈向新一代人工智能，自然子刊《机器智能》,2020,312–316中国迈向新一代人工智能的挑战和机遇培育本土人工智能人才规范人工智能伦理培育人工智能生态（AIEcosystem）潘云鹤院士担任编委会主任，郑南宁院士、高文院士、吴澄院士、陈纯院士和林金安副总编辑担任编委会副主任委员新一代人工智能系列教材特点：权威一流的编委会；来自科研教学一线、朝气勃勃的作者团队；紧扣前沿、富有时代特色的系列教材内容。以教材建设为核心的人才培养：新一代人工智能系列教材潘云鹤院士为系列教材撰写的序言：具有中国特色的人工智能一流教材体系：人工智能基础理论、算法模型、技术系统、硬件芯片和伦理安全以及“智能+”学科交叉等方面内容，在线开放共享课程，各具优势、衔接前沿、涵盖完整、交叉融合。希望“新一代人工智能系列教材”的出版能够为人工智能各类型人才培养做出应有贡献。以教材建设为核心的人才培养：新一代人工智能系列教材(19本）教材名主编出版时间人工智能导论：模型与算法（978-7-04-053466-5）吴飞2020年5月可视化导论（978-7-04-052182-5）陈为、张嵩、鲁爱东、赵烨智能产品设计孙凌云自然语言处理刘挺、秦兵、赵军、黄萱菁、车万翔2020年模式识别周杰、郭振华、张林2020年自主智能运动系统薛建儒2020年人脸图像合成与识别高新波、王楠楠2020年机器感知黄铁军2020年人工智能芯片与系统王则可、李玺、李英明2020年物联网安全徐文渊2020年教材名主编出版时间神经认知学唐华锦

潘纲2021年人工智能伦理与安全秦湛、潘恩荣、任奎2021年金融科技概论郑小林2021年媒体计算韩亚洪2021年人工智能逻辑廖备水2021年人工智能生物医学信息处理沈红斌2021年数字不经济：人工智能与区块链吴超2021年人工智能伦理古天龙2021年赋能：“人工智能+”数字经济王延峰2021年从教材到课程建设：人工智能在线课程、微课程12多万人选课第一期：2018.11.5-2019.1.11共有21109人选课https:///course/ZJU-1003377027

第二期2019.3.4-2019.6.3共有17238人选课人工智能概述搜索求解逻辑与推理统计机器学习深度学习强化学习人工智能博弈中国大学MOOC课程：人工智能：模型与算法第三期2019.9.23-2020.1.7共有18879人选课中国大学MOOC开设《人工智能：模型与算法》第四期2020.2.15-2020.6.9目前29191人选课人工智能基础(数学方法、物理模型)

机器学习

知识表示与处理

机器视觉

自然语言处理

模式识别人工智能芯片与软硬件智能系统与应用新型和交叉的人工智能仿生智能类脑机制人工智能安全基础推动手段应用

生物、医学、化学、材料、地学……复杂理论与系统国家自然科学基金委员会信息学部人工智能学科代码提纲二、教材内容概要一、人工智能历史与课程体系人工智能基本研究内容人工智能：以机器为载体实现的人类智能或生物智能从模拟人类智能角度而言，人工智能应具备如下能力：具备视觉感知和语言交流的能力。即能够识别和理解外界信息（计算机视觉研究范畴）、能够与人通过语言交流（自然语言理解研究范畴）。具备推理与问题求解能力。即基于已有知识，对所见事物和现象进行演绎推理以解决问题。具备协同控制能力。即将视觉（看）、语言（说）、推理（悟）等能力统一协调，加以控制，这是常见的机器人研究领域内容。知其意，悟其理，守其则，践其行人工智能基本研究内容人工智能：以机器为载体实现的人类智能或生物智能从模拟人类智能角度而言，人工智能应具备如下能力：具备遵守伦理道德能力。即模拟人类智能的智能体在社会环境中要遵从一定的伦理道德。阿西莫夫在科幻小说中按照优先级定义了机器人需要遵从的三条伦理原则：不得伤人，或弃人于危难；需服从人；在不违反上述两条原则情况下，保护机器人自己。具备从数据中进行归纳总结的能力。即需要从数据中进行知识、规律和模式学习的模型和方法，这是机器学习研究范畴。知其意，悟其理，守其则，践其行《人工智能导论：模型与算法》：第一章绪论可计算思想起源与发展人工智能的发展简史人工智能研究的基本内容人工智能概述

“我们必须知道，我们必将知道”（大卫希尔伯特，DavidHilbert)《人工智能导论：模型与算法》：第一章绪论手段与方法特点以符号主义为核心的逻辑推理将概念（如命题等）符号化，从若干判断（前提）出发得到新判断（结论）以问题求解为核心的探寻搜索探寻搜索依据已有信息来寻找满足约束条件的待求解问题的答案以数据驱动为核心的机器学习从数据中发现数据所承载语义（如概念）的内在模式以行为主义为核心的强化学习根据环境所提供的奖罚反馈来学习所处状态可施加的最佳行动，在“探索（未知空间）-利用（已有经验）（explorationvs.exploitation）”之间寻找平衡，完成某个序列化任务，具备自我学习能力以博弈对抗为核心的群体智能（两人及以上）从“数据拟合”优化解的求取向“均衡解”的求取迈进这里的“擢”即抽引，表示从一个典型个别事例中抽引出一个一般命题（虑），这种归纳推理的方式不用怀疑，因为其理由或根据是“与典型事例同类的事物联系是存在，还是不存在”逻辑与推理命题逻辑谓词逻辑知识图谱推理因果推理擢虑不疑，说在有无

《墨辨·经下》《人工智能导论：模型与算法》：第二章逻辑与推理启发式搜索对抗搜索（Minimax及Alpha-Beta剪枝搜索）蒙特卡洛树搜索搜索求解搜索算法通过模拟智能体的一系列动作，按照一定规则探索智能体的所有可能行动，直到找到一种满足约束限制的解法，以此来指导智能体的行动。《人工智能导论：模型与算法》：第三章搜索求解故记诵者，学问之舟车也清章学诚《文史通义》化繁为简、大巧不工RonaldAylmerFisher机器学习基本概念回归分析、决策树

线性判别分析、AdaBoosting支持向量机、生成学习模型统计机器学习监督学习从标注数据到概念空间的映射《人工智能导论：模型与算法》：第四章机器学习：监督学习物以类聚，人以群分《战国策·齐策三》统计机器学习非监督学习学习无标注数据的分布K均值聚类主成分分析特征人脸方法潜在语义分析期望极大算法（EM）《人工智能导论：模型与算法》基本内容：第五章统计机器学习：无监督学习深度学习端到端学习数据的区别性表达前馈神经网络（误差后向传播）卷积神经网络循环神经网络深度生成学习自然语言理解与视觉分析《人工智能导论：模型与算法》基本内容：第六章深度学习Neuronsthatfiretogether,wiretogether(DonaldHebb)强化学习强化学习定义基于价值的强化学习基于策略的强化学习深度强化学习的应用通过平衡“探索未知空间与利用已有经验”（explorationvs.exploitation）”与环境进行交互，获得回报，从而序贯地作出决策通过动作施加影响反馈环境状态的变化智能主体环境动作的收益(reward)《人工智能导论：模型与算法》基本内容：第七章强化学习谋定而后动，知止而有得人工智能博弈博弈相关概念(纳什均衡)博弈策略求解博弈规则设计非完全信息博弈的实际应用两害相权取其轻，两利相权取其重博弈行为是多个带有相互竞争性质的主体，为了达到各自目标和利益，采取的带有对抗性质的行为。现代博弈论主要研究博弈行为中最优的对抗策略及其稳定局势，协助对弈者在一定规则范围内寻求最合理的行为方式。《人工智能导论：模型与算法》基本内容：第八章人工智能博弈未来发展与趋势类脑计算自动化机器学习神经网络模型压缩人工智能芯片量子机器学习人工智能伦理与治理人工智能算法开发框架凡是过往、皆为序章（莎士比亚）《人工智能导论：模型与算法》基本内容：第九章未来发展和趋势“智海”新一代人工智能科教平台将以人才培育、科技创新为使命，深度聚焦深度聚焦AI技术创新、AI人才培养与生态建设，汇聚国内外前沿技术和产业资源，联动校、企、政力量，搭建开源、开放、互通的新一代人工智能生态体系，推动中国社会经济的智能化建设。AI赋能、教育先行：“智海：新一代人工智能科教平台”寓意：有智之能，方可驱动时代变革，有海之容，便可赋能万物更新具能、使能和赋能吾生也有涯、而知也无涯2016验证引力波、2017年获得诺贝尔物理奖：一个13亿年前的声音经过漫长星际旅行终于抵达地球，被我们“听到”了爱因斯坦于1918年在论文《论引力波(On

Gravitational

Waves)》预言了引力波存在人类智能与机器智能存在巨大不同人类大脑机器智能self-learninglearningbyexamples

adaptationroutinecommonsenseNointuitionlogic……见一叶落，而知岁之将暮；审堂下之阴，而知日月之行，阴阳之变；见瓶水之冰，而知天下之寒，鱼鳖之藏也《淮南子说山训》

大数据、小任务；小数据、大任务莫拉维克悖论(Moravec’sparadox)：困难的问题是易解的，容易的问题是难解的使能技术、赋能社会：人工智能是引领这一轮科技革命、产业变革和社会发展的战略性技术，具有溢出带动性很强的头雁效应，其作始也简，其将毕也必巨致天下之治者在人才，成天下之才者在教化，教化之所本者在学校

逻辑与推理

《人工智能导论：模型与算法》提纲二、谓词逻辑一、命题逻辑三、知识图谱推理四、因果推理逻辑与推理是人工智能的核心问题逻辑是探索、阐述和确立有效推理原则的学科，提出了演绎推理中“三段论”方法的古希腊学者亚里士多德被誉为“逻辑学之父”。一般而言，逻辑是用数学方法来研究关于推理和证明等问题的研究。亚里士多德（Aristotle公元前384-前322，古代先哲、古希腊人）逻辑与推理是人工智能的核心问题墨翟（尊称为墨子）被认为是东方逻辑学的奠基人。墨子提出了名、辞、说三种基本思维形式和由故、理、类三物构成的逻辑推理。墨子也提出了一些几何思想，如“平，同高也（两平行线或两平行平面间距离处处相等）”、“

圆，一中同长也”。墨子（生卒年不详，名翟（dí），东周春秋末期战国初期宋国人）逻辑与推理是人工智能的核心问题人类思维活动一个重要功能是逻辑推理，即通过演绎和归纳等手段对现有观测现象进行分析，得出判断。在人工智能发展初期，脱胎于逻辑推理的符号主义人工智能(symbolicAI)是人工智能研究的一种主流学派。在符号主义人工智能中，所有概念均可通过人类可理解的“符号”及符号之间的关系来表示。例如：如果使用符号A来表示对象概念、IsCar（）来表示某个对象是否为“汽车”，那么IsCar(A)表示“A是一辆轿车”这样的概念。注意IsCar(A)由对象A和IsCar（）两部分所构成。如果A是轿车，则IsCar(A)为正确描述、否则为错误描述。符号主义人工智能方法基于如下假设：可通过逻辑方法来对符号及其关系进行计算，实现逻辑推理，辨析符号所描述内容是否正确。命题逻辑(PropositionalLogic)

命题逻辑(propositionlogic)是应用一套形式化规则对以符号表示的描述性陈述进行推理的系统。在命题逻辑中，一个或真或假的描述性陈述被称为原子命题，对原子命题的内部结构不做任何解析。若干原子命题可通过逻辑运算符来构成复合命题。命题逻辑

命题逻辑

命题连接符号表示形式意义与(and)或(or)非（not）条件(conditional)双向条件(bi-conditional)命题逻辑

通过真值表来计算复合命题的真假。FalseFalseTrueFalseFalseTrueTrueFalseTrueTrueFalseTrueTrueFalseTrueFalseFalseFalseTrueFalseFalseTrueTrueFalseTrueTrueTrueTrue命题逻辑

“条件”命题联结词中前提为假时命题真假取值

命题逻辑

命题逻辑

逻辑等价的例子命题逻辑：若干逻辑等价命题的解释

命题逻辑中的推理规则假言推理(ModusPonens)与消解(And-Elimination)与导入(And-Introduction)命题逻辑中的推理规则双重否定(Double-NegationElimination)单项消解或单项归结(UnitResolution)消解或归结(Resolution)应用归结法进行证明(1)Knowledgebase

1231已知22进行蕴涵消除33进行蕴涵消除451和2进行归结62和4进行归结73和4进行归结85和7进行归结9应用归结法进行证明(2)Knowledgebase证明如上命题集是不可满足的12341已知2已知3已知4已知51和2进行归结63和4进行归结提纲二、谓词逻辑一、命题逻辑三、知识图谱推理四、因果推理从命题逻辑到谓词逻辑

从命题逻辑到谓词逻辑

个体的性质（是）、个体和个体之间的关系（最大）在谓词逻辑中，将原子命题进一步细化，分解出个体、谓词和量词，来表达个体与总体的内在联系和数量关系，这就是谓词逻辑研究内容。谓词逻辑中三个核心概念：个体、谓词（predicate）和量词（quantifier）谓词逻辑

谓词逻辑：谓词与个体

谓词逻辑：量词谓词逻辑：量词

谓词逻辑：量词

谓词逻辑：函数与谓词的区别

谓词逻辑：谓词演算的合式公式

若干谓词逻辑的推理规则

谓词逻辑的推理例子

谓词逻辑的推理例子

自然语言的形式化

自然语言的形式化

专家系统的构成对某个领域的自然语言、文本语句等信息进行逻辑化答案输出数据知识服务推理机（专家系统）问题逻辑化（机器可理解）提纲二、谓词逻辑一、命题逻辑三、知识图谱推理四、因果推理知识图谱可视为包含多种关系的图。在图中，每个节点是一个实体（如人名、地名、事件和活动等），任意两个节点之间的边表示这两个节点之间存在的关系。一般而言，可将知识图谱中任意两个相连节点及其连接边表示成一个三元组（triplet）,即(left_node,relation,right_node)，例：(David,Father,Mike)。知识图谱：基本概念知识图谱推理知识图谱中存在连线的两个实体可表达为形如<left_node,relation,right_node>的三元组形式，这种三元组也可以表示为一阶逻辑(firstorderlogic,FOL)的形式，从而为基于知识图谱的推理创造了条件。例如从<奥巴马，出生地，夏威夷>和<夏威夷，属于，美国>两个三元组，可推理得到<奥巴马，国籍，美国>。一个简单的家庭关系知识图谱

一个简单的家庭关系知识图谱知识图谱推理知识图谱推理

一个简单的家庭关系知识图谱如果能够学习得到这条规则，该有多好？（从具体例子中学习，这是归纳推理的范畴）

知识图谱推理：归纳学习归纳逻辑程序设计（ILP）是机器学习和逻辑程序设计交叉领域的研究内容。ILP使用一阶谓词逻辑进行知识表示，通过修改和扩充逻辑表达式对现有知识归纳，完成推理任务。作为ILP的代表性方法，FOIL（FirstOrderInductiveLearner）通过序贯覆盖实现规则推理。归纳逻辑程序设计(inductivelogicprogramming，ILP)算法知识图谱推理：FOIL(FirstOrderInductiveLearner)

目标谓词(已知)前提约束谓词(学习得到)

一个简单的家庭关系知识图谱

知识图谱推理：FOIL(FirstOrderInductiveLearner)一个简单的家庭关系知识图谱

知识图谱推理：FOIL(FirstOrderInductiveLearner)

目标谓词(已知)前提约束谓词(学习得到)

知识图谱推理：FOIL(FirstOrderInductiveLearner)

目标谓词(已知)前提约束谓词(学习得到)哪些谓词好呢？可以作为目标谓词的前提约束谓词？

FOIL中信息增益值(informationgain)知识图谱推理：FOIL(FirstOrderInductiveLearner)

目标谓词(已知)前提约束谓词(学习得到)依次将谓词加入到推理规则中作为前提约束谓词，并计算所得到新推理规则的FOIL增益值。基于计算所得FOIL增益值来选择最佳前提约束谓词。

知识图谱推理：FOIL(FirstOrderInductiveLearner)

目标谓词(已知)前提约束谓词(学习得到)背景知识样例集合目标谓词训练样例集合知识图谱推理：FOIL(FirstOrderInductiveLearner)推理规则推理规则涵盖的正例和反例数FOIL信息增益值目标谓词前提约束谓词正例反例信息增益值空集NANANANANA0.32NANANANANA0.74NA1.32NANANANA

知识图谱推理：FOIL(FirstOrderInductiveLearner)推理规则推理规则涵盖的正例和反例数FOIL信息增益值目标谓词前提约束谓词正例反例信息增益值空集NANANANANA0.32NANANANANA0.74NA1.32NANANANA

知识图谱推理：FOIL(FirstOrderInductiveLearner)推理规则推理规则涵盖的正例和反例数FOIL信息增益值目标谓词前提约束谓词正例反例信息增益值空集NANANANANA0.32NANANANANA0.74NA1.32NANANANA

知识图谱推理：FOIL(FirstOrderInductiveLearner)推理规则推理规则涵盖的正例和反例数FOIL信息增益值目标谓词前提约束谓词正例反例信息增益值空集NANANANANA0.32NANANANANA0.74NA1.32NANANANA

知识图谱推理：FOIL(FirstOrderInductiveLearner)推理规则推理规则涵盖的正例和反例数FOIL信息增益值目标谓词前提约束谓词正例反例信息增益值空集NANANANANA0.32NANANANANA0.74NA1.32NANANANA

知识图谱推理：FOIL(FirstOrderInductiveLearner)推理规则推理规则涵盖的正例和反例数FOIL信息增益值目标谓词前提约束谓词正例反例信息增益值空集NANANANANA0.32NANANANANA0.74NA1.32NANANANA

知识图谱推理：FOIL(FirstOrderInductiveLearner)

Back-groundknowledgePositiveandnegativesamples知识图谱推理：FOIL(FirstOrderInductiveLearner)推理规则推理规则涵盖的正例和反例数FOIL信息增益值现有规则拟加入前提约束谓词正例反例信息增益值1.32NANANANANA1NANANANANANANA0NANANANA

知识图谱推理：FOIL(FirstOrderInductiveLearner)推理规则推理规则涵盖的正例和反例数FOIL信息增益值现有规则拟加入前提约束谓词正例反例信息增益值1.32NANANANANA1NANANANANANANA0NANANANA

知识图谱推理：FOIL(FirstOrderInductiveLearner)

目标谓词(已知)前提约束谓词(学习得到)

背景知识样例集合目标谓词训练样例集合给定目标谓词，FOIL算法从实例（正例、反例、背景样例）出发，不断测试所得到推理规则是否还包含反例，一旦不包含负例，则学习结束，展示了“归纳学习”能力。知识图谱推理：FOIL(FirstOrderInductiveLearner)知识图谱推理：FOIL(FirstOrderInductiveLearner)给定目标谓词，FOIL算法从实例（正例、反例、背景知识样例）出发，不断测试所得推理规则是否还包含反例，一旦不包含，则学习结束，由此充分展示了“归纳学习”的能力。在学得推理规则后，再给推理规则中的变量赋予具体例子，经过“演绎”得到新的知识提纲二、谓词逻辑一、命题逻辑三、知识图谱推理四、因果推理公鸡打鸣与太阳升起“力，形之所以奋也”（墨经）从关联到因果计算的可解释：因果是现象加解释，是一种人类文化，即人类在与自然的反复观察、预报、检验中得到的很好考验。因果推理（CausalInference）:Simpson’sParadox(辛普森悖论)1973年伯克利本科生录取率PeterJ.Bickel,EugeneA.Hammel,O’Connell,J.W,Sexbiasingraduateadmissions:DatafromBerkeley,Science,187(4175):398-404,1975男生女生申请数录取率申请数录取率整体844244%432135%学院男生女生申请数录取率申请数录取率A82562%10882%B56063%2568%C32537%59334%D41733%37535%E19128%39324%F3736%3417%男生录取率(44%)远高于女生(35%)六个最大的院系中，4个院系女生录取率大于男生。如果按照这样的分类，女生实际上比男生的录取率还高一点点。女生更愿意申请那些竞争压力很大的院系（比如英语系），但是男生却更愿意申请那些相对容易进的院系（比如工程学系）。传统以统计建模为核心的推理手段JudeaPearl，Causality:models,reasoning,andinference(secondedition)，CambridgeUniversityPress,2009JudeaPearl,MadelynGlymour,NicholasP.Jewell,Causalinferenceinstatistics:aprimer,JohnWiley&Sons,2016DataInferenceQ(P)(AspectsofP)JointDistributionP购买了A商品的顾客是否会购买B商品(对A和B的联合分布建模)Q

=P(B|A)“Theobjectofstatisticalmethodsisthereductionofdata”(Fisher1922).因果推理（CausalInference）:Simpson’sParadox(辛普森悖论)从统计建模推断到因果推理DataQ(P′)(AspectsofP′)changeJointDistribution

PJointDistribution

P′Inference如果商品价格涨价一倍，预测销售量P′(sales)的变化如果放弃吸烟，预测癌症P′(cancer)的概率数据分布从P变换到P′因果推理（CausalInference）:Simpson’sParadox(辛普森悖论)关联(association)：

直接可从数据中计算得到的统计相关

反事实(counterfactual)：某个事情已经发生了，则在相同环境中，这个事情不发生会带来怎样的新结果

介入(intervention):无法直接从观测数据就能得到关系，如“某个商品涨价会产生什么结果”可观测性问题WhatifweseeA(whatis?)决策行动问题WhatifwedoA(whatif?)反事实问题(Counterfactual)WhatifwedidthingsdifferentlyOptions:withwhatprobability从关联到推理：因果推理搜索与求解

《人工智能导论：模型与算法》提纲二、对抗搜索一、启发搜索三、蒙特卡洛树搜索人工智能中的搜索你见，或者不见我我就在那里不悲不喜

---扎西拉姆多多海量信息源问题求解器约束条件额外信息问题所对应答案搜索算法的形式化描述：

<状态、动作、状态转移、路径/代价、目标测试〉对智能体和环境当前情形的描述。例如，在最短路径问题中，城市可作为状态。将原问题对应的状态称为初始状态。状态从当前时刻所处状态转移到下一时刻所处状态所进行操作。一般而言这些操作都是离散的。动作问题：寻找从城市A到城市K之间行驶时间最短路线？智能体选择了一个动作之后，其所处状态的相应变化状态转移一个状态序列。该状态序列被一系列操作所连接。如从A到K所形成的路径。路径/代价评估当前状态是否为所求解的目标状态。目标测试搜索算法的形式化描述：

<状态、动作、状态转移、路径/代价、目标测试〉问题：寻找从城市A到城市K之间行驶时间最短路线？在搜索的过程中利用与所求解问题相关的辅助信息，其代表算法为贪婪最佳优先搜索(Greedybest-firstsearch)和A*搜索。

搜索算法：启发式搜索(有信息搜索)问题：寻找从城市A到城市K之间行驶时间最短路线？

搜索算法：启发式搜索(有信息搜索)辅助信息（启发函数）：任意一个城市与终点城市K之间的直线距离辅助信息所求解问题之外、与所求解问题相关的特定信息或知识评价函数（evaluationfunction）f(n)启发函数（heuristicfunction）h(n)问题：寻找从城市A到城市K之间行驶时间最短路线？贪婪最佳优先搜索(Greedybest-firstsearch)：评价函数f(n)=启发函数h(n)

搜索算法：贪婪最佳优先搜索辅助信息（启发函数）：任意一个城市与终点城市K之间的直线距离问题：寻找从城市A到城市K之间行驶时间最短路线？贪婪最佳优先搜索(Greedybest-firstsearch)：评价函数f(n)=启发函数h(n)

搜索算法：A*算法

辅助信息：任意一个城市与终点城市K之间的直线距离问题：寻找从城市A到城市K之间行驶时间最短路线？

搜索算法：A*算法辅助信息：任意一个城市与终点城市K之间的直线距离问题：寻找从城市A到城市K之间行驶时间最短路线？

提纲二、对抗搜索一、启发搜索三、蒙特卡洛树搜索对抗搜索对抗搜索(AdversarialSearch)也称为博弈搜索(GameSearch)在一个竞争的环境中，智能体(agents)之间通过竞争实现相反的利益，一方最大化这个利益，另外一方最小化这个利益。狭路相逢勇者胜勇者相逢智者胜智者相逢德者胜德者相逢道者胜智能体目标对手最大化利益最小化利益对抗搜索最小最大搜索(MinimaxSearch):

最小最大搜索是在对抗搜索中最为基本的一种让玩家来计算最优策略的方法.Alpha-Beta剪枝搜索(PruningSearch):一种对最小最大搜索进行改进的算法，即在搜索过程中可剪除无需搜索的分支节点，且不影响搜索结果。.蒙特卡洛树搜索(Monte-CarloTreeSearch):通过采样而非穷举方法来实现搜索。对抗搜索本书主要讨论在确定的、全局可观察的、竞争对手轮流行动、零和游戏（zero-sum）下的对抗搜索两人对决游戏(MAXandMIN,MAX先走)可如下形式化描述，从而将其转换为对抗搜索问题状态动作状态转移终局状态检测终局得分注：所谓零和博弈是博弈论的一个概念，属非合作博弈。指参与博弈的各方，在严格竞争下，一方的收益必然意味着另一方的损失，博弈各方的收益和损失相加总和永远为“零”，双方不存在合作的可能。与“零和”对应，“双赢博弈”的基本理论就是“利己”不“损人”，通过谈判、合作达到皆大欢喜的结果。对抗搜索：最小最大搜索

对抗搜索：Alpha-Beta剪枝搜索alpha-beta剪枝搜索算法在Minimax算法中可减少被搜索的节点数，即在保证得到与原Minimax算法同样的搜索结果时，剪去了不影响最终结果的搜索分枝。

图中MIN选手所在的节点C下属分支4和6与根节点最终优化决策的取值无关，可不被访问。对抗搜索：Alpha-Beta剪枝搜索对抗搜索：Alpha-Beta剪枝搜索基于MIN节点反馈收益进行剪枝(alpha剪枝)

MAX

…MINMAXMIN

已被访问后继分支节点未被访问后继分支节点被剪枝…

提纲二、对抗搜索一、启发搜索三、蒙特卡洛树搜索对抗搜索：蒙特卡洛树搜索

对抗搜索：蒙特卡洛树搜索

对抗搜索：蒙特卡洛树搜索

对抗搜索：蒙特卡洛树搜索

对抗搜索：蒙特卡洛树搜索

对抗搜索：蒙特卡洛树搜索

（3.4.3）

对抗搜索：蒙特卡洛树搜索

选择（selection）：选择指算法从搜索树的根节点开始，向下递归选择子节点，直至到达叶子节点或者到达具有还未被扩展过的子节点的节点L。这个向下递归选择过程可由UCB1算法来实现，在递归选择过程中记录下每个节点被选择次数和每个节点得到的奖励均值。扩展（expansion）：如果节点L不是一个终止节点（或对抗搜索的终局节点），则随机扩展它的一个未被扩展过的后继边缘节点M。模拟（simulation）：从节点M出发，模拟扩展搜索树，直到找到一个终止节点。模拟过程使用的策略和采用UCB1算法实现的选择过程并不相同，前者通常会使用比较简单的策略，例如使用随机策略。反向传播（BackPropagation）：用模拟所得结果（终止节点的代价或游戏终局分数）回溯更新模拟路径中M以上（含M）节点的奖励均值和被访问次数。对抗搜索：蒙特卡洛树搜索

对抗搜索：蒙特卡洛树搜索

对抗搜索：蒙特卡洛树搜索

在图3.4.6(b)中，算法随机扩展了L的子节点C，将其总分数和被访问次数均初始化为0。注意，为了清晰地展示算法选择扩展的节点，图3.4.6(b)画出了L的其他未被扩展的子节点，并标记其UCB值为正无穷大，以表示算法下次访问到L时必然扩展这些未被扩展的节点。图3.4.6(c)中采用随机策略模拟游戏直至完成游戏。当游戏完成时，终局得分为3。对抗搜索：蒙特卡洛树搜索

在图3.4.6(d)中C节点的总分被更新为-3，被访问次数被更新为1；L节点的总分被更新为13，被访问次数被更新为2；根节点的总分被更新为-18，被访问次数被更新为3。在更新时，会将MIN层节点现有总分加上终局得分分数，MAX层节点现有总分减去终局得分分数。这是因为在对抗搜索中，玩家MIN总是期望最小化终局得分，因此在MIN层选择其子节点时，其目标并非选取奖励最大化的子节点，而是选择奖励最小化的节点，为了统一使用UCB1算法求解，算法将MIN层的子节点（即MAX层节点）的总分记为其相反数。机器学习：监督学习

《人工智能导论：模型与算法》提纲二、线性回归一、机器学习基本概念三、AdaBoosting机器学习:从数据中学习知识

图像数据文本数据PersonDog…

喜悦愤怒…类别分类情感分类

}机器学习的分类

监督学习(supervisedlearning)数据有标签、一般为回归或分类等任务无监督学习(un-supervisedlearning)

数据无标签、一般为聚类或若干降维任务强化学习(reinforcementlearning)序列数据决策学习，一般为与从环境交互中学习半监督学习(semi-supervisedlearning)机器学习：分类问题

人员数学好身体好会编程嗓门大程序员AYesNoYesYes作家ANoNoYesNo程序员BYesYesNoNo……………医生AYesYesYesYes程序员CYesYesYesYes程序员DYesYesYesNo从数据中学习

映射函数模式类别标签数据监督学习的重要元素如何学习得到映射模型标注数据学习模型标识了类别信息的数据如何对学习结果进行度量损失函数监督学习：损失函数

监督学习：损失函数典型的损失函数

损失函数名称损失函数定义0-1损失函数平方损失函数绝对损失函数对数损失函数/对数似然损失函数监督学习：训练数据与测试数据

监督学习：经验风险与期望风险

经验风险(empiricalrisk

)训练集中数据产生的损失。经验风险越小说明学习模型对训练数据拟合程度越好。期望风险(expectedrisk):当测试集中存在无穷多数据时产生的损失。期望风险越小，学习所得模型越好。

映射函数训练目标：经验风险最小化(empiricalriskminimization,

ERM)

选取一个使得训练集所有数据损失平均值最小的映射函数。这样的考虑是否够？映射函数训练目标：期望风险最小化(expectedriskminimization)

期望风险是模型关于联合分布期望损失，经验风险是模型关于训练样本集平均损失。根据大数定律，当样本容量趋于无穷时，经验风险趋于期望风险。所以在实践中很自然用经验风险来估计期望风险。由于现实中训练样本数目有限，用经验风险估计期望风险并不理想，要对经验风险进行一定的约束。监督学习：经验风险与期望风险监督学习:“过学习(over-fitting)”与“欠学习(under-fitting)”经验风险小（训练集上表现好）期望风险小（测试集上表现好)泛化能力强经验风险小（训练集上表现好）期望风险大（测试集上表现不好)过学习（模型过于复杂）经验风险大（训练集上表现不好）期望风险大（测试集上表现不好)欠学习经验风险大（训练集上表现不好）期望风险小（测试集上表现好)“神仙算法”或“黄粱美梦”

经验风险最小化期望风险最小化监督学习:结构风险最小

经验风险最小化：仅反映了局部数据期望风险最小化：无法得到全量数据结构风险最小化(structuralriskminimization)：为了防止过拟合，在经验风险上加上表示模型复杂度的正则化项(regulatizer)或惩罚项(penaltyterm)：

模型复杂度经验风险在最小化经验风险与降低模型复杂度之间寻找平衡监督学习两种方法：判别模型与生成模型监督学习方法又可以分为生成方法(generativeapproach)和判别方法(discriminativeapproach)。所学到的模型分别称为生成模型(generativemodel)和判别模型(discriminativemodel).

人脸

=0.99

监督学习两种方法：判别模型与生成模型监督学习

分类识别推荐…提纲二、线性回归一、机器学习基本概念三、AdaBoosting线性回归(linearregression)在现实生活中，往往需要分析若干变量之间的关系，如碳排放量与气候变暖之间的关系、某一商品广告投入量与该商品销售量之间的关系等，这种分析不同变量之间存在关系的研究叫回归分析，刻画不同变量之间关系的模型被称为回归模型。如果这个模型是线性的，则称为线性回归模型。一旦确定了回归模型，就可以进行预测等分析工作，如从碳排放量预测气候变化