1、比較感知機的對偶形式與線性可分支持向量機的對偶形式，

1.1、感知機的對偶形式

由于李航老師書上的感知機的對偶形式有點問題，這里先對其進行一下改進
最后學習到的感知機的引數是：
w = ∑ i = 1 N α i y i x i (1) w = \sum_{i = 1}^{N}\alpha _{i} y_{i} x_{i} \tag{1} w=i=1∑N?αi?yi?xi?(1)
b = ∑ i = 1 N α i y i (2) b = \sum_{i = 1}^{N}\alpha _{i} y_{i} \tag{2} b=i=1∑N?αi?yi?(2)
其中 α i = n i η \alpha _{i} = n_{i}\eta αi?=ni?η, n i n_{i} ni?是表示樣本 ( x i , y i ) (x_{i},y_{i}) (xi?,yi?)的更新的次數， N N N是樣本的個數，
我們需要將上式(1),(2)都帶入到感知機模型中，于是得到感知機的模型是：

1. 輸入：線性可分的資料集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . ( x N , y N ) } T=\{(x_{1},y_{1}),(x_{2},y_{2}),...(x_{N},y_{N})\} T={(x1?,y1?),(x2?,y2?),...(xN?,yN?)}，學習率 η \eta η
2. 輸出：感知機模型 f ( x ) = s i g n ( ∑ i = 1 N n i η y i x i + ∑ i = 1 N n i η y i ) f(x) = sign( \sum_{i = 1}^{N}n_{i}\eta y_{i} x_{i}+\sum_{i = 1}^{N}n_{i}\eta y_{i}) f(x)=sign(∑i=1N?ni?ηyi?xi?+∑i=1N?ni?ηyi?)
3. 初始化 n = ( 0 , 0 , . . . , 0 ) ， 第 i 個 位 置 表 示 n i 的 初 始 值 n = (0,0,...,0)，第i個位置表示n_{i}的初始值 n=(0,0,...,0)，第i個位置表示ni?的初始值
4. 在訓練集 T T T中選取資料點 ( x i , y i ) (x_{i},y_{i}) (xi?,yi?)
5. 如果是誤分類的資料點或者資料點在平面上，也就是 y i ( ∑ i = 1 N n i η y i x i + ∑ i = 1 N n i η y i ) < = 0 y_{i}(\sum_{i = 1}^{N}n_{i}\eta y_{i} x_{i}+\sum_{i = 1}^{N}n_{i}\eta y_{i})<=0 yi?(∑i=1N?ni?ηyi?xi?+∑i=1N?ni?ηyi?)<=0,則有 n i = n i + 1 n_{i} = n_{i}+1 ni?=ni?+1
6. 轉到第四步直到沒有誤分類資料，

1.2、線性可分支持向量機的對偶性形式

1. 輸入訓練資料集
2. 輸出分離超平面和分類決策函式
3. 構造并且求解最優化約束 m i n α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ? x j ) ? ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 0 ; α i > = 0 ; i = 1 , 2 , . . . , N \underset{\alpha }{min}\ \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N}\alpha _{i}\alpha _{j}y_{i}y_{j}(x_{i}\bullet x_{j}) -\sum_{i=1}^{N}\alpha _{i}\\ s.t. \ \sum_{i = 1}^{N}\alpha _{i}y_{i} = 0;\\\alpha _{i}>=0;\\i=1,2,...,N αmin? 21?i=1∑N?j=1∑N?αi?αj?yi?yj?(xi??xj?)?i=1∑N?αi?s.t. i=1∑N?αi?yi?=0;αi?>=0;i=1,2,...,N求得關于 α \alpha α的最優解，
4. 計算引數關于 α \alpha α的具體表達 w = ∑ i = 1 N α i y i x i w = \sum_{i=1}^{N}\alpha_{i}y_{i}x_{i} w=i=1∑N?αi?yi?xi?并且選擇一個 α \alpha α的正分量 α j \alpha_{j} αj?，計算 b = y j ? ∑ i = 1 N α i y i ( x i ? x j ) b = y_{j}-\sum_{i=1}^{N}\alpha_{i}y_{i}(x_{i}\bullet x_{j}) b=yj??i=1∑N?αi?yi?(xi??xj?)
5. 上面的一步就已經求得了分離超平面和分類決策函式了，

