DETAILED ACTION
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 .
This office action is in response to submission of application on 10/24/2023.
Claims 1-20 are presented for examination.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 10/24/2023 and 05/19/2026 is/are in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Drawings
The Drawings filed on 10/24/2023 are acceptable for examination purposes.
Specification
The Specification filed on 10/24/2023 is acceptable for examination purposes.
Drawings
The drawings are objected to as failing to comply with 37 CFR 1.84(p)(4) because:
Reference characters "140-1, ..., 140-N" [¶0025] and "145-1, …, 145-N” [Figure 1] have both been used to designate “Examples”.
Reference character “140” has been used to designate both “Batch” [Figure 1 and ¶0033] and “Examples” [¶0025].
Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended.” If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
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-4, 9-12, and 16-19 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. The analysis of the claims will follow the 2019 Revised Patent Subject Matter Eligibility Guidelines (“2019 PEG”).
Independent Claims
Step 2A Prong One: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes, independent claim 1 recites an abstract idea in the form of mental processes. A mental process is a process that “can be performed in the human mind, or by a human using a pen and paper” (MPEP § 2106.04(a)(2)(III), paragraph 1). Examples of mental processes include “observations, evaluations, judgments, and opinions” (MPEP § 2106.04(a)(2)(III), paragraph 2).
The following limitations of claims 1 are mental processes:
Identifying a plurality of nodes included in a plurality of decision trees of a tree-based ensemble model; [This is a mental process that can be performed by observations, evaluations, judgements, and opinions. No specific methodology for identifying is recited in the claim; therefore, it broadly encompasses methods that can be performed as a mental process.]
Determining, from the plurality of nodes, a first set of nodes where each node represents a unique combination of a feature and a threshold; [This is a mental process that can be performed by observations, evaluations, judgements, and opinions. This limitation further defines the structure of the nodes and no specific method of node selection is defined in the spec; therefore, it broadly encompasses methods that can be performed as a mental process.]
Assigning distinct identifiers to the nodes of the first set; [This is a mental process that can be performed by observations, evaluations, judgements, and opinions. [¶0052] “The distinct identifiers may be provided in any suitable form, such as sequential numbers, arbitrarily assigned values, …”; Both sequential numbering or arbitrarily assigning values as identifiers can be performed in the human mind, or by a human using a pen and paper.
Identifying a second set of paths included in the plurality of decision trees; [This is a mental process that can be performed by observations, evaluations, judgements, and opinions. No specific methodology for identifying is recited in the claim; therefore, it broadly encompasses methods that can be performed as a mental process.]
Generating an optimized model, where each path of the second set is represented using the distinct identifiers that correspond to the respective nodes along the path, and branch directions taken from the respective nodes. [While an optimized model is generated, this process does not involve training or deploying the model. This is a combination of organizing and relabeling a series of trees and as such is a mental process: observation, evaluation, judgement, opinions, something that can done with the human mind, or with the aid of pen and paper (MPEP § 2106.06(a)(2)(III)).]
Therefore, the independent claims recite a judicial exception.
Step 2A Prong Two: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No additional claim elements are recited; therefore, under MPEP § 2106.04(d), the judicial exception is not integrated into a practical application.
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
There are no additional elements recited, as such the claim does not provide a practical application and is not considered to be significantly more.
Claims 8 and 15 are substantially similar in scope and spirit to claim 1. Therefore, they would be rejected under similar analysis.
Dependent Claims
The remaining dependent claims being rejected do not recite additional elements, whether considered individually or in combination, that are sufficient to integrate the judicial exception into a practical application or amount to significantly more than the judicial exception.
Claims 2, 9, & 16:
Step 2A Prong One: There are no additional abstract idea limitations.
Step 2A Prong Two:
wherein each path of the second set represents a unique path from a root node to a leaf node of a respective decision tree of the plurality of decision trees. [This additional element does no more than generally link the use of a judicial exception to a particular technological environment or field of use (MPEP § 2106.05(h)). These limitations merely describe the details of the path as a technology environment therefore rejected under step 2A, Prong2 and step 2B]
Claims 3, 10, & 17:
Step 2A Prong One:
wherein determining the first set of nodes comprises: removing one or more duplicate nodes, from the plurality of nodes, having a same feature and a same threshold as one or more other nodes of the plurality of nodes. [This is a mental process that can be performed by observations, evaluations, judgements, and opinions.]
Step 2A Prong Two and Step 2B:
There are no additional elements recited, as such the claim does not provide a practical application and is not considered to be significantly more.
Claim 4, 11, & 18:
Step 2A Prong One:
further comprising: quantizing, prior to determining the first set of nodes, the plurality of nodes to produce the one or more duplicate nodes. [This is a mental process that can be performed by observations, evaluations, judgements, and opinions.]
Step 2A Prong Two and Step 2B:
There are no additional elements recited, as such the claim does not provide a practical application and is not considered to be significantly more.
Claim 5, 12, & 19:
Step 2A Prong One: There are no additional abstract idea limitations.
Step 2A Prong Two:
encrypting the optimized model using a fully homomorphic encryption algorithm; [This additional element is mere recitation that a judicial exception is to be performed using generic computer equipment running general class of computer algorithms in their ordinary capacity, therefore rejected under step 2A, Prong 2 and step 2B (MPEP § 2106.05(f)). Although advantages of using a fully homomorphic encryption (FHE) algorithm are noted within the specification, FHE is a well-known algorithm and the act of encryption does not amount to more than applying a general class of algorithms using generic computer equipment.]
transmitting the encrypted, optimized model to a computing device […] [The steps of collecting information, storing, electronically sending requests, electronically receiving feedback, and presenting are routine data gathering and output steps are well-understood, routine and conventional activities recognized by the Courts (MPEP § 2106.05(d)(II)). Using a generic computer and/or general class of computer algorithms with well-understood, routine, conventional activities to implement the abstract idea does not amount to significantly more than the abstract idea itself. Therefore, rejected under step 2A Prong 2 and Step 2B]
included in an untrusted domain. [This additional element does no more than generally link the use of a judicial exception to a particular technological environment or field of use, therefore rejected under step 2A Prong 2 and Step 2B (MPEP § 2106.05(h)). This element merely limits performance of the abstract idea to a particular computing environment, namely an untrusted domain, and therefore does not integrate the judicial exception into a practical application or amount to significantly more than the abstract idea itself.]
The following references are relied upon for the art rejection set forth below
Peterson et al. Reducing Decision Tree Ensemble Size Using Parallel Decision DAGS, July 2009, hereinafter Peterson
Bolelli et al. One DAG to Rule Them All, July 2022, hereinafter Bolelli
Frery et al. Privacy-Preserving Tree-Based Inference with Fully Homomorphic Encryption, March 2023, hereinafter Frery
Sarpatwar et al. Efficient Encrypted Inference on Ensembles of Decision Trees, March 2023, hereinafter Sarpatwar
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 1-3 are rejected under 35 U.S.C. 103 as being unpatentable over Peterson, in view of Bolelli.
Regarding Claim 1, Peterson discloses A method comprising: Identifying a plurality of nodes included in a plurality of decision trees of a tree-based ensemble model; [Peterson: Abstract] “an ensemble of decision tree” [Peterson: §2 ¶2] “During classification, the tree is traversed from the root node down to a single leaf node by examining a feature attribute at each branching node”. Peterson teaches a method of compressing a decision tree ensemble, a person having ordinary skill in the art would understand a tree ensemble to include a plurality of decision trees, each tree containing a plurality of nodes. An example of this structure will be provided in a secondary reference.
Determining, from the plurality of nodes, a first set of nodes where each node represents a unique combination of a feature and a threshold. [Peterson: Algorithm 1] “Return the model, a list of root nodes with shared children” [Peterson: §3 ¶1] “Nodes which perform the same function can be collapsed into a single node…Two nodes are equivalent if both are real-valued nodes which split on the same attribute, have the same threshold…” By identifying and collapsing equivalent nodes into parallel nodes, Peterson is creating a list of nodes that have a unique combination of splitting attribute (feature) and thresholds.
Generating an optimized model […], [Peterson: Abstract] “represent an ensemble of decision trees while using significantly less storage.” Reducing the resource consumption of a model is reasonably comparable to optimizing a model.
Peterson does not specifically teach: Assigning distinct identifiers to the nodes of the first set. Identifying a second set of paths included in the plurality of decision trees. And […] where each path of the second set is represented using the distinct identifiers that correspond to the respective nodes along the path, and branch directions taken from the respective nodes.
However, Bolelli in the same field of endeavor discloses methods of uniquely identifying nodes and paths in a decision tree forest, or tree ensemble.
Assigning distinct identifiers to the nodes of the first set. [Bolelli: §2.1 Definition 1 ] “(3) Each internal node is labeled with an index i ∈ Dx … with left and right outgoing edges labeled respectively with 0 and 1; (4) Root to leaf paths uniquely identify cubes … by means of nodes and edges labels”. The indexing of nodes combined with per node branch directions distinctly identifies each node’s position for path reconstruction and reasonably corresponds to assigning distinct identifiers to nodes as claimed.
Identifying a second set of paths included in the plurality of decision trees. [Bolelli: §2.1 Definition 1] “root to leaf paths uniquely identify cubes associated to leaves by means of nodes and edges labels.” These uniquely identified root to leaf paths through the decision structure reasonably correspond to the second set of paths within the plurality of decision trees.
where each path of the second set is represented using the distinct identifiers that correspond to the respective nodes along the path, and branch directions taken from the respective nodes. [Bolelli: §2.1 Definition 1] “Each internal node is labeled with an index … with left and right outgoing edges labeled respectively with 0 and 1; Root to leaf paths uniquely identify cubes associated to leaves by means of nodes and edges labels.” The combination of Peterson and Bolelli reasonably corresponds to this distinctly labeled and optimized model, with the motivation to combine as previously disclosed.
Additionally, Bolelli demonstrates a tree ensemble to include a plurality of decision trees, each tree containing a plurality of nodes as seen in Fig 6(a).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the optimization techniques taught by Bolelli with the tree ensemble compression method of Peterson because [Bolelli: Abstract] “the proposed algorithmic solutions allow to combine different optimization techniques and significantly improve performance… When compared to existing approaches –in 2D and 3D–, implementations … perform significantly better than previous state-of-the-art algorithms, both on CPU and GPU.”
Regarding claim 2, Peterson in view of Bolelli discloses the method of claims 1, wherein each path of the second set represents a unique path from a root node to a leaf node of a respective decision tree of the plurality of decision trees. [Bolelli: §2.1 Definition 1] “Root to leaf paths uniquely identify cubes associated to leaves by means of nodes and edges labels.” Each root to leaf path reasonably corresponds to a unique path through the decision structure from a root node to a leaf node.
Regarding claim 3, Peterson in view of Bolelli discloses the method of claims 1, wherein determining the first set of nodes comprises: removing one or more duplicate nodes, from the plurality of nodes, having a same feature and a same threshold as one or more other nodes of the plurality of nodes. [Peterson: §3 ¶1] “Nodes which preform the same function can be collapsed into a single node while preserving the overall behavior. This is done by … removing redundant nodes. Two nodes are equivalent if: both are real-valued nodes which split on the same attribute, have the same threshold…”. This method of collapsing, or merging equivalent nodes reasonably corresponds to removing duplicate nodes as claimed.
Claims 4, 5, 8-12, and 15-19 are rejected under 35 U.S.C. 103 as being unpatentable over the Peterson in view of Bolelli, further in view of Frery.
Regarding claim 4, the combination of Peterson and Bolelli discloses the method of claims 3.
The combination of Peterson and Bolelli does not specifically teach quantizing, prior to determining the first set of nodes, the plurality of nodes to produce the one or more duplicate nodes.
However, Frery in the same field of endeavor discloses the above limitation. [Frery: §4.1 ¶1] “decision thresholds are converted to integer and prediction values (in terminal leaves) are quantized” converting threshold values to integer representations is comparable to quantization of the threshold values associated with the nodes. As earlier discussed, Peterson defines nodes by conditions including threshold values and uses these values to determine node equivalency. Therefore, this method of quantizing prediction values and thresholds reasonably corresponds to that which is claimed.
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate Frery’s Fully Homomorphic Encryption techniques, including quantization, with the tree ensemble compression method of Peterson because it is [Frery: Abstract] “…a way to protect the privacy of data while still allowing for data analysis” and “a powerful tool that allows for arbitrary computations to be performed on encrypted data”. Additionally, applying FHE to tree-based models offers state-of-the-art solutions over encrypted tabular data and “is applicable to a wide range of tree-based models, including decision trees, random forests, …”.
Regarding claim 5, the combination of Peterson and Bolelli discloses the method of claim 1.
The combination of Peterson and Bolelli does not disclose encrypting the optimized model using a fully homomorphic encryption algorithm; and transmitting the encrypted, optimized model to a computing device included in an untrusted domain.
However, Frery in the same field of endeavor teaches fully homomorphic encryption (FHE) [Frery: §4.1] “the process of converting the model to its FHE equivalent… FHE binary is produced… that implements every FHE operations.” and deployment of a model [Frery: §5] “providing a secure mechanism for the deployment of machine learning models by service providers” in an untrusted domain. [Frery: §1 Existing art] “allows for the execution of virtually complex computations on untrusted servers.” As stated above, the combination of Frery’s FHE and Peterson’s tree ensemble compression would have been obvious to one of ordinary skill in the art prior to the effective filing date.
Claims 8-12 disclose a computer program product that implement the method of claims 1-5 respectively, with substantially the same limitations. Therefore, the rejection applied to claims 1-5 also applies. In addition, Frery discloses A computer program product comprising: a computer-readable storage medium having computer-readable program code embodied therewith, the computer-readable program code executable by one or more computer processors to perform an operation [Frery: §4.1] “The FHE binary is produced by Concrete-Compiler land implements every FHE operations… Once the model is trained and compiled, the user can use Concrete-ML Python API to encrypt, quantize/dequantize and run the FHE execution easily.” The compiled FHE binary and Concrete-ML implementation corresponds to executable program code for performing the disclosed operations.
Claims 15-19 disclose a system that implements the method of claims 1-5 respectively, with substantially the same limitations. Therefore, the rejection applied to claims 1-5 also applies. In addition, Frery discloses A system comprising: a memory storing a tree-based ensemble model; and one or more processors to: [Frery: §4.1] ”A tree-based model is trained… Once the model is trained and compiled, the user can use Concrete-ML Python API to encrypt, quantize/dequantize and run the FHE execution easily.” The trained and compiled tree-based model corresponds to the model stored in memory, and running the FHE execution corresponds to execution by one or more processors.
Claims 6, 7, 13, 14, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over the Peterson in view of Bolelli and Frery, further in view of Sarpatwar (Cited by Applicant on IDS dated 10/24/2023).
Regarding claim 6, the combination of Peterson, Bolelli, and Frery discloses the method of claim 5.
The combination of Peterson, Bolelli, and Frery does not teach encrypting data of one or more examples using the fully homomorphic encryption algorithm; transmitting an inference request to an inference service executing on the computing device, the inference request including the encrypted data; receiving one or more encrypted scores from the inference service corresponding to the one or more examples, each of the one or more encrypted scores indicating which path of the second set to use for the respective example; and decrypting the one or more encrypted scores to infer one or more labels corresponding to the one or more examples.
However, Sarpatwar in the same field of endeavor does disclose [Sarpatwar: §1] “An FHE scheme can be defined as: H = (ℇ, Ɗ, λ, Eval), where ℇ and Ɗ represent encryption and decryption operations … The client encrypts its data x and sends the encrypted data ℇ(x) to the cloud. The service provider… performs inference computation in the encrypted domain … and returns the encrypted result back to the client for decryption.” Therefore, Sarpatwar teaches FHE to encrypt the data prior to being transmitted for inference and the inference service returns the encrypted inference result to the client for decryption.
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the encryption methods of Sarpatwar, with the tree ensemble compression method of Peterson. Motivation to use this system is that it is [Sarpatwar: Abstract] “… highly scalable and can perform efficient inference on batched encrypted data with amortized time in milliseconds. This is approximately three orders of magnitude faster than the standard approach…”. As the optimized model of claims 1-5 represents decision tree paths, it would also be understood by a person having ordinary skill in the art that the encrypted inference result would correspond to the traversal path selected for the example and therefore indicate the path used.
Regarding claim 7, the combination of Peterson, Bolelli, Frery, and Sarpatwar discloses the method of claim 6. Additionally, Frery teaches quantizing the data of the one or more examples prior to encrypting the data. [Frery §4.1 ¶2] “Both input and output quantizer remain at the user’s disposal as they are needed to pre/post process the data before and after FHE execution.” The input quantizer for pre-processing the data reasonably corresponds to quantizing the data before encrypting the data.
Claims 13 & 14 disclose a computer program product that implement the method of claims 6 & 7 respectively, with substantially the same limitations. Therefore, the rejection applied to claims 6 & 7 also applies. The rejections made to the additional limitations of independent claim 8 is also applied as above.
Claim 20 disclose a system that implements the method of claim 6, with substantially the same limitations. Therefore, the rejection applied to claims 6 also applies. The rejections made to the additional limitations of independent claim 15 is also applied as above.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Frery et al. “Privacy-Preserving Tree-Based Inference with TFHE”
Fully homomorphic encryption as applied to ensemble-based decision trees, including encrypted, quantization, and model compression.
Ratha et al. US20210376995 “Privacy-Enhanced Decision Tree-Based Inference on Homomorphically-Encrypted Data”
Deploying decision tree in encrypted environment and runs inference on encrypted input data without decryption.
Lucchese et al. “QuickScorer: A Fast Algorithm to Rank Documents with Additive Ensembles of Regression Trees”
Decision-tree ensemble models and node structures, including feature tests, thresholds and bit vector representation evaluation structure.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to GRANT F FITCH whose telephone number is (571)270-0621. The examiner can normally be reached Bi-Week M-F 7-3 Friday Flex.
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, Miranda Huang can be reached at (571) 270-7092. 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.
/G.F.F./Examiner, Art Unit 2124
/MIRANDA M HUANG/ Supervisory Patent Examiner, Art Unit 2124
Prosecution Insights