2.1 Introduction

이전 장에서는 확률이 어떻게 머신 러닝에서 사용될 수 있는지 살펴보았다면, 2장에서는 더 자세한 확률 이론에 대해 알아본다. 확률에 대한 기술적인 논의를 하기 전에, "확률이란 무엇인가?"라는 질문에 먼저 답해보도록 한다. 쉽게 생각할 수 있는 주제로 '동전을 던졌을 때, 앞면이 나올 확률은 0.5'라는 것은 다들 알 것이다. 사실 확률에 대한 해석은 크게 2가지가 가능하다.

1. Frequentist

• 빈도주의적인 해석으로써 장기간에 걸쳐 발생 빈도를 의미한다. 즉, 동전을 수없이 많이 던져서 앞면이 나올 확률이 0.5가 나온다는 것을 알 수 있다는 것이다.

2. Bayesian

• 베이지안 해석으로 확률은 어떤 것에 대한 불확실성을 수량화하는 것이며, 반복되는 시도보다는 기본적으로 정봐와 연관된 것이다. 즉, 베이지안적 시각으로 보면, 다음 동전 던지기 때에 앞면과 뒷면이 나올 확률은 동일하다는 것이다.

베이지안식 해석의 큰 장점은 장기간의 빈도를 가지지 않는 사건에 대한 불확실성을 모형화하는 것에 사용할 수 있다는 것이다. 따라서 이 책에서는 베이지안식 해석을 채택하여 설명하도록 한다.

2.2 A brief review of probability theory

이 절에서는 확률 이론에 대한 기초 개념을 간단히 리뷰하도록 한다. 따라서 이미 확률 이론에 대해 익숙한 사람이라면 이 절을 생략해도 무관하다.

2.2.1 Discrete random variables

p(A)는 event A가 발생할 확률을 의미한다. 예를 들어, A는 "내일 비가 올 확률"가 될 수 있다. 0<= p(A) <=1 이어야 하며, p(A)=0은 사건이 절대 발생하지 않는다는 것을 의미하고, p(A)=1은 사건이 반드시 발생한다는 것을 의미한다.
이산 확률 변수 X를 정의해서 이항 사건에 대한 개념을 확장할 수 있으며, X는 유한 집합이나 가산 무한 집합으로부터 어떠한 값도 가질 수 있다. X=x의 확률은 p(X=x)로 나타내고, 간단히 p(x)라고 나타낸다. 여기서 p()는 확률 질량 함수 또는 pmf이다.p(x)도 0과 1 사이의 값을 가지며, 총합은 1이 된다는 조건을 만족한다. 위 그림은 유한한 상태 공간에서 정의된 두 개의 pmf며, 왼쪽은 균등 분포를 가지고 있으며, 오른쪽은 퇴화 분포에 해당하며, X가 항상 1과 같다는 것을 표현한다.

2.2.2 Fundamental rules

생략

2.2.3 Bayes rule

조건부 확률의 곱, 합 법칙을 통합하면 Bayes rule을 도출 할 수 있으며, 이를 Bayes Theorem이라고 부른다.

2.2.3.1 Example: medical diagnosis

베이즈 법칙을 사용하는 예로 의학적 진단 문제를 생각해보자. 당신은 40대 여성이라고 가정하고, 유방조열술로 유방암에 대한 의학 검진을 받기로 했다. 검사가 양성일 때, 실제로 암일 확률은 얼마일까?
이 확률을 구하기 위해서는 우선 검사가 얼마나 신뢰성이 있는지 알아야 한다. 검사가 80%의 정확성을 가지고 있을 경우 당신이 암이라면 0.8의 확률로 양성이 나타날 것이다. 즉, 다음과 같다.

p(x=1|y=1) = 0.8

여기서 x=1은 유방조영술이 양성인 사건을 의미하고, y=1은 유방암인 경우의 사건이다. 대부분의 사람들이 이런 경우 80%가 암이라고 결론을 내린다. 하지만 이것은 False다! 이러한 결론은 유방암을 가지고 있는 사전 확률을 무시한 것이다. 다행히도 암을 가질 확률은 매우 낮다.

p(y=1) = 0.004

사전 확률을 무시하는 것을 기저율 에러(base rate fallacy)라고 한다. 또한 테스트가 거짓 양성 또는 거짓 정보일 케이스인 경우도 고려해야 한다. 불행하게도 거짓 양성인 가능성은 높다.

p(x=1|y=0) = 0.1

베이즈 법칙을 사용해 세 개의 조건을 모두 결합하면 다음과 같이 정확한 답을 계산할 수 있다.

즉, 검사가 양성이라면 실제 유방암일 확률은 대략 3%에 해당한다.

2.2.4 Independence and conditional independence

X와 Y의 결합 확률을 곱으로 표현할 수 있다면 무조건적인 독립, 또는 marginally 독립이라고 하며, X⊥Y로 표현한다. 즉, 다음과 같다.

일반적으로 결합 확률이 marginal의 곱이면 변수 집합이 상호 독립적이라고 한다.
대부분의 변수는 다른 변수에게 영향을 주는 경우가 많기 때문에 무조건적인 독립은 매우 드물다. 하지만 이런 영향은 직접적이라기보다는 다른 변수에 의해 중재된다. 그러므로 조건부 결합 확률이 조건부 주변의 곱으로 표현될 수 있는 경우에만 "Z가 주어졌을 때 X와 Y는 조건부 독립이다" 라고 한다.

2.2.5 Continuous random variables

지금까지는 불확실한 이산량에 대한 추정만을 다뤘으며, 이번 절에서는 어떻게 확률을 확장해야 하는지 알아본다.
X를 불확실한 연속량으로 가정한다면, X가 a이상 b이하일 확률은 다음과 같이 계산한다.

위와 같이 확률을 계산하는 것을 함수 형태로 정의하고, 이것을 X의 누적 분포 함수(cumulative distribution function) 혹은 cdf라고 정의한다. 이는 그림 (a)에 해당하고, 표기법을 사용하면 다음과 같다.

이제 도함수를 정의하고, 이것을 확률 밀도 함수(probability density function) 혹은 pdf라고 한다. 이는 그림 (b)에 해당한다. 표기법을 사용하면 다음과 같다.

2.2.6 Quantiles

cdf F가 단조 증가 함수이기 때문에 역함수를 가지고 있다. 이를 F^-1라고 하고, F의 분위수(quantile)라고 부른다. F^-1(0.5)는 중앙값이고, F^-1(0.25), F^-1(0.75)는 각각 하위 및 상위 사분위수다.

2.2.7 Meana and variance

분포를 설명할 때 가장 익숙한 속성은 평균 또는 기댓값이며, μ와 같이 표기한다. 분산은 분포의 '흩어진 정도'를 측정하는 것이며 σ2로 표기한다.

2.3 Some common discrete distributions

보편적으로 사용되는 이산 상태 공간에서 정의된 모수적 분포들에 해당한다. 자세하게 설명하지 않고, 분포의 종류들만 나열하도록 한다.

1. The binomial and Bernoulli distribuions
2. The multinomial and multinoulli distributions
3. The Poisson distribution
4. The empirical distribution

2.4 Some common continuous distributions

2.3절과 같이 분포들에 대해 나열만 하도록 한다.

1. Gaussian distribution
2. Degenerate pdf
3. The Laplace distribution
4. The gamma distribution
5. The beta distribution
6. Pareto distribution

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

1.4 Some basic concepts in machine learning

이번 절에서는 머신 러닝에서의 주요 아이디어를 제공한다. 뒷 파트에서 더 자세히 다룰 예정이기 때문에 여기서는 간략하게만 다룬다.

1.4.1 Parametric vs non-parametric models

이 책에서는 지도 학습과 비지도 학습에 따라서 확률 모형을 다르게 구성한다. 이런 모형을 정의하는 많은 방법이 있지만, 가장 중요한 차이는 모형이 고정된 개수의 변수(Parametric)를 갖는지, 혹은 훈련 데이터의 양에 따라 개수가 증가하는지(non-parametric) 여부다. Parametric한 모형은 빠르게 사용할 수 있는 장점이 있지만 데이터분포에 대한 강한 가정(데이터 분포에 영향을 많이 받는다.)을 만들기는 어렵다. non-parametric하면 데이터 분포에 영향을 덜 받지만 계산적으로 다루기 어렵다.

1.4.2 A simple non-parametric classifier: K-nearest neighbors

non-parametric 분류기의 가장 간단한 예를 K nearest neighbor (KNN) 분류기다. 이것은 데이터 집하에서 테스트 입력 x에 가장 가까이 에 있는 K개의 포인트를 찾는 것이며, 각 클래스의 멤버가 얼마나 이 집합에 있는지 개수를 계산하고, 실험적 비율을 추정 값으로 반환한다.

1.4.3 The curse of dimensionality

KNN 분류기는 간단하며, 레이블된 훈련 데이터가 충분하게 있다면 잘 작동한다. 하지만 KNN 분류기의 주요 문제는 고차원의 입력에 대해서는 잘 작동하지 않는다는 점이다. 고차원에서 성능이 잘 나오지 않는다는 것은 curse of dimensionality(차원의 저주) 때문이다.

1.4.4 Parametric models for classification and regression

차원의 저주에 대항하는 주요 방법은 데이터 분포의 성질에 관한 가정을 만드는 것이다. 귀납적 편향성이라고 불리는 이 가정은 parametric한 모델로 구현하며, 고정된 개수의 매개변수를 가지는 통계 모형이다. 폭넓게 사용되는 두 가지의 예를 살펴본다.