1.3、兩者的比較

對于感知機的學習，是基于梯度下降演算法的，每次只選取一個資料點在滿足條件的情況下進行引數更新，迭代更新，而支持向量機的學習是基于條件約束規劃，通過對偶問題來更新，在資料集不大時，可以一次性求得模型的引數的具體表達，支持向量機可以在理論上求得決議解，

2、已知正例點 x 1 = ( 1 , 2 ) , x 2 = ( 2 , 3 ) , x 3 = ( 3 , 3 ) x_{1}=(1,2),x_{2}=(2,3),x_{3}=(3,3) x1?=(1,2),x2?=(2,3),x3?=(3,3),負例點是 x 4 = ( 2 , 1 ) , x 5 = ( 3 , 2 ) x_{4}=(2,1),x_{5}=(3,2) x4?=(2,1),x5?=(3,2),試求最大間隔分離超平面和分類決策函式，并在圖上畫出分離超平面、間隔邊界以及支持向量，

解：
使用sklearn的求解如下

代碼如下

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

def plot_svc_decision_function(X,y,model, ax=None, plot_support=True):
    
    plt.scatter(X[:,0],X[:,1],c=y,s=50,cmap='autumn') #將影像展示出來
    if ax is None:
        ax = plt.gca()
    xlim = ax.get_xlim()
    ylim = ax.get_ylim()
    x = np.linspace(xlim[0], xlim[1], 30)
    y = np.linspace(ylim[0], ylim[1], 30)
    Y, X = np.meshgrid(y, x)
    xy = np.vstack([X.ravel(), Y.ravel()]).T
    P = model.decision_function(xy).reshape(X.shape)
    ax.contour(X, Y, P, colors='k',levels=[-1, 0, 1], alpha=0.5,linestyles=['--', '-', '--'])
    ax.set_xlim(xlim)
    ax.set_ylim(ylim)


if __name__ == '__main__':
    X = np.array([[1, 2],
                  [2, 3],
                  [3, 3],
                  [2, 1],
                  [3, 2]])
    y = np.array([1, 1, 1, 0, 0])
    model = SVC(kernel='linear', C=1E10)
    model.fit(X, y)
    plot_svc_decision_function(X, y, model)

比較遺憾的是，自己實作了一下針對這個題目的線性可分支持向量機演算法，因為演算法里面有個求解約束規劃，我使用的是懲罰函式方法，搭建了一個Pytorch模型，但是求解不成功，下面將代碼放出來，如果有大神指點，萬分榮幸！！

下面是我自己實作的代碼，希望有大神指點一二，萬分感謝

import torch
import numpy as np
import torch.nn as nn
import torch.optim as optim
import matplotlib.pyplot as plt
import os
os.environ["KMP_DUPLICATE_LIB_OK"]="TRUE"

class max_m(nn.Module):
    def __init__(self, M = 10**5, dim = 2, data_nums = 5):
        super(max_m, self).__init__()
        self.w = nn.Parameter(torch.randn(dim, 1))
        self.bias = nn.Parameter(torch.randn(1))
        self.M = M
        self.data_nums = data_nums
    def forward(self,X, Y):#這個是不需要Gram矩陣的
        X = torch.from_numpy(X).float()
        Y = torch.from_numpy(Y).float().T
        out = torch.mm(X, self.w) + self.bias
        y_o = Y * out - 1
        y_o_low_0 = torch.where(y_o < 0, y_o, torch.FloatTensor([[0] * self.data_nums]).T)
        
        #下面開始構造損失函式
        # print(y_o)
        loss = 0.5*torch.norm(self.w, p = 2) ** 2 - self.M * torch.sum(y_o_low_0)
        return loss
        
