基于组块3×2交叉验证t检验的模型选择算法

刘焱青， 王　钰， 李济洪*

(1.山西大学 数学科学学院， 山西 太原　030006； 2.山西大学 计算中心， 山西 太原　030006)



基于组块3×2交叉验证t检验的模型选择算法

刘焱青1， 王钰2， 李济洪2*

(1.山西大学 数学科学学院， 山西 太原030006； 2.山西大学 计算中心， 山西 太原030006)

摘要：传统的模型选择问题中,往往以所关心的性能指标的大小来评价模型.然而,许多情形下模型性能指标之间的差异在统计意义下是不显著的,是由随机误差导致的.为此,基于组块3×2交叉验证指标差异的显著性t检验给出了一种新的模型选择算法.模拟实验结果表明,在统计意义的最小化即平方损失(回归)和0-1(分类)损失最小化下,该方法常常被选择到较为简单的模型.

关键词：模型选择; 组块3×2交叉验证; t检验; 测试误差; 模型复杂度

0引言

统计机器学习的主要目的是依据训练数据建立预测模型, 用以描述给定数据的统计规律, 并通过此模型对新数据进行预测和问题求解. 其中, 模型的建立和选择是关键. 所谓模型选择指的是根据某种评价准则, 在所有候选模型中选出使得该评价准则最优的模型.典型地,训练误差的评价准则是很自然的选择, 然而,它是泛化误差的过分乐观估计,常常导致较差的预测误差.因此,在评价准则中必须权衡模型的复杂度与训练数据的拟合优度,如在进行神经网络中隐节点数目和多项式拟合中多项式次数的选择时，不能仅仅考虑训练数据中训练误差最小化,还需要考虑模型的复杂度(隐节点数目和多项式次数).现实中,许多这样的模型选择方法也已经被提出,如在传统回归分析中常用的AIC(Akaike Information Criterion),BIC(Bayesian Information Criterion),最小描述长度(MDL)以及结构风险最小化(SRM)的解析估计样本内预测误差的方法[1-4].

近年来, 研究者们提出多种直接估计样本外误差(预测误差)的方法，如文献[5,6]的自助法(Bootstrap)，文献[7,8]的交叉验证(CV)法等.特别地,像文献[1]中指出的那样,交叉验证是预测误差估计中最简单、最广泛使用的方法,同时也得到了很多学者的广泛关注.实际应用中交叉验证也有多种形式,包括标准K折交叉验证,RLT(Repeated Learning Testing)交叉验证,MC(Monte-Carlo)交叉验证,5×2交叉验证方法等(如文献[9-12]).但面对折数的选择、计算复杂度和数据集切分等问题,这些交叉验证方法都存在着令人不满意的地方,文献[13]在综合分析已有交叉验证研究成果的基础上提出组块3×2交叉验证,并在自然语言处理的实际应用中验证了此方法优于常用的K折交叉验证.文献[14]也通过实验验证了此方法应用于算法性能对照检验中的优良性质,为此本文考虑把它应用于模型选择.

同时我们注意到,无论是上面提到的哪种模型选择方法都存在这样的一个问题,在某种评价准则下,一个具有较高复杂度的模型是最优的,而一个较简单模型是次优的,但实际上它们之间的差异可能是随机误差造成的,在统计上不显著,此时选择简单模型可能更合适.为此,本文把统计显著性检验应用于模型选择,给出了基于组块3×2交叉验证t检验的模型选择算法,并通过基于回归和分类的模拟实验进行了验证.

1基于组块3×2交叉验证t检验的模型选择算法

1.1组块3×2交叉验证

所谓组块3×2交叉验证指的是首先将数据集D随机地划分为4等份(P1,P2,P3,P4),然后任取两份训练,两份测试进行2折交叉验证,其中D={z1,z2,…,zn},zi∈Z是从某个未知分布P中独立抽样得到,zi=(xi,yi),xi为输入向量,yi为输出变量.具体如表1所示.

表1　组块3×2交叉验证

传统的基于交叉验证的模型选择就是要选择使得下式达到最小的模型A：

1.2基于组块3×2交叉验证t检验的模型选择算法

具体地,假定有m个备选模型A1,A2,…,Am,复杂度依次为h1,h2,…,hm,且不妨假设随着备选模型中下标增加, 模型的复杂度也相应增加(即h1≤h2≤…≤hm).记Cm为m维计数数组,用来统计重复实验中各备选模型A1,A2,…,Am作为最优模型的次数.

基于组块3×2交叉验证t检验的模型选择算法1.计数初值置为0,即cp=0(p=1,2,…,m);2.forp=1,2,…,(m-1) forq=(p+1),…,m a.计算用于模型Ap和Aq之间差异对照的检验统计量(见文献[14]) tpq=^μ3×2(Ap,Aq)16∑3i=1∑3k=1(^μ(i)k(Ap,Aq)-^μ3×2(Ap,Aq))2

