D054

Parellel Design of Decision Trees

의사결정나무에서 test 를 만들기 위해서는 많은 양의 계산이 필요합니다.
하나의 feature 에 대해서도 모든 트레이닝 데이터를 정렬해야하고
각각의 impurity 를 계산하여 최소가 되는 부분을 찾아야합니다.
이러한 작업은 다음과 같은 병렬처리를 적용하여 좀 더 빠르게 처리할 수 있습니다.

• 한 노드에서 모든 feature 들에 대해 병렬적으로 처리하여 분할을 찾을 수 있습니다.
• 동일 레벨에 있는 노드들은 병렬로 계산할 수 있습니다.
  모든 트레이닝 데이터들은 어떤 레벨에서든 하나의 노드에 도달 합니다.
  그러므로 각 레벨에서 전체 작업량은 거의 비슷하다고 볼 수 있습니다.
• feature 의 값에 따라 트레이닝 데이터를 그룹화하여 병렬에서 효율적으로 처리할 수 있습니다.
• 병렬처리는 정렬을 빠르게 합니다. $O(\log n)$ 으로 처리할 수 있습니다.

하나의 feature A 를 사용해서 하나의 노드를 설계하는 작업 상황을 가정해봅시다. (node-feature 쌍으로 병렬 처리되는)
그룹핑이나 정렬 후에 몇개의 누적 합을 계산해야합니다.
누적 합을 계산하는 것은 serial 처럼 보이지만, 이것도 병렬로 수행할 수 있습니다.
한번 누적합을 계산하면, 리스트 안의 각 맴버에 대해 필요한 비율이나 impurity 을 병렬로 계산할 수 있습니다.

누적합을 병렬로 계산해 봅시다.
숫자들의 리스트 $a_1,a_2,…,a_n$ 이 주어지고,
$x_i = \sum_{j=1}^i a_j,\ i=1,2,\dots ,n$ 에 대해 계산을 해야합니다.
$x_i$ 를 계산하기 위해 n 개의 스텝이 필요한 것 처럼 보이고,
n이 커지면 시간이 더 소요될 것 처럼 보이지만,
다음과 같이 divide-and-conquer 알고리즘을 사용하여 x에 대해 $O(\log n)$ 의 병렬로 계산할 수 있습니다.

BASIS
n=1일 때, $x_1=a_1$ 이다.

INDUCTION
n>1 이라면 a 의 리스트를 왼쪽 절반과 오른쪽 절반으로 최대한 균등하게 나눈다.
n 이 짝수이면 $a_1,a_2,\dots,a_{n/2}$와 $a_{n/2+1},a_{n/2+2},\dots , a_n$ 으로
홀수이면 $a_{\lfloor n/2 \rfloor}$ 와 $a_{\lceil n/2 \rceil} $ 로 나눕니다.

재귀 과정은 아래 그림과 같습니다.

이 알고리즘은 왼쪽과 오른쪽 반에 병렬적으로 적용합니다.
왼쪽 절반의 마지막 누적 합은($x_{n/2}$) 의 계산을 한번 수행하면,
오른쪽 절반의 누적합 각각에 이를 더해주면 됩니다.
예를들어, i 번째 결과가 오른쪽 절반에 있다면 $\sum_{j=n/2+1}^{i} a_j$ 가되고, 여기에 $x_{n/2}$ 를 더합니다.
이 식은 정확히 $\sum_{j=1}^{n/2+i} a_j$ 이 됩니다.

각 재귀 스텝마다, 병렬으로 한번의 덧셈만 필요합니다.
n이 2의 거듭 제곱 인 경우 재귀 단계의 각 작업해야하는 목록의 크기를 2로 나눕니다.
따라서 병렬로 수행하는 총 스텝의 수는 $1+ \log_2 n$입니다.
2의 거듭제곱이 아닌 경우 $1+ \lceil \log_2 n \rceil$ 이 됩니다.

Overfitting in Decision Tree

Node Pruning

의사결정트리를 만들 때, 많은 레벨을 사용해 각 leaf 노드가 pure 하게 만든다면 트레이닝 데이터에 오버피팅이 될 가능성이 큽니다.
다른 데이터를 사용해 검증을 하면 낮은 성능이 나오게 됩니다.
트리을 단순화하면 이러한 현상을 방지할 수 있습니다.

leaf 노드만 갖고 있는 노드 N 을 찾고, 그 N 을 그것의 자식노드(leaf) 로 바꿔서 트리를 수정합니다.
여기서 leaf는 클래스가 섞여있으므로, 그중에 더 많은 클래스를 output 으로 설정합니다.
이전과 새로운 트리의 에러률 사이에 차이가 조금 있으면, 노드 N 에서 오버피팅에 영향을 주었다고 기대할 수 있고, 전체 데이터에서의 속성을 나타내지 못했다고 볼 수 있습니다.
이런 경우 수정한, 더 단순한 트리를 사용합니다.
만약에 수정한 트리에서 에러률이 크게 올라갔다면, 이를 사용해선 안됩니다.
위와 같은 식으로 leaf 만 갖고 있는 노드들에 대해서 바꿔가면서 puring 을 수행하면 됩니다.

Decision Forest

많은 레벨을 가진 단일 트리는 낮은 레벨에서 오버피팅을 만드는 많은 노드가 있을 가능성이 있습니다.
pure 와 다른 방식으로 오버피팅을 처리하는 기법이 있습니다.
decision forest 라는 방식은 많은 트리를 사용해서 주어진 데이터가 속한 클래스에 voting 을 합니다.
여기서 각 트리는 랜덤이나 체계적으로 피쳐를 선택하여 생성하고, 레벨은 작게 만들도록 제한합니다. (한 두개 정도)
그래서 각 트리는 높은 impurity 를 갖지만, 그것들을 모으면 하나의 트리보다 테스트에서 더 높은 성능을 보입니다.
그리고 forest 는 tree 들을 병렬로해서 생성할 수 있기 때문에 빠르게 만들 수 있습니다.

output 은 decision forest 에 있는 모든 트리들의 결과를 모아서 제일 많은 클래스로 선택합니다.
혹은 각 트리에 대한 weight 를 학습시켜서 최종 결과를 고르는 방식도 있습니다.

트레이닝 데이터 $(x_1, y_1), (x_2, y_2),\dots, (x_n, y_n)$과 트리 $T_1, T_2, \dots,T_k$,가 있다고 가정합시다.
decision forest 에 $(x_i, y_i)$ 를 넣으면 각 트리에 대한 클래스 $c_i = [c_{i1}, c_{i2},\dots, c_{ik}]$ 를 얻습니다.
$x_i$ 의 실제 클래스에 대해 알고 있으므로,
새로운 트레이닝 세트 $(c_1, y_1), (c_2, y_2),\dots , (c_n, y_n)$ 을 만들 수 있습니다.
이 데이터를 퍼셉트론이나 SVM 등을 사용해서 학습시킬 수 있고,
학습에서 나온 가중치 w 를 사용하여 최종 클래스를 분류하는데 사용할 수 있습니다.