Discovering Knowledge Graph Schema from Short Natural Language Text via Dialog (2020)

Abstract: We study the problem of schema discovery for knowledge graphs. We propose a solution where an agent engages in multi-turn dialog with an expert for this purpose. Each mini-dialog focuses on a short natural language statement, and looks to elicit the expert’s desired schema-based interpretation of that statement, taking into account possible augmentations to the schema. The overall schema evolves by performing dialog over a collection of such statements. We take into account the probability that the expert does not respond to a query, and model this probability as a function of the complexity of the query. For such mini-dialogs with response uncertainty, we propose a dialog strategy that looks to elicit the schema over as short a dialog as possible. By combining the notion of uncertainty sampling from active learning with generalized binary search, the strategy asks the query with the highest expected reduction of entropy. We show that this significantly reduces dialog complexity while engaging the expert in meaningful dialog.

## introduction increasingly, within and outside of enterprises, knowledge is represented and stored in knowledge graphs @xcite . many such knowledge graphs have a schema @xcite , so that entities and relationships are labeled with discrete categories. there has been a lot of research on annotating natural language text using the provided schema of such knowledge graphs @xcite . a task that is often overlooked in this context is that of designing and updating the knowledge graph schema itself. it is common for such knowledge graphs schemas to be incomplete. the schema is typically designed by a human expert ahead of time based assumptions about the data to be accommodated in the future. thus schema design is not a one-shot affair, since the expert becomes better aware of the need once the system is deployed. updating the schema based on new needs forms an integral part of maintaining a knowledge graph. in this paper, we propose dialog with an expert as a means to construct and update such a schema using as evidence a collection of short natural language statements from the domain. the role of dialog has been explored in the context of updating schema-free knowledge @xcite . our purpose is to recover the expert's desired schema for such knowledge. the proposed overall dialog consists of a sequence of many mini dialogs. each mini dialog focuses on a single short natural language statement, and recovers the expert's desired schema-based annotation of the statement, taking into account possible enhancements to the current schema. the overall schema is augmented iteratively by performing dialog over the collection of statements. the dialog ends when the agent is able to confidently annotate all statements with its current schema. as an illustration, consider the following mini dialog between a human (h) and an agent (a). a: i understand the statement as researcher tom mitchell leading project focusing on topic never ending learning. the agent had existing knowledge of certain entity and relationship types, but needed to introduce the new entity type project and the relation types leads @xcite and focuseson(project topic) to the schema. it was then able to associate a short path from the schema (research to project to topic) with the statement. it elicited this knowledge from the expert using a short dialog. queries are sequentially chosen based on their 'utility' -the reduction in uncertainty over path probabilities. this has high-level similarities with active learning for structured prediction @xcite . this considers eliciting the entire structured label for an instance from the expert in one shot. in reality, experts do not always answer queries. if the query is too 'complex' (e.g. "which of the following 100 paths is the right schema path for this statement?"), the expert is very likely to not answer at all. on the other hand, a simpler query (e.g. "is this statement about a project?") is more likely to get a response. therefore, we consider a mini dialog for each instance consisting of a sequence of simple queries, based on their utility. each query has an associated probability of response from the user, thereby affecting its utility. the response probability depends on the complexity of the query. active learning literature has studied no-response probability for complex queries @xcite . however, the notion of complexity in this work relates to closeness to the decision boundary. in the structured prediction setting, we hypothesize that the complexity relates more to the 'size' of the query. in the presence of such response uncertainty, given a collection of statements and an initial knowledge graph, our goal is to design a dialog strategy that picks the statements in some sequence and elicits their desired schema paths from the expert with the shortest overall dialog length. we propose a dialog strategy that combines the notion of uncertainty sampling from the active learning literature with that of generalized binary search. we iteratively pick the best statement to query, and then the query for the statement by considering expected entropy reduction, accounting for no-response probability. we propose two different types of categorical queries, any-of queries, where the expert confirms one part of a bi-partition of the current candidate set, and which-of queries, where the expert is asked to pick a specific candidate from a set. we model response probability as a parametric function of query complexity, which we represent as the sum of the lengths of the paths included in the query. we show that the standard active learning strategy falls out as a special case of our strategy when there is no response uncertainty. the no-response parameters are learnt by the agent as the dialog progresses. we evaluate our strategy using a collection of short statements from the web-page of a large organization. we show that our proposed strategy results in meaningful and dialog with an expert that yields the expert's desired schema for the organization via significantly lower dialog complexity compared to multiple baseline strategies. there is existing work on active learning for structured output spaces @xcite @xcite . of these, sequence annotation @xcite also considers paths, but not on schema graphs. more importantly, these pose a single query to the expert for the structured label of an instance. in contrast, we propose to break this into a series of simple queries, in view of answer uncertainty, which is not considered in this line of work. active learning with imperfect labelers @xcite considers no-response and query complexity. however, since this is not for structured labels, query complexity does not account for structural complexity. a typed knowledge graph (or kg in short) @xmath0, i) has a schema g and instances i of the entity and relation types in g. for example, our research kg may contain entity instances isresearcher(t. mitchell), isproject(nell), ispaper(coupled semisupervised learning), and relation instance affiliat-edwith(t. mitchell, nell), etc. we assume that every entity type has a single name attribute. consider an example statement s i : "a scientist wrote the paper 'coupled semi-supervised learning'". we restrict ourselves to short statements that refer to at most two entities and two entity types, which we call e i1 , e i2 and t i1 , t i2 respectively. in s i , t @xmath1, and 'scientist' is a mention of t i1 , which we denote as m(t i1 ). t @xmath2, and its mention m(t i2 ) is 'paper'. e i2 is a specific paper instance and its mention m(e i2 ) is 'coupled semi-supervised learning'. the first entity e i1 is not explicitly mentioned in this statement. beyond mentioning the entities and their types, s i also refers to a connection between them in the schema via the defined binary relations. we call this the statement schema path p i , which is a subgraph of the schema. here, p i is researcher-authorof-paper. typically, given a statement, the above variables other than mentions are latent or unobserved. we will assume the availability of a probability model for the posterior distribution of these variables an important consideration for such a model in the context of schema discovery is its ability to consider entity types (also entities) not contained in the current kg schema (also instances). consider the statement s 1 from the introduction: "tom mitchell works on never ending learning". the true schema path p 1 in this case looks as follows: researcher-leads-project-focuseson-topic. this includes the entity type project and relation types focuseson(project, key-word) and leads(researcher, project) which are not contained in the observed schema g; i.e., p 1 ⊂ g. in order to correctly interpret s 1 , its schema path p 1 , and therefore the schema, needs to be enhanced to include an additional entity type and two new relation types. in other words, the posterior distribution should be capable of assigning non-zero probability to previously unseen yet likely entity types and schema paths. given a set of statements s and an initial schema g 0 , our goal is an enhancement g * of g 0 such that the schema paths p i for all statements s @xmath3. along with g * , the schema paths for the individual statements are unknown as well, and need to be identified. dialog for schema path discovery: the problem above is difficult to solve in practice, even without considering schema enhancements, and requires very large volumes of training data. to aid this generally intractable search, we propose a dialog with an expert. our task is to design a dialog strategy that reduces the uncertainty (entropy) about the schema path p i for each s @xmath4. the length of the dialog is the aggregated complexity of all the queries posed to the expert during the dialog. our strategy uses one mini dialog for each question statement in s. the j th mini dialog considers some statement s @xmath5, and poses a sequence of queries to identify the true schema path p i for s i . each mini dialog consists of a sequence of simple mini-queries, denoted as q(s i ). specifically, the agent poses two kinds of close-ended mini-queries to the expert. the first is a binary (yes/no) query of the form "is the statement about any of p 1 or p 2 or ... p k ?", where each p 1 is a possible path in g * . the second is an n-ary query of the form "this statement is about which of p 1 or p 2 or ... p k ?" note that the response for this query can be 'none'. the paths in the queries can include new entity and relation types that are not in the current schema graph. note that such categorical queries can only recover the structure of p i . an additional type of query therefore asks for the names of any new entity or relation types in p i . any such query q(s i ) has a utility. intuitively, utility measures potential reduction in entropy of the posterior distribution over possible responses to the query. there reduction is 0 if the query gets no response from the expert. the response probability depends on the complexity of the query. our goal is design a strategy that can evaluate the utilities for the different query types taking into account noresponse probability, and then select the mini-query with the best utility at each step. ## candidate schema paths in this section, we discuss a probabilistic model for schema paths for a statement, and then an algorithm for finding the best schema path given a statement along with their probabilities. this is not the focus of our work, and ideally we would prefer to use a state of the art method for this task. there has been recent progress on joint linking of mentions in short statements to entities and relationships in a knowledge graph @xcite . this is similar to our task, but does not consider the possibility of extending the current schema with new entity and relationship types. there is also work on inferring paths in schema-based knowledge graph given a query node @xcite ) using random walks. we extend this line of work for statements with mentions while also considering new schema nodes in the random walk. in this section, we first explain our probabilistic model, and then the candidate path sampling algorithm. ## dialog for schema path discovery at this point, for each statement s i , we have n candidate schema paths p i1 , p i2 , . . . , and their probabilities. our task now is to minimize the entropy of schema path predictions over all statements with a dialog of length l, knowing that the expert may not answer all queries. let us recall the standard active learning paradigm: (a) select the next statement for expert labeling, (b) acquire expert's preferred label for selected statement, (c) retrain model with newly labeled statement in training data, and continue until budget is exhausted. for selecting the next statement, the principle of uncertainty sampling is followed, with entropy as the notion of uncertainty @xcite . in step (b), the expert provides the preferred label in one shot, even for structured output spaces @xcite . we call this interaction format the active learning dialog format and the overall strategy the entropy-based active learning strategy (e-al). our major departure from this strategy is in step (b). we may present the expert with candidate schema paths and ask the expert to pick one. we call this a which-of query. when the list is long, this is unlikely to receive a response. in addition, we can elicit the schema path with a mini-dialog, which is a sequence of simple mini-queries. the basic idea is to iteratively prune the set of remaining candidates by splitting into two parts at each step, showing any one part to the expert and querying if it contains his preference. we call this an any-of query. within a mini dialog (step (b)), our strategy repeatedly chooses the best (which-of or any-of) mini-query until the complete schema path is obtained from the expert. we call this the mixed any-which mini dialog format. we can see that this is more general than the active learning dialog format. lemma 1. the mixed any-which mini dialog format reduces to the active learning dialog format when each mini dialog has a single which-of query. for completion, we point out that if the elicited schema path in a mini dialog includes new entities and relationships, their names are also elicited from the expert via name queries. an example name query may be "what is the name of the new entity related to both researchers and topics?". generalized binary search and entropy reduction: at any step within a mini dialog, the strategy needs to choose between the which-of query and many possible any-of queries, one for each bi-partition of the remaining candidate set. to evaluate different queries, we define the utility u(q) of a query q borrowing from entropy-based uncertainty sampling and generalized binary search @xcite . let p k i be the set of remaining candidates at step k of the mini dialog for statement s i , and e k i denote the entropy of the candidate distribution. a bipartition π k i splits p k i into p k i1 and p k i2 such that the entropies of the two splits are e k i1 and e k i2 . depending on the expert's response to the any-of query with this bi-partition, either p k i1 or p k i2 becomes the next candidate set. so the residual entropy after this query is either (e or (e k i -e k i2 ). we define the utility u(q) of this bi-partition (any-of) query q as the average reduction of entropy after the query, which is instead of all partitions, we order the candidate schema paths by probability, and consider each position in the order as a possible splitting point. the alternative to partitioning is to present the entire set of candidates p k i to the expert and pose a which-of query. if the expert responds to this query, this mini dialog concludes and the entropy becomes 0, so that the utility (reduction in entropy) of the which-of query is e k i . but this query is 'complex' and may not be answered by the expert. response uncertainty and expected utility: utility as defined above is not sufficient when queries are not answered with certainty. we define the complexity c(q) of a query q as the sum of lengths of the paths specified in the query. for example, the query "is this about researchers-relatedto-projects-relatedto-topics?" has complexity 3, while the query "is this about researchers-relatedto-projects-relatedto-topics or researchers-relatedto-topics?" has complexity 5. we model the no-reponse probability r(q) for a query as a function of its complexity. we have the option of various squashing functions which map positive integers to [0, 1]. we use the generalized logistic function: using this definition of no-response probability, we define the expected utility of a query as ū(q) = u(q)(1-r(q)). our strategy picks that mini-query at step k of a mini dialog that maximizes this expected utility. if the expert does not respond, then the next best mini-query is posed. having introduced the notion of expected utility to deal with no-response probability, we also modify step (a) of the framework by using expected utility instead of entropy to select the next statement for mini dialog. the expected utility of a statement is taken to be the maximum of the expected utilities of the which-of query and the possible any-of queries for its candidate set. this completes the description of our overall expected utility based dialog strategy (eu). theorem 2. when the expert's response probability is 1, and the dialog strategy is aware of this, the eu dialog strategy recovers the entropy-based active learning strategy (e-al). the proof follows from the observation that when response probability is 1, the query with the highest expected utility is the which-of query on the entire set of candidates, and a mini dialog reduces to a single which-of query. so the dialog format becomes identical to that of active learning. further, expected utility and entropy lead to the same statement being selected for querying. thus e-al is a special case of the eu dialog strategy which is meaningful when the expert al-ways responds. our experiments show that eu far outperforms e-al under response uncertainty. query for a partition: having selected a bipartition for an any-of query, the query for it needs to be formulated. recall that any-of queries have the form "is the statement about any of p 1 or p 2 or ...?". the naive query for a partition enumerates all the paths in the smaller split. instead, we identify the smallest discriminating path feature for the two parts of the partition -such as nodes, edges, length-2 paths, etc. for example, if all the paths in one of the splits contain the entity paper, and no path in the other split contains it, then a possible query for the partition is the following: "is the statement about papers?". being a less complex query, this is much more likely to get a response. estimating response probability: at the start of a dialog, the agent has an initial guess about the expert's response probability model. after receiving responses or non-responses for specific queries, the parameters of this model can be estimated. on the conclusion of a mini dialog, we update the parameters w and t in the standard way for logistic regression using gradient descent. ## experiments for empirical evaluation, we experimented with statements collected from the website of a large multi-national company, to see how accurately an expert's desired schema behind the website data can be recovered. from 64 web-pages on the company's website, we picked short statements representative about the company's business, each containing at most 2 pairs of entity / type mentions. this resulted in a dataset of 850 short statements. in addition, we obtained from an expert a schema for the company's business, which covers the statements that were picked. the resultant schema contains 15 entity types and 17 relationships between these. using this schema, we manually annotated the statements with entities, entity types and type paths. about 40% statements had schema paths of length 1 and remaining of length 2. we used 200 the statements for train and the remaining 650 for test, ensuring that all entity and relation types used in the test schema paths are covered in the train. to simulate the expert for large-scale experimentation, we used an 'expert bot' that had knowledge of the gold standard schema paths. the noresponse parameters of the expert bot were manually specified. for each query, the expert bot sam-pled from a bernoulli distribution for the query to decide whether or not to respond. to evaluate a dialog, we use the learning curve, where we plot the length of the dialog (terms of number of mini-queries) against the correctness of the inferred schema paths for the statements in the test set as compared with the gold-standard schema paths, evaluated using the f1 measure. our proposed dialog strategy eu -l, picks the next statement for mini-dialog and also the next mini-query within a mini-dialog using expected utility (eu) , and further learns (l) the no-response parameter based on the expert's action (response / no-response). we compare our strategy against a few baselines. eu does not learn the expert's no-response probability. random + eu picks the next statement for dialog uniformly at random (r), instead of expected utility, but uses expected utility (eu) to selected the query within a mini dialog. e-al++ uses entropy (e) reduction assuming certain response for selecting the next statement for dialog as well as the next query within a mini dialog. note that this is still more powerful than the e-al strategy @xcite , which only poses which-of queries assuming the expert will respond. this makes no progress for non-zero noresponse probability. in contrast, e-al++ uses the mixed any-which mini-dialog format and has the flexibility to pose any-of queries by partitioning. in addition, we also evaluate as a skyline eu-o, where the agent is an oracle (o) with perfect knowledge about the expert's no-response parameters. in the first experiment, the agent has knowledge of the complete schema, and does not need to consider new entity or relation types. in fig. 1 , we plot the performances of eu-l along with the baselines. for each strategy, we plot the number of mini-queries on the x-axis and cumulative f1 on the test set after re-estimating parameters and re-inferring paths at the end of a mini-dialog on the yaxis. e-al++ performs quite poorly and gets very little improvement in accuracy. accounting for noresponse via expected utility for selecting the query within a mini dialog (random + eu) makes some improvement over this, but a eu makes a major improvement by using expected utility when selecting the next statement for dialog. finally, eu-l makes a steady improvement by estimating the noresponse parameters. note that the skyline eu-o with perfect knowledge of the no-response parameters performs the best, but eu-l catches up with it as the dialogs progress, showing the effectiveness of our learning strategy. we also note that e-al++ can be seen as a special case of eu where the agent assumes that the expert always answers and does not update this model. average number of mini-queries per statement is very different for different strategies. this is 39 for e-al++, 7.0 for random eu, 7.0 for eu and finally to 6.0 for eu-l. average query complexity (number of entity type nodes in a query) also varies significantly across the strategies. for e-al (only which-of queries), average query complexity is 73.5, which explains why it makes no progress for non-zero no-response probability. this drops to 46 for e-al++, 5.4 for random eu, 4.8 for eu and finally to 2.7 for eu-l. beyond dialog length, this also helps to highlight the benefit of expected utility and learning. in the first experiment, the agent had knowledge of the complete schema, and only needed to detect occurrences of known entity and relation types in schema paths. we call this agent eu-l detect. in the second experiment we compare this with an agent eu-l discover, which only has partial knowledge of the schema at the start, and discovers new entity and relation types via dialog. in the training data for eu-l discover, we randomly removed 5 entity types from the schema, which appear either as intermediate nodes as well as end nodes in the statement paths. we also removed the 9 relationships involving these entity types. this resulted in a pruned schema with 10 entities and 8 relationships. statements associated with prune relationships were removed from the training data. in contrast, eu-l detect was given the complete training data and the complete schema. figure 2: learning curves for discovery and detection provement as the dialog progresses. in summary, we have shown that with response uncertainty, the eu strategy works significantly better than e-al for detecting and discovering schema paths for short natural language statements, thereby enabling the enhancement of the underlying schema for the domain. on top of this, estimating the no-response parameters of the expert leads to further improvements in the learning curve. ## discussion and future work we have introduced the problem of discovering the schema for the knowledge graph for a domain by engaging in dialog with an expert about interpreting short natural language statements in terms of the desired schema. we have proposed dialogue strategy that is aware of no-response probability for the expert, and accounts for it in its strategy by splitting the interaction for a statement into a sequence of short and simple queries, which are chosen using expected utility. the agent also estimates the no-response parameters for an expert. we have demonstrated that the proposed strategy is able to discover a schema starting from an initial partial observation. this goes well beyond the state of the art in active learning for structured spaces. however, much remains to be done. one shortcoming of our expert model is that we have considered no-response to be the only form of 'noise'. in reality, the expert, when presented with a complex question, may provide an incorrect response, and the algorithm should be resilient to a small probability of such erroneous responses. next, we have only considered simple statements for which the statement graphs are paths. in general, such statement graphs can be trees or directed acyclic graphs. we will investigate these aspects in future work.