WO2021096009A1 - Method and device for supplementing knowledge on basis of relation network - Google Patents

Abstract

Disclosed is a method for supplementing knowledge on the basis of a relation network. A method for supplementing knowledge on the basis of a relation network according to one embodiment of the present invention comprises: a step for extracting, for a plurality of node pairs included in a knowledge graph, path information which is information about a plurality of paths representing a relationship between a source node and a target node constituting the node pairs; a step for generating training data corresponding to each of the plurality of paths on the basis of the path information; and a step for training a relation network model by using the training data.

Description

Knowledge supplement method and device based on relation network

The present invention relates to a method and apparatus for supplementing knowledge on a knowledge graph using a relation network (RN).

Knowledge Graphs (KGs) are used as important resources in the fields of machine learning and data mining, and are particularly useful for solving problems such as question answering, fact checking, and link prediction. . The knowledge graph is a knowledge network composed of entity nodes and relationship edges, and may be expressed as a triple <h, r, t> in an RDF format. In this case, h is the head entity, and r is the relationship between the tail entity t connected to h. Although knowledge graphs are widely used in various tasks, there is a problem that correctness and completeness are not guaranteed.

Therefore, it is necessary to improve the quality of the knowledge graph through the Knowledge Graph Completion (KGC) that can find the missing link or entity of the knowledge graph. Recently, many algorithms for KGC have been developed, and all successful models have a common point of expressing entities and relationships as low-dimensional embedding vectors. Since these methods learn entities and relationships themselves, there are limitations in learning the entire knowledge graph, and there are problems in that the prediction performance is no longer improved.

As a related background technology, there is Korean Patent Laid-Open Publication No. 10-2016-0064826 (title of the invention: an apparatus and method for providing a semantic search service based on a knowledge graph, publication date: June 8, 2016).

An embodiment of the present invention is to provide a method and apparatus for supplementing knowledge showing excellent performance while solving the problem of the existing KGC by extracting a relationship path based on a Path Ranking Algorithm (PRA) and using it as training data for a relation network. .

The problem to be solved by the present invention is not limited to the problem(s) mentioned above, and another problem(s) not mentioned will be clearly understood by those skilled in the art from the following description.

A knowledge supplementation method based on a relation network according to an embodiment of the present invention for achieving the above object is a plurality of nodes representing a relationship between a source node constituting a node pair and a target node for a plurality of node pairs included in the knowledge graph. Extracting route information, which is information about the route of Generating training data corresponding to each of the plurality of paths based on the path information; And training a relation network model using the training data.

Preferably, the training data includes a context including information on a relationship represented by each of at least one link constituting an individual path, a question about a relationship between a source node and a target node, and the question. May include an answer to.

Preferably, in the training of the relation network model, a source node, a target node, and a first triple composed of a relationship between the source node and the target node of each of the at least one link are converted into a long A Short (LSTM). -Encoding by inputting into Term Memory; Generating a first result vector by first learning the relation network model using two of the encoded results and a plurality of second triples consisting of the question; And summing the first result vector for each element to secondarily train the relation network model.

Preferably, the at least one link may be less than or equal to a predetermined threshold number.

Preferably, the step of extracting the path information may extract the plurality of paths based on a Path Ranking Algorithm (PRA).

In addition, the knowledge supplement apparatus based on a relation network according to an embodiment of the present invention for achieving the above-described object provides a relationship between a source node and a target node constituting a node pair with respect to a plurality of node pairs included in the knowledge graph. A route extraction unit for extracting route information, which is information on a plurality of routes shown; A data generator for generating training data corresponding to each of the plurality of paths based on the path information; And a learning unit that trains a relation network model by using the training data.

Preferably, the training data includes a context including information on a relationship represented by each of at least one link constituting an individual path, a question about a relationship between a source node and a target node, and the question. May include an answer to.

Preferably, the learning unit encodes the source node of each of the at least one link, the target node, and the relationship between the source node and the target node into Long A Short-Term Memory (LSTM), and encodes the encoded result. By first learning the relation network model using a plurality of triples consisting of two and the questions, a first result vector is generated, and the first result vector is summed in element units to form the relation network model. Secondary learning can be done.

Preferably, the at least one link may be less than or equal to a predetermined threshold number.

Preferably, the path extraction unit may extract the plurality of paths based on a Path Ranking Algorithm (PRA).

Details of other embodiments are included in the detailed description and the accompanying drawings.

The method and apparatus for supplementing knowledge based on a relation network according to the present invention extracts a relational path based on a PRA (Path Ranking Algorithm) and uses it as training data for the relation network, thereby solving the problem of the existing KGC and showing excellent performance. have.

In addition, the knowledge supplement method and apparatus based on the relation network according to the present invention facilitates extraction of meaningful information such as customized services specialized for a user, and thus various service fields of artificial intelligence (Q&A system, recommendation system, interactive agent system, etc. ), there is an effect that can be used.

