技术创新篇

第三章 机器学习算法

第一节 总体发展概况

机器学习是指“计算机利用经验自动改善系统自身性能的行为”，是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。简而言之，机器学习指的是计算机可以像人类学习新事物一样，在处理数据的过程中不断地分析规律性信息，获取新的知识和经验，找到更优性能的解决方案以提升系统性能和智能性。它是人工智能核心，是使计算机具有智能的根本途径，是机器智能化道路上迈出的重要一步。

一、发展历程

2016年 3 月 15 日，谷歌公司开发的人工智能机器AlphaGo以总比分 4 : 1 战胜围棋世界冠军李世石，轰动世界的“人机大战”落下帷幕。2017年 1 月 4 日，升级为Master的AlphaGo，经过 7 天的“踢馆”大战，力克国际 60 位顶级围棋高手，再次掀起“腥风血雨”。事实上，早在 20 世纪 50年代，人工智能便开始向人类发起挑战。当时来自IBM工程研究组的萨缪尔（Samuel）开发出一款跳棋程序，该程序能够在与人对弈的过程中，不断累积经验提升棋艺，并于 1959年战胜了萨缪尔本人。应该说，无论是半个多世纪前的“跳棋对决”，还是当前的“人机大战”，推动人工智能发展的核心动力未曾改变，即计算科学的璀璨明珠—机器学习。围棋仅是机器学习应用的极小方面，在过去半个多世纪里，机器学习经历了以下五个发展阶段。

第一阶段，是 20 世纪 40年代的萌芽时期。在这一时期，心理学家McCulloch和数理逻辑学家Pitts引入生物学中的神经元概念，在分析神经元基本特性的基础上，提出“M-P神经元模型”。在该模型中，每个神经元都能接收到来自其他神经元传递的信号，这些信号往往经过加权处理，再与接受神经元内部的阈值进行比较，经过神经元激活函数产生对应的输出。M-P神经元模型主要具有以下特征：

① 每个神经元都是多输入输出的信息处理单元。

② 神经元之间的连接方式包括“兴奋”和“抑制”两种，当某个神经元处于“兴奋”状态时，便会向相连神经元发送信号并改变其“电位”。

③ 每个神经元需要整合所有输入信号并根据阈值决定是否“兴奋”起来，即神经元具有空间整合特性和阈值特性。当接受信号的神经元“电位”超过自身阈值时，便“兴奋”起来并重复信号发送过程。

④ 激活函数的选取应当视具体应用而定，主要分为连续型和非连续型。M-P神经元模型是神经网络学习的基础，而后者则是机器学习中出现时间最早、应用时间最长的模型。

第二阶段，是 20 世纪 50年代中叶至 60年代中叶的热烈时期。尽管在萌芽阶段，神经元的运作过程得到明晰，但神经网络学习的高效运作需要依赖相关学习规则。热烈时期的标志正是经典学习规则的提出。早在 1949年，心理学家Hebb便提出与神经网络学习机理相关的“突触修正”假设。其核心思想是当两个神经元同时处于兴奋状态时，两者的连接度将增强，基于该假设定义的权值调整方法被称为“Hebbian规则”。由于Hebbian规则属于无监督学习，故在处理大量有标签分类问题时存在局限。1957年，美国神经学家Rosenblatt提出了最简单的前向人工神经网络—感知器，开启了有监督学习的先河。感知器的最大特点是能够通过迭代试错解决二元线性分类问题。在感知器被提出的同时，求解算法也相应诞生，包括感知器学习法、梯度下降法和最小二乘法（Delta学习规则）等。1962年，Novikoff推导并证明了在样本线性可分情况下，经过有限次迭代，感知器总能收敛，这为感知器学习规则的应用提供了理论基础。在热烈时期，感知器被广泛应用于文字、声音、信号识别、学习记忆等领域。

第三阶段，是 20 世纪 60年代中叶至 70年代中叶的冷静时期。由于感知器结构单一，并且只能处理简单线性可分问题，故如何突破这一局限，成为理论界关注的焦点。在冷静时期，机器学习的发展几乎停滞不前。究其原因，主要在于：

① 理论匮乏是制约人工神经网络发展的关键因素。

② 随着现实问题难度提升，单层人工神经网络的应用局限越来越多。尽管这一时期出现了Winston的结构学习系统和Roth的逻辑归纳学习系统，但由于只能学习单一概念而未投入实际使用。

