感知机模型和其相关算法笔记。

感知机

• 输入空间： $\mathcal X\subseteq R^n$ ；输入：$x=(x^1, x^2, ..., x^n)^T\in\mathcal X$
• 输出空间： $\mathcal Y=\{+1, -1\}$ ；输出 $y\in\mathcal Y$
• 感知机：

$$f(x)=\mathbb{sign}(w\cdot x+b)= \begin{cases} +1,\ w\cdot x+b\ge0\\ -1,\ w\cdot x+b<0 \end{cases}$$

其中， $w$ 称为权值（Weight）， $b$ 称为偏置（Bias）， $w\cdot x$ 表示内积。

• 假设空间： $\mathcal F=\{f|f(x)=w\cdot x+b\}$

线性方程：

$$w\cdot x+b=0$$

法向量： $w$，截距： $b$ 。

区分正负的是特征空间 $\mathrm R^n$ 中的一个超平面 $\mathrm S$ 。这个超平面是 $n-1$ 维的。

例如：当n=3时，可以利用2维的平面将三维空间划分为两个部分。我们可以感性地理解更高维的情况。

学习策略

要求：数据集线性可分

对于给定的数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_n)\}$

若存在某个超平面 $S$

$$w\cdot x+b=0$$

能够将数据集的正负实例点完全正确的划分到超平面两侧，即

$$\begin{cases} y_i=+1& w\cdot x_i+b>0\\ yi=-1& w\cdot x_i+b<0 \end{cases}$$

那么称数据集线性可分，否则不可分。

定义感知机的损失函数

定义 $\forall x_0\in\mathrm R^n$ 到 $\mathrm S$ 的距离：

$$\frac{1}{||w||}|w\cdot x_0+b|$$

若 $x_0$ 是正确分类点：

$$\frac{1}{||w||}|w\cdot x_0+b|= \begin{cases} \frac{w\cdot x_0+b}{||w||} & y_0=+1\\ -\frac{w\cdot x_0+b}{||w||} & y_0=-1 \end{cases}$$

若 $x_0$ 是错误分类点：

$$\frac{1}{||w||}|w\cdot x_0+b|= \begin{cases} -\frac{w\cdot x_0+b}{||w||} & y_0=+1\\ \frac{w\cdot x_0+b}{||w||} & y_0=-1 \end{cases}=\frac{-y_0}{||w||}|w\cdot x_0+b|$$

误分类点 $x_i$ 到 $\mathrm S$ 的距离：

$$-\frac{-y_i}{||w||}|w\cdot x_i+b|$$

所有误分类点到 $\mathrm S$ 的距离：

$$-\frac{1}{||w||}\sum y_i|w\cdot x_i+b|$$

系数 $-\frac{1}{||w||}$ 不影响算法。终止点是 $\mathrm S=0$ 。

梯度下降法

求解无约束最优化问题。

梯度：指某一函数在该点处最大的方向导数，沿着该方向可以取得最大的变化率。

$$\nabla=\frac{\partial f(\theta)}{\partial\theta}$$

若 $f(\theta)$ 为凸函数，则可以通过梯度下降法进行优化取得最小值：

$$\theta^{(k+1)}=\theta^{(k)}-\eta\nabla f(\theta^{(k)})$$

其中 $\eta$ 指步长。

算法

输入：目标函数 $f(\theta)$ ，步长 $\eta$ ，精度 $\epsilon$ 。

输出： $f(\theta)$ 的极小值点

1. 选取初始值 $\theta^{(0)}\in\mathrm R^n$ ，置 $k=0$ 。
2. 计算 $f(\theta^{(k)}$ 。
3. 计算梯度 $\nabla f(\theta^{(k)})$ 。
4. 置 $\theta^{(k+1)}=\theta^{(k)}-\eta\nabla f(\theta^{(k)})$ ，计算 $f(x^{(k+1)})$ ，当 $||f(\theta^{(k+1)}-f(\theta^{(k)}))||<\epsilon$ 或者 $||\theta^{(k+1)}-\theta^{(k)}||<\epsilon$ 时停止迭代 $\theta^*=\theta^{(k+1)}$ 。
5. 否则 $k=k+1$ ，继续第3步

计算梯度：

• 单变量

  $f(x)$ 那么 $\nabla_x=\frac{\partial f}{\partial x}=\frac{\mathrm df}{\mathrm dx}$ 。

• 多变量

  $$F(\Theta)=5\theta_1^2+2\theta_2+\theta_3^4, \Theta=(\theta_1,\theta_2,\theta_3)^T$$

  分别对三个变量求偏导。

  $$\nabla_{\theta_1}=\frac{\partial F(\Theta)}{\partial\theta_1}=10\theta_1\\ \nabla_{\theta_2}=\frac{\partial F(\Theta)}{\partial\theta_2}=2\\ \nabla_{\theta_3}=\frac{\partial F(\Theta)}{\partial\theta_3}=4\theta^3$$

  得出

  $$\nabla_\Theta=(10\theta_1,2,4\theta_3^3)^T$$

一个例子：

原始形式算法

训练数据集： $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_n)\}$ 其中，$x_i\in\mathcal X\subseteq\mathrm R^n,y_i\in\{+1,-1\}$

损失函数： $L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)$ ，其中， $M$ 表示所有误分类点的集合。

模型参数估计：

$$\mathop{arg}_{w,b}\min L(w,b)$$

批量梯度下降需要大量计算。随机梯度下降计算更简便。

算法的收敛性

计 $\hat w=(w^T,b)^t$ ， $\hat x=(x^T,1)^T$ ，则分离超平面可以写为 $\hat w\cdot \hat x=0$ 。

• 收敛性：对于线性可分的 $T$ ，经过有限次的搜索，可得到将 $T$ 完全分离开的超平面。
• 依赖性：分离超平面的结果依赖于不同的初值选择，或者迭代过程中不同的误分类点的选择顺序。
• 对于线性不可分的 $T$ ，迭代结果会发生震荡，无法收敛。
• 为得到唯一的分离超平面，需增加约束条件。

对偶形式的学习算法

在原始形式中，若 $(x_i,y_i)$ 为误分类点，可如下更新参数：

$$w\leftarrow w+\eta y_ix_i\\ b\leftarrow b+\eta y_i$$

假设初始值 $w_0=\mathbf0，b_0=0$ ，对误分类点 $(x_i,y_i)$ 通过上述的公式更新参数，修改 $n_i$ 次后， $w,b$ 的增量分别是 $\alpha_iy_ix_i$ 和 $\alpha_iy_i$ ，其中 $\alpha_i=n_i\eta_i$ 。

最后学习到的参数为：

$$w=\sum_{i=1}^{N}\alpha_iy_ix_i\\ b=\sum_{i=1}^N\alpha_iy_i$$