导图社区 最强人工智能
- 249
- 28
- 0
- 举报
最强人工智能
根据慕课上的人工智能导论课程整理而来,知识点非常详细,还包括几个其他分页: 早期整理的机器学习算法等。
编辑于2021-01-18 17:36:22- 最强力扣算法题目重点思路代码整理
整理了力扣上面的算法题目的主要思路和代码, 此思维导图会持续更新中, 购买的朋友可通过我个人介绍中的博客加我好友, 我会持续提供更新, 也可和我一起探讨算法问题。
- 最强英语学术写作东南大学
整理了东南大学的英语学术写作的考试重点内容, 旨在培养学生的英语学术写作能力,帮助学生在初步掌握写作技巧的基础上把学术论文写得更加规范,为毕业论文的写作及今后学术研究打下坚实基础。
- 最强Matplotlib思维导图
根据B站莫烦的视频教程整理而来, Matplotlib 是 Python 的绘图库。 它可与 NumPy 一起使用,提供了一种有效的 MatLab 开源替代方案。
最强人工智能
社区模板帮助中心，点此进入>>
- 最强力扣算法题目重点思路代码整理
整理了力扣上面的算法题目的主要思路和代码, 此思维导图会持续更新中, 购买的朋友可通过我个人介绍中的博客加我好友, 我会持续提供更新, 也可和我一起探讨算法问题。
- 最强英语学术写作东南大学
整理了东南大学的英语学术写作的考试重点内容, 旨在培养学生的英语学术写作能力,帮助学生在初步掌握写作技巧的基础上把学术论文写得更加规范,为毕业论文的写作及今后学术研究打下坚实基础。
- 最强Matplotlib思维导图
根据B站莫烦的视频教程整理而来, Matplotlib 是 Python 的绘图库。 它可与 NumPy 一起使用,提供了一种有效的 MatLab 开源替代方案。
- 相似推荐
- 大纲
人工智能
1.人工智能概述
1.概念
1.智能的概念
1.自然界四大奥秘
物质的本质、宇宙的起源、生命的本质、智能的发生
2.主要流派
(1)思维理论：智能的核心是思维 (2)知识阈值理论：智能取决于知识的数量及一般化程度 (3)进化理论：用控制取代知识的表示
3.智能是知识与智力的总和
1.知识是一切智能行为的基础
2.智力是获取知识并应用知识求解问题的能力
2.智能的特征
1.感知能力
通过视觉、听觉、触觉、嗅觉等感觉器官感知外部世界的能力。 80%以上信息通过视觉得到,10%信息通过听觉得到
2.记忆与思维能力
0.简述
1.记忆是存储由感知器官感知到的外部信息以及由思维所产生的知识
2.思维能力是对记忆的信息进行处理
1.逻辑思维(抽象思维)
依靠逻辑进行思维。思维过程是串行的。容易形式化。思维过程具有严密性、可靠性
2.形象思维(直感思维)
依据直觉,思维过程是并行协同式的,形式化困难,在信息变形或缺少的情况下仍有可能得到比较满意的结果
3.顿悟思维(灵感思维)
不定期的突发性,非线性的独创性及模糊性,穿插于形象思维与逻辑思维之中
3.学习能力
学习既可能是自觉的、有意识的,也可能是不自觉的、无意识的既可以是有教师指导的也可以是通过自己实践的
4.行为能力(表达能力)
人们的感知能力：用于信息的输入。行为能力: 信息的输出
3.人工智能
1.人工智能
用人工的方法在机器(计算机)上实现的智能;或者说是人们使机器具有类似于人的智能
2.人工智能学科
一门研究如何构造智能机器(智能计算机)或智能系统使它能模拟延伸扩展人类智能的学科
3.图灵测试
1950年图灵发表的《计算机与智能》中设计了一个测试个测试,用以说明人智能的概念
4.中文屋思考实验
1.锁在屋里的看不懂卡片上汉字的人,根据英文说明书把从门缝中得到的汉字与屋内的汉字进行匹配然后扔出去,从外观上看好像这个人懂中文,而且正确匹配的速度会越来越快,实际上他不懂中文
2.证明：即使通过图灵测试也不能说明计算机能思维
2.发展简史
1.孕育(1956年之前)
公元前,亚里斯多德(Aristotle)：三段论 培根(FBacon)：归纳法 莱布尼茨(G.W.Leibnitz)：万能符号、推理计算 布尔(G.Boole)：用符号语言描述思维活动的基本推理法则推法则 1936年,图灵：图灵机 1943年,麦克洛奇(W.McCulloch)、匹兹(W.Pitts)：M－P模型 美国爱荷华州立大学的阿塔纳索夫教授和他的研究生贝瑞在1937年至1941年间开发的世界上第一台电子计算机“阿塔纳索夫－贝瑞计算机(Atanasoff-BerryComputer,ABC)”为人工智能的研究奠定了物质基础。(不是美国数学家莫克利和埃柯1946年发明的！)
2.形成(1956年－1969年)
1956年夏,当时美国达特茅斯大学数学助教、现任斯坦福大学教授麦卡锡和哈佛大学数学和神经学家、现任MIT教授明 斯基、IBM公司信息研究中心负责人洛切斯特、贝尔实验室信息部数学研究员香农共同发起,邀请普林斯顿大学莫尔和 IBM公司塞缪尔、MIT的塞尔夫里奇和索罗莫夫以及兰德公司和卡内基－梅隆大学的纽厄尔、西蒙等10名年轻学者在达 特莫斯大学个的学术讨会特莫斯大学召开了两个月的学术研讨会,讨论机智能讨论机器智能问题 会上经麦卡锡提议正式采用“人工智能”这一术语,标志着人工智能学科正式诞生。麦卡锡因而被称为人工智能之父 此后,美国形成了多个人工智能研究组织,如纽厄尔和西蒙的CarnegieRAND协作组,明斯基和麦卡锡的MIT研究组, 塞缪尔的IBM工程研究组等 1956年以后,人工智能的研究在机器学习、定理证明、模式识别问题求解专家系统及人工智能语言等方面都取得了许多引人瞩目的成就 1969年,成立了国际人工智能联合会议(International Joint Conferenceson Artificial Intelligence,IJCAI) 1970年,创刊了国际性的人工智能杂志(Artificial Intelligence)
3.发展(1970年－)
1977年,费根鲍姆在第五届国际人工智能联合会议上提出了“知识工程”概念,推动了知识为中心的研究 1981年,日本宣布第五代计算机发展计划,并在1991年展出了研制的PSI－3智能工作站和由PSI－3构成的模型机系统 我国自1978年开始把“智能模拟”作为国家科学技术发展规划的主要研究课题。1981年成立了中国人工智能学会 现在,人工智能已经成为计算机、航空航天、军事装备、工业等众多领域的关键技术
3.基本内容
1.知识表示
1.知识表示
将人类知识形式化或者模型化
2.知识表示方法
符号表示法,连接机制表示法
3.符号表示法
用各种包含具体含义的符号以各种不同的方式和顺序组合起来表示知识的一类方法。例如,一阶谓词逻辑、产生式等
4.连接机制表示法
把各种物理对象以不同的方式及顺序连接起来并在其间互相传递及加工各种包含具体意义的信息,以此来表示相关的概念及知识。例如,神经网络等
2.机器感知
使机器(计算机)具有类似于人的感知能力。以机器视觉(machinevision)与机器听觉为主
3.机器思维
对通过感知得来的外部信息及机器内部的各种工作信息进行有目的的处理
4.机器学习
0.简述
研究如何使计算机具有类似于人的学习能力,使它能通过学习自动地获取知识
1.监督学习(有教师学习):通过响应来反馈
2.强化学习(再励学习或增强学习):通过评价来反馈
3.非监督学习(无教师学习):不用反馈
5.机器行为
计算机的表达能力,即“说”、“写”、“画”等能力
4.主要研究领域
2.一阶谓词逻辑 知识表示法
0.知识和知识表示
1.知识的概念
1.人类知识
在长期的生活及社会实践中、在科学研究及实验中积累起来的对客观世界的认识与经验
2.知识
1.把有关信息关联在一起所形成的信息结构
2.知识反映了客观世界中事物之间的关系,不同事物或者相同事物间的不同关系形成了不同的知识
2.知识的特性
1.相对正确性
任何知识都是在一定的条件及环境下产生的,在这种条件及环境下才是正确的
2.不确定性
知识状态：“真”,“假”,“真”与“假”之间的中间状态
3.可表示性
知识可以用适当形式表示出来,如用语言、文字、图形、神经网络等
4.可利用性
利用知识推理更多新的知识
3.知识的表示
1.将人类知识形式化或者模型化
2.知识表示是对知识的一种描述,或者说是一组约定,一种计算机可以接受的用于描述知识的数据结构
3.原则
充分表示信息,有利于对知识的利用,便于对知识的组织、维护与管理,便于理解与实现
1.命题逻辑
1.命题
一个非真即假的陈述句,若命题的意义为真,称它的真值为真,记为T,若命题的意义为假,称它的真值为假,记为F,一个命题可在一种条件下为真,在另一种条件下为假。
2.命题逻辑
研究命题及命题之间关系的符号逻辑系统
3.命题逻辑表示法
无法把它所描述的事物的结构及逻辑特征反映出来,也不能把不同事物间的共同特征表述出来
2.谓词逻辑
1.表示法
1.谓词的一般形式
P(X1,X2,....XN)
2.个体X1,X2,..XN
某个独立存在的事物或者某个抽象的概念
3.谓词名P
刻画个体的性质、状态或个体间的关系
2.个体
1.常量:一个或者一组指定的个体
2.变量(变元):没有指定的一个或者一组个体,只有把个体具体赋值后才能判断它的真值
3.函数:一个个体到另一个个体的映射
4.谓词/二阶谓词
3.谓词公式
1.连接词(连词)
1.﹁：“否定”(negation)或“非”
2.∨：“析取”(disjunction)——或
3.∧：“合取”(conjunction)——与
4.→：“蕴含”(implication)或“条件”(CONDITION)
5.↔：“等价”(equivalence)或“双条件”(bicondition)
6.谓词逻辑真值表
2.量词
1.全称量词(universalquantifier)(∀x):“对个体域中的所有(或任一个)个体x”。
2.存在量词(existentialquantifier)(∃x):“在个体域中存在个体x”
3.全称量词和存在量词出现的次序将影响命题的意思
3.谓词公式
1.单个谓词是谓词公式,称为原子谓词公式
2.若A是谓词公式,则﹁A也是谓词公式
3.若A,B都是谓词公式,则A∧B,A∨B,A→B,A↔B也都是谓词公式
4.若A是谓词公式,则(∀x)A,(∃x)A也是谓词公式
5.有限步应用(1)－(4)生成的公式也是谓词公式
6.连接词的优先级别从高到低排列：﹁,∧,∨,→,↔
4.量词的辖域
1.量词的辖域
位于量词后面的单个谓词或者用括弧括起来的谓词公式
2.约束变元与自由变元
辖域内与量词中同名的变元称为约束变元,不同名的变元称为自由变元
3.谓词逻辑表示法
1.谓词公式表示知识的步骤
1.定义谓词及个体
2.变元赋值
3.用连接词连接各个谓词,形成谓词公式
2.优点
自然性,精确性,严密性,容易实现
3.缺点
不能表示不确定的知识,组合爆炸,效率低
4.应用
1.自动问答系统(Green等人研制的QA3系统)
2.机器人行动规划系统(Fikes等人研制的STRIPS系统)
3.机器博弈系统(Filman等人研制的FOL系统)
4.问题求解系统(Kowalski等设计的PS系统)
3.产生式表达和 框架表示法
1.产生式表达式
1.产生式
0.简述
1.“产生式”：1943年,美国数学家波斯特(E.Post)首先提出
2.1972年,纽厄尔和西蒙在研究人类的认知模型中开发了基于规则的产生式系统
3.产生式通常用于表示事实、规则以及它们的不确定性度量,适合于表示事实性知识和规则性知识
1.表示
1.确定性规则
基本形式：IF P THEN Q或者：P→Q
2.不确定性规则
基本形式：IF P THEN Q(置信度)或者：P→Q(置信度)
3.确定性事实
三元组表示:(对象,属性,值)或者:(关系,对象1,对象2)
4.不确定性事实
四元组表示：(对象,属性,值,置信度)或者:(关系,对象1,对象2,置信度)
2.与蕴含式区别
1.除逻辑蕴含外,产生式还包括各种操作、规则、变换、算子、函数等。 例如,“如果炉温超过上限,则立即关闭风门”是一个产生式,但不是蕴含式
2.蕴含式只能表示精确知识,而产生式不仅可以表示精确的知识,还可以表示不精确知识。蕴含式的匹配总要求是精确的。产生式匹配可以是精确的,也可以是不精确的只要按某种算法求出的相似度落在预先指定的范围内就认为是可匹配的
3.形式描述及语义 巴科斯范式BNF
<产生式>::=<前提>→<结论> <前提>::=<简单条件>|<复合条件> <结论>::=<事实>|<操作> <复合条件>::=<简单条件>AND<简单条件>[AND<简单条件>…|<简单条件>OR<简单条件>[OR<简单条件>… <操作>::=<操作名>[(<变元>,…)]
符号“::=”表示“定义为”;符号“|”表示“或者是”;符号“[]”表示“可缺省”
2.产生式系统
1.基本结构
2.组成
1.规则库
用于描述相应领域内知识的产生式集合
2.综合数据库(事实库、上下文、黑板等)
一个用于存放问题求解过程中各种当前信息的数据结构
3.控制系统(推理机构)
由一组程序组成,负责整个产生式系统的运行,实现对问题的求解
3.控制系统的工作
(1)从规则库中选择与综合数据库中的已知事实进行匹配。 (2)匹配成功的规则可能不止一条,进行冲突消解。 (3)执行某一规则时,如果其右部是一个或多个结论,则把这些结论加入到综合数据库 中;如果其右部是一个或多个操作,则执行这些操作。 (4)对于不确定性知识,在执行每一条规则时还要按一定的算法计算结论的不确定性。 (5)检查综合数据库中是否包含了最终结论,决定是否停止系统的运行
4.例子:动物识别系统
1.规则库
2.综合数据库
设已知初始事实存放在综合数据库中：该动物身上有：暗斑点,长脖子,长腿,奶,蹄
3.推理机构的工作过程
1.从规则库中取出r1,检查其前提是否可与综合数据库中的已知事实匹配。匹配失败则r1不能被用于推理。然后取r2进行同样的工作。匹配成功则r2被执行
2.综合数据库：该动物身上有：暗斑点,长脖子,长腿,奶,蹄,哺乳动物
3.分别用r3,r4,r5,r6综合数据库中的已知事实进行匹配,均不成功.r7匹配成功,执行r7
4.综合数据库：该动物身上有：暗斑点,长脖子,长腿,奶,蹄,哺乳动物,有蹄类动物
5.r11匹配成功,并推出“该动物是长颈鹿”
3.特点
1.优点
1.自然性,模块性,有效性,清晰性
2.缺点
1.效率不高,不能表达结构性知识
3.适合产生式表示的知识
1.领域知识间关系不密切,不存在结构关系
2.经验性及不确定性的知识,且相关领域中对这些知识没有严格、统一的理论。
3.领域问题的求解过程可被表示为一系列相对独立的操作,且每个操作可被表示为一条或多条产生式规则
2.框架表达式
0.简述
1975年,美国明斯基提出了框架理论:人们对现实世界中各种事物的认识都是以一种类似于框架的结构存储在记忆中的
1.框架表示法
一种结构化的知识表示方法,已在多种系统中得到应用
2.框架(frame)
1.一种描述所论对象(一个事物、事件或概念)属性的数据结构
2.—个框架由若干个被称为“槽”(slot)的结构组成,每一个槽又可根据实际情况划分为若干个“面”(faced)
3.一个槽用于描述所论对象某一方面的属性。
4.一个侧面用于描述相应属性的一个方面。
5.槽和侧面所具有的属性值分别被称为槽值和侧面值。
6.当把具体的信息填入槽或侧面后,就得到了相应框架的一个事例框架
3.一般结构
4.特点
1.结构性
便于表达结构性知识,能够将知识的内部结构关系及知识间的联系表示出来
2.继承性
框架网络中,下层框架可以继承上层框架的槽值,也可以进行补充和修改。
3.自然性
框架表示法与人在观察事物时的思维活动是一致的
4.确定性推理
1.推理的基本概念
1.推理的定义
2.推理方式及其分类
1.演绎推理 归纳推理 默认推理
1.演绎推理
1.一般 → 个别
2.三段论式
1.大前提: 足球运动员的身体都是强壮的
2.小前提: 高波是一名足球运动员
3.结论: 所以,高波的身体是强壮的
2.归纳推理
1.个别 → 一般
2.完全归纳推理(必然性推理)
检查全部产品合格 → 该厂产品合格
3.不完全归纳推理(非必然性推理)
检查全部样品合格 → 该厂产品合格
3.默认推理
知识不完全的情况下,假设某些条件已经具备所进行的推理
2.确定性推理 不确定性推理
1.确定性推理
推理时所用的知识与证据都是确定的,推出的结论也是确定的,其真值或者为真或者为假
2.不确定性推理
推理时所用的知识与证据都是不确定的,推出的结论也是不确定的
1.似然推理 (概率论)
2.近似推理或模糊推理 (模糊逻辑)
3.单调推理 非单调推理
1.单调推理
随着推理向前推进及新知识的加入,推出的结论越来越接近最终目标
2.非单调推理
由于新知识的加入,不仅没有加强已推出的结论,反而要否定它,使推理退回到前面的某一步,重新开始
3.推理的方向
1.正向推理
1.事实驱动推理
已知事实 → 结论
2.基本思想
1.从初始已知事实出发,在知识库KB中找出当前可适用的知识,构成可适用知识集KS
2.按某种冲突消解策略从KS中选出一条知识进行推理,并将推出的新事实加入到数据库DB中作为下一步推理的已知事实,再在知识库KB中选取可适用知识构成知识集KS
3.重复(2),直到求得问题的解或KB中再无可适用的知识
2.逆向推理
1.目标驱动推理
以某个假设目标作为出发点
2.基本思想
1.选定一个假设目标
2.寻找支持该假设的证据,若所需的证据都能找到,则原假设成立；若无论如何都找不到所需要的证据,说明原假设不成立的；为此需要另作新的假设
3.优点
不必使用与目标无关的知识,目的性强,同时它还有利于向用户提供解释
4.缺点
起始目标的选择有盲目性
3.混合推理
1.先正向后逆向
先进行正向推理,帮助选择某个目标,即从已知事实演绎出部分结果,然后再用逆向推理证实该目标或提高其可信度
2.先逆向后正向
先假设一个目标进行逆向推理,然后再利用逆向推理中得到的信息进行正向推理,以推出更多的结论
4.双向推理
正向推理与逆向推理同时进行,且在推理过程中的某一步骤上“碰头”的一种推理
4.冲突消解策略
1.已知事实与知识的匹配情况
1.恰好匹配成功(一对一)
2.不能匹配成功
3.多种匹配成功(一对多、多对一、多对多),需要冲突消解
2.常用冲突消解策略
1.按针对性排序
2.按已知事实的新鲜性(后生成性)排序
3.按匹配度(不确定性推理)排序
4.按条件个数排序(优先选择条件少的)
2.自然演绎推理
1.定义
从一组已知为真的事实出发,运用经典逻辑的推理规则推出结论的过程
2.推理规则
0.P规则(前提引入)、T规则(结论引入)、假言推理、拒取式推理
1.假言推理
2.拒取式推理
3.常见错误
1.否定前件
2.肯定后件
4.例子
5.优点
1.表达定理证明过程自然,易理解
2.拥有丰富的推理规则,推理过程灵活
3.便于嵌入领域启发式知识
6.缺点
易产生组合爆炸,得到的中间结论一般呈指数形式递增
3.归结演绎推理
0.反证法
1.定理
2.思路
P⟹Q → P∧¬Q不可满足 → 子句集不可满足(鲁滨逊归结原理) → 海博伦定理
3.术语
1.原子(atom)谓词公式
一个不能再分解的命题
2.文字(literal)
原子谓词公式及其否定
3.P:正文字,¬P: 负文字
4.子句(clause)
任何文字的析取式∨,任何文字本身也都是子句
5.空子句(NIL)
不包含任何文字的子句,空子句是永假的,不可满足的
6.子句集
由子句构成的集合
4.谓词公式 化子句集
0.例题
1.消去谓词公式中的“→”和“↔”符号
1.
2.把否定符号¬移到紧靠谓词的位置上
1.
3.变量标准化
1.
4.消去存在量词
1.存在量词不出现在全称量词的辖域内:随便用一个个体a,b,c就行
2.存在量词出现在一个或者 多个全称量词的辖域内
变量都是x,都在同一个全称量词下
5.化为前束形
0.前束形=(前缀){母式},(前缀):全称量词串,{母式}:不含量词的谓词公式
1.直接把所有全称量词提到最前面即可
6.化为Skolem标准形
1.
7.略去全称量词
8.消去合取词
1.变为集合的形式,两个子句,子句之间默认合取关系
9.子句变量标准化
1.不同子句使用不同的变元
例题
4.鲁宾逊归结原理
0.简述
1.子句集中子句之间是合取关系,只要有一个子句不可满足,则子句集就不可满足
2.鲁宾逊归结原理(消解原理)的基本思想: 检查子句集S中是否包含空子句,若包含,则S不可满足;若不包含,在S中选择合适的子句进行归结,一旦归结出空子句,就说明S是不可满足的。
1.命题逻辑中的归结原理 (基子句的归结)
1.归结定义
设C1与C2是子句集中的任意两个子句,如果C1中的文字L1与C2中的文字L2互补,那么从C1和C2中分别消去L1和L2,并将二个子句中余下的部分析取,构成一个新子句C12。
2.定理
归结式C12是其亲本子句C1与C2的逻辑结论。即如果C1与C2为真则C12为真
3.推论1
设C1与C2是子句集S中的两个子句,C12是它们的归结式,若用C12代替C1与C2后得到新子句集S1,则由S1不可满足性可推出原子句集S的不可满足性,即S1的不可满足性→S的不可满足性
4.推论2
设C1与C2是子句集S中的两个子句,C12是它们的归结式,若C12加入原子句集S,得到新子句集S1,则S与S1在不可满足的意义上是等价的,即S1的不可满足性↔S的不可满足性
2.谓词逻辑中的归结原理 (含有变量的子句的归结)
1.
2.例题
3.结论
1.对于谓词逻辑,归结式是其亲本子句的逻辑结论
2.对于一阶谓词逻辑,即若子句集是不可满足的,则必存在一个从该子句集到空子句的归结演绎;若从子句集存在一个到空子句的演绎,则该子句集是不可满足的
3.如果没有归结出空子句,则既不能说S不可满足,也不能说S是可满足的
5.归结反演
1.定义
应用归结原理证明定理的过程
2.步骤
(1)将已知前提表示为谓词公式F。 (2)将待证明的结论表示为谓词公式Q,并否定得到﹁Q。 (3)把谓词公式集{F,¬Q}化为子句集S。 (4)应用归结原理对子句集S中的子句进行归结,并把每次归结得到的归结式都并入到S中。如此反复进行,若出现了空子句,则停止归结,此时就证明了Q为真
3.例题
6.归结反演求解问题
1.步骤
2.例题
5.不确定性推理
1.不确定推理
0.简述
1.推理
从已知事实(证据)出发,通过运用相关知识逐步推出结论或者证明某个假设成立或不成立的思维过程。
2.不确定性推理
从不确定性的初始证据出发,通过运用不确定性的知识,最终推出具有一定程度的不确定性但却是合理或者近乎合理的结论的思维过程。
1.不确定性的表示与度量
1.知识不确定性的表示
在专家系统中知识的不确定性一般是由领域专家给出的,通常是一个数值—知识的静态强度
2.证据不确定性的表示
用户在求解问题时提供的初始证据,在推理中用前面推出的结论作为当前推理的证据
3.不确定性的度量
1.能充分表达相应知识及证据不确定性的程度。
2.度量范围的指定便于领域专家及用户对不确定性的估计。
3.便于对不确定性的传递进行计算,而且对结论算出的不确定性度量不能超出度量规定的范围,度量的确定应当是直观的,同时应有相应的理论依据。
2.不确定性匹配算法及阈值的选择
1.不确定性匹配算法
用来计算匹配双方相似程度的算法
2.阈值
用来指出相似的限度
3.组合证据不确定性的算法
最大最小方法、Hamacher方法、概率方法、有界方法、Einstein方法等
4.不确定性的传递算法
在每一步推理中,如何把证据及知识的不确定性传递给结论。在多步推理中,如何把初始证据的不确定性传递给最终结论。
5.结论不确定性的合成
2.可信度方法
0.简述
1.1975年肖特里菲(E.H.Shortliffe)等人在确定性理论(theoryofconfirmation)的基础上,结合概率论等提出的一种不确定性推理方法
2.优点：直观、简单,且效果好
3.可信度：根据经验对一个事物或现象为真的相信程度
4.可信度带有较大的主观性和经验性,其准确性难以把握
5.C－F模型：基于可信度表示的不确定性推理的基本方法
1.知识不确定性的表示
1.产生式规则表示
IF E THEN H(CF(H,E))
2.CF(H,E)
1.可信度因子,反映前提条件与结论的联系强度
2.CF(H,E)的取值范围:[-1,1]
3.若由于相应证据的出现增加结论H为真的可信度,则CF(H,E)>0,证据的出现越是支持为真,就使CF(H,E)的值越大。反之,CF(H,E)<0,证据的出现越是支持为假,CF(H,E)的值就越小。
4.若证据的出现与否与H无关,则CF(H,E)=0。
2.证据不确定性的表示
1.CF(E)＝0.6：E的可信度为0.6
2.证据E的可信度取值范围:[-1,1]。对于初始证据,若所有观察S能肯定它为真,则CF(E)=-1。若肯定它为假,则CF(E)=—1。若以某种程度为真,则0<CF(E)<1。若以某种程度为假,则—1<CF(E)<0。若未获得任何相关的观察,则CF(E)=0。
3.静态强度CF(H,E)
知识的强度,即当E所对应的证据为真时对H的影响程度
4.动态强度CF(E)
证据E当前的不确定性程度
3.组合证据不确定性的算法
1.多个单一证据的合取and
CF(E)=min{CF(E1),CF(E2)....CF(En)}
2.多个单一证据的析取or
CF(E)=max{CF(E1),CF(E2)....CF(En)}
4.不确定性的传递算法
1.C－F模型中的不确定性推理：从不确定的初始证据出发,通过运用相关的不确定性知识最终推出结论并求出结论的可信度值。结论H的可信度由下式计算
2.CF(H)=CF(H,E)×max{0,CF(E)}
当CF(E)<0时,则CF(H)=0 当CF(E)=1时,则CF(H)=CF(H,E)
5.结论不确定性的合成算法
IF E1 THEN H(CF(H,E1)) IF E2 THEN H(CF(H,E2))
1.分别对每一条知识求出CF(H) CF1(H)=CF(H,E1)×max{0,CF(E1)} CF2(H)=CF(H,E2)×max{0,CF(E2)}
2.求出E1与E2对H的综合影响所形成的可信度CF12(H)
3.例题
3.证据理论
0.简述
1.证据理论(theoryofevidence)：又称D－S理论,是德普斯特(A.P.Dempster)首先提出,沙佛(G.Shafer)进一步发展起来的一种处理不确定性的理论
2.1981年巴纳特(J.A.Barnett)把该理论引入专家系统中,同年卡威(JGarvey)等人用它实现了不确定性推理
3.目前,在证据理论的基础上已经发展了多种不确定性推理模型
1.概率分配函数
1.样本空间
1.设D是变量x所有可能取值的集合,且D中的元素是互斥的,在任一时刻x都取且只能取D中的某一个元素为值,则称D为x的样本空间。
2.在证据理论中,D的任何一个子集A都对应于一个关于x的命题,称该命题为“x的值是在A中”。
2.概率分配函数
1.设D为样本空间,领域内的命题都用D的子集表示
3.几点说明
1.设样本空间D中有n个元素,则D中子集的个数为2^n个。2^D: D的所有子集。
2.概率分配函数:把D的任意一个子集A都映射为[0,1]上的一个数M(A)。A∈D﹐A≠D时,M(A):对应命题A的精确信任度
3.概率分配函数与概率不同
2.信任函数
1.
2.Bel(A):对命题A为真的总的信任程度。仅为属于A的所有子集
3.空子集的信任函数是0,整个空间的信任函数是1
3.似然函数
1.又称不可驳斥函数或上限函数
2.
3.信任函数是为真的可能性,似然函数是非假的可能性
4.概率分配函数的正交和 (证据的组合)
1.定义
2.例题
5.基于证据理论的 不确定性推理
1.步骤
(1)建立问题的样本空间D。 (2)由经验给出,或者由随机性规则和事实的信度度量算基本概率分配函数。 (3)计算所关心的子集的信任函数值、似然函数值。 (4)由信任函数值、似然函数值得出结论。
2.例题
3个样本空间不好理解
6.模糊推理方法
1.模糊逻辑的提出
1.1965年,美国L.A.Zadeh发表了“fuzzyset”的论文,首先提出了模糊理论
2.从1965年到20世纪80年代,在美国、欧洲、中国和日本,只有少数科学家研究模糊理论
3.1974年,英国Mamdani首次将模糊理论应用于热电厂的蒸汽机控制
4.1976年,Mamdani又将模糊理论应用于水泥旋转炉的控制
5.1983年日本Fuji Electric公司实现了饮水处理装置的模糊控制
6.1987年日本Hitachi公司研制出地铁的模糊控制系统
7.1987年－1990年在日本申报的模糊产品专利就达319种
8.目前,各种模糊产品充满日本、西欧和美国市场,如模糊洗衣机、模糊吸尘器、模糊电冰箱和模糊摄像机等
2.模糊集合与 隶属函数
1.模糊集合的定义
1.论域
所讨论的全体对象,用U等表示
2.元素
论域中的每个对象,常用a,b,c,x,y,z表示
3.集合
论域中具有某种相同属性的确定的、可以彼此区别的元素的全体,常用A,B等表示
4.元素a和集合A的关系
a属于A或a不属于A,即只有两个真值“真”和“假”
5.隶属函数
模糊逻辑给集合中每一个元素赋予一个介于0和1之间的实数,描述其属于一个集合的强度,该实数称为元素属于一个集合的隶属度。集合中所有元素的隶属度全体构成集合的隶属函数
2.模糊集合的 表示方法
0.通用
1.Zadeh表示法
2.序偶表示法
3.向量表示法
不能缺省
3.隶属函数
1.常见的隶属函数有正态分布、三角分布、梯形分布
2.确定方法:模糊统计法,专家经验法,二元对比排序法,基本概念扩充法
3.举例
3.模糊关系及合成
1.模糊关系
1.定义
A、B：模糊集合,模糊关系用叉积(cartesianproduct)表示：R:A×B→[0,1]
2.叉积常用最小算子运算:取小运算
3.A、B：离散模糊集的隶属函数
4.叉积运算:必须用圈,代表模糊合成
5.举例
2.合成
4.模糊推理
1.模糊知识表示
1.人类思维判断的基本形式
如果(条件)→则(结论)
2.模糊规则
从条件论域到结论论域的模糊关系矩阵R。通过条件模糊向量与模糊关系R的合成进行模糊推理,得到结论的模糊向量,然后采用“清晰化”方法将模糊结论转换为精确量
2.对IF A THEN B类型 的模糊规则的推理
1.定义
2.例题
5.模糊决策
0.模糊决策/模糊判决/解模糊/清晰化
由模糊推理得到的结论或者操作是一个模糊向量,转化为确定值的过程
1.最大隶属度法
2.加权平均判决法
3.中位数法
6.模糊推理应用
7.搜索求解策略
1.搜索的概念
0.简述
1.在求解一个问题时,涉及到两个方面:一是该问题的表示,如果一个问题找不到一个合适的表示方法,就谈不上对它求解。
2.另一方面则是选择一种相对合适的求解方法。由于绝大多数需要人工智能方法求解的问题缺乏直接求解的方法,因此,搜索为一种求解问题的一般方法。
1.概念
1.问题求解
问题的表示,求解方法
2.问题求解的基本方法
搜索法,归纳法,归结法,推理法,产生式
2.基本问题
1.是否一定能找到一个解
2.找到的解是否是最佳解
3.时间与空间复杂性如何
4.是否终止运行或是否会陷入一个死循环
3.主要过程
1.从初始或目的状态出发,并将它作为当前状态。
2.扫描操作算子集,将适用当前状态的一些操作算子作用于当前状态而得到新的状态,并建立指向其父结点的指针
3.检查所生成的新状态是否满足结束状态,如果满足,则得到问题的一个解,并可沿着有关指针从结束状态反向到达开始状态,给出一解答路径;否则,将新状态作为当前状态,返回第(2)步再进行搜索
4.搜索方向
1.数据驱动
从初始状态出发的正向搜索——从问题给出的条件出发
2.目的驱动
从目的状态出发的逆向搜索——从想达到的目的入手,看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件
3.双向搜索
从开始状态出发作正向搜索,同时又从目的状态出发作逆向搜索,直到两条路径在中间的某处汇合为止
5.盲目式搜索
在不具有对特定问题的任何有关信息的条件下,按固定的步骤(依次或随机调用操作算子)进行的搜索
6.启发式搜索
考虑特定问题领域可应用的知识,动态地确定调用操作算子的步骤,优先选择较适合的操作算子,尽量减少不必要的搜索,以求尽快地到达结束状态
2.状态空间搜素
1.表示法
1.状态
表示系统状态、事实等叙述型知识的一组变量或数组：Q=[q1,q2,...,qn]^T
2.操作
表示引起状态变化的过程型知识的一组关系或函数：F={f1,f2,...,fn}
3.状态空间
利用状态变量和操作符号,表示系统或问题的有关知识的符号体系,状态空间是一个四元组：(S,O,S0,G)
S:状态集合。 O:操作算子的集合。 S:包含问题的初始状态是S的非空子集。 G:若干具体状态或满足某些性质的路径信息描述。
4.求解路径
从S0结点到G结点的路径
5.状态空间的一个解
一个有限的操作算子序列
2.图描述
2.1盲目式策略
1.回溯策略
1.定义
从初始状态出发,不停地、试探性地寻找路径,直到它到达目的或“不可解结点”,即“死胡同”为止。若它遇到不可解结点就回溯到路径中最近的父结点上,查看该结点是否还有其他的子结点未被扩展。若有,则沿这些子结点继续搜索；如果找到目标,就成功退出搜索,返回解题路径
2.算法
1.PS(path states)表
保存当前搜索路径上的状态。如果找到了目的,PS就是解路径上的状态有序集
2.NPS(new path states)表
新的路径状态表,包含了等待搜索的状态,其后裔状态还未被搜索到,即未被生成扩展
3.NSS(no solvable states)表
不可解状态集,列出了找不到解题路径的状态。如果在搜索中扩展出的状态是它的元素,则可立即将之排除,不必沿该状态继续搜索
3.思想
1.用未处理状态表(NPS)使算法能返回(回溯)到其中任一状态
2.用一张“死胡同”状态表(NSS)来避免算法重新搜索无解的路径
3.在PS表中记录当前搜索路径的状态,当满足目的时可以将它作为结果返回
4.为避免陷入死循环必须对新生成的子状态进行检查,看它是否在该三张表中
2.宽度优先
1.open表(NPS表)
已经生成出来但其子状态未被搜索的状态
2.closed表( PS表和NSS表的合并)
记录了已被生成扩展过的状态
3.深度优先
1.在深度优先搜索中,当搜索到某一个状态时,它所有的子状态以及子状态的后裔状态都必须先于该状态的兄弟状态被搜索
2.具体问题应具有一定的深度限制值,或采取不断加大深度限制值的办法,反复搜索,直到找到解
4.深度受限
5.迭代深度
3.启发式策略
1.启发式信息
用来简化搜索过程有关具体问题领域的特性的信息叫做启发信息
2.特点
重排OPEN表,选择最有希望的节点加以扩展
3.种类
A、A*算法
4.两种基本情况
1.一个问题由于存在问题陈述和数据获取的模糊性,可能会使它没有一个确定的解
2.虽然一个问题可能有确定解,但是其状态空间特别大,搜索中生成扩展的状态数会随着搜索的深度呈指数级增长
5.例子
4.启发信息 和估价函数
1.启发信息
在具体求解中,能够利用与该问题有关的信息来简化搜索过程,称此类信息为启发信息
2.启发式搜索
利用启发信息的搜索过程
3.求解问题中能利用的 大多是非完备的启发信息
1.求解问题系统不可能知道与实际问题有关的全部信息,因而无法知道该问题的全部状态空间,也不可能用一套算法来求解所有的问题
2.有些问题在理论上虽然存在着求解算法,但是在工程实践中,这些算法不是效率太低,就是根本无法实现
4.按运用的方法分类
1.陈述性启发信息：用于更准确、更精炼地描述状态
2.过程性启发信息：用于构造操作算子
3.控制性启发信息：表示控制策略的知识
1.没有任何控制性知识作为搜索的依据,因而搜索的每一步完全是随意的
2.有充分的控制知识作为依据,因而搜索的每一步选择都是正确的,但这是不现实的
5.按作用分类
1.用于扩展节点的选择,即用于决定应先扩展哪一个节点,以免盲目扩展
2.用于生成节点的选择,即用于决定要生成哪些后继节点,以免盲目生成过多无用的节点
3.用于删除节点的选择,即用于决定删除哪些无用节点,以免造成进一步的时空浪费
6.估价函数f
估算节点“希望”程度的量度,并依次给它们排定次序(在open表中)
7.估价函数值f(n)
1.从初始节点经过n节点到达目标节点的路径的最小代价估计值,其一般形式是f(n)=g(n)+h(n)
2.g(n)
从初始节点S0到节点n的实际代价
3.h(n)
从节点n到目标节点Sg的最优路径的估计代价,称为启发函数
4.h(n)比重大
降低搜索工作量,但可能导致找不到最优解,比重越大,表示启发性越强
5.h(n)比重小
一般导致工作量加大,极限情况下变为盲目搜索,但可能可以找到最优解
8.例子
5.A搜索算法
1.A搜索算法
使用了估价函数f的一种加权启发式图搜索算法
2.OPEN表
1.保留所有已生成而未扩展的状态
2.进入open表的状态是根据其估值的大小插入到表中合适的位置,每次从表中优先取出启发估价函数值最小的状态加以扩展
3.CLOSED表
记录已扩展过的状态
4.启发式搜索特点
如何寻找并设计启发函数h(n),然后以f(n)的大小来排列OPEN表中待扩展状态的次序,每次选择f(n)值最小者进行扩展
5.流程图
6.例题
6.A*搜索算法
1.定义
1.目前最有影响的启发式图搜索算法,也称为最佳图搜索算法
2.定义h*(n)为状态n到目的状态的最优路径的代价,则当A搜索算法的启发函数h(n)≤h*(n)时,称为A*搜索算法
3.如果某一问题有解,那么利用A*搜索算法对该问题进行搜索则一定能搜索到解,并且一定能搜索到最优的解而结束
4.上例中的八数码A搜索树也是A*搜索树,所得的解路(s,B,E,I,K,L)为最优解路,其步数为状态L(5)上所标注的5
2.可采纳性
当一个搜索算法在最短路径存在时能在有限步内保证找到它,就称该算法是可采纳的
3.单调性
1.A*搜索算法并不要求g(n)=g*(n),则可能会沿着一条非最佳路径搜索到某一中间状态,如果对启发函数h(n)加上单调性的限制,就可以总从祖先状态沿着最佳路径到达任一状态
2.如果某一启发函数h(n)满足： a)对所有状态ni和nj,其中nj是ni的后裔,满足h(ni)-h(nj)<=cost(ni,nj),其中cost(ni,nj)是从ni到nj的实际代价 b)目的状态的启发函数值为0。则称h(n)是单调的
3.A*搜索算法中采用单调性启发函数,可以减少比较代价和调整路径的工作量,从而减少搜索代价
4.信息性
1.在两个A*启发策略的h1和h2中,如果对搜索空间中的任一状态n都有h1(n)≤h2(n),就称策略h2比h1具有更多的信息性
2.如果某一搜索策略的h(n)越大,则A*算法搜索的信息性越多,所搜索的状态越少
3.但更多的信息性需要更多的计算时间,可能抵消减少搜索空间所带来的益处
8.遗传算法及应用
0.进化算法
1.概念
1.进化算法(evolutionary algorithms,EA)是基于自然选择和自然遗传等生物进化机制的一种搜索算法
2.生物进化是通过繁殖、变异、竞争和选择实现的； 而进化算法则通过重组、变异和选择这三种操作实现优化问题的求解
3.进化算法是一个“算法簇”,包括遗传算法(GA)、遗传规划、进化策略和进化规划等
4.进化算法的基本框架是遗传算法所描述的框架
5.进化算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域
2.生物学背景
1.物竞天择、适者生存
最适合自然环境的群体往往产生了更大的后代群体
2.基本过程
3.设计原则
1.适用性原则
一个算法的适用性是指该算法所能适用的问题种类,它取决于算法所需的限制与假定
2.可靠性原则
一个算法的可靠性是指算法对于所设计的问题,以适当的精度求解其中大多数问题的能力
3.收敛性原则
指算法能否收敛到全局最优。在收敛的前提下,希望算法具有较快的收敛速度
4.稳定性原则
指算法对其控制参数及问题的数据的敏感度
5.生物类比原则
在生物界被认为是有效的方法及操作可以通过类比的方法引入到算法中,有时会带来较好的结果
1.基本遗传算法
0.简述
1.受自然界和生物界规律的启迪,人们根据其原理模仿设计了许多求解问题的算法,包括人工神经网络、模糊逻辑、遗传算法、DNA计算、模拟退火算法、禁忌搜索算法、免疫算法、膜计算、量子计算、粒子群优化算法、蚁群算法、人工蜂群算法、人工鱼群算法以及细菌群体优化算法等,这些算法称为智能计算也称为计算智能(computational Intelligence,CI)
2.智能优化方法通常包括进化计算和群智能等两大类方法,是一种典型的启发式随机优化方法,已经广泛应用于组合优化、机器学习、智能控制、模式识别、规划设计、网络安全等领域,是21世纪有关智能计算中的重要技术之一
1.遗传算法
0.genetic algorithms,GA
1.一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题
2.遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域
2.基本思想
1.在求解问题时从多个解开始,然后通过一定的法则进行逐步迭代以产生新的解,得到的是一组解,可以根据不同标准进行选择
3.特点
1.遗传算法是一种全局优化概率算法,对所求解的优化问题没有太多的数学要求,由于进化特性,搜素过程中不需要问题的内在性质,无论是线性的还是非线性的,离散的还是连续的都可处理,可直接对结构对象进行操作。
2.利用随机技术指导对一个被编码的参数空间进行效率搜索。采用群体搜索策略,易于并行化
3.仅用适应度函数值来评估个体,并在此基础上进行遗传操作,使种群中个体之间进行信息交换
4.进化算子的各态历经性使得遗传算法能够非常有效地进行概率意义的全局搜素
5.遗传算法对于各种特殊问题可以提供极大的灵活性来混合构造领域独立的启发式,从而保证算法的有效性
2.基本操作
1.编码
1.位串编码
0.定义
一维染色体编码方法：将问题空间的参数编码为一维排列的染色体的方法
1.二进制编码
0.定义
用若干二进制数表示一个个体,将原问题的解空间映射到位串空间B={0,1}上,然后在位串空间上进行遗传操作
1.优点
类似于生物染色体的组成,算法易于用生物遗传理论解释,遗传操作如交叉、变异等易实现;算法处理的模式数最多
2.缺点
1.相邻整数的二进制编码可能具有较大的Hamming距离,降低了遗传算子的搜索效率
15：01111 16：10000 两者在二进制上相差较远
2.要先给出求解的精度
3.求解高维优化问题的二进制编码串长,算法的搜索效率低
2.Gray编码
将二进制编码通过一个变换进行转换得到的编码 解决较大的Haming距离
2.实数编码
1.采用实数表达法不必进行数制转换,可直接在解的表现型上进行遗传操作
2.多参数映射编码的基本思想：把每个参数先进行二进制编码得到子串,再把这些子串连成一个完整的染色体
3.多参数映射编码中的每个子串对应各自的编码参数,所以,可以有不同的串长度和参数的取值范围
2.适应度函数
1.将目标函数映射成 适应度函数的方法
2.适应度函数 的尺度变换
0.简述
1.欺骗问题
在遗传算法中,将所有妨碍适应度值高的个体产生,从而影响遗传算法正常工作的问题
2.过早收敛
缩小这些个体的适应度,以降低这些超级个体的竞争力
3.停滞现象
改变原始适应值的比例关系,以提高个体之间的竞争力
4.尺度变换/定标
对适应度函数值域的某种映射变换
1.线性变换
2.幂函数变换法
3.指数变换法
3.选择
1.个体选择概率 分配方法
0.简述
1.选择操作也称为复制(reproduction)操作：从当前群体中按照一定概率选出优良的个体,使它们有机会作为父代繁殖下一代子孙
2.判断个体优良与否的准则是各个个体的适应度值：个体适应度越高,其被选择的机会就越多
1.适应度比例方法/ 蒙特卡罗法
各个个体被选择的概率和其适应度值成比例
2.排序方法
1.线性排序
群体成员按适应值大小从好到坏依次排列,按转盘式选择的方式选择父体
2.非线性排序
将群体成员按适应值从好到坏依次排列,并按下式分配选择概率
2.选择个体方法
1.转盘赌选择
1.按个体的选择概率产生一个轮盘,轮盘每个区的角度与个体的选择概率成比例
2.产生一个随机数,它落入转盘的哪个区域就选择相应的个体交叉
2.锦标赛选择
1.锦标赛选择
从群体中随机选择个个体,将其中适应度最高的个体保存到下一代。这一过程反复执行,直到保存到下一代的个体数达到预先设定的数量为止
2.随机竞争
每次按赌轮选择方法选取一对个体,然后让这两个个体进行竞争,适应度高者获胜。如此反复,直到选满为止
3.最佳个体保存
把群体中适应度最高的个体不进行交叉而直接复制到下一代中,保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体
4.交叉
1.基本的交叉算子
1.一点交叉
在个体串中随机设定一个交叉点,实行交叉时,该点前或后的两个个体的部分结构进行互换,并生成两个新的个体
2.二点交叉
随机设置两个交叉点,将两个交叉点之间的码串相互交换
2.修正的交叉方法
1.部分匹配交叉PMX
5.变异
1.位点变异
群体中的个体码串,随机挑选一个或多个基因座,并对这些基因座的基因值以变异概率作变动
2.逆转变异
在个体码串中随机选择两点(逆转点),然后将两点之间的基因值以逆向排序插入到原位置中
3.插入变异
在个体码串中随机选择一个码,然后将此码插入随机选择的插入点中间
4.互换变异
随机选取染色体的两个基因进行简单互换
5.移动变异
随机选取一个基因,向左或者向右移动一个随机位数
3.一般步骤
0.流程图
1.使用随机方法或者其它方法,产生一个有N个染色体的初始群体pop(1),t:=1
2.对群体中的每一个染色体popi(t),计算其适应值fi=fitness(popi(t))
3.若满足停止条件,则算法停止;否则,以概率pi从pop(t)中随机选择一些染色体构成一个新种群newpop(t+1)={popj(t)|j=1,2,...,N}
4.以概率Pc进行交叉产生一些新的染色体,得到一个新的群体crosspop(t+1)
5.以一个较小的概率Pm使染色体的一个基因发生变异,形成mutpop(t+1);t:=t+1,成为一个新的群体pop(t)=mutpop(t+l),返回(2)
4.改进算法
1.双倍体遗传算法
1.基本思想
1.双倍体遗传算法采用显性和隐性两个染色体同时进行进化,提供了一种记忆以前有用的基因块的功能
2.双倍体遗传算法采用显性遗传
3.双倍体遗传延长了有用基因块的寿命,提高了算法的收敛能力,在变异概率低的情况下能保持一定水平的多样性
2.设计
1.编码/解码
两个染色体(显性、隐性)
2.复制算子
计算显性染色体的适应度,按照显性染色体的复制概率将个体复制到下一代群体中
3.交叉算子
两个个体的显性染色体交叉、隐性染色体也同时交叉
4.变异算子
个体的显性染色体按正常的变异概率变异；隐性染色体按较大的变异概率变异
5.显隐性重排算子
个体中适应值较大的染色体设为显性染色体,适应值较小的染色体设为隐性染色体
2.双种群遗传算法
1.基本思想
1.在遗传算法中使用多种群同时进化,并交换种群之间优秀个体所携带的遗传信息,以打破种群内的平衡态达到更高的平衡态,有利于算法跳出局部最优
2.建立两个遗传算法群体,分别独立地运行复制、交叉、变异操作,同时当每一代运行结束以后,选择两个种群中的随机个体及最优个体分别交换
2.设计
1.编码/解码设计
2.交叉算子、变异算子
3.杂交算子
4.设种群A与种群B,当A与B种群都完成了选择、交叉、变异算子后,产生一个随机数num,随机选择A中num个个体与A中最优个体,随机选择B中num个个体与B中最优个体,交换两者,以打破平衡态
3.自适应遗传算法
1.基本思想
0.Srinvivas M.,Patnaik L. M.等在1994年提出一种自适应遗传算法(adaptive genetic algorithms,AGA)：Pc和Pm能随适应度自动改变
1.当种群各个体适应度趋于一致或者趋于局部最优时,使Pc和Pm增加,以跳出局部最优；而当群体适应度比较分散时,使Pc和Pm减少,以利于优良个体的生存
2.同时,对于适应度高于群体平均适应值的个体,选择较低的Pc和Pm,使得该解得以保护进入下一代；对低于平均适应值的个体,选择较高的Pc和Pm值,使该解被淘汰
9.群智能算法
1.粒子群优化算法
0.产生背景
1.粒子群优化(Particle Swarm Optimization,PSO)算法是由美国普渡大学的Kennedy和Eberhart于1995年提出,它的基本概念源于对鸟群觅食行为的研究
2.一群鸟在随机搜寻食物,在这个区域里只有一块食物,所有的鸟都不知道食物在哪里,但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢
3.最简单有效的就是搜寻目前离食物最近的鸟的周围区域
1.基本原理
1.基本思想
将每个个体看作n维搜索空间中一个没有体积质量的粒子,在搜索空间中以一定的速度飞行,该速度决定粒子飞行的方向和距离。所有粒子有一个由优化函数决定的适应值
2.基本原理
PSO初始化为一群随机粒子,然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解,这个解称为个体极值。另一个是整个种群目前找到的最优解,这个解称为全局极值
3.算法定义
1.在n维连续搜索空间中,对粒子群中的第i(i=1,2,...,m)个粒子进行定义
4.基本的PSO算法
第1部分是粒子在前一时刻的速度; 第2部分为个体“认知”分量,表示粒子本身的思考,将现有的位置和曾经经历过的最优位置相比。 第3部分是群体“社会(social)”分量,表示粒子间的信息共享与相互合作。 ψ1,ψ2分别控制个体认知分量和群体社会分量相对贡献的学习率。 随机系数增加搜索方向的随机性和算法多样性
5.四种类型的PSO模型
1.若ψ1>0,ψ2>0,则称该算法为PSO全模型
2.若ψ1>0,ψ2=0,则称该算法为PSO认知模型
3.若ψ1=0,ψ2>0,则称该算法为PSO社会模型
4.若ψ1=0,ψ2>0且g≠i,则称该算法为PSO无私模型
6.算法流程
1.初始化每个粒子
在允许范围内随机设置每个粒子的初始位置和速度
2.评价每个粒子的适应度
计算每个粒子的目标函数
3.设置每个粒子的Pi
对每个粒子,将其适应度与其经历过的最好位置Pi进行比较,如果优于Pi,则将其作为该粒子的最好位置Pi
4.设置全局最优值Pg
对每个粒子,将其适应度与群体经历过的最好位置Pg进行比较,如果优于Pg,则将其作为当前群体的最好位置Pg
5.更新粒子的速度和位置
根据式(6.20)更新粒子的速度和位置
6.检查终止条件
如果未达到设定条件(预设误差或者迭代的次数),则返回第(2)步
7.流程图
2.参数分析
1.PSO算法的参数
1.最大速度Vmax
对速度vi,算法中有最大速度Vmax作为限制,如果当前粒子的某维速度大于最大速度Vmax,则该维的速度就被限制为最大速度Vmax
2.权重因子
3个权重因子：惯性权重w,加速度ψ1,ψ2
2.位置更新方程中 各部分的影响
1.只有第1部分,即ψ1=ψ2=0
粒子将一直以当前的速度飞行,直到达边界。由于它只能搜索有限的区域,所以很难找到好解
2.没有第1部分,即w=0
速度只取决于粒子当前位置和其历史最好位置Pi和Pg,速度本身没有记忆性
3.没有第2部分,即ψ1=0
粒子没有认知能力,也就是“只有社会模型”,在粒子的相互作用下,有能力达到新的搜索空间。但对复杂问题,容易陷入局部最优点
4.没有第3部分,即ψ2=0
粒子间没有社会共享信息,也就是“只有认知”模型,因为个体间没有交互,一个规模为M的群体等价于M个单个粒子的运行,因而得到最优解的机率非常小
3.参数设置
早期的实验：w固定为1.0,ψ1和ψ2固定为2.0,因此Vmax成为唯一需要调节的参数,通常设为每维变化范围10％~20%。Suganthan的实验表明,ψ1和ψ2为常数时可以得到较好的解,但不一定必须为2,这些参数也可以通过模糊系统进行调节。Shi和Eberhart提出一个模糊系统来调节w
3.应用领域
4.车辆路径问题
1.问题
假定配送中心最多可以用K(k=1,2…K)辆车对L(i=1,2.…L)个客户进行运输配送,i=0表示仓库。每个车辆载重为bk(k=1,2,…K),每个客户的需求为di(i=1,2,…L),客户i到客户j的运输成本为cij(可以是距离,时间,费用等)。定义如下变量:
2.数学模型
3.编码与初始种群
1.对这类组合优化问题,编码方式、初始解的设置对问题的求解都有很大的影响,采用常用的自然数编码方式
2.对于K辆车和L个客户的问题,用从1到L的自然数随机排列来产生一组解X=(x1,x2,...,xL)。然后分别用节约法或者最近插入法构造初始解
4.实验结果
o 粒子群优化算法的各个参数设置如下： o 种群规模：50 o 迭代次数：1000 o c1的初始值为1，随迭代的进行，线性减小到0 o C2=c3=1.4 o Vmax<1000 o 优化结果及其与遗传算法的比较如表6.4所示
2.蚁群算法
0.简述
1.产生背景
1.20世纪90年代初,意大利科学家MarcoDorigo等受蚂蚁觅食行为的启发,提出蚁群算法(Ant Colony Optimization,ACO)
2.一种应用于组合优化问题的启发式搜索算法
3.在解决离散组合优化方面具有良好的性能
2.基本思想
1.信息素跟踪
按照一定的概率沿着信息素较强的路径觅食
2.信息素遗留
会在走过的路上会释放信息素,使得在一定的范围内的其他蚂蚁能够觉察到并由此影响它们的行为
3.规则
1.环境
有障碍物、有其他蚂蚁、有信息素
2.觅食规则
范围内寻找是否有食物,否则看是否有信息素,每只蚂蚁都会以小概率犯错
3.移动规则
都朝信息素最多的方向移动,无信息素则继续朝原方向移动,且有随机的小的扰动,有记忆性
4.避障规则
移动的方向如有障碍物挡住,蚂蚁会随机选择另一个方向
5.信息素规则
越靠近食物播撒的信息素越多,越离开食物播撒的信息素越少
1.算法模型
1.旅行商问题
1.问题
在寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径成本
2.搜索过程
通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径
2.蚁群系统模型
3.三种不同模型
1.蚂蚁圈系统
2.蚂蚁数量系统
3.蚂蚁密度系统
4.比较
4.全局信息更新优点
1.保证了残留信息素不至于无限累积
2.如果路径没有被选中,那么上面的残留信息素会随时间的推移而逐渐减弱,这使算法能“忘记”不好的路径
3.
4.充分体现了算法中全局范围内较短路径(较好解)的生存能力
5.加强了信息正反馈性能
6.提高了系统搜索收敛的速度
2.参数选择
1.信息素启发因子α
1.反映了蚁群在路径搜索中随机性因素作用的强度
2.α值越大,蚂蚁选择以前走过的路径的可能性越大,搜索的随机性减弱
3.当α过大时会使蚁群的搜索过早陷于局部最优
2.期望值启发式因子β
1.反映了蚁群在路径搜索中先验性、确定性因素作用的强度
2.β值越大,蚂蚁在某个局部点上选择局部最短路径的可能性越大
3.虽然搜索的收敛速度得以加快,但蚁群在最优路径的搜索过程中随机性减弱,易于陷入局部最优
3.信息素挥发度1-ρ
1.当要处理的问题规模比较大时,会使那些从来未被搜索到的路径(可行解)上的信息量减小到接近于0,因而降低了算法的全局搜索能力
2.而且当1-ρ过大时,以前搜索过的路径被再次选择的可能性过大,也会影响到算法的随机性能和全局搜索能力
3.反之,通过减小信息素挥发度1-ρ虽然可以提高算法的随机性能和全局搜索能力,但又会使算法的收敛速度降低
3.应用
1.柔性作业车间调度
某加工系统有6台机床,要加工4个工件,每个工件有3道工序,如图
2.分析
由图6.12可以看出机器6并没有加工任何工件。分析其原因为它虽然可以加工工序p23,p33,p42,p43但从表6.5可知机器6的加工时间大于其他可加工机器,特别是p23,p33的加工时间,因此机器6并未分到任何加工任务
3.最优解甘特图/收敛图
10.BP神经网络和 Hopfield神经网络
1.神经元和神经网络
0.简述
1.人工神经网络是对人脑或生物神经网络若干基本特性的抽象和模拟。为机器学习等许多问题的研究提供了一条新的思路,目前已经在模式识别、机器视觉、联想记忆、自动控制、信号处理、软测量、决策分析、智能计算、组合优化问题求解、数据挖掘等方面获得成功应用
2.神经网络
0.neural networks,NN
1.生物神经网络NNN
由中枢神经系统(脑和脊髓)及周围神经系统(感觉神经、运动神经等)所构成的错综复杂的神经网络,其中最重要的是脑神经系统
2.人工神经网络ANN
模拟人脑神经系统的结构和功能,运用大量简单处理单元经广泛连接而组成的人工网络系统
3.神经网络方法：隐式的知识表示方法
1.生物神经元的结构
0.简述
1.人脑构造:皮层(cortex),中脑(midbrain),脑干(brainstem),小脑(cerebellum)
2.人脑由一千多亿(10^11－10^14)个神经细胞(神经元)交织在一起的网状结构组成,其中大脑皮层约140亿个神经元,小脑皮层约1000亿个神经元
3.神经元约有1000种类型,每个神经元大约与10^3－10^4个其他神经元相连接,形成极为错综复杂而又灵活多变的神经网络
1.生物神经元结构
2.工作状态
1.兴奋状态：细胞膜电位>动作电位的阈值→神经冲动
2.抑制状态：细胞膜电位<动作电位的阈值
3.学习与遗忘
由于神经元结构的可塑性,突触的传递作用可增强和减弱
2.神经元数学模型
1.M-P模型
2.一般模型
3.线性环节
4.非线性环节
5.工作过程
3.神经网络结构与 工作方式
1.决定人工神经网络 性能的三大要素
1.神经元的特性
2.神经元之间相互连接的形式——拓扑结构
3.为适应环境而改善性能的学习规则
2.神经网络的结构
1.前馈型:BP神经网络
前面神经元的输出只作为下一层神经元的输入,静态映射
2.反馈型:Hopfield
输出信号直接或间接地反馈到输入端作为输入信号,非线性动力学系统
3.工作方式
1.同步(并行)方式
任一时刻神经网络中所有神经元同时调整状态
2.异步(串行)方式
任一时刻只有一个神经元调整状态,而其它神经元的状态保持不变
两者有一些区别,但是不是太大
2.BP神经网络
1.BP神经网络结构
1.BP网络结构
2.输入输出变换关系
3.工作过程
1.第一阶段/网络训练阶段
对网络的连接权进行学习和调整,以使该网络实现给定样本的输入输出映射关系
2.第二阶段/工作阶段
把实验数据或实际数据输入到网络,网络在误差范围内预测计算出结果
2.BP学习算法
1.两个问题
1.是否存在一个BP神经网络能够逼近给定的样本或者函数
2.如何调整BP神经网络的连接权,使网络的输入与输出与给定的样本相同
2.基本思想
3.学习算法
1.正向传播
输入信息由输入层传至隐层,最终在输出层输出
2.反向传播
修改各层神经元的权值,使误差信号最小
3.BP算法的实现
1.BP算法的设计
1.隐层数及隐层神经元数的确定
目前尚无理论指导
2.初始权值的设置
一般以一个均值为0的随机分布设置网络的初始权值
3.训练数据预处理
线性的特征比例变换,将所有的特征变换到[0,1]或者[-1,1]区间内,使得在每个训练集上,每个特征的均值为0,并且具有相同的方差
4.后处理过程
当应用神经网络进行分类操作时,通常将输出值编码成所谓的名义变量,具体的值对应类别标号
2.计算机实现流程
1.初始化
对所有连接权和阈值赋以随机任意小值
2.从N组输入输出样本中取一组样本
x=[x1,x2,…,xp1]^T,d=[d1,d2,…,dpm]^T,把输入信息x=[x1,x2,…,xp1]^T输入到BP网络中
3.正向传播
计算各层节点的输出
4.计算网络的实际输出与期望输出的误差
5.反向传播
从输出层方向计算到第一个隐层,按连接权值修正公式向减小误差方向调整网络的各个连接权值
6.让t+1→t,取出另一组样本重复(2)－(5),直到N组输入输出样本的误差达到要求时为止
3.流程图
4.特点分析
1.特点
BP网络：多层前向网络(输入层、隐层、输出层)。 连接权值：通过Delta学习算法进行修正。 神经元传输函数：S形函数。 学习算法：正向传播、反向传播。 层与层的连接是单向的,信息的传播是双向的
2.优点
很好的逼近特性,具有较强的泛化能力,具有较好的容错性
3.缺点
收敛速度慢,局部极值,难以确定隐层和隐层结点的数目
3.BP神经网络在 模式识别中应用
1.模式识别
1.模式识别研究用计算机模拟生物、人的感知,对模式信息,如图像、文字、语音等,进行识别和分类
2.传统人工智能的研究部分地显示了人脑的归纳、推理等智能。但是,对于人类底层的智能,如视觉、听觉、触觉等方面,现代计算机系统的信息处理能力还不如一个幼儿园的孩子
3.神经网络模型模拟了人脑神经系统的特点：处理单元的广泛连接;并行分布式信息储存、处理;自适应学习能力等
4.神经网络模式识别方法具有较强的容错能力、自适应学习能力、并行信息处理能力
2.应用
1.问题
设计一个三层BP网络对数字0至9进行分类
2.方法
1.每个数字用97的网格表示,灰色像素代表0,黑色像素代表1。将每个网格表示为0,1的长位串。位映射由左上角开始向下直到网格的整个一列,然后重复其他列
2.选择BP网络结构为63-6-9。97个输入结点,对应上述网格的映射。9个输出结点对应10种分类
3.使用的学习步长为0.3。训练600个周期,如果输出结点的值大于0.9,则取为ON,如果输出结点的值小于0.1,则取为OFF
4.离散Hopfield 神经网络
1.定义
全互联网络,任意两个结点均有反馈,不反馈到自己
2.网络结构
3.输入输出关系
4.工作方式
5.工作过程
6.网络的稳定性
1.若从某一时刻开始,网络中所有神经元的状态不再改变,即x=f(Wx-θ),则称该网络是稳定的,x为网络的稳定点或吸引子
2.Hopfield神经网络是高维非线性系统,可能有许多稳定优态。从任何初始状态开始运动,总可以到某个稳定状态。这些稳定状态可以通过改变网络参数得到
7.稳定性定理
1.串行稳定性——W：对称阵
2.并行稳定性——W：非负定对称阵
5.连续Hopfield 神经网络
1.网络模型
2.网络稳定性
5.Hopfield的应用
1.联想记忆中应用
0.问题
1.设计DHNN结构
2.设计连接权矩阵
3.测试
2.优化方法
1.一般步骤
1.将优化问题的每一个可行解用换位矩阵表示
2.将换位矩阵与由n个神经元构成的神经网络相对应：每一个可行解的换位矩阵的各元素与相应的神经元稳态输出相对应
3.构造能量函数,使其最小值对应于优化问题的最优解,并满足约束条件
4.用罚函数法构造目标函数,与Hopfield神经网络的计算能量函数表达式相等,确定各连接权和偏置参数
5.给定网络初始状态和网络参数等,使网络按动态方程运行,直到稳定状态,并将它解释为优化问题的解
2.应用举例
3.存在的问题
1.解的不稳定性
2.参数难以确定
3.能量函数存在大量局部极小值,难以保证最优解。
11.深度神经网络
1.卷积神经网络
0.简述
1.BP的不足
1.BP神经网络以数值作为输入。如果要处理图像相关的信息,则要先从图像中提取特征
2.由于BP算法依赖于梯度调参,也容易陷入局部最优解
3.随着神经网络的层数加深,训练过程存在严重的“梯度扩散”现象,即网络的输出结果通过反向传播,当到达最前面的几层时,梯度会逐渐消失,不能指引网络权值的训练,从而导致网络训练过程不能收敛
4.BP算法一般只能用于浅层网络结构(通常等于3)的学习,限制了BP算法的数据表征能力,影响了在工程中的应用
5.努力方向：增加神经网络隐层的层数,也就是深度,所以相应的神经网络称为深度神经网络(DNN),相应的学习算法被称为深度学习(deep learning,DL)
2.深度神经网络 的生物学基础
1.2006年,Hinton教授和博士生萨拉赫丁诺夫(Salakhutdinov)根据生物学的重要发现,提出了深度学习方法
2.1968年神经生物学家大卫•休伯尔(David HunterHubel)与托斯坦•威泽尔(TorstenN.Wiesel)在研究猫脑皮层中用于局部敏感和方向选择的神经元时,有两个重要发现:
a.对于视觉的编码,动物大脑皮层的神经元存在局部感受域,也就是说,它们是局部敏感的且具有方向选择性
b.动物大脑皮层是分级、分层处理的。在大脑的初级视觉皮层中存在三类细胞：简单细胞、复杂细胞和超复杂细胞,这些不同类型细胞承担不同抽象层次的视觉感知功能
3.2006年,Hinton教授等在著名学术刊物《科学》上发表深度神经网络学习算法,给出了两个重要结论：
a.具有多个隐层的人工神经网络具有更好的特征学习能力,每一层特征的抽取都是前一层的抽象,学习到的特征更好地刻画了数据。深度学习分层预训练的本质,就是对输入数据进行逐级抽象,符合生物大脑的认知过程
b.通过逐层初始化的“逐层预训练”,可以找到一个接近最优解的神经网络权值,然后再通过“微调”对整个网络进行优化训练,从而大幅减少训练多层神经网络所需的时间
1.定义
卷积神经网络(Convolutional Neural Networks,CNN)是一种多层神经网络,每层由多个二维平面组成,而每个平面由多个独立神经元组成
2.一般结构
3.卷积运算
4.四大技术 减少计算量
1.局部连接
2.权值共享
3.多卷积核
4.池化
1.通过卷积获得了特征之后,如果直接利用这些特征训练分类器,计算量是非常大的,对不同位置的特征进行聚合统计,称为池化(pooling)
2.池化常用方法：平均池化、最大池化
3.卷积神经网络在池化层丢失大量的信息,从而降低了空间分辨率,导致了对于输入微小的变化,其输出几乎是不变的
5.应用
1.手写数字识别系统的卷积网络：YannLeCun于1998年提出的LeNet-5。美国大多数银行当年用它识别支票上面的手写数字,达到了商用地步
2.过程
2.胶囊网络
1.概念
1.针对卷积神经网络训练数据需求大、环境适应能力弱、可解释性差、数据分享难等不足,2017年10月,GeoffreyE.Hinton教授等在“神经信息处理系统大会上发表论文,提出了新型神经网络结构——胶囊网络(Capsule Networks)
2.胶囊是一个包含多个神经元的载体,每个神经元表示了图像中出现的特定实体的各种属性
3.胶囊不是传统神经网络中的一个神经元,而是一组神经元
4.胶囊网络的核心思想：胶囊里封装的检测特征的相关信息是以向量的形式存在的,胶囊的输入是一个向量,是用一组神经元来表示多个特征
2.基本结构
0.图像
1.输入层
数字图片经过标准的卷积层,有256个通道,每个通道均用9×9的卷积核,将输入层图片中的像素亮度转化成局部特征输出,作为Conv1层的输入
2.PrimaryCaps层
卷积的胶囊层,包含32个胶囊。PrimaryCaps才是胶囊真正开始的地方
3.DigitCaps层
胶囊网络的全连接层,要识别的是10类数字(0~9),因此该层的胶囊个数共有10个,每个胶囊表示的向量中元素的个数为16,代表着不同状态下的同一个数字
3.学习运算
1.输入
2.耦合系数
3.非线性激活函数
非线性激活函数squashing也称为压缩函数,前一部分是输入向 量线性求和S的缩放尺度,后一部分是线性求和S的单位向量
4.动态路由算法
在胶囊网络中用动态路由算法代替了卷积神经网络中的池化,都是一种对有用信息的提取方式
算法解释
5.损失函数
网络的卷积参数和Capsule内的权值都要根据损失函数进行更新。采用的损失函数是最大化正负样本到超平面的距离
6.重构网络
0.图像
1.重构是用预测的类别Capsule向量,即模值最大的向量重新构建出该类别代表的实际图像
2.重构网络重构包含三个全连接层的网络解码器。该解码器输出784个数字,对应重构图像的像素个数(28x28=784像素)
3.这一过程的损失函数通过计算FCSigmoid层的输出像素与原始图像像素点的欧氏距离而构建
4.实验
1.在手写数字图像数据集MNIST上的部分实验结果
2.泛化能力实验结果
对MNIST测试集的数字大小、粗细、位置做了部分改变。实验结果：CapsNet在有重叠数字的AFFNIST数据集上获得了比CNN好得多的结果
3.识别数字高度重叠的实验
1.MultiMNIST上两个数字的边框范围平均有80%是重合的数字
2.MultiMNIST图片(白色)和由CapsNet重构后的结果(红色和绿色)重合的数字
3.实验结果：CapsNet实现了较低的分类错误率
5.特点
1.使用胶囊神经网络需要的训练数据量,远小于卷积神经网络,它采用动态路由协议算法,仅使用三层网络便可表现出很出色的性能,能够与深度卷积神经网络相当
2.胶囊网络解决了卷积神经网络存在的信息丢失、视角变化等问题
3.由于胶囊网络具有分别处理不同属性的能力,相比于CNN可以提高对图像变换的鲁棒性,在图像分割中也会有出色的表现
4.胶囊网络相对于卷积网络的工作机理更接近人脑的工作方式
3.生成对抗网络
1.简述
0.典型的无监督深度学习网络
1.深度学习模型分为判别式模型和生成式模型
2.判别模型是将一个高维的感官输入映射为一个类别标签
3.生成网络把随机点变成与数据集相似的图片
4.目前深度学习取得的成果主要集中在判别式模型
5.Goodfellow等于2014年提出生成对抗网络(GAN),使用对抗训练机制对两个神经网络进行训练
6.生成模型将一个高斯噪声矢量z映射为一个生成概率分布,通过优化损失函数调整参数使生成概率分布尽可能逼近真实数据分布
2.结构
3.训练
1.GAN的两个相互交替的训练阶段：固定生成网络,训练判别网络;固定判别网络,训练生成网络
2.两个网络相互对抗的过程,就是各自网络参数不断调整的过程,即学习过程
4.应用
图像修复,图像风格迁移,图像翻译,艺术创作,从文字描述生成图片,诗歌写作,AI换脸术,新闻播报机器人
5.问题
1.GAN在训练中容易出现一些问题,训练过程具有强烈的不稳定性,实验结果随机,具体表现;
2.训练难以收敛,经常出现震荡;
3.训练收敛,但出现模式崩溃: 有几种状态总是不出现
4.训练收敛,但还会生成一些没有意义或者现实中不可能出现的图片
12.专家系统及 知识图谱
1.定义
专家系统是一种智能的计算机程序,它运用知识和推理来解决只有专家才能解决的复杂问题,一类包含知识和推理的智能计算机程序
2.基本组成
3.特点
1.编程思想
传统程序=数据结构+算法
专家系统=知识+推理
2.运用知识的方式
传统程序：关于问题求解的知识隐含于程序中
专家系统：知识单独组成知识库,与推理机分离
3.处理对象
传统程序：数值计算和数据处理
专家系统：还有符号处理
4.解释功能
传统程序：不具有解释功能
专家系统：具有解释功能
5.正确性
传统程序：产生正确的答案
专家系统：通常产生正确的答案,有时产生错误的答案
6.系统的体系结构不同
4.工作原理
5.知识获取
1.主要过程
抽取知识,知识的转换,知识的输入,知识的检测
2.模式
1.非自动化知识获取
科技文献/领域专家→知识工程师→知识编辑器→知识库
2.自动知识获取
6.建立
1.什么情况下开发专家系统是可能的?
1.主要依靠经验性知识,不需运用大量常识性知识就可解决的任务。
2.存在真正的领域专家
3.有明确的开发目标,且任务不太难实
2.什么情况下开发专家系统是合理的?
1.具有较高的经济效益
2.人类专家奇缺,但在许多地方又十分需要
3.人类专家经验不断丢失
4.危险场合需要专业知识
3.什么情况下开发专家系统是合适的?
1.本质:问题能通过符号操作和符号结构进行求解,且需使用启发式知识、经验规则才能得到答案
2.复杂性
3.范围:所选任务的大小可驾驭、任务有实用价值。
4.设计原则和开发步骤
专门的任务,专家合作,原型设计,用户参与,辅助工具,知识库与推理机分离
7.实例
1.医学专家系统MYCIN
1.系统结构
1.MYCIN系统由斯坦福大学1972年开始建造,1978年最终完成
2.系统用INTERLISP语言编写
3.知识库有二百多条规则,可识别51种病菌,正确处理23种抗生素
4.结构图
2.数据表示:上下文树
3.知识表示
1.领域知识的表示：产生式规则
RULE 064 如果：有机体染色是革兰氏阳性， 且 是有机形态是球状的， 且 有机体的生长结构呈链状， 则：存在证据表明该有机体为链球菌类，可信度为0.7。 RULE 064 PREMISE: ( $ AND (SAME CNTXT STALN GRAMPOS) (SAME CNTXT MORPH COCCUS) (SAME CNTXT CONFORM CHAINS)) ACTION: (CONLUDE CNTXT IDENT STREPTO COCCUS TALLY.7)
2.临床参数的表示
临床参数：三元组（上下文树、属性、值） 例：三元组（机体－1，形态，杆状） 三元组（机体－1，染色体，革兰氏阴性） 临床数据：单值、是非值、多值。 MYCIN系统有65个临床参数，按照其相对应的上下文分类
1.临床参数：三元组(上下文树、属性、值)
2.临床数据：单值、是非值、多值
4.推理策略
1.反向推理、深度优先的搜索策略
2.MYCIN系统：通过两个子程序MONITOR和FINDOUT完成整个咨询和推理过程
3.MONITOR：分析规则的前提条件是否满足,以决定拒绝该规则还是采用该规则,并将每次鉴定一个前提后的结果记录在动态数据库中
4.FINDOUT：检查MONITOR所需要的参数,它可能已在动态数据库中,也可以通过用户提问获取
5.治疗方案选择
1.生成可能的“治疗方案表”
2.选择用药配方
该药物对细菌治疗的有效性。 该药物是否已用过。 该药物的副作用
6.知识获取
(1) 告诉专家新建立的规则的名字（规则序号）。 (2) 逐条获取前提，并从英文翻译成LISP表达。 (3) 逐条获取结论动作，也从英文翻译为LISP表达。 (4) 用LISP-english子程序将规则翻译成英语，显示给专家。 (5) 提问专家是否同意这条翻译的规则；如果规则不正确， 专家进行修改并回到步骤 (4)。 (6) 检查新规则与其他旧规则之间的矛盾。 (7) 如果有必要，可调用辅助分类规则对新规则分类。 (8) 把规则加入LOOKHEAD表。 (9) 把规则加入CONTAIED-IN表、UPDATED-BY表。 (10) 告诉专家系统新规则已是规则库中的一部分了
2.地质勘探专家系统 PROSPECTOR
1.系统结构
1.总体结构
2.模型文件 (模型知识库)
12个模型文件,表达成推理规则网络,共有1100多条规则。规则的前提是地质勘探数据,结论的前提是推理得出的地质假设如矿床分类、含量、分布等
3.术语文件 (术语知识库)
有400种岩石、地质名字地质年代和在语义网络中用的其他术语
4.分析器
将模型文件转换成系统内部的推理网络
5.推理网络
具有层次结构的与/或树,将勘探数据和有关地质假设联系起来,进行从顶到底的逐级推理,上一级的结论作为下一级的证据,直到结论可由勘探数据直接证实的端结点为止
6.匹配器
用于语义网络匹配
7.传送器
用于修正推理网络中模型空间状态变化的概率值
8.英语分析器
对用户以简单的英语陈述句输入的信息进行分析,并变换到语义网络上
9.问答系统
检查推理网络的推理过程及模型的运行情况,用户可以随时对系统进行查询,系统也可以对用户提出问题,要求提供勘探证据。知识获取系统：获取专家知识,增删、修改推理网络
10.网络编译程序
通过钻井定位模型,根据推理结果,编制钻井井位选择方案,输出图像信息
11.解释系统
对用户解释有关结论和断言的推理过程、步骤和依据
12.知识获取系统
获取专家知识,增删、修改推理网络
2.系统的功能
勘探结果评价,矿区勘探评测,编制井位计划
3.推理网络
一个矿床模型经编码而成的网络,把探区证据和一些重要地质假设连接成一个有向图
4.推理方法
1.似然推理：根据Bayes原理的概率关系进行推理,用“似然率”表示规则的强度
2.逻辑推理：基于布尔逻辑关系的推理
3.上、下文推理：基于上、下文语义关系的推理
8.开发工具
1.骨架系统
1.EMYCIN系统
1.功能
解释程序,知识编辑程序及类英语的简化会话语言,知识库管理和维护手段,跟踪和调试功能
2.工作过程
专家系统建立过程,咨询过程
3.应用
2.KAS系统
1.定义
1.由PROSPECTOR系统抽去原有的地质勘探知识而形成的,适用于开发解释型专家系统
2.采用产生式规则和语义网络相结合的知识表达方法及启发式正反向混合推理控制策略
2.网络编辑程序
把用户输入的信息转化为相应的语义网络,并检测语法错误和一致性等
3.网络匹配程序
分析任意两个语义网络之间的关系,是否具有等价、包含、相交等关系,从而决定是否匹配,同时检测知识库中的知识是否存在矛盾、冗余等
4.应用
1.用于帮助化学工程师选择化工生产中的物理参数
2.用于根据飞行物的特征和当时的环境条件来识别飞机型号
3.EXPERT系统
1.简述
威斯(Weiss)、库里科斯基(Kulikowski)等人在CASNET系统(青光眼诊断系统)等的基础上于1981年设计完成的一个骨架系统,适用开发诊断和分类型专家系统
2.组成
EXPERT系统的知识由假设、事实和决策规则三部分组成
事实：有待观察、测量和确定的证据。 假设：由系统推出来的结论。 规则：描述事实和假设之间的逻辑关系
3.三种规则
1.FF规则
从事实到事实的规则
2.FH规则
从事实到假设的规则
3.HH规则
从假设到假设的规则
4.推理过程
1.由事实对所有的FF规则进行推理
2.从已有的事实出发,检查所有的FH规则,如果其左部为真,就将其右部的假设存入集合PH中
3.置集合DH为空
4.从已有事实出发,检查所有的HH规则的上下文
5.按假设所形成的推理网络进行推理
6.对假设的选择除可按上述方法选择可信度最大的外,还设置了评分函数
5.应用
2.通用型知识 表达语言OPS5
1.简述
美国卡内基－梅隆大学的麦可达莫特(J.McDermott)、纽厄尔(A.Newell)等研制开发的一种通用知识表达语言
2.特点
将通用的表达和控制结合起来,提供了专家系统所需的基本机制,并不偏向于某些特定的问题求解策略和知识表达结构
3.组成
产生式规则库、推理机、数据库
4.应用
3.开发环境
1.简述
可为专家系统的开发提供多种方便的构件,例如知识获取的辅助工具、适用各种不同知识结构的知识表示模式、各种不同的不确定推理机制、知识库管理系统等
2.AGE(attempttogeneralize)
一种典型的模块组合式开发工具
3.通过AGE构造专家系统的途径
1.用户使用AGE现有的各种组件作为构造材料,方便地组合设计所需系统
2.用户通过AGE的工具界面,定义和设计各种所需的组成部件,以构成自己的专家系统
4.程序设计语言
1.符号处理语言
0.面向AI的语言或AI语言
1.PROLOG语言(R.Kowalski首先提出;1972年,A.Comerauer及其研究小组研制成功)：基于演绎推理的逻辑型程序设计语言
2.LISP语言(1960年,麦卡锡及其研究小组研制成功)：表处理语言,许多早期专家系统(MYCIN、PROSPECTOR)是用LISP建立的
2.面向问题的语言
C语言、C＋＋语言
9.知识图谱
1.提出
由于互联网内容的大规模、异质多元、组织结构松散的特点，给人们有效获取信息和知识提出了挑战。 谷歌为了利用网络多源数据构建的知识库来增强语义搜索，提升搜索引擎返回的答案质量和用户查询的效率，于2012年5月16日首先发布了知识图谱（Knowledge Graph）。 现在的知识图谱已被用来泛指各种大规模的知识库。Google、百度和搜狗等搜索引擎公司为了改进搜索质量，纷纷 构建知识图谱，分别称为知识图谱、知心和知立方
1.目的
为了提高搜索引擎能力,改善用户的搜索质量,改善用户的搜索体验
2.定义
1.定义
又称科学知识图谱,用各种不同的图形等可视化技术描述知识资源及其载体,挖掘、分析、构建、绘制和显示知识及它们之间的相互联系。它把复杂的知识领域通过数据挖掘、信息处理、知识计量和图形绘制而显示出来,揭示知识领域的动态发展规律
2.表示形式
知识图谱以结构化的形式描述客观世界中概念、实体间的复杂关系,将互联网的信息表达成更接近人类认知世界的形式,提供了一种更好地组织、管理和理解互联网海量信息的能力
3.本质
知识库、语义网络
4.形式
1.RDF提供了资源的通用描述方式
2.图数据库是指以图作为数据结构存储和查询数据的数据库
5.基于符号的表示
0.知识图谱本质上是一种语义网络
1.结点代表实体(entity)或者概念(concept)
2.边代表实体/概念之间的各种语义关系/属性
3.关系事实=(head,relation,tail)
head：头部实体 relation：关系/属性 tail：尾部实体
6.图表示
知识图谱也可被看作是一张图,图中的节点表示实体或概念,而图中的边则由属性或关系构成
7.通用表示形式
0.三元组是知识图谱的一种通用表示方式。三元组的基本形式主要分为两种形式
1.(实体1-关系-实体2),中国-首都-北京
2.(实体-属性-属性值),北京-人口-2069万
3.架构与构建
1.架构
1.逻辑结构
模式层与数据层
2.体系架构
体系架构是其构建模式结构,虚线框内的部分为知识图谱的构建过程,也包含知识图谱的更新过程。获取知识的资源对象大体可分为结构化、半结构化和非结构化三类
体系架构图
2.构建
基于信息抽取自动创建,大众协作编辑创建,专家人工创建
4.知识的抽取
0.简述
1.知识抽取是从不同来源、不同结构的数据中进行知识提取,形成知识(结构化数据)存入知识图谱
2.主要面向开放的链接数据,典型输入是自然语言文本或者图像或者视频多媒体内容文档等。然后通过自动化或者半自动化技术抽取出可用的知识单元
3.知识单元主要包括实体(概念的外延)、关系以及属性三个知识要素
1.实体抽取
也称为实体学习/命名实体识别,是从原始的数据语料中自动识别出命名实体
2.语义类抽取
语义类抽取是指文本中自动抽取信息来构造语义类并建立实体和语义类的关联,作为实体层面上的规整和抽象
3.属性和属性值抽取
属性抽取的任务是为每个本体语义类构造属性列表 属性值抽取为一个语义类的实体附加属性值 两者能够形成完整的实体概念的知识图谱维度
4.关系抽取
目标是解决实体语义链接的问题,关系的基本信息包括参数的类型, 满足此关系的元组模式等
5.典型应用
13.机器学习
1.发展
1.为什么要学习
1.图像分类问题：ILSVRC-2010数据集,大于1000类,人眼不能完全辨识。能否找到一个函数F,实现对图片的准确分类
2.人脸识别问题：不同成像环境下,如何准确识别同一个人
3.目标检测问题：检测图像中的不同目标的位置及大小
4.航空公司客户价值分析问题：如何对客户进行价值分类
2.什么是机器学习
1.机器学习是一门人工智能的科学,该领域的主要研究对象是人工智能,特别是如何在经验学习中改善具体算法的性能
2.机器学习是对能通过经验自动改进的计算机算法的研究
3.机器学习是用数据或以往的经验,以此优化计算机程序的性能标准
机器学习基于数据和经验,针对具体问题构建数学模型,实现对已有数据的准确解析或对未来数据的准确分类、识别和预测
3.三者关系
1.人工智能AI
搜索、规划、专家系统、智能游戏、博弈论、机器人、机器学习等
2.机器学习ML
监督式学习、无监督学习,学习理论和算法都重要
3.模式识别PR
监督式学习,偏重算法应用
4.发展历程
1.线性感知机1958
解决一系列分类问题,不能解决异或问题
2.支持向量机1995
在小样本的情况下,能够得到更好的效果
3.深度学习2012至今
5.领域划分
1.按任务划分
分类,回归(线性拟合,非线性拟合),聚类
2.按学习能力划分
有监督学习,无监督学习,半监督学习,强化学习
2.方法
1.有监督学习
1.逻辑回归
1.定义
对于每个训练样本都能找到它的正确标签
2.输入x
图像,视频,音频
3.输出y
类别,位置及大小,深度
4.二分类问题
5.经验风险选择
1.平方误差(绿色)
导致惩罚过于正确的分类
2.0-1误差(黑色)
目标函数难以优化
3.逻辑回归经验风险(红色)
6.经验风险的 概率意义
1.定义正类的PDF (概率密度函数)
2.定义负类的PDF
3.所有类的PDF
7.整体经验风险函数
正则化项
对学习模型的复杂度进行限制,不然会出现最右边的情况:过拟合 分类函数会变得非常复杂,在训练样本上效果很好,在测试样本上效果很差 通过正则化项希望得到B图样子
8.梯度下降算法
1.训练问题
2.梯度
2.多分类逻辑回归
1.解决多类问题
0.多分类:
1.对于k类问题,训练k个one vs.the rest分类器(二分类问题) 综合k个分类器的结果判别
如苹果-非苹果分类器、梨-非梨分类器、香蕉-非香蕉分类器
2.直接训练多类逻辑回归分类器
2.多分类问题的PDF
3.在样本i上的代价函数
3.随机森林
1.标签混杂度
1.假设有一组标签
2.标签混杂度(不确定性)定义为
3.标签的纯净程度,都是0.5时最混杂,为1,有一个概率为0或1时,最纯净为0
2.信息增益
1.运用某个规则把一组数据S分为数个子集, 怎样衡量这种划分的好坏
2.在学习过程中,每次划分(通过选择某个特征)都以最大化信息增益为准则
3.决策树
4.随机森林
1.决策树的缺陷
容易过拟合(overfit training samples)
2.解决方案
1.Tree bagging:多次有重复随机采样训练样本,对每次采样训练一棵决策树,预测结果等于所有树对不同标签进行投票
2.Feature bagging:训练决策树时,每次划分都基于一组随机特征进行(消除强特征带来的决策树关联问题)
4.性能比较
缺少严格证明,只有经验结果
5.线性回归
1.已有房子价格数据D,有一套新房子,预测这套房值多少钱？
2.假设房价由线性函数定义
3.
2.半监督学习
0.简述
1.训练数据
2.半监督学习目标
训练一个更好(与仅使用带标签数据相比)的分类器
3.为什么使用不带标签的样本
数据标注要聘请专业人员,数据标注需要专业设备
4.为什么无标签数据可能对学习有利
假设每一类数据构成一个相关组(例如服从高斯分布),利用无标签数据能学到更好的决策边界
1.自训练算法
3.无监督学习
1.k-means聚类
1.聚类定义
2.核心思想
相似的点聚为一类
3.目标函数
4.例子
5.交替搜索求解
1.目标1：给定中心点,求解每个数据点所属的类
2.目标2：给定数据点类别,求解中心点
4.强化学习
1.奖励矩阵
2.Q学习算法
1.学习和R同阶的知识矩阵Q(quality),假设状态数目已知,初始化Q为全零矩阵
模型对比
3.技术
1.参数优化
2.数据增广
0.如何在不增加标注的前提下扩充训练数据？
1.数据增广
2.针对图像/视频数据：旋转,缩放+裁剪,翻转,随机色彩变换,GAN
3.性能评价
1.定量评价
1.正确率accuracy(分类)
2.模糊矩阵(confusionmatrix)
3.查准率precision、查全率recall(检索)
2.定性评价
实验结果可视化
14.智能体系统
1.概念
1.定义
1.智能体是嵌入于某一环境中,具有自主行动能力的计算机程序或者实体
2.它能够通过传感器(sensor)感知环境,并通过效应器(effector)影响环境,进而完成给定的设计目标
2.特性
1.自主性
能够在没有人或其他智能体的直接干预下正常工作
2.反应性
智能体能够及时对环境的变化做出反应
3.主动性
智能体会主动去完成自身的设计目标,表现出受目标驱动的自发行为
4.社会性
不同智能体之间具有通信交流的能力,能够协作完成任务,在遇到冲突时能够协商解决问题
2.结构
1.体系结构
智能体的内部工作结构,定义了智能体从感知环境信息到行为决策,到最后执行外部动作的整个过程
2.智能体程序
在agent体系结构下进行实际运算的函数,Agent=体系结构+程序
3.常见体系结构
反应式体系结构、慎思式体系结构以及复合式体系结构
4.反应式体系结构
1.简述
1.根据当前的感知信息来选择行动,不考虑历史信息
2.通过If-then规则对当前环境状态和自身行为动作进行映射
3.智能体直接使用感知信息进行映射,不需要内部通过符号建立环境模型,加快了反应式智能体的运行速度
2.结构
1.行为模型：有限状态机(finite-statemachine)
2.动作选择：状态到动作的映射(不含复杂的符号表示)
3.同一时间可能有多个行为满足动作选择规则
4.分层式结构：低层规则优先级高
3.实例
1.条件
1.火星探测器在火星上收集岩石样本并把样本运回基地
2.岩石的位置未知
3.探测器可以接受到基地发出的无线电信号
2.过程
1.如果发现障碍物,则改变方向
2.如果处于基地并且携带着样本,那么放下样本
3.如果携带着样本且不在基地,则往无线电信号增强的方向移动
4.如果检测到样本,则采集样本
5.随机移动(iftrue)
4.优点
简单、优雅、环境反馈及时
5.缺点
1.由于没有环境模型,无法考虑历史信息,无法预测其它智能体的行为
2.在设计时非常困难(需要通过不断实验得出),没有标准方法
3.debug非常困难
4.当智能体拥有的规则数量很大时,设计与实现非常困难(例如,规则之间的优先级与交互)
5.难以与人进行沟通,所有信息都没有进行符号处理
5.慎思式体系结构
1.简述
1.agent内部构建了一个完整的世界模型
2.通过规划或者逻辑推理的方法来对agent的行为进行决策
3.实践推理智能体(practicalreasoningagent)
2.理论推理
针对知识/信念的推理(得到新的知识)
3.实践推理
0.针对行动的推理,包含两个主要步骤
1.慎思(deliberation)：决定要做什么,智能体的意图(intention)
2.目标手段推理(mean-endsreasoning)：决定怎么做,如何实现智能体的意图(生成实现意图的计划)
4.特征
1.如果agent接受了一个意图,那么它就会为该意图选择一个实现的方法
2.一旦意图被接受,agent只有在意图被实现、被认为不能实现或者被重新考虑时才会放弃该意图
3.agent不会选择接受与当前自身意图相冲突的意图
4.agent相信能够完成自身的意图
5.BDI模型
Belief-Desire Intention
1.信念(Beliefs)
对世界的认知
2.愿望(Desires)/目标(goal)
希望达到的世界状态的结合
3.意图(Intentions)
承诺实现的并且正在实现的愿望
4.信念修正(beliefrevision)
根据感知输入更新当前信念集
5.目标生成
根据当前信念和意图生成新的目标
6.目标选择函数
选择要去实现的目标
7.计划函数
生成或者选择实现目标的计划
8.意图选择函数
选择下一步执行的意图以及该意图中的动作
6.优点
通过建立自身的环境模型预测其他智能体的行为,能对历史行为进行预测和使用历史行为进行行为决策
7.缺点
通过环境信息来构建智能体内部的环境模型需要额外开销,决策以及逻辑推理过程相比较于反应式体系结构的一个映射过程会消耗更多时间
6.复合式体系结构
1.简述
1.既包含反应部分也包含慎思部分
2.反应部分可以在不进行复杂推理的情况下对世界(环境)改变作出反应
3.而慎思部分则能够使用符号系统对智能体的行为进行推理
4.常使用分层的结构
5.关键问题：如何处理和控制子系统之间的关系和交互
2.水平分层结构
1.每一层都直接与传感器和效应器相连
2.每一层相当于一个子组件,会产生不同的动作选择建议,并最终返回其中一个“适合”的动作
3.优点：简单、直观
4.缺点：选择复杂度高,设计困难
3.垂直分层结构
1.只有一层直接与传感器/效应器相连
2.单次控制(one-passcontrol)：每一层组件对输入信息和结果进行处理,并将处理结果传递给下一层,与感应器和效应器相连的层是不同的两个层
3.双次控制(two-passcontrol)：信息从传感器开始一层层传递到最后一层,然后从最后一层开始处理结果,将输出反向传递到效应器,与感应器和效应器相连的同一层
4.问题：信息处理需要经过每一层,某一层出现问题时,程序无法运行
4.InteRRaP
1.垂直分层,双次控制
2.行为层
管理智能体的反应式行为,能处理则直接返回,不能处理则传输到计划层
3.计划层
为智能体提供生成和选择计划的能力,能处理则返回给行为层,不能处理则传输给交互层
4.交互层
决定智能体交互协作的策略
记忆内容
1.确定性推理
1.自然演绎推理
2.推理规则
0.P规则(前提引入)、T规则(结论引入)、假言推理、拒取式推理
1.假言推理
2.拒取式推理
2.归结演绎推理
0.反证法
4.谓词公式 化子句集
0.例题
1.消去谓词公式中的“→”和“↔”符号
1.
2.把否定符号¬移到紧靠谓词的位置上
1.
3.变量标准化
1.
4.消去存在量词
1.存在量词不出现在全称量词的辖域内:随便用一个个体a,b,c就行
2.存在量词出现在一个或者 多个全称量词的辖域内
变量都是x,都在同一个全称量词下
5.化为前束形
0.前束形=(前缀){母式},(前缀):全称量词串,{母式}:不含量词的谓词公式
1.直接把所有全称量词提到最前面即可
6.化为Skolem标准形
1.
7.略去全称量词
8.消去合取词
1.变为集合的形式,两个子句,子句之间默认合取关系
9.子句变量标准化
1.不同子句使用不同的变元
例题
3.鲁滨逊归结原理
1.归结定义
设C1与C2是子句集中的任意两个子句,如果C1中的文字L1与C2中的文字L2互补,那么从C1和C2中分别消去L1和L2,并将二个子句中余下的部分析取,构成一个新子句C12。
1.
4.归结反演
(1)将已知前提表示为谓词公式F。 (2)将待证明的结论表示为谓词公式Q,并否定得到﹁Q。 (3)把谓词公式集{F,¬Q}化为子句集S。 (4)应用归结原理对子句集S中的子句进行归结,并把每次归结得到的归结式都并入到S中。如此反复进行,若出现了空子句,则停止归结,此时就证明了Q为真
5.归结反演求解问题
2.不确定性推理
1.不确定性的传递算法
2.CF(H)=CF(H,E)×max{0,CF(E)}
当CF(E)<0时,则CF(H)=0 当CF(E)=1时,则CF(H)=CF(H,E)
2.结论不确定性的合成
2.求出E1与E2对H的综合影响所形成的可信度CF12(H)
3.证据理论
1.信任函数
1.
4.似然函数
1.又称不可驳斥函数或上限函数
2.
3.信任函数是为真的可能性,似然函数是非假的可能性
3.证据理论
1.概率分配函数的正交和 (证据的组合)
1.定义
4.搜索求解策略
1.A搜索算法流程图
5.群智能算法
1.粒子群优化
5.四种类型的PSO模型
1.若ψ1>0,ψ2>0,则称该算法为PSO全模型
2.若ψ1>0,ψ2=0,则称该算法为PSO认知模型
3.若ψ1=0,ψ2>0,则称该算法为PSO社会模型
4.若ψ1=0,ψ2>0且g≠i,则称该算法为PSO无私模型
主题
机器学习算法
比较
1.LDA与PCA
1.相同点
1.两者均可以对数据进行降维
2.两者在降维时均使用了矩阵特征分解的思想
3.两者都假设数据符合高斯分布
2.不同点
1.LDA是有监督的降维方法，而PCA是无监督的降维方法
2.LDA降维最多降到类别数k-1的维数，而PCA没有这个限制
3.LDA除了可以用于降维，还可以用于分类
4.LDA选择分类性能最好的投影方向，而PCA选择样本点投影具有最大方差的方向
3.LDA优点
1.LDA算法既可以用来降维，又可以用来分类，但是目前来说，主要还是用于降维
2.在降维过程中可以使用类别的先验知识经验，而像PCA这样的无监督学习则无法使用类别先验知识
3.LDA在样本分类信息依赖均值而不是方差的时候，比PCA之类的算法较优
4.LDA缺点
1.LDA不适合对非高斯分布样本进行降维，PCA也有这个问题
2.LDA降维最多降到类别数k-1的维数，如果我们降维的维度大于k-1，则不能使用LDA
3.LDA在样本分类信息依赖方差而不是均值的时候，降维效果不好
4.LDA可能过度拟合数据
2.LPP与PCA
1.PCA是一个全局的降维算法，主要是求数据的协方差最大散度
2.LPP是一个局部的降维算法，主要是求数据的近邻方差最小变化
3.两者都是无监督降维算法，都是当前人工智能领域应用非常广泛的算法
0.知识点
1.无监督和有监督
1.无监督: 待处理数据对象没有任何先验知识
聚类
2.有监督: 存在有先验知识的训练数据集
分类
1.k_means均值聚类
0.聚类定义
根据相似性原则，将具有较高相似度的数据对象划分至同一类簇， 将具有较低相异度的数据对象划分至不同类簇。
1.特点
1.无监督过程
2.目标函数
uk是聚类中心，xi是样本点
聚类中心为对应类别中各数据点的平均值，同时为了使得算法收敛， 在迭代过程中，应使最终的聚类中心尽可能的不变
3.算法流程
0.K-means是一个反复迭代的过程，算法分为四个步骤
1.选取数据空间中的K个对象作为初始中心，每个对象代表一个聚类中心
2.对于样本中的数据对象，根据它们与这些聚类中心的欧氏距离，按距离最近的准则将 它们分到距离它们最近的聚类中心（最相似）所对应的类
3.更新聚类中心：将每个类别中所有对象所对应的均值作为该类别的聚类中心，计算目标函数的值
4.判断聚类中心和目标函数的值是否发生改变，若不变，则输出结果，若改变，则返回2
4.优缺点
1.优点
1.KMeans算法擅长处理球状分布的数据
2.简单，容易掌握
2.缺点
1.k的取值需要根据经验，没有可借鉴性
2.对异常偏离的数据非常敏感
5.注意
1.有数学证明K-Means一定会收敛
2．PCA 主成分分析(降维)
Principal Component Analysis
0.三种约束情况
1.无约束条件
2.等式约束条件
朗格朗日乘数法
3.不等式约束条件
KKT
1.工作原理
1.第一个新坐标轴选择是原始数据中方差最大的方向
2.第二个新坐标轴选取是与第一个坐标轴正交的平面中使得方差最大的
3.第三个轴是与第1,2个轴正交的平面中方差最大的。
4.只保留包含绝大部分方差的维度特征，而忽略包含方差几乎为0的特征维度， 实现对数据特征的降维处理。
2.最大方差理论
1.在信号处理中认为信号具有较大的方差，噪声有较小的方差， 信噪比就是信号与噪声的方差比，越大越好
2.最好的k维特征是将n维样本点转换为k维后，每一维上的样本方差都很大
3.一些概念
1.样本均值
2.样本方差
3.样本X和样本Y的协方差
4.数据集
5.散度矩阵
注
散度矩阵就是协方差矩阵乘以（总数据量-1）,它们的特征值和特征向量是一样的
4.推理过程
1.求解一个投影矩阵,使得:
2.PCA目标函数
3.构造拉格朗日函数
4.结论
1.λ是特征向量w对应的特征值，一个矩阵的一组特征向量是一组正交向量
2.对特征值从大到小排序，选择其中最大的k个
3.将其对应的k个特征向量分别作为行（列）向量组成特征向量矩阵
5.算法流程
1.将原始数据按列组成n行m列矩阵X
2.将X的每一行（代表一个样本）进行零均值化，即减去这一行的均值
3.求出协方差矩阵
4.求出协方差矩阵的特征值及对应的特征向量
5.将特征向量按对应特征值大小从上到下按行排列成矩阵，取前k行组成矩阵W
6.将数据转换到个特征向量构建的新空间中
2.1 LDA 线性判别式分析
Linear DiscriminantAnalysis
1.思想
将高维的模式样本投影到最佳鉴别矢量空间，以达到抽取分类信息和压缩特征空间维数的效果，投影后保证模式样本在新的子空间有最大的类间距离和最小的类内距离，即模式在该空间中有最佳的可分离性
2.关键步骤
选择合适的投影方向，即建立合适的线性判别函数
3.特点
1.监督学习的降维技术
2.它的数据集的每个样本是有类别输出的
3.投影后类内方差最小，类间方差最大
4.实现
1.欲使同类样例的投影点尽可能接近，可以让同类样本点的协方差矩阵尽可能小
2.而欲使异类样例的投影点尽可能远离，可以让类中心之间的距离尽可能大
3.协方差不仅是反映了变量之间的相关性,同样反映了多维样本分布的离散程度 (一维样本使用方差),协方差越大表示数据的分布越分散
5.类间散度矩阵Sb
1.为了保证类间的样本投影后尽可能远离，我们应该选择特征值最大的特征向量代表的方向做投影
2.不同类样本投影之后方差尽可能地大，尽可能地远离
6.类内散度矩阵Sw
1.为了保证类内的样本投影后尽可能接近，我们应该选择特征值最小的特征向量代表的方向做投影
2.同类样本投影之后方差尽可能地小，尽可能地接近
7.目标函数
8.三类矩阵
1.总散布矩阵
2.类内散度矩阵
3.类间散度矩阵
9.算法步骤
1.计算类内散度矩阵Sw
2.计算类间散度矩阵Sb
3.计算矩阵
4.计算矩阵 的最大d个特征值对应的特征向量（w1,w2,…,wd），得到投影矩阵
5.对数据集中每个样本进行投影
2.2 LPP 局部保持投影
Locality preserving projections
0.特点
1.使得目标函数最小的时候就是降维效果最好的时候
1.目的
在降低空间维度的同时，能较好的保持内部固定的局部结构， 并且它对异化值（通常理解为错误的点，或者为污点）不敏感
2.损失函数
1.yi表示的是降维后的任意数据点i
2.yj表示的是降维后的任意数据点不包含i
3.平方表示的是任意两个点的欧氏距离也就是任意两个数据点之间的远近关系
4.Wij表示的是原始空间中ij之间的距离权重系数组成的矩阵
3.Wij的构造过程
1.如果数据点i和j是k近邻关系, 不论数据点i是j的近邻，还是数据点j是i的近邻
越近则Wij越大
2.不是k近邻的形式，那么Wij就等于0
4.公式推导
1.Dii=wij对第i行的求和,Djj是Wij对第j列的求和
2.构造拉普拉斯矩阵L=D-W
5.目标函数
转化为
6.求解
对特征值进行从小到大排序，选取前d小的特征值的特征向量构成的矩阵A,最后可得
2.3 LLE 局部线性嵌入
Locally Linear Embedding
1.特点
3.NMF 非负矩阵分解
Non-negative Matrix Factorization
1.思想
对于任意给定的一个非负矩阵V，NMF算法能够寻找到一个非负矩阵W和一个非负矩阵H, 使得满足将一个非负的矩阵分解为左右两个非负矩阵的乘积
2.损失函数
3.算法步骤
1.随机生成矩阵W和H
2.按照第二个公式求解出H
3.按照第一个公式求解出W
4.重复（2）、（3），直到损失函数不变或者变化很小
百度简述
0.实例
1.阿尔法狗算法
1.穷举
把所有可能的局面全部算出来,围棋的局面可能性太多了，计算所有的局面显得不合适，而且难度极高
2.评估函数
1.计算机能自动判断局面的优劣
2.用一个函数来计算每一个局面的得分，把一个局面可能的下一步全部算出来，取计算得分最高的那一步来走
3.机器学习
1.阿尔法狗所使用的评估函数只是一个框架，并没有具体的参数值
2.让阿尔法狗观察人类的下棋棋谱，形成自己的参数
3.通过观摩人类的棋谱，生成了一个评估函数——在算法中被称为策略网络
4.google开发了两个阿尔法狗，让他们互相进行对弈，并将对弈的结果也保存起来，组合到已有的评估函数中——这在算法中被称为学习网络
4.蒙特卡洛搜索树算法
确定下一步落子的方向,在预估得分差不多的位置，随机的落子
1.定义
1.人工智能的研究往往涉及对人的智能本身的研究。其它关于动物或其它人造系统的智能也普遍被认为是人工智能相关的研究课题
2.“人工智能就是研究如何使计算机去做过去只有人才能做的智能工作。”
3.人工智能是研究人类智能活动的规律，构造具有一定智能的人工系统，研究如何让计算机去完成以往需要人的智力才能胜任的工作
4.研究如何应用计算机的软硬件来模拟人类某些智能行为的基本理论,方法和技术
5.人工智能与 思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次
2.价值
1.连续性学习
1.“机器学习”的数学基础是“统计学”、“信息论”和“控制论”
2.这类“机器学习”对“经验”的依赖性很强。计算机需要不断从解决一类问题的经验中获取知识，学习策略
2.跳跃性学习
1.人类除了会从经验中学习之外，还会创造，即“跳跃型学习”(灵感/顿悟)
2.一直以来，计算机最难学会的就是“顿悟”
3.计算机在学习和“实践”方面难以学会“不依赖于量变的质变”，很难从一种“质”直接到另一种“质”，或者从一个“概念”直接到另一个“概念”
3.技术研究
1.研究方法
0.如今没有统一的原理或 范式指导人工智能研究
1.大脑模拟
1.探索 神经病学,信息理论及 控制论之间的联系
2.还造出一些使用电子网络构造的初步智能
3.直到1960, 大部分人已经放弃这个方法，尽管在80年代再次提出这些原理
2.符号处理
1.数字计算机研制成功，研究者开始探索人类智能是否能简化成符号处理
2.称这些方法为GOFAI(出色的老式人工智能),符号方法在小型证明程序上模拟高级思考有很大的成就
3.60~70年代的研究者确信符号方法最终可以成功创造 强人工智能的机器，同时这也是他们的目标
4.认知模拟经济学家 赫伯特·西蒙和 艾伦·纽厄尔研究人类问题解决能力和尝试将其形式化,他们的研究团队使用 心理学实验的结果开发模拟人类解决问题方法的程序
5.基于知识大约在1970年出现大容量内存计算机，研究者分别以三个方法开始把 知识构造成应用软件。这场“知识革命”促成 专家系统的开发与计划,这是第一个成功的人工智能软件形式。“知识革命”同时让人们意识到许多简单的人工智能软件可能需要大量的知识
3.子符号法
1. 80年代符号人工智能停滞不前，很多人认为符号系统永远不可能模仿人类所有的认知过程，特别是感知,很多研究者开始关注子符号方法解决特定的人工智能问题
2.否定符号人工智能而专注于机器人移动和求生等基本的工程问题。他们的工作再次关注早期控制论研究者的观点，同时提出了在人工智能中使用控制理论
3.这与认知科学领域中的表征感知论点是一致的:更高的智能需要个体的表征(如移动，感知和形象)
4.计算智能80年代再次提出 神经网络和 联结主义. 这和其他的子符号方法，如模糊控制和进化计算，都属于计算智能学科研究范畴
4.统计学法
1.90年代，人工智能研究发展出复杂的数学工具来解决特定的分支问题
2.这些工具是真正的科学方法，即这些方法的结果是可测量的和可验证的，同时也是人工智能成功的原因,这些进步不亚于“革命”和“NEATS的成功”
3.有人批评这些技术太专注于特定的问题，而没有考虑长远的强人工智能目标
5.集成方法
1.智能AGENT范式是一个会感知环境并作出行动以达致目标的系统
2.最简单的智能AGENT是那些可以解决特定问题的程序。更复杂的AGENT包括人类和人类组织
3.这些范式可以让研究者研究单独的问题和找出有用且可验证的方案，而不需考虑单一的方法
4.范式同时也给研究者提供一个与其他领域沟通的共同语言--如 决策论和经济学
5.一个系统中包含符号和子符号部分的系统称为 混合智能系统 ,而对这种系统的研究则是人工智能系统集成
6.分级控制系统则给反应级别的子符号AI 和最高级别的传统符号AI提供桥梁，同时放宽了规划和世界建模的时间
2.智能模拟
1.机器视、听、触、感觉及思维方式的模拟
2.指纹识别，人脸识别，视网膜识别，虹膜识别，掌纹识别，专家系统，智能搜索，定理证明，逻辑推理，博弈，信息感应与辨证处理
3.学科范畴
人工智能是一门边沿学科，属于 自然科学、 社会科学、 技术科学三向交叉学科
4.涉及学科
哲学和认知科学，数学，神经生理学，心理学，计算机科学，信息论，控制论，不定性论，仿生学，社会结构学与 科学发展观
5.研究范畴
1.语言的学习与处理，知识表现，智能搜索，推理，规划，机器学习，知识获取，组合调度问题，感知问题，模式识别，逻辑程序设计，软计算，不精确和不确定的管理，人工生命，神经网络，复杂系统，遗传算法人类思维方式
2.最关键的难题还是机器的自主 创造性思维能力的塑造与提升
6.应用领域
1.机器翻译，智能控制，专家系统，机器人学，语言和图像理解，遗传编程机器人工厂，自动程序设计，航天应用，庞大的信息处理，储存与管理，执行化合生命体无法执行的或复杂或规模庞大的任务
2.机器翻译是人工智能的重要分支和最先应用领域,机译系统的译文质量离终极目标仍相差甚远
3.要提高机译的质量，首先要解决的是语言本身问题而不是程序设计问题；单靠若干程序来做机译系统，肯定是无法提高机译质量的
4.在人类尚未明了大脑是如何进行语言的模糊识别和逻辑判断的情况下，机译要想达到“信、达、雅”的程度是不可能的
7.实现方法
1.传统的编程技术 (工程学方法)
1.定义
使系统呈现智能的效果，而不考虑所用方法是否与人或动物机体所用的方法相同
2.应用
文字识别、电脑下棋
3.实现
需要人工详细规定程序逻辑
4.特点
1.角色数量和活动空间增加，相应的逻辑就会很复杂（按指数式增长），人工编程就非常繁琐，容易出错
2.一旦出错，就必须修改原程序，重新编译、调试，最后为用户提供一个新的版本或提供一个新补丁，非常麻烦
2.模拟法
1.定义
不仅要看效果，还要求实现方法也和人类或生物机体所用的方法相同或相类似
2.应用
1.遗传算法
模拟人类或生物的遗传-进化机制
2.人工神经网络
模拟人类或动物大脑中神经细胞的活动方式
3.实现
为每一角色设计一个智能系统（一个模块）来进行控制
4.特点
1.智能系统（模块）开始什么也不懂，但它能够学习，能渐渐地适应环境，应付各种复杂情况
2.开始也常犯错误，但它能吸取教训，下一次运行时就可能改正，至少不会永远错下去，用不到发布新版本或打补丁
3.要求编程者具有生物学的思考方法，入门难度大一点。但一旦入了门，就可得到广泛应用
4.无须对角色的活动规律做详细规定，应用于复杂问题，通常会比前一种方法更省力
8.思维模拟
0.人工智能就其本质而言，是对人的思维的信息过程的模拟
1.两种方式
1.结构模拟
仿照人脑的结构机制，制造出“类人脑”的 机器
2.功能模拟
暂时撇开人脑的内部结构，而从其功能过程进行模拟
2.现代电子计算机的产生便是对人脑思维功能的模拟，是对人脑思维的信息过程的模拟
3.弱人工智能如今不断地迅猛发展，尤其是2008年经济危机后，美日欧希望借机器人等实现再工业化
4.强人工智能则暂时处于瓶颈，还需要科学家们和人类的努力
4.主要成果
1.人机对弈
2.模式识别
1.2D识别引擎已推出指纹识别，人像识别 ，文字识别，图像识别 ，车牌识别
2.驻波识别引擎已推出 语音识别
3.3D识别引擎已推出指纹识别玉带林中挂（玩游智能版1.25）
3.自动工程
自动驾驶（OSO系统）/印钞工厂（￥流水线）/猎鹰系统（YOD绘图）
4.知识工程
0.以知识本身为处理对象，研究如何运用人工智能和软件技术，设计、构造和维护知识系统
1.专家系统/智能搜索引擎/计算机视觉和 图像处理/机器翻译和自然语言理解/数据挖掘和知识发现