论文阅读“Deep Kernel Learning for Cl

2021-07-07 本文已影响0人掉了西红柿皮_Kee

Wu C, Khan Z, Ioannidis S, et al. Deep Kernel Learning for Clustering[C]//Proceedings of the 2020 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2020: 640-648.

摘要翻译

论文提出了一种深度学习方法来发现核（kernels），用于识别样本数据上的类簇。所提出的神经网络产生样本嵌入（embedding），这些嵌入是由谱聚类激发的，并且至少与谱聚类一样具有表现力。我们的训练目标基于希尔伯特·施密特独立标准（Hilbert Schmidt Independence Criterion），可以通过 Stiefel 流形上的梯度适应进行优化，从而显著加速依赖于特征分解（eigen-decompositions）的谱方法。最后，训练好的嵌入表示可以直接应用于样本外数据。通过实验表明，提出的方法在广泛的真实和合成数据集上优于几种最先进的深度聚类方法以及传统的聚类方法如 k -means和 spectral clustering。

引入：聚类算法基于一些预定义的相似性概念将相似的样本组合在一起。表示这种相似性的一种方法是通过核方法。然而，一个适当的“核”的选择是依赖于数据的；因此，核的设计过程通常是一门需要对数据有密切了解的艺术。一个常见的选择是：只需使用在各种条件下性能良好的通用内核，如 polynomial kernels 或 Gaussian kernels。

Intro

论文提出了KernelNet(KNet)，一种直接从观测数据中学习核（kernels）和诱导聚类的方法。KNet通过将神经网络表示与高斯核相结合来训练深度核。给定 $N$ 个样本表示 $\left\{x_i\in {R^d}\right\}_{i=1}^N$ ，我们要学习一个核-- $\tilde{k}(·,·)$ 如下所示：

$ψ_{θ(·)}$ 是由 $\theta$ 参数化的神经网络嵌入函数。 $d_i,d_j$ 是正则化常数。直观地解释是，将神经网络 (NN) 参数化结合到高斯内核中，能够学习一个灵活的用于聚类的深度内核，专门针对给定的数据集定制。

模型使用一个基于希尔伯特·施密特独立标准（HSIC）的谱聚类（ spectral clustering）目标来训练深度核。这种训练可以解释为同时学习非线性变换 $ψ$ （核学习）及其谱嵌入 $U$ （对应于所选特征向量生成的降维后的矩阵）。整个模型通过对训练过程进行适当和直观的初始化，确保了提出的聚类方法至少与谱聚类一样强大。如谱聚类一样，模型学习的核和诱导聚类在非凸聚类上表现较好。
同时，直接从数据集学习到的非线性变换 $ψ$ 允许模型轻松地处理样本外数据。给定一个新的未观察到的样本 $x_u∈R^d$ ，可以通过首先计算其image（我觉得这里需要翻译成映射） $ψ_θ(x_u)$ 来很容易地识别其聚类标签，从而将其嵌入到与（已经集群的）现有数据集相同的空间中。这与谱聚类形成对比，谱聚类则需要在形成的 $N+1$ 个样本组合数据集上从头重新执行算法。
算法的上述特性如下图所示： Fig 1 1(a): 具有非凸螺旋团簇的N=30,000个样本的数据集如图。
1(b): 将 $σ = 0.3$ 的高斯核直接应用于这些样本会导致核矩阵的信息量非常低。
1(c): 只在1%的样本上训练和核嵌入 $ψ_θ(·)$ ，并将其应用到整个数据集，学习对应的嵌入表示，形成了近似凸的、并且线性可分离的簇。
1(d): 更重要的是，相应的学习核 $\tilde{k}(·,·)$ 产生了一个信息丰富的核矩阵，清晰地显示出一个块对角结构。
论文提出了一种通过最大化基于HSCI的目标来训练内核的算法，以及选择一个好的参数初始化。提出的 KNet 可以被视为在（1）训练内核和（2）发现其谱嵌入，之间交替进行。

related work 记录

