Skip to main content

Questions tagged [decision-trees]

Use this tag for questions about graphs or models of decisions and their possible consequences including chance-event outcomes, resource costs, and utility.

Filter by
Sorted by
Tagged with
0 votes
0 answers
9 views

Explicit formula for $F(a,i)=p_iF(a-1,i-1)+(1-p_i)F(a,i-1)$

So, I have this node tree that I have constructed in this way: I start at 0 at the top and add 1 if I go left and do nothing if I go right. I go left with a probability $p_i$ for level $i$ in the tree ...
Vebjorn's user avatar
  • 183
1 vote
0 answers
24 views

Relationship Between Gini Index and Decision Trees

I am trying to learn about the mathematics behind how Decision Tree algorithms work (https://en.wikipedia.org/wiki/Decision_tree_learning). For example (and for simplicity sake), consider a dataset ...
wulasa's user avatar
  • 145
0 votes
1 answer
35 views

What is the average number of questions needed for decision tree

Assume you're using the optimal strategy, where you ask the fewest number of questions to guess the animal from this decision tree. What is the average number of questions you need to ask? Is there ...
cchris's user avatar
  • 3
0 votes
0 answers
25 views

Why is the value of information gain negative?

Here is a sample dataset. I have to calculate the Information gain in Variable. Am I missing anything as information gain should not be negative? Variable Class ...
Sagun Devkota's user avatar
0 votes
1 answer
63 views

Can two combined events have a probability greater than the events themselves?

I'm presented with the following conditional probability problem: There are 2 bags with different numbers of lemon and grape candies: Bag #1: 5 lemon candies, 5 grape candies (10 candies total) Bag #...
Sachintha's user avatar
0 votes
0 answers
19 views

Generalization of Tree Diagrams

In simple probility theory one learns about tree diagrams and their rules. First you draw them with the outcomes. Then you write the probility of each event according to Laplace's formula and then to ...
bochner.martinelli's user avatar
0 votes
1 answer
34 views

How to find the threshold to split the data based on a feature in decision trees

I was studying decision trees from a book about machine learning and it says that the rule applied to partition the data in a node of the tree is the one that maximizes the information gain, which is ...
Chappie733's user avatar
0 votes
0 answers
20 views

Let rankI be the rank relative to the insertion order for σ ∈ S9 . If rankI(σ) =9×8n+23, which value will assume σ(7)?

Let $\mathrm{rank}_I$ be the rank relative to the insertion order for $\sigma \in S_9$ . If $\mathrm{rank}_I(\sigma) = 9 \times 8n+23$, for some $n \in \mathbb{N}$, which value will assume $\sigma(7)...
J P's user avatar
  • 343
0 votes
0 answers
24 views

Decision/Logic tree behavior for solving integral convergence

I'm trying to make a comprehensive decision tree for finding integral/improper integral convergence. The goal would be a comprehensive "guide" or list to follow in order to determine the ...
user11975758's user avatar
2 votes
1 answer
73 views

Prove a lemma about permutations

Let $V$ be a set of $n$ permutations of $m$ numbers. Let $m<n<<m!$ I want to prove the following lemma: Lemma: For any set of permutations $V$ there exists a pair of numbers $(a,b)$ such that ...
xavrojo's user avatar
  • 21
0 votes
0 answers
41 views

What condition on Decision space imply it's a decision tree

Let's say we have tabular data(numerical) and each column is dimension hence each row is a data point in $R^n$ if there are $n$ columns. The decision tree can be seen as the partition of the data now ...
GGT's user avatar
  • 1,045
5 votes
1 answer
69 views

Guessing a triple of digits by knowing if you got at least one of them right

Here is a rephrased version of problem $4$ in BMO $2016$ round $2$. I rephrased to make it clearer and shorter. Given is a triple of digits $(a,b,c)$, where $a$, $b$, $c\in\{0,1,\dots,9\}$. Each turn ...
user avatar
1 vote
1 answer
156 views

How to prove that this greedy algorithm is optimal or find a counterexample?

We play a game where there are arbitrarily many squares in a line and they are numbered $0$, $1$, $2$, etc. We start at square $n >= 0$ and the objective is to get to square $0$ in as few jumps as ...
joseville's user avatar
  • 1,487
2 votes
0 answers
22 views

Is this binary search tree correct?

I have made a binary search tree from this sequence: 4, 1, 7, 5, 6, 3, 0, 2, 9, 8 And I just want to make sure that it is correct. Starting with 4. Then 1 which is less than 4 so its placed on the ...
Peter's user avatar
  • 67
2 votes
0 answers
60 views

Formal definition of decision tree

I am looking for a reference that would provide a formal definition of a decision tree. I am mostly referring to combinatorial games, Markov decision processes and similar fields. It should be ...
alagris's user avatar
  • 193
0 votes
0 answers
51 views

Does geeksforgeeks website has an error regarding maximum number of nodes in a tree?

I know that for a tree with a given height H, the maximum number of nodes on all levels is $n \le 2^0 + 2^1 + 2^2+...+2^H = 2^{H+1}-1$. Basically it's for Perfect Binary Tree. How come that this well ...
theateist's user avatar
  • 113
1 vote
1 answer
66 views

Minimizing average depth of a decision tree: when is greedy optimal?

Fix parameters $m$ and $n$. Consider a finite set $A$ and a set of attributes $f_1,\ldots,f_m$ where $f_i: A \rightarrow [n]$. We want to construct a decision tree $T$ with minimum average depth. We ...
Varun Sivashankar's user avatar
0 votes
0 answers
282 views

Information gain calculation for decision tree when choosing root node

I want to know if my calculation is wrong or correct, because i got a different result when i use an online calculator. Here is the dataset: ...
JoN's user avatar
  • 1
2 votes
1 answer
301 views

How can the number of times an event occurs a given number of times in a decision making tree be calculated when the odds of the occurrences is known?

stackexchangers I am attempting to calculate the probability that a subject will experience an event a minimum of 7 times over ten periods when the probability of the (independent) event occurring is ...
duckegg's user avatar
  • 669
1 vote
2 answers
84 views

What is the idea of ‘probability p’?

Hello mathstackexchange I’m working my way through a book on mathematics and have come to a section on probability. I’ve not done probability before and whilst the resource has been excellent, in the ...
duckegg's user avatar
  • 669
0 votes
0 answers
23 views

Constructing a probability tree from a series of conditional events

In a game, there are a series of attacks, each with a known probability of success. As a specific example, let's say that there are two potential attacks that can be made against a single defender. ...
Thomas's user avatar
  • 101
0 votes
0 answers
48 views

Will growing more trees in random forests increase the variance compared to growing fewer trees?

Elements of mathematical learning says that less tress are not required to obtain a good predictive performance but does that mean growing more trees in random forests will increase the variance ...
pelly pen's user avatar
0 votes
0 answers
33 views

Adverse Selection and Decision Trees

In a group of people 10% are unhealthy but don't know it. Of these 50% will likely need to be hospitalized. Of the 90% that are healthy, 10% will likely need be hospitalized. The cost of ...
user1884367's user avatar
1 vote
0 answers
24 views

Is there a known maximum difference between binary decision diagrams and zero-suppresion diagrams?

In Knuth's analysis on ZDDs and BDDs he states that for a given boolean function f the bounds of the size difference are: $ZDD\_size(f) \leq n/2 (BDD\_size(f) + 1) + 1$ $BDD\_size(f) \leq n/2 (ZDD\...
Daniel Miedema's user avatar
1 vote
0 answers
77 views

Product of sizes of subtrees of a perfect binary tree

A perfect binary tree is a binary tree for which every parent node has exactly two children and each leaf occurs at the same depth (alternatively, same height) in the tree. A perfect binary tree of ...
ExpressionCoder's user avatar
0 votes
0 answers
25 views

Find partitions based on data

I have a set of vectors $V = (v_1, v_2, \cdots, v_i, \cdots, v_n), v_n \in \mathbb{R}^d$ and a partition annotation $L_i$ for each vector $L_i \in \{1, 2, \cdots, K \}$. My goal is to partition $V$ ...
peng yu's user avatar
  • 1,271
1 vote
2 answers
96 views

Probability Conditional Question Please Help

I have a probability question which I would appreciate some help with. a) Complete the values in the tree diagram b) The probability that Terry will not be the champion is 0.58. Find the value of p c)...
RL2's user avatar
  • 23
