支撐向量機(Support Vector Machine, SVM)的目的，是找到一個超平面，以盡可能的將兩類資料分開，並且間隔要愈大愈好。我們先以能完全分開的狀況來說明，以下圖的藍色和橘色兩類為例，黑色和紅色的實線都可以將兩類資料分開，但是紅色線能產生的間隔比較大，所以我們要認為紅色線比黑色線適合。

而在實務上，因為資料可能處在高維空間，因此我們會稱呼上圖的那條實線為「超平面」，而超平面的方程式可以寫成 w^⊤x + b = 0，其中 w 是超平面的法向量。因此，某個資料點 x_i 與超平面間的有符號距離 d_i，是：

d_i = y_i(w^⊤ * x_i + b) / ||w||

其中，y_i ∈ {-1, 1} 是 x_i 所屬的類別，而有符號距離 d_i 是用來判斷資料點與超平面的相對位置，與其與資料所屬類別是否一致的，若 d_i > 0 則代表一致，d_i < 0 則代表不一致。因此，我們可以構建這樣的最佳化問題：

max_{w, b} d

subject to y_i(w^⊤ * x_i + b) / ||w|| ≥ d

也就是讓最小的距離 d 盡可能的增大。而如果考慮到實際資料不太容易出現能用超平面完全分開的狀況，則最佳化問題會寫成：

max_{w, b, ξ} d - C Σξ_i

subject to y_i(w^⊤ * x_i + b) / ||w|| ≥ d - ξ_i

其中，ξ_i 代表資料點 x_i 違反間隔的程度，而 C 是用來控制「間隔最大化」與「分類錯誤容忍度」之間權衡的超參數。C 值愈大，對錯誤分類的懲罰越重，模型會盡量正確分類每個訓練點，但可能容易過擬合；C 值越小，則容許更多分類錯誤，模型較穩健但可能欠擬合。實務上，通常透過交叉驗證來選擇合適的 C 值。實際求解以上最佳化問題的方法，不在本教材的範圍內，若有興趣可以參考 Lagrange multiplier 與 dual problem 等關鍵字。

然而，在更接近真實的狀況中，資料甚至連用一個超平面大略的分開都不太可能，例如 scikit-learn 的 make_circles 產生的範例資料就是如此。因此，我們需要對空間進行變換，以將座標平方為例，就是將原始空間中，圓形的分類邊界：

w₁x₁² + w₂x₂² + b = 0

變成新空間中，直線的分類邊界：

w₁z₁ + w₂z₂ + b = 0

而在實務上，我們不必真的將資料轉換到高維空間，而是求取兩兩資料點在新空間中的內積，這樣的做法稱為 kernel method 或者 kernel trick。以把圓形分類邊界變成直線分類邊界來說，若使用 kernel method 求取內積，則可以寫成如下的式子，其中「∘」運算是 hadamard product：

K(x_i, x_j) = (x_i∘x_i)^⊤(x_j∘x_j)

上述的 kernel function 在實務上比較少見。常用的 kernel function 除了線性分割以外，有這兩個：

• Polynomial kernel: K(x_i, x_j) = (x_i^⊤x_j + c)^d，其中的 c 和 d 是超參數。
  • c 為常數項，愈大代表增加低次項的影響，使決策邊界更平滑；c 愈小代表增加高次項的影響，使決策邊界更複雜。
  • d 為次方數，愈大代表模型複雜度增加，愈小代表模型複雜度降低。
• RBF (Radial Basis Function) kernel: K(x_i, x_j) = exp(- || x_i - x_j ||² / (2 * σ²)) = exp(-γ|| x_i - x_j ||²)，對應到無限高維的空間，其中 γ = 1 / (2σ²) 是超參數。
  • γ 減小（σ 增大）代表決策邊界更平滑，模型更簡單；γ 增大（σ 減小）代表決策邊界更複雜，模型更複雜。

若有需要，你也可以設計自己的 kernel funtion，只要其所構成的 kernel matrix 是 symmetric positive semi-definite 即可，否則在求取最佳化的計算上可能會不穩定，甚至於無法計算。

我們可以使用 scikit-learn 的 svm.SVC 來幫我們執行 SVM 演算法，使用的資料集是 Wine Data Set，該資料集在 scikit-learn 有內建一版，你可以直接透過 import 相關函式來使用，不必自己下載：

import numpy as np
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC
 
dataset = load_wine()
print('Data shapes:', dataset.data.shape, dataset.target.shape)
 
X_train, X_test, y_train, y_test = train_test_split(dataset.data, dataset.target)
classes = np.unique(y_train)
print('Training data info:', X_train.shape, y_train.shape, classes)
print('Test data shapes:', X_test.shape, y_test.shape)
 
model = SVC()
model.fit(X_train, y_train)
pred = model.predict(X_test)
print('Accuracy: {:.2f}%'.format(100*np.mean(pred==y_test)))

在上述範例中，若你想要調整超參數，請參照文件；若要改為處理回歸問題，可以使用 sklearn.svm.SVR。