1.4.5 Linear regrssion

회귀에서는 선형 회귀(Linear regression)이라고 알려져 있는 것을 주로 사용한다. 이 모형에서는 입력에 대한 식을 1차 함수로 나타낸다. 다음과 같이 식을 표현한다.

1.4.6 Logistic regression

앞서 본 선형회귀를 두 가지만 변경한다면 일반화할 수 있다. 첫번째는 선형 회귀에서는 가우시안 분포라고 가정했던 것을 베르누이 분포라고 가정한다. y의 값이 0과 1만을 가진다면 다음과 같이 분포를 정의한다.

1.4.7 Overfitting

유연한 모델을 만들기 위해서 overfit(과적합)하지 않도록 주의해야 한다. 즉, 입력의 모든 변화를 모형화하는 것을 피해야 한다는 것으로, 이런 모형일 수록 노이즈인 경우가 많기 때문이다. 위와 같은 예시가 있을 수 있다. (b)가 모든 변화를 모형화를 한 경우에 해당된다. 하지만 실제 함수가 예시와 같이 생긴 확률을 낮기 때문에, 이런 모형을 사용해서 예측을 하는 경우 부정확한 결과를 얻을 수 있다.

1.4.8 Model selection

생략

1.4.9 No free lunch theorem

대부분의 머신 러닝의 알고리즘은 새로운 모델을 만들거나, 그것들이 적합하도록 만드는 것에 관심이 있다. 특정 문제에 대해서 최적화할 수 있지만, 모든 문제에 대해 최적의 모델은 없다. 이것을 No free lunch theorem 라고 한다. 하나의 영역에서 잘 작동하는 가정이 다른 영역에서 잘 작동하는 가정이 다른 영역에서 잘못 작동하는 경우가 있다.

케빈 머피의 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를 둔다.

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

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

1.2.2 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차원 평면으로 투영한 것이다.

1.3.3 Discovering graph structure

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

1.3.4 Matrix completion

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

Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

6. Value Function Approximation

지금까지는 Grid World를 통해서 작은 상황을 설정했고 table로 저장하는 것이 가능했다. 그리고 value function과 policy를 구하는 과정을 살펴보았다. 이러한 문제들을 Tabular Method라고 부른다. 하지만 실제 문제에 대해서 강화학습을 적용하기에는 너무 크다.

지금 강화학습으로 해결할 수 있거나 해결하려고 하는 문제에 대해서 state의 갯수를 알아보면 다음과 같다. Backgammon은 10²⁰, 알파고는 10¹⁷⁰, 헬리콥터(자율주행)은 사실상 무한대의 상태들을 가지고 있다. 따라서 이러한 문제에 대해서 value function과 policy를 구하고자 하는 것은 어렵다. 따라서 이 값들을 추정하는 방법들에서 배우도록 한다.

function approximation을 하는 방법은 어렵지 않다. 새로운 변수 w를 대입해서 이 변수가 table의 정보를 대변하도록 만들면 된다. 즉 다음과 같이 함수화 할 수 있다.

w는 학습을 통해서 update하며, true value와 근사하도록 맞춰나간다. 최근에는 이 학습을 하는 과정에 deep learning을 사용하기도 한다.

Value Function Approximation에는 다음과 같은 종류들이 있다고 한다.

function approximator에는 여러 개가 있지만 그 중 미분가능한 Linear combinations of features, Neural network를 이번 장에서 소개하도록 한다. 그리고 이들은 non-stationary, non-iid한 data라고 하는데, 분포가 계속해서 바뀌며 독립적이지 않다.

Incremental Methods

w를 업데이트를 하는 방법중 가장 좋은 것은 Gradient Descent이다. 이 방법은 간단하고 프로그램 상으로도 강력하다. 하지만 시작점에서 조금만 달라져도 다른 점에 도착할 수 있고, 이 점이 local optima일 수도 있다.

w로 표현되는 loss function인 J(w)는 true value와의 error로써 이를 최소화하는 것이 목적이다.

이를 미분해서 값을 update 할 수 있는데 expectation을 쓰는 방법과 sampling을 하는 방법이 있고 다음과 같다.

MC와 TD에서 했던 것처럼 v_π(S)를 대체해서 사용할 수 있다.

MC with Value Function Approximation

MC의 G_t는 unbiased 하고, true value의 noisy sample이다. 그러므로 training data를 지도학습으로 적용할 수 있다. 그래서 위와 같이 사용가능하며, local optimum으로 수렴하게 된다. 그리고 non-linear한 경우에도 적용할 수 있다고 한다.

TD Learning with Value Function Approximation

TD-target은 guess를 사용하는 것이기 때문에 true value의 biased sample이다. 하지만 여전히 training data를 지도학습으로 적용이 가능하고 위에서 소개한 것처럼 TD(0)를 적용할 수 있다.

Linear TD(0)는 (거의) global optimum에 수렴한다.

TD(λ) with Value Function Approximation

G_t^λ도 true value의 biased sample이다. 그러므로 역시 training data를 지도학습으로 적용할 수 있으며 Forward view linear TD(λ), Backward view linear TD(λ)로 각각 적용할 수 있고, 서로 equivalent하다.

Control with Value Function Approximation

하지만 value function을 사용하면 control 문제를 다룰 때 발생했던 model-free가 발생한다. 따라서 이번에도 value function을 q-function으로 바꾸도록 한다.

그리고 그 뒤로는 value function을 했던 내용과 동일합니다.

Batch Methods

Gradient descent는 간단하고 매력적이지만 한번 쓰고 버린다. 따라서 sample efficient하지 않다고 한다. 따라서 Batch method는 1000개의 데이터가 있으면 그 중 10개를 sample로 해서 사용하는 방식이다. 이를 통해 value function의 best fitting을 찾을 수 있다고 한다.

value function approximation을 사용하고, experience D는 <state, value>의 쌍으로 구성된다. 이 때 best fitting value인 파라미터 w를 찾기 위해서 Least squares 알고리즘을 사용한다.

Least squares 알고리즘은 추측값과 참값 사이의 sum-squared error를 최소화하는 w를 찾는 알고리즘이다.

Stochastic Gradient Descent with Experience Replay

<state, value>로 쌍이 묶어진 experience D가 있을 때, 다음을 반복한다.

그러면 이는 다음과 같이 수렴한다.

이러한 방법을 Experience replay라고 하며 강화학습에서 자주 사용하는 방법이다.

Experience replay in Deep Q Networks

Non-linear랑 off-policy일 때 학습을 진행하면 수렴을 하지 않고 발산한다는 문제점이 발생한다. 따라서 이러한 문제를 해결하기 위해 DQN은 experience replay와 fixed Q-target을 사용한다고 한다.

• Experience reaply: 어떤 action에 어떤 reward와 그 state등 정보들이 있는 transition을 replay memory에 저장하고, random하게 mini batch를 뽑는다. 그리고 MSE를 통해 학습한다.
• Fixed Q-target: target을 계산할 때에 예전 parameter를 쓰는 것, 두 개의 파라미터 set이 있다. 하나는 고정시키고 다른 하나는 업데이트 중인 파라미터 set을 가진다. non-linear 함수일 때에 업데이트 방향이 계속 바뀌기 때문에 수렴되기 어렵다. 따라서 1000번 정도는 고정된 parameter set을 사용하며 진행하다가 그 이후에 고정된 parameter set을 업데이트 하던 parameter set으로 바꾼다. 예전 버전을 w^-, 현재 버전을 w라 했을 때, target에서는 고정된 것을 사용하기 때문에 fixed Q-target이라 한다.

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

12. 연속 잠재 변수

• 이미 9장에서 가우시안 혼합 분포와 같은 이산 잠재 변수를 가지는 확률 모델을 살펴보았다.

  • 이제 몇몇 잠재 변수들 또는 모든 잠재 변수들이 연속적인 모델에 대해 살펴본다.

• 이러한 모델은 원래 데이터 집합 공간의 차원보다 훨씬 더 낮은 차원의 manifold에 모든 데이터 포인트들이 가깝게 놓이는 성질을 가진다.

  • manifold란 데이터가 있는 공간이라고 생각하면 된다.

• 예시를 살펴 보도록 한다.

  • 64 x 64 픽셀로 표현되는 숫자 이미지를 100 x 100 크기의 이미지에 삽입하도록 한다.

  • 빈 공간은 0 값을 가지게 되고, 숫자를 넣는 위치는 random이며 다음과 같이 표현된다.

    

  • 각 이미지는 10,000개의 픽셀을 가지게 되며, 세 개의 변동 가능한 자유도만이 존재한다.

    • 수직 이동, 수평 이동, 회전 이동

  • 각각의 데이터 포인트들은 실 데이터 공간의 부분 공간상에 존재, 이 부분 공간을 intrinsic dimensionality라고 한다.

• 위의 예시의 경우 manifold는 비선형이다. 하나의 숫자를 이동시켰을 때 특정 픽셀은 0에서 1로, 다시 0으로 바뀌는 비선형 이기 때문이다.

• 또한 이동과 회전 매개변수는 잠재 변수들이다.

  • 우리가 관측하게 되는 것은 이미지 벡터인데 생성될 때 이동 변수나 회전 변수들이 사용되었는지 알 수 없다.

