如何理解感知機學習演算法的對偶形式？

11-23

李航博士的《統計學習方法》中，對於對偶形式的感知機學習演算法的原理該如何理解。可以理解原始形式的感知機學習演算法

你好，我盡量用通俗一點的話語講述這個對偶的問題。

遇到對偶問題呢，一定要先回歸基礎，不要急著去看結論：
首先，咱們了解一下【對偶】的定義是什麼，簡單的說，就是從一個不同的角度去解答相似問題，但是問題的解是相通的，甚至是一樣一樣的。ok，這個很簡單，定義咱們就不深究了。

回到樓主的問題，先給出原始問題的形式：
$min_{w,b} L(w,b) = -sum_{x_{i}in M }^{}{y_{i}(wullet x_{i} +b ) }$

現在先看原始問題的解法步驟：
首先，求解L(w,b)的梯度，求得如下偏導：
▽ $▽_{w}$ L(w,b) = - $sum_{x_{i} in M}^{}{y_{i}x_{i} }$

▽ $_{b} L(w,b) = -sum_{x_{i} in M}^{}{y_{i} }$ 其中M為誤分類點集合
然後，由於上面的偏導數是有累計加法器，咱們嘗試著去理解一下梯度演算法是怎麼用計算機實現的，這個對解答問題很重要，我們通過幾個問答的方式來掌握：
問題一、怎麼理解 A = ▽ $_{w}$ L(w,b) 這個偏導數，以及為什麼偏導算出的明明是累加 $sum_{}^{}{}$ ，但是到了演算法當中就變成了與單個 ${y_{i} x_{i} }$ 相加了，即變成下面的方式了？
$w_{1} leftarrow w_{0} + eta cdot y_{1} x_{1}$
可以這麼理解：當你已經有 i 次誤判的時候，如何調整(學習) w 這個參數，使得在下一次（即第 i+1 次）誤判的時候 L(w,b) 可以達到最小？因為 w 是參數，所以根據微積分的知識，咱們可以很快的知道，參數 w 沿著其偏導的方向變化，可以使得 L(w,b) 變動的最劇烈(因為我們需要損失函數最小)，所以我們應該在經過 i 次誤判之後，將 w 調整為 w+ k▽ $_{w}$ L(w,b) ,即
$wleftarrow w+$ k▽ $_{w}$ L(w,b) 等價於 $w leftarrow w+$ k $sum_{x_{i}in M }^{}{y_{i} x_{i} }$
此為梯度演算法！
但是，要注意一點，上面 w 的變動指的是總變動，是一次性從第1次直接跳到第i次的時候w應該有的變動，也就是 1.2.3..i-1 次誤判之後w沒有進行過任何調整，直接在第i次的時候w的變動。但是【計算機的實現的時候】跟我們人在紙上做題的思維不一樣，首先程序是串列執行的(將數據放在寄存器中，對同一個數據做加法，無法並行處理)，所以我們只能在執行了1，2，3....i-1 次w調整之後才能調整才能再次執行第 i 次的w調整，用以保證下一次失誤時，L(w,b)增長的最小。所以，我們將w的變動在計算機中編程成迭代的方式來進行,步驟如下：
1、當第一次出現誤判的時候，先將 $w_{1} leftarrow w_{0} + eta cdot y_{1} x_{1}$
2、當第二次出現誤判的時候，由於此時 $w$ 已經改變了一次了，所以只需要再累計本次的微分因子就行了： $w_{2} leftarrow w_{1} + eta cdot y_{2} x_{2}$
.....
i、當第i次出現誤判的時候，由於此時 $w$ 已經改變了(i-1)次了，所以只需要再累計本次的微分因子就行了： $w_{i} leftarrow w_{i-1} + eta cdot y_{i} x_{i}$

在書上的演算法中其實就一個 $w$ ，我是為了讓大家看到步驟才加上下標的。

PS.知道很多細緻的人會有疑問：從 $w_{1}$ 變成 $w_{2}$ 不是應該再次加上累加嗎，應該是 $w_{2} leftarrow w_{0} + eta cdot y_{1} x_{1} + eta cdot y_{2} x_{2}$ (a) 即 $w_{2} leftarrow w_{1} +sum_{x_{1},x_{2}}^{}{eta y_{i} x_{i} }$ ，為什麼是 $w_{2} leftarrow w_{1} + eta cdot y_{1} x_{1}$ (b) ？ Good question，這是個思維方式的問題，還是計算機思維，當你在感知到第k次誤分類的時候，為了讓第 k+1 次誤分類能夠盡量的減少損失，即讓L(w,b)更小，這個時候需要去求L(w,b)關於w的梯度即偏導，但是這個時候你別忘了，計算機是累加的，所以在這個步驟上，問題的形式不在是：

