본 포스트는 문일철 교수님의 인공지능 및 기계학습 개론 I 강의를 바탕으로 작성하였습니다. 다양한 결정 트리 알고리즘에 대한 부분은 이곳 을 참조하였습니다.

Decision Tree

규칙 기반 학습(Rule Based Learning)에서는 우리가 관측한 데이터가 완벽한 세계(Perfect)의 것임을 가정하였습니다. 하지만 우리가 살고 있는 세계는 완벽한 세계와는 너무나도 다릅니다. 일단, 모든 특성을 관측할 수 없습니다. 관측 오차도 발생하기 마련이지요. 그렇기 때문에 실제 상황에서 규칙 기반 학습을 적용하기 어렵습니다. 그렇기 때문에 다른 방법을 통해 분석을 시도해야 하는데 그 중 가장 쉬운 방법 중 하나로 의사 결정 나무(Decision Tree) 가 있습니다.

이번 게시물에서는 UCI 신용평가 데이터셋을 분석하며 의사 결정 나무에 대해서 알아보도록 합시다. 이 데이터셋에서는 총 690개의 인스턴스가 있으며 각 인스턴스는 15개의 특성을 가지고 있습니다. 아래 사진은 학습 데이터셋이 첫 번째 특성(A1) 또는 아홉 번째 특성(A9)으로 나누었을 때 각각의 결과가 어떻게 나오는지 도식화한 것이다.

이미지 출처 : 인공지능 및 기계학습 개론 학습자료

위 이미지와 같이 원래 데이터에는 Positive 레이블을 가진 인스턴스가 307개, Negative 레이블을 가진 인스턴스가 383개 포함되어 있습니다. A1특성으로 나눌 경우 왼쪽처럼 $a$ 노드에 98개의 Positive, 112개의 Negative 인스턴스가 배정되며, $b$ 노드에 206개의 Positive, 262개의 Negative 인스턴스가 배정됩니다. 그리고 어느 분류에도 속하지 않는 12개의 인스턴스가 또 다른 세 번째 노드에 배정됩니다. A9 특성으로 나눌 경우에는 오른쪽처럼 $t$ 노드에 284개의 Positive, 77개의 Negative 인스턴스가 배정되며, $f$ 노드에 23개의 Positive, 306개의 Negative 인스턴스가 배정됩니다.

Entropy & Information Gain

위와 같은 결과가 나왔다면 어떤 특성을 기준으로 나누었을 때가 더 좋은 기준이라고 할 수 있을까요? 더 좋은 분류를 평가하기 위한 수치(Metric)로 정보 엔트로피 혹은 섀넌 엔트로피(Shannon Entropy) 가 있습니다. 정보 엔트로피가 무엇인지 알기 전에 정보 이론에서 사용되는 정보량에 대해 알아봅시다. 정보량 $I$ 를 표현하는 수식은 아래와 같습니다.

[I(X) = \log_2 \frac{1}{p(X)}]

위 식에서 $p(X)$ 는 사건 $X$ 가 발생할 확률을 나타냅니다. 해당 수식으로부터 특정 사건이 가지고 있는 정보량은 그 사건깅 일어날 확률의 로그값에 반비례하는 것을 알 수 있습니다. 엔트로피 $H(X)$ 는 이 정보량의 평균을 나타내는 것으로 수식은 다음과 같습니다.

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

엔트로피는 데이터의 불확실성(Uncertainty)을 나타내므로 이 값이 높을수록 그 데이터셋이 더 불확실하다는 것을 의미합니다. 이 엔트로피 식에 조건부 확률을 적용하면 조건 엔트로피(Conditional entropy)에 대한 식이 됩니다.

[\begin{aligned} H(Y\vert X) &= \sum_X P(X=x) \log_b H(Y\vert X=x)
&= \sum_X P(X=x) { -\sum_Y P(Y=y\vert X=x) \log_b H(Y=y\vert X=x)} \end{aligned}]

위 식을 이용하여 원래 데이터셋의 엔트로피와 이 데이터셋을 각각 A1과 A9으로 나누었을 때의 엔트로피를 계산해봅시다.

[\begin{aligned} H(Y) &= -\sum_{Y \in {+,-}} P(Y=y) \log_2 P(Y=y) = 0.991
H(Y\vert A1) &= \sum_{X \in {a,b,?}} \sum_{Y \in {+,-}} P(A1= x, Y=y) \log_2 \frac {P(A1=x)}{P(A1= x, Y=y)} = 0.989
H(Y\vert A9) &= \sum_{X \in {t,f}} \sum_{Y \in {+,-}} P(A9= x, Y=y) \log_2 \frac {P(A9=x)}{P(A9= x, Y=y)} = 0.566 \end{aligned}]

이제는 정보 획득도(Information Gain, IG) 에 대해 알아봅시다. 정보 획득도는 엔트로피가 얼마나 줄어들었는 지를 나타내는 것으로 데이터셋의 불확실성이 얼마나 줄어들었는지 나타내는 수치기이도 합니다. 정보 획득도를 구하는 식은 다음과 같습니다. 아래는 이를 사용하여 각 특성으로 나누었을 때의 정보 획득도입니다.

[\begin{aligned} IG(Y,A_i) &= H(Y) - H(Y \vert A_i)
IG(Y,A_1) &= H(Y) - H(Y \vert A_1) = 0.991 - 0.989 = 0.002
IG(Y,A_9) &= H(Y) - H(Y \vert A_9) = 0.991 - 0.566 = 0.425 \end{aligned}]

A9 특성을 기준으로 나누었을 때가 A1 특성을 기준으로 나누었을 때보다 훨씬 더 높은 정보 획득도를 보이는 것을 알 수 있습니다. 이를 기준으로 노드를 나눌 때 A1보다 A9가 더 나은 특성임을 판가름하게 됩니다.

Variable Decision Tree

의사 결정 나무의 종류에도 여러가지가 있습니다.

첫 번째로 알아볼 것은 ID3(Iterative Dichotomiser 3) 입니다. 먼저 모든 인스턴스가 포함된 하나의 노드를 만듭니다. 그 다음에는 그 노드를 분류할 최적의 특성을 선택합니다. 그리고 그 특성의 클래스에 맞게 인스턴스를 분리하여 새로운 노드에 배치합니다. 한 노드에 담긴 인스턴스의 레이블이 모두 동일한 경우에 나누는 것을 종료합니다. 가장 기본적인 의사 결정 나무 알고리즘이지만, 범주형 특성만을 다룰 수 있다는 단점이 있습니다. 또한 순수한 노드가 나올 때까지 가지를 나누게 되므로 과적합(Overfitting)이 쉽게 발생하는 문제점이 있습니다.

두 번째는 ID3의 단점을 보완한 C4.5 입니다. ID3가 범주형 속성만을 다룰 수 있는데 비해 이 알고리즘은 수치형 속성까지 다룰 수 있습니다. 그리고 C4.5 알고리즘에서는 가지치기(Pruning)를 추가하여 트리가 너무 깊게 형성되는 것을 방지할 수 있습니다. 또한 결측치를 알아서 처리하고 속성마다 다른 가중치를 부여함으로서 계산을 효율적으로 진행할수 있다는 장점도 가지고 있습니다.

세 번째로 알아볼 의사 결정 나무 알고리즘은 CART(Classification And Regression Tree) 입니다. 이 알고리즘이 진행되는 방향은 ID3와 알고리즘이 진행되는 방향이 동일합니다. 차이점은 특성을 선택하는 기준에 있습니다. ID3는 특성 선택의 기준으로 엔트로피의 변화인 정보 획득도를 사용하지만 CART에서는 지니 계수(Gini Index) 라는 새로운 수치를 사용합니다. 지니 계수 $G_i$ 는 다음과 같은 수식으로 구할 수 있습니다.

[G_i = 1 - \sum^n_{k=1} {p_{i,k}}^2]

훈련 데이터셋을 특성 $k$ 의 임곗값인 $t_k$ 를 기준으로 두 개의 서브셋으로 나눕니다. 그리고 아래의 비용함수(Cost function)를 최소화하는 특성과 그 임곗값이 가지를 나누는 기준이 됩니다. 아래의 비용함수 식에서 $G$ 는 각 서브셋(Subset)의 불순도를, $m$은 각 서브셋의 샘플 수를 나타냅니다.

