(카이스트 강의) K-means, Gaussian Mixture Model

#머신러닝의 종류

1) 지도학습

2) 비 지도학습

3) 강화학습

# 비 지도학습 특징

- true value가 무엇인지 모른다.

#clustering의 문제

- 문제 : 여러 case들이 있는데, 그 case가 어떤 군집에 속하는지 명확하게 판단하기

힘든 경우가 있음 

- 해결 방법 : K-Means 알고리즘

# K-means 알고리즘

- 정의 : N개의 case들이 있을 때, K개의 추정되는 값들(Means, 평균값)을 구해내는 

          알고리즘.

- 순서 :

   1) K 개의 추정되는 값들을 정한다 (centroids)

   2) 모든 case들에 대해, 자신과 가까운 centroid를 선정해서 clustering 한다

-> 이 내용을 수식으로 나타낼 수 있다

# Expectation and Maximization

- 순서 : 

      1) Expectation

- 주어진 parameter를 통해 log-likehood 기댓값을 구한다

- R_nk를 optimize 해주는 과정

** R_ij :  i번째 데이터값이 j번째 centroid에 할당이 되어 있으면 1, 할당이

           되어있지 않으면 0 으로 갱신되는 변수.

      2) Maximization

- 여러 parameters 의 maximization (log-likehood에 따라)

- 알게 된 R_nk를 통해, centroid 의 위치를 갱신한다

      3) 1,2번 과정을 반복

- μ_k 값 구하기 : 이의 expectation-maximization 의 식을 미분해준다 

-> 미분값=0 이 되도록 하는 μ_k 값을 구해서 사용해준다

- 한계점 :

      1) 몇 개의 군집(centroid) 으로 이뤄져있는지 불분명

      2) 초기 centroid의 위치를 어떻게 임의로 잡을것인가?

      3) 유클리드 거리는 너무 제한적인 정보다 (더 많은 정보가 필요)

      4) 반드시 어떤 데이터가 특정 centroid에"만" 속하는게 아닐수도 있음.  

(ex. 빨강팀일 확률이 0.6, 파란팀일 확률이 0.4)

-> 3, 4번의 해결책 : Gaussian Mixture Model

# Multinomial Distribution

      - Binary variable 의 경우, 맞으면 y=1, 틀리면 y=0 같이, 딱 두 개의 값만 가질 수 있음

        Multinomial 의 경우, 가능한 option 의 갯수를 늘리자는 취지임

      - 방법 : k 개의 option 이 있다고 할 떄, k개의 binary variable을 설정해서 표현하자

(ex. x = {0,0,0,1,0,0}  -> 6개의 option을 표현하고 있음 with binary variable)

-> 더 나아가서, 이렇게 구한 값을 계산하기 위해선 MLE 를 사용해야 한다

      - MLE 를 구하기 위해서, 함수식을 maximize 해야한다

        이때, "제약조건"이 있다는게 엄청 거슬린다? 

-> 라그랑주 method 를 활용하자!

- 라그랑주 method :

      1) 라그랑주 상수(λ)를 도입한 라그랑주 함수식을 만든다

      2) 미분을 취해준다 -> 미분값=0 이 되는 μ 값을 구한다

      3) λ의 값을 구하기 위해 계산해준다 -> λ=N (데이터의 총 갯수) 임을 알 수 있다

      4) 이로 인해 생겨난 마지막 결괏값을 MLE를 활용하여 구하면, Multinomial Distribution을 완성할 수 있다

       - Multivariate Gaussian Distribution

- 우리가 일반적으로 알고 있는 정규분포식을 다차원으로 확대시킨 것.

       - Mixture model

- Mixture model 기본 꼴 : 

        - 히스토그램을 봤을때, n 개의 봉우리가 있다?

        - 이 봉우리들은 분명, 동일한 Normal Distribution으로부터 나온게 아닐것이다!

        - 각각 다른 Distribution Model이라고 생각하고 관찰하자!

- Mixture model 의 수학적 표현 :

        - π_k 값 : multinomial distribution 을 활용한다. 

         k번째 Gaussian Distribution이 선택될 확률 의미

-> "mixture coefficient"

-> MLE 과정으로 구할 수 없음!! 반드시 EM (expectation maximization)과정으로만 구할수 있음

        - N 그래프 : multivariate distribution 을 활용한다 

-> "mixture component"

# Expectation of GMM (=Gaussian mixture model)

       - K-means algo 와의 공통점

1) 두 개의 상응하는 parameter가 있다

      - r_nk = π_k

      - centroid와의 거리 공식 = N( x | μ, φ)

2) 둘다 EM algo를 사용한다 

      ** 단, 차이점이라고 한다면, K-means에서는 hard assignment였으나 (0또는 1)

          GMM에서는 soft assignment를 사용한다 (함숫값으로 변형해서 표현함)

       - 특징

1) Expectation Step 에서 : soft assignment를 사용하기 떄문에, "확률"적으로 배치시킬 수 있다

** k-means에서는 확률적으로 배치시킨다기보단, 그냥 거리를 이용해서 배치시킨것 (비확률적임)

2) supervised 연산임. x, μ, π 값들이 전부 미리 주어져있다고 생각하고, 학습을 한다

       - Maximization 방식 : 

1) log 화 해준다

2) 각 변수들에 대한 편미분을 해준다 -> 라그랑주 method 사용하기!!! (why? 제약조건이 있음)

3) 미분값 = 0 이 되는 지점에서 max 값을 구한다

# GMM 의 장단점

       - 장점 

1) 더 많은 정보들을 얻을 수 있다 : 각각의 데이터들이 서로 어떤 관계에 놓여져있는지

        알 수 있다

2) soft clustering 을 활용한다 : 더 많은 정보를 얻을 수 있다.

       - 단점

1) 계산이 오래걸린다

2) local maximum에 빠질 수 있다

-> EM 알고리즘을 쓰기 떄문에 어쩔 수 없음

3) K 값을 결정하기가 힘들다 (몇 개의 category로 구성되어있는지 알 수 없다)

-> 이건 K-means 에서도 마찬가지

       - 단점 보완 방식 : 해결 방안이 있다. 몇 가지 추가사항을 넣으면 해결 가능(3번 특히)

# GMM 과 K-means의 유사점

       - 조건만 추가한 것일 뿐, 둘은 거의 똑같다

       - GMM 에다가 극한의 조건(상황) 을 적용하면, K-means 모양으로 변한다

- soft assignment -> hard assignment 형식으로 변환됨

# Latent Variable (Z값) 의 등장에 따른 차이점

       - Classification  vs  Clustering

1) Classification : Z 값이 없을때

     - marginalize 과정 없이, 곧바로 확률값이 산출되면서 계산이 가능함

2) Clustering : Z 값이 있을때

      - 이 값을 구하기 위해선, marginalization 과정이 필요하다

      - 그러나 이 marginalization 과정떄문에, log 계산에서 어려움이 생긴다

-> 이젠, Z와 Θ 를 iterative 하게 optimize 해야한다!!!!!

-> 서로간에 interaction이 발생한다!!!

        - log 계산 문제 해결 방안 : Probability Decomposition

- Jensen's Inequality 속성을 이용한다 : 볼록함수의 경우, f((x1+x2)/2) < (f(x1)+f(x2))/2

- 이걸 이용한다면, log 계산을 부등식꼴로 쪼개서 사용이 가능하다

      how? Lower Bound 를 maximize 해주자  (데과기때 배웠던 내용 떠올리기)