Chapter 1. Motivation and Basics

Motivation
- Machine Learning, AI, Datamining
What is Machine Learning?
- MLE
- MAP
Basics
- Probability
- Distribution
- And some Rules

1-1. Motivation

Machine Learning에는 학습 방법에 따라 supervised learning, unsupervised learning, reinforcement learning 이 있다. 먼저 supervised learning에는 요약하거나 예측과 같은 것들이 이에 해당하고, 요약하고 정리하고 군집을 찾는 것이 unsupervised learning에 해당한다. 마지막으로 어떤 것이 지능적이고, 원하는 계획인가에 대한 학습이 reinforcement learning이다.

더 자세하게 살펴보자.

supervised learning

사람이나, 기계가 지정한 가이드가 있는 것이 supervised라 할 수 있다. 예를 들어, 스팸 필터링은 매우 많은 데이터들에 의해 어떤 것을 필터링할지 판단한다. 또한, 자동 카테고리화도 수많은 데이터의 축적에 의해 분류하는 모델을 생성하는 것이다.

또는, 특정 값에 대해 가격을 예측하는 것과 같은 것들은 regression, 또는 prediction 도 supervised learning task에 해당한다.

unsupervised learning

그에 반해, 순수히 주어진 데이터에 의해 기계가 군집을 찾고, 패턴을 찾도록 하는 것이 unsupervised learning이다. 또는 잠재적인 현상을 분석할 때도 활용한다. 예를 들어 신문기사가 엄청 많을 때, 주제를 10개로 추려보는 것은 직접 가이드를 제작해주기 힘들어서, 기계가 직접 군집을 찾아야 하므로 unsupervised learning에 해당한다.

1-2. What consists of Machine Learning?

Thumbtack, 압정을 활용하여 게임을 해보자. 동전과 달리, 압정은 앞과 뒤가 50:50이라 하기 어렵다. 그래서 앞 또는 뒤가 나올 확률을 직접 구해보고자 한다. 가장 먼저 해야 할 방법은 직접 던져보는 것이다.

뾰족한 부분이 아래일 때를 Head, 뾰족한 부분이 위일 때를 Tail 이라 하고, 5번을 던져봤을 때 Head가 2번 Tail이 3번 나온다면, 확률은 각각 2/5, 3/5 인 것은 당연한 결과다. 그러나 이 2/5, 3/5라는 값은 사실 그리 간단하게 구해지는 것이 아니다.

이 2/5, 3/5로 구하는 것은 Binomial distribution이라 하는데, 이는 뚜렷한, 이산적인 사건에 대한 확률 분포를 말한다. 즉, Head가 나오든, Tail이 나오든 2가지의 경우만 존재하므로 Binomial distribution이라 한다.

먼저 head가 나올 경우, 다음에 Tail이 나올 때 앞서 나온 값이 영향을 주지는 않으므로 독립적인 상황이다. 만약 Head가 나올 경우를 P(H) = Theta, Tail이 나올 경우를 P(T) = 1 - Theta 라 하자. 이럴 때, 방금 전 상황인 HHTHT에 대한 확률은 $ P(HTTHT) = \theta (1-\theta) (1-\theta) \theta (1-\theta) = \theta^2 (1-\theta)^3 $ 이다. 전체 Data를 D, Head가 나온 횟수를 a_H, 반대의 경우를 a_T라 한다면 theta, 즉 head가 나올 확률은 다음과 같다.

\[P(D | \theta) = \theta^{a_H}(1-\theta)^{a_T}\]

이러한 추정값이 최적의 $ \theta $ 라는 것을 증명해야 하는데, 이를 증명하는 것이 확률이라 할 수 있다. 이를 증명할 때 사용하는 대표적인 방법에는 MLE, MAP이 있다.

MLE(Maximum Likelihood Estimation)

관측된 데이터의 확률이 최대가 되는 값 theta를 찾는 방법이 MLE이다. MLE를 수식적으로 나타내면 다음과 같다.

\[\hat{\theta} = argmax_{\theta} P(D|\theta)\]

즉, P(D|theta)가 최대가 되는 theta를 theta hat이라 표현한다는 것이다. 여기에 위에서 구한 식을 대입하면

\[\hat{\theta} = argmax_{\theta} P(D|\theta) = argmax_{\theta} \theta^{a_H}(1-\theta)^{a_T}\]

이를 구할 때, 쉽게 구하는 방법은 log를 씌우는 것이다. log를 씌운 값이 최대가 되면, 그 log 안의 값도 최대가 된다는 특성이 있다.