0 votes
1 answer
197 views

Prove that the average height of a full binary tree is greater or equal to the logarithm of its leaf count [closed]

The average height of a full binary leaf (a node is either a parent with 2 childs or a leaf) is: $$h_m(T) = \frac{1}{|B(T)|}\sum_{b\in B(T)}\operatorname{depth}(b)$$ B(T) is the set of leaves. Now I ...
stackNutzer89's user avatar
1 vote
0 answers
82 views

Metric for partitions of a topological space

Let $X$ be a topological space. Consider the set $B_X$ of partitions of $X$ such that every block of the partition is simply connected. How can one define a metric $d$ on $B_X$? To help answer this, ...
ChargeShivers's user avatar
2 votes
0 answers
85 views

Understanding the $\alpha$-regularity assumption for trees

In this paper, definition 4 claims that a tree grown by recursive partitioning is $\alpha$-regular for some $\alpha>0$ if each split leaves at least a fraction $\alpha$ of the available training ...
WeakLearner's user avatar
  • 6,096
2 votes
1 answer
80 views

Why is $\sum x(1-x)$ equal to $1-\sum x^2$?

I'm going through Python Machine Learning and I'm at the Gini impurity sections, where they define Gini Impurities as $I_g(t) = \sum_{i=1}^c p(i|t) (1 - p(i|t))$ where p is the proportion of samples ...
user2019645's user avatar
0 votes
5 answers
189 views