• 가장 단순한 연속 잠재 변수 모델에서는 잠재 변수와 관측 변수가 둘 다 가우시안 분포를 이룬다고 가정하고 잠재 변수들의 상태에 대한 관측 변수들의 선형 가우시안 종속성을 사용한다.

  • 이를 통해 PCA를 도출한다.

12.1 PCA

PCA는 차원수 감소, 손실 허용 데이터 압축, 특징 추출, 데이터 시각화 등의 여러 분야에서 사용되고 있다.

• PCA에는 두 가지 정의가 있지만 결과적으로는 같은 알고리즘을 도출하게 된다.
  • 데이터를 주 부분 공간(prinipal subspace)이라고 하는 더 낮은 선형 공간에 직교 투영하는 과정이며 위 그림과 같이 진행된다.
    • 이때 투영 과정은 투영된 데이터의 분산이 최대화되는 방향으로 이루어져야 한다.
  • 평균 투영 비용을 최소화하는 선형 투영으로 PCA를 정의
    • 이 경우 평균 투영 비용은 데이터 포인트와 그 투영체 간의 평균 제곱 거리로 정의

12.1.1 최대 분산 공식화

• 관측 데이터 집합 x_n이 있다고 하자. 이는 차원수 D를 가지는 유클리드 변수다. 우리의 목표는 데이터를 M < D의 차원수를 가지는 공간상에 투영하는 것이다.
  • 이때 투영된 데이터의 분산이 최대가 되도록 한다.
  • M값이 주어졌다고 가정하고, 나중에 적절한 M 값을 찾아내는 것을 알아본다.
• M = 1이라고 하자.
• 이 공간의 방향을 D차원 벡터 u₁로 정의할 수 있다. 편의를 위해서 단위 벡터를 사용한다.
  • 즉 u₁^Tu₁ = 1 이다.
    • u₁에 의해 정의되는 방향이므로 임의의 크기를 자기는 벡터를 사용해도 일반성을 잃지 않는다.
• 각각의 데이터 포인트는 u₁^Tx_n에 투영된다.

• 그리고 투영된 데이터 분산은 다음처럼 주어진다.

  

• S는 데이터 공분산 행렬로서 다음처럼 주어진다.

  

• 이제 투영된 분산을 u₁에 대해서 극대화하도록 한다. 이 때 이 값이 무한대로 발산하는 것을 막기 위해 제약 조건을 걸어야 하며 정규화 조건으로부터 제약 조건을 얻고 라그랑주 승수법을 도입해 최대화를 실시하도록 한다.

  

• u₁에 대한 미분을 0으로 설정하면 다음과 같다.

  

  • 즉 u₁이 S의 고유 벡터가 된다. 왼쪽에 u₁^T를 곱하면 분산은 다음과 같이 주어진다.

    

  • u₁를 가장 큰 고윳값 λ₁을 가지는 고유 벡터로 설정하면 최대의 분산을 가지게 되고, 이 고유 벡터를 제1주성분이라고 한다.

• 요약하면, PCA는 데이터 집합의 평균과 공분산 행렬 S를 계산하고 S의 가장 큰 M개의 고윳값들에 해당하는 M개의 고유 벡터들을 찾는 과정

12.1.2 최소 오류 공식화

• 투영 오류를 최소화하는 방식을 살펴본다.

• 완전히 정규 직교하는 D차원의 기저 벡터들 u_i을 도입해 보자.

  • u_i^Tu_j = δ_ij를 만족한다.

• 이 기저들은 완전하므로, 데이터 포인트들을 기저 벡터들의 선형 결합으로 정확하게 표현할 수 있다.

  

  • 계수 a_ni는 각 데이터 포인트마다 다른 값이며, 새 시스템으로 좌표계를 회전 변환하는 것에 해당한다.

  • u_j와 내적을 진행한 후 정규 직교 성질을 이용하면 a_nj=x_n^Tu_j를 얻는다.

    

• 목표는 이 데이터 포인트들을 제한된 수 M < D개의 변수들을 이용해서 근사하는 것

  • 저차원 부분 공간으로의 투영에 해당

• M개의 기저 벡터들을 이용해 M차원 선형 부분 공간 표현할 수 있고, x_n을 다음과 같이 근사한다.

• z_ni는 특정 데이터 포인트에 대해 종속적이지만 b_i는 모든 데이터 포인트들에 대해 동일한 상수다.

  • 이러한 값들은 차원을 줄임으로 인해 발생하는 왜곡도를 감소시키는 방향으로 자유롭게 선택할 수 있다.

• 왜곡도를 측정하고 이를 최소화하도록 한다. 왜곡도는 다음과 같다.

  

  • 우선 각각의 z_ni 값에 대한 최소화를 고려해 보자. x_tilda 값을 치환하고, z_nj에 대한 미분값을 0으로 설정한 후 정규직교 조건을 사용하면 다음을 구할 수 있다.

    

    • 여기서 j = 1, ... ,M이다.
    • 12.10 식에서 앞 부분에 해당하는 것을 의미한다.

  • b_i에 대한 미분값을 0으로 놓고 정규직교 조건을 이용하면 다음을 얻을 수 있다.

    

    • 여기서 j = M+1, ... , D다.
    • 12.10 식에서 뒷 부분에 해당하는 것을 의미한다.

• 여기서 z_ni와 식 12.10의 b_i를 대입해 넣고 식 12.9의 일반 전개식을 사용하면 다음과 같다.

• 이로부터 x_n에서 x_tilda로의 이동 벡터는 주 부분 공간에 직교하는 공간상에 존재함을 알 수 있다.

  • 이동 벡터들은 i = M+1 , ... , D에 대한 {u_i}의 선형 결합이기 때문
  • 투영된 포인트는 x_tilda 부분 공간상에 놓여 있어야 하지만, 공간 내에서는 자유롭게 이동시킬 수 있으므로 최소 오류를 달성 할 수 있다.

• 따라서 J를 {u_i}의 함수로 표현한다.

  

• 이제 {u_i}에 대해 최소화한다.

  • 이는 제약 조건이 있는 최소화이다. 따라서 라그랑주 승수법을 사용한다.
  • 제약 조건은 정규직교 조건으로부터 기인한다.

• 이차원 데이터 공간 D = 2, 주 부분 공간 M = 1의 예시로 살펴본다.

  • J=u₂^TSu₂를 최소화하는 방향 u₂를 선택해야 하고, 제약 조건u₂^Tu₂=1을 만족해야 한다.

    

  • u₂에 대한 미분값을 0으로 설정하면 Su₂ = λ₂u₂를 얻는다. u₂는 S의 고유 벡터가 된다.

  • u₂에 대한 해를 왜곡도 식에 역으로 대입해 넣으면 J=λ₂가 된다.

    • 두 개의 고윳값들 중 작은 고윳값에 해당하는 고유 벡터로 u₂를 선택해 J를 최소로 만들 수 있다.

• 이 내용은 제곱 투영 거리의 평균값을 최소화하기 위해 주성분 부분 공간이 데이터 포인트들의 평균을 통과하도록 해 최대 분산의 방향과 정렬되도록 한다.

• 따라서 이를 일반화하면 다음과 같다.

  

• 지금까지는 M < D인 경우만 고려하였는데, M=D인 경우에도 유효하다.

  • 이 경우엔 차원 감소는 없으며, 좌표축들을 회전시켜 주성분들에 정렬되도록 한다.

아래 모든 내용들은 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 알고리즘은 이들 중 가장 큰 값을 찾는 것을 보장하지 못한다.

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

4.2 확률적 생성 모델

• 앞서 설명했던 용어들을 다시 한 번 정리하고 넘어간다.

  • 사후 확률 (posterior) : p(C_k|x)

    • 임의의 데이터 x가 주어졌을 때 이 데이터가 특정 클래스에 속할 확률

  • 클래스-조건부 밀도(class-conditional density) : p(x|C_k)

    • 특정 클래스에서 입력된 하나의 데이터 x가 발현될 확률

  • 가능도 함수 p(X|C_k)

    • 주어진 샘플 데이터가 실제 발현될 확률값을 주로 사용하며, 로그를 불이는게 일반적이다.

• 생성적 접근법을 사용해서 클래스가 2 개인 경우를 고려해본다. 그러면 C₁에 대한 사후 확률을 다음과 같이 적을 수 있다.

  

• σ(a)는 로지스틱 시그모이드 함수로서 다음과 같이 정의된다.

  

• 시그모이드 함수는 다음과 같이 그려진다.

  

• 시그모이드 함수는 다음과 같은 대칭성을 만족한다.

  

• 시그모이드는 0과 1 사이의 값으로 수렴을 하므로, 확률 값으로 고려를 해도 되고, 모든 점에서 연속이기 때문에 미분 가능해 수학적 전개에도 매우 편리하다.

• 로지스틱 시그모이드의 역(inverse)은 다음과 같다.

  

• 이를 로짓이라고 부른다.

• K > 2인 경우에도 식을 확장할 수 있다.

  • 이를 일반 선형 모델이라고 부른다.

    

  • a_k는 다음과 같다

    

  • 이를 정규화된 지수 함수라 하며, 다중 클래스 분류에 사용되는 식이 된다. 이를 softmax function이라고도 한다.

    • 평활화된 버전의 최댓값 함수에 해당한다.

4.2.1 연속적인 입력값(Continuous inputs)

• 클래스별 조건부 밀도가 가우시안이라고 가정하자.

  • 모든 클래스들이 같은 공분산 행렬을 공유한다고 가정하자.

  

