$\frac{| 2 w^{T} x + 2 b |}{\sqrt{\sum_{i = 1}^{N} (2 w_{i}^{T})^{2}}} = \frac{2 | w^{T} x + b |}{2 \sqrt{\sum_{i = 1}^{N} (w^{T})^{2}}} = \frac{| w^{T} x + b |}{\sqrt{\sum_{i = 1}^{N} (w^{T})^{2}}}$

几何间隔就是函数间隔除以了w的模。使用二范数可以让距离变得不那么重要。——对超平面的法向量w加以一定的约束，如规范化。

由于感知机的前提是原数据集线性可分，这意味着必须存在一个正确的超平面。那么，不管几何距离还是函数距离，损失函数最后都要等于0，因此感知机并不关心点到超平面之间的间隔，关心的是误分类的点的个数。使用函数间隔并不会带来什么好处，反而会使学习过程复杂化。所以我们采用几何间隔即可满足需要。

函数间隔与几何间隔的关系：

$当||w||=1时，函数距离 = 几何距离。如果超平面参数w和b成比例的缩放（超平面不变的前提下），函数间隔会因此发生改变，但是几何间隔不会改变。 $

所以一个误分类点到超平面的几何距离是：

$- \frac{1}{| | w | |} y_{i} (w^{T} x + b)$

所有误分类点到超平面的几何距离是：

$- \frac{1}{| | w | |} \sum_{x_{i} \in M}^{} y_{i} (w^{T} x + b)$

感知机的损失函数

设数据集线性可分，则感知机的损失函数为所有误分类点到分类超平面的函数间隔，即：

$L (w, b) = - \sum_{x_{i} \in M} y_{i} (w^{T} x + b)$

其中M为所有误分类点的集合。并且L(w,b)函数一定是非负的，误分类点越少，误分类点离超平面越近，这个函数的值越接近0，直到没有误分类点则函数值为0。

感知机学习算法

感知机学习算法的原始形式

接下来分别为w和b求偏导，得到w和b的参数更新公式。

最终得到下述算法：

输入：训练数据集 $T = (x_{1}, y_{1}), (x_{2}, y_{2}), . ., (x_{N}, y_{N})$ ，其中 $x_{i} \in R^{n}$ ，$Y_i\in{-1,1} $；学习率$ \eta\in(0,1]$

输出：w,b；感知机模型 $f (x) = s i g n (w^{T} x + b)$

随机任选一个超平面 $w_{0}, b_{0}$ ，一般都初始化为0
在训练集中选取数据 $(x_{i}, y_{i})$
如果 $y_{i} (w^{T} x_{i} + b) \leq 0$ ，则更新w和b：

$w_{i} = w_{i - 1} + η y_{i} x_{i}$
$b_{i} = b_{i - 1} + η y_{i}$
转至第二步，直到训练集中没有误分点

感知机学习算法的对偶形式（暂时跳过了）

对偶形式的基本想法是，将w和b表示为实例 $x_{i}$ 和标签 $y_{i}$ 的线性组合的形式，通过求解其系数而求得w和b。

由感知机算法的原始形式可以得出，修改n次过后w，b关于 $(x_{i}, y_{i})$ 的增量分别是 $α_{i} y_{i} x_{i}$ 和 $α_{i} y_{i}$ ，这里 $α_{i} = n_{i} η$ 。这样，最后学习到的w和b可以分别表示为：

$w = \sum_{i = 1}^{N} α_{i} y_{i} x_{i} b = \sum_{i = 1}^{N} α_{i} y_{i}$

具体算法为：

输入：训练数据集 $T = (x_{1}, y_{1}), (x_{2}, y_{2}), . ., (x_{N}, y_{N})$ ，其中 $x_{i} \in R^{n}$ ， $Y_{i} \in - 1, 1$ ；学习率 $η \in (0, 1]$

输出： $α$ ,b；感知机模型 $f (x) = s i g n (\sum_{i = 1}^{N} α_{i} y_{i} x_{i} x + b)$ ，其中 $α = (α_{1}, α_{2}, \dots, α_{N})^{T}$

令 $α = 0, b = 0$
在训练集中选取数据 $(x_{i}, y_{i})$
如果 $y_{i} (\sum_{j = 1}^{N} α_{j} y_{j} x_{j} x_{i} + b) \leq 0$ ，则更新w和b：

$α = α + η b = b + η y_{i}$
转至第二步，知道训练集中没有误分点

感知机算法的对偶形式主要适用于训练数据的特征维度远大于训练样本数的场景，此时原始形式每次更新都需要计算w和x的内积，但对偶形式可以将所有样本间的内积预先计算好以矩阵的形式存储(Gram矩阵)，这样会节省训练耗时。

书中例子

图P29页例2.1

手解：

编程解：

