1.  This question concerns probability theory.

a)     The discrete random variable X represents the outcome of a biased coin toss.  X has the probability distribution given in the table below,

where H represents a head and T represents a tail.

(i)    Write an expression in terms of θ for the probability of observing the sequence

H, T, H, H.                                                                                                                           [5%]

(ii)    A sequence of coin tosses is observed that happens to contain NH  heads and

NT  tails.  Write an expression in terms of θ for the probability of observing this speciic sequence.                        [5%]

(iii)    Show that having observed a sequence of coin tosses containing NH  heads and NT tails, the maximum likelihood estimate of the parameter θ is given by

NH

NH + NT

[20%]

c)      Consider the distribution sketched int the igure below.

2λ                          

p(x)

0

b

x

1

  2λ   if 0 <= x < b

p(x) =〈  λ     if b <= x <= 1

( 0     otherwise

(i)    Write an expression for λ in terms of the parameter b.                                        [15%]

(ii)    Two independent samples, x1  and x2 , are observed. x1  has the value 0.25 and

x2  has the value 0.75. Sketch p(x1 ,x2 ; b) as a function of bas b varies between

0 and 1.  Using your sketch, calculate the maximum likelihood estimate of the parameter b given the observed samples.                            [20%]

(v)    Compute the inverse covariance matrix, Σ — 1 . [15%]

(iii)    Using the igure above estimate the  mean-centred range of ape  indexes that would include 99% of the population.                      [5%]

3.  This question concerns classiiers.

a)     Consider a Bayesian classiication system based on a pair of univariate normal distribu- tions.  The distributions have equal variance and equal priors.  The mean of class 1 is less than the mean of class 2. For each case below say whether the decision threshold increases, decreases, remains unchanged or can move in either direction.

(i)    The mean of class 2 is increased.                                                                                 [5%]

(ii)    The mean of class 1 and class 2 are decreased by equal amounts.                    [5%]

(iii)    The prior probability of class 2 is increased.                                                               [5%]

(iv)    The variance of class 1 and class 2 are increased by equal amounts.                [5%]

(v)    The variance of class 2 is increased.                                                                           [5%]

b)     Consider a Bayesian classiication system based on a pair of 2-D multivariate normal distributions, p(x| ω1 ) ~ N(μ1 , Σ1 ) and p(x| ω2 ) ~ N(μ2 , Σ2 ) .  The distributions have the following parameters

μ1 = (2(1) )     μ2 = (5(3) )     Σ1 = Σ2 = ( 0(1)   1(0) )

The classes have equal priors, i.e., P(ω1 ) = P(ω2 ).

Calculate the equation for the decision boundary in the form x2 = mx1 + c. [25%]

c)     Consider a K nearest neighbour classiier being used to classify 1-D data belonging to classes ω1 and ω2. The training samples for the two classes are

ω 1 = {1, 3, 5, 7, 9}      ω2 = {2, 4, 6, 8}

The diagram below shows the decision boundaries and class labels for the case K = 1.

Make similar sketches for the cases K = 3, K = 5, K = 7 and K = 9.                         [25%]

d)     Consider a K-nearest neighbour that uses a Euclidean distance measure, K = 1, and the following samples as training data,

ω 1     =   {(0, 1)T , (1, 1)T , (1, 2)T }

ω2     =   {(1, 0)T , (2, 1)T }

A point is selected uniformly at random from the region deined by 0 ≤x1 ≤2, 0 ≤x2 ≤2.

What is the probability that the point is classiied as belonging to class ω1 ?  [Hint: start by sketching the decision boundary.] [25%]

a)     The points in the above igure are to be clustered using the agglomerative clustering algorithm.  The cluster-to-cluster distance is deined to be the minimum point-to-point distance. In the initial clustering, C0 , each point is in a separate cluster and the clustering can be presented as a set of sets as such.

C0 = {{A}, {B}, {C}, {D}, {E}, {F}, {G}, {H} }

(i)    Point-to-point distances are measured using the Manhattan distance.  Perform the algorithm and use set notation to show the clustering after each iteration. [10%] 

(ii)    Point-to-point distances are measured using the Euclidean distance. Perform the algorithm and use set notation to show the clustering after each iteration.        [10%]

(iii)    Draw a dendogram to represent the hierarchical sequence of clusterings found when using the Euclidean distance.                                       [10%]

(iv)    Consider a naive implementation of the algorithm which does not store point-

to-point distance measures across iterations.  Calculate the precise number of

point-to-point distances that would need to be computed for each iteration when performing the clustering described in 4 (a)(ii).                                                        [20%]

b)      Consider the following dimensionality reduction techniques

.     Discrete Cosine Transform (DCT),

.     Principal Coponent Analysis (PCA) transform and

.     Linear Discriminant Analysis (LDA) transform.

They can all be expressed as a linear transform of the form Y = XM where M is the transform and X is the data matrix and Y is the data matrix after dimensionality reduc- tion.

(i)    Copy the table below and ill the cells with either ‘Yes’ or ‘No’ to indicate what information is required in order to determine M.

[15%]

(ii)    PCA is being used to reduce the dimensionality of a 1000 sample set from 50

dimensions down to 5.  State the number of rows and columns in each of Y , X and M in the equation Y = XM that performs the dimensionality reduction.    [15%]

(iii)    Dimensionality reduction is to be used to reduce two dimensional data to one dimension.   Draw  a scatter plot for a two class problem  in which  PCA would perform very badly but for which LDA would work well. [20%]