CN115858821A

CN115858821A - Knowledge graph processing method and device and training method of knowledge graph processing model

Info

Publication number: CN115858821A
Application number: CN202310132855.9A
Authority: CN
Inventors: 张勇东; 何向南; 陈伟健; 冯福利
Original assignee: University of Science and Technology of China USTC
Current assignee: University of Science and Technology of China USTC
Priority date: 2023-02-20
Filing date: 2023-02-20
Publication date: 2023-03-28
Anticipated expiration: 2043-02-20
Also published as: CN115858821B

Abstract

The invention provides a knowledge graph processing method and device and a knowledge graph processing model training method, which can be applied to the technical field of computers and the technical field of machine learning. The method comprises the following steps: acquiring a first entity relationship pair and a second entity relationship pair of the initial knowledge graph, wherein the first entity relationship pair comprises a first head entity, a first tail entity and a first connection relationship between the first head entity and the first tail entity, and the second entity relationship pair comprises a second head entity, a second tail entity and a second connection relationship between the second head entity and the second tail entity; determining a third entity-relationship pair based on the first attention score of the first entity-relationship pair and the second attention score of the second entity-relationship pair; and processing the first connection relation, the second connection relation and the third connection relation to obtain a target knowledge graph.

Description

Knowledge graph processing method and device and training method of knowledge graph processing model

Technical Field

The invention relates to the technical field of computers and machine learning, in particular to a knowledge graph processing method and device, electronic equipment and a knowledge graph processing model training method.

Background

Knowledge maps (KG) can display complex Knowledge in the fields of medicine, finance, e-commerce and the like through data mining, information processing, knowledge measurement and graphic drawing, reveal dynamic development rules of the Knowledge field, and provide practical and valuable references for subject research, such as drug discovery, user modeling, dialogue systems and the like. However, the existing Knowledge Graph has a serious problem of information loss, and compared with the high cost of manual labeling, the Knowledge Graph Completion (KGC) can automatically predict a missing entity relationship pair based on an incomplete Knowledge Graph.

In implementing the concept of the present invention, the inventors found that at least the following problems exist in the related art: the knowledge graph completion method in the related art cannot fully utilize the connection relation in the knowledge graph, so that the completion of the knowledge graph is not comprehensive.

Disclosure of Invention

In view of the above problems, the present invention provides a method and an apparatus for processing a knowledge graph, an electronic device, and a method for training a knowledge graph processing model.

According to a first aspect of the present invention, there is provided a knowledge-graph processing method, comprising:

acquiring a first entity relationship pair and a second entity relationship pair of the initial knowledge graph, wherein the first entity relationship pair comprises a first head entity, a first tail entity and a first connection relationship between the first head entity and the first tail entity, and the second entity relationship pair comprises a second head entity, a second tail entity and a second connection relationship between the second head entity and the second tail entity;

determining a third entity relationship pair based on the first attention score of the first entity relationship pair and the second attention score of the second entity relationship pair, wherein the third entity relationship pair comprises a first head entity, a second tail entity, and a third connection relationship between the first head entity and the second tail entity;

and processing the first connection relation, the second connection relation and the third connection relation to obtain a target knowledge graph.

According to an embodiment of the invention, wherein determining the third pair of entity relationships based on the first attention score of the first pair of entity relationships and the second attention score of the second pair of entity relationships comprises:

determining a first attention score for the first entity-relationship pair and a second attention score for the second entity-relationship pair using an attention mechanism;

determining a third connection relation satisfying a preset condition based on the first attention score and the second attention score;

based on the third connection relationship, a third entity-relationship pair is determined.

According to an embodiment of the present invention, the first connection relationship, the second connection relationship, and the third connection relationship each include I dimensions, and the processing of the first connection relationship, the second connection relationship, and the third connection relationship to obtain the target knowledge graph includes:

performing aggregation updating on the first connection relation of the ith dimension, the second connection relation of the ith dimension and the third connection relation of the ith dimension to obtain a first updating connection relation, a second updating connection relation and a third updating connection relation which respectively correspond to the first connection relation, the second connection relation and the third connection relation, wherein I is more than or equal to 1 and less than or equal to I, and I and I are integers;

and processing the first updated connection relation, the second updated connection relation and the third updated connection relation to obtain the target knowledge graph.

According to the embodiment of the present invention, the aggregating and updating the first connection relationship of the ith dimension, the second connection relationship of the ith dimension, and the third connection relationship of the ith dimension to obtain the first updated connection relationship, the second updated connection relationship, and the third updated connection relationship respectively corresponding to the first connection relationship, the second connection relationship, and the third connection relationship includes:

generating a first initial relation matrix based on the first connection relation, the second connection relation and the third connection relation, wherein a column vector in the first initial relation matrix represents a dimension, and a row vector represents a connection relation;

determining a target connection relation according to the first connection relation, the second connection relation and the third connection relation;

performing relation masking on the target connection relation in the first initial relation matrix to obtain a first intermediate relation matrix;

determining an ith column vector from the first intermediate relationship matrix based on the first connection relationship of the ith dimension, the second connection relationship of the ith dimension and the third connection relationship of the ith dimension;

and performing aggregation updating on the ith column vector to obtain a first updating connection relation, a second updating connection relation and a third updating connection relation which respectively correspond to the first connection relation, the second connection relation and the third connection relation.

According to an embodiment of the present invention, the processing the first updated connection relationship, the second updated connection relationship, and the third updated connection relationship to obtain the target knowledge graph includes:

generating a second initial relation matrix based on the first updated connection relation, the second updated connection relation and the third updated connection relation, wherein the column vectors in the second initial relation matrix represent dimensions, and the row vectors represent connection relations;

performing dimension mask on the nth column vector in the second initial relation matrix based on the nth dimension to obtain a second intermediate relation matrix, wherein n is a positive integer;

and processing each row vector in the second intermediate relation matrix to obtain a target knowledge graph.

According to an embodiment of the present invention, performing aggregation update on the ith column vector to obtain a first updated connection relationship, a second updated connection relationship, and a third updated connection relationship respectively corresponding to the first connection relationship, the second connection relationship, and the third connection relationship, includes:

activating the ith column vector by using a first activation function to obtain an intermediate column vector;