[J(k, t_k) = \frac{m_{\text{left}}}{m}G_{\text{left}} + \frac{m_{\text{right}}}{m}G_{\text{right}}]

CART는 다양한 XGboost 등 부스팅 알고리즘의 기본 알고리즘으로 사용되고 있습니다.

마지막으로 알아볼 알고리즘은 CHAID(Chi-squared Automatic Interaction Detection) 입니다. 이 알고리즘은 이산형 목표 변수에 대한 카이제곱( $\chi^2$ ) 검정과 연속형 목표 변수에 대한 F-검정을 이용하여 다지 분리(Multiway split)을 수행하는 알고리즘입니다. 이 두 검정에 대한 수치를 기준으로 노드를 분할합니다. 해당 수치가 임곗값보다 낮을 경우 하위 노드를 병합하는 과정을 통해 과적합을 면할 수 있다는 장점이 있습니다.

본 포스트는 문일철 교수님의 인공지능 및 기계학습 개론 I 강의를 바탕으로 작성하였습니다.

Rule Based Learning

머신러닝이란 무엇일까요? 위키백과로부터 머신러닝의 정의를 가져와 봅시다.

” 기계 학습 또는 머신 러닝(Machine learning)은 경험을 통해 자동으로 개선하는 컴퓨터 알고리즘의 연구이다. 인공지능의 한 분야로 간주된다. 컴퓨터가 학습할 수 있도록 하는 알고리즘과 기술을 개발하는 분야이다.”

위에 설명되어 있는 것처럼 머신러닝을 수행하기 위해서 컴퓨터는 많은 경험을 학습합니다. 그리고 학습된 경험을 바탕으로 알고리즘을 만들어 특정한 일(Task)을 수행하지요. 중요한 것은 컴퓨터가 학습을 통해 만드는 알고리즘의 성능은 얼마나 많은 경험(데이터)을 수집하여 학습했는지에 달렸다는 것입니다.

사람이 지식을 습득하는 방법 중 하나도 위와 유사합니다. 흔히 사용하는 관용어 중에 “실패를 통해 배운다” 라는 말이 있습니다. 어떤 일을 성공시키기 위해서 무엇을 해야 할 지, 또는 하지 말아야 할 지를 많은 경험을 통해 배울 때 이 말을 사용합니다. 하지 말아야 할 일은 한 경우에는 실패하게 되고, 해야 할 일을 하지 않은 경우에도 실패하게 되지요. 반대로 해야할 일을 하고, 하지 말아야 할 일은 하지 않으면 성공합니다. 이를 경험을 통한 시행착오를 통해 배우지요.

이번 게시물에서는 머신러닝의 가장 기초적인 방법 중 하나인 규칙 기반 학습(Rule Based Learning) 에 대해 배워보도록 하겠습니다.

Rule Based Learning (규칙 기반 학습)

이후에 이루어질 논의를 더 쉽게 하기 위해서 몇 가지 가정을 해야합니다. 첫 번째로 우리가 알아볼 세상에서는 관측 오차(Observation errors)가 없습니다. 두 번째로 일관성이 없는 관측(Inconsistent observations)도 없습니다. 세 번째로 어떤 확률론적 요소(Stochastic element)도 없습니다. 마지막으로는 우리가 관측하는 정보가 시스템에 있는 모든 정보입니다. 이 가정을 모두 만족하는 곳을 완벽한 세계(Perfect world) 라고 합니다.

이 완벽한 세계에서 관측한 아래와 같은 데이터가 있다고 해봅시다.

앞으로 머신러닝에서 등장할 데이터는 일반적으로 위와 같이 생겼습니다. 우리의 목적은 위와 같이 관측된 데이터로부터 더 좋은 근사 함수를 생성하는 것입니다. 아래는 위 표의 요소를 설명하기 위한 용어들입니다.

가장 먼저 알아야 할 용어는 인스턴스(Instance) 입니다. 위 표에서 각 행(Row)이 인스턴스입니다. 일반적으로 특성(Feature)과 레이블(Label)로 이루어져 있습니다. 위 표에서 (하늘 상태, 온도, 습도, 바람, 해수 온도, 일기예보) 를 특성이라고 하고 그 값에 해당하는 (맑음, 따듯함, 보통, 강함, 따듯함, 일정함) 을 특성값이라고 합니다. 그에 따라 결정되는 (물놀이를 나갈까?) 와 그 값은 레이블이라고 합니다.

가설(Hypothesis) 에 대해서도 알아야 합니다. 가설은 특성값으로부터 특정 레이블을 도출할 가능성이 있는 함수입니다. 위 데이터셋에서 도출할 수 있는 가설은 다음과 같습니다.

$h_0$ : (맑음, 따듯함, ?, ?, ?, ?) $\rightarrow$ 예

위 가설에서 (습도, 바람, 해수온도, 일기예보) 가 ”?” 로 표시된 이유는 주어진 데이터셋을 통해서 도출해낼 수 없기 때문입니다. 습도의 경우 인스턴스에서 2와 3에서 모두 “높음” 이지만 2번 인스턴스의 레이블은 “예”, 3번 인스턴스의 레이블은 “아니오” 입니다. 이렇게 주어진 데이터셋 만으로는 해당 특성값이 레이블에 어떤 영향을 미치는지 알 수 없기 때문에 ”?” 로 표시합니다. 이렇게 결정되지 않은 특성 때문에 여러 종류의 가설이 가능합니다. 데이터를 더욱 많이 수집하여 여러 가설로부터 하나의 목적 함수(Target function) 을 찾는 것이 우리의 목적이라 할 수 있겠습니다.

이번에는 관측한 데이터의 개수에 따라 가설이 어떻게 변화하는지 알아봅시다. 위 표에서 1, 2, 3번 인스턴스를 관측하여 도출한 가설 $h_1$ 은 (맑음, 따듯함, ?, ?, ?, 일정함) $\rightarrow$ “예” 입니다. 결정되지 않은 특성이 3개인 것을 알 수 있습니다. 1, 2번 인스턴스만 관찰한 뒤에 가설을 세워봅시다. 이 때의 가설 $h_2$ 는 (맑음, 따듯함, ?, 강함, 따듯함, 일정함) $\rightarrow$ “예” 입니다. 2, 3번 인스턴스를 관찰한 뒤 가설을 세워보면 어떻게 나올까요? 이 가설 $h_3$ 는 (맑음, 따듯함, 보통, ?, ?, 일정함) $\rightarrow$ “예” 입니다.

앞서 4개의(1, 2, 3, 4번) 인스턴스를 모두 관측하여 나타낸 가설 $h_0$ 에서는 결정되지 않은 특성, 즉 ”?” 로 나타난 특성이 4개가 있었습니다. 그리고 3개의 인스턴스를 관측하여 나타낸 가설 $h_1$ 에서는 ”?” 인 특성이 3개가 있었습니다. 2개의 인스턴스를 관측했을 때는 가설 $h_2, h_3$ 에 “?” 가 각각 1번, 2번씩 등장했습니다.

가설들 중 $h_0, h_1$ 은 상대적으로 여러 인스턴스로부터 도출된 일반적(General) 인 가설입니다. 관측된 데이터셋에 있는 인스턴스 말고도 해당 가설을 만족하는 인스턴스가 더 많을 수 있기 때문이지요. 반대로 $h_2, h_3$ 는 상대적으로 특수한(Specific) 가설입니다. 특히 $h_2$ 같이 결정되지 않은 특성( ”?” )이 하나인 경우에는 2번과 3번 인스턴스 이외에 가설을 만족하는 다른 인스턴스가 없습니다.

상대적으로 일반적인 가설과 특수한 가설 중 어떤 것이 더 좋은 것일까요? 위에서 보았던 위키백과 머신러닝 페이지로 돌아가봅시다. 위에서 인용했던 머신러닝의 정의 뒷부분에는 다음과 같은 말이 써있습니다.

“기계 학습의 핵심은 표현(representation)과 일반화(generalization)에 있다. 표현이란 데이터의 평가이며, 일반화란 아직 알 수 없는 데이터에 대한 처리이다.”

위의 인용 부분으로부터 상대적으로 일반적인 가설이 더 좋은 것을 알 수 있습니다. 특수한 가설이 좋지 않은 이유는 그것이 관측되지 않은 데이터를 만족시킬 수 없기 때문이지요. 아무튼 더 일반적인 가설을 만들어 내기 위해서 더 많은 데이터를 관측해야 합니다. 아래부터는 가설을 찾아나가기 위한 규칙 기반 학습 알고리즘에 대해 알아봅니다.

