学步园

下面介绍一下结构化预测(structured prediction)的概念以及常见的参数学习方法：

1.概念：

结构化预测(structured prediction)是由SVM发展而来的。SVM是一种最大间隔(max-margin)的方法，最擅长处理二分类问题，后来也被用于处理多分类问题。SVM的优点在于有很好的理论基础，即它的泛化能力很强。它的缺点在于1）训练复杂度高；2）不能用于预测结构化问题。

结构化问题的例子有很多：给定一个句子，找出它对应的依存树(dependency tree)；对一个图进行分割(image segmentation)等。

结构化预测(structured prediction)通过修改SVM的约束条件以及目标函数，将SVM从二分类问题扩展到可以预测结构化问题。一种常见的表述方法如下：

约束条件的意思是：对于任何一个学习用例，数据集的标注结果应该比模型预测的结果都要好！

2.参数学习方法

参数学习方法有很多：

structured perceptron(Collins, 2002)

stochastic subgradient(Ratliff, 2007)

extra-gradient(Taskar, 2006)

cutting-plane algorithms(Joachims, 2009)

Dual decomposition(Meshi, 2010)

下边是关于structured prediction的reading list:

[2005 ICML]integer linear programming inference for conditional random fields.pdf

[2005 IJCAI]learning and inference over constrained output.pdf

[2006 EMNLP]competitive generative models with structure learning for NLP classifiction tasks.pdf

[2007]Pegasos-primal estimated subgradient solver for svm.pdf

[2007]subgradient methods for structured prediction.pdf

[2008 ICML]training structural svms when exact inference is intractable.pdf

[2008 NIPS]strctured learning with approximate inference.pdf

[2009 ICML]polyhedral outer approximations with application to natural language parsing.pdf

[2009 machine learning]piecewise training for structured prediction.pdf

[2010 ICML]learning effieicently with approximate inference via dual losses.pdf

[2012 ICML]efficient decomposed learning for structured prediction.pdf