and performing aggregation updating on the intermediate column vectors according to the first weight matrix to obtain a first updated connection relation, a second updated connection relation and a third updated connection relation which respectively correspond to the first connection relation, the second connection relation and the third connection relation.

According to an embodiment of the present invention, wherein processing each row vector in the second intermediate relationship matrix to obtain the target knowledge-graph includes:

activating the row vectors by using a second activation function to obtain intermediate row vectors;

and aggregating the intermediate row vectors according to the second weight matrix to obtain the target knowledge graph.

A second aspect of the present invention provides a method for training a knowledge-graph processing model, comprising:

acquiring an initial knowledge graph sample, wherein the initial knowledge graph sample comprises a first entity relationship pair sample and a second entity relationship pair sample, the first entity relationship pair sample is an unprocessed entity relationship pair in the initial knowledge graph, and the second entity relationship pair sample is a processed entity relationship pair in the initial knowledge graph;

and taking the second entity relation pair sample pair as a label, taking the first entity relation pair sample as an input to train the knowledge graph processing model, and obtaining the trained knowledge graph processing model.

A third aspect of the present invention provides a knowledge-graph processing apparatus comprising:

the first obtaining module is used for obtaining a first entity relationship pair and a second entity relationship pair of the initial knowledge graph, wherein the first entity relationship pair comprises a first head entity, a first tail entity and a first connection relationship between the first head entity and the first tail entity, and the second entity relationship pair comprises a second head entity, a second tail entity and a second connection relationship between the second head entity and the second tail entity;

a determining module for determining a third entity-relationship pair based on the first attention score of the first entity-relationship pair and the second attention score of the second entity-relationship pair, wherein the third entity-relationship pair comprises a first head entity, a second tail entity, and a third connection relationship between the first head entity and the second tail entity;

and the first obtaining module is used for processing the first connection relation, the second connection relation and the third connection relation to obtain a target knowledge graph.

A fourth aspect of the present invention provides an electronic apparatus comprising: one or more processors; memory for storing one or more programs, wherein the one or more programs, when executed by the one or more processors, cause the one or more processors to perform the above-described method.

According to the knowledge graph processing method, the knowledge graph processing device, the electronic equipment and the training method of the knowledge graph processing model, a first entity relation pair and a second entity relation pair of an initial knowledge graph are obtained, wherein the first entity relation pair comprises a first head entity, a first tail entity and a first connection relation between the first head entity and the first tail entity, and the second entity relation pair comprises a second head entity, a second tail entity and a second connection relation between the second head entity and the second tail entity; determining a third entity-relationship pair based on the first attention score of the first entity-relationship pair and the second attention score of the second entity-relationship pair, wherein the third entity-relationship pair comprises a first head entity, a second tail entity, and a third connection relationship between the first head entity and the second tail entity; and processing the first connection relation, the second connection relation and the third connection relation to obtain a target knowledge graph. The third entity relationship pair is determined through the first attention score and the second attention score, more entity relationship pairs are obtained, the target knowledge graph is obtained through processing based on the first connection relationship, the second connection relationship and the third connection relationship, and utilization of the connection relationship in the initial knowledge graph is enhanced.

Drawings

The above and other objects, features and advantages of the present invention will become more apparent from the following description of embodiments of the present invention with reference to the accompanying drawings, in which:

FIG. 1 illustrates an application scenario diagram of a knowledge-graph processing method according to an embodiment of the present invention;

FIG. 2 shows a flow diagram of a knowledge-graph processing method according to an embodiment of the invention;

FIG. 3 illustrates a schematic processing diagram of a first initial relationship matrix and a second initial relationship matrix according to an embodiment of the invention;

FIG. 4 shows a flow diagram of a method of training a knowledge-graph processing model according to an embodiment of the invention;

FIG. 5 shows a training diagram of a knowledge-graph processing model according to an embodiment of the invention;

FIG. 6 shows a schematic diagram of an example knowledge graph processing model process according to an embodiment of the invention;

FIG. 7 shows a block diagram of a knowledge-graph processing apparatus according to an embodiment of the invention;

FIG. 8 shows a block diagram of a training apparatus for a knowledge-graph processing model according to an embodiment of the present invention;

FIG. 9 shows a block diagram of an electronic device suitable for implementing a knowledge-graph processing method according to an embodiment of the invention.

Detailed Description

Hereinafter, embodiments of the present invention will be described with reference to the accompanying drawings. It is to be understood that such description is merely illustrative and not intended to limit the scope of the present invention. In the following detailed description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the embodiments of the invention. It may be evident, however, that one or more embodiments may be practiced without these specific details. Moreover, in the following description, descriptions of well-known structures and techniques are omitted so as to not unnecessarily obscure the concepts of the present invention.

The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the invention. The terms "comprises," "comprising," and the like, as used herein, specify the presence of stated features, steps, operations, and/or components, but do not preclude the presence or addition of one or more other features, steps, operations, or components.

All terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art unless otherwise defined. It is noted that the terms used herein should be interpreted as having a meaning that is consistent with the context of this specification and should not be interpreted in an idealized or overly formal sense.

Where a convention analogous to "at least one of A, B, C, etc." is used, in general such a construction is intended in the sense one having skill in the art would understand the convention (e.g., "a system having at least one of A, B, C" would include but not be limited to systems that have a alone, B alone, C alone, a and B together, a and C together, B and C together, and/or A, B, C together, etc.).

In the technical scheme of the invention, the collection, storage, use, processing, transmission, provision, disclosure, application and other processing of the personal information of the related user are all in accordance with the regulations of related laws and regulations, necessary confidentiality measures are taken, and the customs of the public order is not violated.

In the technical scheme of the invention, the data acquisition, collection, storage, use, processing, transmission, provision, disclosure, application and other processing are all in accordance with the regulations of relevant laws and regulations, necessary security measures are taken, and the public order and good custom are not violated.

In the related art, KGC aims to use the existing information in KG to perform inference of unknown entities, and can be roughly classified into an embedding-based method and a multi-hop inference-based method. The basic idea of the embedding-based approach is to learn representations of entities and connection relationships to model semantic associations between pairs of entity relationships. They typically assess the rationality of unknown entities through well-designed scoring functions. These methods can be classified as translation-based, semantic matching-based and neural network-based, according to different design criteria of the scoring function. These methods train in an end-to-end fashion, which can balance efficiency and performance well. In contrast, multi-hop inference based methods sacrifice some performance to improve interpretability, with the basic idea being to discover possible paths between head and tail entities to infer missing entities. These efforts typically include reinforcement learning based and neural symbol rule based models. The former uses reinforcement learning mainly to take entity and/or connection relation as state or action to go along the existing graph structure, while the latter helps to establish inference path by mining logic rule.

