基于广义置信度的样本选择算法

摘要：对模式识别系统而言，不同的训练样本在建立模式类模型时所起的作用不同，因此必须对训练样本进行选择。而在训练样本中，边界样本的判定方式以及训练样本中包含边界样本数量的多少对分类的精度起主要作用。为此，结合基于模板匹配的脱机手写汉字识别，定义了一种通过广义置信度判定边界样本的方法，并且在此基础上建立了基于广义置信度的训练样本选择算法。通过在脱机手写汉字数据库HCL2004上进行实验，由该算法选择出的训练样本集在训练样本数减少的同时，使得系统识别率有了较大的提高，从而证实了该算法的有效性。

关键词：人工智能；模式识别；广义置信度；样本选择；手写汉字识别；HCL2004

中图分类号：TP391　文献标识码：A

1 引言

对于有监督的模式识别系统而言，模式识别的过程就是通过各模式类中一定数量的样本训练得到它们的基本模型，然后对未知样本进行分类决策的过程，因此，训练结果的好坏将直接影响到整个识别系统的性能[1]，而要得到一个好的训练结果，除了要选择合适的模型外，训练样本的好坏也是至关重要的，由于不同训练样本在训练过程中所起的作用不同，这就需要对训练样本进行选择。

近年来，许多学者在样本选择方面进行了大量的研究工作。文献[2～4]指出，对训练样本进行精心选择可以在缩短训练时问的同时增加分类器的推广能力。研究还表明，在训练样本中，位于分类边界面附近的样本(即边界样本)和位于模式类中心部分的非边界样本对分类所起的作用不同，其中，边界样本对分类的精度起主要作用[5～6]，也即在选择训练样本时，只有包含了足够多的边界样本，才能训练出好的分类曲面。对应于不同的分类器，有各种不同的边界样本的定义方法，在文献[7]中的基于神经网络分类器的识别系统中，边界样本定义为使输出变化较大的输入样本，从而将位于输出对输入的一阶偏导峰值某邻域内的点作为边界样本。文献[8]中则给出了通过聚类的边缘定义边界样本的方法。

本文以基于模板匹配的手写汉字识别系统为基础，定义了一种通过广义置信度判定边界样本的方法，并在此基础上建立了手写汉字样本选择算法。文章介绍了置信度和广义置信度的概念，并给出了广义置信度的估计方法，选取其中的最优估计形式，建立了基于广义置信度边界样本的定义和样本选择方法，最后给出了该算法在HCL2004手写汉字数据库上的实验结果。

2　分类器的置信度分析

对于任何一个模式分类器，除了希望它有尽可能高的识别率外，还希望能比较准确地估计其分类结果的准确性，也即识别结果的置信度。置信度越高，则识别结果的可信程度越高。对于字符识别来说，为了估计其识别结果的准确性，给出了广义置信度的概念[9]。

2.1 分类器的置信度和广义置信度

设分类器S，x为待识别样本的特征向量，S对x的判决为es(x)，x的真实类别为ω(x)，则定义S在特征向量空间内点x处的置信度cs(x)为es(x)判定正确的概率，即：

cs(x)=P(es(x)=ω(x))

(1)

由置信度的概念可见，置信度为值域在[0，1]上的关于分类器S在不同特征点的可靠性度量，为一种广义的绝对的概率度量。但在实际系统中，我们直接得到的观察量往往只能反映识别结果的相对可靠性，而无法给出绝对的概率度量，为此，我们引入了广义置信度的概念。具体为：

若存在函数fs(x)和一个单调递增函数g(・)，使得：

fs(x)=g(cs(x))

(2)则称fs(x)为S的广义置信度。可见，广义置信度是一种相对度量，即：只要fs(x1)＞fs(x2)，就认为分类器S在特征点x1上比在x2上更可靠一些，而无须给出绝对的概率度量。

显然，置信度cs(x)是广义置信度的一个特例。对一个分类器而言，其置信度是唯一的，广义置信度则不是唯一的。因为只要将任何一个单调递增函数作用在置信度上就可以得到一个广义置信度。

2．2分类器的置信度估计

