ML - 10 Unsupervised Learning

Basic Idea

지금까지는 dataset에 항상 정답이 표기되어 있었다. 그러나 실생활에서는 일일이 정답을 표기하기 어려운 경우가 많다.

Unsupervised Learning은 정답이 없는 dataset에서 패턴을 찾아내는 방법이다.

K-Means Clustering

입력 데이터셋에서 $k$개의 cluster로 데이터를 나누는 방법이다.

Input: $x_1, x_2, \ldots, x_n$ (dataset), $k$ (number of clusters)
Output: $c_1, c_2, \ldots, c_k$ (cluster centers)

\[\begin{aligned} &\textbf{Algorithm 1: k-means-Clustering}(k, x^{(1)}, \cdots, x^{(n)}) \\[0.4em] &\begin{array}{r@{\quad}l} 1 & \text{Initialize cluster centroids } \mu_1, \mu_2, \cdots, \mu_k \in \mathbb{R}^d \text{ randomly} \\ 2 & \textbf{while } \text{Until Convergence} \textbf{ do} \\ 3 & \qquad \textbf{for } i = 1 \textbf{ to } k \textbf{ do} \\ 4 & \qquad\qquad c^{(i)} := \arg\min_j \left\| x^{(i)} - \mu_j \right\|^2 \\ 5 & \qquad \textbf{for } j = 1 \textbf{ to } k \textbf{ do} \\ 6 & \qquad\qquad \mu_j := \frac{\sum_{i=1}^{n} \mathbf{1}\{c^{(i)} = j\}x^{(i)}} {\sum_{i=1}^{n} \mathbf{1}\{c^{(i)} = j\}} \end{array} \end{aligned}\]

1. $x_i$를 가까운 cluster center $\mu_j$에 할당
2. 각 cluster에 모인 데이터의 평균을 계산하여 cluster center $\mu_j$ 업데이트

1,2를 반복하면 비슷한 데이터끼리 모이는 cluster가 형성된다.

Theorem: k-means 알고리즘은 수렴한다. (즉, cluster center가 더 이상 변하지 않게 된다.)

\[J(c, \mu) = \sum_{i=1}^{n} \left\| x^{(i)} - \mu_{c^{(i)}} \right\|^2\]

위처럼 cost function $J$를 정의하면, k-means 알고리즘은 $J$를 감소시키는 방향으로 작동한다. 정확히는 첫번째 loop에서는 $\mu$가 고정된 상태에서 $c$를 업데이트하여 $J$를 감소시키고, 두번째 loop에서는 $c$가 고정된 상태에서 $\mu$를 업데이트하여 $J$를 감소시킨다. 따라서 k-means 알고리즘은 cost function $J$가 더 이상 감소하지 않을 때까지 반복하므로 수렴한다.

Expectation-Maximization (EM) Algorithm

EM 알고리즘은 Expect step과 Maximize step으로 이루어진 반복적인 최적화 알고리즘이다.

1. Expectation step: 숨어있는 변수 $z^{(i)}$를 추정한다.
2. Maximize step: 모델의 파라미터를 업데이트한다.

1, 2를 반복하면서 모델의 파라미터가 수렴할 때까지 진행한다. 이후 어떠한 data가 관측되면 EM 알고리즘은 그 점이 어떤 cluster에 속하는지 확률적으로 추정할 수 있다.

Mixture of Gaussians

EM 알고리즘의 대표적인 예시로 Mixture of Gaussians 모델이 있다.

먼저 unlabeled dataset $x_1, x_2, \ldots, x_n$이 있다고 하자. 이 detaset은 $k$개의 Gaussian distribution이 섞여서 만들어졌다고 가정하자. 즉,

\[z^{(i)} \sim \text{Multinomial}(\phi)\] \[x^{(i)} | z^{(i)} = j \sim \mathcal{N}(\mu_j, \Sigma_j)\]

// TODO