感知机

作者: 引线小白-本文永久链接:http://www.limoncc.com/机器学习/2017-04-05-感知器-机器学习13/
知识共享许可协议: 本博客采用署名-非商业-禁止演绎4.0国际许可证

神经网络

神经网络是由简单处理单元构成的大规模并行分布式处理器。


神经元

$$\begin{align}
o_j(t)=f\{[\sum_{i=1}^{n}w_{ij}x_i(t-\tau_{ij})]-T_j\}
\end{align}$$

单神经元—感知机模型(Perceptron)

模型的建立

1943年生理学家W.S.McCulloch和W.A.Pitts提出了形式神经元数学模型,史称M-P模型。开创了神经科学理论研究的新时代!

1949年心理学家Donald Olding Hebb在《行为构成》(Organization of Behavior)中提出了Hebb算法。而且首次提出了连接主义(connectionism):大脑活动是靠脑细胞的组合连接实现的。

1958年美国Frank Rosenblatt提出了感知机(Perceptron)这应该是世界上第一个真正优秀的人工神经网络

概念与符号

下面我们将说明这个模型,
1、 $\displaystyle \boldsymbol{x}=[x_1,…,x_k]^\text{T}$为特征向量, 或者叫输入向量
2、 $\displaystyle \boldsymbol{w}=[w_1,…,w_k]^\text{T}$为权值向量,也可以叫突触权值向量 ,模仿神经元的突触。
3、 $\displaystyle w_0$为阈值。 $\displaystyle o=f$
4、为简洁记令 $\displaystyle x_0=1$,于是有增广特征向量 $\displaystyle \boldsymbol{x}:=[x_0,x_1,…,x_k]^\text{T}$。
5、增广权值向量$\displaystyle \boldsymbol{w}:=[w_0,w_1,…,w_k]^\text{T}$。
6、定义输出 $\displaystyle o$,
7、激活函数:硬限函数 $\displaystyle \mathrm{hardlims}(x)=\begin{cases} 1, &x\geqslant0 \\\ -1, &x<0\end{cases}$。于是有:
$$\begin{align}
o=\mathrm{hardlims}\left(\boldsymbol{w}^\text{T}\boldsymbol{x}\right)
\end{align}$$


神经元
感知机学习与训练
感知机学习算法:误差修正学习算法

对于二分类增广数据集 $\displaystyle \{\boldsymbol{x}_i,y_i\}_{i=1}^{n}$,注意我们用的都是增广数据,$\displaystyle \boldsymbol{x}:=[1,x_1,…,x_k]^\text{T}$,$\displaystyle \boldsymbol{w}:=[w_0,w_1,…,w_k]^\text{T}$,同时 $\displaystyle y=+1\text{ or }-1$,表示 $\displaystyle c_1 \text{ or } c_2$类。 学习误差$\displaystyle y_t-o_t$于是有:


算法:误差修正学习算法1


$1\displaystyle \boldsymbol{w}_0=\boldsymbol{0}$
$2\displaystyle \text{while }\boldsymbol{w}=\text{converged}$ :
$\displaystyle
\quad\begin{array}{|lc}
\boldsymbol{w}_{t+1}=\boldsymbol{w}_t+\eta_t(y_t-o_t)\boldsymbol{x}_t
\end{array}\\
$
3 #end while

如果我们定义 $\displaystyle \boldsymbol{z}=y\times\boldsymbol{x}$,这样取得新的数据集 $\displaystyle \{\boldsymbol{z}_i,y_i\}_{i=1}^{n}$,一般称之为二分类规范增广数据集。在这个数据集下,线性可分意味着:存在一个 $\displaystyle \boldsymbol{w}$使得对于任意的 $\displaystyle \boldsymbol{z}_i$,$\displaystyle \boldsymbol{w}\boldsymbol{z}_i>0$成立。


算法:误差修正学习算法2


