【现货速发】模式识别

模式识别是从输入数据中自动提取有用的模式并将其用于决策的过程, 一直以来都是计算机科学及相关领域的重要研究内容之一. 当前受到高度重视的深度学习技术, 其应用主要也是各种模式识别任务. 模式识别在社会生活的各个方面均有广泛的直接应用, 而相关的人才缺口却相当大, 也就是说, 我们为加强模式识别及相关领域的人才培养添砖加瓦是很有必要的.

本书作为模式识别领域的入门教材, 目的就是介绍模式识别中的基础知识、主要模型及热门应用, 通过理论学习和动手实践相结合的形式使初学者能有效入门, 并培养独立解决任务的能力, 为模式识别的项目开发及相关科研活动打好基础.

在模式识别领域中已经出版了若干经典的中、英文教材, 那么, 是否还需要一本新的教材 (比如你眼前的这一本) 呢？

受诸多因素 (例如深度学习的广泛普及) 影响, 目前模式识别体现出一些与 10 年前较为不同的特性, 而本领域的一些经典教材大多出版于 10 年之前. 因此, 本书除了在后一章介绍了卷积神经网络这一主要的深度学习模型之外, 还在各处给出近年来本领域一些新的成果和观点.

然而, 作为一本入门教材, 笔者的主要目的亦本书的特点是: 即便某些读者在数学知识和其他相关背景知识方面的基础一般, 甚至薄弱, 本书通过使用示例、图解、强调方法的来龙去脉(意图、用途、适用条件)、不省略任何推导步骤、适时补充背景知识及鼓励动手实践等方式, 力图使这些基础有所欠缺的读者也能顺利理解书中的内容！

本书第 14 章可作为一个例子来说明上述特点. 期望化 (EM) 方法在模式识别与机器学习领域均非常重要. 然而, 在经典教材 [20] 中, EM 方法只占了 7 页, 而其核心的数学推导部分甚至仅用了 2 页的篇幅加以说明！笔者就曾经试图用 [20] 的内容来向一位朋友 (美国相关专业排名前 10 某学校的一位博士) 解释 EM 方法, 结果很令人沮丧. 这样简练的教材或许适合一些有经验的读者抑或是天才的读者, 却未必普遍适用于大多数教程所面向的读者群体.

在本书第 14 章中, 我们首先通过一个实例 (高斯混合模型, GMM) 来引入 EM 方法, 介绍其必要性和主要的思路, 从而为 EM 方法的形式化建模铺平道路; 然后, 对这个形式上很短小精干的算法, 以该实例为例, 详尽地揭示每一步的推导步骤及其含义; 后, 水到渠成地得到GMM 的 EM 更新公式. 在这章的一道习题中, 我们要求读者在不借助于教材内容的前提下, 独立完成所有的推导; 在另外一道习题中, 我们分步骤给出足够的提示, 希望读者能独立推导Baum-Welch——另一个经典算法的 EM 更新公式. 对于同样的 EM 主题, 笔者使用了 15 页的篇幅, 相信这样的安排不仅有助于读者较容易地学会 EM 方法, 还可以深入理解其思想与优缺点, 甚至能够有所推广.

具体来说, 本书在写作时希望具有以下特点:

• 强调可读. 通过增加样例 (包括图例)、解释意图、详细推导 (不省略任何中间步骤) 等方法, 力图使得中等水平的读者可以完全理解课程内容, 包括一些相对复杂的数学推导. 本书在专用名词首次出现的时候提供其对应的英文词组, 并在书末提供了中文和英文两个索引,有助于读者建立中英文专业术语之间的对应关系. 同时, 本书的第 2 章简要总结了本科数学教学中对本书有用的一部分知识, 并额外补充了一些必要的数学知识.
• 注重实践. 模式识别是一门实践性很强的学科, 笔者在教材章节, 尤其是习题中注意培养动手能力, 并强调一些理论推导涉及不到但在实践中却极其重要的实现细节. 本书的习题中有若干需要读者自行安装软件、阅读文档并编程解决的问题. 本书的大部分习题由笔者设计完成, 设计习题大概花了一年的时间. 如果想完全理解课程内容, 完成每章的习题是非常重要的.
• 拓广视野. 笔者注意从学科整体而不是从单个技术或方法的角度来介绍各章内容. 尽管本书详细介绍的只是经过仔细选择的一些核心内容, 但通常会对其他相关技术的意义、要点及如何获取更多相关知识也进行简要的描述. 例如, 在习题中介绍了指数族(exponentialfamily)、局部线性嵌入 (LLE) 等内容, 并在每一章的后一节提供阅读材料的指南.
• 培养能力. 通过样例、推导等潜移默化的手段, 培养学生以下两个方面的能力. 首先, 在面对一个新的问题时, 能够按照问题剖析、产生想法、形式化定义、问题简化、问题研究与解决的经典步骤, 独立解决问题; 其次, 通过拓广视野, 在遇到新的问题 (或子问题) 时, 能够主动发现和利用可用的现有资源 (如软件、文档、产品等) 快速加以解决, 避免自己重复“造轮子”.

