Neural-Guided Program Synthesis of Information Extraction Rules Using Self-Supervision (2022)

Abstract: We propose a neural-based approach for rule synthesis designed to help bridge the gap between the interpretability, precision and maintainability exhibited by rule-based information extraction systems with the scalability and convenience of statistical information extraction systems. This is achieved by avoiding placing the burden of learning another specialized language on domain experts and instead asking them to provide a small set of examples in the form of highlighted spans of text. We introduce a transformer-based architecture that drives a rule synthesis system that leverages a self-supervised approach for pre-training a large-scale language model complemented by an analysis of different loss functions and aggregation mechanisms for variable length sequences of user-annotated spans of text. The results are encouraging and point to different desirable properties, such as speed and quality, depending on the choice of loss and aggregation method.

## introduction rule-based information extraction is interpretable, maintainable, and highly precise, but typically requires both domain expertise and deep knowledge of an esoteric rule language. the language barrier presents a major impediment to adoption for subject matter experts who are otherwise comfortable with providing examples of their information need in the form of a handful of highlighted spans of text. synthesizing information extraction rules from such examples has the potential to bridge this divide and empower subject matter experts, but how can we learn to synthesize such programs for any domain? we propose a self-supervised approach for pre-training a large-scale language model for synthesizing information extraction rules using randomly generated rules (programs) paired with matched spans in context (program specifications). the contributions of this work are: ## related work generating computer programs automatically has been a longstanding dream within the field of artificial intelligence. the goal of program synthesis is to generate programs from a high-level specification foot_0 @xcite . existing approaches to program synthesis fall into one of two broad categories: search-based methods (e.g., enumerative search, stochastic search @xcite and constraint satisfaction @xcite . in this work, we focus on search-based program synthesis @xcite , specifically a neural-guided enumerative search. neural approaches have come to dominate search-based program synthesis @xcite @xcite . similar to @xcite , our approach learns a distribution over programs to guide every step of the search. unlike @xcite , however, we score only the transitions allowed by the dsl grammar and encode the specification in a manner which reflects that our programs are meant to match natural language. rule-based information extraction systems are more interpretable than its statistical counterparts. rule languages with high expressiveness allow to model complex surface and syntactic patterns @xcite . these systems are suitable to create highly specialized domainspecific information extraction tools without the need of large and expensive annotated datasets @xcite . unfortunately, mastering rule-based systems often implies a steep learning curve and a significant time investment by domain experts. in this work we focus on the intersection of both pattern-based and neural-based techniques by training a statistical model to synthesize rule patterns by exposing it to user-provided examples. ## odinson information extraction system in this work, we are interested in synthesizing information extraction rules expressed in a domain specific language (dsl) first described in @xcite . this language supports extraction rules based on token constraints (e.g., parts-of-speech and lemmas) as well as syntactic patterns. however, only surface rules are targeted in this work, leaving support for syntactic rules for future work. we apply the rules expressed in the dsl using the odinson information extraction framework @xcite , which supports the efficient application of the extraction rules over a large corpus through the use of a custom lucene foot_1 index. like lucene, odinson can store an index on-disk or in-memory, and we take advantage of both indexes types during this work. an on-disk index is used to store a large corpus used during the data generation process described in section 5, and an in-memory index is created onthe-fly during the enumerative search to store the sentences that form part of the user specification, indicated in algorithm 1 as the make_index() function. ## enumerative search the enumerative search procedure, outlined in algorithm 1, takes as input a user specification, (referred to as specification for brevity) comprised of a collection of sentences and a set of spans representing the desired extractions; a rule scorer component which drives the behavior of the search; and a performance threshold that functions as a stopping criteria for the search. the specification encodes the user's intent and is the main source of signal at the time of scoring any given partial rule encountered during the search. rules are composed of syntactic elements defined by the dsl. one noteworthy element is the placeholder, represented by the symbol □, which is introduced to represent an underspecified portion of the rule that must be expanded by following the grammar of the dsl. a rule is considered valid (grammatical) if it has no placeholders, otherwise it is a partial rule containing one or more placeholder. partial rules are subject to further expansions of the form allowed by the dsl grammar. to conduct an enumerative search, we create an in-memory index containing the phrases included in the rule's specification and initialize a priority queue with a partial rule consisting of a single placeholder (i.e., the root of the search tree). at each iteration, we retrieve the top-ranked partial rule in the priority queue and check its validity. if it is a valid rule, we query the index to verify if the rule matches the spans highlighted in the specification, and compute a score to measure the rule's performance (e.g., an f1 score over the spans matched in the specification). if the score is above some threshold foot_2 , the candidate rule is returned. if the rule still contains placeholders, we expand the left-most placeholder according to our dsl grammar and use the rule scorer to produce a score for each of the expanded rules with respect to the user-provided specification. each expanded rule is placed into the priority queue according to its score. the process repeats until a complete rule is found that meets or exceeds the specified performance threshold. our enumerative search process implements the branch-and-bound algorithm @xcite using a priority queue. an ideal scorer would guide the expansions directly to a correct rule approximating a depth-first search, but the priority queue allows the search to backtrack to the most promising candidate if necessary. it is worth noting that the rule scorer component of the algorithm can be any function that takes as input a partial rule and the specification, and returns a score denoting the rule's priority for further expansion. in the remaining sections of this work, we describe neural architectures for training rule scoring models ( §7.1) with supervised training data ( §5). algorithm 1 enumerative search. require: spec ▷ user specification require: scorer ▷ partial rule scorer require: threshold ▷ score threshold (sentences, gold_spans) ← spec index ← make_index(sentences) queue ← priority_queue() push(queue, □, ∞) while queue ̸ = ∅ do candidate ← pop(queue) if is_valid(candidate) then results ← query(index, candidate) score ← eval(results, gold_spans) if @xmath0, spec) push(queue, child, score) end for end if end while 5 data generation to learn to synthesize information extraction rules in a supervised fashion, we first need (spec, rule) pairs. conceptually, a spec (i.e., matches in context) is easily obtained by querying an index, as long as the rule is available. our data generation pipeline can be broken down into 4 steps, as highlighted in algorithm 2. ## pre-training we take inspiration from the question-answering community @xcite and train a model to predict the span matched by a given rule in a given sentence. concretely, we use a dataset generated according to the description in section 5 and interpret the concatenation of the rule (rule) with the sentence (sent) as the question. then, the self-supervised task becomes to predict the start and the end of the span, as in classical span-based question answering. this pre-training objective has two aims. first, we expose the backbone model (a transformer) to the in-domain vocabulary in which the words and symbols of the dsl are much more frequent than they are in the wikipedia or book corpora @xcite . our second aim is to expose the model to an unfamiliar task closely related to our ultimate goal: span prediction (i.e., the match for an information extraction rule against some sentence). by learning to predict spans, the model is primed to learn to score candidate rules generated through enumerative search. ## rule scorer architecture the heart of the enumerative search process lies at the rule scoring function. the rule scoring function assigns a priority value to each of the rule's expansions encountered throughout an enumerative search. since priority scores control the exploration behavior during the search, it is critical to have an optimized scoring model that can discriminate between promising or futile rule expansions. we opt to follow a data-driven approach to train a rule-scoring artificial neural network. figure 1 depicts the architecture of scoring network. the network takes as input a rule: either partially or totally expanded, and the specification; as output, it produces a score used to prioritize a candidate rule in the search process. we used the rule-specs described in §5 to build a dataset of transitions for rule scoring. we split the rules into training, development and testing with 1.5 million, 6,000 and 500 items, respectively. for the training and development subsets, we used the odinson's language grammar to enumerate all the transitions necessary to derive each of the rules, and collected the transitions along the path from the root placeholder to the ground truth rule that matches the specification. to obtain negative examples, at any given step we collected the syntactically valid expansions that don't lead to the ground truth rule. figure 2 shows an example of the expansion steps to generate a simple rule composes of two token constrains in dsl. each row shows a transition, considered a positive training example while the rest of the other syntactically valid transitions (not shown in the figure) are used as negative examples. following this approach, the dataset contains 9,731,804 and 748,836 transitions in the training and development subsets, respectively. the ratio of positive to negative transitions is 1 to 3.21. ## experiments we tested the rule scoring architecture on several rule synthesis processes. for each model, we control the loss function ( §8.1) used for training and transformer encoder & pooler embedding aggregation layer scoring head aggregated rule-spec embedding rule-spec score rule-spec pairs tokens contextualized rule-spec pairs embeddings (1) (2) (3) figure 1: rule scoring architecture. step 1 takes as input the pair-wise concatenation of a) the partial rule and b) the annotated phrases in the provided specification. the input is fed through a foundation transformer model which outputs the [cls] embedding for each rule-spec pair. step 2 aggregates the matrix of [cls] embeddings, either through average pooling or an attention layer, and outputs a fixed-size rule-spec vector. step 3 linearly maps the rule-spec vector into a real-valued scalar score. the output score will be used as the priority value during the enumerative search process. the method for aggregating the specification ( §7.1). all models are fine-tuned on top of a bert checkpoint pre-trained for rule span prediction ( §6). each trained model was applied on a held-out test set of 500 rule synthesis problems with their respective specification. each synthesis process was carried out by an enumerative search with a limit of 500 steps. ## future work the results presented in this work are promising and open the door for further research in several directions that will help to better understand the properties of the rule scoring architectures. in its current state, our approach has at least avenues to future work.