import numpy as np
import matplotlib.pyplot as plt
class Perception():
    '''
    感知机算法，包括原始形式和对偶形式
    '''
    def __init__(self):
        self.learing_rate = 1
    def train(self, data, labels):
        '''
        原始形式的感知机算法，输入数据必须线性可分
        :param data: (n*m),n为样本个数，m为特征个数
        :param labels: 样本标签
        '''
        data_size = data.shape[0]
        #初始化w,b
        self.w = [0] * (data.shape[1])
        self.b = 0
        y_pred = np.sign((np.dot(data, self.w) + self.b))
        #是否有误分类标记，当有误分类样本时执行以下循环
        flag = (y_pred == labels).all()
        while not flag:
            for i in range(data_size):
                y_pred = np.sign((np.dot(data, self.w) + self.b))
                if y_pred[i]*labels[i] <= 0:
                    self.w += self.learing_rate * data[i] * labels[i]
                    self.b += self.learing_rate * labels[i]
                    print(self.w,self.b)
            flag = (y_pred == labels).all()
    def get_gram_matrix(self, data):
        #计算格拉姆矩阵
        data_size = data.shape[0]
        gram_matrix = np.zeros((data_size, data_size))
        for i in range(data_size):
            for j in range(data_size):
                gram_matrix[i, j] = np.dot(data[i], data[j])
        self.gram_matrix = gram_matrix
    def dual_output(self, x_index, data_size, labels):
        '''
        计算第x_index个样本的对偶形式的输出，这里不进行符号函数运算
        :param x_index: 样本索引
        :param data_size: 样本个数
        :param labels: 样本标签
        '''
        output = self.b
        for i in range(data_size):
            output += (self.alpha[i] * labels[i] * self.gram_matrix[i, x_index])
        return output
    def train_dual(self, data, labels):
        #d对偶形式的感知机算法
        self.b = 0
        self.get_gram_matrix(data)
        data_size = data.shape[0]
        self.alpha = [0] * data_size
        flag = False
        while not flag:
            y_pred = [0] * data_size
            for i in range(data_size):
                y_pred[i] = np.sign(self.dual_output(i, data_size, labels))
                if labels[i] * y_pred[i] <= 0:
                    self.alpha[i] += self.learing_rate
                    self.b += self.learing_rate * labels[i]
                    print(self.alpha,self.b)
            flag = (y_pred == labels).all()
if __name__ == '__main__':
    # data1中第一列表示x轴坐标；第二列代表y轴作表；第三列表示标签，1表示正例，-1代表反例。
    data1 = np.array([[3, 3, 1], [4, 3, 1], [1, 1, -1]])    # 书中例题数据检验算法
    # numpy切片：https://www.runoob.com/numpy/numpy-indexing-and-slicing.html
    data = data1[..., 0:2]
    labels = data1[..., -1]
    model = Perception()
    # 使用原始形式（还有一种对偶形式代码写了，但暂时不研究）
    model.train(data, labels)
    # 画图
    # 轴范围 0~5
    plt.xlim(0, 5)
    plt.ylim(0, 5)
    x = data1[..., 0]
    y = data1[..., 1]
    labl = data1[..., 2]
    # 参考:https://www.codenong.com/12487060/
    colors = ['red' if l == 1 else 'green' for l in labl]
    plt.scatter(x, y, c=colors)
    # python如何根据斜率和截距画直线？:https://www.3rxing.org/question/ca80d8505f642814980.html
    print("model.w[0]：", model.w[0])
    print("model.w[1]：", model.w[1])
    print("model.b：", model.b)
    k = - (model.w[0] / model.w[1])
    print("斜率k：", k)
    b = -model.b / model.w[1]
    print("截距b：", b)
    # 生成x的等差数列0-10之间取100个数
    xx = np.linspace(0, 5, 100)
    # 生成每个x对应的y
    y = k * xx + b
    # 画直线
    plt.plot(xx, y)
    plt.show()
    # #随机生成数据,在y=x附近生成数据（暂时不做）
    # x = np.linspace(0,50,50)
    # y1 = x + np.random.randint(1,5,50)
    # y2 = x + np.random.randint(-5,-1,50)
    # data_positive = np.c_[x,y1]
    # data_negative = np.c_[x,y2]
    # labels_positive = np.ones(50)
    # labels_negative = -np.ones(50)
    # data = np.r_[data_positive,data_negative]
    # labels = np.r_[labels_positive,labels_negative]
    #
    # model = Perception()
    # model.train(data,labels)

