人工智能引论课件 第七章 绪论

第七章绪论7.1概述7.2归纳学习7.3分析学习7.4无监督学习7.5强化学习7.1机器学习概述

机器学习是人工智能的核心研究课题之一，通过解决机器的知识拥有量从而使机器具有智能的根本途径。任何人工智能系统特别是专家系统，在它拥有功能较强的自动化知识获取能力之前，都不会成为名副其实的强有力的智能系统。传统的手工式知识获取方法耗资耗时，已成为建造专家系统和其他知识系统的“瓶颈”问题。

机器学习已成为知识获取技术发展的主要方向。机器学习的应用领域极为广泛，涉及自然语言处理、计算机视觉、医疗诊断、金融预测等多个关键领域。7.1.1机器学习的定义什么是机器学习？从字面上来理解:机器学习是研究如何使用机器来模拟人类学习活动的一门学科。从人工智能的角度：机器学习是一门研究使用计算机获取新知识和技能，并能够识别现有知识的科学。7.1.2机器学习的基本结构机器学习系统:环境:系统外部信息的源泉，涵盖了系统的工作对象及其所处的外界条件。学习单元:处理环境所提供的信息，其作用类似于各种学习算法。知识库:专为存储学习环节所得知识的场所。执行单元:致力于解决系统所面临的现实问题，它运用知识库中的知识来解决各种问题，如问题求解、自然语言理解和定理证明等。7.1.3机器学习的基本策略每个机器学习系统的学习单元都可以包含一种或者多种学习策略，用来解决特定领域的特定问题。不存在一种普适的、可以解决任何问题的学习算法。根据学习方法：演绎学习、归纳学习、分析学习(含类比学习、解释学习)有无指导来分：有监督学习（或有导师学习）、无监督学习（或无导师学习）和强化学习（或增强学习）以上几种分类方法是相互联系和相互渗透的！7.2归纳学习归纳推理：是从特殊到一般的推理，它是一种“从事实建立理论的过程”，从主观上讲是一种主观地不充分置信的推理。归纳学习：是应用归纳推理进行学习的一种方法。根据归纳学习有无教师指导，可把它分为示例学习和观察发现学习。前者属于监督学习，后者属于无监督学习。7.2.1归纳学习的模式和规则1.归纳学习的一般模式给定：①观察陈述（事实）F，用于表达特定对象、状态和过程等的相关知识；②假定的初始归纳断言（可能为空）；③背景知识，用于定义有关观察陈述、候选归纳断言以及任何相关问题领域知识、假设和约束，其中包括能够刻画所求归纳断言的性质的优先准则。求：归纳断言（假设）H，能重言蕴涵或弱蕴涵观察陈述，并满足背景知识。7.2.1归纳学习的模式和规则这里，从H推导到F是演绎推理，因此是保真的；而从F推导出H是归纳推理，因此不是保真的，而是保假的，归纳学习系统的模型如图所示。实验规划过程通过对实例空间的搜索完成实例选择，并将这些选中的活跃实例提交给解释过程。解释过程对实例加以适当转换，把活跃实例变换为规则空间中的特定概念，以引导规则空间的搜索。7.2.1归纳学习的模式和规则2.归纳学习的规则

在归纳推理过程中，需要引用一些归纳规则。这些规则分为选择性概括规则和构造性概括规则两类。令D1和D2，分别为归纳前后的知识描述，则归纳是D1

D2。选择性概括：如果D2中所有描述基本单元（如谓词子句的谓词）都是D1中的，只是对D1中基本单元有所取舍，或改变连接关系。构造性概括：如果D2中有新的描述基本单元（如反映D1各单元间的某种关系的新单元）。这两种概括规则的主要区别在于，构造性概括能够构造新的描述符或属性。7.2.2归纳学习方法1.示例学习

示例学习（LearningfromExamples）：又称实例学习，是一种通过环境中的多个与某一概念相关的示例，经归纳推理得出一般性概念的学习方法。