1 is a flowchart illustrating a method of supplementing knowledge based on a relation network according to an embodiment of the present invention.

2 is a flowchart illustrating a method of learning a relation network model according to an embodiment of the present invention.

3 is a block diagram illustrating an apparatus for supplementing knowledge based on a relation network according to an embodiment of the present invention.

4 is a diagram showing a path matrix according to an embodiment of the present invention.

5 is a diagram illustrating a path sequence according to an embodiment of the present invention.

6 is a diagram for explaining training data according to an embodiment of the present invention.

7 is a diagram illustrating a learning process according to an embodiment of the present invention.

Advantages and/or features of the present invention, and a method of achieving them will become apparent with reference to the embodiments described below in detail together with the accompanying drawings. However, the present invention is not limited to the embodiments disclosed below, but will be implemented in a variety of different forms, only these embodiments are intended to complete the disclosure of the present invention, and common knowledge in the technical field to which the present invention pertains. It is provided to completely inform the scope of the invention to those who have, and the invention is only defined by the scope of the claims. The same reference numerals refer to the same elements throughout the specification.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is a flowchart illustrating a method of supplementing knowledge based on a relation network according to an embodiment of the present invention.

In step S110, the knowledge supplement apparatus provides path information, which is information on a plurality of paths indicating a relationship between a source node and a target node constituting the node pair for a plurality of node pairs included in the knowledge graph. Extract.

Here, when a plurality of nodes exist in the knowledge graph, the knowledge supplement device extracts path information, which is information about a plurality of paths representing the relationship between the source node and the target node, for a plurality of node pairs that pair two nodes among them. can do.

For example, the knowledge supplement apparatus may include path information including information on a plurality of paths existing between A and B with respect to the source node A and the target node B. More specifically, when A and B are connected through intermediate nodes C and D respectively, the knowledge supplement apparatus may extract information about the paths of A-C-B and A-D-B as path information.

In addition, the relationship between the source node and the target node may include content describing the relationship between the subject and the object when the source node is a subject and the target node is an object. For example, when the source node is lebron james and the target node is LA lakers, the relationship may be playsFor.

In another embodiment, the knowledge supplement device may extract a plurality of paths based on a Path Ranking Algorithm (PRA).

That is, the knowledge supplement apparatus may extract a plurality of paths for the source node and the target node from the knowledge graph using the PRA. At this time, the knowledge supplement device can use a random walk on graph algorithm, and the random walk on graph algorithm starts from the source node and moves through other nodes in the middle to reach the target node. Algorithm.

More specifically, the knowledge supplement apparatus may generate a path matrix by calculating a random walk probability for all paths for a plurality of node pairs.

In this case, referring to FIG. 4, each cell value of the path matrix refers to the probability that the _{source node s i reaches the target node t i} through the path ð _i (the i-th column). It becomes possible to identify routes that are not helpful. For example, ð ₂ of FIG. 4 may be classified as a poor path because it has a relatively low probability for most of the node pairs (s _i , t _i ) compared to ð _1. Alternatively, _{even if the probability for some node pairs is high, such as π 1} , it can be determined that it is difficult to classify a path that is helpful for learning even if the majority of node pairs are not connected or have a low probability.

Also, since the number of extracted paths is very large, it is very inefficient to use all paths for learning. Therefore, it is necessary to select a path that can be used for learning. To this end, paths that can have a good influence on learning can be selected based on two criteria.

First, the knowledge supplement device may select paths in which the ratio of node pairs connected through each path occupies more than 70% of the total. For example, if the proportion connected through _{path ð 1} among all triples for a given relationship R is less than 50%, the column for _{path ð 1 can be excluded from the path matrix.}

Second, the knowledge supplement apparatus may select paths to which most of the nodes existing in the node pair can be connected except for paths with a cell value of less than 5% on average in the path matrix, which is a random walk probability for each path.

In step S120, the knowledge supplement apparatus generates training data corresponding to each of the plurality of routes based on the route information.

That is, the knowledge supplement apparatus may generate training data for each of a plurality of paths corresponding to an individual node pair.

In another embodiment, the training data includes a context including information on a relationship represented by each of at least one link constituting an individual path, a question about a relationship between a source node and a target node, and the question. May include an answer to.

First, as training data of the relation network (RN), a story form consisting of a context, a question, and an answer is required.

In this case, the context may include information on at least one link corresponding to a relationship sequence existing between the source node and the target node. Further, the relationship sequence may be divided into individual relationship units (ie, link units) constituting the relationship sequence, and may be divided into a source node, a target node, and a triple structure comprising the relationship. That is, the context can be composed of the separate triple set.

Also, the question can be generated using a target relation with the source node of the first triple of the triple set.

