机器学习实战第15章pegasos算法原理剖析以及伪代码和算法的对应关系

Pegasos原文是：
http://www.ee.oulu.fi/research/imag/courses/Vedaldi/ShalevSiSr07.pdf
还是挺长的，论文结构是：
第1~6页：主要原理
第7~15页：讲一些定理配合核函数使用的一些理论
第16~26页：实验和参考文献

对于急功近利的同学而言，这个博客就不要浪费时间看了，因为面试基本是用不到的。
因为这是这本书的最后一章，本人优点完美主义，所以还是想搞懂。

################下面是一些必备的基本知识#######################
对于subgradient
不采用国内的次梯度的翻译，一律使用子梯度的说法

子梯度下降的应用场景是？
子梯度下降就是对付非处处求导的函数的极值求解的
所以子梯度的意思就是：其实还是梯度，但是可能是多个分段函数的梯度，相邻两个分段函数之间的分界点可能导数不存在，
分界点的梯度可能是一个区间，而不是唯一的一个值，为了应对这种情况，取名叫做字梯度(sub-gradient)
而梯度下降和梯度上升都是针对所研究的函数处处可导的情况的。

先来一个案例吧：
子梯度求导参考案例：

该案例来自：
http://www.seas.ucla.edu/~vandenbe/236C/lectures/subgradients.pdf
所以看看，其实也没啥，通俗来讲：什么是子梯度下降呢？
其实就是分段求导，对于导数不存在的临界点，我们取该点左右两边的导数作为“次导数”的区间的上下限
#######################以上是一些基本知识#################
下面开始回顾SVM要解决的问题：
首先是论文P4（第4页，下同）的式（3)：
$f(w;i_t)=\frac{\lambda}{2}||w||^2+l( w;( x_{i_t},y_{i_t} ))$f(w;it​)=2λ​∣∣w∣∣2+l(w;(xit​​,yit​​))
其中$l( w;( x_{i_t},y_{i_t} ) )=max\{0,1-y·&lt;w,x&gt;\}$l(w;(xit​​,yit​​))=max{0,1−y⋅<w,x>}
$l( w;( x_{i_t},y_{i_t} ) )$l(w;(xit​​,yit​​))定義來自論文Ｐ２的式（２)

考虑子梯度求导，我们得到论文P4（第4页，下同）的式（4)：
$\triangledown_{w_t}=\lambdaｗ_t-index[y_{i_t}·&lt;w_t·x_{i_t}&gt;&lt;1 ]·y_{i_t}x_{i_t}①$▽wt​​=λｗt​−index[yit​​⋅<wt​⋅xit​​><1]⋅yit​​xit​​①
这里的index是指示函数，意思是当满足括号中的条件时，返回1，否则返回0
这么看其实还是优点晕的哈，我们把(4)写得更加清楚些，如下：
$\triangledown_{w_t}=\left\{ \begin{array}{c l} λ·w_t-y_{i_t}x_{i_t}, &amp; y_{i_t}· &lt;w_t,x_{i_t}&gt;＜1\\ λ·w_t &amp; y_{i_t}· &lt;w_t,x_{i_t}&gt; ≥1 \end{array}\right.①$▽wt​​={λ⋅wt​−yit​​xit​​,λ⋅wt​​yit​​⋅<wt​,xit​​>＜1yit​​⋅<wt​,xit​​>≥1​①
所以上面的意思其实就是，预测错误，就施加惩罚项，
没有预测错，那就维持原样。
#---------------------------------------
但是顯然，每次循環處理一條數據不太劃算，
於是啊，這裏原先的式(4)變成了論文中的式(8),如下：
$\triangledown_{w_t}=\lambdaｗ_t-\frac{1}{k}\sum_{i∈Ａ_t}index[y_{i_t}·&lt;w_t·x_{i_t}&gt;&lt;1 ]·y_{i_t}x_{i_t}②$▽wt​​=λｗt​−k1​∑i∈Ａt​​index[yit​​⋅<wt​⋅xit​​><1]⋅yit​​xit​​②

下面注意！！！！！
①與②的$\triangledown_{w_t}$▽wt​​不是同一個意思，他們有細微的差別。
在下面描述僞代碼後，結合僞代碼再說明他們的區別。
#---------------------------------------
好了，接下来说下算法的伪代码：
和书中代码对应的伪代码是论文中的Mini_batch Iterations（在论文的P5～P6）
#---------------------------下面是ｐｅｇａｓｏｓ-minibatch僞代碼------------------------------------------------
$I_{NPUT}：S,\lambda,T,k$INPUT​：S,λ,T,k
$I_{NITIALIZE}:Set　　w_1=0$INITIALIZE​:Set　　w1​=0
$F_{OR}　　 t∈[1,T]$FOR​　　t∈[1,T]
$Ｃｈｏｏｓｅ　Ａ_t⊆[m],where|A_t|=k,uniformly　at　random$　　　Ｃｈｏｏｓｅ　Ａt​⊆[m],where∣At​∣=k,uniformly　at　random
$Set　Ａ_t^{+}=\{i∈A_t:y_i·&lt;w_t,x_i&gt;&lt;1\}$　　　Set　Ａt+​={i∈At​:yi​⋅<wt​,xi​><1}
$Ｓｅｔ　\eta_t=\frac{1}{\lambda·ｔ}$　　　Ｓｅｔ　ηt​=λ⋅ｔ1​
$F_{OR}　ｊ　ｉｎ　ｒａｎｇｅ（ｋ）：$　　　FOR​　ｊ　ｉｎ　ｒａｎｇｅ（ｋ）：
$判斷當前ｂａｔｃｈ中的每條數據對應的y_ix_i)是否需要被添加入懲罰項$　　　　　判斷當前ｂａｔｃｈ中的每條數據對應的yi​xi​)是否需要被添加入懲罰項
$Ｓｅｔ　ｗ_{t+1}\longleftarrow w_t－\eta_t(\lambda w_t-\frac{1}{k}\sum_{i∈Ａ_i^{+}}y_ix_i)③$　　　Ｓｅｔ　ｗt+1​⟵wt​－ηt​(λwt​−k1​∑i∈Ａi+​​yi​xi​)③
#-------------------------------上面是ｐｅｇａｓｏｓ-minibatch僞代碼-------------------------------------#
其中：
Ｔ：最大迭代次數
ｔ：第ｔ次迭代
Ｓ：整個數據集
ｋ：$|A_t|=k$∣At​∣=k,也就是ｍｉｎｉ－ｂａｔｃｈ的數據集的數量。
我們可以看到，這個僞代碼中，居然沒有ｉｆ語句，也就是說，它被省略了。
《機器學習實戰》Ｐ２８７中，是有ｉｆ語句的，那麼這個ｉｆ語句就在上面的僞代碼中，我自己用中文添加的內循環中。
也就是說，②中的$\triangledown_{w_t}是上述僞代碼中內ｆｏｒ循環結束後的結果$▽wt​​是上述僞代碼中內ｆｏｒ循環結束後的結果
也就是說$③＝ｗ_t- \eta_t·②＝ｗ_t-\eta_t·\triangledown_{w_t}$③＝ｗt​−ηt​⋅②＝ｗt​−ηt​⋅▽wt​​
那麼①中的$\triangledown_{w_t}$▽wt​​對應僞代碼中的什麼地方呢？這個對應的是ｐｅｇａｓｏｓ算法在逐條處理數據時（也就是“非ｍｉｎｉ-batch算法”中）的③中的懲罰項（“非ｍｉｎｉ-batch算法”中的③與本文的③是不一樣的，由於和《機器學習實戰》第１５章不完全對應，所以本文沒有給出“非ｍｉｎｉ-batch算法”的僞代碼）。

