通过硬基数约束的线性支持向量机特征选择：一种可扩展的 SDP 分解方法

Apr, 2024

通过硬基数约束的线性支持向量机特征选择：一种可扩展的 SDP 分解方法

Feature selection in linear SVMs via hard cardinality constraint: a scalable SDP decomposition approach

Immanuel Bomze, Federico D'Onofrio, Laura Palagi, Bo Peng

TL;DR我们研究了线性支持向量机（SVM）中的嵌入式特征选择问题，其中采用了基数约束，从而形成了一个完全可解释的选择模型。我们提出了两种混合整数模型，并针对其提出了新的 SDP 松弛策略。通过利用松弛策略的稀疏性模式，我们将问题进行分解，并在一个较小的锥体中获得了等效的松弛策略，使锥形方法具有可伸缩性。为了最大程度地利用分解的松弛策略，我们提出了使用其最优解信息的启发式方法。此外，通过解决一系列混合整数分解的 SDP 问题，我们提出了一种精确的过程。我们报告了在经典基准数据集上的数值实验结果，展示了我们方法的效率和效果。

Abstract

In this paper, we study the embedded feature selection problem in linear Support Vector Machines (SVMs), in which a cardinality constraint is employed, leading to a fully explainable selection model. The problem

embedded feature selection linear support vector machines cardinality constraint sdp relaxations conic approaches

发现论文，激发创造

优化与机器学习：半监督支持向量机的精确算法

支持向量机（SVM）是用于二分类的广泛研究的监督学习模型。半监督支持向量机（S3VMs）通过利用有标签和无标签数据，扩展了传统的 SVM 分类器，旨在在存在无标签数据的情况下最大化样本间的边界，以实现比传统 SVM 更高的准确性和鲁棒性。本文提出了一种新的基于半定规划（SDP）松弛的 S3VMs 分支定界方法。我们应用基于最优性的界限加强方法来限制可行集。箱约束使我们能够包括有效不等式，增强下界。与文献中提供的界限相比，所得到的 SDP 松弛提供了显著更强的界限。至于上界，则利用 SDP 松弛的解定义局部搜索。计算结果突显了该算法的效率，展示其解决数据点数量比文献中的解决数量多 10 倍的实例的能力。

Dec, 2023

关于决定 SDD 及相关分类器解释中特征成员资格的研究

本文从机器学习、解释、特征成员问题、分类器和多项式时间五个关键词出发，提出了一种能够较为高效地解决多项式时间分类器中特征成员问题的方法，并通过实验结果验证了其可行性。

Feb, 2022

使用成员预言主动学习组合优化

使用成员预测器解决未知线性约束的组合优化问题，以学习和利用替代线性约束的新框架，并通过采样策略和解决 0-1 整数线性规划来选择需要标记的新点，以提高结果的质量。

May, 2024

具有可证明保证的线性 SVM 的特征选择

给定线性支持向量机（SVM），提出了一种特征选择算法，以实现有监督或无监督的学习。算法能够在确定性和随机化的情况下运行，并且在特征空间中的误差得到保证，从而保证了与完整的特征空间相当的概括能力。在真实世界的数据集上的实验结果表明，该方法比之前的最佳方法更加高效。

Jun, 2014

使用 L1 松弛和整数规划获得稀疏主成分分析的对偶界限

本文提出了一种使用凸整数规划框架来导出 Sparse PCA 的对偶界限的方法，包括在标准半定编程（SDP）松弛中获得对偶界限的双重界限，并将其进一步放松为凸整数编程。此方法表现出在高维数据集上表现的能力，尤其是与 SDP 松弛相比，可以通过商业整数规划求解器更好地扩展。

Oct, 2018

利用半正定规划对稀疏 PCA 进行直接求解

研究在 Frobenius-norm 意义下，将正半定对称矩阵近似为一个秩为一的矩阵，其特征向量的基数有一个上限的问题以及其在协方差矩阵分解到稀疏因子等领域中的应用，提出了一个基于半定规划的方法，并讲解了 Nesterov's 平滑最小化技术在直接稀疏 PCA 方法中的应用。

Jun, 2004

面向大数据的超高维特征选择

本文提出了一种新的自适应特征缩放方案用于大数据上的超高维特征选择，解决了激活大量特征时优化速度缓慢的问题，采用特征生成方法迭代激活一组特征并通过多重核学习子问题得到最优解，通过加速近端梯度算法在原始形式中求解多重核学习子问题并采用缓存技巧加速训练，通过大量论文实验验证了方法的竞争性能。

Sep, 2012

稀疏主成分分析的精确和近似算法

该论文提出了两种混合整数 SDP，用于优化选择主子矩阵的最大特征值，进一步分析和证明了它们的理论最优性差距优于现有技术，然后解决了在解决 MISDP 时存在的计算难题，同时提出了近似算法和 MILP 模型，有效地解决了规模问题，最后将其扩展到非对称矩阵和多个协方差矩阵的情况。

Aug, 2020

组稀疏模型选择：难度和放松

本研究通过图形模型的理解和动态规划技术，基于组稀疏模型的组结构，解决了组模型选择问题，提出了一种修正的组模型，并研究了两个可操作的模型的群稀疏逼近的 Pareto 前沿以及选择和计算的权衡。

Mar, 2013

插值和 SVM 之间的新等效性：核和结构化特征

该论文介绍了一种新的和灵活的分析框架，可用于证明任意再生核希尔伯特空间中的支持向量机，并且在独立亚高斯特征和一般有界正交系统家族（例如傅里叶特征）中的特征两个方面都表现出支持向量增殖现象，这些实验未能覆盖。

May, 2023