【機器學習】算法原理詳細推導與實現(xiàn)(四):支持向量機(上)

在之前的文章中，包括線性回歸和邏輯回歸，都是以線性分界線進行分割劃分種類的。而本次介紹一種很強的分類器【支持向量機】，它適用于線性和非線性分界線的分類方法。

函數(shù)間隔概念

為了更好的理解非線性分界線，區(qū)別兩種分界線對于分類的直觀理解，第一種直觀理解需要考慮 logistic 回歸，我們用一個 logistic 回歸函數(shù)表示當 $y=1$ 時概率表示為：

$\begin{split} p(y=1|x;\theta)&=h(\theta) \\ &=g({\theta}^Tx) \\ &=g(z) \\ \end{split}$

當 $h(\theta) \geq 0.5$ 時，即 ${\theta}^Tx \geq 0$ 時 $y=1$ ；同理當 $h(\theta) < 0.5$ 時，即 ${\theta}^Tx < 0$ 時 $y=0$ ?；仡?logistic 回歸的圖像如下所示：

image

由上圖可以看出：如果 ${\theta}^Tx >> 0$ 時，那么可以相當確定的預測 $y=1$ ；如果 ${\theta}^Tx << 0$ 時，那么可以相當確定的預測 $y=0$

當我們根據(jù)這樣的樣本擬合logistic 回歸得出分類器時，這樣的分類器是良好的。即對于所有的 $i$ ，如果 $y^{(i)}=1$ ，那么 ${\theta}^Tx^{(i)} >> 0$ ；如果 $y^{(i)}=0$ ，那么 ${\theta}^Tx^{(i)} << 0$ 。換句話說，如果我們根據(jù)訓練集找到了合適的參數(shù) $\theta$ ，那么我們的學習算法不僅會保證分類結果正確，更會進一步的保證對分類結果的 確定性。

假設訓練集都是線性可分隔的，即一定有一條直線可以將訓練集分開，假設 ${\theta}^Tx^{(i)} =0$ 代表中間那條分隔線，使得正樣本和負樣本到這條線的距離最大，即這條線是最優(yōu)的分隔線：

image

考慮上面3個點 A 、B和C。從圖中我們可以確定A是×類別的，然而C我們是不太確定的，B還算能夠確定。logistic 回歸強調所有的點盡可能的遠離中間那條線即可，由此可能造成如上所示，點C可能屬于o類別也可能屬于×類別，所以我們這里希望找到一個分隔線，使其所有的分類結果有足夠的 確定性，這就是logistic 回歸和支持向量機的不同點。

間隔器

函數(shù)間隔

支持向量機的符號和logistic 回歸的符號有點差別。支持向量機的取值范圍是 $y \in \{-1, 1\}$ ，而logistic 回歸的取值范圍是 $y \in \{0, 1 \}$

logistic 回歸的假設函數(shù)為：

$\begin{split} h(x)&=\theta_0x_0+\theta_1x_1+\theta_2x_2+...+\theta_nx_n \\ &=\theta^Tx \end{split}$

其中這里假設 $x_0=1$ 。而支持向量機假設 $\theta_0=b$ ，即假設函數(shù)為：

$\begin{split} h(x)&=\theta_0+\theta_1x_1+\theta_2x_2+...+\theta_nx_n \\ &=b+\omega_1x_1+\omega_2x_2+...+\omega_nx_n \\ &=\omega^Tx+b \end{split}$

即為：

$h_{w,b}(x)=g(\omega^Tx+b)$

將其假設函數(shù)映射到 $y \in \{-1, 1 \}$ 上：

$g(z)= \begin{cases} 1, & \text{z $\geq$ 0} \\ -1, & \text{z<0} \end{cases}$

給定一個訓練樣本 $(x^{(i)}, y^{(i)})$ ，那么定義支持向量機的間隔函數(shù)為：

$\hat{\gamma}^{(i)}=y^{(i)}(\omega^Tx+b)$

對于這個式子的理解是:

