Decision Trees and Influences of Variables Over Product Probability Spaces

DOI10.1017/S0963548309009833MaRDI QIDQ3557496zbMATH OpenOpenAlexFDO

Authors Hamed Hatami

Publication date 23 April 2010

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0612405

Mathematics Subject Classification ID

General harmonic expansions, frames (42C15) Probabilistic measure theory (60A10) Combinatorial probability (60C05)

Abstract: A celebrated theorem of Friedgut says that every function $f:{0,1}^{n}o0,1$ can be approximated by a function $g:{0,1}^{n}o0,1$ with $|f-g{|}_2^{2}leepsilon$ which depends only on $e^{O(I_f/epsilon)}$ variables where $I_f$ is the sum of the influences of the variables of $f$. Dinur and Friedgut later showed that this statement also holds if we replace the discrete domain ${0,1}^n$ with the continuous domain $[0,1{]}^n$, under the extra assumption that $f$ is increasing. They conjectured that the condition of monotonicity is unnecessary and can be removed. We show that certain constant-depth decision trees provide counter-examples to Dinur-Friedgut conjecture. This suggests a reformulation of the conjecture in which the function $g:[0,1{]}^{n}o0,1$ instead of depending on a small number of variables has a decision tree of small depth. In fact we prove this reformulation by showing that the depth of the decision tree of $g$ can be bounded by $e^{O(I_f/epsilo{n}^2)}$. Furthermore we consider a second notion of the influence of a variable, and study the functions that have bounded total influence in this sense. We use a theorem of Bourgain to show that these functions have certain properties. We also study the relation between the two different notions of influence.

Recommendations

• DECISION-TREE MODELLING OF PROBABILITY DISTRIBUTIONS¹
• Multivariate decision trees
• Probabilistic characterization of random decision trees
• Classification with decision trees from a nonparametric predictive inference perspective
• A copulas-based approach to modeling dependence in decision trees
• scientific article; zbMATH DE number 2101261
• scientific article; zbMATH DE number 1931833
• Symbolic and Quantitative Approaches to Reasoning with Uncertainty
• scientific article; zbMATH DE number 1786652

Cites work

• Boolean functions whose Fourier transform is concentrated on the first two levels.
• Boolean functions with low average sensitivity depend on few coordinates
• Constant depth circuits, Fourier transform, and learnability
• Every monotone graph property has a sharp threshold
• Inequalities in Fourier analysis
• Influences in Product Spaces: KKL and BKKKL Revisited
• Isoperimetry and integrability of the sum of independent Banach-space valued random variables
• Learning Monotone Decision Trees in Polynomial Time
• On Russo's approximate zero-one law
• On the critical percolation probabilities
• On the distribution of the Fourier spectrum of Boolean functions
• Sharp thresholds of graph properties, and the k-sat problem
• The hardness of 3-uniform hypergraph coloring
• The influence of variables in product spaces
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)

Cited in

(17)

• Lower bound on the correlation between monotone families in the average case
• The influence of variables in product spaces
• Influence measures for CART classification trees
• On the failure of concentration for the _-ball
• Juntas in the \(\ell_{1}\)-grid and Lipschitz maps between discrete tori
• A copulas-based approach to modeling dependence in decision trees
• Decision trees and influence: an inductive proof of the OSSS inequality
• On the influences of variables on Boolean functions in product spaces
• Geometric influences
• A structure theorem for Boolean functions with small total influences
• A simple reduction from a biased measure on the discrete cube to the uniform measure
• Approximation of biased Boolean functions of small total influence by DNFs
• Geometric influences. II: Correlation inequalities and noise sensitivity
• scientific article; zbMATH DE number 7559121 (Why is no real title available?)
• Influence in product spaces
• MULTIPLICATIVE PROPERTIES IN EVALUATION OF DECISION TREES
• Extended commonality of paths and cycles via Schur convexity

This page was built for publication: Decision Trees and Influences of Variables Over Product Probability Spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557496)