Pegasos原文是：
http://ttic.uchicago.edu/~nati/Publications/PegasosMPB.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}))$
其中$l(w;(x_{i_t},y_{i_t}))=max\{0,1?y?<w,x>\}$
$l(w;(x_{i_t},y_{i_t}))$定義來自論文P2的式（２)

考慮子梯度求導，我們得到論文P4（第4頁，下同）的式（4)：
${▽}_{w_t}=\lambda {ｗ}_t?index[y_{i_t}?<w_t?x_{i_t}><1]?y_{i_t}{x}_{i_t}①$
(Pegasos Algorithm)
這里的index是指示函數，意思是當滿足括號中的條件時，返回1，否則返回0
這么看其實還是優點暈的哈，我們把(4)寫得更加清楚些，如下：
${▽}_{w_t}=\{\begin{array}{cl}\lambda ?w_t?y_{i_t}{x}_{i_t},& y_{i_t}?<w_t,x_{i_t}>＜1\\ \lambda ?w_t& y_{i_t}?<w_t,x_{i_t}>\ge 1\end{array}①$
所以上面的意思其實就是，預測錯誤，就施加懲罰項，
沒有預測錯，那就維持原樣。
#---------------------------------------
但是顯然，每次循環處理一條數據不太劃算，
於是啊，這裏原先的式(4)變成了論文中的式(8),如下：
${▽}_{w_t}=\lambda {ｗ}_t?\frac{1}{k}{\sum }_{i\in {Ａ}_t}index[y_{i_t}?<w_t?x_{i_t}>$<$1]?y_{i_t}{x}_{i_t}②$
(Mini_Batch　Pegasos　Algorithm)

下面注意！！！！！
①與②的${▽}_{w_t}$不是同一個意思，他們有細微的差別。
在下面描述僞代碼後，結合僞代碼再說明他們的區別。
#---------------------------------------
好了，接下來說下算法的偽代碼：
和書中代碼對應的偽代碼是論文中的Mini_batch Iterations（在論文的P5～P6）
#---------------------------下面是Mini_Batch　Pegasos　Algorithm僞代碼------------------------------------------------
$I_{NPUT}：S,\lambda ,T,k$
$I_{NITIALIZE}:Set{w}_1=0$
$F_{OR}t\in [1,T]$
$Choose{Ａ}_t?[m],where|A_t|=k,uniformlyatrandom$
$Set{Ａ}_t^{+}=\{i\in A_t:y_i?<w_t,x_i><1\}$
$Ｓｅｔ{\eta }_t=\frac{1}{\lambda ?ｔ}$
$F_{OR}\text{j?in?range(k):}$
$判斷當前batch中的每條數據對應的y_i{x}_i)是否需要被添加入懲罰項$
$Set{ｗ}_{t+1}?w_t－{\eta }_t(\lambda w_t?\frac{1}{k}{\sum }_{i\in {Ａ}_i^{+}}{y}_i{x}_i)③$
#-------------------------------上面是Mini_Batch　Pegasos　Algorithm僞代碼-------------------------------------#
其中：
Ｔ：最大迭代次數
ｔ：第ｔ次迭代
Ｓ：整個數據集
ｋ：$|A_t|=k$,也就是mini-batch的數據集的數量。
我們可以看到，這個僞代碼中，居然沒有if語句，也就是說，它被省略了。
《機器學習實戰》P287中，是有if語句的，那麼這個if語句就在上面的僞代碼中，我自己用中文添加的內循環中。
也就是說，②中的${▽}_{w_t}是上述僞代碼中內for循環結束後的結果$
也就是說$③＝{ｗ}_t?{\eta }_t?②＝{ｗ}_t?{\eta }_t?{▽}_{w_t}$

那麼①中的${▽}_{w_t}$對應僞代碼中的什麼地方呢？
這個對應的是"Pegasos　Algorithm"的③中的懲罰項
（**$\underline{PegasosAlgorithm}$與本文的$\underline{Min{i}_{B}atchPegasosAlgorithm}$**是不一樣的，由於和《機器學習實戰》第15章不完全對應，所以本文沒有給出$\underline{Min{i}_{B}atchPegasosAlgorithm}$的僞代碼）。

算法停止迭代的條件是（論文第2頁上方）：
$f(w)\le mi{n}_{w}f(w)+$ε

偽代碼中$y_i$與$y_{i_t}$的區別？
$y_i$表示的是第i條數據的標簽值
$y_{i_t}$表示的是for循環中的第t次迭代隨機選中的第i條數據對應的標簽值

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

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 wDeltaeta = 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 codeif labels[i]*p < 1: #mapper codewDelta += labels[i]*dataSet[i,:].A #accumulate changes w = (1.0 - 1/t)*w + (eta/k)*wDelta #apply changes at each Treturn w

＃＃＃＃＃＃＃＃＃＃＃＃＃pegasos的算法復雜度分析＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
論文講了兩個東西：原始版本的pegasos和mini-batch的pegasos
論文中只給出了原始版本（非mini-batch的pegasos）的算法的復雜度，
下面是原始版本的偽代碼和《機器學習實戰》上的代碼：
原始版本的pegasos偽代碼：

原始版本的pegasos的《機器學習實戰》上第十五章給出的實現代碼

def seqPegasos(dataSet, labels, lam, T):#這個對應論文中的Pegasos Algorithm（Fig.1）m,n = shape(dataSet); w = zeros(n)for t in range(1, T+1):i = random.randint(m)eta = 1.0/(lam*t)p = predict(w, dataSet[i,:])if labels[i]*p < 1:w = (1.0 - 1/t)*w + eta*labels[i]*dataSet[i,:]else:w = (1.0 - 1/t)*wprint wreturn w

下面分析復雜度為什么是論文中提到的：
$\Omega （\frac{d}{\lambda ?}）$
注意這里的復雜度的單位不再是傳統算法中常見的“一次循環”=Ω（1）
這里的Ω（1）=一次計算機底層運算

這里的d是每一條數據的維度，其實也就是最終求解目標w的維度
代碼中的$\frac{1}{t}=\eta \lambda$其實就是$\lambda ?$
所以當數據的非0維度是d時
那么整個循環的復雜度等于$\Omega （\frac{dT}{\lambda ?}）$->$\Omega （\frac{d}{\lambda ?}）$

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

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

總結

以上是生活随笔為你收集整理的机器学习实战第15章pegasos算法原理剖析以及伪代码和算法的对应关系的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。