In order to improve the embedding-based KGC method, a Graph Convolutional Network (GCN) is introduced to model the Graph structure of the knowledge Graph, and the GCN is usually used as an encoder to complete the representation learning of the entity and the connection relationship, and then, an embedding-based scoring function is used as a decoder to evaluate the reasonableness of the fact. The strategy further improves the performance of the embedding-based approach due to the rich structural information contained in the optimized representation. However, most of these approaches focus on updates to the connection relationships between entities, ignoring updates to the intrinsic associations between connection relationships.

In view of this, an embodiment of the present invention provides a method for processing a knowledge graph, including: acquiring a first entity relationship pair and a second entity relationship pair of the initial knowledge graph, wherein the first entity relationship pair comprises a first head entity, a first tail entity and a first connection relationship between the first head entity and the first tail entity, and the second entity relationship pair comprises a second head entity, a second tail entity and a second connection relationship between the second head entity and the second tail entity; determining a third entity-relationship pair based on the first attention score of the first entity-relationship pair and the second attention score of the second entity-relationship pair, wherein the third entity-relationship pair comprises a first head entity, a second tail entity, and a third connection relationship between the first head entity and the second tail entity; and processing the first connection relation, the second connection relation and the third connection relation to obtain a target knowledge graph. The third entity relation pair is determined through the first attention score and the second attention score, more entity relation pairs are obtained, processing is carried out based on the first connection relation, the second connection relation and the third connection relation, the target knowledge graph is obtained, and utilization of the connection relation in the initial knowledge graph is enhanced.

Fig. 1 shows an application scenario diagram of a knowledge-graph processing method according to an embodiment of the present invention.

As shown in fig. 1, the application scenario 100 according to this embodiment may include a first terminal device 101, a second terminal device 102, a third terminal device 103, a network 104, and a server 105. The network 104 is used to provide a medium for communication links between the first terminal device 101, the second terminal device 102, the third terminal device 103 and the server 105. Network 104 may include various connection types, such as wired, wireless communication links, or fiber optic cables, to name a few.

The user may interact with the server 105 via the network 104 using the first terminal device 101, the second terminal device 102, the third terminal device 103, to receive or send messages, etc. Various communication client applications, such as a shopping application, a web browser application, a search application, an instant messaging tool, a mailbox client, social platform software, etc. (for example only), may be installed on the first terminal device 101, the second terminal device 102, and the third terminal device 103.

The first terminal device 101, the second terminal device 102, and the third terminal device 103 may be various electronic devices having a display screen and supporting web browsing, including but not limited to smart phones, tablet computers, laptop portable computers, desktop computers, and the like.

The server 105 may be a server providing various services, such as a background management server (for example only) providing support for websites browsed by the user using the first terminal device 101, the second terminal device 102, and the third terminal device 103. The background management server may analyze and perform other processing on the received data such as the user request, and feed back a processing result (e.g., a webpage, information, or data obtained or generated according to the user request) to the terminal device.

It should be noted that the method for processing a knowledge graph provided by the embodiment of the present invention may be generally executed by the server 105. Accordingly, the knowledge-graph processing apparatus provided by the embodiment of the present invention may be generally disposed in the server 105. The method for processing the knowledge graph provided by the embodiment of the present invention may also be executed by a server or a server cluster that is different from the server 105 and is capable of communicating with the first terminal device 101, the second terminal device 102, the third terminal device 103 and/or the server 105. Accordingly, the knowledge-graph processing apparatus provided in the embodiment of the present invention may also be disposed in a server or a server cluster different from the server 105 and capable of communicating with the first terminal device 101, the second terminal device 102, the third terminal device 103 and/or the server 105.

It should be understood that the number of terminal devices, networks, and servers in fig. 1 is merely illustrative. There may be any number of terminal devices, networks, and servers, as desired for an implementation.

FIG. 2 shows a flow diagram of a knowledge-graph processing method according to an embodiment of the invention.

As shown in FIG. 2, the knowledge-graph processing method of the embodiment includes operations S210-S230.

In operation S210, a first entity relationship pair and a second entity relationship pair of the initial knowledge-graph are obtained, where the first entity relationship pair includes a first head entity, a first tail entity, and a first connection relationship between the first head entity and the first tail entity, and the second entity relationship pair includes a second head entity, a second tail entity, and a second connection relationship between the second head entity and the second tail entity.

According to embodiments of the invention, the initial knowledge-graph may be a relatively sparse knowledge-graph of entity-relationship pairs.

According to embodiments of the present invention, a first entity-relationship pair may characterize a triple in the initial knowledge-graph, the first entity-relationship pair comprising a first head entity, a first tail entity, and a first connection relationship, e.g., the first entity-relationship pair may be (A, co-workers, B) where A is the first head entity, B is the first tail entity, and "co-workers" is the first connection relationship.

According to an embodiment of the present invention, the second entity-relationship pair may represent a different triplet of the initial knowledge-graph than the first entity-relationship pair, and specifically may be that the first connection relationship is different from the second connection relationship, for example, the first entity relationship is (a, coworkers, B), and the second entity-relationship pair is (a, friends, B), where a is both the first head entity and the second head entity, and B is both the first tail entity and the second tail entity; the first and second pairs of entity relationships may also be different entities, for example, the first pair of entity relationships is (a, with coworkers, B), the second pair of entity relationships is (B, with friends, C), B is both the first tail entity and the second head entity, and the second pair of entity relationships may also be (C, with coworkers, B).

According to an embodiment of the present invention, there may be a plurality of first entity-relationship pairs, and there may also be a plurality of second entity-relationships.

In operation S220, a third entity relationship pair is determined based on the first attention score of the first entity relationship pair and the second attention score of the second entity relationship pair, wherein the third entity relationship pair includes the first head entity, the second tail entity, and a third connection relationship between the first head entity and the second tail entity.

According to an embodiment of the invention, the first attention score may be indicative of a degree of closeness between the first cephalic entity and the first caudal entity and the second attention score may be indicative of a degree of closeness between the second cephalic entity and the second caudal entity.

