Learning Constraints for Structured Prediction Using Rectifier Networks (2020)

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 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.

## 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. @xcite 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., @xcite , especially when the number of training examples is limited. designing constraints often requires taskspecific 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 twolayer 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). @xcite 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., @xcite @xcite , the learned constraints will become additional linear inequalities, which can be used directly. alternatively, a structure can be constructed using graph search (e.g., @xcite @xcite @xcite , in which case the learned constraints can filter available actions during search-node expansions. other inference techniques that extend lagrangian relaxation @xcite @xcite 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 @xcite . in the final experiment we consider chunking, i.e., shallow parsing, which is also a sequence labeling task. we train a bilstm-crf model @xcite 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: ## 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 @xmath0, 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: 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 foot_1 : 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: we will show that such learned constraints aid prediction performance. ## learning constraints 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 foot_2 . 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-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 that we assume to be invalid. applying the constraint feature extractor to it gives a negative example (ψ(x, y ), -1). we also need to ensure that ψ(x, y ) 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 @xcite , or using adversarial learning @xcite ) 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. ## entity and relation extraction experiments 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): 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 problem-we cannot make isolated entity and relation predictions. dataset and baseline: we use the dataset from @xcite . 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 @xcite ). 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: ## citation field extraction experiments 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: dataset and baseline. we use the dataset from @xcite whose training, development and test splits have 300, 100 and 100 examples, respectively. we train a first-order markov model using structured svm @xcite 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 ## chunking experiments chunking is the task of clustering text into groups of syntactically correlated tokens or phrases. in the instance below, the phrase labels are underlined: 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 "b-" prefixed to phrase label while the other tokens are labeled with an "i-" prefixed to the phrase label. hence, this is done for all phrase labels except "o". ## related work structured prediction is an active field in machine learning and has numerous applications, including various kinds of sequence labeling tasks, parsing (e.g., @xcite , image segmentation (e.g., @xcite , and information extraction (e.g., @xcite . the work of @xcite 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., @xcite @xcite . the interplay between constraints and representations has been sharply highlighted by recent work on integrating neural networks with structured outputs (e.g., @xcite @xcite @xcite . 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 @xcite , 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. @xcite describes the id3 algorithm, which extracts rules as a decision tree. first order logic rules can be learned from examples using inductive logic programming @xcite @xcite . notable algorithms for inductive logic programming include foil @xcite and progol @xcite . statistical relation learning addresses learning constraints with uncertainty @xcite . markov logic networks @xcite ) 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. ## conclusions 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. ioannis tsochantaridis, thomas hofmann, thorsten joachims, and yasemin altun. 2004. support vector machine learning for interdependent and structured output spaces. proceedings of the twenty-first international conference on machine learning. sam wiseman and alexander m rush. 2016. sequence-to-sequence learning as beam-search optimization. proceedings of the 2016 conference on empirical methods in natural language processing. jingyi xu, zilu zhang, tal friedman, yitao liang, and guy van den broeck. 2018. a semantic loss function for deep learning with symbolic knowledge. in proceedings of the 35th international conference on machine learning.