二分类线性模型

1. 模型

$$
f(x)=\operatorname{sign}(w \cdot x+b)
$$

Loss function:
$$
L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right)
$$
因此其目标函数为
$$
\min_{w, b}L(w, b)=-\sum_{x_{i} \in M} y_{i}(w \cdot x_{i}+b)
$$
优化方法：

随机梯度下降(SGD)：每次更新使用一个数据

算法2.1:

输入：训练数据集 $T = {(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$ ，其中 $x_{i} \in \mathcal{X}=\mathbf{R}^{n}$，$y_{i} \in \mathcal{Y}=\lbrace -1,+1 \rbrace$, $i=1,2, \cdots, N $ ；学习率 $\eta (0<\eta \leqslant 1) ;$
输出：$ w, b $ 知机模型 $f(x)=\operatorname{sign}(w \cdot x+b)$ 。
(1) 选取初值 $w_{0}, b_{0} ;$
(2) 在训练集中选取数据 $\left(x_{i}, y_{i}\right) ;$
(3) 如果 $y_{i}\left(w \cdot x_{i}+b\right) \leqslant 0$,
$$
\begin{array}{l}
w \leftarrow w+\eta y_{i} x_{i} \\
b \leftarrow b+\eta y_{i}
\end{array}
$$
(4) 转至 (2)，直至训练集中没有误分类点。

2. 算法的收敛性

对于线性可分的的数据集，perceptron经过有限次迭代一定会收敛

证明过程待后续补充：

3. 感知机的对偶形式

对偶形式的基本想法是，将 $w$ 和 $b$ 表示为实例 $x_{i}$ 和标记 $y_{i}$ 的线性组合的形式, 通过求解其系数而求得 $w$ 和 $b$ 。不失一般性，在算法中可假设初始值 $w_{0}, b_{0}$ 均为
$0 。$ 对误分类点 $\left(x_{i}, y_{i}\right)$ 通过
$$
\begin{array}{l}
w \leftarrow w+\eta y_{i} x_{i} \\
b \leftarrow b+\eta y_{i}
\end{array}
$$
最后学得的 $w,b$ 可以表示为
$$
\begin{array}{c}
w=\sum_{i=1}^{N} \alpha_{i} y_{i} x_{i} \\
b=\sum_{i=1}^{N} \alpha_{i} y_{i}
\end{array}
$$
算法 2.2(感知机学习算法的对偶形式)
输入：线性可分的数据集 $T = \lbrace (x_1,y_1),(x_2,y_2),…,(x_N,y_N) \rbrace$, 其中 $x_{i} \in \mathbf{R}^{n}$，$y_{i} \in\lbrace -1,+1 \rbrace, i=1,2, \cdots, N $ 学习率 $\eta(0<\eta \leqslant 1) ;$
输出：$\alpha, b$；感知机模型 $f(x)=\operatorname{sign}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x+b\right), \quad$ 其中 $\alpha=\left(\alpha_{1}, \alpha_{2}, \cdots, \alpha_{N}\right)^{\mathrm{T}}$
(1) $\alpha \leftarrow 0, b \leftarrow 0 ;$
(2) 在训练集中选取数据 $\left(x_{i}, y_{i}\right) ;$

(3) 如果 $y_{i}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x_{i}+b\right) \leqslant 0$,
$$
\begin{array}{l}
\alpha_{i} \leftarrow \alpha_{i}+\eta \\
b \leftarrow b+\eta y_{i}
\end{array}
$$
(4）转至 (2) 直到没有误分类数据。

讨论感知机的对偶有什么意义？

这两个不应该是一样的吗？

4. 感知机代码

import numpy as np
import pandas as pd
np.random.seed(0)
from sklearn import datasets
iris = datasets.load_iris()
X = iris.data[:100, :2]
Y = iris.target[:100]
Y[Y == 0] = -1

# 数据标准化
def _normalize(X, train_set = True, specified_column = None, X_mean = None, X_std = None):
    if specified_column == None:
        specified_column = np.arange(len(X[0]))
    if train_set:
        X_mean = np.mean(X[:, specified_column], axis = 0)
        X_std = np.std(X[:, specified_column], axis = 0)
    X[:, specified_column] = (X[:, specified_column] - X_mean) / (X_std + 1e-8)
    return X, X_mean, X_std

X, X_mean, X_std = _normalize(X, train_set = True)

## 注意label的标枪必须是 -1 和 1 要不然会无限循环下去
## 这样写有个错误，如果数据集不是线性可分的，将一直循环下去, iris数据集是线性可分的
def _train(X, Y, learning_rate = 0.2):
    data_dim = len(X[0])
    w = np.zeros((1, data_dim))
    b = 0
    not_finish = True
    while not_finish:
        wrong_count = 0
        for idx in range(len(X)):
            Y_pred = np.sign(np.dot(w, X[idx]) + b)
            if Y_pred * Y[idx] <= 0: 
                w += learning_rate * Y[idx] * X[idx]
                b += learning_rate * Y[idx]
                wrong_count += 1
        if wrong_count == 0:
            not_finish = False
    return 'Perceptron is done!'
_train(X,Y,0.1)

水广山

Perceptron(未完待更)

1. 模型

2. 算法的收敛性

3. 感知机的对偶形式

4. 感知机代码