第一章 绪论
1.1 研究背景及意义
机器学习模型已被广泛应用于现代智能信息系统中，如，语音识别系统、搜索引擎、信息检索及多模态自动问答系统等。机器学习模型通常使用各种类型的结构化数据或非结构化数据（如，文本数据）作为输入，来训练不同的学习算法并验证它们的性能。模型构建初期，研究者一般采用规模适中的数据，经过特征提取、特征选择、超参数选择、分类器选择及评估等阶段，最后将模型确定下来。之后，研究者再使用大规模的数据再次训练该模型中的参数，以得到较好的参数估计。这个过程中，在分类器选择、特征选择、超参数选择等多个阶段，研究者均需要采用合理的方法来比较多种算法在同一个数据集上产生的多个模型的性能（以下简称算法比较）。比如，在特征选择阶段，研究者需要判断新特征对模型的性能提升是否有显著作用；在超参数选择时，研究者需要比较新的超参数选择算法产生的模型与旧算法的模型的性能差异。由此可见，算法比较是机器学习中的一个基本问题，是建模过程中的重要技术。
本文仅考虑两个有监督学习算法的比较问题，并将该问题描述为：给定两个学习算法及用于算法训练和验证的一个数据集，哪个算法可以产生性能更为优良的模型？[1] 在算法比较中，交叉验证方法和统计显著性检验常结合使用。交叉验证方法是指对给定的一个数据集进行多次切分，形成多组训练集和验证集，先使用训练集训练机器学习算法，得到相应模型，之后在验证集上得到算法性能指标的估计（简称指标估计），最后综合分析多组指标估计来以推断出性能更为优良的算法。常用的交叉验证方法包括 repeated learning-testing （RLT）、K 折交叉验证[2]、5 × 2 交叉验证、组块 3 × 2 交叉验证等[3–5]。交叉验证中的多组估计，可用来构造 t 检验统计量，Wilcoxon 秩统计量等，进而结合显著性检验来进行算法比较[1]。在通常的IID 数据集上，用于算法比较的显著性检验方法主要包括基于 K 折交叉验证的 t 检验方法、基于 5 × 2 交叉验证的 t 检验及 F 检验方法[6,7]、基于组块 3 × 2 交叉验证的 t 检验方法[8]、基于均衡 5 × 2 交叉验证的校正 t 检验[9]等。
.............................
1.2 数据切分的优化设计：正则化交叉验证方法
1.2.1 设计原则
对于交叉验证方法的设计，本文以减小训练集、验证集的差异，降低算法性能指标估计的方差为目标，从如下三个原则来考虑。
原则一：应使不同切分的两个训练集间的重叠样本个数尽量少且相同相同数据集上的多次随机切分，会使任意两个训练集间存在重叠样本，而且重叠样本的个数是随机的。Markatou 等证明了重叠样本的个数服从超几何分布[20]。王钰等的研究工作表明，重叠样本个数越多，指标估计的方差也越大[8]。本文引理2.1 进一步揭示重叠样本个数与指标估计的方差间的关系可以用二次函数近似来描述。因此，交叉验证方法的数据切分中，任意两个训练集间重叠样本个数应尽量少且尽量相同，以减小指标估计的方差。
原则二：应使训练集和验证集分布尽可能的一致
理论上来说，机器学习要求训练集、验证集的数据分布相同。在通常的 IID 数据集上，随机切分会引入训练集和验证集间的分布差异，增大指标估计的方差。因此，研究者需要对训练集和验证集上的分布差异进行度量，然后使用该度量来指导训练集和验证集中样例的分配。相比结构化数据而言，文本数据是非结构化的，它似乎更难达到“分布相同”这个要求。在随机切分形成的训练集和验证集中，预测标记的分布、词分布等可能存在明显差异，导致指标估计波动较大，且更容易受到交叉验证的切分方法的影响。为此，基于通常的 IID 数据和文本数据各自的特点，交叉验证在切分数据时，应尽量减少训练集和验证集间的分布差异。
原则三：应选择适合算法比较的交叉验证方法，并有效地增加切分次数
在处理通常的 IID 数据时，针对算法比较问题，许多研究表明，常用的 5 折和10 折交叉验证方法不如 5 × 2 交叉验证和组块 3 × 2 交叉验证方法[1,6–8]。5 × 2 和3 × 2 交叉验证可自然拓展为 m × 2 交叉验证。m × 2 交叉验证具体指在给定的数据集上，重复做 m 次 2 折交叉验证，并综合使用 m 次结果来比较算法的性能。重复次数 m 的增加，可以带来更好的指标估计，有利于建立更好的显著性检验方法，
如，序贯检验。另外，m × 2 交叉验证的 m 次切分中，每一次数据切分使用对半的比例，相对容易使得训练集和验证集的分布趋于相同，有利于减小分布的不均匀带来的影响。这一点在在文本数据上尤为重要。因此，针对算法比较问题，本文着重研究基于 m × 2 交叉验证的统计推断方法。
...............................
第二章 正则化 RLT 方法
2.1 记号及定义
.............................
2.2 正则化 RLT 的形式化描述
............................
第三章 正则化 m × 2 交叉验证方法 . . . . . . . . . . . . . . 43
3.2 m × 2 交叉验证估计的方差的理论分析 . . . . . . . . . . . . . . . . . . 45
3.3 正则化 m × 2 交叉验证切分集的增量式构造算法 . . . . . . . . . . . . . 50
第四章 文本数据的正则化 m × 2 交叉验证初探 . . . . . . . . . . . . . . . . . . 67
4.1 构造正则化交叉验证方法的基本思路 . . . . . . . . . . . . . . . . . . . . 67
4.1.1 记号和定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.1.2 正则化 m × 2 交叉验证求解的优化表示 . . . . . . . . . . . . . . . 69
第五章 针对泛化误差的正则化 m × 2 交叉验证统计推断方法 . . . . . . . . . . 79
5.1 问题描述 . . . . . . . . . . . . . . 79
5.2 泛化误差差值 μ 的正则化 m × 2 交叉验证序贯置信区间 . . . . . . . . . 79
第七章 正则化 m × 2 交叉验证在软件缺陷预测任务上的应用
7.1 软件缺陷预测任务的特点
在软件缺陷预测任务中，软件历史数据常以软件模块为基本单位进行收集。每个软件模块的特性可以通过多种度量进行量化。常用的度量多达五六十种，主要包括一些静态的软件复杂度度量[104]，如代码行数、Halstead 复杂度、圈复杂度等，以及一些软件运行时的动态度量[105]，如传递消息数、接受消息数、类实例数等。软件历史数据常以 IID 数据集的形式进行存储和使用。IID 数据集中的每条样例对应于一个软件模块，每个特征对应于软件模块的一种度量。基于这种形式的软件历史数据，软件缺陷预测任务常被看作一个机器学习的建模问题，也必须采用合理的算法比较方法来对比和分析各种不同的学习算法，以保障选择到优良的缺陷预测模型。这为本文的正则化 m × 2 交叉验证提供了一个重要的应用场景。
缺陷倾向性预测任务旨在判断一个新软件模块是否有缺陷，对应于机器学习中的二分类问题，可用 logistic 回归、支持向量机等分类器进行建模。缺陷倾向性预测任务的历史数据集使用正类和负类来标识软件模块是否存在缺陷，其中，正类表示软件模块存在缺陷。常见的缺陷倾向性数据集规模通常不大，含有数百到数千条样例不等，且类别不均衡问题非常明显[106]。正类的样例占比通常小于 20%。从类别不均衡的角度分析，常用的 5 折和 10 折交叉验证容易使得正类样例在验证集中出现的频次过少，可能会导致缺陷倾向性预测模型的指标估计大幅度波动，不利于得到可靠的算法比较结论。相比而言，在缺陷倾向性预测数据上，正则化 m × 2 交叉验证不仅可以将训练集间的重叠个数“正则化”到 n/4 左右（n 为数据集大小），还可以引入“分层”约束将正例在训练集和验证集中占比“正则化”成相同的比例。这可以保障正则化 m × 2 交叉验证在缺陷倾向性预测任务上得到可靠的算法比较结论。
...........................
结论及展望
优良的算法比较方法是构建现代智能软件的核心技术，也为研究者高效开发新型的机器学习算法提供了重要保障。本文面向算法比较任务，针对通常的 IID 数据和文本数据的特点，综合分析泛化误差、准确率、召回率和 F1值等算法性能指标的特性，从交叉验证数据切分的优化及算法比较的统计推断两个方面进行研究，初步形成了一个基于正则化交叉验证的算法比较统计推断的方法体系。本文以软件缺陷预测任务为例，给出了正则化交叉验证在缺陷数预测模型上的一个具体应用。本文的主要研究结论和创新总结如下：
一、揭示了训练集间重叠样本个数与算法性能指标的交叉验证估计的方差间的关系。 对泛化误差的 RLT 估计的方差及 m × 2 交叉验证估计的方差进行深入分析。研究了交叉验证估计所含的任意两个 hold-out 估计间的协方差与训练集间重叠样本个数的关系，发现两个 hold-out 估计的协方差是训练集间重叠样本个数的下凸函数。进而，证明泛化误差的两个 2 折交叉验证估计的协方差为其训练集间重叠样本个数的下凸对称函数，且对称轴为 n/4 （n 为数据集大小）。这些性质为正则化交叉方法的理论创新提供了前提。
二、建立了正则化交叉验证方法。以最小化泛化误差的交叉验证估计的方差为目标，建立相应的优化问题，并引入相应的正则化条件，来优化交叉验证的数据切分方式，以建立正则化交叉验证方法。对于 RLT 方法，引入了两个正则化条件：1）所有重叠样本个数的总和最小；和 2）训练集间所有重叠样本个数尽量相同。进而，提出了正则化 RLT 方法，从理论上保证了泛化误差的正则化 RLT 估计的方差小于随机切分情形下 RLT 估计的方差。对于 m × 2 交叉验证，引入一个正则化条件将训练集间重叠样本个数约束至 n/4 （n 为数据集大小），并建立了正则化 m × 2交叉验证方法。本文证明泛化误差的正则化 m × 2 交叉验证估计的方差小于随机切分情形下 m × 2 交叉验证估计的方差。对于文本数据，本文引入卡方度量来度量训练集和验证集间多种频次分布的不同。基于该卡方度量构造正则化条件来约束该分布之差，并将该正则化条件引入正则化 m × 2 交叉验证中，构造了适用于文本数据的正则化 m × 2 交叉验证方法。本文以汉语框架语义角色标注任务为例，说明了文本数据的正则化 m × 2 交叉验证方法的有效性。
参考文献（略）