import numpy as np
import matplotlib.pyplot as plt
class Perception():
'''
感知机算法，包括原始形式和对偶形式
'''
def __init__(self):
self.learing_rate = 1
def train(self, data, labels):
'''
原始形式的感知机算法，输入数据必须线性可分
:param data: (n*m),n为样本个数，m为特征个数
:param labels: 样本标签
'''
data_size = data.shape[0]
#初始化w,b
self.w = [0] * (data.shape[1])
self.b = 0
y_pred = np.sign((np.dot(data, self.w) + self.b))
#是否有误分类标记，当有误分类样本时执行以下循环
flag = (y_pred == labels).all()
while not flag:
for i in range(data_size):
y_pred = np.sign((np.dot(data, self.w) + self.b))
if y_pred[i]*labels[i] <= 0:
self.w += self.learing_rate * data[i] * labels[i]
self.b += self.learing_rate * labels[i]
print(self.w,self.b)
flag = (y_pred == labels).all()
def get_gram_matrix(self, data):
#计算格拉姆矩阵
data_size = data.shape[0]
gram_matrix = np.zeros((data_size, data_size))
for i in range(data_size):
for j in range(data_size):
gram_matrix[i, j] = np.dot(data[i], data[j])
self.gram_matrix = gram_matrix
def dual_output(self, x_index, data_size, labels):
'''
计算第x_index个样本的对偶形式的输出，这里不进行符号函数运算
:param x_index: 样本索引
:param data_size: 样本个数
:param labels: 样本标签
'''
output = self.b
for i in range(data_size):
output += (self.alpha[i] * labels[i] * self.gram_matrix[i, x_index])
return output
def train_dual(self, data, labels):
#d对偶形式的感知机算法
self.b = 0
self.get_gram_matrix(data)
data_size = data.shape[0]
self.alpha = [0] * data_size
flag = False
while not flag:
y_pred = [0] * data_size
for i in range(data_size):
y_pred[i] = np.sign(self.dual_output(i, data_size, labels))
if labels[i] * y_pred[i] <= 0:
self.alpha[i] += self.learing_rate
self.b += self.learing_rate * labels[i]
print(self.alpha,self.b)
flag = (y_pred == labels).all()
if __name__ == '__main__':
# data1中第一列表示x轴坐标；第二列代表y轴作表；第三列表示标签，1表示正例，-1代表反例。
data1 = np.array([[3, 3, 1], [4, 3, 1], [1, 1, -1]]) # 书中例题数据检验算法
# numpy切片：https://www.runoob.com/numpy/numpy-indexing-and-slicing.html
data = data1[..., 0:2]
labels = data1[..., -1]
model = Perception()
# 使用原始形式（还有一种对偶形式代码写了，但暂时不研究）
model.train(data, labels)
# 画图
# 轴范围 0~5
plt.xlim(0, 5)
plt.ylim(0, 5)
x = data1[..., 0]
y = data1[..., 1]
labl = data1[..., 2]
# 参考:https://www.codenong.com/12487060/
colors = ['red' if l == 1 else 'green' for l in labl]
plt.scatter(x, y, c=colors)
# python如何根据斜率和截距画直线？:https://www.3rxing.org/question/ca80d8505f642814980.html
print("model.w[0]：", model.w[0])
print("model.w[1]：", model.w[1])
print("model.b：", model.b)
k = - (model.w[0] / model.w[1])
print("斜率k：", k)
b = -model.b / model.w[1]
print("截距b：", b)
# 生成x的等差数列0-10之间取100个数
xx = np.linspace(0, 5, 100)
# 生成每个x对应的y
y = k * xx + b
# 画直线
plt.plot(xx, y)
plt.show()
# #随机生成数据,在y=x附近生成数据（暂时不做）
# x = np.linspace(0,50,50)
# y1 = x + np.random.randint(1,5,50)
# y2 = x + np.random.randint(-5,-1,50)
# data_positive = np.c_[x,y1]
# data_negative = np.c_[x,y2]
# labels_positive = np.ones(50)
# labels_negative = -np.ones(50)
# data = np.r_[data_positive,data_negative]
# labels = np.r_[labels_positive,labels_negative]
#
# model = Perception()
# model.train(data,labels)