在这种学习方式中，外部环境（教师）提供一组示例，包括正例和反例，它们都是一种特殊的知识，每个示例表达了仅适用于该例子的知识。

示例学习的目标是从这些特殊知识中归纳出适用于更广泛范围的一般性知识，以覆盖所有的正例并排除所有反例。7.2.2归纳学习方法通过示例学习，可以从病例中归纳产生如下的诊断规则：血沉=正常

(听诊=干鸣音

水泡音)→诊断=肺炎血沉=快→诊断=肺结核7.2.2归纳学习方法2.观察发现学习

观察发现学习（LearningfromObservationandDiscovery）：又称为描述性概括，其目标是确定一个定律或理论的一般性描述，刻画观察集，指定某类对象的性质。观察发现学习可分为概念聚类与机器发现两种。概念聚类：对事例进行聚类，形成概念描述。机器发现：发现规律，产生定律或规则。7.2.3ID3决策树归纳算法

决策树学习是离散函数的一种树形表示，表达能力强，可以表示任意的离散函数，是一种重要的归纳学习方法。决策树中有决策节点和状态节点两种节点，即决策节点和状态节点。昆兰在1979年提出的ID3算法是一种典型的决策树算法，是通用的规则归纳算法。决策节点：由决策节点可引出若干树枝，每个树枝代表一个决策方案，每个方案树枝连接到一个新的节点，它既可以是一个新的决策节点，也可以是一个状态节点；对于分类问题而言，决策节点表示待分类的对象属性，每一个树枝表示它的一个可能取值状态节点：状态节点对应着叶节点，每个状态节点表示一个具体的最终状态；对于分类问题而言，状态节点表示分类结果。7.2.3ID3决策树归纳算法ID3（Examples，Target_attribute，Attributes），其中Examples即训练样例集，Target_attribute是这棵树要预测的目标属性，Attributes是除目标属性外供学习的决策树要测试的属性列表。1）创建树的Root（根）结点。2）如果Examples都为正，那么返回label=+的单结点树Root。3）如果Examples都为反，那么返回label=-的单结点树Root。4）如果Examples为空，那么返回单结点树Root，label=Examples中最普遍的Target_attribute值。5）否则：①A←Attributes中分类Examples能力最好的属性，一般认为具有最高信息增益(informationgain)的属性是最好的属性。②Root的决策属性←A。③对于A的每个可能值vi：a．在Root下加一个新的分支对应测试A=vi。b．令Examples（vi）为Examples中满足A属性值为vi的子集。c．如果Examples（vi）为空：在这个新分支下加一个叶结点，结点的label=Examples中最普遍的Target_attribute值；否则在这个新分支下加一个子树ID3(Examples(vi)，Target_attribute，Attributes-{A})。6）结束。7）返回Root。7.2.3ID3决策树归纳算法思考：如何选择具有最高信息增益即分类能力最好的属性?昆兰建议选取获得信息量最大的属性作为扩展属性，这一启发式规则又称最小熵原理。因为获得信息量最大，即信息增益Gain最大，等价于使其不确定性最小，即使得熵最小，即条件熵H(S|Ai)为最小。因此也可以以条件熵H(S|Ai)为最小作为选择属性的重要标准。H(S|Ai)越小，说明Ai引人的信息越多，系统熵下降得越快。7.3分析学习归纳学习方法需要通过在大量训练样例中寻找经验化的规律来形成一般假设。然而，若训练数据不足时它会失败，无法达到一定的泛化精度。分析学习则使用先验知识扩大训练样例提供的信息，推导一般假设，降低了对数据量的要求。本节将探讨分析学习中的类比学习与基于解释的学习。7.3.1类比推理和类比学习1.类比推理类比推理是从个别事例到个别事例的推理方法。它是根据认识的新情况（目标）和已知情况（源）在某些方面的相似性，推断出其他相关方面的推理形式。其一般模式为：

