模式识别

模式识别(英语:Pattern recognition),就是通过计算机用数学技术方法来研究模式的自动处理和判读。 我们把环境与客体统称为“模式”。 随着计算机技术的发展,人类有可能研究复杂的信息处理过程。 信息处理过程的一个重要形式是生命体对环境及客体的识别。其概念与数据挖掘、机器学习类似。

来源:维基百科
简介

模式识别领域涉及通过使用计算机算法自动发现数据的规律性以及使用这些规则来采取诸如将数据分类成不同类别的行为。

考虑识别手写数字的例子,如下图所示:

image.png

每个数字对应于28×28像素图像,因此可以由包括784个实数的矢量x表示。我们目标是构建一个机器,它将这样的向量x作为输入,并将产生数字0,...,9的标识作为输出。由于手写的广泛可变性,这是一个非常重要的问题。它可以使用手工制作的规则或启发法来解决,以根据笔画的形状区分数字,但实际上这种方法会导致规则的扩散和规则的例外等等,并且总是会产生不良结果。

通过采用机器学习方法可以获得更好的结果,其中使用称为训练集的大量N个数字{x1,...,xN}来调整自适应模型的参数。训练集中的数字类别是我们预先知道的,通常通过单独检查它们并手动标记它们来获取标签。我们可以使用目标向量t来表示数字的类别,目标向量t表示相应数字的标识。

运行机器学习算法的结果可以表示为函数y(x),其将新的数字图像x作为输入并且生成输出矢量y,以与目标矢量相同的方式编码。基于训练数据,函数y(x)的精确形式在训练阶段期间确定,也称为学习阶段。一旦模型被训练,它就可以确定新数字图像的身份。正确分类与用于训练的示例不同的新示例的能力称为鲁棒性(robustness)。在实际应用中,输入矢量的可变性将使得训练数据可以仅包括所有可能输入矢量的一小部分,因此鲁棒性是模式识别的中心目标。

对于大多数实际应用,原始输入变量通常是经过预处理的,以将它们转换为一些新的变量空间,以此使得模式识别问题更容易解决。例如,在数字识别问题中,我们通常缩放数字的图像,使得每个数字包含在固定大小的框内。这极大地减少了每个数字类内的可变性,因为所有数字的位置和比例现在都相同,这使得后续模式识别算法更容易区分不同的类。该预处理阶段有时也称为特征提取。

其中训练数据包括输入矢量的示例以及它们对应的目标矢量的应用被称为监督学习问题。诸如数字识别示例之类的情况被称为分类问题,其中目标是将每个输入向量分配给有限数量的离散类别之一。如果所需输出包含一个或多个连续变量,则该任务称为回归。回归问题的一个例子是在化学制造过程中预测产量,其中输入由反应物浓度,温度和压力组成。

在其他模式识别问题中,训练数据由一组输入矢量x组成,没有任何相应的目标值。这种无监督学习问题的目标可能是发现数据中的相似示例组,称为聚类,或确定输入空间内的数据分布,称为密度估计,或从高处投射数据 - 用于可视化目的的二维或三维空间。

最后,强化学习(reinforcement learning)关注的是在特定情况下寻找合适行动以获得最大回报的问题。这里学习算法没有给出最佳输出的例子,算法必须通过反复试验的过程来发现它们。通常,任务中存在一系列状态和动作,其中学习算法与其环境需要交互。

[图片及描述来源:Bishop C. M. (2006). Pattern Recognition and Machine Learning. Springer.]

发展历史

在数据中搜索模式的问题是一个基本问题,并且具有漫长而成功的历史。例如,16世纪对第谷·布拉赫的广泛天文观测让约翰内斯·开普勒发现了行星运动的经验定律,这反过来又为经典力学的发展提供了跳板。同样,原子光谱中规律性的发现在二十世纪早期量子物理学的发展和验证中发挥了关键作用。

分类算法:

