Learning Open Domain Multi-hop Search Using Reinforcement Learning (2022)

Abstract: We propose a method to teach an automated agent to learn how to search for multi-hop paths of relations between entities in an open domain. The method learns a policy for directing existing information retrieval and machine reading resources to focus on relevant regions of a corpus. The approach formulates the learning problem as a Markov decision process with a state representation that encodes the dynamics of the search process and a reward structure that minimizes the number of documents that must be processed while still finding multi-hop paths. We implement the method in an actor-critic reinforcement learning algorithm and evaluate it on a dataset of search problems derived from a subset of English Wikipedia. The algorithm finds a family of policies that succeeds in extracting the desired information while processing fewer documents compared to several baseline heuristic algorithms.

## introduction the sheer size of public corpora such as wikipedia foot_0 or large paper repositories like arxiv foot_1 and pubmed central foot_2 poses an enormous challenge to automating effective search for relevant information. this problem is compounded when the underlying information needs require multi-hop connections, e.g., searching for biological mechanisms that connect two proteins @xcite or searching for explanations that require complex reasoning by understanding text supported by different documents in qa systems @xcite . in a naive approach, an automated information extraction agent could process all the documents in a corpus, searching for the indirect connections that satisfy a multi-hop information need. however, this quickly becomes prohibitively expensive as the corpus size increases. further, the documents may also be behind a paywall, adding an additional economic cost to accessing information. thus, the naive exhaustive reading approach is simply not feasible for most large corpora scenarios. instead, we need to incorporate the kind of iterative focused reading that humans are capable of. when people search for information, they use background knowledge, based in part on what they have just read, to narrow down the search space while selectively committing time and other resources to carefully reading documents that appear relevant. this process may be repeated multiple times until the information need is satisfied. we propose a methodology that uses reinforcement learning (rl) to teach an automated agent how to direct a search process, using existing information retrieval and machine learning components selectively, focusing on the relevant parts of the corpus in order to minimize the expenditure of computational resources and access costs. the contributions of our work are the following: ## related work modern machine reading technology enables the extraction of structured information from natural language data. named-entity recognition @xcite systems detect and label specific classes of concepts from text, both in the general domain @xcite and for specific domains @xcite . relation extraction systems extract interactions between different concepts in open-domain @xcite @xcite and domain-specific scenarios @xcite @xcite . reinforcement learning has been successfully deployed for a variety of natural language processing (nlp) tasks. @xcite proposed a policy-gradient method to resolve the correct coreference chains for the task of coreference resolution. @xcite used reinforcement learning to train an end-to-end task-completion dialogue system. for the task of machine translation, @xcite formulated the task as a dual-learning game in which two agents teach each other without the need of human labelers using policy-gradient algorithms. reinforcement learning has also been specifically applied to improving search and machine reading. in learning how to search, @xcite proposed a methodology for the task of slot-filling based on temporal-difference q-learning that uses domain specific state representation features to select actions in a resourceconstrained scenario. @xcite successfully applied rl to finding relevant biochemical interactions in a large corpus by focusing the allocation of machine reading resources towards the most promising documents. similarly, @xcite explore the use of deep neural networks and deep rl to simulate the search behavior of a researcher, also in the biomedical domain. ## learning to search we propose a methodology to teach an automated agent how to selectively retrieve and read documents in an iterative fashion in order to efficiently find multi-hop connections between a pair of con-cepts (or entities). each search step focuses on a restricted set of documents that are hypothesized to be more relevant for finding a connection between the two target concepts. the focus set is retrieved and processed and if a path connecting the concepts is found, the search terminates. otherwise, a new set of focus documents is identified based on what has been learned so far during the search. the process is repeated iteratively until the desired information is found or a number of iterations is exceeded. our method is general as it does not directly rely on any supervised domain specific semantics. during the search, the agent iteratively constructs a knowledge graph (kg) that represents the relations between concepts found so far through machine reading. in each iteration, the algorithm formulates a document retrieval query based on the current state of the knowledge graph, which is then executed by an information retrieval (ir) component. the ir component contains data structures to query the corpus, for example using an inverted index. the construction of these data structures usually only requires shallow processing, such as tokenization and stemming, and not a full-fledged nlp pipeline. any documents returned from executing the query are processed by an information extraction (ie) component that performs named entity recognition and relation extraction. the kg is expanded by adding newly identified entities as new nodes and previously unseen relations as new edges. the overall goal of the method is to focus on the documents that appear to be most likely to contain a path between the target concepts, all while processing as few documents as possible. @xcite formalized this iterative search process as a family of focused reading algorithms, shown in algorithm 1: the algorithm starts with the kg representing only the endpoints of the search: the named entities e1 and e2. the algorithm then initiates the search loop. the first step in the loop analyzes the knowledge graph and generates an information retrieval query, q. as we will describe shortly, the current state of the kg is used to parameterize and constrain the scope of q, focusing it on returning a limited subset of documents that are hypothesized to be most relevant. after retrieval, the documents are processed by the ie component. any entities not previously found in the kg are placed in the new entity set v , and similarly any new relations linking entities are placed in the new relation set, e. v and e are incorporated into the kg and the algorithm then searches the updated kg for any new possible paths connecting e1 and e2. if a path exists, it is returned as a candidate explanation of how e1 and e2 are related. otherwise, if no such path exists, the query formulation process (using the updated kg) followed by ir and ie, is repeated until a path is found or the process times out. this framework can answer multi-hop search queries for which the relationships along a connecting path come from different documents. for example, this process may discover that valley of mexico is connected to the aztecs because the aztecs were a pre-columbian civilization (found in one document), which, in turn, was located in the valley of mexico (found in another document). in the following subsections, we formulate focused reading as a markov decision process (mdp). ## evaluation and discussion to evaluate the focused reading learning method, we introduce a novel dataset derived from the english version of wikipedia. our dataset consist of a set of 369 multi-hop search problems, where a search problem is consists of a pair of entities to be connected by a path of relations, potentially connecting to other entities along the path. the foundation of the dataset is a subset of 6,880 wikipedia articles from the wikihop @xcite corpus. we used wikification @xcite to extract named entities from these documents and normalize them to the title of a corresponding wikipedia article. wikification does not perform relation extraction, so we lack gold-standard relations. to overcome this limitation, in this paper we induce a relation between entities that co-occur within a window of three sentences. every relation extracted this way can be traced back to at least one document in the corpus. we create a gold-standard knowledge graph using the induced entities and relations, and we sample pairs of entities connected by paths to create search problems for the dataset. we train an lda model foot_4 and constructed an information retrieval inverted index over the collection of documents. 7 we used the advantage actor critic algorithm @xcite (a2c) to implement our reinforcement learning focused reading method. 8 a2c is an actor-critic method and we use a single neural network architecture to model the action policy (actor) as well as the state value function (critic). we use a single neural network architecture to implement the a2c actor-critic model. the architecture consists of a fully-connected feed-forward neural network with four layers and two output heads. the first output head represents the approximation of the action policy (the actor) as a soft-max activation layer whose size is the cardinality of the action space. this approximates the probability distribution of the actions given the current state. the second head approximates the state value, as a single neuron with a linear activation. the state value estimates the expected long-term reward of using the estimated action distribution of the first head in the current state. altogether the model consists of approximately 3.79 million parameters. we performed an ablation analysis on the development dataset to find the best configuration of features. the development dataset contains five hundred search problems. the set of endpoints of the search problems does not overlap with those of the training and validation datasets. this is enforced to avoid any accidental leak of training information. processed docs provides the number of documents processed in all the search problems of the test set. docs per success is a summary the other two columns: it contains the number of documents processed divided by the number of successes. this ratio is an aggregate statistic useful for comparing the performance between different policies. we report the sample averages and their standard deviations in parentheses. for example, the success rate column displays the average and standard deviation of five success rate calculations over five hundred search problems. the processed documents column displays the average and standard deviation of the cumulative count of documents processed in the search problems, and so forth. we implement three baseline policies that were not derived using rl: for consistency, each baseline was also evaluated with five different random seeds over the testing set. the top part of to test for statistical significance, we performed a non-parametric bootstrap resampling test with ten thousand samples for the the following metrics: success rate, processed documents and documents per success. for each metric, we calculated the difference between the result of the cascade baseline and the result of each of the reinforcement learning (rl) policies. if @xmath0.05 of the difference being in favor of the reinforcement learning policy, the quantity is starred in the table. in terms of success rate, most of the reinforcement learning models perform better than the cascade baseline. the notable exceptions are two feature configurations that do not use endpoint embeddings. these configurations are the one that