COMPSCI 527- Homework 1


Category: You will Instantly receive a download link for .zip solution file upon Payment


5/5 - (3 votes)

The exercises in this homework assignment cover basic material on probability corresponding to chapter 2 of the textbook. This
material has been briefly summarized in class, under the assumption that most of these concepts are familiar to you. If you have had
probability in previous classes, you may be able to complete this assignment without reading the book. However, please refer to the
textbook for notation, which may be different from what you have used in the past.
The difficulty of these problems varies, and I would expect you to take a few hours to complete the assignment. If it takes you
an inordinate amount of time and effort to do the exercises (especially 1–5), or if a large number of the concepts involved are entirely
foreign to you, you may want to reconsider taking this class.
Some questions require writing simple MATLAB code. Please intersperse concise comments with your code whenever useful, but do
not go overboard with comments. Try to use matrix notation whenever possible, so as to avoid explicit for loops over images. These
are very inefficient in MATLAB.
1. Compute the expected value of the fluctuation |X − m| from the mean m of a random variable X with uniform distribution between
0 and 1. Show your calculations. [Hint: The average fluctuation is not the standard deviation.]
2. Problem 2.4 from the book.
3. Problem 2.6 from the book. While this result is trivial to obtain, it gives a more intuitive meaning to the notion of statistical
independence: x and y are independent if the conditional distribution of x given y is the same as the unconditional distribution of x. In
other words, knowing y does not change the distribution of (does not change our information about) x. This of course goes both ways,
as the definition of independence is symmetric in x and y.
4. Problem 2.8 from the book.
5. Problem 2.10 from the book.
6. In this set of exercises, you will implement a few MATLAB functions to work on joint probability distributions of two discrete random
variables x and y. If x can assume m values ξ1, . . . , ξm and y can assume n values η1, . . . , ηn, we represent such a distribution with a
m × n matrix P of double numbers. Entry P(i, j) of this matrix is the probability that x equals ξi and y equals ηj . Of course, not
every matrix P represents a valid probability distribution.
(a) Write a MATLAB function isProbability that takes a matrix P as input and returns true if P represents a valid probability distribution and false otherwise. [Hint: The entries of P are represented in finite precision, so equalities can only hold
(b) Write the outputs from the following commands:
isProbability([0 1; 1 0])
isProbability([0 -0.2; 0.7 0.5])
isProbability([1 2 1; 3 0 1] / 8)
(c) Write a MATLAB function with header
function [Px, Py] = marginals(P)
that takes a matrix P that represents the joint probability distribution of x and y and computes the marginal probability distributions
of x and y. If P has size m × n, then Px is a column vector with m entries and Py is a row vector with n entries. For safety, your
code should check that the input represents a valid probability distribution, and generate an error otherwise. [Hint: Do not confuse
x and y with each other.]
(d) Write the outputs from the following commands:
P = = [0 1 2 1; 0 9 0 3] / 16;
[Px, Py] = marginals(P)
(e) Write a MATLAB function with header
function [Pxgy, Pygx] = conditionals(P)
whose input argument P represents the joint probability distribution of x and y. The function computes two matrices1 P(x|y) and
P(y|x) each the same size as P. Column j of P(x|y) is the conditional probability Pr(x | y = ηj ) for all x. Row i of P(y|x) is
the conditional probability Pr(y | x = ξi) for all y. Again, check that the input represents a valid probability distribution, and do
not confuse x with y.
There is a twist in this problem, in that the definition of conditional probability involves a division, and we need to avoid dividing
by zero. For instance, if we compute
p(x|y) = p(x, y)
for the matrix
p(x, y) =
0 0.2 0.3
0 0.4 0.1

we obtain the marginal distribution
p(y) =
0 0.6 0.4

so that the two entries of the conditional probability p(x|y = η1) are undefined (here, η1 is the first of two values that the random
variable y can take).
In situations like these, we fill the corresponding column with a uniform probability distribution. There are m entries in a column if
P is an m×n matrix, so the uniform distribution has value 1/m everywhere. The uniform distribution is said to be uninformative,
in the sense that it carries the minimum possible amount of information about a random variable: we have no preference for one
value of x over another, given that y = η1. So the resulting matrix in this example is as follows:
p(x|y) =
1/2 1/3 3/4
1/2 2/3 1/4

(the uniform distribution is shown in bold).
Similar considerations hold for the rows of p(y|x). In your code, it is easiest to write a subroutine that handles p(x|y) correctly, and
then use matrix transposition appropriately to call the same subroutine to compute p(y|x). Following this suggestion is optional,
but saves you time and effort.
(f) Write the outputs from the following command
[Pxgy, Pygx] = conditionals(P)
where P is the same matrix you used to test marginals.
(g) One way to write Bayes’s theorem is as follows:
Pr(y = ηj | x = ξi) = Pr(x = ξi
| y = ηj )Pr(y = ηj )
j Pr(x = ξi
| y = ηj )Pr(y = ηj )
In terms of the MATLAB matrices defined in earlier questions, this equality can be rewritten as follows:
Pygx(i, j) = Pxgy(i, j)Py(j)
Pxgy(i, :)Py
(if you remember what the entries of Pygx mean, you will realize that the order of i and j in Pygx(i, j) is not a typo). In the
expression above, Pxgy(i,:) is MATLAB notation to denote the i-the row of Pxgy.
The matrix that contains all the entries in the left-hand side of this equation is obviously Pygx. Write a MATLAB function
function Pygx = bayes(Pxgy, Py)
that computes the matrix Pxgy in terms of the matrices Pygx and Py. As before, both Pxgy and Pygx are m × n matrices and
Py is a row vector with n entries. Check for input argument validity in your code (careful!), and prevent division by zero similarly
to what you did for the function conditionals.
1You can read the MATLAB variable names Pxgy and Pygx corresponding to the mathematical symbols P(x|y) and P(y|x) as “probability of x given y” and
“probability of y given x.
(h) Evaluate the matrix Pygx with the function bayes you wrote as answer to the last question using the numerical values for Pygx
and Py obtained in your answers to questions (d) and (f) above. Compare the resulting matrix with the matrix Pxgy you obtained
in (f).
(i) How can you use your function bayes to compute p(x|y) from p(y|x) and p(x)? Just write the one line of code that does this,
assuming that p(x|y), p(y|x), p(x) correspond to MATLAB variables Pxgy, Pygx, Px.
7. The image yeast.png available with this assignment shows several yeast cells viewed through a Differential Interference Contrast
(DIC) microscope. Look at the image, either in MATLAB or in your favorite image viewer. Each cell is surrounded by a ring that is
darker than both cell and background. In addition, a halo that is brighter than both cell and background is often visible on the lower left
side of the cell. These are artifacts of the DIC imaging process, and we will call them the dark ring and the bright halo in this exercise.
A computer vision expert is asked to write software to segment images like yeast.png, that is, to create a binary mask image the
same size as the input image. A pixel in the mask image is true (or 1) if the same pixel in the input image is on the body of a cell, and
is false (or 0) otherwise. The expert’s first thought is to segment the image with a threshold, under the assumption that cell bodies are
either all brighter or all darker than the background. Pixels whose values in the input image are on one side of the threshold are set to
true and the others to false.
To test this and other ideas, the expert labels the yeast.png image by hand. That is, he manually draws the desired output mask
for this image using Adobe Photoshop. He then collects separate statistics of the pixel values in the cell bodies and in the background
of the original image, using the mask as a guide. More specifically, he obtains the conditional probability p(x|c) that a pixel has value
x given that it is in the cell, and the conditional probability p(x|b) that a pixel has value x given that it is in the background. In this and
other distributions in this exercise, pixel values are in the set {0, . . . , 255}. The image has size 1024 × 1024, and 58,299 pixels were
found to be on cell bodies.
(a) A pixel in yeast.png is either on a cell or in the background. What are the probabilities p(c) and p(b) that a pixel is on a cell
or on the background, respectively, as estimated from the image yeast.png? Use three significant (nonzero) decimal digits in
your answer.
(b) The conditional probabilities p(x|c) and p(x|b)found by the expert are contained in variables pxgc and pxgb in the file hw1.mat
available with this assignment. You can load this file in MATLAB with the command
load hw1
and the variables will then be defined in your MATLAB workspace. Plot the two conditional probabilities on the same diagram
using the MATLAB stairs function. Use different colors for the two plots, label the axes with values and meaning of the axes,
and add a legend on the graph that tells which plot is which. Hand in your plot (not the code you write to generate it). [Hint: The
MATLAB functions xlabel, ylabel, and legend and the command hold on are useful here. MATLAB has a very good
help facility to find out how to use these and other utilities (look for a question mark in the menu bar to start help).]
(c) Compute the conditional probabilities p(c|x) and p(b|x) that a pixel drawn at random from the image belongs to a cell or to the
background, given that the value of the pixel is x. These two functions of x are called the posterior probabilities of cell/background
given pixel value. Use the MATLAB stairs function to plot both p(c|x) and p(b|x) as functions of x on the same diagram and
in different colors. Show the code you wrote to compute the posteriors, and show your figure. As before, add meaningful axis
labels and legends. [Hint: You may want to use the bayes function you developed earlier, although this is not mandatory.]
(d) If you did things right, the two plots in your answer to the last question should be mirror images of each other. Why?
(e) The plots of p(c|x) and p(b|x) do not seem to reveal a natural place to put a threshold ξ such that all pixel values x that are on
one side of ξ are cells and all others are background. This is because the cell bodies have bright pixels (the bright halos, plus
some specs in the middle), dark pixels (the dark rings), and pixel values in-between. The pixel values in the background are in
the middle of the range of brightnesses, so there exists no single threshold on pixel values that can distinguish cell bodies from
Instead of putting the threshold on the pixel value x, we can instead define a threshold τ on p(c|x), so that pixels whose value x
satisfies p(c|x) > τ are declared to be cell pixels. What is the most natural value of τ , given the definition of p(c|x), and why?
(f) You have just come up with what is called the Bayes classifier for our segmentation problem. Try it on the image yeast.png
and show the resulting mask image. Avoid complicated and slow code with explicit for loops. As an example of “thinking in
MATLAB,” I’ll show you how to write this code. You may want to revisit some of your previous answers if you use explicit loops
in them. In the following code snippet, I assume that your image is in variable img, your posterior distribution p(c|x) is in variable
pcgx, and your threshold is in variable tau.
bayesCell = pcgx(img) > tau;
colormap gray
axis image
axis off
You can then use the MATLAB print command to save the result in your favorite file format.
(g) Comment on your result, which are inevitably far from perfect. In particular, what does the classifier flag as “cells”? Is this
satisfactory? Is it a good start? Are there ways to get much better results based on individual pixel values alone? Why or why not?
(h) In what way is the Bayes classifier more expressive than the classifier based on a single threshold on pixel value x? Another way
to ask this question is as follows: Describe the types of subsets of X = {0, . . . , 255} that each classifier can yield in principle, as
p(c|x) is suitably changed.