SVM公式詳盡推導，沒有思維跳躍。
- 2022 年 9 月 24 日
- 筆記
假定數據集\(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]
\]
距離（動詞），兩類數據最近的那個點，的距離最大。[2]
\]
假設在所有\((w,b) \in \{(w_1,b_1),(w_2,b_2),\cdots\}\)中，最優解為\((w^*,b^*)\),該最優解對應的，離這個超平面最近的點為\((w_k,y_k)\)，我們現在改寫\(\eqref{2}\)，但是畢竟是需要優化的，我們就不把最優解放到裏面去，那麼\(\eqref{2}\)可以改寫為：
\]
如果要寫進去，那麼就可以寫成：
\]
我們繼續在上面的假設內，我們看到離超平面\((w^*,b^*)\)最近的點，到該超平面的距離為\(y_k\frac{w^*·x_k+b^*}{||w^*||}\),那麼公式\(\eqref{1}\)可以改寫為：
\]
現在讓我們假設（注意，我現在已經在上面的假設上又假設了一次，相當於if語句裏面又來了個if語句，我現在還沒有說明對應的兩個else語句，只有說明了兩個else語句，所有情況才算全部討論到），我們找到了\((w^*,b^*)\)，但是讓我們來看看這個解\((2w^*,2b^*)\)。首先，其滿足\(\eqref{2}\)，另外：
||2w^*||=\sqrt{(\sum{(2w_i)^2})}=\sqrt{(4\sum{w_i^2})}=2\sqrt{(\sum{w_i^2})}=2||w^*||
\]
我們再來看更一般的：
\]
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),所以
\]
那麼優化目標可以改寫為[3]：
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
\]
注意：
\]
所以最終優化目標為(在上面的兩個假設內）：
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}\)最裏面的公式為點到超平面的距離，見 文章：高維空間中，點的超平面的距離 .
-
\(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\)就沒法優化了，後面的優化還沒看。
可行解: 對於某個問題，如果某個結果滿足其約束條件，那麼該結果就是該問題的可行解。比如：
有以下問題：
s.t:\space y>= 1
\]
那麼\(y=4\)就是可行解，因為其滿足約束條件。
