Unsupervised Learning

Question 1

(a) [8]

• (i) Fixed $\mu_k$: $J$ decouples per point $i$; minimizing $\sum_k r_{ik}\lVert x_i-\mu_k\rVert^2$ subject to one-hot $r_i$ picks $k^*=\arg\min_k\lVert x_i-\mu_k\rVert^2$. (2) Hence nearest-centroid assignment is optimal. (1)
• (ii) Fixed assignments: $\partial J/\partial\mu_k = -2\sum_i r_{ik}(x_i-\mu_k)=0 \Rightarrow \mu_k=\frac{\sum_i r_{ik}x_i}{\sum_i r_{ik}}$, the cluster mean. (3) Second derivative $2\sum_i r_{ik}>0$ ⇒ minimum. (1)
• Each step is exact minimization over one block ⇒ $J$ non-increasing; $J\ge0$ bounded below and finite number of assignment configurations ⇒ convergence in finite steps. (1)

(b) [6]

• Iter 1 assign: distances to $\mu_1=-3,\mu_2=-1$. $-3\to\mu_1;\ -1\to\mu_2;\ 1\to\mu_2$ (dist 4<2? no: |1-(-3)|=4,|1-(-1)|=2 →$\mu_2$); $3\to\mu_2$ (|3+3|=6,|3+1|=4). Clusters: $\{-3\},\{-1,1,3\}$. (2)
• Update: $\mu_1=-3,\ \mu_2=(-1+1+3)/3=1$. (1)
• Iter 2 assign: $\mu_1=-3,\mu_2=1$. $-3\to\mu_1$; $-1$: |−1+3|=2,|−1−1|=2 tie → assign $\mu_1$ (or $\mu_2$); resolving to nearest with tie-break to lower index: $-1\to\mu_1$; $1\to\mu_2$;$3\to\mu_2$. Clusters $\{-3,-1\},\{1,3\}$. (1)
• Update: $\mu_1=-2,\ \mu_2=2$. Reassign confirms stable. Final centroids $-2,2$. (1)
• $J=(-3+2)^2+(-1+2)^2+(1-2)^2+(3-2)^2=1+1+1+1=4$. (1)

(c) [6]

• Mean $=0$; variance $=\frac{1}{4}(9+1+1+9)=5$. (2)
• Single feature ⇒ PC1 explains 100% of variance, ratio $=1$. (2)
• Spectral relaxation: relaxing the discrete cluster indicator to be real-valued and orthogonal to $\mathbf 1$, the optimal continuous solution maximizing between-cluster variance is the top eigenvector of the (centered) covariance/Gram matrix = PC1. Sign of PC1 projection then gives a natural 2-cluster split; thus PCA relaxes the NP-hard K-Means assignment. (2)

(d) [4]

• Non-convex / concentric-ring (or two-moons) geometry. (2) K-Means minimizes squared distance to a single centroid ⇒ assumes convex isotropic (spherical) clusters and will slice rings incorrectly; DBSCAN groups by density-connectivity so it follows arbitrary shapes and labels sparse points as noise. (2)

Question 2

(a) [8]

• Complete-data LL: $\log\prod_i\prod_k[\pi_k\mathcal N(x_i|\mu_k,\Sigma_k)]^{z_{ik}}=\sum_i\sum_k z_{ik}[\log\pi_k+\log\mathcal N(\cdots)]$. (2)
• E-step: $\gamma_{ik}=E[z_{ik}]=P(z_{ik}=1|x_i)=$ posterior via Bayes = stated formula. (2)
• M-step $\mu_k$: maximize $Q=\sum_i\gamma_{ik}\log\mathcal N$; $\partial/\partial\mu_k$ of $-\tfrac12(x_i-\mu_k)^T\Sigma_k^{-1}(x_i-\mu_k)$ gives $\sum_i\gamma_{ik}\Sigma_k^{-1}(x_i-\mu_k)=0\Rightarrow \mu_k=\frac{\sum_i\gamma_{ik}x_i}{\sum_i\gamma_{ik}}$. (4)

(b) [8]