1936年,英国统计学家费舍尔(Ronald Fisher)提出线性判别分析(LDA),其目的是通过线性变换对二元分类问题进行求解。逻辑回归则始于19世纪对人口增长的描述及自催化反应的研究,比利时统计学家Verhulst在协助其导师研究指数增长期间发现并命名了逻辑方程(logistic function),并于1838至1847年间发表了三篇相关论文。1922年,美国生物学家Raymond Pearl基于Verhulst的方程发表了一系列相关论文,用于解释人口增长模型,并提出了另一种logistic function的表达方法。

决策树是一类树模型的统称,这是常用于分类的一大类模型,其最早可以追溯到1948年左右,当时克劳德·香农介绍了信息论,这是决策树学习的理论基础之一。随后,1963年,Morgan 和 Sonquist 开发出第一个回归树,他们提出了一种分析调查数据的方法,它不对交互影响施加任何限制,侧重于减少预测误差,顺序操作,并且不依赖于分类中的线性程度或解释变量的排列顺序,当时他们起名为交互检测(AID)模型。此后各类决策树模型层出不穷,具体请见相应词条,在此不多赘述。

K近邻法(KNN)是一种简单却强大的无监督分类算法,1951年,Fix 和 Hodges 设想了最近邻规则,这也是KNN的最早设想之一。1967年,Cover 和 Hart 在论文《Nearest neighbor pattern classification》中正式介绍了 KNN,也是KNN的首次正式的提出。

另一种不得不知的分类——其后也有支持回归的版本——的算法是支持向量机(SVM)。最初的SVM算法是由Vladimir N. Vapnik和Alexey YaChervonenkis在1963年发明的。1992年,Bernhard E. Boser, Isabelle M. Guyon和Vladimir N. Vapnik提出了一种方法,通过将内核技巧应用到最大限度的超平面上,来创建非线性分类器。1993年,Corinna Cortes和Vapnik提出了目前的标准化身(soft margin),并于1995年出版。

聚类算法中最著名的则是K-means 算法,最初在1955年由Steinhaus提出,随后在不同领域得到了广泛应用并产生了诸多变体。其他的有Kernel PCA等。

作为使用多种兼容的学习算法/模型来执行单个任务的技术,集成学习中的主要方法可归类为三大类: 堆叠(Stacking)、提升(Boosting) 和 装袋(Bootstrap aggregating)。1979年,Dasarathy 提出集成系统(ensemble system)的思想,并使用线性分类器和最近邻居(NN)分类器组成的复合系统作为其组成部分的例子来说明这些概念。同年,Bootstrap由 Bradley Efron发表在他的论文"Bootstrap methods: another look at the jackknife"中。因其通用性和简便性,bootstrapping在各种机器学习算法中具有很强的实用性。堆叠泛化由Wolpert在1992年首次提出,堆叠通常能获得比任何单个的训练模型更好的性能。1996年,Breiman 开发出 Bagging 预测器,并对其原理和训练进行了详细描述。他提出回归和分类的一个关键问题是预测方法的不稳定性——如果扰乱训练集,那么可能会导致构建的预测变量发生重大变化,而Bagging 可以提高准确性。

集成学习内各类算法的演变请参阅相应词条。

另一类非常重要的模型是基于马尔科夫链(Markov Chain)的模型,1906年,Andrey Andreyevich Markov为了描述随机过程首次提出了马尔科夫链,并应用在俄语字符序列的计算中。在随后的半个世纪中,该概念深刻影响了数学,统计,计算机,物理学,生物学,语言学等各个领域,并引申发展出了马尔可夫毯,马尔可夫模型,马尔可夫随机场等多种重要概念。在此基础上还有常常被认为是隐马尔可夫模型(HMM)的替代的CRF模型,由John Lafferty等人提出,作为判别模型,可以解决HMM在某些问题上由于是生成模型不方便计算的问题。

与此类似的还有基于贝叶斯理论的一类算法,如贝叶斯网络(Bayesian network)。该方法基于贝叶斯条件,由Pearl在1985年针对主观的输入信息依靠贝叶斯条件作为更新信息的基础而提出来的,并在其后几年快速发展,成为了一个单独的研究领域。