According to the embodiment of the present invention, the second tail entity may be used as a tail entity in a third entity relationship pair to be complemented, and a relationship path from the first head entity to the second tail entity is determined according to the first attention score and the second attention score, so as to determine a third connection relationship, thereby obtaining a third entity relationship pair.

In operation S230, the first connection relationship, the second connection relationship, and the third connection relationship are processed to obtain a target knowledge graph.

According to the embodiment of the invention, the entities in the initial knowledge graph can be connected through the first connection relation, the second connection relation and the third connection relation, so that the target knowledge graph is obtained.

According to an embodiment of the present invention, a first entity relationship pair and a second entity relationship pair of an initial knowledge-graph are obtained, wherein the first entity relationship pair includes a first head entity, a first tail entity and a first connection relationship between the first head entity and the first tail entity, and the second entity relationship pair includes a second head entity, a second tail entity and a second connection relationship between the second head entity and the second tail entity; determining a third entity relationship pair based on the first attention score of the first entity relationship pair and the second attention score of the second entity relationship pair, wherein the third entity relationship pair comprises a first head entity, a second tail entity, and a third connection relationship between the first head entity and the second tail entity; and processing the first connection relation, the second connection relation and the third connection relation to obtain a target knowledge graph. The third entity relationship pair is determined through the first attention score and the second attention score, more entity relationship pairs are obtained, the target knowledge graph is obtained through processing based on the first connection relationship, the second connection relationship and the third connection relationship, and utilization of the connection relationship in the initial knowledge graph is enhanced.

According to an embodiment of the invention, wherein determining the third entity-relationship pair based on the first attention score of the first entity-relationship pair and the second attention score of the second entity-relationship pair comprises:

According to an embodiment of the present invention, the attention mechanism may be a relationship-aware weightless GCN establishment, and specifically, the third entity relationship pair may be described by an aggregation function.

（1）

wherein ,

represents a third trailing entity, in a third entity-relationship pair>

Represents a first entity-relationship pair and a second entity-relationship pair in the initial knowledge-graph, and->

Represents a first head entity and a first connection relation in a first entity-relationship pair or a second head entity and a second connection relation in a second entity-relationship pair, respectively, < >>

Respectively represent passing throughlThe first head entity, the first connection relation and the first tail entity after the second iteration or after the second iterationlThe second head entity after the second iteration, a second connection relationship and a second tail entity, device for selecting or keeping>

Representing an update function.

According to an embodiment of the present invention, a first head entity and a first tail entity in a first entity-relationship pair and a second head entity and a second tail entity in a second entity-relationship pair may be mapped to a relationship space, and specifically, a sparse matrix may be used as a projection matrix by applying a diagonal constraint:

（2）

（3）

wherein ,

a projection matrix representing a first head entity and a first connection relation or a second head entity and a second connection relation, ->

A projection matrix representing a first trailing entity and a first connection or a second trailing entity and a second connection, <' >>

A diagonal matrix representing the first connection or the second connection.

According to an embodiment of the present invention, the third entity relationship pair may be updated by the projection matrix:

（4）

wherein ,d _s indicates the number of first header entities or second header entities,d _t indicating the number of first tail entities or second tail entities,

a first or second attention score is represented.

In accordance with an embodiment of the present invention,

calculated by the following equation (5):

（5）

wherein, in the formula (5), use is made of

(hyperbolic tangent function) rather than conventional

(normalization function), mainly because the tanh function better aggregates information from the first and second pairs of entity-relationships.

According to embodiments of the invention, the third pair of entity relationships may be determined by a first attention score of a plurality of first pairs of entity relationships and a second attention score of a plurality of second pairs of entity relationships, e.g. a set of relationships assuming a third connection relationship between the first head entity and the second tail entity

The set of relationships consists of at least one first connection and at least one second connection, i.e. < >>

（nIs a number of first and second connection relations, is>

Representing either the first connection relationship or the second connection relationship), the following may be obtained:

（6）

wherein ,

representing a second tail entity in a third entity-relationship pair,

are respectively>

Is the corresponding first attention score or second attention score. In the event that the attention scores on one path all exceed the threshold, then a third entity relationship pair may be determined.

and processing the first updating connection relation, the second updating connection relation and the third updating connection relation to obtain a target knowledge graph.

According to the embodiment of the invention, the first connection relation, the second connection relation and the third connection relation all comprise I dimensions, the first connection relation, the second connection relation and the third connection relation in the same dimension can be aggregated to obtain the correlation of the first connection relation, the second connection relation and the third connection relation in the same dimension, and the first updated connection relation, the second updated connection relation and the third updated connection relation respectively corresponding to the first connection relation, the second connection relation and the third connection relation are obtained after aggregation and updating.

According to an embodiment of the present invention, the first updated connection relationship, the second updated connection relationship, and the third updated connection relationship are obtained as follows:

（7）

wherein ,

a first updated connection, a second updated connection, or a third updated connection representing an ith dimension, based on a predetermined criteria>

A first relational inference function is represented that represents,Rrepresenting a set of relationships comprising a first connection relationship, a second connection relationship and a third connection relationship,krepresents any connected relationship in a set of relationships>

And representing the connection relation obtained in the previous layer of network, the first connection relation of the ith dimension, the second connection relation of the ith dimension and the third connection relation of the ith dimension in the relation set.

According to an embodiment of the present invention, the first entity-relationship pair may be (food, including fruit and apple), and the closeness between the "food" and the "apple" may be embodied by the distance between the first head entity "food" and the first tail entity "apple" in the initial knowledge graph, that is, the attention score of the first connection relationship "including fruit" is, for example, 0.1, the attention score of the first connection relationship may be 0.2, and the attention score of the aggregated updated connection relationship may be 0.2, so that the distance between the first head entity "food" and the first tail entity "apple" is reduced, so that the connection between the head entity and the tail entity is strengthened, and it is more favorable for discovering a new entity-relationship pair, and the second updated connection relationship and the third updated connection relationship are similar to the first updated connection relationship, and will not be described herein again.

According to an embodiment of the present invention, the processing of the first connection relationship, the second connection relationship, and the third connection relationship may be updating I dimensions of the connection relationship itself, as follows:

（8）

wherein ,

representing connections in a target knowledge-graph>

