DETAILED ACTION
This action is responsive to communications filed on March 27, 2024. This action is made Non-Final.
Claims 1-20 are pending in the case.
Claims 1, 8, and 15 are independent claims.
Claims 1-20 are rejected.
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 .
Information Disclosure Statement
The information disclosure statement (IDS(s)) submitted on 03/27/2024 is/are in compliance with the provisions of 37 C.F.R. 1.97. Accordingly, the IDS(s) is/are being considered by the examiner.
Claim Interpretation
Paragraph 0028 of the specification recites “computer readable storage medium, as
that term is used in the present disclosure, is not to be construed as storage in the form of transitory signals per se.” Accordingly, claims 8-20 are statutory under 35 USC §101 CRM analysis.
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.
Claim(s) 1-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Russell, Chris. "Efficient search for diverse coherent explanations." Proceedings of the conference on fairness, accountability, and transparency. 2019 (“Russel”), and further in view of Kanamori, Kentaro, et al. "Distribution-aware counterfactual explanation by mixed-integer linear optimization." Transactions of the Japanese Society for Artificial Intelligence 36.6 (2021): C-L44_1 (“Kanamori”).
Claim 1:
Russel teaches or suggests a computer-implemented method comprising:
responsive to receiving an input, a trained model, a trained model outcome, a local outlier factor (LOF) threshold and a maximum number of live polytopes to search over, generating an optimization problem to determine an output that is closest to the input with respect to a distance measure (see Fig. 4; Table 1; §1 - the search for an optimal solution of a well-defined model permits to control the quality of the solution and ensures the stability of the results; mathematical models to search for counterfactual explanations in tree ensembles with a number of binary variables that is logarithmic in the number of vertices, and therefore scales to large trees while retaining its ability to find an optimal solution; §2.1 – feasibility region of the problem is defined as the intersection of a polytope (Constraint 2); §2.2 - Given an origin point ^x and a desired prediction class c_, searching for a plausible and actionable counterfactual explanation consists in locating a new data point x 2 X that solves the following problem: (5),(6), and (7). a training set; f^x is a separable convex cost that represents how difficult it is to move from ^x to x. This generic cost function includes distance metrics (e.g., squared Euclidean or Mahalanobis distance) as a special case; Plausibility constraints (polytope XP) should ensure that the explanation x respects the structure of the data and that it is located in a region that has a sufficiently large density of samples; l1-norm distance and plausibility constraints grounded on the Local Outlier Factor (LOF) score; §3.3 - model gives an extensible framework for efficiently modeling most existing data types, decision-tree structures, and objectives. As it mathematically represents the space of all feasible counterfactual explanations, solving it to optimality; §3.5 - Isolation forests are trained to return an outlier score for any sample, inversely proportional to its average path depth within a set of randomized trees grown to full extent on random sample subsets. Therefore, constraining this average depth controls the outlier score (and consequently the plausibility) of the counterfactual explanation. To include this constraint, we train the isolation forest TI on the training samples from the target class; d is a fixed threshold defining the average depth under which samples are declared as outliers. In our experiments, we will set this threshold to capture 10% of the training data as an outlier, and therefore we seek a counterfactual explanation typical of the 90% most common cases of the target class; §4 - training random forests.);
a set of quadratic mixed integer constraints (see Fig. 4; Table 1; §1 - solution approach grounded on mixed integer linear and quadratic programming (MILP and MIQP); §2.1 – feasibility region of the problem is defined as the intersection of a polytope (Constraint 2) along with a set of quadratic restrictions (Constraint 3).);
decomposing an input space into a plurality of polytopes based on a geometry associated with the trained model; and generating a counterfactual based on the plurality of polytopes (see Fig. 4; Table 1; §1 - the search for an optimal solution of a well-defined model permits to control the quality of the solution and ensures the stability of the results; mathematical models to search for counterfactual explanations in tree ensembles with a number of binary variables that is logarithmic in the number of vertices, and therefore scales to large trees while retaining its ability to find an optimal solution; §2.1 – feasibility region of the problem is defined as the intersection of a polytope (Constraint 2); §2.2 - Given an origin point ^x and a desired prediction class c_, searching for a plausible and actionable counterfactual explanation consists in locating a new data point x 2 X that solves the following problem: (5),(6), and (7). a training set; f^x is a separable convex cost that represents how difficult it is to move from ^x to x. This generic cost function includes distance metrics (e.g., squared Euclidean or Mahalanobis distance) as a special case; Plausibility constraints (polytope XP) should ensure that the explanation x respects the structure of the data and that it is located in a region that has a sufficiently large density of samples; l1-norm distance and plausibility constraints grounded on the Local Outlier Factor (LOF) score; §3.3 - model gives an extensible framework for efficiently modeling most existing data types, decision-tree structures, and objectives. As it mathematically represents the space of all feasible counterfactual explanations, solving it to optimality; §3.5 - Isolation forests are trained to return an outlier score for any sample, inversely proportional to its average path depth within a set of randomized trees grown to full extent on random sample subsets. Therefore, constraining this average depth controls the outlier score (and consequently the plausibility) of the counterfactual explanation. To include this constraint, we train the isolation forest TI on the training samples from the target class; d is a fixed threshold defining the average depth under which samples are declared as outliers. In our experiments, we will set this threshold to capture 10% of the training data as an outlier, and therefore we seek a counterfactual explanation typical of the 90% most common cases of the target class; §4 - training random forests; §4.2 – counterfactual search has a decomposable geometrical structure.).
Kanamori more specifically teaches or suggests transforming a LOF constraint into a set of linear mixed integer constraints ..., utilizing the distance measure (see §1-2 – describing using MILO with Mahalanobis distance and LOF; §2-2 – describing LOF and distance between an instance and its nearest neighbor; §4-1 – describing MILO, LOF, and a l1-norm based MD; §6 – based on MD, LOF, and efficient MILO formulation.)
Accordingly, it would have been obvious to one having ordinary skill before the effective filing date of the claimed invention to modify the system and method, taught in Russel, to include transforming a LOF constraint into a set of linear mixed integer constraints ..., utilizing the distance measure for the purpose of efficiently using mixed integer linear optimization formulation of LOF constraints and distance measures to extract optimal actions, improving counterfactual explanation determinations, as taught by Kanamori (Abstract, §6).
Claim(s) 8 and 15:
Claim(s) 8 and 15 correspond to Claim 1, and thus, Russel and Kanamori teach or suggest the limitations of claim(s) 8 and 15 as well.
Claim 2:
Russel further teaches or suggests presenting the generated counterfactual (see §1 - Counterfactual explanations are contrastive arguments of the type: “To obtain this loan, you need $40,000 of annual revenue instead of the current $30,000”. They correspond to small perturbations of an example that permit to modify the classification outcome; §5 - generate optimal plausible counterfactual explanations.).
Claim(s) 9 and 16:
Claim(s) 9 and 16 correspond to Claim 2, and thus, Russel and Kanamori teach or suggest the limitations of claim(s) 9 and 16 as well.
Claim 3:
Russel further teaches or suggests wherein generating the counterfactual satisfies a manifold alignment constraints (see Table 1; Fig. 4; §1 - Isolation forests are an effective and distribution agnostic way to associate a plausibility score for the different regions of the feature space. impact of our plausibility constraints via isolation forests, demonstrating the flexibility of the approach and showing that these extra constraints do not significantly impact the performance of the solution process while significantly boosting the usefulness of the explanations; §2 – feasibility region of the problem is defined as the intersection of a polytope (Constraint 2); §2.2 - 1-norm distance and l1 plausibility constraints grounded on the Local Outlier Factor (LOF) score. Plausibility constraints (polytope XP) should ensure that the explanation x respects the structure of the data and that it is located in a region that has a sufficiently large density of samples; §4.3 - restricts the search for counterfactual examples to the core of the distribution of the desired class. high practical importance of fine-grained plausibility constraints; §5 - modeling toolkit that can be used as a building block for a disciplined evaluation of counterfactual search models, plausibility constraints, and actionability paradigms in various applications.).
Claim(s) 10 and 17:
Claim(s) 10 and 17 correspond to Claim 3, and thus, Russel and Kanamori teach or suggest the limitations of claim(s) 10 and 17 as well.
Claim 4:
Russel further teaches or suggests wherein decomposing the input space into the plurality of polytopes based on the geometry associated with the trained model, comprises: calculating a series of optimization problems with the LOF constraint for a set of closest polytopes (see Fig. 4; Table 1; §1 - the search for an optimal solution of a well-defined model permits to control the quality of the solution and ensures the stability of the results; mathematical models to search for counterfactual explanations in tree ensembles with a number of binary variables that is logarithmic in the number of vertices, and therefore scales to large trees while retaining its ability to find an optimal solution; §2.1 – feasibility region of the problem is defined as the intersection of a polytope (Constraint 2); §2.2 - Given an origin point ^x and a desired prediction class c_, searching for a plausible and actionable counterfactual explanation consists in locating a new data point x 2 X that solves the following problem: (5),(6), and (7). a training set; f^x is a separable convex cost that represents how difficult it is to move from ^x to x. This generic cost function includes distance metrics (e.g., squared Euclidean or Mahalanobis distance) as a special case; Plausibility constraints (polytope XP) should ensure that the explanation x respects the structure of the data and that it is located in a region that has a sufficiently large density of samples; l1-norm distance and plausibility constraints grounded on the Local Outlier Factor (LOF) score; §3.3 - model gives an extensible framework for efficiently modeling most existing data types, decision-tree structures, and objectives. As it mathematically represents the space of all feasible counterfactual explanations, solving it to optimality; §3.5 - Isolation forests are trained to return an outlier score for any sample, inversely proportional to its average path depth within a set of randomized trees grown to full extent on random sample subsets. Therefore, constraining this average depth controls the outlier score (and consequently the plausibility) of the counterfactual explanation. To include this constraint, we train the isolation forest TI on the training samples from the target class; d is a fixed threshold defining the average depth under which samples are declared as outliers. In our experiments, we will set this threshold to capture 10% of the training data as an outlier, and therefore we seek a counterfactual explanation typical of the 90% most common cases of the target class; §4 - training random forests; §4.2 – counterfactual search has a decomposable geometrical structure.).
Claim(s) 11 and 18:
Claim(s) 11 and 18 correspond to Claim 4, and thus, Russel and Kanamori teach or suggest the limitations of claim(s) 11 and 18 as well.
Claim 5:
Russel further teaches or suggests wherein the plurality of polytopes contains a point with a minimum distance to the input (see Fig. 4; Table 1; §1 - the search for an optimal solution of a well-defined model permits to control the quality of the solution and ensures the stability of the results; mathematical models to search for counterfactual explanations in tree ensembles with a number of binary variables that is logarithmic in the number of vertices, and therefore scales to large trees while retaining its ability to find an optimal solution; §2.1 – feasibility region of the problem is defined as the intersection of a polytope (Constraint 2); §2.2 - Given an origin point ^x and a desired prediction class c_, searching for a plausible and actionable counterfactual explanation consists in locating a new data point x 2 X that solves the following problem: (5),(6), and (7). training set; f^x is a separable convex cost that represents how difficult it is to move from ^x to x. This generic cost function includes distance metrics (e.g., squared Euclidean or Mahalanobis distance) as a special case; Plausibility constraints (polytope XP) should ensure that the explanation x respects the structure of the data and that it is located in a region that has a sufficiently large density of samples; l1-norm distance and plausibility constraints grounded on the Local Outlier Factor (LOF) score; §3.3 - model gives an extensible framework for efficiently modeling most existing data types, decision-tree structures, and objectives. As it mathematically represents the space of all feasible counterfactual explanations, solving it to optimality; §3.5 - Isolation forests are trained to return an outlier score for any sample, inversely proportional to its average path depth within a set of randomized trees grown to full extent on random sample subsets. Therefore, constraining this average depth controls the outlier score (and consequently the plausibility) of the counterfactual explanation. To include this constraint, we train the isolation forest TI on the training samples from the target class; d is a fixed threshold defining the average depth under which samples are declared as outliers. In our experiments, we will set this threshold to capture 10% of the training data as an outlier, and therefore we seek a counterfactual explanation typical of the 90% most common cases of the target class; §4 - training random forests; §4.2 – counterfactual search has a decomposable geometrical structure.).
Claim(s) 12 and 19:
Claim(s) 12 and 19 correspond to Claim 5, and thus, Russel and Kanamori teach or suggest the limitations of claim(s) 12 and 19 as well.
Claim 6:
Kanamori further teaches or suggests wherein the trained model is a trained rectified linear unit network (see §1-2 – describing using MILO with Mahalanobis distance and LOF; §2-2 – describing LOF and distance between an instance and its nearest neighbor; §2-3 – describing the use of MLP with ReLU function; P. 4 footnote describing methods extended to general multilayer ReLU networks; §4-1 – describing MILO, LOF, and a l1-norm based MD; §4-3 – MLP with ReLU and MILO formulation; 5-1 – describing trained two-layer ReLU network classifiers; §6 – based on MD, LOF, and efficient MILO formulation.).
Accordingly, it would have been obvious to one having ordinary skill before the effective filing date of the claimed invention to modify the system and method, taught in Russel, to include transforming a LOF constraint into a set of linear mixed integer constraints ..., utilizing the distance measure for the purpose of efficiently using mixed integer linear optimization formulation of LOF constraints and distance measures to extract optimal actions, improving counterfactual explanation determinations, as taught by Kanamori (Abstract, §6).
Claim(s) 13:
Claim(s) 13 correspond to Claim 6, and thus, Russel and Kanamori teach or suggest the limitations of claim(s) 13 as well.
Claim 7:
Russel further teaches or suggests updating the counterfactual with a minimum distance with respect to the input (see Fig. 4; Table 1; §1 - the search for an optimal solution of a well-defined model permits to control the quality of the solution and ensures the stability of the results; mathematical models to search for counterfactual explanations in tree ensembles with a number of binary variables that is logarithmic in the number of vertices, and therefore scales to large trees while retaining its ability to find an optimal solution; §2.1 – feasibility region of the problem is defined as the intersection of a polytope (Constraint 2); §2.2 - Given an origin point ^x and a desired prediction class c_, searching for a plausible and actionable counterfactual explanation consists in locating a new data point x 2 X that solves the following problem: (5),(6), and (7). training set; f^x is a separable convex cost that represents how difficult it is to move from ^x to x. This generic cost function includes distance metrics (e.g., squared Euclidean or Mahalanobis distance) as a special case; Plausibility constraints (polytope XP) should ensure that the explanation x respects the structure of the data and that it is located in a region that has a sufficiently large density of samples; l1-norm distance and plausibility constraints grounded on the Local Outlier Factor (LOF) score; §3.3 - model gives an extensible framework for efficiently modeling most existing data types, decision-tree structures, and objectives. As it mathematically represents the space of all feasible counterfactual explanations, solving it to optimality; §3.5 - Isolation forests are trained to return an outlier score for any sample, inversely proportional to its average path depth within a set of randomized trees grown to full extent on random sample subsets. Therefore, constraining this average depth controls the outlier score (and consequently the plausibility) of the counterfactual explanation. To include this constraint, we train the isolation forest TI on the training samples from the target class; d is a fixed threshold defining the average depth under which samples are declared as outliers. In our experiments, we will set this threshold to capture 10% of the training data as an outlier, and therefore we seek a counterfactual explanation typical of the 90% most common cases of the target class; §4 - training random forests; §4.2 – counterfactual search has a decomposable geometrical structure.).
Claim(s) 14 and 20:
Claim(s) 14 and 20 correspond to Claim 7, and thus, Russel and Kanamori teach or suggest the limitations of claim(s) 14 and 20 as well.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Andrew T McIntosh whose telephone number is (571)270-7790. The examiner can normally be reached M-Th 8:00am-5:30pm.
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, Tamara Kyle can be reached at 571-272-4241. 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.
/ANDREW T MCINTOSH/Primary Examiner, Art Unit 2144
Prosecution Insights