英语原文共 8 页
大规模核机器的随机特征
简介
为了加速核机器的训练，我们提出将输入数据映射到随机的低维特征空间，然后应用现有的快速线性方法。这些特征的设计使得转换后的数据的内积与用户指定的平移不变核的特征空间中的内积近似相等。我们研究了两组随机特征，给出了它们逼近各种径向基核的能力的收敛边界，并表明在大规模分类和回归任务中，应用于这些特征的线性机器学习算法优于最先进的大型核机器。
介绍
支持向量机等核心机具有很强的吸引力，因为它们可以用足够的训练数据任意逼近任意函数或决策边界。不幸的是，在数据的内核矩阵（gram矩阵）上操作的方法与训练数据集的大小不匹配。例如，即使使用功能最强大的工作站，也可能需要几天时间在一个数据集上训练一个非线性SVM，该数据集包含50万个训练示例。另一方面，当数据的维数很小的[1，2，3]时，线性机器可以很快地在大型数据集上进行训练。利用这些线性训练算法训练非线性机器的一种方法是近似地对核矩阵进行因子分解，并将因子矩阵的列作为线性机器的特征（例如示例4）。相反，我们建议考虑内核函数本身。这种因式分解不依赖于数据，允许我们通过将数据映射到相对低维的随机特征空间，将核心机的训练和评估转换为线性机的相应操作。我们的实验表明，这些随机特性与非常简单的线性学习技术相结合，在速度和准确性方面与最先进的基于内核的分类和回归算法（包括那些影响内核矩阵的算法）有着同样的优势。
内核技巧是为仅依赖于成对输入点之间的内积的算法生成特性的简单方法。通过观察，任意带x，yisin;的正定函数定义内积和提升phi;，使提升数据点之间的内积可以快速计算为。这种方便性的代价是算法只能通过的计算或通过应用于所有数据点对的由k组成的内核矩阵来访问数据。因此，大型训练集会产生巨大的计算和存储成本。
我们提出用随机特征映射将数据显式映射到一个低维欧几里得内积空间，而不是依赖于内核技巧提供的隐式提升，因此使一对变换点之间的内积近似于它们的内核评价:
与内核的提升ϕ不同，z是低维的。因此，我们可以简单地用Z变换输入，然后应用快速线性学习方法来逼近相应的非线性核机器的答案。在下面的内容中，我们展示了如何构造特征空间，在只有维的情况下，将流行的平移不变核均匀地近似到的内部，并从经验上证明，对于更小的d，可以获得良好的回归和分类性能。
除了让我们能够使用极快的学习算法，这些随机特征图还提供了一种快速评估机器的方法。有了内核技巧，评估一个测试点x就需要计算，这需要运算来计算，并且需要保留大量数据集，除非机器非常稀疏。对于大型数据集，这通常是不可接受的。另一方面，在学习超平面W之后，可以通过简单地计算来评价线性机器，这里给出的随机特征图只需要O（D d）操作和存储。
我们演示了两个随机特征映射来近似移动不变核。我们在第3节中给出的第一个随机图，由我们寻求近似的核函数的傅立叶变换随机抽取的正弦曲线组成。由于此图平滑，因此非常适合于插值任务。我们的第二个随机映射（见第4节）使用随机移动的网格以随机选择的分辨率来划分输入空间。这种映射并不平滑，但是利用了输入点之间的接近性，并且非常适合于近似依赖于数据点之间的l1距离的内核。我们在第5节中的实验表明，在各种回归和分类场景中，将这些随机图与简单线性学习算法相结合，可以与最先进的训练算法进行更好的竞争。
相关工作
大型核机器最常用的方法是求解支持向量机（SVM）的分解方法。这些方法使用坐标上升迭代更新内核机系数的子集，直到KKT条件满足在公差[5,6]范围内。虽然这种方法是多功能的工作工具，但它们并不总是能够扩展到具有数十万个数据点的非线性问题数据集。为了将核机器学习扩展到这些尺度，提出了几种加速核矩阵运算的近似方案。
核函数的评估可以使用线性随机投影加速[7]。丢弃内核矩阵的单个条目[7]或整行[8、9、10]会降低在内核矩阵上操作的存储和计算成本。这些近似值要么保留了数据的可分离性[8]，要么产生了很好的真核矩阵的低秩或稀疏近似值[7，9]。快速多极和多网格方法也被提出用于这一目的，但是，虽然它们似乎对小尺寸和低尺寸问题有效，但它们还没有在大数据集中得到证明。此外，这些方法所依赖的Hermite或Taylor近似的质量随着数据集的维数呈指数级下降[11]。使用kd树进行的快速最近邻查找已被用于与内核矩阵进行近似乘法，反过来，还有各种其他操作[12]。我们在第4节中展示的特征图让人想起了kd树，它使用与[13]中开发的嵌入线性分配问题类似的多分辨率轴对齐网格来划分输入空间。
随机傅里叶特征
我们的第一组随机特性将数据投影到一条随机选择的线上，然后通过一个正弦曲线传递结果的标量（见图1和算法1）。从分布中画出随机线，以保证两个变换点的内积近似于所需的平移不变核。
谐波分析的以下经典定理提供了这种转换背后的关键见解：
定理1（博赫纳15）.当且仅当是非负测度的傅立叶变换时，上的连续核是正定的。
图像1：随机傅立叶特征。特征图的每个分量将X投影到从k（∆）的傅立叶变换p(omega;)绘制的随机方向omega;上，并将该线缠绕到中的单位圆上。用这种方法变换两点x和y后，它们的内积是k（x，y）的无偏估计量。该表列出了一些常用的移位不变内核及其傅立叶变换。为了处理非各向同性内核，在应用其中一个内核之前，数据可能会变白。
如果核k（delta;）被适当地缩放，Bochner定理保证其傅立叶变换是一个适当的概率分布。定义，我们得到，因此，当omega;从中提取时，是的无偏估计。
要获得k的实值随机特征，请注意概率分布和核k(∆)都是实的，因此被积函数可以替换为。定义给出一个满足条件的实值映射，因为。其他映射，如，其中omega;由p(omega;)绘制，b由[0,2pi;]均匀绘制，也满足条件。
我们可以通过将随机选择的连接成列向量z并将每个分量正规化来降低的方差。由二维随机特征z，特征化的点的内积是的样本平均值，因此是较低的方差近似值来达到预期(2)。
由于在-1和1之间有界，对于一对固定的点x和y，Hoeffding不等式保证了和：在D中的指数快速收敛。基于这一观察，可以同时为输入空间中的每对点证明一个更强有力的断言：
断言1（傅立叶特征的一致收敛性）。设M为直径为diam(M)的的紧子集。然后，对于算法1中定义的映射z，我们得到，式中，是k的傅立叶变换的第二个力矩。此外，当时，具有任何恒定概率。
这个断言的证明首先保证了在一个mtimes;m上的网络中心的接近。然后利用特征图平滑且概率高的事实将这个结果扩展到整个空间。详见附件。
通过标准傅立叶恒等式，标量等于k在0时的Hessian迹线。它量化了内核在原点的曲率。对于球面高斯核，，我们得到。
算法1 随机傅里叶特征
要求：一个正定移位不变量核
确保：随机特征图因此有
计算k核的傅立叶变换p：
从P中提取D IID样本。
设
随机装箱算法
我们的第二个随机映射以随机选择的分辨率使用随机移位的网格划分输入空间，并为输入点分配一个二进制位字符串，该字符串对应于它所在的存储单元（见图2和算法2）。网格的构造使得两个点x和y被分配到同一个网格的概率与成正比。一对转换点之间的内积与两个点合并在一起的次数成正比，因此是的无偏估计。
图像2：随机装箱算法。（左图）该算法使用随机移动的网格以随机选择的分辨率重复地划分输入空间，并为每个点x分配与其分配的箱相关联的位串。（右图）描述该划分的二进制邻接矩阵在其第i，j等条项中具有，并且是核矩阵的无偏估计。
我们首先描述一个随机映射来近似Rtimes;R的紧子集上的“hat”核，然后展示如何构造更一般的可分离多维核的映射。用一个节距delta;网格划分实数线，然后用从[0，delta;]中均匀绘制的量u随机移动该网格。此网格将实数线划分为所有整数n的间隔。此网格中两个点x和y落在同一个网格中的概率最大[13]。
换言之，如果我们对网格的箱进行编号，使X点落在箱中，，Y落在箱中，，则。如果我们将编码为二进制指示向量，如果x和y落在同一个仓位，则，否则为零，因此。因此，Z是的随机图。
现在考虑可以写成Rtimes;R：的紧子集上帽形核的凸组合的平移不变核。如果网格的节距delta;是从p取样的，则z再次给出k的随机图，因为。也就是说，如果网格的节距delta;是从p采样的，并且位移u是从[0，delta;]均匀地绘制出来的，那么x和y结合在一起的概率是k（x，y）。附录中的引理1表明，通过设置，p很容易从k中恢复。例如，在拉普拉斯核的情况下，，是伽马分布。对于高斯核，k并不是到处都是正的，所以这个过程不会产生随机映射。
如果每个都可以写成帽核的凸组合，（如多变量拉普拉斯核）形式的可分离多变量平移不变核的随机映射，则可以用类似的方式构造。我们将上述分块过程独立地应用于的每个维度。在尺寸m中，和结合在一起的概率为。因为装箱过程是跨维度独立的，x和y在每个维中结合在一起的概率是。在这种多变量情况下，将与d维网格的每个bin对应的整数向量编码为二进制指示向量。在实践中，为了防止在d较大时计算时溢出，我们的实现从表示中消除了未占用的箱。由于箱的数量永远不会超过测试点，这就确保了不会发生溢出。
我们可以通过将p随机分块函数z连接到一个更大的特征z列表中并按缩放来再次减少估计量的方差。内积是p独立的平均值，因此方差较小。
由于是二元的，Hoeffding不等式保证对于一对固定的点x和y，作为p的函数以指数形式快速收敛到。同样，一个更强有力的说法是，这种收敛同时适用于所有点：
断言2.设M为diam(M)的的紧子集。设，表示k相对于范数的Lipschitz常数。如之前z所述，我们得到，注意为1，拉普拉斯核。断言要求的证明（见附录）将Mtimes;M分成几个小的矩形单元，在这些单元上变化不大，和不变。在这些单元的中心，很可能接近，这就保证了和在整个Mtimes;M中都很接近。
算法2 随机装箱算法
要求：点.核函数，因此是上的概率分布。
确保：一种随机特征映射，使。
对于，用节距绘制网格参数delta;，，并将从均匀分布移到[0,]。让z返回包含x的bin的坐标，作为二进制指示向量.
实验
表1中总结的实验表明，具有随机特征的岭回归是一种快速逼近有监督内核机器训练的方法。我们将重点与核心向量机[14]进行比较，因为[14]中显示的核心向量机比其他已知的核心机培训方法更快、更准确，在大多数情况下，包括对数据点的随机抽样[8]。实验在[14]中评估的五个标准大规模数据集上进行，不包括合成数据集。我们使用各自作者提供的二进制文件复制了有关CVM、和libSVM的文献中的结果1。对于随机特征实验，我们通过求解岭回归问题来训练回归器和分类器，其中y表示期望输出的向量，z表示随机特征的矩阵。
备注1我们将KDDCUP 99结果包括在完整性中，但请注意，该数据集固有的样本过多：在50个训练示例（训练数据集的0.001%）的随机抽样上训练SVM（或具有随机特征的最小二乘）足以持续产生8%的测试误差。此外，当我们能够用作者提供的参数复制CVM的6.2%的错误率时，随机重组训练集后的再训练将导致18%的错误，并将计算时间增加一个数量级。即使在最初的顺序上，仅将CVM的正则化参数扰动15%就得到49%。测试集的错误率[16]。
表1：文献报道的具有随机特征的岭回归、核向量机和各种最先进的精确方法之间的测试误差和训练时间的比较。对于分类任务，报告错误预测的测试点百分比，对于回归任务，用地面真值范数归一化的均方根误差。
图3：随着训练集的增长，测试数据的准确性不断提高。在Forest数据集上，使用随机分块，将数据集大小加倍可以将测试错误减少多达40%（左）。误差随着p的增长而迅速衰减（中间）。训练时间随着P的增长而缓慢增长（右）。
为了在数据点x上评估结果机器，我们可以简单地计算w′z（x）。尽管简单，但具有随机特性的岭回归比其他方法更快，并提供具有竞争力的准确性。它还生成非常紧凑的函数，因为只需要保留w和一组随机向量或分区的哈希表。随机傅立叶特征在很大程度上依赖于插值的任务上表现得更好。另一方面，随机分块功能在记忆任务（标准SVM需要许多支持向量的任务）上表现得更好，因为它们显式地保留了输入空间中的位置。这种差异在FOREST数据集中最为显著。
图3（左图）说明了在更大的数据集上训练分类器的好处，随着训练中使用的数据越多，准确性不断提高。图3（中间）和（右侧）显示，即使从少量的特性中也可以获得良好的性能。
结论
我们提出了随机特征，其内部产物一致地接近许多流行的内核。我们从经验上证明，将这些特性作为标准线性学习算法的输入，可以产生在精度、培训时间和评估时间方面与最先进的大型核机器相竞争的结果。
值得注意的是，傅立叶特征和分块特征的混合可以通过连接这些特征来构造。虽然我们专注于回归和分类，但我们的特性可以应用于加速其他核心方法，包括半监督和无监督学习算法。在所有这些情况下，可以通过首先计算随机特征，然后应用相关的线性技术来实现显著的计算速度。
致谢
我们感谢Eric Garcia对这些功能的早期版本的帮助，Sameer Agarwal和James R.Lee对这些功能进行了有益的讨论，Erik还学习了Miller和Andres Corrada Emmanuel对这些功能进行了有益的更正。
证明
引理1：假设函数是两次可微的，其形式为。则.
证明.我们需要p所以
(3)
(4)
为了解p，将两次w.r.t.与∆进行微分，得到和.
断言1的证明.定义和。
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