$1\displaystyle \boldsymbol{w}_0=\boldsymbol{0}$
$2\displaystyle \text{while }\boldsymbol{w}=\text{converged}$ :
$\displaystyle
\quad\begin{array}{|lc}
\boldsymbol{z}_t=y_t\times\boldsymbol{x}_t\\
\boldsymbol{w}_{t+1}=\boldsymbol{w}_t+2\eta_t\mathbb{I}(\boldsymbol{w}_t^\text{T} \boldsymbol{z}\leqslant 0)\boldsymbol{z}_t
\end{array}\\
$
3 #end while

感知机学习算法:梯度下降算法

分析之前,令 $\displaystyle \boldsymbol{z}=y\times\boldsymbol{x}$,这样我们把属于 $\displaystyle c_2$的特征变成了 $\displaystyle -\boldsymbol{x}$。定义目标函数: $\displaystyle J(\boldsymbol{w})=k \left(|\boldsymbol{w}^\text{T}\boldsymbol{z}|-\boldsymbol{w}^\text{T}\boldsymbol{z}\right),k>0
$ 通常令 $\displaystyle k=1$易知: $\displaystyle \min J(\boldsymbol{w})=0$时, $\displaystyle \boldsymbol{w}^\text{T}\boldsymbol{z}\geqslant 0$,于是分类正确。问题转化为:
$$\begin{align}
\min_{\boldsymbol{w}}J(\boldsymbol{w})
\end{align}$$
我们使用梯度下降算法:
$$\begin{align}
\boldsymbol{w}_{t+1}=\boldsymbol{w}_t-\alpha_t\nabla_t
\end{align}$$

我们知道: $\displaystyle \nabla_t
=\frac{\partial J}{\partial\boldsymbol{w}_t}
=k[\boldsymbol{z}_t\times\mathrm{sgn}\left(\boldsymbol{w}_t^\text{T}\boldsymbol{z}_t\right)-\boldsymbol{z}_t]$ 代入3式得:
$$\begin{align}
\boldsymbol{w}_{t+1}=\boldsymbol{w}_t-\alpha_tk\left[\mathrm{sgn}\left(\boldsymbol{w}_t^\text{T}\boldsymbol{z}_t\right)-1\right]\boldsymbol{z}_t
\end{align}$$
当 $\displaystyle k=1$时,就是误差修正学习算法。


算法:梯度下降算法(Gradient Descent)


$1\displaystyle \boldsymbol{w}_0=\boldsymbol{0}$
$2\displaystyle \text{while }\boldsymbol{w}=\text{converged}$ :
$\displaystyle
\quad\begin{array}{|lc}
\boldsymbol{z}_t=y_t\times\boldsymbol{x}_t\\
\boldsymbol{w}_{t+1}=\boldsymbol{w}_t-\alpha_tk\left[\mathrm{sgn}\left(\boldsymbol{w}_t^\text{T}\boldsymbol{z}_t\right)-1\right]\boldsymbol{z}_t
\end{array}\\
$
3 #end while

感知机学习算法:最小均方误差算法

取任意正数 $\displaystyle \nu_i$,有 $\displaystyle \boldsymbol{\nu}=[\nu_1,…,\nu_k]^\text{T}$。定义误差: $\displaystyle \boldsymbol{\epsilon}=\boldsymbol{X}\boldsymbol{w}-\boldsymbol{\nu}$
$$\begin{align}
\mathrm{MES}(\boldsymbol{w})
=\boldsymbol{\epsilon}^\text{T}\boldsymbol{\epsilon}
=\left[\boldsymbol{X}\boldsymbol{w}-\boldsymbol{\nu}\right]^\text{T}\left[\boldsymbol{X}\boldsymbol{w}-\boldsymbol{\nu}\right]
\end{align}$$
容易知道问题化为
$$\begin{align}
\min_{\boldsymbol{w}} \mathrm{MES}(\boldsymbol{w})
\end{align}$$
知道这就最小二乘解: $\displaystyle \hat{\boldsymbol{w}}
=\left[\boldsymbol{X}^\text{T}\boldsymbol{X}\right]^{-1}\boldsymbol{X}^\text{T}\boldsymbol{\nu}=\boldsymbol{X}^\dagger \boldsymbol{\nu}
$。求解伪逆的计算量大。我们使用梯度下降方法,知道
$$\begin{align}
\nabla\mathrm{MES}(\boldsymbol{w})=2\boldsymbol{X}^\text{T}\left[\boldsymbol{X}\boldsymbol{w}-\boldsymbol{\nu}\right]
\end{align}$$