Represents a second relational inference function, < > based>

And represents any one of the first updated connection relationship, the second updated connection relationship and the third updated connection relationship.

According to the embodiment of the invention, the first connection relation, the second connection relation and the third connection relation are aggregated and processed, so that the internal relation among the relations can be inferred from the connection relations, the initial knowledge graph can be supplemented better, and the target knowledge graph can be obtained.

performing relation mask on the target connection relation in the first initial relation matrix to obtain a first intermediate relation matrix;

According to the embodiment of the present invention, in order to facilitate the update process of the initial map by the computer, the first initial relationship matrix may be generated based on the first connection relationship, the second connection relationship, and the third connection relationship.

According to the embodiment of the present invention, in order to enable the first initial relationship matrix to better learn the intrinsic correlation between the connection relationships, a target connection relationship may be randomly determined from the first connection relationship, the second connection relationship, and the third connection relationship, and a column vector corresponding to the target connection relationship is subjected to relationship masking in the first initial relationship matrix to obtain a first intermediate relationship matrix, and specifically, an element corresponding to the target connection relationship in the first initial relationship matrix may be set to zero.

According to the embodiment of the present invention, the number of column vectors in the first intermediate relationship matrix corresponds to the dimensions of the first connection relationship, the second connection relationship and the third connection relationship, that is, the first intermediate relationship matrix has I column vectors, and the ith column vector corresponding to the ith dimension can be determined from the first intermediate relationship matrix based on the ith dimension.

According to the embodiment of the present invention, the ith column vector is updated in an aggregation manner, which may be to analyze semantic information of the connection relationship of the ith dimension to obtain a first updated connection relationship, a second updated connection relationship, and a third updated connection relationship respectively corresponding to the first connection relationship, the second connection relationship, and the third connection relationship.

According to the embodiment of the invention, the internal relation between the connection relations can be further learned by processing the connection relations under the same dimensionality.

generating a second initial relation matrix based on the first updated connection relation, the second updated connection relation and the third updated connection relation, wherein the column vectors in the second initial relation matrix represent the dimensions, and the row vectors represent the connection relations;

According to the embodiment of the invention, the second initial relation matrix can be generated by the first updated connection relation, the second updated connection relation and the third updated connection relation, so that the initial knowledge graph can be better updated and supplemented.

According to the embodiment of the present invention, the column vectors of the second initial relationship matrix correspond to n dimensions of the connection relationship, the nth dimension may be determined randomly, and the correspondence between the dimensions and the column vectors may be determined according to the nth column vector of the second initial relationship matrix determined by the nth dimension, so as to perform dimension masking on the nth column vector to obtain the second intermediate relationship matrix, and specifically, the corresponding elements of the nth column vector in the second initial relationship matrix may be set to zero.

According to the embodiment of the invention, the semantic analysis processing can be carried out on the I dimensions of the entity relation pair corresponding to the row vector to obtain the target knowledge graph.

According to the embodiment of the present invention, the aggregating and updating the ith column vector to obtain a first updated connection relation, a second updated connection relation, and a third updated connection relation corresponding to the first connection relation, the second connection relation, and the third connection relation, respectively, includes:

According to an embodiment of the present invention, the first weight matrix may include a first sub-weight matrix, the second sub-weight matrix, and the second weight matrix may include a third sub-weight matrix and a fourth sub-weight matrix, and the above process may be represented by the following formula:

（9）

（10）

wherein ,

a first result matrix representing an output of the i-th dimension aggregated with the first connection, the second connection, and the third connection, and/or a decision matrix representing a decision whether to perform a decision based on the first and/or the second connection>

Denotes the firstlA second result matrix for level output, < > or >>

Represents a target result matrix corresponding to the target knowledge-map, based on the results of the analysis, and->

Represents a first adjustment parameter, is selected>

Represents a relationship mask, <' > based on>

Represents a second adjustment parameter, is selected>

Represents an activation function, <' > is selected>

Represents a dimension mask, < >>

Represents a first sub-weight matrix, < > based on the weight of the reference signal>

Represents a second sub-weight matrix, < > based on the weight of the sub-block>

Represents a third sub-weight matrix, < > based on the weight of the sub-block>

A fourth sub-weight matrix is represented.

Fig. 3 shows a schematic processing diagram of the first initial relationship matrix and the second initial relationship matrix according to the embodiment of the present invention.

As shown in fig. 3, a first intermediate relationship matrix is obtained by performing random relationship masking on a first initial relationship matrix, a first result relationship matrix is obtained by performing aggregation update on column vectors in the first intermediate relationship matrix, where the first result relationship matrix includes a first updated connection relationship, a second updated connection relationship, and a third updated connection relationship respectively corresponding to the first connection relationship, the second connection relationship, and the third connection relationship, a second intermediate relationship matrix is obtained by performing random dimension masking on the second initial relationship matrix, a row vector in the second intermediate relationship matrix is processed by a multi-layer sensing mechanism, a target relationship matrix is obtained, and a target knowledge graph is obtained based on the connection relationship in the target relationship matrix.

FIG. 4 shows a flow diagram of a method of training a knowledge-graph processing model according to an embodiment of the invention.

As shown in FIG. 4, the method includes operations S410-S420.

Operation S410, acquiring an initial knowledge-graph sample, where the initial knowledge-graph sample includes a first entity-relationship pair sample and a second entity-relationship pair sample, the first entity-relationship pair sample pair is an unprocessed entity-relationship pair in the initial knowledge-graph, and the second entity-relationship pair sample pair is a processed entity-relationship pair in the initial knowledge-graph;

operation S420 is performed, where the second entity relationship pair sample pair is used as a label, and the first entity relationship pair sample is used as an input to train the knowledge graph processing model, so as to obtain a trained knowledge graph processing model.

According to embodiments of the present invention, an initial knowledge-graph sample may be obtained from a knowledge-graph database.

According to an embodiment of the present invention, the first entity relationship pair sample may be a set of relatively sparse entity relationship pairs in the initial knowledge-graph, and the second entity relationship pair sample may be a richer entity relationship pair obtained by complementing the initial knowledge-graph.

According to the embodiment of the invention, completion on the sparse KG can be completed through multiple iterations, and the optimized input scoring function is subjected to

To complete the entity-relationship pair>

