NeurIPS 2022 | 广义拉普拉斯特征映射

公众号新闻

2022-12-18 15:12

©作者 | 堪村无业土拨鼠

论文标题：

Generalized Laplacian Eigenmaps

论文链接：

https://openreview.net/pdf?id=HjicdpP-Nth

论文来源：

NeurIPS 2022

感谢 AC 慧眼识珠（Zhu）双关 LOL。这篇文章打分不高，556。但是很明显的并没有比较 senior 的审稿人（没有经历过 Manifold Learning 时代）的那种，问的问题都有点牛头不对马嘴。关注的点都异常诡异，抓住一个技术细节（LogDet）说你这玩意不 novel...... 大哥我从来就没说 LogDet 是我发明的啊，而且我引了 20 年前那篇经典文章。

最后凭借求生欲极强的 rebuttal，让 ac 都给出了 nice rebuttal 的评价。这篇文章让我激动的一个大点是，我们可能找到了对某一大类方法（Linear Discriminant Analysis, Manifold Learning）更加 high level 的一个认识。高能预警，此文是挖坑文，并没有展开太多的特例，全程都透露着各种填坑的姿势，欢迎各位来填坑或者合作。让我们在开始故事之前先补个最基本的常识：

但凡学过一点点传统 machine learning，statistical learning 之类的同学应该都听说过 Linear Discriminant Analysis（LDA，但不是 NLP 的那个 LDA）。St 很好理解，就是 PCA 最喜欢用的协方差矩阵，Sw 其实是假设每个类都 share 同一个分布，所以减掉内类均值之后的残差无视类别构造协方差矩阵。

Sb 就更好理解了，每一类的均值看做一个样本构造协方差矩阵。一般来说这三个矩阵有这么一个关系 Rank(Sw) + Rank(Sb)>=Rank(St)，这个很容易想象为啥是这样，我就不在这展开讨论了。

接下来让我们思考一下 Condition 1.Rank(St) = Rank(Sw) + Rank(Sb)（这是本文的核心贡献）。之所以为核心贡献是，这个 condition 定义了一个具有非常优秀性质的嵌入空间。接下来我们会解释这个 condition 的意义，以及基于这个 condition 怎么定义一个目标函数（NP-hard），以及怎么松弛这个 NP-hard 的目标函数。

为了便于想象，我们给了几个非常简单的例子：

在 Figure 1 中，我们给了一个三维空间中有三类的例子他们都满足 Condition 1. 分别是 Rank(Sb)=0,1,2. 当 Rank(Sb)=0 意味着三个类别的均值重合成到一个点。Rank(Sb)=1 则意味着类中心应该在一条线上。Rank(Sb)=2 这意味着类中心应该在一个平面上。我们会发现一个非常有趣的性质，从这三个图启发了我们一个理论：

这个理论非常简单，就是说如果满足这个条件，类中心之间的距离是任意非同类 pair 距离的下界。不做 metric learning 或者 representation learning 的同学可能意识不到这个性质有多么优秀。我这插个 metric learning 大家比较耳熟能详的 loss function 进来让大家理解为啥这玩意从理论上而言非常有用：

▲ ArcFace

以 arcface 为例，其实从 LargeMargin（SphereFace 前身）开始，都会多一个margin 项使得类间拉的足够开从而优化他们之间 overlap 尽可能小。ok 问题来了，这种操作就算对 close set 数据都是没有任何 guarantee 的比如一个下界说明 margin 参数和最差情况下的不同样本间距之间的关系。因此这类 loss 纯粹是个经验性质的 loss function。

让我们回到这个 condition。换句话说，我只需要满足这个 condition 的情况下，去优化类间距离我就可以通过改善下界的方式来提高判别能力。接下来问题来了，我怎么根据这个 condition 来设计一个 loss function 呢？

首先我希望 Rank(St) 越大越好，因为越大代表 features 利用了整个空间。至于 Rank(Sb) 和 Rank(Sw) 怎么分配，我们很容易发现 Rank(Sb) 有一个上界 c-1,c 是类别数。其实在很多情况下 c 都比特征维度低，比如 CIFAR10，ImageNet 在 ResNet 上的特征。所以我们可以定义一个 loss function 像这样：

一方面我最大化 Rank(St) 另一方面我也想最大化 Rank(Sw)。

这个地方就是我们的第二层贡献，基于 condition 1 的性质提出了一个 Loss Function 使得 Loss function的全局最优（其实还有局部最优）能够达到condition 1. 这里请注意（敲黑板），这不是唯一（坑1）的一个loss function能达到 condition 1. 我们之所以这么设计是因为通过这么设计，我们能和一大类方法 Linear Discriminant Analysis，Manifold Learning，还有我们的 COLES 建立非常紧密的联系。

从而对于这类方法提供了一个新的优化观点，这类方法只是我们这个框架的一种 approximation（当然是不太好的那种）。这里还有一个坑，这里其实提出了一个比较欠打的 Rank Difference 问题（坑2），这个问题我仔细想了一下其实不是简单的替换两个 surrogate function 那么简单。当然我最优化比较弱鸡，如果有知道怎么更好求解的，欢迎赐教。

