Description
Problem 1 From chapter 2 in TESL, the 2-dimensional dataset is created using the following procedure: 1. sample mi ∼ N([1, 0]0 , I) for i = 1, . . . , 5. 2. sample mi ∼ N([0, 1]0 , I) for i = 6, . . . , 10. 3. sample m from (m1, . . . , m10), each with probability 1/10 and sample xj ∼ N(m, I/5). 4. if m ∈ {m1, . . . , m5}, let xj ∈ {class 1} (otherwise xj ∈ {class 2}). (Note: save the subclass information (subclasses 1, . . . , 10). You will use this later.) 5. repeat steps 3 and 4 for j = 1, . . . , 100. Part a Simulate from the above procedure (Gaussian mixture model), and plot the data. Use 2 separate colors to denote the two classes. See Figure 1, the blue points belong to class 1, whereas the orange points belong to class 2. The red points are generated according to step 1 and step 2. The python code for this part can be found in Appendix I. 1 Part b Use the least squares method to classify the data. Show a plot denoting your linear separating boundary. State both false positive and false negative rates. The least squares method gives βb = (X 0X) −1X 0 Y . Then we categorize points satisfying Xβ b 0.5 into class 2. The separating boundary can be found in Figure 1. The false positive rate by this classifier is 0.066667, whereas the false negative rate is 0.109091. The python code for this part can also be found in Appendix I. Figure 1: Simulated data points and the classification results by the least squares methods. Problem 2 Given knowledge of all the parameters in the model ({m1, . . . m10}), the mixture weights (1/10 for each subclass), and the covariance functions, derive the optimal separating boundary. With the given information, we can build a Bayesian classifier. The optimal separating boundary can be derived as follows: P r(cj |x, mj ) ∝ P(x|mj , cj )P r(cj ), P r(cj ) = 1 10 (1) P r(cj |x, mj ) ∝ P(x|mj , cj ) (2) For superclass 1 and superclass 2, since the subclasses and mutually exclusive, we have: 2 P r(C1|x) = X 5 j=1 P r(cj |x, mj ) ∝ X 5 j=1 P(x|mj , cj ) (3) P r(C2|x) = X 10 j=6 P r(cj |x, mj ) ∝ X 10 j=6 P(x|mj , cj ) (4) To derive the separating boundary of superclass C1 and C2, we need to set P r(C1|x) = P r(C2|x). Equivalently, we should set P5 j=1 P(x|mj , cj ) = P10 j=6 P(x|mj , cj ). More explicitly, we need the following condition for setting up the separating boundary: X 5 j=1 e − 5 2 k −→x − −→mj k 2 = X 10 j=6 e − 5 2 k −→x − −→mj k 2 (5) Thus, Eq.(6) gives optimal separating boundary. Problem 3 Show a plot denoting this boundary. (Note: This may look a little different than what is in the book since your {m1, . . . m10} are different from what they’ve simulated). State both false positive and false negative rates. Figure 2: Bayesian classification and the corresponding separating boundary. Figure 2 shows a plot of the result of Bayesian classification. The false positive rate is 0.094340, whereas the false negative rate is 0.085106. The python code for this part can also be found in Appendix II. 3 Problem 4 If you aren’t given knowledge of the mis, but are given the subclass labels, show how to construct the separating boundary. (Note: many methods exist, and some are better than others. You may use any method you deem reasonable). Show a plot of your results, and state both false positive and false negative rates. Figure 3: KNN classification with uniform weight and its separating boundary. If the values of mj ’s are not given, we can estimate the values of mj ’s. One reasonable way to estimate mj is to take the average of the locations of all data points that belong to the subclass Cj . That is, calculate mcj = (¯xc=cj , y¯c=cj ), and plug mcj back into the Eq.(6) for further calculation. Here in Figure 3 the white diamonds are true locations of the mj ’s (not used for classification in Problem 4) and the red dots are the locations of the mcj . The false positive rate is 0.088889, the false negative rate is 0.054545. Problem 5 If you weren’t provided the {m1, . . . m10} and subclass labels, but were given the superclass labels (class 1,2), what would you do? You don’t have to derive anything, or code anything up. Simply describe in plain english. With only superclass labels, we can use the K-Nearest Neighbor (KNN) method to do the classification. The implementation of KNN is as follows, we first create a fine mesh grid, then each point of the mesh grid is classified by a majority vote of its (k nearest) neighbors’ superclass labels. After each point on the mesh grid is classified, we will have a good idea where the separating boundary is. A plot of the 4 KNN algorithm with uniform weight of votes can be found in Figure 4. A plot of the KNN algorithm with weight 1/di of vote can be found in Figure 5. (di is the distance from the point in question and its i th neighbor, where i = 1, 2, …, k.) Figure 4: KNN classification with uniform weight and its separating boundary. Figure 5: KNN classification with distance weight and its separating boundary. The performance analysis for both classifiers show: with the KNN classifier with uniform weight the false positive rate is 0.0888889 and the false negative rte is 0.90901; with the KNN classifier with uniform weight the false positive rate is 0 and the false negative rate is also 0. 5