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 .
Claims 1-9 are presented for examination.
Information Disclosure Statement
The listing of references in the specification is not a proper information disclosure statement. 37 CFR 1.98(b) requires a list of all patents, publications, or other information submitted for consideration by the Office, and MPEP § 609.04(a) states, "the list may not be incorporated into the specification but must be submitted in a separate paper." Therefore, unless the references have been cited by the examiner on form PTO-892, they have not been considered.
Drawings
The drawings are objected to as failing to comply with 37 CFR 1.84(p)(4) because reference character “105” has been used to designate “Algorithm A”, “Algorithm B”, and “Algorithm C”, such that it is unclear which algorithm the pseudo-code lines in paragraphs [0027]-[0029] are referring to. 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. 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.
The drawings are objected to as failing to comply with 37 CFR 1.84(p)(5) because they do not include the following reference sign(s) mentioned in the description: “program code 107” in paragraph [0029]. 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. 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.
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 3-4 and 7-8 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 7 recite the limitation "wherein the operation comprises". There is insufficient antecedent basis for this limitation in the claim. Previous recitations in the claims from which claims 3 and 7 depend on recite performing sets of operations, including steps a-r, such that it is unclear which operation “the operation” in claims 3 and 7 is referring to.
Claims 4 and 8 recite the limitation “wherein the operation of compiling a current group of random data coordinates comprises”. There is insufficient antecedent basis for this limitation in the claim. Namely, there is no compiling operation in the previously recited limitations. At best, step (p) recites “selecting a new group of compiled data coordinates”, so it is unclear if the recited “operation of compiling” is referring to this step or if the recited “current group” in claims 4 and 8 is referring to the “new group” in claims 2 and 6.
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.
Independent Claims
Step 1 – Claim 1 is drawn to a method, claim 5 is drawn to a system, and claim 9 is drawn to a computer program product. Therefore, each of these claims fall under one of the four categories of statutory subject matter (process/method, machine/product/apparatus, manufacture or composition of matter).
Step 2A Prong 1 – Claims 1, 5, and 9 are directed to a judicially recognized exception of an abstract idea without significantly more. Claims 1, 5, and 9 recite:
converting the sparse dataset into a matrix of plural data coordinates defined by a feature value and a column gradient – This limitation is directed towards the abstract idea of a mathematical relationship (see MPEP § 2106.04(a)(2), section I, A). In Paragraph [0027] of the specification, it states “As shown in lines 1-5 of program code 105, the processor 104 converts the sparse dataset into a matrix of plural data coordinates defined by a feature value and a column gradient”. BRI in light of lines 1-5 of Algorithm A in [Fig. 1] would support that “converting the sparse dataset into a matrix” would encompass organizing information and manipulating information through mathematical correlations and fall under the mathematical concepts grouping.
generating a priority queue populated with the plural data coordinates – This limitation is directed towards the abstract idea of a mathematical relationship (see MPEP § 2106.04(a)(2), section I, A). BRI in light of the plain meaning of priority queue data structure and lack of further description in the specification would support that “generating a priority queue” would encompass organizing information and manipulating information through mathematical correlations and fall under the mathematical concepts grouping.
iteratively selecting a data coordinate from the priority queue, each coordinate indicating a next covariate to update in the machine learning model – This limitation is directed towards the abstract idea of a mental process, or a concept that can be performed in the human mind, including observation, evaluation, judgement or opinion (see MPEP § 2106.04(a)(2), subsection III, C). BRI in light of the plain meaning of priority queue data structure and lack of further description in the specification would support that “iteratively selecting a data coordinate from the priority queue” would encompass a mental process with or without the assistance of pen and paper of iterating through a sequence of tasks.
calculating based on the selected data coordinate, at least a first gradient value as a row gradient of the matrix, a second gradient value as a column gradient of the matrix, a dot product of the row gradient with a weight value of the feature associated with the first data coordinate, and a convergence gap value as a base convergence gap value of the machine learning model – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). In Paragraph [0027] of the specification, it states “Based on lines 23-29, the processor 105 calculates based on the selected data coordinate, at least a first gradient value as a row gradient of the matrix, a second gradient value as a column gradient of the matrix, a dot product of the row gradient with a weight value of the feature associated with the first data coordinate, and a convergence gap value as a base convergence gap value of the machine learning model”. BRI in light of lines 23-29 of Algorithm A in [Fig. 1] would support that “calculating row and column gradients, dot product of the row gradient with a weight value of a feature, and a convergence gap value” would encompass a set of mathematical computations and fall under the mathematical concepts grouping.
selecting a next data coordinate from the plural data coordinates in the priority queue, the next data coordinate corresponding to a next feature for training the model – This limitation is directed towards the abstract idea of a mental process, or a concept that can be performed in the human mind, including observation, evaluation, judgement or opinion (see MPEP § 2106.04(a)(2), subsection III, C). BRI in light of the plain meaning of priority queue data structure and lack of further description in the specification would support that “iteratively selecting a data coordinate from the priority queue” would encompass a mental process with or without the assistance of pen and paper of iterating through a sequence of tasks.
altering a weight value of the next feature to produce an altered weight value – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). In Paragraph [0027] of the specification, it states “At lines 16-22 of the program code 105, the processor 104 alters a weight value of the next feature to produce an altered weight.” BRI in light of lines 16-22 of Algorithm A in [Fig. 1] would support that “altering a weight value of the next feature” would encompass a series of mathematical computations and fall under the mathematical concepts grouping.
updating plural variables of the matrix based on the altered weight value, the plural variables being located in rows of the matrix that include the next feature, the plural variables including at least the column gradient, the dot product of each row of the matrix that includes the next feature in the matrix with the altered weight value, and the base convergence gap value associated with training of the machine learning model – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). In Paragraph [0027] of the specification, it states “The processor 104 then updates plural variables of the matrix based on the altered weight value (lines 24-28), the plural variables being located in rows of the matrix that include the next feature, the plural variables including at least the column gradient, the dot product of each row of the matrix that includes the next feature j in the matrix with the altered weight value, and the base convergence gap value g associated with training of the machine learning model value.” BRI in light of lines 24-28 of Algorithm A in [Fig. 1] would support that “updating plural variables of the matrix based on the altered weight value” would encompass a set of mathematical computations and fall under the mathematical concepts grouping.
updating the priority queue to adjust a priority of the data coordinates based on the update to the plural variables – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). In Paragraph [0027] of the specification, it states “In executing line 30 of the program code 105, the processor 104 updates the priority queue Q to adjust a priority of the data coordinates based on the update to the plural variables.” BRI in light of line 30 of Algorithm A in [Fig. 1] would support that “updating the priority queue” would encompass a mathematical computation and fall under the mathematical concepts grouping.
Step 2A Prong 2 – The following additional limitations recited do not integrate the abstract idea into a practical application:
storing, in memory, program code for training a machine learning model and for preventing leakage of training data by the machine learning model subsequent to training – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). It recites a generic computer or generic computer components that merely act as a tool on which the method operates.
executing, in a processor, the program code stored in memory, the program code causing the processor to be configured to execute operations – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). It recites a generic computer or generic computer components that merely act as a tool on which the method operates.
in such a manner that any zero value in the sparse dataset is avoided in use while maintaining a same result – This limitation merely recites the idea of avoiding zero values in the dataset to maintain a same result but fails to recite details of how the same result is maintained or how the zero values are avoided. Reciting the idea of a solution or outcome without detailing how the result is accomplished is equivalent to saying "apply it" (see MPEP § 2106.05(f)) and thus, fails to integrate the exception into a practical application.
repeating steps f to i until the model has converged to a solution – This limitation recites an insignificant extra-solution activity of post-solution iteration (see MPEP § 2106.05(g)) and thus, fails to integrate the exception into a practical application.
Step 2B – The additional elements in Step 2A Prong 2, view individually or wholistically, do not provide an inventive concept or otherwise amount to significantly more than the abstract idea itself.
storing, in memory, program code for training a machine learning model and for preventing leakage of training data by the machine learning model subsequent to training – This limitation recites the well-understood, routine, conventional activity of storing and retrieving information in memory (see MPEP § 2106.05(d)) and thus, fails to provide significantly more to the judicial exception.
executing, in a processor, the program code stored in memory, the program code causing the processor to be configured to execute operations – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). Mere instructions to apply an exception using a generic computer component cannot provide an inventive concept.
in such a manner that any zero value in the sparse dataset is avoided in use while maintaining a same result – This limitation merely recites the idea of avoiding zero values in the dataset to maintain a same result but fails to recite details of how the same result is maintained or how the zero values are avoided. Reciting the idea of a solution or outcome without detailing how the result is accomplished is equivalent to saying "apply it" (see MPEP § 2106.05(f)) and thus, fails to provide significantly more to the judicial exception.
repeating steps f to i until the model has converged to a solution – This limitation recites the well-understood, routine, conventional activity of performing repetitive calculations (see MPEP § 2106.05(d)) and thus, fails to provide significantly more to the judicial exception.
As such, Claims 1, 5, and 9 are not patent eligible.
Dependent Claims
Claims 2-4 and 6-8 merely narrow the previously cited abstract idea limitations. For the reasons described above with respect to independent claims 1 and 5, these judicial exceptions are not meaningfully integrated into a practical application, nor amount to significantly more than the abstract idea itself. The claims disclose similar limitations described for the independent claims above and do not provide anything more than the mental processes that are practically capable of being performed in the human mind with the assistance of pen and paper and mathematical concepts that are achievable through mathematical computation. Therefore, claims 2-4 and 6-8 also recite abstract ideas that do not integrate into a practical application or amount to significantly more than the judicial exception, and are rejected under U.S.C. § 101.
Step 1 – Claims 2-4 are drawn to a method and claims 6-8 are drawn to a system. Therefore, each of these claims fall under one of the four categories of statutory subject matter (process/method, machine/product/apparatus, manufacture or composition of matter).
Step 2A Prong 1 – These claims are directed to a judicially recognized exception of an abstract idea without significantly more.
Claims 2 and 6:
multiplying the data coordinates in the priority queue by a scaling variable having a noise parameter – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C).
computing a threshold weight value for each feature to be used in training the machine learning model – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C).
generating plural groups of data coordinates of the matrix by populating each group with data coordinates that are randomly selected based on a proportionality of a corresponding weight value to the threshold weight value – This limitation is directed towards the abstract idea of a mathematical relationship, specifically organizing information and manipulating information through mathematical correlations (see MPEP § 2106.04(a)(2), section I, A).
computing a cumulative weight value for each group of data coordinates – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C).
comparing the cumulative weight value of a current group of the plural groups to the threshold weight value – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C).
selecting a new group of compiled data coordinates from the plural groups when the cumulative weight value of the current group is smaller than the threshold weight value – This limitation is directed towards the abstract idea of a mental process, or a concept that can be performed in the human mind, including observation, evaluation, judgement or opinion (see MPEP § 2106.04(a)(2), subsection III, C).
inspecting each data coordinate in the current group when the cumulative weight value of the current group is larger than the threshold weight value – This limitation is directed towards the abstract idea of a mental process, or a concept that can be performed in the human mind, including observation, evaluation, judgement or opinion (see MPEP § 2106.04(a)(2), subsection III, C).
Claims 3 and 7:
identifying the next data coordinate in the current group based on a result of the inspecting operation – This limitation is directed towards the abstract idea of a mental process, or a concept that can be performed in the human mind, including observation, evaluation, judgement or opinion (see MPEP § 2106.04(a)(2), subsection III, C).
Claims 4 and 8:
identifying data coordinates in the current group that were included in a previous comparison – This limitation is directed towards the abstract idea of a mental process, or a concept that can be performed in the human mind, including observation, evaluation, judgement or opinion (see MPEP § 2106.04(a)(2), subsection III, C).
subtracting a weight value of the identified data coordinates in the previous comparison from the threshold weight value – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C).
Step 2A Prong 2 – These limitations do not recite any additional elements which integrate the abstract idea into a practical application.
Claims 2 and 6:
repeating steps n to q to select the next priority item with randomness so that privacy is maintained according to a predetermined sensitivity – This limitation recites an insignificant extra-solution activity of post-solution iteration (see MPEP § 2106.05(g)) and thus, fails to integrate the exception into a practical application.
Step 2B – These limitations, as a whole, do not amount to significantly more than the judicial exception.
Claims 2 and 6:
repeating steps n to q to select the next priority item with randomness so that privacy is maintained according to a predetermined sensitivity – This limitation recites the well-understood, routine, conventional activity of performing repetitive calculations (see MPEP § 2106.05(d)) and thus, fails to provide significantly more to the judicial exception.
As such, Claims 2-4 and 6-8 are not patent eligible.
Claim Rejections - 35 USC § 103
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 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, 5, and 9 are rejected under 35 U.S.C. 103 as being unpatentable over Mangold et al. (“High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent”, published 10/21/2022), hereinafter Mangold; in view of Liu et al. (“Fast Sparse Classification for Generalized Linear and Additive Models”, published 05/20/2022), hereinafter Liu; in further view of Friedman et al. (“Regularization Paths for Generalized Linear Models via Coordinate Descent”, published January 2010), hereinafter Friedman.
Regarding Claim 1, Mangold recites A method for training a model (Mangold: “In this paper, we consider the classic central model of DP, where a trusted curator has access to the raw dataset and releases a model trained on this dataset.” [Section 2. Preliminaries]), the method comprising:
storing, in memory, program code for training a machine learning model and for preventing leakage of training data by the machine learning model subsequent to training; and executing, in a processor, the program code stored in memory (Mangold: “The algorithms are implemented in C++ for efficiency, together with a Python wrapper for simple use. It is provided as supplementary. Experiments are run on a computer with a Intel (R) Xeon (R) Silver 4114 CPU @ 2.20GHz and 64GB of RAM” [Appendix D. Experimental Details]), the program code causing the processor to be configured to execute operations including:
a. receiving a dataset populated predominately with zero data values as a sparse dataset (Mangold: “The first two datasets, coined log1 and log2, are synthetic. We generate a design matrix X ∈ R1,000×100 with unit-variance, normally-distributed columns. Labels are computed as y = Xw(true) + ε, where ε is normally-distributed noise and w(true) is drawn from a log-normal distribution of parameters µ = 0 and σ = 1 or 2 respectively. This makes w(true) quasi-sparse. The square dataset is generated similarly, with X ∈ R1,000×1,000 and w(true) having only 10 non-zero values.” [Section 5. Experiments]);
b. converting the sparse dataset into a matrix of plural data coordinates defined by a feature value and a column gradient (Mangold: “We start by defining two conjugate norms that will allow to keep track of coordinate-wise quantities. Let M = dialog(M1,…,Mp) with M1,…,Mp > 0, and [Equation]. When M is the identity matrix I, ‖۰‖M,1 is the standard l1-norm and ‖۰‖M,1,∞ is the l∞-norm.” [Section 2. Preliminaries]; “A common principle for releasing a private estimate of a function h : D → Rp is to perturb it with noise. To ensure privacy, the noise is scaled with the sensitivity ∆q(h) = supD∼D’ ‖h(D)−h(D’)‖q of h, with q = 1 for Laplace, and q = 2 for Gaussian mechanism. In coordinate descent methods, we release coordinate-wise gradients. The j-th coordinate of a loss function’s gradient ∇j l: Rp → R has sensitivity ∆1(∇jf) = ∆2(∇jf) (∇jf is a scalar).” [Section 2. Preliminaries]);
d. iteratively selecting a data coordinate, each coordinate indicating a next covariate to update in the machine learning model (Mangold: “As described in Section 3.1, DP-GCD updates only one coordinate per iteration, which is selected greedily as the (approximately) largest entry of the gradient so as to maximize the improvement in utility at each iteration.” [Section 3. Private Greedy CD]; “At an iteration t, data is accessed twice. First, to compute the index jt of the coordinate to update. It is obtained as the index of the largest noisy entry of f’s gradient, with noise Lap(λj’).” [Section 3.2 Privacy Guarantees]);
e. calculating based on the selected data coordinate, at least a gradient value of the matrix and a convergence gap value as a base convergence gap value of the machine learning model (Mangold: “At an iteration t, data is accessed twice. First, to compute the index jt of the coordinate to update. It is obtained as the index of the largest noisy entry of f’s gradient, with noise Lap(λj’). By the report-noisy-argmax mechanism, jt is ϵ’-DP. Second, to compute the gradient’s jt’s entry, which is released with noise Lap(λj). The Laplace mechanism ensures that this computation is also ϵ’-DP. Algorithm 1 is thus the 2T-fold composition of ϵ’-DP mechanisms, and the result follows from DP’s advanced composition theorem.” [Section 3.2 Privacy Guarantees]; “First, we use convexity of f to upper bound the decrease described in Lemma B.2. This gives Lemma B.3 in Appendix B.3.1, where the suboptimality gap f(wt+1) − f(w∗) at time t + 1 is upper bound by a function of the suboptimality gap f(wt) − f(w∗) at time t and the noise injected in step t. The novelty of our analysis lies in Lemma B.4, where examine the decrease of the objective. Specifically, we show that either (i) f(wt) is far from its minimum, and the suboptimality gap decreases with high probability, either (ii) f(wt) is close to its minimum, then all future iterates of DP-GCD will remain in a ball whose radius is determined by the variance of the noise.” [Appendix B.3. Utility for General Convex Functions]);
f. selecting a next data coordinate from the plural data coordinates, the next data coordinate corresponding to a next feature for training the model (Mangold: “As described in Section 3.1, DP-GCD updates only one coordinate per iteration, which is selected greedily as the (approximately) largest entry of the gradient so as to maximize the improvement in utility at each iteration.” [Section 3. Private Greedy CD]);
g. altering a weight value of the next feature to produce an altered weight value (Mangold: “At each iteration, DP-GCD (Algorithm 1) updates the parameter with the greatest gradient value (rescaled by the inverse square root of the coordinate-wise smoothness constant).” [Section 3.1 The Algorithm]);
h. updating plural variables of the matrix based on the altered weight value, the plural variables including at least the gradient and the base convergence gap value associated with training of the machine learning model (Mangold: “At an iteration t, data is accessed twice. First, to compute the index jt of the coordinate to update. It is obtained as the index of the largest noisy entry of f’s gradient, with noise Lap(λj’). By the report-noisy-argmax mechanism, jt is ϵ’-DP. Second, to compute the gradient’s jt’s entry, which is released with noise Lap(λj). The Laplace mechanism ensures that this computation is also ϵ’-DP. Algorithm 1 is thus the 2T-fold composition of ϵ’-DP mechanisms, and the result follows from DP’s advanced composition theorem.” [Section 3.2 Privacy Guarantees]; “First, we use convexity of f to upper bound the decrease described in Lemma B.2. This gives Lemma B.3 in Appendix B.3.1, where the suboptimality gap f(wt+1) − f(w∗) at time t + 1 is upper bound by a function of the suboptimality gap f(wt) − f(w∗) at time t and the noise injected in step t. The novelty of our analysis lies in Lemma B.4, where examine the decrease of the objective. Specifically, we show that either (i) f(wt) is far from its minimum, and the suboptimality gap decreases with high probability, either (ii) f(wt) is close to its minimum, then all future iterates of DP-GCD will remain in a ball whose radius is determined by the variance of the noise.” [Appendix B.3. Utility for General Convex Functions]); and
j. repeating steps f to i until the model has converged to a solution (Mangold: “In Appendix B.2, we prove a general descent lemma, which implies that iterates of DP-GCD converge (with high probability)to a neighborhood of the optimum. This property is proven rigorously in Appendix B.3.2, and we give the utility results for general convex functions in Appendix B.3.3. Under the additional assumption that the objective is strongly convex, we prove better utility bounds in Appendix B.4. These bounds follow from a key lemma (see Appendix B.4.1), which implies linear convergence to a neighborhood of the optimum.” [Appendix B. Proof of Utility]).
However, Mangold fails to expressly disclose c. generating a priority queue populated with the plural data coordinates; d. iteratively selecting a data coordinate from the priority queue; e. calculating based on the selected data coordinate, at least a first gradient value as a row gradient of the matrix, a second gradient value as a column gradient of the matrix, a dot product of the row gradient with a weight value of the feature associated with the first data coordinate, in such a manner that any zero value in the sparse dataset is avoided in use while maintaining a same result; f. selecting a next data coordinate from the plural data coordinates in the priority queue; h. updating plural variables of the matrix based on the altered weight value, the plural variables being located in rows of the matrix that include the next feature, the plural variables including at least the column gradient, and the dot product of each row of the matrix that includes the next feature in the matrix with the altered weight value; and i. updating the priority queue to adjust a priority of the data coordinates based on the update to the plural variables.
In the same field of endeavor, Liu teaches c. generating a priority queue populated with the plural data coordinates (Liu: “There are two main steps per iteration in these types of algorithms: (i) coordinate descent steps involving a line search along the objective function, often using a local surrogate function, and (ii) local swaps, where the support set (the set of features permitted to have nonzero coefficients) changes over iterations... For (ii), we find that the order in which we evaluate features plays an important role, which has been previously overlooked. We use a priority queue to dynamically manage the order of evaluating features.” [Section 1. Introduction]);
d. iteratively selecting a data coordinate from the priority queue (Liu: “Our second technique uses a priority queue to manage the search order for pairs of features to swap. At each outer iteration, we drop a feature j in the support and at each inner iteration, we evaluate adding a feature j′.” [Section 3. Overview of Fast Sparse Logistic Regression]);
f. selecting a next data coordinate from the plural data coordinates in the priority queue (Liu: “Our second technique uses a priority queue to manage the search order for pairs of features to swap. At each outer iteration, we drop a feature j in the support and at each inner iteration, we evaluate adding a feature j′.” [Section 3. Overview of Fast Sparse Logistic Regression]); and
i. updating the priority queue to adjust a priority of the data coordinates based on the update to the plural variables (Liu: “Update priority queue. If no alternative feature can replace feature j, we add feature j back into the support and rate feature j less promising in our priority queue. This allows us to explore features that have a better chance of being swapped with an alternative feature next time.” [Section 3. Overview of Fast Sparse Logistic Regression]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to have incorporated c. generating a priority queue populated with the plural data coordinates; d. iteratively selecting a data coordinate from the priority queue; f. selecting a next data coordinate from the plural data coordinates in the priority queue; and i. updating the priority queue to adjust a priority of the data coordinates based on the update to the plural variables, as taught by Liu to the method of Mangold because both of these methods are directed towards coordinate descent algorithms for training a machine learning model on a sparse dataset with methods for determining a next coordinate/feature to update. In making this combination and replacing Mangold’s greedy selection strategy with Liu’s priority queue, it would provide the method of Mangold with different selection strategy that ultimately seek to accomplish the same goal, that being to discourage “checking features that are unlikely to change the model’s support set, making the process of finding high-quality solutions more efficient”, while additionally allowing for the method to “dynamically manage the order of evaluating features”, as the queue is updated after each iteration (Liu: [Section 1. Introduction]).
Mangold and Liu still fail to expressly disclose e. calculating based on the selected data coordinate, at least a first gradient value as a row gradient of the matrix, a second gradient value as a column gradient of the matrix, a dot product of the row gradient with a weight value of the feature associated with the first data coordinate, in such a manner that any zero value in the sparse dataset is avoided in use while maintaining a same result; and h. updating plural variables of the matrix based on the altered weight value, the plural variables being located in rows of the matrix that include the next feature, the plural variables including at least the column gradient, and the dot product of each row of the matrix that includes the next feature in the matrix with the altered weight value.
In the same field of endeavor, Friedman teaches e. calculating based on the selected data coordinate, at least a first gradient value as a row gradient of the matrix, a second gradient value as a column gradient of the matrix, a dot product of the row gradient with a weight value of the feature associated with the first data coordinate, in such a manner that any zero value in the sparse dataset is avoided in use while maintaining a same result (Friedman: “Looking more closely at (5), we see that [Equation 7] where ^yi is the current fit of the model for observation i, and hence ri the current residual. Thus [Equation 8] because the xj are standardized. The first term on the right-hand side is the gradient of the loss with respect to Bj. It is clear from (8) why coordinate descent is computationally efficient. Many coefficients are zero, remain zero after the thresholding, and so nothing needs to be changed. Such a step costs O(N) operations--the sum to compute the gradient.” [Section 2.1. Naive updates]; “Further efficiencies can be achieved in computing the updates in (8). We can write the first term on the right (up to a factor 1/N) as [Equation 9] where
x
j
,
y
=
∑
i
=
1
N
x
i
j
y
i
. Hence we need to compute inner products of each feature with y initially, and then each time a new feature xk enters the model (for the first time), we need to compute and store its inner product with all the rest of the features (O(Np) operations). We also store the p gradient components (9). If one of the coefficients currently in the model changes, we can update each gradient in O(p) operations.” [Section 2.2. Covariance updates]; “We are sometimes faced with problems where the N x p feature matrix X is extremely sparse... Coordinate descent is ideally set up to exploit such sparsity, in an obvious way. The O(N) inner-product operations in either the naive or covariance updates can exploit the sparsity, by summing over only the non-zero entries.” [Section 2.3. Sparse updates]); and
h. updating plural variables of the matrix based on the altered weight value, the plural variables being located in rows of the matrix that include the next feature, the plural variables including at least the column gradient, and the dot product of each row of the matrix that includes the next feature in the matrix with the altered weight value (Friedman: “Looking more closely at (5), we see that [Equation 7] where ^yi is the current fit of the model for observation i, and hence ri the current residual. Thus [Equation 8] because the xj are standardized. The first term on the right-hand side is the gradient of the loss with respect to Bj. It is clear from (8) why coordinate descent is computationally efficient. Many coefficients are zero, remain zero after the thresholding, and so nothing needs to be changed. Such a step costs O(N) operations--the sum to compute the gradient.” [Section 2.1. Naive updates]; “Further efficiencies can be achieved in computing the updates in (8). We can write the first term on the right (up to a factor 1/N) as [Equation 9] where
x
j
,
y
=
∑
i
=
1
N
x
i
j
y
i
. Hence we need to compute inner products of each feature with y initially, and then each time a new feature xk enters the model (for the first time), we need to compute and store its inner product with all the rest of the features (O(Np) operations). We also store the p gradient components (9). If one of the coefficients currently in the model changes, we can update each gradient in O(p) operations.” [Section 2.2. Covariance updates]; “We are sometimes faced with problems where the N x p feature matrix X is extremely sparse... Coordinate descent is ideally set up to exploit such sparsity, in an obvious way. The O(N) inner-product operations in either the naive or covariance updates can exploit the sparsity, by summing over only the non-zero entries.” [Section 2.3. Sparse updates]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to have incorporated e. calculating based on the selected data coordinate, at least a first gradient value as a row gradient of the matrix, a second gradient value as a column gradient of the matrix, a dot product of the row gradient with a weight value of the feature associated with the first data coordinate, in such a manner that any zero value in the sparse dataset is avoided in use while maintaining a same result; and h. updating plural variables of the matrix based on the altered weight value, the plural variables being located in rows of the matrix that include the next feature, the plural variables including at least the column gradient, and the dot product of each row of the matrix that includes the next feature in the matrix with the altered weight value, as taught by Friedman to the method of Mangold and Liu because both of these methods are directed towards sparse updates of a feature matrix with coordinate descent. In making this combination and calculating and updating gradient variables in a matrix based on an altered weight value such that zero values are avoided, it would allow the method of Mangold and Liu to efficiently exploit the sparsity of the dataset to update the feature matrix and store the matrix efficiently with low computational cost (Friedman: [Sections 2.1-2.4]).
Regarding Claims 5 and 9, they are system and computer program product claims that correspond with the method of Claim 1. Therefore, they are rejected for the same reasons as Claim 1 above.
Claims 2-4 and 6-8 are rejected under 35 U.S.C. 103 as being unpatentable over Mangold in view of Liu and Friedman, as applied to Claims 1 and 5 above, in further view of Hubschle-Schneider et al. (“Parallel Weighted Random Sampling”, published 09/10/2022), hereinafter Hubschle-Schneider.
Regarding Claim 2, Mangold, Liu, and Friedman teach the method of Claim 1, wherein the program code causes the processor to select a next data coordinate for analysis by performing operations including:
k. multiplying the data coordinates in the priority queue by a scaling variable having a noise parameter (Mangold: “At each iteration, DP-GCD (Algorithm 1) updates the parameter with the greatest gradient value (rescaled by the inverse square root of the coordinate-wise smoothness constant). This corresponds to the Gauss-Southwell-Lipschitz rule (Nutini et al., 2015). To guarantee privacy, this selection is done using the report-noisy-max mechanism (Dwork and Roth, 2013) with noise scales λj’ along j-th entry (j ∈ [p]). DP-GCD then performs a gradient step with step size γj > 0 along this direction.” [Section 3.1 The Algorithm]);
However, they fail to expressly disclose l. computing a threshold weight value for each feature to be used in training the machine learning model; m. generating plural groups of data coordinates of the matrix by populating each group with data coordinates that are randomly selected based on a proportionality of a corresponding weight value to the threshold weight value; n. computing a cumulative weight value for each group of data coordinates; o. comparing the cumulative weight value of a current group of the plural groups to the threshold weight value; p. selecting a new group of compiled data coordinates from the plural groups when the cumulative weight value of the current group is smaller than the threshold weight value; q. inspecting each data coordinate in the current group when the cumulative weight value of the current group is larger than the threshold weight value; and r. repeating steps n to q to select the next priority item with randomness so that privacy is maintained according to a predetermined sensitivity.
In the same field of endeavor, Hubschle-Schneider teaches l. computing a threshold weight value for each feature to be used in training the machine learning model (Hubschle-Schneider: “During each batch, a PE inserts into its local reservoir all items whose key is smaller than the largest key of any item in the sample (the global threshold). When a batch finishes, the PEs perform a distributed selection for the k-th smallest key, which becomes the new global threshold, and discard all items with larger keys.” [Section 9.2 Weighted Reservoir Sampling]);
m. generating plural groups of data coordinates of the matrix by populating each group with data coordinates that are randomly selected based on a proportionality of a corresponding weight value to the threshold weight value (Hubschle-Schneider: “We adapt the streaming algorithm of Efraimidis and Spirakis [27] to a distributed (mini-)batch streaming model (also known as discretized streams), where PEs process a sequence of variable size batches of items one at a time. After processing a batch, the task is to update the sample to be a uniform (or weighted) random sample without replacement of size min(k,n′) of all n′ items seen so far, up to and including the items of the current batch.” [Section 9. Sampling with a Reservoir]);
n. computing a cumulative weight value for each group of data coordinates (Hubschle-Schneider: “Let vi denote the key of item i, that is, the exponentially distributed variate associated with it, and define T := maxi∈Rvi as the threshold value, i.e., the largest key of any item in the reservoir. Then, the amount of weight to be skipped is exponentially distributed with rate T, which can be computed as X := −ln(rand())/T, where rand() is uniformly random in (0,1].” [Section 9.2 Weighted Reservoir Sampling]);
o. comparing the cumulative weight value of a current group of the plural groups to the threshold weight value (Hubschle-Schneider: ““Let vi denote the key of item i, that is, the exponentially distributed variate associated with it, and define T := maxi∈Rvi as the threshold value, i.e., the largest key of any item in the reservoir. Then, the amount of weight to be skipped is exponentially distributed with rate T, which can be computed as X := −ln(rand())/T, where rand() is uniformly random in (0,1]. The key associated with the newly sampled item j is thenvj := −ln(rand(e−Twj,1))/wj, with rand(a,b) := a+rand()(b−a).The range of this variate has been chosen so that vj is less than T, as it has already been determined that item j must be part of the reservoir.” [Section 9.2 Weighted Reservoir Sampling]; “Keeping the threshold fixed for the duration of each batch is correct because the set of all items above any threshold always forms a weighted random sample (whose size is not known a priori). Here, the threshold is chosen so that the sample size is guaranteed to be at least k, and the selection process determines a new threshold to restore a fixed sample size of k items.” [Section 9.2 Weighted Reservoir Sampling]);
p. selecting a new group of compiled data coordinates from the plural groups when the cumulative weight value of the current group is smaller than the threshold weight value (Hubschle-Schneider: “Secondly, the algorithm globally maintains the threshold T, which is the same at all Pes and does not change during a batch. The PEs process their items using the skip distance method described above, inserting the new candidate sample items into their local reservoirs.” [Section 9.2 Weighted Reservoir Sampling]);
q. inspecting each data coordinate in the current group when the cumulative weight value of the current group is larger than the threshold weight value (Hubschle-Schneider: “once all items of the batch are processed, the PEs jointly select the globally k-th smallest key (see Section 2.5) in the union of all local reservoirs. This key becomes the insertion threshold for the next batch. Each PE then discards all items with larger keys using a split operation on its local reservoir.” [Section 9.2 Weighted Reservoir Sampling]); and
r. repeating steps n to q to select the next priority item with randomness so that privacy is maintained according to a predetermined sensitivity (Hubschle-Schneider: “We adapt the streaming algorithm of Efraimidis and Spirakis [27] to a distributed (mini-)batch streaming model (also known as discretized streams), where PEs process a sequence of variable size batches of items one at a time. After processing a batch, the task is to update the sample to be a uniform (or weighted) random sample without replacement of size min(k,n′) of alln′ items seen so far, up to and including the items of the current batch.” [Section 9. Sampling with a Reservoir]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to have incorporated l. computing a threshold weight value for each feature to be used in training the machine learning model; m. generating plural groups of data coordinates of the matrix by populating each group with data coordinates that are randomly selected based on a proportionality of a corresponding weight value to the threshold weight value; n. computing a cumulative weight value for each group of data coordinates; o. comparing the cumulative weight value of a current group of the plural groups to the threshold weight value; p. selecting a new group of compiled data coordinates from the plural groups when the cumulative weight value of the current group is smaller than the threshold weight value; q. inspecting each data coordinate in the current group when the cumulative weight value of the current group is larger than the threshold weight value; and r. repeating steps n to q to select the next priority item with randomness so that privacy is maintained according to a predetermined sensitivity, as taught by Hubschle-Schneider to the method of Mangold, Liu, and Friedman because both of these methods are directed towards targeted sorting and sampling of features through use of a priority queue. In making this combination and allowing for weight-based sample skipping, it would allow the method of Mangold, Liu, and Friedman to reduce computational costs, allowing for “faster and numerically more efficient generation in practice” (Hubschle-Schneider: [Section 9.2 Weighted Reservoir Sampling]).
Regarding Claim 3, Mangold, Liu, Friedman, and Hubschle-Schneider teaches the method of Claim 2, wherein the operation comprises: identifying the next data coordinate in the current group based on a result of the inspecting operation (Hubschle-Schneider: “Operation split(T,x) outputs two trees T≤ and T> such that T≤ contains {e ∈ T : e ≤ x} and T> contains T\T≤, function rank(x) computes |{e ∈ T : e ≤ x}|, and function select(k) finds the element with rank k in T.” [Section 9.2 Weighted Reservoir Sampling]).
Regarding Claim 4, Mangold, Liu, Friedman, and Hubschle-Schneider teaches the method of Claim 2, wherein the operation of compiling a current group of random data coordinates comprises:
identifying data coordinates in the current group that were included in a previous comparison (Hubschle-Schneider: “More efficient algorithms for WRS–N repeatedly sample an item and remove it from the dis tribution using a dynamic data structure.” [Section 3.2. Sampling without Replacement (Problems WRS-N and WRP)]; “A common approach to sampling without replacement is to sample with replacement and reject items that were already sampled.” [Section 6. Sampling without Replacement (Problem WRS-N)); and
subtracting a weight value of the identified data coordinates in the previous comparison from the threshold weight value (Hubschle-Schneider: “WRS–N: Sample k pairwise unequal items s1 ≠ ··· ≠ sk without replacement such that for any sample index j ∈ 1..k and
i
∉
s
l
l
<
j
,
P
s
j
=
i
=
w
i
/
(
W
-
∑
l
<
j
w
s
l
)
.” []).
Regarding Claims 6-8, they are system claims that correspond with the method of Claims 2 and 3. Therefore, they are rejected for the same reasons as Claims 2-4.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Jaggi (“Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization”) discusses a framework for convex optimization over matrix factorizations, in which a low-rank update is performed in every Frank-Wolfe iteration.
Efraimidis et al. (“Weighted random sampling with a reservoir”) presents new algorithms for weighted random sampling.
Osokin et al. (“Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs”) discusses improvements on the block-coordinate Frank-Wolfe algorithm, including adaptive non-uniform gap-based sampling and pairwise and away-step variants of Frank-Wolfe in the block-coordinate setting.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MEGAN E HWANG whose telephone number is (703)756-1377. The examiner can normally be reached Monday-Thursday 10:00AM-7:30PM ET.
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, Jennifer Welch can be reached at (571) 272-7212. 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.
/M.E.H./Examiner, Art Unit 2143 /JENNIFER N WELCH/Supervisory Patent Examiner, Art Unit 2143
Prosecution Insights