위키피디아 내용 정리

1. Random Forest

1.1 도입

1.1.1 정의

  • 분류, 회귀 분석 등에 사용되는 앙상블 학습 방법의 일종
  • 훈련 과정에서 다수의 결정 트리로부터 분류 또는 회귀분석을 출력

1.1.2 역사

  • Random Subset(임의의 부분 집합)에 대해 검색하는 아이디어를 도입
  • Random Subspace(임의의 부분 공간)을 선택하는 틴 캄 호(Tin Kam Ho)의 아이디어도 영향 미침
  • Leo Breiman이 randomized node optimization과 bootstrap aggregating을 결합한 방법인 CART(classification and regression tree)를 사용해 상관관계가 없는 트리들로 포레스트를 구성

1.1.3 동기

  • 일반적으로 결정 트리를 이용한 방법의 경우, 그 결과 또는 성능의 변동 폭이 크다는 결점을 가지고 있다. 특히 학습 데이터에 따라 생성되는 결정트리가 매우 달라지기 때문에 일반화하여 사용하기에 매우 어려움이 따른다. 특히, 결정 트리는 계층적 접근방식이기 때문에 만약 중간에 에러가 발생한다면 다음 단계로 에러가 계속 전파되는 특성을 가진다. 배깅 또는 임의 노드 최적화(randomized node optimization)과 같은 임의화 기술은 결정 트리가 가진 이러한 단점을 극복하고 좋은 일반화 성능 갖도록 한다.

1.1.4 기여

  • 월등히 높은 정확성
  • 간편하고 빠른 학습 및 테스트 알고리즘
  • 변수소거 없이 수천 개의 입력 변수들을 다루는 것이 가능
  • 임의화를 통한 좋은 일반화 성능
  • 다중 클래스 알고리즘 특성

1.2 결정 트리

1.2.1 수학적 표기법

하나의 일반적인 데이터 포인트를 다음과 같이 벡터 v로 정의한다.

    $$v = (x_1, x_2, ..., x_d)$$

여기서 $$x_i$$ 는 스칼라 특징을 나타낸다. 실제 응용에서 특징의 차원 $$d$$ 는 매우 큰 값을 갖는데, 심지어 무한대가 되기도 한다. 그러나 랜덤 트리 또는 랜덤 포레스트에서 $$v$$ 내의 $$d$$ 개의 모든 특징 원소들에 대해 미리 계산할 필요가 없으며, 필요한 기저(basis)에 있는 특징들만 취급하는 것이 일반적이다. 종종 특징을 가능한 모든 특징들의 집합으로부터 하나의 함수 $$\phi(v)$$ 는 관심 특징들의 부분집합을 선택하는 함수로, 다음과 같이 정의한다.

