CSE 802 -Homework2 Solved

- Pattern Recognition and Analysis






Please read the following instructions carefully:

1.    You are permitted to discuss the following questions with others in the class. However, you must write up your own solutions to these questions. Any indication to the contrary will be considered an act of academic dishonesty.

2.    A hard-copy of this assignment must be submitted by March 9, 12:40 pm in class. In this copy, please include the names of individuals you discussed this homework with and the list of external resources (e.g., websites, other books, articles, etc.) that you used to complete the assignment (if any). Late submissions will not be graded.

3.    When solving equations or reducing expressions you must explicitly show every step in your computation and/or include the code that was used to perform the computation. Missing steps or code will lead to a deduction of points.

4.    Code developed as part of this assignment must be included as an appendix to your submission or inline with your solution.



1.      Consider a set of 1-dimensional feature values (i.e., points) pertaining to a class that is available here.

(a)     [3 points] Plot the histogram of these points using a bin size of 2, i.e., each bin should have a range of 2.

(b)    [4 points] Compute and report the mean and the biased variance of these points.

(c)     [3 points] Assuming that the given points are generated by an underlying Gaussian distribution, plot the pdf function on the same graph as (a).

2.      Consider the three-dimensional normal distribution p(x) ∼ N(µ,Σ), where µ = (1,1,1)t and Σ =

                       

            1   0   0

          0    5    2.

            0   2   5

(a)     [2 points] Compute and report the determinant of the covariance matrix, i.e., | Σ |.

(b)    [2 points] Compute and report the inverse of the covariance matrix, i.e., Σ−1.

(c)     [3 points] Compute and report the eigen-vectors and eigen-values of the covariance matrix.

(d)    [3 points] Compute and report the probability density at (0,0,0)t and at (5,5,5)t.

(e)     [2 points] Compute the Euclidean Distance between µ and the point (5,5,5)t.

(f)      [3 points] Compute the Mahalanobis Distance between µ and the point (5,5,5)t.

3.      [10 points] Suppose we have two normal distributions, corresponding to two classes (ω1 and ω2) with the same covariances but different means: N(µ1,Σ) and N(µ2,Σ). In terms of their prior probabilities P(ω1) and P(ω2), state the condition that the Bayes decision boundary not pass between the two means.

4.      [10 points] Consider a two-class problem with the following class-conditional probability density functions (pdfs): p(x | ω1) ∼ N(0,σ2)

and p(x | ω2) ∼ N(1,σ2).

Show that the threshold, τ, corresponding to the Bayes decision boundary is:

τ=   −σ2ln•λλ2112PP((ωω12))˜,

where we have assumed that λ11 =λ22 = 0.

5.      [15 points] Consider a two-category classification problem involving one feature, x. Let both classconditional densities conform to a Cauchy distribution as follows:

1     1 p(x | ωi)= πb.1+ x−bai 2,  i = 1,2.

Assume a 0-1 loss function and equal priors.

(a)     Compute the Bayes decision boundary.

(b)    Show that the probability of misclassification according to the Bayes decision rule is

                                                                                   1     1

P(error)= 2 − π tan−1a22−ba1.

(c)     Plot P(error) as a function of |a2 − a1|/b.

(d)    What is the maximum value of P(error). Under what conditions will this occur?

6.      [10 points] Consider the following class-conditional densities for a three-class problem involving twodimensional features:

p(x|ω1) ∼ N (−1,−1)t,I; p(x|ω2) ∼ N (1,1)t,I;

p .

(Here, class ω3 conforms to a Gaussian Mixture Model (GMM) with two components - one component is N (0.5,0.5)t,I and the other component is N   - whose weights are equal (i.e.,  )).

(a)     In a 2D graph, mark the mean of ω1, ω2, and the two components of ω3. In the same graph, mark the point x =(0.1,0.1)t.

(b)    Assuming a 0-1 loss function and equal priors, determine the class to which you will assign the two-dimensional point x =(0.1,0.1)t based on the Bayes decision rule.

7.      Consider the following bivariate density function for the random variable x:

                                       0 20           10

            poriginal(x) ∼ N          0 , 10     30    .

(a)     [5 points] What is the whitening transform, Aw, of x? (You can use matlab (or any other programming language) to compute the eigenvectors/values).

(b)    [3points]Whenthewhiteningtransformationisappliedto x, whatisthedensityfunction, ptransf orm of the resulting random variable?

(c)     [5 points] Generate 10,000 bivariate random patterns from poriginal (if you are using matlab, then the mvnrnd function can be used to generate these patterns). Plot these patterns in a graph.

(d)    [5 points] Apply the whitening transform, Aw, to the 10,000 bivariate patterns generated above. Plot the transformed patterns in a separate graph.

(e)     [2 points] Compare the patterns in 7c and 7d. What do you observe?.

8.      Consider a two-category (ω1 and ω2) classification problem with equal priors. Each feature is a twodimensional vector x = (x1, x2)t. The class-conditional densities are:

p(x|ω1) ∼ N(µ1 =(0,0)t,Σ1 = 2I), p(x|ω2) ∼ N(µ2 =(2,2)t,Σ2 = I).

(a)     [7 points] Compute the Bayes decision rule and the Bayes decision boundary.

(b)    [3 points] Generate 10,000 bivariate random patterns from each of the two densities (if you are using matlab, then the mvnrnd function can be used to generate these patterns). Plot these patterns in a graph using different markers to distinguish the two classes. On the same graph, plot the Bayes decision boundary.

(c)     [5 points] Compute and report the empirical error rate and the confusion matrix when classifying these 10,000 patterns using the Bayes decision policy.

9.      Consider a two-category classification problem involving two-dimensional feature vectors of the form x = (x1, x2)t. The two categories are ω1 and ω2, and

p(x | ω1) ∼ N (−1,−1)t,I, p(x | ω2) ∼ N (1,1)t,I,

P .

(a)     [10 points] Calculate the Bayes decision boundary and write down the Bayes decision rule assuming a 0-1 loss function. The Bayes decision rule has to be written in terms of the Bayes decision boundary.

(b)    [5 points] What are the Bhattacharyya and Chernoff theoretical bounds on the probability of misclassification, P(error)?

(c)     [5 points] Generate n = 25 test patterns from each of the two class-conditional densities and plot them in a two-dimensional feature space using different markers for the two categories (if you are using matlab, then the mvnrnd function can be used to generate these patterns). Draw the Bayes decision boundary on this plot for visualization purposes.

(d)    [5 points] What is the confusion matrix and empirical error rate when classifying the generated patterns using the Bayes decision rule?

(e)     [5 points] Can the empirical error rate exceed the theoretical bounds on the probability of misclassification? Why or why not? (Hint: Compute the empirical error rate multiple times by repeatedly generating n = 25 test patterns from each of the two class-conditional densities.)

10.    [15 points] Consider a 1-dimensional classification problem involving two categories ω1 and ω2 such that P(ω1) = 2/3 and P(ω2) = 1/3. Assume that the classification process can result in one of three actions:

α1 - choose ω1; α2 - choose ω2; α3 - do not classify.

Consider the following loss function, λ:

λ(α1|ω1)=λ(α2|ω2)= 0; λ(α2|ω1)=λ(α1|ω2)= 1; λ(α3|ω1)=λ(α3|ω2)= 1/4.

For a given feature value x, assume that p(x|ω1)= 2−2x and p(x|ω2)= 1/2. Here, 0 ≤ x ≤ 2.

Based on the Bayes minimum risk rule, what action will be undertaken when encountering the value x = 0.5?