• With $\Sigma=\sigma^2 I$, equal $\pi$: $\gamma_{ik}=\frac{\exp(-\lVert x_i-\mu_k\rVert^2/2\sigma^2)}{\sum_j\exp(-\lVert x_i-\mu_j\rVert^2/2\sigma^2)}$. (3) As $\sigma\to0$ the softmax sharpens: the term with smallest $\lVert x_i-\mu_k\rVert^2$ dominates → $\gamma_{ik}\to1$ for nearest centroid, 0 else = hard assignment = K-Means. (3) Analogy: $\sigma^2 \leftrightarrow$ temperature $T$; $\sigma\to0$ is the zero-temperature limit where the Boltzmann/softmax distribution collapses to the ground state (nearest centroid). (2)

(c) [6]

• $\mathcal N(1|0,1)\propto e^{-1/2}$, $\mathcal N(1|2,1)\propto e^{-1/2}$ (both distance 1). (3) Equal priors ⇒ $\gamma_{i1}=\frac{e^{-1/2}}{e^{-1/2}+e^{-1/2}}=0.5$. (3)

Question 3

(a) [7]

DBSCAN(D, eps, minPts):
  label = {} (undefined for all)
  C = 0
  for p in D:
    if label[p] defined: continue
    N = rangeQuery(D, p, eps)      # neighbors within eps (incl p)
    if |N| < minPts:
      label[p] = NOISE; continue    # may become border later
    C += 1; label[p] = C
    Seed = N \ {p}
    while Seed not empty:
      q = Seed.pop()
      if label[q]==NOISE: label[q]=C   # border point
      if label[q] defined: continue
      label[q]=C
      Nq = rangeQuery(D,q,eps)
      if |Nq| >= minPts: Seed += Nq    # q is core, expand
  return label

• Core: $\ge$ minPts neighbors in $\varepsilon$. Border: non-core but in a core's neighborhood. Noise: neither. (3 correctness, 2 core/border/noise distinction)
• Complexity: $O(n^2)$ naive; $O(n\log n)$ with a spatial index (kd-tree/ball-tree) for low dimensions. (2)

(b) [4]

• $\varepsilon=1.5$, neighbors: 1↔2, 2↔3, 3↔2 → each of 1,2,3 has ≥2 pts incl self ⇒ all core; cluster A={1,2,3}. (1.5)
• 10↔11 within 1.5 ⇒ each core; cluster B={10,11}. (1.5)
• 50 isolated ⇒ noise. (1)

(c) [3]

• Two elongated (non-spherical) bands ⇒ a single Gaussian per band mismatches shape and a global Gaussian anomaly detector flags band tails as anomalies. DBSCAN (density) captures arbitrary band shapes and cleanly labels scattered points as noise/outliers ⇒ more appropriate. (3)

[
  {"claim":"Q1b final J = 4 with centroids -2,2","code":"pts=[-3,-1,1,3]; c1=[-3,-1]; c2=[1,3]; m1=sum(c1)/2; m2=sum(c2)/2; J=sum((x-m1)**2 for x in c1)+sum((x-m2)**2 for x in c2); result = (m1==-2 and m2==2 and J==4)"},
  {"claim":"Q1c variance (divisor n) = 5","code":"x=[-3,-1,1,3]; n=len(x); mu=sum(x)/n; var=sum((xi-mu)**2 for xi in x)/n; result = (var==5)"},
  {"claim":"Q2c responsibility gamma=0.5 for x=1","code":"import sympy as sp; f=lambda x,mu: sp.exp(-(x-mu)**2/2); g=f(1,0)/(f(1,0)+f(1,2)); result = (sp.simplify(g)==sp.Rational(1,2))"},
  {"claim":"Q3b cluster A={1,2,3} all core with eps=1.5 minPts=2","code":"P=[1,2,3,10,11,50]; eps=1.5; A=[p for p in P if abs(p-1)<=eps or abs(p-2)<=eps or abs(p-3)<=eps]; core1=len([q for q in P if abs(q-1)<=eps])>=2; core2=len([q for q in P if abs(q-2)<=eps])>=2; result = (core1 and core2 and set([1,2,3]).issubset(set(A)))"}
]