\[\hat{\theta} = argmax_{\theta} ln\theta^{a_H}(1-\theta)^{a_T} = argmax_{\theta} (a_H ln\theta + a_T ln(1-\theta))\]

그 후, 미분을 통해 최솟값을 찾는다. 그러면 theta_hat = a_H / (a_T + a_H) 가 된다.

그런데, 만약 5번이 아닌 50번을 수행해서 동일하게 head가 나올 확률이 0.6이 나온다면, 효율상 5번이 더 좋다고 생각할 수 있다. 여기에는 조금의 오류가 존재한다. 우리가 이때까지 구한 것은 정답(Ground Truth)이 아니라 추론(estimation)값이므로, 오류가 항상 존재한다. 정답인 $ \theta* $ 와 $ \hat{\theta} $ 사이의 오차값과 error boundary($ \epsilon $) 에 대한 수식이 있다.

\[P(|\hat{\theta} - \theta*| \geq \epsilon) \leq 2e^{-2N\epsilon^2}\]

정답과 추론의 차이가 특정 에러보다 클 확률은 우항보다 작다는 것이다. N은 trial, 즉 반복횟수인데, N이 커질수록 우항은 작아지므로 오차가 특정 error boundary보다 클 확률도 작아지게 될 것이다.

이러한 방식이 PAC(Probably Approximate Correct)이라 하는데, 즉 아마도 특정 확률과 오차범위 안에서 존재하는 theta를 추정하는 기법이다.

MAP

MLE에서 구한 확률은 사전정보가 포함되어 있지 않다. 그러나 만약 사전정보를 가미하여 확률을 구하고자 한다면 다른 방식을 통해 구해야 할 것이다. Bayes라는 학자는 다음과 같이 확률에 대한 식을 정의했다.

\[P(\theta | D) = \cfrac{P(D | \theta)P(\theta)}{P(D)} \: == \: Posterior = \cfrac{Likelihood \: x \: Prior \: Knowledge}{Normalizing\:Constant}\]

theta가 주어졌을 때 data를 관측할 확률 x theta에 대한 사전정보 / 데이터를 관측할 확률 를 하면 데이터가 주어졌을 때 theta의 확률을 구할 수 있다. 이 떄 우리는 theta에 대해 구하고 있으므로, P(D)는 상수가 된다. 그리고 P(D|theta)는 이전에 구했으므로 P(theta)만 지정해둔다면 p(theta|D)를 구할 수 있다.

또한, Bayes는 P(theta)를 binomial distribution이 아닌 Beta Distribution을 통해 구하고자 했다.

\[P(\theta) = \cfrac{\theta^{\alpha-1}(1-\theta)^{\beta-1}}{B(\alpha,\beta)},\: B(\alpha,\beta) = \cfrac{r(\alpha)r(\beta)}{r(\alpha+\beta)},\:r(\alpha) = (\alpha - 1)!\]

이 때, B(alpha, beta)는 theta와 관련이 없으므로 상수 취급할 수 있다. 그렇다면, P(theta|D)는

\[P(\theta|D) \propto P(D|\theta)P(\theta) \propto \theta^{a_H}(1-\theta)^{a_T} \theta^{\alpha-1}(1-\theta)^{\beta-1} = \theta^{a_H+\alpha-1} (1-\theta)^{a_T+\beta-1}\]

이 식은 P(D|theta) 와 유사한 것으로 보아, theta_hat은 쉽게 추정할 수 있다.

\[\hat{\theta} = \cfrac{a_H+\alpha-1}{a_H+\alpha+a_T+\beta-2}\]

이 때, MLE와 MAP의 값이 다를 수 있다. 그러나 만약 반복 횟수를 증가시킨다면, alpha와 beta에 비해 a_H와 a_T는 증가하여 비중이 커질 것이므로 같아질 수 있다.

1-3. Basics

Normal Distribution

가장 많이 사용되는 기본적인 확률분포의 형태이다. 이 평균(mean) 또는 분산(variance)를 통해 함수의 모양을 바꿀 수 있을 것이다. Normal distribution에는 양쪽에 롱테일, 즉 무한대로 가는 긴 꼬리가 존재한다.

Beta Distribution

beta에서는 롱테일이 존재하지 않는다. 따라서 확률을 모델링할 때 0과 1이라는 확실한 범위가 존재하므로 beta distribution을 사용할 수 있다.

Binomial Distribution

이 binomial distribution은 앞서 배운 함수 형태를 가지고 있고, 이산적인(discrete) 함수 형태를 가지고 있다.

