Decision Trees for Decision-Making under the Predict-then-Optimize Framework
- Award ID(s):
- 1763000
- PAR ID:
- 10282267
- Date Published:
- Journal Name:
- Proceedings of the 37th International Conference on Machine Learning
- Page Range / eLocation ID:
- 2858-2867
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Optimal decision-making requires consideration of internal and external contexts. Biased decision-making is a transdiagnostic symptom of neu- ropsychiatric disorders. We created a computational model demonstrating how the striosome compartment of the striatum constructs a context- dependent mathematical space for decision-making computations, and how the matrix compartment uses this space to define action value. The model explains multiple experimental results and unifies other theories like reward prediction error, roles of the direct versus indirect pathways, and roles of the striosome versus matrix, under one framework. We also found, through new analyses, that striosome and matrix neurons increase their synchrony during difficult tasks, caused by a necessary increase in dimensionality of the space. The model makes testable predictions about individual differences in disorder susceptibility, decision-making symptoms shared among neuropsychiatric disorders, and differences in neuropsychiatric disorder symptom presenta- tion. The model provides evidence for the central role that striosomes play in neuroeconomic and disorder-affected decision-making.more » « less
-
We give the first reconstruction algorithm for decision trees: given queries to a function f that is opt-close to a size-s decision tree, our algorithm provides query access to a decision tree T where: - T has size S := s^O((log s)²/ε³); - dist(f,T) ≤ O(opt)+ε; - Every query to T is answered with poly((log s)/ε)⋅ log n queries to f and in poly((log s)/ε)⋅ n log n time. This yields a tolerant tester that distinguishes functions that are close to size-s decision trees from those that are far from size-S decision trees. The polylogarithmic dependence on s in the efficiency of our tester is exponentially smaller than that of existing testers. Since decision tree complexity is well known to be related to numerous other boolean function properties, our results also provide a new algorithm for reconstructing and testing these properties.more » « less
An official website of the United States government

