May, 2016

利用结构回收随机性进行次线性时间核扩展

PDF
TL;DR提出一种方案，通过随机嵌入将高斯随机向量回收到结构化矩阵中，以实现对各种核函数的近似，该方案可在亚线性时间内完成。其中包括 Fastfood 构造作为特例，还可扩展到周而复始、托普利兹和汉克尔矩阵以及广泛的结构化矩阵家族，该矩阵家族的特征在于低位移秩的概念。介绍了控制逼近质量的相干性和图论结构常数的概念，并证明了在我们的框架内出现的随机特征映射的无偏性和低方差性质。对于低位移矩阵的情况，我们展示了如何控制结构和随机性的程度，以降低统计方差的代价，但需要增加计算和存储要求。实证结果强烈支持我们的理论，并证明了使用随机特征来扩展核方法的可行性。
random embeddingskernel functionsstructured matriceslow-displacement rankrandom feature maps
发现论文，激发创造
  • 快餐：对数线性时间的近似核展开

    本文提出了一种名为 Fastfood 的近似方法，通过利用 Hadamard 矩阵和对角高斯矩阵而不是高斯随机矩阵，使得计算非线性基函数的时间复杂度缩小到了 O (n log d) 并且仅需 O (n) 的存储空间，同时保证了无偏和低方差的特点，为核方法的实际应用提供了可能性。

    Aug, 2014

  • 任意元素相关下的结构化矩阵学习和马尔可夫转移核估计

    该研究考虑了嘈杂的低秩加稀疏矩阵恢复的一般框架，并提出了一个不相干约束的最小二乘估计器，证明了它在确定性下界和匹配最小极小风险方面的紧密性，同时展示了在一些重要的统计机器学习问题中的应用。

    Jan, 2024

  • 结构化散列投影的二进制嵌入

    此论文研究了利用哈希机制来构建二进制嵌入的方法，该方法包括伪随机投影和非线性映射，使用结构化矩阵可以有效地压缩信息并降低随机性使用，实验证明了其对神经网络学习性能和最近邻分类器性能的依赖关系。

    Nov, 2015

  • 结构化随机正交嵌入的不合理有效性

    本文使用基于结构化随机矩阵和正交行的嵌入，分析了其在机器学习中的应用，包括降维和核逼近，同时通过实证结果证明了该方法在各种机器学习应用中具有明显提高精度和 / 或速度的效果。

    Mar, 2017

  • 基于随机特征的高效全局字符串核函数：超越子结构计数

    使用全局字符串内核通过随机特征映射来维护正定性并避免对角线支配的内核矩阵，具有与字符串长度和训练字符串样本数量的线性训练成本。

    Nov, 2019

  • 随机傅里叶特征的误差

    本文介绍了核方法在机器学习问题中的应用，提到了采用随机傅里叶特征解决大规模数据集问题的方法，并给出了更好的误差界限及嵌入方式的理解、近似误差、在某些机器学习方法中的使用，同时指出了该特征的两种变体中，更常用的一种在高斯核中具有严格更高的方差且具有更糟糕的界限的令人惊讶的事实。

    Jun, 2015

  • 非随机特征

    本文提出一种基于 Fourier 分析的方法，用于训练翻译不变或旋转不变的核，并通过一种在线平衡找到动态算法来解释我们的算法，并在合成和现实世界数据集上进行评估，证明了扩展性和与相关随机特征方法相比的一致改进。

    Oct, 2017

  • 利用随机性发现结构：构造近似矩阵分解的概率算法

    本文介绍了一种用于构建随机算法的模块化框架，以进行矩阵分解，通过随机抽样识别矩阵的大部分内容，并将输入矩阵压缩到子空间，这种方法在精度、速度和鲁棒性方面都比传统方法更具优势，能够更好地解决大数据集合的问题。

    Sep, 2009

  • 正交随机特征

    本文通过使用正交矩阵代替高斯随机矩阵来减小核近似误差提出了正交随机特征和结构化正交随机特征，并为此行为提供理论和实证证据。实验结果证明了与现有方法相比 ORF 和 SORF 的有效性。

    Oct, 2016

  • 正交随机特征：显式形式和尖锐不等式

    通过正交随机特征来近似普遍的高斯核，本研究分析了基于正交随机特征的核逼近的偏差和方差，并通过使用归一化贝塞尔函数推导出了明确的表达式，并提供了支持正交随机特征比随机傅里叶特征更具信息性的尖锐指数界限。

    Oct, 2023