Multinomial Distribution

binomial distribution은 2가지의 경우만 판단하지만, 만약 2가지 이상의 선택지가 존재한다면 더 다양한 예제를 판단할 수 있어야 한다. 대화를 할 때, 수많은 단어 중 하나를 선택하므로 수많은 데이터를 가진 이산적인 함수를 사용한다.

Chapter 2. Fundamentals of Machine Learning

classical method overview
- rule based approach
- classical statistics approach
- information theory approach
rule based machine learning
- how to find generalized rules
decision tree
- how to create decision tree
- weakness of decision tree given new dataset
linear regression
- how to infer a parameter set

2-1. Rule Based Machine Learning Overview

perfect world라고 가정해보자. 즉 관측에 대한 에러가 존재하지 않고, 관측한 정보가 전부라 가정하는 것이다. 이러한 상황에서 날씨에 대해 관측하여 밖으로 나가 운동을 할지에 대한 태스크를 진행한다.

function approximation

function approximation이란 몇 개의 데이터가 있을 때, 어떤 함수에 입력하면 나오는 결과가 정답인 함수를 추정하는 것이다. 그래서 머신러닝이란 더 나은 함수를 생성하는 기법이 된다.

데이터의 개수, instance,X 가 존재하고, 그 instance에 대한 feature가 O=<Sunny, Warm, Normal, Strong, Warm, Same> 이라는 값을 가지고, 원하는 정답인 Y=yes 라 해보자. 이러한 instance가 여러 개 존재할 때, dataset D가 될 것이다. 데이터를 통해 가설, H를 세워 X를 집어넣을 떄 Y가 나오는 함수를 생성할 수 있다. 예를 들어 sunny, warm, same만 일치한다면 나머지에는 상관없이 yes라는 Y를 출력하는 h_i를 가정할 수 있다. 이는 가설한 것이므로 수많은 가설이 존재할 수 밖에 없다.

그리고, 우리가 진짜 원하는 함수인, target function, c 가 있다면, 항상 c(X) = Y라는 식이 참이 된다. 이 c는 알 수 없으므로 추론하여 알아내야만 한다. 그래서 데이터의 개수가 많을수록 우리가 원하는 정답인 Y를 정확하게 추출할 수 있게 된다.

그래서 instance가 x1,x2,x3가 있고, instance에 대한 가설인 h1,h2,h3가 있다고 해보자. 그렇다면, 가설이 정확한지 아닌지를 판단하기 위해서는 h1,h2,h3에 각각의 instance를 집어넣어 정답이 잘 추론되었는지 역계산해야 한다. 위의 h1,h2,h3를 살펴보면, h1은 x1,x2,x3가 모두 yes라는 값을 추출하는 가설이 되고, h2와 h3는 각각 2개씩만 yes라는 값을 추출하는 가설이다. 그러면 h1은 다소 일반적인 가설이므로 generalized function이라 할 수 있고, h2와 h3는 h1보다 specificed function이라 할 수 있다.

Find-S Algorithm

그래서 정답의 가설인 c를 잘 추론하기 위한 알고리즘으로 Find-S 라는 알고리즘이 있다. 이 알고리즘은 먼저, 가장 specific한 가설인 H = <None, None, None, None, None, None> 라는 H를 세운다. 그 후 각 instance마다 각 feature들을 현재의 가설과 비교하여 업데이트한다.

  
if x is positive
  For feature in O
    if h_i in H == feature_i
      pass
    else
      update to more generalize

처음에는 모두 None이었다가 x1에 의해 H에 있는 모든 feature들을 업데이트하고, 다음 x2에서 각 feature들과 H에 있는 feature들을 비교하여 같지 않으면 둘다 포함이 되도록 업데이트한다.

이러한 방법으로 하면 가설을 확정지을 수는 있지만, 만약 이렇게 나온 h1,2,3,4가 정답과 다를수도 있을 것이다. 그래서 생각한 방법이 범위를 정하여 그 범위 안에 존재하는 가설은 모두 정답의 후보라 할 수 있게 하는 알고리즘을 생각했다.

Version Space

VS(Version Space)란 가능한 가설의 집합을 나타내고, 이를 구하기 위해서 가장 일반적인 가설과 가장 구체적인 가설을 정의하여 범위를 좁혀나가는 Candidate Elimination Algorithm을 사용해보고자 한다. 일반적인 가설을 G, 구체적인 가설을 S 라 하고, dataset에 포함되어 있는 각 instance마다 값을 비교해나가며 업데이트한다.

  
if y of x is positive
  # update first S, before G

