케빈 머피의 Machine Learning 책을 보고 정리한 내용들입니다.

1.1 Machine Learning: what and why?

현재 우리는 빅데이터 시대에 살고 있으며, 수많은 양의 정보들을 마주하고 있다. 이러한 데이터들을 분석하기 위해 자동화된 데이터 분석 기법이 필요하게 되었고, 머신 러닝이 이러한 역할을 수행할 수 있다. 머신 러닝은 데이터의 패턴을 자동으로 인지하고, 다뤄지지 않은 패턴을 사용해 미래의 데이터를 예상하거나 불확실성 아래서 여러 종류의 결정을 선택하는 방법이다.

1.1.1 Types of machine learning

머신 러닝은 보통 두 개의 타입으로 구분할 수 있다.

1. Predictive, supervised learning
   • 레이블이 있는 입출력의 쌍이 주어졌을 때, 입력 x로 출력 y를 매핑하는 함수를 학습하는 것이 목표
   • 입력 x는 D차원 벡터로서 특징(feature), 속성(attribute), 공변량(covariance)라고 한다.
   • 출력 y는 한정된 값을 가지는 범주형 변수, 실수 값을 가지는 스칼라 변수가 있을 수 있다.
     • y가 범주형인 경우 분류(classification), 실수인 경우는 회귀(regression)이라고 한다.
2. Descriptive, unsupervised learning
   • 해당 방법에서는 입력만이 주어지고, 데이터 내의 흥미있는 패턴(interesting pattern)을 찾는 것이다.
   • 찾고자 하는 패턴이 주어지지 않기 때문에, 정의가 불분명하고, 에러를 측정할 수 있는 명확한 방법이 없다.
3. Reinforcement learning
   • 보상(reward)이 주어질 때 동작이나 행동을 배울 때 유용하다.
   • RL에 대해서는 이 책에서 자세히 다루지 않도록 한다.

1.2 Supervised learning

1.2.1 Classification

Classification의 목적은 입력 x로부터 출력 y를 매핑하는 것을 학습하는 것으로, y는 1~C의 값을 가지며, C는 class의 갯수를 의미한다. C=2인 경우에는 binary classification이라 하고, C > 2는 multiclass classification이라고 한다.
훈련 데이터에 대해서 학습을 하고 예측을 하는 것을 쉽기 때문에 classification의 주요 목적은 전에 보지 못했던 데이터들에 대해서도 답을 정확하게 예측하는 것(Generalization)이다.

1.2.1.2 The need for probabilistic predictions
주어진 입력 벡터 x와 훈련 집합 D에 대해 가능한 레이블들의 확률 분포를 나타낸다. 일반적으로 이 것은 길이가 C로 나타난다. 훈련 집합 D 뿐만 아니라 테스트 입력 x에 대한 조건부 확률이라는 것을 명시적으로 나타내기 위해 표기법에서 조건식 기호 | 의 오른쪽에 D와 x를 둔다.

확률적인 결과가 주어진다면, 다음의 식을 사용하여 레이블 값이 참인 경우에 대해 최선의 추측을 계산할 수 있다.

이 값은 가장 확률이 높은 클래스 레이블이고, 최대 사후 확률(MAP estimate) 로 알려져 있다. 해당 내용은 5.7에서 수학적인 검증을 한다.
다음과 같은 분야에서 실제로 응용되고 있다.

1. 문서 분류와 이메일 스팸 필터링
2. 꽃 분류
3. 이미지 분류와 글씨 인식
4. 얼굴 검출과 인식

1.2.2 Regression

Regression은 결과 변수가 연속적이라는 것을 제외하고 분류와 같다. 다음 그림은 단순한 예시를 보여준다.

다음은 실생활에 존재하는 Regression 문제의 예다.

• 현재 시장 상황과 다른 가능한 정보를 통해 다음 날의 주식 시장을 예측하는 것
• YouTube를 보는 사용자의 나이 예측
• 날씨 데이터와 시간, 문의 센서를 통해 건물 안의 온도를 예측하는 것

1.3 Unsupervised learning