Find-S Algorithm & Version Space

Find-S Algorithm 은 특수한 가설로부터 일반적인 가설로 가설의 범위를 확장해나가는 알고리즘입니다. 이 알고리즘은 아무런 특성도 한정되지 않은 영가설(Null hypothesis)로부터 시작합니다. 그리고 Positive한 레이블을 나타내는 인스턴스 하나씩을 골라 해당하는 특성을 기존의 가설과 비교하며 판단해나갑니다. 기존의 가설과 새로운 인스턴스의 특성값이 다를 경우 이 경우를 포함시키며 가설의 범위를 확장해 나갑니다. 예시를 위해 위에서 사용했던 표를 다시 인용해봅시다.

이미지 출처 : aistudy.com

위 표에서 Positive한 레이블을 나타내는 인스턴스는 1, 2, 4번 인스턴스 입니다. 이 세 인스턴스를 사용하여 Find-S Algorithm 과정을 진행해봅시다. 맨 처음은 영가설인 $h_0 = (\phi, \phi, \phi, \phi, \phi, \phi)$ 에서 시작합니다. 새로운 인스턴스 1번에 의해 정해지는 가설 $h_1$ 은 (맑음, 따듯함, 보통, 강함, 따듯함, 일정함) 입니다. 이 가설에 새로운 인스턴스 2번을 적용하면 새로운 가설 $h_2$ 는 (맑음, 따듯함, ?, 강함, 따듯함, 일정함) 으로 변하게 됩니다. “습도” 특성에 해당하는 가설이 변경되며 가설의 범위가 확장되는 것을 볼 수 있습니다. 마지막으로 4번 인스턴스를 추가로 적용하여 최종적으로 도출되는 가설 $h_3$ 은 (맑음, 따듯함, ?, 강함, ?, ?) 이 됩니다.

이미지 출처 : excelsior-cjh.tistory.com

이 과정에서 생성가능한 모든 가설의 수를 모아둔 집합을 버전 공간(Version Space, VS) 이라고 합니다. 버전 공간에는 가장 일반적인 가설을 나타내는 경계 $G$ 와 가장 특수한 가설을 나타내는 경계 $S$ 가 있습니다. 두 경계를 수식으로는 아래와 같이 나타낼 수 있습니다.

[VS_{H,D} = {h \in H \vert \quad \exists s \in S, \exists g \in G, \quad g \geq h \geq s }]

이미지 출처 : aistudy.com

위에서 알아 본 것처럼 4개의 데이터셋으로부터 Find-S Algorithm을 통해 구할 수 있는 특수한 경계 $S$ 는 (맑음, 따듯함, ?, 강함, ?, ?) 입니다. 그리고 가장 일반적인 경계 $G$ 로는 {(맑음, ?, ?, ?, ?, ?), (?, 따듯함, ?, ?, ?, ?)} 이 있습니다. 이 사이에는 (맑음, ?, ?, 강함, ?, ?), (맑음, 따듯함, ?, ?, ?, ?), (?, 따듯함, ?, 강함, ?, ?) 등의 많은 가설이 존재할 수 있습니다.

이미지 출처 : excelsior-cjh.tistory.com

Find-S 알고리즘은 너무 특수한 가설에 빠질 경우 이를 개선할 수 있는 역추적 방식을 제공하지 않는다는 단점을 가지고 있습니다. 그렇다면 Find-S 알고리즘 이외에 버전 공간(Version space)을 구하는 다른 방법은 없을까요?

후보 제거 알고리즘(Candidate Elimination Algorithm)

후보 제거 알고리즘(Candidate Elimination Algorithm) 은 버전 공간을 구하기 위한 또 다른 알고리즘입니다. 이 알고리즘은 가장 특수한(Specific)한 가설 $S_0 = (\phi, \phi, \phi, \phi, \phi, \phi)$ 와 가장 일반적인 가설 $G_0 = (?, ?, ?, ?, ?, ?)$ 로부터 시작하게 됩니다. 후보 제거 알고리즘도 Find-S 알고리즘과 마찬가지로 인스턴스 하나씩을 적용하여 두 가설 사이에 존재하는 후보 가설들을 줄여나갑니다. Find-S 알고리즘에서는 Positive한 인스턴스만을 사용하여 일반화했지만 후보 제거 알고리즘은 Positive한 인스턴스와 Negative한 인스턴스 2가지를 모두 사용합니다.

이미지 출처 : excelsior-cjh.tistory.com

후보 제거 알고리즘이 진행되는 과정을 살펴봅시다. 새로 적용할 인스턴스의 레이블이 Positive하면 이 인스턴스를 만족시킬 수 있을 만큼만 특수 경계인 $S$ 를 일반화 해나갑니다. 이 과정에서 일반 경계인 $G$ 에 어긋나는 가설이 있을 경우에는 해당 조건을 제거합니다. 반대로 새로 적용할 인스턴스의 레이블이 Negative이면 이 인스턴스가 Negative로 분류될 수 있도록 일반 경계 $G$ 의 범위를 줄여나갑니다. 이 과정에서도 $S$ 쪽에 새로 적용되는 인스턴스를 만족시키는 조건이 있다면 이 조건을 탈락시킵니다. 말로만 설명하니 이해하기가 어렵습니다. 위에서 사용했던 표를 다시 가져와서 후보 제거 알고리즘을 적용해봅시다.

첫 번째 인스턴스를 적용했을 때의 각 경계는 다음과 같이 변하게 됩니다. $S_1 = (맑음, 따듯함, 보통, 강함, 따듯함, 일정함), G_1 = (?, ?, ?, ?, ?, ?)$ 첫 번째 인스턴스의 레이블이 “예” 이므로 이에 맞게 $S$ 를 조정하고 $G$ 는 거스르는 부분이 없으므로 그대로 유지합니다.

두 번째 인스턴스를 적용하면 $S_2 = (맑음, 따듯함, ?, 강함, 따듯함, 일정함)$, $G_2 = (?, ?, ?, ?, ?, ?)$ 이 됩니다. 앞선 과정과 동일하며 여기까지는 Find-S 알고리즘과도 유사합니다. 첫 번째와 두 번째 인스턴스 모두 Positive 하므로 $S$ 만 점점 General 해지는 것을 볼 수 있습니다.

이미지 출처 : excelsior-cjh.tistory.com

이번에는 세 번째 인스턴스를 적용해봅시다. 여기서 Find-S 알고리즘과의 차이가 발생합니다. Find-S 알고리즘에서는 레이블링이 “아니오” 인 인스턴스는 적용하지 않았기 때문입니다. 세 번째 인스턴스를 적용하여 변한 가설은 $S_3 = (맑음, 따듯함, ?, 강함, 따듯함, 일정함), G_3 = {(맑음, ?, ?, ?, ?, ?), (?, 따듯함, ?, ?, ?, ?), (?, ?, ?, ?, ?, 일정함)}$ 입니다. 앞선 두 인스턴스와 세 번째 인스턴스는 “하늘 상태, 온도, 일기 예보” 세 가지 특성에서 다른 값을 나타냅니다. 각 특성들에서 세 번째 인스턴스 특성값은 “흐림, 추움, 가변적” 입니다. 이와 반대되는 특성값으로 이루어진 가설을 각각 $G$ 에 추가해주면 위와 같이 $G_3 = {(맑음, ?, ?, ?, ?, ?), (?, 따듯함, ?, ?, ?, ?), (?, ?, ?, ?, ?, 일정함)}$ 를 나타내게 됩니다.

이미지 출처 : excelsior-cjh.tistory.com

마지막으로 네 번째 인스턴스를 적용하여 가설을 개선해봅시다. 개선된 가설은 $S_4 = (맑음, 따듯함, ?, 강함, ?, ?), G_4 = {(맑음, ?, ?, ?, ?, ?), (?, 따듯함, ?, ?, ?, ?)}$ 입니다. 먼저 $S$ 쪽은 “해수 온도” 와 “일기 예보” 에서 기존 가설과 네 번째 인스턴스의 특성값이 다르므로 ”?” 로 처리해주어 일반화합니다. 그리고 $G$ 쪽은 네 번째 인스턴스에서 “일기 예보” 의 특성값이 “가변적” 임에도 레이블이 “예” 이므로 $(?, ?, ?, ?, ?, 일정함)$ 에 해당하는 가설을 탈락시킵니다.

