SMO算法陷入无限循环？

Question

我有兴趣建立一个支持向量机多类分类器，所以我目前正在实现顺序最小优化SMO。

我的实现是基于John C. Platt的“序贯最小优化快速训练支持向量机”中的伪码。

我观察到，对于某些训练例子。Smo可能会发散，并在主例程中遇到一个无限循环(以下循环)

numChanged = 0；

examineAll = 1；

时间(numChanged >0\x{ examineAll >0) {…}

可能会遇到无限的循环。

是否有防止smo算法例程陷入无限循环的线索或准则？

我要感谢你的回答。问候

Answer 1

如果需要，可以添加最大迭代条件：

while ((numChanged > 0 || examineAll) && iter < MaxIter)

但在大多数情况下，它不应该遇到无限循环，这是Platt的完整伪代码：

while (numChanged > 0 || examineAll)
{
    numChanged = 0;
    // Adding curly brackets for better readability
    if (examineAll)
    {
        loop I over all training examples
        numChanged += examineExample(I);
    }
    else
    {
        loop I over examples where alpha is not 0 & not C
        numChanged += examineExample(I);
    }

    if (examineAll == 1)
    {
        examineAll = 0;
    }
    else 
    {
        examineAll = 1;
    }
}

请注意，它正在执行一个迭代来检查示例，下一个迭代只对alpha不是0或C的示例执行相同的操作。如果在“检查所有”迭代之后没有任何更改，while循环条件将为false，因此停止循环。

因此，要使其处于无限循环中，必须有一个角的情况(可能是数值误差)，它引入振荡，使示例在检查的所有阶段发生变化，但在“仅检查α== 0和C”中不发生变化。

通常情况下，如果数据在-1,1或0,1中进行归一化，且算法的参数有合理的值，则这些角点情况将是罕见的。无论如何，如果你想格外小心，你可以把最大-iter安全网。