暂无说说

感知机

理论基础 jiajun 11个月前 (11-30) 303次浏览 0个评论 扫描二维码

感知机(Perceptron) 于 1957 年由 Rosenblatt 最早提出,是神经网络与支持向量机的基础。感知机是二分类的线性分类模型,输入为实例的特征向量,输出为实例的类别,取值为 1 或-1。感知机模型对应于输入空间(特征空间),是一个能将实例分为正负两类的分离超平面。

感知机的定义

假设输入空间(特征空间)为\(\chi \subseteq {R^n}\),输出空间为\(\gamma = \{ – 1,1\} \)。由输入空间到输出空间的映射

\(f(x) = sign(\omega \bullet x + b)\)

称为感知机。其中,\(\omega ,b\)为感知机模型的参数,输入\(x \in \chi \),表示实例的特征向量,相当于特征空间的一个点,输出\(y \in \gamma \)表示实例的类别,\(\omega \in {R^n}\)表示权值(权值向量),\(b \in R\)称为偏置,\(\omega \bullet x\)表示\(\omega \)\(x\)的内积,\(sign\)是符号函数,即

\(sign(x) = \left\{ {\begin{array}{*{20}{c}}
{1\begin{array}{*{20}{c}}
{}&{x \ge 1}
\end{array}}\\
{ – 1\begin{array}{*{20}{c}}
{}&{x < 0}
\end{array}}
\end{array}} \right.\)

感知机的损失函数

假设训练集是线性可分的,感知机学习的目标是求得一个能将整个训练集中的正实例点跟负实例点完全分开的超平面,即确定感知机模型的参数 \(\omega ,b\)。为此,需要定义一个损失函数,并将损失函数最小化。

设训练集为

\(T = \{ \left( {{x_1},{y_1}} \right),\left( {{x_2},{y_2}} \right),…\left( {{x_N},{y_N}} \right)\} \)

其中\({x_i} \in \chi \subset {R^n}\)\({y_i} \in \gamma = \{ – 1,1\} ,i = 1,2,…,N\)

设集合\(M\)为误分类点的集合,则损失函数可以由所有误分类点到超平面的总距离和来表示,即

\(L(\omega ,b) = \sum\limits_{{x_i} \in M} {\frac{{\left| {\omega {x_i} + b} \right|}}{{\left\| w \right\|}}} \)

不考虑\(\frac{1}{{\left\| \omega \right\|}}\),另外,对于所有误分类点\( – {y_i}(\omega {x_i} + b) > 0\),所以感知机的损失函数可以简化为:

\(L(\omega ,b) = – \sum\limits_{{x_i} \in M} {{y_i}(\omega {x_i} + b)} \)

对于特定的样本点,分类正确时,损失函数的值为 0,分类错误时,损失函数是\(\omega ,b\)的线性函数,因此对于给定训练集\(T\),损失函数是\(\omega ,b\)连续可导函数。

感知机的学习

感知机的学习就是在给定训练集\(T = \{ \left( {{x_1},{y_1}} \right),\left( {{x_2},{y_2}} \right),…\left( {{x_N},{y_N}} \right)\} \)的情况下,求参数\(\omega ,b\),使其为以下损失函数极小化问题的解

\(\mathop {\min }\limits_{\omega ,b} L(\omega ,b) = – \sum\limits_{{x_i} \in M} {{y_i}(\omega {x_i} + b)} \)

感知机的学习,可以采用梯度下降法求解。损失函数的梯度由:

\(\begin{array}{l}
{\nabla _\omega }L(\omega ,b) = – \sum\limits_{{x_i} \in M} {{x_i}{y_i}} \\
{\nabla _b}L(\omega ,b) = – \sum\limits_{{x_i} \in M} {{y_i}}
\end{array}\)

给出。

任意选取一个超平面\({\omega _0},{b_0}\),随机选择一个误分类\(\left( {{x_i},{y_i}} \right)\),对\(\omega ,b\)进行更新

\(\begin{array}{l}
\omega = {\omega _0} + \eta {x_i}{y_i}\\
b = {b_0} + \eta {y_i}
\end{array}\)

其中\(\eta (0 < \eta \le 1)\)是步长(学习率),通过不断的迭代(学习),期待损失函数\(L(\omega ,b)\)不断减小,直至为 0。综上所述,可以得出如下算法:

输入:训练集\(T = \{ \left( {{x_1},{y_1}} \right),\left( {{x_2},{y_2}} \right),…\left( {{x_N},{y_N}} \right)\} \),其中\({x_i} \in \chi \subset {R^n}\),                                                          \({y_i} \in \gamma = \{ – 1,1\} ,i = 1,2,…,N\),学习率\(\eta (0 < \eta \le 1)\)

输出:\(\omega ,b\),感知机模型\(f(x) = sign(\omega \bullet x + b)\)

(1)选取初始值\({\omega _0},{b_0}\)

(2)在训练集上选取数据\(\left( {{x_i},{y_i}} \right)\)

(3)若\({y_i}(\omega {x_i} + b) \le 0\)

\(\begin{array}{l}
\omega = {\omega _{}} + \eta {x_i}{y_i}\\
b = {b_{}} + \eta {y_i}
\end{array}\)

(4)转至(2),直至训练集中没有误分类点为止。

这种算法直观上解释为:当一个实例点被误分类,即位于分离超平面的错误一侧时,则调整\(\omega ,b\)使分离超平面朝该误分类点的一侧移动,以减少该误分类点与分离超平面的距离,直至分离超平面越过该误分类点,使其被正确分类。

喜欢 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址