③ 计算机有限的内存和缓慢的处理速度使得机器学习算法的应用受到限制。与此同时，这一时期数据库的容量相对较小，数据规模的增大也使得单一机器学习算法效果失真。

④ 以Minsky、Papert等为代表的一批学者对感知器效果提出严重质疑。他们通过严密推导并出版著作（如 1969年出版的《感知器》），来说明感知器应用失败的事实。

在此之后，多国停止了对神经网络研究的资助，这进一步加速了以感知器为核心的单层人工神经网络的衰败。

第四阶段，是 20 世纪 70年代中叶至 80年代末的复兴时期。1980年，美国卡内基梅隆大学举办了首届机器学习国际研讨会，标志着机器学习在世界范围内的复兴。1986年，机器学习领域的专业期刊Machine Learning面世，意味着机器学习再次成为理论及业界关注的焦点。在此复兴时期，机器学习领域的最大突破是人工神经网络种类的丰富，由此弥补了感知器单一结构的缺陷。1983年，加州理工学院物理学家Hopfield采用新型的全互连神经网络，很好地解决了旅行商问题。1986年，UCSD的Rumelhart与McClelland合著《并行分布式处理：认知微结构的探索》一书，提出了应用于多层神经网络的学习规则—误逆差传播算法（BP算法），推动了人工神经网络发展的第二次高潮。除了BP算法，包括SOM（自组织映射）网络、ART（竞争型学习）网络、RBF（径向基函数）网络、CC（级联相关）网络、RNN（递归神经网络）、CNN（卷积神经网络）等在内的多种神经网络也在该时期得到迅猛发展。

第五阶段，是 20 世纪 90年代后的多元发展时期。通过对前面四个阶段的梳理可知，虽然每一阶段都存在明显的区分标志，但几乎都是围绕人工神经网络方法及其学习规则的衍变展开。事实上，除了人工神经网络，机器学习中的其他算法也在这些时期崭露头角。例如，1986年，澳大利亚计算机科学家罗斯·昆兰在Machine Learning上发表了著名的ID3 算法，带动了机器学习中决策树算法的研究。20 世纪 90年代，自1995年苏联统计学家瓦普尼克在Machine Learning上发表SVM（支持向量机）起，以SVM为代表的统计学习便大放异彩，并迅速对符号学习的统治地位发起挑战。与此同时，集成学习与深度学习的提出，成为机器学习的重要延伸。集成学习的核心思想是通过多个基础学习器的结合来完成学习任务，最著名的是Schapire提出的Boosting算法、Freund和Schapire提出的AdaBoost算法、Breiman提出的Bagging算法以及Breiman提出的随机森林算法。进入 21 世纪后，在计算机硬件技术飞速发展，以及研究界和产业界巨大需求刺激下，Ruslan Salakhutdinov和Geoffrey Hinton两位机器学习界泰斗提出了深度学习模型，开启了深度网络机器学习的新时代，围绕此技术的研究与应用开始急速发展，如图 3-1 显示，深度学习随训练数据的提升可有效增加预测准确率。随着后来在云计算、大数据和计算机硬件技术发展的支撑下，深度学习开始在各行各业取得前所未有的成就，一批批成功的商业应用也不断问市。其中具有代表性的应用有来自苹果的Siri、微软的Cortana语音助手，各大支付应用推出的人脸识别认证技术，以及名扬全球的谷歌AlphaGo战胜顶尖人类围棋高手的人机大战事迹，标志着机器学习已经成为计算机科学中的一个重要领域。

二、算法分类

机器学习算法可以分为有监督学习、无监督学习、强化学习 3 种类型。半监督学习可以认为是有监督学习与无监督学习的结合。有监督学习通过训练样本学习得到一个模型，然后用这个模型进行推理。例如，我们如果要识别各种水果的图像，则需要用人工标注的样本进行训练，得到一个模型，接下来，就可以用这个模型对未知类型的水果进行判断，这称为预测。如果只是预测一个类别值，则称为分类问题；如果要预测出一个实数，则称为回归问题，如根据一个人的学历、工作年限、所在城市、行业等特征来预测这个人的收入。

无监督学习则没有训练过程，给定一些样本数据，让机器学习算法直接对这些数据进行分析，得到数据的某些知识。其典型代表是聚类，例如，我们抓取了 1 万个网页，要完成对这些网页的归类，在这里，我们并没有事先定义好的类别，也没有已经训练好的分类模型。聚类算法要自己完成对这 1 万个网页的归类，保证同一类网页是同一个主题的，不同类型的网页是不一样的。无监督学习的另外一类典型算法是数据降维，它将一个高维向量变换到低维空间中，并且要保持数据的一些内在信息和结构。