其中^μ(i)k(Ap,Aq)=2n∑zj∈T(i)k(L(Ap(D(i)k),zj)-L(Aq(D(i)k),zj) b.iftpq>t1-α(5),且^μ3×2(Ap)>^μ3×2(Aq),则选择复杂度为hq的模型Aq,即cq=cq+1; else复杂度为hp的模型Ap和复杂度为hq的模型Aq没有显著差异,选择具有较低复杂度hp的模型Ap,即cp=cp+1;3.挑选出备选模型被选到的次数最多的模型Ak作为最优模型,其中k=argmaxpc(p)(p=1,2,…,m);如果它们中次数有相同的,则选择复杂度较低的模型作为最优模型.

2模拟实验

本节中我们分别在多项式回归和分类情形下对传统的模型选择方法(AIC,BIC,5折交叉验证, 组块3×2交叉验证)和本文提出的组块3×2交叉验证t检验方法进行了对照.首先描述了实验的设置,接着给出了实验对照结果.

2.1实验设置

2.1.1回归

2.1.2分类

在多项式分类中，xt(t=1,…,N)由[-1,1]上的均匀分布生成，rt(t=1,…,N)通过比较后验概率

的大小得到, 其中C0表示0类,C1表示1类.若P(C0|x)>P(C1|x),则rt取值为0,否则为1.类条件密度P(x|Ci),i=0,1通过

P(x|C0)=0.5N(-0.58,0.17)+0.5N(0.32,0.13)

P(x|C1)=0.6N(-0.10,0.15)+0.4N(0.65,0.09)

2.2实验结果和分析

这一小节中, 我们给出了五个模型选择方法(AIC,BIC,5折交叉验证(5CV),组块3×2交叉验证(32CV), 组块3×2交叉验证t检验(32CVt))的实验对照.考虑两个评价准则:最优模型的复杂度和测试集上最优模型的测试误差.为了使得对照更有效,相同的训练和测试样本用于所有的模型选择方法.通过1 000次重复实验来进行模型的选择.

2.2.1回归结果

图1～2给出了五种方法在两种样本量下1 000次重复实验中各阶多项式作为最优模型的次数.对中样本来说,AIC,BIC,5折交叉验证和组块3×2交叉验证方法选择5阶多项式作为最优模型,而本文给出的组块3×2交叉验证t检验方法选择4阶多项式作为最优模型.大样本下,AIC,BIC,组块3×2交叉验证方法选择6阶多项式作为最优模型,5折交叉验证选择7阶多项式作为最优模型,而本文方法选择的是5阶多项式.前四种方法在中样本下结果一致,在大样本下5折交叉验证选择更复杂的模型,而基于t检验的方法选择更简单的模型,因为如果一个简单模型不是比复杂模型统计意义下显著差的话,则倾向于选择简单模型.

图1　回归情形中样本的模型选择方法对照

图2　回归情形大样本的模型选择方法对照

用于模型选择方法对照的第二个准则是测试集上的测试误差,如表2所示.中样本下,AIC,BIC,5折交叉验证和组块3×2交叉验证四种方法具有相似的错误率和标准差(四种方法的错误率在后面的小数位上是有差异的),都比本文方法得出的要小,但是它们之间的差异是不显著的.随着样本量从中样本变为大样本,我们方法的错误率虽然还是最大的,但五种方法的结果变得更加相似.

表2　最优模型在测试集上的误差及其标准差

2.2.2分类结果

图3～4给出了分类情形五种方法在两种样本量下1 000次重复实验中各阶多项式作为最优模型的次数.中样本中,AIC,BIC,5折交叉验证和本文方法选择了3阶多项式作为最优模型,而组块3×2交叉验证选择的是5阶多项式.然而,5折和组块3×2交叉验证选择的波动比较大,比如组块3×2交叉验证选择的3,4,5,6,7阶多项式的次数均在150次左右.AIC,BIC和本文方法在1 000次重复中有950次以上选的是3阶多项式, 波动很小.

在大样本下,AIC方法选择的是5阶多项式,BIC和本文方法选择的是3阶多项式,这是因为BIC比AIC惩罚复杂模型更多,尤其是在大样本量下要远大于2.而5折和组块3×2交叉验证选择的是更复杂的6阶多项式来作为最优模型,且它们波动同样比较大.

图3　分类情形中样本的模型选择方法对照

图4　分类情形大样本的模型选择方法对照

表3给出了分类情形下两种测试样本集上五种方法的测试错误率和标准差.和回归情形类似,虽然本文提出的方法有较大的错误率,但是它和AIC,BIC,组块3×2交叉验证方法的差异是不显著的.5折交叉验证具有出奇高的错误率,这是因为虽然5折交叉验证中选的最优模型是6阶多项式,但实际上在1 000次重复中选到3～8阶多项式的次数都非常接近,所以也很容易犯错.

表3　最优模型在测试集上的

综上所述,组块3×2交叉验证t检验方法与其它方法相比较,测试误差的差异在统计意义下不显著,且该方法选择更简单的模型,这种选择更符合实际应用.

3结论

本文主要分析了组块3×2交叉验证t检验方法在回归和分类的模型选择任务中的性能,从选择的最优模型复杂度和测试集上最优模型的测试误差等两方面分析,本文所述方法具有较好的性能.

然而,在其它应用领域如密度估计和高维度的生物数据问题中,组块3×2交叉验证t检验方法是否也具有优良的性能? 另外,能否构造出组块m×2交叉验证方法和组块m×2交叉验证t检验方法,并将其用于分类和回归的模型选择任务? 上述这些问题，还值得我们在今后进一步去研究.

参考文献

[1] Wasseman L.Bayesian model selection and model averaging[J].Journal of Mathematical Psychology,2000,44:92-107.

[2] Hastie T,Tibshrani R,Friedman J.The elements of statistical learning:data mining,inference,and prediction[M].2nd edition.New York:Springer,2009.

[3] Spiegelhalter D J,Bes N G,Carlin B P,et al.Bayesian measures of model complexity and fit[J].Statistical Methodology,2002,64(4):583-639.

[4] Kadane J B,Lazar N A.Methods and criteria for model selection[J].Journal of the American Statistical Association,2004,99(465):279-290.

[5] Fronmont M.Model selection by bootstrap penalization for classification[J].Journal of Machine Learning,2007,66(2-3):165-207.

[6] Breiman L.The little bootstrap and other methods for dimensionality selection in regression:X-fixed prediction error[J].Journal of the American Statistical Association,1992,87:738-754.

[7] 李根,邹国华,张新雨.高维模型选择方法综述[J].数理统计与管理,2012,31(4):640-658.

[8] Houwelingen H C,Sauerbrei W.Cross-validation,shrinkage and variable selection in liner regression revisited[J].Open Journal of Statistics,2013,3:79-102.

[9] Bengio Y,Grandvalet Y.No unbiased estimator of variance of K-fold cross validation[J].Journal of Machine Learning,2004,5:1 089-1 105.

[10] Arlot S,Celisse A.A survey of cross-validation procedures for model selection[J].Statistics Surveys,2010,4:40-79.

[11] Nadeau C,Bengio Y.Inference for the generalization error[J].Machine Learning,2003,52(3):239-281.

[12] Yildiz O T.Omnivariate rule induction using a novel pairwise statistical test[J].IEEE Transactions on Knowledge and Data Engineering,2013,25:2 105-2 118.

[13] 李济洪,王瑞波,王蔚林,等.汉语框架语义角色的自动标注研究[J].软件学报,2010,30(4):597-611.

[14] Wang Yu,Wang Ruibo,Jia Huichen.Blocked 3×2 cross-validated t-test for comparing supervised classification learning algorithms[J].Neural Computation,2014,26(1):208-235.

[15] Yilidiz O T.Tuning model complexity using cross-validation for supervised learning[D].Turkey:Bagazici University,2005.

Model selection algorithm based on blocked 3×2 cross-validatedt-test

LIU Yan-qing1， WANG Yu2， LI Ji-hong2*

(1.College of Mathematical Sciences, Shanxi University, Taiyuan 030006, China ；2.Computer Center, Shanxi University, Taiyuan 030006, China)

Abstract:In traditional model selection problem,the evaluation of the model is always based on the performance indexes. However,in many cases,the difference of the performance indexes of the models may not be statistically significant,which may result from random error.Therefore,a new model selection algorithm is proposed based on blocked 3×2 cross-validated significance t-test for the difference of the indexes.Experiment results show that the algorithm always select the simple models based on the minimization of square loss (regression) or 0-1 loss (classification).

Key words:model selection； blocked 3×2 cross-validation； t-test； test error； model complexity

中图分类号：TP181

文献标志码：A

文章编号：1000-5811(2015)01-0179-05

通讯作者:李济洪(1964-), 男, 山西长治人, 教授, 博士生导师，研究方向:统计机器学习及统计自然语言处理,lijh@sxu.edu.cn

作者简介:刘焱青(1988-), 女, 山西忻州人, 在读硕士研究生, 研究方向: 统计机器学习

基金项目：山西省科技厅科技基础条件平台建设项目(20130910030101)