二分問題的數據集$\{({\mathbf{x}}_i,y_i)\}$，$i=1,2,?,m$中，特征數據 { x i } \{\boldsymbol{x}_i\} {xi?}未必能被一塊超平面按其標簽值 y i ∈ { ? 1 , 1 } y_i\in\{-1,1\} yi?∈{?1,1}分隔，即二分問題未必是線性可分的。如果存在超平面$\pi$：$({\mathbf{x}}^{?},1){\mathbf{w}}_0=0$，使得大多數樣本點的特征數據被$\pi$按標簽數據取值分隔，滿足約束$y_i({\mathbf{x}}_i,1){\mathbf{w}}_0\ge 1$，但有少數樣本點特征數據不滿足此約束而交叉糾結，如下圖所示。這樣的問題，稱為近似線性可分問題。圖中的超平面$({\mathbf{x}}^{?},1){\mathbf{w}}_0=\pm 1$稱為軟邊界。

解決近似線性可分問題的支持向量機模型引入松弛變量$\mathbf{z}=\left(\begin{array}{c}{z}_1\\ z_2\\ ?\\ z_m\end{array}\right)$，構造優化問題
$$?\begin{array}{l}\min \frac{1}{2}{\mathbf{w}}^{?}\mathbf{Hw}+{\mathbf{c}}^{?}\mathbf{z}\\ \text{s.t.?}{y}_i({\mathbf{x}}_i,1)\mathbf{w}\ge 1?z_i\\ z_i\ge 0\end{array}i=1,2,?m.(1)$$
其中，$\mathbf{H}=\left(\begin{array}{ccccc}1& 0& ?& 0& 0\\ 0& 1& ?& 0& 0\\ ?& ?& ?& ?& ?\\ 0& 0& ?& 1& 0\\ 0& 0& ?& 0& 0\end{array}\right)$，$\mathbf{c}=\left(\begin{array}{c}C\\ C\\ ?\\ C\end{array}\right)$，正則化參數$C>0$為松弛變量的罰因子。其值越大，模型對誤分類的懲罰越強；反之，模型將側重于分類間隔。當C足夠大時，上述問題退化為問題。
$$\{\begin{array}{l}\min \frac{1}{2}{\mathbf{w}}^{?}\mathbf{Hw}\\ \text{s.t.}{y}_i({\mathbf{x}}_i^{?},1)\mathbf{w}\ge 1i=1,2,?,m.\end{array}$$
根據強對偶定理，可以證明二次規劃問題(1)的最優解${\mathbf{w}}_0$與其對偶問題
$$?\begin{array}{l}\min \frac{1}{2}{\mathbf{\mu }}^{?}\mathbf{Q\mu }?{\mathbf{\mu }}^{?}1\\ \text{s.t.??}{\mathbf{\mu }}^{?}\mathbf{y}=0\\ \mathbf{o}\le \mathbf{\mu }\le \mathbf{c}\end{array}.(2)$$
的最優解${\mathbf{\mu }}_0$等價。其中，$\mathbf{Q}={\mathbf{X}}^{?}\mathbf{X}$，$\mathbf{X}=(y_1{\mathbf{x}}_1,y_2{\mathbf{x}}_2,?,y_m{\mathbf{x}}_m)$，$\mathbf{\mu }\in {\text{R}}^m$。等價的意義為
$${\mathbf{w}}_0=\left(\begin{array}{c}\sum _{i\in s}{\mu }_{0_i}{y}_i{\mathbf{x}}_i\\ \frac{1}{m_s}\sum _{j\in s}\left(y_j?\sum _{i\in s}{\mu }_{0_i}{y}_i{\mathbf{x}}_j^{?}{\mathbf{x}}_i\right)\end{array}\right).$$
其中，
s = { i ∣ 0 ≤ i ≤ m , 0 < μ 0 i < C } s=\{i|0\leq i\leq m, 0<\mu_{0_i}<C\} s={i∣0≤i≤m,0<μ0i??<C}
為支持向量下標集，$m_s$為$s$支持向量個數。
下列代碼實現通過求解二次規劃問題(2)的近似線性可分問題支持向量機模型。

import numpy as np
from scipy.optimize import minimize
class ALineSvc(Classification, LineModel):								#近似線性可分支持向量機分類器def __init__(self, C = 1e+4):										#構造函數self.C = Cself.tagVal = np.signdef obj(self, mu):													#目標函數return 0.5 * (mu @ (self.Q @ mu)) - mu.sum()def ynormalize(self, y, trained):									#標簽數據預處理if not trained:self.ymin = 0self.ymax = 1return (y - self.ymin) / (self.ymax - self.ymin)def fit(self, X, Y, mu = None):										#訓練函數print("訓練中...，稍候")m, n = X.shapeself.scalar = (len(X.shape) == 1)self.X, self.Y = self.pretreat(X, Y)if not isinstance(mu, np.ndarray):if mu == None:mu = np.random.random(m)else:mu = np.array([mu] * m)Qk = np.array([[self.X[i] @ self.X[j]							#內積矩陣for j in range(m)]for i in range(m)])self.Q=np.outer(self.Y, self.Y) * Qk							#系數矩陣h = lambda x: self.Y @ x										#等式約束條件函數g1 = lambda x: x												#不等式約束函數1g2 = lambda x: self.C - x										#不等式約束函數2cons = [{'type': 'eq', 'fun': h},								#約束條件列表{'type': 'ineq', 'fun': g1},{'type': 'ineq', 'fun': g2}]res = minimize(self.obj, mu, constraints = cons)				#求解最優化問題self.mu0 = res.xself.support_ = np.where((self.mu0 > 1e-5) &					#支持向量下標(self.mu0 < self.C))[0]self.w0 = (self.mu0[self.support_] * self.Y[self.support_]) @\self.X[self.support_,0:n]									#模型參數前n項b0 = (self.Y[self.support_]-(self.mu0[self.support_] * self.Y[self.support_])\@ Qk[np.ix_(self.support_, self.support_)]).mean()	#模型參數最末項self.w0 = np.append(self.w0, b0)								#整合模型參數self.coef_, self.intercept_ = self.coef_inte()					#計算超平面系數和截距print("%d次迭代后完成訓練。"%res.nit)

程序中第3~44行定義的近似線性可分支持向量機分類器類ALineSvc繼承了Classification（見博文《最優化方法Python計算：無約束優化應用——線性回歸分類器》）和LineModel（見博文《最優化方法Python計算：無約束優化應用——線性回歸模型》）的屬性與方法。類定義體中

• 第4~6行定義構造函數，設置松弛變量上限C的默認值為$10^4$。第6行將標簽值函數tagVal設置為Numpy的sign函數，以適于計算分類預測值。
• 第7~8行定義問題(2)的目標函數obj，返回值為$\frac{1}{2}{\mathbf{\mu }}^{?}\mathbf{Q}\mathbf{\mu }?{\mathbf{\mu }}^{?}1$。
• 第9~11行重載標簽數據歸一化函數ynormalize。由于近似線性可分支持向量機模型中的標簽數據不需要歸一化，所以在訓練時將self.ymin和self.ymax設置為0和1。第12行返回歸一化后的標簽數據。做了這樣的調整，我們在進行預測操作時，按式
  $$y=y?(\max y?\min y)+\min y$$
  仍保持$y$的值不變，進而可保持LineModel的predict函數代碼不變（見博文《最優化方法Python計算：無約束優化應用——線性回歸分類器》）。
• 第14~44行重載訓練函數fit。對比程序4.1中定義的父類fit函數可見第15~23行的代碼是保持一致的。
  - 第24~26行計算內積矩陣$${\mathbf{Q}}_k=\left(\begin{array}{cccc}{\mathbf{x}}_1^{?}{\mathbf{x}}_1& {\mathbf{x}}_1^{?}{\mathbf{x}}_2& ?& {\mathbf{x}}_1^{?}{\mathbf{x}}_m\\ {\mathbf{x}}_2^{?}{\mathbf{x}}_1& {\mathbf{x}}_2^{?}{\mathbf{x}}_2& ?& {\mathbf{x}}_2^{?}{\mathbf{x}}_m\\ ?& ?& ?& ?\\ {\mathbf{x}}_m^{?}{\mathbf{x}}_1& {\mathbf{x}}_m^{?}{\mathbf{x}}_2& ?& {\mathbf{x}}_m^{?}{\mathbf{x}}_m\end{array}\right)$$
  第27行計算目標函數系數矩陣$$\mathbf{Q}=\left(\begin{array}{cccc}{y}_1{y}_1{\mathbf{x}}_1^{?}{\mathbf{x}}_1& y_1{y}_2{\mathbf{x}}_1^{?}{\mathbf{x}}_2& ?& y_1{y}_m{\mathbf{x}}_1^{?}{\mathbf{x}}_m\\ y_2{y}_1{\mathbf{x}}_2^{?}{\mathbf{x}}_1& y_2{y}_2{\mathbf{x}}_2^{?}{\mathbf{x}}_2& ?& y_2{y}_m{\mathbf{x}}_2^{?}{\mathbf{x}}_m\\ ?& ?& ?& ?\\ y_m{y}_1{\mathbf{x}}_m^{?}{\mathbf{x}}_1& y_m{y}_2{\mathbf{x}}_m^{?}{\mathbf{x}}_2& ?& y_m{y}_m{\mathbf{x}}_m^{?}{\mathbf{x}}_m\end{array}\right).$$
  - 第28~30行定義等式約束條件函數h和不等式約束條件函數g1和g2。第31~33行構造約束條件列表cons。第34行調用minimize函數求解優化問題(2)，返回值賦予res。第35行將res的x屬性賦予mu0，為問題(2)的最優解${\mathbf{\mu }}_0$。
  - 第36~37行按條件
  $$0<{\mu }_{0_i}<C,i=1,2,?,m$$
  查找支持向量的下標集$s$并賦予屬性support_。
  - 第38~39行計算原問題(1)的最優解${\mathbf{w}}_0$的前$n$個元素$\sum _{i\in s}{\mu }_{0_i}{y}_i{\mathbf{x}}_i$。第40~41行計算原問題(1)的最優解${\mathbf{w}}_0$的最后一個元素$b_0$。第43行連接兩部分構成${\mathbf{w}}_0$賦予屬性w0。
  - 第44行調用父類的coef_inte函數（見博文《最優化方法Python計算：無約束優化應用——線性回歸模型》）計算決策面的系數coef_與截距intercept_。
  綜合案例
  井字棋是很多人兒時喜愛的游戲。方形棋盤被井字形的4條直線分成9個空格。兩個玩家各執標有一符：或為“$\times$”，或為“$°$”的棋子，輪流在棋盤中放置一子。一方所執符號棋子占據棋盤中一直線（水平或豎直或對角）上的三個空格（見題圖），即勝出。文件tic-tac-toe.csv（來自UC Irvine Machine Learning Repository）羅列了958例棋盤格局及其勝負判斷

x	x	x	x	o	o	x	o	o	positive
x	x	x	x	o	o	o	x	o	positive
$?$	$?$	$?$	$?$	$?$	$?$	$?$	$?$	$?$	$?$
b	b	b	b	o	o	x	x	x	positive
x	x	o	x	x	o	o	b	o	negative
$?$	$?$	$?$	$?$	$?$	$?$	$?$	$?$	$?$	$?$
o	x	o	o	x	x	x	o	x	negative
o	o	x	x	x	o	o	x	x	negative

文件中，每一行表示一種棋盤格局及對該格局勝負方的判定。前9個數據表示按行優先排列的棋盤格局，第10個數據“positive”表示執“$\times$”者勝，“negative”表示執“$°$”者勝。例如，第一行中前9個數據“x x x x o o x o o”表示棋盤格局

由于執“$\times$”者占滿了第1行和第1列，故判斷執“$\times$”者勝出，即第10個數據為“positive”。注意，格局數據中“b”表示對應格子未置入任何棋子。例如，數據“b b b b o o x x x”表示棋盤格局

下列代碼試圖用文件中的70例數據訓練一個ALineSvc支持向量機分類模型，用其余數據對其進行測試。

import numpy as np
data = np.loadtxt('tic-tac-toe.csv',		#讀取數據文件delimiter = ',', dtype = str)
X = np.array(data)							#轉換為數組
Y = X[:, 9]									#讀取標簽數據
X = np.delete(X, [9], axis = 1)				#去掉標簽列
m, n=X.shape
print('共有%d個數據樣本'%m)
for i in range(m):for j in range(n):if X[i, j] == 'x':X[i, j] = 1if X[i, j] == 'o':X[i, j] = -1if X[i, j] == 'b':X[i, j] = 0
X = X.astype(float)
Y = np.array([1 if y == 'positive' else		#類別數值化-1 for y in Y]).astype(int)
a = np.arange(m)							#數據項下標
m1=70										#訓練集樣本容量
np.random.seed(3489)
print('隨機抽取%d個樣本作為訓練數據。'%(m1))
train = np.random.choice(a,m1,replace=False)
test = np.setdiff1d(a,train)				#檢測數據下標
tictactoe = ALineSvc(C = 10)				#創建模型
tictactoe.fit(X[train], Y[train])			#訓練模型
print('系數：', tictactoe.coef_)
print('截距：%.4f'%tictactoe.intercept_)
support = tictactoe.support_				#支持向量下標
print('支持向量：%s'%support)
acc=tictactoe.score(X[test], Y[test]) * 100
print('對其余%d個樣本數據測試，正確率：%.2f'%(m - m1,acc) + '%')

程序的第2~6行從文件中讀取數據并轉換為數組X，并從中拆分出標簽數據Y。由于表示格局的特征數據和表示勝負的標簽數據都是字符型，應轉換為數值類型。對特征數據，作映射：
$$\text{x}\to 1,\text{o}\to ?1,\text{b}\to 0$$
第9~16行的嵌套for循環完成9個格局數據按上述對應關系的類型轉換。第18~19行將標簽數據按映射
$$\text{positive}\to 1,\text{negative}\to ?1$$
進行類型轉換。第20~25行從958個棋盤格局數據中隨機選取70（m1）個作為訓練數據集X[train]、Y[train]，其余888個作為訓練數據集X[test]、Y[test]。第26行聲明ALineSvc類對象tictactoe作為支持向量機分類模型，設置罰項系數C為10.0。第27行調用tictactoe的fit函數用X[train]、Y[train]對其進行訓練。第32行調用tictactoe的score函數用X[test]、Y[test]對其進行測試。運行程序，輸出

共有958個數據樣本
隨機抽取100個樣本作為訓練數據。
訓練中...，稍候
15次迭代后完成訓練。
系數： [2. 2. 2. 2. 2. 2. 2. 2. 2.]
截距：-19.0286
支持向量：[ 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 2324 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 4748 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69]
對其余888個樣本數據測試，正確率：98.31%

意為用70個訓練數據，經過15次迭代完成訓練。對其余888個數據對訓練所得模型測試，正確率為98.31%。訓練給出了決策面
$$\pi :2x_1+2x_2+2x_3+2x_4+2x_5+2x_6+2x_7+2x_8+2x_9?19.03=0$$

寫博不易，敬請支持：
如果閱讀本文于您有所獲，敬請點贊、評論、收藏，謝謝大家的支持！