流形学习:背后的理论

Evan 2018-09-28

流形学习:背后的理论

流形学习已经成为几何学的一个激动人心的应用,特别是微分几何学在机器学习中的应用。理解算法背后的理论将有利于更有效地应用算法。

我们将阐述什么是流行学习方式,以及它在机器学习中的应用。流形学习使用高维数据的几何属性来实现以下内容:

  1. 聚类:查找类似点的组。给定{X1,...,Xn},构建函数f:X到{1,...,k}。两个“close”点应该在同一个聚类中。
  2. 降维:Project points指向较低维空间,同时保留结构。给定R ^ D中的{X1,...,Xn},构建函数f:R ^ D到R ^ d,其中d<D,“Closeness”应该被保留。
  3. 半监督,监督:给定标记和未标记点,建立标记函数。给定{(X1,Y1),...,(Xn,Yn)},构建f:X到Y.两个“close”点应该具有相同的标签。

使用数据分布进一步细化“closeness”的概念。有一些框架可通过以下方式实现:

  1. 概率观点:密度缩短了距离
  2. 聚类视点:连接区域中的点共享相同的属性
  3. 流形观点:距离应该“沿着”数据流形测量
  4. 混合版本:两个“close”点是通过高密度区域的短路径连接的点

我们将要讨论的第一个想法是拉普拉斯正则化,它可以用作机器学习中监督和半监督学习中的正则化器,以及可以通过投影到Laplaican最后一个特征向量来降低维度。

让我们理解拉普拉斯在这种情况下的含义。拉普拉斯算子仅仅是度矩阵(这是对每个顶点入射的边数的度量)减去邻接矩阵(这是衡量各个顶点如何相互连接的度量)。现在我们准备开始理解第一种方法:拉普拉斯正则化

拉普拉斯正则化

正则化在减少过度拟合和确保机器学习模型不会过于复杂方面非常有用。使用laplacian进行规范化扩展了Tikhonov正则化中首次使用的思想,该理论应用于再生核希尔伯特空间(RKHS)。

我们不需要深入研究RKHS,但是我们必须要理解的主要结果是在RKHS中,对于函数空间X中的每个函数x,在kernel中存在一个允许的唯一元素K_x,它允许我们定义一个范数|| f || 对于代表RKHS中函数复杂性的每个函数(在机器学习的情况下学习的映射函数),我们可以使用它来规范算法。所以问题就会变成

流形学习:背后的理论

这个regulariser 被称为extrinsic regulariser。现在laplacian正则化增加了另一个称为intrinsic regulariser的regulariser ,它考虑了流形(manifold)的内在几何,并用它来规范算法。如何定义regulariser 有多种选择,但大多数定义都围绕着manifold上的梯度。我们希望regulariser在不需要时(当数据密集时)惩罚复杂的函数。换句话说,当数据密集时,我们希望函数是平滑的,这也意味着当数据的边际概率密度很大时,函数manifold 上的梯度必须很小。这被形式化为

流形学习:背后的理论

如果我们能直接计算这个积分,那就太棒了,但就像大多数机器学习概念一样,实现它需要使用可用数据进行某种形式的估计。在这种情况下,我们需要将数据点看作是图上的点,并基于某种距离的概念将它们连接起来。这通常是通过实现某个函数和设置一个条件来实现的,如果距离(使用函数导出)小于一个特定的值,那么这两个点与一条边相连。其中一个函数是标准高斯函数:

流形学习:背后的理论

现在我们需要一种估计积分的方法。遍历完整的推导过程会使这篇文章太长,因此我将概述所涉及的主要思想:使用Stokes定理和Laplacian approximates Laplace-Beltrami算子的事实,我们可以得到大量数据点的近似积分。因此,可以估计该regulariser 的性能

流形学习:背后的理论

其中f是数据函数的向量值,n是数据点的数量(标记和未标记)。所以现在要解决的最后一个问题就变成了

流形学习:背后的理论

与其他内核方法一样,主要缺点是Hilbert空间可能是无限维的,如果无法明确地找到正则化,则无法在空间中搜索解。因此,在正则化上强加某些条件(严格单调递增实值函数)并使用着名的表达式定理,我们可以将所需函数分解为权重α的有限维空间,这样

流形学习:背后的理论

现在我们只需要搜索alpha的有限维空间来解决我们想要的函数。

与L1或L2正则化相比,这是一个更复杂的正则化,但它与数据的几何结构密切相关,并且在确保机器学习模型不过度拟合方面似乎有所回报。

拉普拉斯特征映射

Laplacian特征映射使用了与上述正则化相似的推理,只是它被应用于降维而不是正则化。我们首先生成一个以顶点为数据点的图,并将具有特定距离(确切地说是欧几里得)且间隔更小的点连接起来。然后根据Heat kernel加入权重。最后计算特征值和特征向量,利用最小特征向量将数据空间嵌入到m维空间中。在形式上,

流形学习:背后的理论

解决这个特征向量问题

流形学习:背后的理论

现在我们可以将数据投影到第一个m特征向量f1 ... fm上,有效地减少了数据的维数。

结论

回顾一下,我们介绍了流形学习的内容,利用数据的几何形状来提高机器学习算法的效率(通过减少过度拟合或维度)。接下来,我们讨论了两个程序,特别是拉普拉斯正则化和拉普拉斯特征映射。它们都建立在图论和微分几何上,理解它们背后的理论将有助于知道何时部署哪个程序以及某些数据结构如何影响这些程序的效率。

相关推荐