算法:最小均方误差算法(Least Mean-Square Error)


$1\displaystyle \boldsymbol{w}_0=\boldsymbol{X}^\text{T}\boldsymbol{\nu},\boldsymbol{\nu}>0$
$2\displaystyle \alpha_0=\alpha$
$3\displaystyle \text{while }\boldsymbol{w}=\text{converged}$ :
$\displaystyle
\quad\begin{array}{|lc}
\alpha_t=\alpha\div t\\
\boldsymbol{w}_{t+1}=\boldsymbol{w}_t-2\alpha_t\boldsymbol{X}^\text{T}\left[\boldsymbol{X}\boldsymbol{w}_t-\boldsymbol{\nu}\right]\\
\end{array}\\
$
4 # end while
$5\displaystyle \text{ if }\,\boldsymbol{\epsilon}_{end}=\boldsymbol{X}\boldsymbol{w}_{end}-\boldsymbol{\nu}\geqslant 0$ :
$\displaystyle
\quad\begin{array}{|lc}
\text{print(‘线性可分’)}\\
\end{array}
$
$\displaystyle \,\,\,\,\,\text{else }$ :
$\displaystyle
\quad\begin{array}{|lc}
\text{print(‘线性不可分’)}\\
\end{array}
$
6 # end if

感知器收敛定律
如果样本集合线性可分,那么感知器存在收敛解。
证明:
1、我们使用规范增广数据集 $\displaystyle \{\boldsymbol{z}_i,y_i\}_{i=1}^{n} $

2、假定解向量 $\displaystyle \hat{\boldsymbol{w}}$,则对任意的 $\displaystyle \boldsymbol{z}$有 $\displaystyle \hat{\boldsymbol{w}}^\text{T}\boldsymbol{z}>0$。我们注意到对于 $\displaystyle \delta>0$ ,$\displaystyle \delta\cdot\hat{\boldsymbol{w}}$也是解向量。