• 이를 class가 2 개인 경우에 대해 고려해보자.

  

• 위 식은 σ(a)에 정의되어 있었다.

  

• 위와 같은 내용을 얻을 수 있다.

• x에 대한 2차 term이 모두 사라지면서 직선 식을 얻게 되었다.

  • 공분산 행렬을 공유한다는 가정으로 인해

• 같은 분산을 가지는 두 개의 가우시안 분포가 만나는 지점은 당연히 직선의 형태일 것이다.

  

• 왼쪽 그림은 2-class에서의 확률 밀도를 표현한 것이다.

  • 공분산이 동일하므로 모양이 같고, 따라서 경계면은 직선일 것이다.

• 이제 이를 K 클래스 문제로 확장하면 어떻게 될까?

  

• 계산을 간단히 하기 위해 공분산이 동일하다고 가정했지만 다르면 어떻게 될까?

  • 경계면을 구하는 식에서 이차항이 남게 되어 경계면이 곡선이 될 수 있다.

4.2.2 최대 가능도 해

• 클래스 조건부 밀도의 매개변수적 함수 형태를 명시하고 나면 최대 가능도 방법을 이용해서 매개변수들의 값과 사전 클래스 확률을 구할 수 있다.

  • 이를 위해 관측값 x와 그에 대한 데이터 집합이 필요하다.

• 두 개의 클래스가 있는 경우를 고려해보자.

  • 각각의 클래스들은 가우시안 클래스 조건부 밀도를 가지며, 공분산 행렬은 공유한다.

• t_n=1인 경우 C₁로, t_n=0인 경우 C₂로 분류한다.

• 따라서 가능도 함수는 다음과 같다.

  

• π 구하기

  • 로그 가능도 함수를 π에 대해 미분하여 관련된 항목만 모으면 된다.

    

• 여기서 N₁은 C₁에 속하는 샘플의 수이고, N₂은 C₂에 속하는 샘플의 수이다.

• π는 정확히 C₁에 속하는 샘플의 비율을 의미하게 된다.

• μ 구하기

  • 마찬가지로 로그 가능도 함수를 각각의 μ 값으로 미분하여 값을 구한다.

    

• 이 식을 0으로 놓고 μ₁, μ₂에 대해 풀면 다음을 얻을 수 있다.

  

• Σ 구하기

  • 역시 로그 가능도 함수를 미분하여 값을 구한다.

    

• 여기서 S는 다음과 같다.

  

4.2.3 이산 특징

• 입력 값이 연속적이지 않고 Discrete이라고 가정한다.

• 입력 데이터가 D차원이라면 각 class별로 얻을 수 있는 확률 분포의 실제 x의 Discrete 범위는 2^D개이다.

  • 이 중 독립 변수는 2^D-1이다. (합산 제약 조건 때문)

• 나이브 베이즈 가정을 사용했고 각 class C_k에 대해 조건부일 때 독립적으로 취급한다. 따라서 다음과 같다.

  

• 이 식을 4.63에 대입한다.

  

• 이는 다시 입력 변수 x_i에 대해 선형 함수다.

• 2-class에서는 시그모이드를 도입하면 동일할 것이다.

4.2.4 지수족

• 지금까지 사후확률의 경우 항상 sigmoid, softmax를 이용해서 모델링을 할 수 있었다.

  • 이를 더 일반화 시켜보자.

• 클래스 조건부 밀도가 지수족 분포를 따른다면 가능하다.

  • 지수족 분포를 따를 경우의 확률 분포는 다음의 형태로 적을 수 있다.

    

• 이 중 u(x) =x인 부분 집합들만 고려한다. 여기에 척도 매개변수 s를 도입해서 제한된 형태의 지수족 분포 클래스 조건부 밀도를 구할 수 있다.

• 각각의 클래스들의 각자의 매개변수 벡터를 가지지만, 척도 매개변수 s는 공유한다고 가정한다.

• 2-class에서 사용한 a_k에 대입하여 전개해본다.

  

• K-class에도 비슷하게 나오며 모두 선형 식임을 알 수 있다.

4.3 확률적 판별 모델

• 2-class 문제에 대해서는 사후 확률을 시그모이드 함수로 표현하고, k-class 문제에 대해서는 softmax 함수로 제동되는 것을 확인하였다.

• 다른 방식을 생각해본다

  • 선형 모델의 함수 형태를 명시적으로 사용하고, 최대 가능도 방법을 적용해 직접 구한다.

  • 이를 위해 iterative reweighted least squares, IRLS라고 한다.

• 앞에서 설명했던 간접적으로 매개변수를 찾는 방식은 생성적 모델의 예시이다.

• 이번 절에서는 판별적 훈련의 예시를 살펴볼 것이며, 적응 매개변수의 숫자가 더 적으며, 더 나은 예측 성능을 보일 수도 있다.

4.3.1 고정된 기저 함수

• 지금까지는 원 입력 벡터 x에 대해 직접적으로 적용되는 분류 모델에 대해 고려했다.

• 이제는 비선형 기저 함수를 이용하여 입력 값을 변환하는 형태를 사용한다.

  

• 위의 그림은 비선형 기저 함수를 이용하여 변환된 데이터를 선형 판별하는 것을 묘사하고 있다.

  • 왼쪽 그림은 최초 입력에 대한 공간을 나타내며 2개의 클래스로 구성되어 있음을 알 수 있다.

  • 오른쪽은 입력 데이터가 변환된 뒤, 선형 판별식에 의해 클래스가 구별되고 있음을 보여준다.

  • 왼쪽에서의 검은 원은 오른쪽에서는 선형으로 바뀐 것을 알 수 있다.

• ϕ₀(x)=1를 추가해서 w₀가 bias 역할을 수행하도록 한다.

• 실제의 여러 문제들에서는 클래스 조건 밀도들 사이에 상당한 중첩이 있다.

  • 각각의 값이 0과 1이 아닌 경우가 발생한다.

  • 하지만 ϕ(x)는 이러한 중첩 현상을 제거해주진 못한다.

    • 그렇지만 적절한 비선형성을 선택한다면 사후 확률을 모델링하는 과정이 쉬워지게 된다.

4.3.2 로지스틱 회귀

• 2-class에서 일반화된 선형 모델에 대해 알아보도록 하자. 분류에 대한 사후 확률 값은 로지스틱 회귀로 기술되는 것을 확인했다. 식은 다음과 같다.

  

• 여기서 σ 는 로지스틱 시그모이드라고 부른다.

• 기저 함수 ϕ 가 M차원이면 M개의 조절 가능한 매개변수를 가게 된다.

  • 최대 가능도 방법을 이용하여 가우시안 클래스 조건부 밀도를 근사했다면 평균값에 대해서는 2M개, 공분산 행렬에 대해서는 M(M+1)/2개의 매개변수를 가지게 되었을 것이다.

  • 사전 분포까지 고려한다면 M(M+5)/2+1 개의 파라미터가 필요하게 된다.

  • 따라서 M이 클 경우 로지스틱 회귀 모델을 직접 다루는 것이 더 유리할 수 있다.

• 최대 가능도 방법을 통해서 로지스틱 회귀 모델의 매개변수를 구할 수 있다.

  • 이를 위해서는 로지스틱 시그모이드의 미분값을 구해야 하고, 자세한 증명은 생략하도록 한다.

    

• 가능도 함수를 다음과 같이 적어보자.

  

  • n=1,2,...,N에 대해 t_n={0,1}이고, ϕ_n=ϕ(x_n)이다.

  • 가능도 함수의 음의 로그값을 취하여 오류 함수를 정의한다.

    

  • 이러한 형태를 cross entropy error function이라고 한다.

• 이를 w에 대하여 오류 함수의 기울기를 계산하면 다음과 같다.

  

  • 로그 가능도 함수의 기울기를 위한 간단한 형태의 식이 된다.

• 원한다면 한 번에 하나씩 데이터를 추가하여 순차적인 알고리즘을 만들 수 있다.

• 선형적으로 분리 가능한 데이터 집합에 대해 최대 가능도 방법을 사용하면 심각한 과적합 문제를 겪을 수 있다.

4.3.3. IRLS(Iterative reweighted least squares)

• 가우시안 노이즈 모델을 선정하여 식을 모델링했고, 이 식은 닫힌 형태이므로 최적의 해를 구할 수 있다.

  • w에 대해 이차 종속성을 가지고 있었기 때문

• 하지만 로지스틱 회귀 모델의 경우에는 sigmoid 함수의 비선형성으로 인해 해가 닫힌 형태가 아니다.

  • convex 형태이므로 유일한 최솟값을 가지고 있다.

  • Newton-Raphson 방식으로 쉽게 최소화가 가능하다.

    

• 선형 회귀 모델과 제곱합 오류 함수에 대해 Newton-Raphson 방법을 적용해본다.

  

• 여기에 그래디언트와 헤시안을 적용하도록 한다.

  

• Newton-Raphson 업데이트 식은 다음과 같다.

  

• 이 결과값은 표준 최소 제곱 해에 해당하고, 오류 함수는 이차식이며, 한 단계만에 정확한 해를 구할 수 있다.

• 이제 이 업데이트를 cross-entropy 오차함수에 적용해 본다.

  

• 여기서 R은 N x N인 대각 행렬이다.

