|
Chang et al. 2015提出加速结构化学习的近似算法AI-DCD，通过缓存整数线性规划中相似的问题及解，减少对ILP solver的调用次数，从而加速训练，同时不损失精度。
每个词语是实体的概率如表格所示，ILP的转化方法为：
这里的yy 都是二值向量中的元素，对应于论文中的zz 。最后一个式子是约束配偶关系只能成立于两个人名之上。
一些特殊的结构（如标注序列）允许将推断问题转化为搜索问题，然后通过高效精确的算法（如维特比算法）解决。而其他场景下的推断问题则是计算代价昂贵的，所以希望得到缓解。
Srikumar, Kundu, and Roth 2012发现（1）不同的目标函数常常导致相同的解，（2）哪怕所有可能的结构是指数级，实际上成立的只有少数。他们通过刻画那些共享式（2）中相同解的问题来加速推断。
他们提出了下列理论：
利用Amortized Inference加速训练
以前的研究大多将推断过程当成黑盒子，作者提出应当结合具体模型设计算法：用于结构化SVM的AI-DCD（Amortized Inference framework for Dual Coordinate Descent）和用于结构化感知机的AI- SP(Amortized Inference for Structured Perceptron)。
加速结构化SVM
加速结构化感知机
同为在线学习算法，可应用类似的缓存技巧。
试验
在实体关系抽取任务上应用平摊推断技巧到结构化SVM上：
黑线是朴素方法对ILP solver的调用次数，蓝线是理论上所需的最低调用次数（样本的结构数量），红线是平摊推断算法的调用次数。
在提高推断速度的同时，AI-DCD并没有损失精确度：
References
[1]K.-W. Chang, S. Upadhyay, G. Kundu, and D. Roth, “Structural Learning with Amortized Inference.,” AAAI, 2015.
http://web.cs.ucla.edu/~kwchang/TAAI17.pdf
原文：http://www.hankcs.com/ml/structural-learning-with-amortized-inference.html
| 
收藏