if y of x is negative
  # update first G, before S

y값이 참이라고 한다면, S의 범위를 x에 존재하는 feature들을 커버할 수 있을만큼만 일반적으로 업데이트해야 하는데, 만약 G에 대해 거짓이 나오게 된다면 G를 한 단계 일반적인 방향으로 떨어뜨려야 한다. 반대로, 거짓이라면 G의 범위를 커버할 수 있을만큼만 구체적으로 업데이트해야 하고, 만약 S에서 참이라 한다면 S를 한 단계 구체적인 방향으로 올려야 한다. 구체적인 동작방식은 다음과 같다.

출력값이 yes라고 한다면, S를 먼저 업데이트하므로 G0==G1==G2가 될 것이다. 그리고 G3에서 same의 경우 마지막 instance에서 forest가 change이지만, yes가 나오는 결과로 인해 forest라는 feature는 y에 대해 관련이 없다라고 업데이트가 되야 하므로, 후보에서 제외가 된다.

이 때, 만약 새로운 instance가 등장했고, 한가지의 instance인 세번째 값이 Specific boundary에는 만족하지 않으나, General boundary에는 만족하는 값이라면, 즉 VS안의 수많은 가설 중 하나라면 판단하기 어려우므로 이러한 rule based 방식은 적합하지 않다. perfect world에서는 rule based가 정확하지만, real world에서는 정확하지 않다.

2-2. Desicion Tree

perfect world에서는 정확하나 real world에서는 불안정한 이유는 바로 노이즈 때문이다. real world에서는 노이즈는 항상 존재하는데, 이러한 노이즈를 제거하기 위해 수많은 연구들이 진행되어 왔다. 그 중 하나가 decision tree이다.

sky가 sunny라고 하면, temp를 고려하여 warm일 때만 다음을 고려하고, 그렇게 feature들을 모두 고려하는 방식이 desicion tree이다.

조금 더 구체적인 예시를 위해 흔히 사용되는 uci dataset을 사용해보고자 한다. uci 데이터셋 중에서 credit approval, 신용평가에 대한 데이터셋을 사용할 것이다. 총 690개의 instance가 존재하고, 307개는 positive, 나머지는 negative로 구성되어 있다. 그리고 신용평가에 사용되는 feature들은 15개가 존재한다. 여기서 A1에 대해서만 판단하여 a를 항상 negative, b는 항상 positive를 준다고 판단했을 때, 실제 결과는 a에 대해 112개는 negative, 98개는 positive이고, b에 대해서는 206개는 positive, 262개는 negative로 구성되게 된다. 그렇다면 a의 98개와 b의 262개는 틀린 값이 된다. 이 때, ? 는 don’t care가 아니라, 데이터가 존재하지 않는 instance에 대한 값이다. A9에 대해 t를 positive, f에 대해 negative를 주게 된다면, A1보다는 적게 틀리게 되겠지만 에러는 존재하게 된다.

2-3. Entropy and Information Gain

Entropy

불확실성(uncertainty), 즉 에러를 줄이기 위해 어떤 속성이 좋은지를 측정하기 위해 Entropy를 사용한다. entropy, H는 다음과 같이 구할 수 있다. 이 때, entropy가 높을수록 불확실성도 높아진다.

\[H(X) = -\sum_X P(X = x)log_bP(X = x)\]

Conditional Entropy

조건부를 적용한 상황에서 entropy도 구할 수 있다. 우리는 특정 feature가 주어졌을 때의 entropy를 구하고 싶어 한다. 그래서 X가 주어졌을 때, Y에 대한 entropy는 다음과 같다.

\[H(Y|X) = \sum_X P(X = x)H(Y|X = x) = \sum_X P(X = x)(\sum_Y P(Y = y | X = x)log_bP(Y = y | X = x))\]

Information Gain

information gain은 또 다른 측정기법이다. 우리는 A1 또는 A9에 대한 entropy를 구할 수도 있지만, A1에서 a,b,? 각각의 클래스에 대한 entropy도 구할 수 있을 것이다.

+,- 각각에 대한 확률을 구하여 A1에 대한 entropy를 구할 수 있다.

\[P(Y = +) = \cfrac{307}{307 + 383}, \: P(Y = -) = \cfrac{383}{307 + 383}\]

