感知机算法

1. 问题设定

为了便于后面的计算，我们定义：

y_i= \begin{cases} 1, & X_i\in C,\\[6pt] -1, & X_i\notin C. \end{cases}

我们的目标是找到 权重向量 $w$ 使得：

X_i\cdot w \begin{cases} \ge 0, & \text{if } y_i=1,\\[6pt] \le 0, & \text{if } y_i=-1. \end{cases}

乘上我们的标签，式子统一为一种情况：

y_iX_i \cdot w\geq 0

根据这个统一的式子，我们定义风险函数 $R$ ，当上面的约束式子没有满足时，风险函数为正数。然后我们就可以使用优化方法来优化这个风险函数使得它的值最小。

为了计算整体的风险，我们定义损失函数 $L$ ：

L(\hat{y}, y_i)= \begin{cases} 0, & \text{if }\, y_i\hat{y} \ge 0,\\[6pt] -\,y_i\hat{y}, & \text{otherwise.} \end{cases}

其中 $\hat{y}_i$ 为分类器预测结果， $y_i$ 为实际的分类结果。这样，对于权重 $w$ ，风险函数可以如下计算：

R(w)=\frac{1}{n}\sum_{i=1}^n L(X_i\cdot w, y_i) =\frac{1}{n}\sum_{i\in V} -y_i\,(X_i\cdot w), \qquad V=\{\,i\in\{1,\dots,n\}\mid y_i(X_i\cdot w)<0\,\}.

这样，我们就将问题转化为：寻找 $w$ 使得 $\min R(w)$

在这里，我们不再只是关注找到超平面 $H$ ，而是具体到对 $w$ 的优化。我们的视角从样本空间 $X$ 转换到了权重空间 $W$ /

优化 $R(w)$ 的一个常用方法是梯度下降。我们计算 $R(w)$ 的梯度：

\begin{aligned} \nabla R(w) &= \nabla\sum_{i\in V}\big(-y_i\,X_i\cdot w\big) \\[6pt] &= -\sum_{i\in V} y_i\,X_i \end{aligned}

然后按照如下规则更新 $w$ ：

\begin{aligned} & w \leftarrow \text{arbitrary nonzero starting point (e.g. any } y_i X_i\text{)}\\[6pt] & \text{while } R(w)>0:\\[6pt] &\quad V \leftarrow \{\,i \mid y_i (X_i\cdot w) < 0\,\}\\[6pt] &\quad w \leftarrow w + \epsilon\sum_{i\in V} y_i X_i\\[6pt] & \text{return } w \end{aligned}

但是逐一更新所有错分点的时间复杂度为 $O(nd)$ ，在实践中我们一般采用随机梯度下降：我们不一次性找出所有错分点，而是随机选择一个错分点，然后直接开始更新：

\begin{aligned} &\text{while }\exists\,i\text{ such that }y_i\,(X_i\cdot w)<0:\\[6pt] &\quad\text{choose such }i\quad w \leftarrow w + \epsilon\,y_i X_i\\[6pt] &\text{return } w \end{aligned}