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
2 votes
0 answers
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 ...
user avatar
  • 153
0 votes
0 answers
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,...
user avatar
  • 302
0 votes
0 answers
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 ...
user avatar
  • 113
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 155
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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
user avatar
  • 1
0 votes
0 answers
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,...
user avatar
0 votes
0 answers
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: ...
user avatar
  • 1
0 votes
0 answers
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 ...
user avatar
2 votes
1 answer
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 ...
user avatar
  • 597
1 vote
2 answers
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 ...
user avatar
  • 597
0 votes
0 answers
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. ...
user avatar
  • 101
0 votes
0 answers
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 ...
user avatar
  • 101
1 vote
0 answers
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....
user avatar
  • 2,189
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
0 answers
19 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\...
user avatar
1 vote
0 answers
38 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 ...
user avatar
  • 145
0 votes
0 answers
24 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$ ...
user avatar
  • 1,133
1 vote
2 answers
55 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)...
user avatar
  • 23
0 votes
1 answer
133 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 ...
user avatar
1 vote
0 answers
53 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, ...
user avatar
2 votes
0 answers
64 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 ...
user avatar
  • 4,495
2 votes
1 answer
70 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 ...
user avatar
0 votes
5 answers
144 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. ...
user avatar
0 votes
0 answers
23 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 ...
user avatar
  • 43
1 vote
3 answers
75 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 ...
user avatar
  • 185
0 votes
1 answer
186 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 ...
user avatar
  • 897
2 votes
1 answer
92 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: &...
user avatar
2 votes
2 answers
68 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 $...
user avatar
3 votes
0 answers
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| $ ...
user avatar
  • 176
0 votes
0 answers
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. ...
user avatar
2 votes
1 answer
50 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 ...
user avatar
  • 53
0 votes
2 answers
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 ...
user avatar
0 votes
0 answers
89 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, \...
user avatar
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, \ \ \...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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?
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. ...
user avatar
  • 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, ..., ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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} ...
user avatar
1 vote
0 answers
40 views

How to optimise a boolean expression

I am working on an optimization problem involving Boolean expressions and wanted some help as I have very little knowledge about the topic. The problem statement is as follows: There are a set of ...
user avatar
1 vote
0 answers
42 views

Compute conditional probability for a decision analysis network

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&...
user avatar