그렇다면, A1 또는 A9이라는 조건을 주고 conditional entropy를 측정한다면 H(Y|A1) 과 같은 형태를 띌 것이다. 여기서 우리가 구해봐야 할 것은 단지 conditional entropy가 아니라, 이를 활용하여 원래의 entropy인 H(Y)에 비해 불확실성이 얼마나 줄어드는지를 측정해야 한다. 그래서 이러한 값이 information gain이라 하는 값이 되고, 이는 원래의 값에서 conditional entropy를 빼주면 된다.

\[IG(Y, A_i) = H(Y) - H(Y|A_i)\]

당연히 IG가 클수록 불확실성이 그만큼 줄어들었다는 것이므로 더 좋은 지표가 될 것이다.

이렇게 각 클래스별로 information gain을 가지고, 최적의 루트를 정할 수 있다.

이렇게 decision tree를 만드는 방식에는 여러 가지가 있는데, 대표적으로 ID3 algorithm이 있다. 먼저 하나의 클래스를 정해서 오픈 노드를 생성한다. 이에 대해 최적의 루트를 판단하기 위해 위에서 배운 Information gain을 활용하여 어느 방향이 더 좋은지 확인한다.

여기서 tree가 깊을수록 좋을 것이라 생각할 수 있지만, 현실은 그렇지 않다. 왜냐하면 이러한 tree는 주어진 데이터셋에 대해 너무 많이 최적화되기 떄문이다. 이를 overfitting이라 하고, 그래서 최적의 tree 깊이를 잘 정해줘야 한다.

2-4. Linear Regression

지금까지는 Rule 기반의 모델을 구축했지만, 이제는 조금 더 통계 기반의 모델을 구축해보고자 한다. 머신러닝이란 더 나은 함수를 추정하는 것인데, 그 중 Linear Regression은 선형으로 decision boundary를 추정해보는 것이다.

rule 기반의 모델에서는 뚜렷한 구별 형태로 가설을 세웠지만, 이제는 함수 형태로 가설해볼 것이다. 지금은 선형의 모델을 구성할 예정이므로, 가중치(weight)인 theta를 잘 정의하여 최적화한다.

가설 h는 $ \hat{f}(x;\theta) = \theta_0 + \sum_{i=1}^n \theta_i x_i = \sum_{i=0}^n \theta_i x_i $ 로 정의할 수 있다. 이때, n은 feature의 개수이다. 이러한 h를 matrix 형태로 변환해보면 다음과 같다.

따라서 $ \hat{f} = X\theta $ 가 된다. 그리고, real world에서는 노이즈가 항상 존재하므로, error term인 e를 추가하여 정답의 f를 정의한다. 그리고 우리는 이 error term을 최소인 가설이 최적의 가설이라 판단할 수 있다. 그러므로 e가 최소가 되는 theta를 구한다.

\[f = X\theta + e = Y\] \[\hat{\theta} = argmin_{\theta} (f-\hat{f})^2 = argmin_{\theta} (Y - X\theta)^2\]

이 때, 이 식을 행렬의 특성을 활용하여 다시 나타내면 다음과 같다.

\[argmin_{\theta} (Y - X\theta)^T (Y-X\theta) = argmin_{\theta} (Y-X\theta)^T (Y-X\theta) = argmin_{\theta} (\theta^T X^T X\theta - 2\theta^TX^TY + Y^TY) = argmin_{\theta} (\theta^TX^TX\theta - 2 \theta^T X^T Y)\]

우리가 최소화시키고자 하는 값은 theta이므로 theta와 관련이 없는 Y^T Y 는 제거할 수 있다. MLE를 구할 때 사용했던 테크닉을 그대로 사용하여 argmin 안에 있는 값을 미분하여 최소가 되는 theta를 구한다.

\[\theta = (X^TX)^{-1} X^TY\]

이를 통해 값을 추정할 수 있다. 빨간색 점이 GT 즉 정답인 Y값이고, 파란색 점들이 우리가 선형으로 추정한 Y^ 이다. 선형으로 추정을 하니 생각보다 잘 맞지 않는 모습을 보이고 있다. 따라서 이러한 linear 특성을 수정하여 비선형 가설을 세우고자 한다.

원래의 식에서 x value에 제곱, 세제곱 네제곱… 을 취하여 새로운 variable을 생성한다.

이를 통해 새로운 곡선을 만들었는데, 뒤에 오는 값들이 거의 희박하게 존재하는데도 이들을 위해 더 깊게 만들어야 하는지에 대한 의문이 든다. 따라서 최적의 깊이를 정하는 것이 또 다시 중요해진다.

[KOOC] 인공지능 및 기계학습 개론 1,2주차 - MLE, MAP, Decision Tree, Entropy