已知：S1，T1 （源S1和目标T2）（源和目标相似）（源S1和源S2相关）S2 （已知源S2）

7.3.1类比推理和类比学习2.类比学习类比学习的一般原理基于类比推理的学习过程分为两步，首先归纳找出源域和目标域的公共性质，然后演绎地推理出从源域到目标域映射，得出目标域的新性质。不难看出，类比学习过程既有归纳过程，又有演绎过程，所以类比学习是演绎学习和归纳学习的组合，是由一个系统已有某领域中类似的知识，来推测另一个领域里相关知识的过程。7.3.1类比推理和类比学习2.类比学习类比学习的表示假设对象的知识是框架集来表示的，则类比学习可描述为把一个称为源框架的槽值传递给另一个称为目标框架的槽中，传递过程分为两步。1）利用源框架产生若干候选槽，并将这些槽值送到目标框架中去。2）利用目标框架中现有的信息来筛选上一步提取出来的相似性。7.3.1类比推理和类比学习2.类比学习例

考虑比尔与消防车之间的相似关系，关于比尔和消防车的框架为：比尔是一个（ISA）人

性别男

活动级

音量

进取心中等消防车是一个（ISA）车辆

颜色红

活动级快

音量极高

燃料效率中等

梯高异或（长、短）7.3.1类比推理和类比学习2.类比学习基于启发式规则求解，得到比尔的框架为：比尔是一个（ISA）人

性别男

活动级快

音量极高

进取心中等可以看出类比学习过程也依赖于知识表示和推理技术，在类比学习过程中合理地使用这些技术，能够形成一种合理的、有效的学习方法。7.3.2基于解释的学习基于解释的学习力图反映人工智能领域里基于知识的研究和发展趋势，将机器学习从归纳学习方法向分析学习方法的方向发展。

基于解释的学习的一般框架解释学习一般包括下列3个步骤：1）利用基于解释的方法对训练实例进行分析与解释，以说明它是目标概念的实例。2）对实例的结构进行概括性解释,建立该训练实例的一个解释结构以满足所学概念的定义；解释结构的各个叶结点应符合可操作性准则,且使这种解释比最初的例子适用于更大的一类例子。3）从解释结构中识别出训练实例的特性,并从中得到更大一类例子的概括性描述，获取一般控制知识。7.3.2基于解释的学习

基于解释的学习过程基于解释的学习过程可分为如下两个步骤：1）分析阶段：根据领域知识生成一棵证明树，解释为什么该实例是目标概念的一个实例。2）基于解释的概括阶段：通过将实例证明树中的常量用变量进行替换，形成一棵基于解释的抽象树（简称EBG树），得到目标概念的一个充分条件。7.3.2基于解释的学习例

下面以学习概念cup（杯子）为例说明EBG的学习过程。1）目标概念：cup2）高级描述：cup（z）3）领域知识：stable(x)

liftable(x)

drinkfrom(x)

cup(x)has(x,y)

concavity(y)

upward-pointing(y)

drinkfrom(x)bottom(x,y)

flat(y)

stable(x)light-weight(x)

graspable(x)

liftable(x)small(x)

madefrom(plastic)

light-weight(x)has(x,y)

handle(y)

graspable(x)（中文解释：stable稳定的；liftable便于拿起；drinkfrom可用来喝饮料；concavity凹空；light-weight轻质；graspable可握住；upward-pointing向上指示；bottom底；flat平坦的；plastic塑胶。）4）训练例子：Small(obj),madetrom(obj,plastic),has(obj,part1),handle(part2),has(obj,part2),concavity(part2),upward-pointing(part),bottom(obj,b),flat(b)。5）可操作性准则：目标概念必须以系统可识别的物理特征描述。7.3.2基于解释的学习利用以上规则和事实，以cup(obj)为目标作逆向推理，可以构造如图（a）所示的解释结构，其叶结点满足可操作性准则。对解释进行概括，变常量为变量，便得到概括后的解释结构。将此结构中的所有叶结点作合取，就得到目标概念所应满足的一般性的充分条件，以产生式规则形式表示为图（b）（a）解释结构（b）形成规则7.4无监督学习