By selecting TransE (translation-based), distMult (semantic matching-based) and ConvE (neural network-based) as representative scoring functions >>

And determining the loss value of the knowledge graph processing model according to the cross entropy function, wherein the loss value is represented by the following formula (11):

（11）

wherein ,

represents a loss value of the knowledge-graph processing model, <' >>

Is the activation (logical signature) function,ois the tail entity in the initial knowledge-graph sample,Vrepresents a set of entities, <' > based on>

Representing pairs of inferred entity relationships of the knowledgegraph processing model, y representing an indicator, if and only if>

In the case where the second entity relationship pair exists in the sample, y is 1.

According to embodiments of the present invention, mutual information is used to normalize their representations in order to avoid knowledge-graph processing models that produce too close results during the training process. Specifically, using InfoNCE (self-supervised contrast learning) loss as a constraint of the connection relationship, the following equation (12):

（12）

wherein ,

represents a connection versus a loss value, < >>

Representing the similarity between two entity-relationship pairs, set as a cosine similarity function;

Representing the first hyperparameter.

According to the embodiment of the invention, the learning capacity of the knowledge graph processing model is further improved by taking the connection relation comparison loss value as an auxiliary part. Finally, the following loss functions are used for the training of the knowledge-graph processing model:

（13）

wherein ,

represents the second hyper-parameter, < >>

Represents a third hyper-parameter, is present>

Model parameters representing a knowledge-graph processing model.

FIG. 5 shows a training diagram of a knowledge-graph processing model according to an embodiment of the invention.

As shown in fig. 5, the knowledge graph processing model may include multiple network layers, and connection relationships in the initial knowledge graph may be sufficiently mined through multiple layers of iterations, and only two network layers are shown in the figure for convenience of presentation. Inputting the initial knowledge graph into a knowledge graph processing model, in each layer of updating, obtaining the attention score of an entity relationship pair, updating the entity relationship pair of the initial knowledge graph according to the attention score, updating the relationship according to the connection relationship, and finally completing the training of the knowledge graph processing model through a scoring function to obtain the trained knowledge graph model.

In order to intuitively understand the reasonableness and effectiveness of the knowledge-graph processing model design according to the embodiment of the invention, a NELL23K data set is taken as an example for illustration.

FIG. 6 shows a schematic diagram of an example knowledge-graph processing model process according to an embodiment of the invention.

As shown in fig. 6, (pest, invertebrate diet, foliage) is one entity relationship pair to be judged from the NELL23K test set. From the attention scores, we can find a valuable path between the head entity "pest" and the tail entity "leaf": both connections between "pests" and "leaves" connected via "arthropod-containing" and "invertebrate food" have a high attention score. Obviously, these paths reflect the following rules: given (x, comprising arthropod, y) and (y, invertebrate diet, z), we may have (x, invertebrate diet, z). This not only indicates that the knowledge-map processing model can provide interpretability for the prediction result, but also indicates that the knowledge-map processing model can effectively learn endogenous relations between connection relations in the knowledge map (invertebrates include arthropods).

Based on the knowledge graph processing method, the invention also provides a knowledge graph processing device. The apparatus will be described in detail below with reference to fig. 7.

Fig. 7 shows a block diagram of the knowledge-graph processing apparatus according to an embodiment of the present invention.

As shown in fig. 7, the knowledge-graph processing apparatus 700 of this embodiment includes a first obtaining module 710, a determining module 720, and a first obtaining module 730.

A first obtaining module 710, configured to obtain a first entity-relationship pair and a second entity-relationship pair of the initial knowledge-graph, where the first entity-relationship pair includes a first head entity, a first tail entity, and a first connection relationship between the first head entity and the first tail entity, and the second entity-relationship pair includes a second head entity, a second tail entity, and a second connection relationship between the second head entity and the second tail entity; in an embodiment, the first obtaining module 710 may be configured to perform the operation S210 described above, which is not described herein again.

A determining module 720, configured to determine a third entity relationship pair based on the first attention score of the first entity relationship pair and the second attention score of the second entity relationship pair, wherein the third entity relationship pair includes the first head entity, the second tail entity, and a third connection relationship between the first head entity and the second tail entity; in an embodiment, the determining module 720 may be configured to perform the operation S220 described above, which is not described herein again.

A first obtaining module 730, configured to process the first connection relationship, the second connection relationship, and the third connection relationship to obtain a target knowledge graph. In an embodiment, the first obtaining module 730 may be configured to perform the operation S230 described above, which is not described herein again.

According to an embodiment of the present invention, the determining module 720 for determining the third entity-relationship pair based on the first attention score of the first entity-relationship pair and the second attention score of the second entity-relationship pair includes:

a first determination submodule for determining a first attention score of the first entity-relationship pair and a second attention score of the second entity-relationship pair using an attention mechanism;

a second determining submodule for determining a third connection relation satisfying a preset condition based on the first attention score and the second attention score;

and the third determining submodule is used for determining a third entity relationship pair based on the third connection relationship.

According to an embodiment of the present invention, the first obtaining module 730, configured to process the first connection relationship, the second connection relationship, and the third connection relationship, where the first connection relationship, the second connection relationship, and the third connection relationship all include I dimensions, and obtain the target knowledge graph, includes:

the first obtaining submodule is used for performing aggregation updating on the first connection relation of the ith dimension, the second connection relation of the ith dimension and the third connection relation of the ith dimension to obtain a first updating connection relation, a second updating connection relation and a third updating connection relation which respectively correspond to the first connection relation, the second connection relation and the third connection relation, I is more than or equal to 1 and less than or equal to I, and I and I are integers;

and the second obtaining submodule is used for processing the first updating connection relation, the second updating connection relation and the third updating connection relation to obtain the target knowledge graph.

According to the embodiment of the present invention, the first obtaining sub-module, configured to perform aggregation update on the first connection relationship of the ith dimension, the second connection relationship of the ith dimension, and the third connection relationship of the ith dimension, and obtain the first updated connection relationship, the second updated connection relationship, and the third updated connection relationship respectively corresponding to the first connection relationship, the second connection relationship, and the third connection relationship, includes:

the first obtaining unit is used for generating a first initial relation matrix based on the first connection relation, the second connection relation and the third connection relation, wherein a column vector in the first initial relation matrix represents a dimension, and a row vector in the first initial relation matrix represents a connection relation;

