Enforcing Output Constraints via SGD: A Step Towards Neural Lagrangian Relaxation

Abstract

Structured prediction problems such as named entity recognition and parsing are crucial for automated knowledge base construction. Increasingly, researchers are exploring ways of improving them with neural networks. However, many structured-prediction problems require deterministic constraints on the output values; for example, requiring that the sequential outputs encode a valid tree. While hidden units might capture such properties, the network is not always able to learn them from the training data alone, and practitioners must then resort to post-processing. In this paper, we present an inference method for neural networks that enforces deterministic constraints on outputs without performing post-processing or expensive discrete search. Instead, for each input, we nudge continuous weights until the networks unconstrained inference procedure generates an output that satisfies the constraints. We apply our method to pre-trained networks of various quality for constituency parsing and find that in each case, not only does the algorithm rectify a vast majority of violating outputs, it also improves accuracy.