无监督学习（UnsupervisedLearning）：是指在学习之前没有（不知道）关于输入数据的标准输出，对学习结果的判定由学习模型自身设定的条件决定。无监督学习的学习过程一般是一个自组织的过程，学习模型不需要先验知识。无监督学习可用于解决聚类问题，其典型方法有K均值聚类、主成分分析算法等。7.4.1聚类算法

在聚类算法中，训练样本的标记信息是未知的，将样本集分为若干互不相交的子集，即样本簇。聚类算法的目标：同一簇：样本尽可能彼此相似，即具有较高的类内相似度(Intra-clusterSimilarity)。不同簇：样本尽可能不同，即簇间的相似度低。K-均值算法是聚类方法的一种，期目标是使得聚类簇内的平方误差最小化。7.4.1聚类算法K-均值算法特性：对参数的选择比较敏感，不同的初始位置或者类别数量的选择往往会导致完全不同的结果。

（a）K=2：颜色

（b）K=2：形状

（c）K=2：大小

（a）K=4：颜色、形状

（b）K=4：形状、尺寸

（c）K=4：尺寸、颜色7.4.2主成分分析

主成分分析（PrincipleComponentsAnalysis，PCA）：是一种特征降维的方法，即通过分析找到数据特征的主要成分，使用这些主要成分来代替原始数据。主成分分析要求：降维后的结果要保持原始数据的原有结构。7.4.2主成分分析主成分分析的目的是求取一个d×l的映射矩阵W。给定一个样本集X，可将X从d维空间如下映射到l维空间：(xi)1×d(W)d×l。将所有降维后的数据用Y表示，有Y=XW，其中Y∈Rd×l是降维后的结果，X∈Rn×d是原始数据，W∈Rd×l是映射矩阵。

降维后n个l维样本数据Y的方差为:式中，tr表示矩阵的迹（Trace），即一个方阵主对角线（从左上方到右下方的对角线）上各个元素的总和。降维前n个d维样本数据X的协方差矩阵记为：7.4.2主成分分析主成分析的优化求解目标函数为：该优化求解目标需要满足如下约束条件：这是带约束的最优化问题求解，可通过拉格朗日乘子法转化为无约束的最优化问题，即：式中，λi（1≤i≤l）为拉格朗日乘子，wi为矩阵W第i列。对上述拉格朗日函数中的变量wi求偏导并令导数为零，有Σwi=λiwi上式表明：每一个wi，均是n个d维样本数据X的协方差矩阵Σ的特征向量，λi是这个特征向量所对应的特征值。为了使方差最大，可以求出协方差矩阵Σ的特征向量和特征根，然后取前l个最大特征根所对应的特征向量组成映射矩阵W即可。7.4.2主成分分析主成分分析算法伪代码：注意:每个特征向量wi与原始数据xi的维数是一样的，均为d。7.5强化学习

强化学习是智能体（Agent）在不断与其所处环境交互中进行学习的一种方法。学习信号以奖励形式出现，根据在终止状态所获得的奖惩来改进行动策略，智能体在与环境交互中取得最大化收益。

