Machine Learning

两分类-硬分类-感知机算法

我们选取激活函数为： $$sign(a)=\{\begin{array}{c}+1,a\ge 0\\ -1,a<0\end{array}$$ 这样就可以将线性回归的结果映射到两分类的结果上了。

定义损失函数为错误分类的数目，比较直观的方式是使用指示函数，但是指示函数不可导，因此可以定义： $$L(w)=\sum _{x_i\in {\mathcal{D}}_{wrong}}-y_i{w}^T{x}_i$$ 其中，${\mathcal{D}}_{wrong}$是错误分类集合，实际在每一次训练的时候，我们采用梯度下降的算法。损失函数对 $w$ 的偏导为： $$\frac{\partial }{\partial w}L(w)=\sum _{x_i\in {\mathcal{D}}_{wrong}}-y_i{x}_i$$ 但是如果样本非常多的情况下，计算复杂度较高，但是，实际上我们并不需要绝对的损失函数下降的方向，我们只需要损失函数的期望值下降，但是计算期望需要知道真实的概率分布，我们实际只能根据训练数据抽样来估算这个概率分布（经验风险）：

\mathbb{E}{\mathcal D}[\mathbb{E}\hat{p}[\nabla_wL(w)]]=\mathbb{E}{\mathcal D}[\frac{1}{N}\sum\limits{i=1}^N\nabla_wL(w)]

我们知道， $N$ 越大，样本近似真实分布越准确，但是对于一个标准差为 $\sigma$ 的数据，可以确定的标准差仅和 $\sqrt{N}$ 成反比，而计算速度却和 $N$ 成正比。因此可以每次使用较少样本，则在数学期望的意义上损失降低的同时，有可以提高计算速度，如果每次只使用一个错误样本，我们有下面的更新策略（根据泰勒公式，在负方向）： $$w^{t+1}\leftarrow w^t+\lambda y_i{x}_i$$ 是可以收敛的，同时使用单个观测更新也可以在一定程度上增加不确定度，从而减轻陷入局部最小的可能。在更大规模的数据上，常用的是小批量随机梯度下降法。