强化学习是一类特殊的机器学习算法，算法要根据当前的环境状态确定一个动作来执行，然后进入下一个状态，如此反复，目标是让得到的收益最大化。如围棋游戏就是典型的强化学习问题，在每个时刻，要根据当前的棋局决定在什么地方落棋，然后进行下一个状态，反复的放置棋子，直到赢得或者输掉比赛。这里的目标是尽可能赢得比赛，以获得最大的奖励。

三、主流算法

（1）支持向量机算法（Support Vector Machine）

支持向量机算法（SVM）可能是目前最流行、讨论最多的机器学习算法之一，图 3-2 为支持向量机算法示意图。超平面是一条对输入变量空间进行划分的“直线”。支持向量机算法会选出一个将输入变量空间中的点按类（类 0 或类 1）进行最佳分割的超平面。在二维空间中，你可以把他想象成一条直线，假设所有输入点都可以被这条直线完全地划分开来。SVM学习算法旨在寻找最终通过超平面得到最佳类别分割的系数。超平面与最近数据点之间的距离叫作间隔（margin）。能够将两个类分开的最佳超平面是具有最大间隔的直线。只有这些点与超平面的定义和分类器的构建有关，这些点叫作支持向量，它们支持或定义超平面。在实际应用中，人们采用一种优化算法来寻找使间隔最大化的系数值。

（2）线性回归算法（Linear Regression）

在统计学和机器学习领域，线性回归算法可能是最广为人知也最易理解的算法之一，如图 3-3 为线性回归算法示意图。预测建模主要关注的是在牺牲可解释性的情况下，尽可能最小化模型误差或做出最准确的预测。我们将借鉴、重用来自许多其他领域的算法来实现这些目标。线性回归模型被表示为一个方程式，它为输入变量找到特定的权重（即系数B），进而描述一条最佳拟合了输入变量（x）和输出变量（y）之间关系的直线。

（3）逻辑回归算法（Logistic Regression）

逻辑回归是机器学习从统计学领域借鉴过来的另一种技术，图 3-4为逻辑回归算法示意图。它是二分类问题的首选方法，像线性回归一样，Logistic回归的目的也是找到每个输入变量的权重系数值。但不同的是，Logistic回归的输出预测结果是通过一个叫作“logistic函数”的非线性函数变换而来的。logistic函数的形状看起来像一个大的“S”，它会把任何值转换至 0～1 区间内。这十分有用，因为我们可以把一个规则应用于logistic函数的输出，从而得到 0～1 区间内的捕捉值，并预测类别的值。

（4）线性判别算法

线性判别算法是一种传统的分类算法，它的使用场景仅限于二分类问题，图 3-5 为线性判别算法示意图。如果你有两个以上的类，那么线性判别算法（LDA）是首选的线性分类技术。LDA的表示方法非常直接。它包含为每个类计算的数据统计属性。对于单个输入变量而言，这些属性包括每个类的均值和所有类的方差。线性判别分析预测结果是通过计算每个类的判别值、并将类别预测为判别值最大的类而得出的。该技术假设数据符合高斯分布，因此最好预先从数据中删除异常值。LDA是一种简单而有效的分类预测建模方法。

（5）最近邻居/K-近邻算法（K-Nearest Neighbors）

K-近邻算法（KNN）是非常简单而有效的，图 3-6 为K-近邻算法示意图。KNN的模型表示就是整个训练数据集。对新数据点的预测结果是通过在整个训练集上搜索与该数据点最相似的K个实例（近邻）并且总结这K个实例的输出变量而得出的。对于回归问题来说，预测结果可能就是输出变量的均值；而对于分类问题来说，预测结果可能是众数的类的值。关键之处在于如何判定数据实例之间的相似程度。如果你的数据特征尺度相同，那么最简单的度量技术就是使用欧几里得距离，你可以根据输入变量之间的差异直接计算出该值。

（6）K-平均算法（K-Means）

K-平均算法是一种无监督学习算法，为聚类问题提供了一种解决方案，图 3-7 为K-平均算法示意图。K-Means算法把n个点划分到k个集群，使得每个点都属于离他最近的均值对应的集群。重复上述过程一直持续到重心不改变。

