LDA的思想 寻找最能把两类样本分开的投影直线 的思想: 的思想 寻找最能把两类样本分开的投影直线. 自 LDA的目标 使投影后

LDA的思想 寻找最能把两类样本分开的投影直线 的思想: 的思想 寻找最能把两类样本分开的投影直线. 自 LDA的目标 使投影后两类样本的均值之差与投影 的目标: 的目标 动 化 样本的总类散布的比值最大

这是 Google 对 http://wenku.baidu.com/view/cf389a0e52ea551810a68722.html 的缓存。 这是该网页在 2010年12月7日 03:39:15 GMT 的快照。 当前页在此期间可能已经更改。 了解详情

纯文字版本突出显示以下搜索字词： 流 形 学习 问题
手机文库 | 百度首页 | 百度知道 | 百度文库首页 | 登录 新闻　网页　贴吧　知道　MP3　图片　视频　百科　文库

帮助

全部 DOC PDF PPT XLS TXT


百度文库 > 专业文献/行业资料 > 计算机
下载文档收藏流形学习问题 中国科学院自动化研究所的资料 中国科学院自动化研究所的资料

中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 流形学习问题 杨 剑中国科学院自动化研究所 2004年12月29日 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 维数约简增加特 征数 增加信 息量 提高准 确性 类 增 器 的 难 度 分 训 练 加 维数 , 特征约简. 特征约简 特征, 特征 中 国 科 学 院 自 动 化 研 究 所特 征 约 简 Machine Learning and Data Mining 2004 特征特征选择 选择 特征 特征 特征 特征 2 3 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 Outline 线性维数约简方法 流形和维数约简. 流形和维数约简 流形学习的一些数学基础. 流形学习的一些数学基础 几种流形学习算法简介： 几种流形学习算法简介：LLE, Isomap, Laplacian Eigenmap. 流形学习问题的简单探讨. 流形学习问题的简单探讨 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 线性约简方法通过特征的线性组合来降维. 本质上是把数据投影到低维线性子空间. 线性方法相对比较简单且容易计算. 两种经典且广泛使用的线性变换的方法: 主成分分析 (PCA); 多重判别分析 (MDA). 中 国 主成分分析 ( PCA ) 科 学 PCA的目的：寻找能够表示采样数据的最好的投影子 的目的： 的目的 院 空间 空间. 自 PCA的求解：对样本的散布矩阵进行特征值分解 所 的求解： 的求解 对样本的散布矩阵进行特征值分解, 动 求子空间为过样本均值 以最大特征值所对应的特征向量 求子空间为过样本均值, 化 为方向的子空间 为方向的子空间. 研 Principal 究 component 所 Machine Learning and Data Mining 2004 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 主成分分析 PCA对于椭球状分布的样本集有很好的效果, 学 习所得的主方向就是椭球的主轴方向. PCA 是一种非监督的算法, 能找到很好地代表所 有样本的方向, 但这个方向对于分类未必是最有利的. 中 国 线性判别分析(LDA)1 线性判别分析 科 学 LDA是一种监督的维数约简方法 是一种监督的维数约简方法. 是一种监督的维数约简方法 院 LDA的思想 寻找最能把两类样本分开的投影直线 的思想: 的思想 寻找最能把两类样本分开的投影直线. 自 LDA的目标 使投影后两类样本的均值之差与投影 的目标: 的目标 动 化 样本的总类散布的比值最大 . Best projection 研 direction for 究 classification 所 Machine Learning and Data Mining 2004 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 线性判别分析(LDA) 线性判别分析 2 LDA的求解 经过推导把原问题转化为关于样本集总 的求解: 的求解 类内散布矩阵和总类间散布矩阵的广义特征值问题. 类内散布矩阵和总类间散布矩阵的广义特征值问题 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 多重判别分析 (MDA) MDA把LDA推广到多类的情况. 对于c-类问题, MDA把样本投影到 c-1 维子空间. 目标和解法与LDA相似,只是类内散布矩阵的定义 更为复杂, 求解的广义特征值问题也更为复杂. 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 线性方法的缺点线性方法对于很多数据不能进行有效的处理. 线性方法对于很多数据不能进行有效的处理 20 15 10 5 0 1 0.5 0 -0.5 -1 -1 -0.5 0.5 0 1 现实中数据的有用特性往往不是特征的线性组合. 现实中数据的有用特性往往不是特征的线性组合 线性组合 R 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 流形学习和维数约简流形是线性子空间的一种非线性推广. 流形是线性子空间的一种非线性推广 流形是一个局部可坐标化的拓扑空间. 流形是一个局部可坐标化的拓扑空间 流形学习是一种非线性的维数约简方法. 流形学习是一种非线性的维数约简方法 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 流形学习的可行性 1 许多高维采样数据都是由少数几个隐含变量所决定 的, 如人脸采样由光线亮度, 人离相机的距离, 人的头 部姿势, 人的脸部肌肉等因素决定. 2 从认知心理学的角度, 心理学家认为人的认知过程是 基于认知流形和拓扑连续性的. R 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 流形学习的一些数学基础参考文献: 陈省身, 陈维桓, 微分几何讲义. 北京大学出版社, 1983 M Berger, B Gostiaux. Differential Geometry: Manifolds, Curves and Surfaces, GTM115. SpringerVerlag, 1974 陈维桓, 微分流形初步(第二版). 高等教育出版社, 2001 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 拓扑的满足以下性质的子集族: 集合 X上的拓扑 τ 是 X 的满足以下性质的子集族 τ 对属于它的任意多元素的并集是封闭的 对属于它的任意多元素的并集是封闭的; (ii) τ 对属于它的有限多元素的交集是封闭的 对属于它的有限多元素的交集是封闭的; (iii) φ ∈ τ 且 X ∈ τ , 称 ( X ,τ ) 是一个拓扑空间. 是一个拓扑空间 (i) 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 Hausdorff 空间如果对空间( X ,τ )中的任意两点 x ≠ y, 存在 A ∈ ? (x ) 和 B ∈ ? ( y ) 使得 A ∩ B = φ , 称 ( X ,τ )是一个 Hausdorff 拓扑空间 拓扑空间. 中 国 流形的定义 科 学 设 M 是一个 是一个Hausdorff 拓扑空间 若对每一点 p ∈ M ,都有 拓扑空间, 院 P 的一个开领域 U 和 R n 的一个开子集同胚 则称 M 为 n 的一个开子集同胚, 自 维拓扑流形, 维流形. 动 维拓扑流形 简称为 n 维流形 化 研 究 所 Machine Learning and Data Mining 2004 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 坐标卡是同胚, 中的开集, 假定 ? : U → ? (U ) ? R n 是同胚 其中? (U ) 是 R n中的开集 的一个坐标卡, 则称 (U , ? )为流形 M 的一个坐标卡 并且把 ? ( p ) 在 R n 的坐标, 中的坐标 (? ( p )) 称为点 p ∈ U 的坐标 M R2 x2 z x: coordinate for z x x1 流形在本质上是局部可坐标化的拓扑空间. 流形在本质上是局部可坐标化的拓扑空间 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 C 相关 r 的两个坐标卡. 设 (U1 , ?1 ), (U 2 , ? 2 ) 是 n 维流形 M 的两个坐标卡 若当 U1 ∩ U 2 ≠ φ 时 , ? 2 ?1?1 : ?1 (U1 ∩ U 2 ) → ? 2 (U1 ∩ U 2 ) 次可微的, 和它的逆映射都是 次可微的 则称(U1 , ?1 ), (U 2 , ? 2 ) 是 C r r 相关的. 相关的 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 微分结构维流形, 设 M 是 n 维流形 假定Λ = {(U α , ?α ) : α ∈ I } 是 M 上 坐标卡的一个子集合, 且满足以下条件: 坐标卡的一个子集合 且满足以下条件 (1) {U α : α ∈ I } 构成 M 的一个开覆盖 的一个开覆盖; (2) 属于Λ 的任意两个坐标卡都是 C 相关的 相关的; r 是极大的, Λ 是极大的 微分结构. 则称 Λ 是 M 上的一个C r 微分结构 (3) 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 C 微分流形 r 维流形, 设 M 是 n 维流形 若在 M 上指定了一个 C r 微分结构 Λ, 微分流形. 则称 ( M , Λ ) 为一个 n 维 C r 微分流形 属于 Λ 的坐标卡(U , ? ) 称为该微分流形的容许坐标卡. 称为该微分流形的容许坐标卡 为光滑流形. 当 r = ∞ 时, 称 M 为光滑流形 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 光滑函数上的连续函数. 设 f : M → R 是定义在光滑流形 M 上的连续函数 若在点 x ∈ M , 存在 M 的一个容许坐标卡 (U , ? ) 使得 x ∈U , f ? ?1 : ? (U ) → R 是在点? (x ) 处光滑的函数 则称函数 处光滑的函数, f 处是光滑的. 在点 x 处是光滑的 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 光滑映射维光滑流形, 设 M, N 分别是 m 维, n 维光滑流形 f : M → N 是连续映 射. 设 x ∈ M , 若存在 M 在点 x 处的容许坐标卡 (U , ? ) 及 N 在点 f (x ) 处的容许坐标卡 (V ,ψ ) , 使得 ψ f ? ?1 : ? (U ∩ f ?1 (V )) → ψ (V ) 处光滑的映射, 是在点 ? ( x )处光滑的映射 则称映射 f 在点 的. 处处光滑的映射称为光滑映射. 处处光滑的映射称为光滑映射 x 处是光滑 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 切向量光滑流形M在点 光滑流形 在点 x 的切向量 v 是一个满足下列条件的映 ∞ 射 v : Cx → R (1) ?f , g ∈ C x∞ , 有 v ( f + g ) = v ( f ) + v ( g ); (2) ?f ∈ C x∞ , ?λ ∈ R,有 v (λf ) = λ ? v ( f ); (3) ?f , g ∈ C x∞ , 有 v ( f ? g ) = f ( x ) ? v ( g ) + g ( x ) ? v ( f ). 光滑流形的切向量是曲线的切向量的一种推广. 光滑流形的切向量是曲线的切向量的一种推广 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 切空间设 M 是 m 维光滑流形, x0 ∈ M 用Tx0 M 表示 M 在点 维光滑流形 构, 使得 Tx0 M 成为 m 维向量空间 称其为 M 在点 维向量空间, 的切空间. 的切空间 x0 处的全体切向量的集合, 处的全体切向量的集合 则在 Tx0 M 中有自然的线性结 x0 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 Riemann 流形黎曼流形就是以光滑的方式在每一点的切空间上指 定了欧氏内积的微分流形. 定了欧氏内积的微分流形 R 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 与流形学习有关的参考文献与机器学习, 统计学等相关的各种杂志和会议论文 http://www.cse.msu.edu/~lawhiu/manifold/ 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 流形学习问题 是一个低维流形, 是一个光滑嵌入, 设 Y ? R d 是一个低维流形 f : Y → R D 是一个光滑嵌入 是随机生成的, 其中 D>d . 数据集 { yi }是随机生成的 且经过 f 映射为观 察空间的数据 {xi = f ( yi )}. 流形学习就是在给定观察样本 集 {xi } 的条件下重构 f 和 { yi } . V. de Silva and J. B. Tenenbaum. Global versus local methods in nonlinear dimensionality reduction . Neural Information Processing Systems 15 (NIPS'2002), pp. 705712, 2003. 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 几种流形学习算法局部线性嵌入(LLE). S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, vol. 290, pp. 2323--2326, 2000. 等距映射(Isomap). J.B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, vol. 290, pp. 2319--2323, 2000. 拉普拉斯特征映射(Laplacian Eigenmap). M. Belkin, P. Niyogi, Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, Vol. 15, Issue 6, pp. 1373 –1396, 2003 . 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 局部线性嵌入(LLE) 前提假设： 前提假设：采样数据所在的低维流形在局部是线性的, 即每个采样点可以用它的近邻点线性表示. 学习目标： 学习目标：在低维空间中保持每个邻域中的权值不变, 即假设嵌入映射在局部是线性的条件下, 最小化重构误差. 求解方法： 求解方法：特征值分解. 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 LLE算法 1 计算每一个点 X i 的近邻点, 一般采用K 近邻或者 ε 邻域. 使得把 X i 用它的K个近邻点线性表示 2 计算权值 Wij， 的误差最小, 即通过最小化 X i ? Wij X j 来求出 Wij . 3 保持权值 Wij 不变, 求 X i 在低维空间的象 Yi , 使 得低维重构误差最小. 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 LLE算法示意图 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 LLE算法的求解 1 计算每一个点 X i 的近邻点. 2 对于点 X i 和它的近邻点的权值 W , Wij = ij ∑k G ijk ?1 i Glm ∑lm ，其中 G ijk＝（X i ? η j） X i ? ηl） j ,ηl为X i的近邻点. ? （ ,η ?1 3 令 W＝(W )， M ij = ( I ? W ) ( I ? W ) , 低维嵌入 T 是 M 的最小的第 2到第 d＋1 个特征向量. 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 LLE算法的例子(1) 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 LLE算法的例子(2) 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 LLE算法的优点 LLE算法可以学习任意维的局部线性的低维流形. LLE算法中的待定参数很少, K 和 d. LLE算法中每个点的近邻权值在平移, 旋转,伸缩变换下 是保持不变的. LLE算法有解析的整体最优解,不需迭代. LLE算法归结为稀疏矩阵特征值计算, 计算复杂度相对 较小, 容易执行. 中 国 LLE算法的缺点 科 学 LLE算法要求所学习的流形只能是不闭合的且在局部 院 是线性的. 自 LLE算法要求样本在流形上是稠密采样的. 动 LLE算法中的参数 K, d 有过多的选择. 化 研 LLE算法对样本中的噪音很敏感. 究 所 Machine Learning and Data Mining 2004 R 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 多维尺度变换 (MDS) MDS 是一种非监督的维数约简方法. MDS的基本思想: 约简后低维空间中任意两点间的距离 应该与它们在原高维空间中的距离相同. MDS的求解: 通过适当定义准则函数来体现在低维空间 中对高维距离的重建误差, 对准则函数用梯度下降法求解, 对于某些特殊的距离可以推导出解析解法. 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 MDS的准则函数 J ee = (d ij ? δ ij ) 2 ∑i 0, 则只要样本集充分大且适当选择K 且适当选择 , 不等式 graph distance 1 ? λ1 ≤ ≤ 1 + λ2 geodesic distance 成立. 至少以概率 1 ? ? 成立 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 Isomap 算法的例子(1) 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 Isomap 算法的例子(2) 中 国 Isomap算法的特点 科 学 Isomap是非线性的, 适用于学习内部平坦的低维流形, 院 自 不适于学习有较大内在曲率的流形 . Isomap算法中有两个待定参数K, d . 动 化 Isomap算法计算图上两点间的最短距离, 执行起来比 研 较慢 . 究 所 Machine Learning and Data Mining 2004 R 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 拉普拉斯算子设 M 是光滑的黎曼流形, f 是 M 上的光滑函数, ?f 是 f 的梯度, 则称线性映射 ? : C ∞ ( M ) → C ∞ ( M ), ?f = ?div( ?f ) 为 M 上的拉普拉斯算子, 其中div是散度算子. 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 图上的拉普拉斯算子设 G 是一个图, v 是它的顶点, d v 是 v 的自由度, w(u,v) 是连接顶点u,v 的边的权值,令 ?d v ? w(u, v ) ? l (u, v ) = ? -w(u,v ) ? 0 ? u=v u,v是连接的 其它 L=T u u ~v ? 12 lT ? 12 , 其中 T 是对角矩阵,对角线的元素为 ∑ ? w(u, v) , 则称 L 为图 G 上的拉普拉斯算子. 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 拉普拉斯特征映射(Laplacian Eigenmap) 基本思想： 基本思想：在高维空间中离得很近的点投影到低维空间 中的象也应该离得很近. 求解方法：求解图拉普拉斯算子的广义特征值问题. 求解方法： 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 Laplacian Eigenmap 算法 1 从样本点构建一个近邻图, 图的顶点为样本点, 离得 很近两点用边相连 (K近邻或 ε 邻域). 个点不相连， 2 给每条边赋予权值 如果第 i个点和第 j 个点不相连， 权值为0，否则 Wij = 1 ; 3 计算图拉普拉斯算子的广义特征向量, 求得低维嵌入. 令D为对角矩阵 Dii = ∑ W ji , L = D ? W , L是近邻图上的 j 拉普拉斯算子, 求解广义特征值问题 Lf = λDf . 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 Laplacian Eigenmap算法的例子(1) 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 Laplacian Eigenmap算法例子(2) 300 most frequent words of the Brown corpus represented in the spectral domain 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 Laplacian Eigenmap算法例子(2) The first is exclusively infinitives of verbs, the second contains prepositions and the third mostly modal and auxiliary verbs. We see that syntactic structure is well-preserved. 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 Laplacian Eigenmap算法的特点算法是局部的非线性方法. 算法与谱图理论有很紧密的联系. 算法中有两个参数 k,d. 算法通过求解稀疏矩阵的特征值问题解析地求出整 体最优解. 算法使原空间中离得很近的点在低维空间也离得很 近, 可以用于聚类. R 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 LLE, Isomap, Laplacian Eigenmap 有效的原因它们都是非参数的方法, 不需要对流形的很多的参数假 设. 它们是非线性的方法, 都基于流形的内在几何结构, 更 能体现现实中数据的本质. 它们的求解简单, 都转化为求解特征值问题, 而不需要 用迭代算法. 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 流形学习问题探讨保持高维数据的某种性质不变为目标. 将问题转化为求解优化问题. 提供有效的解法. 1 对嵌入映射或者低维流形作出某种特定的假设, 或者以 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 流形学习问题探讨如何确定低维目标空间的维数. 2 为流形学习提供更为坚实和易于接受的认知基础. 当采样数据很稀疏时, 怎样进行有效的学习. 将统计学习理论引入流形学习对其泛化性能进行 研究. 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 流形学习问题探讨 3 流形学习作为一种非线性降维或数据可视化的方法 已经在图像处理如人脸图像,手写数字图像, 语言处理 方面得了利用. 将其作为一种监督的学习方法用于模式识别, 虽然 有研究者涉足, 但是目前在这方面的工作还很有限. 中 国 科 学 院 自 动 化 研 究 所 Machine Learning and Data Mining 2004 Thanks!
下载本文档需要登录，并付出相应积分。如何获取积分?


大小: 2.4MB

所需积分: 2

当前文档信息

已有2人评价

浏览：24次下载：6次

贡献时间：2010-11-27


--------------------------------------------------------------------------------

贡献者： hz_hdlinux 蜻蜓点水 一级

文档关键词
流形学习
更多相关推荐文档
基于流形学习的数据降维方法...
0人评 11页

函数学习
0人评 12页

学习顺序
0人评 2页

Excel学习
1人评 53页

PS学习笔记
0人评 14页

更多同分类热门文档
程序员羊皮卷下载版
5173人评 60页

C语言深度解剖
6544人评 131页

代码之美中文版
4330人评 120页

Linux系统命令及其使用...
2908人评 39页

SQL语言艺术
3374人评 85页

©2010 Baidu使用百度前必读文库协议