$min_{w,b} L(w,b) = -sum_{x_{i}in M }^{}{y_{i}(wullet x_{i} +b ) }$ （1）
而是
$min_{w,b} L(w,b) = L_{1,2...k} (w,b) -{y_{k+1}(wullet x_{k+1} +b ) }$ （2）

其中 $L_{1,2...k} (w,b)$ 是前面k次計算的固定值，是個常量(常量哈，就到就變成0了，不是變數，切記)，請看清楚上面的式子，在計算機中得到第 k+1 個樣本的時候，計算機是無法判斷樣本有沒有輸入結束的，他只能感知到本次的輸入，換句話說，感知的結尾很多的時候不是依賴於x樣本的數量，而是w,b,L損失的大小。所以是對（2）式求導，而不是（1）式，所以求導之後得到的不是(a)而是(b)，這個一定要注意，很多人看到書上說的只是知道大概是這麼個理，不敢深究，因為深究覺得有問題，其實是深究的程度不夠，僅此而已！

同上，b每次迭代的調整思路是： $bleftarrow b+eta y_{i}$ ，思路跟上面一樣，不在贅述了。

問題二、 $eta$ 是什麼東東，意義何在？數據量有限的情況下如何繼續學習的更好？
這個問題很重要，是回答樓主問題的關鍵，下面解答又不懂的地方，可能大家需要回過頭來看這個問題。
首先 $eta$ 只是學習的一個比率，例如 f(x) = $x^{2}$ ，我們求x的偏導之後得到 $f(x)^{$ = 2x，即沿著w=(1,2)的方向上走f(x)大小可以變動的最快，但是你是基於w還是基於2*w,3*w 這是你步伐的問題，係數越大肯定f(x)變動的越快，所以偏導只是指明你數據L(w,b)變動最快的方向，但是 $eta$ 指明的卻是你數據變動的快慢。實際上計算機每次迭代一下，就可以更換一個新的 $eta$ ，只是為了方便才用一個的。這就是 $eta$ 全部意義之所在。
數據有限的情況下如何學習的更好？很簡單啊，將 X 樣本集反覆的抽查使用，所以可以將 $x_{1}$ 學習3次， $x_{2}$ 學習6次，等等啦，我們將 $x_{i}$ 被學習的總次數標記為 $n_{i}$ . 這個時候，我們假設學習的時候是按照 $x_{1},x_{1},x_{2},x_{3},x_{3},x_{3},x_{4},x_{5},x_{5}$ 的順序去學習樣本，然後假設這個序列都是被誤判的樣本，這個時候很顯然N=5為樣本空間種類數量，記住不是誤判樣本的大小，而是種類，即只有 $x_{1},x_{2},x_{3},x_{4},x_{5}$ 著五個種類，N=5。好了，既然樣本這麼少，這個時候去用計算機學習 w 如何更簡單？
當然是下面這種方式啦：
$w_{i+1} leftarrow w_{i} + eta cdot n_{i}cdot y_{i} x_{i}$
所以這個時候 w 下標 i+1,不再代表第幾個誤判樣本，而代表第幾類誤判樣本的權重，在上面的 $x_{1},x_{1},x_{2},x_{3},x_{3},x_{3},x_{4},x_{5},x_{5}$ 中， $n_{1}=2,n_{2}=1,n_{3}=3,n_{4}=1,n_{5}=2$ ,
這樣看著更簡單嘛，省的迭代那麼多次，多省力啊，是吧？（一定要理解好上面這段話的內容，否則下面還是會看不懂，重點記住 $n_{i}$ 代表什麼意思,以及更好的w迭代方式）

ok，有了這個上面那些亂起八糟的鋪墊之後，咱們再來看看對偶的問題，現在w，b每次在感知到誤判的時候更好的迭代(學習)思路是：
$w_{i+1} leftarrow w_{i} + eta cdot n_{i}cdot y_{i} x_{i}$ (W)
$bleftarrow b+eta y_{i}$ (B)

好了，看到上面的問題，我們想辦法簡化一下參數的數量，所以，令
$alpha_{i} = eta cdot n_{i}$ i=1,2,....N, N為樣本中分類的數量
注意 N $e$ 迭代的次數哦，只代表種類，即不等於原表達式M的數量。好了，重頭戲來了，咱們來優化上面的問題，我們觀察到，在上面的(W)和(B)兩個表達式中，如果給定一個默認參數 $w_{0}=0$ 開始迭代，則有:
$w_{1}=w_{0} + eta cdot n_{1} cdot y_{1} x_{1} = 0 + eta cdot n_{1} cdot y_{1} x_{1} = alpha_{1} cdot y_{1} x_{1}$
我們發現測試階段是沒有未知的參數的，我們在迭代幾次試一下哈，別急，耐心點，我都打了這麼多字了，至少比你看得更累，第二次迭代： $w_{2}=w_{1} + eta cdot n_{2} cdot y_{2} x_{2} =alpha_{1} cdot y_{1} x_{1} + eta cdot n_{2} cdot y_{2} x_{2} = alpha_{1} cdot y_{1} x_{1} + alpha_{2} cdot y_{2} x_{2}$
再看第三次，
$w_{3}=w_{2} + eta cdot n_{3} cdot y_{3} x_{3} = w_{2} + alpha_{3} cdot y_{3} x_{3} = alpha_{1} cdot y_{1} x_{1}+ alpha_{2} cdot y_{2} x_{2} + alpha_{3} cdot y_{3} x_{3}$

數學歸納法吧，是吧？沒問題吧？所以 $w_{i}$ 可以如下求得：
$w_{i}=sum_{c}^{i}{alpha_{c} cdot y_{c} x_{c}}$
ok，ok，any way。現在咱們觀察上面的問題，可以得出一下幾點結論：
第一，顯而易見、到第 c 步的時候 $y_{c} x_{c}$ 已知；
第二，顯而易見、只要能夠求解出 $alpha_{1},alpha_{2},......,alpha_{c}$ ,就一定能求出 $w_{c}$ ，而且是線性運算吧，時間複雜度為O(n)；甚至如果有累加器的話，可以讓 $w_{c}=w_{c-1}+alpha_{c} cdot y_{c-1} x_{c-1}$ ,為O(1)；
第三，顯而易見、 $alpha_{i}$ 可以迭代，設置初始值 $alpha_{i}=0$ ，其中 i = 1,.....N,迭代的方式如下：
因為 $alpha_{i} = eta cdot n_{i}$ ，所以當輸入第 i 種類型的樣本的時候，相應的 $n_{i}$ 加1，表示第 i 種類型樣本又多抽查了一次，記住，不是 第i次樣本，而是第i種樣本。例如： $x_{1},x_{1},x_{2},x_{3},x_{3},x_{3},x_{4},x_{5},x_{5}$ 有9次抽樣誤判的樣本，但是只有 $x_{1},x_{2},x_{3},x_{4},x_{5}$ 五種樣本。這個很重要。
所以，每迭代一次之後 $alpha_{i}$ 的變動為： $alpha_{i} leftarrow eta (n_{i}+1)$ ,即如果抽到的是第i中類型的樣本，在其種類抽中的數量 n 上加1就可以了，其他的不變。化成迭代模式：
$alpha_{i} leftarrow eta (n_{i}+1) = eta n_{i}+ eta =alpha_{i}+eta$ 即

$alpha_{i} leftarrow alpha_{i}+eta$

所以，我們的對偶問題為，
$alpha_{i} leftarrow alpha_{i}+eta$
$bleftarrow b+eta y_{i}$

b與原始一樣，只是將對 $w$ 的迭代，轉化成了對 $alpha$ 的迭代，因為 α 要簡單的多，其計算式為： $alpha_{i} = eta cdot n_{i}$ ，都不需要考慮 $y_{i} x_{i}$ ，迭代完成求出所有的 α 之後，計算 $w$ 也是O(1)的複雜度。而且這個問題符合我開篇提到的【對偶】的定義。

寫到這裡，我想樓主的問題，我已經解答了，望採納。

首先對於高票答案中提到的更新公式為什麼不是累加和的問題，個人理解不是因為所謂的「計算機思維」問題，而是因為批量梯度下降（BGD）和隨機梯度下降（SGD）的問題。具體區別可見 @Happy dog 給出的鏈接隨機梯度下降（Stochastic gradient descent）和批量梯度下降（Batch gradient descent ）的公式對比、實現對比。

回到這個問題本身上來。其實用另一種方式來理解對偶形式的感知機模型可能會更容易理解一些。zhihu不支持latex公式，我就直接貼我筆記的截圖了。

菜鳥一枚，不知道理解上有沒有問題，歡迎大家指正。

假設按照感知機原始形式所有的參數更新一共需要n次，對偶形式就是把這n次分攤到i個樣本中去，這樣最終的參數可以展開使用每個樣本點進行表示，這樣在判斷誤分類的時候的計算就都可以展開成樣本之間的點乘形式，這樣就可以通過提前算好的Gram矩陣來大大降低計算量，因為僅僅計算了一次，後續全部通過查表就可以了。而反觀原始形式，每次參數改變，所有的矩陣計算全部需要計算，導致計算量比對偶形式要大很多。以上是我個人的理解，我也是剛看這本書，希望可以多交流一起學習

我只想說高票答案真的沒有錯誤嗎？
你們怎麼個個都看得懂....

每一個線性規劃問題，我們稱之為原始問題，都有一個與之對應的線性規劃問題我們稱之為對偶問題。原始問題與對偶問題的解是對應的，得出一個問題的解，另一個問題的解也就得到了。並且原始問題與對偶問題在形式上存在很簡單的對應關係：

目標函數對原始問題是極大化,對對偶問題則是極小化
原始問題目標函數中的收益係數（優化函數中變數前面的係數）是對偶問題約束不等式中的右端常數,而原始問題約束不等式中的右端常數則是對偶問題中目標函數的收益係數
原始問題和對偶問題的約束不等式的符號方向相反
原始問題約束不等式係數矩陣轉置後即為對偶問題的約束不等式的係數矩陣
原始問題的約束方程數對應於對偶問題的變數數,而原始問題的變數數對應於對偶問題的約束方程數
對偶問題的對偶問題是原始問題

總之他們存在著簡單的矩陣轉置，係數變換的關係。當問題通過對偶變換後經常會呈現許多便利，如約束條件變少、優化變數變少，使得問題的求解證明更加方便計算可能更加方便。

其實覺得很簡單

本來對w進行更新，要把每次具體加的數（eta yixi）加上去，而且每次的梯度與現在w的值無關，只和隨機選的xiyi的值有關

那麼我就可以用 α 記錄對每個yixi要加多少次，最後一次加上去就好了。

希望沒感覺錯。

高票答案很明顯有問題，書中明確寫了是使用隨機梯度下降法而不是全局梯度下降，更不是高票答案所說計算機實現中的問題。而原始形式和對偶形式比較我認為LeviBaymax所說的有道理，原始形式每次判斷誤分類點時都需要進行向量點乘運算，而對偶形式只需要對gram矩陣查表即可，避免了重複運算，可以提高效率。

在原始公式中的做法是直接更新參數 $w$ ；而在對偶式裡面，記錄下樣本點（實例點）由於誤分而更新的次數。如例題2.2中表2.2： $x_{1}$ 被誤分2次 $x_{2}$ 被誤分0次 $x_{3}$ 被誤分5次，對應 $alpha_{1} = 2, alpha_{2} = 0, alpha_{3} = 5$

在通過公式(2.14)和公式(2.15)就能求得參數 $w,b$

公式(2.14)： $w = sum_{i=1}^{N}alpha_{i}y_{i}x_{i}$
公式(2.15)： $b = sum_{i=1}^{N}alpha_{i}y_{i}$

這個對偶式的好處在於引入了 Gram 矩陣進行運算

最高票答案明顯有誤啊。
首先，《統計學習方法》書上在講解參數更新時，只是採用了隨機梯度下降的思想，並不是像最高票答主解釋的那樣。
其次，當學習率為1時，alpha_i代表每個樣本被錯分類的次數，所以對於每個樣本每錯分一次就要加1。
最後，所謂的對偶形式將w和b表示成了樣本（x）和標籤的（y）的線性組合，為核函數的引入提供了機會，尤其是像高斯核函數這種泰勒展開式無數項的函數，在這種情況下複雜度只與樣本數有關，且因為很多alpha其實是0，所以對優化速度會有一定提升作用。

感知機的對偶形式的推導是很簡單的，《統計學習方法》上寫得夠清楚了，這裡解釋一下動機。

對偶形式的目的是降低運算量，但是並不是在任何情況下都能降低運算量，而是在特徵空間的維度很高時才起到作用。

不妨設特徵空間是 $mathbb{R}^n$ ， $n$ 很大，一共有 $N$ 個訓練數據， $N$ 相對 $n$ 很小。我們考慮原始形式的感知機學習演算法，每一輪迭代中我們至少都要判斷某個輸入實例是不是誤判點，既對於 $x_i,y_i$ ,是否有 $y_i(wx_i+b) leq 0$ 。這裡的運算量主要集中在求輸入實例 $x_i$ 和權值向量 $w$ 的內積上， $Theta(n)$ 的時間複雜度，由於特徵空間維度很高，所以這很慢。

而在對偶形式的感知機學習演算法中，對於輸入實例 $(x_i,y_i)$ 是否誤判的條件變換為 $y_i(sum_{j=1}^{N}alpha_jy_jx_jx_i+b)leq0$ 。注意到這裡所有輸入實例都僅僅以內積的形式出現，所以我們可以預先計算輸入實例兩兩之間的內積，得到所謂的Gram矩陣 $G=[x_ix_j]_{N imes N}$ 。這樣一來每次做誤判檢測的時候我們直接在Gram矩陣里查表就能拿到內積 $x_jx_i$ ，所以這個誤判檢測的時間複雜度是 $Theta(N)$ 。

也就是說，對偶形式的感知機，把每輪迭代的時間複雜度的數據規模從特徵空間維度 $n$ 轉移到了訓練集大小 $N$ 上，那麼對於維度非常高的空間，自然就能提升性能了。

統計學習方法中關於感知機提供了原始和對偶模型，

數學中的對偶關係是指形式相似,並具有某種對稱關係一對關係式,在解題過程中,有時若能合理構造對偶關係式,並通過對這對對偶關係式進行適當的和、差、積等運算,可達到解決數學問題的目的.在解題的過程中,恰當使用對偶法,往往能使問題得到巧妙解決,收到事半功倍的效果。

對偶能給我們提供一種額外思路，但在計算上有明顯區別，原始模型簡單，對偶形式把參數w展開，複雜，可以提前算出Gram Matrix，也沒有明確複雜度得比較

看到不少人反對高票答案，似乎分歧在於書中為何要使用隨機梯度下降而非批量梯度下降法，個人搜索到的一篇博文里感覺說的有點道理，引用如下

用普通的基於所有樣本的梯度和的均值的批量梯度下降法（BGD）是行不通的，原因在於我們的損失函數裡面有限定，只有誤分類的M集合裡面的樣本才能參與損失函數的優化。所以我們不能用最普通的批量梯度下降,只能採用隨機梯度下降（SGD）或者小批量梯度下降（MBGD）。

原始鏈接在這感知機原理小結 - 劉建平Pinard - 博客園

此外，關於對偶形式的優勢，感覺後續一些答案點出來了，小結一下：

1、對偶形式將權重向量w轉化為實例x_i和標記y_i的線性組合形式，且如 @Zongrong Zheng 所述，在原書中也提到，對偶形式中的訓練實例僅以內積的形式出現，所以可以預先使用Gram矩陣存儲，也就是時間換空間的方法提高計算效率

2、如 @田海山所述書中這裡應該也有點為後續介紹支持向量機做鋪墊，所以這裡為核函數的引入埋一個伏筆，畢竟書中提到感知機是神經網路與支持向量機的基礎，而且後面書中在支持向量機部分的講解也多次使用對偶形式的求解

以上純屬個人整理的一點信息，歡迎批評指正，也歡迎訪問我的博客統計學習方法筆記(二) —— 感知機一起探討

對偶是optimization中的一個重要概念，分強對偶和弱對偶。
在linear programming的問題里，從duality提取出來的dual simplex可以極大地強化simplex的作用，尤其是有沒有解之類的問題。
在machine learning中，就像那本書里寫的，強對偶也簡化了演算法。
演算法即是建模，用數學概念簡化其形式也是重要的一個環節。

對偶形式基本思想：將w,b 表示為xi,yi的線性組合的形式，通過求解係數而得到w和b。
給我的第一感覺是： w就僅僅像是展開了而已。

It is important to note that the perceptron algorithm(primal) works by adding misclassified positive trarining examples or substracting misclassified negative ones to an initial arbitrary weight vector. Without loss of generality, we have assumed that the initial weight vector is the zero vector, and hence the final hypothesis will be a linear combination of the training points.

Once a sample training set S has been fixed, you can think of the vector alpha as alternative representation of the hypothesis in different or dual coordinates.

感知機模型是基於誤分類驅動的，對偶形式的思想是將w,b表示成為實例xi和標記yi的線性組合的形式，通過求解其係數而得到w和b。換而言是就是通過實例xi和標記yi表示w和b，書上寫的很清楚，個人認為應該就是解法不一樣吧。注意本節末作者提到的，感知機學習演算法的對偶形式和原始形式一樣，也有多個解存在，具體的解的值取決於你實例點喂進演算法的順序。

計算變得簡單而已

梯度下降過程，本質就是用輸入空間各點修正，對偶形式顯式寫出來了；
主要是對高維空間減少計算量吧