Solution 3 Computational Intelligence Lab 2015

Problem 1 (Conditional Probability)

1. 3/4
2. 1/4
3. 1/2
4. 1/3 (we know one is a girl, so we're left with: girl girl, girl boy, boy girl. One out of these three is girl girl)
5. 1/3

Problem 2 (Bayes' Rule)

There is an uncommon disease that has infected 1% of the human population. Assume that we have a test for this disease that is positive on an infected person with probability 99% and negative on a healthy person also with probability 99%.

If my test comes out positive, what is the probability that I am infected?

Solution

$P[{\text{infected}}|{\text{positive}}]={\frac {P[{\text{positive}}|{\text{infected}}]\cdot P[{\text{infected}}]}{P[{\text{positive}}]}}={\frac {P[{\text{positive}}|{\text{infected}}]\cdot P[{\text{infected}}]}{P[{\text{infected}}]\cdot P[{\text{positive}}|{\text{infected}}]+P[{\text{not infected}}]\cdot P[{\text{positive}}|{\text{not infected}}]}}={\frac {0.01\cdot 0.99}{0.01\cdot 0.99+0.99\cdot 0.01}}={\frac {1}{2}}$

Problem 3 (K-means Theory)

2.

Show that the K-means algorithm solves a matrix factorisation problem by showing that $||\mathbf {X} -\mathbf {UZ} ||_{F}^{2}=\sum _{n=1}^{N}\sum _{k=1}^{K}z_{k,n}||\mathbf {x} _{n}-\mathbf {u} _{k}||_{2}^{2}$ where the matrices are defined as follows:

$\mathbf {X} =[\mathbf {x_{1}} \dots \mathbf {x_{N}} ]\in \mathbb {R} ^{D\times N}$

$\mathbf {U} =[\mathbf {u_{1}} \dots \mathbf {u_{K}} ]\in \mathbb {R} ^{D\times K}$

$\mathbf {Z} =[\mathbf {z_{1}} \dots \mathbf {z_{K}} ]\in \mathbb {R} ^{K\times N}$

Solution

$||\mathbf {X} -\mathbf {UZ} ||_{F}^{2}=\sum _{i=1}^{D}\sum _{j=1}^{N}\left(x_{ij}-(\mathbf {UZ} )_{ij}\right)^{2}$

$=\sum _{i=1}^{D}\sum _{j=1}^{N}\left(x_{ij}-\sum _{k=1}^{K}u_{ik}z_{kj}\right)^{2}$

$=\sum _{i=1}^{D}\sum _{j=1}^{N}\left(\sum _{k=1}^{K}x_{ij}z_{kj}-\sum _{k=1}^{K}u_{ik}z_{kj}\right)^{2}\qquad ({\text{since }}\sum _{k=1}^{K}z_{kj}=1)$

$=\sum _{i=1}^{D}\sum _{j=1}^{N}\left(\sum _{k=1}^{K}z_{kj}(x_{ij}-u_{ik})\right)^{2}$

$=\sum _{i=1}^{D}\sum _{j=1}^{N}\sum _{k=1}^{K}z_{kj}(x_{ij}-u_{ik})^{2}\qquad ({\text{since }}\forall k,j.\ z_{kj}\in \lbrace 0,1\rbrace {\text{ and }}\sum _{k=1}^{K}z_{kj}=1$

$=\sum _{j=1}^{N}\sum _{k=1}^{K}z_{kj}\sum _{i=1}^{D}(x_{ij}-u_{ik})^{2}$

$=\sum _{n=1}^{N}\sum _{k=1}^{K}z_{k,n}||\mathbf {x} _{n}-\mathbf {u} _{k}||_{2}^{2}\qquad \Box$