import numpy as np
import matplotlib.pyplot as plt
class Perception():
    '''
    感知机算法，包括原始形式和对偶形式
    '''
    def __init__(self):
        self.learing_rate = 1
    def train(self, data, labels):
        '''
        原始形式的感知机算法，输入数据必须线性可分
        :param data: (n*m),n为样本个数，m为特征个数
        :param labels: 样本标签
        '''
        data_size = data.shape[0]
        #初始化w,b
        self.w = [0] * (data.shape[1])
        self.b = 0
        y_pred = np.sign((np.dot(data, self.w) + self.b))
        #是否有误分类标记，当有误分类样本时执行以下循环
        flag = (y_pred == labels).all()
        while not flag:
            for i in range(data_size):
                y_pred = np.sign((np.dot(data, self.w) + self.b))
                if y_pred[i]*labels[i] <= 0:
                    self.w += self.learing_rate * data[i] * labels[i]
                    self.b += self.learing_rate * labels[i]
                    print(self.w,self.b)
            flag = (y_pred == labels).all()
    def get_gram_matrix(self, data):
        #计算格拉姆矩阵
        data_size = data.shape[0]
        gram_matrix = np.zeros((data_size, data_size))
        for i in range(data_size):
            for j in range(data_size):
                gram_matrix[i, j] = np.dot(data[i], data[j])
        self.gram_matrix = gram_matrix
    def dual_output(self, x_index, data_size, labels):
        '''
        计算第x_index个样本的对偶形式的输出，这里不进行符号函数运算
        :param x_index: 样本索引
        :param data_size: 样本个数
        :param labels: 样本标签
        '''
        output = self.b
        for i in range(data_size):
            output += (self.alpha[i] * labels[i] * self.gram_matrix[i, x_index])
        return output
    def train_dual(self, data, labels):
        #d对偶形式的感知机算法
        self.b = 0
        self.get_gram_matrix(data)
        data_size = data.shape[0]
        self.alpha = [0] * data_size
        flag = False
        while not flag:
            y_pred = [0] * data_size
            for i in range(data_size):
                y_pred[i] = np.sign(self.dual_output(i, data_size, labels))
                if labels[i] * y_pred[i] <= 0:
                    self.alpha[i] += self.learing_rate
                    self.b += self.learing_rate * labels[i]
                    print(self.alpha,self.b)
            flag = (y_pred == labels).all()
if __name__ == '__main__':
    # data1中第一列表示x轴坐标；第二列代表y轴作表；第三列表示标签，1表示正例，-1代表反例。
    data1 = np.array([[3, 3, 1], [4, 3, 1], [1, 1, -1]])    # 书中例题数据检验算法
    # numpy切片：https://www.runoob.com/numpy/numpy-indexing-and-slicing.html
    data = data1[..., 0:2]
    labels = data1[..., -1]
    model = Perception()
    # 使用原始形式（还有一种对偶形式代码写了，但暂时不研究）
    model.train(data, labels)
    # 画图
    # 轴范围 0~5
    plt.xlim(0, 5)
    plt.ylim(0, 5)
    x = data1[..., 0]
    y = data1[..., 1]
    labl = data1[..., 2]
    # 参考:https://www.codenong.com/12487060/
    colors = ['red' if l == 1 else 'green' for l in labl]
    plt.scatter(x, y, c=colors)
    # python如何根据斜率和截距画直线？:https://www.3rxing.org/question/ca80d8505f642814980.html
    print("model.w[0]：", model.w[0])
    print("model.w[1]：", model.w[1])
    print("model.b：", model.b)
    k = - (model.w[0] / model.w[1])
    print("斜率k：", k)
    b = -model.b / model.w[1]
    print("截距b：", b)
    # 生成x的等差数列0-10之间取100个数
    xx = np.linspace(0, 5, 100)
    # 生成每个x对应的y
    y = k * xx + b
    # 画直线
    plt.plot(xx, y)
    plt.show()
    # #随机生成数据,在y=x附近生成数据（暂时不做）
    # x = np.linspace(0,50,50)
    # y1 = x + np.random.randint(1,5,50)
    # y2 = x + np.random.randint(-5,-1,50)
    # data_positive = np.c_[x,y1]
    # data_negative = np.c_[x,y2]
    # labels_positive = np.ones(50)
    # labels_negative = -np.ones(50)
    # data = np.r_[data_positive,data_negative]
    # labels = np.r_[labels_positive,labels_negative]
    #
    # model = Perception()
    # model.train(data,labels)

参考文献：

《统计学习方法》李航

https://www.bilibili.com/video/BV1i4411G7Xv?p=2

https://github.com/1033020837/Basic4AI

https://ld246.com/article/1585574258471

作者：高志远

高志远，24岁，男生查看高志远的所有文章

感知机 – 一种二分类线性分类模型，划分红豆和绿豆

感知机模型

什么是感知机

感知机学习策略

什么是线性可分

几何间隔与函数间隔

函数间隔

使用几何间隔

为什么感知机不使用函数间隔

感知机的损失函数

感知机学习算法

感知机学习算法的原始形式

感知机学习算法的对偶形式（暂时跳过了）

书中例子

编程解：

作者：高志远

发表评论取消回复

感知机模型

什么是感知机

感知机学习策略

什么是线性可分

几何间隔与函数间隔

函数间隔

使用几何间隔

为什么感知机不使用函数间隔

感知机的损失函数

感知机学习算法

感知机学习算法的原始形式

感知机学习算法的对偶形式（暂时跳过了）

书中例子

编程解：

作者： 高志远

发表评论 取消回复

作者：高志远

发表评论取消回复