为了在实际中应用置信度进行分析，首先要找到置信度的估计方法。对基于距离的分类器，常用的广义置信度估计的公式有：

c1(x)=-d1(x)

(3)

c2(x)=d2(x)-d1(x)

(4)

c3(x)=1-d1(x)/d2(x)

(5)

其中：d1(x)是未知样本x与最近的代表样本xm间的距离，d2(x)是x与代表样本中与xm属于不同类别的样本的最近距离。

在文献[10，11]中证明了：对于最近邻分类器，在训练样本充分多、特征维数为1、类别数为2的情况下，式(5)的数学期望是一种广义置信度，而式(3)和(4)的数学期望都不是广义置信度。文献[12]中在用最近邻分类器进行手写数字识别的实验中，用参数优化的方法求广义置信度的表达式时，得到的也是(5)式。综合以上的理论分析和应用，有理由认为：对基于距离的分类器，用式(5)作为广义置信度估计是一种有理的选择。因此在本文中，我们一律用(5)式给出的表达式作为分类器的置信度估计。

3 基于广义置信度的边界样本定义

广义置信度给出了对样本识别结果正确性的评价指标。置信度较小，相当于样本被识别为当前类别的后验概率比较小，反之，则认为样本被识别为当前类别的后验概率比较大。样本被识别为当前类别的后验概率小，也就意味着该样本容易被误认为其他类，或者说容易与其他类的样本混淆，因此认为该样本为位于分类面附近的样本，也即边界样本。基于这一思想，给出了如下的基于广义置信度的边界样本的定义。

定义：对于分类器s，用训练样本集X训练得到该分类器所需的识别要素，然后再对该样本集作识别，分别得到正确识别样本集Xc和误识样本集Xe，可见，Xc+Xe=X，分别对Xc和Xe中的样本的置 信度进行排序，则各数据集中置信度较小的样本为边界样本。

由上述定义可见，我们将训练样本中置信度比较小的样本定义为边界样本，这与广义的边界样本的定义是一致的，所谓边界样本，是指位于两类的分界面附近的点，而样本的置信度比较小，则认为它被判定为当前类别数的后验概率比较小，也即容易与其他类的样本发生混淆的样本，也就是位于分界面附近的样本。若置信度比较大，则当样本被正确识别时，说明它不容易与其他类混淆，则为好样本。对置信度较大的误识样本，则认为它被识别为其他类的概率比判定为其本身所属类别的概率要大，是坏样本。

在给出边界样本的定义时，之所以要将被正确识别和误识的样本分开来考虑，一方面是便于一同给出好样本和坏样本的定义，另一方面，通过我们对手写汉字训练样本置信度的统计，发现误识样本的置信度分布区间往往比被正确识别样本的置信度分布区间要小，因此，如果统一定义，则不利于对训练过程中不同样本所起的作用进行分析。

4　基于广义置信度的样本选择算法

基于上节给出的边界样本的定义，我们给出如下的基于广义置信度的样本选择算法。

设初始训练样本集为X0={X0m，m=1,…，M}，其中，M为类别数，X0m={Xi，i=1，2，…，N0m}为各类的训练样本集，N0m为第m类的初始训练样本数，则基于广义置信度的样本选择算法描述为：

(1)取训练样本集X0。中的全部样本进行训练，得到各模式类的初始模型T0m(m=1，…，M)；

(2)用初始模型T0m(m＝1，2，…，M)对所有样本X0进行识别，得到所有样本的平均识别率r0和各样本的识别结果置信度，以及各类中样本的识别情况，即哪些样本的识别结果正确，哪些样本发生了误识，将第m类中识别正确的样本组成数据集X0cm={Xj，j=1，2，…，N0cm}，被误识的样本组成数据集X0em={Xk，k=1，2，…，N0em}，其中N0cm和N0em分别为该类中正确识别和错误识别的样本数；

(3)分别将各类的识别正确的样本数据集X0cm(m=1，2，…，M)和误识样本数据集X0em(m=1，2，…，M)中的样本按置信度由大到小的顺序进行排序；

(4)初始化参数：n1，Unit，其中n为迭代参数，Unit为在每次迭代时减少的样本个数，为一个事先设定的参数；