因為 SVM 的目標是將邊界盡量撐開，所以資料中一定會有一些點位於邊界上，這些點稱為 support vectors，也就是 SVM 名稱的由來。我們以線性可分割的狀況展示如下：

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.svm import SVC
from sklearn.model_selection import train_test_split

np.random.seed(42)
X, y = datasets.make_blobs(n_samples=100, centers=2, random_state=42, cluster_std=1.5)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

model = SVC(kernel='linear', C=1.0)
model.fit(X_train, y_train)

def plot_svm_boundary(model, X, y, title):
	plt.scatter(X[:, 0], X[:, 1], c=y)
	
	ax = plt.gca()
	xlim = ax.get_xlim()
	ylim = ax.get_ylim()
	xx = np.linspace(xlim[0], xlim[1], 200)
	yy = np.linspace(ylim[0], ylim[1], 200)
	YY, XX = np.meshgrid(yy, xx)
	xy = np.vstack([XX.ravel(), YY.ravel()]).T
	Z = model.decision_function(xy).reshape(XX.shape)

	ax.contour(
		XX, YY, Z, colors='k', levels=[-1, 0, 1], alpha=0.5, linestyles=['--', '-', '--']
	)
	

	ax.scatter(
		model.support_vectors_[:, 0],
		model.support_vectors_[:, 1],
		facecolors='none',
		edgecolors='green',
		label='Support Vectors',
	)

	plt.title(title)
	plt.legend()

plt.subplot(1, 2, 1)
plot_svm_boundary(model, X_train, y_train, 'Linear SVM - Training Set')

plt.subplot(1, 2, 2)
plot_svm_boundary(model, X_test, y_test, 'Linear SVM - Test Set')

plt.show()

print(f'Num of support vectors: {len(model.support_vectors_)}')
print(f'Acc (tr): {model.score(X_train, y_train)*100:.2f}%')
print(f'Acc (te): {model.score(X_test, y_test)*100:.2f}%')

在線性不可分割的狀況（例如 make_circles）中，不同 kernel 的效果展示如下：

from sklearn.datasets import make_circles
from sklearn.svm import SVC
import matplotlib.pyplot as plt
import numpy as np

X, y = make_circles(n_samples=200, factor=0.5, noise=0.1, random_state=42)

kernels = ['linear', 'poly', 'rbf']
titles = ['Linear Kernel', 'Polynomial Kernel (degree=3)', 'RBF Kernel']

fig, axes = plt.subplots(1, 3)

for ax, kernel, title in zip(axes, kernels, titles):
	if kernel == 'poly':
		model = SVC(kernel=kernel, degree=3, C=1)
	else:
		model = SVC(kernel=kernel, C=1)
	
	model.fit(X, y)
	
	# Draw decision boundary
	xx, yy = np.meshgrid(
		np.linspace(X[:, 0].min()-0.5, X[:, 0].max()+0.5, 200),
		np.linspace(X[:, 1].min()-0.5, X[:, 1].max()+0.5, 200),
	)
	Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
	Z = Z.reshape(xx.shape)
	
	ax.contourf(xx, yy, Z, alpha=0.3, cmap='bwr')
	ax.scatter(X[:, 0], X[:, 1], c=y, cmap='bwr', edgecolors='k', s=50)
	ax.scatter(
		model.support_vectors_[:, 0],
		model.support_vectors_[:, 1],
		s=200,
		linewidth=1.5,
		facecolors='none',
		edgecolors='green',
	)
	ax.set_title(f'{title}\nAccuracy: {model.score(X, y)*100:.1f}%')

plt.show()

前面提到，C 值愈大，對錯誤分類的懲罰越重；C 值越小，則容許更多分類錯誤。相關展示如下：

from sklearn.datasets import make_blobs
from sklearn.svm import SVC
import matplotlib.pyplot as plt
import numpy as np

# 生成有噪音的資料
X, y = make_blobs(n_samples=100, centers=2, random_state=42, cluster_std=3.0)

# 測試不同 C 值
C_values = [0.01, 1, 100]
titles = ['C=0.01', 'C=1', 'C=100']

fig, axes = plt.subplots(1, 3)

for ax, C, title in zip(axes, C_values, titles):
	model = SVC(kernel='linear', C=C)
	model.fit(X, y)
	
	# 繪製決策邊界
	xx, yy = np.meshgrid(
		np.linspace(X[:, 0].min()-1, X[:, 0].max()+1, 200),
		np.linspace(X[:, 1].min()-1, X[:, 1].max()+1, 200)
	)
	Z = model.decision_function(np.c_[xx.ravel(), yy.ravel()])
	Z = Z.reshape(xx.shape)
	
	ax.contour(
		xx, yy, Z, colors='k', levels=[-1, 0, 1], alpha=0.5, linestyles=['--', '-', '--']
	)
	ax.scatter(X[:, 0], X[:, 1], c=y, cmap='bwr', edgecolors='k', s=50)
	ax.scatter(
		model.support_vectors_[:, 0],
		model.support_vectors_[:, 1],
		s=200,
		linewidth=1.5,
		facecolors='none',
		edgecolors='green'
	)
	ax.set_title(f'{title}\nNum of Support Vectors: {len(model.support_vectors_)}')

plt.show()