이미지 출처 : excelsior-cjh.tistory.com

이렇게 도출된 버전 공간을 다른 데이터에 적용하면 어떻게 될까요? 아래 표는 레이블링이 되어있지 않은 추가 데이터셋입니다. 4개의 인스턴스에 후보 제거 알고리즘을 적용하여 도출된 버전 공간을 통해 아래 데이터를 레이블링해 봅시다.

위 표에서 첫 번째와 두 번째 인스턴스는 위에서 도출한 버전 공간 바깥에 위치하기 때문에 레이블을 결정할 수 있습니다. 첫 번째 인스턴스의 경우 $S_4 = (맑음, 따듯함, ?, 강함, ?, ?)$ 를 모두 만족시키므로 “예” 로 레이블링 할 수 있습니다. 두 번째 인스턴스는 $G_4 = {(맑음, ?, ?, ?, ?, ?), (?, 따듯함, ?, ?, ?, ?)}$ 중 어느 것도 만족시키고 있지 않으므로 “아니오” 로 레이블링하면 됩니다.

하지만 마지막 인스턴스는 버전 공간인 $S_4, G_4$ 사이에 위치합니다. 이 경우에는 함부로 레이블을 결정할 수가 없습니다. 이런 문제를 해결하기 위해서는 어떻게 해야 할까요?

정답은 데이터의 수를 늘리는 것입니다. 완벽한 세계(Perfect world)에서는 데이터가 늘어나게 되면 후보 제거 알고리즘을 통해서 버전 공간(Version space)을 점점 줄여나갈 수 있습니다. 더욱 많아진다면 하나의 가설로 축소할 수도 있지요. 하지만 현실세계에서는 모든 관측 데이터에 소음이 존재하고 우리가 관측하지 못하는 특성이 개입될 수도 있습니다. 이 때문에 후보 제거 알고리즘 등의 규칙 기반 방식으로는 현실에서 일어나는 모든 데이터에 대한 설명력이 떨어지게 됩니다.

본 포스트는 문일철 교수님의 인공지능 및 기계학습 개론 I 강의를 바탕으로 작성하였습니다.

Probability & Distribution

Probability (확률)

이번 게시물에서는 확률에 대해서 알아봅시다. 확률(Probability) 이란 무엇일까요? 넓은 의미에서 이 질문에 답을 한다는 것은 쉬운일이 아닙니다. 하지만 ‘수학적’ 확률로 범위를 축소한다면 그리 어려운 문제는 아닙니다. 수학에서의 확률은 아래의 특징을 가지는 함수로 정의할 수 있습니다. 발생 가능한 모든 사건을 나타내는 $\Omega$ 에 대하여 특정 사건 $E$ 의 확률 $P(E)$ 는 아래와 같이 수식으로 나타낼 수 있습니다.

[P(E) \in R, \quad P(E) \geq 0, \quad P(\Omega) = 1
P(E_1 \cup E_2 \cup …) = \sum^{\infty}_{i=1} P(E_i)
\text{단, } E_i \text{ 가 서로 상호 배타적(Mutually Exclusive)일 경우}]

확률은 특별한 조건을 가지고 있기 때문에 그로부터 발생하는 몇 가지 특성을 가지고 있습니다.

[\begin{aligned} & 1.\quad \text{만약 } A \subset B \text{ 이면 } P(A) \leq P(B)
& 2. \quad P(\phi) = 0
& 3. \quad 0 \leq P(A) \leq 1
& 4. \quad P(X \cup Y) = P(X) + P(Y) - P(X \cap Y)
& 5. \quad P(E^c) = 1 - P(E) \end{aligned}]

첫 번째 특성은 한 사건이 다른 사건의 부분집합일 경우 성립하는 특성입니다. 예를 들면, 주사위를 던져 3이 나오는 사건은 홀수가 나오는 사건의 부분집합입니다. 그렇기 때문에 3이 나올 확률은 홀수가 나올 확률보다 작거나 같습니다. 두 번째 특성은 사건이 공집합일 경우에 대한 특성입니다. 주사위를 던져 7 이상의 눈이 나올 확률이 이에 속합니다. 당연히 0이 되겠습니다. 세 번째 특성은 임의의 사건이 일어날 확률이 $[0,1]$ 사이에 있음을 나타내는 일반적인 성질입니다. 따로 예시는 들지 않도록 하겠습니다.

네 번째는 합집합에 대한 확률입니다. 이번에도 주사위를 던지는 예를 들어봅시다. $X$ 를 소수인 눈이 나오는 사건이라 하고, $Y$ 를 홀수인 눈이 나오는 사건이라고 합시다. 1부터 6까지의 눈 중에서 소수인 눈은 2, 3 으로 2개 이므로 $P(X) = 2/6 =1/3$ 입니다. 또 홀수인 눈은 1, 3, 5 로 3개 이므로 $P(Y) = 3/6 = 1/2$ 입니다. 이제 두 사건의 합사건 $X \cup Y$ 과 곱사건 $X \cap Y$ 을 알아봅시다. 두 사건의 합사건은 1, 2, 3, 5 로 4개 이므로 $P(X \cup Y) = 4/6 = 2/3$ 이고, 곱사건은 두 사건에 동일하게 등장하는 3 하나뿐이므로 $P(X \cap Y) = 1/6$ 입니다. 이를 4번에 나와있는 공식에 대입하면 $2/3 = 1/3 + 1/2 - 1/6$ 으로 공식이 성립한다는 것을 볼 수 있습니다.

마지막은 여집합에 대한 확률입니다. 특정 사건의 확률이 $P(E)$ 일 때, 그 사건이 일어나지 않을 확률 $P(E^c)$ 은 $1 - P(E)$ 임을 특별한 예시 없이도 알 수 있습니다.

Conditional Probability (조건부 확률)

우리가 경험하는 대부분의 사건은 특정 조건하에서 일어납니다. 예를 들면, 오늘 비가 왔을 때 내일 비가 또 올 확률을 구하는 경우가 대표적입니다. 이런 조건(Condition) 은 우리가 특정 확률을 예측하는 데에 필수적인 요건이 됩니다. 1부터 45까지 45개의 번호 중 6개의 번호를 맞추는 로또 번호를 예측하는 경우에도 마찬가지입니다. A라는 사람은 평소에 20번대가 많이 나온다고 생각해서 20번대에 3개의 숫자를 찍을 수도 있습니다. B라는 사람은 지난 주에 나온 숫자가 다시 나올 확률은 적으니 그 숫자를 피할 수도 있고요. 이렇게 우리는 항상 어떤 예측을 할 때, 이전에 어땠는지에 대한 조건을 따져보며 확률을 예측하게 됩니다. 이렇게 조건이 있을 떄의 확률을 조건부 확률(Conditional Probability) 이라고 합니다. 조건부 확률을 구하는 수식은 아래와 같습니다.

[P(X \vert Y) = \frac{P(X \cap Y)}{P(Y)}]

위 식에서 $\vert$ 를 기준으로 뒤에 있는 것이 조건입니다. 위에서 나온 주사위의 예를 통해 조건부 확률도 계산해봅시다. 위 4번 공식에서 사용했던 예시를 그대로 사용합니다. 이 예시에서 $P(X \vert Y)$ 를 어떻게 설명할 수 있을까요? $\vert$ 를 기준으로 뒤에 위치한 것이 조건이므로, $P(X \vert Y)$ 는 “주사위를 던져 홀수인 눈이 나왔을 때 그 눈이 소수일 확률” 이 됩니다. 공식을 통해 $P(X \vert Y)$ 의 값을 구하면 $P(X \cap Y) = 1/6, P(Y) = 1/2$ 이므로 $1/3$ 이 됩니다. 실제로도 홀수인 눈이 나오는 경우는 1, 3, 5 이고 그 중 소수인 것은 3이므로 $P(X \vert Y) = 1/3$ 이 맞다는 것을 알 수 있습니다.

해당 공식을 사용하면 아래의 식을 유도할 수 있습니다. 참고로 아래의 식은 베이즈 법칙(Bayes’ Rule) 공식으로 최대 사후 확률 측정(Maximum A Posterior estimation, MAP)을 통해 사건의 확률을 추정하는 데에도 사용됩니다.

[P(Y \vert X) = \frac{P(X \vert Y)P(Y)}{P(X)}]

아래의 식도 조건부 확률의 중요한 특성 중 하나입니다. 아래 식에서 $Y_n$ 각각은 각 조건을 나타내며 겹치지 않는 배반사건입니다. 또한 조건 $Y_n$ 을 모두 고려한 경우 전체가 되어야 합니다. \(P(X) = \sum^n P(X \vert Y_n)P(Y_n) \qquad \text{if} \quad P(Y_i \cap Y_j) = 0 \text{ and } \sum^n Y_i = 1\)

해당 공식의 예시를 들기 위해 다시 이전에 사용했던 예시를 가져와 봅시다. 이번에는 $P(Y_1)$ 을 홀수인 면이 나올 조건, $P(Y_2)$ 를 짝수인 면이 나올 조건이라고 합시다. 이 두 사건은 교집합이 없는 배반 사건이며, 두 사건 이외의 어느 사건도 등장할 수 없습니다. 각 조건에 따르는 조건부 확률 P(X \vert Y_n) 을 구해봅시다. 먼저 $P(X \vert Y_1), P(Y_1)$ 은 이전에 구했던 것과 같이 $1/3, 1/2$ 이므로 $P(X \vert Y_1)P(Y_1) = 1/6$ 입니다. 짝수인 조건 $Y_2$ 에 대해서도 동일한 과정을 수행해봅시다. 짝수의 눈이 나오는 경우의 수는 2, 4, 6으로 3이고 그 중 소수는 2입니다. 이로부터 $P(X \vert Y_2), P(Y_2)$ 는 각각 $1/3, 1/2$ 임을 알 수 있습니다. 그리고 둘의 곱하여 $P(X \vert Y_2)P(Y_2) = 1/6$ 도 구할 수 있습니다. 이제 최종적인 $P(X) = 1/3$ 가 제대로 구해지는지 아래 수식을 따라가며 알아봅시다.

이전의 예시에서 제대로 구해지는 것을 볼 수 있습니다. 다음으로 확률 분포에 대해 알아봅시다.

Probability Distribution (확률 분포)

확률 분포(Probability distribution) 란 확률 변수가 특정한 값을 가질 확률을 나타내는 함수입니다. 이 특정한 값은 연속적(Continuous)일 수도 있고 이산적(Discrete)일 수도 있습니다. 예를 들어, 주사위를 던지는 행위는 확률 변수가 1, 2, 3, 4, 5, 6의 값을 나타내므로 이산 확률 분포(Discrete probability distribution)에 속합니다. 반대로 OO고등학교 학생들의 몸무게를 확률 분포로 나타낸다면 이 값은 연속적인 값을 나타내므로 연속 확률 분포(Continuous probability distribution)를 나타내게 됩니다.

첫 번째로 알아볼 확률 분포는 이항 분포(Binomial distribution) 입니다. 베르누이 시행에 대하여 사건이 나타내는 값이 이산적(Discrete)인 경우를 표현하는 확률분포입니다. 기호로는 $B(n,p)$ 와 같이 나타냅니다. 아래는 이항 분포의 수식 및 확률 질량 함수 그래프를 나타낸 것입니다. 연속적이지 않으므로 점으로 나타나는 것이 특징입니다.

[f(x;n, p) = \left(\begin{array}{c}n \k \end{array}\right)p^k (1-p)^{n-k}, \qquad \left(\begin{array}{c}n \k \end{array}\right) = \frac{n!}{k!(n-k)!}
np : \text{mean} \qquad np(1-p) : \text{variance}]

이미지 출처 : 위키피디아 - 이항분포

이항 분포에서 항의 개수를 일반화 하면 다항 분포(Multinomial distribution) 가 됩니다. 다항 분포의 확률 질량 함수 수식은 아래와 같습니다. 주사위를 던지는 경우가 다항 분포를 띠는 대표적인 경우에 속합니다. 실제 Task에서는 언어 생성(Text generation) 모델에서 특정 단어(토큰) 다음에 올 단어를 매 단어마다 예측하게 됩니다. 이것도 여러 이산적인 사건값 중에서 하나를 선택하는 경우이기 때문에 다항 분포에 속한다고 볼 수 있습니다. 기호로는 $\text{Mult}(P), P=<p_1, … , p_k>$ 로 나타냅니다.

[f(x_1,x_2 …, x_k; n,p_1,p_2 …, p_k) = \frac{n!}{x_1!x_2! … x_k!}p_1^{x_1}p_2^{x_2}…p_k^{x_k}
E(x_i) = np_i : \text{mean} \qquad \text{Var}(x_i) = np_i(1-p_i) : \text{variance}]

다음으로 알아볼 확률 분포는 정규분포(Normal distribution) 입니다. 정규 분포는 가우스 분포(Gaussian distribution) 라는 이름으로도 불립니다. 사건이 연속적인 값을 나타낼 때 쓰이는 연속 확률 분포의 모형 중 하나입니다. 기호로는 $N(\mu, \sigma^2)$ 와 같이 나타냅니다. 위에서 나타난 이산 확률 변수도 부분적으로는 정규분포의 형태를 띠고 있으며 수행 횟수를 더욱 늘린다면 점이 더욱 빽빽하게 찍혀 하나의 선과 비슷하게 나타날 것입니다. 이와 같이 중심극한정리[^1] 에 따라서 독립적인 확률변수의 평균이 정규분포에 가까워지기 때문에 수집된 자료의 분포를 근사하는 데에 정규분포가 자주 사용됩니다.

[f(x;\mu, \sigma) = \frac{1}{\sigma \sqrt{2 \pi}} \exp \bigg{-\frac{(x - \mu)^2}{2 \sigma^2}\bigg}
\mu : \text{mean} \qquad \sigma^2 : \text{variance}]

이미지 출처 : 위키피디아 - 정규분포

세 번째로 알아볼 것은 베타 분포(Beta distribution) 입니다. 베타 분포는 정규 분포와 비슷하게 생겼지만 사건값의 범위가 정해져 있다는 차이가 있습니다. 정규 분포에서 사건값의 범위는 $[-\infty, \infty]$ 입니다. 하지만 베타 분포의 사건값은 $[0,1]$ 범위를 갖습니다. 기호로는 $\text{Beta} (\alpha, \beta)$ 로 나타냅니다. 베타 분포는 특정한 모양을 가지고 있지 않으며 두 매개변수 $\alpha, \beta$ 의 값에 따라서 다양한 모양을 갖습니다. 수식으로는 아래와 같이 나타낼 수 있으며 각 $\alpha, \beta$ 에 따른 그래프는 아래와 같이 생겼습니다.

[f(\theta; \alpha, \beta) = \frac{\theta^{\alpha-1}(1-\theta)^{\beta-1}}{B(\alpha, \beta)}
B(\alpha, \beta) = \frac{\Gamma(\alpha)\Gamma(\beta)}{\Gamma(\alpha+\beta)}, \quad \Gamma(\alpha) = (\alpha -1)!, \quad \alpha \in N^+
\frac{\alpha}{\alpha + \beta} : \text{mean} \qquad \frac{\alpha\beta}{(\alpha + \beta)^2(\alpha + \beta+1)} : \text{variance}]

이미지 출처 : 위키피디아 - 베타분포

위에서 알아본 4가지 확률 분포(이항, 다항, 정규, 베타) 외에도 디리클레 분포, 푸아송 분포 등 수많은 확률 분포가 있습니다. 하지만 이번 게시물에서는 이정도만 알아보고 마치는 것으로 하겠습니다.

본 포스트는 문일철 교수님의 인공지능 및 기계학습 개론 I 강의를 바탕으로 작성하였습니다.

최대 우도 추정

본 챕터에서는 최대 우도 추정(Maximum Likelihood) 에 대해서 알아보겠습니다. 최대 우도 추정을 알기위해 필요한 이항 분포(Binomial distribution)에 대해서 알아봅시다.

Binomial Distribution(이항 분포)

아래와 같이 생긴 압정을 던져 가운데 압정처럼 뒤집어진 모양이 나올지, 아니면 양 옆에 위치한 압정처럼 엎어진 모양이 나올지를 예측하는 게임을 한다고 가정해봅시다. 이 때 편의상 엎어진 모양을 머리(Head, H)라고 하고 뒤집어진 모양을 꼬리(Tail, T)라고 표현합니다.

이미지 출처 : flicker.com

