论文阅读“Deep Kernel Learning for Clustering”

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$ 进行初始化使得后续的更新提升了谱聚类的性能。整体思路值得借鉴。

最后编辑于：2021.07.07 22:57:23

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 221,576评论 6赞 515
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 94,515评论 3赞 399
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 168,017评论 0赞 360
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 59,626评论 1赞 296
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 68,625评论 6赞 397
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 52,255评论 1赞 308
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,825评论 3赞 421
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,729评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 46,271评论 1赞 320
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,363评论 3赞 340
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,498评论 1赞 352
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 36,183评论 5赞 350
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,867评论 3赞 333
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,338评论 0赞 24
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,458评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,906评论 3赞 376
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,507评论 2赞 359