人工智能（4）

Genetic Programming

上次我们提到了error-correction ，也即错误纠正的方式去训练和调整模型，是最基本的训练方式，适用于线性可分的情况（linear separable），这种方式也具有自身的局限性，举个例子，假如说现在有四个训练数据，（-1，-1，1），（1，1，1），（1，-1，0），（-1，1，0），括号内前两个值分别是特征，最后一个值是label（标签），这四条数据是线性不可分的一个例子。数据是二维的，对应的在二维平面上，找不到一条直线，能把点（-1，-1），（1，1）分到直线的一边，同时把（1，-1），（-1，1）分到另一边 （分成0和1两类），也即线性不可分，所以说error-correction 过程有局限性。

今天来看一个新的学习过程，Genetic Programming, 中文翻译多用“遗传规划”，这里我们也用遗传规划。

（部分参考自中国香港科技大学AI课程资料）

根据达尔文的进化论，我们人类一步步走到今天，是长时间的演进而来的。同样的，机器能不能也进化呢（Machine Evolution）? 或者往小的说，我们要想训练的模型能不能由一个随机的模型进化成我们想要的模型呢？答案，是可以的。

简单的来说，evolution（进化）的过程主要包括 reproduction （繁殖）和survival of the fittest （择优）。Reproduction的过程其实涉及到三个方面的过程，我们这样去模拟：

Copy（从上一代直接复制下来）

Crossover（混合双亲的基因）

Mutation（变异）

那么survival of fittest 过程需要定义一个function 来选择最合适的那个。比如：假设长颈鹿的进化过程是选择最长脖子的那一个，那么这个function就应该是 从给定的数量的长颈鹿中，找出脖子最长的那一个。这就是一个简单的fitness function。

对于一个模型（或者程序），我们寻求最合适的程序或者模型的过程通常可以这样去实行：

随机产生若干数量（比如5000，10000）的模型，作为第一代模型，下一代模型的产生过程是这样的：

Copy 9% 作为下一代，这9%的选择是择优的一个过程，假设有10000个模型，那么900个模型将会直接复制过来，其中每一个都经过了tournament selection （中文：锦标赛选择，简称TS）过程。TS过程是这样的，随机选择7个模型，用fitness function选出最合适的那一个。Fitness function 依据问题的不同，也不同。就像猎豹的进化可能fitness function 就是选择速度最快的那一个，长颈鹿则是看脖子的长短。（例子如有不当之处，还请指出。。）

Crossover 90%, 也即9000个下一代的产生过程是这样的：

先用TS过程选出一个mother，然后TS过程选出一个father，然后随机的把mother的模型的一部分去替换father模型的对应的部分，从而产生一个新的个体，作为下一代。

Mutation 1%，也即有100个下一代是这样产生的，其中每一个的产生过程是这样的：

首先TS 过程选出一个模型，随机选择模型的某一部分，做出随机的改变。

好了，讲了上面这么多，还有两个疑问，模型是什么？fitness function 是啥？

来看一个实际的问题，假设现在有若干条数据，每一条数据是n维的，也即有n个特征，和对应的标签，标签是0和1假定。希望通过genetic programming的过程确定一个模型，这个模型尽可能的适用于给出的数据。

那么这个模型其实可以是一个n+1维的权重向量，因为数据虽然是n维的，我们一般会加一个数字1，作为第n+1个向量值，这样权重向量的第n+1个值即为threshold（阈值），可以参考上一次的内容。

好，来看一下参考的训练集，

训练过程，最后权重向量趋于稳定值。