For example, referring to FIG. 5, when the target relationship is playsIn, the relationship sequence extracted through the PRA becomes playsFor → worksFor ^-1 → playsIn. In this case, lebron james and NBA can be matched to Athlete and League, and through this, the knowledge supplement device can generate questions and answers included in the training data as <leb-ron_james playsIn ?> and NBA. In addition, the knowledge supplement apparatus may extract a context for a question in the form of a triple from an instance matching the relationship sequence. That is, the context of <lebron james playsFor LA lakers>, <LA lakers playsFor ^-1 rajon rondo>, and <rajon rondo playsIn NBA> can be constructed from lebron james, the subject of the question. Through this method, a story composed of a context, a question, and an answer from the training data may be constructed as shown in FIG. 6, and may be used as training data for learning of the RN.

In another embodiment, at least one link may be less than or equal to a predetermined threshold number.

That is, when extracting a plurality of paths corresponding to an individual node pair, the knowledge supplementation apparatus may ensure that each of the plurality of paths includes only links less than a threshold number. This is because, when the number of links included in the path exceeds the critical number, the amount of computation required for the knowledge supplement device may increase in proportion thereto.

For example, the knowledge supplement apparatus may extract only paths including only three or fewer links.

Finally, in step S130, the knowledge supplement device learns the relation network model by using the training data.

Here, the relation network is proposed by DeepMind and is a deep learning-based learning model that infers the relationship between objects. RN is composed of a structure that uses training data in the form of a story consisting of context, question, and answer as input, and learns the model through two multi-layer perceptrons (MLPs).

In this case, the relation network model can be expressed using Equation 1 below.

[Equation 1]

Here, o _i and o _j are the i and j-th objects, respectively, a is the answer, q is the question,

Is the relation function,

Is a parameter that predicts an answer to a question based on the learned relationship information.

_{At this time, the combination pair (o i} , o _j ) of individual sentences (ie, source node, target node, and their relationship) constituting the context is merged with the question q, and the first MLP is

Relationships can be learned through. Also, the second MLP

It is possible to learn a parameter that predicts an answer to a question based on the relationship information learned through.

As described above, the knowledge supplement method based on the relation network according to an embodiment of the present invention extracts a relational path based on a PRA (Path Ranking Algorithm) and uses it as training data of the relation network, thereby solving the problem of the existing KGC It has the effect of indicating performance.

2 is a flowchart illustrating a method of learning a relation network model according to an embodiment of the present invention.

In step S210, the knowledge supplement device inputs a source node, a target node, and a first triple consisting of a relationship between the source node and the target node of each of the at least one link into a Long A Short-Term Memory (LSTM). Encode.

For example, referring to FIG. 7, when the knowledge supplement device _{extracts h → e 1} → e ₂ → t, which is a path connecting the node h and the node t, the path may include three first triples. At this time, the three first triples are (h, R ₁ , e ₁ ), (e ₁ , R ₂ , e ₂ ), (e ₂ , R ₃ , e ₃ ).

In this case, the knowledge supplement apparatus may obtain _{C 1} , C ₂ , and C ₃ respectively as a result of encoding the three first triples into the LSTM.

In step S220, the knowledge supplement device generates a first result vector by first learning a relation network model using two of the encoded results and a plurality of second triples consisting of questions.

For example, referring to FIG. 7, the knowledge supplement device selects two of the encoded results C ₁ , C ₂ , and C ₃ , and inputs the question q into an LSTM to generate a total of three second triples including the result of encoding. Configuration, and included in the relational network model

The first result vector can be generated by learning by using it as an input of.

Finally, in step S230, the knowledge supplement apparatus adds the first result vector in element units to secondarily learn the relation network model.

For example, referring to FIG. 7, the knowledge supplement device sums the first result vector in an element-wise sum and is included in the relation network model.

It can be learned by using it as an input of.

At this time,

There are a total of 4 fully connected layers, and each layer can consist of 256 units. All input data

It can be considered that the context and the question are embedded together as it passes through. After each

The first result vectors of are

Is used as the input of.

There are a total of 3 fully connected layers, and the first layer may consist of 256 units and the second layer may consist of 512 units. The last layer is set to the overall vocabulary size, so the softmax value for the answer can be output.

Furthermore, as forward/backward propagation for the above process is repeated for all training data, the relationship between the first triples and the question is learned, so that a model for predicting the target node of the second triple may be trained.

That is, the knowledge supplement apparatus may predict a relationship between missing nodes by using the learned relation network model. Furthermore, the knowledge supplement device can provide various services based on artificial intelligence by applying the learned relation network model to a Q&A system, a recommendation system, an interactive agent system, a chatbot system, and the like.

3 is a block diagram illustrating an apparatus for supplementing knowledge based on a relation network according to an embodiment of the present invention.