关于autoencoder的深度聚类方法，进行了举例介绍。最后指出：不同于以上方法，在KNet中使用基于HSIC的目标（动机来源：谱聚类）。在实验中，这使得KNet更好地适合学习非凸数据聚类。
介绍自己工作的灵感来源。（本文的工作最接近SpectralNet，一种将基于神经网络的谱聚类方法：首先使用 Siamese network学习一个相似度矩阵，然后保持这个相似度不变，通过优化一个谱聚类目标来学习谱嵌入。）以及本文工作的不同：相比之下，KNet使用迭代提升的方式共同学习核相似矩阵和谱嵌入。（这也是KNet性能较高的原因）
将模型方法也与kernels的相关方法进行联系。（与KNet最相似的是“Dimensionality reduction for spectral clustering”--使用HSIC共同发现数据存在的子空间及其谱嵌入，并使用得到的谱嵌入用于聚类）

Hilbert-Schmidt Independence Criterion

Hilbert Schmidt Independency Criterion (HSIC) 是两个随机变量之间的统计相关性度量。与互信息 (MI) 一样，它通过比较（两个随机变量的联合分布）与（其边缘分布的乘积）来衡量相关性。然而，与 MI 相比，HSIC 更容易凭经验计算，因为它不需要直接估计联合分布。
考虑样本量为 $N$ 的独立同分布样本, $\left\{(x_i,y_i)\right\}_{i=1}^N$ 来自一个联合分布（注：我认为这里考虑的是样本特征 $x$ 和样本的标签 $y$ 之间的联合分布（依赖关系））。设 $X ∈ R^{N×d}$ 和 $Y ∈ R^{N×c}$ 是包含每个样本的相应矩阵。
令 $k_X：R^d×R^d→R$ 是任意的特征核；本方法中使用的是高斯核：

Gaussian kernel
令

k_Y：R^c×R^c→R

是另一个特征核---线性核（注：使用one-hot向量，相同的标签向量之间相乘为1；不同的标签向量之间正交，相乘为0）：

linear kernel
并且定义

K_X

和

K_Y

为核矩阵，

K_{X_{i,j}}=k_X(x_i,x_j)

，

K_{Y_{i,j}}=k_Y(y_i,y_j)

。正则化的高斯核矩阵

{\tilde{K}_X}\in R^{N×N}

如下计算：

其中

D

为度矩阵：

由此，

X

和

Y

之间的 HSIC 通过经验估计:

直观地，HSIC通过经验测量了两个随机变量的样本之间的依赖性。尽管 HSIC 可以更普遍地定义为任意特征内核，但这种特殊选择与谱聚类（以及来自谱聚类的动机）有直接关系。
对于给定的

X

，考虑如下的优化目标：

target
最优解

U_0∈R^{N×c}

对应到“target”正好是获得的谱嵌入。实际上，

U_0

包括归一化相似度矩阵的top c个特征向量，由

给定。

问题形式化

因为涉及到谱聚类，所以模型对非凸类型的数据集也很友好。模型的设计目标是通过首先将样本嵌入到类簇变得凸的空间（得到嵌入表示）来对样本进行聚类（如使用k-means）。作者希望由神经网络学习的嵌入表示至少像谱聚类一样具有表现力，即通过谱聚类可分离的数据也可以通所提出的模型进行分离。此外，这种学习到的嵌入表示应该泛化到样本外的数据，从而使模型能够在原始数据集之外聚类新的样本，而不需要重新训练模型。

Learning the Embedding and a Deep Kernel