如果 $y^{(i)}=1$ ，為了獲得較大的函數(shù)間隔，你需要令 $(\omega^Tx+b)$ 取得較大值，即 $(\omega^Tx+b) >> 0$ ，得到的 $\hat{\gamma}^{(i)}$ 是一個大正數(shù)
如果 $y^{(i)}=-1$ ，為了獲得較大的函數(shù)間隔，那么唯一使其獲得較大值的方式是，令 $(\omega^Tx+b) << 0$ ，得到的 $\hat{\gamma}^{(i)}$ 是一個大負數(shù)

這個定義捕捉到了我們之前對于函數(shù)間隔的直觀理解的特點，在之前logistic 回歸的直觀理解中，如果 $y^{(i)}=1$ ，我們希望 $(\omega^Tx+b)$ 取較大的值；如果 $y^{(i)}=-1$ ，我們希望 $(\omega^Tx+b)$ 取較小的值，這個定義用一個公式捕捉到了，我們希望函數(shù)間隔去較大值的兩種情況。

上面定義的某一個樣本的函數(shù)間隔為： $\hat{\gamma}^{(i)}=y^{(i)}(\omega^Tx+b)$ ，那么針對全局樣本得到的一個超平面的函數(shù)間隔定義為：

$\hat{\gamma}=min\hat{\gamma}^{(i)},(i=1,2,...,m)$

代表在全部的訓練樣本上，以分類正例和負例置信度最低的那個函數(shù)間隔為準，即 函數(shù)間隔是最差的情況，也要能很好的分類正負 。

實際上，這種直觀理解存在一個小問題，要使函數(shù)間隔取較大的值是非常容易的，比如說：如果我們的參數(shù)是 $\omega$ 和 $b$ ，那么我們可以將 $\omega$ 變?yōu)樵瓉淼?code>2倍，將 $b$ 也變?yōu)樵瓉淼?code>2倍：

$\omega \to 2\omega，b \to 2b$

那么根據(jù)函數(shù)間隔的定義：

$\hat{\gamma}^{(i)}=y^{(i)}(\omega^Tx+b)$

如果把 $\omega$ 和 $b$ 變?yōu)樵瓉淼?code>2倍，那么我可以很容易的使函數(shù)間隔加倍。所以單純的以最大化函數(shù)間隔為目標是沒有多大意義的，因為通過對參數(shù)翻倍就可以使函數(shù)間隔獲得任意大的值，也許我們可以解決這個問題。通過添加一個正規(guī)化條件，使得 $\omega$ 的長度為1，即 $||\omega||=1$

幾何間隔

分類器的確定邊界會由平面給出，假設存在一個 $B$ 點在分割面上，其他任何一點，比如 $A$ 點到分割面的距離，這就是幾何間隔

image

那么上圖的 $A$ 點和分割面成 $90°$ 夾角，即法向量表示為 $\frac{\omega}{||\omega||}$ ， $A$ 點到分割面的距離為 ${\gamma}$ （沒有帽子的是幾何間隔，有帽子的是函數(shù)間隔 $\hat{\gamma}$ ），假設 $A$ 點的坐標為 $(x^{(i)},y^{(i)})$ ， $B$ 點的坐標為(x,y)，那么可以得到 $x=x^{(i)}-{\gamma}^{(i)}\frac{\omega}{||\omega||}$ (利用初中的幾何知識)，因為 $\frac{\omega}{||\omega||}$ 是長度為1且與超平面垂直的單位向量，用點 $x^{(i)}$ 減掉 ${\gamma}^{(i)}\frac{\omega}{||\omega||}$ 就是超平面上面點 $B$ 的 $x$ 坐標了。因為分割面上面的點都滿足 $\omega^Tx+b=0$ ，而點B在分割面上，所以也滿足 $\omega^Tx+b=0$ ，，即：

$\omega^T(x^{(i)}-{\gamma}^{(i)}\frac{\omega}{||\omega||})+b=0$

進一步化簡得到：

