DataManyo

4.1:

충돌되는 데이터conflicting data(즉, 특성 벡터가 완전히 같지만 레이블은 다른)를 포함하지 않는 훈련 세트에 대해, 훈련 세트와 일치(훈련 오차가 0인)하는 의사결정 트리가 반드시 존재한다는 사실을 증명하라.

참고 답안1.

훈련 데이터셋과 일치하는 의사결정 트리가 존재하지 않는다고 가정한다면, 훈련 데이터셋으로 훈련해 얻은 의사결정 트리의 최소 한개의 노드상에 분할할 수 없는 데이터가 있어야한다(만약 노드상에 conflicting data가 없다면 해당 데이터는 분리 가능해야 한다). 이는 전제(충돌되는 데이터를 포함하지 않는다)와 모순되기 때문에 반드시 훈련데이터셋과 일치하는 의사결정 트리가 있어야 한다.

참고답안2.

단단한 머신러닝 책 그림4.2에 나오는 알고리즘 설명에 따르면, 노드를 생성하는 3가지 상황은 다음과 같다:

1,2,3 총 3가지 상황으로 정리가 가능한데, 

이 문제의 목적은 훈련 데이터셋과 일치하는 의사결정 트리를 찾는 것이기 때문에 3번째 포인트는 고려하지않아도 된다.  1,2,번 상황만 고려하면 의사결정 트레에서 가지가 잎 노드 생성을 멈출 때는 샘플이 모두 같은 클래스에 속하거나 모든 특성(feature)을 다 사용했을 때이다. 그렇다면 잎노드 레이블과 실제 훈련셋이 다를 경우는 특성을 모두 다 사용한 상황일 것이다. 하지만 훈련셋에 충돌 데이터가 없다고 했기 때문에 각 노드상에 훈련 오차는 모두 0이 된다.