此外,随着深度学习的流行,神经网络等模型又重新回到人们的视野,这一起源于 20 世纪 50 年代的监督式机器学习模型,目前也有了众多分支,近几年的最新研究也大多与此有关。

主要事件

年份事件相关论文/Reference
1838 - 1847比利时统计学家Verhulst为logistic function命名Verhulst, Pierre-Francois (1838) Notice sur la loi que la population suit dans son accroissement. Correspondance mathématique et Physique, publiée par A. Quetelet, 10, 113-120
1906Andrey Andreyevich Markov 引入了马尔可夫链的概念Markov, A. A. (1906). Rasprostranenie zakona bol’shih chisel na velichiny, zavisyaschie drug ot druga. Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 15(135-156), 18.
1922Pearl在研究美国人口增长时提出logistic function另一种表达方法On the Rate of Growth of the Population of the United States Since 1790 and its Mathematical RepresentationRaymond Pearl, and Lowell J. ReedPNAS 1920;6;275-288 doi:10.1073/pnas.6.6.275
1936Ronald Fisher发表最早期的线性判别分析论文Fisher, R.A., 1936. The use of multiple measurements in taxonomic problems. *Annals of human genetics*, *7*(2), pp.179-188.
1943WarrenMcCulloch 和 Walter Pitts 首次建立了神经网络模型McCulloch, W. S.; Pitts, W. (1943). A logical calculus of the ideas immanent in nervous activity. The bulletin of mathematical biophysics. 5(4): 115–133.
1951Fix 和 Hodges 设想了最近邻规则Fix, E., & Hodges Jr, J. L. (1951). Discriminatory analysis-nonparametric discrimination: consistency properties. California Univ Berkeley.
1955K-means 算法的雏形由Steinhaus被提出Steinhaus, H. (1956). Sur la division des corps matériels en parties. Bull.acad.polon.sci.cl.iii, 801-804.
1963Morgan 和 Sonquist 开发出第一个回归树Morgan. J. N. & Sonquist, J. A. (1963) Problems in the Analysis of Survey Data, and a Proposal, Journal of the American Statistical Association, 58:302, 415-434.
1967Cover 和 Hart 在论文《Nearest neighbor  pattern classification》中正式介绍了 KNNCover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE transactions on information theory, 13(1), 21-27.
1979Dasarathy 提出集成系统(ensemble system)的思想Dasarathy, B. V. and Sheela, B. V. (1979). A composite classifier system design: Concepts and methodology. Proceedings of the IEEE. 67(5): 708-713.
1980《Markov random fields and their applications》出版,详细描述了马尔可夫随机场的理论和应用Kindermann, R., & Snell, J. L. (1980). Markov random fields and their applications (Vol. 1). American Mathematical Society.
1985Pearl提出贝叶斯网络的概念Pearl J. (1985). Bayesian Networks: A Model of Self-Activated Memory for Evidential Reasoning. Proceedings of the 7th Conference of the Cognitive Science Society, University of California, Irvine, CA. pp. 329–334.
1992David Wolpert 研究出了堆叠泛化(Stacking /Stacked  Generalization)Wolpert, D. H. (1992). Stacked generalization. Neural networks, 5(2), 241-259.
1995提出标准的SVM with Soft marginCortes, C., & Vapnik, V. (1995). Support-vector networks. Machine learning, 20(3), 273-297.
1996Breiman 开发出 Bagging 预测器Breiman, L. (1996). Bagging predictors. Machine Learning. 24(2): 123–140.
2001John Lafferty等人提出CRFLafferty, J. D., McCallum, A., and Pereira, F. C. N. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In ICML 2001, Stanford, CA.

发展分析

瓶颈

模式识别中不同的算法有其自身的优点和局限性,但总体来说,我们目前主要的瓶颈是模式识别算法虽然能在一些任务上取得优秀的表现,但我们离真正的通用人工智能还有很远的距离。

未来发展方向

自动机器学习算法,如AutoML可以省去调参的问题;多智能体系统等研究方向也是我们通往通用人工智能的一个突破口。

Contributor: Yuanyuan Li

相关人物
简介
相关人物