a second obtaining unit, configured to determine a target connection relationship according to the first connection relationship, the second connection relationship, and the third connection relationship;

a third obtaining unit, configured to perform relationship masking on the target connection relationship in the first initial relationship matrix to obtain a first intermediate relationship matrix;

a fourth obtaining unit, configured to determine an ith column vector from the first intermediate relationship matrix based on the first connection relationship of the ith dimension, the second connection relationship of the ith dimension, and the third connection relationship of the ith dimension;

and a fifth obtaining unit, configured to perform aggregation update on the ith column vector to obtain a first updated connection relationship, a second updated connection relationship, and a third updated connection relationship that respectively correspond to the first connection relationship, the second connection relationship, and the third connection relationship.

According to the embodiment of the present invention, the second obtaining sub-module, configured to process the first updated connection relationship, the second updated connection relationship, and the third updated connection relationship, and obtain the target knowledge graph, includes:

a sixth obtaining unit, configured to generate a second initial relationship matrix based on the first updated connection relationship, the second updated connection relationship, and the third updated connection relationship, where a column vector in the second initial relationship matrix represents a dimension, and a row vector represents a connection relationship;

a seventh obtaining unit, configured to perform dimension masking on an nth column vector in the second initial relationship matrix based on an nth dimension to obtain a second intermediate relationship matrix, where n is a positive integer;

and the eighth obtaining unit is used for processing each row vector in the second intermediate relation matrix to obtain the target knowledge graph.

According to an embodiment of the present invention, the fifth obtaining unit, configured to perform aggregation update on the ith column vector to obtain a first updated connection relationship, a second updated connection relationship, and a third updated connection relationship respectively corresponding to the first connection relationship, the second connection relationship, and the third connection relationship, includes:

the first obtaining subunit is used for performing activation operation on the ith column vector by using a first activation function to obtain an intermediate column vector;

and the second obtaining subunit is configured to perform aggregation update on the intermediate column vector according to the first weight matrix to obtain a first updated connection relationship, a second updated connection relationship, and a third updated connection relationship that respectively correspond to the first connection relationship, the second connection relationship, and the third connection relationship.

According to an embodiment of the present invention, the eighth obtaining unit, configured to process each row vector in the second intermediate relationship matrix, and obtain the target knowledge graph, includes:

the third obtaining subunit is configured to perform activation processing on the row vector by using a second activation function to obtain an intermediate row vector;

and the fourth obtaining subunit is used for aggregating the intermediate row vectors according to the second weight matrix to obtain the target knowledge graph.

Based on the training method of the knowledge graph processing model, the invention also provides a training device of the knowledge graph processing model. The apparatus will be described in detail below with reference to fig. 8.

FIG. 8 shows a block diagram of a training apparatus for a knowledge-graph processing model according to an embodiment of the present invention.

As shown in fig. 8, the training apparatus 800 of the knowledge-graph processing model of this embodiment includes a second obtaining module 810 and a second obtaining module 820.

A second obtaining module 810, configured to obtain an initial knowledge-graph sample, where the initial knowledge-graph sample includes a first entity-relationship pair sample and a second entity-relationship pair sample, the first entity-relationship pair sample is an unprocessed entity-relationship pair in an initial knowledge-graph, and the second entity-relationship pair sample is a processed entity-relationship pair in the initial knowledge-graph; in an embodiment, the second obtaining module 810 may be configured to perform the operation S410 described above, which is not described herein again.

And a second obtaining module 820, configured to train the knowledge-graph processing model by using the second entity-relationship pair sample pair as a label and using the first entity-relationship pair sample as an input, so as to obtain the trained knowledge-graph processing model. In an embodiment, the second obtaining module 820 may be configured to perform the operation S420 described above, which is not described herein again.

According to the embodiment of the present invention, any plurality of the first obtaining module 710, the determining module 720 and the first obtaining module 730 may be combined into one module to be implemented, or any one of the modules may be split into a plurality of modules. Alternatively, at least part of the functionality of one or more of these modules may be combined with at least part of the functionality of the other modules and implemented in one module. According to an embodiment of the present invention, at least one of the first obtaining module 710, the determining module 720 and the first obtaining module 730 may be implemented at least partially as a hardware circuit, such as a Field Programmable Gate Array (FPGA), a Programmable Logic Array (PLA), a system on a chip, a system on a substrate, a system on a package, an Application Specific Integrated Circuit (ASIC), or may be implemented by hardware or firmware in any other reasonable manner of integrating or packaging a circuit, or may be implemented by any one of three implementations of software, hardware and firmware, or any suitable combination of any of the three implementations. Alternatively, at least one of the first obtaining module 710, the determining module 720 and the first obtaining module 730 may be at least partially implemented as a computer program module, which when executed may perform the corresponding functions.

FIG. 9 shows a block diagram of an electronic device suitable for implementing the knowledge-graph processing method according to an embodiment of the invention.

As shown in fig. 9, an electronic apparatus 900 according to an embodiment of the present invention includes a processor 901 which can perform various appropriate actions and processes in accordance with a program stored in a Read Only Memory (ROM) 902 or a program loaded from a storage section 908 into a Random Access Memory (RAM) 903. Processor 901 may comprise, for example, a general purpose microprocessor (e.g., a CPU), an instruction set processor and/or associated chipset, and/or a special purpose microprocessor (e.g., an Application Specific Integrated Circuit (ASIC)), among others. The processor 901 may also include on-board memory for caching purposes. The processor 901 may comprise a single processing unit or a plurality of processing units for performing the different actions of the method flows according to embodiments of the present invention.

In the RAM 903, various programs and data necessary for the operation of the electronic apparatus 900 are stored. The processor 901, the ROM 902, and the RAM 903 are connected to each other through a bus 904. The processor 901 performs various operations of the method flow according to the embodiment of the present invention by executing programs in the ROM 902 and/or the RAM 903. Note that the programs may also be stored in one or more memories other than the ROM 902 and the RAM 903. The processor 901 may also perform various operations of method flows according to embodiments of the present invention by executing programs stored in the one or more memories.

