DETAILED ACTION
This nonfinal action is in response to application 18/057,740 filed 11/21/2022 with priority to foreign application JP2021-189955 filed on 11/24/2021. Claims 1-9 are pending in the case. Claims 1, 4, and 7 are independent claims.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Information Disclosure Statement
The information disclosure statements (IDS) filed 11/21/2022 and 06/29/2023 have been considered by the examiner.
The examiner has noted the presence of a search report for a related foreign application (App. No. EP.22208041.A) – the references referred to therein have also been considered.
Drawings
The drawings are objected to because of the following informality:
In Fig. 4A, “Positive Example 1: RUG A – DISEASE – X DISEASE” should read “Positive Example 1: DRUG A – DISEASE – X DISEASE” – correction of the typographical error is requested.
Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended.” If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Specification
The specification is objected to because the title of the invention is not descriptive. A new title is required that is clearly indicative of the invention to which the claims are directed.
Claim Objections
Claims 1, 3, and 6 are objected to because of the following informalities:
In claims 1, 3, and 6, “one or more graphs each having a subject, a predicate, and an object” should read “one or more graphs, each graph having a subject, a predicate, and an object” for improved clarity
In claims 1, 3, and 6, “one or more negative example graphs each having a subject, a predicate, and an object” should read “one or more negative example graphs, each negative example graph having a subject, a predicate, and an object” for improved clarity.
In claims 1, 3, and 6, the “generating a negative example graph dataset…” step recites a number of sub-elements/sub-steps without sufficient organization and/or punctuation to clearly delineate between them, resulting in a lack of clarity. An alternate recitation of the claim to improve clarity (along with addressing indefiniteness issues) has been suggested below (see Claim Rejections – 35 USC § 112 interpretation of claim 1).
Appropriate corrections are required.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-9 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Regarding claim 1, it initially recites “acquiring a graph dataset that includes one or more graphs each having a subject, a predicate, and an object”, and then later recites “setting the acquired graph dataset as a positive example graph dataset that includes one or more positive example graphs”. However, the claim does not explicitly state the “positive example graphs” as being equivalent to the previously recited “graphs”. As such, when the claim later recites “a predicate of each negative example graph being same as a predicate of one of the positive example graphs”, the term “a predicate of one of the positive example graphs” has insufficient antecedent basis, because the “positive example graphs” were not previously recited as having a predicate. Consequently, one of ordinary skill in the art would not be reasonably apprised of the scope of the invention.
Claim 1 further recites “an object of the negative example graph being different from an object of the one of the positive example graphs”. The term “the negative example graph” has insufficient antecedent basis – the claim previously recited “each negative example graph”, but did not recite any particular negative example graph within the “one or more negative example graphs”, such that it is unclear what particular element “the negative example graph” may be referring to. Additionally, for similar reasons to those stated above regarding the term “a predicate of one of the positive example graphs”, the term “an object of the one of the positive example graphs” also has insufficient antecedent basis. Consequently, one of ordinary skill in the art would not be reasonably apprised of the scope of the invention.
Claim 1 further recites “the negative example graph being excluded from the negative example graph dataset when the object of the negative example graph is different from each object to which a predicate of any other of the positive example graphs is linked”.
For similar reasons to those stated above, the term “the negative example graph” has insufficient antecedent basis. It is further unclear what is meant by “the negative example graph being excluded from the negative example graph dataset”. The phrase is recited in past tense, indicating that the current negative example graph element was never a part of the recited “negative example graph dataset” – however, all negative example graph elements are first recited in the claims as being included within the negative example graph dataset (“a negative example graph dataset that includes one or more negative example graphs”). It is therefore unclear if the phrase is reciting removing negative example graphs from the negative example graph dataset when they meet a particular condition, or is instead reciting avoiding generation entirely of a particular type of negative example graph within the negative example graph dataset. Consequently, one of ordinary skill in the art would not be reasonably apprised of the scope of the invention.
For similar reasons to those stated above, the terms “the object of the negative example graph” and “a predicate of any other of the positive example graphs” also have insufficient antecedent basis. It is further unclear what the term “each object to which a predicate of any other of the positive example graphs is linked” refers to. Even assuming that there exists a predicate for each positive example graph, it is unclear what is meant by “any other” of the positive example graphs, as the claim does not clearly establish what particular claim element (or elements) the phrase is in relation to – for example, the phrase could be referring to all existing positive example graphs besides the previously recited “one of the positive example graphs”, or could be referring to all existing positive example graphs that share the same “predicate” as the previously recited “one of the positive example graphs”. It is further unclear if “a predicate” is reciting the same predicate element as “a predicate of one of the positive example graphs”, or is reciting an entirely separate claim element. Consequently, one of ordinary skill in the art would not be reasonably apprised of the scope of the invention.
For purposes of examination and as best understood in light of the instant specification (see [¶ 0060-0068] describing Embodiment 1 and generation of negative example datasets), the examiner has interpreted claim 1 as follows:
A non-transitory computer-readable storage medium storing an information processing program that causes at least one computer to execute a process, the process comprising:
acquiring a graph dataset that includes one or more graphs, each graph having a subject, a predicate, and an object from a knowledge graph;
setting the acquired graph dataset as a positive example graph dataset, and setting the graphs of the acquired graph dataset as positive example graphs;
creating negative example graphs based on the positive example graphs, each negative example graph having a subject, a predicate, and an object;
generating a negative example graph dataset that includes one or more of the negative example graphs, the generating further comprising:
for each negative example graph of the negative example graph dataset, the predicate of the negative example graph being the same as the predicate of a particular positive example graph of the positive example graphs, and the object of the negative example graph being different from the object of the particular positive example graph;
excluding, from the negative example graph dataset, any negative example graph wherein its object is different from every object to which a predicate of any other positive example graph that has the same predicate as the particular positive example graph is linked; and
training for embedding in the knowledge graph by using the positive example graph dataset and the negative example graph dataset.
Regarding claim 2, it inherits the deficiencies of its parent claim. Additionally, it is further unclear what is meant by “the negative example graph dataset having an object in a class that is same as a class of the object of the graph dataset when the class of the object of the graph dataset and the class of the object of the negative example graph dataset is set in an ontology”, as object[s] were previously recited in the parent claim as being incorporated within the recited negative example graphs or graphs elements themselves, rather than the recited datasets. Consequently, the terms “the object of the graph dataset” and “the object of the negative example graph dataset” have insufficient antecedent basis, and one of ordinary skill in the art would not be reasonably apprised of the scope of the invention.
It is further unclear as to why the limitations of claim 2 are recited with the “graph dataset” elements instead of the “positive graph dataset” elements, as this recitation incites confusion regarding the interrelation of claim elements, and appears inconsistent with the associated written description in the specification ((see [¶ 0087-0088, 0090-0092] describing Embodiment 2). This inconsistency between the claimed subject matter and the specification disclosure renders the scope of the claim uncertain, such that one of ordinary skill in the art would no longer be reasonably apprised of the scope of the invention.
For purposes of examination and as best understood in light of the instant specification (see [¶ 0087-0088, 0090-0092] describing Embodiment 2), the examiner has interpreted claim 2 as follows: The non-transitory computer-readable storage medium according to claim 1, wherein generating the negative example graph dataset further comprises:
for each negative example graph of the negative example graph dataset, the object of the negative example graph and the object of the particular positive example graph being in a same class, wherein the class is set in an ontology.
Regarding claim 3, it inherits the deficiencies of its parent claims. It is further unclear what is meant by “when at least one class of selected from the object of the graph dataset and the class of the object of the negative example graph dataset is set out of the ontology, generating the negative example graph dataset having the object in a class that is same as a class of the object of the graph dataset by predicting a class of an object that is not set”. For similar reasons to those stated above, the terms “the object of the graph dataset” and “the object of the negative example graph dataset” have insufficient antecedent basis. It further unclear what “at least one class of selected from [the object]” refers to, as the claim does not previously recite “select[ing]” a class from an object. Additionally, it is unclear if the claim is intended to recite “predicting a class of an object that is not set” as a step performed prior to “generating the negative example graph dataset”, as would appear consistent with the instant specification (see [¶ 0109-0110, 0112-0115] describing Embodiment 3), or is reciting “predicting” as a sub-step of generating the negative example graph dataset”. It is further unclear what “an object that is not set” refers to – the claim previously recites classes being either “set in an ontology” or “set out of the ontology”, but does not previously recite a relationship between objects and “the ontology” – there is therefore uncertainty regarding whether or not the recitation of an object not being “set” is in reference to “the ontology”, or if being “not set” and “set out of the ontology” have the same meaning. Consequently, one of ordinary skill in the art would not be reasonably apprised of the scope of the invention.
For purposes of examination and as best understood in light of the instant specification (see [¶ 0109-0110, 0112-0115] describing Embodiment 3), the examiner has interpreted claim 3 as follows:
The non-transitory computer-readable storage medium according to claim 2, wherein the process comprises:
prior to generating the negative example graph dataset, when an object of a graph of the acquired graph dataset is set out of the ontology, predicting a class of the object, and
using the predicted class as the class of the object when generating the negative example graph dataset.
Regarding claims 4-6 and 7-9, they have substantially similar deficiencies to those found in claims 1-3. Consequently, they are rejected as being indefinite for the same reasons as claims 1-3, and are likewise interpreted as set forth above.
Applicant is advised to consider other parts of the disclosure, including the specification and drawings, for clarity and indefiniteness issues similar to those raised above. The examiner notes that any amendments made to the specification, claims, or drawings must only contain subject matter that is supported by the originally filed disclosure in order to avoid being rejected under U.S.C. 112(a) as new matter (see MPEP § 608.04). Additionally, any interpretations of indefinite claim language as detailed above are made solely for the purpose of examining the instant application on the merits, and are not attested as being adequately supported by the disclosure or adequately resolving all indefiniteness issues raised.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-9 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. The analysis of the claims will follow the 2019 Revised Patent Subject Matter Eligibility Guidance, 84 Fed. Reg. 50 (“2019 PEG”).
Independent Claims (Claim 1, Claim 4, Claim 7):
Step 1: Claim 1 is drawn to a product, claim 4 is drawn to a system/apparatus, and claim 7 is drawn to a method. Therefore, each of these claims falls under one of the four categories of statutory subject matter (process/method, machine/apparatus, manufacture/product, or composition of matter).
Step 2A Prong 1: Claims 1, 4, and 7 each recite a judicially recognized exception of an abstract idea.
Claim 1 recites, inter alia:
setting the acquired graph dataset as a positive example graph dataset that includes one or more positive example graphs; – This limitation amounts to merely observing existing graph data representing examples of subject-predicate-object relationships, and recognizing said data as “positive”, i.e., real; it therefore recites a step with respect to evaluating relationship data that a human could reasonably perform in the mind or using pen and paper.
generating a negative example graph dataset that includes one or more negative example graphs each having a subject, a predicate, and an object, a predicate of each negative example graph being same as a predicate of one of the positive example graphs, an object of the negative example graph being different from an object of the one of the positive example graphs, – This limitation amounts to a process of generating, based on observing existing “positive” graph data representing examples of subject-predicate-object relationships (e.g., two nodes in a knowledge graph connected by an edge, the nodes representing subject/object relationship entities and the edge representing a predicate, i.e., relation between them), “negative”, i.e., corrupted/modified examples of these relationships by changing the object to a different entity. For example, a person could observe in a knowledge graph a head node, i.e., subject (e.g., having value “Sky”), and tail node, i.e., object (e.g., having value “Blue”), connected by an edge, i.e., relation (e.g., having value “Color”) in a knowledge graph, as an example, and “generate” a modified example having head node “Sky”, edge “Color”, and new tail node “Red”. Therefore, the limitation recites steps with respect to evaluating relationship data that a human could reasonably perform in the mind or using pen and paper.
the negative example graph being excluded from the negative example graph dataset when the object of the negative example graph is different from each object to which a predicate of any other of the positive example graphs is linked; – This limitation amounts to a further process step, after “generating” a modified example, of observing the object node, i.e., relationship entity, of the modified example, comparing the object node to object nodes from previously existing “positive” examples, and based on said comparison, determining whether the object node is in some way “different” from the existing nodes and should be excluded from a formed group of modified examples. Therefore, the limitation further recites steps with respect to evaluating relationship data that a human could reasonably perform in the mind or using pen and paper.
Claims 4 and 7 recite substantially similar abstract idea limitations to those recited in claim 1, and therefore recite the same judicial exception.
Step 2A Prong 2: The following additional elements recited in claims 1, 4, and 7 do not integrate the recited judicial exceptions into a practical application.
Claim 1 additionally recites:
A non-transitory computer-readable storage medium storing an information processing program that causes at least one computer to execute a process, the process comprising: – The elements recited in the preamble amount to no more than mere instructions to implement an abstract idea on a computer or computer components.
acquiring a graph dataset that includes one or more graphs each having a subject, a predicate, and an object from a knowledge graph; – This limitation amounts to a mere pre-solution step of gathering data in order to perform an existing mental process of evaluating relationship data, and therefore recites insignificant extra-solution activity.
training for embedding in the knowledge graph by using the positive example graph dataset and the negative example graph dataset – This limitation merely recites a generic training step of a graph embedding model using results of the claimed procedure, and therefore does no more than generally linking the recited judicial exception to the technological environment of knowledge graph embedding models without providing anything more (e.g., specific details that would adequately reflect an improvement to conventional technology).
Claim 4 recites substantially similar additional elements to those recited in claim 1, and further recites:
An information processing apparatus comprising: one or more memories; and one or more processors coupled to the one or more memories and the one or more processors configured to: – The elements recited in the preamble amount to no more than mere instructions to implement an abstract idea on a computer or computer components.
Claim 7 recites substantially similar additional elements to those recited in claim 1, and further recites:
An information processing method for a computer to execute a process comprising: – The elements recited in the preamble amount to no more than mere instructions to implement an abstract idea on a computer or computer components.
Step 2B: The additional elements recited in claims 1, 4, and 7, viewed individually or as an ordered combination, do not provide an inventive concept or otherwise amount to significantly more than the recited abstract ideas themselves.
Claim 1 additionally recites:
A non-transitory computer-readable storage medium storing an information processing program that causes at least one computer to execute a process, the process comprising: – Mere instructions to implement an abstract idea on a computer or computer components do not provide an inventive concept or significantly more to the recited abstract idea.
acquiring a graph dataset that includes one or more graphs each having a subject, a predicate, and an object from a knowledge graph; – Receiving and transmitting data is well-understood, routine, and conventional activity (see MPEP § 2106.05(d); “Storing and retrieving information in memory”, “Receiving or transmitting data over a network”) and therefore does not provide an inventive concept or significantly more to the recited abstract idea.
training for embedding in the knowledge graph by using the positive example graph dataset and the negative example graph dataset – Generally linking the recited judicial exception to the technological environment of knowledge graph embedding models without providing anything more (e.g., specific details that would adequately reflect an improvement to conventional technology) does not provide an inventive concept or significantly more to the recited abstract idea.
Claim 4 recites substantially similar additional elements to those recited in claim 1, and further recites:
An information processing apparatus comprising: one or more memories; and one or more processors coupled to the one or more memories and the one or more processors configured to: – Mere instructions to implement an abstract idea on a computer or computer components do not provide an inventive concept or significantly more to the recited abstract idea.
Claim 7 recites substantially similar additional elements to those recited in claim 1, and further recites:
An information processing method for a computer to execute a process comprising: – Mere instructions to implement an abstract idea on a computer or computer components do not provide an inventive concept or significantly more to the recited abstract idea.
Even when considered as an ordered combination, the additional elements recited in the claims ultimately do no more than recite insignificant data gathering steps and generally link the recited judicial exception to the technological environment of knowledge graph embedding models without providing anything more. As such, claims 1, 4, and 7 are not patent eligible.
Dependent Claims (Claims 2-3, Claims 5-6, Claims 8-9):
Dependent claims 2-3, 5-6, and 8-9 narrow the scope of independent claims 1, 4, and 7, and thus merely narrow the recited judicial exceptions. With respect to the independent claims, the recited judicial exceptions are not meaningfully integrated into a practical application, and also do not amount to significantly more than the recited abstract ideas themselves. The dependent claims recite abstract idea limitations similar to those recited within the independent claims, as they also do not provide anything more than mathematical concepts or mental processes that are capable of being performed in the human mind and/or using pen and paper. The dependent claims also do not recite any further additional elements that successfully integrate the recited judicial exceptions into a practical application or amount to significantly more than the recited abstract ideas themselves. Consequently, claims 2-3, 5-6, and 8-9 are also rejected under 35 U.S.C. 101.
Step 1: Claims 2-3 are drawn to a product, claim 5-6 are drawn to a system/apparatus, and claims 8-9 are drawn to a method. Therefore, each of these claims falls under one of the four categories of statutory subject matter (process/method, machine/apparatus, manufacture/product, or composition of matter).
Step 2A Prong 1: Claims 2-3, 5-6, and 8-9 each recite a judicially recognized exception of an abstract idea.
Claim 2 recites, inter alia:
wherein the generating includes generating the negative example graph dataset having an object in a class that is same as a class of the object of the graph dataset when the class of the object of the graph dataset and the class of the object of the negative example graph dataset is set in an ontology – This limitation amounts to a further process step with respect to evaluating relationship data – namely, determining whether a modified example should be included within a formed group of modified examples by comparing the “class”, or type, of the object node, i.e., relationship entity, of the modified example with the types of object nodes from previously existing “positive” examples. Therefore, the limitation further recites steps with respect to evaluating relationship data that a human could reasonably perform in the mind or using pen and paper.
Claim 3 recites, inter alia:
wherein the generating includes, when at least one class of selected from the object of the graph dataset and the class of the object of the negative example graph dataset is set out of the ontology, generating the negative example graph dataset having the object in a class that is same as a class of the object of the graph dataset by predicting a class of an object that is not set. – This limitation amounts to a further step with respect to the recited process of evaluating relationship data – namely, determining whether or not a newly observed object node, i.e., relationship entity, corresponds in “class”, or type, to previously existing object nodes, and if not, determining an appropriate designation based on reasoning. Therefore, the limitation further recites steps with respect to evaluating relationship data that a human could reasonably perform in the mind or using pen and paper.
Claims 5-6 and 8-9 recite substantially similar abstract idea limitations to those recited in claims 2-3, and therefore recite the same judicial exceptions.
Step 2A Prong 2: Claims 2-3, 5-6, and 8-9 do not recite any further additional elements besides those recited in the independent claims, and therefore do not integrate the recited judicial exceptions into a practical application.
Step 2B: Claims 2-3, 5-6, and 8-9 do not recite any further additional elements besides those recited in the independent claims, and therefore do not provide an inventive concept or otherwise amount to significantly more than the recited abstract ideas themselves.
As such, claims 2-3, 5-6, and 8-9 also are not patent eligible.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1-2, 4-5, and 8-9 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Krompaß et al., (“Type-Constrained Representation Learning in
Knowledge Graphs”, available arXiv 28 Aug 2015) hereinafter Krompass.
Regarding claim 1, Krompass discloses A non-transitory computer-readable storage medium storing an information processing program that causes at least one computer to execute a process (“Besides storing facts about the world, schema-based knowledge graphs are backed by rich semantic descriptions of entities and relation-types that allow machines to understand the notion of things and their semantic relationships. In this work, we study how type-constraints can generally support the statistical modeling with latent variable models. More precisely, we integrated prior knowledge in form of type-constraints in various state of the art latent variable approaches. Our experimental results show that prior knowledge on relation-types significantly improves these models up to 77% in link- prediction tasks.” [Krompass Abstract]; “We extracted diverse datasets from instances of the Linked-Open Data Cloud, namely Freebase, YAGO and DBpedia,...From these KGs we constructed
datasets that will be used as representatives for general purpose KGs that
cover a wide range of relation-types from a diverse set of domains, domain
focused KGs with a small amount of entity classes and relation-types and
high quality KGs…In the remainder of this section we will give details on the extracted datasets and the evaluation, implementation and training of RESCAL, TransE and mwNN” [Krompass pages 8-9 Experimental Setup]; Executing state of the art knowledge graph embedding algorithms on a diverse array of datasets inherently requires a computer with adequate processing and storage capabilities (i.e., a processor coupled to a storage medium storing instructions) for performing the disclosed functions), the process comprising:
acquiring a graph dataset that includes one or more graphs each having a subject, a predicate, and an object from a knowledge graph (“Knowledge graphs (KGs), i.e., graph-based knowledge-bases, have proven to be sources of valuable information that have become important for various applications like web-search or question answering. Whereas, KGs were initially driven by academic efforts which resulted in KGs like Freebase [4], DBpedia [3], Nell [6] or YAGO [9], more recently commercial applications have evolved” [Krompass page 1 Introduction]; “Further (s,p,o) will denote a triple with subject entity s, object entity o and predicate relation-type p, where the entities s and o represent nodes in the KG that are linked by the predicate relation-type p. The entities belong to the set of all observed entities E in the data” [Krompass page 3 Notation]; “We extracted diverse datasets from instances of the Linked-Open Data Cloud, namely Freebase, YAGO and DBpedia… From these KGs we constructed datasets that will be used as representatives for general purpose KGs that cover a wide range of relation-types from a diverse set of domains, domain focused KGs with a small amount of entity classes and relation-types and high quality KGs” [Krompass page 8 Experimental Setup]; see Table 1. Datasets used in the experiments – each Dataset (e.g., DBpedia-Music, Freebase-150k, YAGOc-195k) has >900,000 Triples; The disclosed process acquires three datasets (i.e., graph datasets) extracted from knowledge graphs, each dataset including triples (i.e., (s, p, o) graphs having subject (s) and object (s) entities connected by a predicate (p) relation type))
setting the acquired graph dataset as a positive example graph dataset that includes one or more positive example graphs; (“TransE [5] is a distance-based model that models relationships of entities as translations in the embedding space. The approach assumes for a true fact that a relation-type specific translation function exists that is able to map (or trans-late) the latent vector representation of the subject entity to the latent representation the object entity… The embeddings are learned by minimizing the max-margin-based ranking cost function [see equation 4 below]
PNG
media_image1.png
98
713
media_image1.png
Greyscale
on a set of observed training triples T…The “corrupted” entities s′ and o′ are drawn from the set of all observed entities E where the ranking loss function enforces that the confidence in the corrupted triples (θs′,p,o or θs,p,o′) is lower than in the true triple by a certain margin” [Krompass pages 4-5 Translational Embeddings Model]; “Generally, KG data does not explicitly contain negative evidence, i.e. false triples, and is generated in this algorithms through corruption of observed triples (see Section 2.3 and 2.4)” [Krompass page 7 Type-Constrained Stochastic Gradient Descent]; Triplets (s,p,o) from observed data (i.e., acquired graph dataset) are assumed to be true (i.e., positive example graphs), given that false (i.e., negative) triples must be manually generated)
generating a negative example graph dataset that includes one or more negative example graphs each having a subject, a predicate, and an object, a predicate of each negative example graph being same as a predicate of one of the positive example graphs, an object of the negative example graph being different from an object of the one of the positive example graphs, (“The embeddings are learned by minimizing the max-margin-based ranking cost function [see equation 4 above] on a set of observed training triples T…The “corrupted” entities s′ and o′ are drawn from the set of all observed entities E where the ranking loss function enforces that the confidence in the corrupted triples (θs′,p,o or θs,p,o′) is lower than in the true triple by a certain margin” [Krompass pages 4-5 Translational Embeddings Model]; “Generally, KG data does not explicitly contain negative evidence, i.e. false triples, and is generated in this algorithms through corruption of observed triples (see Section 2.3 and 2.4)” [Krompass page 7 Type-Constrained Stochastic Gradient Descent]; A collection of corrupted triples (i.e., negative example graphs) are drawn from the observed triples (i.e., positive example graphs) via modifying either the subject or object entity – see that for corrupted triples of the type θs,p,o’ (i.e., negative example graph dataset), the predicate (p) is the same as the observed triple (s, p, o), while the object entity (o’) is different from the observed triple (s, p, o)) the negative example graph being excluded from the negative example graph dataset when the object of the negative example graph is different from each object to which a predicate of any other of the positive example graphs is linked; (“In the original algorithms
of TransE and mwNN the corruption of triples is not restricted and can therefore
lead to the generation of triples that violate the semantics of relation-types. For
integrating knowledge about type-constraints into the SGD optimization scheme
of these models, we have to make sure that none of the corrupted triples violates
the type-constraints of the corresponding relation-types. For TransE we update
Equation 4 and get [see equation 8 below]
PNG
media_image2.png
103
720
media_image2.png
Greyscale
where, in difference to Equation 4, we enforce by s ′ ∈ E[domainp] ⊆ E that the subject entities are only corrupted through the subset of entities that belong to the domain and by o ′ ∈ E[rangep] ⊆ E that the corrupted object entities are sampled from the subset of entities that belong to the range of predicate relation-type p” [Krompass page 7 Type-Constrained Stochastic Gradient Descent]; “Type-constraints as given by KGs tremendously reduce the possible worlds of the statistically modeled KGs, but like the rest of the data represented by the KG, they can also suffer from incompleteness and inconsistency of the data… We argue that in these cases a local closed-world assumption (LCWA) can be applied which approximates the domain and range constraints of the targeted relation-type not on class level, but on instance level based solely on observed triples. Given all observed triples, under this LCWA the domain of a relation-type k consists of all entities that are related by the relation-type k as subject. The range is accordingly defined, but contains all the entities related as object
by relation-type k” [Krompass pages 7-8 Local Closed-World Assumptions]; “As stated before, we explore in our experiments the importance of prior knowledge about the semantics of relation-types for latent variable models. We consider two settings. In the first setting, we assume that curated type-constraints extracted from the KG’s schema are available. In the second setting, we explore the local closed-world assumption (see Section 3.3)” [Krompass page 8 Experimental Setup]; Under enforcement of LCWA and type constraints, the accepted range constraint of object entities when generating corrupted triples (i.e., negative example graphs) is limited by the range of the predicate (p) relation-type, wherein the range of the relation-type is defined by all existing entities that are related as object in the observed triples (i.e., positive example graphs) – the disclosed procedure thereby excludes from the set of corrupted triples of the type θs,p,o’ (i.e., negative example graph dataset) any corrupted triple whose object entity (o’) has not been previously observed as being linked as an object to the predicate (p) in the observed triples (i.e., positive example graphs)) and
training for embedding in the knowledge graph by using the positive example graph dataset and the negative example graph dataset (“TransE [5] is a distance-based model that models relationships of entities as translations in the embedding space…The embeddings are learned by minimizing the max-margin-based ranking cost function [equation 4]” [Krompass pages 4-5 Translational Embeddings Model]; “For TransE we update Equation 4 and get [equation 8]” [Krompass page 7 Type-Constrained Stochastic Gradient Descent]; [see equation 4 (TransE cost function) above and equation 8 (updated TransE cost function) above]; The disclosed translational embeddings (TransE) model trains to learn embeddings by minimizing the cost function, wherein the cost function [equation 8] has corrupted triples θs,p,o’ (i.e., negative example graph dataset) and observed triples θs,p,o (i.e., positive example graph dataset) as parameters)
Regarding claim 2, Krompass discloses the limitations of parent claim 1 and wherein the generating includes generating the negative example graph dataset having an object in a class that is same as a class of the object of the graph dataset when the class of the object of the graph dataset and the class of the object of the negative example graph dataset is set in an ontology ([Krompass page 7 Type-Constrained Stochastic Gradient Descent], as detailed above in claim 1; “Generally, entities in KGs like DBpedia, Freebase or YAGO are assigned to one
or multiple predefined classes (or types) that are organized in an often hierarchical ontology…These concepts are used to represent type-constraints on relation-types by defining the classes or types of entities which they should relate, where the domain covers the subject entity classes and the range the object entity classes in a RDF-Triple. This can be interpreted as an explicit definition of the semantics of a relation, for example by defining that the relation-type marriedTo should only relate instances of the
class Person with each other. In the following, we denote domaink as the ordered indices of all entities that agree with the domain constraints of relation-type k. Accordingly, rangek denotes these indices for the range constraints of relation-type k” [Krompass pages 5-6 Prior Knowledge on Relation-Type Semantics]; “As stated before, we explore in our experiments the importance of prior knowledge about the semantics of relation-types for latent variable models. We consider two settings. In the first setting, we assume that curated type-constraints extracted from the KG’s schema are available. In the second setting, we explore the local closed-world assumption (see Section 3.3)” [Krompass page 8 Experimental Setup]; In light of the specification [¶ 0091 and 0092], the examiner has interpreted the phrase “set in an ontology” as being organized within a framework or structure of related concepts, and has interpreted the term “class” as referencing a grouping or collection of elements and/or types. Under the provision that the data extracted from the KGs contains sufficient prior knowledge so as to identify types for each entity, wherein the types are organized (i.e., set) in an ontology, the disclosed TransE procedure [see equation 8] uses types within the range constraint rangep (i.e., class encompassing the collection of types/subclasses within the constraint) of the predicate p when enforcing type-constraint on the object entity of corrupted triples, such that both o (i.e., object of the positive graph) and o’ (i.e., object of the negative graph) belong to the same range of predicate relation-type p (i.e., are in the same class).
Regarding claims 4-5, they are system/apparatus claims that correspond to the product of claims 1-2, which are already disclosed by Krompass. Krompass further discloses An information processing apparatus comprising: one or more memories; and one or more processors coupled to the one or more memories and the one or more processors configured to: perform the disclosed functions ([Krompass Abstract] and [Krompass pages 8-9 Experimental Setup] as detailed above in claim 1). Consequently, claims 4-5 are rejected for the same reasons as claims 1-2.
Regarding claims 7-8, they are method claims that correspond to the product of claims 1-2, which are already disclosed by Krompass. Krompass further discloses An information processing method for a computer to execute a process comprising: perform the disclosed functions ([Krompass Abstract] and [Krompass pages 8-9 Experimental Setup] as detailed above in claim 1). Consequently, claims 7-8 are rejected for the same reasons as claims 1-2.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 3, 6, and 9 are rejected under 35 U.S.C. 103 as being unpatentable over Krompass, as applied to claims 2, 5, and 8 above, further in view of Qin et al., (“Knowledge Graph Embedding Based on Adaptive Negative Sampling”, published 13 September 2019) hereinafter Qin.
Regarding claim 3, Krompass teaches the limitations of parent claim 2.
However, Krompass does not explicitly teach wherein the generating includes, when at least one class of selected from the object of the graph dataset and the class of the object of the negative example graph dataset is set out of the ontology, generating the negative example graph dataset having the object in a class that is same as a class of the object of the graph dataset by predicting a class of an object that is not set, because the disclosed procedure defaults to a local closed-world assumption approach when type-constraints are unavailable or incomplete in the given ontology (“Since type-constraints can be absent or fuzzy (due to e.g. insufficient typing of entities), we further showed that an alternative, a local closed-world assumption (LCWA), can be applied in these cases that approximates domain range constraints for relation-types on instance level rather on class level solely based on observed triples” [Krompass page 15 Conclusion]).
In the same field of endeavor, Qin discloses a means of adapting negative sampling of knowledge graph embedding algorithms (e.g., translation-based models such as TransE) (“Knowledge graph embedding aims at embedding entities and relations in a knowledge graph into a continuous, dense, low-dimensional and real valued vector space. Among various embedding models appeared in recent years, translation-based models such as TransE, TransH and TransR achieve state-of-the-art performance. However, in these models, negative triples used for training phase are generated by replacing each positive entity in positive triples with negative entities from the entity set with the same probability; as a result, a large number of invalid negative triples will be generated and used in the training process. In this paper, a method named adaptive negative sampling (ANS) is proposed to generate valid negative triples” [Qin Abstract]) wherein the generating includes, when at least one class of selected from the object of the graph dataset and the class of the object of the negative example graph dataset is set out of the ontology, generating the negative example graph dataset having the object in a class that is same as a class of the object of the graph dataset by predicting a class of an object that is not set (“A valid negative triple can help the knowledge graph embedding, so we need to get a valid negative triple. The key of obtaining a valid negative triple is extracting a negative entity similar to a positive entity. In vector space, we can determine whether they are similar by calculating the distance between two entity vectors. If the distance between two entity vectors is smaller, the more similar they are and vice versa. This motivates us the idea of clustering entities and then looking for similar entities in a cluster. Therefore, we decided to use simple and effective K-Means algorithm [13–15] to cluster entities, so that positive and negative entities come from the same cluster. We refer to the above sampling process of negative entities as Adaptive Negative Sampling (ANS)… We aim to divide N entities into K clusters by K-Means in which each entity belongs to a cluster with the nearest mean…Given a positive entity e ∈ Ek(k ∈ 1,2,…,K), a negative entity e’ will be selected from the cluster Ek. Then, the obtained negative entity e 0 and the positive entity e will have a high similarity. Therefore, we can get a valid negative triple to help knowledge graph embedding” [Qin pages 556-557 Adaptive Negative Sampling]; see Fig. 2 The Adaptive Negative Sampling Framework – “m and n represent the number of entity vectors and the dimensions of the vector, respectively. Entity vectors are clustered to obtain k clusters, each cluster containing several entity vectors” [Qin page 556]; see Algorithm 1 Learning TransE-ANS – “Require: Training sets positive triples S = {(h, r, t)} and negative triples S’ = {(h’, r, t) | h’ ∈ Eh} U {(h, r, t’) | t’ ∈ Et})” [Qin page 557]; In light of the specification [¶ 0091 and 0109], the examiner has interpreted the phrase “set out of the ontology” as not being organized or included within a framework or structure of related concepts, and has interpreted the term “class” as referencing a grouping or collection of elements and/or types. Under the assumption that type-constraints are unavailable or incomplete for entities in the given graph dataset, (i.e., entities (e.g., object entities) of the graph dataset are set out of the ontology), the disclosed procedure of Qin can generate clustered groupings of entities (i.e., classes) via a K-means algorithm to divide entities into K clusters (i.e., predict a class for the entity). When generating negative triples, the disclosed procedure ensures that the tail (i.e., object) entity (t’) of the negative triple (i.e., negative example graph) is within the same cluster Et (i.e., class) as the tail (i.e., object) entity (t) of the positive triple (i.e., positive example graph))
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have incorporated wherein the generating includes, when at least one class of selected from the object of the graph dataset and the class of the object of the negative example graph dataset is set out of the ontology, generating the negative example graph dataset having the object in a class that is same as a class of the object of the graph dataset by predicting a class of an object that is not set as taught by Qin into Krompass because they are both directed towards adapting negative