机器学习——感知器学习算法

这里开始介绍神经网络方面的知识（Neural Networks）。首先我们会介绍几个监督式学习的算法，随后便是非监督式的学习。

一、感知器学习算法基本介绍

1.神经网络

就像进化计算，神经网络又是一个类似的概念。神经网络由一个或者多个神经元组成。而一个神经元包括输入、输出和“内部处理器”。神经元从输入端接受信息，通过“内部处理器”将这些信息进行一定的处理，最后通过输出端输出。

2.感知器

感知器（Perceptron），是神经网络中的一个概念，在1950s由Frank Rosenblatt第一次引入。

基本概念

线性可分：在特征空间中可以用一个线性分界面正确无误地分开两 类样本；采用增广样本向量，即存 在合适的增广权向量 a 使得：

则称样本是线性可分的。如下图中左图线性可分，右图不可分。所有满足条件的权向量称为解向量。权值空间中所有解向量组成的区域称为解区。

通常对解区限制：引入余量b，要求解向量满足：

使解更可靠（推广性更强），防止优化算法收敛到解区的边界。

感知准则函数及求解

对于权向量a，如果某个样本yk被错误分类，则

。我们可以用对所有错分样本的求和来表示对错分样本的惩罚：

其中Yk是被a错分的样本集合。当且仅当JP(a*) = min JP(a) = 0 时，a*是解向量。这就是Rosenblatt提出的感知器（Perceptron）准则函数。

感知器准则函数的最小化可以使用梯度下降迭代算法求解：

其中，k为迭代次数，η为调整的步长。即下一次迭代的权向量是把当前时刻的权向量向目标函数的负梯度方向调整一个修正量。

因此，迭代修正的公式为：

即在每一步迭代时把错分的样本按照某个系数叠加到权向量上。

通常情况，一次将所有错误样本进行修正不是效率最高的做法，更常用是每次只修正一个样本或一批样本的固定增量法：

收敛性讨论：可以证明，对于线性可分的样本集，采用这种梯度下降的迭代算法：

经过有限次修正后一定会收敛到一个解向量。

理论结论：只要训练样本集是线性可分的，对于任意的初值 a(1) ，经过有限次叠代，算法必定收敛。

感知器是最简单可以“学习”的机器，可以解决线性可分的问题。当样本线性不可分时，感知器算法不会收敛。实际应用中直接使用感知器的场合并不多，但他是很多复杂算法的基础。

3.单层感知器

单层感知器（Single Layer Perceptron）是最简单的神经网络。它包含输入层和输出层，而输入层和输出层是直接相连的。

图1.1

图1.1便是一个单层感知器，很简单一个结构，输入层和输出层直接相连。

接下来介绍一下如何计算输出端。

利用公式1计算输出层，这个公式也是很好理解。首先计算输入层中，每一个输入端和其上的权值相乘，然后将这些乘机相加得到乘机和。对于这个乘机和做如下处理，如果乘机和大于临界值（一般是0），输入端就取1；如果小于临界值，就取-1。

以下就给出一段单层感知器的代码。

[cpp] view plaincopyprint?

1. //////////////////////////////////////////////////////////////////////////
2. //singlelayer perceptrons(SLP)
3. bool slp_calculate_output(constdouble * inputs,constdouble * weights,intnInputs,int & output)
4. {
5. if(NULL ==inputs || NULL == weights)
6. return false;
7. double sum =0.0;
8. for (int i = 0 ; i < nInputs ; ++i)
9. {
10. sum += (weights[i] * inputs[i]);
11. }
12. //这里我们对乘机和的处理：如果大于0，则输出值为1；其他情况，输出值为-1
13. if(sum >0.0)
14. output = 1;
15. else
16. output = -1;
17. }
18. //////////////////////////////////////////////////////////////////////////

单层感知器其简单的特性，可以提供快速的计算。它能够实现逻辑计算中的NOT、OR、AND等简单计算。

