patternMinor
Expressivity of Polysize Decision Trees
Viewed 0 times
decisionexpressivitypolysizetrees
Problem
A binary decision tree (DT) is a binary tree whose internal nodes are labelled by boolean variables (with repetitions), and whose leaves are labelled either $0$ or $1$. The size of a decision tree is the number of branches (or equivalently the number of leaves).
A DT determines a unique Boolean function of the variables labelling the internal nodes: given an assignment of these variables, start at the root of the tree and take the left branch if the label is assigned $0$ and the right branch otherwise, and repeat until a leaf is reached; the value of the function is the label of the leaf. Any boolean function $f\colon \{0,1\}^n\to\{0,1\}$ can be represented by a DT with size $2^n$ (a complete tree where the $i^\text{th}$ level of internal nodes is labelled by variable $x_i$).
Question: Is the class of languages recognisable by a family of polynomial-size decision trees known to be related to a ''natural'' class of single-output boolean circuits (e.g. NC$^0$, TC$^0$...)?
I am hoping for something analogous to Barrington's theorem [Bar89] for branching programs (which can be seen as an extension of DTs where ''tree'' is replaced by ''DAG'').
The class of decision problems solvable by a family of polynomial-size, constant-width ($\geq 5$) branching programs is exactly (non-uniform) NC$^1$.
However, the existence of strong learning algorithms for DTs [BLQT21] leads me to believe I'm looking for far less expressive classes.
[Bar89] D. A. M. Barrington. Bounded-width polynomial-size branching programs can recognize exactly those languages in NC1, Journal of Computer and System Sciences 38:150-164, 1989.
[BLQT21] Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan:
Properly learning decision trees in almost polynomial time. CoRR abs/2109.00637 (2021).
A DT determines a unique Boolean function of the variables labelling the internal nodes: given an assignment of these variables, start at the root of the tree and take the left branch if the label is assigned $0$ and the right branch otherwise, and repeat until a leaf is reached; the value of the function is the label of the leaf. Any boolean function $f\colon \{0,1\}^n\to\{0,1\}$ can be represented by a DT with size $2^n$ (a complete tree where the $i^\text{th}$ level of internal nodes is labelled by variable $x_i$).
Question: Is the class of languages recognisable by a family of polynomial-size decision trees known to be related to a ''natural'' class of single-output boolean circuits (e.g. NC$^0$, TC$^0$...)?
I am hoping for something analogous to Barrington's theorem [Bar89] for branching programs (which can be seen as an extension of DTs where ''tree'' is replaced by ''DAG'').
The class of decision problems solvable by a family of polynomial-size, constant-width ($\geq 5$) branching programs is exactly (non-uniform) NC$^1$.
However, the existence of strong learning algorithms for DTs [BLQT21] leads me to believe I'm looking for far less expressive classes.
[Bar89] D. A. M. Barrington. Bounded-width polynomial-size branching programs can recognize exactly those languages in NC1, Journal of Computer and System Sciences 38:150-164, 1989.
[BLQT21] Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan:
Properly learning decision trees in almost polynomial time. CoRR abs/2109.00637 (2021).
Solution
This is not an exact characterization, but the class of languages recognizable by poly-size DT is included in $\mathrm{AC}^0$, specifically within its second level: that is, any DT can be converted to a polynomially larger CNF and DNF. To see this, take
$$\bigvee_i\bigwedge_jp_{i,j},$$
where $i$ runs over all accepting leaves of the DT, and for each $i$, $p_{i,j}$ enumerates literals corresponding to the decisions made on the path from the root to $i$.
$$\bigvee_i\bigwedge_jp_{i,j},$$
where $i$ runs over all accepting leaves of the DT, and for each $i$, $p_{i,j}$ enumerates literals corresponding to the decisions made on the path from the root to $i$.
Context
StackExchange Computer Science Q#148112, answer score: 2
Revisions (0)
No revisions yet.