def learn(X, Y,M = 10 ** 5, epoch = 1000, lr = 0.01):
    svm_loss = max_m(M = M)
    optim_adam = optim.Adam(svm_loss.parameters(), lr = lr)
    svm_loss.train()
    for e in range(epoch):
        loss = svm_loss(X, Y)
        optim_adam.zero_grad()
        loss.backward()
        optim_adam.step()
        if e % 100 == 0:
            d = svm_loss.state_dict()
            print('w is :', d['w'])
            print('b is :', d['bias'])
            # print('loss is :', loss)
            
    d = svm_loss.state_dict()
    w = d['w']
    bias = d['bias']
    w = w.detach().numpy()
    bias = bias.detach().numpy()
    
    plt.scatter(X[:3, 0], X[:3, 1], marker = '*')
    plt.scatter(X[3:, 0], X[3:, 1], marker = 'o')
    x_new = [1, 3]
    y_new = [-(w[0]/w[1])*x_new[0] - (bias/w[1]), -(w[0]/w[1])*x_new[1] - (bias/w[1])]
    y_new1 = [-(w[0]/w[1])*x_new[0] + (1 - bias)/w[1], -(w[0]/w[1])*x_new[1] + (1 - bias)/w[1]]
    y_new2 = [-(w[0]/w[1])*x_new[0] - (1 + bias)/w[1], -(w[0]/w[1])*x_new[1] - (1 + bias)/w[1]]
    plt.plot(x_new, y_new)
    plt.plot(x_new, y_new1)
    plt.plot(x_new, y_new2)
    print('y_new is :', y_new)
    print('y_new1 is :', y_new1)
    print('y_new2 is :', y_new2)
    print(w)
    print(bias)
       
if __name__ == "__main__":
    dim = 2
    M = 10 ** 8
    lr = 0.0005
    epoch = 10000
    X = np.array([[1, 2],
                  [2, 3],
                  [3, 3],
                  [2, 1],
                  [3, 2]])
    Y = np.array([[1, 1, 1, -1, -1]])
    learn(X, Y, M = M, epoch = epoch, lr = lr)

畫的影像是：

3、線性支持向量機也可以定義為以下形式： m i n w , b , ξ 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i 2 s . t . y i ( w ? x i ) ≥ 1 ? ξ i , i = 1 , 2 , . . . , N ξ i ≥ 0 , i = 1 , 2 , . . . , N \underset{w,b,\xi }{min} \ \frac{1}{2}\left \| w \right \| ^{2} + C\sum_{i = 1}^{N}\xi _{i}^{2}\\s.t. \ y_{i}(w*x_{i})\ge 1 -\xi _{i},\ i = 1,2,...,N\\\xi _{i} \ge 0,\ i = 1,2,...,N w,b,ξmin? 21?∥w∥2+Ci=1∑N?ξi2?s.t. yi?(w?xi?)≥1?ξi?, i=1,2,...,Nξi?≥0, i=1,2,...,N試求出其對偶形式，

