网站流量好难做,西安建设网站制作,免费的毕业设计网站建设,网站建设合同黑客攻击这是一篇来自JMLR的论文#xff0c;论文主要关注稀疏主成分分析#xff08;Sparse PCA#xff09;的问题#xff0c;提出了一种新颖的几何解法#xff08;GeoSPCA#xff09;。
该方法相比传统稀疏PCA的解法的优点#xff1a;1#xff09;更容易找到全局最优#xff…这是一篇来自JMLR的论文论文主要关注稀疏主成分分析Sparse PCA的问题提出了一种新颖的几何解法GeoSPCA。
该方法相比传统稀疏PCA的解法的优点1更容易找到全局最优2计算效率更高3因为不再需要计算存储整个协方差矩阵所以对存储资源需求更少4GeoSPCA能够一次性构建所有主成分而不是通过迭代的方式逐步添加这有助于避免因迭代过程中的数据秩减而导致的信息损失。
这个笔记不会记录原文中过于数学的证明和推理部分仅整理原理、结论和算法流程等。对数学推理感兴趣的可自行到以下地址查看原文
https://www.jmlr.org/papers/volume24/22-0088/22-0088.pdf
1什么是稀疏PCA
首先给不了解的读者补充一下稀疏PCA概念
普通PCA得到的主成分有大量非0的原始变量所以主成分其实是不太清晰的。稀疏PCA通过减少构建主成分的变量数量可以提高模型的可解释性、预测能力或降低操作成本。相比较而言稀疏PCA更适用于需要模型解释性的场景。
稀疏PCA 在普通PCA的基础上引入了一个惩罚函数。这样做的目的是使得大部分系数变为零从而凸现出主成分的主要部分。
稀疏PCA的实现通常涉及到在标准的PCA优化问题中加入一个正则化项以促使某些系数变为零。 2现有稀疏PCA计算方式的缺陷
大多数现有方法通过迭代方式构建主成分PCs这些方法通常无法保证整体最优解且计算成本较高。 3本文提出的GeoSPCA方法
这种方法通过将问题转化为一个二元线性优化问题BLO来近似原始问题从而绕开了非凸优化的问题。
GeoSPCA算法一次性构建所有主成分而不是通过迭代的方式。这种方法通过引入一个参数η来近似原始问题并通过一系列切割平面算法cut generation algorithm来逐步改进解。
切割平面算法的核心思想是逐步添加约束条件即切割平面以逼近问题的最优解。 3.1 整体流程思路 初始化算法开始时首先解决一个没有额外约束的基本二元线性优化问题BLO以获得初始解。 计算当前解的正交投影对于当前解计算数据矩阵在由当前解定义的子空间上的正交投影。 检查投影误差计算当前解的正交投影与原始数据矩阵之间的差异即误差。如果这个误差小于预设的阈值η当前解就是可接受的。 生成切割平面如果投影误差超过阈值η算法会生成一个新的线性约束切割平面该约束会排除当前解迫使算法在下一次迭代中寻找更好的解。 迭代过程将新生成的切割平面添加到优化问题中并重新解决BLO问题以获得新的解。这个过程会不断重复直到找到满足误差阈值的解或达到预设的迭代次数。 终止条件算法在以下情况下终止1找到一个满足误差阈值η的解。2达到预设的最大迭代次数。3无法进一步改进当前解。
注其中线性约束也称为切割平面或切割约束是一种限制变量取值范围的表达式它以线性方程或不等式的形式出现。 3.2 具体落实的算法
在具体落实层面原文提出了2个算法。
算法1在给定参数η的情况下找到一组最优支持Optimal support这些支持用于构建稀疏主成分。
算法2是从较大的η值开始逐步细化η的值以逼近最优的η值同时也获得稀疏PCA的最优解。 算法1
算法步骤如下 初始化开始时使用一个二元线性优化BLO问题目标是最大化数据矩阵列的范数加权和约束条件是支持的大小不超过k。 求解BLO问题使用BLO求解器找到当前问题的最优解 s∗。 计算正交投影对找到的解 s∗计算数据矩阵在由解 s∗ 定义的子空间上的正交投影并求解PCA以得到对应的主成分。 检查投影误差计算正交投影与原始数据矩阵之间的Frobenius范数误差 η(s∗)。注两个矩阵之间的Frobenius范数一般指的是两个矩阵差的Frobenius范数也就是同位置元素相减后的平方和的平方根 生成切割平面如果误差 η(s∗)超过给定的阈值η则生成一个新的线性约束切割平面将其添加到BLO问题中以排除当前解。 迭代重复求解BLO问题并根据需要生成和添加新的切割平面直到找到满足误差阈值的解。 返回结果算法返回找到的支持集这些支持集定义了稀疏主成分。 算法2
算法步骤如下 初始化设置初始η值 η0和最优解的η值 η∗ 为较大的值。 迭代过程进行多次迭代每次迭代使用算法1来求解当前η值下的BLO问题。 更新η值如果当前解的η值 ηt小于 η∗并且当前解的函数值 f(ηt) 高于 η∗则更新 η∗为 ηt并减小η值以进行下一步迭代。 检查停止条件如果经过λ次迭代后没有改进或者达到预设的迭代次数则停止迭代。 返回结果算法返回找到的近似最优解的支持集 s∗以及对应的η值 η∗和函数值 f(η*)。