If $4$ distinct integers $a, b, c, d$ are randomly selected from $n$ distinct integers, what is the probability that $a \lt b \lt c \lt d$?

a. If $i$ distinct integers $r_1, r_2, \ldots,r_i$, i $\leq n$, are randomly selected (one after other) from n distinct integers, what is the probability that $r_1 < r_2 < \cdots < r_i$? b. ...
Haslo Vardos's user avatar
0 votes
0 answers
35 views

Decision based on decision tree

Based on a text I created a decision tree. This decision tree shows options A, B and C. I calculated the value that could be expected for each decision and the highest one would be that of option C ...
xyz's user avatar
  • 43
0 votes
3 answers
85 views

Probability of disease transmission to future generations

Assume disease D is transmitted through a father (male) to his children. Let us assume that every family in a society have $C\geq1$ children. Let the father of a family have the disease D. What is the ...
Mahdi's user avatar
  • 305
0 votes
1 answer
589 views

What is the difference between P(W1,W2) vs P(W2|W1) in this context

What is the conceptual difference between the probability of winning two successive games in a playoff series vs winning the second game given that you won the first game? I understand P(W2|W1) as the ...
val's user avatar
  • 987
2 votes
1 answer
110 views

Complete path of a decision tree

The task is to prove that a complete path starts at the root and ends at the leaf. For me is quite obvious, but I should write a mathematical proof, so, need some help with it. I found a definition: &...
Adolf Miszka's user avatar
2 votes
2 answers
73 views

How to cheapest test N people for an infection?

Say you have $N$ people each having a probability of $p$ for being affected (and, $p+q=1$, a probability of $q$ for being not infected). Say you have a test where you can combine the samples for any $...
Gyro Gearloose's user avatar
3 votes
0 answers
82 views

Probability of a feature in a randomly permuted decision tree constrained that no feature is reached twice in any decision path

I have a (binary) decision tree consisting of nodes $N=\{N_i\}$ that take on boolean propositions/features $F=\{F_k\}$. Different decision paths can split on the same feature so $ |N| >> |F| $ ...
Ilya's user avatar
  • 176
0 votes
0 answers
75 views

