Loading... # 人工智能导论 ## 绪论 ### 人工智能的基本概念 #### 人工智能 - 用人工的方法在机器(计算机)上实现的智能 #### 图灵测试 - 机器通过测试,就具有智能。 ### 人工智能的发展简史 #### 孕育阶段 #### 形成阶段 #### 发展阶段 - 强弱人工智能 - 弱人工智能 - 主要关注执行结果,是否模拟人类并不重要 - 强人工智能 - 模拟人类、能够执行“通用任务”的人工智能 ### 人工智能的主要学派 #### 符号主义 - 物理符号系统假设和有限合理性原理 #### 连接主义 - 神经网络和神经网络间的连接机制和学习算法 #### 行为主义 - 控制论及感知-动作型控制系统 ### 人工智能的主要研究领域与典型应用 ## 搜索 ### 搜索的基本概念 #### 搜索方向 - 正向搜索 - 逆向搜索 - 双向搜索 #### 搜索策略 - 盲目搜索 - 在不具有对特定问题的任何有关信息的条件下,按固定的步骤(依次或随机调用操作算子)进行的搜索。 - 启发式搜索 - 考虑特定问题领域可应用的知识,动态地确定调用操作算子的步骤,优先选择较适合的操作算子,尽量减少不必要的搜索,以求尽快地到达结束状态。 ### 状态空间图和搜索树 #### 状态空间表示法 - 状态 - 表示系统状态、事实等叙述型知识的一组变量或数组: $Q=[q_1,q_2,\dots,q_n]$ - 操作 - 表示引起状态变化的过程型知识的一组关系或函数: $F=\{f_1,f_2,\dots,f_m\}$ - 状态空间 - 利用状态变量和操作符号,表示系统或问题的有关知识的符号体系,状态空间是一个四元组: $(S,G,S_0,G)$ - 求解路径 - 从$S_0$结点到$G$结点的路径。 - 状态空间解 - 一个有限的操作算子序列。 #### 状态空间的图描述 - 状态空间图 - 用有向图描述状态空间,称为状态空间图 . - 结点表示状态、边表示操作算子 - 初始状态为根结点 - 图中某一路径↔一种状态转换为另一种状态的操作算子序列 ### 盲目搜索策略 #### 回溯策略 #### 贪婪策略 #### 宽度优先搜索 - 定义 - 以接近起始节点的程度(深度)为依据,进行逐层扩展的节点搜索方法。 - 保存状态空间搜索轨迹用到的表 - Open:已经生成出来但其子状态未被搜索的状态(类似NPS表) 。 - Closed:记录了已被生成扩展过的状态(相当于 PS表和NSS表的合并) 。 #### 深度优先搜索 - 定义 - 首先扩展最新产生的节点,深度相等的节点按生成次序的盲目搜索。 - 特点 - 扩展最深的节点使得搜索沿着状态空间某条单一的路径从起始节点向下进行; - 仅当搜索到达一个没有后裔的状态时,才考虑另一条替代的路径。 ### 启发式搜索策略 #### 最佳优先搜索 - 最佳优先搜索算法(Best-First-Search) 是用估价函数f(n) 对将要被遍历到的节点进行估价,然后选择最有希望的节点进行遍历。 #### 启发式搜索策略 - 启发式信息 - 用来简化搜索过程的有关具体问题领域的特性信息叫做启发信息 - 启发式搜索:利用启发信息的搜索方法 - 估价函数(evaluation function) :估算节点“希望” 程度的度量 - 估价函数值 f(n) :从初始节点经过n节点到达目标节点的路径的最小代价估计值, 其一般形式是 $f(n)=g(n)+h(n)$ - A搜索 - 寻找并设计启发函数h(n), 然后以f(n)的大小来排列OPEN表中待扩展状态的次序, 每次选择 f(n) 值最小者进行扩展。 - A*搜索 - 定义h*(n)为状态n到目的状态的最优路径代价, 当A搜索算法的启发函数满足可采纳性(admissibility),即h(n)小于等于h*(n),表示如下: $$ h(n) ≤ h*(n), 对所有结点n $$ 时,被称为A*搜索算法。 #### 统一代价搜索 - 佳优先搜索的特例 - 估价函数: f(n) = g(n) - 是对宽度优先的改进,可以解决有权重图搜索问题,宽度优先搜索只能处理无权重图搜索问题 - Dijkstra算法 #### 贪婪最佳优先搜索 - 估价函数: f(n) =h(n) ## 机器学习 ### 机器学习的基本概念 #### 机器学习 - 通过算法使得机器能从大量数据中学习规律从而对新的样本做决策。 #### 规律: - 决策(预测)函数 #### 常见的机器学习问题 - 回归 - 分类 - 聚类 #### 三要素 - 模型 - 学习准则 - 损失函数 - 风险最小化准则 - 过拟合和欠拟合 - 优化算法 - 参数: 模型 𝑓(𝒙; 𝜃) 中的参数 𝜃 - 超参数:用来定义模型结构或优化策略的参数 ### 机器学习的分类及概述 #### 分类 - 按标签信息来源分类: - 监督学习 - 无监督学习 - 强化学习 - 按学习方法分类(温斯顿, 1977 ) - 机械式学习、指导式学习、示例学习、类比学习、解释学习等。 - 符号学习、非符号学习(连接学习) - 按推理方式分类: - 基于演绎的学习(解释学习)。 - 基于归纳的学习 (示例学习、发现学习等 )。 - 按综合属性分类: - 归纳学习、分析学习、连接学习、遗传式学习等 #### 概述 ##### 监督学习 - 已知输入和输出的情况下训练出一个模型,将输入映射到输出 - 通过学习标记的训练样本来构建预测模型,并依此模型推测新的实例 - 输出可以是一个连续的值(称为回归分析),或是预测一个分类标签(称作分类) ##### 无监督学习 - 不给定事先标记过的训练示例,自动对输入的数据进行分析 - 不需要数据标注,对大数据分析很重要,但在实际应用中性能受限 - 包括聚类、降维等 ##### 强化学习 - 强化学习(Reinforcement learning) 中外部环境对系统输出结果只给出评价信息(奖励或惩罚),而不是正确答案,学习系统通过那些受惩动作改善自身的性能。 - 强化学习通过接收环境对动作的奖励(反馈)获得学习信息并更新模型参数。 ##### 早期机器学习 - 械式学习 - 通过直接记忆或者存储外部环境所提供的信息达到学习的目的, 并在以后通过对知识库的检索得到相应的知识直接用来求解问题。 ##### 早期机器学习 - 指导式学习 - 由外部环境向系统提供一般性的指示或建议,系统把它们具体地转化为细节知识并送入知识库中。 在学习过程中要反复对形成的知识进行评价, 使其不断完善。 可用于专家系统的知识获取。 ##### 现代机器学习 - 深度学习 - 把原始数据通过一些简单但非线性的(神经元)模型,转变为更高层次、更加抽象的表达 - 可以学习非常复杂的函数 - 实质是通过构建具有很多隐层的模型和海量的训练数据来学习更有用的特征,从而提升分类或预测的准确性 ##### 现代机器学习 - 迁移学习 - 将已经学习过的知识迁移应用到新的问题中 ### 机器学习的关键思想 #### 归纳偏置 - 很多学习算法经常会对学习的问题做一些假设,这些假设就称为归纳偏置 - 归纳偏置在贝叶斯学习中也经常称为先验 (Prior)。 #### 常用定理 ##### 奥卡姆剃刀原理 - 如无必要,勿增实体 - 若有多个假设与观察一致,则选最简单的那个 ##### 没有免费午餐定理 - 对于基于迭代的最优化算法,不存在某种算法对所有问题(有限的搜索空间内)都有效。如果一个算法对某些问题有效,那么它一定在另外一些问题上比纯随机搜索算法更差 ##### 丑小鸭定理 - 丑小鸭与白天鹅之间的区别和两只白天鹅之间的区别一样大 ### 机器学习与人工智能的关系 - 机器学习是人工智能的基础 - 基于机器学习的人工智能的优势和局限性 ## 符号学派 ### 符号学派简介 #### 符号主义 - 物理符号系统假设 - 物理符号系统是普遍的智能行为的充分必要条件。 - 有限理性原理 - 人类决策**不可能简单地归结为某种目标函数优化**的完美数学形式的原理。原因在于人类目标的模糊性,其知识和信息的不完备性,其推理判断能力的局限性等。 #### 符号学派 - 认知即计算 - 知识是信息的一种形式,是构成智能的基础 - 知识表示、 知识推理、 知识运用是人工智能的核心 ### 知识表示与推理基本概念 #### 知识的概念 - 在长期的生活及社会实践中、在科学研究及实验中积累起来的对客观世界的认识与经验。 - 把有关信息关联在一起所形成的信息结构。 - 反映了客观世界中事物之间的关系。不同事物或者相同事物间的不同关系形成了不同的知识。 #### 知识的特性 - 相对正确性 - 任何知识都是在一定的条件及环境下产生的,在这种条件及环境下才是正确的。 - 不确定性 - 由于现实世界的复杂性,信息可能精确/模糊,关联可能确定/不确定,知识于是存在“真”的程度的问题。 - 可表示性与可利用性 - 知识的可表示性 - 知识可以用适当形式表示出来,如用语言、文字、图形、向量等。 - 知识的可利用性 - 知识可以被利用。 #### 知识表示 #### 知识推理 - 知识表示(计算机掌握知识) →知识推理(具有思维能力) - 推理是求解问题的一种重要方法 - 推理方法是人工智能的一个重要研究课题 #### 推理的定义 #### 推理方式及其分类 - 演绎推理、归纳推理、默认推理 - 确定性推理、不确定性推理 - 单调推理、非单调推理 - 启发式推理、非启发式推理 #### 推理的方向 - 正向推理: (事实驱动推理) : 已知事实 → 结论 - 从初始已知事实出发,在知识库中匹配知识进行推理,将推理出的新事实加入数据库作为下一步推理的已知事实,直到求解为止 - 简单,易实现,目的性不强,效率低 - 逆向推理 :(目标驱动推理):以某个假设目标作为出发点 - 选定一个假设目标->寻找支持该假设的证据->找到则假设成立/找不到则重新假设 - 目的性强,但起始目标的选择有盲目性 - 混合推理(结合正向与逆向推理) - 双向推理(同时进行正向与逆向推理) #### 冲突消解策略 ### 谓词逻辑知识表示与推理 #### 一阶谓词逻辑表示法 #### 自然演绎推理 #### 归结演绎推理 ### 产生式知识表示与推理 - 产生式 - 产生式和蕴含式的区别 - 产生式系统 - 一组产生式放在一起,互相配合;一个产生式的结论可以供另一个产生式作为事实使用,以求得问题的解。 ### 不确定性知识表示与推理 #### 不确定性知识表示与推理的概念 #### 可信度方法 - 可信度(Certainty Factor) : 根据经验对一个事物或现象为真的相信程度 - 基本方法: C-F模型 #### 证据理论方法 - 证据理论基本概念 - 信任区间:对假设A的信任区间$[Bel(A),Pl(A)]$ - Dempster 证据合成规则 - $m_1 \oplus m_2(A)=\frac 1 K \sum_{B\cap C=A}m_1(B)\cdot m_2(C)$ - $K=\sum_{B\cap C\not=\empty}m_a(B)\cdot m_2(C)=1-\sum_{B\cap C = \empty}m_1(B)\cdot m_2(C)$ #### 模糊推理方法 - 模糊集合的定义 - 模糊集合中,论域X中的每一个元素x赋予一个介于0和1之间的实数,描述其属于该模糊集合的程度, 该实数称μ(x) 为元素x属于此模糊集合的 **隶属度**或**隶属函数**。 - 与经典集合表示不同, 模糊集合不仅要列出属于集合的元素,还要注明元素属于集合的隶属度。 模糊集合A的数学描述为: $$ A={(x,\mu_A(x)),x\in X} $$ 其中, $μ_A(x)$为元素属于模糊集A的隶属度, X是元素x的论域。 - 模糊集合的表示方法 - Zadeh表示法:论域离散且元素数有限 - Zadeh表示法:论域连续或元素数无限 - 序偶(ordered pair)表示法 - 向量表示法 - 模糊集合的运算 - 模糊关系 - 模糊关系描述两个模糊集合中的元素之间的关联程度 - A、 B 为两个模糊集合, 模糊关系用叉积(cartesian product)表示: $$ R:A\times B \to [0,1] $$ 叉积常用最小算子运算: $$ \mu_{A \times B}(a,b)=\min \{\mu_A(a),\mu_B(b)\} $$ 若A、 B 为离散模糊集, 其隶属函数分别为: $$ \mu_A=[\mu_A(a_1),\mu_A(a_2),\cdots,\mu_A(a_n)], \mu_B=[\mu_B(b_1),\mu_B(b_2),\cdots,\mu_B(b_n)] $$ 则其叉积运算: $$ \mu_{A\times B}(a,b)=\mu_A^T\circ \mu_ B $$ - 当论域为有限时,可以用**模糊矩阵**来表示模糊关系 - 模糊关系的合成 - 模糊推理 - 模糊决策 ### 知识图谱表示与推理 #### 知识图谱的表示 - 数据 - 对客观世界的符号化记录 - 信息 - 被赋予意义的数据 - 知识 - 信息之间有意义的关联 - 数据与信息中的精华 - 知识图谱: - 承担人类知识的传承。 #### 知识图谱的推理 #### 知识图谱的特点 ## 链接学派 ### 连接学派简介 #### 连接主义 - 连接主义(connectionism),又称为仿生学派或生理学派,其主要原理为神经网络及神经网络间的连接机制与学习算法 - 源于仿生学,认为高级的智能行为是从大量神经网络的连接中自发出现的 ### 神经网络基本概念与近代史 #### 神经网络的生物学启发 - 生物神经元 - 生物神经元结构 #### 神经网络基本概念 ##### 神经网络 - 人工神经网络主要由大量的神经元以及它们之间的有向连接构成 ##### 神经网络三要素 - 神经元 - 神经元的激活规则:主要是指神经元输入到输出之间的映射关系,一般为非线性函数。 - 网络拓扑结构 - 人工神经网络由许多神经元组成的信息处理网络,通常具有并行分布结构。 - 学习算法 - 参数的学习:关心神经网络权值和偏置的更新问题 - 结构的学习:关心神经网络结构的改变,包括节点数目的改变以及连接方式的改变 ##### 基于神经网络的知识表示与推理 - 基于神经网络的知识表示 - 将知识用神经元之间的连接权值隐性表示。 - 基于神经网络的推理 - 在一个已经训练好的网络基础上对未知样本进行预测。 ##### 人工神经网络的特性 - 非线性映射 - 通过样本训练进行学习 - 并行分布处理 - 适应于集成 - 硬件实现 #### 神经网络近代史 - McCulloch – Pitts 模型 - 感知器模型 - ADALINE模型 - BP神经网络 ### 神经网络基本思想与结构 #### Hopfield网络 - Hopfield网络是单层、 全连接、固定参数的反馈型神经网络 - 输出到输入均有反馈连接 - 每个神经元既是输入也是输出,神经元的输入结合其他所有神经元的输出以及自身输入 - 引入能量函数的概念,判断网络运行的稳定性 - 有离散型和连续性两种 - 离散型适用于联想记忆 - 连续性适合处理优化问题 #### 前馈神经网络 ##### 前馈神经网络的基本概念 - 前馈神经网络(feedforward neural networks),也叫多层感知器(multilayer perception),通常用于监督式机器学习或模式识别任务。 - 前馈神经网络的主要目标是去逼近某个函数 $f^*$,它通过定义一个映射$y=f(x;\theta)$,调整参数0去尝试获得一个最好的$f*$的逼近。 - 相比二层的感知器模型,前馈神经网络最大的特点是增加了非线性的激活单元,使得网络拥有非线性建模能力 ##### 前馈神经网络的结构 - 输入层 - 输出层 - 隐含层 - 由多个神经元组成,隐含层的个数可以是任意的,神经元的个数也可以是任意的,在实践中通常作为超参数 - 相邻两层之间的神经元两两连接 ,是一个全连接的结构,故有时候也叫做全连接层 ##### 非线性激活函数 - Logistic函数 - Tanh函数 ##### 前馈神经网络的前向传播 ##### 通用近似定理 - 指出人工神经网络近似任意函数的能力 ##### 前馈神经网络的后向传播 - 后向传播用于**网络参数的更新** - 网络的学习由**损失函数**驱动 - 学习的目的在于:**调整前馈神经网络的连接权重,使网络的输入与输出与给定的样本相同** - 学习过程中需要求损失函数对网络中每个权重的偏导数,这个过程从输出端到输入端逐层传递,因此叫做**后向(反向) 传播(BP算法)** #### 循环神经网络 ##### 序列化数据 - 序列是被排成一行的元素,可以被表示为$[a_1, a_2, \cdots,a_n]$ ##### 循环神经网络基本结构 - 循环神经网络,以下简称RNN,是⼀种为了适应序列化数据的序列特性而设计的神经网络。它具有**短期记忆能力**并能够在序列化数据上进行端到端的学习和计算。 - RNN的两种计算图表示方法: **折叠表示**和**展开表示** - RNN同样包含**输入层**、 **隐含层**和**输出层**三种类型的网络 ##### 未展开的RNN结构 - 与前馈神经网络的结构⼀样, 输⼊X[x1, x2, …, xn](n表示序列长度)的特征, 隐层用S[s1, s2, …, sn] 表示,输出用O[o1, o2, …, on] 表示,神经网络的输出层参数用V表示。则当前的输出函数(Output Function) g 为: $$ \mathbf{O}=g(\mathbf{V},\mathbf{S}) $$ ##### 展开RNN的计算 - 由于序列的序列特性,特征$s_t$不仅仅取决于当前输⼊$x_t$,还取决于$s_{t-1}$。把RNN的结构按照序列展开,每⼀个时间点的隐藏层函数(HiddenLayer Function) f 为:$\mathbf s_t=f(Ux_t+Ws_{t-1})$ 即RNN可表示为: $$ O_t=g(Vs_t) $$ $$ s_t=f(Ux_t+Ws_{t-1}) $$ ##### RNN与非线性动力系统的关系 - RNN可以理解为一个通用的非线性系统 ##### RNN的通用近似定理 - 一个完全连接的循环网络是任何非线性动力系统的近似器 ##### RNN参数的更新 - RNN的模型参数更新同样需要用到反向传播(BP)算法,但使用的BP算法是标准BP算法的推广,叫做**随时间反向传播**(BPTT, BP Through Time) ### 从浅层学习到深度学习 #### 深度学习的层级思想 #### 深度学习的模块化思想 ### 现代神经网络重要思想与结构 #### 深度卷积网络 ##### 动机和由来 - 来自神经科学与生理学的启发 ##### 基本构成与性质 ##### 网络层的概念 - 深度卷积网络的基本构成 - 卷积 (Convolution Layer) - 池化层 (Pooling Layer) - 非线性激活单元 (Nonlinear Activation Units) - 归一化层(Normalization Layer) - 全连接层(Fully-connected Layer)与分类器(Classifier) - 图像卷积 - 卷积算子的定义 - 卷积的作用 - 局部算子 - 平移同变性 - 特征增强 - 降噪 - 池化 - 又称下采样(Subsampling)或降采样(Down sampling), 常用于降低特征图的空间分辨率 - 池化的作用 - 局部变化的不变性(增加特征的鲁棒性) - 增大感受野 - 降维(降低卷积层输出的特征维度) - 防止过拟合 ##### 平移不变性和平移同变性 ##### 非线性激活单元 ##### 线性整流单元 ##### 归一化层 ##### 卷积网络模型的简化 ##### 典型架构 - LeNet - AlexNet - VGGNet - GoogLeNet - ResNet ##### 存在的问题 #### 生成与对抗 ##### 背景与应用 ##### 主要思想 - GAN的框架 - 生成网络接收一个随机的噪声,并生成“假数据”;判别网络接收“真数据”和生成的“假数据”,并预测不同数据的真实性概率。 - GAN的学习目标 - $$ \min_G\max_DV(D,G)=\mathbb{E}_{\boldsymbol{X}\sim p_{data}(\boldsymbol{X})}[\log D(\boldsymbol{x})]+\mathbb{E}_{\boldsymbol{Z}\sim p_{\boldsymbol{Z}}(\boldsymbol{Z})}[\log(1-D(G(\boldsymbol{z})))] $$ - 训练判别器D时,固定生成器G参数不变 - 训练生成器G时,固定判别器D参数不变 - GAN的优缺点 - 优点 - 并未局限网络结构的具体形式,理论上,只要是可微分函数都可以用于构建生成器和判别器; - 生成器的参数更新不是直接来自数据样本,而是使用来自判别器的反向传播,因此网络设计更加灵活,降低了损失函数设计的困难。 - 缺点 - 可解释性差,生成模型的分布没有显式的表达; - 比较难训练,生成器与判别器之间需要很好的同步,例如判别器更新 k 次而生成器只更新1次。 ##### 发展历程 - DCGAN - WGAN - CGAN - Pix2Pix - CycleGAN - PGGAN #### 注意力机制 ##### 动机与由来 - 人眼的视觉注意力 - 注意力机制的含义 - 注 意 力 机 制 ( AttentionMechanism) 表示一类模拟人类认知注意力的技术。 - 它主要通过引入乘法交互使输入的重要部分得到加强, 同时弱化剩余输入——网络应将算力关注到某些虽小但重要的区域。 - 注意力机制的发展 - 注意力模型 - 注意力机制的分类 - 点积注意力 - 强注意力(Hard-attention): {0, 1}二值分布问题 - 图像中每个点都有可能延伸出注意力;同时强注意力是⼀个**不可微**的过程,训练过程往往通过**强化学习**实现。 - 软注意力(Soft-attention): [0, 1] 连续分布问题 - 软注意力关注区域或者特征通道,同时软注意力是**可微**的,因此可以通过神经网络计算出梯度并且通过前向传播和**后向反馈**来学习得到注意力的权重 - 自注意力(Self-attention):特征间的自主学习 - 自注意力关注**全局信息**,有显式的表达式。由于每⼀个点都要捕捉全局上下文信息,导致自注意力机制模块计算复杂度和内存占用较大。 ##### 点积注意力简介 - 空间注意力 - 通道注意力 - 时间注意力 - 混合注意力 ##### 自注意力简介 - 自注意力 - 自注意力机制通过(Query, Key, Value)的三元组提供了一种有效的捕捉全局上下文信息的建模方式: $$ Attention(Q,K,V)=softmax(\frac{QK^T}{\sqrt{d_k}})V $$ Q表示query, K表示key, V表示value, $d_k$表示k的维度。 $$ $$ - 多头注意力 - 多头自注意力机制(Multi-head self-attentionmechanism),将模型分为多个头,形成多个子空间,可以让模型去关注不同方面的信息。 ##### 典型应用 #### 图上的深度学习 ##### 基本概念 - 网格化数据 - 图结构数据 - 非结构化(图)数据的难点 - 图的大小任意,拓扑结构复杂, 没有像图像⼀样的空间规律性 - 图没有固定的节点顺序,或者说没有参考节点 - 图通常是动态的,可能包含多模态的特征 - 图 - 图(graph)是⼀种数据结构,它可直观表示和可视化不同变量间的相互关系 $$ \mathcal{G}=\{\mathcal{V},\mathcal{E}\} $$ V 是节点(nodes)或顶点(vertices)的集合,E 是边(edges)的集合 - 属性图 - 节点和边都可以具有属性(特征) - 在⼀个图结构中, 每⼀个节点由它自身的特征以及与其相连的节点特征来定义该节点 - 图相关任务 - 图分类 - 节点分类 - 连接预测 - 群体检测(图聚类) - 图嵌入 - 图生成 ##### 图神经网络 - 图神经网络的提出 - 图神经网络元年 - 图神经网络 - 将图数据和神经网络进行结合,在图数据上进行端对端的学习和计算。 ##### 图卷积网络 ##### 典型应用 ## 行为学派 ### 行为学派简介 - 行为主义(Actionism) - 其原理为控制论(Cybernetics)及感知-动作型控制系统 - 行为主义认为人工智能源于**控制论**,其研究工作重点是**模拟人在控制过程中的智能行为**和作用,如对自寻优、自适应、自学习等控制论行为系统的研究。 ### 智能优化的产生与发展 #### 最优化理论的发展 #### 传统优化方法基本步骤 1. 选一个初始解 2. 停止判据——停止规则最优性检验 3. 向改进方向移动——得到改进解 #### 传统优化的局限性 - 对问题中目标函数、约束函数有很高的要求 - 最优性达到的条件太苛刻 - 只从一个初始点出发, 难以进行并行计算,以提高计算效率 - 不能够处理不确定性的优化问题 #### 实际问题中对最优化方法的要求 - 对问题的描述要宽松(目标和约束函数) - 并不苛求最优解 - 计算快速、高效,可随时终止(根据时间定解的质量) - 能够处理数据、信息的不确定性(如数据的模糊性,事件的随机性) #### 智能优化 - 进化计算 - 群智能算法 ### 智能优化典型思想与方法 #### 进化算法 ##### 遗传算法的生物学思想 ##### 遗传算法的基本框架 1. 根据问题的目标函数构造适应度函数(Fitness Function) 2. 产生一个初始种群(100-1000) 3. 根据适应度函数的好坏,不断选择和重组变异 4. 若干代后得到适应度函数最好的个体即最优解 ##### 遗传算法的要素 - 种群(Population) - 基因表达法——**编码/解码方法** (Encoding/Decoding Scheme) - **遗传算子**(Genetic Operator) - 交叉(Crossover) - 变异(Mutation) - **选择策略**: 一般为正比选择(赌盘轮选择) - 停止准则 (Stopping Rule/Criterion) #### 群智能算法 ##### 群体智能 - 群 - 群(swarm)定义为某种交互作用的组织或agent的结构集合(相互作用的相邻个体的集合)。群集中**个体行为简单**,但**群体行为相当复杂**。 - 群体智能 - 群集系统能够在没有外部指导和中心协调控制的情况下, 完成动态变化环境中的复杂任务。 ##### 群智能算法 ##### 群智能算法共性 1. 都有多个粒子, 代表多个智能体; 2. 每个个体通过一定的机制进行位置的变化或者移动,来对解的空间进行搜索; 3. 个体之间具有一定的独立性,利用局部信息和全局信息进行交互; 4. 群体在演变过程中都引入了随机数,以便进行充分地探索。 ##### 粒子群优化算法 - 基本思想 - 利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程,从而获得问题的可行解。 ##### 蚁群优化算法 ### 强化学习 #### 强化学习的机制由来 ##### 动物学习实验 - 效果法则 - 操作条件反射 ##### 计算神经科学 - 赫布(Hebbian)学习 - 多巴胺和基底核模型 - 情绪理论 ##### 最优控制与强化学习 - 最优控制 - 以优化方法的形式框架,求取连续时间控制问题中的最优控制策略。 - 假设模型已知(Model-based) - **动态规划**是求解最优控制问题的一种经典方法 - 强化学习 - 通过与未知和不确定(如随机)环境的直接交互(试错)学习一种行为策略,使长期的奖励总和(延迟奖励)最大化。 - 模型通常未知(Model-free) #### 基本模型和核心概念 ##### 强化学习要素与基本模型 - 智能体与环境 - 强化学习要素 - 环境 - 智能体 - 状态s - 历史(History) - 观察(Observation)、动作(Action)和奖励(Reward)的序列 $$ H_t=O_1,R_1,A_1,...,A_{t-1},O_t,R_t $$ - 历史包括了截止到t时刻所有能观察到的变量 - 状态(State) - 决定下一步要做什么所需要的信息 - 状态是历史的函数:$S_t=f(H_t)$ - 动作a - 奖励r - 奖励 - 一种标量的反馈信号;反映了t时刻,智能体Action的好坏 - 智能体的任务:最大化累积奖励(Cumulative reward) - 回报 - $$ G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+... $$ - 奖励假设 - 所有的目标都可以描述为某种期望的累积奖励的最大化。 - 状态的马尔科夫性质 - 信息状态(Information State) - 某状态包含了历史中的全部有用信息。 - 状态S具备马尔科夫性质,当且仅当满足: $$ P[S_{t+1}|S_t,A_t]=P[S_{t+1}|S_t,...,S_1,A_t] $$ ##### 智能体与环境的交互 ##### 智能体学习的核心构成 - 策略(Policy) - 代表了智能体的行为函数 - 表示从状态到动作的映射 - 确定性策略: $a=\pi(s)$ - 随机型策略(处于状态s时采取动作a的概率): $\pi(a|s)=P[A_t=a|S_t=s]$ - 模型(Model) - 预测环境接下来如何变化 - 转移(Transition)模型:P预测下一个状态 $$ \mathcal{P}_{ss^{\prime}}^a=\mathbb{P}[S_{t+1}=s^{\prime}\mid S_t=s,A_t=a] $$ - 奖励模型:R预测下一个瞬时奖励 $$ \mathcal{R}_s^a=\mathbb{E}\left[R_{t+1}\mid S_t=s,A_t=a\right] $$ - 值函数(Value function) - 对未来的回报期望(Return) ##### RL智能体分类 - 基于值函数的 - 在值函数空间中搜索 - 策略隐式表达( 基于值函数选择动作) - 基于策略的 - 在策略空间中搜索 - 没有值函数 - 混合型策略 - 有策略显式表达(动作网络) - 有值函数(评价网络) - Actor Critic - 无模型的(Model-free) - 不学模型 - 基于模型的(Model-based) - 学习模型 - 动态规划(环境已知) - 不需要学习模型 - 动态规划求解 #### 强化学习的若干关键问题 ##### 学习与规划 ##### 探索与利用 #### 经典强化学习: Q学习 ##### Q学习(其中一种Value-based RL方法,同类:SARSA) - 无模型的(Model-free) - 基于动作值函数0(s,a) - 通过与环境交互直接训练Q(s,a),找到Q*(s,a)和π*(s) ##### Q学习: Q表 ##### Q学习:更新Q值 ##### 值函数的近似表示 #### 深度强化学习 - 深度强化学习 - 运用深度神经网络完成强化学习中的各种子任务(譬如策略网络)。 ##### 深度Q网络 © 允许规范转载 赞 1 富婆饿饿饭饭