${\gamma}^{(i)}=\frac{\omega^Tx^{(i)}+b}{||\omega||}=(\frac{\omega}{||\omega||})^Tx^{(i)}+\frac{||\omega||}$

上述是假設已經(jīng)對樣本分好了正確的類別，那么如果點 $A$ 是樣本，即很多個類似于點 $A$ 的樣本 $(x^{(i)},y^{(i)})$ ，那么上述公式轉化為：

${\gamma}^{(i)}=y^{(i)}((\frac{\omega}{||\omega||})^Tx^{(i)}+\frac{||\omega||})$

現(xiàn)在這樣子的形式和之前的函數(shù)間隔形式非常相似，除了在這里我們對向量 $\omega$ 進行了標準化。所以像之前一樣，我們希望幾何間隔取較大的值，也就是意味著如果我們對訓練樣本進行了正確的分類，那么這些樣本在分類正確的一面距離分割面的距離越大越好，這里用乘上 $y^{(i)}$ 來判斷樣本正負分類的方向。

這里有幾個非常容易得到的結論：

如果 $||\omega||=1$ ，那么函數(shù)間隔等于幾何間隔

幾何間隔=函數(shù)間隔 / $||\omega||$

同樣，如果同時擴大 $\omega$ 和 $b$ ，那么 $||\omega||$ 也會相應的擴大，結果無影響。所以針對全局樣本得到的一個超平面的函數(shù)間隔定義為：

$\gamma=min \gamma ^{(i)},(i=1,2,...,m)$

最優(yōu)間隔分類器

最優(yōu)間隔分類器是指選擇合適的 $\gamma$ 、 $\omega$ 、 $b$ ，使得間隔最大，也就是說滿足函數(shù)：

$max_{\gamma,\omega,b}->\gamma$

$y^{(i)}(\omega^Tx+b) \geq \gamma,(||\omega||=1)$

慮幾何間隔和函數(shù)間隔的關系，即 $\gamma=\frac{\hat{\gamma}}{||\omega||}$ ，那么上面可以轉化為：

$max_{\gamma,\omega,b}->\frac{\hat{\gamma}}{||\omega||}$

$y^{(i)}(\omega^Tx+b) \geq \hat{\gamma}$

這樣子就取消了 $||\omega||=1$ 的約束了，但是目標函數(shù)目前不是凸函數(shù)，無法求得最優(yōu)值，沒發(fā)直接帶入優(yōu)化算法里面去計算，所以這里還是需要改寫一下。前面說到同時擴大 $\omega$ 和 $b$ 對結果沒有影響，但我們最后要求的仍然是 $\omega$ 和 $b$ 的確定值，不是他們的一組倍數(shù)值，因此，我們需要對 $\hat{\gamma}$ 做一些限制，以保證我們解是唯一的。這里為了簡便取 $\hat{\gamma}=1$ ，這樣的意義是將全局的函數(shù)間隔定義為 1 ，也即是將離超平面最近的點的距離定義為 $\frac{1}{||\omega||}$ 。這里解釋一下為什么這么定義，因為求解 $\frac{1}{||\omega||}$ 的最大值相當于求 $\frac{1}{2}||\omega||^2$ 的最小值，因此改寫的結果為：

$min_{\gamma,\omega,b}->\frac{1}{2}||\omega||^2$

$y^{(i)}(\omega^Tx+b) \geq 1$

這下定義變成只有線性約束了，而且是個典型的二次規(guī)劃問題（目標函數(shù)是自變量的二次函數(shù)），利用算法可以輕松求解。

拉格朗日對偶

含有等式約束形式的求解最值

這里需要用到微積分知識中的拉格朗日乘子法，它可以用來求解像這樣的優(yōu)化問題，例如在滿足一定數(shù)量的約束條件的前提下，求解最小化、最大化問題，在這里先簡要的介紹一下它的一種一般化的形式。拉格朗日乘子法是這樣的：假設有一個函數(shù) $f(\omega)$ ，你想使他最大化或者最小化，與此同時需要滿足一些約束條件：

