结构化预测也叫做结构化学习，目标是从数据中学习一个复杂的结构，它是自然语言处理、数据挖掘、机器学习领域的一个研究热点。N元特征在很大程度上反映了结构化预测中“结构”的信息，是结构化预测中一类特殊且极为重要的特征。然而，绝大多数关于N元特征选择的工作，仅仅将它当作一种普通的特征来处理，而没有考虑N元特征的性质，其实质仍然是普通特征选择。少数几个研究考虑了N元特征的性质，但很不充分，而且仅仅关注具体任务中的一种或几种特征，其方法不具普遍性。因此，对结构化预测中N元特征选择的研究非常少，可以说几乎是一片空白。　　本文将结构化预测中N元特征选择作为一个全新的研究课题，旨在提出一种适用于结构化预测的N元特征选择的通用框架。基于对该目标的分析，论文在绪论部分就确定了该框架的大致雏形，包括特征选择的方式（封装式）、特征选择的对象（N元特征模板而非特征函数）、特征搜索策略（启发式），以及特征搜索的顺序（自下而上），并对该雏形框架可能存在的问题，包括特征选择效率、鲁棒性和过拟合，逐一给出解决方案。本文的主要工作包括以下几个方面：　　1)论文定义了结构化预测中的N元特征模板，系统地研究了它的性质，给出了结构化预测中N元特征重要性的大致分布，并通过实验予以验证。　　2)论文提出一种高效的N元单特征选择算法（SNFS）。该算法包括三个子算法：阶数重要性排序算法、水平搜索算法、特征模板对组合算法。其中，最关键的是特征模板对组合算法，它的核心思想是：根据N元特征的重要性大致分布，能定位最有可能的两个候选者，通过比较这两个候选者和它们的并集，能进一步准确地判断N元特征重要性的具体走向，从而高效地裁剪搜索空间。　　3)论文提出一种N元多特征选择算法（MNFS）。SNFS算法每次只能处理一种N元特征，如果任务中需要同时选择多种类型的N元特征，那么该算法必须运行多次，每次处理一种特征，最后求并集。但这种做法没有考虑多种N元特征之间的相关性，所以得到的特征集可能存在冗余。MNFS算法有效地解决了特征冗余的问题。论文通过实验全面地分析了算法的特征选择性能、效率、鲁棒性以及抗过拟合的能力，并与经典的封装式特征选择方法进行了对比。实验表明，MNFS算法的特征选择性能与经典的封装式方法大致相当，但MNFS算法极其高效、鲁棒，抗过拟合能力也优于经典的封装式方法。　　4)论文提出一种通用的封装式特征选择的加速方法。该方法的基本思想是：“放松”模型中跟训练时间相关的变量以加速训练过程，同时定义了一个相似度度量值TopMatches用于平横模型的预测性能和特征选择性能，并利用坐标下降法搜索相关的变量值。　　5)论文提出一种路径约束的维特比算法来替代结构化预测中耗时严重的转移特征，进一步提高了特征选择效率。