论文部分内容阅读
支持向量机(SVM)问题和最小包含球(MEB)问题，虽然二者的研究背景和问题的原始描述不同，但它们都是可以通过引入拉各朗日乘子，由对偶理论转换为约束条件更简单的凸二次规划问题。由于该问题的最优解具有全局性，因此在二次规划问题中对它的研究有重要的意义。本文在凸二次规划问题的框架下对上述两个问题进行了探讨和研究。
SVM的几何解释理论曾指出：在两个给定的点集间寻找最大间隔平面等价于在包含两类点集的的两个最小凸壳中寻找一对最近点。从那以后，很多学者探讨研究了不同范数意义下的分隔超平面，并声称：优化问题在L1范数意义下获得的分隔超平面比在传统L2范数意义下获得的分隔超平面的训练时间更短，对外点的稳健性更好。本文借鉴了相关的研究工作，在不同的范数下探讨了MEB和SVM的对偶形式，并给出了二者在L1、L∞范数下的对偶等价。此外，本文还就MEB已有算法进行了有益地改进，提出了两种启发式的迭代算法，并从理论分析和实验结果上对比了所提算法与已有算法的性能优劣。
在本文中，主要的工作和贡献有：
①给出了SVM问题与MEB问题在L1、L∞范数下的对偶等价，并指出：二类软间隔L1-MEB和二类硬间隔MEB在L1(L∞)范数下的间隔平面优化问题的对偶问题分别是二类软间隔L1-SVM和二类硬间隔SVM在L1(L∞)范数下的间隔平面优化问题的对偶问题的特例，为后续的研究提供了理论基础。
②利用线性规划方法在L1、L∞范数下对MEB问题进行求解，获得了比在L2范数下训练时间更短、稳健性更好的训练过程，使得在不同范数下讨论MEB问题具有了一定的现实意义。
③提出了一种基于优化软件包的改进的MEB算法，在根据与当前球心距离最远的原则向当前核心集增加核心向量的同时，再根据有理论上保证算法收敛的去点原则来缩减当前核心集，从而使得当前核心集规模最小，为后继的迭代减少计算复杂度。我们通过理论分析和实验证得到结论：在基本不改变支持向量、不降低分类正确率的前提下，该方法可以获得更少的核心向量，从而降低计算过程中的空间复杂度和时间复杂度，因此更加适合大规模数据的增量学习和数据约简。
④提出了一种不基于优化软件包的更简单的MEB算法，通过放宽对核函数的要求，获得了一种半径在逐渐扩张的更简单的MEB算法，并使得该方法在核方法中的潜在应用范围更广；同时，我们还给出了该算法的收敛性证明，也从理论上对其空间、时间复杂度进行了分析；最后，通过实验，我们得出了与其他算法相比，本文提出的更简单的MEB算法更加适合解决较大规模的数据集。
总的说来，本文在SVM问题与MEB问题的联系以及MEB算法的改进方面作了有益的探索和研究。