随机傅立叶特征(RFF)方法是内核方法可扩展性的强大而流行的技术。 RFF的理论基础是基于将对称,正定(PD)函数与概率度量相关联的Bochner定理。这种条件自然排除了在实践中具有广泛应用的不对称函数,例如有向图,条件概率和不对称内核。然而,从理论和经验上尚不清楚理解不对称函数(内核)及其通过RFF的可伸缩性尚不清楚。在本文中,我们引入了一种复杂的度量,其真实和虚构部分对应于四个有限的正措施,从而扩大了Bochner定理的应用范围。通过这样做,该框架允许通过一种积极度量来处理经典的对称,PD内核;通过签名措施对称,非阳性的确定内核;并通过复杂的措施通过不对称内核,从而将它们统一为RFF的一般框架,称为Ask-RFF。从统一收敛的角度来看,通过复杂措施通过复杂度量的这种近似方案享有理论保证。在算法实现中,由于总质量的计算而加快内核近似过程,这是昂贵的,我们采用了一种基于子集的快速估计方法,可优化子训练集中的总质量。我们的ask-rffs方法在几个典型的大规模数据集上得到了经验验证,并实现了有希望的内核近似性能,这证明了Ask-RFF的有效性。
translated by 谷歌翻译
通过建立神经网络和内核方法之间的联系,无限宽度极限阐明了深度学习的概括和优化方面。尽管它们的重要性,但这些内核方法的实用性在大规模学习设置中受到限制,因为它们(超)二次运行时和内存复杂性。此外,大多数先前关于神经内核的作品都集中在relu激活上,这主要是由于其受欢迎程度,但这也是由于很难计算此类内核来进行一般激活。在这项工作中,我们通过提供进行一般激活的方法来克服此类困难。首先,我们编译和扩展激活功能的列表,该函数允许精确的双重激活表达式计算神经内核。当确切的计算未知时,我们提出有效近似它们的方法。我们提出了一种快速的素描方法,该方法近似于任何多种多层神经网络高斯过程(NNGP)内核和神经切线核(NTK)矩阵,以实现广泛的激活功能,这超出了常见的经过分析的RELU激活。这是通过显示如何使用任何所需激活函​​数的截短的Hermite膨胀来近似神经内核来完成的。虽然大多数先前的工作都需要单位球体上的数据点,但我们的方法不受此类限制的影响,并且适用于$ \ Mathbb {r}^d $中的任何点数据集。此外,我们为NNGP和NTK矩阵提供了一个子空间嵌入,具有接近输入的距离运行时和接近最佳的目标尺寸,该目标尺寸适用于任何\ EMPH {均质}双重激活功能,具有快速收敛的Taylor膨胀。从经验上讲,关于精确的卷积NTK(CNTK)计算,我们的方法可实现$ 106 \ times $速度,用于在CIFAR-10数据集上的5层默特网络的近似CNTK。
translated by 谷歌翻译
We consider neural networks with a single hidden layer and non-decreasing positively homogeneous activation functions like the rectified linear units. By letting the number of hidden units grow unbounded and using classical non-Euclidean regularization tools on the output weights, they lead to a convex optimization problem and we provide a detailed theoretical analysis of their generalization performance, with a study of both the approximation and the estimation errors. We show in particular that they are adaptive to unknown underlying linear structures, such as the dependence on the projection of the input variables onto a low-dimensional subspace. Moreover, when using sparsity-inducing norms on the input weights, we show that high-dimensional non-linear variable selection may be achieved, without any strong assumption regarding the data and with a total number of variables potentially exponential in the number of observations. However, solving this convex optimization problem in infinite dimensions is only possible if the non-convex subproblem of addition of a new unit can be solved efficiently. We provide a simple geometric interpretation for our choice of activation functions and describe simple conditions for convex relaxations of the finite-dimensional non-convex subproblem to achieve the same generalization error bounds, even when constant-factor approximations cannot be found. We were not able to find strong enough convex relaxations to obtain provably polynomial-time algorithms and leave open the existence or non-existence of such tractable algorithms with non-exponential sample complexities.
translated by 谷歌翻译
非线性自适应控制理论中的一个关键假设是系统的不确定性可以在一组已知基本函数的线性跨度中表示。虽然该假设导致有效的算法,但它将应用限制为非常特定的系统类别。我们介绍一种新的非参数自适应算法,其在参数上学习无限尺寸密度,以取消再现内核希尔伯特空间中的未知干扰。令人惊讶的是,所产生的控制输入承认,尽管其底层无限尺寸结构,但是尽管它的潜在无限尺寸结构实现了其实施的分析表达。虽然这种自适应输入具有丰富和富有敏感性的 - 例如,传统的线性参数化 - 其计算复杂性随时间线性增长,使其比其参数对应力相对较高。利用随机傅里叶特征的理论,我们提供了一种有效的随机实现,该实现恢复了经典参数方法的复杂性,同时可透明地保留非参数输入的表征性。特别地,我们的显式范围仅取决于系统的基础参数,允许我们所提出的算法有效地缩放到高维系统。作为该方法的说明,我们展示了随机近似算法学习由牛顿重力交互的十点批量组成的60维系统的预测模型的能力。
translated by 谷歌翻译
内核方法是机器学习中最流行的技术之一,使用再现内核希尔伯特空间(RKHS)的属性来解决学习任务。在本文中,我们提出了一种新的数据分析框架,与再现内核Hilbert $ C ^ * $ - 模块(rkhm)和rkhm中的内核嵌入(kme)。由于RKHM包含比RKHS或VVRKHS)的更丰富的信息,因此使用RKHM的分析使我们能够捕获和提取诸如功能数据的结构属性。我们向RKHM展示了rkhm理论的分支,以适用于数据分析,包括代表性定理,以及所提出的KME的注射性和普遍性。我们还显示RKHM概括RKHS和VVRKHS。然后,我们提供采用RKHM和提议的KME对数据分析的具体程序。
translated by 谷歌翻译
在最近的研究中,分布式学习和随机特征的概括特性假设在假设空间中存在目标概念。但是,这种严格的条件不适用于更常见的情况。在本文中,使用精致的证明技术,我们首先将具有随机特征的分布式学习的最佳速率扩展到了不可算力的情况。然后,我们通过数据依赖性生成策略减少所需的随机特征的数量,并使用其他未标记的数据来改善允许的分区数量。理论分析表明,这些技术显着降低了计算成本,同时保留了标准假设下的最佳概括精度。最后,我们对模拟和实际数据集进行了几项实验,经验结果验证了我们的理论发现。
translated by 谷歌翻译
我们研究了估计回归函数的导数的问题,该函数的衍生物具有广泛的应用,作为未知函数的关键非参数功能。标准分析可以定制为特定的衍生订单,参数调整仍然是一个艰巨的挑战,尤其是对于高阶导数。在本文中,我们提出了一个简单的插入式内核脊回归(KRR)估计器,其非参数回归中具有随机设计,该设计广泛适用于多维支持和任意混合派生衍生物。我们提供了非反应分析,以统一的方式研究提出的估计量的行为,该估计量涵盖回归函数及其衍生物,从而在强$ l_ \ infty $ norm中导致一般核类中的一般内核的两个误差范围。在专门针对多个多项式衰减特征值核的具体示例中,提出的估计器将最小值的最佳速率恢复到估计H \ h \ offormions ofergarithmic因子的最佳速率。因此,在任何衍生词的顺序中都选择了调整参数。因此,提出的估计器享受\ textIt {插件属性}的衍生物,因为它会自动适应要估计的衍生物顺序,从而可以轻松地在实践中调整。我们的仿真研究表明,相对于几种现有方法蓝色的几种现有方法的有限样本性能有限,并证实了其最小值最优性的理论发现。
translated by 谷歌翻译
比较概率分布是许多机器学习算法的关键。最大平均差异(MMD)和最佳运输距离(OT)是在过去几年吸引丰富的关注的概率措施之间的两类距离。本文建立了一些条件,可以通过MMD规范控制Wassersein距离。我们的作品受到压缩统计学习(CSL)理论的推动,资源有效的大规模学习的一般框架,其中训练数据总结在单个向量(称为草图)中,该训练数据捕获与所考虑的学习任务相关的信息。在CSL中的现有结果启发,我们介绍了H \“较旧的较低限制的等距属性(H \”较旧的LRIP)并表明这家属性具有有趣的保证对压缩统计学习。基于MMD与Wassersein距离之间的关系,我们通过引入和研究学习任务的Wassersein可读性的概念来提供压缩统计学习的保证,即概率分布之间的某些特定于特定的特定度量,可以由Wassersein界定距离。
translated by 谷歌翻译
最近开发的基于矩阵的renyi的熵能够通过在再现内核Hilbert空间中的对称正半明确(PSD)矩阵中的EigensPectrum,而无需估计基础数据分布的情况下,能够测量数据中的信息。这种有趣的属性使得新信息测量在多种统计推理和学习任务中广泛采用。然而,这种数量的计算涉及PSD矩阵$ G $的跟踪运算符,以便为电源$ \ alpha $(即$ tr(g ^ \ alpha)$),具有近O $ o的正常复杂性(n ^ 3 )$,当样品数量(即$ N $)大时,严重妨碍了它的实际用法。在这项工作中,我们向这种新的熵功能呈现计算有效的近似,这可以降低其复杂性,以明显不到$ O(n ^ 2)$。为此,我们首先将随机近似为$ \ tr(\ g ^ \ alpha)$,将跟踪估计转换为矩阵矢量乘法问题。我们扩展了$ \ Alpha $(整数或非整数)的任意值策略。然后,我们建立基于矩阵的renyi的熵和PSD矩阵近似之间的连接,这使我们能够利用群集和阻止$ \ g $的低级结构来进一步降低计算成本。理论上我们提供近似精度保证并说明不同近似的属性。综合性和现实数据的大规模实验评估证实了我们的理论发现,展示了有希望的加速,准确性可忽略不计。
translated by 谷歌翻译
我们在非标准空间上介绍了积极的确定核的新类别,这些空间完全是严格的确定性或特征。特别是,我们讨论了可分离的希尔伯特空间上的径向内核,并在Banach空间和强型负类型的度量空间上引入了广泛的内核。一般结果用于在可分离的$ l^p $空间和一组措施上提供明确的核类。
translated by 谷歌翻译
内核平均值嵌入是一种强大的工具,可以代表任意空间上的概率分布作为希尔伯特空间中的单个点。然而,计算和存储此类嵌入的成本禁止其在大规模设置中的直接使用。我们提出了一个基于NyStr \“ Om方法的有效近似过程,该过程利用了数据集的一个小随机子集。我们的主要结果是该过程的近似误差的上限。它在子样本大小上产生足够的条件以获得足够的条件。降低计算成本的同时,标准的$ n^{ - 1/2} $。我们讨论了此结果的应用,以近似的最大平均差异和正交规则,并通过数值实验说明了我们的理论发现。
translated by 谷歌翻译
从大型套装中选择不同的和重要的项目,称为地标是机器学习兴趣的问题。作为一个具体示例,为了处理大型训练集,内核方法通常依赖于基于地标的选择或采样的低等级矩阵NYSTR \“OM近似值。在此上下文中,我们提出了一个确定性和随机的自适应算法在培训数据集中选择地标点。这些地标与克尼利克里斯特步函数序列的最小值有关。除了ChristOffel功能和利用分数之间的已知联系,我们的方法也有限决定性点过程(DPP)也是如此解释。即,我们的建设以类似于DPP的方式促进重要地标点之间的多样性。此外,我们解释了我们的随机自适应算法如何影响内核脊回归的准确性。
translated by 谷歌翻译
神经网络的经典发展主要集中在有限维欧基德空间或有限组之间的学习映射。我们提出了神经网络的概括,以学习映射无限尺寸函数空间之间的运算符。我们通过一类线性积分运算符和非线性激活函数的组成制定运营商的近似,使得组合的操作员可以近似复杂的非线性运算符。我们证明了我们建筑的普遍近似定理。此外,我们介绍了四类运算符参数化:基于图形的运算符,低秩运算符,基于多极图形的运算符和傅里叶运算符,并描述了每个用于用每个计算的高效算法。所提出的神经运营商是决议不变的:它们在底层函数空间的不同离散化之间共享相同的网络参数,并且可以用于零击超分辨率。在数值上,与现有的基于机器学习的方法,达西流程和Navier-Stokes方程相比,所提出的模型显示出卓越的性能,而与传统的PDE求解器相比,与现有的基于机器学习的方法有关的基于机器学习的方法。
translated by 谷歌翻译
To accelerate the training of kernel machines, we propose to map the input data to a randomized low-dimensional feature space and then apply existing fast linear methods. The features are designed so that the inner products of the transformed data are approximately equal to those in the feature space of a user specified shiftinvariant kernel. We explore two sets of random features, provide convergence bounds on their ability to approximate various radial basis kernels, and show that in large-scale classification and regression tasks linear machine learning algorithms applied to these features outperform state-of-the-art large-scale kernel machines.
translated by 谷歌翻译
过度参数化神经网络(NNS)的小概括误差可以通过频率偏见现象来部分解释,在频率偏置现象中,基于梯度的算法将低频失误最小化,然后再减少高频残差。使用神经切线内核(NTK),可以为训练提供理论上严格的分析,其中数据是从恒定或分段构剂概率密度绘制的数据。由于大多数训练数据集不是从此类分布中汲取的,因此我们使用NTK模型和数据依赖性的正交规则来理论上量化NN训练的频率偏差,给定完全不均匀的数据。通过用精心选择的Sobolev规范替换损失函数,我们可以进一步扩大,抑制,平衡或逆转NN训练中的内在频率偏差。
translated by 谷歌翻译
内核平均嵌入是表示和比较概率度量的有用工具。尽管具有有用性,但内核的意思是考虑无限维度的特征,在差异私有数据生成的背景下,这是具有挑战性的。最近的一项工作建议使用有限维的随机特征近似数据分布的内核平均值嵌入,从而产生可分析的敏感性。但是,所需的随机特征的数量过高,通常是一千到十万,这会使隐私准确的权衡加剧。为了改善权衡取舍,我们建议用Hermite多项式特征替换随机功能。与随机特征不同,储能多项式特征是排序的,其中低订单的特征包含的分布更多的信息比高订单处的分布更多。因此,与明显更高的随机特征相比,HERMITE多项式特征的相对较低的阶多项式特征可以更准确地近似数据分布的平均嵌入。正如在几个表格和图像数据集中所证明的那样,Hermite多项式特征似乎比随机傅立叶功能更适合私人数据生成。
translated by 谷歌翻译
矩阵近似是大规模代数机器学习方法中的关键元件。最近提出的方法Meka(Si等人,2014)有效地使用了希尔伯特空间中的两个常见假设:通过固有的换档内核功能和数据紧凑性假设获得的内部产品矩阵的低秩属性块集群结构。在这项工作中,我们不仅适用于换档内核,而且扩展Meka,而且还适用于多项式内核和极端学习内核等非静止内核。我们还详细介绍了如何在MEKA中处理非正面半定位内核功能,由近似自身或故意使用通用内核功能引起的。我们展示了一种基于兰兹的估计频谱转变,以发展稳定的正半定梅卡近似,也可用于经典凸优化框架。此外,我们支持我们的调查结果,具有理论考虑因素和各种综合性和现实世界数据的实验。
translated by 谷歌翻译
近年来目睹了采用灵活的机械学习模型进行乐器变量(IV)回归的兴趣,但仍然缺乏不确定性量化方法的发展。在这项工作中,我们为IV次数回归提出了一种新的Quasi-Bayesian程序,建立了最近开发的核化IV模型和IV回归的双/极小配方。我们通过在$ l_2 $和sobolev规范中建立最低限度的最佳收缩率,并讨论可信球的常见有效性来分析所提出的方法的频繁行为。我们进一步推出了一种可扩展的推理算法,可以扩展到与宽神经网络模型一起工作。实证评价表明,我们的方法对复杂的高维问题产生了丰富的不确定性估计。
translated by 谷歌翻译
我们考虑通过复制内核希尔伯特空间的相关协方差操作员对概率分布进行分析。我们表明,冯·诺伊曼(Von Neumann)的熵和这些操作员的相对熵与香农熵和相对熵的通常概念密切相关,并具有许多特性。它们与来自概率分布的各种口径的有效估计算法结合在一起。我们还考虑了产品空间,并表明对于张量产品内核,我们可以定义互信息和联合熵的概念,然后可以完美地表征独立性,但只能部分条件独立。我们最终展示了这些新的相对熵概念如何导致对数分区函数的新上限,这些函数可以与变异推理方法中的凸优化一起使用,从而提供了新的概率推理方法家族。
translated by 谷歌翻译
本文提出了一个无网格的计算框架和机器学习理论,用于在未知的歧管上求解椭圆形PDE,并根据扩散地图(DM)和深度学习确定点云。 PDE求解器是作为监督的学习任务制定的,以解决最小二乘回归问题,该问题施加了近似PDE的代数方程(如果适用)。该代数方程涉及通过DM渐近扩展获得的图形拉平型矩阵,该基质是二阶椭圆差差算子的一致估计器。最终的数值方法是解决受神经网络假设空间解决方案的高度非凸经验最小化问题。在体积良好的椭圆PDE设置中,当假设空间由具有无限宽度或深度的神经网络组成时,我们表明,经验损失函数的全球最小化器是大型训练数据极限的一致解决方案。当假设空间是一个两层神经网络时,我们表明,对于足够大的宽度,梯度下降可以识别经验损失函数的全局最小化器。支持数值示例证明了解决方案的收敛性,范围从具有低和高共限度的简单歧管到具有和没有边界的粗糙表面。我们还表明,所提出的NN求解器可以在具有概括性误差的新数据点上稳健地概括PDE解决方案,这些误差几乎与训练错误相同,从而取代了基于Nystrom的插值方法。
translated by 谷歌翻译