大规模机器学习：矩阵低秩近似与在线学习

代理获取

页面导航

目录
摘要
著录项
相似文献
相关主题

摘要

在本文我们将探讨两种适合大规模计算的框架——矩阵的低秩近似和在线学习——来解决机器学习中的两个重要问题：非监督学习与监督学习。对大规模矩阵进行特征值分解是在非监督学习中最经常遇到的问题，例如核主成分分析，谱聚类。但是其三次方的算法复杂度阻碍了其在大规模数据集上的应用。另一方面，支持向量机是在监督学习中是最常用的方法。在大规模数据集中，稀疏性规约通常用来保证模型不会过拟合。然而，稀疏性规约的加入则使得优化算法异常复杂。
　　Nystrm方法是一个有效的对大规模核矩阵进行特征值分解的手段。但是，为了保证足够的的近似精度，Nystr?m方法需要从核矩阵中采样足够多的列。而在大数据集上，作用在采样的子矩阵上的SVD算法会很快凸显出耗时的缺点，以致于严重到影响Nystr?m方法的效率。在这篇文章里，我们通过使用一个近似的奇异值分解算法来对Nystr?m方法进行改进，使其可以被高效地应用在超大规模的数据集上。理论分析表明该改进后的算法和标准的Nystr?m方法一样精确。一系列在大规模数据集上的测试验证了该算法的以上特性。此外，我们还将其从在CPU上运行扩展到了在GPU上运行，从而使得8百万×8百万的核矩阵可以在1分钟之内被很好的近似。
　　Nystr?m方法的一个重要应用是在谱聚类上。然而，当数据量足够大时，谱聚类处理和存储采样列的代价仍然非常昂贵。在这篇文章里，我们提出了一个在时间和空间上同时高效的算法，使得谱聚类可以被应用在超大规模数据集上。同时被提出的还有一个一般化的正交化方法，该方法用于正交化近似得到的特征向量。我们对大量的规模从数万到数百万的数据集，进行了谱聚类实验，来测试并验证了该算法的准确和高效。更进一步，我们将其应用到图片分割上。该算法可以在1台机器上，于1分钟之内，处理千万像素的图片。
　　多样例学习是一个最近提出的监督学习框架，与传统的监督学习相比，前者能处理模糊的标号。一般来说，多样例学习被应用在离线的学习框架下。但是，诸如物体跟踪等应用并不能作用于离线框架下。因此，在基于已有成功应用的离线多样例学习算法MILES上，我们提出了一个在线的多样例学习算法。其通过在线的方法来对一个有稀疏性规约的支持向量机求解。该算法有O(√T)的（累计）后悔量上界，即，能很快收敛，且该算法性能达到了最佳解法；这里T表示迭代次数。算法的有效性在多样例分类和物体跟踪实验中被证明。

著录项

作者
李沐;
展开▼
作者单位

上海交通大学;

展开▼
授予单位上海交通大学;
学科计算机软件与理论
授予学位硕士
导师姓名吕宝粮;
年度 2011
页码
总页数
原文格式 PDF
正文语种中文
中图分类自动推理、机器学习;
关键词
机器学习; 低秩近似; 稀疏性规约; 优化算法;

相似文献

中文文献
外文文献
专利

1. 基于低秩矩阵近似的鲁棒DOA估计方法 [J] . 温超 ,徐丽云 ,段鹏婷 . 北京理工大学学报 . 2022,第2期
2. 基于奇异值分解的矩阵低秩近似量子算法 [J] . 王芙蓉 ,杨帆 ,张亚 . 物理学报 . 2021,第015期
3. 基于加权Schatten-1/2范数的低秩矩阵近似算法 [J] . 王素 ,顾颖菁 ,袁泉 . 理论数学 . 2021,第006期
4. 基于加权核范数的低秩矩阵近似及其应用 [J] . 冯伟 ,谢冬秀 . 计算机应用 . 2020,第0z1期
5. 低秩分块矩阵的核近似 [J] . 王中元 ,刘惊雷 . 智能系统学报 . 2019,第006期
6. 基于低秩矩阵近似的高光谱图像去光谱变化研究 [C] . 梅少辉 ,毕芊芊 ,吉靖宇 . 第三届全国成像光谱对地观测学术研讨会 . 2015
7. 基于局部低秩矩阵近似推荐算法研究 [A] . 陈新吾 . 2018

大规模机器学习：矩阵低秩近似与在线学习

目录

摘要

著录项

相似文献

相关主题

期刊订阅