Problem 1. Let p(x|wi) ∼ N (µi, σ2) for a two-category one-dimensional problem with P (ω1) = P (ω2) = 2
Show that the minimum probability of error is given by where a = |µ1 −µ2 | .
Pe = √2π
Pe = √2πe−t /2 1dt ≤ √2πae−a /2
show that Pe goes to zero as |µ1 −µ2 | goes to infinity.
Problem 2. Consider a two-category classification problem in two dimensions with(x|ω1) ∼ N (0, I), p(x|ω2) ∼ N (.1Σ , I)and P (ω1) = P (ω2) = 1 ,
Problem 3. Suppose that we have three categories in two dimensions with the following underlying distributions:
p(x ω ) ( 1 , I) 1
Problem 4. Consider two normal distributions with arbitrary but equal covariances. Prove that the Fisher linear discriminant, for suitable threshold, can be derived from the negative of the log-likelihood ratio
Problem 5. It is easy to see that the nearest-neighbor error rate P can equal the Bayes rate P ∗ if P ∗ = 0 (the best possibility) or if P ∗ = c−1 (the worst possibility). One might ask whether or not there are problems for which P = P ∗ when P ∗ is between these extremes.
Problem 6. Prove that the computational complexity of the basic nearest-neighbor editing algorithm for
n points in d dimension is O(d3n| d ∫ ln n).
Nearest-Neighbor Editing Algorithm
1: begin initialize j 0, data set, n #prototypes
2: construct the full Voronoi diagram of 3: do j j + 1, for each prototype x³ j 4: find the Voronoi neighbors of x³ j
5: if any neighbor is not from the same class as x³ j , then mark x³ j
6: until j = n
7: discard all points that are not marked
8: construct the Voronoi diagram of the remaining (marked) prototypes
Problem 7. Consider classifiers based on samples with priors P (ω1) = P (ω2) = 0.5 and the distributions
p(x|ω ) = .2x, 0 ≤ x ≤ 1
p(x|ω ) = .2 − 2x, 0 ≤ x ≤ 1
Pn(e) = 3 + (n + 1)(n + 3) + 2(n + 2)(n + 3)
Confirm this formula makes sense in the n = 1 case.
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t
Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of