商品详情
书名：分片线性分类器设计的新方法 : 组合凸线性感知器
定价：98.0
ISBN：9787030569196
作者：冷强奎,李玉鑑,秦玉平
版次：1
出版时间：2018-03
内容提要：
本书系统论述了分片线性分类器的设计方法及相关问题。全书共六章：第1章介绍分片线性分类器的发展历程和演化趋势，以及传统的分片线性分类器的设计方法，并对其优缺点进行分析和总结；第2章详细论述该领域的*新研究成果，即组合凸线性感知器这一通用理论框架；第3～6章分别从分类精度提升、分类模型简化、克服数据可分性限制和新框架设计等方面论述组合凸线性感知器框架的改进之处和完善策略，这其中包含作者的大部分工作。
目录：
目录
前言
本书所用符号及含义
第1章 绪论 1
1.1 分片线性分类基础 1
1.2 分片线性分类器的设计方法介绍 4
1.2.1 委员会机 4
1.2.2 线性规划方法 6
1.2.3 局部训练方法 9
1.2.4 决策树方法 12
1.2.5 *大-*小可分性方法 14
1.2.6 组合凸线性感知器 16
1.3 *新研究概况 17
1.3.1 生长设计方法 17
1.3.2 极大切割设计方法 18
1.3.3 软间隔设计方法 18
1.3.4 新框架设计 19
第2章 组合凸线器框架 20
2.1 支持向量机简介 20
2.2 支持组合凸线器 23
2.2.1 凸包和可分性 23
2.2.2 线性分类器 24
2.2.3 支持凸线器的定义 26
2.2.4 支持组合凸线器的形式 28
2.2.5 支持组合凸线器的预测规则 31
2.3 小结 32
第3章 生长设计方法 34
3.1 原有设计方法存在的问题 34
3.2 凸线器的生长设计方法 35
3.2.1 挤压操作 35
3.2.2 生长支持凸线器算法 37
3.2.3 算法复杂度 38
3.3 组合凸线器的生长设计方法 39
3.3.1 膨胀操作 39
3.3.2 生长支持组合凸线器算法 41
3.3.3 算法复杂度 43
3.4 实验结果及分析 44
3.4.1 在人工合成数据集上的实验 44
3.4.2 在标准数据集上的实验 45
3.4.3 与NNA和DTA的对比实验 51
3.4.4 在n维单位超球组上的实验 52
3.5 小结 53
第4章 极大切割设计方法 55
4.1 奥卡姆剃刀原理 55
4.2 凸线器的极大切割设计方法 56
4.2.1 极大切割过程 56
4.2.2 极大切割支持凸线器算法 58
4.2.3 算法复杂度 60
4.3 组合凸线器的极大切割设计方法 60
4.3.1 极大切割过程 60
4.3.2 极大切割支持组合凸线器算法 62
4.3.3 算法复杂度 63
4.4 实验结果及分析 64
4.4.1 在人工合成数据集上的实验 64
4.4.2 在标准数据集上的实验 65
4.4.3 与NNA和DTA的对比实验 68
4.4.4 在n维单位超球组上的实验 69
4.5 与生长设计方法的对比分析 70
4.6 小结 72
第5章 软间隔设计方法 73
5.1 显式空间映射 73
5.2 CDMA的带核推广 75
5.2.1 核化的CDMA 76
5.2.2 KCDMA的预测规则 80
5.3 组合凸线器的软间隔设计方法 81
5.3.1 软间隔凸线器设计 81
5.3.2 聚类的软间隔组合凸线器设计 82
5.4 实验结果及分析 84
5.4.1 与SMA的对比实验 84
5.4.2 与SVM、NNA及DTA的对比实验 86
5.4.3 在n维单位超球组上的实验 88
5.4.4 在非叠可分数据集上的实验 89
5.5 小结 90
第6章 交错式组合凸线器设计方法 92
6.1 设计分片线性分类器的新思路 92
6.2 极大凸可分子集 94
6.3 交错式组合凸线器的定义 95
6.4 支持交错式组合凸线器算法 99
6.5 实验结果及分析 102
6.5.1 在Fourclass数据集上的实验 102
6.5.2 在标准数据集上的实验 104
6.5.3 与NNA和DTA的对比实验 106
6.5.4 在n维单位超球组上的实验 106
6.6 小结 107
参考文献 109
结束语 117
在线试读：
第1章 绪论
1.1 分片线性分类基础
模式识别（pattern recognition）是指对表征事物或现象的各种形式信息（如数值、文字或逻辑关系等）进行处理和分析，并*终用于描述、辨认、分类和解释的过程[1]。人通过自己的感官从外界获取信息，经过思维、分析、判断，建立对客观世界的认识，这是一个自然的模式识别过程。具体来讲，收听广播是在做语音识别，阅读报纸是在做文字识别，观看照片是在做图像识别[2]。
随着20世纪40年代计算机的出现及50年代人工智能的兴起，人们希望用计算机来代替或扩展人类的部分脑力劳动。在这种形势下，模式识别在60年代迅速崛起并形成一门新学科，成为信息科学和人工智能的重要组成部分[1]。经过几十年的发展，模式识别研究已经取得了大量成果，在诸多领域实现了成功应用[3, 4]，如医学图像分析、自然语言处理、生物特征识别、文本分类、信用度评价等。
一个典型的模式识别系统由四个递进的阶段组成：模式输入、特征提取和选择、分类器设计、系统评估[5, 6]。模式输入通常由传感器来完成，获取的内容和质量在很大程度上依赖于传感器的特性和局限。特征提取和选择要对原始数据进行变换和挑拣，得到*能反映分类本质的特征。分类器根据特征提取器得到的特征给一个被测对象赋予特定的类别标记。*后，系统对分类器性能做出评估。图1-1给出了模式识别系统设计的基本步骤，虚线箭头表示某些系统可以采用反馈机制。
图1-1 模式识别系统设计的基本步骤
分类器设计是模式识别系统构建的关键环节，其目的在于根据给定的观测或训练数据学习分类规则，获得分类模型或函数，实现对未见样本的预测，并达到尽可能好的泛化能力（generalization ability），即准确预测新样本或未见样本的能力。广义地讲，任何一种设计分类器的方法，只要它利用了训练样本的信息，都可以认为是运用了学习算法[6]。学习算法通常有三种形式，即监督学习、无监督学习和强化学习。监督学习和无监督学习根据学习过程中有无教师信号（类别标签）来区分，而强化学习是指从环境状态到动作映射的学习，以使动作从环境中获得的累积奖赏值*大，它的*优行为策略是通过试错来发现的[7]。
有监督分类是设计分类器时使用*广泛的一种方法，它以训练数据中的类别标签信息为指导，通过分类模型或函数的不断优化和完善来达到在测试数据上的良好预测性能。典型的有监督分类方法包括人工神经网络、支持向量机、*近邻法、决策树、Adaboost等。
尽管一个过分复杂的分类模型单纯对训练样本集能获得近乎完美的表现，但对于新样本则可能不令人满意，这种情况称为过拟合（overfitting）。为了获得较好的泛化能力，在分类器设计时要考虑折中调整模型的复杂程度：既不能太简单以至于不足以描述模式类间的差异，又不能太复杂而对新样本的分类能力有限。
支持向量机（support vector machine，SVM）[8, 9]是上述折中思想的完美体现者。它建立在统计学习理论（statistical learning theory）的VC维（Vapnik-Chervonenkis dimension）理论和结构风险*小化（structural risk minimization）原则（图1-2）的基础之上，根据有限的样本信息在模型复杂性和学习能力（即无错误地识别任意样本的能力）之间寻求*佳折中，以期获得好的泛化能力。它能够保证得到全局*优解，在解决小样本、非线性及高维模式识别中表现出许多特有的优势[10]。SVM已经取得了许多成功的应用[11-24]，一些快速算法被相继提出来[25-30]。随着SVM理论的发展，一些新的方法扩展了原有的基本模型[31-39]。
图1-2 结构风险*小化原则
核函数在SVM中起着至关重要的作用，它通常能够隐式地在高维空间中求解线性可分问题。根据模式识别理论，低维空间中的线性不可分数据通过非线性映射后，在高维特征空间中则可能实现线性可分。但是如果直接采用这种技术在高维空间中进行分类或回归，则存在确定非线性映射的函数形式和参数等难题，并且会导致严重的“维数灾难”问题。而核函数通过将高维特征空间中的内积运算转化为低维输入空间的函数形式，从而巧妙地解决了上述难题。同时，核函数的形式和参数的变化会隐式地改变从输入空间到高维特征空间的映射，并对特征空间的性质产生影响，进而改变各种核函数方法的性能，*终为在高维特征空间解决复杂的分类或回归问题奠定了理论基础。
然而，核函数的选择通常缺乏一定的指导[40-44]，并且隐式映射对空间度量变化的解释存在一定的困难[39, 45]。对研究者来说，一个值得思考的问题是，如何在原输入空间设计分类器，能否在不使用任何隐式映射核函数的情况下，分开任意复杂的两类数据。解决此问题的一个有效策略是发展分片线性分类器，通过分片线性函数的逼近来得到好的分类效果。
分片线性分类器（piecewise linear classifier，PLC）是一种特殊的非线性分类器，它确定的决策面由若干个超平面段组成。因此，与一般超曲面相比，它仍然是简单的，而且不需要根据数据集来设计参数，不需要假设样本的统计分布。同时它能逼近各种形状的超曲面，具有很强的适应能力[46]。上述优点使得分片线性分类器非常适合集成在小型侦察机器人、智能相机、嵌入式/实时系统以及各种便携设备中[47]。
然而，分片线性分类器的设计也存在一定的问题，一般来说，分片线性分类器边界的确定是一个复杂的全局优化问题[48]。在大多数情况下，寻找这样的边界被转化为*小化分类误差函数问题。分片线性分类器的另一个设计目标是选择合适的超平面的数量，但往往这样的训练算法非常复杂，并且导致训练时间过长，这在一定程度上限制了它的应用。为了减少训练时间，并且避开解优化问题，许多启发式的方法被使用，但这些方法经验性太强，不利于推广。
组合凸线性感知器（multiconlitron）[49]无疑在分片线性学习领域迈出了坚实的一步。它是设计分片线性分类器的一个通用理论框架，吸收了SVM的优点，采用SVM的*大间隔思想，但不使用核函数，不进行空间映射，因此可看做SVM的无核推广。同时，它能够*小化训练集上的分类误差，并且动态地获得超平面数量。在标准数据集上的实验已经证实了组合凸线性感知器的有效性。下面首先介绍传统分片线性分类器的设计方法及组合凸线性感知器框架，使读者对分片线性学习的发展有更好的了解。
1.2 分片线性分类器的设计方法介绍
分片线性学习的核心是设计分片线性分类器，这是一项具有挑战性并且复杂的任务，是模式识别领域中的一个基本问题。通常，设计方法的研究主要集中在两个方面：一是*小化分类误差；二是适度选择超平面数量。在这两个目标指导下，一些设计方法被相继提出来，如委员会机、线性规划方法、局部训练方法、决策树方法、*大-*小可分性方法以及组合凸线性感知器等。下面分别针对每一种方法，简述其发展概况。
1.2.1 委员会机
早在20世纪60年代，Nilsson就提出了委员会机（committee machine）的概念[50]。它是一个两层的布尔神经网络，其中每一个委员（即网络中的阈值逻辑单元，也可称为专家）根据计算结果进行二值投票，*后对所有单元的投票进行表决。委员会机可看做分片线性分类器的特殊形式，但它需要复杂的判别步骤，计算代价较大。70年代，Meisel[51]对委员会机做了一些改进，通过*小化概率密度函数（probability density function）来解决超平面的放置问题，但这种改进对密度函数的评估仍然存在困难。委员会机的一般结构如图1-3所示。
20世纪90年代，委员会机开始受到广泛关注，一些改进和提高被相继提出来。集成平均（ensemble averaging）方法[52, 53]通过引入Cauchy不等式证实了使用集成平均得到的预测误差要小于或等于原始委员会机的预测误差。随着研究的深入，人们发现如果通过某种扰动使得委员之间的相关性降低，那么委员会方法的泛化性能能够得到进一步提高。基于这种思想，Breiman[54]提出了经典的Bagging（bootstrap aggregation）方法，该方法通过可重复取样（bootstrap sampling）来增加网络的差异度，从而提高泛化能力。Boosting[55, 56]是训练委员会机的另外一种方法，它的各个预测函数只能顺序生成，并且各轮训练集的选择与前面各轮的学习结果有关。但Boosting方法需要大规模数据来执行训练，导致其在解决实际问题中表现并不理想。AdaBoost[57]的提出能够在一定程度上解决上述问题，它结合了Boosting和Bagging两种方法，不需要使用大规模的训练集。AdaBoost能够非常容易地应用到实际问题中，它已成为目前*流行的Boosting方法。关于Bagging与Boosting的区别，在文献[58]和[59]中已经有详细介绍，这里就不再赘述。另一种类型的委员会机称为混合专家模型（mixture of experts）[60]，它采用分而治之的模块化策略，由不同的委员负责建模输入空间的不同区域。与集成平均方法不同的是，在混合专家模型中，输入会对输出产生一定的影响，这种影响通过加到输入上面的选通网络（gating network）来实现[58]。
图1-3 委员会机的一般结构
需要说明的是，早期委员会机中的委员可能只是一个神经元，而后来的诸多方法均使用神经网络作为投票或评估委员。目前，许多方法已经不再称为委员会机，而是形成了一个新的概念，即神经网络集成[61]或集成学习[62]。随着该概念的提出和明确，集成方法已经构成了一个新的研究领域和方向，并且取得了蓬勃发展。
本书引入委员会机的目的有两个：一是它可以看做早期的分片线性分类器，而集成平均、Bagging、Boosting、混合专家模型这些流行方法与它一脉相承，都可以看做它的推广和发展；二是引出分片线性分类器与神经网络存在一定的关联。Vriesenga和Sklansky[63]指出，任意一个分片线性分类器均能设计为一个3层的神经网络。其中，第1层使用多个超平面将输入空间划分为多个区域，第2层标定每个区域的类别，第3层将多个区域组合起来进行决策。分片线性分类器与神经网络的对应关系如图1-4和图1-5所示。
图1-4 超平面划分的例子
图1-5 超平面划分对应的3层网络结构
由于委员会机是一种网络结构，因此它也存在人工神经网络所共有的缺点，如模型难以构建、委员个数不易确定、网络训练依靠经验等。
1.2.2 线性规划方法
1968年，Mangasarian[64]提出了一种多平面模式分类技术，该技术基于线性规
定价：98.0
ISBN：9787030569196
作者：冷强奎,李玉鑑,秦玉平
版次：1
出版时间：2018-03
内容提要：
本书系统论述了分片线性分类器的设计方法及相关问题。全书共六章：第1章介绍分片线性分类器的发展历程和演化趋势，以及传统的分片线性分类器的设计方法，并对其优缺点进行分析和总结；第2章详细论述该领域的*新研究成果，即组合凸线性感知器这一通用理论框架；第3～6章分别从分类精度提升、分类模型简化、克服数据可分性限制和新框架设计等方面论述组合凸线性感知器框架的改进之处和完善策略，这其中包含作者的大部分工作。
目录：
目录
前言
本书所用符号及含义
第1章 绪论 1
1.1 分片线性分类基础 1
1.2 分片线性分类器的设计方法介绍 4
1.2.1 委员会机 4
1.2.2 线性规划方法 6
1.2.3 局部训练方法 9
1.2.4 决策树方法 12
1.2.5 *大-*小可分性方法 14
1.2.6 组合凸线性感知器 16
1.3 *新研究概况 17
1.3.1 生长设计方法 17
1.3.2 极大切割设计方法 18
1.3.3 软间隔设计方法 18
1.3.4 新框架设计 19
第2章 组合凸线器框架 20
2.1 支持向量机简介 20
2.2 支持组合凸线器 23
2.2.1 凸包和可分性 23
2.2.2 线性分类器 24
2.2.3 支持凸线器的定义 26
2.2.4 支持组合凸线器的形式 28
2.2.5 支持组合凸线器的预测规则 31
2.3 小结 32
第3章 生长设计方法 34
3.1 原有设计方法存在的问题 34
3.2 凸线器的生长设计方法 35
3.2.1 挤压操作 35
3.2.2 生长支持凸线器算法 37
3.2.3 算法复杂度 38
3.3 组合凸线器的生长设计方法 39
3.3.1 膨胀操作 39
3.3.2 生长支持组合凸线器算法 41
3.3.3 算法复杂度 43
3.4 实验结果及分析 44
3.4.1 在人工合成数据集上的实验 44
3.4.2 在标准数据集上的实验 45
3.4.3 与NNA和DTA的对比实验 51
3.4.4 在n维单位超球组上的实验 52
3.5 小结 53
第4章 极大切割设计方法 55
4.1 奥卡姆剃刀原理 55
4.2 凸线器的极大切割设计方法 56
4.2.1 极大切割过程 56
4.2.2 极大切割支持凸线器算法 58
4.2.3 算法复杂度 60
4.3 组合凸线器的极大切割设计方法 60
4.3.1 极大切割过程 60
4.3.2 极大切割支持组合凸线器算法 62
4.3.3 算法复杂度 63
4.4 实验结果及分析 64
4.4.1 在人工合成数据集上的实验 64
4.4.2 在标准数据集上的实验 65
4.4.3 与NNA和DTA的对比实验 68
4.4.4 在n维单位超球组上的实验 69
4.5 与生长设计方法的对比分析 70
4.6 小结 72
第5章 软间隔设计方法 73
5.1 显式空间映射 73
5.2 CDMA的带核推广 75
5.2.1 核化的CDMA 76
5.2.2 KCDMA的预测规则 80
5.3 组合凸线器的软间隔设计方法 81
5.3.1 软间隔凸线器设计 81
5.3.2 聚类的软间隔组合凸线器设计 82
5.4 实验结果及分析 84
5.4.1 与SMA的对比实验 84
5.4.2 与SVM、NNA及DTA的对比实验 86
5.4.3 在n维单位超球组上的实验 88
5.4.4 在非叠可分数据集上的实验 89
5.5 小结 90
第6章 交错式组合凸线器设计方法 92
6.1 设计分片线性分类器的新思路 92
6.2 极大凸可分子集 94
6.3 交错式组合凸线器的定义 95
6.4 支持交错式组合凸线器算法 99
6.5 实验结果及分析 102
6.5.1 在Fourclass数据集上的实验 102
6.5.2 在标准数据集上的实验 104
6.5.3 与NNA和DTA的对比实验 106
6.5.4 在n维单位超球组上的实验 106
6.6 小结 107
参考文献 109
结束语 117
在线试读：
第1章 绪论
1.1 分片线性分类基础
模式识别（pattern recognition）是指对表征事物或现象的各种形式信息（如数值、文字或逻辑关系等）进行处理和分析，并*终用于描述、辨认、分类和解释的过程[1]。人通过自己的感官从外界获取信息，经过思维、分析、判断，建立对客观世界的认识，这是一个自然的模式识别过程。具体来讲，收听广播是在做语音识别，阅读报纸是在做文字识别，观看照片是在做图像识别[2]。
随着20世纪40年代计算机的出现及50年代人工智能的兴起，人们希望用计算机来代替或扩展人类的部分脑力劳动。在这种形势下，模式识别在60年代迅速崛起并形成一门新学科，成为信息科学和人工智能的重要组成部分[1]。经过几十年的发展，模式识别研究已经取得了大量成果，在诸多领域实现了成功应用[3, 4]，如医学图像分析、自然语言处理、生物特征识别、文本分类、信用度评价等。
一个典型的模式识别系统由四个递进的阶段组成：模式输入、特征提取和选择、分类器设计、系统评估[5, 6]。模式输入通常由传感器来完成，获取的内容和质量在很大程度上依赖于传感器的特性和局限。特征提取和选择要对原始数据进行变换和挑拣，得到*能反映分类本质的特征。分类器根据特征提取器得到的特征给一个被测对象赋予特定的类别标记。*后，系统对分类器性能做出评估。图1-1给出了模式识别系统设计的基本步骤，虚线箭头表示某些系统可以采用反馈机制。
图1-1 模式识别系统设计的基本步骤
分类器设计是模式识别系统构建的关键环节，其目的在于根据给定的观测或训练数据学习分类规则，获得分类模型或函数，实现对未见样本的预测，并达到尽可能好的泛化能力（generalization ability），即准确预测新样本或未见样本的能力。广义地讲，任何一种设计分类器的方法，只要它利用了训练样本的信息，都可以认为是运用了学习算法[6]。学习算法通常有三种形式，即监督学习、无监督学习和强化学习。监督学习和无监督学习根据学习过程中有无教师信号（类别标签）来区分，而强化学习是指从环境状态到动作映射的学习，以使动作从环境中获得的累积奖赏值*大，它的*优行为策略是通过试错来发现的[7]。
有监督分类是设计分类器时使用*广泛的一种方法，它以训练数据中的类别标签信息为指导，通过分类模型或函数的不断优化和完善来达到在测试数据上的良好预测性能。典型的有监督分类方法包括人工神经网络、支持向量机、*近邻法、决策树、Adaboost等。
尽管一个过分复杂的分类模型单纯对训练样本集能获得近乎完美的表现，但对于新样本则可能不令人满意，这种情况称为过拟合（overfitting）。为了获得较好的泛化能力，在分类器设计时要考虑折中调整模型的复杂程度：既不能太简单以至于不足以描述模式类间的差异，又不能太复杂而对新样本的分类能力有限。
支持向量机（support vector machine，SVM）[8, 9]是上述折中思想的完美体现者。它建立在统计学习理论（statistical learning theory）的VC维（Vapnik-Chervonenkis dimension）理论和结构风险*小化（structural risk minimization）原则（图1-2）的基础之上，根据有限的样本信息在模型复杂性和学习能力（即无错误地识别任意样本的能力）之间寻求*佳折中，以期获得好的泛化能力。它能够保证得到全局*优解，在解决小样本、非线性及高维模式识别中表现出许多特有的优势[10]。SVM已经取得了许多成功的应用[11-24]，一些快速算法被相继提出来[25-30]。随着SVM理论的发展，一些新的方法扩展了原有的基本模型[31-39]。
图1-2 结构风险*小化原则
核函数在SVM中起着至关重要的作用，它通常能够隐式地在高维空间中求解线性可分问题。根据模式识别理论，低维空间中的线性不可分数据通过非线性映射后，在高维特征空间中则可能实现线性可分。但是如果直接采用这种技术在高维空间中进行分类或回归，则存在确定非线性映射的函数形式和参数等难题，并且会导致严重的“维数灾难”问题。而核函数通过将高维特征空间中的内积运算转化为低维输入空间的函数形式，从而巧妙地解决了上述难题。同时，核函数的形式和参数的变化会隐式地改变从输入空间到高维特征空间的映射，并对特征空间的性质产生影响，进而改变各种核函数方法的性能，*终为在高维特征空间解决复杂的分类或回归问题奠定了理论基础。
然而，核函数的选择通常缺乏一定的指导[40-44]，并且隐式映射对空间度量变化的解释存在一定的困难[39, 45]。对研究者来说，一个值得思考的问题是，如何在原输入空间设计分类器，能否在不使用任何隐式映射核函数的情况下，分开任意复杂的两类数据。解决此问题的一个有效策略是发展分片线性分类器，通过分片线性函数的逼近来得到好的分类效果。
分片线性分类器（piecewise linear classifier，PLC）是一种特殊的非线性分类器，它确定的决策面由若干个超平面段组成。因此，与一般超曲面相比，它仍然是简单的，而且不需要根据数据集来设计参数，不需要假设样本的统计分布。同时它能逼近各种形状的超曲面，具有很强的适应能力[46]。上述优点使得分片线性分类器非常适合集成在小型侦察机器人、智能相机、嵌入式/实时系统以及各种便携设备中[47]。
然而，分片线性分类器的设计也存在一定的问题，一般来说，分片线性分类器边界的确定是一个复杂的全局优化问题[48]。在大多数情况下，寻找这样的边界被转化为*小化分类误差函数问题。分片线性分类器的另一个设计目标是选择合适的超平面的数量，但往往这样的训练算法非常复杂，并且导致训练时间过长，这在一定程度上限制了它的应用。为了减少训练时间，并且避开解优化问题，许多启发式的方法被使用，但这些方法经验性太强，不利于推广。
组合凸线性感知器（multiconlitron）[49]无疑在分片线性学习领域迈出了坚实的一步。它是设计分片线性分类器的一个通用理论框架，吸收了SVM的优点，采用SVM的*大间隔思想，但不使用核函数，不进行空间映射，因此可看做SVM的无核推广。同时，它能够*小化训练集上的分类误差，并且动态地获得超平面数量。在标准数据集上的实验已经证实了组合凸线性感知器的有效性。下面首先介绍传统分片线性分类器的设计方法及组合凸线性感知器框架，使读者对分片线性学习的发展有更好的了解。
1.2 分片线性分类器的设计方法介绍
分片线性学习的核心是设计分片线性分类器，这是一项具有挑战性并且复杂的任务，是模式识别领域中的一个基本问题。通常，设计方法的研究主要集中在两个方面：一是*小化分类误差；二是适度选择超平面数量。在这两个目标指导下，一些设计方法被相继提出来，如委员会机、线性规划方法、局部训练方法、决策树方法、*大-*小可分性方法以及组合凸线性感知器等。下面分别针对每一种方法，简述其发展概况。
1.2.1 委员会机
早在20世纪60年代，Nilsson就提出了委员会机（committee machine）的概念[50]。它是一个两层的布尔神经网络，其中每一个委员（即网络中的阈值逻辑单元，也可称为专家）根据计算结果进行二值投票，*后对所有单元的投票进行表决。委员会机可看做分片线性分类器的特殊形式，但它需要复杂的判别步骤，计算代价较大。70年代，Meisel[51]对委员会机做了一些改进，通过*小化概率密度函数（probability density function）来解决超平面的放置问题，但这种改进对密度函数的评估仍然存在困难。委员会机的一般结构如图1-3所示。
20世纪90年代，委员会机开始受到广泛关注，一些改进和提高被相继提出来。集成平均（ensemble averaging）方法[52, 53]通过引入Cauchy不等式证实了使用集成平均得到的预测误差要小于或等于原始委员会机的预测误差。随着研究的深入，人们发现如果通过某种扰动使得委员之间的相关性降低，那么委员会方法的泛化性能能够得到进一步提高。基于这种思想，Breiman[54]提出了经典的Bagging（bootstrap aggregation）方法，该方法通过可重复取样（bootstrap sampling）来增加网络的差异度，从而提高泛化能力。Boosting[55, 56]是训练委员会机的另外一种方法，它的各个预测函数只能顺序生成，并且各轮训练集的选择与前面各轮的学习结果有关。但Boosting方法需要大规模数据来执行训练，导致其在解决实际问题中表现并不理想。AdaBoost[57]的提出能够在一定程度上解决上述问题，它结合了Boosting和Bagging两种方法，不需要使用大规模的训练集。AdaBoost能够非常容易地应用到实际问题中，它已成为目前*流行的Boosting方法。关于Bagging与Boosting的区别，在文献[58]和[59]中已经有详细介绍，这里就不再赘述。另一种类型的委员会机称为混合专家模型（mixture of experts）[60]，它采用分而治之的模块化策略，由不同的委员负责建模输入空间的不同区域。与集成平均方法不同的是，在混合专家模型中，输入会对输出产生一定的影响，这种影响通过加到输入上面的选通网络（gating network）来实现[58]。
图1-3 委员会机的一般结构
需要说明的是，早期委员会机中的委员可能只是一个神经元，而后来的诸多方法均使用神经网络作为投票或评估委员。目前，许多方法已经不再称为委员会机，而是形成了一个新的概念，即神经网络集成[61]或集成学习[62]。随着该概念的提出和明确，集成方法已经构成了一个新的研究领域和方向，并且取得了蓬勃发展。
本书引入委员会机的目的有两个：一是它可以看做早期的分片线性分类器，而集成平均、Bagging、Boosting、混合专家模型这些流行方法与它一脉相承，都可以看做它的推广和发展；二是引出分片线性分类器与神经网络存在一定的关联。Vriesenga和Sklansky[63]指出，任意一个分片线性分类器均能设计为一个3层的神经网络。其中，第1层使用多个超平面将输入空间划分为多个区域，第2层标定每个区域的类别，第3层将多个区域组合起来进行决策。分片线性分类器与神经网络的对应关系如图1-4和图1-5所示。
图1-4 超平面划分的例子
图1-5 超平面划分对应的3层网络结构
由于委员会机是一种网络结构，因此它也存在人工神经网络所共有的缺点，如模型难以构建、委员个数不易确定、网络训练依靠经验等。
1.2.2 线性规划方法
1968年，Mangasarian[64]提出了一种多平面模式分类技术，该技术基于线性规