经由对偶分解评估损失函数或损失函数的梯度的系统和方法

技术领域

本公开总地涉及评估损失函数或损失函数的梯度。更具体地，本公开涉及经由损失函数的对偶分解针对大输出空间的问题来高效地评估损失函数和/或其梯度的计算机系统和方法。

背景技术

大输出空间在当今的若干机器学习问题中是无处不在的。这种机器学习问题可以包括例如具有许多类别的极端多类或多标签分类问题、具有大词汇量的语言建模、或具有大量成对距离约束的度量学习。在所有这种问题中，训练模型中的主要瓶颈是所述对损失函数及其梯度的评估。用于这种问题的损失函数通常需要列举出所有可能的输出，并且在用于评估的输出数目方面可能需要线性运行时间。这可以是迭代方法(诸如用于训练所述模型的梯度下降)中的显著瓶颈，因为每个步骤都可能需要大量操作。

发明内容

本公开的实施例的方面和优点将在以下描述中部分地阐述，或可以根据所述描述来获知，或可以通过实践实施例而获知。

本公开的一个示例方面涉及一种用于评估损失函数或损失函数的梯度的计算机实施的方法。该方法包括：通过包括一个或多个计算设备的计算系统将权重矩阵分割成多个块，所述权重矩阵对应于评分函数。该方法包括：通过所述计算系统为所述多个块中的每一个标识第一标签集合，该第一标签集合与大于第一阈值的分数相关联。该方法包括：通过所述计算系统至少部分地基于第一标签集合来为所述多个块中的每一个构建评分向量的稀疏近似。该方法包括：通过所述计算系统为所述多个块中的每一个的评分向量的每个稀疏近似确定校正值。该方法包括：通过所述计算系统，通过至少部分地基于所述多个块中的每一个的评分向量的稀疏近似和与所述评分向量的稀疏近似相关联的校正值而评估分解的损失函数或所述分解的损失函数的梯度，来确定与所述评分函数相关联的损失或损失的梯度的近似。

所述计算系统可以为多个训练示例中的每一个确定所述损失或损失的梯度的近似。

所述计算系统可以至少部分地基于与评分函数相关联的损失或损失的梯度的所确定的近似来修改所述权重矩阵或评分函数的一个或多个参数。

为多个块中的每一个标识第一标签集合可以包括：通过所述计算系统查询相应地与权重矩阵的多个块相关联的多个最大内积搜索数据结构中的每一个。

为多个块中的每一个构建评分向量的稀疏近似可以包括：通过所述计算系统针对多个块中的每一个设置用于多个标签中的每一个的相应近似分数，该多个标签中的每一个既不包括在块的第一标签集合中也不包括在等于零的正标签中。

为多个块中的每一个构建评分向量的稀疏近似可以包括：通过所述计算系统针对多个块中的每一个设置多个标签中的每一个的相应近似分数，该多个标签中的每一个既不包括在块的第一标签集合中，也不包括在等于根据最大内部搜索乘积搜索查询确定的真正分数的正标签中。

为多个块中的每一个的评分向量的每个稀疏近似确定校正值可以包括：通过所述计算系统至少部分地基于多个块中的每一个的第一标签集合来标识第二标签集合，该第二标签集合与大于第二阈值的梯度相关联；通过所述计算系统确定跨越多个块的第二标签集合中的每个标签的平均近似分数；通过所述计算系统为在多个块中的每一个的第二标签集合中的每个标签确定近似分数；通过所述计算系统为在第二标签集合中的标签与多个块中的块的每个组合确定在用于多个块中的每一个的平均近似分数与近似分数之间的差；以及通过计算系统至少部分地基于针对第二标签集合中的标签与多个块中的块的每个组合的所确定的差，来更新用于多个块中的每一个的评分向量的每个稀疏近似的校正值。

确定与评分函数相关联的损失或损失的梯度的近似可以包括：通过计算系统跨越多个块使用于这种块的相应近似评分向量加上每个块的校正值向量所评估的每个块的相应损失的平均值最小化，以使得跨越多个块的校正值向量的总和等于零。

分解的损失函数可以包括多个部分，每个部分同与多个块中的每一个的评分向量的相应稀疏近似相关联的损失相对应。

计算系统可以对损失函数执行平滑技术，以构建具有连续梯度的替代损失函数；以及至少部分地基于所述替代损失函数来确定分解的损失函数。

所述多个块中的每一个可以包括权重矩阵的一个或多个列。

查询相应地与权重矩阵的多个块相关联的多个最大内积搜索数据结构中的每一个可以包括：通过计算系统获得与权重矩阵和评分函数相对应的特征图；通过计算系统将特征图分割成与权重矩阵的多个块相对应的多个块；以及通过计算系统查询相应地与权重矩阵的多个块相关联的多个最大内积搜索数据结构中的每一个，其中，分割后的特征图的输出对应于与权重矩阵的块和第一阈值。

本公开的另一示例方面涉及一种计算机系统。该计算机系统包括：一个或多个处理器；以及一个或多个非暂时性计算机可读介质，该一个或多个非暂时性计算机可读介质在被一个或多个处理器执行时使计算机系统进行上文所描述的方法。