$min_{\omega}->f(\omega)$

對于每個 $i$ ，必須保證約束函數(shù)的值為0：

$h_i(\omega)=0,i=1,2,...,l$

給定這些約束，我可以寫成向量的形式，將整個向量表示成 $h(\omega)$ ：

$\begin{bmatrix} h_1(\omega) \\ h_2(\omega) \\ ... \\ h_l(\omega) \\ \end{bmatrix} = \overrightarrow{0}$

上面表示所有的元素都是 $0$ 向量。如果像求解這個最優(yōu)化問題，利用拉格朗日乘子法，首先應該創(chuàng)建一個拉格朗日算子：

$\Gamma(\omega,\beta)=f(\omega)+\sum_{i=1}^l\beta_ih_i(\omega)$

它應該等于原始的目標函數(shù)加上這些限制函數(shù)的線性組合，這些參數(shù) $\beta_i$ 被稱為拉格朗日算子，然后解決這個問題的方法是，對每一個原始值求偏導之后將其設為0：

$\frac{\partial_{\Gamma}}{\partial_{\omega_i}}=0;\frac{\partial_{\Gamma}}{\partial_{\beta_i}}=0$

分別對 $\omega$ 和 $\beta$ 求偏導，使其偏導數(shù)等于0，理論上可以解出一個 $w^*$ 最優(yōu)解，是這個最優(yōu)解的必要條件是：存在 $\beta^*$ 使得這些偏導數(shù)的值為0。所以根據(jù)這個結論，求解的過程是：

用拉格朗日乘子法創(chuàng)建一個拉格朗日算子

之后相對于原始參數(shù) $\omega$ 和拉格朗日算子 $\beta$ 求偏導數(shù)，并令偏導數(shù)等于0

之后對方程組進行求解，最后檢查下得到的解是否確實為一個最小值

至于為什么引入拉格朗日乘子法可以求出極值，原因是 $f(\omega)$ 的 $d_{\omega}$ 變化方向受其他不等式的約束， $d_{\omega}$ 的變化方向與 $f(\omega)$ 的梯度垂直時才能獲得極值，而且在極值處， $f(\omega)$ 的梯度與其他等式梯度的線性組合平行，因此他們之間存在線性關系。(kkt條件)

含不等式約束形式的求解最值

然后我們探討有不等式約束的極值問題求法，假設不僅僅存在約束條件 $h_i(\omega)=0$ ，還存在約束條件 $g_i(\omega)\leq 0$ ，問題如下所示：

$min_{\omega}->f(\omega)$

對于每個 $i$ ，必須保證約束函數(shù) $h(\omega)$ 的值為0：

$h_i(\omega)=0,i=1,2,...,l$

對于每個 $i$ ，必須保證約束函數(shù) $g(\omega)$ 的值小于等于0：

$g_i(\omega)\leq 0,i=1,2,...,k$

給定這些約束，我可以寫成向量的形式，可以用向量表示成：

$\begin{bmatrix} h_1(\omega) \\ h_2(\omega) \\ ... \\ h_l(\omega) \\ \end{bmatrix} = \overrightarrow{0}$

$\begin{bmatrix} g_1(\omega) \\ g_2(\omega) \\ ... \\ g_k(\omega) \\ \end{bmatrix} \leq \overrightarrow{0}$

在這種情況下，既有等式約束條件也有不等式約束條件，那么利用拉格朗日乘子法，首先應該創(chuàng)建兩個拉格朗日算子：

$\Gamma(\omega,\alpha,\beta)=f(\omega)+\sum_{i=1}^k\alpha_ig_i(\omega)+\sum_{i=1}^l\beta_ih_i(\omega)$

