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 output space, can help improve predictive accuracy. However, designing good constraints often relies on domain expertise. In this paper, we study the problem of learning such constraints. We frame the problem as that of training a two-layer rectifier network to identify valid structures or substructures, and show a construction for converting a trained network into a system of linear constraints over the inference variables. Our experiments on several NLP tasks show that the learned constraints can improve the prediction accuracy, especially when the number of training examples is small. 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 interdependent variables. Certain joint assignments may be prohibited by constraints designed by domain experts. As a simple example, in the problem of extracting 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; Anzaroot 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 integrated into the learning process for global training. A system of linear inequalities represents a bounded or unbounded convex polytope. We observe 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 satisfied 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 construction of a specific two-layer rectifier network represents linear inequality constraints. This network also contains a single linear threshold output unit, but in the hidden layer, it contains rectified linear units (ReLUs). Pan and Srikumar (2016) showed that a two-layer rectifier network constructed in such a way is equivalent to a threshold network, and represents the same set of linear inequalities as the threshold network with far fewer hidden units. The linear constraints thus obtained can augment existing models in multiple ways. For example, if a problem is formulated as an integer program (e.g., Roth and Yih, 2004, 2005; Riedel and Clarke, 2006; Martins et al., 2009), the learned constraints will become additional linear inequalities, which can be used directly. Alternatively, a structure can be constructed using graph search (e.g., Collins and Roark, 2004; Daume et al., 2009; Doppa et al., 2014; Chang et al., 2015; Wiseman and Rush, 2016), in which case the learned constraints can filter available actions during search-node expansions. Other inference techniques that extend Lagrangian Relaxation (Komodakis et al., 2007; Rush et al., 2010; Martins et al., 2011) can also employ the learned constraints. Essentially, the learned constraints can be combined with various existing models and inference techniques and the framework proposed in this paper can be viewed as a general approach to improve structured prediction. We report experiments on three NLP tasks to verify the proposed idea. The first one is an entity and relation extraction task, in which we aim to label the entity candidates and identify relations between them. In this task, we show that the learned constraints can be used while training the model to improve prediction. We also show that the learned constraints in this domain can be interpreted in a way that is comparable to manually designed constraints. The second NLP task is to extract citation fields like authors, journals and date from a bibliography entry. We treat it as a sequence labeling problem and show that learned constraints can improve an existing first-order Markov model trained using a structured SVM method (Tsochan-taridis et al., 2004). In the final experiment we consider chunking, i.e., shallow parsing, which is also a sequence labeling task. We train a BiLSTM-CRF model (Huang et al., 2015) on the training set with different sizes, and we show that learned constraints are particularly helpful when the number of training examples is small. In summary, the contributions of this paper are: 1. We propose that rectifier networks can be used to represent and learn linear constraints for structured prediction problems. 2. In tasks such as entity and relation extraction, the learned constraints can exactly recover the manually designed constraints, and can be interpreted in a way similar to manually designed constraints. 3. When manually designed constraints are not available, we show via experiments that the learned constraints can improve the original model's performance, especially when the original model is trained with a small dataset. 1 1 The scripts for replaying the experiments are available at https://github.com/utahnlp/learning-constraints 2 Representing Constraints In this section, we formally define structured prediction and constraints. In a structured prediction problem, we are given an input x belonging to the instance space, such as sentences or images. The goal is to predict an output y  Y x , where Y x is the set of possible output structures for the input x . The output y have a predefined structure (e.g., trees, or labeled graphs), and the number of candidate structures in Y x is usually large, i.e., exponential in the input size. Inference in such problems can be framed as an optimization problem with a linear objective function: y  = argmax y Y x    ( x , y ) , (1) where  ( x , y ) is a feature vector representation of the input-output pair ( x , y ) and  are learned parameters. The feature representation  ( x , y ) can be designed by hand or learned using neural networks. The feasible set Y x is predefined and known for every x at both learning and inference stages. The goal of learning is to find the best parameters  (and, also perhaps the features  if we are training a neural network) using training data, and the goal of inference is to solve the above argmax problem given parameters  . In this paper, we seek to learn additional constraints from training examples { ( x , y ) } . Suppose we want to learn K constraints, and the k th one is some Boolean function 2 : c k ( x , y ) = 1 if ( x , y ) satisfies the k th constraint, and c k ( x , y ) =  1 if it does not. Then, the optimal structure y  is the solution to the following optimization problem: max y Y x    ( x , y ) , (2) subject to  k, c k ( x , y ) = 1 . Boolean functions over inference variables may be expressed as linear inequalities over them (Roth and Yih, 2004). In this paper, we represent constraints as linear inequalities over some feature vector  ( x , y ) of a given input-output pair. The k th constraint c k is equivalent to the linear inequality w k   ( x , y ) + b k  0 , (3) 2 We use 1 to indicate true and  1 to indicate false . whose weights w k and bias b k are learned. A Boolean constraint is, thus, a linear threshold function, c k ( x , y ) = sgn (cid:0) w k   ( x , y ) + b k (cid:1) . The feature representations  ( x , y ) should not be confused with the original features  ( x , y ) used in the structured prediction model in Eq. (1) or (2). Hereafter, we refer to  ( x , y ) as constraint features . Constraint features should be general properties of inputs and outputs, since we want to learn domain-specific constraints over them. They are a design choice, and in our experiments, we will use common NLP features. In general, they could even be learned using a neural network. Given a constraint feature representation  (  ) , the goal is thus to learn the parameters w k 's and b k 's for every constraint. For an input x , we say the output y is feasible if it satisfies constraints c k for all k = 1 , . . . , K . We can define a Boolean variable z ( x , y ) indicating whether y is feasible with respect to the input x : z ( x , y ) = c 1 ( x , y )      c K ( x , y ) . That is, z is a conjunction of all the Boolean functions corresponding to each constraint. Since conjunctions are linearly separable, we can rewrite z ( x , y ) as a linear threshold function: z ( x , y ) = sgn (cid:16) 1  K + K (cid:88) k =1 c k ( x , y ) (cid:17) . It is easy to see that z ( x , y ) = 1 if, and only if, all c k 's are 1 precisely the definition of a conjunction. Finally, we can plug Eq. (4) into Eq. (5): z = sgn (cid:16) 1  K + K (cid:88) k =1 sgn (cid:0) w k   ( x , y ) + b k (cid:1)(cid:17) (6) Observe that Eq. (6) is exactly a two-layer threshold neural network:  ( x , y ) is the input to the network; the hidden layer contains K linear threshold units with parameters w k and b k ; the output layer has a single linear threshold unit. This neural network will predict 1 if the structure y is feasible with respect to input x , and  1 if it is infeasible. In other words, constraints for structured prediction problems can be written as two-layer threshold networks. One possible way to learn constraints is thus to learn the hidden layer parameters w k and b k , with fixed output layer parameters. However, the neural network specified in Eq. (6) is not friendly to gradient-based learning; the sgn(  ) function has zero gradients almost everywhere. To circumvent this, let us explore an alternative way of learning constraints using rectifier networks rather than threshold networks. We saw in the previous section that a system of linear inequalities can be represented as a two-layer threshold network. In this section, we will see a special rectifier network that is equivalent to a system of linear inequalities, and whose parameters can be learned using backpropagation. Denote the rectifier (ReLU) activation function as R( x ) = max(0 , x ) . Consider the following two-layer rectifier network: z = sgn (cid:16) 1  K (cid:88) k =1 R (cid:0) w k   ( x , y ) + b k (cid:1)(cid:17) (7) The input to the network is still  ( x , y ) . There are K ReLUs in the hidden layer, and one threshold unit in the output layer. The decision boundary of this rectifier network is specified by a system of linear inequalities. In particular, we have the following theorem (Pan and Srikumar, 2016, Theorem 1): Theorem 1. Consider a two-layer rectifier network with K hidden ReLUs as in Eq. (7) . Define the set [ K ] = { 1 , 2 , . . . , K } . The network output z ( x , y ) = 1 if, and only if, for every subset S of [ K ] , the following linear inequality holds: 1  (cid:88) k S (cid:0) w k   ( x , y ) + b k (cid:1)  0 (8) The proof of Theorem 1 is given in the supplementary material. To illustrate the idea, we show a simple example rectifier network, and convert it to a system of linear inequalities using the theorem. The rectifier network contains two hidden ReLUs ( K = 2 ): z = sgn (cid:16) 1  R (cid:0) w 1   + b 1 (cid:1)  R (cid:0) w 2   + b 2 (cid:1)(cid:17) Our theorem says that z = 1 if and only if the following four inequalities hold simultaneously, one per subset of [ K ] :   1  0 1  (cid:0) w 1   + b 1 (cid:1)  0 1  (cid:0) w 2   + b 2 (cid:1)  0 1  (cid:0) w 1   + b 1 (cid:1)  (cid:0) w 2   + b 2 (cid:1)  0 The first inequality, 1  0 , corresponding to the empty subset of [ K ] , trivially holds. The rest are just linear inequalities over  . In general, [ K ] has 2 K subsets, and when S is the empty set, inequality (8) is trivially true. The rectifier network in Eq. (7) thus predicts y is a valid structure for x , if a system of 2 K  1 linear inequalities are satisfied. It is worth mentioning that even though the 2 K  1 linear inequalities are constructed from a power set of K elements, it does not make them dependent on each other. With general choice of w k and b k , these 2 K  1 inequalities are linearly independent. This establishes the fact that a two-layer rectifier network of the form of Eq. (7) can represent a system of linear inequality constraints for a structured prediction problem via the constraint feature function  . In the previous section, we saw that both threshold and rectifier networks can represent a system of linear inequalities. We can either learn a threshold network (Eq. (6)) to obtain constraints as in (3), or we can learn a rectifier network (Eq. (7)) to obtain constraints as in (8). The latter offers two advantages. First, a rectifier network has non-trivial gradients, which facilitates gradient-based learning 3 . Second, since K ReLUs can represent 2 K  1 constraints, the rectifier network can express constraints more compactly with fewer hidden units. We will train the parameters w k 's and b k 's of the rectifier network in the supervised setting. First, we need to obtain positive and negative training examples. We assume that we have training data for a structured prediction task. Positive examples can be directly obtained from the training data of the structured prediction prob-3 The output threshold unit in the rectifier network will not cause any trouble in practice, because it can be replaced by sigmoid function during training. Our theorem still follows, as long as we interpret z ( x , y ) = 1 as  ( x , y )  0 . 5 and z ( x , y ) =  1 as  ( x , y ) < 0 . 5 . We can still convert the rectifier network into a system of linear inequalities even if the output unit is the sigmoid unit. lem. For each training example ( x , y ) , we can apply constraint feature extractors to obtain positive examples of the form (  ( x , y ) , +1) . Negative examples can be generated in several ways; we use simple but effective approaches. We can slightly perturb a structure y in a training example ( x , y ) to obtain a structure y (cid:48) that we assume to be invalid. Applying the constraint feature extractor to it gives a negative example (  ( x , y (cid:48) ) ,  1) . We also need to ensure that  ( x , y (cid:48) ) is indeed different from any positive example. Another approach is to perturb the feature vector  ( x , y ) directly, instead of perturbing the structure y . In our experiments in the subsequent sections, we will use both methods to generate negative examples, with detailed descriptions in the supplementary material. Despite their simplicity, we observed performance improvements. Exploring more sophisticated methods for perturbing structures or features (e.g., using techniques explored by Smith and Eisner (2005), or using adversarial learning (Goodfellow et al., 2014)) is a future research direction. To verify whether constraints can be learned as described here, we performed a synthetic experiment where we randomly generate many integer linear program (ILP) instances with hidden shared constraints. The experiments show that constraints can indeed be recovered using only the solutions of the programs. Due to space constraints, details of this synthetic experiment are in the supplementary material. In the remainder of the paper we focus on three real NLP tasks. In the task of entity and relation extraction, we are given a sentence with entity candidates. We seek to determine the type of each candidate, as in the following example (the labels are underlined): [ Organization Google LLC] is headquartered in [ Location Mountain View, California]. We also want to determine directed relations between the entities. In the above example, the relation from Google LLC to Mountain View, California is OrgBasedIn , and the opposite direction is labeled NoRel , indicating there is no relation. This task requires predicting a directed graph and represents a typical structured prediction problemwe cannot make isolated entity and relation predictions. Dataset and baseline : We use the dataset from (Roth and Yih, 2004). It contains 1441 sentences with labeled entities and relations. There are three possible entity types: Person , Location and Organization , and five possible relations: Kill , LiveIn , WorkFor , LocatedAt and OrgBasedIn . Additionally, there is a special entity label NoEnt meaning a text span is not an entity, and a special relation label NoRel indicating that two spans are unrelated. We used 70% of the data for training and the remaining 30% for evaluation. We trained our baseline model using the integer linear program (ILP) formulation with the same set of features as in (Roth and Yih, 2004). The baseline system includes manually designed constraints from the original paper. An example of such a constraint is: if a relation label is WorkFor , the source entity must be labeled Person , and the target entity must be labeled Organization . For reference, the supplementary material lists the complete set of manually designed constraints. We use three kinds of constraint features: (i) source-relation indicator, which looks at a given relation label and the label of its source entity; (ii) relation-target indicator, which looks at a relation label and the label of its target entity; and (iii) relation-relation indicator, which looks at a pair of entities and focuses on the two relation label, one in each direction. The details of the constraint features, negative examples and hyper-parameters are in the supplementary material. We compared the performance of two ILP-based models, both trained in the presence of constraints with a structured SVM. One model was trained with manually designed constraints and the other used learned constraints. These models are compared in Table 1. We manually inspected the learned constraints and discovered that they exactly recover the designed constraints, in the sense that the feasible output space is exactly the same regardless of whether we use designed or learned constraints. As an additional confirmation, we observed that when a model is trained with designed constraints and tested with learned constraints, we get the same model perfor-Performance Metric Designed Learned entity F-1 84 . mance as when tested with designed constraints. Likewise, a model that is trained with learned constraints performs identically when tested with learned and designed constraints. Below, we give one example of a learned constraint, and illustrate how to interpret such a constraint. (The complete list of learned constraints is in the supplementary material.) A learned constraint using the source-relation indicator features is  1 . 98 x 1 + 3 . 53 x 2  1 . 90 x 3 + 0 . 11 x 4 + 2 . 66 x 5  2 . 84 x 6  2 . 84 x 7  2 . 84 x 8 + 2 . 58 x 9 + 0 . 43 x 10 + 0 . 32  0 (9) where x 1 through x 10 are indicators for labels NoEnt , Person , Location , Organization , NoRel , Kill , LiveIn , WorkFor , LocatedAt , and OrgBasedIn , respectively. This constraint disallows a relation labeled as Kill having a source entity labeled as Location , because  1 . 90  2 . 84 + 0 . 32 < 0 . Therefore, the constraint  Location cannot Kill  is captured in (9). In fact, it is straightforward to verify that the inequality in (9) captures many more constraints such as  NoEnt cannot LiveIn ,  Location cannot LiveIn ,  Organization cannot WorkFor , etc. A general method for interpreting learned constraints is a direction of future research. Note that the metric numbers in Table 1 based on learned constraints are lower than those based on designed constraints. Since the feasible space is the same for both kinds of constraints, the performance difference is due to the randomness of the ILP solver picking different solutions with the same objective value. Therefore, the entity and relation experiments in this section demonstrate that our approach can recover the designed constraints and provide a way of interpreting these constraints. In the citation field extraction task, the input is a citation entry. The goal is to identify spans corresponding to fields such as author, title, etc. In the example below, the labels are underlined: [ Author A . M . Turing . ] [ Title Computing machinery and intelligence . ] [ Journal Mind , ] [ Volume 59 , ] [ Pages 433-460 . ] [ Date October , 1950 . ] Chang et al. (2007) showed that hand-crafted constraints specific to this domain can vastly help models to correctly identify citation fields. We show that constraints learned from the training data can improve a trained model without the need for manual effort. Dataset and baseline. We use the dataset from Chang et al. (2007, 2012) whose training, development and test splits have 300, 100 and 100 examples, respectively. We train a first-order Markov model using structured SVM (Tsochantaridis et al., 2004) on the training set with the same raw text features as in the original work. Constraint features. We explore multiple simple constraint features  ( x , y ) in the citation field extraction experiments as shown in Table 2. Detailed descriptions of these features, including how to develop negative examples for each feature, and experiment settings are in the supplementary material. For each constraint feature template, we trained a rectifier network with 10 ReLUs in the hidden layer. We then use Theorem 1 to convert the resulting network to a system of 2 10  1 , or 1023 linear inequalities. We used beam search with beam size 50 to combine the learned inequalities with the original sequence model to predict on the test set. States in the search space correspond to partial assignments to a prefix of the sequence. Each step we predict the label for the next token in the sequence. The pretrained sequence model (i.e., the baseline) ranks search nodes based on transition and emission scores, and the learned inequality prunes the search space accordingly 4 . Table 3 shows the token level accuracies of various methods. The results show that all versions of constrained search outperform the baselines, indicating that the learned constraints are effective in the citation field extraction task. Furthermore, different constraints learned with different features can be combined. We observe that combining different constraint features generally improves accuracy. It is worth pointing out that the label existence and label counts features are global in nature and cannot be directly used to train a sequence model. Even if some constraint features can be used in training the original model, it is still beneficial to learn constraints from them. For example, the bigram label feature is captured in the original first order model, but adding constraints learned from them still improves performance. As another test, we trained a model with POS features, which also contains punctuation information. This model achieves 91.8% accuracy. Adding constraints learned with POS improves the accuracy to 92.6%; adding constraints learned with punctuation features further improves it to 93.8%. We also observed that our method for learning constraints is robust to the choice of the number of hidden ReLUs. For example, for punctuation, learning using 5, 8 and 10 hidden ReLUs results an accuracy of 90 . 1% , 90 . 3% , and 90 . 2% , respectively. We observed similar behavior for other constraint features as well. Since the number of constraints learned is exponential in the number of hidden units, these results shows that learning redundant constraints will not hurt performance. 4 Since the label-existence and label-counts features are global, pruning by learned inequalities is possible only at the last step of search. The other four features admit pruning at each step of the search process. Note that carefully hand-crafted constraints may achieve higher accuracy than the learned ones. Chang et al. (2007) report an accuracy of 92.5% with constraints specifically designed for this domain. In contrast, our method for learning constraints uses general constraint features, and does not rely on domain knowledge. Therefore, our method is suited to tasks where little is known about the underlying domain. Chunking is the task of clustering text into groups of syntactically correlated tokens or phrases. In the instance below, the phrase labels are underlined: [ NP An A.P. Green official] [ VP declined to comment] [ PP on] [ NP the filing] [ O .] We treat the chunking problem as a sequence labeling problem by using the popular IOB tagging scheme. For each phrase label, the first token in the phrase is labeled with a Bprefixed to phrase label while the other tokens are labeled with an Iprefixed to the phrase label. Hence, [ NP An A.P. Green official] is represented as [[ B-NP An] [ I-NP A.P.] [ I-NP Green] [ I-NP official]] This is done for all phrase labels except O. Dataset and Baselines. We use the CoNLL2000 dataset (Tjong Kim Sang and Buchholz, 2000) which contains 8936 training sentences and 2012 test sentences. For our experiments, we consider 8000 sentences out of 8936 training sentences as our training set and the remaining 936 sentences as our development set. Chunking is a well-studied problem and showing performance improvements on full training dataset is difficult. However, we use this task to illustrate the interplay of learned constraints with neural network models, and the impact of learned constraints in the low training data regime. We use the BiLSTM-CRF (Huang et al., 2015) for this sequence tagging task. We use GloVe for word embeddings. We do not use the BERT (De-vlin et al., 2019) family of models since tokens are broken down into sub-words during pre-processing, which introduces modeling and evaluation choices that are orthogonal to our study of label dependencies. As with the citation task, all our constrained models use beam search, and we compare our results to both exact decoding and beam search baselines. We use two kinds of constraint features: (i) n -gram label existence, and (ii) n -gram part of speech. Details of the constraint features and construction of negative samples are given in the supplementary material. We train the rectifier network with 10 hidden units. The beam size of 10 was chosen for our experiments based on preliminary experiments. We report the average results on two different random seeds for learning each constraint. Note that the n -gram label existence is a global constraint while the n -gram POS constraint is a local constraint which checks for validity of label assignments at each token. In essence, the latter constraint reranks the beam at each step by ensuring that states that satisfy the constraint are preferred over states that violate the constraint. Since the n -gram label existence is a global constraint, we check the validity of the tag assignments only at the last token. In the case where none of the states in the beam satisfy the constraint, the original beams are used. The results for this set of experiments are presented in Table 4. We observe that the POS constraint improves the performance of the base-Constraint n Percentage of training data used 1% 5% 10% 25% 50% 100% Label existence 2 81.28 88.30 89.73 91.24 90.40 92.48 3 80.98 88.20 90.58 91.20 92.37 93.12 Part-of-speech 3 86.52 90.74 91.80 92.41 93.07 93.84 4 84.21 90.99 92.17 92.46 93.08 93.93 Search without constraints 81.29 88.27 90.62 91.33 92.51 93.44 Exact decoding 82.11 88.70 90.49 92.57 93.94 94.75 Table 4: Token level accuracies (in percentage) for the chunking baseline and constrained model. line models significantly, outperforming the beam search baseline on all training ratios. More importantly, the results show sizable improvements in accuracy for smaller training ratios (e.g, 4 . 41% and 5 . 23% improvements on exact and search baselines respectively with 1% training data ). When the training ratios get bigger, we expect the models to learn these properties and hence the impact of the constraints decreases. These results (along with the experiments in the previous sections) indicate that our constraints can significantly boost performance in the low data regime. Another way to improve performance in low resource settings is to use better pretrained input representations. When we replaced GloVe embeddings with ELMo, we observed a 87 . 09% accuracy on 0.01 ratio of training data using exact decoding. However, this improvement comes at a cost: the number of parameters increases from 3M (190k trainable) to 94M (561k trainable). In contrast, our method instead introduces a smaller rectifier network with  1000 additional parameters while still producing similar improvements. In other words, using trained constraints is computationally more efficient. We observe that the label existence constraints, however, do not help. We conjecture that this may be due to one of the following three conditions: (i) The label existence constraint might not exist for the task; (ii) The constraint exists but the learner is not able to find it; (iii) The input representations are expressive enough to represent the constraints. Disentangling these three factors is a future research challenge. Structured prediction is an active field in machine learning and has numerous applications, including various kinds of sequence labeling tasks, parsing (e.g., Martins et al., 2009), image segmentation (e.g., Lam et al., 2015), and information extraction (e.g., Anzaroot et al., 2014). The work of Roth and Yih (2004) introduced the idea of using explicitly stated constraints in an integer programming framework. That constraints and knowledge can improve models has been highlighted by several lines of work (e.g., Ganchev et al., 2010; Chang et al., 2012; Hu et al., 2016). The interplay between constraints and representations has been sharply highlighted by recent work on integrating neural networks with structured outputs (e.g., Rocktaschel and Riedel, 2017; Niculae et al., 2018; Manhaeve et al., 2018; Xu et al., 2018; Li and Srikumar, 2019; Li et al., 2019, and others). We expect that constraints learned as described in this work can be integrated into these formalisms, presenting an avenue for future research. While our paper focuses on learning explicit constraints directly from examples, it is also possible to use indirect supervision from these examples to learn a structural classifier (Chang et al., 2010), with an objective function penalizing invalid structures. Related to our goal of learning constraints is rule learning , as studied in various subfields of artificial intelligence. Quinlan (1986) describes the ID3 algorithm, which extracts rules as a decision tree. First order logic rules can be learned from examples using inductive logic programming (Muggle-ton and de Raedt, 1994; Lavrac and Dzeroski, 1994; Page and Srinivasan, 2003). Notable algorithms for inductive logic programming include FOIL (Quin-lan, 1990) and Progol (Muggleton, 1995). Statistical relation learning addresses learning constraints with uncertainty (Friedman et al., 1999; Getoor and Mihalkova, 2001). Markov logic networks (Richardson and Domingos, 2006) combines probabilistic models with first order logic knowledge, whose weighted formulas are soft constraints and the weights can be learned from data. In contrast to these directions, in this paper, we exploit a novel representational result about rectifier networks to learn polytopes that represent constraints with off-the-shelf neural network tools. We presented a systematic way for discovering constraints as linear inequalities for structured prediction problems. The proposed approach is built upon a novel transformation from two layer rectifier networks to linear inequality constraints and does not rely on domain expertise for any specific problem. Instead, it only uses general constraint features as inputs to rectifier networks. Our approach is particularly suited to tasks where designing constraints manually is hard, and/or the number of training examples is small. The learned constraints can be used for structured prediction problems in two ways: (1) combining them with an existing model to improve prediction performance, or (2) incorporating them into the training process to train a better model. We demonstrated the effectiveness of our approach on three NLP tasks, each with different original models. We thank members of the NLP group at the University of Utah, especially Jie Cao, for their valuable insights and suggestions; and reviewers for pointers to related works, corrections, and helpful comments. We also acknowledge the support of NSF Cyberlearning-1822877, SaTC-1801446 and gifts from Google and NVIDIA.
abstain abstain abstain method result result abstain abstain abstain abstain abstain abstain method method abstain abstain result abstain method abstain result abstain abstain abstain abstain abstain abstain objective objective objective result result abstain abstain method result objective objective result other abstain abstain abstain abstain abstain abstain objective method abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain method abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain method abstain method abstain abstain method abstain abstain method abstain abstain abstain abstain method abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain result abstain abstain abstain result abstain result abstain abstain abstain abstain result abstain abstain abstain abstain abstain other other other other method abstain objective other other other other other objective method abstain abstain method abstain objective other other