[ML] Reduced Error Pruning

Decision Tree Training은 가장 널리 사용되는 machine learning 방법론 중 하나이다. 이 중 자주 사용되는 것은 ID3, ASSISTANT, C4.5가 있다. 여기서는 ID3의 간략한 소개와 ID3의 pruning 방법 중 하나인 Reduced Error Pruning에 대해서 다루어보고자 한다.

Decision Tree의 간략한 소개

Decision Tree는 학습에 Tree 형태의 decision tree를 사용한다. 다음과 같은 모양이다.

전체 형태를 보면 맨 위의 root node, 중간의 branch node, 말단의 leaf node로 구성되어 있다. 말단 노드인 leaf node에 class label이 붙어 있는 것을 알 수 있고, branch node는 특성들의 분류지점(conjunction)이 된다.

decision tree는 target variable이 이산적이냐, 연속적이냐에 따라서 classification tree와 regression tree로 나눌 수 있다.

figure 1은 여러 가지 attribute에 따라 그 날 테니스 경기를 하거나 하지 않았을 지 예측하기 위한 모델이다. root node에서는 날씨를 기준으로 나누고 있고, Sunny인 경우 다시 Humidity로 나누고, Overcast인 경우에는 반드시 테니스 경기를 했다고 본다. Rain인 경우에는 비가 많이 올 경우 테니스 경기를 취소할 것이라고 예측하고, 비가 적게 오면 테니스 경기를 정상적으로 진행할 것이라고 예측하는 식이다.

이러한 방법은 deep neural network 모델(black box)과는 다르게 왜 그런 선택을 했는지 쉽게 알 수 있다(white-box or open-box). 또한 모든 data가 특정한 수의 형태로 preprocessing 되어야 하는 network와는 다르게, 어떤 형태의 데이터도 사용할 수 있다는 장점이 있다.

실제 구현은 recursive partitioning으로 이루어지고, 각 단계에서 현재 set을 가장 잘 나눌 수 있는 기준으로 분류한다는 점에서 Greedy algorithm으로 분류할 수 있다.

ID3 algorithm

그럼 여기서 데이터를 나누는 기준을 무엇으로 설정해야 가장 좋을까? ID3 algorithm에서는 entropy와 information gain을 사용하여 그 기준을 정한다.

사건 $x$의 정보량을 나타내는 information function은 다음과 같이 정의된다 :

$$ I(x) := log_2 {1 \over p(x)} $$

이때 $p(x)$는 사건 $x$가 발생할 확률이다. 확률의 역수이므로 발생할 확률이 0에 수렴하면 정보량은 무한대로 발산한다. 만약 항상 발생하는 확률이라서 1이라면 정보량은 0이다. '해가 동쪽에서 뜬다'는 정보로서 어떠한 새로운 정보를 주지 않는 것을 생각해 보면 된다.

이에 따라 entropy는 다음과 같이 정의된다.

$$ E(S) := \sum^c_{i=1}p_i I(X_i) = \sum^c_{i=1}p_i \log_2{1 \over p(X_i)} = \sum^c_{i=1}p_i \log_2 {1 \over p_i} $$

entropy는 어떤 sample들의 집합의 (im)purity를 보여주는 척도이다. 어떤 집합이 하나의 결과값만 가진다면, entropy는 최소가 된다. 반대로, 어떤 집합의 여러 값이 같은 개수로 분포한다면 entropy는 최대가 된다. 정보이론에서 entropy를 이해하는 한 가지 방법은, 임의의 집합 $S$를 encoding하는데 필요한 bit의 최소 개수로 보는 것이다.

Figure 2 : boolean classification의 경우, 한 쪽으로 분포할 경우 entropy는 줄어든다.^[각주:4]

Information Gain $G$는 다음과 같이 정의된다.

$$Gain(S,A) \equiv Entropy(S) - \sum _{v\in Values(A)} {|S_v| \over |S|}Entropy(S_v)$$

Information Gain은 특정 attribute로 example을 나누었을 때, 줄어들 것으로 예상되는 entropy로 이해할 수 있고, entropy가 많이 줄어들수록 Gain 값은 커진다. 즉, decision tree에서 전체 데이터를 더 잘 나누는 attribute가 information gain이 더 크다.

이런 식으로 entropy가 0이 되는 경우 leaf node로 만들고, 그렇지 않을 경우 information gain이 최대가 되는 attribute를 찾아서 branch를 늘려가는 방식을 ID3 algorithm이라고 한다.

Overfitting Problem

하지만, ID3에는 문제가 있는데, training data의 accuracy를 높이려고 tree의 size를 키울 수록 test data의 accuracy는 감소한다는 것이다. Figure 4를 보자.

실선은 training data의 accuracy고, 점선은 test data의 accuracy이다. training data의 accuracy가 monotonically increase하는 데 반해, test data의 accuracy는 잠시 증가하다가 곧바로 감소한다. size of tree가 증가할수록 더 감소한다. tree의 size가 커질 수록 overfitting의 문제가 심하게 발생하고 있는 것이다.

