SVM公式詳盡推導，沒有思維跳躍。

假定資料集$T=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}，x_n \in R_k, y_n \in \{1,-1\}$線性可分,SVM的優化目標是：

優化一個超平面的引數，使得這個超平面，能夠正確劃分兩類資料，並且，距離（動詞），兩類資料最近的那個點，的距離最大。

tip: 優化一個超平面的引數指的是：調整超平面的引數值。

寫成數學公式為：

使得這個超平面，能夠正確劃分兩類資料[1]

\[y(w·x+b) > 0 \tag{1} \label{1} \]

距離（動詞），兩類資料最近的那個點，的距離最大。[2]

\[max(min(y\frac{w·x+b}{||w||})) \tag{2} \label{2} \]

假設在所有$(w,b) \in \{(w_1,b_1),(w_2,b_2),\cdots\}$中，最優解為$(w^*,b^*)$,該最優解對應的，離這個超平面最近的點為$(w_k,y_k)$，我們現在改寫$\eqref{2}$，但是畢竟是需要優化的，我們就不把最優解放到裡面去，那麼$\eqref{2}$可以改寫為：

\[max(y_k\frac{w·x_k+b}{||w||}) \]

如果要寫進去，那麼就可以寫成：

\[max(y_k\frac{w·x_k+b}{||w||}) = y_k\frac{w^*·x_k+b^*}{||w^*||} \]

我們繼續在上面的假設內，我們看到離超平面$(w^*,b^*)$最近的點，到該超平面的距離為$y_k\frac{w^*·x_k+b^*}{||w^*||}$,那麼公式$\eqref{1}$可以改寫為：

\[\frac{y(w^*·x+b^*)}{||w^*||} \geq \frac{y_k(w^*·x_k+b^*)}{||w^*||} \]

現在讓我們假設（注意，我現在已經在上面的假設上又假設了一次，相當於if語句裡面又來了個if語句，我現在還沒有說明對應的兩個else語句，只有說明了兩個else語句，所有情況才算全部討論到），我們找到了$(w^*,b^*)$，但是讓我們來看看這個解$(2w^*,2b^*)$。首先，其滿足$\eqref{2}$，另外：

\[max(y_k\frac{w·x_k+b}{||w||}) = y_k\frac{w^*·x_k+b^*}{||w^*||}=y_k\frac{2w^*·x_k+2b^*}{||2w^*||}，\\ ||2w^*||=\sqrt{(\sum{(2w_i)^2})}=\sqrt{(4\sum{w_i^2})}=2\sqrt{(\sum{w_i^2})}=2||w^*|| \]

我們再來看更一般的：

\[max(min(y\frac{w·x+b}{||w||})) =max(min(y\frac{kw·x+kb}{||kw||})),k \neq 0 \]

tip: 我這裡假設了$k \neq 0$,其實這不是假設，而是必然的結果，因為如果$k=0$，那麼超平面$(kw^*,kb^*)=(0，0)$，這是不滿足$\eqref{1}$的（把$w$和$b$均設為0，然後看看左邊是否都大於0），既然不滿足$\eqref{1}$，$(0，0)$就不是解，那麼$k=0$就不在我們的討論範圍內，所以$k \neq 0$。$k \neq 0$的原因是其不在我們的討論範圍內，而不是簡單的，聽到已經麻木了的"分母不能為0，所以$k \neq 0$"。另外，通過窮舉可以看出$ k \in R \space \and \neq 0$。

從上面的一個式子可以看出，就算我們找到了一個最優解$(w^*,b^*)$（或者我們找到的是$(2w^*,2b^*)$，但是我們可以把$(kw^*,kb^*)$記作$(w^*,b^*)$），我們可以通過給予$w$和$b$一個非零引數$k$，誕生出另一個解，但實際上集合$\{(w^*,b^*),(2.2w^*,2.2b^*),(3w^*,3b^*),...\}$都是同一個向量(如果$w$是一個n維向量,那麼$(w,b)$，可以看作一個n+1維向量。)，另外,因為$k \in R \space \and \neq 0$,$y(w·x+b) > 0$(因為$y\frac{w·x+b}{||w||}$為點$(x,y)$到超平面$(w,b)$的距離，資料集T是線性可分的，那麼該距離大於0，從而分子大於0),所以

\[y(kw·x+kb) > 0 \]

那麼優化目標可以改寫為[3]：

