EE 559 Homework 2
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
EE 559
Homework 2
Posted: Fri., 1/26/2024
Due: Fri., 2/2/2024, 11:59 PM PST
Reminder on MATLAB use: for Problem 2 in this homework, you may use either Python or MATLAB. Starting with Homework 3, only Python will be permitted.
|
For a dataset: Classification accuracy is defined as number of correctly classified data points divided by the total number of data points. Error rate is defined as number of misclassified data points (errors) divided by the total number of data points. Unclassified rate is defined as number of unclassified data points divided by the total number of data points. |
1. This is an analytic problem to be done by hand. Parts (a)-(c) refer to a 2-class nearest-means classifier, and class-mean vectors μ1, μ2. All parts below have D features.
(a) Give an algebraic expression for the decision boundary, the decision rule, and the
discriminant function g(x). Simplify as much as possible. Is the classifier linear?
(b) If the classifier is linear, starting from the general expression for a 2-class discriminant function g(x) for a linear classifier, find an expression for the weights for the nearest- means classifier in terms of the mean vectors μ1, μ2 .
(c) If the classifier is not linear, then write an expression for a nonlinear function g(x) with weight for coefficients of each term. Then find expressions for the weights of the nearest-means classifier in terms of μ1, μ2 .
Parts (d)-(f) refer to a C-class nearest-means classifier, with C > 2.
(d) Consider the following decision rule:
x ∈ Γk iff k = argmaxm {gm (x)}
Can you find expressions for the gm (x), i = 1,2, ⋯ , C , such that this is the decision rule for a nearest-means classifier? If so, give your expression for gm (x), and simplify it as much as possible.
Hint: when comparing gm (x) only to each other (e.g., gi (x) to gj (x)), any additive term that doesn’t depend on m, and that is common to gm (x) ∀m, can be dropped from all gm (x).
(e) Is gm (x) linear? Justify your answer. If yes, give expressions for the weights for the nearest-means classifier in terms of the mean vectors µk .
(f) Is this multiclass nearest-means classifier an example of the MVM multiclass method? Justify your answer.
2. In this problem you will code a multiclass classifier to use the OvR method. For each 2-class problem, use a nearest-means classifier. You will apply this multiclass classifier separately to each of datasets 4, 5, 6 from Homework 1, as directed below.
For the plots below, you may find it useful to use plotDecBoundaries code that was given with Homework 1. You may need to modify it somewhat for this problem.
For the decision rule that combines the results of the 2-class classifiers (“combining rule”), you will use 3 different methods, as follows.
(a) Use the default decision rule we gave in Lecture 3 for OvR method, leaving points in indeterminate regions as unclassified.
Plot the training points, decision regions and boundaries, for each 2-class (binary) classifier (3 plots for each dataset).
Plot the final decision boundary and regions for the 3-class problem (1 plot for each dataset).
Report the training classification accuracy, error rate, and unclassified rate, on the training set and separately on the test set (18 numbers total): report them in a table: columns labeled “accuracy”, “error”, “unclassified”; and rows labeled “dataset_4 train”, “dataset_4 test”, “dataset_5 train”, “dataset_5 test”, “dataset_6 train”, “dataset_6 test” .
(b) Use the default decision rule we gave in Lecture 3 for OvR method, but also classify points in indeterminate regions using the rule:
x ∈ Γk iff k = argmaxm {gm (x)}
in which the discriminant gm (x) for each m is the discriminant function value for the S'm vs. S'm 2-class (nearest-means) classifier.
Repeat the plots and numerical-results table of part (a), except using this decision rule.
(c) Use an alternate decision rule instead of the default decision rule: classify all points in
feature space according to:
x ∈ Γk iff k = argmaxm {gm (x)}
in which the discriminant gm (x) for each m is the discriminant function value for the S'm vs. S'm 2-class (nearest-means) classifier.
Repeat the plots and accuracy reports of part (a), except using this decision rule.
(d) Compare the 3 different combining rules: comment on, and explain if you can, any
observed similarities and differences.
3. Let each function on the left-hand side below represent the exact time (or space) complexity of an algorithm. For each part, answer whether the given expression is true or false. If you aren’t sure, refer the definitions of big-O, big-Ω, and big- Θ .
(a) m3 + 5m − 50 = O(m3)
(b) m3 + 5m − 50 = O(m4)
(c) m3 + 5m − 50 = Ω(m3 )
(d) m3 + 5m − 50 = Ω(m4 )
(e) m3 + 5m − 50 = Θ(m3)
(f) m3 + 5m − 50 = Θ(m4)
(g) 2(m+3) = Θ(2m )
4. You are given that algorithm A has a computational time-complexity of:
p(m) = Θ Gq(m)I
in which m is a variable; here we can take m to represent the number of features.
You will consider the following exact time complexities (each part represents a different algorithm):
(i) p(m) = 3m
(ii) p(m) = 100m
(iii) p(m) = 8m3
(iv) p(m) = 10log2 (m)
(v) p(m) = 2m
(a) For each time complexity given above, give the simplest-form asymptotic tight bound, Θ Gq(m)I.
We measure the computation time with m = m3 features, and get a time of T3 . We want to know the computation time T4 of running the same algorithm with m4 = R m3 features, for R > 1, as well as an asymptotic bound for it. We can consider m3 to be constant, and R to be the variable that is increasing.
For each time-complexity function p(m) given above, we have
T4 p(m4 ) p(Rm3 )
= =
T3 p(m3 ) p(m3)
(b) Give the exact 
for each of the time complexities p(m) given above, in terms of R. Express in simplest form. (Simplest form will generally include R, but will not include m4 ; and will only include m3 if necessary.)
(c) Now for each result of (b), give a simplest-form asymptotic tight bound in terms of R . Your answers should be in the form Θ Rq' (R)S, in which qI (R) is your asymptotic tight-
bound expression. Your expression may include m3 if necessary, but not m4 .
(d) Compare your answers to (c) with your answers to (a); what conclusions can you draw?
(e) Compare your answers to (c) with your answers to (b) (that is, compare exact T3/T4 of (b)
with the asymptotic-bound function q’ (R) of (c)). What conclusions can you draw?
2024-02-26