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 .
Note on Prior Art
The prior art of record does not teach or make obvious claim 12’s, “for each of a plurality of graph elements of the first augmented graph, the first probability distribution assigns a probability to the graph element that is based at least in part on the embedding of the graph element in the intermediate representation of the first augmented dataset; and
wherein for each of a plurality of graph elements of the second augmented graph, the second probability distribution assigns a probability to the graph element that is based at least in part on the embedding of the graph element in the intermediate representation of the second augmented dataset.”
Claim Rejections - 35 USC § 112
The following is a quotation of the first paragraph of 35 U.S.C. 112(a):
(a) IN GENERAL.—The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor or joint inventor of carrying out the invention.
Claims 1-20 are rejected under 35 U.S.C. 112(a) or 35 U.S.C. 112 (pre-AIA ), first paragraph, because the specification, while being enabling for “sorting a set of numerical values, or searching a set of numerical values, or identifying a strongly connected component of a graph”, does not reasonably provide enablement for all algorithmic tasks. The specification does not enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to use the invention commensurate in scope with these claims.
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.
Claims 3, 4, 8-13 and 18 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.
Claims 3 and 4 recite the limitation "the representation of the input dataset". There is insufficient antecedent basis for this limitation in the claim. Make claim 3 depend on claim 2 to solve this problem.
Claims 8-13 recite the limitation “the first augmented graph” and “the second augmented graph”. There is insufficient antecedent basis for this limitation in the claim
Claim 10 recites the limitation “the graph element”. There is insufficient antecedent basis for this limitation in the claim.
Claim 18 is unclear because there are potentially two different input datasets introduced without resolving if they are different input datasets or not.
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 1-3, 7-11 and 13-20 are rejected under 35 U.S.C. 103 as being unpatentable over A Generalist Neural Algorithmic Learner by Ibarz et al and Relational Self-Supervised Learning on Graphs by Lee et al.
Claims 4-6 are rejected under 35 U.S.C. 103 as being unpatentable over A Generalist Neural Algorithmic Learner by Ibarz et al, Relational Self-Supervised Learning on Graphs by Lee et al and Data Augmentation for Graph Neural Networks by Zhao et al
Ibarz teaches claims 1 and 18-20. A method performed by one or more computers, the method comprising: (Ibarz sec. 3.1 “The decoded hints and outputs are used to compute the loss during training…”)
training a neural network to perform an algorithmic task using a machine learning training technique, (Ibarz abs “a single graph neural network processor capable of learning to execute a wide range of algorithms, such as sorting, searching, dynamic programming, path-finding and geometry. We leverage the CLRS benchmark to empirically show that…” Ibarz sec. 4 teaches training.)
wherein the algorithmic task is specified by a computational algorithm defined by a set of rules that, when applied to a dataset, cause the dataset to be processed over a sequence of computational steps to generate an algorithmic output, (Ibarz abs “a single graph neural network processor capable of learning to execute a wide range of algorithms, such as sorting, searching, dynamic programming, path-finding and geometry. We leverage the CLRS benchmark to empirically show that…” The CLRS benchmark includes different sets of rules for the different types of algorithms that are tested, such as sorting, searching etc.) and
wherein training the neural network comprises:
obtaining an input dataset; (Ibarz sec. 3 “Each algorithm in the CLRS benchmark [5] is specified by a number of inputs, hints and outputs.” Ibarz sec. 3.2.1 “To prevent our model from over-fitting to the statistics of the fixed CLRS training dataset [5], we augmented the training data…”)
generating a first augmented dataset and a second augmented dataset, wherein for both the first augmented dataset and the second augmented dataset: (Ibarz sec. 3 “To prevent our model from over-fitting to the statistics of the fixed CLRS training dataset [5], we augmented the training data in three key ways…”)
applying the computational algorithm to the augmented dataset causes the same computational operations to be performed at a target computational step as would be performed by applying the computational algorithm to the input dataset; (Where Ibarz modifies the dataset by sampling, Ibarz doesn’t change the computational algorithm.1 So, the computational steps all stay the same, just the sampled/augmented training dataset changes.)
processing the first augmented dataset and the second augmented dataset using the neural network, comprising, for each augmented dataset:
generating an intermediate representation of the augmented dataset at an intermediate layer of the neural network; and (Ibarz p. 7 teaches “we note that the edge representations are updated by choosing an intermediate node… first, computing representations over triplets of nodes, then reducing over one node to obtain edge latents…” The latents are the intermediate representation, the intermediate node is in the intermediate layer.)
Ibarz’s objective function is slightly different than what is claimed.
However, Lee teaches training the neural network on an objective function, (Lee title “Relational Self-Supervised Learning on Graphs”) wherein the objective function comprises a self-supervised loss term that depends on: (i) the intermediate representation of the first augmented dataset generated at the intermediate layer of the neural network, and (ii) the intermediate representation of the second augmented dataset generated at the intermediate layer of the neural network. (Lee sec. 4.1 “among nodes for learning node representations. More precisely, we first generate two graph views ˜G1 = ( ˜ X1, ˜ A1)and ˜G2 = ( ˜ X2, ˜ A2) by applying a stochastic graph augmentation function T1 and T2 to the original graph G, respectively. Then, the online encoder 𝑓𝜃 produces online representation… while the target encoder 𝑓𝜉 produces target representation…” The online representation is the intermediate representation of the first augmented graph, the target representation is the second augmented intermediate representation.)
Ibarz, Nam, and the claims all train on augmented graph data. It would have been obvious to a person having ordinary skill in the art, at the time of filing, to use Nam’s objective function because Lee “overcomes limitations of previous contrastive and non-contrastive methods, and achieves the best of both worlds.” Lee abs.
Ibarz teaches claim 2. The method of claim 1, wherein the training further comprises:
processing a representation of the input dataset using the neural network to generate a predicted output at an output layer of the neural network; and (Ibarz p. 4 “The processed embeddings are finally decoded with a task-based decoder gτ, to predict the hints for the next step, and the outputs at the final step.”)
wherein the objective function comprises a supervised loss term that measures an error between: (i) the predicted output generated at the output layer of the neural network by processing the input dataset, and (ii) an algorithmic output generated by applying the computational algorithm to the input dataset. (Ibarz p. 4 “The decoded hints and outputs are used to compute the loss during training, according to their type [5]. For each sample in a batch, the hint prediction losses are averaged across hints and time, and the output loss is averaged across outputs (most algorithms have a single output, though some have two outputs).”)
Ibarz teaches claim 3. The method of claim 1, wherein the representation of the input dataset comprises an input graph, the representation of the first augmented dataset comprises a first augmented graph, and the representation of the second augmented dataset comprises a second augmented graph. (Ibarz sec. 3 “A sample of every algorithm is represented as a graph, with each input, output and hint located in either the nodes, the edges, or the graph itself…” Ibarz sec. 3 “To prevent our model from over-fitting to the statistics of the fixed CLRS training dataset [5], we augmented the training data in three key ways…”)
Ibarz teaches claim 4. The method of claim 3.
Ibarz doesn’t teach that the input graph is a subset of the first and second graph.
However, Zhao teaches wherein the input graph is a sub-graph of the first augmented graph and the second augmented graph. (Zhao fig. 1 below)
PNG
media_image1.png
436
1316
media_image1.png
Greyscale
Ibarz, the claims and Zhao all augment input graphs. It would have been obvious to a person having ordinary skill in the art, at the time of filing, to augment according to Zhao because “augmentation via GAUG improves performance across GNN architectures and datasets.” Zhao abs.
Ibarz teaches claim 5. The method of claim 1,
wherein the input dataset comprises an input set of data elements, the first augmented dataset comprises a first augmented set of data elements, and the second augmented dataset comprises a second augmented set of data elements; (Ibarz sec. 3 “A sample of every algorithm is represented as a graph, with each input, output and hint located in either the nodes, the edges, or the graph itself…”)
Ibarz doesn’t teach that the input graph is a subset of the first and second graph.
However, Zhao teaches wherein the input set of data elements is a subset of the first augmented set of data elements and the second augmented set of data elements. (Zhao fig. 1 below)
PNG
media_image1.png
436
1316
media_image1.png
Greyscale
Ibarz, the claims and Zhao all augment input graphs. It would have been obvious to a person having ordinary skill in the art, at the time of filing, to augment according to Zhao because “augmentation via GAUG improves performance across GNN architectures and datasets.” Zhao abs.
Ibarz teaches claim 6. The method of claim 5, wherein the data elements are numerical values. (Ibarz sec. 3 “The CLRS benchmark defines five types of features: scalar, categorical, mask, mask_one and pointer,” and Fig. 1.)
Ibarz teaches claim 7. The method of claim 2, wherein the self-supervised loss term measures a similarity between: (i) the intermediate representation of the first augmented dataset, and (ii) the intermediate representation of the second augmented dataset. (Lee sec. 2.2 “learns node representations by encoding two augmented versions of a graph using two separate encoders: one is trained by maximizing the cosine similarity between the representations generated by the two encoders, while the other encoder is updated by an exponential moving average of the first encoder.”)
Ibarz teaches claim 8. The method of claim 7, wherein the intermediate representation of the first augmented dataset comprises a respective embedding of each graph element in a set of graph elements of the first augmented graph; and (Ibarz “sec. 3 “A sample of every algorithm is represented as a graph, with each input, output and hint located in either the nodes, the edges, or the graph itself, and therefore has shape (excluding batch dimension, and, for hints, time dimension) n × f, n × n × f, or f, respectively, f being the dimensionality of the feature…” The feature f is the embedding.)
wherein the intermediate representation of the second augmented dataset comprises a respective embedding of each graph element in a set of graph elements of the second augmented graph. (Ibarz p. 7 teaches “we note that the edge representations are updated by choosing an intermediate node… first, computing representations over triplets of nodes, then reducing over one node to obtain edge latents… 8-dimensional features…” That 8-D feature vector of the latent is the embedding of the intermediate representation.)
Ibarz teaches claim 9. The method of claim 8, wherein the set of graph elements of the first augmented graph comprises one or more nodes of the first augmented graph or one or more edges of the first augmented graph; and
wherein the set of graph elements of the second augmented graph comprises one or more nodes of the second augmented graph or one or more edges of the second augmented graph. (Ibarz sec. 3 “To prevent our model from over-fitting to the statistics of the fixed CLRS training dataset [5], we augmented the training data in three key ways…” Graphs contain edges and nodes. And the CLRS training set is graphs.)
Ibarz teaches claim 10. The method of claim 9, wherein for each of one or more pairs of graph elements comprising: (i) a first graph element from the set of graph elements of the first augmented graph, and (ii) a second graph element of the set of graph elements of the second augmented graph: (Lee sec. 4.1 “among nodes for learning node representations. More precisely, we first generate two graph views ˜G1 = ( ˜ X1, ˜ A1)and ˜G2 = ( ˜ X2, ˜ A2) by applying a stochastic graph augmentation function T1 and T2 to the original graph G, respectively.”)
the self-supervised loss term measures a similarity between: (i) the embedding of the graph element in the intermediate representation of the first augmented dataset, and (ii) the embedding of a corresponding graph element in the intermediate representation of the second augmented dataset. (Lee sec. 2.2 “learns node representations by encoding two augmented versions of a graph using two separate encoders: one is trained by maximizing the cosine similarity between the representations generated by the two encoders, while the other encoder is updated by an exponential moving average of the first encoder.”)
Ibarz teaches claim 11. The method of claim 9, wherein the self-supervised loss term measures a divergence between: (Lee sec. 4.1 “The similarity is then converted into a probability distribution via softmax…” Lee equation 3 “Having computed two probability distributions for each node 𝑣𝑖 ∈V, i.e.,𝑝𝜃 𝑖 and𝑝𝜉 𝑖 , derived from the query-anchors similarity, we minimize the following sum of KL divergence…”)) (i) a first probability distribution over a subset of the graph elements of the first augmented graph, and (Lee equation 1 below)
PNG
media_image2.png
194
616
media_image2.png
Greyscale
(ii) a second probability distribution over a subset of the graph elements of the second augmented graph. (Lee equation 2 below. Lee equation 3 “Having computed two probability distributions for each node 𝑣𝑖 ∈V, i.e.,𝑝𝜃 𝑖 and𝑝𝜉 𝑖 , derived from the query-anchors similarity, we minimize the following sum of KL divergence…”)
PNG
media_image3.png
268
616
media_image3.png
Greyscale
Ibarz teaches claim 13. The method of claim 11, wherein the divergence comprises a Kullback-Leibler divergence. (Lee equation 2 below. Lee equation 3 “Having computed two probability distributions for each node 𝑣𝑖 ∈V, i.e.,𝑝𝜃 𝑖 and𝑝𝜉 𝑖 , derived from the query-anchors similarity, we minimize the following sum of KL divergence…”)
Ibarz teaches claim 14. The method of claim 1, wherein the algorithmic task comprises sorting a set of numerical values, or searching a set of numerical values, or identifying a strongly connected component of a graph. (Ibarz abs “a single graph neural network processor capable of learning to execute a wide range of algorithms, such as sorting, searching, dynamic programming, path-finding and geometry.”)
Ibarz teaches claim 15. The method of claim 1, further comprising, after training the neural network to perform the algorithmic task:
training the neural network to perform a machine learning task. (Ibarz abs “a single graph neural network processor capable of learning to execute a wide range of algorithms, such as sorting, searching, dynamic programming, path-finding and geometry.”)
Ibarz teaches claim 16. The method of claim 15, wherein the machine learning task comprises an image processing task, or a video processing task, or a text processing task, or an audio processing task, or a point cloud processing task. (Ibarz sec. 2 “we provide a generalist agent for a diverse set of algorithmic domains, including sorting, searching, graphs, strings, and geometry.” Strings are text.)
Ibarz teaches claim 17. The method of claim 1, wherein the neural network has a graph neural network architecture. (Ibarz abs “a single graph neural network processor…”)
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Austin Hicks whose telephone number is (571)270-3377. The examiner can normally be reached Monday - Thursday 8-4 PST.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Mariela Reyes can be reached at (571) 270-1006. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/AUSTIN HICKS/ Primary Examiner, Art Unit 2142
1 Ibars p. 5 “Firstly, we used the on-line samplers in CLRS to generate new training examples on the fly, rather than using a fixed dataset which is easier to overfit to. Secondly, we trained on examples of mixed sizes, n ≤ 16, rather than only 16, which helps the model anticipate for a diverse range of sizes, rather than overfitting to the specifics of size n = 16. Lastly, for graph algorithms, we varied the connectivity probability p of the input graphs (generated by the Erd˝os-Rényi model [38]); and for string matching algorithms, we varied the length of the pattern to be matched.”
Prosecution Insights