\[max(min(y\frac{w·x+b}{||w||})) =max(min(y\frac{kw·x+kb}{||kw||}))=max(y_k\frac{kw·x_k+kb}{||kw||})=max(\frac{1}{||k_1w||})=max(\frac{1}{||w||}), \\ s.t: \frac{y(w·x+b)}{||w||} \geq \frac{y_k(w·x_k+b)}{||w||}=\frac{1}{||k_1w||}=\frac{1}{||w||},\\k \neq 0 \]

注意：

\[max(\frac{1}{||w^*||}) \iff min(||w^*||) \iff min(\frac{1}{2}||w^*||^2) \]

所以最終優化目標為(在上面的兩個假設內）：

\[min(\frac{1}{2}||w||^2),\\ s.t \space\space y(w·x+b) \geq 1 \]

到這裡為止，SVM的推導其實還未完，因為我們是做了兩個假設才推出SVM的優化公式的，那萬一假設不滿足呢？
我們一共做了兩個假設：

假設在所有$(w,b) \in \{(w_1,b_1),(w_2,b_2),\cdots\}$中，最優解為$(w^*,b^*)$

現在讓我們假設,(xxx)，我們找到了$(w^*,b^*)$

現在讓我們討論另外的情況：

對應於假設」現在讓我們假設,(xxx)，我們找到了$(w^*,b^*)$「，如果找不到$(w^*,b^*)$怎麼辦，那就繼續找嘛，因為大假設裡面保證了最優解存在，所以$(w^*,b^*)$是一定能找到的。所以，第二個if對應的else語句就是continue，即一直找。（應該是的，既然存在，那麼就可以找到）
對應於假設」假設在所有$(w,b) \in \{(w_1,b_1),(w_2,b_2),\cdots\}$中，最優解為$(w^*,b^*)$「，如果$(w,b) \in \{\}$怎麼辦？因為資料集線性可分，那麼就存在$(w,b)$能夠正確劃分資料集,所以$(w,b) \in \{\}$不成立，那麼$(w,b) \in \{(w_1,b_1),(w_2,b_2),\cdots\}$一定成立，那麼如果沒有最優解怎麼辦？從最終的優化目標中可以看出，優化目標有下界（即值的變化範圍存在一個最小值），那麼最優解一定是存在的。所以，第一個if對應的else不用寫，因為不會走else語句。

至此，SVM的推導才算真正完成。

註釋：

線性可分:對於資料集$S$,若存在一個超平面$(w,b)$，能夠正確劃分資料集，即對於任意樣本$(x,y)$,如果$y=1$,那麼$w·x+b>0$，否則$w·x+b<0$,則（這個字對應前面的‘若’），超平面$(w,b)$可分資料集$S$,資料集$S$線性可分。

超平面:滿足某個等式（如$w·x-y+b=0$）的高維度（即$x \in R_k,k>2$)點$(x,y)$(這裡的$x$和$y$對應前面一個括號裡面的$x$和$y$)，的集合。【另外可以看這裡】

[1]:公式$\eqref{1}$的解釋，見線性可分,運運算元號‘$·$’為向量的點積運算.

[2]:公式$\eqref{2}$最裡面的公式為點到超平面的距離，見文章：高維空間中，點的超平面的距離 .

[3]:

$max(min(y\frac{kw·x+kb}{||kw||}))=max(y_k\frac{kw·x_k+kb}{||kw||})$的解釋：
對於任意一個超平面$(w,b)$可行解，都存在一個點$(x_k,y_k)$（自己在三維空間中想一下，對於某個能完全正確劃分資料集的平面$(w,b)$，都會有一個離其最近的點$(x_k,y_k)$），使得$min(y\frac{kw·x+kb}{||kw||})$=$y_k\frac{kw·x_k+kb}{||kw||}$.
$max(y_k\frac{kw·x_k+kb}{||kw||})=max(\frac{1}{||k_1w||})$的解釋：
因為$y(kw·x+kb)>0$取任何值，都會有分母對應其值，使其回到原來的值。另外可以這樣理解：不管$y(w·x+b)>0$取什麼值，都存在一個值$k_1$使得$y(k_1w·x+k_1b)=1$，所以我們可以把$y(w·x+b)$的值限制為1，至於為什麼要這麼做，應該是為了簡化表示式，但是這樣子$b$就沒法優化了，後面的優化還沒看。

可行解: 對於某個問題，如果某個結果滿足其約束條件，那麼該結果就是該問題的可行解。比如：
有以下問題：

\[min \space y,\\ s.t:\space y>= 1 \]

那麼$y=4$就是可行解，因為其滿足約束條件。