Supervised learning과는 다르게 각 입력에 대해 기대되는 출력이 주어지지 않는다. 대신 작업을 확률 밀도 추정의 하나로 공식화한다. 즉, p(x|theta) 형태의 모형을 설계하는 것이 목표다. 이 말은 Unsupervised learning은 비조건적인 밀도 추정 문제에 해당한다.

1.3.1 Discovering clusters

Unsupervised learning의 기본이 되는 예제로 데이터를 그룹으로 clustering하는 문제다. 아래 그림은 210명의 키와 몸무게 대한 데이터들이다. 여러 개의 클러스터나 하위 그룹이 있는 것으로 보인다. K가 클러스터의 숫자를 의미한다고 하면, 첫 번째 목표는 p(K|D)를 예측하는 것이다. Supervised learning에서는 남자/여자와 같은 클래스가 있지만 Unsupervised learning은 클러스터의 갯수를 자유롭게 설정할 수 있다.
두 번째 목표는 각 데이터가 어떤 클러스터에 속하는지를 추정하는 것이다.(b)는 K=2일 때의 결과에 해당한다.

이 책에서는 model based clustering에 초점을 맞춘다. 모형 기반 클러스터링은 객관적인 방법으로 여러 모형을 비교할 수 있고, 여러 모형을 더 큰 시스템으로 조합할 수 있다.

클러스터링의 실제 응용은 다음과 같다.

• 천문학에서 천제 물리학의 측정값을 클러스터링하여 새로운 타입의 별을 발견할 수 있다.
• e-커머스에서 구입 내역과 웹 서핑을 분석하여 사용자들을 분석할 수 있고, 각 그룹에 타켓팅한 광고를 설정할 수 있다.

1.3.2 Discovering latent factors

고차원의 데이터를 처리할 때에는 데이터의 'essence'을 가지고 있는 작은 차원의 부분 공간으로 사영시키는 것이 유용하다.이것을 차원 축소라고 부른다. 아래 그림은 간단한 예시로, 3차원의 데이터를 2차원 평면으로 투영한 것이다.

2차원 데이터로 투영한 (b)는 유사한 위치에 놓여 있는 것을 보아 결과가 좋게 나왔지만, 1차원으로 축소한 (a)의 빨간 선은 결과가 좋지 못하다. (해당 내용은 12장에서 더 자세히 다룬다.)
낮은 차원의 표현은 다른 통계 모형의 입력으로 사용하면 좀 더 예측 정확도가 높아진다. 이는 불필요한 특징을 거르기 때문이다. 차원 축소를 위한 가장 일반적인 접근은 주성분분석(Principal Componenet Analysis, PCA) 이다. 이는 linear regression의 비지도 버전과 같다. 고차원 응답 y를 관찰하지만, 저차원의 '원인' z는 발견하지 못한다. 이 모델은 z -> y 형태를 가지고 , 화살표를 뒤집어서 관찰된 고차원 y를 통해 잠재된 차원 z를 추정해야 한다.

1.3.3 Discovering graph structure

상관관계가 있는 변수를 측정하고, 가장 관련이 있는 것을 발견하려는 때가 있다. 이러한 구조는 그래프로 표현할 수 있다. 노드는 변수를 표현하고, 엣지는 변수 사이의 의존 관계를 표현한다.

1.3.4 Matrix completion

데이터가 손실되는 경우가 있다. 즉, 변수의 값을 모르는 경우가 발생할 수 있다. 따라서 이렇게 손실된 데이터에 타당한 값을 추정하는 것이며, 이것을 매트릭스 완성이라고 한다.

아래 모든 내용들은 Christopher Bishop의 pattern recognition and machine learning에서 더 자세히 볼 수 있습니다.

Mixture models and EM

• 관측 변수와 잠재 변수들에 대한 결합 분포를 정의한다
  • 그러면 이에 해당하는 관측변수들만의 분포는 주변화를 통해서 구할 수 있다.

• 복잡한 관측 변수들에 대한 주변 분포를 상대적으로 더 다루기 쉬운 관측 변수와 잠재 변수 확장 공간상의 결합 분포를 통해서 표현할 수 있도록 한다.
  • 잠재 변수를 도입하면 단순한 원소를 복잡하게 만들 수 있다.