解：
我們先引入拉格朗日函式，其中 α ≥ 0 , β ≥ 0 \alpha \ge0, \beta \ge 0 α≥0,β≥0
L ( w , ξ , α , β ) = 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i 2 ? ∑ i = 1 N α i ( y i ( w ? x i ) ? 1 + ξ i ) ? ∑ i = 1 N β i ξ i L(w,\xi ,\alpha ,\beta ) = \ \frac{1}{2}\left \| w \right \| ^{2} + C\sum_{i = 1}^{N}\xi _{i}^{2}-\sum_{i = 1}^{N}\alpha _{i}(y_{i}(w*x_{i})-1 +\xi _{i})-\sum_{i=1}^{N}\beta _{i}\xi _{i} L(w,ξ,α,β)= 21?∥w∥2+Ci=1∑N?ξi2??i=1∑N?αi?(yi?(w?xi?)?1+ξi?)?i=1∑N?βi?ξi?
那么原始問題就是
m i n w , ξ m a x α , β L ( w , ξ , α , β ) = 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i 2 ? ∑ i = 1 N α i ( y i ( w ? x i ) ? 1 + ξ i ) ? ∑ i = 1 N β i ξ i \underset{w,\xi }{min}\ \underset{\alpha ,\beta }{max} L(w,\xi ,\alpha ,\beta ) = \ \frac{1}{2}\left \| w \right \| ^{2} + C\sum_{i = 1}^{N}\xi _{i}^{2}-\sum_{i = 1}^{N}\alpha _{i}(y_{i}(w*x_{i})-1 +\xi _{i})-\sum_{i=1}^{N}\beta _{i}\xi _{i} w,ξmin? α,βmax?L(w,ξ,α,β)= 21?∥w∥2+Ci=1∑N?ξi2??i=1∑N?αi?(yi?(w?xi?)?1+ξi?)?i=1∑N?βi?ξi?
原始問題是先關于 α , β \alpha, \beta α,β極大化，這是因為，假如有一個資料點 ( x i , y i ) (x_{i},y_{i}) (xi?,yi?)不滿足條件 y i ( w ? x i ) ≥ 1 ? ξ i y_{i}(w*x_{i})\ge 1-\xi _{i} yi?(w?xi?)≥1?ξi?，也就是 y i ( w ? x i ) ≤ 1 ? ξ i y_{i}(w*x_{i})\le 1-\xi _{i} yi?(w?xi?)≤1?ξi?,因為我們是先極大化,那么在極大化的時候，就是讓對應的 α i \alpha_{i} αi?趨近于 + ∞ +\infty +∞,只要讓其他的 α , β \alpha, \beta α,β均為0，此時的目標函式的值就是 + ∞ +\infty +∞.此時 m a x α , β L ( w , ξ , α , β ) = 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i 2 ? ∑ i = 1 N α i ( y i ( w ? x i ) ? 1 + ξ i ) ? ∑ i = 1 N β i ξ i = + ∞ \underset{\alpha ,\beta }{max} L(w,\xi ,\alpha ,\beta ) = \ \frac{1}{2}\left \| w \right \| ^{2} + C\sum_{i = 1}^{N}\xi _{i}^{2}-\sum_{i = 1}^{N}\alpha _{i}(y_{i}(w*x_{i})-1 +\xi _{i})-\sum_{i=1}^{N}\beta _{i}\xi _{i} \\=+\infty α,βmax?L(w,ξ,α,β)= 21?∥w∥2+Ci=1∑N?ξi2??i=1∑N?αi?(yi?(w?xi?)?1+ξi?)?i=1∑N?βi?ξi?=+∞
如果是資料點滿足約束條件，因為是極大化，就是讓所有的 α , β \alpha, \beta α,β均為0，此時
m a x α , β L ( w , ξ , α , β ) = 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i 2 ? ∑ i = 1 N α i ( y i ( w ? x i ) ? 1 + ξ i ) ? ∑ i = 1 N β i ξ i = 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i 2 \underset{\alpha ,\beta }{max} L(w,\xi ,\alpha ,\beta ) = \ \frac{1}{2}\left \| w \right \| ^{2} + C\sum_{i = 1}^{N}\xi _{i}^{2}-\sum_{i = 1}^{N}\alpha _{i}(y_{i}(w*x_{i})-1 +\xi _{i})-\sum_{i=1}^{N}\beta _{i}\xi _{i} \\=\ \frac{1}{2}\left \| w \right \| ^{2} + C\sum_{i = 1}^{N}\xi _{i}^{2} α,βmax?L(w,ξ,α,β)= 21?∥w∥2+Ci=1∑N?ξi2??i=1∑N?αi?(yi?(w?xi?)?1+ξi?)?i=1∑N?βi?ξi?= 21?∥w∥2+Ci=1∑N?ξi2?