一本教材的完成绝非易事. 本书的写作开始于 2013 年秋季, 那时我刚回到母校南京大学任教, 并计划开设一门新课程——模式识别. 本书用英文写作, 迄今已逾 5 年. 这本教材能完成, 笔者必须感谢相当多人士的帮助, 试按大致的时间先后顺序致谢如下:

• 南京大学计算机系、人工智能学院、LAMDA研究所的领导、同事与同学们. 校系两级领导在科研环境甚至生活环境等各方面提供了一个宽松的氛围, 他们还允许我结合自己的研究兴趣开设一门新课程. 此前在新加坡任教时必须教一门自己完全不感兴趣的课程, 这一经历让我深恶痛绝, 所以我在 “模式识别” 课程上倾注了极大的热情. 机器学习与数据挖掘 (LAMDA) 研究所提供了一个极优秀的科研环境, 与所长周志华教授、其他同事以及研究生同学间的讨论、合作也让我很快安定下来, 有足够的时间可以从事科研与教学 (包括写这本书). 事实上, LAMDA 研究所聘请的科研助理也功不可没——否则, 我大概要把所有写作本书的时间都花在报销手续上了.
• 选修 “模式识别” 课程的同学们. 在本书初的几章草稿发布后, 他们的热情反馈是支撑我继续写下去的动力, 而在教学过程中的不断交流显然有助于随时调整本书的方向、内容与细节. 这几年课上的同学还为本书指出了大量的错误和笔误. 笔者将在本书配套的主页详细致谢每位曾为本书各稿纠错的读者. 由于篇幅所限, 详细名单此处暂从略.
• 我所指导的研究生们. 正是由于我们共同的努力, 研究组的科研工作能够正常开展, 从而使得我有额外的时间来写这本教材; 同时他们也常常是本书的批读者和纠错者. 谢谢他们！
• 剑桥大学出版社与机械工业出版社的编辑们. 在本书初稿接近完成之时, 剑桥大学出版社的刘泳辰 (David Liu) 先生适时出现, 与笔者商讨由剑桥大学出版社出版本书的事宜, 刘先生的时时来信不断提醒我在本书投入时间, 使其完稿时间大为提前. 而在初稿完成之后不到一个星期, 机械工业出版社华章分社的姚蕾女士从天而降, 很快说服我由机械工业出版社出版中文版, 并商定了远远快于我原本规划的翻译与出版时间表. 事实证明, 她的计划比我更合理、高效, 从而使得本书可以尽早与读者诸君见面——目前英文版合同已经签署, 但书稿的编辑工作尚未后完成, 而中文版就要面市了. 由于与一般的外文文献翻译成中文的过程颇为不同, 本书的中文版与英文版会包含一些轻微的差异.
• 本书的两位译者. 我指导的两位研究生——罗建豪 (博士研究生, 前 8 章的译者) 与张皓(硕士研究生, 后 7 章的译者) 在仔细考虑后同意翻译本书. 感谢他们在繁忙的学业与研究工作之余提供高质量的译文！译文由笔者逐字校对、审核和修改.
• 创作TEX系列软件的志愿者们. 在初开始写作时, 笔者没有发现能够在 Ubuntu 下运行的中文LATEX环境, 正是基于这个近乎可笑的原因, 本书是用英文写作的. 在数年后翻译工作开始时, 两位译者告诉我中文LATEX写作在 Windows 环境中已相当方便 (使用XETEX和 xeCJK 宏包), 我仔细研究之后发现其在 Ubuntu 环境下也变得颇为方便. 感谢无私开发并维护TEX、LATEX 、XETEX 和CTEX(中文LATEX) 的志愿者们. 书中的图和表 格均由笔者自行绘制.
• 家人们. 在小儿彬彬出生之前, 这本书的大部分写作是我上班前或下班后在家完成的; 而在彬彬出生尤其是会走路之后, 就只能在办公室或者飞机、火车上抽出时间来进行写作了. 感谢家人对我的一贯支持, 尤其是在彬彬出生之后, 感谢父母、岳父母与太太在育儿方面历经辛苦, 万分感谢！

在努力提高可读性之余, 笔者也已尽力使本书严谨、准确, 但受精力和水平所限, 书中的错误在所难免. 欢迎读者 (例如使用本教材的老师与同学, 以及相关领域的研究和开发人员) 不吝指出书中技术上、文字上或是翻译中的任何错误 (请发送电子邮件至 pr.book.wujx@gmail.com). 笔者将在本书配套主页一并致谢.