이 게임을 할 때 압정을 던지는 행위는 연속적(Continuous)이지 않습니다. 던지는 횟수가 1.123…번, 3.1415… 번과 같이 될 수 없고 1번, 2번, 3번 … 과 같이 일종의 마디를 가지고 증가하기 때문입니다. 그렇기 때문에 이 게임에서 압정을 던지는 행위는 이산적(Discrete)이라고 할 수 있습니다. 그리고 이산적인 행위에서 특정 사건이 발생할 확률의 분포를 이산 확률 분포(Discrete probability distribution) 라고 합니다.

그리고 이 게임에서 발생할 수 있는 사건은 오직 머리(H)와 꼬리(T), 즉 사건의 개수는 ‘2’ 입니다. 압정을 던지는 게임처럼 2가지 사건만을 가지는 것을 베르누이 시행(Bernoulli trial)이라고 부릅니다. 동전의 앞과 뒤, 특정 미션에 대한 성공 혹은 실패 등 다양한 상황에서 베르누이 시행을 찾아볼 수 있습니다.

이번에는 독립 항등 분포(independent and identical distributed, i.i.d) 에 대해서 알아봅시다. 단어의 듯에서도 알 수 있듯이 i.i.d는 독립적이며 동일한 확률 분포를 가지는 조건을 말합니다. 압정을 던지는 게임도 i.i.d 조건을 만족합니다. 압정을 한 번 던져 나온 사건의 결과는 이후 사건에 영향을 주지 않기 때문에 독립적(Independent)이라고 할 수 있습니다. 또한 압정을 던지는 행위의 확률 분포는 언제나 고유하기(Identical) 때문입니다.

위와 같은 것들이 가정되었다면 이 게임에서 특정 사건이 발생할 확률을 알 수 있습니다. 예를 들어, 압정을 5번 던져 (머리, 머리, 꼬리, 머리, 꼬리)가 나왔다고 합시다. 압정을 한 번 던져 머리가 나올 확률 $P(H) = \theta$ 라고 하면 (머리, 머리, 꼬리, 머리, 꼬리)의 순서대로 나타날 확률은 아래와 같이 나타낼 수 있습니다.

[P(HHTHT) = \theta \cdot \theta \cdot (1-\theta) \cdot \theta \cdot (1-\theta) = \theta^3 (1 - \theta)^2]

이를 일반화하면 $\theta$ 가 주어졌을 때 해당 데이터셋(Dataset) $D$ 가 발생할 확률인 $P(D \vert \theta)$ 로 나타낼 수 있습니다. 아래 식에서 $\alpha_H, \alpha_T$ 는 데이터셋 $D$ 에서 머리(H)와 꼬리(T)가 각각 발생한 횟수입니다. \(P(D|\theta) = \theta^{\alpha_H}(1 - \theta)^{\alpha_T}\) 위 식은 $HHTHT$와 같이 정해진 순서대로 나왔을 때의 확률을 일반화하여 나타낸 것입니다. 그렇다면 순서에 상관없이 머리와 꼬리가 나타날 확률은 어떻게 구할 수 있을까요? 위에서 나타냈던 특정 한 사건(여기서는 머리)이 발생할 확률 $\theta$ 를 $p$로, 그 사건이 $\alpha_H$ 를 $k$ 로 바꿔줍시다. 그러면 임의의 순서대로 구성된 $n$ 개의 사건 세트에서 발생할 확률이 $p$ 인 특정 한 사건이 $k$ 번 나올 확률을 아래와 같은 함수 $f$ 로 나타낼 수 있습니다.

[f(k;n,p) = P(K=k) = \left(\begin{array}{c}n\k\end{array}\right) p^k (1-p)^{n-k}
\because \left(\begin{array}{c}n\k\end{array}\right) = \frac{n!}{k!(n-k)!}]

Maximum Likelihood Estimation(최대 우도 추정)

특정 데이터셋으로부터 사건이 일어날 확률을 구하는 것은 중요합니다. 압정 게임이든 내일 비가 올 지 맑을지 예측하든 확률을 알아야 그에 맞춰 행동할 수 있기 때문입니다. 그렇다면 데이터셋 $D$ 로부터 압정 게임에서 머리(H)가 발생할 확률 $p$ 는 어떻게 추정할 수 있을까요? 우리가 알아볼 최대 우도 추정(Maximum Likelihood Estimation) 은 확률 $p$ 추정하기 위한 하나의 방법입니다. 최대 우도 추정은 말 그대로 현재 가지고 있는 데이터셋이 나올 확률을 최대화하는 우도(Likelihood) $\theta$ 를 구하는 것입니다. 아래 그래프는 최대 우도 추정을 설명하기 위한 그래프입니다. 수식으로는 아래와 같이 나타낼 수 있습니다.

[\hat{\theta} = \text{argmax}_{\theta} P(D \vert \theta)]

위 식에서 $\hat{\theta}$ 는 $P(D \vert \theta)$ 를 최대로 하는 $\theta$ 입니다. 예를 들어, 특정 사건의 확률 $\theta$ 가 [0,1] 사이의 범위일 때 특정 데이터셋 $D$ 가 나올 확률 $P(D \vert \theta)$ 가 아래 그래프의 붉은 곡선과 같다고 합시다. (주어지는 데이터셋 $D$ 에 따라 그래프의 모양은 달라질 수 있습니다.)

이미지 출처 : Stackoverflow.com

최대 우도 추정은 위 그래프에서 확률이 최대인 점의 $\theta$ 를 찾는 과정입니다. 주어진 데이터셋에 가장 Fit한 $\theta$ 를 찾는 과정이라고 말할 수 있겠습니다. 위에서 알아본 식을 다음과 같이 나타낼 수 있습니다.

[\hat{\theta} = \text{argmax}{\theta} P(D \vert \theta) = \text{argmax}{\theta} \theta^{\alpha_H}(1 - \theta)^{\alpha_T}
\hat{\theta} = \text{argmax}{\theta} \ln P(D \vert \theta) = \text{argmax}{\theta} { \alpha_H \ln \theta + \alpha_T \ln (1 - \theta) }]

위 첫 번째 식에서 구한 $\hat{\theta}$ 과 두 번째 식에서 구한 $\hat{\theta}$ 은 동일합니다. 로그 함수 $(\ln)$ 은 $[0,1]$ 에서 단조 증가 함수¹ 이므로 $\text{argmax}$ 이후의 식에 함수를 취해주어도 변화하지 않습니다. 우리의 목표는 $\text{argmax}$ 이후에 위치한 식이 최댓값일 때의 $\theta$ 를 찾는 것입니다. 특정 함수의 도함수가 0이되는 지점이 있다면 그 점이 원래 함수의 최댓값 혹은 최솟값일 가능성이 있습니다. 그렇기 때문에 식을 미분한 후, 미분한 식의 값이 0이 되는 $\theta$ 를 구할 수 있습니다.

[\begin{aligned} \frac{d}{d\theta}(\alpha_H \ln \theta + \alpha_T \ln (1 - \theta)) &= \frac{\alpha_H}{\theta} - \frac{\alpha_T}{1 - \theta} = 0
\theta &= \frac{\alpha_H}{\alpha_H + \alpha_T}
\therefore \hat{\theta}_{MLE} &= \frac{\alpha_H}{\alpha_H + \alpha_T} \end{aligned}]

이제 최대 우도 추정을 통해 특정 데이터셋이 주어졌을 때 그 데이터셋이 일어날 확률을 최대로 하는 특정 사건이 일어날 확률 $\theta$ 를 구해낼 수 있게 되었습니다.

Simple Error Bound(오차 범위)

위에서 알아본 바에 따르면 $\hat{\theta}$ 에 영향을 미치는 것은 $\alpha_H$ 과 $\alpha_T$ 의 비율입니다. 전체 횟수인 $n$ 이 커지더라도 이 비율만 지켜진다면 $\hat{\theta}$ 은 동일하게 됩니다.

동일한 비율을 가진 두 개의 데이터셋을 예로 들어봅시다. 한 데이터셋은 5번 던져 머리가 3번, 꼬리가 2번 나왔다고 합니다. 나머지 하나의 데이터셋은 50번 던져 머리가 30번, 꼬리가 20번 나온 경우입니다. 두 데이터셋 모두 최대 우도 추정을 통해 사건의 확률을 구하면 $\hat{\theta} = 0.6 = 3/(3+2) = 30/(30+20)$ 입니다. 그렇다면 두 데이터셋은 아무런 차이가 없는 것일까요? 데이터셋이 가지는 비율만 일정하다면 더 큰 데이터셋이 주는 이점은 없을까요?