本公开的另一示例方面涉及一种计算机系统。该计算机系统包括：一个或多个处理器；以及一个或多个非暂时性计算机可读介质，该一个或多个非暂时性计算机可读介质在被一个或多个处理器执行时使计算机系统执行操作。该操作包括：为权重矩阵的多个块分割中的每一个标识多个标签的第一子集，该第一子集具有大于第一阈值的分数。该操作包括：针对多个块分割中的每一个，至少部分地基于针对这种块分割标识的多个标签的第一子集来构建用于这种块分割的评分向量的稀疏近似。该操作包括：通过经由一次或多次迭代更新用于多个标签中的至少一些的校正值来迭代地优化分解的损失函数。该操作包括：在迭代地优化分解的损失函数之后，返回对分解的损失函数或分解的损失函数的梯度的评估。

本公开的另一示例方面涉及一种训练分类器的计算机实施的方法。该方法包括：使用从上文所描述的方法获得的损失函数或损失函数的梯度来训练分类器。例如，可以在训练分类器时通过使用上述方法来获得损失函数和/或梯度的近似。所述分类器可以配置为用于极端多类或多标签分类问题。分类器可以提供任何合适的数据项的分类。

本公开的其它方面涉及各种系统、装置、非暂时性计算机可读介质、用户界面以及电子设备。

通过参考以下描述和随附权利要求书将更佳地理解本公开的各种实施例的这些和其它特征、方面和优点。并入在本说明书中且构成本说明书的一部分的附图图示了本公开的示例实施例，并且与所述描述一起用于说明相关原理。一个方面的可选特征可以在适当情况下与其它方面组合。

附图说明

在本说明书中阐述了针对本领域的普通技术人员的实施例的详细讨论，该说明书参考了附图，在附图中：

图1描绘了根据本公开的一些实施方式的示例计算设备的框图；

图2描绘了根据本公开的一些实施方式的在Megaface数据集上的多类分类结果的绘图；

图3描绘了根据本公开的一些实施方式的在WikiLSHTC数据集上的多标签分类结果的绘图；

图4描绘了根据本公开的一些实施方式的在用跳跃元语法目标进行的词嵌入上的结果的绘图；以及

图5描绘了根据本公开的一些实施方式的用于评估损失函数或损失函数的梯度的示例方法的流程图。

在多个附图上重复的附图标记旨在标识各种实施方式中的相同组件或特征。

具体实施方式

总的来说，本公开涉及用于评估损失函数或损失函数的梯度的系统和方法。对于大输出空间的问题，评估损失函数及其梯度可以是在计算上昂贵的，通常在输出空间的大小方面花费线性时间。近来，已经开发了经由用于最近邻搜索(NNS)或最大内积搜索(MIPS)的高效数据结构来加速学习的方法。然而，这种数据结构的性能通常在高维度上劣化。本公开提供了经由损失函数的对偶分解来将难以解决的高维搜索问题减少至若干容易解决得多的较低维搜索问题的系统和方法。本公开进一步提供了一种保证了原始损失的收敛的贪婪消息传递技术。以这种方式，本公开的系统和方法可以大幅度提高基于搜索的梯度近似方法的准确性并且胜过基于采样的梯度近似方法。具体地，本公开的方面提供了特别适用于一个或多个计算机的内部函数化的方法。

已经提出了许多方案来减轻作为在具有大输出空间的机器学习问题的训练模型中的瓶颈的对损失函数及其梯度的评估。一种方案在输出空间上强加了结构。该结构可以包括例如，低等级结构、树结构、局部低等级结构或分层因子分解结构。然而，结构假设可以在许多情况下被违反。例如，虽然低等级结构在推荐问题中通常是合理的，但在多类分类中通常是不成立的，因为对于每一种情况都存在恰好一个正确答案(即，类别可以不是彼此相关的)。另外，即使对于有效的结构假设，也难以根据数据构建正确结构，并且在实践中，需要启发法或人工注释。

另一途径是采样近似，其基于负输出类别中的仅一小部分的分数且还基于被标记为正的小类别集合来计算梯度的估计。然而，当损失在类别上具有偏斜分布时，所述近似具有较大方差。例如，在极端多类或多标签分类中，损失通常仅集中于几种混淆类别上，这些混淆类别具有较小的采样概率。在梯度估计中的方差通常导致学习算法的缓慢进展。

对于具有大输出空间但具有相对较小的正确输出集合的机器学习问题，学习目标通常将其梯度集中于相对较少数目的类别上，且因此，一种高效的学习方式是搜索具有显著梯度幅度的类别。用于高效地搜索类别的所提出的策略是在训练期间维持稀疏模型。然而，此方法仅适用于高输入维度的问题。另一个策略是利用数据结构以通过最大内积搜索(MIPS)或最近邻搜索(NNS)高效地找到类别。此处的主要挑战在于，随着维度的增长，变得难以同时以高查全率和高精度来执行MIPS或NNS，且因此，通过MIPS或NNS进行的梯度近似通常会牺牲准确性以实现效率。

本公开的各方面提供了一种基于将对偶分解应用于损失函数的凸共轭表示的算法。它可以被视为用于将搜索数据结构应用于学习问题的互补技术。所述算法通过经由对偶分解将维度解耦来用若干较低维搜索替换高维搜索问题。较低维搜索可以更高效地进行，且然后经由贪婪消息传递算法将不同搜索耦合在一起。所述贪婪消息传递算法被保证是收敛的，且因此，可以用于获得对损失及其梯度的良好近似。