• 혼합 모델은 clustering에서도 사용가능하다.
  • 대표적으로 K-means 알고리즘이 있다.

• 일반적인 혼합 모델에서 가장 많이 사용하는 알고리즘인 EM알고리즘에 대해서 알아본다.

K-means clustering

• 다차원 공간 데이터 포인트들에서 해당 데이터들이 어떤 군집에 해당하는지 알아내는 작업을 수행한다.

• 데이터 집합 (x₁,...,x_N)를 고려하자.

  • 이는 D차원을 가지며 K개의 집단으로 나눈다.

  • μ_k는 k번째 클러스터의 중심을 나타내는 값이라고 하자.

    • 각각의 데이터 포인트로부터 가장 가까운 μ_k까지 거리의 제곱합들이 최소가 되도록 하는 것이 목표다.

• 데이터 포인트들을 집단에 할당하는 것을 설명하는 표현법을 정의한다.

  • 변수 r_nk ∈ 0,1을 정의한다.
  • 만약 x_n이 집단 k에 할당된다면 r_nk=1이며 아닌 경우는 0이라 한다.
    • 이를 one hot encoding이라 한다.

• 목적 함수를 정의한다. 이를 distortion measure(뒤틀림 척도)라고도 부른다.

  

• 이는 같은 클러스터에 속하는 각각의 점들로부터 그 클러스터의 평균과의 거리의 합을 제곱한 함수를 뜻한다.

• 이제 여기서 r_nk, μ_k를 구해야 한다.

  • 물론 J의 값이 최소가 되어야 한다.
  • 반복적인 절차를 통해서 이를 해결하는 방법을 알아본다.

• r_nk 와 μ_k 를 구하기 위해 크게 2개의 단계로 나누게 된다.

  • 먼저 μ_k의 임의의 초기값을 설정한다.
  • 첫 번째 단계에서는 이 μ_k 값을 고정한 채로 J를 최소화하는 r_nk 값을 구한다.
  • 두 번째 단계에서는 r_nk를 고정하고 μ_k를 구한다.
  • 값이 수렴할 때까지 이 두 단계의 최적화 과정을 반복하게 된다.
  • 각각의 두 단계를 E(expectation, 기댓값) 단계와 M(maximization, 최대화) 단계로 이를 합쳐 EM 알고리즘이라고 부른다.

---

• 이제 E,M을 이용한 K-means 알고리즘을 알아본다.

• r_nk를 구하는 과정을 알아본다.

  • J가 r_nk에 대한 선형 함수이므로 쉽게 최적화 할 수 있고, 닫힌 형태의 해를 얻을 수 있다.

  • 서로 다른 n에 해당하는 항들은 각자가 독립적이므로 각각의 n에 대해서 따로 최적화가 가능하다.

  • 각 클러스터 중심과 데이터 포인트들의 거리를 측정해서 가장 가까운 클러스터를 선택한다.

    

• 이제 μ_k를 구해보도록 한다. 물론 r_nk는 고정한다.

  • 목적 함수 J는 μ_k에 대해서 제곱 함수이므로 미분을 통해 최솟값이 되는 지점을 얻을 수 있다.

  

• 이 식을 μ_k에 대해 풀면 다음과 같다.

  

  • 이 식의 분모는 집단 k에 할당된 포인트들의 숫자에 해당한다. 결국 집단 k에 할당된 모든 데이터 포인트들의 평균이라는 것이다. 따라서 이러한 이유로 이 과정을 K -means 알고리즘이라 한다.

---

• 그림을 통해서 K-means가 수렴하는 과정을 살펴보도록 한다.

  

• 그림으로 보면 쉽게 이해 할 수 있다.

  • 우선 K=2로 설정을 하였고, (a)에서 임의의 μ_k 두 개를 설정한 것을 알 수 있다.
  • (b)과정에서 두 개의 평균 값을 이용해서 E 과정을 거쳤고, (c)에서 M 과정을 거친다.
  • 계속해서 EM 과정을 반복하고, 수렴 조건이 만족할 때까지 반복한다.

  

• 위 그림은 EM 과정을 반복할 때마다 목적 함수 J의 값이 줄어드는 것을 나타내는 단계이다.