질문에 대한 답은 “아니다”입니다. 일단 우리가 지금까지 알아본 $\hat{\theta}$ 은 그저 추정값일뿐 실제 확률이 아닙니다. 추정값은 언제나 실제값과 오차가 있기 마련입니다. 오차는 둘 사이의 차이이므로 절댓값을 활용하여 $\vert \hat{\theta} - \theta^* \vert$ 로 나타낼 수 있습니다. 수학자들은 이 오차에 수학적 기술을 적용하여 오차의 범위(Error bound) 를 구하는 식을 만들어 놓았습니다. 오차의 범위를 구하는 식은 아래와 같습니다.

[P(\vert \hat{\theta} - \theta^* \vert \geq \epsilon ) \leq 2e^{-2N \epsilon^2}
\because N = a_H + a_T]

위 식을 보면 오차가 임의의 작은 값 $\epsilon$ 보다 커질 확률은 $2e^{-2N \epsilon^2}$ 로 나타납니다. 즉, $\epsilon$ 이 동일한 조건에서는 실행횟수 $N$ 이 증가할수록 오차의 범위가 줄어들게 된다는 의미입니다. 이러한 학습 방식을 팩 학습(Probably Approximate Correct learning, PAC learning)이라고 합니다. PAC learning의 목적은 높은 확률(Probably)로 낮은 오차 범위(Approximately Correct)를 갖도록 하는 것입니다. 즉 이를 달성하기 위해서는 데이터셋이 많아야 하고, 향후 머신러닝에서 커다란 데이터셋이 중요한 이유도 이 때문입니다.

최대 사후 확률 추정

사전 지식 포함시키기

지금까지 최대 우도 추정에 대해 알아보았습니다. 하지만 최대 우도 추정말고도 확률 $\theta$ 를 추정하기 위한 다른 관점의 방법이 있습니다. 이를 최대 사후 확률 추정(Maximum a Posterior Estimation) 이라고 합니다. 최대 우도 추정이 주어진 데이터셋 $D$ 가 나올 가능성을 최대로 하는 $\theta$ 를 구하는 것이었다면, 최대 사후 확률 추정은 말 그대로 사후 확률(Posterior)을 최대화 하는 과정입니다. 그렇기 때문에 최대 우도 추정에서는 사용하지 않았던 사전 지식(Prior knowledge)에 대한 Term이 추가됩니다. 아래는 베이즈 정리²를 사용하여 사후 확률을 구하는 수식입니다.

[\begin{aligned} P(\theta \vert D) &= \frac{P(D \vert \theta) P(\theta)}{P(D)}
\text{Posterior} &= \frac{\text{Likelihood}\times \text{Prior Knowledge}}{\text{Normalizing Constant}} \end{aligned}]

베이즈 관점에서 바라보기

위에서 구한 식에서 $P(D)$ 는 $P(\theta \vert D)$ 를 $[0,1]$ 사이의 값으로 만들어주기 위한 정규화 상수(Normalizing Constant) 입니다. 해당 상수는 사후 확률에 아무 영향을 주지 않기 때문에 $P(\theta \vert D) \propto P(D \vert \theta) P(\theta)$ 로 나타낼 수 있습니다.

그렇다면 사전 지식에 해당하는 $P(\theta)$ 는 어떻게 구할 수 있을까요? 압정을 던지는 행위와 같은 베르누이 시행이라면 베타 분포(Beta distribution)를 사용합니다. 베타 분포에 대한 더 자세한 이야기는 확률 분포 에서 볼 수 있습니다. 여기서는 그냥 이 분포를 사용한다는 것만 알아두고 넘어가도록 합시다. 베타 분포를 사용하여 사전 확률 $P(\theta)$ 을 추정하면 다음과 같습니다.

[P(\theta) = \frac{\theta^{\alpha-1}(1 - \theta)^{\beta-1}}{B(\alpha, \beta)}
B(\alpha, \beta) = \frac{\Gamma(\alpha)\Gamma(\beta)}{\Gamma(\alpha + \beta)} ,\quad \Gamma(\alpha) = (\alpha-1)!]

Maximum a Posteriori Estimation(최대 사후 확률 추정)

이제 $P(D \vert \theta) P(\theta)$ 식에서 각 항의 값을 알고 있으므로 아래과 같이 식을 정리할 수 있습니다.

[P(D \vert \theta) P(\theta) = \theta^{\alpha_H}(1 - \theta)^{\alpha_T} \cdot \theta^{\alpha-1}(1 - \theta)^{\beta-1} = \theta^{\alpha_H + \alpha -1}(1 - \theta)^{\alpha_T +\beta-1}]

최대 사후 확률 추정에서 우리의 목표는 사후 확률인 $P(\theta \vert D)$ 를 최대화하는 것입니다. 수식으로는 $\text{argmax}$ 를 사용하여 아래와 같이 나타낼 수 있습니다.

[\hat{\theta} = \text{argmax}_{\theta} P(\theta \vert D)]

위에서 알아본 바와 같이 $P(D)$ 는 상수이므로 위 식을 아래와 같이 변형해주어도 $\hat{\theta}$ 의 값은 변하지 않습니다.

[\hat{\theta} = \text{argmax}{\theta} P(D \vert \theta) P(\theta) \qquad
\qquad \quad = \text{argmax}{\theta} [\theta^{\alpha_H + \alpha -1}(1 - \theta)^{\alpha_T +\beta-1}]]

이제부터는 최대 우도 추정에서 했던 과정을 동일하게 해주면 됩니다. $\text{argmax}$ 이하의 식에 로그를 취해준 뒤 미분하여 그 값이 0이 되는 $\theta$ 를 찾아줍니다.

[\begin{aligned} \hat{\theta} &= \text{argmax}{\theta} [\theta^{\alpha_H + \alpha -1}(1 - \theta)^{\alpha_T +\beta-1}]
&= \text{argmax}{\theta} \ln [\theta^{\alpha_H + \alpha -1}(1 - \theta)^{\alpha_T +\beta-1}]
&= \text{argmax}_{\theta}[(\alpha_H + \alpha -1) \ln \theta + (\alpha_T +\beta-1) \ln (1 - \theta)] \end{aligned}]

[\begin{aligned} \frac{d}{d\theta}[(\alpha_H + \alpha -1) \ln \theta + (\alpha_T +\beta-1) \ln (1 - \theta)] &= 0
\frac{(\alpha_H + \alpha -1)}{\theta} - \frac{(\alpha_T + \beta -1)}{1-\theta} &= 0 \end{aligned}]

마지막 방정식 $\theta$ 에 관해서 정리하면 아래와 같다

[\hat{\theta}_{MAP} = \frac{\alpha_H + \alpha -1}{\alpha_H + \alpha + \alpha_T +\beta - 2}]

최대 우도 추정과 최대 사후 확률 추정을 통해 추정한 특정 사건의 확률 $\theta$ 는 비슷한 모양새를 띠고 있지만 완전히 같지는 않습니다. 베타 분포 내의 상수가 $\alpha=\beta=1$ 일 경우에만 서로 같아집니다. 하지만 시행 횟수 $N$ 이 커지면, 데이터셋의 크기가 커질수록 상수인 $\alpha, \beta$ 에 비해 $\alpha_H , \alpha_T$ 가 커지게 됩니다. 그렇기 때문에 $N$ 이 커질수록 최대 우도 추정으로 구한 $\theta$ 와 최대 사후 확률 추정으로 구한 $\theta$ 가 비슷해집니다.

Models

이번 게시물에서는 컴퓨터 비전 분야에 사용되어온 모델들에 대해서 알아보겠습니다. 블로그에서는 비전에 대해서는 깊게 다루고 있지 않으므로 모델의 이름과 구조만 간단하게 소개하도록 하겠습니다.

AlexNet

가장 첫 번째는 대표적인 모델인 알렉스넷(AlexNet)입니다. 알렉스넷은 2012년 이미지넷(ImageNet)¹ 데이터 분류 대회에서 우승하며 큰 주목을 받았습니다. 아래는 알렉스넷의 구조입니다.

이미지 출처 : neurohive.io

총 5개의 합성곱 층을 사용하고 있으며 2개의 완전 연결 층을 사용하고 있는 것을 볼 수 있습니다.