本书是模式识别领域的入门教材，系统阐述了模式识别中的基础知识、主要模型及热门应用，并给出了近年来本领域一些新的成果和观点；通过理论学习和动手实践相结合的形式使初学者能有效入门，并培养独立解决任务的能力，为模式识别的项目开发及相关科研活动打好基础.

全书共15章，大致分为五部分：*部分（第1~4章）介绍了本书的概论和基础知识，包括绪论、数学背景知识、模式识别系统概述以及评估；第二部分（第5~6章）介绍了与领域知识无关的特征提取，包括主成分分析和Fisher线性判别；第三部分（第7~10章）介绍了分类器与其他工具，包括支持向量机、概率方法、距离度量与数据变换、信息论和决策树；第四部分（第11~12章）介绍了如何处理变化多端的数据，包括稀疏数据和未对齐数据、隐马尔可夫模型；第五部分（第13~15章）介绍了一些高阶课题，包括正态分布、EM算法和卷积神经网络.

本书可作为高等院校人工智能、计算机、自动化、电子和通信等相关专业研究生或本科生的教材，也可供人工智能、计算机、自动化、电子和通信等领域研究人员和工程技术人员参考.

吴建鑫

南京大学计算机科学与技术系教授、博士生导师，入选中组部青年海外高层次人才引进计划（青年千人计划），2014年获得国家自然科学基金委优秀青年科学基金项目支持. 同时，担任Minieye首席科学家（minieye.cc）. 主要从事计算机视觉和机器学习等领域的研究. 在重要国际期刊如TPAMI、IJCV、AIJ、JMLR等以及重要国际会议如ICCV、CVPR、ICML等发表论文六十余篇. 曾担任国际会议ICCV、AAAI、CVPR等领域主席。发表论文被60余个国家和地区的学者引用7000余次.

前言 
符号表 
部分概述.........................................................................1
第1章绪论.............................................................................2
1.1样例:自动驾驶..................................................................3
1.2模式识别与机器学习.............................................................5
1.2.1一个典型的模式识别流程.....................................................5
1.2.2模式识别vs.机器学习.......................................................8
1.2.3评估、部署和细化...........................................................9
1.3本书的结构......................................................................9
习题.................................................................................12
第2章数学背景知识..................................................................14
2.1线性代数.......................................................................14
2.1.1内积、范数、距离和正交性..................................................14
2.1.2角度与不等式..............................................................15
2.1.3向量投影..................................................................16
2.1.4矩阵基础..................................................................17
2.1.5矩阵乘法..................................................................18
2.1.6方阵的行列式与逆..........................................................19
2.1.7方阵的特征值、特征向量、秩和迹............................................20
2.1.8奇异值分解................................................................22
2.1.9(半)正定实对称矩阵.......................................................22
2.2概率............................................................................23
2.2.1基础......................................................................23
2.2.2联合分布、条件分布与贝叶斯定理............................................25
2.2.3期望与方差/协方差矩阵.....................................................26
2.2.4不等式....................................................................27
2.2.5独立性与相关性............................................................28
2.2.6正态分布..................................................................29
2.3优化与矩阵微积分..............................................................30
2.3.1局部极小、必要条件和矩阵微积分............................................30
2.3.2凸优化与凹优化............................................................31
2.3.3约束优化和拉格朗日乘子法.................................................33
2.4算法复杂度.....................................................................34
2.5阅读材料.......................................................................35
习题.................................................................................35
第3章模式识别系统概述.............................................................39
3.1人脸识别.......................................................................39
3.2一个简单的近邻分类器.......................................................40
3.2.1训练或学习................................................................40
3.2.2测试或预测................................................................40
3.2.3近邻分类器..............................................................41
3.2.4k-近邻....................................................................42
3.3丑陋的细节.....................................................................43
3.4制定假设并化简................................................................46
3.4.1设计工作环境vs.设计复杂算法.............................................46
3.4.2假设与简化................................................................47
3.5一种框架.......................................................................51
3.6阅读材料.......................................................................51
习题.................................................................................53
第4章评估............................................................................55
4.1简单情形中的准确率和错误率..................................................55
4.1.1训练与测试误差............................................................56
4.1.2过拟合与欠拟合............................................................56
4.1.3使用验证集来选择超参数...................................................58
4.1.4交叉验证..................................................................59
4.2小化代价/损失...............................................................61
4.2.1正则化....................................................................62
4.2.2代价矩阵..................................................................62
4.2.3贝叶斯决策理论............................................................63
4.3不平衡问题中的评估............................................................64
4.3.1单个类别内的比率..........................................................64
4.3.2ROC曲线下的面积.........................................................65
4.3.3查准率、查全率和F值.....................................................66
4.4我们能达到100％的准确率吗?..................................................68
4.4.1贝叶斯错误率........................................................