Overfitting의 문제를 해결하기 위해서 제안된 방법이 Reduced Error Pruning과 Rule Post-Pruning이다. Rule Post-Pruning을 적용한 ID3 algorithm을 C4.5 algorithm이라고 한다. 여기서는 Reduced Error Pruning에 대해 다룬다.

Reduced Error Pruning (REP)

Reduced Error Pruning은 Quinlan(1987)에 의해 제안된 방식이다. 처음 Quinlan의 서술은 다음과 같다.

For every non-leaf subtree $S$ of $T$ we examine the change in misclassications over the test set that would occur if $S$ were replaced by the best possible leaf. If the new tree would give an equal or fewer number of errors and $S$ contains no subtree with the same property, $S$ is replaced by the leaf. The process continues until any further replacements would increase the number of errors over the test set.
[...] the final tree is the most accurate subtree of the original tree with respect to the test set and the smallest tree with that accuracy.

요약하면, tree 내에 존재하는 leaf가 아닌 모든 subtree에 대해서, 그 subtree를 leaf node로 바꿨을 때, accuracy가 같거나 증가하면, leaf로 바꾸는 방식으로 진행한다는 이야기이다.

이런 진술은 algorithmical하지 않으므로, 어떻게 구현할 지 명확하게 알 수 없다. 따라서 REP을 이름으로 하는 여러 가지 알고리즘이 제안되었다. 크게 나누자면 bottom-up 방식과 iterative한 방식이다. 원래 진술은 이 두 가지 모두 포함한다고 볼 수 있다.

Oates & Jensen의 REP algorithm

Oates & Jensen(1997, 1998, 1999)는 Quinlan의 진술을 보고, single-scan bottom-up strategy를 제안했는데, 이 방법은 다음과 같이 진술된다.

single bottom-up sweep에 의해 pruning된다. node는 postorder로 process된다.

이 경우 pruning의 cadidate이 되는 node는 pruning의 대상이 되는 subtree를 포함할 수 없다. bottom-up 방식이므로 당연한 이야기인데, 어떤 subtree가 pruning이 대상이 될 지 확인한다는 것은, 그 subtree의 children node들이 postorder traversal에 따라서 먼저 탐색되었고 children node 중 pruning되어야 하는 node가 있었다면, 이미 모두 pruning이 완료된 이후일 것이기 때문이다.

하지만, 이 알고리즘은 Esposito et al.(1993, 1997)에 의해서 항상 optimal solution을 주지는 않는 것으로 증명되었다.

따라서, 이 방법을 수정한 방법이 오늘날에는 일반적으로 사용된다.

Leaf Labeling

Quinlan(1987)의 서술에서는 어떻게 각 node를 labeling할 지 명확하게 규정하지 않아서 혼란을 야기하기도 했다. Oates & Jensen(1999)는 Quinlan(1987)의 서술이 pruning에 의해 새로 만들어진 leave를 training example의 majority로 label한다고 쓰여진 것으로 보았는데, 그들 스스로는 pruning example의 majority로 label하는 것이 더 좋다고 보았다. 그러나 실상 별 차이는 없다.

이 말을 이해하려면 REPTree algorithm에서 training procedure에 training data와 pruning data가 사용된다는 점을 알아야 한다. 먼저 ID3 algorithm에 의해서 training data를 entropy가 0이 될 때까지 recursive하게 partitioning하고, tree가 모두 만들어진 이후에, pruning data를 같은 tree에 넣어서 분류한 다음, pruning한다. 이때, 보통 pruning data의 개수는 training data의 개수보다 적다.

그럼 이제 training example의 majority로 새로운 leaf node를 labeling하는 방법과, pruning example의 majority로 labeling하는 방법을 구체적 예시를 이용하여 비교해 보자.

figure 5는 training example로 만들어진 decision tree를 이용하여 pruning example을 분류한 상황을 보여준다. leaf node 밑에 있는 $x/y$는 각각 negative example의 개수와 positive example의 개수를 의미하고, node에 써 있는 부호는 그 node가 negative로 분류하는지, positive로 분류하는지를 보여준다. node의 부호는 원래 Quinlan의 방법대로 training example의 majority에 따라 부여된 것이다.

figure 5의 결과를 보면, 현재 상태의 error는 leaf node에서 각각 1개, 0개, 0개, 2개 발생하였다. 만약 이 tree를 pruning한다고 하면, depth가 1인 node들에서 pruning을 하게 되면,

이런 형태가 될 것이다. 이때 error의 개수는 총 6개가 되므로, 이러한 pruning은 하지 않게 될 것이다. 하지만 만약 이 상태에서 추가로 depth 1의 node들도 pruning을 하여 root node만 남겨놓으면 어떻게 될까?