• 헤시안이 더 이상 상수가 아니며, 가중 행렬 R을 통해서 w에 종속성을 가지고 있음을 알 수 있다.

• y_n이 0과 1 사이의 수 라는 사실로 부터 H의 속성을 이해할 수 있다.

  • 임의의 벡터 u에 대해 u^THu > 0 을 만족한다.

  • 헤시안 행렬은 양의 정부호 행렬이고, w에 대한 볼록 함수이다.

• 로지스틱 회귀 모델에 대한 Newton-Raphson 업데이트는 다음과 같다.

  

  • 여기서 z는 다음을 원소로 가지는 N차원 벡터다.

    

• R이 상수가 아니고, 파라미터 w에 영향을 받는 요소이므로 이를 반복 업데이트 방식으로 풀어야 한다.

  • 따라서 IRLS라고 부른다.

• 이렇게 가중치가 부여된 최소 제곱 문제는 가중치 대각 행렬 R을 분산으로 생각할 수 있다. 로지스틱 회귀 모델에서 t의 평균과 분산은 다음과 같기 때문이다.

  

• IRLS는 변수 a = w^T ϕ에 대해 선형 문제를 가진다.

  

4.3.4 다중 클래스 로지스틱 회귀

• 다중 클래스 분류 문제를 다루는 생성적 모델에서는 선형 함수인 softmax가 사용한다고 이야기했다.

  

• 클래스 조건부 분포와 사전 분포를 따로 구하기 위해 MLE나 베이지안 정리를 사용해서 사후 확률을 찾았다.

  • 이를 바탕으로 간접적으로 매개변수 w_k를 구했던 것이다.

  • w_k를 직접 구하기 위해 y_k에 대한 미분값이 필요하다.

    

  • 여기서 I_kj는 단위 행렬이다.

• 가능도 함수에 대해 알아 본다. one hot encoding을 사용해서 표현하도록 한다.

  

  • 여기서 y_nk=y_k( ϕ_n)이고, T는 N x K인 행렬이다.

  • 음의 로그값을 취하면 다음과 같이 된다.

    

  • 이를 cross-entropy라고 부른다.

• 매개변수 벡터 w_j에 대해서 오류 함수의 기울기를 취해 본다.

  

• 선형 모델에 제곱합 오류 함수를 사용하였을 경우와 로지스틱 회귀 모델에 교차 엔트로피 오류 함수를 사용하였을 경우에 기울기 함수의 형태가 같다는 것을 확인할 수 있다.

4.3.5 프로빗 회귀

• 지금까지 클래스 조건 분포가 지수족으로 표현 가능하며 사후 분포를 로지스틱 함수로서 표현할 수 있다는 것을 보았다.

• 그러나 단순한 형태의 사후 확률이 모든 종류의 클래스 조건부 밀도 분포에 대해 결과로 나오는 것은 아니다.

  • 가우시안 혼합 분포를 이용하면 불가능하다.

• 다른 종류의 판별적 확률 모델을 살펴보도록 한다.

  • 2개의 분류 문제를 가진 일반화된 선형 모델의 틀을 유지한다.

    

  • 여기서 a=w^T ϕ 이고, 함수 f는 활성 함수(activation function)가 된다.

• 노이즈 임계값 모델을 고려해서 연결 함수를 선택할 수 있다.

  • ϕ_n을 a_n=w^Tϕ_n으로 계산한 후, 다음에 따라 표적값을 설정한다.

    

  • 여기서 θ 는 확률 밀도 p( θ )에서 추출된다면 활성 함수는 다음과 같이 기술할 수 있다.

    

    

• 여기서 파란색 곡선은 p( θ )로 두 개의 가우시안 함수의 혼합으로 이루어진다.

• 이에 해당하는 누적 분포 함수 f(a)는 붉은색 곡선으로 그려져 있다.

• 파란색 곡선 상의 녹색 수직선에서의 값은 같은 지점에서의 붉은색 곡선의 기울기와 같다.

• 이제 p( θ )를 표준 정규 분포로 생각한다면 식을 다음과 같이 기술할 수 있다.

  

• 이 함수를 역프로빗 함수라고 부른다.

  • 시그모이드 함수의 모양과 비슷하게 생겼으므로 일반적인 가우시안 분포를 사용해도 이 모델은 그대로 유지된다.

  • 오차 함수는 다음과 같이 정의된다.

    

  • 이 함수는 보통 erf 함수 또는 에러 함수라고 부른다.

    • 머신 러닝 모델에서 사용중인 오류 함수와는 다른 것이다.

• 이 오차 함수는 역프로빗 함수와 다음과 같은 관계를 가진다.

  

• 역프로빗 활성화 함수를 바탕으로 한 일반화된 선형 모델을 프로빗 회귀라 한다.

• MLE 방법을 이용하여 프로빗 회귀의 매개변수를 구할 수 있다.

  • 로지스틱 회귀와 비슷한 경우가 많다.

• 실제 응용 사례에서 문제가 될 수 있는 것은 outlier이다.

  • 입력 벡터 x를 측정할 때, 오류가 발생하거나 표적 벡터 t를 잘못 라벨링했을 때, 이상값 문제가 발생한다.

  • 이러한 데이터는 분류기를 심각하게 왜곡할 수 있다.

  • 로지스틱 회귀 모델과 프로빗 회귀 모델은 서로 다른 반응을 보인다.

    • 로지스틱 모델은 x가 문한대로 감에 따라서 exp(-x)와 같이 감쇠되는 반면, 프로빗은 exp(-x²)와 같이 감쇠되므로 더 예민하게 반응한다.

• 하지만 두 모델 모두 데이터는 모두 정확하게 라벨링되어 있다고 가정한다.

4.3.6 정준 연결 함수

• 가우시안 노이즈 분포를 사용한 선형 회귀 모델에서 에러 함수는 음의 로그 가능도 함수를 사용한다.

  

• 여기서 매개변수 벡터 w에 대해 미분하면 오륫값에 특징 벡터를 곱한 형태를 띠게 된다.

• 이 결과가 타깃 변수의 조건부 분포가 지수족에 포함되는 경우에 일반적으로 얻을 수 있는 결과이다.

  • 이 경우의 활성화 함수를 정준 연결 함수(canonical link function)라 한다.

• 입력 벡터 x에 대해 지수족 함수 분포를 가정했지만 여기서는 타겟 값 t에 대해 가정한다.

  

• 일반화된 선형 모델은 y가 입력의 선형 결합을 비선형 함수에 넣은 결과로 표현되는 모델이라 정의된다.

  

  • 여기서 f()가 활성 함수이며, f^-1()가 연결 함수다.

• η 의 함수로 표현되는 이 모델의 로그 가능도 함수를 고려해보자.

  

• 모든 관측값들이 동일한 척도 매개변수를 공유한다고 가정한다.

  • s는 n에 대해 독립적이다.

• 모델 매개변수 w에 대해 미분하면 다음과 같다.

  

• 여기서 a_n=w^T ϕ _n이고, y_n=f(a_n)이다.

  

• f( ψ (y))=y 이고, 따라서 f'( ψ ) ψ '(y)=1이다.

• 또한 a=f^-1(y) 이므로 a = ϕ 이고, 결국 f'(a) ψ '(y)=1이 된다.

  

Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

5. Model Free Control

• Model Free : MDP에 대한 정보가 없는 경우, 즉 environment에 대한 정보를 가지고 있지 않다.
• Control : value function을 최적화 하는 것, 즉 최적의 정책을 찾는 것

Model Free Control에서는 다양한 예제들이 있으며, 주로 다음 특징을 가지는 문제들을 해결한다,

• MDP를 모르지만, 경험을 sampling 할 수 있다.
• MDP는 알지만, sample들을 제외하고는 사용하기에는 너무 크다.

On Policy & Off Policy

• On Policy learning
  • "Learn on the job"
  • 학습하는 policy와 행동하는 policy가 같은 경우
    • ex)Sarsa
• Off Policy learning
  • "Look over someone's shoulder"
  • 학습하는 policy와 행동하는 policy가 반드시 같지 않아도 된다.
    • ex)Q-learning

On-Policy Monte-Carlo Control

• Generalised Policy Iteration

  

  • 3장에서 배웠던 내용으로 최적의 정책을 찾는 문제를 해결하기 위한 일반적인 방법론이다.
    • 임의의 정책으로 시작하여 value function을 추정하는 단계를 거친다.
    • 추정한 value를 바탕으로 정책을 발전시킨다.
    • 다시 맨처음으로 돌아간다.
    • 이는 EM 알고리즘과 같은 형태를 가지고 있다.
      • 따라서 Policy evaluation을 E단계, Policy improvement를 M 단계라 지칭한다.

• 4장에서 value function을 estimate 하는 방법들에 대해서 배웠는데 이를 E 단계에 적용해보도록 한다.

  • 하지만 그대로 적용한다면 다음과 같은 3가지 문제가 발생하게 된다.
    1. Value funcion의 model-based
    2. Local optimum
    3. Inefficiency of policy evaluation

1. Model-based

MC로 E단계를 수행하게 된다면 state value function을 사용해야 한다. 하지만 value function을 사용하면 M단계를 진행할 때 문제가 발생하게 된다. MC를 사용했던 이유가 Model-Free이기 때문이지만 value function으로 policy를 improve하려면 MDP의 model을 알아야 한다.

즉 위와 같이 reward와 state transition probaility를 알아야 한다. 즉 Model-based이어야 한다는 것이다.

