A Credit Assignment Compiler for Joint Prediction
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.
This paper presents a system designed to speed up the implementation and execution of learning-to-search algorithms. Once the user implements their application as a small program built atop two library functions ("Predict" and "Loss"), the system can use that program to both learn the model parameters and generate predictions at test time, essentially by swapping in different versions of the two library primitives. Experiments show that several NLP problems can be solved very quickly and accurately using this system, which the authors call a "credit assignment compiler".
This is an interesting and novel paper. It's sort of a fusion between proposing a general "master algorithm" for a number of existing learn-to-search approaches (Searn, DAgger, etc.) and an engineering exercise in making this master algorithm run quickly. The empirical runtime/accuracy results are compelling, and I suspect the system might be useful to a wide range of people once it is released.  At the same time, I have some reservations about the way the paper is written and structured. Since the authors are emphasizing that their implementation of this general algorithm is easy and fast for practitioners to use, it seems problematic that it is (to me) very difficult to understand how one would actually use it. Partly this is because, for instance, Algorithm 1 (MyRun) uses a bunch of terms that have not been explained at that point (tags, etc.) -- i.e., some reordering might help. But partly it's because some things are never really explained.  For instance, other than reverse-engineering the desired learning procedure using Algorithm 3, how should a user write MyRun? How should we think of Predict and Loss in an intuitive way? And how is this different from writing a search algorithm? The concept of a TDOLR function is defined without much context, but seems to be central. There is a footnote about letting MyRun control the machine stack, but I am not sure what this is supposed to mean for pseudocode. And to be honest, I still don't understand why this is called a credit assignment compiler. I get that search provides credit assignment by measuring the effect of each decision in (relative) isolation, but in what sense is this a compiler?  In general, I found the idea of the paper and the results produced compelling, but wished the middle part was better able to articulate why I should believe that this system is natural or easy to use. Some additional examples, tutorial-style, would go a long way. There are also a large number of typos and grammatical errors that need to be fixed.