感知机是一个二分类的线性分类模型，是神经网络和支持向量机的基础。
考虑统计学习方法三要素：
模型：f(x) = sign(w*x+b)
策略：收敛前提条件：数据集是线性可分的
学习策略：考虑每一个点到超平面的距离：(二维的点到平面距离公式），对于分类错误的数据，yi*(w*xi_b)<0，则令损失函数为-Σyi*(w*xi+b)
算法：SGD,若分类错误则计算梯度然后更新。
算法的收敛性：
收敛次数k有上界(R/γ)^2，其中R是x1到xn中二阶范式的最大值，γ是满足对任意i，yi*(wopt * xi + bopt) >= γ的一个常数（由于判别是否分类正确的条件是yi*(wopt * xi + bopt) > 0, 所以肯定可以找到这样一个γ）
对偶形式的算法：
观察更新的过程可以发现，令αi = ni * η，则w = ∑ αi * yi * xi, b = ∑ αi * yi, 其中ni是算法运行过程中数据i被误分类的次数。
实际处理的过程中，可以预处理出Gram矩阵（作用是保存任意两个特征向量的叉积）
两种不同是算法对应的支持向量机的原始形式和对偶形式。
算法测试代码:
import random
import numpy as np
import math
import torch
import matplotlib.pyplot as plt
n = 10
k = -1
bias = 1
lr = 1
def line(x):
return k * x + bias
def learn(x, y):
w = np.random.randn(2)
b = 0
epoch = 0
while True:
flag = False
count = 0
for i in range(len(x)):
if (y[i] * (np.dot(w, x[i]) + b)) <= 0:
# print('updated')
w = w + lr * y[i] * x[i]
b = b + lr * y[i]
flag = True
count += 1
if not flag:
break
epoch += 1
print('epoch count', epoch, count)
return w, b
Gram = np.zeros((n, n))
def dual_learn(x, y):
alpha = np.zeros(n)
b = 0
epoch = 0
while True:
flag = False
count = 0
for i in range(len(x)):
tot = 0
for j in range(len(x)):
tot += alpha[j] * y[j] * Gram[j][i]
tot = y[i] * (tot + b)
if tot <= 0:
print('updated')
alpha[i] += lr
b += lr * y[i]
flag = True
count += 1
if not flag:
break
epoch += 1
print('epoch count', epoch, count)
return alpha, b
if __name__ == '__main__':
x = np.random.uniform(0, 1, (n, 2))
y = np.zeros(n)
for i in range(n):
for j in range(n):
Gram[i][j] = np.dot(x[i], x[j])
print(Gram)
for i in range(len(y)):
if x[i][1] > line(x[i][0]):
y[i] = 1
else:
y[i] = -1
# plt.show()
print(x, y)
alpha, b = dual_learn(x, y)
print(alpha)
w = np.zeros(2)
for i in range(n):
w += alpha[i] * y[i] * x[i]
vector = [0, 0]
ax = plt.gca()
ax.plot(x)
plt.show()
for i in range(10):
vector[0] = float(input())
vector[1] = float(input())
# print(w)
print(vector)
print(np.dot(w, np.array(vector).astype('float64')) + b)
以y=-x+1（0 <= x <= 1， 0 <= y <= 1）为分界线，随机生成一些点进行标记，通过SGD进行更新。