Questions tagged [decision-trees]
The decision-trees tag has no usage guidance.
10 questions with no upvoted or accepted answers
How can one find the "hard" probability distribution on the input for recursive boolean functions?
Update: Since, it seems there is no progress regarding this question, any idea, conjecture, hunch, or advice is welcome. For example, are there any partial or incomplete results? What are the main ...
Tree rotation, a problem similar to Huffman coding
I am not sure whether the following problem has been studied. We have a undirected tree $T$. We would like to construct another tree $T'$. $T'$ is a binary tree. Each inner nodes of $T'$ ...
The Complexity of Properly Learning Decision Trees
Where does this paper prove the middle bullet point of its abstract? I have looked through that paper fairly thoroughly. There are three things I want to read how they're getting around. Reductions ...
Is it possible that the Aanderaa–Karp–Rosenberg conjecture is just a bit false?
The Aanderaa–Karp–Rosenberg conjecture is that any non-trivial monotone property on graphs is evasive. It has been proved for several special cases, but for a general graph on $n$ vertices, we only ...
Algebraic decision trees and adversary arguments
In the comparison tree model, we establish lower bounds on computing $\min$ and $\max$ of $n$ numbers via the adversary argument. Are there problems on which we know lower bounds in the algebraic ...
Approximation class of finding decision trees with minimal depth
We are given some sets $S_1, \cdots , S_n$ and two disjoint sets $A$ and $B$. A decision tree is a binary tree where each node asks "$x \in S_i? $" for some $i$, taking the left branch means "yes", ...
Is there a tight lower bound on the complexity of SSSP on a graph?
I'm an undergrad and I'm not sure if this is the right way to ask this question. I want to know the lower bound on single-source shortest path computation in a general graph. The graph is allowed to ...
How hard is it to compute an approximately optimal non-greedy CART tree?
The question itself is closer to the bottom of this post, and is formulated without any rerefence to the term "CART". Motivation: In traditional CART (Classification and Regression Trees), one ...
Designing an appropriate training set for CART classification using imbalanced data
I'm experimenting with using CART (or maybe Random Forest) to classify genomic data. There are essentially two classes, whereof one is the 'normal' state and the other is the 'exceptional' state. Now,...
Time complexity analysis of random forest and k-means?
I am working with random forest for a supervised classification problem, and I am using the k-means clustering algorithm to split the data at each node, where $n$ is the number of points, $K$ is ...