(5)剔除各类中置信度较大的n・Unit个样本(具体方法见下)，其余的样本构成新的训练样本集Xn={Xnm=1，…，M}，Xnm={xi，i=1，2，…，Nnm}；

(6)由Xn训练得到各类的新模型Tnm(m=1，2，…，M)：

(7)通过Tnm(m=1，2，…，M)对样本集X0进行识别，得到所有样本的平均识别率rn

(8)若rn＞rn-1，则nn+1，转到(5)；

否则，迭代终止。

则训练样本集Xn-1={Xn-1m，m=1，…，M}，Xn-1m={xi，i＝1，2，…，Nn-1m}为选择出的训练样本集，其中各类的样本数为Nn-1m，模型为Tn-1m(m=1，2，…，M)。

在上述算法第(5)步中，每次迭代时需要剔除各类中置信度较大的n・Unit个样本，也即选择置信度较小的(N0m-n・Unit)个样本。为了比较各种不同样本在训练过程中的作用，本文给出了三种不同的方法。

Meth.a正确识别样本和错误识别样本成比例减小。

对第n次迭代，要求各类的样本数Nnm=N0m-n・Unit，则我们从各类的正确识别样本数据集中选取Nncm个样本，并从各类的误识样本数据集中选取Nnem个样本，其中

Meth.b 选取全部误识样本，减少正确识别样本。

对第n次迭代，要求各类的样本数Nnm=N0m-n・Unit，则我们保持误识数据集中的样本数不变，只是从各类的正确识别样本数据集选取Nncm个样本，即

Nncm=N0cm-n・Unit，Nnem=N0em

(8)

Meth．c 只选取全部正确识别的样本进行训练。

该方法只选择被正确识别的样本作为训练样本，即对第n次迭代，有

Nnm＝Nncm=N0cm-n・Unit

(9)

5 实验

为了证实本文给出的算法的有效性，我们在HCL2004脱机手写汉字数据库中的3755个字类 上进行实验。训练样本为各字类第600～899的300个样本，测试样本为各汉字900～999的100个样本。实验系统为先粗分类后细分类的两级识别系统，其中粗分类为基于绝对值距离的模板匹配，细分类则采用基于二阶标准差的距离测度进行模板匹配，粗分类时的特征向量为由5×5的模板分割生成的100维方向线素特征组成，细分类特征向量则为由7×7+8×8的重叠网格分割得到的452维方向线素特征。另外，在本文给出的系统中，取Unit＝20，即训练样本以20为单位逐步递减。

图1给出了通过本文给出的样本选择方法对训练样本进行选择，并由挑选出的样本生成各字类的标准模板，然后对训练样本和测试样本进行识别得到的实验结果。其中，图1(a)、图1(b)和图1(c)分别对应于上节给出的Meth.a、Meth.b和Meth.c三种不同的样本选择方法。在各图中，横坐标为各类的训练样本数，纵坐标为识别率(以百分比为单位)，“train”为对训练样本进行识别的结果，“test”为在测试样本集上的识别结果。

由图1(a)可见，采用成比例减少正确识别样本集和误识样本集中置信度较大的样本的方法对样本进行选择，随着训练样本数的减少，训练样本的识别率逐渐增大，当各类的样本数减小到220时，识别率达到最大，为97.52％，比采用全部样本进行训练时的识别率要高0.54个百分点，而当样本数继续减少时，识别率则开始下降，由此可见，基于方法(a)进行样本选择，当训练样本数为220时的样本集为最佳训练样本集，此时得到的标准模板为最佳模板。通过在测试样本上进行实验，其识别率变化曲线“test”曲线与训练样本集上的识别率变化曲线有相同的趋势，而且也为当样本数为220时，识别率达到最大，从而证实了用成比例减少正确识别样本集和误识样本集中置信度较大的样本的方法对样本进行选择的正确性。

同样地，由图1(b)中给出的曲线，可以证实通过保留全部的误识样本，剔除正确识别样本集中置信度较大的样本得到最佳训练样本集的方法的正确性，而且由图可知，样本数为220时生成的模板为最佳模板。

