Learning Constraints for Structured Prediction Using Rectifier Networks

Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 4843–4858 July 5 - 10, 2020. c⃝2020 Association for Computational Linguistics 4843 Learning Constraints for Structured Prediction Using Rectifier Networks Xingyuan Pan, Maitrey Mehta, Vivek Srikumar School of Computing, University of Utah {xpan,maitrey,svivek}@cs.utah.edu Abstract Various natural language processing tasks are structured prediction problems where outputs are constructed with multiple interdependent decisions. Past work has shown that domain knowledge, framed as constraints over the out- put space, can help improve predictive accu- racy. However, designing good constraints of- ten relies on domain expertise. In this pa- per, we study the problem of learning such constraints. We frame the problem as that of training a two-layer rectifier network to iden- tify valid structures or substructures, and show a construction for converting a trained net- work into a system of linear constraints over the inference variables. Our experiments on several NLP tasks show that the learned con- straints can improve the prediction accuracy, especially when the number of training exam- ples is small. 1 Introduction In many natural language processing (NLP) tasks, the outputs are structures which can take the form of sequences, trees, or in general, labeled graphs. Predicting such output structures (e.g. Smith, 2011) involves assigning values to multiple interdepen- dent variables. Certain joint assignments may be prohibited by constraints designed by domain ex- perts. As a simple example, in the problem of ex- tracting entities and relations from text, a constraint could disallow the relation “married to” between two entities if one of the entity is not a “person”. It has been shown that carefully designed constraints can substantially improve model performance in various applications (e.g., Chang et al., 2012; An- zaroot et al., 2014), especially when the number of training examples is limited. Designing constraints often requires task- specific manual effort. In this paper, we ask the question: can we use neural network methods to automatically discover constraints from data, and use them to predict structured outputs? We provide a general framework for discovering constraints in the form of a system of linear inequalities over the output variables in a problem. These constraints can improve an already trained model, or be inte- grated into the learning process for global training. A system of linear inequalities represents a bounded or unbounded convex polytope. We ob- serve that such a system can be expressed as a two- layer threshold network, i.e., a network with one hidden layer of linear threshold units and an output layer with a single threshold unit. This two-layer threshold network will predict 1 or −1 depending on whether the system of linear inequalities is sat- isfied or not. In principle, we could try to train such a threshold network to discover constraints. However, the zero-gradient nature of the threshold activation function prohibits using backpropagation for gradient-based learning. Instead, in this paper, we show that a construc- tion of a specific two-layer rectifier network rep- resents linear inequality constraints. This network also contains a single …

Content truncated to 500 words