Construct the weight vector of the maximum margin hyperplane

Assignment Help Data Structure & Algorithms
Reference no: EM13851882

Part 1. Text Reading:

Decision Trees Reasoning with uncertainty Course Slides

Part 2. Problems:

(Note: Please include any external reference materials other than the textbook. Use the APA format where appropriate.)

Problem 2.1: Decision Tree

For this question you need to refer to the decision tree section in the Course Slides (Module 2-2) posted on Blackboard.

One major issue for any decision tree algorithm is how to choose an attribute based on which the data set can be categorized and a well-balanced tree can be created. The most traditional approach is called the ID3 algorithm proposed by Quinlan in 1986. The detailed ID3 algorithm is shown in the slides. The textbook provides some discussions on the algorithm in Section 18.3.

For this problem please follow the ID3 algorithm and manually calculate the values based on a data set similar to (but not the same as) the one in the course slides. This exercise should help you get deep insights on the execution of the ID3 algorithm. Please note that concepts discussed here (for example, entropy, information gain) are very important in information theory and signal processing fields. The new data set is shown as follows. In this example one row is removed from the original set and all other rows remain the same.

Following the conventions used in the slides, please show a manual process and calculate the

following values: Entropy(Sweather=sunny), Entropy (Sweather = windy), Entropy(Sweather = rainy)

Gain (S, weather), Gain (S, parents) and Gain (S, money). Based on the last three values, which attribute should be chosen to split on?

Please show detailed process how you obtain the solutions.

Weekend  Weather  Parents  Money  Decision (Category)  
W1  Sunny  Yes  Rich  Cinema 
W2  Sunny  No  Rich  Tennis 
W3  Windy  Yes  Rich  Cinema 
W4  Rainy  Yes  Poor  Cinema 
W5  Rainy  No  Rich  Stay in 
W6  Rainy  Yes  Poor  Cinema 
W7  Windy  No  Poor  Cinema 
W8  Windy  No  Rich  Shopping 
W9  Windy  Yes  Rich  Cinema 

Problem 2.2:

The Decision Tree inductive learning algorithm may be used to generate "IF ... THEN" rules that are consistent with a set of given examples. Consider an example where 10 binary input variables X1, X2, , X10 are used to classify a binary output variable (Y).

(i) At most how many examples do we need to exhaustively enumerate every possible combination of inputs?

(ii) At most how many leaf nodes can a decision tree have if it is consistent with a training set containing 100 examples?

Please show detailed process how you obtain the solutions.

Problem 2.3. Bayes Theorem

A quality control manager has used algorithm C4.5 to come up with rules that classify items based on several input factors. The output has two classes -- Accept and Reject. Test results with the rule set indicate that 5% of the good items are classified as Reject and 2% of the bad items classified as Accept.

Historical data suggests that two percent of the items are bad. Based on this information, what is the conditional probability that:

(i) An item classified as Reject is actually good?

(ii) An item classified as Accept is actually bad?

Please show detailed process how you obtain the solutions.

Problem 2.4: Support Vector Machine

Consider the following set of training data.

x1  x2  class 
1 1
2 2
2 0
3 1
0 0
1 0
0 1
-1 1

(i) Plot these six training points in a two-dimensional space (with x1 and x2). Are the classes {+, -} linearly separable? Why?

(ii) Construct the weight vector of the maximum margin hyperplane by inspection and identify the support vectors.

(iii) If you remove one of the support vectors, does the size of the optimal margin decrease, stay the same, or increase? Justify your answer.

(iv) Is your answer to (iii) also true for any dataset in a 2-dimentioanl space? Provide a counterexample if it is not true, or give a short proof if it is true. When we have another dataset in a space with more than two dimensions, do you have the same answer? Justify.

Reference no: EM13851882

Questions Cloud

Give specific interpretations for the coefficients in model : Suppose we collect the following information from a large number of junior and senior level college students: Give specific interpretations for the coefficients in the model, and discuss whether or not they make sense. Based on this equation, what co..
Supply goods and services for consumers at attractive prices : Why are entrepreneurs willing to supply goods and services for consumers at attractive prices? Is it because they care personally about the consumers?
Write a report on the csp and customer responsibilities : You are to write a report on the CSP and customer responsibilities associated with the different cloud architectures (SaaS, PaaS, and IaaS). Explain the different types of cloud service architectures.
What is the growth rate of output per person in economy : Now suppose the parameters of the model take the following values. what is the growth rate of output per person in this economy? what is the initial level of output per person? What is the level of output per person after 100 years?
Construct the weight vector of the maximum margin hyperplane : Construct the weight vector of the maximum margin hyperplane by inspection and identify the support vectors - how many leaf nodes can a decision tree have if it is consistent with a training set containing 100 examples?
What will be amount of interest accumulated at the time : Emily Dorsey's current salary is $85,000 per year, and she is planning to retire 19 years from now. She anticipates that her annual salary will increase by $1,000 each year ($85,000 the first year, to $86,000 the second year, $87,000 the third year, ..
Annual heating and cooling cost of an office building : A “green” (environmentally friendly) office building costs as average of $3.50 per square foot each year to heat and cool. What is the total annual heating and cooling cost of an office building that has 10,000 square meters of space?
Increase manufacturers costs of producing insulation : New safety regulations increase manufacturers’ costs of producing insulation. What happens in the market for insulation as a result?
How describe an experiment about frequency of sound : How describe an experiment about "frequency of sound"

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Explain two possible solution-fill in blank squares by words

The objective is to fill in blank squares using words from the list. Your task is to formulate problem as constraint satisfaction problem. Explain two possible solutions.

  Articles available our csu library databases

The Article Critique is required to be a minimum of two pages to a maximum of four pages, double-spaced, APA style, from the journals and articles available in our CSU Library Databases. The article should deal with any of the material presented i..

  Discuss the issues involved in managing software selection

Prepare a PowerPoint presentation which summarizes the background, requirements, analysis and reasons for your choice. Alternative presentation formats such as Prezi are acceptable

  Questionneural and tree learning on continuous attributesa

questionneural and tree learning on continuous attributesa in general feedforward neural networks multi-layer

  Write a program that uses a recursive algorithm to compute

Write a program that uses a recursive algorithm to compute the determinant of a maxtrix. It should read a matrix, print it out, and compute and print the determinant.

  Modify bellman ford algorithm to find negative weight cycle

Demonstrate how to modify the Bellman Ford algorithm to find and print a negative weight cycle in a weighted directed graph G if one exists.

  Determine schedule that obtains maximum amount of profit

Assume you have one machine and a set of n jobs a1, a2, ..., an to process on that machine. Determine the schedule that obtains the maximum amount of profit. Compute the running time of your algorithm?

  Possible external-memory map implementation

Another possible external-memory map implementation is to use a skip list, but to collect consecutive groups of  O ( B ) nodes, in individual blocks, on any level in the skip list

  Write the relation r as a set if ordered pairs

let A={a,b,c,d,e} and suppose R is an equivalence relation on A . Suppose R has two equivalence classes. also aRd ,bRc and eRd in R . WRITE the relation R as a set if ordered pairs

  Advantage of fast running time of insertion sort

Running time of quicksort can be enhanced in practice by taking advantage of fast running time of insertion sort when its input is "nearly" sorted.

  Write algorithm to decide which commute is cheaper

Write working algorithm in pseudo code to decide which commute is cheaper: You wish to decide whether you must drive your car to work or take train. You know one-way distance

  Draw the cash-flow diagram for this situation

Construct a loan amortization table, similar to the one shown in table 6-2, showing the principal and interest seperated for the first 6 months of FunSoft's loan.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd