人工智能课程知识总结

Agent：通过传感器感知所处环境并通过执行器对该环境产生作用的计算机程序及其控制的硬件。感知信息：表示任意给定时刻Agent的感知输入/感知序列：该Agent所收到的所有输入数据的完整历史Agent函数：把任意给定感知序列映射到Agent行动的描述/Agent程序：抽象的Agent函数的一个具体实现，该程序在Agent自身结构上运行。性能度量：通常由理性设计者给出，根据实际在所处的环境中希望得到的结果来设计度量，而不是根据Agent应该表现的行为。理性的判断取决于：性能度量、Agent对环境的先验知识、Agent可执行的行动、Agent到那时为止的感知序列。理性Agent应该选择期望能使其性能度量最大化的行动。任务环境的属性:完全可观察的vs部分可观察的；确定性的vs随机的；片段式的vs延续式的；静态的vs动态的；离散的vs连续的；单Agentvs多Agent。有4种类型的Agent程序：简单反射型Agent、基于模型的反射型Agent、基于目标的Agent、基于效用的Agent。A算法八数码问题令：g(n)=d(n)——节点深度h(n)=w(n)——不在位的数码个数（启发函数）则f(n)=d(n)+w(n)如：初始节点s的f值计算结果为f(n)=d(n)+w(n)=0+4=4有4个数码不在位对于f(n)=g(n)+h(n)，如果单独考虑g(n)或h(n)，既：①f(n)=g(n)只考虑搜索过的路径已经耗费的费用②f(n)=h(n)只考虑未来的发展趋势那么可以得到两种特殊的算法：爬山算法和分支界限算法。动态规划算法：仅保留queue中公共节点路径中耗散值最小的路径，余者删去，按g值升序排序。①动态规划与分支界限的差别在于去掉公共路径中的冗余部分，提高效率。②如果问题空间是树结构，动态规划与分支界限相同。A*算法迷宫问题给定迷宫图如下，找出从入口到出口得最短路径。规则集：右移、下移、左移、上移A*算法f函数定义f(n)＝g(n)＋h(n)g(n)＝d(n)从初始节点s到当前节点n的搜索深度h(n)＝|Xg－Xn|＋|Yg－Yn|当前节点n与目标节点间的坐标距离与或图搜索①从节点n开始，正确选择一个外向连接符。②从该连接符指向的每个后继节点出发，继续选择一个外向连接符。③依次类推，直到由此产生的每个后继节点都是N中的一个元素为止，N为终节点集合。其耗散值：K(n,N)＝Cn+K(n1,N)+K(n2,N)+…+K(ni,N)极大极小值搜索策略在极大极小值算法基础上增加了剪枝功能,并采用深度优先策略进行搜索。剪枝条件：极小≤极大，剪枝；极大≥极小，剪枝。注意：只有一个结点的值“固定”以后，其值才能向其父结点传递，如下图所示：谓词公式标准化：将一个给定的公式化成一个合取前束范式，最终得到一个子句集。1消去蕴含符号。2缩小否定符号的辖域：利用DeMorgan定律。3变量标准化：利用变量代换使不同的量词所约束的变元各不相同。4消去存在量词：（斯托林标准化）。5化成前束形式。6将母式化成合取范式：（每个合取项是一个析取式）。7消去全称量词：由于公式中的所有变元均受全程量词约束，所以可直接将全称量词消去。8消去合取符号，得到一个子句集。9更换变元名称：（变元分离标准化）。归结的基本过程：1公式标准化，得到子句集2构造初始子句集S=S0∪{~W}；3检验S中是否存在空子句（即永假式：P∧～P），如有空子句，则结束；4否则，用归结方法扩大子句集S，GOTO2。子句合一：C1=P(x,f(A))∨P(x,f(y))∨Q(y)C2=~P(z,f(A))∨~Q(z)首先找出能够合一的二个子集L11=P(x,f(A)),L21=~P(z,f(A))利用unify算法对L11和~L21进行合一，求出合一置换S={z/x}L11和~L21的合一结果是：P(z,f(A))采用归结方法，在C1中去掉L11，在C2中去掉L21，余下部分用S={z/x}进行置换，得到归结式：C=P(z,f(y))∨Q(y)∨~Q(z)归结式的不唯一性：原因是C1和C2的子集选择可以不同。Find-S算法:1.将h初始化为H中最特殊假设2.对每个正例x:对h的每个属性约束ai,如果x满足ai那么不做任何处理,否则将h中ai替换为x满足的下一个更一般约束3.输出假设h。例如：x1=sunny,warm,normal,strong,warm,same,+x2=sunny,warm,high,strong,warm,same,+x3=rainy,cold,high,strong,warm,change,-x4=sunny,warm,high,strong,cool,change,+执行算法后h0=h1=sunny,warm,normal,strong,warm,sameh2=sunny,warm,?,strong,warm,sameh3=sunny,warm,?,strong,warm,sameh4=sunny,warm,?,strong,?,?候选消除算法：1.初始化G和S；2.如果d是一个正例，从G中移去所有与d不一致的假设，对S中每个与d不一致的假设s从S中移去s，把s的所有的极小泛化式h加入到S中，其中h满足：h与d一致，而且G的某个成员比h更一般从S中移去所有这样的假设：它比S中另一个假设更一般；3.如果d是一个反例，从S中移去所有与d不一致的假设，对G中每个与d不一致的假设g从G中移去g把g的所有的极小特殊化式h加入到G中，其中h满足：h与d一致，而且S的某个成员比h更特殊从G中移去所有这样的假设：它比G中另一个假设更特殊。熵值计算举例：“PlayTennis”中S是一个关于某布尔概念的14个样例的集合，包括9个正例和5个反例[9+，5-]。那么S相对于这个布尔分类的熵为：940.0)14/5(log14/5)14/9(log)14/9(])5,9([22Entropy熵值分析：如果S的所有成员属于同一类，那么S的熵为0如果S中正反样例的数量相等时（或者：S中各类样例等比例时），熵值为1如果S集合中正反例的数量不等时，熵介于0和1之间。计算属性Wind的信息增益Values(Wind)=Weak,StrongS=[9+,5-]Sweak=[6+,2-]Sstrong=[3+,3-]信息增益：)()(),(},{vstrongweakvvSEntropySSSEntropyWindSGain=Entropy(S)-(8/14)Entropy(Sweak)-(6/14)Entropy(Sstrong)=0.940-(8/14)0.811-(6/14)1.00=0.048