算法停止迭代的条件是（论文第2页上方）：
$f(w)≤min_wf(w)+$f(w)≤minw​f(w)+ε

伪代码中$y_i$yi​与$y_{i_t}$yit​​的区别？
$y_i$yi​表示的是第i条数据的标签值
$y_{i_t}$yit​​表示的是for循环中的第t次迭代随机选中的第i条数据对应的标签值

上述算法分析對應的《機器學習實戰》第１５章中的代碼是：

def batchPegasos(dataSet, labels, lam, T, k):
    m,n = shape(dataSet); w = zeros(n); 
    dataIndex = range(m)
    for t in range(1, T+1):
        wDelta = mat(zeros(n)) #reset wDelta
        eta = 1.0/(lam*t)
        random.shuffle(dataIndex)
        for j in range(k):#go over training set 
            i = dataIndex[j]
            p = predict(w, dataSet[i,:])        #mapper code
            if labels[i]*p < 1:                 #mapper code
                wDelta += labels[i]*dataSet[i,:].A #accumulate changes  
        w = (1.0 - 1/t)*w + (eta/k)*wDelta       #apply changes at each T
    return w

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
下面是與ＳＭＯ的大致比較：
ＳＭＯ主要思想是使用ＫＫＴ＋廣義的拉格朗日，主要解決的問題就是狹義的拉格朗日(就是我們高等數學中的那個拉格朗日)只能處理等式約束，不能處理不等式約束，所以來個ＫＫＴ條件，就能使用廣義的拉格朗日了，使用形式上與狹義的拉格朗日一致，只不過
ＫＫＴ約束條件實在又多有麻煩，所以出來個ＳＭＯ解決一下。

而ｐｅｇａｓｏｓ的主要原理是對於“非處處可導”的凸函數使用，上面的描述中，“非處處可導”的凸函數指的是$l( w;( x_{i_t},y_{i_t} ) )$l(w;(xit​​,yit​​))，我們知道，感知機是用的梯度下降，那麼ＳＶＭ和感知機這麼相似，爲啥不用梯度下降呢？
因爲感知機的目標函數是處處可導的。
而ＳＶＭ的目標函數中，帶有“非處處可導”的函數$l( w;( x_{i_t},y_{i_t} ) )$l(w;(xit​​,yit​​))，所以沒辦法使用梯度下降，只能使用“子梯度下降”（ｓｕｂ－ｇｒａｄｉｅｎｔ），所以文章開頭的預備知識就是這個。
也就是說，對於ＳＶＭ的目標函數，目前處理有兩個思路：
一，滿足ＫＫＴ條件，不等式約束－>等式約束，然後使用廣義的拉格朗日（ＳＭＯ算法）。
二，使用子梯度下降，處理$l( w;( x_{i_t},y_{i_t} ) )$l(w;(xit​​,yit​​))（Ｐｅｇａｓｏｓ算法）