图1(c)给出了通过由正确识别样本集中的边界样本生成的标准模板对整个训练样本集作识别的识别结果，由图可见，训练样本数的减少，系统的识别率一直在下降，这说明通过该方法对样本进行选择是不正确的，也起不到提高分类器识别率的作用。究其原因，主要在于在训练样本中只包含了被正确识别的样本，而没有包含误识样本的信息。因此尽管所选出的样本为被正确识别的样本中的边界样本，但系统的识别率却始终在降低，从而说明在训练分类器的过程中，误识样本是必不可少的。

综上所述，可以得到如下的结论：

(1)在基于广义置信度的边界样本定义的前提下，通过正确识别样本和误识样本成比例减少的样本选择方法，以及选取全部误识样本，只减少正确样本的样本选择方法是有效的；而只选取正确识别样本的样本选择方法是不可行的。

(2)在训练样本中，误识样本是必须的。

6 结论

在训练样本中，位于分类边界面附近的边界样本和位于模式类中心部分的非边界样本对分类所起的作用不同，其中，边界样本对分类的精度起主要作用，因此，在对训练样本进行选择时，只有包含了足够多的边界样本，才能训练出好的分类曲面。本文在距离分类器的基础上，给出了基于广义置信度的边界样本的定义，并在此基础上，给出了基于广义置信度的样本选择算法，为了分析不同的样本在训练分类器时所起的作用，文中给出了三种不同的样本挑选的方法。通过在手写汉字数据库HCL2004上进行测试，分析了该样本选择算法的可行性，进而也说明了本文给出的基于广义置信度的边界样本的定义是合理的。

需要说明的是，本文给出的基于广义置信度的样本选择算法有很好的推广性，对所有基于最近邻的分类都是适用的。对于其他类型的分类器，只要能得到关于其识别结果的置信度估计，则可以通过本文所给出的算法进行训练样本的选择。

收稿日期：2005－08－30　定稿日期：2007－01－25

基金项目：国家自然科学基金资助项目(60475007)

作者简介：任俊玲(1979－)，女，博士，讲师，主要研究领域为图像处理与中文信息处理。

参考文献：

[1]Foody,G.M.,Issue in training set selection and re-finement for classification by a feedforward neural net-work[A].In:IEEE International Geoscience and Re-mote Sensing sysmposium proceedings[C].1998.1:409-411.July.

[2]M.Wann,T.Hediger,and N.N.Greenbaun,The influence of training sets on generalization in feesfor-ward neural networks[A].In:Proc.International Joint Conf.On Neural Networks[C].1990.3:137- 142.

[3]D Cohn,L Altlas,R Ladner,Improving generalization with active learning[J].Machine Learning,1994,15:201-221.

[4]A Robel,Dynamic pattern selection for faster learning and controlled generalization of neural networks [A].ESANN[C].1994.

[5]Chaudhuri D.,Murthy C.A.,Chaudhuri B.B.,Find-ing a subset of representative points in a dataset[J].IEEE Trans.Syst.Man Cyber.,24,1994,1416-1425.

[6]Dasarathy B.V.,Minimal consistent set identification for optimal nearest neighbor decision system design[J].IEEE Trans,Syst.Man Cyber.,6,1994,511-516.

[7]Engelbrecht,A.P.;Cloete,I.,Selective learning u-sing sensitivity analysis[A].In:Neural Networks Proceedings,1998.IEEE World Congress on Compu-tational Intelligence[C].1998.2:1150-1155.

[8]Tatiana Tambouratzis,Counter-clustering for training pattern selection[J].The Computer Journal,2000,43(3):177-190.

[9]林晓帆，丁晓青，吴佑寿，等．字符识别的置信度分析[J]．清华大学学报(自然科学版)，1998，38(9)：47－50．[10]林晓帆，丁晓青，吴佑寿．最近邻分类器置信度估计的理论分析[J]．科学通报，1998，43(3)：322-325．

[11]Gondail F,Lange E,Iwamoto T,et al.Face recogni-tion system using local autocorrelations and multiscale integration[J].IEEE Trans PAMI,1996,18(10): 1024-1028.

[12]Smith S J,Handwritten character classification using nearest neighbor in large database[J].IEEE Trans PAMI,1994,16(9):915-919.