（7）决策树算法（Decision Tree）

决策树是一类重要的机器学习预测建模算法，图 3-8 为决策树算法示意图。决策树可以被表示为一棵二叉树。这种二叉树与算法设计和数据结构中的二叉树是一样的，没有什么特别。每个节点都代表一个输入变量（x）和一个基于该变量的分叉点。决策树的叶子结点包含一个用于做出预测的输出变量（y）。预测结果是通过在树的各个分叉路径上游走，直到到达一个叶子结点并输出该叶子结点的类别值而得出。决策树的学习速度很快，做出预测的速度也很快。它们在大量问题中往往都很准确，而且不需要为数据做任何特殊的预处理准备。

（8）朴素贝叶斯算法（Naive Bayes）

朴素贝叶斯是一种简单而强大的预测建模算法，图 3-9 为朴素贝叶斯算法示意图。该模型由两类可直接从训练数据中计算出来的概率组成：①数据属于每一类的概率；②给定每个x值，数据从属于每个类的条件概率。一旦这两个概率被计算出来，就可以使用贝叶斯定理，用概率模型对新数据进行预测。当你的数据是实值的时候，通常假设数据符合高斯分布（钟形曲线），这样你就可以很容易地估计这些概率。朴素贝叶斯之所以被称为“朴素”，是因为它假设每个输入变量相互之间是独立的。这是一种很强的、对于真实数据并不现实的假设。不过，该算法在大量的复杂问题中十分有效。

（9）随机森林算法（Random Forest）

随机森林算法是最流行也是最强大的机器学习算法之一，它是一种集成机器学习算法，图 3-10 为随机森林算法示意图。自助法是一种从数据样本中估计某个量的强大统计学方法，你需要在数据中取出大量的样本，计算均值，然后对每次取样计算出的均值再取平均，从而得到对所有数据的真实均值更好的估计。Bagging使用了相同的方法。但是最常见的做法是使用决策树，而不是对整个统计模型进行估计。Bagging会在训练数据中取多个样本，然后为每个数据样本构建模型。当你需要对新数据进行预测时，每个模型都会产生一个预测结果，Bagging会对所有模型的预测结果取平均值，以便更好地估计真实的输出值。随机森林算法是这种方法的改进，它会创建决策树，这样就不用选择最优分割点，而是通过引入随机性来进行次优分割。因此，为每个数据样本创建的模型比在其他情况下创建的模型更加独特，但是这种独特的方式仍能保证较高的准确率。结合它们的预测结果可以更好地估计真实的输出值。如果使用具有高方差的算法获得了良好的结果，那么通常可以通过该算法来获得更好的结果。

（10）Boosting（增强算法）

Boosting是一种集成技术，它试图集成一些弱分类器来创建一个强分类器，图 3-11 为增强算法示意图。它通过从训练数据中构建一个模型，然后创建第二个模型尝试纠正第一个模型的错误来完成。一直添加模型直到能够完美预测训练集，或添加的模型数量已经达到最大数量。AdaBoost是第一个为二分类开发的真正成功的Boosting算法。这是理解Boosting的最佳起点。现代Boosting算法建立在AdaBoost之上，最显著的是随机梯度提升。AdaBoost与短决策树一起使用。在第一个决策树创建之后，利用每个训练实例上树的性能来衡量下一个决策树应该对每个训练实例付出多少注意力。难以预测的训练数据被分配更多权重，而容易预测的数据分配的权重较少。依次创建模型，每个模型在训练实例上更新权重，影响序列中下一个决策树的学习。在所有决策树建立之后，对新数据进行预测，并且通过每个决策树在训练数据上的精确度评估其性能。因为在纠正算法错误上投入了太多注意力，所以具备已删除异常值的干净数据非常重要。

（11）降维算法（Dimensional Reduction）

在机器学习和统计学领域，降维是指在限定条件下，降低随机变量个数，得到一组“不相关”主变量的过程，并可进一步细分为特征选择和特征提取两大方法，图 3-12 为降维算法示意图。一些数据集可能包含许多难以处理的变量。特别是在资源丰富的情况下，系统中的数据将非常详细。在这种情况下，数据集可能包含数千个变量，其中大多数变量也可能是不必要的，几乎不可能确定我们预测影响的最大变量。此时，我们需要使用降维算法，降维的过程中也可能需要用到其他算法，例如借用随机森林、决策树算法来识别最重要的变量。