Syntactic Search by Example (2020)

Abstract: We present a system that allows a user to search a large linguistically annotated corpus using syntactic patterns over dependency graphs. In contrast to previous attempts to this effect, we introduce a light-weight query language that does not require the user to know the details of the underlying syntactic representations, and instead to query the corpus by providing an example sentence coupled with simple markup. Search is performed at an interactive speed due to efficient linguistic graph-indexing and retrieval engine. This allows for rapid exploration, development and refinement of syntax-based queries. We demonstrate the system using queries over two corpora: the English wikipedia, and a collection of English pubmed abstracts. A demo of the wikipedia system is available at https://allenai.github.io/spike/ .

## introduction the introduction of neural-network based models into nlp brought with it a substantial increase in syntactic parsing accuracy. we can now produce accurate syntactically annotated corpora at scale. however, the produced representations themselves remain opaque to most users, and require substantial linguistic expertise to use. patterns over syntactic dependency graphs 1 can be very effective for interacting with linguistically-annotated corpora, either for linguistic retrieval or for information and relation extraction (fader et al., 2011; akbik et al., 2014; valenzuela-escárcega et al., 2015, 1 in this paper, we very loosely use the term "syntactic" to refer to a linguistically motivated graph-based annotation over a piece of text, where the graph is directed and there is a path between any two nodes. while this usually implies syntactic dependency trees or graphs (and indeed, our system currently indexes enhanced english universal dependency graphs @xcite ) the system can work also with more semantic annotation schemes e.g, @xcite , given the availability of an accurate enough parser for them. @xcite ). however, their use in mainstream nlp as represented in acl and affiliated venues remain limited. we argue that this is due to the high barrier of entry associated with the application of such patterns. our aim is to lower this barrier and allow also linguistically-naïve users to effectively experiment with and develop syntactic patterns. our proposal rests on two components: figure 1 (next page) shows the interface of our web-based system. the user issued the query: the query specifies a sentence (paul was a founder of microsoft) and three named captures: founder, t and entity. the founder and entity captures should have the same entity-type as the corresponding sentence words (person for paul and organization for microsoft, indicated by @xcite ), and the t capture should have the same word form as the one in the sentence (founder) (indicated by @xcite ). the syntactic relation between the captures should be the same as the one in the sentence, and the founder and entity captures should be expanded (indicated by ). the query is translated into a graph-based query, which is shown below the query, each graph-node associated with the query word that triggered it. the system also returned a list of matched sentences. the matched tokens for each capture group (founder, t and entity) are highlighted. the user can then issue another query, browse the results, or download all the results as a tab-separated file. 2 existing syntactic-query languages while several rich query languages over linguistic tree and graph structure exist, they require a substantial amount of expertise to use. 2 the user needs to be familiar not only with the syntax of the query language itself, but to also be intimately familiar with the specific syntactic scheme used in the underlying linguistic annotations. for example, in odin @xcite , a dedicated language for pattern-based information extraction, the same rule as above is expressed as: the spacy nlp toolkit 3 also includes pattern matcher over dependency trees,using json based syntax: the dep search system foot_1 from turku university @xcite is designed to provide a rich and expressive syntactic search over large parsebanks. they use a lightweight syntax and support working against pre-indexed data, though they do not support named captures of specific nodes. ## syntactic search by example we propose a substantially simplified language, that has the minimal syntax and that does not require the user to know the underlying syntactic schema upfront (though it does not completely hide it from the user, allowing for exposure over time, and allowing control for expert users who understand the underlying syntactic annotation scheme). the query language is designed to be linguistically expressive, simple to use and amenable to efficient indexing and query. the simplicity and indexing requirements do come at a cost, though: we purposefully do not support some of the features available in existing languages. we expect these features to correlate with expertise. 6 at the same 6 example of a query feature we do not support is quantifi-time, we also seamlessly support expressing arbitrary sub-graphs, a task which is either challenging or impossible with many of the other systems. the language is based on the following principles: the required syntactic knowledge from the user, both in terms of the syntax of the query language itself and in terms of the underlying linguistic formalism, remains minimal. ## graph query formalism the language is structured around between-token relations and within-token constraints, where tokens can be captured. formally, our query @xmath0, e) is a labeled directed graph, where each node v @xmath1, and a labeled edge @xmath2, v j , ℓ) ∈ e between the nodes corresponds to a between-token syntactic constraint. this query graph is then matched against parsed target sentences, looking for a correspondence between query nodes and target-sentence nodes that adhere to the token and edge constraints. for example, the following graph specifies three tokens, where the first and second are connected via an 'xcomp' relation, and the second and third via a 'dobj' relation. the first token is unconstrained, while the second token must have the pos-tag of vb, and the third token must be the word home. sentences whose syntactic graph has a subgraph that aligns to the query graph and adheres to the constraints will be considered as matches. example of such matching sentences are: between-token constraints correspond to labeled directed edges in the sentence's syntactic graph. within-token constraints correspond to properties of individual sentence tokens. 8 for each property we specify a list of possible values (a disjunction) and if lists for several properties are provided, we require all of them to hold (a conjunction). for example, in the constraint @xmath3, and the lemma buy. the list of possible values for a property can be specified as a pipe-separated list (@xmath4. ## example-based user-friendly query language the graph language described above is expressive enough to support many interesting queries, but it is also very tedious to specify query graphs g, especially for non-expert users. we propose a simple syntax that allows to easily specify a graph query g (constrained nodes connected by labeled edges) using a textual query q that takes the form of an example sentence and lightweight markup. let @xmath5, ..., w n be a proper english sentence. let d be its dependency graph, with nodes w i and labeled edges (w i , w j , ℓ). a corresponding textual query q takes the form @xmath6, ..., q n , where each q i is either a word q @xmath7, or a marked word q @xmath8. a marking of a word takes the form: :word (unnamed capture) name:word (named capture) or name:[constraints]word , :[constraints]word . consider the query: john w:wanted to v:[@xmath9:[@xmath10. the marked words are: let m be the set of marked query words, and m + be a minimal connected subgraph of d that includes all the words in m. when translating q to g, each marked word w @xmath11. the additional words w @xmath12, unnamed nodes v q j . we add a query graph edge (v q i , v q j , ℓ) for each pair in v for which (w i , w j , ℓ) ∈ d. ## implementation details the indexing is handled by lucene. 10 we currently use odinson @xcite , 11 an open-source lucene-based query engine developed at lum.ai, as a successor of odin @xcite , that allows to index syntactic graphs and issue efficient path queries on them. we translate our queries into an odinson path query that corresponds to a longest path in our query graph. we then iterate over the returned odinson matches and verify the constraints that were not on the path. conceptually, the odinson system works by first using lucene's reverse-index for retrieving sentences for which there is a token matching each of the specified token-constraints, and then verifying the syntactic between-token constraints. to improve the lucene-query selectivity, tokens are indexed with incoming and outgoing syntactic edge label information, which is incorporated as additional token-constraints to the lucene engine. the system easily supports millions of sentences, returning results at interactive speeds. ## conclusions we introduce a simple query language that allows to pose complex syntax-based queries, and obtain results in an interactive speed. a search interface over wikipedia sentences is available at https://allenai.github.io/ spike/ . we intend to release the code as open source, as well as providing hosted open access to a pubmed-based corpus.