這里的 $\alpha_i$ 和 $\beta_i$ 都是拉格朗日算子。如果按這個公式和之前的方法求解，即求解最小值 $min f(\omega)$ 會出現(xiàn)問題。因為我們求解的是最小值，而這里的 $g_i(\omega) \leq 0$ ，我們可以將 $\alpha_i$ 調整成很大的正值，來使最后的函數(shù)結果是負無窮。因此我們需要排除這種情況，即需要定義下面的函數(shù)：

$\theta_P(\omega)=max_{(\alpha,\beta:\alpha_i \geq 0)} \Gamma(\omega,\alpha,\beta)$

以上公式，假設 $g_i(\omega) \geq 0$ 或者 $h_i(\omega) \neq 0$ ，那么可以調整參數(shù) $\alpha_i$ 和 $\beta_i$ 使得 $\theta_P(\omega)$ 的最大值為正無窮。

但是當 $g_i(\omega)$ 和 $h_i(\omega)$ 滿足約束條件 $g_i(\omega)\leq 0$ 和 $h_i(\omega)=0$ 時， $\theta_p(\omega)$ 的最大值為 $f(\omega)$ 。所以上面式子可知，當 $g_i(\omega) \geq 0,h_i(\omega) \neq 0$ 時 $\theta_P(\omega)=\infty$ ，當 $g_i(\omega)\leq 0,h_i(\omega)=0$ 時 $\theta_P(\omega)=f(\omega)$ ：

$\theta_P(\omega)= \begin{cases} f(\omega), & g_i(\omega)\leq 0,h_i(\omega)=0 \\ \infty, & g_i(\omega) \geq 0,h_i(\omega) \neq 0 \end{cases}$

這樣原來要求的 $min f(\omega)$ 可以轉換成求 $min \theta_P(\omega)$ ，因為 $\theta_P(\omega)$ 的最小值為 $f(\omega)$ ， $f(\omega)$ 越小則 $\theta_P(\omega)$ 越小，即求 $min f(\omega)$ 等于求 $min \theta_P(\omega)$ ：

$min_{\omega} \theta_P(\omega)=min_{\omega} max_{(\alpha,\beta:\alpha_i \geq 0)} \Gamma(\omega,\alpha,\beta)$

拉格朗日對偶步驟

下面使用 $p^*$ 來表示 $min_{\omega} \theta_P(\omega)$ ，如果直接求解，首先面對的是兩個參數(shù) $\alpha,\beta$ ，這個過程不容易求解。因此這里引入拉格朗日對偶，即函數(shù) $\theta_P$ 的對偶函數(shù) $\theta_D$ ，它是一個以 $\alpha$ 和 $\beta$ 為變量的函數(shù)：

$\theta_D(\alpha,\beta)=min_{\omega} \Gamma(\omega,\alpha,\beta)$

由求解 $\theta_P(\omega)$ 的最小值 $min_{\omega} \theta_P(\omega)$ 的推理步驟可知， $\theta_D(\alpha,\beta)$ 求解最大值的函數(shù)為

$max_{(\alpha,\beta:\alpha_i \geq 0)} \theta_D(\alpha,\beta)=max_{(\alpha,\beta:\alpha_i \geq 0)} min_{\omega} \Gamma(\omega,\alpha,\beta)$

這個問題是原問題的對偶問題，相對于原問題只是更換了 $max$ 和 $min$ 的順序，而一般更換 $max$ 和 $min$ 順序總有如下式子成立：

$max (min(x)) \leq min (max(x))$

所以有：

$d^* \leq p^*$

$d^*=max_{(\alpha,\beta:\alpha_i \geq 0)} (min_{\omega} \Gamma(\omega,\alpha,\beta)) \leq min_{\omega} (max_{(\alpha,\beta:\alpha_i \geq 0)} \Gamma(\omega,\alpha,\beta))=p^*$

下面會解釋在什么條件下兩者會相等 $d^*=p^*$ 。

