A Credit Assignment Compiler for Joint Prediction
Kai-Wei Chang University of Illinois \AndHe He University of Maryland \AndHal Daumé III University of Maryland \ANDJohn Langford Microsoft Research \AndStephane Ross Google
Abstract
Many machine learning applications involve jointly predicting multiple mutually dependent output variables. Learning to search is a family of methods where the complex decision problem is cast into a sequence of decisions via a search space. Although these methods have shown promise both in theory and in practice, implementing them has been burdensomely awkward. In this paper, we show the search space can be defined by an arbitrary imperative program, turning learning to search into a credit assignment compiler. Altogether with the algorithmic improvements for the compiler, we radically reduce the complexity of programming and the running time. We demonstrate the feasibility of our approach on multiple joint prediction tasks. In all cases, we obtain accuracies as high as alternative approaches, at drastically reduced execution and programming time.
中文速览
联合预测（joint prediction）中如何让模型在做出一连串子决策时合理分配"功过"（信用分配问题），一直是让研究者头疼又难以工程化落地的难题。本文提出将"搜索式学习"（learning to search）框架重新诠释为一个信用分配编译器，允许开发者用普通的命令式程序来描述搜索空间，而不必再手工定义繁琐的有限状态机——同一套解码函数既用于训练也用于测试，训练逻辑几乎"免费"获得。配合记忆化缓存和强制路径折叠两项算法优化，编译器大幅压缩了重复推理的计算开销。在词性标注、实体识别等多项联合预测任务上，该方法以极少的代码量达到了与现有最优方法相当的精度，同时显著缩短了运行时间。这项工作的意义在于，它把理论上严谨但工程上笨重的搜索式联合预测变成了一个对开发者友好、性能又不打折的实用工具，为未来研究提供了简洁有力的基准。
原文 arXiv:1406.1837;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1406.1837v5