尽管有了这么一个框架，但是是个人都知道 Rank 是个 NP-hard 的算子所以我们需要把公式 3 松弛一下。Rank 的一个比较常见的替代函数是 LogDet，因此我们可以把公式 3 变成：

事实上如果我们用 Trace 来松弛，我们就得到了我们自己的 COLES （NeurIPS2021）和 trace difference 形式的 LDA。实际上 trace difference 和 trace ratio 是有紧密关系的，当年贾杨清还有篇文章是关于这个。不过 trace difference 效果嘛，和比 logdet difference 要差了一大截。

所以其实 trace difference 及其相关的很多方法比如 linear discriminant analysis，COLES 还有 Manifold Learning（最直接的就是 Locality Preserving Projection）。所以这是本文第一个和现有方法的 connection（因为还有一个）。

现有的方法实际上也是在优化公式 3，只不过用的 approximation 太粗糙了。因此如果公式 3 是一个更本质的目标的话，我们从最优化的角度使用更加好的拟合方式理论上能得到进一步的提高。大家看到这觉得故事讲完了吧。不不不，刚刚讲到一半呢。接下来我们要从 Machine Learning on Riemman Geometry 的角度来解释公式 5 的意义（公式 5 在几何上有个非常有趣的解释）。

首先让我们来 reformulate 两个基于 trace 的两个方法：

我们 reformulate 的目的是为了和公式 3 一致，变成一个 maximizing 两个不同矩阵度量的距离（坑3）。我们先简单说一下公式 5 和两个很常见的矩阵（Riemannian metric）之间距离的关系：the Affine-invariant Riemannian metric（AIRM），and Jessen-Bregman LogDet Divergence（JBLD）.

首先是 AIRM，从 prop.5 可以看到我们的 loss 其实 bounded 在 AIRM 和一个常系数大小的 AIRM 之间。

然后是 JBLD，我们有

所有的证明都草鸡简单就是最基本最基本的变换。所以能看到 JBLD 和我们的关系。当时老板嘴欠的问了一句，如果按你这个分析万一有人怼：如果是这样那我直接用 JBLD 或者 AIRM 不就好了么，为毛要用你得公式 5 呢？

这个回答其实也异常的简单，首先我们来看看公式 12. 公式 12 需要显式的计算一个矩阵函数，因为又有 -1/2 又有 log 所以大概率是要特征值分解了。大家都懂特征值分解的感人效率把，特别是当 dimension 比较大的情况下。

相对而言 logdet 有很多近似方法是不需要特征值分解的，比如可以展开成 trace 的高阶形式。然后是 JBLD，大家可以看到 JBLD 需要计算 St,Sw,Sb. 有人会说，这不是挺好么，也不需要特征值分解就可以搞定。

问题来了，我们不一定有 Sb。因为 Sw 和 Sb 严格来说只有有标签数据才能生成对应的协方差矩阵。但是我们考虑更 generalized 的情况，我们没有标签，只有一个 adjacent matrix（也就是 manifold learning 或者 graph embedding）的情况。Sw 依然是可以计算的因为 adjacent matrix 保留了彼此之间的关系（有噪声）。所以就如同公式 1 里面我们定义的那样使用 adjacent matrix 替换掉用类标签构造的关系矩阵即可。

但是 Sb 就非常难了，因为 adjacent matrix 一般是个联通图，这就意味着你在这上面找类中心的话是一个很不靠谱的事情（虽然也不是不能找）。但是在我们的方法里面，是不需要考虑 Sb 的。请注意 AIRM 和 JBLD 分别度量不同的两个矩阵距离：AIRM(St,Sw) 和 JBLD(Sw,Sb). 其实这个地方有一个 implicit 的性质，能看出来的同志自己琢磨。

贴个主要结果，因为我本身是做图的。所以我更愿意从 graph embedding 的角度来看我们的这个方法，毕竟叫 Generalized Laplacian Eigenmaps 嘛。其他的不说比 COLES 高了一大截......

另外值得注意的事 COLES 会导致 dimension Collapse（这个可以参考 contrastive learning 的分析），但是 GLEN 不会哦。COLES 基本上只能训练线性的 NN 对 MLP 非常不友好。但是 GLEN 对 NN 是非常友好。这就是为啥 GLEN-GCN 性能能暴涨的主要原因。

可能还有些盆友觉得，这个东西和马老板他们那套 learning diverse and discriminative representation 非常像。就我个人认为，我们的这个观点比较符合 ML 的人的 insight（因为我真的不懂信息论那套东西）。并且从几个比较不同的角度（loss function 设计，最优化，几何）启发新的方法提出。

learning diverse and discriminative representation 里面的方法在本文的框架体系下就是一个 GLEN-QDA（当然细节可能有区别）。因为 QDA 的假设就是每一个类有自己的协方差矩阵而不是 LDA 的大家 Share 协方差矩阵。但是缺点也显而易见，样本不够多的情况 QDA 很可能是一个费力不太好的模型。

更多阅读