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 .
Response to Arguments
Applicant's arguments filed 11/13/2025 have been fully considered but they are not fully persuasive.
Regarding the 101 rejections, on page 10 of “Remarks” applicant contends that the amended claim 1 does not recite abstract ideas under Step 2A Prong 1 as the claims are performed with a processor, or computer, and a column generation operation. The examiner respectfully disagrees. Under the broadest reasonable interpretation, performing a column generation on a feature graph by performing an intersection of samples to paths of the feature graph is interpreted as a mathematical calculation of using a column generation calculation to find intersecting values, a mathematical calculation is considered a mathematical concept (MPEP 2106)). The mention of the abstract ideas being performed by a processor, or computer, does not mean that the claim no longer recites abstract ideas. The processor is interpreted as a generic computer component that is used merely as a tool to perform abstract ideas (MPEP 2106.05(f)). Therefore, the inclusion of a processor and column generation does not overcome the abstract ideas in claim 1.
On pages 11-12 of “Remarks” applicant contends that the amended claim 1 provides a practical application under Step 2A Prong 2. The examiner respectfully disagrees. Applicant argues that the improvement to the technology field of decision trees comes from the added benefits of using the column generation and mixed integer programming for optimization. It appears that the proposed improvement in this case is only realized because of the specific mathematical concepts (MIP and column generation) used in the claim. The judicial exception itself cannot provide the improvement. See MPEP 2106.05(a): “It is important to note, the judicial exception alone cannot provide the improvement. The improvement can be provided by one or more additional elements.”
On page 13 of “Remarks” applicant contends that the amended claim 1 recites additional elements that are not well understood, routine, or conventional activities under Step 2B. The examiner respectfully disagrees. As discussed above, the amended limitations of claim 1 still recite mental process abstract ideas. Additionally, the mention of performing the identified abstract ideas using a computer, under the broadest reasonable interpretation, merely recite steps that apply generic computer components to perform an abstract idea which represents merely adding the words “apply it”, or an equivalent, which are not indicative of an inventive concept (MPEP 2106.05(f)). Under Step 2B, the courts have found that adding the words “apply it”, or an equivalent, with the judicial exception does not qualify as significantly more under Step 2B (MPEP 2106.05). Therefore, applicant’s arguments regarding the 101 rejections are not persuasive.
Regarding the 103 rejections, applicant's arguments filed with respect to the prior art Penberthy are persuasive and therefore the rejections under Penberthy are withdrawn. Applicant has amended the claims to recite new combinations of limitations and a new combination of references is applied below. Please see below for new grounds of rejection, necessitated by Amendment.
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-11 and 13-20 are rejected under 35 U.S.C 101 because the claimed invention is directed to an abstract idea without significantly more.
Regarding claim 1, in step 1 of the 101 analysis set forth in MPEP 2106, the claim recites A computer-implemented method of decision tree machine learning,. The claim recites a method. A method is one of the four statutory categories of invention.
In Step 2A, Prong 1 of the 101 analysis set forth in MPEP 2106, the examiner has determined that the following limitations recite a process that, under broadest reasonable interpretation, covers a mental process or mathematical concept but for the recitation of generic computer components:
splitting a decision tree associated with a path-based machine learning model into a plurality of multiway decision trees in a path-based formulation, each of the plurality of multiway decision trees having an attribute not occurring more than once in each of the plurality of multiway decision trees; (i.e., the broadest reasonable interpretation includes a step of evaluation and judgement and could be performed mentally or with pen and paper like creating decision trees from unique paths, which is either a mental process of evaluation/judgement (MPEP 2106)).
and solving a problem associated with the path-based machine learning model using one or more multiway decision trees of the plurality of multiway decision trees, wherein: a multiway decision tree of the one or more multiway decision trees includes one or more decision rules that are mapped using a mixed-integer program (MIP), (i.e., the broadest reasonable interpretation includes mathematical calculation of using MIP to map decision rules, a mathematical calculation is considered a mathematical concept (MPEP 2106)).
the solving of the problem associated with the path-based machine learning model includes performing a column generation (CG) operation on a feature graph, (i.e., the broadest reasonable interpretation includes mathematical calculation of using column generation on a graph, a mathematical calculation is considered a mathematical concept (MPEP 2106)).
and the CG operation includes performing intersection of training samples of a plurality of nodes of a path of a plurality of paths in the feature graph. (i.e., the broadest reasonable interpretation includes mathematical calculation of using a column generation calculation to find intersecting values, a mathematical calculation is considered a mathematical concept (MPEP 2106)).
If the claim limitations, under their broadest reasonable interpretation, covers activities classified under Mental processes: concepts performed in the human mind (including observation, evaluation, judgement, or opinion) (see MPEP 2106.04(a)(2), subsection (III)) or Mathematical concepts: mathematical relationships, mathematical formulas or equations, or mathematical calculations (see MPEP 2106.04(a)(2), subsection (I)). Accordingly, the claim recites an abstract idea.
In Step 2A, Prong 2 of the 101 analysis, set forth in MPEP 2106, the examiner has determined that the following additional elements do not integrate this judicial exception into a practical application:
the computer-implemented method comprising: (i.e., the generic computer components recited in this limitation merely add the words “apply it”, or an equivalent, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea (MPEP 2106.05(f))).
Since the claim does not contain any other additional elements, that amount to integration into a practical application, the claim is directed to an abstract idea.
In Step 2B of the 101 analysis set forth in the 2019 PEG, the examiner has determined that the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception:
Regarding limitation (V), under the broadest reasonable interpretation, merely recite steps that apply generic computer components to perform judicial exceptions, which represents merely adding the words “apply it”, or an equivalent, which are not indicative of an inventive concept (MPEP 2106.05(f)). Considering additional elements individually and in combination, and the claim as a whole, the additional elements do not provide significantly more than the abstract idea. Therefore, the claim is not patent eligible.
Regarding claim 2, it is dependent upon claim 1 and fails to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. For example, claim 2 recites wherein the decision tree comprises a multiway decision tree. Under the broadest reasonable interpretation merely recite steps that applies a multiway decision tree to perform a judicial exception, which represents merely adding the words “apply it”, or an equivalent, which are not indicative of an inventive concept (MPEP 2106.05(f)). Therefore, claim 2 does not solve the deficiencies of claim 1.
Regarding claim 3, it is dependent upon claim 1 and fails to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. For example, claim 3 recites wherein the solving of the problem associated with the path-based machine learning model further includes providing a restricted master program version of the plurality of multiway decision trees. Under the broadest reasonable interpretation merely recite steps that applies a restricted master program to perform a judicial exception, which represents merely adding the words “apply it”, or an equivalent, which are not indicative of an inventive concept (MPEP 2106.05(f)). Therefore, claim 3 does not solve the deficiencies of claim 1.
Regarding claim 4, it is dependent upon claim 3 and fails to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. For example, claim 4 recites wherein the solving of the problem associated with the path-based machine learning model further includes finding multiway regression trees using the MIP. Under the broadest reasonable interpretation, the limitations recite determining decision trees using a MIP calculation which is interpreted as a mathematical calculation. A mathematical calculation is a mathematical concept thus, claim 4 does not solve the deficiencies of claim 3.
Regarding claim 5, it is dependent upon claim 1 and fails to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. For example, claim 5 recites wherein the solving of the problem further comprises incorporating rule constraints associated with the solving of the problem. Under the broadest reasonable interpretation, the limitations recite solving a problem using constraints which is a step of observation, evaluation, and judgement which can be performed mentally or with pen and paper. The steps of observation, evaluation, and judgement are mental processes thus, claim 5 does not solve the deficiencies of claim 1.
Regarding claim 6, it is dependent upon claim 5 and fails to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. For example, claim 6 recites wherein the rule constraints in the solving of the problem comprise intra-rule constraints and inter-rule constraints. Under the broadest reasonable interpretation, the limitations recite solving a problem using intra and inter rule constraints which is a step of observation, evaluation, and judgement which can be performed mentally or with pen and paper. The steps of observation, evaluation, and judgement are mental processes thus, claim 6 does not solve the deficiencies of claim 5.
Regarding claim 7, it is dependent upon claim 5 and fails to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. For example, claim 7 recites wherein the incorporating of the rule constraints in the solving of the problem comprises incorporating at least one of a monotonic prediction output or a fairness constraint. Under the broadest reasonable interpretation, the limitations recite solving a problem using a fairness constraint which is a step of observation, evaluation, and judgement which can be performed mentally or with pen and paper. The steps of observation, evaluation, and judgement are mental processes thus, claim 7 does not solve the deficiencies of claim 5.
Regarding claim 8, it is dependent upon claim 1 and fails to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. For example, claim 8 recites wherein the solving of the problem associated with the path-based machine learning model further comprises analyzing metrics including at least one of a precision or a recall for imbalanced datasets. Under the broadest reasonable interpretation, the limitations recite analyzing precision value for an imbalanced dataset which is a step of observation, evaluation, and judgement which can be performed mentally or with pen and paper. The steps of observation, evaluation, and judgement are mental processes thus, claim 8 does not solve the deficiencies of claim 1.
Regarding claim 9, it is dependent upon claim 1 and fails to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. For example, claim 9 recites wherein the solving of the problem further comprises generating the feature graph in which each decision rule of the one or more decision rules is mapped to a distinct independent path of the plurality of paths in the feature graph. Under the broadest reasonable interpretation, the limitations recite making a graph of unique decision paths which is a step of observation, evaluation, and judgement which can be performed mentally or with pen and paper. The steps of observation, evaluation, and judgement are mental processes thus, claim 9 does not solve the deficiencies of claim 1.
Regarding claim 10, it is dependent upon claim 9 and fails to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. For example, claim 10 recites wherein: the generating of the feature graph includes providing an acyclic multi-level digraph comprising multiple features, and each feature of the multiple features indicates a level in the feature graph that is represented by the plurality of nodes corresponding to distinct feature values. Under the broadest reasonable interpretation, the limitations recite making a directed graph of unique decision paths with multiple levels which is a step of observation, evaluation, and judgement which can be performed mentally or with pen and paper. The steps of observation, evaluation, and judgement are mental processes thus, claim 10 does not solve the deficiencies of claim 9.
Regarding claim 11, in step 1 of the 101 analysis set forth in MPEP 2106, the claim recites A computing device configured to perform decision tree machine learning,. The claim recites a device. A device is interpreted as an apparatus and is one of the four statutory categories of invention.
In Step 2A, Prong 1 of the 101 analysis set forth in MPEP 2106, the examiner has determined that the following limitations recite a process that, under broadest reasonable interpretation, covers a mental process or mathematical concept but for the recitation of generic computer components:
splitting the decision tree into a plurality of multiway decision trees in a path-based formulation, each of the plurality of multiway decision trees having an attribute not occurring more than once in each of the plurality of multiway decision trees; (i.e., the broadest reasonable interpretation includes a step of evaluation and judgement and could be performed mentally or with pen and paper like creating decision trees from unique paths, which is either a mental process of evaluation/judgement (MPEP 2106)).
and solving a problem associated with the path-based machine learning model using one or more multiway decision trees of the plurality of multiway decision trees, wherein: a multiway decision tree of the one or more multiway decision trees includes one or more decision rules that are mapped using a mixed-integer program (MIP), (i.e., the broadest reasonable interpretation includes mathematical calculation of using MIP to map decision rules, a mathematical calculation is considered a mathematical concept (MPEP 2106)).
the solving of the problem associated with the path-based machine learning model includes performing a column generation (CG) operation on a feature graph, (i.e., the broadest reasonable interpretation includes mathematical calculation of using column generation on a graph, a mathematical calculation is considered a mathematical concept (MPEP 2106)).
and the CG operation includes performing intersection of training samples of a plurality of nodes of a path of a plurality of paths in the feature graph. (i.e., the broadest reasonable interpretation includes mathematical calculation of using a column generation calculation to find intersecting values, a mathematical calculation is considered a mathematical concept (MPEP 2106)).
If the claim limitations, under their broadest reasonable interpretation, covers activities classified under Mental processes: concepts performed in the human mind (including observation, evaluation, judgement, or opinion) (see MPEP 2106.04(a)(2), subsection (III)) or Mathematical concepts: mathematical relationships, mathematical formulas or equations, or mathematical calculations (see MPEP 2106.04(a)(2), subsection (I)). Accordingly, the claim recites an abstract idea.
In Step 2A, Prong 2 of the 101 analysis, set forth in MPEP 2106, the examiner has determined that the following additional elements do not integrate this judicial exception into a practical application:
the computing device comprising: a processor; a memory coupled to the processor, the memory storing instructions to cause the processor to perform acts comprising: (i.e., the generic computer components recited in this limitation merely add the words “apply it”, or an equivalent, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea (MPEP 2106.05(f))).
accessing a decision tree associated with a path-based machine learning model; (i.e., the broadest reasonable interpretation of accessing a model is mere data gathering, which is an insignificant extra solution activity (MPEP 2106.05(g))).
Since the claim does not contain any other additional elements, that amount to integration into a practical application, the claim is directed to an abstract idea.
In Step 2B of the 101 analysis set forth in the 2019 PEG, the examiner has determined that the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception:
Regarding limitation (VI), under the broadest reasonable interpretation, recite steps of mere data gathering, which has been recognized by the courts as being well-understood, routine, and conventional functions. Specifically, the courts have recognized computer functions directed to mere data gathering as well-understood, routine, and conventional functions when they are claimed in a merely generic manner or as insignificant extra-solution activity when considering evidence in view of Berkheimer v. HP, Inc., 881 F.3d 1360, 1368, 125 USPQ2d 1649, 1654 (Fed. Cir. 2018), see USPTO Berkheimer Memorandum (April 2018)).
Examiner uses Berkheimer: Option 2, a citation to one or more of the court decisions discussed in MPEP 2106.05(d)(II) as noting well-understood, routine, and conventional nature of the additional elements:
Receiving or transmitting data over a network, e.g., using the Internet to gather data, Symantec, 838 F.3d at 1321, 120 USPQ2d at 1362 (utilizing an intermediary computer to forward information); TLI Communications LLC v. AV Auto. LLC, 823 F.3d 607, 610, 118 USPQ2d 1744, 1745 (Fed. Cir. 2016) (using a telephone for image transmission); OIP Techs., Inc., v. Amazon.com, Inc., 788 F.3d 1359, 1363, 115 USPQ2d 1090, 1093 (Fed. Cir. 2015) (sending messages over a network); buySAFE, Inc. v. Google, Inc., 765 F.3d 1350, 1355, 112 USPQ2d 1093, 1096 (Fed. Cir. 2014) (computer receives and sends information over a network). See MPEP 2106.05(d)(II).
Further, limitation (V), under the broadest reasonable interpretation, merely recite steps that apply generic computer components to perform judicial exceptions, which represents merely adding the words “apply it”, or an equivalent, which are not indicative of an inventive concept (MPEP 2106.05(f)). Considering additional elements individually and in combination, and the claim as a whole, the additional elements do not provide significantly more than the abstract idea. Therefore, the claim is not patent eligible.
Regarding claims 13-19, they are rejected under the same rationales as claims 3-10.
Regarding claim 20, in step 1 of the 101 analysis set forth in MPEP 2106, the claim recites A non-transitory computer readable storage medium tangibly embodying a computer readable program code having computer readable instructions that, when executed, causes a computer device to carry out a method of decision tree machine learning, the method comprising:. The claim recites a computer readable storage medium (CRM). A CRM is interpreted as an article of manufacture and is one of the four statutory categories of invention.
In Step 2A, Prong 1 of the 101 analysis set forth in MPEP 2106, the examiner has determined that the following limitations recite a process that, under broadest reasonable interpretation, covers a mental process or mathematical concept but for the recitation of generic computer components:
splitting the decision tree into a plurality of decision trees in a path-based formulation, each of the plurality of decision trees having an attribute not occurring more than once in each of the plurality of decision trees; (i.e., the broadest reasonable interpretation includes a step of evaluation and judgement and could be performed mentally or with pen and paper like creating decision trees from unique paths, which is either a mental process of evaluation/judgement (MPEP 2106)).
and solving a problem associated with the path-based machine learning model using one or more decision trees of the plurality of decision trees, wherein the one or more decision trees include one or more decision rules that are mapped using a mixed-integer program MIP, (i.e., the broadest reasonable interpretation includes mathematical calculation of using MIPs to map decision rules, a mathematical calculation is considered a mathematical concept (MPEP 2106)).
the solving of the problem associated with the path-based machine learning model includes performing a column generation (CG) operation on a feature graph (i.e., the broadest reasonable interpretation includes mathematical calculation of using column generation on a graph, a mathematical calculation is considered a mathematical concept (MPEP 2106)).
and the CG operation includes performing intersection of training samples of a plurality of nodes of a path of a plurality of paths in the feature graph. (i.e., the broadest reasonable interpretation includes mathematical calculation of using a column generation calculation to find intersecting values, a mathematical calculation is considered a mathematical concept (MPEP 2106)).
If the claim limitations, under their broadest reasonable interpretation, covers activities classified under Mental processes: concepts performed in the human mind (including observation, evaluation, judgement, or opinion) (see MPEP 2106.04(a)(2), subsection (III)) or Mathematical concepts: mathematical relationships, mathematical formulas or equations, or mathematical calculations (see MPEP 2106.04(a)(2), subsection (I)). Accordingly, the claim recites an abstract idea.
In Step 2A, Prong 2 of the 101 analysis, set forth in MPEP 2106, the examiner has determined that the following additional elements do not integrate this judicial exception into a practical application:
A non-transitory computer readable storage medium tangibly embodying a computer readable program code having computer readable instructions that, when executed, causes a computer device to carry out a method of decision tree machine learning, the method comprising: (i.e., the generic computer components recited in this limitation merely add the words “apply it”, or an equivalent, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea (MPEP 2106.05(f))).
accessing a decision tree associated with a path-based machine learning model (i.e., the broadest reasonable interpretation of accessing a model is mere data gathering, which is an insignificant extra solution activity (MPEP 2106.05(g))).
wherein: the plurality of decision trees comprises multiway decision trees provided by the splitting operation, (i.e., the generic computer components recited in this limitation merely add the words “apply it”, or an equivalent, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea (MPEP 2106.05(f))).
and providing a restricted master program version of the multiway decision trees, (i.e., the generic computer components recited in this limitation merely add the words “apply it”, or an equivalent, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea (MPEP 2106.05(f))).
Since the claim does not contain any other additional elements, that amount to integration into a practical application, the claim is directed to an abstract idea.
In Step 2B of the 101 analysis set forth in the 2019 PEG, the examiner has determined that the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception:
Regarding limitation (VI), under the broadest reasonable interpretation, recite steps of mere data gathering, which has been recognized by the courts as being well-understood, routine, and conventional functions. Specifically, the courts have recognized computer functions directed to mere data gathering as well-understood, routine, and conventional functions when they are claimed in a merely generic manner or as insignificant extra-solution activity when considering evidence in view of Berkheimer v. HP, Inc., 881 F.3d 1360, 1368, 125 USPQ2d 1649, 1654 (Fed. Cir. 2018), see USPTO Berkheimer Memorandum (April 2018)).
Examiner uses Berkheimer: Option 2, a citation to one or more of the court decisions discussed in MPEP 2106.05(d)(II) as noting well-understood, routine, and conventional nature of the additional elements:
Receiving or transmitting data over a network, e.g., using the Internet to gather data, Symantec, 838 F.3d at 1321, 120 USPQ2d at 1362 (utilizing an intermediary computer to forward information); TLI Communications LLC v. AV Auto. LLC, 823 F.3d 607, 610, 118 USPQ2d 1744, 1745 (Fed. Cir. 2016) (using a telephone for image transmission); OIP Techs., Inc., v. Amazon.com, Inc., 788 F.3d 1359, 1363, 115 USPQ2d 1090, 1093 (Fed. Cir. 2015) (sending messages over a network); buySAFE, Inc. v. Google, Inc., 765 F.3d 1350, 1355, 112 USPQ2d 1093, 1096 (Fed. Cir. 2014) (computer receives and sends information over a network). See MPEP 2106.05(d)(II).
Further, limitation (V), under the broadest reasonable interpretation, merely recite steps that apply generic computer components to perform judicial exceptions, which represents merely adding the words “apply it”, or an equivalent, which are not indicative of an inventive concept (MPEP 2106.05(f)). Similarly, limitation (VII), under the broadest reasonable interpretation, merely recites a multiway decision tree to perform a judicial exception, which represents merely adding the words “apply it”, or an equivalent, which are not indicative of an inventive concept (MPEP 2106.05(f)). Similarly, limitation (VIII), under the broadest reasonable interpretation merely recite steps that applies a restricted master program to perform a judicial exception, which represents merely adding the words “apply it”, or an equivalent, which are not indicative of an inventive concept (MPEP 2106.05(f)). Considering additional elements individually and in combination, and the claim as a whole, the additional elements do not provide significantly more than the abstract idea. Therefore, the claim is not patent eligible.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-6, 11, 13-15, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Mern, et al., Non-Patent Literature “Interpretable Local Tree Surrogate Policies” (“Mern”) in view of Firat, et al., Non-Patent Literature “Constructing classification trees using column generation” (“Firat”) and further in view of Fulton, et al., Non-Patent Literature “Efficient Algorithms for Finding Multi-way Splits for Decision Trees” (“Fulton”).
Regarding claim 1, Mern discloses:
splitting a decision tree associated with a path-based machine learning model into a plurality of…decision trees in a path-based formulation, (Mern, abstract, “In this work, we propose a method to build predictable policy trees as surrogates for policies such as neural networks [splitting a decision tree associated with a path-based machine learning model].”, and Mern, pg. 3 col. 2 and Figure 1, “Trees are built by simulating multiple executions of the base line policy from the given initial state or belief and clustering them into action nodes [into a plurality of…decision trees in a path-based formulation,].”).
each of the plurality of…decision trees having an attribute not occurring more than once in each of the plurality of…decision trees; (Mern, pg. 2 col. 1 and see Figure 1, “During execution of a tree policy, the actions taken by an agent are guaranteed to be along one of the unique paths from the root [each of the plurality of…decision trees having an attribute not occurring more than once in each of the plurality of…decision trees;].”).
and solving a problem associated with the path-based machine learning model using one or more…decision trees of the plurality of…decision trees, (Mern, pg. 1 col. 2, “In this work, we propose a method to develop transparent surrogate models as local policy trees. The resulting trees encode an intuitive plan of future actions with high-fidelity to the original policy [and solving a problem associated with the path-based machine learning model using one or more…decision trees of the plurality of…decision trees,].”).
While Mern teaches a system that generates a plurality of unique decision trees from a base tree, Mern does not explicitly teach:
A computer-implemented method of decision tree machine learning, the computer-implemented method comprising:
multiway trees
wherein: a…decision tree of the one or more…decision trees includes one or more decision rules that are mapped using a mixed-integer program (MIP),
the solving of the problem associated with the path-based machine learning model includes performing a column generation (CG) operation on a feature graph, and the CG operation includes performing intersection of training samples of a plurality of nodes of a path of a plurality of paths in the feature graph.
Firat teaches A computer-implemented method of decision tree machine learning, the computer-implemented method comprising: (Firat, pg. 14, “All experiments were conducted on a Windows 10 OS, with 16GB of RAM and an Intel(R) Core(TM) i7-7700HQ CPU @ 2.80 GHz [A computer-implemented method of decision tree machine learning, the computer-implemented method comprising:].”).
Mern and Firat are both in the same field of endeavor (i.e. decision trees). It would have been obvious for a person having ordinary skill in the art before the effective filing date of the claimed invention to combine Mern and Firat to teach the above limitation(s). The motivation for doing so is that a computer and its components are required in order to run a decision tree process.
Firat also teaches:
wherein: a…decision tree of the one or more…decision trees includes one or more decision rules that are mapped using a mixed-integer program (MIP), (Firat, pg. 6, “As it is usual in a CG approach, the master problem and the pricing problem are solved iteratively, where the former passes to the latter the dual variables in order to find paths with positive reduced costs; a subset of these paths are added to the master MILP to improve the objective [wherein: a…decision tree of the one or more…decision trees includes one or more decision rules that are mapped using a mixed-integer program (MIP),].”).
the solving of the problem associated with the path-based machine learning model includes performing a column generation (CG) operation on a feature graph, (Firat, pg. 2, “Firstly, we propose a novel ILP formulation for constructing classification tree [on a feature graph,], that is suitable for a Column Generation approach [the solving of the problem associated with the path-based machine learning model includes performing a column generation (CG) operation].”). and the CG operation includes performing intersection of training samples of a plurality of nodes of a path of a plurality of paths in the feature graph. (Firat, pg. 10, “In each step of the pricing heuristic, the pool is updated. The update procedure starts by selecting a subset of nl leaves Nlf ⊆ Nlf, [training samples of a plurality of nodes] corresponding to the ones for which columns with high (positive) reduced costs are found in the previous iteration. Then, a leaf is chosen uniformly at random from the set Nlf and a decision path to the selected leaf is constructed by choosing uniformly at every internal node j a decision check in Cset(j). If the constructed decision path is not correct according to the definition given in Section 3 because the same decision check appears several times along the path, its reduced cost is artificially set to −∞. The nc columns with highest positive reduced costs are then added to the master problem (if the number of columns with positive costs is lower than nc, add all columns with positive reduced costs) [and the CG operation includes performing intersection of training samples of a plurality of nodes of a path of a plurality of paths in the feature graph.].”).
Mern and Firat are both in the same field of endeavor (i.e. decision trees). It would have been obvious for a person having ordinary skill in the art before the effective filing date of the claimed invention to combine Mern and Firat to teach the above limitation(s). The motivation for doing so is that using MIP and column generation improves the efficiency of decision trees (cf. Firat, pg. 2, “In this paper, our contribution is threefold. Firstly, we propose a novel ILP formulation for constructing classification tree, that is suitable for a Column Generation approach. Secondly, we show that by using only a subset of the feature checks (decision checks), solutions of good quality can be obtained within short computation time.”).
While Mern in view of Firat teaches a system that generates a plurality of unique decision trees from a base tree using column generation and MIP, the combination does not explicitly teach:
multiway trees
Fulton teaches multiway trees (Fulton, pg. 244 col. 1, “This paper introduces algorithms for inducing decision trees with arity greater than two [multiway trees], which in some domains will yield decision trees with more accurate class prediction and fewer leaf nodes than conventionally induced binary decision trees.”).
Mern, in view of Firat, and Fulton are both in the same field of endeavor (i.e. decision trees). It would have been obvious for a person having ordinary skill in the art before the effective filing date of the claimed invention to combine Mern, in view of Firat, and Fulton to teach the above limitation(s). The motivation for doing so is that considering multi-split decisions in trees reduces tree size (cf. Fulton, pg. 244 col. 2, “We found that in some cases our multi-split algorithm leads to much smaller trees than are found by standard binary decision tree”).
Regarding claim 2, Mern in view of Firat and Fulton teaches the computer-implemented method according to claim 1. Fulton further teaches wherein the decision tree comprises a multiway decision tree. (Fulton, pg. 244 col. 1, “This paper introduces algorithms for inducing decision trees with arity greater than two [wherein the decision tree comprises a multiway decision tree.], which in some domains will yield decision trees with more accurate class prediction and fewer leaf nodes than conventionally induced binary decision trees.”).
It would have been obvious to one of ordinary skill in the art before the effective filling date of the present application to combine the teachings of Fulton with the teachings of Mern and Firat for the same reasons disclosed in claim 1.
Regarding claim 3, Mern in view of Firat and Fulton teaches the computer-implemented method according to claim 1. Fulton teaches multiway trees as seen in claim 1. Firat further teaches wherein the solving of the problem associated with the path-based machine learning model further includes providing a restricted master program version of the plurality of…decision trees. (Firat, pg. 12, “During our exploratory experiments, we see that the master ILP model has a high number of decision variables that are not found by generating columns. This is not the case in majority of the CG based applications. Therefore, to alleviate for the high complexity of CTCP, we propose to use a restricted set of decision checks at each node j, namely Cset(j) [wherein the solving of the problem associated with the path-based machine learning model further includes providing a restricted master program version of the plurality of…decision trees.].”).
Mern, Fulton, and Firat are all in the same field of endeavor (i.e. decision trees). It would have been obvious for a person having ordinary skill in the art before the effective filing date of the claimed invention to combine Mern, Fulton, and Firat to teach the above limitation(s). The motivation for doing so is that using a restricted master program reduces the complexity of the program (cf. Firat pg. 12, “Therefore, to alleviate for the high complexity of CTCP, we propose to use a restricted set of decision checks at each node j, namely Cset(j).”).
Regarding claim 4, Mern in view of Firat and Fulton teaches the computer-implemented method according to claim 3. Fulton teaches multiway trees as seen in claim 1. Firat further teaches wherein the solving of the problem associated with the path-based machine learning model further includes finding…regression trees using the MIP. (Firat, pg. 3, “Our ILP builds on the ideas in Verwer and Zhang (2017), where an efficient encoding is proposed for constructing both classification and regression (binary) trees of univariate splits of depth k [wherein the solving of the problem associated with the path-based machine learning model further includes finding…regression trees using the MIP.].”).
It would have been obvious to one of ordinary skill in the art before the effective filling date of the present application to combine the teachings of Firat with the teachings of Mern and Fulton for the same reasons disclosed in claim 1.
Regarding claim 5, Mern in view of Firat and Fulton teaches the computer-implemented method according to claim 1. Mern further teaches wherein the solving of the problem further comprises incorporating rule constraints associated with the solving of the problem. (Mern, pg. 5 Figure 3, “Tree build example. (a) An initial set of particles is sampled from the given initial state or belief. These particles are advanced in the simulation using the action at the root node a0. Particles reaching terminals states are marked with ×. (b) Non-terminal particles are clustered into new action nodes. (c) Action nodes with a sufficient number of particles are advanced another time step [wherein the solving of the problem further comprises incorporating rule constraints associated with the solving of the problem.].”).
Regarding claim 6, Mern in view of Firat and Fulton teaches the computer-implemented method according to claim 5. Mern further teaches wherein the rule constraints in the solving of the problem comprise intra-rule constraints and inter-rule constraints. (Mern, pg. 5 Figure 3, “Tree build example. (a) An initial set of particles is sampled from the given initial state or belief. These particles are advanced in the simulation using the action at the root node a0. Particles reaching terminals states are marked with ×. (b) Non-terminal particles are clustered into new action nodes [wherein the rule constraints in the solving of the problem comprise intra-rule constraints]. (c) Action nodes with a sufficient number of particles are advanced another time step [and inter-rule constraints.].”).
Regarding claim 11, the claim is similar to claim 1. Mern further teaches the additional limitation accessing a decision tree associated with a path-based machine learning model; (Mern, abstract, “In this work, we propose a method to build predictable policy trees as surrogates for policies such as neural networks [accessing a decision tree associated with a path-based machine learning model;].”).
Firat also teaches the additional limitation A computing device configured to perform decision tree machine learning, the computing device comprising: a processor; a memory coupled to the processor, the memory storing instructions to cause the processor to perform operations comprising: (Firat, pg. 14, “All experiments were conducted on a Windows 10 OS, with 16GB of RAM and an Intel(R) Core(TM) i7-7700HQ CPU @ 2.80 GHz [A computing device configured to perform decision tree machine learning, the computing device comprising: a processor; a memory coupled to the processor, the memory storing instructions to cause the processor to perform operations comprising:].”).
Mern, Fulton, and Firat are both in the same field of endeavor (i.e. decision trees). It would have been obvious for a person having ordinary skill in the art before the effective filing date of the claimed invention to combine Mern, Fulton, and Firat to teach the above limitation(s). The motivation for doing so is that a computer and its components are required in order to run a decision tree process.
Regarding claim 13, the claim is similar to claim 4 and rejected under the same rationales.
Regarding claim 14, the claim is similar to claim 3 and rejected under the same rationales.
Regarding claim 15, the claim is similar to claim 6 and rejected under the same rationales.
Regarding claim 20, the claim is similar to claim 1. Mern further teaches the additional limitation accessing a decision tree associated with a path-based machine learning model; (Mern, abstract, “In this work, we propose a method to build predictable policy trees as surrogates for policies such as neural networks [accessing a decision tree associated with a path-based machine learning model;].”).
Firat also teaches the additional limitation A non-transitory computer readable storage medium tangibly embodying a computer readable program code having computer readable instructions that, when executed, causes a computer device to carry out a method of decision tree machine learning, the method comprising: (Firat, pg. 14, “All experiments were conducted on a Windows 10 OS, with 16GB of RAM and an Intel(R) Core(TM) i7-7700HQ CPU @ 2.80 GHz [A non-transitory computer readable storage medium tangibly embodying a computer readable program code having computer readable instructions that, when executed, causes a computer device to carry out a method of decision tree machine learning, the method comprising:].”).
Mern, Fulton, and Firat are both in the same field of endeavor (i.e. decision trees). It would have been obvious for a person having ordinary skill in the art before the effective filing date of the claimed invention to combine Mern, Fulton, and Firat to teach the above limitation(s). The motivation for doing so is that a computer and its components are required in order to run a decision tree process.
Firat also teaches and providing a restricted master program version of the…decision trees (Firat, pg. 12, “During our exploratory experiments, we see that the master ILP model has a high number of decision variables that are not found by generating columns. This is not the case in majority of the CG based applications. Therefore, to alleviate for the high complexity of CTCP, we propose to use a restricted set of decision checks at each node j, namely Cset(j) [and providing a restricted master program version of the…decision trees].”).
Mern, Fulton, and Firat are all in the same field of endeavor (i.e. decision trees). It would have been obvious for a person having ordinary skill in the art before the effective filing date of the claimed invention to combine Mern, Fulton, and Firat to teach the above limitation(s). The motivation for doing so is that using a restricted master program reduces the complexity of the program (cf. Firat pg. 12, “Therefore, to alleviate for the high complexity of CTCP, we propose to use a restricted set of decision checks at each node j, namely Cset(j).”).
Claims 7 and 16 are rejected under 35 U.S.C. 103 as being unpatentable over Mern, et al., Non-Patent Literature “Interpretable Local Tree Surrogate Policies” (“Mern”) in view of Firat, et al., Non-Patent Literature “Constructing classification trees using column generation” (“Firat”) and further in view of Fulton, et al., Non-Patent Literature “Efficient Algorithms for Finding Multi-way Splits for Decision Trees” (“Fulton”) and Aghaei, et al., Non-Patent Literature “Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making” (“Aghaei”).
Regarding claim 7, Mern in view of Firat and Fulton teaches the computer-implemented method according to claim 5. While the combination teaches incorporating rule constraints in solving the problem, the combination does not explicitly teach wherein the incorporating of the rule constraints in the solving of the problem comprises incorporating at least one of a monotonic prediction output or a fairness constraint.
Aghaei teaches wherein the incorporating of the rule constraints in the solving of the problem comprises incorporating at least one of a monotonic prediction output or a fairness constraint. (Aghaei, abstract, We propose a versatile mixed-integer optimization framework for learning optimal and fair decision trees [wherein the incorporating of the rule constraints in the solving of the problem comprises incorporating at least one of a monotonic prediction output or a fairness constraint.] and variants thereof to prevent disparate treatment and/or disparate impact as appropriate.).
Mern, in view of Firat and Fulton, and Aghaei are both in the same field of endeavor (i.e. decision trees). It would have been obvious for a person having ordinary skill in the art before the effective filing date of the claimed invention to combine Mern, in view of Firat and Fulton, and Aghaei to teach the above limitation(s). The motivation for doing so is that utilizing a fairness constraint reduces discrimination for different samples (cf. Aghaei, pg. 1419 col. 1, “which serves to penalize discrimination, mitigating disparate treatment”).
Regarding claim 16, the claim is similar to claim 7 and rejected under the same rationales.
Claims 8 and 17 are rejected under 35 U.S.C. 103 as being unpatentable over Mern, et al., Non-Patent Literature “Interpretable Local Tree Surrogate Policies” (“Mern”) in view of Firat, et al., Non-Patent Literature “Constructing classification trees using column generation” (“Firat”) and further in view of Fulton, et al., Non-Patent Literature “Efficient Algorithms for Finding Multi-way Splits for Decision Trees” (“Fulton”) and Liu, et al., Non-Patent Literature “A Robust Decision Tree Algorithm for Imbalanced Data Sets” (“Liu”).
Regarding claim 8, Mern in view of Firat and Fulton teaches the computer-implemented method according to claim 5. While the combination teaches solving the problem associated with the model, the combination does not explicitly teach wherein the solving of the problem associated with the path-based machine learning model further comprises analyzing metrics including at least one of a precision or a recall for imbalanced datasets.
Liu teaches wherein the solving of the problem associated with the path-based machine learning model further comprises analyzing metrics including at least one of a precision or a recall for imbalanced datasets. (Liu, pg. 769 col. 2, “CC is focused in how many actual positive/negative instances are predicted correctly (the recall). Thus, even if there are many more negative than positive instances in the data set (tp+fn fp+tn), Equations 3.10 and 3.11 will not be affected by this imbalance [wherein the solving of the problem associated with the path-based machine learning model further comprises analyzing metrics including at least one of a precision or a recall for imbalanced datasets.].”).
Mern, in view of Firat and Fulton, and Liu are both in the same field of endeavor (i.e. decision trees). It would have been obvious for a person having ordinary skill in the art before the effective filing date of the claimed invention to combine Mern, in view of Firat and Fulton, and Liu to teach the above limitation(s). The motivation for doing so is that considering imbalanced datasets makes a decision tree more robust (cf. Liu, abstract, “Class Confidence Proportion Decision Tree (CCPDT), which is robust and insensitive to size of classes and generates rules which are statistically significant.”).
Regarding claim 17, the claim is similar to claim 8 and rejected under the same rationales.
Claims 9-10 and 18-19 are rejected under 35 U.S.C. 103 as being unpatentable over Mern, et al., Non-Patent Literature “Interpretable Local Tree Surrogate Policies” (“Mern”) in view of Firat, et al., Non-Patent Literature “Constructing classification trees using column generation” (“Firat”) and further in view of Fulton, et al., Non-Patent Literature “Efficient Algorithms for Finding Multi-way Splits for Decision Trees” (“Fulton”) and Hetherington, et al., US Pre-Grant Publication US20200302318A1 (“Hetherington”).
Regarding claim 9, Mern in view of Firat and Fulton teaches the computer-implemented method according to claim 1. While the combination teaches generating a feature graph, the combination does not explicitly teach wherein the solving of the problem further comprises generating the feature graph in which each decision rule of the one or more decision rules is mapped to a distinct independent path of the plurality of paths in the feature graph. (Hetherington, ⁋86 and Figure 3, “As discussed above, rules such as 321-328 may be arranged into levels such as 1B and 2B, with rule level 2B having more rules than shown. FIG. 3 further arranges tree nodes (shown as conditions 311-314) of a decision tree [wherein the solving of the problem further comprises generating the feature graph] into levels such as 1A, 2A, and 3A. For example, tree level 2A contains conditions 312-313. In an example not shown, a decision tree and its derived ruleset have a same count of levels, and mapping tree levels to rule levels is trivial (i.e. one-to-one) [in which each decision rule of the one or more decision rules is mapped to a distinct independent path of the plurality of paths in the feature graph.].”).
Mern, in view of Firat and Fulton, and Hetherington are both in the same field of endeavor (i.e. decision trees). It would have been obvious for a person having ordinary skill in the art before the effective filing date of the claimed invention to combine Mern, in view of Firat and Fulton, and Hetherington to teach the above limitation(s). The motivation for doing so is that Hetherington’s decision rules generated from traversing a graph improves candidate rulesets (cf. Hetherington, ⁋24, “Candidate decision rules are generated by traversing the tree. Each rule is built from one or more combinations of a subset of nodes in a traversal path of the tree. This improves on other existing techniques used to generate the candidate rulesets, such as by histogram binning and/or frequent itemset mining.”).
Regarding claim 10, Mern in view of Firat, Fulton, and Hetherington teaches the computer-implemented method according to claim 1. Hetherington further teaches wherein: the generating of the feature graph includes providing an acyclic multi-level digraph comprising multiple features, and each feature of the multiple features indicates a level in the feature graph that is represented by the plurality of nodes corresponding to distinct feature values. (Hetherington, ⁋86 and Figure 3, “As discussed above, rules such as 321-328 may be arranged into levels such as 1B and 2B, with rule level 2B having more rules than shown. FIG. 3 further arranges tree nodes (shown as conditions 311-314) of a decision tree into levels such as 1A, 2A, and 3A [wherein: the generating of the feature graph includes providing an acyclic multi-level digraph comprising multiple features,]. For example, tree level 2A contains conditions 312-313. In an example not shown, a decision tree and its derived ruleset have a same count of levels, and mapping tree levels to rule levels is trivial (i.e. one-to-one); Figure 3 shows that at level 2A that there are a plurality of nodes for distinct conditions (i.e. and each feature of the multiple features indicates a level in the feature graph that is represented by the plurality of nodes corresponding to distinct feature values.).”).
It would have been obvious to one of ordinary skill in the art before the effective filling date of the present application to combine the teachings of Hetherington with the teachings of Mern, Firat, and Fulton for the same reasons disclosed in claim 9.
Regarding claims 18-19, the claims are similar to claims 9-10 and rejected under the same rationales.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Nanavati, et al., US20210027315A1 discloses generating multiple decision trees using directed acyclic graph of rules.
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to NICHOLAS S WU whose telephone number is (571)270-0939. The examiner can normally be reached Monday - Friday 8:00 am - 4:00 pm EST.
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, Michelle Bechtold can be reached at 571-431-0762. 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.
/N.S.W./Examiner, Art Unit 2148 /MICHELLE T BECHTOLD/Supervisory Patent Examiner, Art Unit 2148