따라서 이를 해결하기 위해서 value function을 action value function으로 바꾸게 되면 Model-Free 성질을 만족할 수 있다.

• return이 아닌 agent가 episode마다 random하게 움직이며 얻은 reward들 그리고 state transition prob.를 통해서 action-value function을 계산할 수 있다.

2. Local optimum

그러면 이제 Policy evaluation에서 value function을 action value function으로 바꾼다면 On policy MC를 사용할 수 있는 것일까? 다음 예시를 살펴보도록 한다.

• 두 개의 문이 내 앞에 있다.

  • 처음 왼쪽 문을 열었고, reward 0을 받았다.

    • V(left) = 0

  • 두번째에는 오른쪽 문을 열었고, reward 1을 받았다.

    • V(right) = +1

  • 세번째에 오른쪽 문을 열었고, reward 3을 받았다.

    • V(right) = +2

  • 네번째에 오른쪽 문을 열었고, reward 2를 받았다.

    • V(right) = +2

  • 그러면 지금까지 상황을 보았을 때 어느 문을 여는 것이 최선의 선택일까?

    • 아마도 이 네가지 상황으로만 본다면 오른쪽 문을 여는 것이 최선의 선택으로 보인다. 하지만 다음에 왼쪽 문을 열었을 때 reward를 100을 받을 수도 있는 것이다. 즉 지금 탐험과 탐사 trade-off에 빠지게 된 상황이다.

  • exploration(탐험) : environment에서 더 많은 정보를 알아내고자 하는 방법으로, 모든 행동을 할 때 일정 확률로 다른 곳으로 이동한다.

  • exploitation(탐사) : 알고 있는 정보를 바탕으로 보상을 최대화하고자 하는 것이다.

즉 지금 greedy 하게 improve 하는 것은 탐사에 빠지게 되는 것이다. 따라서 탐험을 어느정도 보장함으로써 model을 모르는 상황에서 더 좋은 성능을 낼 수 있을 것이다.

따라서 policy를 최적화 할 때 다음과 같이 일정한 확률을 부여해서 정하도록 한다.

3. Inefficiency of policy evaluation

하지만 MC 방법의 경우에 모든 episode들을 다 마친 후에 evaluation을 하면 너무 오랜 시간이 걸린다는 단점이 존재하게 된다. 따라서 이를 줄이기 위해서 매 episode들이 끝난 후에 policy evaluation을 수행하는 것으로 바꾸도록 한다.

즉 최종적인 On-Policy Monte-Carlo Control은 다음과 같다.

On- Policy Temporal-Difference Learning

TD가 MC보다 적은 variance를 가지고 online으로 학습가능하며, Incomplete sequence라는 장점들을 가지고 있기 때문에 control 문제에 적용해볼 수 있다.

Prediction에서 TD는 다음과 같이 표현을 했었다.

MC와 같은 이유로 value function을 사용할 수 없으므로 해당되는 부분들을 action value function으로 수정하도록 하자. 따라서 S에서 A 행동을 하면 보상 R을 받고 S'이라는 상태로 이동한다. 이 상태 S'에서 A'이라는 임의의 행동을 할 때의 action value function 값이 필요한 것이므로 다음과 같이 표현할 수 있다.

따라서 이를 앞부터 철자를 따서 Sarsa라고 부른다. Policy evaluation 부분에 MC 대신에 sarsa를 적용하면 다음과 같다.

n-step Sarsa

Sarsa가 애초에 TD의 개념에서 나온 것이므로 TD(λ)와 마찬가지로 Sarsa(λ)로 사용할 수 있다.

• forward view Sarsa(λ)

  • MC와 TD의 절충안이 n-step인 것처럼, 여러 개의 n-step을 선택하여 이의 평균을 취하면 각 n-step의 장점을 모두 가질 수 있게 된다. 이 때, 단순히 산술평균을 사용하는 것이 아니라 λ라는 weight를 이용해서 가중 평균을 취하도록하고 이를 Forward-view라고 한다.

  • episode가 모두 끝나야 계산이 가능하다. 따라서 TD의 장점을 많이 잃게 된다.

    

• backward view sarsa(λ)

  • 이제는 다시 forward-view TD(λ)에서 time-step마다 update할 수 있는 방법을 알아본다. 여기서 eligibility trace라는 개념이 나오게 된다. 이는 과거에 방문했던 state 중에서 현재 얻게 되는 reward에 영향을 주는 state를 판단해, 현재 얻게 되는 reward를 해당 state에 나누는 것이다.

    

Off- Policy learning

자신의 policy가 아니라 다른 사람의 policy를 통해서 학습을 하는 것이다. 이는 다음과 같은 관점으로 인해 중요하다.

1. 다른 agent를 관찰하는 것으로부터 배운다.
   • 다른 사람의 policy를(행동을) 따라 하는 것이 아닌, 경험만을 받아 학습해서 새로운 행동을 한다.
2. On policy의 경우에는 경험을 통해 policy를 업데이트를 했다면 사용한 경험은 버린다. 하지만 off policy는 이를 버리지 않고 재사용한다.
3. 탐험적인 행동을 하면서 최적의 policy를 찾을 수 있다.
4. 한 policy를 따르면서 여러 개의 policy를 학습할 수 있다.

Importance Sampling

X는 확률분포 P상에서 sampling 되는 것이고, Q는 P와 다른 확률분포를 의미한다. f(X)는 모든 함수를 넣을 수 있다. (f(X)=x, f(X)=3x...) 따라서 P를 따를 때의 f(X)의 기댓값을 구하고 싶은 것이다. 그런데 이를 이용해서 Q를 사용했을 때의 기댓값을 구하고 싶은 것이다.

이는 확률 분포 P와 Q의 비율을 곱해서 얻을 수 있는 것이다. 이를 Monte-Carlo에 적용해보자.

• Importance Sampling for Off-Policy Monte-Carlo

  • Monte Carlo를 수행할 때, 지나온 모든 행동들에 대해서 비율을 곱해준다.

  • 하지만 µ가 0이면 되면 사용할 수 없고, variance가 엄청 크기 때문에 사실상 사용할 수 없다.

• Importance Sampling for Off-Policy TD

  • 따라서 MC의 단점을 보완하기 위해서 TD를 사용하도록 한다.

Q-learning

Importance learning을 하지 않으면서 off-policy를 사용하기 위한 방법이다. 다음 행동은 behavior policy로 고르고, 다음 state S'에서 action A'은 target policy를 통해서 선택하는 것이다. 즉 다음과 같이 q-function이 업데이트가 된다.

Off-policy control with Q-learning

Q-learning에서는 behavior policy와 target policy를 동시에 improve 할 수 있다. Q-learning에서는 behavior policy μ는 ε-greedy로 target policy π는 greedy하게 선택하도록 한다. 각각 수렴 속도가 느리고, local optima에 빠질 수 있다는 단점을 해결하기 위해 적용된 절충안이다.

따라서 이제 다음과 같이 Q-learning이 진행된다.

1. 현재 state S에서 behavior policy μ( ε-greedy)에 따라 action A를 선택한다.

2. q-function을 이용해서 다음 state S'에서의 action A'은 π(greedy)에 따라 선택한다.

   

3. Q-learning의 target은 다음과 같이 구한다.

4. 다음과 같이 최종 update를 수행한다.

   

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

4. 선형 분류 모델

• 지금까지는 회귀 문제에 대해서만 다루어 보았지만 이번엔 분류 문제에 대해서 다루어 보도록 한다.

• 분류는 입력 벡터 x를 받았을 때 대응되는 클래스에 속하도록 하는 작업이다.
  • 이 때 클래스는 K개로 C_k 로 표기한다.
  • 하나의 데이터는 하나의 클래스에만 속하며, 하나의 클래스는 다른 클래스를 포함하지 않는다.
  • 이렇게 나누어진 영역을 decision region이라고 부르며 나누는 경계면을 decision boundaries라고 부른다.

4.1 판별 함수

4.1.1 두 개의 클래스

• 선형 판별식의 가장 간단한 형태를 다음과 같다.

• 여기서 w는 가중치 벡터라 부르고, w₀은 bias라고 부른다. 회귀랑 동일하다.

• 보통 2개의 클래스를 분류하는 문제에서 y(x)>=0인 경우를 C1으로 분류하고, 아닌 경우를 C2로 분류한다.

  • 이 때 decision boundaries는 y(x)=0임을 알 수 있다.

• 이제 임의의 두 점 x_A, x_B가 이 경계면 위에 있다고 하자.

  • 이 때 y(x_A)=y(x_B)=0를 만족하고, w^T(x_A−x_B)=0다. 여기서 w는 결정 경계에 대해 수직임을 알 수 있다.

  • 결정 경계에서 식을 전개하면 다음의 식을 얻을 수 있다.

    

• 이제 D=2라고 할 때 그림을 살펴본다.

  

• 임의의 한 점 x에 대해 결정 경계면에 수직으로 내린 지점을 x_ㅗ라고 하자.

• 이 경우 다음과 같은 식이 성립한다.

  

• 3장에서와 비슷하게 x₀=1를 이용하자.

  

• 위와 같이 간단하게 적을 수 있다.

4.1.2 다중 클래스

• K > 2인 상황을 다중 클래스라고 부른다.

  • 이 문제를 2-class 문제를 여러 개 조합해서 해결할 수 있다.
  • K-1개의 2-class 분류기가 있으면 K개의 클래스를 분류 가능하다.

  