이런 형태가 될 것이다. 주목할 만한 점은, 이 때의 error는 총 2개로, pruning을 하지 않은 경우보다도 accuracy가 증가했다는 점이다. 따라서 이렇게 pruning되는 형태가 바람직하지만, figure 6의 형태대로 pruning을 하지 못하기 때문에 이런 pruning은 사실상 일어나지 않는다. 즉, 이렇게 pruning을 더 하는 경우에 accuracy가 증가함에도 불구하고, 그 subtree에서 pruning되지 않아 전체의 optimal solution을 제공하지 못한다는 것이 training example의 majority로 leaf labeling을 하는 경우에 발생하는 문제이다.

하지만 pruning example로 leaf labeling을 하면 이런 문제는 해결된다. 다시 figure 5로 돌아가서 pruning을 해 보자.

이때는 leaf node의 label이 각각 majority인 positive와 negative로 label된다. 이 경우는 error가 총 0개이므로 효율적인 결과를 산출하였음을 알 수 있다. Figure 6의 형태로 pruning도 이루어질 수 있다. 물론 pruning할 경우 accuracy가 떨어지므로 실제로 그렇게 되지는 않을 것이다. 이러한 점이 pruning example로 leaf labeling하는 경우의 장점이다.

그러나 training example의 개수가 pruning example보다 많으므로, training example을 고려하는 모델이 더 robust한 것으로 생각될 수 있다. 따라서 둘 다 고려하는 것이 일반적이다.

Empty subtree

한 가지 더 고려할 사항은, REPTree algorithm의 경우 tree를 construct할 때에와 pruning할 때 다른 dataset을 쓰기 때문에, pruning phase에서 tree의 일부분이 어떠한 data도 받지 못할 수도 있다는 것이다. 이렇게 classification 과정에서 어떠한 pruning data도 받지 못한 tree의 부분을 empty subtree라고 한다.

empty subtree를 어떻게 다루어야 할 지에 대해서는 명확하지 않고, 많은 논의가 이어져 왔다. Quinlan(1987)도 이런 경우를 예견하였고, 이런 부분은 제거되어야 한다고 보았다.

실제로는 관점에 따라,

training set의 도움을 받을 수도 있고,
training set에만 존재하는 data 때문에 만들어졌다고 보고 잘라내는 것도 방법이다.

REP에서는 잘라내는 방법이 선호된다.

REP pseudocode

이는 Tapio Elomaa & Matti Kääriäinen(2001)에 의해서 정리된 버전이다. 크게 어려운 것은 없으니 쭉 따라가 보면 된다. 간단히 설명하자면, REP 함수에서 DecisionTree T와 ExampleArray S를 받는다. ExampleArray는 pruning dataset을 의미한다. classify 함수에서 각 subtree에 positive sample의 개수와 전체 sample의 개수를 저장한다. prune 함수에서는 leaf node가 아니면 recursive하게 postorder로 pruning한다. 만약 pruning했을 때 error가 줄어든다면, pruning하고, leaf label은 pruning example의 majority로 붙인다.

References

김의중. (2016). 알고리즘으로 배우는 인공지능, 머신러닝, 딥러닝 입문. 위키북스.
Mitchell, T. M. (1997). Machine Learning. McGraw Hill.
Tapio Elomaa & Matti Kääriäinen. (2001). An Analysis of Reduced Error Pruning. In Journal of Artificial Intelligence Research 15, pp. 163-187,

Footnotes

사진 출처 : machine learning (McGraw-Hill) [본문으로]
사진 출처 : machine learning (McGraw-Hill) [본문으로]
사진 출처 : machine learning (McGraw-Hill) [본문으로]
사진 출처 : machine learning (McGraw-Hill) [본문으로]
사진 출처 : machine learning (McGraw-Hill) [본문으로]
사진 출처 : machine learning (McGraw-Hill) [본문으로]
사진 출처 : machine learning (McGraw-Hill) [본문으로]
사진 출처 : machine learning (McGraw-Hill) [본문으로]
사진 출처 : Tapio Elomaa &amp; Matti Kaariainen(2001) [본문으로]
사진 출처 : Tapio Elomaa & Matti Kaariainen(2001) [본문으로]
출처 : Tapio Elomaa &amp; Matti Kaariainen(2001) [본문으로]
출처 : Tapio Elomaa & Matti Kaariainen(2001) [본문으로]

'DL·ML' 카테고리의 다른 글

[paper review] Efficient Estimation of Word Representations in Vector Space (Word2Vec) (0)	2022.07.06
[DL] Hierarchical Softmax (0)	2022.07.01
[DL] RNN(Recursive Neural Network)의 이해 (0)	2021.12.26
Xavier initializer (0)	2021.12.22
[paper review] ImageNet Classification with Deep Convolutional Neural Network (AlexNet) (0)	2021.11.29