相比于普通的机器学习算法,结构化机器学习可以利用结构信息达到更好的效果,但其时间复杂度要高很多,虽然有快速的近似解法,但精度的损失一定程度上抵消了结构信息带来的好处,因此研究快速精确的结构化机器学习算法成了一个重要的课题。本文中,我们对结构化机器学习中的推断算法以及特征抽取两个重要环节进行改进。首先,我们针对序列标注问题,基于许多实际应用中高阶特征信息的稀疏性特点,提出了稀疏高阶的条件随机场模型和一种新的快速精确的推断算法,它可以同时处理局部特征和稀疏的高阶特征。由于稀疏性的存在,这种新的推断算法是十分高效的。在手写体识别任务上,我们采用词缀特征作为高阶特征,稀疏高阶的条件随机场模型达到了所有公开的实验结果中最高的精度。在中文组织机构名识别任务上,我们将人工抽取的规则转化为高阶特征,并取得了微软亚洲研究院数据集上第二名的成绩。这两个实验表明,在特征集相同的情况下,稀疏高阶的条件随机场模型明显优于其他的方法。其次,我们提出了一种新的特征字符串索引结构以加速特征抽取,从而缩短解码时间。现在许多结构化机器学习方法采用模板生成数以百万千万的特征。复杂的模板可以产生大量复杂的特征,从而提高了精度,但却需要更多特征抽取的时间,大大影响了解码速度。为此,我们提出了两维的Trie结构,该结构可以利用模板之间的相互关系提高特征抽取的速度：一个模板生成的特征字符串是它的扩展模板生成的特征字符串的前缀,因此前一个特征字符串的索引号可以用来检索后一个特征字符串,从而节约了时间。我们将这种新的数据结构用在基于图模型的依存句法分析的任务上。在中文宾州树库上的实验表明,两维Trie的特征抽取速度是传统Trie的5倍,整个句法分析的解码速度是后者的4.3倍。