• 왼쪽 그림을 보면 3개의 클래스를 분류하기 위해 2개의 2-class 문제를 사용하였다. 하지만 녹색 영역과 같이 판정을 할 수 없는 부분이 생기게 된다.

• 또한 만약 K(K-1)/2 개의 분류기를 사용해서 분류를 한다면 오른쪽과 같다.

  • 이 경우에도 녹색 영역과 같은 애매한 부분이 생긴다.

• 이 문제를 해결하기 위해 다른 방법을 사용한다.

  

• j != k일 때, y_k(x)>y_j(x)를 만족하면 x를 클래스 C_k로 판별하자.

  • 그러면 두 클래스 간의 decision boundaries는 y_k(x)=y_j(x)에서 형성된다.

  • 이 때 식을 전개하면,

    

  • 2-class 문제에서 사용하던 것과 같다.

• 이러한 판별 함수의 결정 경계는 언제나 단일하게 연결되어 있으며 볼록 성질을 가진다.

  • 모두 하나의 선으로 연결되어 있고, 내부의 어느 각도 180도를 넘지 않는다는 것과 같다.

  • 이를 확인할 수 있다.

    

    • x_A,x_B는 같은 지역의 임의의 두 점이다. x는 두 점 사이에 위치한 임의의 한 점을 나타내고, λ 는 0과 1 사이의 값이다.

      

    • y_k(x_A)>y_j(x_A) 이고 y_k(x_B)>y_j(x_B)이므로 y_k(xˆ)>y_j(xˆ)가 된다. 즉 아래 그림과 같다.

      

4.1.3 분류를 위한 최소 제곱법

• 최소제곱법을 사용해서 분류 문제를 해결해보자.

  • 사실 그리 정확하진 않다.

• 판별식은 다음과 같이 정의하고 간단히 정리하는 것이 가능하다.

  

• n번째 행이 t_n^T인 행렬 T와 n번째 행이 x

  _n^T라 하면, 전체 샘플 데이터를 X

  로 정의할 수 있다.

• 최소제곱법을 다음과 같이 적는다.

  

  • Tr은 행렬의 trace를 의미하며, trace는 행렬의 대각성분 합을 의미한다.

  • W에 대해 미분하고 정리하면 다음과 같다.

    

  • X^† 는 pseudo-inverse 행렬이다.

• 모든 훈련 집합의 표적 벡터들이 식 4.18의 선형 제약 조건을 어떠한 a와 b 값에 대해서 만족한다면 x 값에 대한 모델 예측값이나 제약 조건 4.19를 만족한다.

  

  

• 원 핫 인코딩을 통해 얻은 예측값들은 어떤 x의 경우에든 y(x)의 원소들을 전부 합하면 1이 된다.

  • 하지만 (0,1) 범위 내 안이라는 조건은 없으므로 확률값이라고 할 수 없다.

• 문제는 최소 제곱법은 outlier에 대해 너무 민감한 성질을 보인다. 따라서 더 강건한 모델을 고를 필요가 있다.

  

  • 녹색선은 로지스틱 회귀 분석으로 얻은 경계선, 보라색 선은 최소 제곱법을 사용한 것이다.
  • 보라색선은 우측의 그림처럼 outlier가 존재할 때 잘 분류하지 못하는 것을 알 수 있다.

4.1.4 피셔의 선형 판별

• 2-class 문제로 접근을 한다.

• D차원의 입력 벡터 x를 일차원에 투영한다고 해보자. 식은 다음과 같다.

  

• 이 식은 임의의 한 벡터를 한 차원의 벡터 위의 한 점(스칼라 값)으로 변환해준다.

• y에 임계값을 추가해 클래스를 분류하도록 한다.

• 높은 차원을 낮은 차원으로 줄였기 때문에 정보 손실은 당연하다.

  • 그렇기 때문에 정보 손실을 적게 하도록 해야 한다.

• w에 투영되었을 경우에 클래스 간의 분리 정도를 측정할 수 있는 가장 쉬운 방법은 투영된 클래스의 평균들이 얼마나 분리되어 있는가를 보는 것이다.

  

• 각 클래스의 평균을 나타내는 벡터를 표기할 수 있다.

• 이 값을 가지고 두 클래스간의 거리가 최대화되도록 하는 식을 전개한다.

• 1차원의 벡터로 투영된 후의 값은 다음과 같다.

  

• w를 찾아야 하는데, w 값만 무한정 커지면 값이 커지므로 단위 벡터로 고정을 한다.

• 이 식에 라그랑주 승수법을 적용해서 최소값을 구하면 w는 (m₂-m₁)에 비례한다.

• 왼쪽이 지금까지 한 방법인데 상당히 중복되는 것을 볼 수 있다. 이는 클래스 분포가 심한 비대각 공분산을 가지고 있기에 생긴다.

• 피셔의 제안은 투영된 클래스 평균 사이의 분리 정도를 크게 하는 동시에 각 클래스 내의 분산을 작게 하는 함수를 최대화함으로써 클래스 간의 중복을 최소화하는 것이다.

• 따라서 분산도를 정의한다.

  

• 여기서 y_n=w^Tx_n이다. 이 식은 투영 후 점들의 분산도를 의미한다.

  

• 최종 피셔 판별식은 위와 같으며, 정리하면 다음과 같은 식을 얻게 된다.

  

  • S_B는 클래스 간 공분산 행렬을 의미하고, S_W는 클래스 내 공분산 행렬을 의미한다.

    

  • J(w)를 w에 미분하면 최종적으로 위와 같은 식을 얻게 된다.

4.1.5 최소 제곱법과의 관계

• 에러 함수를 정의해본다.

  

• E는 w₀와 w에 대해 각각 미분하고 그 값을 0으로 설정하면 다음의 식을 얻게 된다.

  

• t_n은 다음과 같다.

  

  • N₁,N₂은 각 클래스에 속한 샘플 수를 의미하고 N은 전체 샘플 수를 의미한다.
  • C₁ = N/N₁, C₂=N₂

• m은 전체 데이터 집합의 평균이다.

  

• 4.32식에 x_n을 곱하고 전개하면 다음과 같다.

  

• 최종적으로 다음과 같으면 피셔 판별식과 동일하다.

  

4.1.6 다중 클래스에 대한 피셔 판별식

• 이제 K의 값이 2보다 큰 경우 피셔 판별식을 적용해보자.

  • 단 K<D임을 가정하자.

• D차원을 더 낮은 차원으로 변환하는 식을 아래와 같이 기술한다.

  

• W의 컬럼 개수는 D'로 정의한다. 당연히 D'의 값은 D보다 작다.

• 클래스 내 공분산 행렬

  • 앞서 살펴본 S_W를 K개의 클래스 버젼으로 확장한다.

  • N_k는 클래스 C_k에 속한 샘플의 수 이다.

    

• 클래스 간 공분산 행렬

  • 클래스 사이의 분산이 아닌 전체 데이터에 대한 공분산 행렬을 정의한다.

  • N은 전체 샘플 합계 : N=sum to k N_k

  • m은 전체 평균

    

  • 이 때 클래스 간 분산과 클래스 내 분산으로 나눌 수 있다.

  • 즉, S_T로 부터 S_W를 제외한 나머지를 S _B라고 정의한다.

    

  • 이 공분산 행렬들은 x 공간상에서 정의되었다. 행렬들을 투영된 D'차원의 y 공간상에서 정의해보자.

    

  • 에러 함수 만들 때, 여러 가지 선택지가 있지만 Fukunaga의 방법을 선택한다.

    

  • 투영 행렬 W에 대한 명시적인 함수로 다음과 같이 다시 적는다.

    

    • 이 기준을 최대화 하는 것은 어렵지 않지만 노력이 필요해서 Fukunaga에 설명되어 있다고 한다.

4.1.7 퍼셉트론 알고리즘

• 2-class에 대해 간단하게 알아보자.

  

• 활성 함수로 가장 간단한 형태인 계단형 함수를 쓴다.

  

• 여기서 ϕ ₀(x) = 1 이다. 표적값은 0,1 이 아닌 +1, -1로 정의해서 사용한다.

• 퍼셉트론에서 매개변수 w를 구하기 위한 알고리즘도 오류 함수를 최소화하는 방식이다.

  • 오분류된 패턴의 총 숫자를 오류 함수로 고를 수 있지만 사용하지 않는다.

    • 학습 알고리즘이 복잡해진다.
    • 오류 함수가 w에 대해 조각별 상수 함수다. w에 대한 변화가 결정 경계를 데이터 포인트들 중 하나를 건너 이동하게 하는 곳에서 불연속성이 발생한다.
      • 따라서 이 경우에 함수의 기울기를 통해서 w를 변경시키는 방법을 사용할 수 없다.

  • 따라서 퍼셉트론 기준이라는 오류 함수를 사용한다.

    

• 클래스 C₁에 대해서는 w^T ϕ (x_n) > 0이 되고, C₂는 w^T ϕ (x_n) < 0 을 만족하는 w를 찾고자 한다.

• 에러를 최소화 하는 방향으로 식을 전개해야 하므로 기울기 방법으로 w를 만들 수 있다.

  

  • η : 파라미터 학습 비율
  • τ : 알고리즘 스텝 인덱스

  

