CRPI--模糊聚类表示学习.pptx

,A Clustering-Based Graph Laplacian Framework for Value Function Approximation in Reinforcement Learning,IEEE TRANSACTIONS ON CYBERNETICS, VOL. 44, NO. 12, DECEMBER 2014,1. 介绍,2. 模型,3. 分析和讨论,1. 介绍,强化学习是一类机器学习方法，求解可以描述为MDPs的序贯决策问题。通过与未知环境的交互，智能体学习动作策略来最大化累计回报。 强化学习已被认为是求解模型不确定的学习控制或自适应最优控制问题的重要框架。 早期研究主要集中在具有离散的状态和动作空间的MDPs。 但在很多实际应用中，需要用强化学习求解具有大规模或连续状态空间的MDPs。 针对这个问题，近似强化学习方法在近年来得到了广泛研究，如策略搜索、值函数估计（VFA）、actorcritic方法、分层强化学习、迁移学习等。,1. 介绍,在很多强化学习应用中，值函数估计一直处于核心地位，有线性估计结构和非线性估计结构。线性估计结构可以保证收敛性和稳定性，而非线性估计结构虽然可能具有更好的估计能力，但却难以进行严格的理论分析。 几个线性估计算法：线性Sarsa学习、最小二乘策略迭代、基于核的最小二乘策略迭代等。 之前的VFA算法的一个共同的缺点是，基函数通常需要人为确定，而不是基于状态空间来自动构造。 近来，有文献提出了一种称为原型值函数（proto-value function，PVF）的VFA方法。通过对自伴拉普拉斯算子的特征分析来构造PVFs，即将拉普拉斯矩阵对角化后，通过计算最小的特征值和对应的光滑特征向量来生成基函数。,1. 介绍,基于这种思想，相关文献提出了一类近似策略迭代算法representation policy iteration (RPI)。 针对大规模或连续状态空间MDPs，RPI中一个重要的问题就是二次抽样。因为收集的样本数量可能会很大，需要选取合适的样本子集来构造图。文献研究了一种随机二次抽样方法和一种基于轨迹的二次抽样方法。但针对大规模或连续状态空间的MDPs时，RPI的性能需要进一步提高。 围绕特征表示和值函数估计（VFA），本文提出了一种基于聚类的图拉普拉斯框架。 基于聚类技术，也即K-means clustering 或fuzzy C-means clustering，采用二次抽样构建了具有连续状态空间的MDPs的图拉普拉斯。通过对图拉普拉斯的特征分析，自动生成VFA中的基函数。,1. 介绍,基于聚类的图拉普拉斯结合了RPI，本文所提出的新的学习控制算法称为基于聚类的RPI（CRPI）。 在CRPI中，二次抽样的目的是过滤掉那些不必要的点，这些点所包含的状态空间的基本流形特征的信息很少，从而用具有代表性的点来学习一个有效的基函数集。 经过聚类分析后，同一聚集中的所有点呈现出最大的相似性。中心即为同一聚集中所有点的平均或权重平均。基于所有聚集的中心所构造的图能更准确地表示状态空间的基本流形。 仿真和实验表明，相比较之前的方法，本文提出的基于聚类的图拉普拉斯方法只需要很少的样本就可得到有效的基函数集，且CRPI的性能要比RPI好很多。,A. MDP M: X, A ,R, P X 状态空间， A 动作空间，R=R(x,a) 回报函数， P 状态转移概率 策略：从状态空间到动作空间概率分布的映射；,2. 模型,基于聚类的图拉普拉斯框架 与之前的图拉普拉斯方法相比，本文的方法具有如下特点： 一是构造图拉普拉斯时的子集选择。在基于聚类的框架下，用基于聚类的方法选择的数据点更具有代表性。本文提供两种基于聚类的二次抽样方法。 在RPI中，随着所收集的样本的增加，用于构造图的子集的规模也在增加，使得图越来越复杂。而基于聚类的拉普拉斯框架能避免这种情形，因为在整个学习过程中，二次抽样的数目和聚集数总是一样的。,2. 模型,B . 基于聚类的图拉普拉斯框架,最主要的优点是在构造图时可以通过选择合适的二次抽样来增强基函数的估计能力。 在连续域内，通常使用Nystrm extension method将已检测点的特征函数扩展到未检测点，也可以看作是整个状态空间基函数的估计。 依据基于聚类的图拉普拉斯框架，提出了CRPI算法。 在CRPI中，样本是随机收集的，或者通过一个初始策略收集。样本收集之后，采用基于聚类的方法从原始样本集中选取二次抽样样本。通过连接样本子集中的任意两个点得到边，并给所有边赋予权重，从而可以构造图。使用组合或标准拉普拉斯计算拉普拉斯特征函数。则基函数由图拉普拉斯的最小特征值对应的最光滑的特征向量构成。,2. 模型,对于点 , =1,2, ，用表示一个对角矩阵，其所有元素为权重矩阵 = 的行和。 则组合拉普拉斯 L 定义为如下的算子L=D-W 。 权重 =( , ) 可以设为 其中0为预先定义的参数。 计算L的前l 个最小的特征值 (=1,2,)，进而得到l个最光滑的特征向量。 将这l个特征向量作为列构造基函数矩阵 = .,2. 模型,(公式6),sigma,phi,lamda,基函数矩阵 的第 i 行记为 这里 是点集或样本集中状态 的特征向量。 如果一个样本点 不在图的点集 V 中，则其基函数 可以 通过 Nystrm extension 来生成如下： 其中 是 的k-最近邻点集， 计算如下：,2. 模型,(公式9),(公式8),(公式7),gamma,phi,为了对具有连续状态和 n 个离散动作的MDPs的动作值函数进行估计，对每个动作重复以上基函数 是指标函数, 如果 , 否则 从而对于策略 的动作值函数 估计为 其中 是基函数的维数， 是 的第 i 个元素， 是第 i 个系数。,2. 模型,(公式10),(公式11),psi,令 这里 是从策略 收集到的样本集，其中 是由 决定的， t 为迭代数，其初始化为0。 则可以通过下式得到策略估计的最小二乘定解和对应的改进策略,2. 模型,(公式13),(公式12),phi,psi,2. 模型,2. 模型,CRPI中，聚类方法用来从所收集的样本集中选择一个子集，该子集的规模通常远远小于原始样本集。论文提供了两个基于聚类的二次抽样方法，分别使用了K-均值聚类算法和FCM算法。 所提方法的一个特性是：输出不是聚集的质心或权重质心，而是聚集中离质心或权重质心最近的样本点。 聚类方法中采用两点间的欧式距离作为度量。,2. 模型,C . CRPI中基于聚类的二次抽样算法,对收集的样本集 ，K-均值算法将每个点分配到K 个聚集的某一个中，从而最小化聚集方差 其中 是 的第 k 个子集， 是聚集 k 的质心 其中 是 中点的数目。,2. 模型,C-1 . 使用K-均值聚类的二次抽样-算法描述,(公式15),(公式14),聚集中心产生后，通过选择那些最接近聚集中心的点，每个聚集都产生了一个子集。 在使用K-均值聚类的二次抽样算法中，初始中心的选择始终不是随机的。如果学习策略的性能足够好的话，最后生成的子集中的 K 个点将作为下一次迭代的初始质心。,2. 模型,C-1 . 使用K-均值聚类的二次抽样-算法描述,2. 模型,通过最小化类内方差 FCM算法将给定的数据集 X 划分成 c 个模糊集。式中b为权重指数， ， 是 X 的模糊c-划分，满足如下条件 是中心向量集合， 是是第 k 个聚集中心， 是 上的诱导A-范数。具体算法中用单位矩阵代替A 。,2. 模型,C-2 . 使用 FCM 聚类的二次抽样-算法描述,(公式16),(公式17),2. 模型,在连续状态的MDPs中，为了学习近似最优策略，有必要基于存在样本的特征函数去计算那些新的未检测点的特征函数。 在RPI中，运用了 Nystrm extension 方法，同时结合迭代更新和随机算法，以实现 low-rank 逼近。 用组合拉普拉斯算子 来做性能分析。其迹可以表示为 也即 L 的特征值之和等于 W 的除对角线之外的元素之和。,3. 分析和讨论,A. 性能分析,令 和 分别为用基于聚类的方法和基于轨迹的方法构造的算子， 和 是对应于边 的权重， 和 是 和 的特征值。则有 上式说明，相比RPI中基于轨迹的二次抽样方法，基于聚类的图拉普拉斯具有更小的特征值。因此，有利于CRPI算法寻找更光滑的基函数。,3. 分析和讨论,下面分析 Nystrm extension 方法的估计误差。 按照Nystrm extension误差，CRPI和RPI的性能分析将基于构造图所选择的子集的质量来进行。 令L为一个图算子，它是用基于聚类的二次抽样方法得到的子集而构造的。H表示由所有样本生成的图算子矩阵。 Nystrm extension方法实现了将基于部分状态计算的L的特征向量向全部状态的插入。 设 H 为一个需要估计的 对称半正定矩阵（SPSD）。选择 H 的一个 最重要的子矩阵，将 H 分块如下 其中 L 为 SPSD矩阵。,3. 分析和讨论,B. 误差分析,对应多指标集 考虑划分。 H 和 L的特征分解如下 其中 为对角阵， 为 H