US 12,688,366 B2Grant
Apparatus and method for filling a knowledge graph by way of strategic data splits
Issue Date:2026-07-21
•11 Claims
•4 Drawing Sheets
Abstract
A method for filling a knowledge graph. A first and second subset of data points are determined. A data point to which a label is assigned is associated with a cluster from among a set of clusters, depending on whether a distribution of labels from data points that are already associated with the cluster satisfies a condition. Data points that are associated with the cluster are associated with the first or second subset. Models for classification are trained depending on data points from the first subset. For at least one of the models, a value of a quality factor is determined depending on data points from the second subset. A model for classification is selected from the models depending on the value. A classification that defines a relationship, node, or type of node in the knowledge graph for the sentence is determined using the selected model.
Metadata
Assignee
- ROBERT BOSCH GMBH
Inventors
- Hanna Wecker
- Annemarie Friedrich
- Heike Adel-Vu
Application Information
Application Number:US 17/357,157
Filing Date:2021-06-24
Priority Date:2020-06-29
Art Unit:2144
Classifications
IPC:
G06N5/02G06F18/20G06F18/23213G06F40/205G06F40/30
Field of Search:
G06N 5/02G06F 40/30G06F 40/205G06F 18/285G06F 18/23213
Patent Drawings (4 sheets)
Description
Cross Reference
[0001] The present application claims the benefit under 35 U.S.C. § 119 of German Patent Application No. DE 102020208041.0 filed on Jun. 29, 2020, which is expressly incorporated herein by reference in its entirety.
Field
[0002] The present invention relates to a method and an apparatus for filling a knowledge graph.
Summary
[0003] By way of a method and an apparatus in accordance with example embodiments of the present invention, a model for classifying data points, which is more suitable for unknown data points as compared with other models, is trained and is used to fill the knowledge graph.
[0004] In accordance with an example embodiment of the present invention, the method for filling the knowledge graph provides that a first subset of a set of data points and a second subset of the set of data points are determined; a data point to which a label is assigned being associated with a cluster from among a set of clusters; the data point being associated with the cluster depending on whether a distribution of labels from data points that are already associated with the cluster satisfies a condition; data points that are associated with the cluster being associated either with the first subset or with the second subset; a plurality of models for classification being trained depending on data points from the first subset; for at least one of the models from among the plurality of models, a value of a quality factor being determined depending on data points from the second subset; a model for classification being selected from the plurality of models depending on the value; a classification that defines a relationship or a node or a type of node in the knowledge graph for the sentence being determined using the model, selected depending on the value, for classification for data. The first subset encompasses training data points. The second subset encompasses development data points. Subdivision according to the distribution of the labels enables improved distribution of the data points depending on their labels, so that a distribution of the data points having the same label into the subsets can be established. The set of data points can thereby be subdivided into different subsets. The number of subsets and the number of clusters can match. The cluster defines one of the subsets.
[0005] Preferably a number of data points, which are associated with the cluster and with which the label is associated, is determined, the data point being associated with the cluster if the number satisfies a condition, and otherwise not. The number can define a maximum number of data points of the same label, which number is associated with the cluster. If the number is exceeded, the data point is, for example, associated with another cluster.
[0006] In one aspect of the present invention, a series of data points with which the label is associated is determined, the data points being associated with the cluster in accordance with the series as long as the number of data points satisfies the condition. The data points thereby become associated one after another. Data points that are placed farther back in the series are thus associated with the cluster only when the maximum number of data points has not yet been reached as a result of data points placed farther ahead of them in the series.
[0007] The series can encompass the data point, the series being determined depending on a difference between a distance of the data point from a first cluster center of a first cluster from among the set of clusters, and a distance of the data point from a second cluster center of a second cluster from among the set of clusters. The difference represents an indication of the sorting of data points in the series.
[0008] The data point is preferably placed in the series either before another data point if the difference is greater than a reference, or otherwise after the other data point in the series. The reference is a difference that is determined correspondingly for the other data point. A data point from the series having a greatest difference with respect to other data points of the series thus represents the first data point in the series. This means that the data point having the greatest difference is associated with the cluster first, and the others in decreasing order in terms of their difference.
[0009] The first cluster center is preferably that cluster center, from among the set of cluster centers, which is located closest to the data point, the second cluster center being that cluster center, from among the set of cluster centers, which is located farthest from the data point.
[0010] In accordance with an example embodiment of the present invention, provision can be made that a third cluster center is determined depending on data points that are associated with the first cluster; a fourth cluster center being determined depending on data points that are associated with the second cluster; a first distance of a first data point of the first cluster from the third cluster center, and a second distance of the first data point from the fourth cluster center, being determined; a third distance of a second data point of the second cluster from the fourth cluster center, and a fourth distance of the second data point from the third cluster, being determined; a first difference between the first distance and the second distance being determined; a second difference between the third distance and the fourth distance being determined; if the labels of the two datapoints are the same, and if the first difference satisfies a first condition and the second difference satisfies a second condition, the first data point being associated with the second cluster, and the second data point with the first cluster. It is thereby possible to perform an exchange of data points if two data points exist which are farther from their respective cluster center than from the respective other cluster center. This improves clustering, or more precisely intra-cluster density, i.e. the fact that the respective clusters have their points as close together as possible, since the data points that are located farthest from their current cluster center are then exchanged with the highest priority.
[0011] Provision can be made that a plurality of cluster centers is furnished, data points from among the set of data points being associated with one of the cluster centers from among the plurality of cluster centers. The data points can thereby be associated with a plurality of subsets.
[0012] Preferably a number of subsets for the data points is predefined, the number of subsets defining the number of cluster centers. For example, K cluster centers can be predefined, a first subset being constituted from K−1 clusters, and a second subset from the remaining one cluster.
[0013] In accordance with an example embodiment of the present invention, a method for generating training data provides that a first subset of a set of data points and a second subset of the set of data points are determined; a data point to which a label is assigned being associated with one cluster from among a set of clusters; the data point being associated with the cluster depending on whether a distribution of labels from data points that are already associated with the cluster meets a condition; data points that are associated with the cluster being associated either with the first subset or with the second subset.
[0014] In accordance with an example embodiment of the present invention, the apparatus is embodied to execute the method(s) disclosed herein.
[0015] Further advantageous embodiments are evident from the description below and from the figures.
Brief Description of the Drawings
[0016] FIG. 1 schematically depicts an apparatus for filling a knowledge graph, in accordance with an example embodiment of the present invention.
[0017] FIG. 2 shows steps in a method for filling the knowledge graph, in accordance with an example embodiment of the present invention.
[0018] FIG. 3 shows details of a step of the method, in accordance with an example embodiment of the present invention.
Detailed Description of Example Embodiments
[0019] FIG. 1 schematically depicts portions of an apparatus 100 for filling a knowledge graph. Apparatus 100 encompasses at least one processor 102 and at least one memory 104, and is embodied to execute the method described below.
[0020] A set of data points 106 is stored in the at least one memory 104. In the example, a data point from the set is defined by an embedding of a word, of a sentence, of a partial sentence, or of one or more word sequences, and by a label. The embedding of the sentence can be determined from embeddings of words of the sentence. The other embeddings can be determined correspondingly from embeddings of words. Preferably, a vector for the embedding of the sentence is determined. Preferably, the vector is normalized to one. Vectors that are likewise normalized to one can be determined for the embeddings of the words of the sentence.
[0021] A word2vec embedding can be used for the words. This is implemented, for example, as described in Tomas Mikolov, Kai Chen, Greg Corrado, Jeffrey Dean, “Efficient Estimation of Word Representations in Vector Space,” ICLR Workshop 2013.
[0022] In the example, a set of labels is predefined. One of those labels is associated with the data point.
[0023] In the example, a text corpus that contains the sentence is provided. In the example, the procedure for other sentences of the text corpus is as described for the data point. The set of data points 106 encompasses a plurality of data points for a plurality of sentences from the text corpus. Different text corpora can also be provided. The text corpus can derive from a domain. The different text corpora can derive from the same domains or different domains.
[0024] Apparatus 100 encompasses a model 108 for classification. Model 108 is embodied to associate an embedding of a sentence, for example from a data point from among the set of data points, with a label. In the example, the label defines a relationship for the sentence in a knowledge graph. Apparatus 100 is embodied to select, from among a plurality of models, that model 108 with which the knowledge graph is filled.
[0025] FIG. 2 shows steps in a method for filling the knowledge graph.
[0026] The method provides a step 202 in which input data are furnished. The input data encompass the set of data points.
[0027] In a step 204, at least one data point to which a label is assigned is associated with a cluster from among a set of clusters. The data point is associated either with a first cluster or with a second cluster, depending on whether or not a distribution of labels from data points that are already associated with the cluster satisfies a condition. This aspect will be described in more detail below with reference to FIG. 3 .
[0028] In the example, a number K of clusters is generated for the data points of the set of data points, which clusters can encompass data points having the same labels and/or ones different from one another. Provision can be made to associate each data point with exactly one cluster.
[0029] In a step 206, depending on the K clusters a first subset of the set of data points having training data points, and a second subset of the set of data points having development data points, are furnished. In the example, a set of training data points which encompasses data points from K−1 of the clusters is furnished. In the example, a set of development data points is furnished which encompasses data points from one of the clusters. This aspect will be described in further detail below with reference to FIG. 3 .
[0030] Preferably, the second subset is not contained in the set of training data points. Preferably, the set of development data points does not encompass the first subset or any of the data points from one of the K−1 clusters.
[0031] Provision can be made to provide a subdivision differing from an association of K−1 clusters with the first subset and of one cluster with the second subset.
[0032] In a step 208, a plurality of models for classification are trained in a plurality of epochs, depending on data points from the first subset.
[0033] At least one model from among the plurality of models can be an artificial neural network that is defined by its hyperparameters. Different models from among the plurality of models can be artificial neural networks having different hyperparameters. In training, the weights of the respective artificial neural network are adapted. Preferably, training occurs in several epochs with the training data points from among the set of training data points. In one aspect, the hyperparameters of the artificial neural network remain unmodified in the training process.
[0034] In a step 210, a value of a quality factor is determined, depending on data points from the second subset, for at least one of the models from among the plurality of models. The value can be an indication of a conformity of the label from the classification of the embeddings from the data points of the second subset by the at least one model with the labels from those data points. In the example, the value is determined for the plurality of models.
[0035] In a step 212, a model for classification is selected, depending on the value, from among the plurality of models. In the example, the model selected is the one that best executes the classification of the development data points in accordance with the value.
[0036] Steps 208 to 212 can be repeated. Provision can be made to determine an average of the values of the models from the repetitions, and to select the model depending on the average.
[0037] In a step 214, a set of data is furnished. In the example, the data encompass an embedding of a sentence from a text corpus. The embedding can be determined in the manner described for the data point from among the set of data points. In the example, the data do not encompass a label. In the example, the data are determined from a text corpus other than the text corpus or corpora that were used for determining the set of data points.
[0038] In a step 216, a classification that defines a relationship in the knowledge graph for the sentence is determined using the model, selected depending on the value, for classification for data from among the set of data.
[0039] FIG. 3 shows details of step 204 of the method.
[0040] In a step 302, a plurality of cluster centers are furnished.
[0041] One of the cluster centers is associated with a cluster from among a set of clusters. In the example, one cluster from among the set of clusters is associated with each of the cluster centers. In step 302, a number of clusters for the data points is predefined. In the example, the number of clusters defines the number of cluster centers. For example, K cluster centers for K clusters can be predefined. Different sizes of clusters can be provided. For example, N data points can be provided for the second subset, (K−1)*N data points being provided for the first subset. The set of training data points thus encompasses (K−1)*N of the data points, and the set of development data points encompasses N of the data points. Provision is made, for example, that the N data points from one cluster are to constitute the second subset. In this example, the other (K−1)*N data points, which are associated with others of the K clusters, are to constitute the first subset.
[0042] The cluster centers are initialized or determined, for example, as described for the k-means++ algorithm in: David Arthur and Sergei Vassilivitskii, “k-means++: The Advantages of Careful Seeding,” http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf.
[0043] In a step 304, a series of data points with which the label is associated is determined.
[0044] In the example, the series is determined depending on a difference between a distance of a data point from a first cluster center of a first cluster from among the set of clusters, and a distance of the data point from a second cluster center of a second cluster from among the set of clusters.
[0045] In the example, the first cluster center is that cluster center from among the set of cluster centers which is located closest to the data point. In the example, the second cluster center is that cluster center from among the set of cluster centers which is located farthest from the data point.
[0046] For example, the data point is placed before another data point in the series if the difference is greater than a reference. Otherwise the datapoint is placed after the other data point in the series. A data point having the greatest difference with respect to the other data points is therefore placed as the first data point in the series. The others are then placed so as to be sorted in order of decreasing difference.
[0047] In the example, a series is determined for a plurality of labels.
[0048] A respective number of data points that are already associated with the respective cluster, and with which the respective label is associated, is then determined For the plurality of clusters for the plurality of labels.
[0049] In a step 306, the data points are associated with the clusters.
[0050] In the example, the data point is associated with the cluster if the number of data points that are associated with the cluster for the label satisfies a condition. The condition can define a predefined maximum number of data points that can be associated with the cluster. This means that an association is determined depending on whether or not a distribution of labels from data points that are already associated with the cluster satisfies a condition.
[0051] In the aspect in which the series is determined, the data points are associated in series with the cluster until the number of data points satisfies the condition.
[0052] In the example, data points from among the set of data points are associated with one of the cluster centers from among the plurality of cluster centers in the manner described for the data point.
[0053] In an optional step 308, pairs of data points from different clusters, which points are suitable for the purpose and whose labels match, can be exchanged. This will be described below for one pair. A corresponding test can be performed for a plurality of data points.
[0054] In a step 308-A, a third cluster center is determined depending on data points that are associated with the first cluster. The third cluster center is a new cluster center for the first cluster.
[0055] In a step 308-B, a fourth cluster center is determined depending on data points that are associated with the second cluster. The fourth cluster center is a new cluster center for the second cluster.
[0056] In a step 308-C, a first distance of a first data point of the first cluster from the third cluster center, and a second distance of the first data point from the fourth cluster center, are determined.
[0057] In a step 308-D, a third distance of a second data point of the second cluster from the fourth cluster center, and a fourth distance of the second data point from the third cluster center, are determined.
[0058] In a step 308-E, a first difference between the first distance and the second distance is determined.
[0059] In a step 308-F, a second difference between the third distance and the fourth distance is determined.
[0060] A step 308-G checks whether the first difference satisfies a first condition and the second difference satisfies a second condition.
[0061] In the example, in a step 308-H, if both conditions are satisfied, the first data point is associated with the second cluster and the second data point with the first cluster. These data points are thus exchanged with one another. Otherwise the data points are not exchanged with one another.
[0062] Steps 308-A to 308-H can be performed in this or another sequence for various data points. Preferably, the steps are repeated until no further pairs suitable for exchange are discovered.
[0063] In a subsequent step 310, data points that are associated with the cluster are associated either with the first subset or with the second subset.
[0064] In the example, the data points associated with the first cluster are associated with the first subset. In the example, the data points associated with the second cluster are associated with the second subset.
[0065] Provision can be made that data points from a plurality of clusters are associated with the first subset or with the second subset, depending on which cluster they are associated with.
Claims
What is claimed is:
1. A method for filling a knowledge graph, comprising the following steps:
determining a first subset of a set of data points and a second subset of the set of data points;
associating a data point to which a label is assigned with a cluster from among a set of clusters, the data point being associated with the cluster in response to a distribution of labels from data points that are already associated with the cluster satisfies a condition;
associating data points that are associated with the cluster either with the first subset or with the second subset;
training a plurality of models for classification depending on data points from the first subset;
determining, for at least one of the trained models from among the plurality of trained models, a value of a quality factor depending on data points from the second subset;
selecting a trained model for classification from the plurality of trained models depending on the value; and
determining a classification that defines a relationship or a node or a type of node in the knowledge graph for a sentence using the trained model, selected depending on the value, for classification for data.
2. The method as recited in claim 1, wherein a number of data points, which are associated with the cluster and with which the label is associated, is determined, the data point being associated with the cluster if the number satisfies a condition, and otherwise not being associated.
3. The method as recited in claim 2, wherein a series of data points with which the label is associated is determined, the data points being associated with the cluster in accordance with the series as long as the number of data points satisfies the condition.
4. The method as recited in claim 3, wherein the series encompasses the data point, the series being determined depending on a difference between a distance of the data point from a first cluster center of a first cluster from among the set of clusters, and a distance of the data point from a second cluster center of a second cluster from among the set of clusters.
5. The method as recited in claim 4, wherein the data point is placed in the series either before another data point if the difference is greater than a reference, or otherwise after the other data point in the series.
6. The method as recited in claim 4, wherein the first cluster center is that cluster center, from among the set of cluster centers, which is located closest to the data point, the second cluster center being that cluster center, from among the set of cluster centers, which is located farthest from the data point.
7. The method as recited in claim 6, further comprising:
determining a third cluster center depending on data points that are associated with the first cluster;
determining a fourth cluster center depending on data points that are associated with the second cluster;
determining a first distance of a first data point of the first cluster from the third cluster center, and a second distance of the first data point from the fourth cluster center;
determining a third distance of a second data point of the second cluster from the fourth cluster center, and a fourth distance of the second data point from the third cluster;
determining a first difference between the first distance and the second distance;
determining a second difference between the third distance and the fourth distance; and
based on the labels of the first and second data points being the same, and based on the first difference satisfying a first condition and the second difference satisfying a second condition, associating the first data point with the second cluster, and the second data point with the first cluster.
8. The method as recited in claim 1, wherein a plurality of cluster centers is furnished, data points from among the set of data points being associated with one of the cluster centers from among the plurality of cluster centers.
9. The method as recited in claim 8, wherein a number of subsets for the data points is predefined, the number of subsets defining a number of cluster centers.
10. An apparatus configured to fill a knowledge graph, the apparatus configured to:
determine a first subset of a set of data points and a second subset of the set of data points;
associate a data point to which a label is assigned with a cluster from among a set of clusters, the data point being associated with the cluster in response to a distribution of labels from data points that are already associated with the cluster satisfies a condition;
associate data points that are associated with the cluster either with the first subset or with the second subset;
train a plurality of models for classification depending on data points from the first subset;
determine, for at least one of the trained models from among the plurality of trained models, a value of a quality factor depending on data points from the second subset;
select a trained model for classification from the plurality of trained models depending on the value; and
determine a classification that defines a relationship or a node or a type of node in the knowledge graph for a sentence using the trained model, selected depending on the value, for classification for data.
11. A non-transitory computer-readable medium on which is stored a computer program including computer-readable instructions for filling a knowledge graph, the instructions, when executed by a computer, causing the computer to perform the following steps:
determining a first subset of a set of data points and a second subset of the set of data points;
associating a data point to which a label is assigned with a cluster from among a set of clusters, the data point being associated with the cluster in response to a distribution of labels from data points that are already associated with the cluster satisfies a condition;
associating data points that are associated with the cluster either with the first subset or with the second subset;
training a plurality of models for classification depending on data points from the first subset;
determining, for at least one of the trained models from among the plurality of trained models, a value of a quality factor depending on data points from the second subset;
selecting a trained model for classification from the plurality of trained models depending on the value; and
determining a classification that defines a relationship or a node or a type of node in the knowledge graph for a sentence using the trained model, selected depending on the value, for classification for data.
Patent Citations (10)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US10719301(B1) | 2020-07-01 | Dasgupta | Examiner |
| US11379501(B2) | 2022-07-01 | Yadav | Examiner |
| US2009/0319457(A1) | 2009-12-01 | Cheng et al. | Applicant |
| US2013/0097103(A1) | 2013-04-01 | Chari et al. | Applicant |
| US2017/0293608(A1) | 2017-10-01 | Seow | Examiner |
| US2021/0097140(A1) | 2021-04-01 | Chatterjee | Examiner |
| US2021/0248193(A1) | 2021-08-01 | Cho | Examiner |
| CN106991296(A) | 2017-07-01 | Applicant | |
| CN110413856(A) | 2019-11-01 | Applicant | |
| JP2019185665(A) | 2019-10-01 | Applicant |
Non-Patent Literature (11)
- Alessandro Lulli, etc., “Scalable k-NN based text clustering”, published via 2015 IEEE International Conference on Big Data, Santa Clara, CA, USA, Oct. 29-Nov. 1, 2015, retrieved Dec. 5, 2024. (Year: 2015).Examiner
- Liang Yao, etc., “Graph Convolutional Networks for Text Classification”, published via arXiv as of Nov. 13, 2018, retrieved Dec. 5, 2024. (Year: 2018).Examiner
- Smail Sellah, etc., “A Document Clustering Approach for Automatic Building of Ontologies”, published via 2018 Fifth International Conference on Social Networks Analysis, Management and Security, Valencia, Spain, Oct. 15-18, 2018, retrieved Dec. 5, 2024. (Year: 2018).Examiner
- Derek Greene, etc., “TextLuas: Tracking and Visualizing Document and Term Clusters in Dynamic Text Data”, published via arXiv as of Nov. 3, 2014, retrieved Dec. 5, 2024. (Year: 2014).Examiner
- Lirong Qiu, etc., “Chinese-Uyghur-English Semantic Search Based on the Knowledge Graphs”, 2017 IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC), Jul. 21-24, 2017, retrieved Dec. 5, 2024. (Year: 2017).Examiner
- Xiaoli Wang, etc., “An Improved K_means Algorithm for Document Clustering Based on Knowledge Graphs”, published via 2018 11th International Congress on Image and Signal Processing, BioMedical Engineering and Informatics, Oct. 13-15, 2018, retrieved Dec. 5, 2024. (Year: 2018).Examiner
- John Violos, etc., “Text Classification Using the N-Gram Graph Representation Model Over High Frequency Data Streams”, published via Frontiers in Applied Mathematics and Statistics, vol. 4, article 41, Sep. 2018, retrieved Dec. 5, 2024. (Year: 2018).Examiner
- Mikolov et al., “Efficient Estimation of Word Representations in Vector Space,” ICLR Workshop, 2013, pp. 1-12. <https://arxiv.org/pdf/1301.3781.pdf> Downloaded Jun. 24, 2021.Applicant
- Arthur et al., “K-Means++: the Advantages of Careful Seeding,” Proceedings of the Eighteenth Annual Acm-Siam Symposium on Discrete Algorithms, 2007, pp. 1-11. <http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf> Downloaded Jun. 24, 2021.Applicant
- Wecker et al., “Clusterdatasplit: Exploring Challenging Clustering-Based Data Splits for Model Performance Evaluation,” Proceedings of the First Workshop on Evaluation and Comparison of NLP Systems (EVAL4NLP ), 2020, pp. 155-163.Applicant
- Vanderplas, “Hyperparameters and Model Validation,” Python Data Science Handbook, 2016, pp. 1-19.Applicant