假設 $f(\omega)$ 和 $g_i(\omega)$ 都是凸函數(shù)， $h_i(\omega)=\alpha_i^T\omega+b_i$ ，并且存在 $\omega$ 使得所有的 $i$ 都有 $g_i(\omega)<0$ 。在這種假設下，一定存在 $\omega^*,\alpha^*,\beta^*$ 使得 $\omega^*$ 是原問題 $p^*$ 的解， $\alpha^*,\beta^*$ 是對偶問題 $d^*$ 的解，以及 $d^*=p^*=\Gamma(\omega^*,\alpha^*,\beta^*)$ ，這時 $\omega^*,\alpha^*,\beta^*$ 滿足kkt條件：

$\frac{\partial_{\Gamma(\omega^*,\alpha^*,\beta^*)}}{\partial_{\omega_i}}=0,i=1,2,...,n$

$\frac{\partial_{\Gamma(\omega^*,\alpha^*,\beta^*)}}{\partial_{\beta_i}}=0,i=1,2,...,l$

$\alpha_i^*g_i(\omega^*)=0,i=1,2,...,k$

$g_i(\omega^*) \leq 0,i=1,2,...,k$

$\alpha^* \geq 0,i=1,2,...,k$

如果 $\omega^*,\alpha^*,\beta^*$ 滿足了kkt條件，那么他們就是原問題和對偶問題的解。而 $\alpha_i^*g_i(\omega^*)=0,i=1,2,...,k$ 被稱作是kkt條件，這個條件隱含了如果 $\alpha^*>0$ ，那么 $g_i(\omega^*)=0$ 。也就是說， $g_i(\omega^*)=0$ 時， $\omega$ 處于邊界上，而當 $\alpha^*=0$ 時，其 $g_i(\omega^*) \leq 0$ ，即 $\omega$ 不在邊界上在可行域內(nèi)。

最優(yōu)函數(shù)間隔器

重新回到 svm 的優(yōu)化問題，在上面我們需要優(yōu)化的問題是：

$min_{\gamma,\omega,b}->\frac{1}{2}||\omega||^2$

$y^{(i)}(\omega^Tx^{(i)}+b) \geq 1 ,i=1,2,...,m$

這里將約束條件改成：

$g_i(\omega,b)=-y^{(i)}(\omega^Tx^{(i)}+b)+1 \leq 0 ,i=1,2,...,m$

而kkt條件可知，如果 $\alpha_i > 0$ 就一定意味著 $g_i(\omega,b)=0$ (因為 $\alpha_i^*g_i(\omega^*)=0,i=1,2,...,k$ )，也就是存在訓練樣本 $(x_i,y_i)$ 使得函數(shù)間隔為1，即 $g_i(\omega,b)=-y^{(i)}(\omega^Tx^{(i)}+b)+1=0$ 。它到底表示了什么可以用圖展示一下：

image

你有一些訓練樣本和一個分隔超平面，根據(jù)上面的假設 $\alpha_i > 0$ (換個說法是 $\alpha_i \neq 0$ )就一定會有函數(shù)間隔為1的樣本，即上圖中虛線部分，這些里超平面最近的樣本。在這個用圖展示的例子中，所有離超平面較遠樣本的函數(shù)間隔都大于1。

從上面圖形可以看出：通常情況下，可以發(fā)現(xiàn)只有很少數(shù)量的訓練樣本函數(shù)間隔等于1，在上面的圖中只有3個樣本的函數(shù)間隔等于1，只有少量的樣本到超平面的距離是最小距離，這些樣本我們稱之為支持向量，支持向量機的支持向量就是這個意思

支持向量的數(shù)量一般都會很少，即大多數(shù)情況下拉格朗日算子 $\alpha_i =0$ ，如果 $\alpha_i = 0$ ，那么其對應的樣本就可能不是支持向量( $g_i(\omega) \leq 0$ )。

回到上面的優(yōu)化問題，由于只有 $g_i(\omega)$ ，所以上面的拉格朗日函數(shù)：

$\Gamma(\omega,\alpha,\beta)=f(\omega)+\sum_{i=1}^k\alpha_ig_i(\omega)+\sum_{i=1}^l\beta_ih_i(\omega)$

