Homework Set OneECE 271ADepartment of Computer and Electrical EngineeringUniversity of California, San DiegoNuno Vasconcelos Fall 2007Due October 11, 2007The purpose of this assignment is to give you experience with Bayesian decision theory. The firstfour problems are of the pen-and-paper type, while problem 5 is a computer problem. Some of theproblems simply require the straightforward application of the principles covered in class. These areintended to give you some practice on the Bayesian manipulations that are usually involved in decisiontheory. Others involve somewhat deeper thinking and extend in some way what we have seen in class.The problems are not ordered by difficulty.1. In this problem we will consider the traditional probability scenario of coin tossing. However, wewill consider two variations. First, the coin is not fair. Denoting by S the outcome of the coin toss wehavePS(heads)=α, α ∈ [0, 1].Second, you do not observe the coin directly but have to rely on a friend that reports the outcome ofthe toss. Unfortunately your friend is unreliable, he will sometimes report heads when the outcome wastails and vice-versa. Denoting the report by R we havePR|S(tails|heads)=θ1(1)PR|S(heads|tails)=θ2(2)where θ1,θ2∈ [0, 1]. Your job is to, given the report from your friend, guess the outcome of the toss.a) Given that your friend reports heads, what is the optimal decision function in the minimum proba-bility of error sense. That is, when should you guess heads, and when should you guess tails?b) Consider the case θ1= θ2. Can you give an intuitive interpretation to the rule derived in a)?c) You figured out that if you ask your friend to report the outcome of the toss various times, he willproduce reports that are statistically independent. You then decide to ask him to report the outcomen times, in the hope that this will reduce the uncertainty. (Note: there is still only one coin toss, butthe outcome gets reported n times). What is the new minimum probability of error decision rule?d) Consider the case θ1= θ2and assume that the report sequence is all heads. Can you give an intuitiveinterpretation to the rule derived in c)?2. Problem 2.2.2 in DHS.3. Problem 2.5.23 in DHS (feel free to use MATLABheretocomputeeigenvalues, matrix vectorproducts, and so forth. The goal is not evaluate your mastery of the mechanics of linear algebra, butto give you an intuitive understanding of what whitening is).14. Problem 2.9.43 in DHS5. (computer) This is the first in a series of computer problems where we will get a feel for thedifficulty of practical pattern recognition problems, such as computer vision. The goal is to segmentthe “cheetah” image (shown below in the left) into its two components, cheetah (foreground) and grass(background).To formulate this as a pattern recognition problem, we need to decide on an observation space. Herewe will be using the space of 8 × 8 image blocks, i.e. we view each image as a collection of 8 × 8blocks.For each block we compute the discrete cosine transform (function dct2 on MATLAB) and obtainan array of 8 × 8 frequency coefficients. We do this because the cheetah and the grass have differenttextures, with different frequency decompositions and the two classes should be better separated in thefrequency domain. We then convert each 8 × 8 array into a 64 dimensional vector because it is easierto work with vectors than with arrays. The file Zig-Zag Pattern.txt contains the position (in the 1Dvector) of each coefficient in the 8 × 8 array. The file TrainingSamplesDCT8.mat contains a trainingset of vectors obtained from a similar image (stored as a matrix, each row is a training vector) for eachof the classes. There are two matrices, TrainsampleDCTBG and TrainsampleDCT FG for foregroundand background samples respectively.To make the task of estimating the class conditional densities easier, we are going to reduce eachvector to a scalar. For this, for each vector, we compute the index (position within the vector) of thecoefficient that has the 2ndlargest energy value (absolute value). This is our observation or feature X.(The reason we do not use the coefficient with the largest energy is that it is always the so-called “DC”coefficient, which contains the mean of the block). By building an histogram of these indexes we obtainthe class-conditionals for the two classes PX|Y(x|cheetah)andPX|Y(x|grass). The priors PY(cheetah)and PY(grass) should also be estimated from the training set.a) using the training data in TrainingSamplesDCT8.mat, what are reasonable estimates for the priorprobabilities?b) using the training data in TrainingSamplesDCT8.mat, compute and plot the index histogramsPX|Y(x|cheetah)andPX|Y(x|grass).c) for each block in the image cheetah.bmp, compute the feature X (index of the DCT coefficient with2ndgreatest energy). Compute the state variable Y using the minimum probability of error rule basedon the probabilities obtained in a) and b). Store the state in an array A. Using the commands imagescand colormap(gray(255)) create a picture of that array.d) The array A contains a mask that indicates which blocks contain grass and which contain thecheetah. Compare it with the ground truth provided in image cheetahmask.bmp (shown below on theright) and compute the probability of error of your algorithm.Notes:• in TrainingSamplesDCT8.mat each matrix row contains the “zig-zag scanned” vector of coeffi-cients. So, for a) and b) you do not need to compute the DCT, etc.• the training data that we provide was created by representing images as doubles in the range [0, 1].You need to represent the image in the same way, in order to have consistency between the trainand test sets. This can be done by using the commands im2double(img) or double(img)/255on MATLAB (where img is the array that contains the image as read from cheetah.bmp).2• in Zig-Zag Pattern.txt the zig-zag pattern goes from 0 to 63, not 1 to 64. Please rememberthis as MATLAB starts indexes from 1. (You can just add 1 to the numbers in the file to get tothe MATLAB coordinates).50 100 150 200 2505010015020025050 100 150 200