A natural number can become equal to double of itself, zero, or any natural number in between. What is the probability of outcome X after n tries.

Tentative title, too long to fit the titling rules: Let A be a natural number. An experiment is defined as A doubling in count, becoming zero, or becoming any natural number in between zero and 2A. ...
Pablo Mery's user avatar
2 votes
1 answer
89 views

Adaboost intuition

The intuition behind adaboost is that if a decision stump is performing well, i.e. $\alpha_t > 0$ by a significant amount, then we'll assign more weights to the misclassified instances and less ...
Eli.Z's user avatar
  • 53
0 votes
2 answers
135 views

12 Balls , prove you have to put 4 balls on each side in order to find odd ball is 3 times

You have twelve (12) balls and a set of balance scales. One (1) of the balls is a different weight to the other eleven (11) balls. You are allowed to use the balance scales three (3) times. You ...
KIMKES1232's user avatar
0 votes
0 answers
91 views

Is it possible to prove this conjecture about Collatz sequences?

I have constructed a tree that looks something like this: $$ 1,2,4,8,16, \begin{cases} 32,64,\begin{cases} 128, 256, \begin{cases} 512...\\ 85... \end{cases}\\ 21, 42, 84... \end{cases}\\ 5, 10, \...
Micah Windsor's user avatar
1 vote
0 answers
116 views

Prove that a split at a node in a decision tree reduces the RSS

Problem: let $m_1, m_2 \in \mathbb{Z}_+$ and $m = m_1 + m_2$ and let $y_1, ... , y_m$ be m real numbers. Define: $\mu = \frac1m\sum_{i=1}^m y_i,\ \ \mu_1 = \frac{1}{m_1}\sum_{i=1}^{m_1} y_i, \ \ \...
Mitch Hughes's user avatar
0 votes
1 answer
77 views

Decision Tree Problem: Evaluate probabilities and determine in terms of C, all the optimal decisions.

I'm struggling with this decision tree question: A part of an aircraft engine can be given a test before installation. The test has only a 75 % chance of revealing a defect if it is present, and the ...
MJ2000's user avatar
  • 17
0 votes
1 answer
102 views

Need help understand this theorem of decision trees

A version of the game of Nim is used to illustrate the minmax strategy in Rosen's Discrete Mathematics and Its Applications, 3ed, chapter 11 p. 768. I understand the ...
J. Doe's user avatar
  • 405
0 votes
0 answers
19 views

in machine learning’s impurity measures. Where does the word Gini originate from? Why entropy is represented with an H? Where does this H come from?

Where does the word Gini originate from? Why entropy is represented with an H? Where does this H come from?
Mr-Programs's user avatar
0 votes
0 answers
16 views

Looking for a counterfactual approach to interpreting classification decisions

Suppose you're a surgeon and you are making a decision based on the output of a model. The variables in this model $x_1, x_2,...$ are clinically interpretable, like age, blood sugar, or hemoglobin. ...
Sam's user avatar
  • 1,013
3 votes
0 answers
65 views

Alice, Barb, and Claire each toss a fair die in that order until someone gets a 6 and wins. What are the probabilities of each player winning? ...

... Generalize this to $n$ players. Compute the probabilities $p_1, ..., p_n$ that each player wins. Proposed Solution: Let $p_k$ be the probability of player $k$ winning in the set $\{p_1, ..., ...
Joshua Anderson's user avatar
0 votes
1 answer
50 views

Nearest-neighbour classifier

Given a dataset $\mathcal D =\{x_i, y_i\}$ where $i$ runs from $1$ to $N$ and a new sample $x$, we simply assign to $x$ the label of the nearest sample to $x$ in $\mathcal D$, i.e. $f(x)=y_i$ such ...
taupi's user avatar
  • 377
1 vote
1 answer
107 views

𝛾-rule in semantic tableaux of first-order logic

I'm a novice and I'm trying to understand semantic tableaux in First-Order Logic. 𝛿 - existential rule makes sense to me, if ∃x A(x) is true, saying "let c by ...
jack malkovick's user avatar