JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
Back to the library
人工智慧 1995

支持向量網路

科琳娜·科爾特斯 與 弗拉基米爾·瓦普尼克(AT&T 貝爾實驗室)

用最寬的間隔把兩類分開——而它落在何處,只由邊界上那幾個點說了算。

Choose your version
In depth · the introduction

在所有能把兩群點分開的直線裡,支持向量機偏偏只挑一條——留出最多迴旋餘地的那條;而正是這一個選擇,讓它的泛化如此出色。

把這個想法拆開看

假設你手裡有兩類東西——比方說垃圾郵件與正常郵件——每一封都用若干數字來描述,你想要一條規則把它們分開。從幾何上看,你是在找一條直線(在更高的維度裡,是一張平展的面),讓一類落在一邊、另一類落在另一邊。通常,許多條線都行得通。哪一條最好?

支持向量機的回答是:在兩側都留下最寬空隙的那條。它把邊界盡量推離兩類各自最近的樣本,好讓在「一個略有不同的新樣本被判錯」之前,留有盡可能多的餘地。妙的是,唯有最近的那幾個樣本——支持向量——才要緊;其餘的統統消失,這條線也不會動。

它從哪裡來

這套方法生長於 AT&T 貝爾實驗室——正是那座成就了電晶體與資訊理論的傳奇之地。弗拉基米爾·瓦普尼克在蘇聯花了幾十年,構築一套關於「學習」的數學理論;移居美國後,他與同事把它化作了一個演算法。1992 年的一篇論文,處理了兩類能被完美分開的乾淨情形。隨後在 1995 年,科琳娜·科爾特斯與瓦普尼克發表了《支持向量網路》,補上了應對雜亂、相互交疊之真實資料的關鍵能力——這套方法,就此騰飛。

它為何重要

在深度學習重新崛起之前,支持向量機是實用機器學習的主力。它準確,帶有關於「何時能夠泛化」的真正數學保證,又能借一個叫作「核技巧」的巧妙捷徑,畫出彎曲而複雜的邊界,同時仍只在求解一個簡單、性情溫良、答案唯一的問題。有十五年之久,它都是「要被打敗」的那個標杆。

一個精確的類比

想像在兩片住宅區之間,修一條盡可能寬的馬路。你不在乎深嵌在各自街區裡的房子;唯有最靠近對面的那些房子,才約束著馬路能修多寬、又該修在哪裡。那幾棟邊界上的房子,就是支持向量。挪動內部的一棟,馬路毫無變化;輕推一棟邊界上的,整條馬路就會移位。在下方的點上,親手試試。

一張兩類點的可互動散點圖,配一根旋轉筆直分界線的滑桿。對每一個角度,控件都為兩類之間那條空「街道」著色,畫出它的兩條間隔邊緣,並圈出抵住邊緣的支持向量,同時以讀數顯示當前的間隔寬度與可達到的最寬間隔;專家面板另列出間隔、最大間隔、直線角度與支持向量的數目。

它落在何處

這是機器學習的一大支脈:統計學習——它追求的是「可被證明的泛化」,而非受大腦啟發的接線方式。它與神經網路一脈同列於本館的 AI 書架——羅森布拉特的感知器、魯梅爾哈特的反向傳播,以及後來超越了它的 AlexNet 與 Transformer 等深度網路。但在 1990 與 2000 年代的大半時光裡,支持向量機一直默默地贏著。

The original document
Original source text
C. Cortes & V. Vapnik · Machine Learning 20(3): 273–297 · 1995
Abstract
The support-vector network is a new learning machine for two-group classification problems.
The machine conceptually implements the following idea: input vectors are non-linearly mapped to a very high-dimension feature space. In this feature space a linear decision surface is constructed. Special properties of the decision surface ensures high generalization ability of the learning machine.
The abstract continues that the idea had previously been implemented only for the separable case; that this paper extends it to non-separable training data; and that the resulting classifier is benchmarked against classical learning algorithms on optical character recognition.
The optimal hyperplane
The paper takes the separating boundary that maximizes the margin between the two classes as the optimal hyperplane, and shows it is determined by a small subset of the training vectors — the support vectors — which lie exactly on the margin.
Soft margin
To handle data that cannot be separated without error, the authors introduce non-negative slack variables and a penalty, allowing some points to violate the margin while keeping the boundary as wide as possible. This soft margin is the central new contribution of the 1995 paper.
Convolution of the dot-product (kernels)
Because the optimization depends on the data only through dot products, each dot product is replaced by a kernel function — equivalent to constructing the optimal hyperplane in a high-dimensional feature space without ever computing the mapping explicitly. Polynomial kernels are used in the experiments.
[ … ]
Experiments
On the U.S. Postal Service handwritten-digit benchmark the support-vector network attains an error rate of about 4%, comparable to the best competing methods of the day — evidence for the high generalization ability claimed in the abstract.
AT&T Bell Laboratories · 1995