• 각 단계에서 J의 값이 감소하기 때문에 수렴은 보장되어 있지만 전역 최솟값으로 간다는 보장은 존재하지 않는다.

• 평균 μ_k의 초기 값이 어디에 위치하는지에 따라 성능의 차이가 발생한다.

  • 실제 반복 횟수의 차이가 발생하게 된다.

---

• K-means 알고리즘은 유클리드 거리를 사용하고 있기 때문에 매우 느릴 수 있다.
• 따라서 이를 빠르게 하는 방법들이 있다.
  • 서로 근접한 포인트들이 같은 서브트리에 속하게 하는 방식의 트리와 같은 데이터 구조를 미리 계산한다.
  • 삼각 부등식을 사용해서 불필요한 거리 계산을 줄인다.

---

• K-means 알고리즘은 모든 데이터 포인트들과 평균 간의 유클리드 거리를 계산해야 하기 때문에 느릴 수 있다.
  • 따라서 유클리드 거리를 사용할 수 있어야 하고, outlier에 영향을 많이 받는 알고리즘이다.
• 따라서 이러한 문제를 해결할 수 있도록 k-medoids 알고리즘, 중간값을 활용하도록 한다.

k-medoids 알고리즘

• 유클리디안 거리 측정 대신 v(x,x')를 정의해서 사용한다.

• 목적 함수는 다음과 같다.

  

• E 단계은 앞서 살펴본 방식과 동일한 방법으로 O(NK)가 된다.

• M 단계는 이전보다 더 복잡할 수 있다.

  • v 의 비용이 이전보다 커지게 되고, 연산량을 줄이기 위해서 중심점을 클러스터에 속하는 데이터 중 하나로만 선정하기도 한다.
  • 이 경우 O(N_k²)의 비용이 필요하게 된다.

---

• K-means 알고리즘은 모든 데이터 포인트들이 정확하게 단 하나의 집단에만 할당된다.
  • 하지만 가끔 모두 비슷한 거리에 위치에 어디에 속하게 해야 할지 애매할 수 있다.
  • 이러한 경우 확률적인 접근 방식을 이용하여 특정 클러스터에 대한 할당을 클러스터에 포함될 확률값으로 결정할 수 있다.

혼합 가우시안

• 앞서 가우시안 성분들을 선형으로 중첩시킨 가우시안 혼합 모델을 사용하면 단일 가우시안을 사용할 때보다 더 다양한 종류의 밀도 모델들을 표현할 수 있다.

• 이번 절에서는 이산 잠재(latent) 변수들을 이용해서 혼합 가우시안 모델을 만든다.

• 가우시안 혼합 분포를 다음과 같이 선형 중첩 형태로 적을 수 있다.

  

• 이제 K차원을 가지는 이산 확률 변수 z를 도입한다. 이 변수는 특정 원소 z_k는 1이고 나머지는 0인 one-hot encoding 방법을 사용한다.

• 결합 분포는 다음과 같이 정의 한다.

  • p(x,z)=p(z)p(x|z)

    

  • 이제 z_k의 주변 분포를 혼합 계수 π_k를 사용하여 정의한다.

    

  • 매개변수 π_k는 다음의 두 제약 조건을 만족해야 한다.

    

  • 또한 z가 one-hot-encoding을 사용하므로 이 분포를 다음의 형태로 적을 수 있다.

    

• 이와 비슷하게 특정 z 값이 주어졌을 때의 x에 대한 조건부 분포는 다음 형태의 가우시안 분포다.

  

• 이는 다음의 형태로 적을 수 있다.

  

• 결합 분포는 p(z)p(x|z)의 형태로 주어진다. 이때 모든 가능한 z의 상태에 대한 결합 분포를 합산함으로써 x의 주변 분포를 구할 수 있다.

• x의 주변 분포는 식 9.7 형태의 가우시안 혼합 분포가 된다. 여러 개의 값 x₁, ... x_N을 관측했을 경우, 주변 분포를 p(x)의 형태로 표현했기 때문에 모든 관측된 데이터 포인트 x_n에 대해서 해당 잠재 변수 z_n이 존재한다.

---

• 명시적으로 잠재 변수를 사용하는 가우시안 혼합 분포를 보았다.
  • 이 결과로 주변 분포 대신에 결합 분포를 직접 활용할 수 있다.
  • 이것이 계산 과정을 매우 단순하게 만들어 준다.
• x가 주어졌을 때의 z의 조건부 확률을 구하는 것도 중요하다. 그 확률은 다음과 같이 정의하도록 한다.

• 우리는 π_k가 z_k=1일 때의 사전 확률 값이라는 것을 안다.
  • 이제 γ(z_k)는 관찰 데이터 x가 주어졌을 때의 사후 확률 값이 된다.
  • 이를 성분 k에 대한 responsibility라고 한다.

---

• ancestral sampling를 통해서 가우시안 혼합 모델에 부합하는 random 표본을 추출해 내는 것이 가능하다.

  • 이를 위해서 z 값 하나를 주변 분포 p(z)에서 추출하여 z_hat이라고 한다.
  • 조건부 분포 p(x|z_hat)로부터 x 값을 추출한다. 정확한 내용은 11장에서 소개한다.

  

• 결합 분포로부터의 표본들은 (a)에 해당한다. 여기서 x 값에 해당하는 포인트들을 그리고 이에 대한 해당 z 값에 따라 그 포인트를 색칠(빨강, 초록, 파랑)하는 방식을 사용했다.

  • 어떤 가우시안 성분이 x 값을 만들어 낸 책임이 있는지 표현할 수 있다.

• 주변 분포 p(x)로부터 표본들은 z 값을 무시하고 결합 분포에서 표본들을 추출해서 생성할 수 있고 이는 (b)에서 표시되어 있다.

• 데이터 포인트 각각에 대해서 데이터 집합이 생성된 혼합 분포의 각 성분에 대한 사후 분포를 구하는 방식을 이용하면 합성 데이터를 이용해 책임 정도를 표현할 수 있다.

  • 즉 각 색의 비율로 표현할 수 있고, (c)에 표현되어 있다.

• (a)와 같은 결과를 complete하다고 표현하고, (b)와 같은 경우엔 imcomplete 하다고 표현한다.

9.2.1 최대 가능도 방법

• 관찰 데이터가 x₁,...,x_N으로 주어져 있다.

  • 이 데이터 집합은 N x D 행렬 X로 표현한다. (N은 sample 수,D는 한 sample의 차원)

  • 이와 비슷하게 해당 잠재 변수들은 N x K 행렬 Z로 표현할 수 있다.

  • 모든 데이터가 독립이라고 가정하면 그래프를 이용해서 표현할 수 있다.

    

  • 이제 로그 가능도 함수는 다음과 같이 주어진다.

    

• MLE를 통해 이 함수를 최대화하기 위해 발생하는 문제들에 대해 알아본다.

---

특이점(singularity) 문제

• 공분산 행렬이 Σ_k=σ²_kI 인 가우시한 혼합 모델을 고려한다.

• j번째 성분이 평균으로 μ_j를 가지며, 이것이 데이터 포인트들 중 하나의 값과 정확히 일치한다고 하자.

  • μ_j=x_n이다.

• 이 데이터 포인트는 가능도 함수 식의 항에 다음과 같이 기여한다.

  

• 만약 σ_j가 0으로 간다면 무한대의 값을 가지게 될 것이고, 로그 가능도 함수를 최대화하는 것은 적절하지 않다.

  • 이러한 특이점들은 항상 존재하고, 하나가 문제가 발생해도 이러한 문제는 발생할 수 있다.

• 하지만 단일 가우시안 분포의 경우에는 문제가 없었다.

  • 하나의 위치로 거의 수렴하는 단일 가우시안 모델은 평균 값 외에는 밀도 값이 0이 된다.
  • 곱 인자에 기여하게 되므로 전체 가능도 함수값이 0 값을 가지게 될 것이다.
    • 따라서 모든 데이터 포인트들에 유한한 확률을 부여할 수 있게 된다.

• 사실 MLE 방식은 오버 피팅 문제가 존재하는데 베이지안 접근법을 활용하면 이러한 문제가 발생하지 않는다.

• 평균값을 임의로 선택한 값으로 설정하고, 공분산값을 임의의 큰 값으로 설정한 후 계산을 진행하는 방식을 사용한다.

---

식별 문제(identifiability)

• 최대 가능도 해에 대해서 K!개의 동일한 해가 존재할 것이다.
  • K개의 매개변수들을 K개의 성분들에 할당하는 K!개의 서로 다른 방법들이 있다.

이 문제는 12장에서 더 자세히 다루도록 한다.

9.2.2 가우시안 혼합 분포에 대한 EM

• 잠재 변수를 포함한 모델의 최대 가능도 해를 찾기 위한 좋은 방법 중 하나는 EM 알고리즘이다.

• 우선 가우시안 혼합 모델의 맥락에서 약식으로 EM 알고리즘을 살펴보도록 한다.

• 가능도 함수의 최댓값에서 만족되어야 하는 조건들을 적는 것으로 논의를 해본다.

  • 식 9.14를 가우시안 성분의 평균 μ_k에 대해 미분한 값을 0으로 설정하면 다음을 얻게 된다.

    

• 양변에 Σ_k를 곱하고 전개하면 다음을 얻게 된다. (이 때 행렬이 정칙이라고 가정한다.==역행렬이 존재한다.)

  

• N_k는 집단 k에 할당되는 유효 데이터 포인트의 숫자로 해석한다.

• 수식을 자세히 살펴보면 사실 k번째 가우시안 성분의 평균은 데이터 집합의 모든 포인트들의 가중 평균으로 구할 수 있다.

  • 이때 데이터 포인트 x_n에 대한 가중치는 x_n을 생성하는 데 있어서 성분 k의 책임 정도에 해당하는 사후 확률로 주어진다.

• 위와 동일하게 Σ_k에 대한 미분값을 0으로 놓고 단일 가우시안 공분산 행렬에 대한 해를 바탕으로 비슷한 추론 과정을 거치면 다음과 같다.

  

• 이는 데이터 집합에 근사한 단일 가우시안 분포의 경우와 비슷하다.

  • 다른점은 각각의 데이터 포인트들이 해당 사후 확률로 가중되며, 해당 성분에 연관된 유효 데이터 포인트의 숫자가 분모에 추가된다는 점이다.

• 마지막으로 π_k에 대해 최대화를 해보도록 한다. 이 때에는 이 값들의 합이 1이어야 한다는 제약 조건식을 생각해야 한다. 따라서 라그랑주 승수법을 사용하도록 한다.

  

• 양변에 π_k를 곱하면 γ(z_nk)가 나오게 된다. 이를 다시 정리하면 다음과 같다.

  

• 결국 k번째 성분의 혼합 계수는 데이터 포인트들을 설명하기 위해 취한 responsibility를 평균한 값이 된다.

• 이렇게 얻은 평균, 분산, 혼합 계수는 닫힌 형태의 해를 제공하지 못하는데, γ(z_nk)들이 복잡한 방식으로 종속되어 있기 때문이다.

  

EM 알고리즘 적용

• EM 알고리즘은 반복적인 방법을 이용하여 값을 추정하는데, GMM에서는 다음과 같이 처리한다.
  • (a)와 같이 random한 값으로 평균, 분산을 초기화 한다.
  • E 단계
    • 현재 값을 사용하여 사후 확률 z를 추정한다. -> (b)
  • M 단계
    • E 단계에서 계산한 값을 이용하여 MLE를 통해 평균, 분산, 혼합 계수의 값을 다시 추정한다. -> (c)
  • 반복
    • 수렴 조건이 만족할 때까지 E, M을 반복 (d) , (e) , (f)에 해당한다.
• EM 알고리즘이 수렴을 달성하기 위해 필요로 하는 반복 횟수가 K-means 알고리즘에 비해 훨씬 많다.
  • 따라서 K-means 알고리즘을 먼저 수행해서 적합한 초기값을 찾아내고, EM 알고리즘을 적용하는 것이 일반적이다.
• K-means와 동일하게 특이점 문제가 발생하지 않도록 조심해야 한다.
• 여러 개의 지역적 최댓값이 있으므로 EM 알고리즘은 이들 중 가장 큰 값을 찾는 것을 보장하지 못한다.

---