第6章 算法进化
计算机能学习吗？
在手机上打字很麻烦。为了让打字方便，很多手机都能猜你要打什么字。打得越多，就猜得越准。这是通过学习你的习惯实现的。计算机学家已经发明了很多方法可以让计算机学习。其中许多都是基于复杂引擎的变体。在生命的世界里，进化源自对环境信息的累积——也就是学习。当DNA序列产生微小的随机变化，自然选择会留下那些能产生更“适应”环境的生物的DNA。进化出适应性表明系统获得了其适应对象的信息。鱼适合在水中生活，鸟能飞翔，这都是因为与其生存环境相关的许多信息被存储在它们各自的DNA中。这一章关注的一个方面就是这种适应信息的来源。我们将看到实际上只有两种可能的来源：信息要么是来自其适应的对象，要么就是随机产生，然后选择那些能提高适应性的变化来提取信息。无论哪种情况都可以将这种获得信息的过程视为学习。
计算机与人类大脑相比有两个优势：很快，而且能准确地复制信息。但学习不仅仅是复制。学习涉及抽象。当你下载一个程序或一段音乐，你的计算机会存储数据的准确拷贝。计算机很擅长做这种事情。
但是当你学一首歌或上一堂课时，发生的事情很不一样：你在创建表示这首歌或这节课的神经连接模式，这种模式能引发特定的行为，并存储新的记忆。你在头脑中创建的神经模式与你的老师或作曲者头脑中的模式并不完全一样。我们擅长学习抽象的思想，而不擅长准确的记忆。如果你不相信这一点，可以去访问一下某个事故或大事件的目击者。
计算机学习的概念很难界定，但容易认识到。它必然涉及获取新的信息，并且不仅仅是简单的记忆。学习一词意味着获得推理的能力。学到的东西让计算机可以解决以前从未遇到过的问题。这是智能的标志之一。因此，计算机学习也被称为人工智能。
一个常见的学习任务是模式识别，比如在人群中识别一张脸。机器在学习识别模式时有一个简单方式是人工神经网络（ANN）。在计算机科学中，神经网络一词指的是一种以有序方式组织的逻辑系统，如图6.1所示，并不是指的基于生物神经元的系统。
图6.1 人工神经网络（ANN）。箭头表示节点之间具有方向和权重的连接。方块表示节点
神经网络由3个特征刻画：节点、连接和权重。节点（图中的方块）是接受输入，计算，然后通过连接输出的逻辑装置。节点相互连接，每个连接都有权重，权重决定连接对下一节点的作用效果；权重越大，作用就越大。图6.1展示的网络有3层，上一层的每个节点都连接到下一层的每个节点。一个ANN至少要有2层，也可以多于3层。上一层的节点不一定都要连接下一层的所有节点，有时候还可以有反向连接。图6.1中的ANN只有前向连接。
ANN的运作原理如下。电压或符号0和1形式的信号（信息）输入到输入层。这些输入一起组成了需要处理的数据集。每个输入节点的信号通过图中用箭头表示的连接继续传送到隐藏层的节点。信号在通过连接传送时会乘以权重因子。权重可正可负；若权重为零，连接就不传递信号。隐藏层节点根据某个简单规则对输入进行加权得到输出信号。例如，可以取输入的均值。处理后，隐藏层节点会把信号送到输出层。这些信号也会乘以权重，然后输出层根据这些加权输入计算一个值。最后的输出组成“答案”。
这种方式的输出是确定性的；它们完全取决于输入值和权重。一些ANN能产生复杂的输出（很多输出节点），一些则只有简单输出（一两个输出节点）。图6.1中的ANN就是两个输出节点。输出可以是两个数或两个电压，可以解读成是或否，或者是、可能和否。例如，如果输入描述的是一幅数字图像的像素，那么是或否的输出可能回答的是如下问题：图中是你的姨妈吗？
要让ANN能正确识别出图片里的姨妈，就必须进行训练。训练的目的是寻找合适的权重，这样一旦输入具有某种特征，就能产生特定的输出模式。一般是给ANN各种输入，一些是正面例子，一些不是。如果目标是识别出你姨妈的照片，权重就必须调整到可以对有姨妈的图像输出是，对没有姨妈的图像输出否。让人吃惊的是，有可能找到这样的权重组合（只要所有有姨妈的图像具有某种独特性）。通过训练，ANN可以从没有见过的图像中识别出有姨妈的图像。现在有很多商业软件已经应用了这种学习方式。
寻找合适的权重有两种不同的策略。一种原理很简单，只需对权重进行随机的微小变动，然后使用表现更好的作为下一轮随机变动的种子。也就是说进化出合适的权重。这种策略很有效，但是很慢。还有一种方法是利用所谓的反向传播计算权重。反向传播需要对实际输出和期望输出之间的差别进行量化。还要计算节点输出对各种输入权重的敏感度。如果能够对各节点进行这种分析，就能在每次训练后计算新权重，让新的输出更接近期望值。训练越多，表现就越好。
与对随机变化进行选择相比，反向传播更快，因此在条件允许时通常被采用。但如果条件不允许，例如不知道目标输出值，或者没有最优答案时，基于随机变化的策略就是唯一的选择。有一个例子是用ANN帮助设计更好的机翼。不知道最好的答案，但在引入新的设计约束时，适当训练的神经网络能给出供测试用的解决方案。
ANN只是用于机器学习的许多策略之一
。学习的目标基本都是将一个大的可能性空间分成两个或多个子空间，让所有的正例都属于其中一个子空间，所有的反例都属于其他子空间。对于ANN来说，空间由所有可能的权重和输入组成。就算是规模不大的ANN，可能的权重和输入的组合的数量也很大，无法一一验证。这时必须发展抽象规则。所有机器学习策略都涉及反复的训练，大部分都会在训练中调整参数，计算出比之前的值更好的新值。如果理想值可以直接计算出来，就不用训练了，也不需要学习了。答案直接计算出来。
机器学习算法让计算机可以从训练集获取信息。要做到这一点最简单的办法就是记住训练集中的所有例子，但这需要存储很多数据，而且一旦遇到的问题没有包含在训练集中就没办法了。要解决没有遇到过的问题，必须对信息进行概括后再存储。受过训练的神经网络的权重就是概括信息的例子，通过适当训练，神经网络就可以用这些信息正确分析没有遇到过的输入。
反向传播是一个很有用的确定性技术，但只有可以用数学方法将外部数据的信息融合进权重时才有可能。许多问题无法构造成这种形式。如果不知道或者无法从期望的答案中提取所需的信息，那还有什么信息来源呢？答案出人意料：随机猜测加选择。随机猜测能为任何问题提供答案，问题是要找到一个有效的方法来利用这个缺乏组织的信息源。
如果学习策略完全依靠随机猜测，在大多数时候，好的答案会淹没在糟糕答案的海洋中。显然要解决这个困难得想办法进化出答案。事实上许多实际问题都有多个答案，一些答案比另一些要好一些，而且好的答案可以通过微小的变化进行改进。投资策略、机翼和运输网络只是其中一小部分例子。工程师们遇到的许多问题都有这个特点。
细微的改进有一个很重要的特点是它们通常具有一定的可能性。复杂引擎就是利用了细微改进具有合理的可能性这个优势，虽然大的改善基本不可能。通过这种方式可以很容易找到好的答案，我们可以通过一些简单的进化算法的例子来认识这一点。