SMO算法运行陷入死循环？

Question

我有兴趣构建 SVM 多 class classifier，所以我目前正在实施顺序最小优化 SMO。

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

我观察到某些训练示例。 Smo 可能发散运行进入无限循环主程序中的以下循环

numChanged = 0;

examineAll = 1;

while (numChanged > 0 || 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 的示例执行相同的操作。如果 "examine all" 迭代后没有任何变化， while 循环条件将为假，因此停止循环。

因此，对于处于无限循环中的那个，必须有一个极端情况（可能是数字错误），它会引入振荡，使示例在检查所有阶段发生变化，但在 "examine only alpha == 0 and C" 中不会发生变化。

通常，如果数据在 [-1,1] 或 [0,1] 中归一化并且算法的参数具有合理的值，则这些极端情况将很少见。无论如何，如果您想格外小心，可以放置 max-iter 安全网。

SMO算法运行陷入死循环？

SMO algorithm running into infinite loop?

optimization

machine-learning

svm