PDF《模式识别》

最近邻 & 模式识别系统框架及其各模块的简介 吴建鑫 南京大学计算机系,2019 模式识别

1 目标 ? 理解并能熟练运用最近邻方法进行分类 ? 了解最近邻方法的限制、缺陷以及可能的解决办法 ? 理解并掌握模式识别系统各模块的作用、基本概念 和解决方案的分类 ? 提高目标 ? 进一步能将最近邻方法应用到实际研究问题中去(研 究生、部分本科生) ? DHS第7―10章、PRML第8―12章(偏Bayesian角度) 将不详细讲授,感兴趣的同学可以自学

2 最近邻规则 Nearest neighbor rule

3 问题设置problem setup

4 ? 分类问题classification ? 训练集 ? 训练样本(sample): ∈ ? ? ? 样本的标记(label): ∈ = 1,2, … , ? 样本一共被分为 个类别(category) ? 例如,在我们的例子里, = 2, = 1(男)或者 =

2 (女) ? 存在一个距离(distance)函数: , ∈ ? ? 能够度量x和y之间的距离,或者不相似程度(level of dissimilarity) 最近邻规则和Voronoi图5给定一个测试样例 1.

发现其最近邻 ? = argmin ( , ) 2. 输出对 的分类的预测: ? Voronoi图(Voronoi Diagram) 最近邻可能出现的问题

6 ? 如果出现平局(tie)? ? ? ? 如果出现离群点(outlier)? ? K-近邻(kNN,k-nearest neighbor)规则 ? 可能遇到的问题? ? 能做的多好? ? 当训练样本趋于无穷时( → ∞),最近邻的错误率最 多是最佳错误率的两倍 ? 有限样本(finite sample)时的结论尚不清楚 计算、存储代价(cost)

7 ? 假设 , 是欧式距离(Euclidean distance, ? distance) ? 其复杂度(complexity)是()?NN的复杂度 ( ) ? DHS 152页的复杂度是错的 ? K-NN的复杂度同样是 ( ) ? 或者是 但通常 较小,可以忽略 ? 从 个数(距离)中选择 个最小的,复杂度是? ? 考虑一下,如果是ILSVRC,需要多长时间,多大的存 储空间?这是NN的主要问题 ? = 1,200,000 ? = 262,144 降低NN的计算、存储代价

8 ? 近似最近邻(approximate nearest neighbor,ANN) ? 不要求一定是距离最短的 个?如第 个NN,其距离是 ,则ANN要求其选取的所有 个样例的距离 满足 ≤

1 + 即可 ? 可以将kNN搜索(search、查找)速度提高几个数量级 ? 二值哈希(binary hashing) ? hash函数 :将? 分为两部分,分别用 = 0,1表示 ? 设计 个hash函数 , … , ,每个 表示为 个bit ? ? ,计算和存储大幅简化,需要设计好的hash ? 进一步:基于深度学习的哈希 系统各模块(混合)简介 Introducing various components in a mixed order

9 细化(refined)的框架

10 ? 机器学习 : ? 1. 与领域无关的特征变换和特征抽 取?Normalization, PCA, FLD,… 2. 针对不同数据特点的不同学习算 法?SVM, Decision Tree, imbalanced learning, HMM, DTW, graphical model, deep learning, pLSA, … 3. 机器学习方法常见分类、策略 ? 针对不同问题的评价准则 (evaluation criterion) 评价准则―泛化和测试误差

11 ? 暂时只考虑分类问题的评价 ? 假设( , )~ , ? 泛化误差generalization error: ? 通常无法实际计算 ? 根本假设:训练集 和测试集 都是服从真实数据 分布 ( )的,或者,他们的样例是从 ( )中取样(sample) 的?测试误差(testing error) =

1 ? 精确度(accuracy): =

1 ? 一种常见的学习框架

12 ? 代价最小化cost minimization ? 错误是最常考虑的代价,所以现在我们可以说学习的 目标是在训练集上获得最小的代价 ? min ? 难以优化 C 怎样求解? ? 一种方法是:把不连续的指示函数(indicator function)换成性质相似,但好优化的函数 ? 如, ? ? 学习这种思路:形式化、简化、优化 ? Formalization, simplification, optimization 过拟合和欠拟合