1.2.2 훈련과 테스트 과정

  • 훈련단계에서는 종단 노드에 대한 매개변수와 내부 노드와 관련 노드 분할 함수(split function)의 매개변수를 최적화하는 작업이 진행
  • 트리의 훈련 과정을 설명할 때, 훈련 데이터의 부분집합을 트리의 가지들과 연관시켜 생각하는 것이 편함.
  • 예를 들어, 노드 1에 도달하는 훈련 데이터의 부분집합을 $$S1$$ 이라고 하고, 노드 1의 왼쪽과 오른쪽의 자식 노드를 각각 $$S_1^R$$, $$S_1^R$$ 라고 하자. 이 때, 각 분할 노드 $$j$$ 는 다음과 같은 특성 관계식을 갖는다.$$$$$$S_j = S_j^L \cup S_j^R, S_j^L \cap S_j^R = \emptyset, S_j^L = S{2j+1}, Sj^R = S{2j+2},$$
  • 데이터 포인트 {v}의 훈련 집합 $$S_0$$ 및 실제 데이터 레이블(ground truth)이 주어졌을 때, 트리의 매개변수는 정의한 목적 함수를 최소화 하도록 선택된다.
  • 트리의 성장을 언제 멈출지 결정하기 위해 미리 정의된 여러가지 멈춤 조건이 적용된다. $$T$$ 개의 트리로 구성된 하나의 포레스트의 경우, 일반적으로 훈련 과정은 각 트리에 대해 독립적으로 $$T$$ 번 반복된다. 랜덤 트리 또는 포레스트에서 주목할 사실은 임의성(randomness)이 오직 훈련과정에서만 들어감.
  • 트리가 형성되고 고정되어 있다면, 테스트 단계에서는 완전히 결정적인 특성을 보임.
  • 테스트 단계에서는 이전에 본 적없는 데이터 포인트 $$v$$가 입력으로 주어졌을 때, 각 결정 트리는 사전에 정의된 많은 테스트 값을 계층적으로 적용한다.
  • 루트 노드에서 시작해, 각 노드의 분할 함수를 입력 데이터 v에 적용한다. 입력 데이터는 이진 테스트 결과에 따라 오른쪽 또는 왼쪽의 자식 노드로 보내진다. 이 과정은 입력 데이터 포인트가 단말 노드에 도달할 때까지 반복.

  • (TBD) 특징량으로 binary feature를 사용하는 것은 한계가 있었음, haar-like feature를 사용하여 분류를 시도함.

      • 1.2.3 정보 획득량과 섀넌 엔트로피

  • 훈련 단계에서 트리의 각 노드는 들어오는 데이터 포인트들을 최적으로 분리하기 위해 정보 획득량(information gain)을 측정 기준으로 사용한다.

  • 구체적으로 각 노드에서 정보획득량(신뢰, confidence)을 최대화하는 것이다. 정보 획득량은 다음과 같이 정의된다.

  • 여기서, $$S$$ 는 한 노드에 도달하는 데이터 집합을, $$S^i$$ 는 이 노드의 $$i \in \left{L, R\right}$$, 왼쪽 혹은 오른쪽 방향 자식 노드로 들어가는 데이터 집합을 나타낸다.($$S$$ 와 $$S^i$$ 의 관계식은 훈련과 테스트 과정 참조). 또한, $$\left|\cdot\right|$$ 와 $$H(S)$$ 는 각각 데이터 집합에 속한 데이터 개수와 섀넌 엔트로피(Shannon entropy)를 가리킨다.

  • 위 수식에서 볼 수 있듯이, 정보 획득량을 최대화하기 위해서는 결국 섀넌 엔트로피가 최소화 되어야 한다. 섀넌 엔트로피는 확률 변수의 조합으로 정보원(여기서는 $$S$$)에 대한 불확실성을 보여주는 것으로 아래와 같이 정의된다.

  • 여기서 c는 전체 부류(class) 집합을 나타내며, p(c)는 각 부류에 대한 확률 질량 함수이다.

1.3 랜덤 포레스트

  • 랜덤 포레스트의 가장 핵심적인 특징은 임의성(randomness)에 의해 서로 조금씩 다른 특성을 갖는 트리들로 구성된다는 점
  • 이 특징은 각 트리들의 예측(prediction) 들이 비상관화(decorrelation) 되게 하며, 결과적으로 일반화(generalization) 성능을 향상시킨다.
  • 또한, 임의화(randomization)는 포레스트가 노이즈가 포함된 데이터에 대해서도 강인하게 만들어 줌.
  • 임의화는 각 트리들의 훈련 과정에서 진행
  • 가장 널리 쓰는 방법은 bagging과 randomized node optimization
  • 두가지 방식이 서로 동시에 사용되어, 임의화 특성을 더욱 증진

1.3.1 배깅을 이용한 포레스트 구성

  • bagging은 bootstrap aggregating의 약자로, 부트스트랩(bootstrap)을 통해 조금씩 다른 훈련데이터에 대해 훈련된 기초 분류기(base learner)들을 결합시키는 방법이다.
  • 부트스트랩이란, 주어진 훈련 데이터에서 중복을 허용하여 원 데이터와 같은 크기의 데이터를 만드는 과정을 말함.
  • 배깅을 통해 랜덤 포레스트를 훈련시키는 과정은 다음과 같이 크게 3단계로 구성됨.

results matching ""

    No results matching ""