惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

V
Visual Studio Blog
Y
Y Combinator Blog
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
Hugging Face - Blog
Hugging Face - Blog
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
The Cloudflare Blog
L
LangChain Blog
美团技术团队
N
Netflix TechBlog - Medium
量子位
酷 壳 – CoolShell
酷 壳 – CoolShell
B
Blog
博客园 - 司徒正美
爱范儿
爱范儿
D
DataBreaches.Net
月光博客
月光博客
U
Unit 42
B
Blog RSS Feed
Engineering at Meta
Engineering at Meta
Apple Machine Learning Research
Apple Machine Learning Research
Jina AI
Jina AI
MongoDB | Blog
MongoDB | Blog
腾讯CDC

math.ST updates on arXiv.org

What is Learnable in Valiant's Theory of the Learnable? Learning Perturbations to Extrapolate Your LLM Byzantine-Robust Distributed Sparse Learning Revisited The Sample Complexity of Multiple Change Point Identification under Bandit Feedback A proximal gradient algorithm for composite log-concave sampling Model-based Bootstrap of Controlled Markov Chains Approximation of Maximally Monotone Operators : A Graph Convergence Perspective Posterior Contraction Rates for Sparse Kolmogorov-Arnold Networks in Anisotropic Besov Spaces MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound A Spectral Framework for Closed-Form Relative Density Estimation Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability Higher-Order Equilibrium Tracking for EM-Compressible Online Estimation Scaling Limits of Long-Context Transformers A Note on Non-Negative $L_1$-Approximating Polynomials Susceptibilities and Patterning: A Primer on Linear Response in Bayesian Learning Linear Response Estimators for Singular Statistical Models Statistical inference with belief functions: A survey Robust stochastic first order methods in heavy-tailed noise via medoid mini-batch gradient sampling Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity Adaptive auditing of AI systems with anytime-valid guarantees Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions Risk-Controlled Post-Processing of Decision Policies Covariate Balancing and Riesz Regression Should Be Guided by the Neyman Orthogonal Score in Debiased Machine Learning A Unified Pair-GRPO Family: From Implicit to Explicit Preference Constraints for Stable and General RL Alignment Time-Inhomogeneous Preconditioned Langevin Dynamics A Fine-Grained Understanding of Uniform Convergence for Halfspaces CITE: Anytime-Valid Statistical Inference in LLM Self-Consistency Ratio-based Loss Functions Optimal Confidence Band for Kernel Gradient Flow Estimator A renormalization-group inspired lattice-based framework for piecewise generalized linear models
Identifying subtree perfectness in decision trees
Nathan Huntley, Matthias C. M. Troffaes · 2012-08-06 · via math.ST updates on arXiv.org

In decision problems, often, utilities and probabilities are hard to determine. In such cases, one can resort to so-called choice functions. They provide a means to determine which options in a particular set are optimal, and allow incomparability among any number of options. Applying choice functions in sequential decision problems can be highly non-trivial, as the usual properties of maximising expected utility may no longer be satisfied. In this paper, we study one of these properties: we revisit and reinterpret Selten's concept of subgame perfectness in the context of decision trees, leading us to the concept of subtree perfectness, which basically says that the optimal solution of a decision tree should not depend on any larger tree it may be embedded in. In other words, subtree perfectness excludes counterfactual reasoning, and therefore may be desirable from some philosophical points of view. Subtree perfectness is also desirable from a practical point of view, because it admits efficient algorithms for solving decision trees, such as backward induction. The main contribution of this paper is a very simple non-technical criterion for determining whether any given choice function will satisfy subtree perfectness or not. We demonstrate the theorem and illustrate subtree perfectness, or the lack thereof, through numerous examples, for a wide variety of choice functions, where incomparability amongst strategies can be caused by imprecision in either probabilities or utilities. We find that almost no choice function, except for maximising expected utility, satisfies it in general. We also find that choice functions other than maximising expected utility can satisfy it, provided that we restrict either the structure of the tree, or the structure of the choice function.