本文中所描述的系统和方法提供了许多技术效果和益处。用于实现将高维搜索问题减少至若干较低维搜索问题的技术的系统和方法可以通过降低与高维搜索问题相关联的计算成本而具有提高效率的技术效果。例如，高维搜索问题可以由具有较小存储器要求的一个或多个处理器在更少周期内来解决，和/或较低维搜索问题可以分布在若干处理器上并且并行解决，从而减少了与高维搜索问题相关联的计算时间。将高效数据结构用于最近邻搜索(NNS)或最大内积搜索(MIPS)的最近开发的方法加快了学习速度，但这种数据结构的性能在高维度上会劣化。本公开的技术提高了基于搜索的梯度近似方法的准确性，并且胜过基于采样的梯度近似方法。

因此，用于实现贪婪消息传递技术的系统和方法可以具有保证近似损失收敛到原始损失的技术效果。所述技术可以使得能够将变量解耦到可以被相应地优化的较低维组块中，并且对最优解迭代地执行贪婪下降。因此，本公开的系统和方法改进了处理器或存储器(尤其是并行处理系统)的使用。

本公开的系统和方法还提供了对计算技术(诸如数据匹配和检索计算技术)的改进。例如，本文中的系统和方法使得能够高效地进行对损失或损失的梯度的评估。

1.问题设置

根据本公开的方面，使X表示输入空间且Y表示输出空间，并且使K:＝|Y|，其中K是极大的(例如在十万或更大的数量级)。机器学习问题的学习目标可以包括根据这种函数的给定类别F学习针对大输出空间y的评分函数

其中，

为了降低损失和梯度评估的复杂性，可以对评分函数的类别F施加线性结构假设：存在嵌入维度参数

f(x)＝Wφ(x)， (1)

其中，D<

因此，在给定f和一批样本

