集合的机器学习

在机器学习中，我们通常与输入对(x，y)打交道，我们试图找出x和y是如何相互依赖的。为此，我们收集了许多这样的对，并希望如果a)我们有足够的数据，b)我们的模型有足够的表达能力来逼近这种依赖，c)我们得到了正确的超参数，x和y都只是标量(或向量\(\mathbf{x}，\mathbf{y}\))，在最简单的情况下，x和y都只是标量值(或向量\(\mathbf{x}，\mathbf{y}\))；这里的度量是实向量\(\mathbf{x}\in\mathcal{X}\)，其中输入空间\(\mathcal{X}=\mathbb{R}^d\)通常是欧几里得的，物种是标签\(\mathbf{y}\in\mathcal{Y}\)(通常是整数或一热向量)，但\(\mathbf{x}\)和\(。

我们依赖的一个主要假设是(x，y)点对是独立且同分布的(I.I.D.)。随机变量。让我们把这个解开，从最后开始，

随机变量：存在某种随机生成过程，从该过程中随机抽取变量，

独立：生成过程没有生成样本的记忆，因此任何生成的样本都不会更改将来生成的样本的分布。

\(\mathbf{x}、\mathbf{y}\)中的任何结构都会引入约束，算法对特定问题的成功应用在很大程度上取决于此算法是否将相关约束考虑在内。与图像相关的问题中的一个常见约束是平移等差1-算法的输出应随图像应用的任何平移而移动(您可以在这篇优秀的博客文章中阅读有关方差的更多信息)。在与自然语言相关的问题中，典型的约束是因果关系：位于。但它不能依赖于任何未来的令牌2。

在上述示例中，点之间的依赖关系(例如，NLP中的自回归依赖关系)从上下文中是清楚的。然而，如果数据点不是向量、矩阵或向量序列，而是向量的集合，则这些依赖关系变得不那么清楚。特别地，输入集中的元素类似于数据集中的元素(即，缺乏顺序)，但关键区别在于它们不是独立的，因此破坏了I.I.D.。假设。由于ML模型输入或输出中的这种特殊结构导致了一类集合学习问题，这些问题最近在机器学习界得到了相当大的关注。我认为深入研究集合的机器学习是有用的。在下面，我们将考虑集合到向量、向量到集合和集合到集合的问题，并提供JAX和haiku的简单算法的实现。

在开始之前，我们先介绍一些符号，设\(\mathbf{x}\in\mathbb{R}^d\)为输入向量，\(\mathbf{y}\in\mathbb{R}^k\)为输出向量，设\(X={\mathbf{x}_i\}{i=1}^M\)和\(Y={\mathbf{y}_j\}。从现在开始，\(\mathbf{x}\)和\(\mathbf{y}\)可以住在同一空间，只是不同集合的元素。我还将使用\(\mathcal{L}(X，Y)\)作为在两个集合上运算的损失函数，以及\(l(\mathbf{x}，\mathbf{y。

这可能是最简单的集合学习问题，因为它只需要排列不变性。如果\(\forall\pi\)：\(F(X)=f(\pi X)\)，则函数\(f\)对于排列\(\pi\)不变。排列不变性在机器学习中一直是已知的，因为我们使用的损失函数几乎从不依赖于数据集或小批量中元素的排序。这不是因为缺乏顺序：要创建小批量，我们需要堆叠。这将迷你批次中的每个元素与其迷你批次索引配对，从而隐式创建订单。丢失函数往往会丢弃有关订单的信息，通常是通过取数据示例的平均值。我们可以按照类似的逻辑创建置换不变函数。

小批量中的示例是独立处理的(这反映了它们的I.I.D.。如果小批次中的每个条目包含不止一个数据点(图像中的许多像素、点云中的点、语言语句中的标记)，那么将这些点展平成向量并将其馈送到MLP或CNN中会导致不同的参数被用于处理不同的数据点，因此隐式地使用顺序；将这些点馈送到RNN中重复使用参数，但是引入了对顺序的显式依赖。

该问题的直接解决方案是以我们处理小批量中的示例的相同方式来处理单个示例中的点：独立地处理它们。在Zaheer等人的“Deep Sets”(“Deep Sets”，NeurIPS 2017)中探索了该方法，随后进行了诸如最大或平均合并等排列不变的合并操作，并且被证明是通用集函数近似器4。

类DeepSet(hk.Module)：def__init__(self，编码器，解码器)：Super().__init__()sel._encode=编码器自身._decder=解码器def__call__(self，x)："；"；"；计算DeepSet嵌入。参数：x：形状张量[Batch_size，n_elems，n_dim]。"；"；"；返回self._decder(self._encode(X).means(1))。

虽然有更新的方法具有更好的经验性能，但它们都来自深集框架5。另一个导致集合到向量问题非常容易的因素是，集合操作自然地与可变大小的集合一起工作-我们不需要额外做任何事情来处理可变基数的集合。以下两个问题不是这种情况，我们必须显式地考虑集合的大小。

在向量到集合中，任务是从一些(通常是向量值的)条件生成一组实向量。

现有的大多数方法都集中在生成固定大小或至少已知大小的有序序列而不是无序集合，这允许使用MCP6和RNNS7分别预测固定长度和可变长度的集合，但代价是必须从数据中学习排列等变，学习排列等变可以通过数据扩充来诱导。很容易生成不同的排列，但与真正的排列等变方法8相比，通常会降低性能和/或延长训练时间。

Def set_mlp(条件化，解码器，n_element)："；"；"；预测集合。参数：条件：形状张量[BATCH_SIZE，n_DIM]。解码器：可调用的，例如MLP。N_Elements：int。"；"；"；z=解码器(条件)BATCH_SIZE=Conditioning.Shape[0]#我们在这里所能做的就是重塑！Return z.reshape(Batch_Size，n_Elements，-1)def set_rnn(Conditional，state，rnn，n_element)："；"；"；预测集合。参数：条件：形状张量[BATCH_SIZE，n_DIM]。状态：RNN的初始状态。RNN：RNN核心。N_Elements：int。"；"；"；zs=[]for_in range(N_Element)：z，state=rnn(条件，状态)zs.append(z[：，NONE])#添加轴返回jnp.contatenate(zs，1)。

学习基于某种条件来生成集合通常需要对照条件对该集合进行评分。如果我们有基本事实集可用，我们可以将生成的集合与相同条件下的基本事实集进行比较。这可以采取监督学习的形式(想想检测图像中的对象，其中我们需要生成一组边界框)或无监督学习(比如自动编码点云)。由于我们通常不能保证生成的集合将遵循任何顺序(为什么要这样做呢？)，所以我们必须采用无监督学习的形式(考虑到检测图像中的对象，其中我们需要生成一组边界框)。由于我们通常不能保证生成的集合将遵循任何顺序(为什么要这样做？)

我们可以在两个集合9之间找到最佳匹配，这归结为找到使计算损失最小的集合之一的排列\(\pi\)，即：\(\pi^\star=\arg\min_\pi\mathcal{L}(\pi X，Y)\)，其中\(\mathcal{L}(\pi X，Y)=\sum_i l(\mathbf{x}_{\pi(I)}，\。这可以精确地使用立方匈牙利匹配算法来完成，或者近似地使用例如基于最优传输或消息传递的算法来完成。

我们可以找到匹配损失的下限，而不是找到匹配的损失。这里常用的选择是倒角损失10，它计算\(\sum_{x\in X}\min_{y\in Y}l(x，y)+\sum_{y\in Y}\min_{x\in X}l(x，y)\)。对于一个集合中的每个元素，它都会找到另一个集合中导致最低成对损失的元素。这种损失不适用于多集，因为元素可以重复。

如果我们没有每个条件的基本事实(我们只有集合)，或者如果我们对于每个条件有许多可能的集合(例如，几个标签之一的一组可能的集合)，我们可以通过匹配分布来学习，例如在GAN设置中。如果我们采用这种方法，我们实际上有两个问题：生成器的向量到集合和鉴别器的集合到向量的问题。幸运的是，我们知道如何用置换不变神经网络来解决集合到向量的问题，不久我将描述一些置换等变的生成方法，这正是我们最近在Stelzner等人的“生成性对抗性集合转换器”，ICML 2020面向对象学习研讨会中探索的。

巧合的是，有时我们不得不处理模型内部的一组潜在变量。例如，在Add-Infer-Repeat(AIR、纸张、BLOG)中，一组以对象为中心的潜变量被用来渲染图像，但我们不需要担心这些变量的排列，因为渲染过程是排列不变的，任何损失都会应用于最终图像，并以排列不变的方式传递到潜在变量上！

直到最近，还没有一种公认的方法能够以排列等变的方式预测可变大小的集合，为了完备性，请注意函数g与排列\(\pi\)是等变的，如果\(对于所有\pi\)：\(\pi g(X)=g(\pi X)\)，则函数g与排列\(\pi\)是等变的。张等人的《Deep Set Forecast Networks》，NeurIPS 2019用的是大家熟知的(不过还是挺酷的！)。观察到置换不变函数的梯度(如深度集嵌入)与输入集11的梯度是置换等变的，他们介绍的模型DSPN使用一个固定的初始集，该初始集通过学习损失函数上的梯度下降嵌套循环进行调整。该损失函数将当前生成的集与条件进行比较，告诉我们当前集与条件匹配的情况。DSPN在点云生成(但仅限于MNIST)上取得了相当好的结果，并显示了用于目标检测的概念验证结果。

类DeepSetPredictionNetwork(hk.Module)：def__init__(self，set_encode，max_n_points，n_dim，n_update=5，step_size=1.，repr_oss_func)："；"；"；构建模块。Args：set_encode：集合的编码器，例如DeepSet。MAX_n_POINTS：整数。N_dim：集合元素的维数。N_UPDATES：应用于初始集的渐变更新次数。STEP_SIZE：内部梯度下降循环的学习速率。REPR_LOSS_FUNC：用于比较生成集合的嵌入和条件的嵌入的损失函数，例如平方误差。"；"；"；"；"；"；"；"；"；"；"；"；"；"；"；"；"；"；"；"；"；"；"；"；__init__().__init_()sel._set_encode=set_encode sel._max_n_points=max_n_point self._n_dim=n_dim self._n_update=n_update self.。Def repr_loses(input，target)：h=self._set_encode(*input)#我们取点数的平均值。Return repr_oss_func(h，target).means(1).sum()sel._repr_oss_grad=hk.grad(Repr_Oss)def__call__(self，z)：#创建初始集合和存在变量current_set=hk.get_Parameter('；init_set'；，Shape=(sel._max_n_point，sel._n_dim)，init=hk.initializers.RandomUniform(0，1))current_pres=self._clip_pres(hk.get_parameter('；init_pres'；，Shape=(sel._max_n_points，1)，init=hk.initializers.Constant(.5)，)#dspn返回起始集合/pres并明显地将损失置于其上。All_sets，all_pres=[current_set]，[current_pres]for_in range(self._n_update)：set_grad，pres_grad=self._repr_oss_grad((current_set，current_pres)，z)current_set=current_set-sel._step_size*set_grad current_pres=current_pres-self._step_size*pres_grad#我们需要确保存在。Current_pres=sel._lip_pres(Current_Pres)all_sets.append(Current_Set)all_pres.append(Current_Pres)返回all_sets，all_pres。

虽然这是一个很酷的想法，但是dspn学习到的梯度迭代是一个流场(见图1)，它必然需要多次迭代才能达到f。

初始集可以是高维的(在DSPN中，它必须与输出集的维数相同)，从而产生更多自由度。

变换器层可以对不同维度的集合进行操作，并且不必将其投影到层之间的输出维度。这看起来可能微不足道，但它放松了流场约束，并且在实践中创建了可以保持某些额外状态的转换，类似于RNN。

DSPN仅通过其DeepSet编码器中的池化操作捕获各个点之间的依赖关系。转换器都是关于关系推理的，可以直接利用点之间的相互依赖关系来生成最终集。

我们在最近的两篇论文中探讨了这个想法；这两篇论文都发表在ICML 2020面向对象学习研讨会上，

Kosiorek，Kim和Rezende，“使用变压器的条件集生成”，其中我们介绍了变压器集预测网络(TSPN)。TSPN使用MLP从条件中预测所需的点数，从基本分布中采样所需的点数，并使用变压器对其进行变换，有关概述，请参见图2。

Stelzner、Kersting和Kosiorek在“生成性对抗性集合转换器”一书中介绍了GAST：一个类似的想法，即使用Transormer对基础分布中的多个点进行有条件的转换(基于全局噪声矢量)。然后，我们使用集合转换器来区分生成的集合和实数集合。

至少另外两个小组同时探索了相同的想法12.虽然细节不同，但主要的发现是，经过几层关注的初始集合(随机抽样或确定并学习)会导致最先进的集合生成。总体结构如下：

我们采用确定性或随机抽样的查询集，并关注键-值对。

我们应用上述之一的排列不变损失函数。匈牙利的匹配似乎给出了最好的结果。

Carion等人的DETR模型的结果尤其令人印象深刻。虽然它仍然需要相当多的工程，但这种纯粹的集合预测方法在CoCo！上实现了大规模目标检测的最先进技术！Locatello等人。研究表明，所需的特定注意力形式可能取决于任务；在他们的实验中，他们在查询轴(而不是键轴)上归一化注意力，这导致了查询之间的竞争，并为非监督对象分割提供了优越的结果(图3)。

虽然上述方法确实适用于生成集合，但它们没有利用与建模集合有关的众所周知的统计学领域：点过程！点过程将集合大小\(k\in\mathbb{N}_+)作为随机变量，并将其与集合成员\(X\in\数学{X}^k\)联合建模，从而对联合密度\(p(X，k))进行建模，这与前面描述的一些方法形成了鲜明的对比：点过程！点过程将集合大小(k\in\mathbb{N}_+)视为随机变量，并将其与集合成员\(X\in{X}^k\)联合建模，从而对联合密度\(p(X，k))进行建模；例如，DSPN使用启发式算法来确定集合大小，这取决于它与哪个损失函数一起使用(有关详细信息，请参阅我们的TSPN论文)。在这方面，我们的TSPN也好不到哪里去，并将确定集合大小作为一个分类问题-这在实践中工作得很好，但它不能推广到训练中没有看到的集合大小。虽然点过程的详细描述需要太多篇幅才能放在本博客中，但我想强调一个概念，这是我从一个TSPN文件中了解到的，它在实践中工作得很好，但它不能推广到训练中没有看到的集合大小。虽然在本博客中详细描述点过程会占用太多篇幅，但我想强调一个概念，这是我从一个。称为“基于模型的多实例学习”。

设\(f_k(X)=f_k(x_1，...，x_i，...，x_k)\)是定义在\(k\)元素集上的概率密度函数，并设这个密度与集合中元素的排列顺序不变，即：\(F(X)=f(\pi X)\)，我们可以用这个密度来比较基数相同的集合之间的概率大小，即：\(f_k(X)=f_k(x_1，…，x_i，…，x_k)\)，并且假设这个密度不随集合中元素的顺序而变化，即\(f(X)=f(\pi X)\)，从而可以用这个密度来比较基数相同的集合之间的概率大小。它们的可能性有多高)，但是，即使基数集(K)和(M)有两个这样的函数，我们也不能用它们来比较那些不同基数的集合，这是为什么呢？那么，比较两个元素的集合和三个元素的集合有点像比较平方米m2和立方米m3，或者像比较苹果和橙子一样，不是我们不能比较不同基数的集合，而是我们必须先把它们放到一个集合中来比较，而不是说我们不能比较不同基数的集合，而是我们必须先把它们放到一起来比较，就像比较平方米m2和立方米m3，或者比较苹果和橙子一样，不是不能比较不同基数的集合，而是我们必须先把它们归入。我们必须考虑a)每个集合的可能排列的数目，以及b)单位体积(在度量空间的情况下，比较m(^2)和m(^3)，我们需要计算出一个米m(^1)有多大)，这导致一个大小为(K)的集合的概率密度函数的定义如下，

[P(x_1，...，x_k\})=p(X，k)=p_c(K)k！u^k f_k(x_1，...，x_k)\，，\]其中\(p_c(K)\)是集合大小的概率质量函数，\(k！\)表示集合元素\(\mathbf{x}_i\)的所有可能排列，\(U\in\mathbb{R}_+\)是用标量值表示的单位体积，\(f_k\)是大小k的集合的置换不变密度，有趣的是，上述集合生成论文在定义它们在集合上的可能性时都没有考虑点过程理论，我很想知道它是否像Vu等人那样改进了结果。建议。

给出如何解决集合到矢量和矢量到集合问题的知识，如何解决集合到集合问题应该是非常清楚的：我们可以将集合编码成矢量，然后使用上面的矢量到集合方法之一将该矢量解码成集合。虽然这种方法是正确的，但这种方法迫使我们使用单个矢量形状的瓶颈。也许更好的选择是将集合编码到中间集合，可能基数较小，并且在以下情况下使用较小的集合作为条件。我只想提一下，我们在Lee等人的“Set Transformer”，ICML 2019中探索了一些这样的问题，并鼓励好奇的读者看看这篇论文。

感谢您走到这一步！我们已经通过研究集合到向量、向量到集合和集合到集合的问题以及解决它们的一些方法，涵盖了面向集合的机器学习的一些基础知识。我发现ML的这一领域非常有趣，因为它的种类繁多。

.