大规模核学习的亚线性算法

发布时间：2021-04-23 11:35

　　支持向量机（Support Vector Machines,SVM）与惩罚逻辑斯蒂回归（Penalty Logistic Regression,PLR）是机器学习中两种重要的核学习方法,具有完善的理论基础。对于原始空间中的线性不可分问题,SVM和PLR都可以通过核方法将数据映射至高维线性可分的空间中进行分类。在这种情况下,其对应线性模型的性能远不如非线性模型。然而,非线性核学习问题的计算时间复杂度理论上不会低于O n²,其中n为训练样本的规模。这使得非线性SVM和PLR的应用难以扩展至大规模数据集。为此,本文分别设计非线性SVM的两种亚线性时间优化算法和PLR的一种亚线性时间优化算法。首先,基于梯度下降的优化方法设计非线性SVM的亚线性优化算法。算法的每次迭代包括一个梯度下降更新步和一个投影步。在算法的每次迭代过程中应用随机傅里叶特征映射将采样得到的样本映射至随机傅里叶特征空间执行上述步骤,使得算法单次迭代的时间复杂度为常数。推导出算法的收敛率,并证明算法返回对应目标优化问题ε近似解的时间复杂度是独立于样本规模的。进一步,将SVM中的损失函数替换为指数损失函数,可... 

【文章来源】：天津大学天津市 211工程院校 985工程院校 教育部直属院校

【文章页数】：49 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第1章 绪论
    1.1 研究背景
    1.2 本文工作
    1.3 章节安排
第2章 文献综述
    2.1 亚线性算法概述
        2.1.1 亚线性算法的基本概念
        2.1.2 亚线性算法的分类
    2.2 SVM与 PLR的研究现状
        2.2.1 大规模SVM与 PLR的研究现状
        2.2.2 亚线性SVM与 PLR的研究现状
        2.2.3 存在的问题
第3章 非线性核学习的亚线性时间算法
    3.1 非线性核学习
        3.1.1 非线性SVM
        3.1.2 非线性PLR
        3.1.3 随机傅里叶特征映射
    3.2 基于梯度下降的非线性核学习亚线性算法
        3.2.1 非线性SVM的梯度下降优化算法
        3.2.2 非线性PLR的梯度下降优化算法
    3.3 基于子集选择技术的非线性核学习亚线性算法
        3.3.1 改进的亚线性原始-对偶算法
        3.3.2 非线性SVM的子集选择优化算法
    3.4 小结
第4章 实验
    4.1 实验设置
    4.2 性能评估
    4.3 收敛性评估
    4.4 小结
第5章 结语
    5.1 总结
    5.2 展望
参考文献
发表论文和参加科研情况说明
致谢



本文编号：3155254