Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
12 views

If Impurity of Attribute A is less than Impurity of Attribute B in ID3, does this hold in CART?

I need to prove the following statement true or false: Impurity_CART(A) > Impurity_CART(B) => Impurity_ID3(A) > Impurity_ID3(B) I have managed to reduce the above equation to the following: $-\sum_{...
1
vote
1answer
7 views

VC-dimension of the class of decision trees

I need to show that the VC-dimension of the class of decision trees over the domain ${0,1}^d$ is $2^d$ I tried to show that any binary classi er can be implemented as a decision tree of height at ...
0
votes
1answer
44 views

How would I solve a classic Bayes Theorem problem using a probability tree? To help visualize what Bayes Theorem is doing.

For example Assume that a test for a disease gives a positive result for 2.5% of people who do not have the disease, but does not test negative if the person has the disease. What is the ...
25
votes
4answers
2k views

Shannon entropy of a fair dice

The formula for Shannon entropy is as follows, $$\text{Entropy}(S) = - \sum_i p_i \log_2 p_i $$ Thus, a fair six sided dice should have the entropy, $$- \sum_{i=1}^6 \dfrac{1}{6} \log_2 \dfrac{1}{6}...
0
votes
0answers
11 views

Generating Huffman codes from unsorted code lengths.

As an exercise for myself, I am writing an Ogg Vorbis decoder. Part of the decoding process involves generating Huffman codes from a series of code lengths that is later used when decoding audio ...
0
votes
2answers
61 views

What type of tree is this?

The checkmarks I've drawn means that the branch ends or a node with the same number allready exists in the tree. I.e it means it reaches some cycle or ends the branching. I don't know if this is even ...
-1
votes
1answer
26 views

number of nodes in a decision tree

I don't know how to prove/disprove this: In a decision tree for sort algorithm there are at least $2^{n!}$ nodes. I know that the number of leaves is $n!$
0
votes
0answers
21 views

Do forward binary search tree embeddings have several large jumps of large size?

A forward embedding stores the binary tree in an array in such a way that the parent of every element in the tree has index smaller than its children. A static binary search tree can be stored in an ...
0
votes
0answers
10 views

In DT or Gini, what's the practice of “normalizing” at split?

So in both decision trees and Gini Index (related to selecting meaningful attributes), the split is defined (e.g. for Gini) as: $$gini_A(D)=\frac{|D_1|}{|D|}gini(D_1)+\frac{|D_2|}{|D|} gini(D_2)$$ ...
2
votes
0answers
22 views

Boosting tree for feature generation v.s. Boosting tree for classification

I am referring to this sample (http://scikit-learn.org/stable/auto_examples/ensemble/plot_feature_transformation.html#sphx-glr-auto-examples-ensemble-plot-feature-transformation-py) for the context. ...
0
votes
0answers
10 views

Convergence Rate of Splitting point in a Threshold Regression

I'm doing a research about a thresholding regression model, like $$ Y = \beta_0 + \beta_{1,1} 1_{\{X\ge d\}} + \beta_{1,2} 1_{\{X< d\}} + e \tag{1} $$ where $1_{\{\cdot\}}$ is the indicator ...
1
vote
1answer
24 views

Calculating the GINI impurity

I have a question regarding the GINI impurity that we use while building decision trees. From the wiki page on gini impurity, Gini impurity can be computed by summing the probability ${\...
0
votes
0answers
20 views

How to properly draw a decision tree regarding a problem that involves timeline?

I'm confused about how to draw a decision tree when there's a timeline involved. Briefly speaking, the problem is that, a patient who potentially has serious issues could choose to take a test to ...
0
votes
0answers
20 views

number of possible kd trees from N points

thought this question would already be answered and easy to find but I guess not. If I have N (unique) points in D dimensions, I want to confirm my logic that the number of possible KD trees is: (D^N)...
0
votes
0answers
21 views

Implementing a poisson distribution in a probability tree

I need to produce a probability tree of three variables. The first variable $R$ represents days between rain events and is normally distributed. The second variable $N$ represents the number of ...
0
votes
0answers
11 views

Describe how to prune a regression or decision tree using information given by $E(D_a, T)$ and $E(D_b, T)$.

Yet again I have a question about trees that where I'm completely lost. Would really appreciate an answer to this question. Thank you. Let $D_a$ and $D_b$ be two independent data sets. Let $T$ be a ...
0
votes
1answer
25 views

Decision tree and stopping the splitting process

I've have this question and I'm completely lost. Would really appreciate an answer to this question. Thank you. Let $D_a$ denote the training data set and let $T$ be a decision tree trained on $D_a$ ...
0
votes
0answers
73 views

About cost-complexity pruning of regression trees.

Let $C_{\alpha}(T)$ be the cost-complexity criterion \begin{align} C_{\alpha}(T) = R(T) + \alpha |T|. \end{align} Given $\alpha \geq 0$, a subtree $T(\alpha)$ of $T$ is called optimally pruned ...
0
votes
0answers
127 views

How to build decision trees based on utility function?

You live in an area that has a possibility of incurring a massive earthquake, so you are considering buying earthquake insurance on your home at an annual cost of 1000 dollars. The probability of an ...
0
votes
0answers
69 views

how to get decision tree and calculate the error of tree?

Recently i start to read the artificial intelligent book written by David poole and i am trying to solve some exercise from there. In exercise that "Suppose we have a system that observes a person’s ...
0
votes
1answer
23 views

Event tree - can I add and mulitply the probabilities like this

If I have an event tree such as the following: Is the following solution then correct to get to B or to D: $(0.1 \times 0.4) + (0.1 \times 0.6 \times 0.7) = 0.082$ Or should I only use the first ...
0
votes
1answer
138 views

Poisson Process (Expected Waiting Time) w Tree Diagram

Hi everyone so I have a quick question. Say for example we have a supermarket in which customers arrive with an intensity of 10 per hour. The supermarket has 3 aisles, A,B and C. The probability of ...
0
votes
1answer
44 views

Why do we want a decision tree to be shallow? Why do we split to maximize information gain?

When constructing a decision tree, we use a measure such as the Gini Impurity or Information Gain to decide which split is best. IIUC, we want to have as shallow as tree as possible. But why do we ...
15
votes
4answers
4k views

Monty hall problem probability 2/6?

For the Monty hall problem, with 3 doors, two of which have sheep and 1 has a car. I calculated the probability of getting the car if you swap being 2/6 instead of 2/3. I have drawn this tree diagram ...
1
vote
0answers
164 views

Perfect recall, Absent-minded driver,behavior strategy, equivalent mixed strategy

I wonder if a behavior strategy in an extensive form game has always an equivalent mixed strategy. There is no consensus in the literature I've read on this: in the chapter in the Handbook of game ...
1
vote
1answer
46 views

'ordered' set of rules

I have the following decision tree: ...
0
votes
2answers
283 views

Converting decision tree into a logical expression [closed]

I need to convert this decision tree into a logical expression by using "and", "or" and "not" logical operators. I have been trying to solve this for 3 days. Any help would be appreciated.
1
vote
0answers
74 views

Function for Risk Score based on Decision Tree

I want to build a model that generates a risk score based on a decision tree of six levels. All these levels and options have the same weight (1). The first level has three options. The second level ...
6
votes
2answers
187 views

Diminishing upper limit on Rubik's Cube solutions - why so long?

I distinctly remember the news in 2007 about how researchers at Northwestern University had established the upper bound on moves needed to solve a Rubik's Cube at 26. (I haven't been paying attention ...
1
vote
1answer
32 views

Repetition of formulas in nodes of Semantic Tableau

I'm studying Propositional and First Order Logic and I have to practice with the Tableaux Method in order to check satisfiability of a formula. I create new nodes of the tree by using the Completion ...
0
votes
1answer
40 views

Average number of keystrokes based on probability

"A researcher in the rain forest has left his laptop unattended and a curious monkey has come to investigate. When the researcher looks up from the plant he is studying he sees the monkey at the ...
1
vote
0answers
134 views

Combinatorics applied to a playing card game

I want to analyze the features of a deck of Magic the Gathering cards game, which many of you know for sure. My goal now is to create an Excel sheet, where you can enter the composition of the deck (...
1
vote
0answers
105 views

Decomposition of Probability Tree Choices and Measuring Entropy

Shannon [ref] introduced entropy as a measure of information, with 3 main properties (page 49). My question is with respect to the third property, where the entropy H should be a weighted sum of the ...
0
votes
1answer
91 views

Probability Sum

A purchasing agent must decide to accept or reject an incoming shipment of machine parts. The agent wishes to do either of the following: a1: Accept the shipment a2: Reject the shipment The fraction ...
0
votes
2answers
1k views

Finding the maximum length of a minimum spanning tree

Graph G has 4 vertices/nodes and 5 edges. It is also connected. Its edges have the following weights: 5, 8, 10, 16, 18. The minimum length for a minimum spanning tree of graph G would be ...
0
votes
0answers
172 views

Decision tree probabilities

I am solving the following decision problem. I formulated the problem into the tree OK but am unsure of what the probabilities along the branches are. i.e. how do I go from, for example, $P(H_1 \cap ...
2
votes
1answer
702 views

Probability of selecting a jury

Does anyone know how to find the probability of selecting a jury of $12$ people ($6$ men and $6$ women) out of an initial group of $18$ people ($6$ men and $12$ women)? With my knowledge of ...
0
votes
1answer
160 views

Binary Decision Trees

I know the basics to a binary decision tree, but this problem has me a little stumped, and I'm looking for some verification on my ideas. The problem is: "Create a binary decision tree that reflects ...
3
votes
2answers
1k views

How do I know when to use a Venn diagram or a probability tree? Also, when can I assume that the events are independent?

I have 2 specific problems, one 'requiring' me to use a probability tree, and the other a Venn diagram. I know that apparently the Venn diagrams can be converted into probability trees and vice versa, ...
1
vote
0answers
54 views

Monty-Hall-Problem / Complete Tree of Possibilities [duplicate]

EDIT: I know that this is a trigger topic. I know there is a hell of posts out there. I don't need to be told, that I should switch, neither why. I want to know, what is wrong with those trees. If ...
0
votes
0answers
257 views

Finding the smallest decision tree of a Boolean function

From Computational Complexity: A Moden Approach, A decision tree is a model of computation used to study the number of bits of an input that need to be examined in order to compute some ...
1
vote
1answer
129 views

Value of experimentation on decision analysis problem?

The following table represents a decision analysis problem (in units of a thousand dollars) Suppose you can obtain information which will tell you, with certainty, whether or not state 1 (S1) ...
1
vote
1answer
102 views

Correct calculation of recursive limit

I'm constructing a binomial (decision) tree with nodes $ x_i $ according to the following recursion: $ x_{i+1} = \begin{cases} x_i e^{\mu \delta t + \sigma(x_i)\sqrt{\delta t}} & \text{for next ...
0
votes
1answer
83 views

Bayes' theorem timeline of events

When using Bayes' theorem to find the probability of future events along a tree I have had it explained to me that parent events to the child events have already happened? Is this strictly true or can ...
4
votes
1answer
194 views

Have I Found an Error in “Game Theory” by Hans Peters?

I am reading the book Game Theory: A Multileveled Approach Second Edition by Hans Peters. It appears to be the most recent copy. I've search here and on Google for a list of known errors in the book, ...
0
votes
1answer
95 views

Calculating Entropy

Hi there kind people, I'm studying for an Artificial Intelligence test in a week or so, and this question is from a past paper - and it has really stumped me. Any help would be appreciated. Thank ...