• 퍼셉트론의 동작 방식을 잘 설명하고 있는 그림이다.

  • 녹색 점이 오분류된 점인데 그에 따라 빨간색 방향만큼 보정이 된다.
  • 보정을 하고 난 뒤 다시 오분류된 점을 찾아 보정을 하는 작업을 계속해서 거치면 결정 경계가 완성된다.

• 아래 식을 통해 업데이트를 진행하면 에러가 점점 줄어든다는 것을 알 수 있다.

  

• 퍼셉트론 수렴 법칙(Perceptron convergence theorem)

  • 정확한 해를 가지고 있기만 한다면 퍼셉트론 학습 알고리즘은 정확한 해를 유한한 단계 안에 확실히 구할 수 있다.
    • 훈련 집합이 선형적으로 분리가 가능해야 한다.
  • 하지만 수렴을 위해 필요한 단계의 수가 매우 많을 수 있다.
    • 분리가 불가능한 문제인지, 단순히 수렴하는 데 오랜 시간이 걸리는 문제인지 구별이 불가능

• 퍼셉트론은 출력 값이 확률 값이 아니다.

• 중요한 제약 중 하나는 고정된 기저 함수의 선형 결합을 기반으로 한다.

Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

Model Free Prediction

• Model Free : MDP에 대한 정보가 없는 경우, 즉 environment에 대한 정보를 가지고 있지 않다.

• Prediction : value function을 학습하는 것

즉 Model Free Prediction은 MDP에 대한 정보가 없을 때 value function을 학습해야 하는 문제이고, 다음 장에서 Model Free Control에 대해서 알아보도록 한다.

이번 강의에서 소개한 Model Free Prediction 방법으로 크게 Monte-Carlo Learning(MC), Temporal-Difference Learning(TD)가 있다.

Monte-Carlo Learning

몬테 카를로 방법(다음 부터 MC라 부른다.)은 episode들로 부터 직접적으로 학습한다. 즉 모두 종료가 되는 episode들의 return의 평균을 통해서 학습을 진행한다는 것이다. 그러므로 MC는 완전한 episode들로 부터 학습을 하며 이를 no bootstrapping(추측치로 업데이트 하기)이라고 부른다.

• Goal : Prediction 문제이므로 policy는 π로 정해져 있고, 이를 통해 나온 episode들을 통해 vπ 를 학습하는 것

• return은 Gt=Rt+1+γRt+2+ ... + γT−1RT 와 같이 정의 했으며 vπ(s) = Eπ [Gt | St = s] 로 정의했었다.

MC 방법은 state들을 방문한 것을 바탕으로 다시 크게 First와 Every로 나뉘게 된다.

First- Visit MC Policy Evaluation

terminate까지 도달하기 위해서 state들을 여러번 방문할 수 있는데, , 이때 해당 state에 처음 접한 후 얻은 return 값의 평균을 사용하여 구한다.

Every-Visit MC Policy Evaluation

First와는 달리 state들을 방문할 때마다 return을 계산하고 이를 평균을 내는 방식이다. 보통 first-visit을 사용한다고 한다.

Incremental mean

평균을 구하는 식은 다음과 같이 현재의 값을 뺀 평균의 식으로 바꿀 수 있게 된다. 이를 통해 incremental update를 할 수 있게 된다.

따라서 이를 이용해서 MC 방법에서 V를 계산하는데 사용할 수 있다.

N(S)는 episode를 수행한 횟수에 해당하며 에피소드를 수행하고 나서 v(s)를 바로바로 추정가능하게 된다.

non-stationary 문제의 경우에는 평균을 낼 때 이전의 횟수를 사용하는 것이 아니라 일정한 값인 a로 고정해서 계산을 한다.

Temporal-Difference Learning(TD)

TD방식도 episode들로 부터 직접적인 경험을 하면서 학습을 하는 알고리즘이며 model-free에서 사용한다. 하지만 MC와는 다르게 episode들이 완전히 끝나지 않아도 학습이 가능하며 DP에서 사용하던 bootstrapping 방법을 사용한다. 즉 MC방법과 DP 방법을 적절히 조합한 아이디어라고 할 수 있다. 그리고 추측치에서 다음 추측치를 추정함으로써 업데이트가 가능하다.

MC vs TD

MC와 TD에서 가장 다른 부분은 return Gt이다. MC에서는 종료가 된 episode들로 부터 학습을 하기 때문에 정확한 Gt값을 알 수 있다. 하지만 TD는 그렇지 않기 때문에 return Gt를 추정한 값을 사용해야 한다. 따라서 TD(0)이라고 가정했을 때(뒤에서 이 용어에 대해 자세히 설명한다.),Gt 에 해당하는 부분을 Rt+1+γV(St+1)로 바꿔서 사용하도록 한다.

• 빨간색 term을 TD target이라고 부르고, a 뒤에 있는 항을 TD error라고 부른다고 한다.

TD는 final outcome이 나오기 전에 학습을 할 수 있지만 MC는 결과가 나올 때까지 기다려야 한다. 하지만 TD는 바로바로 학습을 하지만 이 episode가 실제로 종료될 것이라는 보장이 없고, MC는 애초에 끝난 결과를 가지고 학습하므로 확실히 종료된다는 보장을 가지고 있게 된다.

Bias/Varaince Trade-off

v가 실제 Gt에 대해서 unbiased하다고 하면 TD target도 unbiased하다고 할 수 있다. 하지만 TD target은 추정치인 V(St+1)를 사용하기 때문에 bias가 생길 수 밖에 없다.

대신 TD target은 하나의 step에서 계산을 하기 때문에 작은 variance를 가지게 된다. 반면 MC는 episode가 어떤 state sequence로 이루어졌는가에 따라서 value function이 달라지기 때문에 variance가 높게 된다.

즉 종합해보면 MC는 높은 variance를 가지지만 bias가 아예 존재하지 않는다.(정확히 구해진 값들을 사용하기 때문에) 따라서 좋은 수렴 조건을 가지고 있으며, 초기값에 영향을 받지도 않는다.

TD는 낮은 variance를 가지고 있지만 bias가 생기게 된다. 보통 MC보다 더 효과적이고 TD(0)은 수렴을 하지만 항상 그렇다고 볼 순 없다. 또한 초기값에 영향을 받게 된다.

Batch MC and TD

MC, TD 방식 모두 episode를 무한하게 반복하면 실제 value에 수렴할 수 있다. 하지만 batch 방식으로 유한한 episode들을 가지고 학습을 하면 어떻게 될까?

위 예시를 통해서 살펴보도록 한다. 이 예시에서는 8개의 episode들이 있고, 첫번째 episode에서는 A가 reward 0을 받고, B로 가서 reward 0을 받게 된다. 2~7번째 episode들에서는 B에서 reward 1을 받고, 마지막엔 0을 받게 된다.

즉 위 내용을 종합해보면 A는 100% 확률로 B로 가게 될 것이고 이 때 return은 0이 될 것이다.

그러므로 MC에서는 A는 1번 episode에서만 나타나고 이 때 최종 보상이 0이기 때문이다. TD에서는 다른 episode들이 진행이 되면서 A의 value도 같이 업데이트가 될 것이다.

MC는 최종적으로 완료한 episode들의 보상을 사용해서 학습을 하므로 V(A) = 0이 되었다. TD(0) 방식은 max likelihood Markov 방식을 사용하여 수렴하는 알고리즘이기 때문에 V(A) = 0.75가 된다.

이를 보아 TD는 MDP 특성을 가지는 알고리즘이므로 MDP 환경에서 더 유용하고, MC는 그렇지 않기 때문에 MDP가 아닌 환경에서 더 유용하게 된다.

다음은 backup과 bootstrapping에 따른 RL의 분류이다.

TD(λ)

지금까지 설명한 TD들은 TD(0)에 해당하는 것들이었다. 이제 이를 확장해서 TD(λ)로 사용하도록 한다. TD는 guess로 guess를 예측하는 것인데, λ는 steps들에게 얼만큼의 가중치를 부여할지에 대한 값이다. 즉 수식으로 표현하면 다음과 같다.

n=1에 해당하는 것이 우리가 지금까지 보았던 TD(0)에 해당한다. n=2는 G⁽²⁾t와 같이 표현이 될 것이다. 그리고 n이 무한대까지 간다면 이는 종료가 될 때까지 진행한다는 것과 같으므로 MC와 같아지게 된다.

따라서 적당한 n을 잘 선택할 수 있으면 TD와 MC의 장점을 모두 취할 수 있게 된다.

n step에서 n을 고르는 방법은 크게 두 가지 방법이 있다.

• Forward-view TD(λ)

  • MC와 TD의 절충안이 n-step인 것처럼, 여러 개의 n-step을 선택하여 이의 평균을 취하면 각 n-step의 장점을 모두 가질 수 있게 된다. 이 때, 단순히 산술평균을 사용하는 것이 아니라 λ라는 weight를 이용해서 가중 평균을 취하도록하고 이를 Forward-view라고 한다.

    

• Backward-view TD(λ)

  • 이제는 다시 forward-view TD(λ)에서 time-step마다 update할 수 있는 방법을 알아본다. 여기서 eligibility trace라는 개념이 나오게 된다. 이는 과거에 방문했던 state 중에서 현재 얻게 되는 reward에 영향을 주는 state를 판단해, 현재 얻게 되는 reward를 해당 state에 나누는 것이다.

  • 이 때, 영향을 준 것 같은 idx를 credit이라고 하고, 이 credit을 배정할 때 다음 두 개를 사용한다.

    • Frequency heuristic, Recency heuristic