感知机

---

感知机是二分类的线性模型，其输入是实例的特征向量，输出的是事例的类别，分别是+1和-1，属于判别模型。假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练数据集正实例点和负实例点完全正确分开的分离超平面。如果是非线性可分的数据，则最后无法获得超平面

点到线的距离公式：

$d=\frac{Ax_0+By_0+C}{\sqrt{A^2+B^2}}$

假设有一超平面，h=w*x+b，其中w=（w0，w1…wm），x=（x0，x1…xm），样本x’到超平面的距离为：

$d=\frac{w*x’+b}{||w||}$

---

输出的模型如下：

$f(x)=sign(w*x+b)$

$sign(x)=\begin{cases} 1 \quad\quad\quad x>0
-1 \quad\quad\quad x\leq0\end{cases}$

如果 $ \frac{w\star x’+b}{||w||}>0 $，则y=1。如果<0，则y=-1。这样分类正确的话 $y*\frac{w\star x’+b}{||w||}>0$ 恒成立（||w||是L2范数）

---

损失函数：

$L(w,b)=-\frac{1}{||w||}\sum_{x_i \in M}y_i(w*x_i+b)$（M集合是误分类点的集合）

当然因为||$w$||>0所以我们可以去掉它

$L(w,b)=-\sum_{x_i \in M}y_i(w*x_i+b)$

感知机分类的最终目的是让最终值=0，所以少除也无所谓，还能降低计算量。(所以有个前提：能收敛到0)

---

随机梯度下降算法

用普通的基于所有样本的梯度和的均值的批量梯度下降法（BGD）是行不通的，原因在于我们的损失函数里面有限定，只有误分类的M集合里面的样本才能参与损失函数的优化。所以我们不能用最普通的批量梯度下降,只能采用随机梯度下降（SGD）

$\nabla_wL(w,b)=-\sum_{x_i \in M}y_i*x_i$

$\nabla_bL(w,b)=-\sum_{x_i \in M}y_i$

$w \gets w+\etay_ix_i$

$b \gets b+\eta*y_i$

• xi实际上是(x,y)，yi实际上是{-1，1}，$\eta$是步长。

---

计算过程：

1. 获取{-1，1}对应的点，初始化w矩阵和b变量的值。
2. 正确分类的不用管，不正确分类的利用梯度对w和b的值进行更新。
3. 循环带入所有的点，直到满足要求。

例：点x1=（3，3），w0=0，b0=0，y1=1，步长为1

1. y1*（w0*x1+b0）=0，分类错误。

2. w1=w0+y1*x1=(3，3)^T，b1=b0+y1=1

3. 得到线性模型 f（x）=sign（3x+3y+1）(只输出在线的哪一侧)

---

---

对偶形式算法：

对偶形式的目的是降低运算量，但是并不是在任何情况下都能降低运算量，而是在特征空间的维度很高时才起到作用。

原：

$w \gets w+\etay_ix_i$

$b \gets b+\eta*y_i$

现：

初始值为（0，0）的w和b经过了n次修改后：（$a_i=n_i\eta$）

$w=\sum_{i=1}^na_iy_ix_i$

$b=\sum_{i=1}^na_iy_i$

$sign（wx+b）$，将$w=\sum_{i=1}^na_iy_ix_i$带入得$f(x)=\sum_{i=1}^na_iy_ix_ixj+b$

• 第n-1次的参数$a_i$在第2(n-1)轮要再加$\eta$，所以参数$a_i$越大，说明该点位于分割线附近，在更新的时候容易受影响难以正确分类。$a_i$默认初始为0

$a_i \gets a_i+\eta$

$b \gets b+\eta y_i$

---

加速的设计：

gram矩阵，$G=[x_ix_j]_{NN}$

---

很可惜，因为不能解决异或问题躺尸了很多年。。。