在这种方法中，智能体通过“尝试与试错”和“探索与利用”等机制在所处状态采取行动，不断与环境交互，直至进入终止状态。这种学习方式既不是从已有数据出发，也不是依赖于已有知识的学习方式。7.5.1强化学习的基本概念学习过程中要使用的若干概念。智能体（Agent）：智能体是强化学习算法的主体，它能够根据经验做出主观判断并执行动作，是整个智能系统的核心。环境（Environment）：智能体以外的一切统称为环境，环境在与智能体的交互中，能被智能体所采取的动作影响，同时环境也能向智能体反馈状态和奖励。状态（State）：状态可以理解为智能体对环境的一种理解和编码，通常包含了对智能体所采取决策产生影响的信息。动作（Action）：动作是智能体对环境产生影响的方式。策略（Policy）：策略是智能体在所处状态下去执行某个动作的依据。奖励（Reward）：奖励是智能体序贯式采取一系列动作后从环境获得的收益。7.5.2被动强化学习被动强化学习（PassiveReinforcementLearning）：具有少量动作和状态，且环境完全可观测，其中智能体已经有了能决定其动作的固定策略π(s)，智能体将学习效用函数Uπ(s)——从状态s出发，采用策略所得到的期望总折扣奖励。被动强化学习任务中，智能体并不知道转移模型P(s'|a,s)即在状态s下采取动作a后到达状态s'的概率；同时它也不知道奖励函数R(s,a,s')，即每次转移后的奖励。7.5.2被动强化学习（a）状态转移最优策略

（b）状态效用被动强化学习中，智能体使用策略π进行一系列尝试，在每次试验中从起点状态（1，1）出发，经历一系列状态转移，直到达到终止状态（4，2）或（4，3）。它既能感知到当前的状态，也能感知到达到该状态的转移所获得的奖励，下面展示三个典型的尝试结果：7.5.2被动强化学习在以上尝试的每次转移中都标注了到达下一个状态所采取的动作以及获得的奖励。目标是利用有关奖励的信息来学习每个非终止状态的效用期望Uπ(s)。其对应公式描述如下：其中R(St，π(St)，St+1)为在状态St下执行策略π(St)到达St+1所获得的奖励，折扣因子γ=1。7.5.2被动强化学习被动强化学习主要求解方法有两种：直接效用估计（DirectUtilityEstimation）：一个状态的效用定义为从该状态出发的总奖励，并且每次试验将为每个访问过的状态提供一个它的数值样本。这意味着可将强化学习简化为一个标准的监督学习问题，状态的效用取决于后继状态的奖励和期望效用，其应当满足固定策略的贝尔曼方程：自适应动态规划（AdaptiveDynamicProgramming，ADP）：智能体学习状态之间的转移模型并使用动态规划解决相应的马尔可夫决策过程，从而利用了状态效用之间的约束。这意味着可以将学习到的转移模型P(s'|s,π(s))和观测到的奖励R(s,π(s),s')代入上式来求解各个状态的效用。

7.5.3主动强化学习主动强化学习（ActiveReinforcementLearning）：可以自主决定采取什么动作，其关键问题是探索。

从自适应动态规划（ADP）智能体开始入手，首先，智能体需要学习一个完整的转移模型，其中包含所有动作可能导致的结果及概率不仅仅是固定策略下的模型。接下来，我们需要考虑这样一个事实：智能体有一系列动作可供选择。它需要学习的效用是由最优策略所定义的效用，仍满足如下贝尔曼方程：可以使用马尔可夫决策过程中状态估计的价值迭代或策略迭代算法求解这些方程，以得到效用函数U。7.5.3主动强化学习1.探索在被动强化学习中，试验的智能体每一步中都采用所学到的模型的固定最优策略建议的动作，该智能体称作贪心智能体(GreedyAgent)。主动强化学习可能需要花费比被动强化学习更长的探索时间，找到最优策略的方案，并且对于下一步行动的选取都不是贪心的，而是无限探索极限下的贪心（GreedyintheLimitofInfiniteExploration，GLIE）。GLIE方案必须在每个状态下对每个动作尝试任意多次，以避免错过最优动作。7.5.3主动强化学习最简单的基于GLIE的方案是让智能体在时刻t以1/t的概率随机选择一个动作，否则就遵循贪心策略。一个更好的方法是对智能体不经常尝试的动作赋予较高的权重，同时倾向于避免采取智能体认为效用较低的动作。用U+(s)来表示对状态s的目标效用（即期望的预期奖励）的乐观