Electronic device 900 may also include input/output (I/O) interface 905, input/output (I/O) interface 905 also connected to bus 904, according to an embodiment of the invention. The electronic device 900 may also include one or more of the following components connected to the I/O interface 905: an input portion 906 including a keyboard, a mouse, and the like; an output section 907 including components such as a Cathode Ray Tube (CRT), a Liquid Crystal Display (LCD), and the like, and a speaker; a storage portion 908 including a hard disk and the like; and a communication section 909 including a network interface card such as a LAN card, a modem, or the like. The communication section 909 performs communication processing via a network such as the internet. The drive 910 is also connected to the I/O interface 905 as necessary. A removable medium 911 such as a magnetic disk, an optical disk, a magneto-optical disk, a semiconductor memory, or the like is mounted on the drive 910 as necessary so that a computer program read out therefrom is mounted into the storage section 908 as necessary.

The flowchart and block diagrams in the figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams or flowchart illustration, and combinations of blocks in the block diagrams or flowchart illustration, can be implemented by special purpose hardware-based systems which perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.

It will be appreciated by a person skilled in the art that various combinations and/or combinations of features described in the various embodiments and/or in the claims of the invention are possible, even if such combinations or combinations are not explicitly described in the invention. In particular, various combinations and/or combinations of the features recited in the various embodiments and/or claims of the present invention may be made without departing from the spirit or teaching of the invention. All such combinations and/or associations fall within the scope of the present invention.

The embodiments of the present invention have been described above. However, these examples are for illustrative purposes only and are not intended to limit the scope of the present invention. Although the embodiments are described separately above, this does not mean that the measures in the embodiments cannot be used in advantageous combination. The scope of the invention is defined by the appended claims and equivalents thereof. Various alternatives and modifications can be devised by those skilled in the art without departing from the scope of the invention, and these alternatives and modifications are intended to fall within the scope of the invention.

Claims

1. A method of knowledge-graph processing, comprising:

obtaining a first entity relationship pair and a second entity relationship pair of an initial knowledge graph, wherein the first entity relationship pair comprises a first head entity, a first tail entity and a first connection relationship between the first head entity and the first tail entity, and the second entity relationship pair comprises a second head entity, a second tail entity and a second connection relationship between the second head entity and the second tail entity;

determining a third entity-relationship pair based on the first attention score of the first entity-relationship pair and the second attention score of the second entity-relationship pair, wherein the third entity-relationship pair comprises the first head entity, the second tail entity, and a third connection relationship between the first head entity and the second tail entity;

2. The method of claim 1, wherein the determining a third entity-relationship pair based on the first attention score of the first entity-relationship pair and the second attention score of the second entity-relationship pair comprises:

determining a first attention score for the first entity relationship pair and a second attention score for the second entity relationship pair using an attention mechanism;

determining the third connection relation satisfying a preset condition based on the first attention score and the second attention score;

determining a third entity relationship pair based on the third connection relationship.

3. The method of claim 1, wherein the first, second, and third connectivity relationships each include I dimensions, and wherein processing the first, second, and third connectivity relationships to obtain a target knowledge graph includes:

4. The method according to claim 3, wherein the aggregating and updating the first connection relationship of the ith dimension, the second connection relationship of the ith dimension, and the third connection relationship of the ith dimension to obtain a first updated connection relationship, a second updated connection relationship, and a third updated connection relationship respectively corresponding to the first connection relationship, the second connection relationship, and the third connection relationship comprises:

generating a first initial relation matrix based on the first connection relation, the second connection relation and the third connection relation, wherein a column vector in the first initial relation matrix represents a dimension and a row vector in the first initial relation matrix represents a connection relation;

and performing aggregation updating on the ith column vector to obtain the first updated connection relation, the second updated connection relation and the third updated connection relation which respectively correspond to the first connection relation, the second connection relation and the third connection relation.

5. The method of claim 4, wherein the processing the first updated connection relationship, the second updated connection relationship, and the third updated connection relationship to obtain a target knowledge graph comprises:

generating a second initial relation matrix based on the first updated connection relation, the second updated connection relation and the third updated connection relation, wherein a column vector in the second initial relation matrix represents a dimension and a row vector in the second initial relation matrix represents a connection relation;

performing dimension masking on the nth column vector in the second initial relation matrix based on the nth dimension to obtain a second intermediate relation matrix, wherein n is a positive integer;

and processing each row vector in the second intermediate relation matrix to obtain the target knowledge graph.

6. The method according to claim 4, wherein the performing aggregation update on the ith column vector to obtain the first updated connection relationship, the second updated connection relationship, and the third updated connection relationship respectively corresponding to the first connection relationship, the second connection relationship, and the third connection relationship includes:

and performing aggregation updating on the intermediate column vectors according to a first weight matrix to obtain the first updated connection relation, the second updated connection relation and the third updated connection relation which respectively correspond to the first connection relation, the second connection relation and the third connection relation.

7. The method of claim 5, wherein the processing each row vector in the second intermediate relationship matrix to obtain the target knowledge-graph comprises:

activating the row vector by using a second activation function to obtain an intermediate row vector;

and aggregating the intermediate row vectors according to a second weight matrix to obtain the target knowledge graph.

8. A method for training a knowledge-graph processing model, comprising:

acquiring an initial knowledge graph sample, wherein the initial knowledge graph sample comprises a first entity relationship pair sample and a second entity relationship pair sample, the first entity relationship pair sample is an unprocessed entity relationship pair in an initial knowledge graph, and the second entity relationship pair sample is a processed entity relationship pair in the initial knowledge graph;

and taking the second entity relation pair sample pair as a label, and taking the first entity relation pair sample as an input to train the knowledge graph processing model to obtain the trained knowledge graph processing model.

9. A knowledge-graph processing apparatus comprising:

a first obtaining module, configured to obtain a first entity relationship pair and a second entity relationship pair of an initial knowledge-graph, where the first entity relationship pair includes a first head entity, a first tail entity, and a first connection relationship between the first head entity and the first tail entity, and the second entity relationship pair includes a second head entity, a second tail entity, and a second connection relationship between the second head entity and the second tail entity;

a determining module to determine a third entity relationship pair based on the first attention score of the first entity relationship pair and the second attention score of the second entity relationship pair, wherein the third entity relationship pair includes the first head entity, the second tail entity, and a third connection relationship between the first head entity and the second tail entity;

10. An electronic device, comprising:

one or more processors;

a storage device for storing one or more programs,

wherein the one or more programs, when executed by the one or more processors, cause the one or more processors to perform the method of any of claims 1~8.