3、我们令 $\displaystyle \boldsymbol{z}_t$是所有错分样本, 有
$$\begin{align}
\boldsymbol{w}_t\boldsymbol{z}_t\leqslant 0
\end{align}$$误差修正学习算法中令 $\displaystyle \eta_t=\frac{1}{2}$于是有:
$$\begin{align}
\boldsymbol{w}_{t+1}=\boldsymbol{w}_t+\boldsymbol{z}_t
\end{align}$$
另外我们还令规范增广特征向量最大长度,与解向量最小内积
$$\begin{align}
\beta=\max_t ||\,\boldsymbol{z}_t||
\end{align}$$
$$\begin{align}
\alpha=\min_t \hat{\boldsymbol{w}}^\text{T}\boldsymbol{z}_t>0
\end{align}$$
4、现在我们把解向量 $\displaystyle \delta\hat{\boldsymbol{w}}$考虑进来于是:
$$\begin{align}
&\boldsymbol{w}_{t+1}=\boldsymbol{w}_t+\boldsymbol{z}_t\\
&\boldsymbol{w}_{t+1}-\delta\cdot\hat{\boldsymbol{w}}=\boldsymbol{w}_t-\delta\cdot\hat{\boldsymbol{w}}+\boldsymbol{z}_t\\
&||\boldsymbol{w}_{t+1}-\delta\cdot\hat{\boldsymbol{w}}||^2=||\boldsymbol{w}_t-\delta\cdot\hat{\boldsymbol{w}}+\boldsymbol{z}_t||^2
\end{align}$$
5、范数公式 $\displaystyle ||\boldsymbol{x}+\boldsymbol{y}||^2=||\boldsymbol{x}||^2+ 2<\boldsymbol{x},\boldsymbol{y}>+||\boldsymbol{y||^2},\,<\boldsymbol{x},\boldsymbol{y}>=\boldsymbol{x}^\text{T}\boldsymbol{y}$于是我们有:
$$\begin{align}
&||\boldsymbol{w}_{t+1}-\delta\cdot\hat{\boldsymbol{w}}||^2
=||\boldsymbol{w}_t-\delta\cdot\hat{\boldsymbol{w}}||^2+2 \boldsymbol{w}_t^\text{T}\boldsymbol{z}_t-2\delta\cdot\hat{\boldsymbol{w}}^\text{T}\boldsymbol{z}_t+||\boldsymbol{z}_t||^2
\end{align}$$
6、根据上面的1、2、3的分析,有:
$$\begin{align}
&||\boldsymbol{w}_{t+1}-\delta\cdot\hat{\boldsymbol{w}}||^2
\leqslant ||\boldsymbol{w}_t-\delta\cdot\hat{\boldsymbol{w}}||^2-2\delta\cdot\alpha+\beta^2
\end{align}$$
7、为了简洁令: $\displaystyle \delta=\frac{\beta^2}{\alpha}$于是有:
$$\begin{align}
&||\boldsymbol{w}_{t+1}-\delta\cdot\hat{\boldsymbol{w}}||^2
\leqslant ||\boldsymbol{w}_t-\delta\cdot\hat{\boldsymbol{w}}||^2-\beta^2
\end{align}$$
8、考虑上式 $\displaystyle t=\{0,…,m\}$。并累加得:
$$\begin{align}
&0\leqslant||\boldsymbol{w}_{m+1}-\delta\cdot\hat{\boldsymbol{w}}||^2
\leqslant ||\boldsymbol{w}_0-\delta\cdot\hat{\boldsymbol{w}}||^2-m\cdot\beta^2
\end{align}$$
9、可以看到随着 $\displaystyle m$的不断增加,范数 $\displaystyle ||\boldsymbol{w}_{m+1}-\delta\cdot\hat{\boldsymbol{w}}||^2\to 0$,于是:
$$\begin{align}
m_{max}
= \frac{||\boldsymbol{w}_0-\delta\cdot\hat{\boldsymbol{w}}||^2}{\beta^2}
\end{align}$$
10、如果我们令 $\displaystyle \boldsymbol{w}_0=\boldsymbol{0}$,有:
$$\begin{align}
m_{max}
=\frac{\delta^2}{\beta^2}||\,\hat{\boldsymbol{w}}||=\frac{\beta^2}{\alpha^2}||\,\hat{\boldsymbol{w}}||
\end{align}$$
这时感知机的解收敛于: $\displaystyle \frac{\beta^2}{\alpha}\cdot\hat{\boldsymbol{w}}$。史称感知机固定增量收敛定律。

#### 评述
1、 历史说明:分类是科学之始,为解决分类问题,人类殚精竭虑。其中模仿神经元的感知器就是其中之一。
2、上帝给世界分了两类 $\displaystyle c_1$和 $\displaystyle c_2$。人类观测到了 $\displaystyle \{\boldsymbol{x}_i,y_i\}_{i=1}^{n}$。为了解决问题,人类思考了最简单的方法:劈下一刀,不就两半了。于是有了对称硬限函数。
3、有个负号还是很麻烦,于是定义了 $\displaystyle \boldsymbol{z}=y\times \boldsymbol{x}$ 就有了新的数据集$\displaystyle \{\boldsymbol{z}_i,y_i\}_{i=1}^{n}$ 劈下一刀,变成了的折一下,然后裁一刀的问题
$$\begin{align}
\forall \boldsymbol{z}_i,\boldsymbol{w}^\text{T}\boldsymbol{z}_i>0
\end{align}$$
4、满足上式的问题,我们叫线性可分。并且根据学习规则和对问题认识,人类很块发现了感知机固定增量收敛定律
5、但是好景不长,人类的智者很快发现 线性不过是人类的YY,非线性才是上帝的YY。人类继续着征程: 我们的征途是星辰大海!


版权声明
引线小白创作并维护的柠檬CC博客采用署名-非商业-禁止演绎4.0国际许可证。
本文首发于柠檬CC [ http://www.limoncc.com ] , 版权所有、侵权必究。
本文永久链接http://www.limoncc.com/机器学习/2017-04-05-感知器-机器学习13/

予汝玫瑰,渡人沃土。