# 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.

94 questions
Filter by
Sorted by
Tagged with
15 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 ...
• 153
28 views

### leaves of a binary decision tree

Consider the following claims: a) the minimum height of a binary decision tree with 17 leaves is 5 b) the maximum height of a binary decision tree with 17 leaves is 5 I think only a) is true statement,...
• 302
37 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 ...
• 113
19 views

### Prove that the number stored in the root of AVL tree is $2^{\left \lfloor{\log_2(n / 3)}\right \rfloor + 1}$

The question I am having trouble with: For $n \geq 3$, let $T_n$ denote the AVL tree obtained by inserting the numbers 1, 2, 3, ..., n, in this order, into an empty AVL tree. Prove that the number ...
• 21
12 views

### AO* algorithm to solve Canadian Traveller Problems: how are nodes expanded?

I'm re-implementing a AO* algorithm to solve Canadian Traveller Problems (CTPs), of which numerous variants exist like this one. In a nutshell, a CTP consists in reaching the goal vertex of a graph ...
• 155
1 vote
31 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 ...
20 views

### Game theory extensive form game

I have a question regarding the following game. How do we find all the SPNE( Subgame perfect Nash equilibrium)? Click here to see the game
20 views

### Information Gain Using Gini

How do you calculate Information Gain Using Gini? The set is a classification between watching a series or a movie: For choosing to watch a Series, I have: (0, 0, 0, 1) (0, 0, 0, 1) (0, 0, 1, 1) (1, 1,...
60 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: ...
• 1
20 views

### Can CART do multi-lable classifaction like ID3?

I am really confused between 1D3 AND CART. As i know that CART can do regression and binary classification is it possible to do multi-lable classifications with CART. Please recommend me the book ...
47 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 ...
• 597
1 vote
74 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 ...
• 597
22 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. ...
• 101
18 views

### Handling of infinite utility children when backward inducting into a Nature node of a Expectiminimax game tree

Background I am coding a game playing engine for a (3+, but for now assume) 2 player card game, which has a shuffled (AKA random) & face down (AKA hidden) deck. This game has perfect* and complete ...
• 101
1 vote
135 views

### Information Gain is always positive proof?

Let $\vec{p} = (p_1,p_2, p_3, ... p_C)$ be the probability vector of a training set (TS) where $p_i$ is the probability that a datapoint from the TS is in class $i$; and let there be $C$ total classes....
• 2,189
70 views

### Decision tree example expansion and conversion to decision list.

I am working through some questions and I am stumped as to the questions a) and c) and require some direction or examples if possible. In the questions I have been able to answer b) and d) but I get ...
23 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 ...
28 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 ...
• 111
1 vote
19 views

• 1,022
80 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|$ ...
• 176
67 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. ...
50 views

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 ...
• 53
48 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 ...
• 425
89 views

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, \... 1 vote 0 answers 59 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, \ \ \... • 189 0 votes 1 answer 71 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 ... • 17 0 votes 1 answer 46 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 ... • 395 0 votes 0 answers 17 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? • 109 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. ... • 907 3 votes 0 answers 64 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, ..., ... 0 votes 1 answer 43 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 ... • 367 1 vote 1 answer 70 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 ... 3 votes 2 answers 295 views ### Propositional Logic and Redundancy The Dutch philosopher Emanuel Rutten wrote an article, titled Dissolving the Scandal of Propositional Logic?, about the philosophical problems with the material conditional. From his article, we quote ... • 16.3k 2 votes 0 answers 38 views ### Markov decision process structural properties I am trying to prove a structural property of a Markov Decision Process (MDP), but I have not been able to do so. I am wondering if someone can give me some insight in how to prove it or give me some ... • 21 1 vote 0 answers 34 views ### Decision Trees - Regression trees weighting of child nodes? I'm familiar with how classification trees weight the impurity measure of a potential split by the proportion of observations that would fall into each child node, such as:$$ loss = \frac{n_1}{N_m} ...
1 vote
I have to resolve an exercise for decision analysis network. I have the following decision tree for that decision analysis network: \begin{array}{l} G&\to&Y&\to&D&\to&X&...