支持向量機的論文使用順序最小優化混淆細節

Question

最近，我一直在嘗試使用Platt（1998）使用順序最小優化來學習Suppor向量機。這是他們的原皮：

http://research.microsoft.com/apps/pubs/?id=68391

這裏是另一個鏈接：

http://www.cs.iastate.edu/~honavar/smo-svm.pdf

第二個環節介紹了原始論文的實現細節，包括C++源代碼可以是從這裏下載： ftp://www.ai.mit.edu/pub/users/tlp/projects/svm/svm-smo/

（代碼不會運行，但是，由於drand_48（）的一些問題，函數僅在Linux上可用，但我已經具有該函數的源代碼，並且代碼不需要很長時間就可以運行）

但是，在它們的實現中存在一些奇怪和令人困惑的細節： 1）在第一連桿，第10頁，過程takeStep（I1，I2），有一個行：

if |a2 - alpha2 | < eps* (a2 + alpha2 + eps) 
      return 0; 

其中A2是「新的」拉格朗日乘數和α2是「舊」之一。我不太明白這條線是幹什麼的。我所知道的是，在這個函數中：首先它試圖找到2個拉格朗日乘子，用一些條件（即y1 * alpha1 + y2 * alph2 = const）使目標函數最小化（或最大化，如第二個鏈接）那麼它必須根據KKT條件進行檢查（2個alpha必須放在一個盒子裏（0，C）（0，C））。它通過找到一階導數消失的點來實現，然後檢查該點的二階導數以確定它是否是最小值，如果不是，則檢查邊界處的目標函數（L和H中的文件）。 SMO會將拉格朗日乘子移動到具有最低目標函數值的終點。

下面是從第一紙張的摘錄：

「如果目標函數是在兩端具有相同的（一個小的ε爲舍入誤差內）和內核服從Mercer的條件，則該接頭最小化不能使進展。」 （第8頁）

我想這是描述行的意思，但我不明白它是如何工作的！

2）（19）：6頁複雜的公式在第8頁，第一篇論文：我不明白他們的意思。 非常感謝！

Answer 1

12.3的僞代碼讀取

if (|a2 - alph2| < eps*(a2+alpa2+eps)) 
    return 0; 

eps是ε，小量，小舍入誤差。因此，如果絕對（正）差過小，則下一行會產生一個微小的值

a1 = alph1+s*(alph2-a2) 

所以函數終止，因爲該功能不能用這麼小的增量前進。