Questions tagged [decision-trees]
The decision-trees tag has no usage guidance.
10
questions with no upvoted or accepted answers
13
votes
0
answers
444
views
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 ...
- 395
6
votes
0
answers
250
views
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'$ ...
- 769
5
votes
0
answers
173
views
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 ...
user6973
4
votes
0
answers
160
views
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 ...
- 13.9k
4
votes
0
answers
260
views
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 ...
- 83
3
votes
0
answers
143
views
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", ...
- 373
3
votes
0
answers
644
views
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 ...
- 31
2
votes
0
answers
156
views
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 ...
user6973
0
votes
0
answers
95
views
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,...
- 1
-1
votes
1
answer
2k
views
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 ...