问题需要将含有 $N$ 个样本的数据集 $X \in R^{N×d}$ 聚类到 $c$ 个类簇中。设 $ψ：R^{d}×R^m→R^{d~'}$ 是将一个样本嵌入到 $R^{d~'}$ ，由 $θ∈R^m$ 参数化的DNN进行映射学习；我们用 $ψ_θ(x)$ 表示参数 $θ$ 下 $x∈R^d$ 的映射表示。用 $Ψ：R^{N×d}×R^m→R^{N×d~'}$ 表示嵌入由 $ψ$ 映射的整个数据集，并使用 $Ψ_θ(X)$ 表示 $X$ 的嵌入映射。设 $U_0∈R^{N×c}$ 是通过谱聚类得到的关于 $X$ 的谱嵌入。我们可以通过以下优化来训练 $ψ$ 来诱导与 $U_0$ 相似的行为：

op target

由于HSIC是一种变量之间的依赖性度量，通过训练 $θ$ 使 $Ψ_θ(X)$ 最大限度地依赖于 $U_0$ ，使得 $Ψ$ 成为谱嵌入的替代品，与谱嵌入（embedding）具有相似的特性。

然而，通过上式（op target）学习的代理 $Ψ$ 受到 $U_0$ 的限制，因此它只能像 $U_0$ 一样具有鉴别性。为了解决这个问题，不同于（op target），联合发现 $Ψ$ 和一个耦合的谱嵌入 $U$ 。

op target-1 为了直观地了解如何由（op target）得到（op target-1），即（op target-1）如何推广到（op target）。如果嵌入

Ψ

固定为恒等映射（即，对于

Ψ_θ(X) ≡ X

），通过等式（target），仅针对

U

进行优化会产生谱嵌入

U_0

。

Ψ

和

U

的联合优化能够进一步改进

U_0

以及耦合的

Ψ

。

Kernel Learning

关于（op target-1）的优化可以解释为内核学习。通过学习 $ψ$ ，我们发现了如下的正则化的核：

Out-of-Sample Data

学习到的嵌入 $Ψ$ 可以很容易地应用于样本外数据。在数据集 $X$ 上训练 $Ψ$ ，给定一个新的数据集 $Y \in R^{N×d~'}$ ，我们可以用如下的步骤对其进行有效聚类。

首先，使用预先训练好的 $Ψ$ 将 $Y$ 中的每个样本 $y_i$ 映射其对应的映射，生成 $Ψ_θ(Y)$ ：这有效地将 $Y$ 嵌入到与 $Ψ_θ(X)$ 相同的空间中。
聚类可以通过k-means等进行有效的重新计算；或通过将 $ψ_θ(y_i)$ 映射到最近的现有类簇中。

与谱聚类相比，这么做避免了重新计算整个数据集 $(X;Y)$ 的联合嵌入。特别地，给定原始数据集 $X$ ，可以通过在 $X$ 的一个小子集上优化（op target-1）训练嵌入 $Ψ$ ，以达到加速计算的目的。

Convex Cluster Images

待优化（op target-1）中(4.8a)的第一个项鼓励 $Ψ$ 形成凸簇。

在该算法上连续几次迭代可以得出如下的情况：

使得数据逐渐线性可分。

KNet Algorithm

算法通过迭代式交替优化 $\tilde{\theta}=(\theta,\theta')$ 和 $U$ 。

Initialization

我们将 $U$ 初始化为 $U_0$ ，通过 $X$ 的标准化相似度矩阵 $L$ 的top c特征向量计算得出。初始化 $θ$ ，使 $Ψ$ 成为恒等映射（ identity map）; 这是通过SGD预训练来 $(\theta,\theta')$ 实现：

Updating $\tilde{\theta}$

对于k≥1，其中

F

是优化目标（op target-1）中（4.8a）。

To simplify this computation, instead we hold both $U$ and $D$ fixed, and update $\tilde{\theta}$ via one epoch of SGA over (4.8a). At the conclusion of one epoch, we update the Gaussian kernel $K_X$ and the corresponding degree matrix $D$ via Eq. (3.3).

Updating U (via Eigendecomposition)

算法实现

第二种更新U的方式没太看懂，请自行移步论文查看

该算法使用巧妙的将深度学习和核学习结合起来，有漂亮的公式和数学推导。使用交替更新的方式对算法进行优化，既使用了重建约束的方式保证了学习到的谱嵌入的有效性，也使用 $U_0$ 进行初始化使得后续的更新提升了谱聚类的性能。整体思路值得借鉴。