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 .
Specification
The disclosure is objected to because of the following informalities:
The specification at ¶[0021] refers to "subsystem 100" inconsistently with the established nomenclature — reference numeral 100 designates the system (see ¶[0020]: "the system 100 comprises an evolutionary neural architecture search optimization subsystem 102") while reference numeral 102 designates the subsystem; the phrase "The subsystem 100 is configured to overcome the 'permutation problem'" should be corrected to read either "The system 100 is configured..." or "The subsystem 102 is configured...". Appropriate correction is required.
Claim Objections
Claims 12 and 21 are objected to because of the following informalities:
Claim 12: the preamble recites "the method is implemented by a processor executing instructions stored in the memory" — the phrase "the memory" uses the definite article without prior introduction of "a memory" within claim 12, which is an independent claim; "the memory" should be changed to "a memory" or the memory should be introduced before it is referenced with the definite article
Claim 21: the claim recites "the verification unit determines the parameter values by executing the RE method on both the benchmarks" — "the verification unit" is apparatus/structural language (the system of claim 10) used within a method claim; the claim should be amended to use method language describing the step performed (e.g., "the parameter values are determined by executing the RE method..."). Appropriate correction is required.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are as follows:
Claim 1: "an evolutionary neural architecture search optimization engine ... configured to: generate at least two neural network architectures as two parents ...; compute a similarity ... by computing a Graph Edit Distance (GED) ...; and carry out a Shortest Edit Path (SEP) crossover operation ..."
Claimed function: (i) generating at least two neural network architectures as two parents from received inputs (as computation graphs); (ii) computing a similarity between the architectures by computing a Graph Edit Distance (GED) between the corresponding computation graphs by executing one or more graph edit operations; and (iii) carrying out a Shortest Edit Path (SEP) crossover operation by analyzing computed edit paths, randomly shuffling the edit paths in the SEP between parents, selecting half of the shuffled edit paths randomly, and applying them to one parent to generate an offspring graph.
Corresponding structure: Processor 106 with memory 108 (¶[0022]; Fig. 1) programmed to execute the algorithms of neural network architecture generation unit 112 (¶[0024]), GED computation unit 114 (¶[0025]), and SEP crossover computation unit 116 (¶[0026]
Interpretation: Interpreted to cover the foregoing corresponding structure described in the specification as performing the claimed functions, and equivalents thereof.
Claim 3: "a Graph Edit Distance (GED) computation unit executed by the processor and configured to execute the one or more graph edit operations for computing the GED"
Claimed function: executing one or more graph edit operations for computing the GED (applying elementary graph edit techniques transforming G to G' via vertex/edge deletion-insertion or vertex attribute substitution).
Corresponding structure: Processor 106 (¶[0022]-[0023]) programmed to execute the elementary-graph-edit-operation / SEP algorithm of GED computation unit 114 (¶[0025]), and equivalents thereof.
Interpretation: Interpreted to cover the foregoing corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
Claim 6: "an analysis and error computation unit executed by the processor and configured to determine efficiency of the SEP crossover technique by generating an Attributed Adjacency matrix (AA-matrix) ..."
Claimed function: determining efficiency of the SEP crossover technique by generating an AA-matrix representing an attributed directed graph G and computing a main performance metric.
Corresponding structure: Processor 106 (¶[0022]) programmed to execute the AA-matrix (¶[0027]-[0032]), and equivalents thereof.
Interpretation: Interpreted to cover the foregoing corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
Claim 10: "a verification unit executed by the processor and configured to verify that parameter values used in a Monte Carlo simulation lie within favorable regions in real NAS problems ... and to apply one or more standard NAS benchmarks including a NAS-bench-101 and a NAS-bench-NLP to evaluate the parameter values"
Claimed function: verifying that Monte-Carlo parameter values lie within favorable regions in real NAS problems, prior to verifying that parameter values used in analysis of the SEP crossover technique apply to real-world problems; and applying NAS-bench-101 and NAS-bench-NLP to evaluate the parameter values.
Corresponding structure: Processor 106 (¶[0022]) programmed to execute the Monte-Carlo verification and NAS-benchmark/RE evaluation algorithm of verification unit 120 (¶[0033]).
Interpretation: Interpreted to cover the foregoing corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
Claim 21: "the verification unit determines the parameter values by executing the RE method on both the benchmarks including the NAS-bench-101 and the NAS-bench-NLP and recording the relative frequency distributions of the parameters"
Claimed function: determining the parameter values by executing the Regularized Evolution (RE) method on both NAS-bench-101 and NAS-bench-NLP and recording the relative frequency distributions of the parameters.
Corresponding structure: Processor 106 (¶[0022]) programmed to execute the RE-on-benchmarks parameter-determination algorithm of verification unit 120 (¶[0033]).
Interpretation: Interpreted to cover the foregoing corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
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-22 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 1 and 22 each recite the limitation "the graphs" (e.g., "carry out a Shortest Edit Path (SEP) crossover operation by analyzing computed edit paths between the graphs"). There is insufficient antecedent basis for this limitation. Each of claims 1 and 22 introduces the term "computation graphs" (in the phrase "organized structures represented as computation graphs") and subsequently references them as "the neural network architectures corresponding to the computation graphs." However, the phrase "the graphs," without the "computation" modifier, is never introduced as a standalone article in either claim. Because "computation graphs" and "the graphs" are not the same term as introduced, a person of ordinary skill in the art (PHOSITA) cannot be certain with reasonable certainty what "the graphs" refers to in the SEP crossover limitation. See MPEP § 2173.05(e).
For purposes of examination, "the graphs" is interpreted under BRI to refer to the computation graphs (G1 and G2) representing the two parent neural network architectures.
Claims 1, 12, and 22 each recite "shuffling the edit paths in the SEP between the parents" (or "the two parents"). There is insufficient antecedent basis for "the SEP" as used in this limitation. In each claim, "SEP" is first introduced as an abbreviation within the compound phrase "a Shortest Edit Path (SEP) crossover operation." As used in "the SEP between the parents," however, "the SEP" refers not to the crossover operation itself but to the specific set of edit paths constituting the Shortest Edit Path between the two parent computation graphs which is a distinct concept. Because "a SEP" (as the set of shortest edit paths) was never introduced as a discrete article in any of these claims, "the SEP" lacks antecedent basis, and the scope of "the edit paths in the SEP" is indefinite. See MPEP § 2173.05(e).
For purposes of examination, "the SEP" in claims 1, 12, and 22 is interpreted as the set of edit paths of minimum total edit value between the two parent computation graphs.
Claims 1, 12, and 22 each recite "carry out a Shortest Edit Path (SEP) crossover operation by analyzing computed edit paths between the graphs." The phrase "computed edit paths" refers back to previously computed edit paths. However, in each of claims 1, 12, and 22, the only preceding computation step recites "computing a Graph Edit Distance (GED)... wherein one or more graph edit operations are executed for computing the GED." That step introduces "graph edit operations" but does not formally introduce "edit paths" as a distinct named element. Because "edit paths" (as a discrete element subject to the crossover analysis) were never introduced as an article in any of these claims, "computed edit paths" lacks antecedent basis. See MPEP § 2173.05(e).
For purposes of examination, "computed edit paths" in claims 1, 12, and 22 is interpreted as the set of edit paths (sequences of graph edit operations) computed during the GED computation step.
Claim 12 recites "the method is implemented by a processor executing instructions stored in the memory." There is insufficient antecedent basis for "the memory" in claim 12. Unlike system claim 1, which properly introduces "a memory storing program instructions" before referencing "the memory," method claim 12 never introduces "a memory" before using the definite form "the memory." A PHOSITA cannot determine with reasonable certainty what memory is referenced, because no memory has been introduced in claim 12 prior to this use. See MPEP § 2173.05(e).
For purposes of examination, "the memory" in claim 12 is interpreted as any computer-readable storage medium storing the program instructions executed by the processor.
Claims 3 and 14 each recite "a set of elementary graph edit technique carries out a vertex deletion and insertion operation, an edge deletion and insertion operation, or a vertex attribute substitution operation." The phrase "a set of elementary graph edit technique" is grammatically incorrect and ambiguous. The indefinite article "a" combined with the collective noun "set" requires a plural noun to follow ("a set of [plural noun]"), but the claim uses the singular noun "technique." As written, this phrase could mean either (a) a single elementary graph edit technique (in which case "a set of" is superfluous and internally contradictory, because a single item is not a set) or (b) a set of multiple elementary graph edit techniques (in which case "technique" should be "techniques"). This grammatical ambiguity renders indefinite the number of techniques required and, consequently, the metes and bounds of this limitation. See MPEP § 2173.
For purposes of examination, "a set of elementary graph edit technique" in claims 3 and 14 is interpreted as a set of one or more elementary graph edit techniques.
Claim 6 (depending on claim 4, depending on claim 1) recites "configured to determine efficiency of the SEP crossover technique" and "a main performance metric is computed for determining efficiency of the SEP crossover technique." Similarly, claim 17 (depending on claim 15, depending on claim 12) uses "SEP crossover technique" and "the SEP crossover technique." There is insufficient antecedent basis for "the SEP crossover technique" in either claim. In the system claim chain (claims 1, 4, 6), the concept is introduced as "a Shortest Edit Path (SEP) crossover operation" (claim 1) -- not as a "technique." Claim 5 introduces "a SEP technique," but claim 6 does not depend on claim 5. In the method claim chain (claims 12, 15, 17), the concept is introduced as "a Shortest Edit Path (SEP) crossover operation" (claim 12) and "a Shortest Edit Path (SEP)" (claim 15) -- again not as a "technique." Accordingly, "the SEP crossover technique" lacks antecedent basis in both dependency chains. See MPEP § 2173.05(e).
For purposes of examination, "the SEP crossover technique" in claims 6 and 17 is interpreted as the SEP crossover operation introduced in the respective independent parent claim.
Claims 10 and 20 each recite "verify that parameter values used in a Monte Carlo simulation lie within favorable regions in real NAS problems." The term "favorable regions" is a relative term which renders these claims indefinite. The term "favorable regions" is not defined by the claims, the specification does not provide an objective standard for ascertaining what constitutes a "favorable" region (i.e., what parameter value range or distribution qualifies), and a PHOSITA would not be reasonably apprised of the scope of this verification limitation. The specification at ¶[0033] mirrors the claim language without providing any objective criterion for "favorable." Without an objective standard, it is impossible for a PHOSITA to determine what parameter values fall within (or outside of) "favorable regions," rendering the scope of the verification step indefinite.
For purposes of examination, "favorable regions" in claims 10 and 20 is interpreted as parameter value ranges yielding results consistent with actual NAS benchmarks.
Claims 10 and 20 each recite, earlier in the same claim, "favorable regions in real NAS problems" and then subsequently refer to "the real-world problems." There is insufficient antecedent basis for "the real-world problems." The definite article "the" in "the real-world problems" implies prior introduction of this specific phrase, but the prior reference used the different phrase "real NAS problems." Because "the real-world problems" was not introduced with an indefinite article (as "a real-world problem" or "real-world problems") before being referenced with the definite article, there is ambiguity about the referent of "the real-world problems." See MPEP § 2173.05(e).
For purposes of examination, "the real-world problems" in claims 10 and 20 is interpreted as referring to real NAS benchmark problems.
Claims 11 and 21 each recite "the standard NAS technique" with the definite article "the," implying prior introduction. However, neither claim 11 (dependency chain: 11→10→8→7→6→4→1) nor claim 21 (dependency chain: 21→20→19→17→15→12) introduces "a standard NAS technique" in any ancestor claim. Claim 10 introduces "standard NAS benchmarks" and claim 20 likewise introduces "standard NAS benchmarks", where these are benchmarks (test datasets), not techniques. Neither term is "the standard NAS technique." Accordingly, "the standard NAS technique" lacks antecedent basis in both dependency chains. See MPEP § 2173.05(e).
For purposes of examination, "the standard NAS technique" in claims 11 and 21 is interpreted as the Regularized Evolution (RE) method.
Claims 11 and 21 each recite "recording the relative frequency distributions of the parameters." The term "the parameters" is used with the definite article "the," implying prior introduction. However, the ancestor claims in both dependency chains introduce "parameter values" (not "parameters" as a standalone term). While "parameters" is related to "parameter values," the shift in terminology within the same claim creates an antecedent basis ambiguity, specifically, whether "the parameters" refers to the same parameters as the previously introduced "parameter values" or to a different set of parameters. See MPEP § 2173.05(e).
For purposes of examination, "the parameters" in claims 11 and 21 is interpreted as the parameter values introduced in the respective ancestor claims.
Claim 21 recites "the verification unit determines the parameter values by executing the RE method on both the benchmarks." Claim 21 is indefinite for two independent reasons. First, the term "the verification unit" is used with the definite article "the," implying prior introduction. However, no ancestor claim in the method claim dependency chain (21→20→19→17→15→12) introduces "a verification unit." The verification unit appears only in system claims 10 and 11, which are in a separate dependency chain (11→10→8→7→6→4→1) from independent system claim 1, not from independent method claim 12. A method claim cannot import apparatus elements from an unrelated system claim chain. Accordingly, "the verification unit" lacks antecedent basis in claim 21. See MPEP § 2173.05(e). Second, claim 21 is an independent method claim (depending ultimately from method claim 12) that introduces the named apparatus element "the verification unit" as the agent of the method step of "determin[ing] the parameter values by executing the RE method." This improperly mixes apparatus and method elements in a single claim. It is unclear whether the claim requires: (a) a processor performing the method steps, or (b) the presence of a specific apparatus component ("verification unit") that performs one of those steps, or (c) both. Mixing apparatus elements and method steps in a single claim renders it indefinite because the scope cannot be determined. See MPEP § 2173.05(p).
For purposes of examination, "the verification unit" in claim 21 is interpreted as a processor-implemented component performing the verification steps, but the hybrid claim structure renders the scope indeterminate.
Claim 18 recites "the crossover offspring graph is generated by removing all null vertices from the new offspring graph with null vertices (G^new)." There is insufficient antecedent basis for "the crossover offspring graph." No ancestor claim in the dependency chain (18→17→15→12) introduces "a crossover offspring graph." Independent claim 12 introduces "an offspring graph" and claim 18 itself introduces "a new offspring graph (Gnew)", but neither introduces "a crossover offspring graph" before referencing "the crossover offspring graph." The modifier "crossover" added to "offspring graph" introduces a new, more specific term that lacks antecedent. See MPEP § 2173.05(e).
For purposes of examination, "the crossover offspring graph" in claim 18 is interpreted as the offspring graph produced by the SEP crossover operation after null vertex removal.
Claims dependent upon the aforementioned claims are rejected as being upon a rejected base claim.
Appropriate correction is required.
Claim Rejections - 35 USC § 102
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-22 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Shortest Edit Path Crossover: A Theory-driven Solution to the Permutation Problem in Evolutionary Neural Architecture Search to Qiu et al. (hereinafter Qiu).
Per claim 1, Qiu discloses A system for optimized evolutionary neural architecture search (Qiu: Abstract…Qiu presents a population-based black-box NAS approach using a new crossover operator in graph space, which is a method for optimized evolutionary neural architecture search implemented on a computing system), "proposes a new crossover operator based on the shortest edit path (SEP) in graph space"), the system comprising:
a memory storing program instructions; a processor executing instructions stored in the memory (Qiu: Appendix A.1…Qiu's approach is embodied as program code necessarily stored in memory and implemented thru execution on a computing system having a processor, "For experiments in Section 5.1, all the RE-based variants are using a population size of 100, and a tournament selection with size 10 to select the parents. For NAS-bench-101, GED to the global optimal architecture is used as the fitness, and 50 independent runs were performed…In both benchmarks, for each crossover operation, the offspring will undergo the evaluation only if it is a valid architecture in the benchmark space and it is different from both parents, the maximum number of trials is set as 50, and we will skip the current crossover if we reach this trial limit. For experiments in Section 5.2, the same experimental setups as used in Section 5.1 is deployed"); and
an evolutionary neural architecture search optimization engine (Qiu: Appendix A.1…experimental setup algorithm construed to be the optimization engine) and configured to:
generating at least two neural network architectures as two parents based on one or more received inputs, wherein the neural network architectures are in the form of organized structures represented as computation graphs (Qiu: Section 3…Qiu generates two parent neural architectures, each an attributed directed computation graph, "Given two neural architectures as parents, a crossover operator generates an offspring architecture by recombining the two parents"; Section 3…Qiu defines each architecture as a directed computation graph, "A neural architecture is a computation graph that can always be represented by an attributed directed graph");
computing a similarity between the generated two neural network architectures by computing a Graph Edit Distance (GED) between the neural network architectures corresponding to the computation graphs, wherein one or more graph edit operations are executed for computing the GED (Qiu: Section 3, Definition 3.2…Qiu defines elementary graph edit operations for neural architecture graphs, "the set of elementary graph edits typically includes vertex deletion/insertion, edge deletion/insertion, and vertex attribute substitution"; Section 3, Definition 3.2…Qiu defines GED as the minimum-cost edit path between two architecture graphs, "Graph edit distance between two graphs G1 and G2 is then defined as GED(G1, G2) = min Σ c(δi)");
carrying out a Shortest Edit Path (SEP) crossover operation by analyzing computed edit paths between the computation graphs, wherein a shuffling operation is carried out randomly for shuffling the edit paths in the SEP between the parents by selecting half of the shuffled edit paths randomly and applying selected edit paths to one of the parents to generate an offspring graph for optimizing Neural Architecture Search (NAS) to solve real-world problems (Qiu: Section 3, Definition 3.3…Qiu's SEP crossover randomly shuffles edit paths and applies a random half to one parent, empirically verified on NAS-bench-101 and NAS-bench-NLP, "the SEP crossover shuffles the edits randomly in the SEP between parents, then selects half of them randomly, and applies them to one of the parents to obtain the offspring").
Per claim 2, Qiu discloses claim 1, further disclosing the computation graphs are represented by a directed graph (G), and wherein the received inputs relate to the directed graph which includes a set of vertices (vi) (nodes) and a set of directed edges (ei) associated with the directed graph, and wherein the order of the directed graph (G) equals the number of its vertices which is represented by |G| (Qiu: Section 3, Definition 3.1…Qiu expressly defines the computation graph as a directed graph G with vertices and directed edges, and defines the order |G| as the vertex count, "A directed graph G consists of a set of vertices V = {vi|I = 1,2,...,n}, where n is the number of vertices and each vi denotes a vertex (node), and a set of directed edges E = {ei,j|i,j ∈ 1,2,...,n}, where ei,j denotes a directed edge from vi to vj. The order of a directed graph G equals the number of its vertices, represented by |G|").
Per claim 3, Qiu discloses claim 1, further disclosing the evolutionary neural architecture search optimization engine comprises a Graph Edit Distance (GED) computation unit executed by the processor and configured to execute the one or more graph edit operation for computing the GED, the graph edit operation comprises application of an elementary graph edit technique which transforms a directed graph (G) to G' which represents an edited graph, and wherein a set of elementary graph edit technique carries out a vertex deletion and insertion operation, an edge deletion and insertion operation, or a vertex attribute substitution operation (Qiu: Section 3, Definition 3.2…Qiu defines a graph edit operation as a function δ: G → G' that transforms G to an edited graph G' via elementary edits, and expressly enumerates vertex deletion/insertion, edge deletion/insertion, and vertex attribute substitution in the NAS context, "A graph edit operation is defined as a function δ: G → G' that applies an elementary graph edit to transform G to G'. In standard neural architecture search, the set of elementary graph edits typically includes vertex deletion/insertion, edge deletion/insertion, and vertex attribute substitution").
Per claim 4, Qiu discloses claim 1, further disclosing the GED between the one or more computation graphs relates to the computed edit paths that transform the computation graph G1 to G2 or isomorphisms of G2, the graph edit operation has a value of 1, and wherein the edit path that minimizes the total edit value comprises a Shortest Edit Path (SEP) between G1 and G2, and wherein multiple SEPs are computed between G1 and G2 having a same length (Qiu: Section 3, Definition 3.2…Qiu defines GED over all edit paths transforming G1 to an isomorphism of G2, "GED(G1, G2) = min Σ c(δi), where Δ(G1, G2) denotes the set of all edit paths that transform G1 to an isomorphism of G2 (including G2 itself)"; Section 3, Definition 3.2…Qiu assigns unit cost to each edit operation making the SEP the minimizing path, and notes multiple SEPs of equal length may exist, "In this work, all types of edit operations are defined to have the same cost of 1. As a result, the edit path that minimizes the total edit cost equals the shortest edit path between G1 and G2. Thus, GED(G1, G2) = d*G1,G2, where d*G1,G2 is the length of this shortest edit path. Note that δ*G1,G2 may not be unique, and thus there may exist multiple shortest edit paths that have the same length").
Per claim 5, Qiu discloses claim 1, further disclosing the SEP crossover operation employs a SEP technique that analyzes parts that are functionally inconsistent between the two parents (Qiu: Section 3…Qiu explains that the SEP crossover targets the edit-path edits corresponding to the functionally inconsistent differences between parents while automatically preserving common substructures, "the offspring can automatically preserve those common substructures between parents, avoiding unnecessary disruptive behaviors, and thus avoiding the permutation problem").
Per claim 6, Qiu discloses claim 4, further disclosing the evolutionary neural architecture search optimization engine comprises an analysis and error computation unit executed by the processor and configured to determine efficiency of the SEP crossover technique by generating an Attributed Adjacency matrix (AA-matrix) which represents an attributed directed graph (G), and wherein a main performance metric is computed for determining efficiency of the SEP crossover technique (Qiu: Section 4, Definitions 4.1…Qiu defines the AA-matrix as an n×n matrix representation of the attributed directed graph and defines the main performance metric, "An attributed adjacency matrix (AA-matrix) AG is a representation of an attributed directed graph G”, being an n × n matrix, “where n is the number of vertices in G"; Definition 4.7…"expected improvement in terms of topological similarity to the global optimal graph… E(max(de(AGopt, AG1→Gopt}) - de(AGopt, AGnew→Gopt), 0))").
Per claim 7, Qiu discloses claim 6, further disclosing the analysis and error computation unit is configured to process the computation graphs G1 and G2, and wherein G1 and G2 have a same order which is determined by adding null vertices resulting in the neural network architectures G^1 and G^2, and wherein a crossover operation is carried out between G1 and G2 for generating the offspring graph by recombining AA-matrix of G^1 and G^2 represented as AG^1 and AG^2 and wherein the analysis and error computation unit generates a new AA-matrix (AG^new) is generated of a new offspring graph (Gnew) with null vertices associated with the SEP crossover operation, and wherein the crossover offspring graph is generated by removing all null vertices from the new offspring graph with null vertices (G^new) (Qiu: Section 4.1, Definition 4.4…Qiu extends both graphs to the same order by adding null vertices, "Two graphs G1 and G2 can both be extended to have the same order n = max(|G1|, |G2|) by adding null vertices"; Section 4.1, Definition 4.5…Qiu recombines AA-matrices and removes null vertices to obtain the offspring, "A crossover between G1 and G2 is defined as the process of generating an offspring graph Gnew by recombining AG1 and AG2: AGnew = r(AG1, Pπ AG2PπT)…The result, AGnew, is the AA-matrix of the generated new graph with null vertices. By removing all null vertices from Gnew, the offspring graph Gnew is obtained").
Per claim 8, Qiu discloses claim 7, further disclosing the analysis and error computation unit computes the main performance metric for determining efficiency of the SEP crossover technique based on a topological similarity to a global optimal graph, the efficiency of the SEP crossover technique is determined by comparing the new offspring graph (Gnew) with one of the computation graphs G1 in terms of the expected edge differences to Gopt (Qiu: Section 4.1, Definition 4.7…Qiu defines the main performance metric as expected improvement in topological similarity to the global optimal graph, comparing offspring Gnew with parent G1 in expected edge differences to Gopt, "expected improvement refers to E(max(de(AGopt, AG1→Gopt}) - de(AGopt, AGnew→Gopt), 0)), which compares offspring graph Gnew with one parent graph G1 in terms of the expected edge/connection differences to Gopt").
Per claim 9, Qui discloses claim 7, further disclosing the analysis and error computation unit which is configured to compute an error during the GED determination between the two neural network architectures G^1, G^2 (Section 6…Qiu considers analysis of errors during GED calculations, "analyzing the effect of errors in GED calculation").
Per claim 10, Qiu discloses claim 8, further disclosing the evolutionary neural architecture search optimization engine comprises a verification unit executed by the processor and configured to verify that parameter values used in a Monte Carlo simulation are verified to determine whether the parameter values lie within favorable regions in real NAS problems, prior to verifying that one or more parameter values used in analysis of the SEP crossover technique apply to the real-world problems, and wherein the verification unit is configured to apply one or more standard NAS benchmarks including a NAS-bench-101 and a NAS-bench-NLP to evaluate the parameter values used in the SEP crossover technique (Qiu: Section 4…Qiu verifies theoretical parameter values via Monte Carlo simulation with 106 trials to confirm they fall within favorable ranges, the expected improvement in each case was then estimated “via Monte Carlo simulations with 106 trials"; Section 5.1…Qiu applies NAS-bench-101 and NAS-bench-NLP as real-world benchmarks to evaluate those parameter ranges, "While NAS-bench-101 has the most flexible graph search space among all queryable NAS benchmarks, NAS-bench-NLP has the largest search space among all existing NAS benchmarks”, they were both thus used to evaluate the parameter ranges).
Per claim 11, Qiu discloses claim 10, further disclosing the SEP crossover technique is evaluated with the standard NAS technique by incorporating the SEP crossover technique into a Regularized Evolution (RE) method, and wherein the verification unit determines the parameter values by executing the RE method on both the benchmarks including the NAS-bench-101 and the NAS-bench-NLP and recording the relative frequency distributions of the parameters (Qiu: Section 5.1…Qiu integrates the SEP crossover into the Regularized Evolution (RE) method by alternating crossover with mutation, executes RE on both NAS-bench-101 and NAS-bench-NLP, and records the relative frequency distributions, "it is important to verify that the parameters that are critical to the expected improvement indeed lie within the favorable regions in real NAS problems. To this end, SEP crossover was added into the SOTA Regularized Evolution algorithm (RE; Real et al., 2019), in which only mutation operator is deployed. SEP crossover was integrated into RE by simply alternating it with the original mutation operator. Figures 3 and 4 show the relative frequency distribution…”).
Claims 12-22 are substantially similar in scope and spirit as claims 1-11. Therefore, the rejections of claims 1-11 are applied accordingly.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Patents and/or related publications are cited in the Notice of References Cited (Form PTO-892) attached to this action to further show the state of the art with respect to evolutionary neural network architecture search.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ALAN CHEN whose telephone number is (571)272-4143. The examiner can normally be reached M-F 10-7.
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, Kamran Afshar can be reached at (571) 272-7796. 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.
/ALAN CHEN/Primary Examiner, Art Unit 2125
Prosecution Insights