Referring to FIG. 3, a knowledge supplement device 300 based on a relation network according to an embodiment of the present invention includes a path extraction unit 310, a data generation unit 320, and a learning unit 330.

Meanwhile, the knowledge supplement device 300 based on a relation network according to an embodiment of the present invention may be mounted on a desktop PC, a notebook PC, a smart phone, a tablet PC, and a server computer.

The path extracting unit 310 extracts path information, which is information about a plurality of paths representing a relationship between a source node and a target node constituting the node pair, for a plurality of node pairs included in the knowledge graph.

The data generator 320 generates training data corresponding to each of the plurality of paths based on the path information.

The learning unit 330 trains the relation network model by using the training data.

In another embodiment, the training data includes a context including information on a relationship represented by each of at least one link constituting an individual path, a question about the relationship between the source node and the target node, and the question. May include an answer to.

In another embodiment, the learning unit 330 inputs and encodes the source node, target node, and the relationship between the source node and the target node of each of at least one link into Long A Short-Term Memory (LSTM), and the encoded By first learning a relation network model using two of the results and a plurality of triples consisting of the above questions, a first result vector is generated, and the first result vector is summed in element units to form a relation network model. Secondary learning can be done.

In another embodiment, at least one link may be less than or equal to a predetermined threshold number.

In another embodiment, the path extraction unit 310 may extract a plurality of paths based on a path ranking algorithm (PRA).

Although the specific embodiments according to the present invention have been described so far, various modifications can be made without departing from the scope of the present invention. Therefore, the scope of the present invention should not be limited to the described embodiments and should not be defined by the claims to be described later, as well as the scope of the claims and their equivalents.

As described above, although the present invention has been described by the limited embodiments and drawings, the present invention is not limited to the above embodiments, which is, if one of ordinary skill in the field to which the present invention belongs, various modifications and Transformation is possible. Therefore, the idea of the present invention should be grasped only by the claims set forth below, and all equivalent or equivalent modifications thereof will be said to belong to the scope of the idea of the present invention.

Claims (10)

1. Extracting path information, which is information about a plurality of paths representing a relationship between a source node and a target node constituting the node pair, for a plurality of node pairs included in the knowledge graph;

   Generating training data corresponding to each of the plurality of paths based on the path information; And

   Training a relation network model using the training data

   Knowledge supplementation method based on a relation network, characterized in that it comprises a.
2. The method of claim 1,

   The training data is

   A context including information on a relationship represented by each of at least one link constituting an individual path, a question about the relationship between the source node and the target node, and an answer to the question. A method of supplementing knowledge based on a relation network, characterized in that.
3. The method of claim 2,

   The step of training the relation network model

   Encoding a source node, a target node of each of the at least one link, and a first triple consisting of a relationship between the source node and the target node into a Long A Short-Term Memory (LSTM);

   Generating a first result vector by first learning the relation network model using two of the encoded results and a plurality of second triples consisting of the question; And

   Summing the first result vector for each element to secondarily train the relation network model

   Knowledge supplementation method based on a relation network, characterized in that it comprises a.
4. The method of claim 2,

   The at least one link

   A method of supplementing knowledge based on a relation network, characterized in that the number is less than or equal to a predetermined threshold number.
5. The method of claim 1,

   Extracting the route information

   A knowledge supplement method based on a relation network, characterized in that extracting the plurality of paths based on a Path Ranking Algorithm (PRA).
6. A path extracting unit for extracting path information, which is information about a plurality of paths representing a relationship between a source node and a target node constituting the node pair, for a plurality of node pairs included in the knowledge graph;

   A data generator for generating training data corresponding to each of the plurality of paths based on the path information; And

   A learning unit that trains a relation network model using the training data

   A knowledge supplement device based on a relation network, comprising: a.
7. The method of claim 6,

   The training data is

   A context including information on a relationship represented by each of at least one link constituting an individual path, a question about a relationship between a source node and a target node, and an answer to the question A knowledge supplement device based on a relation network, characterized in that.
8. The method of claim 7,

   The learning unit

   The source node of each of the at least one link, the target node, and the relationship between the source node and the target node are input to Long A Short-Term Memory (LSTM) and encoded,

   By first learning the relation network model using two of the encoded results and a plurality of triples consisting of the question, a first result vector is generated,

   The apparatus for supplementing knowledge based on a relation network, characterized in that the relation network model is secondarily trained by summing the first result vector for each element.
9. The method of claim 7,

   The at least one link

   A knowledge supplement device based on a relation network, characterized in that the number is less than or equal to a predetermined threshold number.
10. The method of claim 6,

    The path extraction unit

    A knowledge supplement device based on a relation network, characterized in that extracting the plurality of paths based on a Path Ranking Algorithm (PRA).

Images