但是对于稍微复杂的异或就无能无力。下面介绍的多层感知器，就能解决这个问题。

4.多层感知器

多层感知器（Multi-Layer Perceptrons），包含多层计算。

相对于单层感知器，输出端从一个变到了多个；输入端和输出端之间也不光只有一层，现在又两层:输出层和隐藏层。

图2.2

图2.2就是一个多层感知器。

单个感知器能够完成线性可分数据的分类问题，是一种最简单的可以“学习”的机器。但他无法解决非线性问题。比如下图中的XOR问题：即（1,1）（-1,-1）属于同一类，而（1,-1）（-1,1）属于第二类的问题，不能由单个感知器正确分类。

即在Minsky和Papert的专著《感知器》所分析的：感知器只能解决所谓一阶谓词逻辑问题：与（AND），或（OR）等，而不能解决异或（XOR）等高阶谓词罗辑问题。

用多个感知器实现非线性

单个感知器虽然无法解决异或问题，但却可以通过将多个感知器组合，实现复杂空间的分割。如下图：

将两层感知器按照一定的结构和系数进行组合，第一层感知器实现两个线性分类器，把特征空间分割，而在这两个感知器的输出之上再加一层感知器，就可以实现异或运算。

也就是，由多个感知器组合：

来实现非线性分类面，其中θ(·)表示阶跃函数或符号函数。

多层感知器神经网络

实际上，上述模型就是多层感知器神经网络（Multi-layer perceptron neural networks，MLP neural netwoks）的基础模型。神经网络中每个节点为一个感知器，模型生物神经网络中神经元的基础功能：来自外界（环境或其他细胞）的电信号通过突触传递给神经元，当细胞收到的信号总和超过一定阈值后，细胞被激活，通过轴突向下一个细胞发送电信号，完成对外界信息的加工。

但是，感知器的学习算法并不能直接应用到多层感知器模型的参数学习上。因此，最初提出的学习方案是：除了最后一个神经元之外，事先固定其他所有神经元的权值，学习过程只是用感知器学习算法学习最后一个神经元的权系数。实际上，这相当于通过第一层神经元把原始的特征空间变换到一个新的特征空间，第一层的每个神经元构成新空间的一维，然后在新的特征空间用感知器学习算法构造一个线性分类器。显然，由于第一层的神经元权值需要人为给定，模型的性能很大程度取决于能否设计出恰当的第一层神经元模型，而这取决于对所面临的的问题和数据的了解，并没有针对任意问题求解第一层神经元参数的方法。

对于多层感知器的计算也是比较简单易懂的。首先利用公式1计算每一个。

看一下它代码，就能明白它的工作原理。

[cpp] view plaincopyprint?

1. //////////////////////////////////////////////////////////////////////////
2. //Multi-Layerperceptrons(MLP)
3. const unsignedint nInputs =4;
4. const unsignedint nOutputs = 3;
5. const unsignedint nHiddens = 4;
6. struct mlp
7. {
8. doubleinputs[nInputs+1];//多一个，存放的bias，一般存放入1
9. doubleoutputs[nOutputs];
10. doublehiddens[nHiddens+1]; //多一个，存放的bias，一般存放入1
11. doubleweight_hiddens_2_inputs[nHiddens+1][nInputs+1];
12. doubleweight_outputs_2_hiddens[nOutputs][nHiddens+1];
13. };
14. //这里我们对乘机和的处理：如果大于0，则输出值为1；其他情况，输出值为-1
15. double sigmoid (double val)
16. {
17. if(val >0.0)
18. return1.0;
19. else
20. return-1.0;
21. }
22. //计算输出端
23. bool mlp_calculate_outputs(mlp * pMlp)
24. {
25. if(NULL ==pMlp)
26. return false;
27. double sum =0.0;
28. //首先计算隐藏层中的每一个结点的值
29. for (int h = 0 ; h < nHiddens ; ++h)
30. {
31. doublesum = 0.0;
32. for (int i = 0 ; i < nInputs + 1 ; ++i)
33. {
34. sum += pMlp->weight_hiddens_2_inputs[h][i]*pMlp->inputs[i];
35. }
36. pMlp->hiddens[h] = sigmoid (sum);
38. }
39. //利用隐藏层作为“输入层”，计算输出层
40. for (int o = 0 ; o < nOutputs ; ++o)
41. {
42. doublesum = 0.0;
43. for (int h = 0 ; h < nHiddens + 1 ; ++h)
44. {
45. sum += pMlp->weight_outputs_2_hiddens[o][h]*pMlp->hiddens[h];
46. }
47. pMlp->outputs[o] = sigmoid (sum);
48. }
49. return true;
50. }
51. //////////////////////////////////////////////////////////////////////////