VGG

이후로 소개될 모델은 위 알렉스넷보다 층을 더 깊게 쌓은 모델입니다. 층을 더 깊게 쌓으면 어떤 점이 좋을까요? 우선, 층을 깊게 하면 신경망에 있는 파라미터의 수가 줄어듭니다. 층을 깊게 하면 적은 파라미터로도 높은 수준의 표현력을 달성할 수 있기 때문입니다. 한 개의 층에서 $5 \times 5$ 크기의 필터를 사용하여 하나의 출력값을 낼 때에는 $5 \times 5 = 25$개의 파라미터가 필요합니다. 하지만 $3 \times 3$ 필터를 사용하여 $2$층으로 쌓으면 $3 \times 3 \times 2 = 18$ 개의 파라미터 만으로도 같은 크기의 공간을 표현할 수 있게 됩니다.

이 차이는 층을 더 깊게 쌓으면 더 커집니다. 한 개의 층에서 $9 \times 9$ 크기의 필터를 사용하면 $9 \times 9 = 81$개의 파라미터가 필요하지만, $3 \times 3$ 크기의 필터를 $4$층으로 쌓으면 $3 \times 3 \times 4 = 36$ 개의 파라미터만으로 동일한 공간을 학습하게 됩니다. 이렇게 층을 깊게 쌓으면 한 층에서 학습해야 하는 정보의 양도 줄어들기 때문에 학습 시간을 더욱 빠르게 할 수 있다는 장점이 있습니다.

VGG16은 Visual Geometry Group에서 개발한 이미지 분류를 위한 합성곱 신경망 모델입니다. 13개의 합성곱 층과 3개의 완전 연결 층까지 무려 16개의 층을 쌓았기 때문에 이런 이름이 붙었습니다.

이미지 출처 : neurohive.io

VGG의 특징은 다음과 같은 것들이 있습니다. 첫 번째로 모든 합성곱 층에서 $3 \times 3$ 크기의 작은 필터를 사용하였습니다. 대신 층을 깊게 쌓음으로써 기존에 사용하던 $7 \times 7$ 혹은 $11 \times 11$ 크기의 필터를 사용했을 때와 동일하거나 더 높은 표현력을 가질 수 있게된 것이지요. 두 번째로 활성화 함수로 ReLU를 사용하였으며 가중치 초깃값으로는 He초깃값을 사용하였습니다. 덕분에 층을 깊게 쌓았음에도 기울기 소실(Gradient vanishing)문제를 해결할 수 있었습니다. 마지막으로 완전 연결 층 뒤에 드롭아웃(Dropout)을 사용하여 과적합을 방지하였으며 옵티마이저로는 아담(Adam)을 사용했다는 특징이 있습니다.

VGG16은 14년 이미지넷 대회에서 앞서 소개한 알렉스넷(AlexNet)의 오차율을 반으로 줄임으로써 이미지 인식 분야에서 큰 향상을 가져왔다는 의의를 가지는 모델입니다. 층의 개수를 변형한 모델인 VGG13, VGG19도 존재합니다. 모델의 구조가 단순하기에 VGG를 다양하게 응용하여 사용하는 사례도 많습니다.

GoogLeNet

GoogLeNet은 말 그대로 구글이 발표한 모델이며, 오래 전 이미지 인식 분야에서 획기적인 성능을 나타내었던 LeNet의 이름을 땄습니다. GoogLeNet역시 기본적인 합성곱 신경망 형태를 띠고 있습니다. 하지만 세로 방향의 깊이 뿐만 아니라 가로 방향으로도 넓은 신경망 층을 가지고 있다는 것이 특징입니다. GoogLeNet의 구조는 아래와 같습니다.

이미지 출처 : bskyvision.com

이렇게 가로 방향으로 층을 넓게 구성한 것을 인셉션 구조라고 합니다. GoogLeNet에서는 인셉션 구조를 활용하여 크기가 다른 필터와 풀링을 병렬적으로 적용하여 그 결과를 조합합니다. 위 그림에서 파란색 층은 필터가 적용되는 합성곱 층이며 빨간 색은 풀링 층입니다. GoogleNet은 인셉션 기법을 통해 2015년 이미지넷 대회에서 VGG보다 더 좋은 성능을 달성한 모델입니다.

ResNet

ResNet은 스킵 연결(Skip connection)이라는 기법을 적용하여 성능을 향상시킨 모델입니다. 이를 수행하는 구간을 Residual block 이라고도 부르는데 이로부터 ResNet이라고 이름을 붙였습니다. 스킵 연결이 적용되는 과정을 도식화하면 아래와 같습니다.

이미지 출처 : programmersought.com

스킵 연결을 사용하면 입력 $x$를 연속한 두 합성곱 계층을 뛰어넘어 그 출력값에 바로 더해줍니다. 스킵 연결이 없다면 2개의 층을 지난 후의 출력은 $F(x)$가 되지만, 스킵 연결을 사용하면 출력값 $F(x)$에 입력값 $x$ 를 그대로 더해주어 최종 출력값을 $F(x) + x$ 로 만들어 줍니다. 이 방법은 역전파를 통하여 학습하는 과정에서 너무 작은 그래디언트를 보내지 않도록 합니다. 아래는 스킵 연결을 적용한 ResNet의 전체 구조를 나타낸 이미지입니다.

이미지 출처 : developer.ridgerun.com

위 그림에서 ResNet은 인셉션 구조를 사용하지 않았다는 것을 볼 수 있습니다. 오히려 수직으로만 층을 쌓은 VGG와 더욱 비슷하다고 볼 수 있습니다. 하지만 VGG16의 2배가 넘는 34개의 층을 사용하였으며 이로 인해 발생하는 기울기 소실 문제를 스킵 연결로 극복하고 있다는 것을 알 수 있습니다.

이런 스킵 연결은 ResNet뿐만 아니라 자연어처리의 트랜스포머(Transformer) 등의 다양한 모델에도 사용되고 있습니다. ResNet은 이러한 스킵 연결을 적용한 모델이라는 의의를 가지고 있습니다.

Problems

합성곱 신경망을 활용한 여러 모델은 이미지 처리 분야에서 엄청난 성능을 보여왔지만 여전히 풀어야할 숙제도 있습니다. 첫 번째는 합성곱 층에서의 연산 횟수 문제입니다. 합성곱 신경망은 각 필터가 옮겨가면서 파라미터 개수만큼의 곱연산을 실행하므로 큰 이미지를 처리할 때에는 엄청나게 많은 횟수의 연산을 수행해야 합니다. 이런 많은 연산을 수행하기 위해 GPU컴퓨팅을 통한 고속 연산과 병렬 분산 학습 등 많은 기법이 고안되고 있습니다.

메모리 사용량도 문제입니다. 필터의 개수가 많아질수록 저장해야 하는 가중치 매개변수가 많아집니다. 많은 메모리를 확보하는 것도 하나의 해결방법이 될 수 있지만, 이는 어느정도 한계가 있습니다. 이를 해결하기 위하여 딥러닝에서는 간단한 부동소수점 표현을 사용합니다. 컴퓨터에서는 일반적인 연산을 위해 64bit 혹은 32bit의 부동소수점을 사용하지만, 딥러닝에서는 16bit 반정밀도를 사용하여 연산하여도 큰 문제가 없는 것으로 알려져 있기 때문에 이정도 수준의 표현을 사용하여 메모리를 절약합니다.

Various uses

이미지 처리 분야에서는 이러한 모델을 다양한 분야에 사용하고 있습니다. 첫 번째는 사물 검출(Object detection)입니다. 이는 이미지 속에 담긴 사물의 위치와 그 사물의 클래스를 알아내기 위한 기술입니다. 이를 위해서 R-CNN(Regions with convolutional neural network)류의 모델을 사용합니다.

두 번째는 분할(Segmentation)입니다. 이는 이미지를 픽셀 수준에서 구분하는 기술입니다. FCN(Fully convolutional network) 류의 모델이 이런 역할을 할 수 있습니다. 이런 기술들을 활용하여 컴퓨터가 보는 사물을 구분하고 그 사물의 위치를 인지할 수 있기 때문에 자율 주행을 포함한 여러 분야에 사용할 수 있습니다.

또한, VAE(Variational autoencoder)이나 GAN(Generative adversarial network)등을 사용하는 생성 모델도 활발히 연구되고 있는 분야입니다.