svm理論與實驗之3: 線性分類器(續集)

徐海蛟博士 Teaching

對于文本分類這樣的不适定問題（有一個以上解的問題稱為不适定問題），需要有一個名額來衡量解決方案（即我們通過訓練建立的分類模型）的好壞，而分類間隔是一個比較好的名額。

  在進行文本分類的時候，我們可以讓計算機這樣來看待我們提供給它的訓練樣本，每一個樣本由一個向量（就是那些文本特征所組成的向量）和一個标記（标示出這個樣本屬于哪個類别）組成。如下：

  Di=(xi,yi)

  xi就是文本向量（維數很高），yi就是分類标記。

  在二進制的線性分類中，這個表示分類的标記隻有兩個值，1和-1（用來表示屬于還是不屬于這個類）。有了這種表示法，我們就可以定義一個樣本點到某個超平面的間隔：

  δi = |wxi b| = yi(wxi b)

  這個公式乍一看沒什麼神秘的，也說不出什麼道理，隻是個定義而已，但我們做做變換，就能看出一些有意思的東西。

  首先注意到如果某個樣本屬于該類别的話，那麼wxi b>0（記得麼？這是因為我們所選的g(x)=wx b就通過大于0還是小于0來判斷分類），而yi也大于0；若不屬于該類别的話，那麼wxi b<0，而yi也小于0，這意味着yi(wxi b)總是大于0的，而且它的值就等于|wxi b|！（也就是|g(xi)|）

  現在把w和b進行一下歸一化，即用w/||w||和b/||w||分别代替原來的w和b，那麼間隔就可以寫成

  這個公式是不是看上去有點眼熟？沒錯，這不就是解析幾何中點xi到直線g(x)=0的距離公式嘛！（推廣一下，是到超平面g(x)=0的距離， g(x)=0就是上節中提到的分類超平面）

  小Tips：||w||是什麼符号？||w||叫做向量w的範數，範數是對向量長度的一種度量。我們常說的向量長度其實指的是它的2-範數，範數最一般的表示形式為p-範數，可以寫成如下表達式

  向量w=(w1, w2, w3,…… wn)

  它的p-範數為:

  看看把p換成2的時候，不就是傳統的向量長度麼？當我們不指明p的時候，就像||w||這樣使用時，就意味着我們不關心p的值，用幾範數都可以；或者上文已經提到了p的值，為了叙述友善不再重複指明。

  當用歸一化的w和b代替原值之後的間隔有一個專門的名稱，叫做幾何間隔，幾何間隔所表示的正是點到超平面的歐氏距離，我們下面就簡稱幾何間隔為“距離 ”。以上是單個點到某個超平面的距離（就是間隔，後面不再差別這兩個詞）定義，同樣可以定義一個點的集合（就是一組樣本）到某個超平面的距離為此集合中離超平面最近的點的距離。下面這張圖更加直覺的展示出了幾何間隔的現實含義：

  H是分類面，而H1和H2是平行于H，且過離H最近的兩類樣本的直線，H1與H，H2與H之間的距離就是幾何間隔。

  之是以如此關心幾何間隔這個東西，是因為幾何間隔與樣本的誤分次數間存在關系：

  其中的δ是樣本集合到分類面的間隔，R=max ||xi|| i=1,...,n，即R是所有樣本中（xi是以向量表示的第i個樣本）向量長度最長的值（也就是說代表樣本的分布有多麼廣）。先不必追究誤分次數的具體定義和推導過程，隻要記得這個誤分次數一定程度上代表分類器的誤差。而從上式可以看出，誤分次數的上界由幾何間隔決定！（當然，是樣本已知的時候）

  至此我們就明白為何要選擇幾何間隔來作為評價一個解優劣的名額了，原來幾何間隔越大的解，它的誤差上界越小。是以最大化幾何間隔成了我們訓練階段的目标。