二、感知器学习算法

1.感知器学习

其实感知器学习算法，就是利用第一节介绍的单层感知器。首先利用给的正确数据，计算得到输出值，将输出值和正确的值相比，由此来调整每一个输出端上的权值。

公式2便是用来调整权值，首先 是一个“学习参数”，一般我将它设置成小于1的正数。T便是训练数据中的正确结果，

便是第i个输入端的输入值，

便是第i个输入端上面的权值。

2.代码

对于其介绍，我还是附上代码。

[cpp] view plaincopyprint?

1. //////////////////////////////////////////////////////////////////////////
2. //PerceptronLearning Algorithm(PLA)
3. const unsignedint nTests =4; //训练数据的数量
4. const unsignedint nInputs =2; //输入端的数量
5. const double alpha =0.2; //学习参数
6. struct slp
7. {
8. doubleinputs[nInputs];
9. doubleoutput;
10. }; //单层感知器
11. //计算输出值
12. int compute(double *inputs,double * weights)
13. {
14. double sum =0.0;
15. for (int i = 0 ; i < nInputs; ++i)
16. {
17. sum += weights[i]*inputs[i];
18. }
19. //bias
20. sum += 1.0 * weights[nInputs];
21. if(sum >0.0)
22. return1;
23. else
24. return-1;
25. }
26. //
27. int _tmain(int argc,_TCHAR* argv[])
28. {
29. //正确的训练数据
30. slp slps[nTests] = {
31. {-1.0,-1.0,-1.0},
32. {-1.0, 1.0, 1.0},
33. { 1.0,-1.0, 1.0},
34. { 1.0, 1.0, 1.0}
35. };
36. doubleweights[nInputs + 1] = {0.0};
37. boolbLearningOK = false;
38. //感知器学习算法
39. while(!bLearningOK)
40. {
41. bLearningOK = true;
42. for (int i = 0 ; i < nTests ; ++i)
43. {
44. intoutput = compute(slps[i].inputs,weights);
45. if(output!= (int)slps[i].output)
46. {
47. for(int w = 0 ; w < nInputs ; ++w)
48. {
49. weights[w] += alpha *slps[i].output * slps[i].inputs[w];
50. }
51. weights[nInputs] += alpha *slps[i].output ;
52. bLearningOK = false;
53. }
54. }
55. }
56. for(int w = 0 ; w < nInputs + 1 ; ++w)
57. {
58. cout<<"weight"<<w<<":"<<weights[w] <<endl;
59. }
60. cout<<"\n";
61. for (int i = 0 ;i < nTests ; ++i)
62. {
63. cout<<"rightresult："<<slps[i].output<<"\t";
64. cout<<"caculateresult:" << compute(slps[i].inputs,weights)<<endl;
65. }
67. //
68. char temp ;
69. cin>>temp;
70. return 0;
71. }

2.效果图

下面附上运行效果图

感知器学习算法，算是神经网络中的最简单的学习算法。但是通过这个进入学习神经网络学习算法，是个不错的选择。