The decision-trees tag has no wiki summary.
17
votes
3answers
621 views
Sorting using a black box
Assume that we want to sort a list $S$ of $n$ real numbers.
Assume that we are given a black box that can sort $\sqrt n$ real numbers instantly.
How much advantage can we gain using this black box?
...
1
vote
0answers
77 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 ...
-2
votes
1answer
152 views
Sorting : proof for lower bound of Sorting [closed]
I have read the proof of lower bound of Sorting Algorithm that use comparison to know input is NlogN. In this paper, the author use decision tree for this proof. Everything on this proof I have ...
21
votes
1answer
533 views
Coloring complexity of graphs
Suppose $G$ is a graph with coloring number $d = \chi(G)$. Consider the following game between Alice and Bob. At each round, Alice picks a vertex, and Bob answers with a color in $\{1,\ldots,d-1\}$ ...
6
votes
0answers
165 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'$ ...
5
votes
1answer
151 views
Is there an accepted name for Ross Quinlan's adaptation of the ID3 decision algorithm to use a Pearson's chi-squared test for independence?
In Ross Quinlan's seminal paper Induction of Decision Trees, Quinlan summarizes the current state of machine learning in 1985 and loudly introduces the ID3 decision algorithm in the context of its ...
0
votes
0answers
77 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.
...
10
votes
1answer
538 views
Algorithm for optimizing decision trees
Background
A binary decision tree $T$ is a rooted tree where each internal node (and root) is labeled by an index $j \in \{1,..., n\}$ such that no path from root to leaf repeats an index, the leafs ...
2
votes
2answers
187 views
Building a decision tree to approximate a known function (not to learn an unknown function)
I have a function $f: \mathbb{D} \rightarrow \{0,1\}$ where $\mathbb{D} \in \mathbb{R}^{5000}$.
I would like to approximate $f$ using a decision tree.
Up to now I have only found literature in the ...
3
votes
1answer
213 views
Bounds on the size of smallest decision tree for a boolean function?
Consider a boolean function $f : V \rightarrow \{0,1\}$ with $m$ true points. Are there any non-trivial bounds in $m$ on the size of the smallest decision tree for $f$?
It seems to me that assuming ...
0
votes
2answers
225 views
Learning using decision trees
I have a quick question that I'm stumped on. This is about constructing a decision tree using information gain (entropy). Let's say we have a dataset with two input attributes such that the ...