所以有
m a x α , β L ( w , ξ , α , β ) = { 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i 2 ， 數 據 點 滿 足 約 束 條 件 + ∞ ， 其 他 不 滿 足 約 束 條 件 情 況 \underset{\alpha ,\beta }{max} L(w,\xi ,\alpha ,\beta ) =\left\{ \begin{aligned} &&\frac{1}{2}\left \| w \right \| ^{2} + C\sum_{i = 1}^{N}\xi _{i}^{2}，資料點滿足約束條件 \\ &&+\infty，其他不滿足約束條件情況 \end{aligned} \right. α,βmax?L(w,ξ,α,β)=??????????21?∥w∥2+Ci=1∑N?ξi2?，數據點滿足約束條件+∞，其他不滿足約束條件情況?
因此再對 m a x α , β L ( w , ξ , α , β ) \underset{\alpha ,\beta }{max} L(w,\xi ,\alpha ,\beta ) α,βmax?L(w,ξ,α,β)進行一次極小化調整引數 w w w,使所有的資料滿足約束條件，就可以得到
m i n w , ξ m a x α , β L ( w , ξ , α , β ) = 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i 2 \underset{w,\xi }{min}\ \underset{\alpha ,\beta }{max} L(w,\xi ,\alpha ,\beta )=\frac{1}{2}\left \| w \right \| ^{2} + C\sum_{i = 1}^{N}\xi _{i}^{2} w,ξmin? α,βmax?L(w,ξ,α,β)=21?∥w∥2+Ci=1∑N?ξi2?

那么對偶問題就是調整極大化和極小化的順序，也就是
m a x α , β m i n w , ξ L ( w , ξ , α , β ) \underset{\alpha ,\beta }{max}\ \underset{w,\xi }{min} L(w,\xi ,\alpha ,\beta ) α,βmax? w,ξmin?L(w,ξ,α,β)
也就是先關于 w , ξ w,\xi w,ξ求導，令其導數為0，求出 w , ξ w,\xi w,ξ關于 α , β \alpha,\beta α,β的運算式，然后再代入原式即可得到對偶問題，除了有點麻煩之外，好像沒啥難的，

4、證明內積的正整數冪函式： K ( x , z ) = ( x ? z ) p K(x,z)=(x\bullet z)^p K(x,z)=(x?z)p是正定核函式，這里的p是正整數， x , z ∈ R n x,z\in R^{n} x,z∈Rn.

證明：
我們這里需要構造一個長度為 n p n^p np的函式向量
f ( x 1 , . . . , x n ) = ( x 1 p , . . . , x n p , x 1 p ? 1 x 2 , x 1 p ? 1 x 3 , . . . , x 1 p ? 1 x n , . . . ) f(x_{1}, ..., x_{n})=(x_{1}^{p},...,x_{n}^{p},x_{1}^{p-1}x_{2},x_{1}^{p-1}x_{3},...,x_{1}^{p-1}x_{n},...) f(x1?,...,xn?)=(x1p?,...,xnp?,x1p?1?x2?,x1p?1?x3?,...,x1p?1?xn?,...)
是一個有序的函式向量，舉個例子來說明如何構造
設 x = x 1 , x 2 , p = 2 x={x_{1},x_{2}}, p=2 x=x1?,x2?,p=2,那么 f ( x 1 , x 2 ) = ( x 1 2 , x 2 2 , x 1 x 2 , x 2 x 1 ) f(x_{1},x_{2})=(x_{1}^2,x_{2}^2,x_1x_2,x_2x_1) f(x1?,x2?)=(x12?,x22?,x1?x2?,x2?x1?)
那么對于 z = ( z 1 , z 2 ) z=(z_{1},z_{2}) z=(z1?,z2?),有 f ( z 1 , z 2 ) = ( z 1 2 , z 2 2 , z 1 z 2 , z 2 z 1 ) f(z_{1},z_{2})=(z_{1}^2,z_{2}^2,z_1z_2,z_2z_1) f(z1?,z2?)=(z12?,z22?,z1?z2?,z2?z1?)
所以 K ( x , z ) = x 1 2 z 1 2 + 2 x 1 x 2 z 1 z 2 + x 2 2 z 2 2 = f ( x 1 , x 2 ) ? f ( z 1 , z 2 ) K(x,z) = x_{1}^2z_{1}^2+2x_1x_2z_1z_2+x_{2}^{2}z_{2}^2=f(x_1,x_2)\bullet f(z_1,z_2) K(x,z)=x12?z12?+2x1?x2?z1?z2?+x22?z22?=f(x1?,x2?)?f(z1?,z2?)
其中 ? \bullet ?表示內積，
其他的也均可以這樣構造，注意內積和乘法之間的區別，
如果使用核函式另外一種定義，也就是證明Gram矩陣是半正定矩陣的方法將會很難處理，