从感知机到线性回归，从线性回归到Logistic回归

• 1、感知机
• 1.1、模型
• 1.2、学习策略
• 1.3、学习算法
• 1.4、PLA 对偶形式
• 2、线性回归
• 2.1、模型
• 2.2、学习策略
• 2.3、学习算法
• 3、Logistic回归
• 3.1、模型
• 3.2、学习策略
• 3.3、学习算法

1、感知机

感知机的直观解释为，使用超平面将特征空间中的一组实例分割开来。定义该超平面为：$W^Tx+b=0$WTx+b=0。数据标签取值：$y_i\in\{+1,-1\}$yi​∈{+1,−1}。

---

1.1、模型

该模型决策函数为：
$f(x)=sign(W^Tx+b)\tag1$f(x)=sign(WTx+b)(1)
当 $f(x)&gt;0$f(x)>0 预测为正例，$f(x)&lt;0$f(x)<0 预测为负例。

---

1.2、学习策略

对于模型误分类的样本：
$-y_i(W^Tx+b)&gt;0\tag2$−yi​(WTx+b)>0(2)
误分类样本到分类超平面的距离为：
$-\frac{y_i(W^Tx_i+b)}{||W||}\tag3$−∣∣W∣∣yi​(WTxi​+b)​(3)
其中，$||W||$∣∣W∣∣ 为超平面法向量的 $L_2$L2​ 范数。因此，不妨将其设为 $1$1。

给定训练数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，在模型上发生误分类的样本子集为 $M$M，则所有误分类样本到分类超平面的距离和为：
$L(W,b)=-\sum\limits_{x_i\in M}y_i(W^Tx+b)\tag4$L(W,b)=−xi​∈M∑​yi​(WTx+b)(4)

---

1.3、学习算法

显然，优化过程中，我们选择使 $L(W,b)$L(W,b) 最小的模型作为最终模型。即选择 $(W,b)$(W,b) 使得
$L_{min}(W,b)=-\sum\limits_{x_i\in M}y_i(W^Tx+b)$Lmin​(W,b)=−xi​∈M∑​yi​(WTx+b)
已知损失函数 $L(W,b)$L(W,b) 的梯度为：
$\begin{aligned} \nabla_WL(W,b)&amp;=-\sum\limits_{x_i\in M}y_ix_i\\ \nabla_bL(W,b)&amp;=-\sum\limits_{x_i\in M}y_i \end{aligned} \tag5$∇W​L(W,b)∇b​L(W,b)​=−xi​∈M∑​yi​xi​=−xi​∈M∑​yi​​(5)
选择随机梯度下降（$SGD$SGD）的优化方法，每次从误分类集合 $M$M 中选择一个样本 $(x_i,y_i)$(xi​,yi​)，更新 $W,b$W,b 如下：
$\begin{aligned} W&amp;\leftarrow W+\eta y_ix_i\\ b&amp;\leftarrow b+\eta y_i\tag6 \end{aligned}$Wb​←W+ηyi​xi​←b+ηyi​​(6)
综上，算法学习过程表示如下：

输入：数据集 $T$T，学习率 $\eta(0&lt;\eta\le1)$η(0<η≤1)
1. 选取初始 $W_0,b_0$W0​,b0​
2. 在训练集中选取 $(x_i,y_i)$(xi​,yi​)
3. 如果 $y_i(W^Tx+b)\le0$yi​(WTx+b)≤0：
$\begin{aligned}W&amp;\leftarrow W+\eta y_ix_i\\b&amp;\leftarrow b+\eta y_i\end{aligned}$Wb​←W+ηyi​xi​←b+ηyi​​
4. 不满足条件 3 则转到步骤 2

以上算法可以直观地解释为：当样本发生误分类时，调整 $W,b$W,b 使分类超平面向误分类样本一侧移动，从而减小误分类样本与分类超平面之间的距离，直至超平面将该样本正确分类为止。

---

1.4、PLA 对偶形式

通过观察式 $(6)$(6) 可知：每个误分类样本下，$W$W 每次更新的步长相同，当 $W,b$W,b 均以 $0$0 初始化时，可以得出：
$\begin{aligned} W&amp;=\sum\limits_{i=1}^{n}n_i\eta y_ix_i\\ b&amp;=\sum\limits_{i=1}^{n}n_i\eta y_i \end{aligned}\tag7$Wb​=i=1∑n​ni​ηyi​xi​=i=1∑n​ni​ηyi​​(7)
令 $\alpha_i=n_i\eta$αi​=ni​η，可得：
$\begin{aligned} W&amp;=\sum\limits_{i=1}^{n}\alpha_i y_ix_i\\ b&amp;=\sum\limits_{i=1}^{n}\alpha_i y_i \end{aligned}\tag8$Wb​=i=1∑n​αi​yi​xi​=i=1∑n​αi​yi​​(8)
故对偶算法为：

输入：数据集 $T$T，学习率 $\eta(0&lt;\eta\le1)$η(0<η≤1)
1. $\alpha\leftarrow0, b\leftarrow0$α←0,b←0
2. 在训练集中选取 $(x_i,y_i)$(xi​,yi​)
3. 如果 $y_i(\sum\limits_{j=1}^{n}\alpha_jy_jx_jx_i+b)\le0$yi​(j=1∑n​αj​yj​xj​xi​+b)≤0：
$\begin{aligned}\alpha_i&amp;\leftarrow \alpha_i+\eta\\b&amp;\leftarrow b+\eta y_i\end{aligned}$αi​b​←αi​+η←b+ηyi​​
4. 不满足条件 3 则转到步骤 2 直到样本 $x_i$xi​ 正确分类

---

注意：

1. 该算法是一个 NP 难问题，实际应用中很难保证样本集是线性可分的，不满足线性可分的前提条件，$PLA$PLA 算法不收敛。
2. 满足线性可分的条件时，该算法必收敛，相关证明参考《统计学习方法—李航》
3. 为了加快算法收敛，实际应用中通常使用线性回归的解（$LR$LR 具有解析解）来初始化模型。

---

2、线性回归

2.1、模型

2.2、学习策略

2.3、学习算法

3、Logistic回归

3.1、模型

3.2、学习策略

3.3、学习算法