變成：

$\Gamma(\omega,\alpha)=f(\omega)+\sum_{i=1}^m\alpha_ig_i(\omega)$

$\implies$

$\Gamma(\omega,b,\alpha)=\frac{1}{2}||\omega||^2-\sum_{i=1}^m\alpha_i[y^{(i)}(\omega^Tx^{(i)}+b)-1]$

注意到這里只有 $\alpha_i$ 沒有 $\beta_i$ 是因為原問題中沒有等式約束，只有不等式約束。

下面按照對偶問題的求解步驟，即需要定義下面的函數(shù)：：

$d^*=max_{(\alpha,\beta:\alpha_i \geq 0)} min_{\omega} \Gamma(\omega,\alpha,\beta)$

首先求解最小值 $min_{\omega} \Gamma(\omega,\alpha,\beta)$ ，對于固定的 $\alpha_i$ ， $\Gamma(\omega,\alpha,\beta)$ 的最小值只與 $\omega$ 和 $b$ 有關。所以分別對 $\omega$ 和 $b$ 求偏導：

$\nabla_{\omega}\Gamma(\omega,b,\alpha)=\omega-\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}=0$

$\implies$

$\omega=\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}$

上面得到 $\Gamma(\omega,\alpha,\beta)$ 最小值時 $\omega$ 的取值。

對 $b$ 求偏導得到：

$\frac{\partial_{\Gamma(\omega,b,\alpha)}}{\partial_{b_i}}=\sum^m_{i=1}\alpha_iy^{(i)}=0$

將上面求偏導得到的兩個式子，即代入到如下拉格朗日的函數(shù)中：

$\begin{split} \Gamma(\omega,b,\alpha)&=\frac{1}{2}||\omega||^2-\sum_{i=1}^m\alpha_i[y^{(i)}(\omega^Tx^{(i)}+b)-1] \\ &=\frac{1}{2}\omega^T\omega-\sum_{i=1}^m\alpha_iy^{(i)}\omega^Tx^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}b+\sum_{i=1}^m\alpha_i \\ &=\frac{1}{2}\omega^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}\omega^Tx^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}b+\sum_{i=1}^m\alpha_i \\ &=\frac{1}{2}\omega^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-\omega^T\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}b+\sum_{i=1}^m\alpha_i \\ &=-\frac{1}{2}\omega^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}b+\sum_{i=1}^m\alpha_i \\ &=-\frac{1}{2}(\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)})^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-b\sum_{i=1}^m\alpha_iy^{(i)}+\sum_{i=1}^m\alpha_i \\ &=-\frac{1}{2}\sum^m_{i=1}\alpha_iy^{(i)}(x^{(i)})^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-b\sum_{i=1}^m\alpha_iy^{(i)}+\sum_{i=1}^m\alpha_i \\ &=-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_iy^{(i)}(x^{(i)})^T\alpha_jy^{(j)}x^{(j)}-b\sum_{i=1}^m\alpha_iy^{(i)}+\sum_{i=1}^m\alpha_i \\ &=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_i\alpha_jy^{(i)}y^{(j)}(x^{(i)})^Tx^{(j)}-b\sum_{i=1}^m\alpha_iy^{(i)} \end{split}$

最后得到：

$\Gamma(\omega,b,\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_i\alpha_jy^{(i)}y^{(j)}(x^{(i)})^Tx^{(j)}-b\sum_{i=1}^m\alpha_iy^{(i)}$

$(x^{(i)})^Tx^{(j)}$ 即為向量內(nèi)積，簡化表達為 $<x^{(i)},x^{(j)}>$

由于前面知道，對 $b$ 求偏導時 $\sum_{i=1}^m\alpha_iy^{(i)}=0$ 時可以使 $b$ 取得最小值，所以最后一項 $b\sum_{i=1}^m\alpha_iy^{(i)}$ 的值為0，最小值 $min_{\omega} \Gamma(\omega,\alpha,\beta)$ 的式子轉化為：