Constrained Prescriptive Trees via Column Generation

• URL: http://arxiv.org/abs/2207.10163v1
• Date: Wed, 20 Jul 2022 19:30:22 GMT
• Title: Constrained Prescriptive Trees via Column Generation
• Authors: Shivaram Subramanian, Wei Sun, Youssef Drissi, Markus Ettl
• Abstract summary: We introduce a novel path-based mixed-integer program (MIP) formulation which identifies a (near) optimal policy efficiently via column generation. We demonstrate the efficacy of our method with extensive experiments on both synthetic and real datasets.
• Score: 5.273277327802614
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: With the abundance of available data, many enterprises seek to implement data-driven prescriptive analytics to help them make informed decisions. These prescriptive policies need to satisfy operational constraints, and proactively eliminate rule conflicts, both of which are ubiquitous in practice. It is also desirable for them to be simple and interpretable, so they can be easily verified and implemented. Existing approaches from the literature center around constructing variants of prescriptive decision trees to generate interpretable policies. However, none of the existing methods are able to handle constraints. In this paper, we propose a scalable method that solves the constrained prescriptive policy generation problem. We introduce a novel path-based mixed-integer program (MIP) formulation which identifies a (near) optimal policy efficiently via column generation. The policy generated can be represented as a multiway-split tree which is more interpretable and informative than a binary-split tree due to its shorter rules. We demonstrate the efficacy of our method with extensive experiments on both synthetic and real datasets.

Related papers

• Learning General Continuous Constraint from Demonstrations via Positive-Unlabeled Learning [8.361428709513476]
  This paper presents a positive-unlabeled (PU) learning approach to infer a continuous, arbitrary and possibly nonlinear, constraint from demonstration. The effectiveness of the proposed method is validated in two Mujoco environments.
  arXiv  Detail & Related papers  (2024-07-23T14:00:18Z)
• A Unified Approach to Extract Interpretable Rules from Tree Ensembles via Integer Programming [2.1408617023874443]
  Tree ensemble methods are known for their effectiveness in supervised classification and regression tasks. Our work aims to extract an optimized list of rules from a trained tree ensemble, providing the user with a condensed, interpretable model.
  arXiv  Detail & Related papers  (2024-06-30T22:33:47Z)
• Adversarial Imitation Learning On Aggregated Data [0.0]
  Inverse Reinforcement Learning (IRL) learns an optimal policy, given some expert demonstrations, thus avoiding the need for the tedious process of specifying a suitable reward function. We propose an approach which removes these requirements through a dynamic, adaptive method called Adversarial Imitation Learning on Aggregated Data (AILAD) It learns conjointly both a non linear reward function and the associated optimal policy using an adversarial framework.
  arXiv  Detail & Related papers  (2023-11-14T22:13:38Z)
• Scalable Optimal Multiway-Split Decision Trees with Constraints [3.092691764363848]
  We present a novel path-based MIP formulation where the number of decision variables is independent of $N$. Our framework produces a multiway-split tree which is more interpretable than the typical binary-split trees due to its shorter rules. We present results on datasets containing up to 1,008,372 samples while existing MIP-based decision tree models do not scale well on data beyond a few thousand points.
  arXiv  Detail & Related papers  (2023-02-14T03:48:48Z)
• Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality [94.89246810243053]
  This paper studies offline policy learning, which aims at utilizing observations collected a priori to learn an optimal individualized decision rule. Existing policy learning methods rely on a uniform overlap assumption, i.e., the propensities of exploring all actions for all individual characteristics must be lower bounded. We propose Pessimistic Policy Learning (PPL), a new algorithm that optimize lower confidence bounds (LCBs) instead of point estimates.
  arXiv  Detail & Related papers  (2022-12-19T22:43:08Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  Robust decision processes (MDPs) provide a framework to model decision problems where the system dynamics are changing or only partially known. Recent work established the equivalence between texttts rectangular $L_p$ robust MDPs and regularized MDPs, and derived a regularized policy iteration scheme that enjoys the same level of efficiency as standard MDPs. In this work, we focus on the policy improvement step and derive concrete forms for the greedy policy and the optimal robust Bellman operators.
  arXiv  Detail & Related papers  (2022-05-28T04:05:20Z)
• Constructing a Good Behavior Basis for Transfer using Generalized Policy Updates [63.58053355357644]
  We study the problem of learning a good set of policies, so that when combined together, they can solve a wide variety of unseen reinforcement learning tasks. We show theoretically that having access to a specific set of diverse policies, which we call a set of independent policies, can allow for instantaneously achieving high-level performance.
  arXiv  Detail & Related papers  (2021-12-30T12:20:46Z)
• Generating Explainable Rule Sets from Tree-Ensemble Learning Methods by Answer Set Programming [9.221315229933532]
  We propose a method for generating explainable rule sets from tree-ensemble learners using Answer Set Programming (ASP) We adopt a decompositional approach where the split structures of the base decision trees are exploited in the construction of rules. We show how user-defined constraints and preferences can be represented declaratively in ASP to allow for transparent and flexible rule set generation.
  arXiv  Detail & Related papers  (2021-09-17T01:47:38Z)
• Compressive Summarization with Plausibility and Salience Modeling [54.37665950633147]
  We propose to relax the rigid syntactic constraints on candidate spans and instead leave compression decisions to two data-driven criteria: plausibility and salience. Our method achieves strong in-domain results on benchmark summarization datasets, and human evaluation shows that the plausibility model generally selects for grammatical and factual deletions.
  arXiv  Detail & Related papers  (2020-10-15T17:07:10Z)
• Probabilistic Case-based Reasoning for Open-World Knowledge Graph Completion [59.549664231655726]
  A case-based reasoning (CBR) system solves a new problem by retrieving cases' that are similar to the given problem. In this paper, we demonstrate that such a system is achievable for reasoning in knowledge-bases (KBs) Our approach predicts attributes for an entity by gathering reasoning paths from similar entities in the KB.
  arXiv  Detail & Related papers  (2020-10-07T17:48:12Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.