Questions tagged [decision-tree]
The decision-tree tag has no usage guidance.
43 questions
0
votes
1
answer
23
views
Proper way to compute information gain in a decision tree when tests have pre-requisites
I want to build a decision tree and ID3 (greedy information gain maximization) seems fine, but when picking which test to perform at a node, some tests can only be done after some other tests.
Here's ...
- 1,204
1
vote
0
answers
117
views
How many comparative sorting algorithms are there?
I've invented an abstract structure to represent a comparison-based sorting algorithm, which I will call a comparison tree (similar to the decision tree of a comparative sorting algorithm). ...
- 53
0
votes
0
answers
50
views
Definition of an algebraic decision tree
I am trying to understand what an algebraic decision tree is but wikipedia lacks a formal definition, just an intuition. So I need to check if my understanding is correct.
From what I have read it ...
- 341
0
votes
3
answers
473
views
Can we create a decision tree for any comparison sorting algorithm even if it is very complicated?
I am reading an algorithm book.
Any comparison sort must make $\Omega(n\log(n))$ comparisons in the worst case to sort $n$ elements.
Can we create a decision tree for any comparison sorting algorithm ...
- 113
1
vote
1
answer
25
views
How to come up with combination a short-circuit evaluation table?
(a || b) || (c && d))
Given the above, how do I derive the table below:
a
b
c
d
output
T
-
-
-
TRUE
F
T
-
-
TRUE
F
F
T
T
TRUE
F
F
T
F
FALSE
F
F
F
-
FALSE
I'm told that this is short ...
- 11
2
votes
2
answers
1k
views
Decision tree for searching element in sorted-array
Given the problem of having a sorted array $A$, an element $x$ to be searched for in the array $ A $, what is a lower-bound on the process of finding $x$ in $A$?
The answer is $ \Omega(\log n) $ ...
- 233
1
vote
1
answer
43
views
'Address Function' example of decision tree complexity is not clear
In Arora and Barak's textbook, page 261-262, in decision model complexity, they states:
Address Function: Suppose that $n = k + 2^k$ and let $f$ be the function that maps $x_1, x_2, \dots, x_k, y_1, \...
- 759
3
votes
1
answer
92
views
Expressivity of Polysize Decision Trees
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 ...
- 1,110
0
votes
0
answers
255
views
How to prove that the lower bound of the Huffman coding problem is $\Omega(n \log n)$?
how to prove that the lower bound of the Huffman coding problem is $\Omega(n \log n)$?
Here Huffman coding problem is Huffman encoding.
For example,
...
- 165
1
vote
1
answer
142
views
Intersection of Decision Tree Boundaries in Higher Dimensions
I have trained two binary decision tree classifiers with splits in $\mathbb{R}^4$. Same data, but from two different patches. Now, I want to find the exact intervals where the two trees disagree.
The ...
- 11
0
votes
1
answer
73
views
What is beta and k parameter in Incremental Decision Tree
I have read this paper https://arxiv.org/pdf/1803.03674v1.pdf for outlier detection problem with real data (online training)
In this paper, the authors used Incremental Decision Tree to build ...
- 101
3
votes
1
answer
260
views
Basic exercises on decision trees
I am a pure math person doing some ML self-study and I am pretty lost.
I am trying to solve the following exercises on decision trees:
Exercise 1. Consider the following training set where
$X_1,X_2,...
- 133
1
vote
1
answer
109
views
Can inputs in the decision tree model be computed?
The Wikipedia definition of the decision tree model says that it allows the sign functions of certain classes to be computed in constant time (and presumably also memory). My questions, still ...
- 115
3
votes
3
answers
623
views
how does the shap algorithm work in polynomial time?
I'm trying to understand how the shap algorithm calculates in polynomial time an estimation to the feature attribution function that satisfies the shapely value attributes (specifically for tree based ...
- 369
0
votes
1
answer
106
views
SMO, Random forest and Bayes net algorithms: why does Random forest perform better?
I analyzed a dataset using those 3 different algorithms.
As I can see, Random forest performs better in most cases.
My dataset is composed of 4000 instances of two classes (class A 2000 elements, ...
- 1
1
vote
0
answers
247
views
Rummy Card Game Bot
in my beginner’s computer science class, we are asked to create an bot for a variant of rummy. It has to make logical moves as it needs to beat other very simple bots. I wanted to know how you would ...
- 11
1
vote
1
answer
176
views
How to convert a decision tree to an automaton?
From what I know,
a problem can be transformed to a yes/no answer, which can be
described by a decision tree.
Solution to a problem also can be represented by a set of strings (a language), which ...
- 327
1
vote
2
answers
530
views
Why decision tree method for lower bound on finding a minimum doesn't work
(Motivated by this question. Also I suspect that my question is a bit too broad)
We know $\Omega(n \log n)$ lower bound for sorting: we can build a decision tree where each inner node is a comparison ...
user114966
1
vote
1
answer
217
views
Lower bound on comparison-based sorting
I have a question from one of the exercises in CLRS.
Show that there is no comparison sort whose running time is linear for at least half
of the $n!$ inputs of length $n$. What about a fraction of $1/...
- 23
0
votes
0
answers
30
views
Problems about Decision Tree
Do any one give me some hints to solve this problem. Explain is steps by steps.Thanks
0
votes
1
answer
47
views
Longest palindrome substring in logarithmic runtime complexity
In a palindrome of size N, the amount of candidates for the longest palindrome is N^2. Therefore, the information theoretic lower bound (IBT) should be lg(N^2), which is equivalent to a runtime ...
- 3
0
votes
1
answer
468
views
0
votes
2
answers
2k
views
Lower bound and worst case scenario
We know that the lower bound is the minimum amount of work needed to solve a problem. So for a given problem say x it has the best algorithm ( the most efficient algorithm to solve this problem ) say ...
- 13
1
vote
0
answers
576
views
How to convert a decision table to a consistent decision tree?
I am working from presentation from school, but I am not able to understand how they go from one step to the other. This is the decision table that I have.
From it, the first thing we have to do is ...
- 205
0
votes
0
answers
26
views
Decision tree: how to decide the next node?
I have to decide for which value of "Klasse"
How do i do it?
I know that I have to decide on maximum information gain
So first off I've calculated the entropy of "Klasse"
That is E(Klasse)= -(3/11*...
- 53
4
votes
2
answers
2k
views
In information theory, why is the entropy measured in units of bits?
In information theory, we have the quantity "information".
Suppose we have some discrete random variable $X$, that can take values $\{{a,b,c\}}$ with corresponding probability distribution $\{{\frac{...
- 215
1
vote
1
answer
177
views
How to handle missing attribute's value with ID3 algorithm?
i am working with ID3 algorithm, and i know that classic ID3 basically can handle missing data. But i am trying to code this algorithm, so what should i do if there is missing attribute's value in ...
- 113
2
votes
0
answers
99
views
Decision Tree for searching an element in an n*n matrix
I just learnt decision tree concept in class. I have a question for homework. It says to prove that for searching an element in n*n matrix the lower bound is logn and prove it using decision tree.
My ...
- 21
1
vote
1
answer
282
views
Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)
I need some help understanding how to calculate the lower bound on the time complexity of merging $m$ sorted arrays of length $n$.
The bound should be $nm \lg(m)$. I need to prove this using a ...
- 147
0
votes
1
answer
393
views
How to calculate information gain in ID3?
I am trying to implement a decision tree classifier using ID3 algorithm. According to Aritificial Intelligence - A Modern Approach, information gain of attribute A ...
- 129
0
votes
0
answers
886
views
Random Forest - Conditional Permutation Importance
I've been looking for the most unbiased algorithm to find out the feature importances in random forests if there are correlations among the input features.
Besides the most commonly preferred ...
3
votes
1
answer
71
views
Finding maximum takes at least $\lceil n/2 \rceil$ comparisons
We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$.
I want to prove that finding the maximum in $A$ (that is, outputting the index ...
- 33
2
votes
1
answer
53
views
decision trees and numeric attributes
I have been reading a book about Decision Trees and it caught my attention the following part:
In case of numeric attributes, decision trees can be geometrically
interpreted as a collection of ...
- 413
3
votes
0
answers
31
views
Classify/Distinguish between 8008 binary grids, with 13 queries
I have $8008$ binary grids of size $6 \times 10$ (they are all grids with the property described below), which I want to distinguish between with at most $13$ queries. A query will determine if the ...
- 238
1
vote
0
answers
50
views
Attribute Selection for minimum number of clusters
I have a table consisting of some headers $P, Q, R, S$ (shown in blue in Table 1). According to the headers, the column $T$ is populated using some predefined logic.
Now, any of the headers $P,Q,R,S$ ...
- 175
3
votes
1
answer
205
views
What do Arora and Barak mean by $x|_S$ in their definition of certificate complexity?
I am having much trouble understanding the following definition (of certificate complexity - for decision trees) from Arora and Barak's book Computational Complexity: A Modern Approach. Perhaps there ...
- 211
2
votes
0
answers
57
views
Avoiding collisions in space and time
Say I have an image, represented as a 2D array of pixel values. Also, say I have a set of points on that image where each has a current (x, y) position and a Destination (x, y) associated with it. I ...
2
votes
1
answer
2k
views
What machine learning training algorithm to use for this kind of string dataset?
I am working on a project where I have to train the following data-set using machine learning algorithm. One of my friend suggested decision tree, but I have never seen a situation where independent ...
- 123
2
votes
1
answer
87
views
Decision Tree Learning Deviation - Russell and Norvig
I am working through the Russell and Norvig AI book and came across the following on the top of page 706.
The section concerns Decision Tree pruning and testing a given attribute against the null ...
- 323
3
votes
1
answer
1k
views
What is the main difference between binary decision tree and binary decision diagram(BDD)?
What is the main difference between binary decision tree and binary decision diagram(BDD)? From what I can tell I only understand that a binary decision diagram is a more compact representation ...
- 431
1
vote
1
answer
53
views
Connected Components - Linear Decision Trees
What does connected components mean in the context of non-graphs? Graphs have vertices and the vertices are connected by edges. Hence, you can build a spanning tree (for example) by systematically ...
- 11
0
votes
1
answer
40
views
Decision tree complexity of finding parameters of "zigzag" array
I am currently studying for a test on data structures.
I have to find the lower and upper bounds for the following problem:
An array is called a zigzag array if there are $1 \leq i \leq j \leq n$ so ...
- 23
1
vote
1
answer
141
views
Decision tree complexity of deciding whether array is "zigzag"
I am currently studying for a test on data structures.
I have to find the lower and upper bounds for the following problem:
Input: an array with $n$ numbers.
Output: boolean answer for the ...
- 23