edwith에 올라와있는 문인철 교수님의 인공지능 및 기게학습 개론1을 공부하여 정리한 내용입니다.

현실에서 noise가 있기에 rule based learning을 사용하기 어렵다. 그래서 noise를 다루기 위해 간단한 알고리즘인 Deicision Tree를 알아보자.

Credit Approval Dataset

• Decision Tree의 예시를 위해 Credit Approval Dataset을 사용해보자.
• 
• A1 ~ A15까지는 개인들의 신용을 평가하는 기반 자료인 attribute 이고, C는 positive 인지 negative인지 판단한 class variable이다.
• 간단한 트리를 만들어보면
• 
• A1 attribute를 사용한 경우가 A9를 사용한 경우보다 더 좋지 못한 판단을 내렸다.
• 이처럼 어떤 요소를 선택하는지 또 몇개를 선택하는지는 상당히 중요한 요소이다.
• 그럼 몇개의 어떤 요소를 선택해야할까?

Entropy

• 앞선 예제에서 A1를 사용한 경우가 A9 사용한 경우보다 uncertainty가 더 높았다.
• 이를 어떻게하면 표현할 수 있을까? 이때 사용되는 것이 Entropy이다.
• Entropy는 불확실성이 높을 수록 높다. 조금 더 이해하기 쉽게 이야기 하자면 정보를 많이 가지고 있을 수록 즉, 평균 정보량이 높을 수록 높다.
  $H(X)=-\sum_X P(X=x) \log _b P(X=x)$
• 식으로는 위와 같이 표현 된다.

Conditional Entropy

• 주어진 특정 feature가 있을 때 entropy는 다음과 같이 표현 된다.
  
• 조건부 확률과 유사하게 나타나고 앞에 있는 $P(X=x)$는 마치 Prior Knowledge이 주어진 것 같은 형태로 나와있다.
• X가 주어졌을 때 Y의 Entropy를 측정하는 것이다.

Information Gain

• 위의 예시를 통해 생각해보자.
• 
• $P(Y=y)$는 MLE 관점에서 $\frac{307}{307+383}$이다.
• 우리의 목표는 불확실성을 최대한 없애는 것이다. 즉, $H(Y)$와 $H(Y \mid A_i)$의 차이가 가장 커지게 하는 $A_i$를 찾는 것이다. (엔트로피가 더 크게 감소 했음으로)
• 이러한 차이를 Information Gain이라고 하고 이 예시에서는 다음과 같이 나타낼 수 있다.
• 

Top-Down Induction Algorithm

• Decision Tree에는 다양한 알고리즘들이 있다. 그 중에서는 우리는 ID3 알고리즘을 알아보겠다.

ID3 algorithm

• 이를 통해 실제로 decision tree를 만들어보면 다음과 같다.
  

Problem of Decision Tree

• 그럼 더 많은 tree를 만들면 Dataset을 완벽하게 만들 수 있지 않을까?
• 그렇다. 적어도 우리가 관측한 Dataset에는 더 정확하게 분류할 수 있다.
• 하지만 현실은 Noise와 Inconsistencies한 데이터가 있기 때문에 tree의 사이즈가 커질 수록 현실 데이터에 대한 성능은 떨어지게 된다.
• 
• Size of tree를 클수록 noise에 대한 오류가 커지기 때문에 오히려 성능이 떨어지게 된다.