为了在不完全计算向量f(x)的情况下确定损失f(x

适合于上文所讨论的框架的具有大输出空间的问题的第一示例包括极端分类。在极端分类问题中，流行的分类损失函数包括交叉熵损失

和最大边界损失

对于多类问题，|P|＝1，而对于多标签问题，通常|P|<

f(x)：＝φ(x)。 (4)

这里，φ(x)是根据领域知识或经由学习(例如神经网络)中的任一个构建的特征图。领域知识和学习两者都适合所述结构假设(1)。

适合于所述框架中的具有大输出空间的问题的第二示例包括度量学习。在度量学习问题中，在训练期间的学习对象包括：学习函数

其表示点x与点y∈Y的类集的相异度。相异度函数的常见选择包括通过针对某些

和三重态损失

这种评分函数满足结构假设(1)：对于由ψ和M参数化的平方Mahalanobis距离所给定的评分函数f，矩阵W由针对每个y∈Y的行<-ψ(y)

适合于所述框架中的具有大输出空间的问题的第三示例包括词嵌入。在标准word2vec训练中，输入空间X是词汇量集合，且输出空间Y＝X；因此K是词汇量大小。跳跃元语法目标学习以下形式的评分函数f：

其中，φ(·)是潜在的词嵌入。这明显适合所述结构假设(1)：矩阵W的行是针对所有y∈X的嵌入φ(y)。

然后，在给定文本语料库D的情况下，针对样本(x,P)(其中，P是在输入词x周围的一定大小的窗口内出现的语料库中的词集合)的损失函数由下式给定：

其中，q

1.1经由搜索的损失和梯度近似

在以上示例中考虑的损失函数共享关键特征：它们的值可以通过正标签的分数和负标签的最大分数良好地近似。类似地，它们的梯度由与正标签和具有最大分数的负标签相对应的坐标控制。例如，最大边界损失(3)完全由负标签的最大分数和正标签的最小分数确定，并且其梯度仅在具有最大分数的负标签和具有最小分数的正标签上为非零的。类似地，对于交叉熵损失(2)，与负类别相对应的梯度的坐标由具有最高分数的那些控制，所述梯度坐标随着所述分数减小而以指数方式下降。

根据本公开的方面，由于分数函数f满足线性结构性质(1)，因此可以经由最大内积搜索(MIPS)数据结构高效地计算所述最大分数。这个数据结构存储向量v

算法1经由搜索的损失和梯度近似

输入样本(x,P)，准确性参数τ＞0，且访问针对W的行的MIPS数据结构T。

输出L(f(x),P)、

1：用φ(x)和阈值τ查询T以找到

2：通过针对k∈S∪P设置

3：返回

在这种近似中的误差由τ乘以

在实践中应用此方案的主要困难是维数灾难：对D的依赖性对于确切方法是指数的，甚至对于近似方法(诸如局部敏感哈希)，所述成本仍然隐式地取决于维度，因为各点在固有维度较高时离得较远。

本公开使得基于对偶分解的搜索技术能够应对维数灾难。下文进一步讨论了这种技术及其分析。

为了应用和分析所述技术，损失函数必须是平滑的(例如具有Lipschitz连续梯度)。对于非平滑损失(比如最大边界损失(3))，可以应用平滑技术(例如Nesterov(涅斯捷罗夫)平滑技术)以通过向所述损失的Fenchel(芬切尔)共轭添加强凸条项来构建具有保证的近似质量的替代损失函数：

这里，μ是平滑参数，其确保了替代损失具有

其中，1

2.损失分解

根据本公开的方面，可以将损失分解成若干部分。回顾所述线性结构假设(1)：对于所有x∈X，f(x)＝Wφ(x)。在以下描述中，(x,P)是固定的，且出于方便起见丢弃了在L中对P的依赖性，以简单地使用符号L(f(x))和

因为在W的D维行上的MIPS在计算上是昂贵的，所以可以替代地通过利用f的线性结构来分解W。具体地，可以通过将

如果定义了总分数向量z:＝f(x)＝Wφ(x)，并且针对j∈[B]，定义了每个组块分数向量z

定理1使

证明。首先，对于任何λ

2.1损失分解引导搜索(LDGS)

定理1是用于计算损失及其梯度的近似的基础。这个近似是通过对λ

算法2贪婪消息传递

输入 样本x，阈值参数τ

输出 L(f(x))和

1：使用φ

2：通过针对k∈S

3：对于t＝1、2、......(直到收敛)，进行

4：计算集合

5：对于所有k∈A和所有j∈[B]，计算

6：计算步长

7：对于所有k∈A和所有j∈[B]，更新

8：循环结束

9：返回

在所述算法中的步骤5的K时间实施中的次线性依赖于

2.2误差分析

定义

为了分析所述算法，在所述算法循环的任何给定步骤中用Λ表示BK维向量〈λ

定理2(贪婪消息传递)假设损失函数L为1/μ平滑的。然后，所述循环的第t步骤中的Λ的次优差距可以界定如下：

证明。由于损失函数L为1/μ平滑的，因此容易检查G是否为B/μ平滑的。因此，如果ΔΛ是在所述算法循环的给定步骤中的Λ的变化，那么

注意，对于所有j∈[B]，除了与

这里，可以使用Λ的每个坐标位于在0与Λ*的对应坐标之间的事实来获得所述界||ΔΛ||

虽然这个定理提供了使所述算法收敛到任何期望误差水平的证明，但其提供的界却相当弱。在实践中，仅运行所述循环的一个步骤就足以改善基于直接搜索的方法的性能。如果除了平滑之外，损失函数也是强凸的(例如，这可以通过添加一些

成本分析。可以在O(DK)时间内计算对于单个样本的确切梯度评估。直接应用基于搜索的梯度近似(算法1)的成本为O(DQ

3.实际考虑

MIPS查询。在实践中，当使用MIPS数据结构时，代替检索具有大于阈值τ

数据结构的更新。在训练期间，用于确定f的模型参数将改变，并且需要更新数据结构T

用于初始化的采样。对于随机初始化的模型，由于所有类别的分数彼此接近，因此学习的早期迭代具有均匀地分布在类别上的梯度。因此，没有必要在早期阶段搜索显著梯度幅度的候选项。在实践中，人们可以在若干小批量更新之后从基于采样的梯度近似切换为基于搜索的梯度近似。

本文中所描述的系统和方法提供了很多技术效果和益处。用于实现将高维搜索问题减少至若干较低维搜索问题的技术的系统和方法可以通过降低与高维搜索问题相关联的计算成本而具有提高效率的技术效果。例如，可以由一个或多个处理器在更少周期内按较小存储器要求来解决高维搜索问题，和/或较低维搜索问题可以分布在若干处理器上并且并行地解决，从而减少了与高维搜索问题相关联的计算时间。将高效数据结构用于最近邻搜索(NNS)或最大内积搜索(MIPS)的最近开发的方法加快了学习速度，但这种数据结构的性能在高维度上会劣化。本公开的技术提高了基于搜索的梯度近似方法的准确性，并且胜过基于采样的梯度近似方法。

另外，用于实现贪婪消息传递技术的系统和方法可以具有保证近似损失收敛到原始损失的技术效果。所述技术可以使得能够将变量解耦到可以相应地被优化的较低维组块中，并且朝向最优解迭代地执行贪婪下降。

本公开的系统和方法还提供了对计算技术(诸如数据匹配和检索计算技术)的改进。例如，本文中的系统和方法使得能够高效地进行对损失或损失的梯度的评估。

示例实施例

现在参考诸图，将进一步详细地讨论本公开的示例实施例。

图1描绘了根据本公开的示例实施例的可以评估损失函数和/或损失函数的梯度的示例计算系统100的框图。系统100包括通过网络180通信地耦合的用户计算设备102、服务器计算系统130和训练计算系统150。

用户计算设备102可以是任何类型的计算设备，诸如例如，个人计算设备(例如膝上型计算机或桌上型计算机)、移动计算设备(例如智能电话或平板电脑)、游戏控制台或控制器、可穿戴计算设备、嵌入式计算设备或任何其它类型的计算设备。

用户计算设备102包括一个或多个处理器112和存储器114。一个或多个处理器112可以是任何合适的处理设备(例如处理器核心、微处理器、ASIC、FPGA、控制器、微控制器等)，并且可以是一个处理器或可操作地连接的多个处理器。存储器114可以包括一个或多个非暂时性计算机可读存储介质，诸如RAM、ROM、EEPROM、EPROM、闪存设备、磁盘等以及它们的组合。存储器114可以存储数据116和指令118，这些指令在被处理器112执行时使用户计算设备102执行操作。

在一些实施方式中，用户计算设备102可以存储或包括一个或多个机器学习模型120。例如，机器学习模型120可以是或可以另外包括各种机器学习模型，诸如神经网络(例如深度神经网络)或其它类型的机器学习模型，包括非线性模型和/或线性模型。神经网络可以包括前馈神经网络、递归神经网络(例如长短期记忆递归神经网络)、卷积神经网络或其它形式的神经网络。

更具体地，机器学习模型120可以与大输出空间相关联，诸如例如，具有许多类别的极端多类或多标签分类问题、具有大词汇量的语言建模、和/或具有大量成对距离约束的度量学习。在一些实施方式中，机器学习模型120可以与评分函数的类别F相关联，以使得对于每个f∈F，存在嵌入维度参数

另外或可替代地，可以将一个或多个机器学习模型140包括在服务器计算系统130中或另外由服务器计算系统130存储和实施，该服务器计算系统根据客户端-服务器关系与用户计算设备102进行通信。例如，机器学习模型140可以由服务器计算系统140实施为web服务(例如极端多类或多标签分类服务、语言建模服务、度量学习服务等)的一部分。因此，可以在用户计算设备102处存储和实施一个或多个模型120，和/或可以在服务器计算系统130处存储和实施一个或多个模型140。

用户计算设备102还可以包括用于接收用户输入的一个或多个用户输入组件122。例如，用户输入组件122可以是对用户输入对象(例如手指或触控笔)的触摸敏感的触摸敏感组件(例如触摸敏感显示屏或触摸板)。触摸敏感组件可以用于实施虚拟键盘。其它示例用户输入组件包括麦克风、传统键盘或用户可以借以提供用户输入的其它构件。

服务器计算系统130包括一个或多个处理器132和存储器134。所述一个或多个处理器132可以是任何合适的处理设备(例如处理器核心、微处理器、ASIC、FPGA、控制器、微控制器等)，并且可以是一个处理器或可操作地连接的多个处理器。存储器134可以包括一个或多个非暂时性计算机可读存储介质，诸如RAM、ROM、EEPROM、EPROM、闪存设备、磁盘等以及它们的组合。存储器134可以存储数据136和指令138，这些指令在被处理器132执行时使服务器计算系统130执行操作。

在一些实施方式中，服务器计算系统130包括一个或多个服务器计算设备或另外由一个或多个服务器计算设备实施。在服务器计算系统130包括多个服务器计算设备的情况下，这种服务器计算设备可以根据顺序计算架构、并行计算架构或其某种组合来进行操作。

如上文所描述的，服务器计算系统130可以存储或另外包括一个或多个机器学习的递归超分辨率模型140。例如，所述模型140可以是或可以另外包括各种机器学习模型。示例的机器学习模型包括神经网络或其它多层非线性模型。示例的神经网络包括前馈神经网络、深度神经网络、递归神经网络以及卷积神经网络。参考图2至图7讨论了示例模型140。

用户计算设备102和/或服务器计算系统130可以经由与通过网络180通信地耦合的训练计算系统150所进行的交互来训练模型120和/或140。训练计算系统150可以与服务器计算系统130分开或可以是服务器计算系统130的一部分。

训练计算系统150包括一个或多个处理器152和存储器154。一个或多个处理器152可以是任何合适的处理设备(例如处理器核心、微处理器、ASIC、FPGA、控制器、微控制器等)，并且可以是一个处理器或可操作地连接的多个处理器。存储器154可以包括一个或多个非暂时性计算机可读存储介质，诸如RAM、ROM、EEPROM、EPROM、闪存设备、磁盘等以及它们的组合。存储器154可以存储数据156和指令158，这些指令在被处理器152执行时使训练计算系统150执行操作。在一些实施方式中，训练计算系统150包括一个或多个服务器计算设备或另外由一个或多个服务器计算设备实施。

训练计算系统150可以包括模型训练器160，其通过使用各种训练或学习技术(诸如例如，评估与机器学习模型120和/或140相关联的损失函数和/或损失函数的梯度、以及误差的向后传播)来训练存储在用户计算设备102和/或服务器计算系统130处的机器学习模型120和/或140。在一些实施方式中，执行误差的向后传播可以包括：执行通过时间的截短的反向传播。模型训练器160可以执行若干归纳技术(例如权重衰减、信息漏失等)以提高所训练的模型的归纳能力。

更具体地，模型训练器160可以将对偶分解应用于损失函数的凸共轭表示。除了将搜索数据结构(例如MIPS数据结构)应用于学习问题之外，机器训练器160还可以应用对偶分解。模型训练器160可以通过经由对偶分解将维度解耦来用若干较低维搜索替换高维搜索问题。模型训练器160可以经由贪婪消息传递来耦合不同的较低维搜索，该贪婪消息传递可以保证收敛以获得对损失及其梯度的良好近似。

在一些实施方式中，模型训练器160可以分割权重矩阵，所述权重矩阵对应于与机器学习的模型120和/或140相关联的评分函数。模型训练器160可以将权重矩阵分割成多个块，并且将所述多个块存储在多个对应MIPS数据结构中。例如，模型训练器160可以将多个块中的每一个的行存储在与所述块相对应的MIPS数据结构中。模型训练器160可以用第一阈值查询多个MIPS数据结构中的每一个，以标识与大于第一阈值的分数相关联的第一标签集合。模型训练器160可以至少部分地基于第一标签集合来构建多个块中的每一个的评分向量的稀疏近似，为每个稀疏近似确定校正值。模型训练器160可以通过更新第一标签集合中的至少一些的校正值来迭代地优化所述分解的损失函数。在优化了所述分解的损失函数之后，模型训练器160可以至少部分地基于多个块中的每一个的评分向量的稀疏近似和与评分向量的稀疏近似相关联的校正值来评估所述分解的损失函数或分解的损失函数的梯度。以这种方式，模型训练器160可以确定与评分函数相关联的损失或损失的梯度的近似。

模型训练器160可以基于训练数据集162来训练机器学习模型120和/或140。训练数据162可以包括例如具有x∈X和

在一些实施方式中，如果用户已经提供了同意，那么训练示例可以由用户计算设备102提供。因此，在这种实施方式中，可以通过根据从用户计算设备102接收到的用户特定数据训练计算系统150来训练向用户计算设备102提供的模型120。在一些情况下，这个进程可以被称为个性化模型。

模型训练器160包括用于提供期望功能性的计算机逻辑。模型训练器160可以用控制通用处理器的硬件、固件和/或软件来实施。例如，在一些实施方式中，模型训练器160包括存储在存储设备上、加载到存储器中并且由一个或多个处理器执行的程序文件。在其它实施方式中，模型训练器160包括一个或多个计算机可执行指令集，该计算机可执行指令集存储在有形的计算机可读存储介质(诸如RAM硬盘或光学介质或磁性介质)中。

网络180可以是任何类型的通信网络，诸如局域网(例如内联网)、广域网(例如互联网)或它们的某种组合，并且可以包括任何数目的有线链路或无线链路。通常，可以使用各种通信协议(例如TCP/IP、HTTP、SMTP、FTP)，编码或格式(例如HTML、XML)和/或保护方案(例如VPN、安全HTTP、SSL)，经由任何类型的有线连接和/或无线连接来进行通过网络180的通信。

图1图示了可以用于实施本公开的一个示例计算系统。也可以使用其它计算系统。例如，在一些实施方式中，用户计算设备102可以包括模型训练器160和训练数据集162。在这种实施方式中，可以在用户计算设备102处本地地既训练又使用模型120。在一些这种实施方式中，用户计算设备102可以实施模型训练器160以基于用户特定数据来个性化模型120。

图2描绘了根据本公开的一些实施方式的在Megaface数据集上的多类分类结果的绘图。

图3描绘了根据本公开的一些实施方式的在WikiLSHTC数据集上的多标签分类结果的绘图。

图4描绘了根据本公开的一些实施方式的在用跳跃元语法目标进行的词嵌入上的结果的绘图。

因此，图2至图4描绘了根据本公开的示例实施例的图示不同损失函数与梯度评估方法的比较的绘图。具体地，图2与多类分类问题(例如面部识别)相对应并且描绘了图示了在MegaFace数据集上的多类分类结果的绘图：测试准确性相对于训练时间(左)、训练准确性相对于训练时间(中间)以及训练准确性相对于时期数(右)，其中，x轴为对数标尺。图3与多标签分类问题(例如文档标记)相对应并且描绘了图示了在WikiLSHTC数据集上的多标签分类结果的绘图：测试准确性相对于训练时间(左)、训练准确性相对于训练时间(中间)以及训练准确性相对于时期数(右)，其中，x轴为对数标尺。图4与无监督词嵌入问题相对应并且描绘了图示了在用跳跃元语法目标(9)进行的词嵌入上的结果，其中，GD-Exact、GD-MIPS和GD-Decomp-MIPS用Word2vec-Neg的一个时期所训练的模型来初始化。

关于图2和图3，采用随机梯度下降(SGD)优化算法，其中，从{1，0.1，0.01}中选择初始步长以实现每种方法的最佳性能、以及1/(1+t)冷却方案，其中，t是迭代计数器。小批量大小为10，并且所有方法都用在专用计算机上运行的共享存储器架构中的10个CPU核心并行处理。所有实施方式都是C++的。比较了以下损失函数和梯度评估方法：

Softmax：对交叉熵损失(2)的确切梯度评估，其中，对于图2中的多类，|P|＝1，且对于图3中的多标签，|P|<

Sampled-Softmax(样本Softmax)：采样策略，其包括实例的所有正类别，并且从剩余的负类别中进行统一地二次采样，样本大小为K/100；

Margin(边界)：对平滑的最大边界损失(10)的确切梯度评估，其中，对于图2中的多类，μ＝1，且对于图3中的多标签，μ＝5。利用O(Klog(K))计算双单纯形法投影(11)。对于这个损失，梯度更新比交叉熵的更新更快，因为损失梯度非常稀疏，使得后向传递更快；

MIPS：对平滑的最大边界损失(10)的基于搜索的梯度评估(例如算法1)，其中，对于图2中的多类，μ＝1，且对于图3中的多标签，μ＝5。具有100个质心的球形聚类用作具有大小为K/100的批量查询的MIPS数据结构；以及

Decomp-MIPS(分解MIPS)：经由分解搜索(例如算法2，T＝1次迭代)的梯度评估。对于图2中的多类，将内积划分为B＝8个因子，且对于图3中的多标签，B＝4。具有100个质心的球形聚类用作具有大小为K/100的批量查询的MIPS数据结构。

对于图2，多类分类实验是在最大公开可用的面部识别数据集MegaFace上进行的，其中，每个身份都被视为类别，且每个样本都是由面部检测器裁剪的图像。表1中示出了MegaFace数据集统计。在MS-Celeb-1M数据集上对FaceNet架构进行了预训练，且在MegaFace数据集上对FaceNet架构的最后一层进行了微调。最后一层的输入是大小为128的嵌入，在Decomp-MIPS方法中，将该嵌入划分为B＝8个因子，每个因子的维度为16。

表1：MegaFace数据集的统计

图2中的比较方法的运行时间多于一天，并且图2中示出了结果。对用于优化(平滑的)最大边界损失的方法(Decomp-MIPS、MIPS和Margin)的比较表明，Decomp-MIPS和MIPS两者都可以将迭代加速1至2个数量级。然而，MIPS以比Decomp-MIPS低得多的准确性收敛，并且差距在运行了更多次迭代时变得更大。注意时间和时期是对数标尺。另外，与Margin相比，Softmax具有慢得多的进展。一天后，Softmax和Margin均未完成一个时期(4.7M个样本)。Margin的进展是好得多的，大概是因为其将重点放在令人混淆的身份上。此外，与基于MIPS的途径相比，Sampled-Softmax具有快得多的迭代，但每次迭代的进展却较小，从而导致总体进展较慢。

对于图3，多标签分类实验是在WikiLSHTC(极端分类存储库中的基准数据集)上进行的，其中，每个类别是Wikipedia中的目录标记，且每个样本都是具有词袋表示的文档。表2中示出了WikiLSHTC数据统计。平均而言，每个样本都具有3.19个正标签，且每个类别在17.46个样本中显现为正类别。单隐藏层全连接前馈网络被训练以进行多标签分类任务。第一层具有等于词汇量大小(1.6M)的输入维度和维度为100的输出。第二层具有等于类别数目(325K)的输出大小以及不同损失函数和不同比较方法的近似。训练结果还产生了作为副产品的文档和词嵌入。对于Decomp-MIPS，将最后一层的输入划分为B＝4个因子，每个因子的维度为25。

图3中的比较方法的运行时间多于一天，并且图3中示出了结果。如所示出的，Softmax具有非常好的每次迭代进展，显著地超过了基于平滑的最大边界损失的其它三种方案(Margin、MIPS、Decomp-MIPS)的进展。然而，Softmax的迭代比其它迭代慢得多，这是由于其具有密集的损失梯度，且因此具有较慢的反向传播，以使得在比较训练时间时，Softmax的执行类似于Margin。另一方面，当在每时期的进展方面比较Margin、Decomp-MIPS以及MIPS时，Decomp-MIPS的更新几乎实现了与Margin的确切梯度计算相同的进展，而与Margin和Decomp-MIPS相比，MIPS的训练准确性显著下降，这是由于其运行了更多次迭代。总体而言，基于MIPS的方法导致一个数量级的加速，而Decomp-MIPS保留了确切方法的准确性。另一方面，尽管Sampled-Softmax的迭代较快，但其具有极其缓慢的每次迭代的进展，且即使一天之后，Sampled-Softmax也无法达到可与其它方法相比的准确性。

表2：WikiLSHTC数据集的统计

关于图4，本公开的梯度近似方法在具有跳跃元语法学习目标(9)的词嵌入任务上进行评估，并且与两种广泛使用的梯度近似方法——在word2vec封包中实施的分层Softmax(Word2vec-HS)和负采样(Word2vec-Neg)进行比较。从{5,10,15,20,25}中选出用于Word2vec-Neg的样本大小。

使用由近五十万个词汇量大小组成的基准数据集BillonW。表3中提供了数据统计。使用大小为8的窗口，并且在语料库中对常用词进行了二次采样。每个词w以概率

表3：BillionW数据集的统计

注意，跳跃元语法目标(9)以折叠形式呈现。这里，相同输入输出对的所有条项被分组在一起并且按频率进行加权。通过对(9)中的经验输入输出分布q

图4中的比较方法用24个CPU核心并行处理，并且图4中示出了结果。在第一时期之后，基于交替梯度下降(GD)(具有所述折叠目标(9))的方法具有每个时期的更快收敛，并且GD-Deomp-MIPS的迭代比GD的迭代快了5倍，同时在相同训练时间内具有比GD-MIPS显著更佳的目标值。

图5描绘了用于评估损失函数或损失函数的梯度的方法500的图式。在(502)中，方法500包括：将权重矩阵分割成块。例如，训练计算系统150可以分割与评分函数相对应的权重矩阵。训练计算系统150可以将权重矩阵分割成多个块。所述多个块中的每一个可以包括所述权重矩阵的一个或多个列。

在(504)处，方法500包括：为每个块标识第一标签集合。例如，训练计算系统150可以为多个块中的每一个标识第一标签集合。第一标签集合可以与大于第一阈值的分数相关联。训练计算系统150可以查询相应地与权重矩阵的多个块相关联的多个最大内积搜索数据结构中的每一个。具体地，训练计算系统150可以获得与权重矩阵和评分函数相对应的特征图；将特征图分割成与所述权重矩阵的多个块相对应的多个块；以及查询相应地与权所述重矩阵的多个块相关联的多个最大内积搜索数据结构中的每一个，其中，分割后的特征图的输出与所述权重矩阵的块和第一阈值相对应。

在(506)处，方法500包括：为每个块构建评分向量的稀疏近似。例如，训练计算系统150可以至少部分地基于第一标签集合来为多个块中的每一个构建评分向量的稀疏近似。训练计算系统150可以针对多个块中的每一个设置用于多个标签中的每一个的相应近似分数，该多个标签中的该每一个既不包括在用于所述块的第一标签集合中也不包括在等于零的正标签中；以及针对多个块中的每一个设置用于多个标签中的每一个的相应近似分数，该多个标签中的该每一个既不包括在用于所述块的第一标签集合中也不包括在等于根据最大内部搜索乘积搜索查询所确定的真正分数的正标签中。

在(508)处，方法500包括：为每个评分向量确定校正值。例如，训练计算系统150为多个块中的每一个的评分向量的每个稀疏近似确定校正值。具体地，训练计算系统150可以至少部分地基于多个块中的每一个的第一标签集合来标识第二标签集合，该第二标签集合与大于第二阈值的梯度相关联。训练计算系统150可以确定跨越多个块的第二标签集合中的每个标签的平均近似分数。训练计算系统150可以为多个块中的每一个的第二标签集合中的每个标签确定近似分数。训练计算系统150可以为第二标签集合中的标签与多个块中的块的每个组合而确定在用于多个块中的每一个的平均近似分数与近似分数之间的差。训练计算系统150可以至少部分地基于针对第二标签集合中的标签与多个块中的块的每个组合的所确定的差来更新多个块中的每一个的评分向量的每个稀疏近似的校正值。

在(510)处，方法500包括：对损失或损失的梯度进行近似。例如，训练计算系统150可以通过至少部分地基于多个块中的每一个的评分向量的稀疏近似和与所述评分向量的稀疏近似相关联的校正值而评估分解的损失函数或分解的损失函数的梯度，来确定与所述评分函数相关联的损失或损失的梯度的近似。分解的损失函数可以包括多个部分，每个部分同与多个块中的每一个的评分向量的相应稀疏近似相关联的损失相对应。

训练计算系统105可以对损失函数执行平滑技术，以构建具有连续梯度的替代损失函数；以及至少部分地基于替代损失函数来确定分解的损失函数。

训练计算系统150可以跨越多个块使按这种块的相应近似评分向量加上每个块的校正值向量所评估的每个块的相应损失的平均值最小化，以使得跨越所述多个块的校正值向量的总和等于零。

训练计算系统150可以为多个训练示例中的每一个确定损失或损失的梯度的近似。

训练计算系统150可以至少部分地基于与评分函数相关联的损失的所确定的近似或损失的梯度来修改权重矩阵或评分函数的一个或多个参数。

方法500可以在训练分类器时使用。所述分类器可以用于极端多类或多标签分类问题中。所述分类器可以提供任何合适的数据项的分类，并且可以例如用于例如基于可以表示一个或多个图像或视频的输入序列来分类或发现音频片段、图像或视频。所述数据项可以是表示静止图像或移动图像的数据，在这种情况下，所述数据项中所含有的各个数值可以表示像素值，例如像素的一个或多个颜色信道的值。用于训练模型的训练图像可以是由相机捕获到的真实世界的图像。

可替代地，所述数据项可以是表示声音信号的数据，例如音频波形的振幅值(例如自然语言；在这种情况下，训练示例可以是例如由麦克风根据人类演讲者的语音记录的自然语言的样本)。在另一种可能性中，所述数据项可以是文本数据，例如文本字符串或机器翻译任务中的词和/或子词单元(单词)的其它表示。因此，所述数据项可以是一维、二维或更高维的。

本文中所讨论的技术参考服务器、数据库、软件应用和其它基于计算机的系统以及所采取的动作和向这种系统和从这种系统发送的信息。基于计算机的系统的固有灵活性允许在各组件之间和各组件当中的任务和功能性的多种可能配置、组合和划分。例如，本文中所讨论的进程可以使用单个设备或组件或组合工作的多个设备或组件来实施。数据库和应用可以在单个系统上实施或分布在多个系统上。分布式组件可以按顺序或并行地运行。

虽然已经相对于本主题的各种特定示例实施例详细地描述了本主题，但每个示例都是通过说明而非限制本公开的方式提供的。本领域的技术人员在获得对前述内容的理解后可以容易地产生对这种实施例的更改、变型和等同物。因此，本主题公开并不排除如对于本领域的普通技术人员将容易地显而易见的本主题的这种修改、变型和/或添加。例如，作为一个实施例的一部分所图示或描述的特征可以与另一个实施例一起使用以产生又一个实施例。因此，本公开旨在覆盖这种更改、变型和等同物。