SVM分类是否总是产生独特的解决方案？

可分离的线性分类器可以有多个边界来分类数据。这就是我们选择边界具有最大裕度（对未发现数据的最小泛化误差）的原因。SVM分类是否总是产生独特的解决方案？

是否SVM分类总是产生独特的解决方案（惯于我们得到的所有可能的数据的两个最大余量边界）？

答案取决于硬边缘支持向量机和软边缘支持向量机？

来源

2012-09-26 Jayaprakash Sundararaj

你可以重新提个问题一点。 SMO（顺序最小优化）算法是否能保证全局最优结果？维基百科在这方面没有太多帮助... –

SMO与是否存在全局最优无关。这是优化问题本身的性质（例如，它是否凸起）。考虑到目标函数和约束条件，SMO只是获得某种解的一种数值方法。你可以给SMO一个带有许多局部最优解的非凸问题，然后不能保证找到的解决方案。 – ely

是的，标准支持向量机的软硬配方都是凸优化问题，因此具有独特的全局最优解。我想如果问题非常严重，那么近似方法就会很吝啬，以至于你会使用它们而不是精确求解器，然后你的数值求解技术可能无法找到全局最优值，纯粹是因为它的折衷好处是减少了搜索时间。

典型的做法是，这些序列最小优化 - 保持固定的一些变量，并优化了变量的一小部分，然后用不同的变量重复一遍又一遍，直到你能不能改善目标函数。鉴于此，我发现任何人都会以不会产生全球最佳的方式来解决这些问题，这是不合理的。

当然，您发现的全局最优可能并不适合您的数据;这取决于你的模型，嘈杂的类标签等等如何表示数据生成过程。所以解决这个问题并不能保证你找到了绝对正确的分类器或任何东西。

这里有一些讲义我粗略搜索发现这个问题：（link）

下面是关于凸一个更直接的联系声称：（link）

来源

2012-09-26 21:10:50 ely

凸优化问题没有独特的解决方案。你需要严格的凸性。 – DavidR

这似乎不相关。 – ely

对于凸问题，每个局部最小值是全局最小值，但可能有多个最小值（例如，函数f（x）= 0是凸的并且在任何地方都被最小化）。在严格凸的情况下，任何局部极小值都是唯一的全局极值。但即使是严格凸的目标函数也可能根本没有最小化器，例如， F（X）= 1/X。对于硬边缘SVM，如果我们只有一个类的数据，那么就没有解决方案。（如果数据是可分的话，虽然存在并且是唯一的）。对于软边际，如果存在未规范化的偏差b，则可以得到多个解。 – DavidR

对于没有正则化问题SVM可转化为矫顽二次规划问题线性约束硬间隔分类（假设的溶液/缘阳性存在）。具有线性约束的强制二次规划问题具有独特的全局最小值，并且简单的优化方法（如梯度下降或感知器算法）可保证收敛到全局最小值。例如见

http://optimization-online.org/DB_FILE/2007/05/1662.pdf

对于软间隔支持向量机和正则化方面支持向量机，我觉得也有独特的全球最小和常用技术收敛到全局最小的，但我不知道，覆盖任何样张所有的可能性。

来源

2012-09-26 20:27:57

SVM分类是否总是产生独特的解决方案？

回答

相关问题